Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESGRANRIO 2018

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
cg012200
Banca
CESGRANRIO
Órgão
Petrobras
Ano
2018
Nível
Superior
Cargo
Analista de Sistemas Júnior - Processos de Negócio
A sequência de chaves 20 – 30 – 25 – 31 – 12 – 15 – 8 – 6 – 9 – 14 – 18 é organizada em uma árvore binária de busca. Em seguida, a árvore é percorrida em pré-ordem.Qual é a sequência de nós visitados?
  1. A6 – 9 – 8 – 14 – 18 – 15 – 12 – 25 – 31 – 30 – 20
  2. B20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31
  3. C6 – 8 – 9 – 12 – 14 – 15 – 18 – 20 – 25 – 30 – 31
  4. D20 – 30 – 31 – 25 – 12 – 15 – 18 – 14 – 8 – 9 – 6
  5. E6 – 8 – 9 – 14 – 15 – 18 – 12 – 25 – 30 – 31 – 20
Revelar gabarito e comentário

GabaritoB — 20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31

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

Construção e percurso pré-ordem em árvore binária de busca

Gabarito: letra B. A sequência correta da visita em pré-ordem é: 20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31, conforme a construção da árvore binária de busca a partir das chaves fornecidas.

A questão exige dois passos: (1) montar a árvore binária de busca (ABB) inserindo as chaves na ordem dada e (2) percorrê-la em pré-ordem (raiz → esquerda → direita).

Construção da ABB

Inserções sucessivas:

  • 20: raiz

  • 30: >20 → direita

  • 25: >20 → direita, <30 → esquerda de 30

  • 31: >20 → direita, >30 → direita de 30

  • 12: <20 → esquerda

  • 15: <20 → esquerda, >12 → direita de 12

  • 8: <20 → esquerda, <12 → esquerda de 12

  • 6: <20 → esquerda, <12 → esquerda, <8 → esquerda de 8

  • 9: <20 → esquerda, <12 → esquerda, >8 → direita de 8

  • 14: <20 → esquerda, >12 → direita, <15 → esquerda de 15

  • 18: <20 → esquerda, >12 → direita, >15 → direita de 15

Árvore resultante:

        20
       /  \
     12    30
    /  \   / \
   8   15 25 31
  / \  / \
 6  9 14 18

Percurso pré-ordem

Pré-ordem: visita a raiz, depois subárvore esquerda (recursivamente), depois subárvore direita.

Sequência:

  1. 20

  2. Subárvore esquerda de 20: 12

    • Subárvore esquerda de 12: 8

      • Subárvore esquerda de 8: 6 (sem filhos)

      • Subárvore direita de 8: 9 (sem filhos)

    • Subárvore direita de 12: 15

      • Subárvore esquerda de 15: 14

      • Subárvore direita de 15: 18

  3. Subárvore direita de 20: 30

    • Subárvore esquerda de 30: 25

    • Subárvore direita de 30: 31

Resultado: 20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31.

Análise das alternativas

  1. 120 (raiz)
  2. 212 (esquerda)
  3. 38 (esquerda)
  4. 46 (esquerda)
  5. 59 (direita)
  6. 615 (direita)
  7. 714 (esquerda)
  8. 818 (direita)
  9. 930 (direita)
  10. 1025 (esquerda)
  11. 1131 (direita)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

A sequência começa com 6, que é a última visita da subárvore esquerda. Isso parece um percurso pós-ordem (esquerda → direita → raiz) mal aplicado, mas não é exato: em pós-ordem a raiz (20) seria a última, e aqui aparece 20 no final. Na verdade, a ordem apresentada não corresponde a nenhum percurso padrão.

Alternativa B — ✅ Correta ⟵ GABARITO

Exatamente a sequência calculada.

Alternativa C — ❌ Incorreta

Sequência estritamente crescente: 6, 8, 9, 12, 14, 15, 18, 20, 25, 30, 31. Esse é o percurso em ordem simétrica (esquerda → raiz → direita), não pré-ordem.

Alternativa D — ❌ Incorreta

Começa com 20, mas vai para a subárvore direita (30) antes de terminar a esquerda. Isso viola a pré-ordem (que exige visitar toda a esquerda antes da direita). A sequência parece misturar pré-ordem com algumas inserções aleatórias.

Alternativa E — ❌ Incorreta

Totalmente desordenada. Não segue nenhum padrão de percurso de árvore binária.

NÃO CAIA NESSA!

A banca coloca a alternativa C (ordem simétrica) como um distrator atraente: muitos confundem pré-ordem com ordem crescente. Lembre-se: pré-ordem começa com a raiz e depois desce pela esquerda; já a ordem simétrica produz uma sequência ordenada.

PEGA ESSA DICA!

Para resolver questões assim, desenhe a árvore passo a passo. Depois, aplique o percurso pedido escrevendo a sequência de nós visitados. Treine os três percursos principais: pré-ordem, ordem simétrica e pós-ordem.

Gabarito: letra B

Link permanente: /questoes/cg012200