Considere o esquema com a distribuição das chaves (k) numéricas de uma tabela Hash a seguir.

Acerca do esquema, avalie se as afirmativas a seguir são falsas (F) ou verdadeiras (V).

I. A função Hash utilizada é h(k) = k mod 7.

II. Há colisão em duas das chaves.

III. A complexidade do algoritmo de busca é O(log n).

As afirmativas são, respectivamente,

Considere que em uma tabela de dispersão (ou tabela hash) de módulo 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). O número de colisões para a inserção desses dados é:

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 técnica de hashing que, no pior caso, realiza O(1) acessos à memória para executar uma busca é denominada hashing

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?

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 é

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:

Qual alternativa abaixo representa um mecanismo de tratamento de colisões em tabelas hash? 

A estrutura de dados que consiste no armazenamento de cada elemento em um endereço calculado a partir da aplicação de uma função sobre a chave de busca denomina-se

A colisão é um efeito característico dos algoritmos de resumo de mensagem e ocorre, com maior frequência, quanto menor for o tamanho do bloco de bits do resumo (digest) gerado pelo algoritmo.

No caso do SHA1 (Short Hash Algorithm 1), o tamanho do bloco do resumo é

Funções hash são utilizadas por diversos protocolos de rede e possuem diversas aplicações, entre as quais a verificação de corretude de uma mensagem enviada. Sobre funções hash no contexto de redes, assinale a alternativa correta.

Algoritmos de hash são bastante utilizados como elementos de garantia da segurança da informação. A propriedade da informação garantida pela utilização desses algoritmos é a:

O tamanho, em bites, da saída do algoritmo de hash MD5 é igual a

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: 

Assinale a opção correspondente a estrutura de dados que utiliza uma função de dispersão que gera um índice a partir de determinada chave e que, para resolver os problemas de colisões, é combinada com outros tipos de estrutura de dados.

No método de transformação (hashing), os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa. Com relação às funções de transformação e colisões, assinale a opção correta.