Questão 66704

Uma professora de Algoritmos e Estruturas de Dados está introduzindo o conceito de tabelas de dispersão (hash tables). Seus alunos entendem a ideia geral de usar uma função de hash para mapear uma chave a um índice de um array, mas têm dificuldade em compreender o que acontece quando ocorre uma 'colisão' – ou seja, quando a função de hash produz o mesmo índice para duas chaves diferentes. Para explicar as estratégias de tratamento de colisão, ela se baseia em um texto clássico sobre o tema: "Nenhuma função de hash é perfeita. As colisões são inevitáveis. Portanto, uma tabela de dispersão precisa de uma estratégia para lidar com elas. Duas das estratégias mais comuns são o **Endereçamento Aberto** e o **Encadeamento Separado**. No Encadeamento Separado, cada posição do array não armazena um único elemento, mas sim um ponteiro para uma lista encadeada (ou outra estrutura de dados) contendo todos os elementos que colidiram naquela posição. Na sondagem linear, uma forma de Endereçamento Aberto, quando ocorre uma colisão no índice `i`, o algoritmo simplesmente sonda a próxima posição, `i+1`, depois `i+2`, e assim por diante, até encontrar um espaço vazio para inserir o novo elemento." A professora então propõe uma atividade: inserir a sequência de chaves [10, 22, 31, 4, 15, 28, 17, 88] em uma tabela de hash de tamanho 10, usando a função de hash `h(k) = k mod 10`.

Considerando a função de hash `h(k) = k mod 10` e uma tabela de tamanho 10, qual seria a disposição final dos elementos na tabela se a estratégia de tratamento de colisão fosse a **sondagem linear**?