ATIVIDADE 4 - PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

Curso
	GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-14727.01
	Teste
	ATIVIDADE 4 (A4)
	Iniciado
	04/03/21 18:45
	Enviado
	04/03/21 18:53
	Status
	Completada
	Resultado da tentativa
	9 em 10 pontos  
	Tempo decorrido
	8 minutos
	Resultados exibidos
	Respostas enviadas, Respostas corretas, Comentários
· Pergunta 1
1 em 1 pontos
	
	
	
	O reequilíbrio eficiente é a chave para fazer a Árvore AVL funcionar bem sem sacrificar o desempenho. Para recuperar o equilíbrio de uma árvore AVL, realizaremos uma ou mais rotações na árvore.
 
Entre as configurações a seguir, quais são os tipo de rotações usado para manter  equilíbrio da árvore?
 
I.Rotação à Direita 
II.Rotação à esquerda
III.Rotação tripla à direita
IV.Rotação dupla à esquerda
V.Rotação dupla à direita
           
Agora, assinale a alternativa que apresenta os tipos de rotações usado para realizar o equilíbrio de uma árvore.
	
	
	
	
		Resposta Selecionada:
	 
I, II, IV e V.
	Resposta Correta:
	 
I, II, IV e V.
	Comentário da resposta:
	Resposta correta. Os tipo de rotações usado para manter  equilíbrio de uma árvore binária AVL são: Rotação à Direita, Rotação à esquerda, Rotação dupla à esquerda  e Rotação dupla à direita.
	
	
	
· Pergunta 2
1 em 1 pontos
	
	
	
	Nas árvores de busca balanceada, as chaves alocadas são mantidas ordenadas, permitindo que a operação de busca seja realizada, percorrendo um ramo da árvore, desde a base até chegar ao início (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; NOBRE; Ricardo Holanda. Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.).
 
Assinale a alternativa que diz respeito a uma árvore de busca balanceada.
	
	
	
	
		Resposta Selecionada:
	 
. AVL.
	Resposta Correta:
	 
. AVL.
	Comentário da resposta:
	Resposta correta. A árvore AVL é uma árvore binária que vai seguir as mesmas regras para inserção, busca e remoção de elementos, e adicionar essas regras a métodos para se manter o equilíbrio da árvore.
	
	
	
· Pergunta 3
1 em 1 pontos
	
	
	
	A busca é bem comum na área da computação, onde podemos usar muitos método e estruturas de dados para está realizando essa busca, ela pode ser realizada pelo índice ou pelo valor. A busca realizada pelo índice é considerada uma busca direta , ou seja, vai direto na posição da memória.
 
Para realizar essa busca por valor temos duas maneiras, assinale a alternativa que condiz com essas maneiras.
	
	
	
	
		Resposta Selecionada:
	 
.Busca sequencial e busca binária.
	Resposta Correta:
	 
.Busca sequencial e busca binária.
	Comentário da resposta:
	Resposta correta. Para realizar essa busca por valor temos duas maneiras ou realizamos uma busca sequencial ou uma busca binária.
A busca sequencial ela percorre todas as posições do vetor verificando uma a uma até achar o valor desejado ou simplesmente chegou ao final sem achá-lo, já na busca binária é dividido o vetor ao meio e a busca é realizada apenas em uma das metades.
	
	
	
· Pergunta 4
1 em 1 pontos
	
	
	
	O equilíbrio de uma árvore de busca é medido subtraindo o número de níveis na subárvore da esquerda do número de níveis na subárvore da direita.
Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como corrigir o desequilíbrio.
 
Assinale a alternativa com a forma a qual podemos corrigir este desequilíbrio.
	
	
	
	
		Resposta Selecionada:
	 
.Rotações.
	Resposta Correta:
	 
.Rotações.
	Comentário da resposta:
	Resposta correta. Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como corrigir o desequilíbrio. O equilíbrio da árvore é corrigido através das chamadas rotações.
	
	
	
· Pergunta 5
1 em 1 pontos
	
	
	
	Ambas árvore B e B+ são árvores de auto-equilíbrio que possuem operações logarítmicas de inserção, localização e exclusão.
 
Entre as configurações a seguir, quais alternativas condizem com as propriedades da árvore B?
 
I. Uma árvore B é definida pelo termo grau mínimo t. O valor de t depende do tamanho do bloco de disco.
II.Todos os ( nós)
(incluindo raiz) podem conter no máximo 2t - 1 chaves.  
III.Todo nó
do tipo folha possui a mesma profundidade entre eles e o ( nó) da raiz.
IV.Nenhuma das folhas estão no mesmo nível.
V.Nenhum nó
possui a mesma profundidade entre o ( nó) da raiz.
           
Agora, assinale a alternativa que apresenta as propriedades da árvore B.
	
	
	
	
		Resposta Selecionada:
	 
