Questão 1826992

• Banca: FGV
• Órgão: TJ-PI
• Ano: 2015
• Provas: FGV - 2015 - TJ-PI - Analista Judiciário - Analista de Sistemas / Banco de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

Numa tabela hash adequadamente dimensionada, com N chaves, o número médio de acessos para localização de uma chave situa-se entre:

• A. 1 e 2
• B. N ÷ 2 e N
• C. lg(N) e N
• D. 1 e N ÷ 2
• E. lg(N) e lg(N² )

Gabarito: A

Comentários

• Uma tabela hash adequadamente dimensionada quer dizer que ela não terá muitas colisões. As suas chaves estarão bem distribuídas. Logo, o número médio de acessos será entre 1 e 2.

• Se for por encadeamento: uso de listas encadeadas (O(n) na pesquisa)
  Outra função de hash (O(1) na pesquisa)

• Força Guerreiro!!!!!!