Questão nº 59
Questão de Tecnologia da Informação · CESGRANRIO BASA 01/2021 (nº 59)
A classe Java ArvNo, exibida abaixo, é usada para representar os nós de uma árvore binária.
package estruturas;
class ArvNo {
int info;
ArvNo esq=null,dir=null;
}
Ela é usada na implementação de uma árvore binária pela classe Arv, exibida a seguir.
package estruturas;
public class Arv {
private ArvNo raiz;
public Arv(){
}
public void exibe(){
percorre(raiz);
System.out.println("\n");
}
private void percorre(ArvNo r) {
if(r==null)
return;
percorre(r.dir);
percorre(r.esq);
System.out.print(r.info+" ");
}
}
Que árvore terá os valores de seus nós exibidos em ordem descendente quando for percorrida pelo método percorre(), definido na classe Arv?
- A
(alternativa correta) - B
- C
- D
- E
Resposta comentada
Gabarito Alternativa A
O método percorre() faz um percurso pós-ordem (primeiro filho direito, depois filho esquerdo, depois a raiz), imprimindo os valores nessa ordem. Para que a saída seja em ordem descendente (maior para menor), a árvore deve ser uma árvore binária de busca (ABB) com os maiores valores à direita e os menores à esquerda, pois assim o percurso (direita → esquerda → raiz) visita os nós do maior para o menor.
- (A) Correta: Esta é a árvore binária de busca correta (maiores à direita, menores à esquerda). O percurso pós-ordem (direita → esquerda → raiz) imprime os valores em ordem decrescente: 50, 40, 30, 20, 10.
- (B) Incorreta: Embora seja uma ABB, o percurso pós-ordem (direita → esquerda → raiz) imprime os valores em ordem crescente (10, 20, 30, 40, 50), pois os menores estão à direita e os maiores à esquerda, invertendo a ordem.
- (C) Incorreta: Não é uma ABB (valores não seguem a regra de ordenação), então o percurso pós-ordem não produzirá uma sequência ordenada.
- (D) Incorreta: É uma ABB, mas o percurso pós-ordem (direita → esquerda → raiz) imprime os valores em ordem crescente (10, 20, 30, 40, 50), pois os menores estão à direita.
- (E) Incorreta: Não é uma ABB (valores fora de ordem), então o percurso pós-ordem não produzirá uma sequência ordenada.
Armadilha da banca (distrator mais tentador): A alternativa (B) parece correta porque também é uma ABB, mas o percurso pós-ordem (direita → esquerda → raiz) imprime os valores em ordem crescente (10, 20, 30, 40, 50), não descendente. A banca inverte a posição dos maiores/menores para confundir quem não percebe que a ordem de visitação (direita primeiro) exige que os maiores estejam à direita.
Fonte: CESGRANRIO BASA 01/2021 Técnico Científico - Área de Formação: Tecnologia da Informação. Reproduzida para fins de estudo.