Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FCC 2015
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fc020089
Banca
FCC
Órgão
MANAUSPREV
Ano
2015
Nível
Superior
Cargo
Analista Previdenciário - Tecnologia da Informação
Considere que a Manausprev armazena os nomes dos beneficiários de aposentadorias em uma Árvore Binária de Busca - ABB. Ao se armazenar, nesta ordem, os nomes Marcos, José, Carolina, Paula, Rui, Pedro e Maria, a ABB resultante
Aé perfeitamente balanceada.
Btem altura 3, que corresponde à altura mínima para armazenar os 7 nomes.
Cpossui como folhas os nomes Rui e Maria.
Drequer no máximo 3 comparações para localizar qualquer um dos 7 nomes.
Erequer no máximo 4 comparações para localizar qualquer um dos 7 nomes.
Revelar gabarito e comentário▾
GabaritoE — requer no máximo 4 comparações para localizar qualquer um dos 7 nomes.
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) – Inserção e Altura
Gabarito: letra E. Ao inserir os nomes na ordem dada (Marcos, José, Carolina, Paula, Rui, Pedro, Maria), a árvore resultante tem altura 3 (arestas) e, portanto, o número máximo de comparações para localizar qualquer elemento é altura + 1 = 4. As demais alternativas são falsas: a árvore não é perfeitamente balanceada (A), altura 3 não é a mínima (B), as folhas são Carolina, Pedro e Maria (C) e o máximo são 4 comparações, não 3 (D).
Construção passo a passo da ABB
A inserção segue a regra: valores menores vão para a subárvore esquerda; maiores, para a direita (ordem alfabética).
Marcos – raiz.
José – menor que Marcos → esquerda de Marcos.
Carolina – menor que José → esquerda de José.
Paula – maior que Marcos → direita de Marcos.
Rui – maior que Paula → direita de Paula.
Pedro – maior que Marcos, maior que Paula, menor que Rui → esquerda de Rui.
Maria – maior que Marcos, menor que Paula → esquerda de Paula.
Árvore final (representação horizontal):
Marcos
/ \
José Paula
/ / \
Carolina Maria Rui
/
Pedro
Análise das alternativas
Alternativa A — ❌ Incorreta
A árvore não é perfeitamente balanceada (completa) pois existem nós com apenas um filho (José, Rui). Embora os fatores de balanceamento estejam dentro de -1 a 1 (AVL), o termo "perfeitamente balanceada" geralmente exige que todas as folhas estejam no mesmo nível ou no máximo com diferença de 1 nível, o que não ocorre aqui (Carolina no nível 2, Pedro no nível 3).
Alternativa B — ❌ Incorreta
A altura da árvore é 3 (arestas), mas a altura mínima para 7 nós é 2 – uma árvore binária completa com 7 nós tem altura 2 (por exemplo, raiz + dois níveis de nós preenchidos). Portanto, 3 não é a altura mínima.
Alternativa C — ❌ Incorreta
As folhas (nós sem filhos) são Carolina, Pedro e Maria. Rui possui filho esquerdo (Pedro), logo não é folha.
Alternativa D — ❌ Incorreta
O número máximo de comparações para localizar um elemento é igual à altura da árvore + 1. Como a altura é 3, o máximo é 4 comparações (ex.: para encontrar Pedro, compara-se com Marcos, Paula, Rui e Pedro). A alternativa afirma 3 comparações, o que é insuficiente.
Alternativa E — ✅ Correta ⟵ GABARITO
Com altura 3, o pior caso de busca exige 4 comparações. De fato, qualquer nome requer no máximo 4 comparações (nível 0: raiz; nível 1; nível 2; nível 3).
PEGA ESSA DICA!
Em ABB, o número máximo de comparações é a altura da árvore + 1. Para calcular a altura mínima teórica com n nós, use ⌊log₂n⌋ (considerando arestas). Na questão, com n=7, altura mínima = 2, mas a árvore construída tem altura 3 por causa da ordem de inserção.