Questão nº 25
Questão de Tecnologia da Informação · FCC TRT19 2022 (nº 25)
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:
- A6 – 8 – 4 – 5 – 3 – 7 – 9
- B6 – 4 – 3 – 5 – 8 – 7 – 9
- C6 – 4 – 3 – 8 – 7 – 5 – 9
- D6 – 8 – 9 – 4 – 5 – 3 – 7
- E6 – 4 – 8 – 3 – 5 – 7 – 9 (alternativa correta)
Resposta comentada
Gabarito Alternativa E
Uma Árvore Binária de Pesquisa (ABP) é uma estrutura de dados onde, para cada nó, todos os valores na sua subárvore esquerda são menores que o valor do nó, e todos os valores na sua subárvore direita são maiores. Para armazenar uma árvore em um vetor, podemos usar regras que mapeiam a posição do nó no vetor com base na posição do seu pai.
Para a ABP dada e as regras de mapeamento:
- A raiz (6) fica na posição 1.
vetor[1] = 6 - O filho esquerdo de 6 (que é 4) fica na posição
2 * 1 = 2.vetor[2] = 4 - O filho direito de 6 (que é 8) fica na posição
2 * 1 + 1 = 3.vetor[3] = 8 - O filho esquerdo de 4 (que é 3, pai na posição 2) fica na posição
2 * 2 = 4.vetor[4] = 3 - O filho direito de 4 (que é 5, pai na posição 2) fica na posição
2 * 2 + 1 = 5.vetor[5] = 5 - O filho esquerdo de 8 (que é 7, pai na posição 3) fica na posição
2 * 3 = 6.vetor[6] = 7 - O filho direito de 8 (que é 9, pai na posição 3) fica na posição
2 * 3 + 1 = 7.vetor[7] = 9
O vetor resultante é [6, 4, 8, 3, 5, 7, 9].
(A) Incorreta: A ordem dos elementos 8 e 4 está trocada nas posições 2 e 3.
(B) Incorreta: Esta alternativa representa a árvore em uma travessia pré-ordem (raiz, esquerda, direita), e não o mapeamento específico para o vetor conforme as regras dadas. Esta é a armadilha da banca, pois muitos alunos podem confundir a representação em vetor com uma simples travessia da árvore.
(C) Incorreta: Os elementos 3, 8, 7 e 5 estão em posições incorretas em relação às regras de mapeamento.
(D) Incorreta: Os elementos 8, 9, 4, 5, 3 e 7 estão em posições incorretas em relação às regras de mapeamento.
(E) Correta: Esta alternativa segue exatamente as regras de mapeamento fornecidas, colocando a raiz na posição 1, o filho esquerdo na posição 2*pai e o filho direito na posição 2*pai + 1.
Fonte: FCC TRT19 2022 Analista Judiciário - Área Apoio Especializado - Especialidade Tecnologia da Informação (Caderno Tipo 001). Reproduzida para fins de estudo.