Logo Passei Direto
Buscar
20:09 S 87 VOLTAR Questão 9 Uma maneira simples e rápida de implementar uma árvore binária é empregando o uso de um vetor estático. A seguir podemos visualizar um exemplo de árvore binária: A B C D E F G H I J Considere que, nem sempre que um nó for a raiz de uma árvore, ele ocupará a primeira posição do vetor, considere que a posição inicial (índice inicial) do vetor é igual a 1. Considere, ainda, que ao se inserir os filhos de um nó que OC posição P, o filho esquerdo deverá ser inserido na posição 2*P, e o filho dire posição 2*P + 1. Com base na árvore ilustrada e considerando uma implementação estática baseada nas fórmulas apresentadas, assinale a alternativa correta: A ) Caso a árvore fosse binária completa com altura 2, seriam necessárias no mínimo 15 posições no vetor para armazenar todos OS seus vértices. B) A árvore é uma binária completa. C) o vértice I estaria armazenado na posição 11 do vetor. D) Os vértices que são filhos direitos sempre estarão em posições pares. < Anterior Próxima >
User badge image
LUCÃØ

há 5 dias

Respostas

User badge image

Ed Verified user icon

há 5 dias

Vamos analisar cada alternativa com base nas informações fornecidas: - A) "Caso a árvore fosse binária completa com altura 2, seriam necessárias no mínimo 15 posições no vetor para armazenar todos os seus vértices." Altura 2 significa que a árvore tem 3 níveis (nível 0, 1 e 2). Uma árvore binária completa de altura h tem no máximo 2^(h+1) - 1 nós. Para h=2, isso é 2^(3) - 1 = 8 - 1 = 7 nós. Portanto, seriam necessárias 7 posições, não 15. A alternativa está incorreta. - B) "A árvore é uma binária completa." Sem a imagem da árvore, não podemos afirmar com certeza, mas a questão sugere que não é completa, pois fala que nem sempre o nó raiz está na posição 1 e que a árvore pode não ser completa. Portanto, essa alternativa provavelmente é falsa. - C) "O vértice I estaria armazenado na posição 11 do vetor." Pela regra: filho esquerdo na posição 2*P, filho direito na posição 2*P + 1, e índice inicial 1 para a raiz. Se considerarmos a posição do vértice I, normalmente em uma árvore binária representada em vetor, o nó I estaria na posição 11 se for filho direito do nó na posição 5 (pois 2*5 + 1 = 11). Isso é consistente com a regra. - D) "Os vértices que são filhos direitos sempre estarão em posições pares." Pela fórmula, filho direito está na posição 2*P + 1, que é sempre ímpar (pois 2*P é par, somando 1 dá ímpar). Portanto, essa alternativa é falsa. Conclusão: a alternativa correta é a C) O vértice I estaria armazenado na posição 11 do vetor.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Mais conteúdos dessa disciplina