Questões de Concurso Comentadas sobre hashing em algoritmos e estrutura de dados

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.

Considere uma busca por uma chave entre 1.000.000, que pode ser feita através de uma Busca binária, Hashing ou Árvore B de ordem 20.

Supondo que os três operam em condições semelhantes e satisfatórias, com os registros armazenados num disco rígido, assinale a opção que mostra as alternativas na ordem do menor para o maior tempo de busca

A Lei n^o 953/2005 que dispõe sobre a Taxa Judiciária do Estado no Amapá, estabelece:

Art. 7^o - A alíquota da Taxa Judiciária será de 1,5% sobre o valor da causa, observado o disposto nos artigos 5o e 6o desta Lei. Parágrafo único - Fica assegurada a Taxa Judiciária mínima de R$ 25,00 e máxima de R$ 9.950,00.

Considere que no Tribunal de Justiça do Amapá há um arquivo com uma lista que contém, em cada linha, o nome, CPF, valor da causa e taxa judiciária de milhares de pessoas. O analista judiciário do Tribunal deve propor uma solução para separar somente as pessoas que pagaram taxa mínima e as que pagaram taxa máxima. Uma vez que os dados do arquivo já tenham sido lidos e encontram-se em uma estrutura de dados do tipo tabela (vetor de estruturas), a solução proposta corretamente pelo analista, é percorrer a tabela e

Os bancos de dados, em sua organização física, baseiam-se em árvores B-trees (e suas variantes) para a implementação de índices. Analise as comparações a seguir entre B-trees e índices baseados em funções de hashing.

I. B-trees são mais rápidas na localização de um registro a partir de uma chave.

II. B-trees permitem busca com operadores de comparação “>” e “<”.

III. B-trees permitem busca a partir de uma substring à esquerda da chave.

IV. A partir de um certo ponto, o número máximo de acessos necessários para a localização de uma chave em uma B-tree não aumenta com o número total de chaves indexadas, o que tende a torná-la mais rápida em bancos de dados muito grandes.

Assinale a opção que indica o número de comparações corretas.

Considere as seguintes afirmativas comparativas entre métodos de busca baseados em árvores B e funções de hashing:

I. A inserção de chaves não ordenadas é geralmente mais rápida em métodos de hashing.

II. O número médio de acessos para localização de registros tende a ser menor para métodos baseados em hashing.

III. Métodos de hashing não disponibilizam acesso sequencial às chaves em ordem crescente ou decrescente.

É correto concluir que:

No processo de criação de um banco de dados relacional, primeiro foram criadas as tabelas onde seriam guardados os dados; depois, foi feita a inserção dos dados nessas tabelas. Nenhuma outra estrutura auxiliar foi criada no banco para melhorar o desempenho além das chaves primárias. Após realizar uma simulação de carga, com dados e aplicativos reais, o responsável percebeu que uma busca importante tentava encontrar uma pessoa pelo número do seu título de eleitor, no campo TITELE, que não era uma chave primária planejada. Essa busca demorava muito, pois o SGBD precisava procurar em todos os registros até encontrar aquele com o número desejado.

Supondo-se que o SGBD suporta visões, índices árvore-B e de tabela de espalhamento (hashs), joins e procedimentos armazenados, a maneira de acelerar essa busca ao máximo é criar um(a)

Considere um arquivo sequencial, com 10.000 registros, cujas chaves identificadoras são números inteiros de até 8 dígitos. Para criar um índice tipo hashing para esse arquivo, contendo endereços de 0 até 11.999, a mais adequada definição para uma função de hashing f(x), onde x é uma chave e ( a mod b ) é o resto da divisão de a por b, seria

Selecione a alternativa que complete corretamente a seguinte frase: “A estrutura de dados _________________ armazena valores através de chaves e se baseia em uma função de dispersão que tem por objetivo associar um índice a cada chave, e quando duas chaves recebem um mesmo índice, ocorre ___________________.":

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

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.