PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO 3

Prévia do material em texto

1 - Uma pesquisa sequencial é quando você olha para cada parte dos dados, um por um, e não para até encontrar o que está procurando. Você pode usar uma pesquisa sequencial em qualquer dado. No entanto, a pesquisa sequencial é a única opção que você pode usar quando é preciso pesquisar dados desordenados.
 
Entre as configurações a seguir, quais são as diferenças entre os métodos de busca sequencial e busca binária?
 
I.Os dados de entrada precisam ser classificados na Pesquisa binária e não na Pesquisa linear.
II.A pesquisa linear faz o acesso sequencial, enquanto a pesquisa binária acessa dados aleatoriamente.    
III. A pesquisa binária realiza o acesso de forma sequencial.
IV.A pesquisa linear não realiza o acesso sequencial.
V.A pesquisa linear realiza comparações de igualdade e a pesquisa binária realiza comparações de pedidos.
           Agora, assinale a alternativa que apresenta as diferenças existentes entre as duas buscas, ou seja, tanto a sequencial como a binária.
Resposta: I, II e V.
Resposta correta. As diferenças importantes entre a busca sequencial e busca binária é que os dados de entrada precisam ser classificados na Pesquisa binária e não na Pesquisa linear, assim como para a pesquisa linear é realizado o acesso sequencial, enquanto a pesquisa binária acessa dados de forma aleatória.
A Complexidade temporal da pesquisa linear é -O(n) e para pesquisa binária possui complexidade temporal de O(log n).
A pesquisa linear realiza comparações de igualdade e a pesquisa binária realiza comparações de pedidos.
2 - A pesquisa binária é o algoritmo de pesquisa mais popular, eficiente e também uma das técnicas mais usadas para solucionar problemas. A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista.
 Assinale a alternativa correta para forma como os vetores devem estar para busca binária funcionar.
Resposta: Ordenados.
Resposta correta. A busca binária só funciona em vetores que estejam de forma ordenados, ela divide o vetor ao meio e procura apenas em uma das metades, ou seja, o algoritmo é executado até encontrar o valor ou posição.
3 - 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
Resposta: 0
Resposta correta. Adotando h(x) = x mod m, onde o m = 10, temos h(3) = 3 mod 10 = 3. Como a posição 3 encontra-se ocupada, procura-se a próxima posição disponível para que o 3
seja alocando, portanto a próxima posição livre é a posição 0.
4 - 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: .B(-2).
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).
5 - 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: AVL
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.
6 - 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: Busca sequencial e busca binária.
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.
7 - 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: Função de hashing e resolução de colisões.
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.
8 - O hashing
aberto tem a desvantagem de exigir ponteiros. Isso tende a desacelerar um pouco o algoritmo por causa do tempo necessário para alocar novas células e também requer essencialmente a implementação de uma segunda estrutura de dados.
 Assinale a alternativa com o valor da posição para a chave 21
descrita na tabela abaixo, use a técnica de hashing aberto.
Resposta: 0
Resposta correta. Adotando h(x) = x mod m, onde o m = 5, temos h(21) = 21 mod 5 = 1. Trabalhando com a técnica de hashing aberto é possível a inserção da chave na posição da função hashing, ou seja, o 21 será alocado na posição 1 na segunda estrutura de dados.
		Chave
	3
	75
	16
	24
	21
	 
		Resto
	 
	0
	1
	4
	?
	 
	Adote: h(x) = x mod monde o m = 5  
		0
	1
	2
	3
	4
	5
	6
		75
	16
	 
	 
	24
9 - 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: I, II, IV e V
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.
10 - 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: ( Q = R - L), onde R = número de níveis a direita e L
= número de níveis a esquerda.
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.
image1.gif