GabaritoC — 3.
Gabarito: letra C. Uma árvore binária completa de altura (h) (medida em número de arestas da raiz até a folha mais distante) pode conter entre (2^h) e (2^{h+1}-1) nós. Substituindo (h) pelos valores das alternativas, obtém-se:
Alternativa | Altura (h) | Intervalo de nós possíveis | 15 nós encaixa? |
|---|---|---|---|
A | 1 | ([2,3]) | Não |
B | 2 | ([4,7]) | Não |
C | 3 | ([8,15]) | Sim |
D | 4 | ([16,31]) | Não |
E | 5 | ([32,63]) | Não |
A altura (h=3) é a única que comporta 15 nós (limite máximo do intervalo). Portanto, a resposta é a alternativa C.
Altura 1 corresponderia a uma árvore com no máximo 3 nós, insuficiente para 15.
Altura 2 comporta no máximo 7 nós, também insuficiente.
Altura 3 admite de 8 a 15 nós, sendo 15 o valor exato do limite superior. Uma árvore binária completa com 15 nós é perfeita (todos os níveis completamente preenchidos).
Altura 4 requer no mínimo 16 nós; com 15 nós a árvore teria altura 3, não 4.
Altura 5 requer ao menos 32 nós, muito acima de 15.
Lembre-se da relação entre altura (h) (arestas) e número de nós (n) em uma árvore binária completa: (2^h \leq n \leq 2^{h+1}-1). Se a altura fosse medida em níveis (número de nós no caminho), a fórmula seria (2^{h' -1} \leq n \leq 2^{h'} -1), com (h' = h+1); mas a banca CESPE normalmente adota a definição de altura como número de arestas (raiz com altura 0). Verifique qual convenção a questão utiliza.
Link permanente: /questoes/ce134523