Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IV - UFG 2017
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq253360
Banca
IV - UFG
Órgão
Fundação Unirg
Ano
2017
Nível
Superior
Cargo
CS-UFG - - Analista de Sistemas
A altura de um nó em uma árvore binária é a distância entre o nó e o seu descendente mais afastado. A altura de uma árvore binária é a altura da raiz da árvore. Se a árvore possui somente o nó raiz, então sua altura é 0 (zero). Dentre as árvores binárias que possuem sete nós, a maior altura de árvore possível é:
A5
B6
C7
D8
Revelar gabarito e comentário▾
GabaritoB — 6
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: Altura Máxima
Gabarito: letra B (altura = 6). A altura de uma árvore binária é definida como o número de arestas no caminho mais longo da raiz até uma folha. Para uma árvore com apenas a raiz, a altura é 0 (zero). Para maximizar a altura com um número fixo de nós, a árvore deve ser degenerada — ou seja, cada nó possui no máximo um filho, formando uma cadeia linear. Nessa configuração, a altura é dada por n – 1, onde n é o número de nós. Assim, com 7 nós, a maior altura possível é 6.
Nº de nós
Altura máxima (cadeia)
1
0
2
1
3
2
…
…
7
6
11 nóaltura 0
22 nósaltura 1
33 nósaltura 2
44 nósaltura 3
55 nósaltura 4
66 nósaltura 5
77 nósaltura 6
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Altura 5 seria obtida com 6 nós em cadeia, ou com 7 nós em uma configuração menos alongada (por exemplo, um nó com dois filhos). Como temos exatamente 7 nós, é possível ir além (altura 6).
Alternativa B — ✅ Correta ⟵ GABARITO
A altura máxima para 7 nós é 6, conforme explicado: árvore degenerada com 7 nós → 6 arestas.
Alternativa C — ❌ Incorreta
Altura 7 exigiria 8 nós em cadeia (arestas = nós – 1). Com 7 nós, o máximo de arestas é 6, portanto altura 7 é impossível.
Alternativa D — ❌ Incorreta
Altura 8 também é impossível com 7 nós, pois exigiria 9 nós. A altura máxima cresce linearmente com o número de nós (máximo = nós – 1).