aed3-2011-1-exercicio-4

Prévia do material em texto

Universidade Federal de Lavras
Departamento de Ciência da Computação
GCC109 – Algoritmos e Estruturas de Dados III
Professor: Denilson Alves Pereira
Lista de Exercícios 4
 Data Limite de Entrega: 08/05/11 (turma 10A) e 12/05/11 (turma 14A)
 O exercício deve ser entregue pelo Moodle (http://aluno.dcc.ufla.br). Envie arquivos somente nos 
formatos txt e pdf (não enviar .doc, .docx, .odt etc.). Arquivos compactados somente .zip e .tar.gz (não 
enviar .rar, .z etc.). Não use acentos e nem “ç” nos nomes de arquivo.
 Exercícios copiados receberão nota zero
1. Mostre a árvore B*, de ordem m = 3, resultante após a inserção das chaves abaixo. Os itens (a), 
(b) e (c) formam uma sequência de inserções na mesma árvore.
(a) 7, 10, 12, 3, 5, 8, 4, 6, 9, 11
(b) 13, 21, 22, 14, 15, 16, 17, 18, 19, 20
(c) 32, 31, 30, 29, 28, 27, 26, 25, 24, 23
2. Considerando a árvore B* criada no exercício anterior, mostre a árvore resultante após a 
remoção das chaves abaixo. Os itens (a), (b) e (c) formam uma sequência de remoções da 
mesma árvore.
(a) 16, 17, 18, 19, 20
(b) 32, 31, 30, 29, 28
(c) 3, 7, 6, 4, 5
3. Repita os exercícios (1) e (2) para uma árvore B+ de ordem m1 = 3 para as páginas internas e 
ordem m2 = 2 para as páginas externas (folhas).
4. Repita o exercício (1) para uma árvore 2-3-4. Depois mostre como representar a árvore final 
como uma árvore SBB e uma árvore rubro-negra.
5. Considere a estrutura de dados abaixo para implementação da árvore B+ (proposta por Nivio 
Ziviani). Acrescente a essa estrutura de dados uma lista sequencial para implementação do 
acesso sequencial em ordem crescente dos registros armazenados na árvore.
#define MM  1
#define MM2 2
typedef int TipoChave;
typedef struct TipoRegistro {
  TipoChave Chave;
  /* outros componentes */
} TipoRegistro;
typedef enum {
   Interna, Externa
} TipoIntExt;
typedef struct TipoPagina *TipoApontador;
typedef struct TipoPagina {
  TipoIntExt Pt;
  union {
       struct {
       int ni;
     TipoChave ri[MM];
       TipoApontador pi[MM + 1];
       } U0;
       struct {
       int ne;
       TipoRegistro re[MM2];
       } U1;
  } UU;
} TipoPagina;
6. Implemente a função ImprimeOrdenado, que imprime as chaves dos registros da árvore B+ 
declarada no exercício anterior em ordem crescente.
7. Implemente a função Insere(TipoRegistro Reg, TipoApontador *Ap), que insere o registro Reg na 
árvore B* apontada por *Ap.
	GCC109 – Algoritmos e Estruturas de Dados III
	Lista de Exercícios 4