Question

As árvores binárias são muito utilizadas para organizar informações armazenadas tanto na memória principal como na secundária. Isso se dá devido ao fato de ser fácil e rápida a pesquisa de dados por meio delas. Uma das maneiras de se implementar uma árvore, é calcular a posição dos filhos de um nó a partir de fórmulas matemáticas bem estabelecidas para se descobrir aonde estão as subárvores esquerda e direita.

Dada a seguinte árvore binária gerada a partir de um vetor de nós indexados:

Fonte: O autor.

Assinale a alternativa correta referente ao vetor de armazenamento desta árvore binária, onde # representa uma posição no vetor que não possui nó associado (uma posição vazia, dentro do vetor). Além disso, ao avaliar as alternativas, considere que o vetor tem início na esquerda e seu final está mais à direita.

Alternativa 1:
[ 1 2 3 4 5 6 # ].

Alternativa 2:
[ 1 2 3 4 5 # 6 ].

Alternativa 3:
[ 1 2 3 4 # 5 6 ].

Alternativa 4:
[ 1 2 3 5 4 # 6 ].

Alternativa 5:
[ 1 2 3 4 5 6 # ].

Answer 1

Resposta: Alternativa 3

Explicação:

Com base na inerção de dados em uma árvore binária diferente, temos a seguinte fórmula: 2*p+1, assim pegamos a posição do vetor, multiplicamos por 2, somamos 1 para o filho à esquerda e somamos 2 para o filho à direita.

Exemplo:

1 está na posição 0

2*0+1=1, então 2 vai para a posição 1;

2*0+2=2, então 3 vai para a posição 2.

Logo,

0 1 2 3 4 5 6 - Posições do vetor

1 2 3 4 # 5 6 - Inserção pela fórmula

Answer 2

Resposta:

Alternativa 3: Alternativa 3:

[ 1 2 3 4 # 5 6 ].

Explicação:

0 1 2 3 4 5

1 2 3 4 # 5 6

Fórmula para o filho da esquerda: 2*p+1

Fórmula para o filho da direita: 2*p+2

Página 27  - Estrutura de Dados II.