Pular para o conteúdo principal

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

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qq333399
Banca
FADESP
Órgão
IF-PA
Ano
2018
Nível
Superior
Cargo
Professor - Informática
Considere uma árvore Patricia construída para armazenar as seguintes chaves: A = 011001; B = 110010; C = 100101; D = 001011; E = 011010; F = 110101. A altura da árvore Patricia resultante, considerando-se sua raiz no nível zero, é
  1. Adois.
  2. Btrês.
  3. Cquatro.
  4. Dcinco.
  5. Eseis.
Revelar gabarito e comentário

GabaritoB — três.

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 Patricia: altura

Gabarito: letra B (três). A árvore Patricia construída com as chaves fornecidas tem altura 3, considerando a raiz no nível 0, pois a folha mais profunda está no nível 3.

A árvore Patricia (Practical Algorithm To Retrieve Information Coded In Alphanumeric) é uma estrutura de busca digital baseada em bits. A construção parte da raiz (nível 0) e, em cada nó interno, examina-se o bit onde as chaves do grupo divergem. As chaves dadas são:

  • A: 011001

  • B: 110010

  • C: 100101

  • D: 001011

  • E: 011010

  • F: 110101

Passo a passo da construção:

  1. Primeiro bit (bit mais significativo): as chaves com 0 (A, D, E) vão para a subárvore esquerda; com 1 (B, C, F) para a direita. Cria-se o nó raiz (nível 0).

  1. Subárvore esquerda (bit 0): chaves A (011001), D (001011), E (011010). O segundo bit de A e E é 1, de D é 0. Cria-se um nó interno para o segundo bit (nível 1).

    • Filho esquerdo (bit 0 do segundo bit): D (folha, nível 2).

    • Filho direito (bit 1 do segundo bit): chaves A e E. Elas divergem no quarto bit (posição 4, contando do MSB como pos0): A tem 0, E tem 1. Cria-se nó interno para o quarto bit (nível 2).

      • Filho esquerdo: A (folha, nível 3).

      • Filho direito: E (folha, nível 3).

  1. Subárvore direita (bit 1): chaves B (110010), C (100101), F (110101). O segundo bit de B e F é 1, de C é 0. Cria-se nó interno para o segundo bit (nível 1).

    • Filho esquerdo: C (folha, nível 2).

    • Filho direito (bit 1 do segundo bit): chaves B e F. Elas divergem no terceiro bit (posição 3): B tem 0, F tem 1. Cria-se nó interno para o terceiro bit (nível 2).

      • Filho esquerdo: B (folha, nível 3).

      • Filho direito: F (folha, nível 3).

A árvore resultante tem folhas nos níveis 2 (D, C) e 3 (A, E, B, F). O nível máximo é 3, portanto a altura da árvore (considerando raiz nível 0) é 3.

  1. 1Raiz (nível 0): 1º bit
  2. 2Esquerda (0): A,D,E
  3. 3Direita (1): B,C,F
  4. 4Nó interno (nível 1): 2º bit
  5. 5Folhas nos níveis 2 e 3
  6. 6Altura = 3 (nível máximo)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma altura 2, mas existem folhas no nível 3, o que exige pelo menos altura 3.

Alternativa B — ✅ Correta ⟵ GABARITO

Altura 3, conforme demonstrado pela construção.

Alternativa C — ❌ Incorreta

Altura 4 é maior que a profundidade real; a árvore não tem caminhos com 4 arestas.

Alternativa D — ❌ Incorreta

Altura 5 superestima a estrutura.

Alternativa E — ❌ Incorreta

Altura 6 é incompatível com a árvore que possui apenas 6 chaves e raiz em nível 0.

PEGA ESSA DICA!

Para calcular a altura de uma árvore Patricia, construa a árvore bit a bit, identificando o primeiro bit de divergência em cada grupo. O nível máximo das folhas (contando a raiz como 0) é a altura. Nesta questão, a chave está em reconhecer que as folhas A, E, B e F estão no nível 3.

Gabarito: letra B (três).

Link permanente: /questoes/qq333399