Questão 5 (2 pontos):
Considere uma tabela de Hash com encadeamento interno, e area de colisao (separada do resto da tabela, com 16 posicoes dispon...

Question

Questão 5 (2 pontos):Considere uma tabela de Hash com encadeamento interno, e area de colisao (separada do resto da tabela, com 16 posicoes disponiveis na tabela e outras 16 na area de colisao), e funcao hash dada por h(x) = x mod 16.Considere que a area de colisao encontra-se inicialmente em uma lista apontada por L de posicoes disponiveis.a) Mostre como fica a hash com a insercao das chaves 2, 34, 18, 16, 32 , 64, e 34.b) Escreva o algoritmo de busca de uma chave x nesta tabela hash.

Ed · Answer

a) Para inserir as chaves 2, 34, 18, 16, 32, 64 e 34 na tabela de hash com encadeamento interno, utilizando a função hash h(x) = x mod 16, faremos o seguinte:

1. Inicialmente, a tabela de hash e a área de colisão estão vazias.
2. Inserimos a chave 2 na posição h(2) = 2 da tabela de hash.
3. Inserimos a chave 34 na posição h(34) = 2 da tabela de hash. Como essa posição já está ocupada, inserimos a chave na primeira posição disponível da área de colisão.
4. Inserimos a chave 18 na posição h(18) = 2 da tabela de hash. Como essa posição já está ocupada pela chave 34, inserimos a chave na primeira posição disponível da área de colisão.
5. Inserimos a chave 16 na posição h(16) = 0 da tabela de hash.
6. Inserimos a chave 32 na posição h(32) = 0 da tabela de hash. Como essa posição já está ocupada pela chave 16, inserimos a chave na primeira posição disponível da área de colisão.
7. Inserimos a chave 64 na posição h(64) = 0 da tabela de hash. Como essa posição já está ocupada pela chave 16, inserimos a chave na primeira posição disponível da área de colisão.
8. Inserimos a chave 34 na posição h(34) = 2 da tabela de hash. Como essa posição já está ocupada pela chave 34, inserimos a chave na primeira posição disponível da área de colisão.

A tabela de hash com a inserção das chaves fica da seguinte forma:

Tabela de hash:
0: 16 -> 32 -> 64
1:
2: 2 -> 34 -> 18 -> 34
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

Área de colisão:
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

b) O algoritmo de busca de uma chave x nesta tabela hash seria o seguinte:

1. Calculamos a posição da chave na tabela de hash utilizando a função hash h(x).
2. Verificamos se a chave está na posição calculada da tabela de hash. Se estiver, retornamos a chave encontrada.
3. Caso contrário, verificamos se a chave está na área de colisão. Se estiver, retornamos a chave encontrada.
4. Se a chave não for encontrada nem na tabela de hash nem na área de colisão, retornamos que a chave não existe na tabela.

Espero ter ajudado! Se tiver mais alguma dúvida, é só perguntar.

Questão 5 (2 pontos): Considere uma tabela de Hash com encadeamento interno, e area de colisao (separada do resto da tabela, com 16 posicoes dispon...

Estrutura de Dados I

Outros

Essa pergunta também está no material:

Prova-Final-2012-1-Estrutura-de-Dados

Estrutura de Dados I • Universidade Federal do Rio de JaneiroUniversidade Federal do Rio de Janeiro

💡 1 Resposta

✏️ Responder

Outros materiais

Perguntas relacionadas

Considere uma tabela de Hash com encadeamento interno, e area de colisao (separada do resto da tabela, com 8 posicoes disponiveis na tabela e outra...

3- Considere uma tabela de hash com encadeamento externo. 3.1 - Escreva o algoritmo de insercao de um no de chave x desta tabela hash 3.2- Consider...

3.1- Insira as seguintes chaves: 6, 41, 2, 33, 17 e 7 em uma tabela hash com encadeamento externo. Utilize a função de hash h(x) = x mod 5.

No tratamento de colisões por encadeamento em uma tabela hash T, uma posição j qualquer da tabela possui uma lista encadeada contendo todos os elem...

Materiais relacionados

Outros materiais