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

Prévia do material em texto

Pergunta 1
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 2
· 1 em 1 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:
 
.Ordenados.
Resposta Correta:
  .Ordenados
Comentário da resposta:
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.
	
	
	
	
· Pergunta 3
· 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 4
· 1 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 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.
Resposta Selecionada:
 
. .
Resposta Correta:
  
Comentário da resposta:
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.
	
	
	
	
· Pergunta 5
· 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 6
· 1 em 1 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:
 
.4.
Resposta Correta:
  4
Comentário da resposta:
Resposta correta.     meio = (posiçaoInicial + posicaoFinal) / 2
meio = (0 + 9) / 2
meio = 4.5 (Pegar inteiro 4) vetor formado por números inteiros.
	
	
	
	
· Pergunta 7
· 1 em 1 pontos
	
	
	
	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.
Resposta Selecionada:
 
.Cada nó tem no máximo M filhos.
Resposta Correta:
  .Cada nó tem no máximo M filhos
Comentário da resposta:
Resposta correta. Uma árvore B+ da ordem M é uma árvore que cada nó tem no máximo M filhos.
	
	
	
	
· Pergunta 8
· 1 em 1 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 aberto e hashing fechado.
Resposta Correta:
  .Hashing aberto e hashing fechado.
Comentário da resposta:
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.
	
	
	
	
	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 aberto e hashing fechado.
Resposta Correta:
 
Comentário da resposta:
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.
	
	
	
	
· Pergunta 9
· 1 em 1 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, II e V.
Resposta Correta:
  I, II e V.
Comentário da resposta:
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 pesquisabiná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.
	
	
	
	
· Pergunta 10
· 1 em 1 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:
 
. 0.
Resposta Correta:
  0.
Comentário da resposta:
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.
	
	
	
	
Segunda-feira, 5 de Abril de 2021 18h16min42s BRT