Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADESP 2018

Tabela hash com endereçamento aberto e sondagem linear

Gabarito: letra C. A sequência final da tabela, obtida inserindo as chaves 3, 14, 15, 81, 65, 19, 35, 40, 50 (nesta ordem) em uma tabela hash de comprimento m=9, inicialmente vazia, com função hash h(k)=k mod 9 e tratamento de colisões por sondagem linear, é: [81, 19, 65, 3, 40, 14, 15, 50, 35] (índices 0 a 8).

Simulação passo a passo

1. Inserir 3: h(3) = 3 mod 9 = 3 → posição 3 vazia → coloca 3.

   Tabela: [_, _, _, 3, _, _, _, _, _]

1. Inserir 14: h(14) = 14 mod 9 = 5 → posição 5 vazia → coloca 14.

   Tabela: [_, _, _, 3, _, 14, _, _, _]

1. Inserir 15: h(15) = 15 mod 9 = 6 → posição 6 vazia → coloca 15.

   Tabela: [_, _, _, 3, _, 14, 15, _, _]

1. Inserir 81: h(81) = 81 mod 9 = 0 → posição 0 vazia → coloca 81.

   Tabela: [81, _, _, 3, _, 14, 15, _, _]

1. Inserir 65: h(65) = 65 mod 9 = 2 → posição 2 vazia → coloca 65.

   Tabela: [81, _, 65, 3, _, 14, 15, _, _]

1. Inserir 19: h(19) = 19 mod 9 = 1 → posição 1 vazia → coloca 19.

   Tabela: [81, 19, 65, 3, _, 14, 15, _, _]

1. Inserir 35: h(35) = 35 mod 9 = 8 → posição 8 vazia → coloca 35.

   Tabela: [81, 19, 65, 3, _, 14, 15, _, 35]

1. Inserir 40: h(40) = 40 mod 9 = 4 → posição 4 vazia → coloca 40.

   Tabela: [81, 19, 65, 3, 40, 14, 15, _, 35]

1. Inserir 50: h(50) = 50 mod 9 = 5 → posição 5 ocupada (14) → sondagem linear: próxima posição 6 (ocupada por 15) → posição 7 vazia → coloca 50.

   Tabela final: [81, 19, 65, 3, 40, 14, 15, 50, 35]

Comparação com as alternativas

Portanto, a sequência correta é a da alternativa C.