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.
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.
Se tentarmos inserir o elemento 24, criaremos uma colisão com o elemento 52, sendo que esta colisão será tratada pelo teste linear adicionando o 24 na posição 1.
Se inserirmos o elemento 60, ele será fisicamente colocado exatamente na posição indicada pela função de espalhamento.
Se removermos o 98 e depois inserirmos o elemento 15, este último ficará na posição 7.
Observando a configuração atual da tabela hash, podemos concluir que apenas uma colisão ocorreu, dado que apenas um elemento está posicionado em lugar diferente daquele indicado pela função de espalhamento.
Anexos:
Soluções para a tarefa
Respondido por
4
Resposta:
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.
Explicação:
10/10
Perguntas interessantes