Uma abordagem calcula a posição da chave na tabela com base no valor da chave

ENADE 2021 - QUESTÃO 33

Uma abordagem calcula a posição da chave na tabela com base no valor da chave. Este valor é a única indicação da posição. Quando a chave é conhecida, a posição na tabela pode ser acessada diretamente, sem fazer qualquer outro teste preliminar, conforme exigido na busca binária ou durante a pesquisa em uma árvore. Precisamos encontrar uma função h que possa transformar uma chave particular K — seja ela uma cadeia de caracteres, um número, um registro etc. — em um índice na tabela usada para armazenar itens do mesmo tipo que K. A função h é chamada função de escrutínio (hash) e não retorna valores únicos. Por exemplo, h(“abc”) = h(“acb”). Este problema é chamado colisão.

DROZDEK, A. Estrutura de Dados e Algoritmos em C++.

São Paulo: Cengage do Brasil, p.473, 2016 (adaptado).

Uma tabela na qual os dados são inseridos em entradas determinadas por uma função h, conforme descrito no texto, é chamada de tabela de dispersão ou tabela de espalhamento. A tabela de dispersão é representada por meio do vetor tabelaH de T posições, no qual cada posição é uma estrutura ItemDado e o procedimento de inserção em tabelaH está definido a seguir.

O valor -1 no campo chave de uma entrada na tabela significa que aquela entrada está livre; o campo Prox com o valor NULO significa que ele não aponta para nenhum item de dado. A função h(chave) simplesmente retorna o valor do resto da divisão inteira de chave por T.

Considerando as informações apresentadas e supondo que T = 9, assinale a opção que corresponde ao estado de tabelaH após a seguinte sequência de chamadas: insere(13, 6); insere(46, 7); insere(20, 22); insere(28, 25); insere(19, 26); insere(17, 9).