Prévia do material em texto

P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 1/7 
Aluno(a):__________________________________________ matrícula:____________ 
 
 
1a) 1.0 
2a) 2.0 
3a) 2.0 
4a) 2.0 
5a) 3.0 
 
 
I. A prova é individual e sem consulta. 
II. A interpretação faz parte da questão. 
III. O tempo de prova é 1:30 h. 
IV. As respostas devem seguir as questões. 
V. Caso precise de rascunho use o verso da folha. 
VI. Caso parte da resposta esteja no verso, indique claramente este fato. 
 
 
P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 2/7 
1) (1.0 pontos) A árvore a seguir é conhecida como árvore de Fibonacci. Ela é um caso especial 
pois temos o número máximo de altura para um número mínimo de nós em uma árvore 
balanceada. Remova desta árvore o nó 6 e depois faça a inserção dele novamente. Mostre 
graficamente as rotações que aconteceram. 
 
Resp.: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 3/7 
2) (2.0 pontos) Responda se a árvore B abaixo é valida e se ela é resultado da inserção das chaves 
exatamente nessa ordem:1, 3, 6, 8, 14, 32, 38, 39, 41. Justifique sua resposta de forma completa. 
 
Resp.: 
 
A árvore apresentada é válida, pois para árvores B a página raiz pode apresentar 
menos da metade dos elementos. Contudo o resultado da inserção dos elementos na 
ordem apresentada geraria uma árvore com a configuração apresentada abaixo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 4/7 
3) (2.0 pontos) Escreva em C uma função para determinar se uma árvore é AVL. A função deve 
receber como parâmetro o endereço do nó raiz da árvore e retornar o valor 1 se for AVL e 0 caso 
contrário. Use a seguinte estrutura: 
 
struct no { 
 void *chave; 
 struct no *esq, *dir; 
}; 
 
 
Resp.: 
 
 
int checkAVL( struct no *node ) { 
 if( node==NULL ) return 0; 
 int esq = checkAVL( node->esq ); 
 int dir = checkAVL( node->dir ); 
 if( ( dir < 0 ) || ( esq < 0 ) ) return -1; 
 if( abs( dir - esq ) > 1 ) return -1; 
 return( max( abs( dir ), abs( esq ) ) + 1 ); 
} 
 
int AVL( struct no *node ) { 
 if( checkAVL( node ) >= 0 ) return 1; 
 else return 0; 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 5/7 
4) (2.0 pontos) Descreva a diferença entre as árvores B e B+. Exemplifique cada uma das estruturas 
com ordem 3 e altura 3. Por que a árvore B+ é normalmente preferida como estrutura de acesso a 
arquivos de dados? 
Resp.: 
 
A diferença de uma árvore B é que nesta o nós internos possuem apenas chaves, 
somente os nós folhas que possuem chaves e dados, além disso as folhas são ligadas 
por uma lista encadeada. 
 
Um exemplo de árvore B é o seguinte: 
 
 
 
 
 
 
 
 
 
Já os mesmos dados em uma árvore B+ poderiam ser representados como: 
 
 
 
 
 
 
 
 
 
 
 
Com a árvore B+ foi possível organizar um arquivo de maneira que o processamento 
sequencial e aleatório de chaves fossem eficientes. Além disso os apontamentos 
somente nas folhas permitem que nós mais simples sejam usados para indexar a busca 
e depois nós mais completos acessarem os dados em sí. 
 
 
 
 
P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 6/7 
5) (3.0 pontos) Considere o grafo ponderado não direcionado abaixo: 
a. (1 ponto) Liste os índices na ordem que eles serão visitados se for realizada uma busca por 
profundidade (depth-first search) começando pelo nó A. Assuma que os vizinhos de um nó são 
visitados por sua ordem alfabética. 
b. (1 ponto) Faça a mesma ordenação com as mesmas regras porém usando busca em largura 
(breadth-first search). 
c. (1 ponto) Usando Kruskal, mostre qual é a árvore geradora de custo mínimo. 
 
Resp.: 
 
a) A – B – C – E – D – I – H – J – F – G – K 
 
b) A – B – G – C – F – E – J – D – I – H – K 
 
c) 
 
 
 
 
 
 
 
 
 
 
 
 
 
P2 INF1010-Estruturas de Dados Avançadas 2012.2 
26nov2012 Página 7/7 
Protótipos e macros que podem ser úteis: 
 
 
stdio.h: 
int scanf (char* formato, ...); 
int printf (char* formato, ...); 
FILE* fopen (char* nome, char* modo); 
int fclose (FILE* fp); 
int fscanf (FILE* fp, char* formato, ...); 
int fprintf (FILE* fp, char* formato, ...); 
char* fgets(char* str, int size, FILE* fp)); 
int sscanf(char* str, char* formato, ...); 
 
math.h: 
double sqrt (double x); 
double pow (double x, double exp); 
double cos (double radianos); 
double sin (double radianos); 
 
string.h: 
int strlen (char* s); 
int strcmp (char* s, char *t); 
char* strcpy (char* destino, char* origem); 
char* strcat (char* destino, char* origem); 
 
stdlib.h: 
int abs ( int n ); 
void* malloc (int nbytes); 
void free (void* p); 
void qsort (void *vet, int n, int tam, int (*comp) (const void*, const void*));