Questão 1885120

• Banca: FGV
• Órgão: IBGE
• Ano: 2016
• Provas: FGV - 2016 - IBGE - Analista - Análise de Sistemas - Desenvolvimento de Aplicações - Web Mobile
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

Considere uma tabela hash com as seguintes características:

1. As chaves são as letras A,B,C,D,H.J,K,M,N,O,P,R,S,T,U;

2. A tabela possui 11 posições, referenciadas pelos índices de 0 até 10;

3. A função de hash é definida como hash(x)=posição(x) mod 11 onde x é a chave, e posição(x) é a posição da chave no alfabeto ABCDEFGHIJKLMNOPQRSTUVWXYZ, tal que posição(“A”) retorna 1 e posição(“Z”) retorna 26.

Analise as afirmativas sobre a tabela após seu preenchimento com as chaves listadas acima.

I. Nenhuma chave foi alocada à posição 6;

II. A chave “K” foi alocada à posição zero;

III. As chaves “B” e “N” colidiram na posição 3;

IV.Apenas uma letra foi alocada à posição 9.

Está correto somente o que se afirma em: 

• A. I e II;
• B. I e IV;
  
• C. I, II e IV;
• D. II e III;
• E. II, III e IV.

Gabarito: C

Comentários

• Fica mais fácil se escrevermos o alfabeto e colocarmos o hash(x) correspondente (posição(x) mod 11)

  A B C D E F G H I  J K L M N O P Q R S T  U V W X Y Z
  1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4

  Lembrando que devemos nos basear nas chaves dada pela questão e não no alfabeto como um todo
  A,B,C,D,H.J,K,M,N,O,P,R,S,T,U;

  I. Nenhuma chave foi alocada à posição 6;
  Na posição 6 estão F e Q. Porém ambas não estão nas chaves dadas. CORRETA

  II. A chave “K” foi alocada à posição zero;
  CORRETA

  III. As chaves “B” e “N” colidiram na posição 3;
  B foi colocada na posição 2 e N na posição 3. ERRADA.

  IV.Apenas uma letra foi alocada à posição 9.
  Na posição 9 foram alocados I e T. Porém I não está na lista de chaves dadas. Logo, somente T foi alocada na posição 9. CORRETA.

• Força Guerreiro!!!!!!