Questões de Algoritmos e Estrutura de Dados - Hashing para Concurso

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

Os métodos hashing envolvem o processo de transformação de uma chave em um endereço. Sobre estes métodos é INCORRETO afirmar:

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:

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 é

O Quicksort é um dos métodos de ordenação mais eficientes disponíveis e a técnica de busca por espalhamento ou hashing é muito utilizada em diversas aplicações. Em relação a estes métodos é correto afirmar:

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:

Sobre os algoritmos de hash MD5 e SHA, analise as afirmativas a seguir.

I. O MD5 e o SHA são invulneráveis ao ataque de aniversário.

II. O SHA-1 possui tamanho de hash de 20 bytes.

III. Ambos são algoritmos de hash, tendo como entrada dados de tamanho variável e saída de tamanho também variável.

IV. O MD5 gera um valor de hash de 128 bits.

Estão corretas as afirmativas

No Hash extensível, considerando d como sendo a profundidade global do diretório, o tamanho do bucket será:

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

Leia o fragmento a seguir.

“Hashing para arquivos em disco denominam‐se _____. Para se adaptar as características de armazenamento em disco, se considera que o espaço de endereços alvo é constituído por _____, cada um deles mantém múltiplos registros, formando um _____ de blocos consecutivos.”

Assinale a alternativa cujos itens completam corretamente as lacunas do fragmento acima.

Em processamento de dados, diversas técnicas são estudadas como forma de tornar mais eficazes os processos de indexação, organização e armazenamento de dados. Sobre as afirmações abaixo, assinale com V as verdadeiras e com F as falsas.

( ) O hashing é uma metodologia de indexação de arquivos empregada por sistemas operacionais que possibilita o acesso sequencial aos dados.

( ) A organização direta de arquivos também é conhecida como organização aleatória de arquivos e possibilita acessar diretamente um registro em disco, usando-se uma chave de registro.

( ) Uma colisão acontece quando os discos deixam de funcionar ao executarem uma operação de gravação (escrita).

( ) Dispositivo de armazenamento com acesso direto é indispensável à organização sequencial de arquivos, pois permite a criação de novos arquivos sequenciais, contendo tanto os registros atualizados quanto os não alterados.

( ) A organização sequencial de arquivos determina que os registros sejam armazenados de acordo com um campo-chave. É exemplo de um campo-chave o CPF de um indivíduo.

Assinale a alternativa que contém a sequência CORRETA, de cima para baixo.

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.

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

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.