Questões de Hashing (Algoritmos e Estrutura de Dados)

Limpar Busca

Uma certa tabela de dispersão (hash) em um programa de computador utiliza a função de espalhamento h(k) = k mod m, em que k é a chave e m é o tamanho de um vetor de listas ligadas indexado por h(k).


Para m = 5013, o índice obtido para k = 10034 é

  • A 2.
  • B 8.
  • C 5013.
  • D 5021.
  • E 15047.

A técnica de hashing que, no pior caso, realiza O(1) acessos à memória para executar uma busca é denominada hashing

  • A direto.
  • B perfeito.
  • C fechado.
  • D uniforme.

Considere que em uma tabela de dispersão (ou tabela hash) de comprimento m = 9, inicialmente vazia, que usa endereçamento aberto, técnica de tentativa linear para resolver colisões e função de dispersão h(k) = k mod m, onde k é a chave a ser inserida, foram inseridas as seguintes chaves: 3, 14, 15, 81, 65, 19, 35, 40 e 50 (nesta ordem). A tabela de dispersão após estas inserções é

  • A 3-19-65-40-14-15-50-35-81.
  • B 81-19-65-3-40-50-14-15-35.
  • C 81-19-65-3-40-14-15-50-35.
  • D 19-65-3-40-14-15-50-35-81.
  • E 19-65-3-40-50-14-15-35-81.

Sobre as características de índices estruturados na forma de Btrees e Hash tables, analise as afirmativas a seguir.


I. Hash tables aplicam-se somente em buscas que referenciam a chave por inteiro (operador =).

II. B-trees favorecem consultas que buscam chaves num determinado intervalo (operadores >= e <=).

III. B-trees são usualmente mais lentas para buscas pela chave (operador =).

IV. Hash tables favorecem buscas, com o operador ‘LIKE’ do SQL, que não contenham caracteres curingas na primeira posição.

V. B-trees não se aplicam em buscas que se referem a uma substring à esquerda da chave.


Está correto o que se afirma em:

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

Qual é o método de pesquisa, no qual os registros armazenados em uma tabela são diretamente endereçados a partir de uma função aritmética sobre a chave de pesquisa?

  • A Árvores B.
  • B Hashing.
  • C Quicksort.
  • D Heapsort.
  • E Shellsort.