Atividade 4

Prévia do material em texto

· Pergunta 1
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 2
1 em 1 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.
	Comentário 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 3
1 em 1 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:
	 
. 0.
	Resposta Correta:
	 
. 0.
	Comentário da resposta:
	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.
	
	
	
· Pergunta 4
1 em 1 pontos
	
	
	
	Em 1962, dois cientistas da computação, mudaram para sempre o cenário das  estruturas da Árvore de Pesquisa Binária quando criaram uma árvore revolucionária de auto-equilíbrio que alcança a pior complexidade temporal de O (log n ).
 
Assinale a alternativa com os respectivos nomes desses cientistas.
	
	
	
	
		Resposta Selecionada:
	 
.Georgy Adelson Velsky e Evgenii Landis.
	Resposta Correta:
	 
.Georgy Adelson Velsky e Evgenii Landis.
	Comentário da resposta:
	Resposta correta. Em 1962, dois cientistas da computação soviéticos, Georgy Adelson Velsky e Evgenii Landis, mudaram para sempre o cenário das  estruturas da Árvore de Pesquisa Binária.
	
	
	
· Pergunta 5
1 em 1 pontos
	
	
	
	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 Selecionada:
	 
.Busca sequencial e busca binária.
	Resposta Correta:
	 
.Busca sequencial e busca binária.
	Comentário da resposta:
	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.
	
	
	
· Pergunta 6
1 em 1 pontos
	
	
	
	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.
	
	
	
	
		Resposta Selecionada:
	 
I, II e III.
	Resposta Correta:
	 
I, II e III.
	Comentário da resposta:
	Resposta correta. As propriedades da árvore B é definida pelo termo grau mínimo t. O valor de t depende do tamanho do bloco de disco. Assim como,  todos os ( nós) (incluindo raiz) podem conter no máximo 2t - 1 chaves e Todo nó do tipo folha possui a mesma profundidade entre eles e o ( nó) da raiz.
	
	
	
· Pergunta 7
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 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.
	
	
	
· Pergunta 8
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 9
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 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.