Logo Passei Direto
Buscar

Bases de Dados

Outros
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 C D E F G H 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 ocupa a posição P, o filho esquerdo deverá ser inserido na posição 2*P, e o filho direito na 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 A árvore é estritamente binária.
B Os vértices que são filhos direitos sempre estarão em posições pares.
C vértice I estaria armazenado na posição 11 do vetor.
D A árvore é uma binária completa.
E 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.
User badge image
Testando o Conhecimento

há 2 meses

User badge image
Testando o Conhecimento

há 2 meses

qiyjv_AV2-ESTRUTURA DE DADOS
8 pág.

qiyjv_AV2-ESTRUTURA DE DADOS

Respostas

User badge image

Ed Verified user icon

há 2 meses

Vamos analisar cada alternativa com base nas informações fornecidas: A) A árvore é estritamente binária. - Árvore estritamente binária é aquela em que todo nó tem 0 ou 2 filhos. Sem a figura da árvore, não podemos afirmar isso com certeza, mas geralmente, se há nós com apenas um filho, não é estritamente binária. Como não foi informado que todos os nós têm 0 ou 2 filhos, essa alternativa provavelmente é falsa. B) Os vértices que são filhos direitos sempre estarão em posições pares. - Pela fórmula dada, filho esquerdo está em 2*P (posição par) e filho direito em 2*P + 1 (posição ímpar). Portanto, filhos direitos estão em posições ímpares, não pares. Alternativa falsa. C) Vértice I estaria armazenado na posição 11 do vetor. - Sem a árvore completa, não podemos afirmar com certeza, mas considerando a regra e a sequência dos nós (A C D E F G H J), o vértice I não aparece na lista, então essa alternativa é falsa. D) A árvore é uma binária completa. - Árvore binária completa é aquela em que todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e todos os nós do último nível estão o mais à esquerda possível. Sem a figura, não podemos afirmar, mas geralmente, se a árvore não está cheia, essa alternativa é falsa. E) 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 níveis 0, 1 e 2 (3 níveis). O número máximo de nós em uma árvore binária completa de altura h é 2^(h+1) - 1. Para h=2: 2^(2+1) - 1 = 2^3 - 1 = 8 - 1 = 7 nós. Portanto, seriam necessárias 7 posições, não 15. Alternativa falsa. Conclusão: A alternativa correta é a A) A árvore é estritamente binária.

Essa resposta te ajudou?

0
Dislike0

Ainda não achou a resposta?

  • Integrado com os principais modelos de IA do mercado
  • Respostas em segundos
  • IA treinada para estudantes brasileiros.
PasseIA logoEvolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

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

Essa pergunta também está no material:

qiyjv_AV2-ESTRUTURA DE DADOS
8 pág.

qiyjv_AV2-ESTRUTURA DE DADOS

Mais perguntas desse material

A ordenação de dados é muito utilizada no desenvolvimento de sistemas, pois permite organizar informações para facilitar o processo de busca e análise. Diversos métodos são utilizados para essa tarefa, e um deles é o método da bolha (Bubblesort). Esse método, embora não seja o mais eficiente, destaca-se por sua simplicidade.
Considerando o método "Bubblesort" para ordenação de um vetor, assinale a alternativa correta sobre o seu funcionamento:
A método da bolha compara os elementos do vetor apenas uma vez, garantindo uma ordenação eficiente.
número de repetições no método da bolha é igual ao número de elementos do vetor menos 1, e em cada repetição compara-se os elementos vizinhos, efetuando trocas quando necessário.
método da bolha utiliza um índice de controle que percorre o vetor de forma decrescente, trocando os elementos adjacentes quando necessário.
A ordenação no método da bolha é realizada percorrendo o vetor uma única vez e trocando os elementos imediatamente se estiverem fora de ordem.
método da bolha é mais eficiente quando o vetor já está parcialmente ordenado, sendo menos adequado para vetores desordenados.

Os algoritmos de ordenação utilizam métodos capazes de ordenar, de maneira exata, um conjunto de dados armazenados em um vetor. Fonte: adaptado de: CORMEN, T. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009.
Sobre os algoritmos BubbleSort e SelectionSort, analise as afirmativas a seguir:
I. A técnica de ordenação BubbleSort também é conhecida por ordenação por flutuação ou método da bolha.
II. SelectionSort, apesar de ser uma técnica de simples implementação, possui alto consumo computacional.
III. As técnicas de SelectionSort e BubbleSort estão entre os piores desempenhos entre os algoritmos de ordenação existentes.
IV. método SelectionSort seleciona e ordena um elemento arbitrário do arranjo e, então, chama a si mesmo, recursivamente, para ordenar uma porção menor do arranjo.
A I e IV, apenas.
B IV, apenas.
C II e III, apenas.
D I, II e III, apenas.
E II, III e IV, apenas.

Existem diversas técnicas tradicionais para se realizar a ordenação de um arranjo. Ao desenvolvedor, caberia apenas a escolha de uma dessas técnicas para compor seu programa, caso necessário.
Sobre a ordenação de vetores, analise as afirmativas a seguir:
I. algoritmo BubbleSort possui fácil implementação, e consequentemente baixo custo computacional.
II. MergeSort é uma otimizaçao do ShellSort, na qual uma partição é dividida por meio do seu elemento pivô.
III. algoritmo SelectionSort, assim como o InsertionSort, é de fácil implementação, é um dos algoritmos de ordenação mais veloz.
IV. algoritmo ShellSort de ordenação é o mais eficiente e é considerado uma técnica refinada do método de ordenação por inserção.
A I e IV, apenas.
B IV, apenas.
C II, III e IV, apenas.
D II e III, apenas.
E I, II e III, apenas.

