- Considere uma tabela de espalhamento (tabela hash) de comprimento
, que usa endereçamento aberto (open addressing), a técnica de tentativa linear (linear probing) para resolver colisões e com a função de dispersão (função hash)
, onde k é a chave a ser inserida. Considere as seguintes operações (nesta ordem) sobre essa tabela e escolha a opção que representa a tabela após estas operações (
representa DELETED e
representa posição vazia).
a. Inserção das chaves
(nessa ordem)
b. Remoção da chave 15, e
c. Inserção da chave 43
a. Inserção das chaves
b. Remoção da chave 15, e
c. Inserção da chave 43
Passo 1
O enunciado define uma tabela hash de tamanho
usando endereçamento aberto com sondagem linear e função de hash
. Vamos inserir as chaves na ordem dada, depois remover a chave 15 e em seguida inserir a chave 43, sempre aplicando sondagem linear em caso de colisão.
Passo 2
Inserção das chaves:
– Inserir 3: . A posição 3 está vazia, então colocamos 3 em 3.
– Inserir 14: . A posição 3 já tem 3, sondamos para 4 que está vazia e colocamos 14 em 4.
– Inserir 15: . As posições 4 e 5 são testadas (4 ocupado por 14), a 5 está vazia, então colocamos 15 em 5.
– Inserir 92: . Testamos 4, 5 (ocupados), então 6 está livre e colocamos 92 em 6.
– Inserir 65: . A posição 10 está vazia, então colocamos 65 em 10.
– Inserir 35: . A posição 2 está vazia, então colocamos 35 em 2.
– Inserir 3:
– Inserir 14:
– Inserir 15:
– Inserir 92:
– Inserir 65:
– Inserir 35:
Passo 3
Remoção e nova inserção:
– Remover 15: partimos de , sondamos até encontrar 15 em 5 e marcamos esta posição como deletada, ou seja,
.
– Inserir 43: . A posição 10 tem 65, sondamos para 0 (voltando ao início) que está vazia, então colocamos 43 em 0.
– Remover 15: partimos de
– Inserir 43:
Resposta
Posição:
Conteúdo: 43 92
65
Conteúdo: 43