Questão 3136069

• Banca: Exército
• Órgão: EsFCEx
• Ano: 2019
• Provas: Exército - 2019 - EsFCEx - Oficial - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

Suponha que uma função hash seja escolhida aleatoriamente de uma coleção universal de funções hash e usada para aplicar hash a n chaves em uma tabela T de tamanho m, usando encadeamento para resolver as colisões. Se a chave k não estiver na tabela, o comprimento esperado E [n_h(k) ] é no máximo o fator de carga

• A. α = n/m
• B. 1 + α
• C. h(k) – 1
• D. α = (n/m) – 1
• E. 1 – α

Gabarito: A

Comentários

• Resposta letra A

• Uma tabela de dispersão ou tabela de hash é um vetor cujas posições armazena zero, uma, ou mais chaves.

  M : número de posições na tabela de hash

  N : número de chaves da tabela de símbolos

   = N/M :  fator de carga (load factor)