Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FCC 2018
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fc044548
Banca
FCC
Órgão
DPE-AM
Ano
2018
Cargo
Assistente Técnico de Defensoria - Programador
Certo documento possui 1 milhão de palavras não repetidas e foi editado em um editor de textos. Considerando que o editor de textos utiliza uma Árvore Binária de Busca − ABB de altura mínima para armazenar as palavras digitadas de forma a facilitar sua localização, para se localizar qualquer palavra nesta estrutura de dados serão necessárias, no máximo,
A1 milhão de comparações.
B20 comparações.
C32 comparações.
Dlog₁₀1000000 comparações.
E2 milhões de comparações.
Revelar gabarito e comentário▾
GabaritoB — 20 comparações.
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”.
Árvore Binária de Busca (ABB) — Altura mínima e número de comparações
Gabarito: letra B. Em uma ABB de altura mínima (balanceada), o número máximo de comparações para localizar um elemento é igual à altura da árvore, que é aproximadamente ⌈log₂(n)⌉. Para n = 1.000.000, log₂(1.000.000) ≈ 19,93, o que resulta em no máximo 20 comparações.
A questão testa o conceito de que uma árvore binária balanceada tem altura logarítmica na base 2. A altura mínima de uma ABB com n nós é ⌊log₂(n)⌋ + 1 (considerando raiz no nível 1). Como a busca percorre um caminho da raiz até a folha, o número de comparações é igual à altura.
1n = 1.000.000 nós
2Altura mínima = ⌈log₂(n)⌉
3log₂(1.000.000) ≈ 19,93
4Máx. 20 comparações
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que seriam necessárias 1 milhão de comparações. Isso ocorreria apenas se a árvore estivesse degenerada (praticamente uma lista encadeada), mas a questão especifica altura mínima, ou seja, a árvore é balanceada, o que reduz drasticamente a altura.
Alternativa B — ✅ Correta ⟵ GABARITO
Correta. Conforme explicado, com 1 milhão de elementos, a altura mínima de uma ABB é 20 (pois 2¹⁹ = 524.288 < 1.000.000 ≤ 2²⁰ = 1.048.576). Portanto, no máximo 20 comparações.
Alternativa C — ❌ Incorreta
32 comparações corresponderiam a uma altura de 32, que suporta até 2³² − 1 ≈ 4,3 bilhões de nós. Para 1 milhão, 20 já é suficiente; 32 é um exagero, embora funcione, mas a questão pede o máximo necessário, que é o menor valor que atende ao número de nós — e esse valor é 20.
Alternativa D — ❌ Incorreta
Propõe log₁₀(1.000.000) = 6 comparações. Essa é uma pegadinha clássica: a base do logaritmo em árvores binárias é 2, não 10. O logaritmo na base 10 subestima o número de comparações. Se a árvore fosse uma busca ternária (base 3), faria sentido usar log₃, mas em ABB a base é 2.
Alternativa E — ❌ Incorreta
2 milhões de comparações não tem relação alguma com árvores balanceadas. Seria um valor absurdo, maior até mesmo que o número de elementos.
NÃO CAIA NESSA!
A banca explora a confusão entre logaritmo base 2 e base 10. O candidato pode calcular log₁₀(1.000.000) = 6 e achar que a alternativa D está correta, mas o correto é log₂. Lembre-se: em árvore binária, o crescimento é exponencial na base 2, então a altura é o logaritmo na base 2 do número de nós.
PEGA ESSA DICA!
Para n elementos, a altura mínima de uma ABB é ⌈log₂(n+1)⌉ (se considerar raiz nível 1). Uma forma rápida é encontrar a menor potência de 2 que seja ≥ n+1. Exemplo: n = 1.000.000 → 2²⁰ = 1.048.576 ≥ 1.000.001 → altura = 20.