Questão de Tecnologia da Informação · FCC TRT19 2022 (nº 24)

Uma tabela hash (ou hash table) é uma estrutura de dados que armazena pares chave-valor, permitindo acesso rápido aos dados. Ela usa uma função hash para converter uma chave em um índice numérico (posição) no vetor, e um método de resolução de colisões para lidar com chaves diferentes que geram o mesmo índice.

• (A) Incorreta: Houve colisões. Adriano (12) e Luísa (22) colidem na posição 2 ($12 \pmod{10} = 2$, $22 \pmod{10} = 2$). Carlos (15) e Beatriz (25) colidem na posição 5 ($15 \pmod{10} = 5$, $25 \pmod{10} = 5$).
• (B) Incorreta: Jorge (17) ocupará a posição 7 ($17 \pmod{10} = 7$). Fernando (18) ocupará a posição 8 ($18 \pmod{10} = 8$). A expressão "será deslocado" é imprecisa, pois Fernando é colocado diretamente na posição 8, que é seu endereço hash primário, e não é movido de outro lugar devido a uma colisão. Em encadeamento separado, elementos colididos são adicionados a uma lista na sua posição hash, não deslocados para outras posições do vetor.
• (C) Incorreta: Para pesquisar Adriano (12), calculamos $12 \pmod{10} = 2$. No índice 2, a imagem mostra que Adriano é o primeiro elemento da lista. Portanto, seria necessária apenas 1 comparação (com o próprio Adriano) para encontrá-lo.
• (D) Incorreta: Uma pseudocolisão é um termo geralmente associado a métodos de endereçamento aberto (como sondagem linear ou quadrática), onde a sequência de sondagem de uma chave é afetada por uma posição ocupada por uma chave que não colidiu diretamente com ela, mas foi colocada ali devido a uma colisão anterior. No método de encadeamento separado (como o usado aqui), quando duas chaves (como Adriano e Luísa) geram o mesmo índice, isso é simplesmente chamado de colisão.
• (E) Correta: Para Pedro, cuja chave é 14, aplicamos a função hash: $h(14) = 14 \pmod{10} = 4$. Portanto, Pedro ocupará a posição 4 do vetor.