Algoritmos e Estrutura de Dados · UFLA · 2025 | Questão sqc-qg619874

Algoritmos e Estrutura de DadosEstrutura de Dados

Código: qg619874
Banca: UFLA
Órgão: UFLA
Ano: 2025
Nível: Superior

Cargo: Analista em Tecnologia da Informação

Uma Árvore Binária é uma árvore vazia (sem nós) ou é uma árvore com um nó raiz conectado a um par de árvores binárias, denominadas subárvore esquerda e subárvore direita desse nó.Adaptado de ZIVIANI, N. Projeto de algoritmos: com implementações em JAVA e C++. Porto Alegre: +A Educação – Cengage Learning Brasil, 2012.Uma Árvore de Busca Binária (ABB) é um caso especial de uma árvore binária, em que, para cada nó, a seguinte propriedade é verdadeira: todos os registros com chaves menores do que a chave deste nó estão em sua subárvore esquerda e todos os registros com chaves maiores estão em sua subárvore direita. O caminhamento em uma ABB é uma forma sistemática de “visitar” todos os nós dessa árvore. Há três métodos bem conhecidos para realizar esse caminhamento: 1) pré-ordem, 2) em-ordem e 3) pós-ordem.Considere que os seguintes registros numéricos (50, 30, 70, 20, 40, 10, 35, 60, 80, 65, 5) foram inseridos em uma ABB inicialmente vazia, registro a registro, da esquerda para a direita.O caminhamento pré-ordem irá processar os registros dessa árvore na seguinte ordem:

A5, 10, 20, 30, 35, 40, 50, 60, 65, 70, 80
B5, 10, 20, 35, 40, 30, 65, 60, 80, 70, 50
C50, 30, 20, 10, 5, 40, 35, 70, 60, 65, 80
D50, 70, 65, 60, 80, 40, 35, 30, 20, 10, 5

Revelar gabarito e comentário

GabaritoC — 50, 30, 20, 10, 5, 40, 35, 70, 60, 65, 80

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”.

Árvore de Busca Binária (ABB) — Caminhamento Pré-Ordem

Gabarito: letra C. Construindo a ABB com as inserções na ordem dada (50,30,70,20,40,10,35,60,80,65,5) e aplicando o percurso pré-ordem (visita a raiz, depois subárvore esquerda, depois direita), obtém-se exatamente a sequência 50, 30, 20, 10, 5, 40, 35, 70, 60, 65, 80.

A questão testa a diferença entre os três percursos clássicos em árvores binárias. Na pré-ordem, a ordem de visita é: raiz → subárvore esquerda (recursivamente) → subárvore direita. Já na em-ordem (ordem simétrica) os elementos são visitados em ordem crescente (esquerda → raiz → direita), e na pós-ordem (esquerda → direita → raiz).

Alternativa A — ❌ Incorreta

A sequência apresentada (5,10,20,30,35,40,50,60,65,70,80) corresponde ao caminhamento em-ordem (visita ordenada crescente), não ao pré-ordem.

Alternativa B — ❌ Incorreta

Essa ordem (5,10,20,35,40,30,65,60,80,70,50) é o resultado do caminhamento pós-ordem: percorre-se a subárvore esquerda, depois a direita e, por fim, a raiz. Não é pré-ordem.

Alternativa C — ✅ Correta ⟵ GABARITO

Sequência exata do pré-ordem a partir da árvore construída: 50, 30, 20, 10, 5, 40, 35, 70, 60, 65, 80. Confirma-se com a definição do percurso.

Alternativa D — ❌ Incorreta

A ordem 50,70,65,60,80,40,35,30,20,10,5 seria obtida se visitássemos primeiro a raiz, depois a subárvore direita (não a esquerda) e depois a esquerda – uma variação incorreta do pré-ordem.

NÃO CAIA NESSA!

O mais comum é confundir pré-ordem com em-ordem (alternativa A, ordenada) ou pós-ordem (alternativa B). Memorize: pré = raiz antes dos filhos; em = raiz entre os filhos; pós = raiz depois dos filhos.

Gabarito: letra C

Link permanente: /questoes/qg619874