Sistemas De Arquivos

Exemplo de prova Algorítmos III

CENTRO UNIVERSITÁRIO DO LESTE DE MINAS GERAIS

DIRETORIA DE CIÊNCIAS EXATAS

BACHARELADO EM SISTEMAS DE INFORMAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS III

PROVA 1 – 19/09/2005 – VALOR: 25 PONTOS

Nome: ______________________________________________________

1 Descreva, através de um algoritmo, o processo de re-hash em uma tabela hash com endereçamento aberto. (4pontos)

2 Com os elementos listados a seguir construa as seguintes estruturas: (6 pontos)

a) Hashing com Endereçamento aberto com “probing” linear com tamanho 15;

b) Árvore 2-3-4;

c) Árvore B de ordem 2.

1 6 13 45 23 7 9 15 22 11 12 33

3 É listado abaixo o código da pesquisa no hashing com endereçamento aberto com “probing” linear. Mostre como inserir contadores para registrar o número de comparações entre o elemento procurado (elem) e elementos do vetor. (5

pontos)

int cont;

intPesquisa(HashLinear&t, int elem)

{

intpos=funcao_hash(t, elem);

int fim=(pos+t.tamTabela-1)%t.tamTabela;

while(cont++, pos != fim &&t.tabela[pos] != VAZIO &&t.tabela[pos] != elem)

pos = (pos+1)%t.tamTabela;

if(t.tabela[pos] == elem)

return pos;

return VAZIO;

}

4 Quais as vantagens do hash com resolução de colisões por encadeamento em relação ao hash com endereçamento aberto? (5 pontos)

5 A seguir é apresentado o código da função hash para uma tabela com endereçamento aberto com “probing” linear. Ao utilizar uma tabela hash de tamanho 1000 para armazenar 200 valores inteiros que variam na faixa de 0 a 100, foi verificado que o desempenho da pesquisa é ruim. Proponha alteração(alterações) na função hash para espalhar melhor os elementos pela tabela.

intfuncao_hash(HashLinear&t, int valor) {

return valor % t.tamTabela;

}