Acerca da representação e do armazenamento de informações, assinale a opção correta.
Uma boa função de transformação de chaves tem como requisito essencial a distribuição das chaves tão unifor- memente quanto possível dentro do intervalo dos valores dos índices. Exceto esta exigência, a distribuição não é vinculada a nenhum padrão particular, sendo desejável, inclusive, que pareça totalmente aleatória. Tal propriedade deu a este método uma conotação não-científica (o significado é pulverizar o argumento e espalhá-lo desordenadamente) com o nome de
Considere um processo de recuperação de informações a partir de uma grande massa de informações previamente armazenadas, sendo a informação dividida em registros que possuem uma chave para ser utilizada na pesquisa, cujo objetivo seja encontrar uma ou mais ocorrências de registros com chaves iguais à chave de pesquisa; o conjunto de registros denomina-se tabela ou arquivo, sendo tabela o conjunto de informações armazenadas na memória interna ou principal e arquivo, o conjunto de informações armazenadas na memória secundária ou externa.
Considerando essas informações, assinale a opção correta a respeito dos métodos de acesso, organização de arquivos e estruturas de dados.
O produto da ação de algoritmos que fazem o mapeamento de uma sequência de bits de tamanho arbitrário para uma sequência de bits de tamanho fixo menor, com resistência à colisão e cujo processo reverso também não seja realizável, denomina-se
O objetivo de fazer uma busca rápida a partir de uma chave de pesquisa simples e obter o valor desejado é alcançado pela estrutura de dados especial denominada
Uma desvantagem do hashing ou endereçamento de hash, como técnica utilizada nas estruturas de armazenamento, é que
Acerca de pesquisa de dados e de operações básicas sobre
estruturas, julgue os itens que se seguem.
Ocorre o hashing quando não há o armazenamento de cada entrada de uma tabela em um específico endereço calculado a partir da aplicação de uma função chave da entrada.
A respeito dos métodos de ordenação, pesquisa e hashing, julgue
os seguintes itens.
As tabelas hashing, ou tabelas de dispersão, podem ser usadas no processo de gerenciamento de memória virtual pelo sistema operacional.
A respeito dos métodos de ordenação, pesquisa e hashing, julgue
os seguintes itens.
A estabilidade de um método de ordenação é importante quando o conjunto de dados já está parcialmente ordenado.
Considerando que uma tabela hash (tabela de espalhamento) possua
quatro posições numeradas 0, 1, 2, 3 e 4, e que nela esteja
armazenada uma sequência de quadrado de valores inteiros definida
como 1, 4, 9, 16, ., n2, segundo a função f (x) = x mod 5, julgue os
itens que se seguem.
Cada posição da tabela receberá aproximadamente o mesmo número de elementos.
Considerando que uma tabela hash (tabela de espalhamento) possua
quatro posições numeradas 0, 1, 2, 3 e 4, e que nela esteja
armazenada uma sequência de quadrado de valores inteiros definida
como 1, 4, 9, 16, ., n2, segundo a função f (x) = x mod 5, julgue os
itens que se seguem.
Na tabela hash apresentada, não haverá colisões em suas posições.
Com relação à programação, algoritmos e estrutura de dados, julgue
os itens seguintes.
No método de hashing, por meio de acesso sequencial, são utilizados tabelas e mapas para recuperar informações de endereço de arquivos de forma rápida e eficiente.
Julgue os próximos itens em relação às estruturas de dados.
No uso de estruturas de transformação de chave (hashing), a solução de colisões usando encadeamento tem como principal característica o fato de nunca transbordar. Adicionalmente, o tempo de busca na lista ligada pode ser reduzido se uma lista duplamente encadeada for utilizada.
Uma desvantagem do ou endereçamento de hash ,como técnica utilizada nas estruturas de armazenamento, é que:
Um dos maiores problemas quando se estuda a alocação de estruturas de dados é o tempo de resposta da pesquisa de uma chave em um conjunto de elementos. Como forma de contornar este problema, o Hashing faz uso de funções aritméticas que permitem que o tempo de pesquisa seja independente do número de registros da tabela.
Assinale a opção que NÃO apresenta um exemplo de Hashing.
É um tipo de estrutura de dados em que a função de dispersão é a responsável por gerar um índice a partir de determinada chave; por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados:
Julgue os itens seguintes, acerca de métodos de ordenação e busca.
No uso de funções de hash, a resolução de colisões por encadeamento utiliza uma lista para armazenar todos os elementos que compartilham o mesmo valor de hash.
__________ é um algoritmo que mapeia um conjunto grande de dados, chamado de chaves, em um conjunto menor de dados. O termo que melhor completa a frase é:
Com relação a métodos de pesquisa de dados, julgue os itens subsecutivos.
Listas encadeadas não são utilizadas na busca que emprega tabelas hash.
A busca que utiliza uma tabela hash realiza comparação das chaves para encontrar a posição do elemento que está sendo buscado.
As colisões ocorrem na utilização de tabela hash porque várias chaves podem resultar na mesma posição.
Uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.
Relativo à tabela de dispersão, dentre as alternativas abaixo, marque a alternativa INCORRETA.
Considere uma tabela de espalhamento (hash table) de comprimento igual a 11, na qual a técnica de resolução de colisões utilizada é a de encadeamento. Nessa tabela, as posições são numeradas (indexadas) com os valores 0, 1, 2, ..., 10, o mapeamento de chaves para posições usa a função hash definida por h(k) = k mod 11, onde k é o valor da chave, e mod é o operador de módulo, e os números 1, 5, 18, 20, 4, 12, 10, 34, 15, 28 e 17 foram as chaves inseridas, nessa ordem, nessa tabela de espalhamento que estava inicialmente vazia.
Qual a quantidade de posições em que houve colisão durante as inserções das chaves?
Em relação aos métodos de ordenação, pesquisa e hashing, julgue os itens a seguir.
O armazenamento e a recuperação eficientes de itens provenientes de conjuntos estáticos, tais como palavras em linguagem natural, palavras reservadas em linguagens de programação e URLs, podem ser realizados em máquinas de busca pelas funções hash perfeitas mínimas.
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
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)
Um arquivo é organizado logicamente como uma sequência de registros, cada um deles representando um objeto ou uma entidade. Com base no conhecimento sobre as diferentes maneiras de organizar registros em arquivos, considere as seguintes afirmativas.
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:
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.
A Lei no 953/2005 que dispõe sobre a Taxa Judiciária do Estado no Amapá, estabelece:
Art. 7o - 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
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
No que se refere à organização de arquivos e métodos de acesso a bancos de dados, julgue o próximo item.
O acesso direto a registros será eficiente ao se usar funções hash, visto que essas funções garantem uma relação unívoca entre o registro e a sua localização física.
Acerca de estruturas de dados, assinale a opção correta.
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.
Numa tabela hash adequadamente dimensionada, com N chaves, o número médio de acessos para localização de uma chave situa-se entre:
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.
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:
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.
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 relação à estrutura de dados, assinale a opção correta quanto ao método "hashing" .
Quais são as funções hashing mais conhecidas e usadas?
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
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 é
Julgue o item seguinte, quanto aos conceitos da programação estruturada e da programação orientada a objetos e aos métodos de ordenação, pesquisa e hashing.
Os elementos-chave nas funções de hashing são sempre
números naturais.
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:
Quanto a estruturas de dados e algoritmos básicos, julgue o item seguinte.
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 ___________________.":
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 é