Questão de Algoritmos e Estrutura de Dados — Hashing — FGV 2024
Algoritmos e Estrutura de Dados›Hashing
Código
fg101719
Banca
FGV
Órgão
TRF - 1ª REGIÃO
Ano
2024
Nível
Superior
Cargo
Técnico Judiciário - Área Administrativa - Especialidade: Desenvolvimento de Sistemas de Informação
Considere as afirmações a seguir.I. Função de Hash: h(x) = x % 10 mapeia uma chave x para um índice entre 0 e 9.II. Operação de Módulo: % retorna o resto da divisão.III. Colisões: quando várias chaves mapeiam para o mesmo índice, ocorre uma colisão.IV. Encadeamento: técnica para resolver colisões na qual cada posição na tabela contém uma lista de chaves.Nesse contexto, o analista Zudo está implementando um sistema de armazenamento de dados utilizando uma tabela Hash de tamanho 10. Ele escolhe a função de Hash h(x) = x % 10 para mapear as chaves. Ao enfrentar o desafio das colisões, Zudo opta pela técnica de encadeamento para gerenciá-las. Ele então insere as chaves {15, 25, 35, 45, 55} na tabela Hash. A estrutura final dessa tabela será:
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Tabela Hash com Encadeamento – Inserção de Chaves Colidentes
Gabarito: letra D. As chaves 15, 25, 35, 45 e 55, ao aplicarem a função hash h(x) = x % 10, produzem todas o resto 5. Como a tabela tem tamanho 10 (índices 0 a 9) e a técnica de resolução de colisão é o encadeamento, todas as chaves são inseridas na mesma posição (índice 5) em uma lista ligada, resultando na estrutura: índices 0 a 4 vazios, índice 5 com a lista [15, 25, 35, 45, 55], e índices 6 a 9 vazios.
A função hash mapeia cada chave x para o resto da divisão por 10. Calculando:
15 % 10 = 5
25 % 10 = 5
35 % 10 = 5
45 % 10 = 5
55 % 10 = 5
Todas as chaves colidem para o mesmo índice. No encadeamento, conforme descrito na literatura (CLRS), cada posição da tabela contém um ponteiro para uma lista ligada que armazena todas as chaves que mapeiam para aquele índice. As demais posições permanecem vazias (representadas por []).
Índice
Conteúdo (lista encadeada)
0
[]
1
[]
2
[]
3
[]
4
[]
5
[15, 25, 35, 45, 55]
6
[]
7
[]
8
[]
9
[]
1h(15)=5 → índice 515
2h(25)=5 → colisão25
3h(35)=5 → colisão35
4h(45)=5 → colisão45
5h(55)=5 → colisão55
6Índice 5: [15,25,35,45,55]
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Apresenta cada chave em uma posição separada a partir do índice 5 ([15], [25], [35], [45], [55]). Isso ignora a colisão: todas as chaves têm o mesmo hash e devem estar na mesma lista, e não em listas individuais em índices distintos.
Alternativa B — ❌ Incorreta
Mostra o índice 5 com [15, 25] e depois [35] no índice 6, [45] no 7, [55] no 8, e [ ] no 9. Apenas as chaves 15 e 25 foram agrupadas; as demais foram colocadas em índices diferentes, o que não corresponde ao resultado da função hash (todas dão resto 5).
Alternativa C — ❌ Incorreta
Coloca [15, 25, 35, 45] no índice 5 e [55] no índice 9. A chave 55 também tem hash 5, portanto deveria estar na mesma lista do índice 5, não em índice separado.
Alternativa D — ✅ Correta ⟵ GABARITO
Representa exatamente a estrutura esperada: índices 0–4 vazios, índice 5 contendo a lista [15, 25, 35, 45, 55], e índices 6–9 vazios. Todas as chaves colidem e são inseridas na mesma posição, conforme a técnica de encadeamento.
Alternativa E — ❌ Incorreta
Semelhante à D, mas acrescenta um elemento [55] extra no índice 9, duplicando a chave 55. A chave 55 já está na lista do índice 5; não há razão para uma segunda ocorrência.
NÃO CAIA NESSA!
A banca testa se o candidato compreende que todas as chaves com o mesmo resto da divisão vão para o mesmo índice. As alternativas tentam espalhar as chaves ou duplicá-las, confundindo quem não aplica corretamente a função hash. Lembre-se: o encadeamento agrupa todas as colisões em uma única lista na respectiva posição.