De maneira geral, utilizar árvores no desenvolvimento é bom, pois elas provêm acesso de dados direto e sequencial rápidos, têm fácil inserção e remoção de dados e ainda possuem boa taxa de utilização de memória. Para poder manipular árvores convenientemente, o desenvolvedor necessita ter conhecimento de vários conceitos.
A respeito de árvores, analise as afirmativas a seguir:
I. Considere que a raiz é o vértice inicial e não possui um nó-pai.
II. Considere que o nó V tem uma subárvore cuja raiz dessa subárvore é o nó W. Diz-se que V é pai de W.
III. Considere que o nó V tem uma subárvore cuja raiz dessa subárvore é o nó W. Diz-se que W é pai de V.
IV. Considere que o nó V tem uma subárvore cuja raiz dessa subárvore é o nó W. Diz-se que W é filho de V.
A II, III e IV, apenas.
B III e IV, apenas.
C I, II e IV, apenas.
D I, apenas.
E II e III, apenas.

algoritmo ShellSort de ordenação tem esse nome em homenagem ao seu criador, Donald Shell, publicado pela Universidade de Cincinnat em 1959. Segundo Wirth (1989), ele é o mais eficiente dentro dos algoritmos classificados como complexidade quadrática. Fonte: adaptado de: WIRTH, N. Algoritmos e estrutura de dados. Rio de Janeiro: Prentice-Hall do Brasil, 1989.
Assinale a alternativa correta que apresenta a principal característica do algoritmo ShellSort:
A Ele aplica o método SelectionSort utilizando recursividade.
B Ele aplica uma busca binária utilizando o método BubbleSort.
C Ele divide o vetor em vetores menores e em cada um deles aplica o método InsertionSort.
D Ele aplica uma busca sequencial completa.
E Ele mescla os métodos MergeSort e QuickSort.

Método de ordenação por QuickSort, também conhecido por classificação por troca de partição, foi publicado em 1962 e é considerado o algoritmo de ordenação mais utilizado no mundo. Fonte: adaptado de: CORMEN, et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009.
Sobre o processamento do método QuickSort, analise as afirmativas a seguir:
I. método pode escolher um elemento qualquer do vetor que será o pivô.
II. pivô, durante o processo de partição, já estará na sua posição final do vetor.
III. As sublistas são percorridas de forma recursiva até que haja apenas um elemento nas sublistas criadas recursivamente.
IV. A partir do método Merge(), a lista é dividida em sublistas, uma para valores menores, outra para valores maiores, o pivô e a terceira que é o próprio pivô.
A I, II, III e IV.
B III e IV, apenas.
C I, apenas.
D I, II e III, apenas.
E II e III, apenas.

A técnica de ordenação Mergesort consiste em dividir um problema complexo em problemas menores e assim por diante, até que se encontre uma solução pequena e simples suficiente para que o problema seja resolvido como um todo. Esse conceito é bem conhecido na ciência da computação, e seu nome é para Para além de aplicações tecnológicas, esse conceito é utilizado também em estratégias comerciais ou mesmo sociopolíticas. Fonte: adaptado de: CORMEN, T. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009.
Assinale a alternativa correta que apresenta a forma como é feita a ordenação pelo algoritmo Mergesort:
Os elementos são comparados e trocados conforme o caso, de maneira iterativa, em dois laços de repetição, fazendo os valores maiores "flutuarem" para o final do arranjo, realizando a ordenação de trás para frente.
vetor é dividido em várias partes iguais menores, em que é feita a ordenação em cada uma delas. Depois o vetor é reunido já com valores ordenados, tomando por base a função partition() e o elemento pivô.
elemento atual é removido, de maneira recursiva, em dois laços de repetição, e sua posição ideal é procurada no vetor e, uma vez encontrada, o elemento é reinserido em sua posição quase ordenada.
vetor original é percorrido em um único laço de repetição, de maneira iterativa, e os elementos são adicionados em um segundo vetor único, fazendo a comparação para verificar a ordenação.
vetor é dividido em duas partes, essas partes são divididas novamente, e assim por diante, até que cada parte tenha apenas um elemento. Depois é feita a junção, ordenando essas partes e recompondo o vetor com os dados originais ordenados.

Cada algoritmo de ordenação possui suas particularidades. Dependendo da maneira que se encontram distribuídos os dados no arranjo, pode ser que haja diferença no tempo de execução dos algoritmos. Fonte: adaptado de: CORMEN, T. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009.
Sobre os algoritmos de ordenação, analise as afirmativas a seguir:
I. InsertionSort não é um algoritmo inerentemente recursivo.
II. InsertionSort também é conhecido como método de ordenação por inserção.
III. InsertionSort, assim como o BubbleSort, também utiliza a função "troca" para realizar a ordenação dos elementos.
IV. Pelo fato de possuir dois laços de repetição aninhados, o InsertionSort não é capaz de ser mais veloz que os algoritmos SelectionSort e BubbleSort.
A II e III, apenas.
B I, II, III e IV.
C I, II e III, apenas.
D II e IV, apenas.
E I, apenas.

Mais conteúdos dessa disciplina