Pesquisa, Ordenação e Técnicas de Armazenamento - Atividade 04

Prévia do material em texto

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. 
 
 
 
 
 
 
 
 
• 4. 
• 2. 
• 3. 
• 1. 
• 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. 
 
 
 
 
 
 
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. 
 
• 
 
 
 
 
 
• . 
 
 
• 
 
 
• Nenhuma das alternativas. 
 
 
 
• . . 
 
 
Resposta correta. Para corrigir o problema de desequilíbrio proposto pela figura 
podemos adotar como solução, realizar uma rotação à direita na subárvore da direita 
logo em seguida realizar uma rotação à esquerda na árvore original. 
 
 
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. 
• Nenhuma das alternativas. 
• Hashing de endereçamento e hashing disperso. 
• Hashing aberto e hashing chaves. 
• Hashing aberto e hashing fechado. 
• Hashing fechado e hashing disperso. 
Resposta correta. Os tipos de hashing pode ser divididos em duas formas, sendo ela 
hashing fechado no qual é permitido o armazenar um conjunto de informações de 
tamanho limitado e o hashing aberto no qual é permitido armazenar um conjunto de 
informações de tamanho limitado. 
 
 
 
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. 
• Função hashing e tabela hashing. 
• Nenhuma das alternativas. 
• Função de hashing e resolução de colisões. 
• Colisões e tabela de dispersão. 
• Hashing modular e Função de espelhamento. 
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. 
 
 
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. 
 
• I, III, IV e V. 
• II, IV e V. 
• I, II e V. 
• II, III e IV. 
• I, II, III, IV 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. 
 
 
 
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 
 
• Início = 0 e fim = 8. 
• Início = 5 e fim = 10. 
• Início = 1 e fim = 2. 
• Início = 0 e fim = 6. 
• Início = 0 e fim = 9. 
Resposta correta. O início do intervalo é definido como Low = 0, e o fim do intervalo 
é definido como High = n-1, ou seja, High = 10-1 = 9. 
 
 
 
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. 
• AVL. 
• CVF. 
• BCG. 
• AVC. 
• DEF. 
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. 
 
 
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. 
• Ordenados. 
• Intercalados. 
• Mesclados. 
• Dispersos. 
• Desordenados. 
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. 
 
 
 
As tabelas de hashing podem ser usadas para implementar a inserção e encontrar 
operações em tempo médio constante. É especialmente importante prestar atenção a 
detalhes como fator de carga ao usar tabelas de hashing, pois caso contrário os limites 
de tempo não são válidos. Também é importante escolher a função hashing com 
cuidado quando a chave não for uma sequência curta ou um número inteiro. 
 
Entre as configurações a seguir, quais funções de hashing são consideradas 
satisfatória? 
 
I. Rápido de calcular o O(1) 
II.Tem menos colisões 
III.Tem mais colisões 
IV. Distribui as chaves de forma não uniforme na tabela 
V.Espalha as chaves uniforme na tabela hashing 
 
Agora, assinale a alternativa que apresenta os conceitos de uma boa funções hashing. 
• II, III e IV. 
• I, II, III,IV e V. 
• II, IV e V. 
• I, II e V. 
• I, III, IV e V. 
Resposta correta. Uma função hashing é considerada satisfatória quando é rápida de 
calcular o O(1) e apresenta poucas colisões, assim como as chaves são espalhadas 
de forma distribuída entre a tabela de dispersão. 
 
 
 
 
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. 
• II, IV e V. 
• II, III e IV. 
• I, II, IV e V. 
• I, III, IV e V. 
• I, II, III, 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.