Lista7_ArvB_TabHash

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Eletrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
Lista de Exercícios 
Árvores B e Tabelas Hash 
 
1. Considerando a representação abaixo de árvore B, implemente um método (usando recursão) que 
retorna o maior elemento armazenado em uma árvore B. Faça a análise do algoritmo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2. Considerando a ordem alfabética, mostre o resultado da inserção dos elementos 
F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E nessa ordem. Considere a árvore B de ordem 3. 
Desenhe a árvore após a inserção de cada elemento. 
 
3. Durante a remoção de um elemento em uma árvore B, é possível que seja necessário ajustar a 
árvore. Quais são as operações de ajuste em árvores B? Descreva de forma sucinta quando cada 
uma delas deve ser aplicada. Mostre exemplos de ajustes em árvores B usando estas operações. 
 
4. Qual é a vantagem mais significativa do uso de tabelas hash em relação as outras estruturas de 
dados? 
 
5. Desenhe uma tabela hash com endereçamento aberto e tamanho 9 (com probing linear). Use a 
função de hash "f(k)=k%9". Insira as chaves: 5, 29, 20, 0, 27 and 18 na tabela nessa ordem e 
mostre o estado final da tabela após executar todas as operações. 
 
6. Você planeja inserir 1000 itens em uma tabela hash e quer um número médio de 2 acessos em 
uma busca com sucesso. Qual o tamanho do array interno que você pode utilizar considerando 
que a tabela tem endereçamento fechado e usa chaining para resolver os conflitos? 
 
7. Uma tabela hash com chaining tem tamanho 512. Qual o número máximo de elementos que 
podem ser colocados na tabela? 
 
A. 256 
B. 511 
C. 512 
public class BNode<T extends Comparable<T>> { 
LinkedList<T> elements; 
LinkedList<BNode<T>> children; 
BNode<T> parent; 
intmaxKeys; 
intmaxChildren; 
... 
} 
public class BTreeImpl<K,V> implementsBTree<K, V> { 
 
BNode<K,V> root; 
int order; 
 ... 
} 
D. 1024 
E. Não existe limite máximo. 
 
8. Suponha que você deseja fazer um estudo comparativo entre duas tabelas hash de tamanho 11. 
Uma delas usa endereçamento aberto com probing linear e função primária de hash h’(k)=k % m. 
A outra usa mesma função primaria e probing quadrático com c1=1 e c2=3. Qual a melhor tabela 
considerando que as operações realizadas foram apenas inserções dos valores: 10,22,31,4, 15, 28, 
17, 88, 59?