Questão de Algoritmos e Estrutura de Dados — Algoritmos — Instituto Consulplan 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg295018
Banca
Instituto Consulplan
Órgão
Prefeitura de Cacoal - RO
Ano
2024
Nível
Superior
Cargo
Analista de Sistemas
Heapsort é um algoritmo de ordenação baseado na estrutura de dados heap. Sobre as características desse algoritmo de ordenação, assinale, a afirmativa correta.
AHeapsort é um algoritmo de ordenação estável.
BO tempo de execução do Heapsort no pior caso é O(n log n).
CHeapsort é um algoritmo que não pode ser implementado em uma estrutura de árvore.
DHeapsort sempre utiliza espaço adicional, proporcional ao número de elementos na lista a ser ordenada.
Revelar gabarito e comentário▾
GabaritoB — O tempo de execução do Heapsort no pior caso é O(n log n).
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Heapsort
Gabarito: letra B. O Heapsort possui complexidade de tempo O(n log n) no pior caso, sendo um algoritmo in-place (não requer espaço extra proporcional ao número de elementos) e instável (não é estável). A afirmativa B é a única correta.
A banca testa o conhecimento das propriedades fundamentais do Heapsort. Vamos analisar cada alternativa.
Afirma que o Heapsort é estável. Na verdade, o Heapsort não é estável, pois a operação de heapify pode trocar a ordem relativa de elementos iguais.
Alternativa B — ✅ Correta ⟵ GABARITO
O tempo de execução do Heapsort no pior caso é O(n log n), assim como no caso médio e no melhor caso. Essa é uma das suas principais vantagens em relação a algoritmos como o Quicksort (que pode ter pior caso O(n²)).
Alternativa C — ❌ Incorreta
Diz que o Heapsort não pode ser implementado em uma estrutura de árvore. Na verdade, o Heapsort é baseado em uma heap, que é uma árvore binária (completa). Embora a implementação comum use um vetor, a estrutura lógica é uma árvore.
Alternativa D — ❌ Incorreta
Afirma que o Heapsort sempre utiliza espaço adicional proporcional ao número de elementos. O Heapsort é in-place: a ordenação ocorre no próprio vetor, utilizando apenas O(1) de espaço extra (além do array de entrada), independentemente do tamanho N.
Conclusão: A única alternativa correta é a letra B.