Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Árvores — INSTITUTO AOCP 2023

Algoritmos e Estrutura de DadosÁrvores
Código
qq971017
Banca
INSTITUTO AOCP
Órgão
IF-MA
Ano
2023
Nível
Superior
Cargo
Analista De Tecnologia Da Informação - Desenvolvimento De Sistemas
Considere a seguinte afirmação sobre árvores binárias:Uma árvore binária completa é uma árvore binária em que todos os níveis, exceto talvez o último, estão completamente preenchidos, e todas as folhas no último nível estão o mais à esquerda possível.Tendo em vista uma árvore binária completa, assinale a alternativa correta.
  1. AA altura da árvore é sempre igual ao número de nós na árvore.
  2. BA árvore tem no máximo 2^(h+1) - 1 nós, em que h é a altura da árvore.
  3. CA árvore tem no mínimo 2^(h+1) - 1 nós, em que h é a altura da árvore.
  4. DA árvore tem exatamente 2^(h+1) - 1 nós, em que h é a altura da árvore.
  5. EA árvore tem no máximo 2^h - 1 nós, em que h é a altura da árvore.
Revelar gabarito e comentário

GabaritoD — A árvore tem exatamente 2^(h+1) - 1 nós, em que h é a altura da árvore.

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 completas: relação entre altura e número de nós

Gabarito oficial: letra D. A afirmativa de que uma árvore binária completa tem exatamente 2^(h+1)-1 nós é falsa segundo a definição padrão (a árvore pode ser imperfeita no último nível). O gabarito oficial, no entanto, considera D correta, o que indica que a banca provavelmente confunde "completa" com "perfeita" (full/perfect). Abaixo, a análise de cada alternativa com base na definição usual (h como número de arestas).

Alternativa A — ❌ Incorreta

A altura não é igual ao número de nós. Uma árvore de altura h (arestas) tem no máximo 2^(h+1)-1 nós, que é uma relação exponencial, não linear.

Alternativa B — ✅ Correta (definição usual com h em arestas)

O número máximo de nós em uma árvore binária completa de altura h (arestas) é 2^(h+1)-1, quando a árvore é perfeita. Se h for o número de níveis, o máximo seria 2^h-1.

Alternativa C — ❌ Incorreta

O número mínimo de nós em uma árvore completa de altura h (arestas) é 2^h (quando o último nível tem apenas um nó), e não 2^(h+1)-1.

Alternativa D — ❌ Incorreta (padrão) / ✅ (segundo gabarito)

Uma árvore binária completa não possui exatamente 2^(h+1)-1 nós, a menos que seja perfeita. O gabarito oficial, porém, marca D como correta – inconsistência com a definição do próprio enunciado.

Alternativa E — ❌ Incorreta (se h em arestas) / ✅ (se h em níveis)

Se h for o número de níveis, o máximo seria 2^h-1, o que tornaria E correta. Mas a banca adotou a fórmula com h+1.

Conclusão: O gabarito oficial é a letra D, mas essa resposta contradiz a definição de árvore binária completa fornecida. Para a prova, marque D conforme a banca; contudo, recomenda-se estudo aprofundado das definições de árvores binárias completas, cheias e perfeitas.

Link permanente: /questoes/qq971017