Desenhe uma tabela de hash resultante da introdução das chaves 12, 44, 13, 88, 23, 94,11,39,20, 16 e 5 , usando a função de hash h(k)=(2 k+5) % 11 e supondo que as colisões são tratadas por encadeamento separado.

Passo 1

O enunciado pede para montar uma tabela de hash inserindo as chaves 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 e 5, usando a função de hash h(k)=(2k+5)bmod11 e tratando colisões por encadeamento separado. Vamos aplicar conceitos de funções de hash e listas encadeadas para resolver.

Passo 2

Precisamos usar a função de hash para distribuir cada chave num índice de 0 a 10. Em caso de colisão, vamos colocar a chave no final de uma lista ligada (encadeamento separado) correspondente àquele índice.

Passo 3

Calculamos h(k) para cada chave conforme a seguir:
h(12) &= (2cdot12+5)bmod11 = 29bmod11 = 7, h(44) &= (2cdot44+5)bmod11 = 93bmod11 = 5, h(13) &= (2cdot13+5)bmod11 = 31bmod11 = 9, h(88) &= (2cdot88+5)bmod11 = 181bmod11 = 5, h(23) &= (2cdot23+5)bmod11 = 51bmod11 = 7, h(94) &= (2cdot94+5)bmod11 = 193bmod11 = 6, h(11) &= (2cdot11+5)bmod11 = 27bmod11 = 5, h(39) &= (2cdot39+5)bmod11 = 83bmod11 = 6, h(20) &= (2cdot20+5)bmod11 = 45bmod11 = 1, h(16) &= (2cdot16+5)bmod11 = 37bmod11 = 4, h(5) &= (2cdot5+5)bmod11 = 15bmod11 = 4

Passo 4

Agora agrupamos as chaves em buckets (índices) de 0 a 10, mantendo a ordem de inserção em cada lista encadeada:
  • Índice 0: vazio
  • Índice 1: 20
  • Índice 2: vazio
  • Índice 3: vazio
  • Índice 4: 16 → 5
  • Índice 5: 44 → 88 → 11
  • Índice 6: 94 → 39
  • Índice 7: 12 → 23
  • Índice 8: vazio
  • Índice 9: 13
  • Índice 10: vazio

Resposta

Tabela de hash com encadeamento separado (índices 0–10):
0 : –
1 : 20
2 : –
3 : –
4 : 16 → 5
5 : 44 → 88 → 11
6 : 94 → 39
7 : 12 → 23
8 : –
9 : 13
10: –

Exercícios relacionados