I, II e III.
	Resposta Correta:
	 
I, II e III.
	Comentário da resposta:
	Resposta correta. As propriedades da árvore B é definida pelo termo grau mínimo t. O valor de t depende do tamanho do bloco de disco. Assim como,  todos os ( nós) (incluindo raiz) podem conter no máximo 2t - 1 chaves e Todo nó do tipo folha possui a mesma profundidade entre eles e o ( nó) da raiz.
	
	
	
· Pergunta 6
1 em 1 pontos
	
	
	
	Em 1962, dois cientistas da computação, mudaram para sempre o cenário das  estruturas da Árvore de Pesquisa Binária quando criaram uma árvore revolucionária de auto-equilíbrio que alcança a pior complexidade temporal de O (log n ).
 
Assinale a alternativa com os respectivos nomes desses cientistas.
	
	
	
	
		Resposta Selecionada:
	 
.Georgy Adelson Velsky e Evgenii Landis.
	Resposta Correta:
	 
.Georgy Adelson Velsky e Evgenii Landis.
	Comentário da resposta:
	Resposta correta. Em 1962, dois cientistas da computação soviéticos, Georgy Adelson Velsky e Evgenii Landis, mudaram para sempre o cenário das  estruturas da Árvore de Pesquisa Binária.
	
	
	
· Pergunta 7
1 em 1 pontos
	
	
	
	As vantagens da tabela de dispersão é que ela pode ser usada como índice, porém a grande vantagem está em se ter uma operação cujo acesso é direto, ou seja não é preciso fazer um percurso em uma árvore, não é preciso comparar registro,  pois é uma operação onde vai direto para aquele registro.
 
O hashing tem dois ingredientes fundamentais, assinale a alternativa com os respectivos.
	
	
	
	
		Resposta Selecionada:
	 
.Função de hashing e resolução de colisões.
	Resposta Correta:
	 
.Função de hashing e resolução de colisões.
	Comentário da resposta:
	Resposta correta. O hashing é uma técnica que usa uma função para transformar uma chave em um endereço. Já a colisão acontece quando a função hashing produz o mesmo endereçamento para chaves diferentes.
	
	
	
· Pergunta 8
1 em 1 pontos
	
	
	
	Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como corrigir o desequilíbrio. O equilíbrio da árvore é corrigido através das chamadas rotações.
 
Assinale a alternativa com a fórmula para calcular o fator de equilíbrio de uma árvore AVL.
	
	
	
	
		Resposta Selecionada:
	 
.( Q = R - L), onde R = número de níveis a direita e L
= número de níveis a esquerda.
	Resposta Correta:
	 
.(Q = R - L), onde R = número de níveis a direita e L
= número de níveis a esquerda.
	Comentário da resposta:
	Resposta correta. Para calcular o fator de equilíbrio adotamos a equação ( Q = R - L), onde R = número de níveis a direita e L = número de níveis a esquerda.
	
	
	
· Pergunta 9
1 em 1 pontos
	
	
	
	O equilíbrio de uma árvore de busca é medido subtraindo o número de níveis na subárvore da esquerda do número de níveis na subárvore da direita.
 
De acordo com a Figura abaixo assinale a alternativa que contém o nó
que encontra-se em desequilíbrio.
Figura: Árvore binária AVL. Fonte: Autor.
	
	
	
	
		Resposta Selecionada:
	 
.B(-2).
	Resposta Correta:
	 
.B(-2).
	Comentário da resposta:
	Resposta correta. Uma árvore está desequilibrada quando este número for maior do que 1 ou menor que -1, ou seja em alguns casos não podemos fazer a árvore ter um equilíbrio completamente nulo. Qualquer número entre 1 e -1, será considerado o desequilíbrio, portanto o Nó
no qual se inicia o desequilíbrio é o B(-2).
	
	
	
· Pergunta 10
0 em 1 pontos
	
	
	
	De acordo com Viana a rotação dupla à esquerda consiste em como o próprio nome sugere, os primeiros ( nós) que estão na subárvore da direita passam para a esquerda fazendo com que o filho da direita se torne a novaraiz (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; NOBRE; Ricardo Holanda. Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.).
 
Assinale a alternativa com a opção correta para realizar o equilíbrio na árvore da figura abaixo, usando a rotação dupla à esquerda.
  
Figura: Árvore binária desequilibrada. Fonte: Autor.
	
	
	
	
		Resposta Selecionada:
	 
. .
	Resposta Correta:
	 
..
	Comentário da resposta:
	Sua resposta está incorreta. Para corrigir o desequilíbrio onde a rotação simples nao funciona, podemos adotar como solução, realizar uma rotação à direita na subárvore da direita e em seguida realizar uma rotação à esquerda na árvore original.
	
	
	
Domingo, 28 de Março de 2021 14h51min32s BRT