Exercicios

Prévia do material em texto

Fundação Universidade Federal de Rondônia 
Departamento Acadêmico de Ciência da Computação 
Estrutura de Dados II 
 
Exercícios ‐ Árvores B e variações 
 
1. Criar uma árvore‐B+ pela inserção das chaves A, B, C, D, E, F, G, H, I e J, nesta ordem. 
 Ordem da árvore: 3 
 Blocos de 3 registros. 
2. Dada uma árvore ‐B+ abaixo, remova L, M, K e A, nesta ordem. 
 Número mínimo de registros por bloco=2 
 Número máximo de registros por bloco=4 
 Ordem da árvore=3 
 
3. Quais os separadores dos blocos, considerando uma árvore‐B+ pré‐fixada? 
 
 
4. Construa a árvore‐B+ pré‐fixada sobre os blocos do exercício 3. 
 5. Realize as seguintes operações sobre a árvore‐B+ pré‐fixada do exemplo anterior 
a) inserção de CARTER 
b) inserção de DRAG 
c) remoção de BIXBY 
d) remoção de COLE 
 
6. Quais os problemas de se usar árvores binárias de busca e árvores AVL como estruturas de 
índices para grandes volumes de dados? 
7. Considere uma árvore‐B de ordem 3. Considere que o primeiro elemento do segundo nó é a 
chave promovida durante o particionamento do nó. Insira as seguintes chaves no índice: 
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, Z 
Qual o efeito da inserção das chaves em ordem alfabética? A árvore degenerou? 
8. Quais as vantagens do uso da técnica de redistribuição quando da inserção e remoção de 
chaves em uma árvore‐B? 
9. Suponha que você vai remover uma chave em uma árvore‐B, a qual causa underflow na 
página. Se pela página irmã do lado direito é necessária concatenação, e pela página irmã do 
lado esquerdo é possível redistribuição, qual opção você escolheria? Por quê? 
10. Qual a diferença entre uma árvore‐B e uma árvore‐B*? Quais as vantagens e as 
desvantagens da árvore‐B*? 
11. O que é uma árvore‐B virtual? Quais as vantagens e as desvantagens da árvore‐B virtual? 
12. O que é uma árvore‐B+? Quando ela é necessária? 
13. O que são separadores? Qual a diferença entre separadores e chaves? 
14. Para aplicações reais, juntamente com cada chave da árvore‐B é armazenada uma 
referência para o registro do arquivo de dados que contém os dados que são associados à 
chave (abordagem 1). Outra solução consiste em, juntamente com cada chave da árvore‐B, 
armazenar o registro completo de dados que contém os dados que são associados à chave 
(abordagem 2). Compare essas duas abordagens em termos de vantagens e desvantagens. 
15. Em sala de aula, considerou‐se que os campos da árvore‐B que armazenam as chaves de 
busca são campos de tamanho fixo (abordagem 1). Entretanto, a árvore‐B pode ser 
implementada considerando campos de tamanho variável para armazenar as chaves de busca 
(abordagem 2). Compare essas duas abordagens em termos de vantagens e desvantagens. 
16. Considere a seguinte trie de ordem (raio) 2, com ponteiros para buckets com capacidade 
para abrigar 100 chaves (ou registros): 
 
a. Desenhe a trie estendida e o diretório de endereços hash correspondente. 
b. Considerando que os buckets A, B e C contém, respectivamente, 100, 50 e 03 registros, dê a 
configuração do diretório, e a condição de cada bucket após a  inserção de uma nova chave 
cujo valor da função hash é 00. 
c. Ainda na configuração  inicial, considere agora que todas as chaves de B são eliminadas. O 
que acontece com o diretório? 
17. Considere um máximo de 3 elementos por bucket, e que a  função hash gera 4 bits para 
uma chave. Simule a inserção de chaves que geram os seguintes endereços: 
0000, 1000, 1001, 1010, 1100, 0001, 0100, 1111, 1011 
 
 
 
http://wiki.icmc.usp.br/images/7/72/Alg2_17.Hashing_Externo.pdf