Considere que em uma tabela de dispersão (ou tabela hash) de...

A alternativa correta é a C - 81-19-65-3-40-14-15-50-35.

Explicação do tema: A questão aborda o uso de uma tabela de dispersão (ou tabela hash) com endereçamento aberto e técnica de tentativa linear para resolver colisões. Esse tipo de estrutura de dados é frequentemente utilizado para implementar estruturas de dados associativas como dicionários e mapas. O entendimento necessário para resolver a questão inclui conhecimento sobre:

• Função de Dispersão: Uma função que mapeia uma chave para um índice em um array.
• Tentativa Linear: Técnica para tratar colisões, onde se verifica a próxima posição disponível em sequência.
• Endereçamento Aberto: Método para lidar com colisões sem usar estruturas auxiliares como listas encadeadas.

Nesse caso, temos uma tabela hash de comprimento m = 9 e a função de dispersão é h(k) = k mod m. Vamos inserir as chaves na ordem dada (3, 14, 15, 81, 65, 19, 35, 40 e 50) e verificar a posição de cada uma:

1. 3: h(3) = 3 mod 9 = 3 -> Posição 3
2. 14: h(14) = 14 mod 9 = 5 -> Posição 5
3. 15: h(15) = 15 mod 9 = 6 -> Posição 6
4. 81: h(81) = 81 mod 9 = 0 -> Posição 0
5. 65: h(65) = 65 mod 9 = 2 -> Posição 2
6. 19: h(19) = 19 mod 9 = 1 -> Posição 1
7. 35: h(35) = 35 mod 9 = 8 -> Posição 8
8. 40: h(40) = 40 mod 9 = 4 -> Posição 4
9. 50: h(50) = 50 mod 9 = 5. A posição 5 já está ocupada (por 14), então tentamos a próxima posição livre -> Posição 7

Assim, a tabela final ficará: 81 (posição 0), 19 (posição 1), 65 (posição 2), 3 (posição 3), 40 (posição 4), 14 (posição 5), 15 (posição 6), 50 (posição 7), 35 (posição 8).

Justificativa das alternativas:

• A - 3-19-65-40-14-15-50-35-81: Essa alternativa está incorreta pois a chave 3 não deveria estar na posição 0.
• B - 81-19-65-3-40-50-14-15-35: Essa alternativa está incorreta pois a chave 50 está na posição 5, mas deveria estar na posição 7.
• C - 81-19-65-3-40-14-15-50-35: Essa alternativa está correta.
• D - 19-65-3-40-14-15-50-35-81: Essa alternativa está incorreta pois a chave 81 não deveria estar na posição 8.
• E - 19-65-3-40-50-14-15-35-81: Essa alternativa está incorreta pois a chave 50 está na posição 4, mas deveria estar na posição 7.

Espero que essa explicação tenha esclarecido como funciona a inserção em uma tabela de dispersão com endereçamento aberto e tentativa linear. Se precisar de mais alguma ajuda, estou à disposição!

chaves inseridas 3, 14, 15, 81, 65, 19, 35, 40 e 50

Tabela

início tabela

posição 8 - 35/9 resta 7 logo fica na posição 8 da tabela

posição 7 - acontece que 50 dividido por 9 é 5 e deveria ficar na posição do 5, mas já ta ocupada pelo 14

posição 6 - 15/9 resta 6 logo fica na posição 6 da tabela

posição 5 - 14/9 resta 5 logo fica na posição 5 da tabela

posição 4 - 40/9 resta 4 logo fica na posição 4 da tabela

posição 3 - 3/9 resta 3 logo fica na posição 3 da tabela

posição 2 - 65/9 resta 2 logo fica na posição 2 da tabela

posição 1 - 19/9 resta 1 logo fica na posição 1 da tabela

posição 0 - 81/9 resta 0 logo fica na posição 0 da tabela

fim tabela

resultado: 81,19,65,3,40,14,15,??50 entra pq ficou sem posição??,35

Entendi a questão assim

Força Guerreiro!!!!!!

A resolução do Magno me parece correta.

Quando ele faz 50 mod 9 obtém resto 5, sendo este o índice da tabela em que será incluído o valor.

Acontece que o índice 5 já está ocupado pelo valor 14, então estamos diante de uma colisão.

O que a questão disse quando houver uma colisão? "técnica de tentativa linear para resolver colisões"

Em outra palavras, acredito que ela esteja se referindo a sondagem linear, que, em poucas palavras, significa procurar o próximo índice vazio na tabela e armazenar o valor.

E qual é o próximo índice vazio? O 7.

É por isso que o 50 foi parar naquela posição.

Fonte: https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/st-hash.html