Questão 888970

• Banca: CESGRANRIO
• Órgão: EPE
• Ano: 2012
• Provas: CESGRANRIO - 2012 - EPE - Analista de Gestão Corporativa - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

Considere uma tabela de espalhamento (hash table) de comprimento igual a 11, na qual a técnica de resolução de colisões utilizada é a de encadeamento. Nessa tabela, as posições são numeradas (indexadas) com os valores 0, 1, 2, ..., 10, o mapeamento de chaves para posições usa a função hash definida por h(k) = k mod 11, onde k é o valor da chave, e mod é o operador de módulo, e os números 1, 5, 18, 20, 4, 12, 10, 34, 15, 28 e 17 foram as chaves inseridas, nessa ordem, nessa tabela de espalhamento que estava inicialmente vazia.


Qual a quantidade de posições em que houve colisão durante as inserções das chaves?

• A. 0
• B. 1
• C. 2
• D. 3
• E. 4

Gabarito: D

Comentários

• h(k) = k mod 11

  k = {1,5,18,20,4,12,10,34,15,28,17}

  
  

  h(1) = 1 mod 11 = 1

  h(5) = 5 mod 11 = 6

  h(18) = 18 mod 11 = 7

  h(20) = 20 mod 11 = 9

  h(4) = 4 mod 11 = 7

  h(12) = 12 mod 11 = 1

  h(10) = 10 mod 11 = 1

  h(34) = 34 mod 11 = 1

  h(15) = 15 mod 11 = 4

  h(28) = 28 mod 11 = 6

  h(17) = 17 mod 11 = 6

  
  

  Podemos observar colisões nas posições 1, 6 e 7.

• Como sei se o encadeamento é aberto ou fechado? Não está dizendo nada...

• Leonardo o correto seria:

  h(k) = k mod 11

  k = {1,5,18,20,4,12,10,34,15,28,17}

  h(1) = 1 mod 11 = 1

  h(5) = 5 mod 11 = 5

  h(18) = 18 mod 11 = 7

  h(20) = 20 mod 11 = 9

  h(4) = 4 mod 11 = 4

  h(12) = 12 mod 11 = 1

  h(10) = 10 mod 11 = 10

  h(34) = 34 mod 11 = 1

  h(15) = 15 mod 11 = 4

  h(28) = 28 mod 11 = 6

  h(17) = 17 mod 11 = 6

  
  

  Podemos observar colisões nas posições 1, 4 e 6.

  
  

• Não entendi como foram identificadas as colisões. Me pareceu que é quando o resto é igual à própria chave. Porém, se fosse assim, não seriam 4 posições (pois na 0 o resto também é igual à chave)?

  Alguém pode me ajudar?

• Já eu não entendi é como chegou no resultado abaixo:

  h(15) = 15 mod 11 = 4

  h(28) = 28 mod 11 = 6

  15 - 11 ?? mas e o 28 - 11 ??

• Força Guerreiro!!!!!!