Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADESP 2021

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qq634220
Banca
FADESP
Órgão
Câmara de Marabá - PA
Ano
2021
Nível
Médio
Cargo
Técnico em Processamento de Dados
Seja T uma árvore balanceada do tipo AVL (Adelson-Velski e Landis) vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pré-ordem é
  1. A10, 8, 5, 7, 12, 11 e 13.
  2. B10, 7, 5, 8, 12, 11 e 13.
  3. C5, 7, 8, 10, 11, 12 e 13.
  4. D5, 8, 7, 11, 13, 12 e 10.
  5. E5, 10, 12, 8, 7, 11 e 13.
Revelar gabarito e comentário

GabaritoB — 10, 7, 5, 8, 12, 11 e 13.

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 AVL e percurso pré-ordem

Gabarito: letra B. A sequência correta do percurso pré-ordem (raiz, esquerda, direita) da árvore AVL após as inserções dos elementos 5, 10, 12, 8, 7, 11 e 13, nessa ordem, é 10, 7, 5, 8, 12, 11, 13.

Para chegar a esse resultado, é necessário construir a árvore AVL passo a passo, aplicando rotações sempre que o fator de balanceamento de algum nó se tornar 2 ou -2.

Construção da árvore AVL:

  1. Inserir 5: árvore vazia → raiz 5 (fb=0).

  2. Inserir 10: 10 > 5 → direita de 5. Árvore: 5 (dir:10). fb(5)=1 (ok).

  3. Inserir 12: 12 > 10 → direita de 10. fb(10)=1, fb(5)=2 (desbalanceado!). Rotação simples à esquerda: 10 vira raiz, 5 vira filho esquerdo, 12 filho direito. Árvore:

    ```

    10

    / \

    5 12

    ```

  4. Inserir 8: 8 < 10 → esquerda; 8 > 5 → direita de 5. Árvore:

    ```

    10

    / \

    5 12

    \

    8

    ```

    fb(5)=1, fb(10)=-1 (ok).

  5. Inserir 7: 7 < 8 → esquerda de 8. fb(8)=-1, fb(5)=2 (desbalanceado!). Rotação dupla direita-esquerda: primeiro rotação à direita em 8, depois rotação à esquerda em 5. Resultado:

    ```

    10

    / \

    7 12

    / \

    5 8

    ```

  6. Inserir 11: 11 < 12 → esquerda de 12. fb(12)=-1, fb(10)=0 (ok).

  7. Inserir 13: 13 > 12 → direita de 12. fb(12)=0, fb(10)=0 (ok). Árvore final:

    ```

    10

    / \

    7 12

    / \ / \

    5 8 11 13

    ```

Percurso pré-ordem:

A ordem de visita é: raiz (10), subárvore esquerda (7, 5, 8), subárvore direita (12, 11, 13). Portanto: 10, 7, 5, 8, 12, 11, 13.

Alternativa A — ❌ Incorreta

Apresenta 10, 8, 5, 7... Isso ocorreria se a árvore tivesse outra estrutura (por exemplo, se 8 fosse filho direito de 10, o que não ocorre).

Alternativa B — ✅ Correta ⟵ GABARITO

Exatamente a sequência obtida.

Alternativa C — ❌ Incorreta

Sequência 5, 7, 8, 10, 11, 12, 13 corresponde ao percurso em ordem (ordem crescente), não ao pré-ordem.

Alternativa D — ❌ Incorreta

Sequência 5, 8, 7, 11, 13, 12, 10 não segue nenhum percurso padrão da árvore construída.

Alternativa E — ❌ Incorreta

Sequência 5, 10, 12, 8, 7, 11, 13 é a ordem de inserção, não o percurso pré-ordem.

NÃO CAIA NESSA!

Em árvores AVL, o percurso pré-ordem depende da estrutura balanceada. Treine a simulação de inserções com rotações para não confundir os percursos. Lembre-se: pré-ordem = raiz → esquerda → direita; em ordem = esquerda → raiz → direita (ordem crescente em ABB).

Gabarito: letra B.

Link permanente: /questoes/qq634220