Unidade 4 - Atividade A4 - Pesquisa, Ordenação e Técnicas de Armazenamento

Prévia do material em texto

Atividade 4
1. 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.
2. 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.
3. 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.
4. Formalmente, definimos uma Árvore B + pelos valores M e L, onde M é igual ao número máximo de filhos que um determinado nó pode ter e L é igual ao número máximo de registros de dados armazenados em um nó folha.
 
Uma árvore B + da ordem M é uma árvore que satisfaz uma das propriedade abaixo, assinale qual.
5. A pesquisa binária funciona apenas em um conjunto com elementos ordenados. Para usar a pesquisa binária em uma coleção, a coleção deve primeiro ser classificada.
Quando a pesquisa binária é usada para executar operações em um conjunto ordenado, o número de iterações sempre pode ser reduzido com base no valor que está sendo pesquisado.
 
Antes de iniciar a pesquisa binária, primeiro definimos o início e fim do intervalo, assinale a alternativa com a afirmativa corretas para o início e o fim desse intervalo.
Vamos considerar a seguinte matriz:
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
Figura: Vetor Ordenado
6. 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.
7. 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 nova raiz (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.
8. A idéia essencial por trás de uma tabela de dispersão é que todas as informações são armazenadas em uma matriz de tamanho fixo. O hashing é usado para identificar a posição em que um item deve ser armazenado.
 
Assinale a alternativa com os tipos de hashing mais usados.
9. 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.
10. O hashing fechado, também conhecido como endereçamento aberto, é uma alternativa para resolver colisões com listas vinculadas. Em um sistema de hashing fechado, se ocorrer uma colisão, células alternativas são tentadas até que uma célula vazia seja encontrada.
 
Assinale a alternativa com o valor da posição para a chave 3 descrita na tabela abaixo, use a técnica de hashing fechado.
 
		Chave
	3
	75
	16
	24
	 
	 
		Resto
	?
	5
	6
	4
	 
	 
	Adote: h(x) = x mod monde o m = 10  
		 
	 
	 
	2
	24
	75
	16
		0
	1
	2
	3
	4
	5
	6