Pesquisa, ordenação e técnica de armazenamento

Prévia do material em texto

Pergunta 1
•0 em 0,25 pontos
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 Selecionada:  
I, III, IV e V.
Resposta Correta:  
I, II e V.
Feedback da 
resposta:
Sua resposta está incorreta. As diferenças importantes entre a busca 
sequencial e busca binária está relacionado com a forma como os dados 
encontram-se ordenados. Releia o e-book e procure sobre busca 
sequencial e busca binária para responder corretamente à questão.
• Pergunta 2
•0 em 0,25 pontos
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 .
Chave
3
75
16
24
21
 
Resto
 
0
1
4
?
 
Adote: h(x) = x mod m onde o m = 5    
0
1
2
3
4
5
6
75
16
 
 
24
 
 
 
 
 
 
 
 
 
 
Resposta Selecionada:  
. 1.
Resposta Correta:  
. 0.
Feedback da 
resposta:
Sua resposta está incorreta. Deve-se calcular o h(x) = x mod m, onde o 
temos m = 5, em seguida fazer a inserção na segunda estrutura de 
dados.
• Pergunta 3
•0 em 0,25 pontos
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 m onde o m = 10    
 
 
 
2
24
75
16
0
1
2
3
4
5
6
 
Resposta Selecionada:  
. 4.
Resposta Correta:  
. 0.
Feedback da 
resposta:
Sua resposta está incorreta. Deve-se calcular o h(x) = x mod m, onde o 
temos m = 10, logo em seguida procura a próxima casa para alocar a 
chave desejada.
• Pergunta 4
•0,25 em 0,25 pontos
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.
Resposta Selecionada:  
I, II e V.
Resposta Correta:  
I, II e V.
Feedback da 
resposta:
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.
• Pergunta 5
•0 em 0,25 pontos
Imagine esse vetor ordenado como a Figura abaixo, onde se pretende procurar o elemento 8, a primeira coisa que o vetor irá fazer é 
descobrir a posição inicial, depois descobrir a posição final.
 
Vamos considerar a seguinte matriz:
1 2 3 4 5 6 7 8 9 10
Figura: Vetor Ordenado
Assinale a alternativa com a afirmativa corretas para o meio desse intervalo.
Resposta Selecionada:  
.7.
Resposta Correta:  
.4.
Feedback da 
resposta:
Sua resposta está incorreta. Para achar o meio do intervalo use: meio
= (posiçaoInicial + posicaoFinal) / 2.
• Pergunta 6
•0 em 0,25 pontos
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.
Resposta Selecionada:  
.Hashing de endereçamento e hashing disperso.
Resposta Correta:  
.Hashing aberto e hashing fechado.
Feedback da 
resposta:
Sua resposta está incorreta. Os tipos de hashing pode ser divididos em 
duas formas, onde uma delas é permitido o armazenar um conjunto de 
informações de tamanho limitado e a outra é permitido armazenar um 
conjunto de informações de tamanho limitado.
• Pergunta 7
•0 em 0,25 pontos
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 Selecionada:  
.Mesclados.
Resposta Correta:  
.Ordenados.
Feedback da 
resposta:
Sua resposta está incorreta. A busca binária só funciona em vetores 
que estejam de forma que é possível a divisão do vetor ao meio.
• Pergunta 8
•0,25 em 0,25 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.
Feedback 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 9
•0,25 em 0,25 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.
Feedback 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 10
•0 em 0,25 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:  
.G(0).
Resposta Correta:  
.B(-2).
Feedback da 
resposta:
Sua resposta está incorreta. Uma árvore está desequilibrada quando 
este número for maior do que ( 1) ou menor que ( -1), dado esse 
enunciado releia a questão e assinale a alternativa correta.
	Pergunta 1
	Pergunta 2
	Pergunta 3
	Pergunta 4
	Pergunta 5
	Pergunta 6
	Pergunta 7
	Pergunta 8
	Pergunta 9
	Pergunta 10