Questões de Concurso Sobre hashing em algoritmos e estrutura de dados

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.

Acerca de estruturas de dados, assinale a opção correta.

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

Um Programador da Defensoria Pública do Estado de São Paulo foi solicitado a propor uma solução para o problema: Há uma quantidade grande de dados classificáveis por chave e estes dados devem ser divididos em subconjuntos com base em alguma característica das chaves. Um método eficiente deve ser capaz de localizar em qual subconjunto deve-se colocar cada chave e depois estes subconjuntos bem menores devem ser gerenciados por algum método simples de busca para que se localize uma chave rapidamente. O Programador propôs como solução, corretamente, a implementação de

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

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

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.