Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — COTEC 2021
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq632637
Banca
COTEC
Órgão
Prefeitura de São João da Ponte - MG
Ano
2021
Nível
Médio
Cargo
Técnico em Informática
Considere que em uma tabela de dispersão (ou tabela hash) de módulo 9, inicialmente vazia, que usa endereçamento aberto, técnica de tentativa linear para resolver colisões e função de dispersão h(k) = k mod m, onde k é a chave a ser inserida, foram inseridas as seguintes chaves: 3, 14, 15, 81, 65, 19, 35, 40 e 50 (nesta ordem). O número de colisões para a inserção desses dados é:
A2.
B0.
C4.
D1.
E3.
Revelar gabarito e comentário▾
GabaritoD — 1.
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 e Colisões
Gabarito: letra D. Apenas a chave 50 sofreu colisão, totalizando 1 colisão. A simulação passo a passo mostra que todas as demais chaves foram inseridas sem conflito.
A tabela hash tem módulo 9 (posições 0 a 8), função hash , endereçamento aberto com tentativa linear. Inserimos na ordem: 3, 14, 15, 81, 65, 19, 35, 40, 50.
Simulação da inserção
Chave
Posição inicial
Resultado
Colisão?
3
3
3
insere em 3
Não
14
5
5
insere em 5
Não
15
6
6
insere em 6
Não
81
0
0
insere em 0
Não
65
2
2
insere em 2
Não
19
1
1
insere em 1
Não
35
8
8
insere em 8
Não
40
4
4
insere em 4
Não
50
5
5 (ocupada)
tenta 6 (ocupada), tenta 7 (vazia)
Sim
A chave 50 é a única cujo hash inicial (5) já estava ocupado. Embora tenha sido necessário percorrer duas posições (5 e 6) até encontrar vaga, o conceito de colisão considerado na questão é o conflito inicial – ou seja, quando a posição calculada pela função hash já possui um elemento. Portanto, ocorreu 1 colisão.
SE LIGUE NESSA!
Se a contagem considerasse cada tentativa de ocupado, seriam 2 colisões, mas o gabarito oficial (1) adota a definição de colisão como o número de chaves que, no momento da inserção, encontram a posição original ocupada.