As chaves: 10, 28, 2, 7, 45, 25, 40, 29, são para ser inseridas na seguinte tabela hash. A função hash é key % 11. As colisões são resolvidas pelo método "hash-and-search" (Open Addressing and Linear Probing). Em que célula uma chave 29 ocupará, eventualmente?

Alternativa C - 9

Para resolver esta questão, precisamos simular o processo de inserção das chaves na tabela hash seguindo a função dada e o método de resolução de colisões.

Análise Detalhada

Conceitos Chave:

• Função Hash: h(key) = key \pmod{11}. O resultado é o índice inicial onde a chave deve ser colocada.
• Linear Probing: Se o índice calculado já estiver ocupado, verificamos o próximo índice sequencialmente (i+1) até encontrar um espaço livre. Como a tabela tem tamanho 11, usamos módulo 11 para "voltar ao início" se necessário.

Simulação Passo a Passo:

Vamos inserir as chaves na ordem apresentada: 10, 28, 2, 7, 45, 25, 40, 29.

1. Chave 10:

• $10 \pmod{11} = 10$.
• Índice 10 vazio \rightarrow Insere em 10.

1. Chave 28:

• $28 \pmod{11} = 6$.
• Índice 6 vazio \rightarrow Insere em 6.

1. Chave 2:

• $2 \pmod{11} = 2$.
• Índice 2 vazio \rightarrow Insere em 2.

1. Chave 7:

• $7 \pmod{11} = 7$.
• Índice 7 vazio \rightarrow Insere em 7.

1. Chave 45:

• $45 \pmod{11} = 1$.
• Índice 1 vazio \rightarrow Insere em 1.

1. Chave 25:

• $25 \pmod{11} = 3$.
• Índice 3 vazio \rightarrow Insere em 3.

1. Chave 40:

• $40 \pmod{11} = 7$.
• Colisão! O índice 7 já possui a chave 7.
• Tenta próximo índice: (7+1) \pmod{11} = 8.
• Índice 8 vazio \rightarrow Insere em 8.

1. Chave 29 (A questão pede):

• $29 \pmod{11} = 7$.
• Colisão! O índice 7 está ocupado pela chave 7.
• Tenta próximo índice: (7+1) \pmod{11} = 8.
• Colisão! O índice 8 está ocupado pela chave 40.
• Tenta próximo índice: (8+1) \pmod{11} = 9.
• Índice 9 está vazio \rightarrow Insere em 9.

Estado Final da Tabela (parcial):

Portanto, a chave 29 acabará ocupando a célula de índice 9.