Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Árvores — FCC 2017

Algoritmos e Estrutura de DadosÁrvores
Código
fc038461
Banca
FCC
Órgão
TRE-SP
Ano
2017
Nível
Médio
Cargo
Técnico Judiciário – Programação de Sistemas
Considere que a eleição para prefeito de um município paulista produziu o seguinte resultado:CandidatoA-1504 votos, CandidatoB-7520 votos, CandidatoC-345551 votos, CandidatoD-517440 votos, CandidatoE-2329 votos, CandidatoF-11731 votos e CandidatoG-152 votos.Ao armazenar estes dados em uma árvore
  1. Abinária de busca, tendo como chave de inserção os nomes dos candidatos nesta ordem, resultará em uma árvore de altura mínima.
  2. Bbinária de busca, tendo como chave de inserção a quantidade de votos nesta ordem, o candidato vencedor ficará na raiz.
  3. Cbinária de busca perfeitamente balanceada, tendo como chave de inserção o nome do candidato, o candidato vencedor ficará na raiz.
  4. Dperfeitamente balanceada, resultará em uma árvore de altura 4.
  5. Ebinária de busca, tendo como chave de inserção a quantidade de votos nesta ordem, o candidato vencedor será localizado com 3 comparações.
Revelar gabarito e comentário

GabaritoC — binária de busca perfeitamente balanceada, tendo como chave de inserção o nome do candidato, o candidato vencedor ficará na raiz.

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 e balanceamento

Gabarito: letra C. Em uma árvore binária de busca perfeitamente balanceada, a raiz é o elemento mediano quando as chaves são ordenadas. Com 7 candidatos em ordem alfabética, a mediana é CandidatoD (4º de 7), que é exatamente o vencedor da eleição. As demais alternativas falham por não considerar as propriedades de inserção e balanceamento.

A banca testa a compreensão do comportamento de árvores binárias de busca (ABB) e do conceito de balanceamento perfeito. Em uma ABB comum, a raiz é o primeiro elemento inserido; já em uma árvore perfeitamente balanceada, a raiz é o elemento central da sequência ordenada.

Alternativa A — ❌ Incorreta

Afirma que inserir os nomes na ordem dada (A,B,C,D,E,F,G) em uma ABB resulta em altura mínima. Na verdade, essa ordem é crescente, gerando uma árvore degenerada (lista à direita) com altura máxima (6 arestas para 7 nós). Altura mínima seria 2, obtida apenas com balanceamento.

Alternativa B — ❌ Incorreta

Ao inserir os votos na ordem apresentada (1504, 7520, 345551, 517440, ...), o primeiro valor (1504) torna-se raiz. O vencedor (517440) é inserido posteriormente e não será raiz. Numa ABB a raiz é sempre o primeiro elemento inserido, não o de maior valor.

Alternativa C — ✅ Correta ⟵ GABARITO

Em uma árvore binária de busca perfeitamente balanceada, a raiz é o elemento mediano da sequência ordenada das chaves. Ordenando os nomes alfabeticamente, temos: A, B, C, D, E, F, G. A mediana (quarto elemento) é CandidatoD, que é o vencedor (517440 votos). Portanto, ele estará na raiz.

Alternativa D — ❌ Incorreta

Uma árvore perfeitamente balanceada com 7 nós tem altura 2 (considerando arestas: raiz nível 0, folhas nível 2). Altura 4 corresponderia a uma árvore com pelo menos 15 nós. O valor 4 está incorreto.

Alternativa E — ❌ Incorreta

Inserindo os votos na ordem dada, a ABB resultante é desbalanceada. O maior valor (517440) é inserido quarto e estará na extremidade direita. Para localizá-lo, são necessárias 4 comparações (com 1504, 7520, 345551 e finalmente 517440). A alternativa afirma 3 comparações, o que só seria possível em uma árvore balanceada.

Gabarito: letra C.

Link permanente: /questoes/fc038461