Questão FC373173
Considere a Árvore Binária de Pesquisa (ABP) abaixo. Os elementos desta ABP serão armazenados em um vetor numerado de 1 a 7, seguindo estas regras: a. a raiz sempre ficará na posiç
Algoritmos e Lógica de Programação
FCC · 2022
Considere a Árvore Binária de Pesquisa (ABP) abaixo.
Os elementos desta ABP serão armazenados em um vetor numerado de 1 a 7, seguindo estas regras:
a. a raiz sempre ficará na posição 1 do vetor;
b. um nó filho na subárvore esquerda receberá o dobro do valor da posição do seu pai; e
c. um nó filho na subárvore direita receberá o dobro do valor da posição de seu pai acrescido de 1.
O vetor resultante de 1 a 7 será, correta e respectivamente:
- 6 – 8 – 4 – 5 – 3 – 7 – 9
- 6 – 4 – 3 – 5 – 8 – 7 – 9
- 6 – 4 – 3 – 8 – 7 – 5 – 9
- 6 – 8 – 9 – 4 – 5 – 3 – 7
- 6 – 4 – 8 – 3 – 5 – 7 – 9
Mostrar resposta e comentário
Gabarito
Errado
Comentário do professor
Aplicando as regras ao nó raiz, colocamos 6 na posição 1 do vetor.
O filho esquerdo de 6 vai para a posição \(2 \times 1 = 2\), portanto a posição 2 contém 4. O filho direito de 6 vai para \(2 \times 1 + 1 = 3\), logo a posição 3 contém 8.
Prosseguindo, os filhos de 4 ficam em \(2 \times 2 = 4\) (esquerdo) e \(2 \times 2 + 1 = 5\) (direito), logo posições 4 e 5 são 3 e 5, respectivamente.
Os filhos de 8 ocupam \(2 \times 3 = 6\) (esquerdo) e \(2 \times 3 + 1 = 7\) (direito), preenchendo as posições 6 e 7 com 7 e 9.
Portanto o vetor de 1 a 7 fica, corretamente: 6 – 4 – 8 – 3 – 5 – 7 – 9, obedecendo \(pos_{esq}=2p\) e \(pos_{dir}=2p+1\).
Conteúdo do catálogo FC Concursos · Atualizado em