1. Considere uma tabela de espalhamento (tabela hash) de comprimento m=11, 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) h(k)=k \% m, 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 ( X representa DELETED e \varnothing representa posição vazia).
    a. Inserção das chaves 3,14,15,92,65,35 (nessa ordem)
    b. Remoção da chave 15, e
    c. Inserção da chave 43

Passo 1

O enunciado define uma tabela hash de tamanho m=11 usando endereçamento aberto com sondagem linear e função de hash h(k)=k\%11. 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: h(3)=3. A posição 3 está vazia, então colocamos 3 em 3.
– Inserir 14: h(14)=3. A posição 3 já tem 3, sondamos para 4 que está vazia e colocamos 14 em 4.
– Inserir 15: h(15)=4. 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: h(92)=4. Testamos 4, 5 (ocupados), então 6 está livre e colocamos 92 em 6.
– Inserir 65: h(65)=10. A posição 10 está vazia, então colocamos 65 em 10.
– Inserir 35: h(35)=2. A posição 2 está vazia, então colocamos 35 em 2.

Passo 3

Remoção e nova inserção:
– Remover 15: partimos de h(15)=4, sondamos até encontrar 15 em 5 e marcamos esta posição como deletada, ou seja, X.
– Inserir 43: h(43)=10. A posição 10 tem 65, sondamos para 0 (voltando ao início) que está vazia, então colocamos 43 em 0.

Resposta

Posição: 012345678910
Conteúdo: 43 \varnothing 35314 X 92 \varnothing \varnothing \varnothing 65

Exercícios relacionados