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.

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:

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.   
I. Uma organização de arquivo hash (também chamada de acesso direto) fornece um acesso muito rápido aos registros, quando a condição de pesquisa é de igualdade em um único campo; neste caso, o campo é chamado campo de hash. A ideia do hashing é forncecer uma função h, chamada função hash, que, aplicada ao valor do campo hash de um registro, gere o endereço do bloco do disco no qual o registro será armazenado.
II. Em uma organização de arquivo heap, os registros são armazenados fisicamente em ordem sequencial a partir dos valores de um de seus campos, chamado campo de classificação. Na organização de arquivo heap, a inclusão e a exclusão de registros são operações dispendiosas porque os registros deverão permanecer ordenados fisicamente.
III. Em uma organização de arquivo sequencial, os registros estão posicionados no arquivo segundo a ordem pela qual foram incluídos, de forma que os novos registros são acrescentados ao final do arquivo ou onde haja espaço disponível. Na organização sequencial, para ler todos os registros pela ordem dos valores de algum campo, é preciso criar uma cópia do arquivo e ordená-la através de técnicas especiais de classificação externa.
IV. As operações em arquivos são geralmente divididas em operações de recuperação e operações de atualização. As operações de recuperação não alteram nenhum valor no arquivo, apenas localizam certos registros, de forma que seus valores de campo possam ser examinados e processados. As operações de atualização mudam o arquivo por meio da inclusão ou da exclusão de registros ou pela modificação de valores dos campos.   
Assinale a alternativa CORRETA.

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?

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.

__________ é 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 é:

É 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:

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.