- Estrutura de Dados Apol 5

Question

Questão 3/5 - Estrutura de Dados

Na AULA 6 estudamos endereçamento aberto de tabelas hash com tentativa linear e tentativa quadrática.

Acerca da tentativa linear e da tentativa quadrática, assinale a alternativa INCORRETA:

A
			
			Na tentativa linear, quando uma colisão ocorre, a próxima posição livre, subsequente, é acessada.

B
			
			Na tentativa quadrática, quando uma colisão ocorre, a primeira posição a ser testada após a colisão é sempre a posição seguinte do vetor.

C
			
			Na tentativa quadrática, quando uma colisão ocorre, a nova tentativa é feita em uma posição que está a uma distância d da posição originalmente testada. Onde d será sempre o dobro da posição originalmente testada.

D
			
			A função hash adotada independe do tipo de tentativa empregado (linear ou quadrática).

E
			
			A tentativa quadrática tende a espalhar mais as chaves colididas na tabela hash.

Reginaldo Rey · Answer

Letra C: O calculo de "d" não e o dobro.

Tecnólogo Analise e Desenvolvimento de Sistemas · Answer

fique a vontade para utilizar o material que tenho sobre estrutura de dados em: https://drive.google.com/drive/folders/1OivNWYtKL7VQUAFR6Alhb2mmnjhVIE7e?usp=sharing

Andre Smaira · Answer

As principais compensações entre esses métodos são que o rastreamento linear tem o melhor desempenho de cache, mas é mais sensível ao armazenamento em cluster, enquanto o hashing duplo tem um desempenho de cache ruim, mas exibe virtualmente nenhum armazenamento em cluster; sondagem quadrática cai entre as duas áreas. O hashing duplo também pode exigir mais computação do que outras formas de sondagem. Isso proporciona melhores tempos de pesquisa máximos do que os métodos baseados em sondagem. Uma influência crítica no desempenho de uma tabela de hash de endereçamento aberto é o fator de carga ; isto é, a proporção dos slots na matriz que são usados. À medida que o fator de carga aumenta para 100%, o número de sondas que podem ser necessárias para localizar ou inserir uma determinada chave aumenta drasticamente. Quando a tabela fica cheia, os algoritmos de sondagem podem até falhar em terminar. Mesmo com boas funções de hash, os fatores de carga são normalmente limitados a 80%. Uma função de hash pobre pode exibir um desempenho ruim, mesmo com fatores de carga muito baixos, gerando agrupamento significativo, especialmente com o método de endereçamento linear mais simples. Geralmente, os fatores de carga típicos com a maioria dos métodos de endereçamento abertos são de 50%, enquanto o encadeamento separadonormalmente pode usar até 100%. O que causa funções hash para cluster não é bem compreendido, e é fácil involuntariamente escrever uma função hash que causa clustering severo.Assim, a alternativa que não se enquandra nessas características é a alternativa C.

- Estrutura de Dados Apol 5

Estrutura de Dados I

UNINTER

💡 4 Respostas

Faça como milhares de estudantes: teste grátis o Passei Direto

Agora você pode testar o

Passei Direto grátis

✏️ Responder

Outros materiais

Outros materiais

	A	Na tentativa linear, quando uma colisão ocorre, a próxima posição livre, subsequente, é acessada.
	B	Na tentativa quadrática, quando uma colisão ocorre, a primeira posição a ser testada após a colisão é sempre a posição seguinte do vetor.
	C	Na tentativa quadrática, quando uma colisão ocorre, a nova tentativa é feita em uma posição que está a uma distância d da posição originalmente testada. Onde d será sempre o dobro da posição originalmente testada.
	D	A função hash adotada independe do tipo de tentativa empregado (linear ou quadrática).
	E	A tentativa quadrática tende a espalhar mais as chaves colididas na tabela hash.