Buscar

- Estrutura de Dados Apol 5

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.

💡 4 Respostas

User badge image

Reginaldo Rey

Letra C: O calculo de "d" não e o dobro.
1
Dislike0
User badge image

Andre Smaira

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.
0
Dislike0

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

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

✏️ Responder

SetasNegritoItálicoSublinhadoTachadoCitaçãoCódigoLista numeradaLista com marcadoresSubscritoSobrescritoDiminuir recuoAumentar recuoCor da fonteCor de fundoAlinhamentoLimparInserir linkImagemFórmula

Para escrever sua resposta aqui, entre ou crie uma conta

User badge image

Outros materiais