1. Desenhe uma tabela hash com endereçamento aberto e tamanho 9 (com probing linear). Use a função de hash " f(k)=k \% 9 ". Insira as chaves: 5,29,20,0,27 e 18 na tabela nessa ordem e mostre o estado final da tabela após executar todas as operações.

Passo 1

O enunciado pede para construir uma tabela hash de tamanho 9 usando endereçamento aberto com probing linear e função de hash
f(k)=k \bmod 9
Devemos inserir, nessa ordem, as chaves 5,29,20,0,27,18 e mostrar o estado final da tabela.

Passo 2

Inserção de 5:
h = 5 \bmod 9 = 5.
A posição 5 está livre, então colocamos
T[5] = 5.

Passo 3

Inserção de 29:
h = 29 \bmod 9 = 2.
A posição 2 está livre, então colocamos
T[2] = 29.

Passo 4

Inserção de 20:
h = 20 \bmod 9 = 2.
Posição 2 está ocupada (com 29), aplicamos probing linear e tentamos 2+1=3, que está livre. Logo,
T[3] = 20.

Passo 5

Inserção de 0:
h = 0 \bmod 9 = 0.
A posição 0 está livre, então colocamos
T[0] = 0.

Passo 6

Inserção de 27:
h = 27 \bmod 9 = 0.
Posição 0 está ocupada (com 0), aplicamos probing linear e tentamos 0+1=1, que está livre. Logo,
T[1] = 27.

Passo 7

Inserção de 18:
h = 18 \bmod 9 = 0.
Testamos em sequência as posições 0,1,2,3, todas ocupadas. A próxima é a posição 4, que está livre. Logo,
T[4] = 18.

Resposta

O estado final da tabela hash é
T = \begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\hline T[i] & 0 & 27 & 29 & 20 & 18 & 5 & \text{vazio} & \text{vazio} & \text{vazio} \\hline \end{array}

Exercícios relacionados