Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IBGP 2026

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qg703943
Banca
IBGP
Órgão
Câmara de Porto Velho - RO
Ano
2026
Nível
Médio
Cargo
Técnico em Informática
Um índice em memória para autocompletar nomes de documentos utiliza uma estrutura de árvore para buscas eficientes. O analista comparou árvore binária de busca (BST) com árvore balanceada.É CORRETO afirmar que:
  1. ABST sempre garante O(log n) no pior caso, sem balanceamento.
  2. BÁrvores balanceadas podem degradar para O(n) sempre.
  3. CBalanceamento é irrelevante para desempenho de busca.
  4. DUma BST sem balanceamento pode degradar para O(n) no pior caso; balanceamento ajuda a manter O(log n).
  5. EÁrvores não servem para busca, apenas para ordenação.
Revelar gabarito e comentário

GabaritoD — Uma BST sem balanceamento pode degradar para O(n) no pior caso; balanceamento ajuda a manter O(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”.

Árvores de busca: BST vs balanceada

Gabarito: Letra D. Uma BST sem balanceamento pode degenerar para uma lista ligada, resultando em O(n) no pior caso. Árvores balanceadas, como AVL ou Rubro-Negra, mantêm altura logarítmica, garantindo O(log n) nas operações de busca.

Árvores de busca
  • 1BST (sem balanceamento)
    • Melhor caso: O(log n)
    • Pior caso: O(n) (degenera em lista)
  • 2Balanceada (AVL, Rubro-Negra)
    • Garante O(log n) no pior caso
    • Balanceamento evita degeneração
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que BST garante O(log n) no pior caso sem balanceamento. Na verdade, uma BST pode degenerar para uma lista (ex.: inserções ordenadas), levando a O(n).

Alternativa B — ❌ Incorreta

Diz que árvores balanceadas podem sempre degradar para O(n). O balanceamento impede essa degradação; árvores balanceadas mantêm O(log n) no pior caso.

Alternativa C — ❌ Incorreta

Afirma que balanceamento é irrelevante. O balanceamento é crucial para evitar a degeneração e garantir desempenho previsível O(log n).

Alternativa D — ✅ Correta ⟵ GABARITO

Reconhece que uma BST sem balanceamento pode ter pior caso O(n) e que o balanceamento mantém O(log n), descrevendo corretamente as características.

Alternativa E — ❌ Incorreta

Afirma que árvores não servem para busca, apenas para ordenação. Árvores de busca (BST, balanceadas) são projetadas justamente para busca eficiente.

Gabarito: Letra D.

Link permanente: /questoes/qg703943