Questão 70 · Informática: Programação e algoritmos
Considere que a função em linguagem C a seguir recebe como parâmetro de entrada a raiz r de uma árvore binária. voidpercorre (arvore * r) { if (r!= NULL) { percorre(r->esq); printf("%d\n", r->conteudo); percorre(r->dir); } } Considere ainda que, para qualquer nó x, x->esq é a raiz da subárvore esquerda de x, que x->dir é a raiz da subárvore direita de x e que x->conteudo retorna o conteúdo de um nó.
A respeito da função descrita acima, assinale a afirmativa correta.
- A) Ela imprime somente os nós folha da árvore.
- B) Ela imprime somente os nós à esquerda da raiz “r” da árvore.
- C) Ela imprime primeiramente o conteúdo da raiz da árvore e depois a subárvore direita.
- D) Ela imprime primeiramente a subárvore esquerda da raiz, na ordem esquerda‐raiz‐direita.
- E) Ela imprime primeiramente o conteúdo da raiz da árvore e depois a subárvore esquerda.
Marque a alternativa correta:
Gabarito: D
Gabarito definitivo divulgado pela banca FGV (CONDER 2013).
Comentário
Gabarito: D.
A função percorre a árvore em ordem simétrica (in-order): primeiro chama a si mesma na subárvore esquerda, depois imprime o conteúdo da raiz, e por fim percorre a subárvore direita. A ordem de impressão é esquerda, raiz, direita.
Rastreamento em passos curtos: em uma árvore com raiz 2 e filhos 1 e 3, a saída é 1, 2, 3. Primeiro percorre o nó 1, que imprime 1; depois imprime a raiz 2; depois percorre o nó 3, que imprime 3.
Por que as outras estão erradas:
- (A) a função imprime todos os nós, e não só as folhas.
- (B) a função também imprime a raiz e a subárvore direita.
- (C) a raiz não é impressa primeiro; ela sai depois da subárvore esquerda.
- (E) pelo mesmo motivo, a subárvore esquerda vem antes da raiz.
Dica de prova: observe onde está o printf em relação às chamadas recursivas. No meio indica ordem simétrica; no início, pré-ordem; no fim, pós-ordem.
Fundamentos: Percurso em ordem simétrica (in-order) de árvores binárias · Recursão em estruturas de árvore
Comentário gerado pela Cravei IA a partir do enunciado e do gabarito definitivo divulgado pela banca, e conferido por uma verificação automática. A IA pode errar: o gabarito oficial sempre prevalece.
Fonte: prova FGV CONDER 2013 (Tecnologia da Informação, Processamento de Dados, Ciência da Computação, Engenharia da Computação, Engenharia de Sistemas ou Análise de Sistemas), questão 70, com o gabarito definitivo da banca. Comentário: Equipe Cravei · como fazemos e revisamos.