Questão 245188

• Banca: CESPE / CEBRASPE
• Órgão: TRT - 21ª Região (RN)
• Ano: 2010
• Provas: CESPE - 2010 - TRT - 21ª Região (RN) - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

Considerando que uma tabela hash (tabela de espalhamento) possua
quatro posições numeradas 0, 1, 2, 3 e 4, e que nela esteja
armazenada uma sequência de quadrado de valores inteiros definida
como 1, 4, 9, 16, ., n², segundo a função f (x) = x mod 5, julgue os
itens que se seguem.

Na tabela hash apresentada, não haverá colisões em suas posições.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• ERRADO. Obviamente haverá colisão pois temos apenas quatro posições para armazenar um conjunto numérico infiinto (1, 4, 9, 16, ., n2)

• A colisão pode ser detectada já no terceiro elemento a ser inserido na tabela:
  Elementos = {1, 4, 9, 16, ..., n2, ...}
  elemento 1 => posição: f(1) = 1
  elemento 4 => posição: f(4) = 4
  elemento 9 => posição: f(9) = 4 (colisão com o valor 4 inserido na posição 4)
  
• "... quatro posições numeradas 0, 1, 2, 3, 4 ..." kkk