Escrever o array resultante inserindo a seguinte sequência de 10 chaves em uma tabela hash com sondagem linear inicialmente vazia. Assuma que o tamanho da tabela hash é 10 e que seu tamanho é inalterado.
chave: hash
I: 3
C: 7
W: 7
Y: 9
L: 6
Z: 0
E: 9
0: 9
K: 5
P: 0

Passo 1

Resumimos o enunciado: temos uma tabela hash de tamanho 10 vazia e vamos inserir, por sondagem linear, as 10 chaves I, C, W, Y, L, Z, E, 0, K e P, usando os valores de hash fornecidos.

Passo 2

Para cada chave k, a posição inicial é dada por h(k). Vamos começar com I: h(I)=3. Como a posição 3 está livre, inserimos I em 3.

Passo 3

Próxima chave C: h(C)=7. A posição 7 está livre, então colocamos C em 7.

Passo 4

Agora W: h(W)=7. A posição 7 já tem C, fazemos sondagem linear e testamos 8. A posição 8 está livre, então inserimos W em 8.

Passo 5

Em seguida Y: h(Y)=9. A posição 9 está livre, inserimos Y em 9.

Passo 6

Chave L: h(L)=6. A posição 6 está livre, então L vai para 6.

Passo 7

Chave Z: h(Z)=0. A posição 0 está livre, inserimos Z em 0.

Passo 8

Chave E: h(E)=9. Posição 9 ocupa Y, sondamos para 0 (Z), depois para 1, que está livre. Inserimos E em 1.

Passo 9

Chave ‘0’: h(0)=9. Posição 9 tem Y, 0 tem Z, 1 tem E; sondamos para 2, está livre. Inserimos ‘0’ em 2.

Passo 10

Chave K: h(K)=5. A posição 5 está livre, inserimos K em 5.

Passo 11

Por fim, P: h(P)=0. As posições 0(Z), 1(E), 2(0) e 3(I) estão ocupadas; sondamos para 4, que está livre. Inserimos P em 4.

Resposta

[Z, E, 0, I, P, K, L, C, W, Y]

Exercícios relacionados