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

Question

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

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

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

Estrutura de Dados I

Outros

Essa pergunta também está no material:

Exercícios Estrutura de Dados

Estrutura de Dados I • Universidade Norte do ParanáUniversidade Norte do Paraná

💡 1 Resposta

Faça como milhares de estudantes: teste grátis o Passei Direto

Agora você pode testar o

Passei Direto grátis

✏️ Responder

Outros materiais

Perguntas relacionadas

dada uma tabela hash de tamanho m = 10 com endereçamento aberto, mostre a tabela apos a inserção das chaves 371, 121, 173, 203, 11 para a seguinte ...

Dada uma tabela Hash de tamanho m = 10 com endereçamento aberto, mostre a tabela após a inserção das chaves 173, 203, 11 para a seguinte função de ...

Dada uma tabela Hash de tamanho m=10 com dendereçamento aberto, mostre a tabela após a inserção das chaves 371,121,173,203,11 para a seguinte funçã...

Materiais relacionados

Outros materiais