33) [POSCOMP 2009] 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 mod m, onde k é a chave a ser inserida. Considere as seguintes operações sobre essa tabela: Inserção das chaves 3, 14, 15, 92, 65, 35 (nesta ordem); Remoção da chave 15; e Inserção da chave 43. Escolha a opção que representa esta tabela após estas operações: a) 65 – ø – 35 – 14 – ø – 92 – 3 – ø – ø – ø – 43 b) 43 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 65 c) 65 – ø – 35 – X – 14 – 92 – 3 – ø – ø – ø – 43 d) 65 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 43 e) 43 – ø – 35 – 3 – 14 – X – 92 – ø – ø – ø – 65

Question

33) [POSCOMP 2009] Considere uma tabela de espalhamento (tabela hash) de comprimento m=11, que usa endereçamento aberto (open addressing), a técnic...

Ed · Answer

Vamos analisar as operações na tabela de espalhamento (tabela hash) passo a passo:

1. **Inserção da chave 3**: 
   - h(3) = 3 mod 11 = 3. 
   - A posição 3 é livre, então inserimos 3 na posição 3.

2. **Inserção da chave 14**: 
   - h(14) = 14 mod 11 = 3. 
   - A posição 3 já está ocupada (por 3), então usamos a técnica de tentativa linear e verificamos a próxima posição (4), que está livre. 
   - Inserimos 14 na posição 4.

3. **Inserção da chave 15**: 
   - h(15) = 15 mod 11 = 4. 
   - A posição 4 já está ocupada (por 14), então tentamos a próxima posição (5), que está livre. 
   - Inserimos 15 na posição 5.

4. **Inserção da chave 92**: 
   - h(92) = 92 mod 11 = 4. 
   - A posição 4 está ocupada (por 14) e a posição 5 está ocupada (por 15), então tentamos a próxima posição (6), que está livre. 
   - Inserimos 92 na posição 6.

5. **Inserção da chave 65**: 
   - h(65) = 65 mod 11 = 10. 
   - A posição 10 está livre, então inserimos 65 na posição 10.

6. **Inserção da chave 35**: 
   - h(35) = 35 mod 11 = 2. 
   - A posição 2 está livre, então inserimos 35 na posição 2.

Agora temos a tabela assim:
- 0: ø
- 1: ø
- 2: 35
- 3: 3
- 4: 14
- 5: 15
- 6: 92
- 7: ø
- 8: ø
- 9: ø
- 10: 65

7. **Remoção da chave 15**: 
   - Removemos 15 da posição 5. Agora a posição 5 está livre, mas precisamos marcar como removido para que a técnica de tentativa linear funcione corretamente. Vamos marcar como "X".

8. **Inserção da chave 43**: 
   - h(43) = 43 mod 11 = 10. 
   - A posição 10 já está ocupada (por 65), então tentamos a próxima posição (0), que está livre. 
   - Inserimos 43 na posição 0.

Após todas as operações, a tabela fica assim:
- 0: 43
- 1: ø
- 2: 35
- 3: 3
- 4: 14
- 5: X (removido)
- 6: 92
- 7: ø
- 8: ø
- 9: ø
- 10: 65

Agora, analisando as opções, a que representa corretamente a tabela após as operações é:
**e) 43 – ø – 35 – 3 – 14 – X – 92 – ø – ø – ø – 65.**

Ed · Answer

Vamos analisar as operações descritas:

1. Inserção das chaves 3, 14, 15, 92, 65, 35 (nesta ordem)
2. Remoção da chave 15
3. Inserção da chave 43

Vamos simular essas operações na tabela hash:

- Inserção das chaves 3, 14, 15, 92, 65, 35 (nesta ordem):
    - 3 -> h(3) = 3 mod 11 = 3
    - 14 -> h(14) = 14 mod 11 = 3 (colisão, tentativa linear: 4)
    - 15 -> h(15) = 15 mod 11 = 4
    - 92 -> h(92) = 92 mod 11 = 4 (colisão, tentativa linear: 5)
    - 65 -> h(65) = 65 mod 11 = 10
    - 35 -> h(35) = 35 mod 11 = 2

Tabela após a inserção: ø - ø - 35 - 14 - 92 - ø - ø - ø - ø - 65 - 3

- Remoção da chave 15: A chave 15 é removida.

Tabela após a remoção: ø - ø - 35 - 14 - 92 - ø - ø - ø - ø - 65 - 3

- Inserção da chave 43: 
    - 43 -> h(43) = 43 mod 11 = 10 (colisão, tentativa linear: 0)

Portanto, a tabela após todas as operações será: 43 - ø - 35 - 14 - 92 - ø - ø - ø - ø - 65 - 3

Resposta correta: b) 43 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 65

Estrutura de Dados

Exercícios Estrutura de Dados

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Exercícios Estrutura de Dados

Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n² funciona mais rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina?

Mais conteúdos dessa disciplina