PERGUNTA 1 Uma tabela hash recebe como chave valores inteiros. Internamente, a tabela hash foi implementada como um vetor de tamanho 13, com elementos indexados de 0 a 12. Para tratamento de colisões, é usado o teste linear. Vamos assumir que a seguir temos uma tabela hash obtida após algumas operações de inserção. Note que "-1" indica uma posição vazia. Dito isso, assinale a alternativa correta.
Soluções para a tarefa
Resposta:
Alternativa <D>.
Explicação:
Se quisermos inserir o elemento 20, ele será mapeado pela função de espalhamento para a posição onde está o elemento 98. Nesse caso, o teste linear tentaria colocar na posição seguinte, que também está ocupada pelo elemento 99, restando então colocar o elemento 20 na posição 9, que está livre.
Os números serão armazenados nos endereços de memória de 0 a N-1. Este método tem o problema de que dois ou mais elementos podem produzir o mesmo resto e um índice pode ser apontado por vários elementos.
Esse fenômeno é chamado colisão. Se o número N for 7, os seguintes números são transformados em:
1679 → 6
4567 → 3
8471 → 1
0435 → 1
5033 → 0
O tempo de pesquisa é bastante reduzido e não há necessidade de colocar restrições no tamanho do array, pois os nós podamos ser adicionados dinamicamente à lista.
Teste linear
O teste linear consiste em que uma vez detetada a colisão. Exemplo: Se a posição 397 já estava ocupada, o registro com a chave 0596397 é colocado na posição 398, que está disponível. Uma vez que o registro tenha sido inserido nesta posição, outra posição geradora de registro 397 ou 398 é inserida na próxima posição disponível.
Saiba mais sobre componentes da tabela em: https://brainly.com.br/tarefa/41555616
#SPJ2
