Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — COPEVE-UFAL 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg663986
Banca
COPEVE-UFAL
Órgão
IFAL
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Informática
Árvores binárias de busca são estruturas de dados dinâmicas utilizadas para armazenar e recuperar informações de forma eficiente. O desempenho das operações de busca, de inserção e de remoção depende diretamente da forma como a árvore se encontra estruturada.Ainda sobre árvores binárias de busca (ABB) e algoritmos de pesquisa de dados, dadas as afirmativas,I. Em uma árvore binária de busca balanceada, o custo de uma operação de pesquisa é proporcional ao logaritmo do número de elementos armazenados.II. Uma árvore binária de busca degenerada pode apresentar custo de pesquisa equivalente ao de uma busca sequencial em um vetor.III. Diferentemente das árvores binárias de busca, a busca binária em vetores ordenados não sofre impacto da ordem de inserção dos elementos.verifica-se que está/ão correta/s
AII, apenas.
BIII, apenas.
CI e II, apenas.
DI e III, apenas.
EI, II e III.
Revelar gabarito e comentário▾
GabaritoE — I, II e III.
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”.
Árvores Binárias de Busca (ABB) e Pesquisa
Gabarito: letra E. Todas as três afirmativas estão corretas. Em uma ABB balanceada, a busca é O(log n); em uma ABB degenerada (equivalente a uma lista ligada), a busca é O(n), similar à busca sequencial; já a busca binária em vetor ordenado não depende da ordem de inserção, apenas de o vetor estar ordenado.
A banca testa o entendimento do impacto da estrutura da árvore no desempenho das operações e a comparação com a busca binária em vetores.
Afirmativa
Correta?
Justificativa
I. Em ABB balanceada, custo de pesquisa é O(log n)
✅ Sim
Altura ≈ log₂(n) garante busca proporcional ao logaritmo do número de elementos
II. ABB degenerada pode ter custo O(n) como busca sequencial
✅ Sim
Inserções unidirecionais transformam a árvore em lista encadeada, resultando em busca linear
III. Busca binária em vetor ordenado não sofre impacto da ordem de inserção
✅ Sim
A ordenação do vetor é pré-requisito, mas a sequência de inserções não altera a estrutura de busca
Afirmativa I — ✅ Correta
Em uma árvore binária de busca balanceada (como AVL ou Rubro-Negra), a altura é mantida próxima de log₂(n). Assim, qualquer operação de busca percorre no máximo O(log n) nós. Esse é um resultado clássico de estruturas de dados.
Afirmativa II — ✅ Correta
Uma ABB degenerada é aquela em que as inserções ocorrem sempre no mesmo sentido (crescente ou decrescente), fazendo com que a árvore se torne uma lista encadeada. Nesse caso, a busca exige percorrer todos os elementos no pior caso, resultando em O(n), exatamente como a busca sequencial em um vetor.
Afirmativa III — ✅ Correta
A busca binária em vetores ordenados é feita sobre um conjunto já ordenado, independentemente da ordem em que os elementos foram inseridos (a ordenação pode ser feita a qualquer momento). Já em uma ABB, a ordem de inserção define a topologia da árvore, afetando diretamente o desempenho das buscas. Portanto, a afirmativa está correta.
NÃO CAIA NESSA!
A banca pode tentar confundir o candidato com afirmações parciais. Por exemplo, a afirmativa III parece contrastar ABB e busca binária, mas ambas são afetadas pela ordenação — a diferença está no momento em que a ordenação impacta. Na ABB, a ordem de inserção determina a estrutura; na busca binária, o vetor precisa estar ordenado, mas a ordem de inserção não influencia a busca em si.
Conclusão: As três afirmativas são verdadeiras. Portanto, a alternativa correta é a letra E (I, II e III).