Árvores binárias de busca são estruturas de dados dinâmicas ...

Próximas questões
Com base no mesmo assunto
Q3953508
Algoritmos e Estrutura de Dados Estrutura de Dados ,
Ano: 2026 Banca: COPEVE-UFAL Órgão: IFAL Prova: COPEVE-UFAL - 2026 - IFAL - Professor EBTT - Informática |
Q3953508 Algoritmos e Estrutura de Dados
Á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
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Gabarito: E

Fundamento decisivo: O critério decisivo era comparar a altura da estrutura com o custo de busca: em ABB, a pesquisa acompanha a altura da árvore, e isso basta para validar as três assertivas propostas.

Tema central: Custo de busca
Análise das alternativas
A
Errada
Incorreta porque mantém apenas II e exclui I e III. Isso contraria os critérios da questão: ABB balanceada tem pesquisa O(log n), e a busca binária em vetor ordenado não depende da ordem de inserção.
B
Errada
Incorreta porque mantém apenas III e exclui I e II. Mas I é verdadeira porque a pesquisa em ABB balanceada acompanha a altura logarítmica, e II é verdadeira porque a ABB degenerada pode ter altura linear.
C
Errada
Incorreta porque exclui III. A afirmativa III está correta, pois a busca binária considera o vetor já ordenado e não carrega efeito da ordem histórica de inserção sobre o procedimento de busca.
D
Errada
Incorreta porque exclui II. Essa exclusão erra ao desconsiderar que uma ABB degenerada pode se comportar como uma estrutura linear, levando a custo de pesquisa equivalente ao de busca sequencial.
E
Certa
A alternativa E está certa porque I, II e III são verdadeiras. Em ABB balanceada, a altura é da ordem de log n, então o custo de pesquisa também é logarítmico. Em ABB degenerada, a altura pode chegar a n, tornando a busca equivalente, em custo, à busca sequencial. Já a busca binária em vetor ordenado opera sobre o arranjo final já ordenado e não depende da ordem histórica de inserção dos elementos.
Pegadinha da questão
A confusão real era tratar como universais propriedades que dependem da forma da estrutura: I vale para ABB balanceada, não para qualquer ABB; II fala em equivalência de custo linear, não de estrutura; e III não discute inserção em vetor, mas o fato de a busca binária no vetor já ordenado não depender da ordem histórica de inserção.
Dica para questões semelhantes
  • Em ABB, verifique primeiro a altura da árvore; o custo de busca acompanha essa altura.
  • Separe ABB balanceada de ABB genérica: O(log n) não vale automaticamente para toda árvore binária de busca.
  • Quando a estrutura degenera, compare o pior caso com percurso linear.
  • Em vetor ordenado, avalie a busca binária pelo arranjo final ordenado, não pela ordem em que os dados entraram.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Questões de assuntos semelhantes

Provas relacionadas