P1 - 2011.1 (Gabarito)

Prévia do material em texto

P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 1/7 
Aluno(a):__________________________________________número:____________ 
 
1a) 2.0 
2a) 2.5 
3a) 2.0 
4a) 2.0 
5a) 1.5 
 
I. A prova é individual e sem consulta. A interpretação faz parte da questão. 
II. O tempo de prova é 1:30 h. 
III. As repostas devem seguir as questões. Caso precise de rascunho use o verso da folha. 
 
1) (2.0 pontos.) Tabela de dispersão (hash table) 
 
Mostre através de um desenho como ficaria a tabela hash de 7 elementos que recebesse as 
seguintes chaves de busca (nesta ordem): 
7,10,15,14,17,16 
a) Se ela fosse com encadeamento exterior (o do trabalho) e com a função: ���� � �%7 
 
 
 
b) Se ela fosse com encadeamento aberto e com a função: 
���, 	� � �� 
 	�%7, 	 � 0,1,2, … 
 
 
 
0 7 
1 15 
2 14 
3 10 
4 17 
5 16 
6 
 
P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 2/7 
2) (2.5 pontos) Árvores binárias de busca em ordem crescente. (obs.: os nós nulos não estão 
representados nos desenhos). 
a) Marque sim [S] ou não [N] se árvores abaixo são ou não árvores binárias de busca. 
 
 
 
b) Marque com a letra (m) o nó da ABB abaixo que armazena o menor valor da árvore. 
c) Marque com a letra (s) o nó da ABB abaixo que é o sucessor do nó “x”. 
 
d) No algoritmo do trabalho do curso como ficaria a ABB abaixo após a retirada dos nós 17, 30 
e 35 (nesta ordem)? 
 
 
P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 3/7 
3) (2.0 pontos.) Considere o vetor de heap mostrado abaixo. Mostre quais seriam as modificações 
que o algoritmo de remoção provocaria no vetor. Ou seja, mostre explicando como o vetor iria 
se modificando, chegando até ao heap final. 
95,60,78,39,28,66,70,33 
 
Sai 95 e o heap fica com: 33,60,78,39,28,66,70 
33 troca com seu maior filho que é o 78: 78,60,33,39,28,66,70 
33 na posição 2 tem filhos 2*2+1=5 e 2*2+2=6. 
Ou seja, 66 e 70, respectivamente. 33 troca de posição com o 70 (maior). 
 
 
Final: 78, 60, 70, 39, 28, 66, 33 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 4/7 
 
 
P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 5/7 
4) (2.0 pontos) Escreva a função de inserção numa árvore binária de busca que armazena inteiros 
em ordem crescente, cujo protótipo e estruturas estão mostrados abaixo. (obs.: se quiser você 
pode criar funções auxiliares, mas elas também têm que ser apresentadas aqui). 
 
typedef struct _abb Abb; 
struct _abb { 
 int info; 
 Abb* pai; 
 Abb* esq; 
 Abb* dir; 
}; 
 
Abb* abb_insere(Abb* raiz, int info); 
 
Abb* abb_insere (Abb* r, int info){ 
 if (r==NULL) { 
 Abb* no = (Abb*) malloc(sizeof(Abb)); 
 no->info = info; 
 no->esq = no->dir = NULL; 
 return no; 
 } 
 else if (info<r->info) { 
 r->esq = abb_insere(r->esq,info); 
 r->esq->pai = r; 
 } 
 else if (info>r->info) { 
 r->dir = abb_insere(r->dir,info); 
 r->dir->pai = r; 
} 
 return r; 
} 
 
P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 6/7 
Ou: 
static Abb* cria_filho(Abb* pai, int info) { 
 Abb* filho = (Abb*) malloc(sizeof(Abb); 
 filho->info = info; 
 filho->pai = pai; 
 filho->esq = filho->dir = NULL; 
 return filho; 
} 
 
 
Abb* abb_insere (Abb* r, int info){ 
 if (r==NULL) 
 return cria_filho(r,info); 
 else if (info < r->info) { 
 if (r->esq==NULL) 
 r->esq = cria_filho(r,info); 
 else 
 r->esq = abb_insere(r->esq,info); 
 } 
 else if (info>r->info) { 
 if (r->dir==NULL) 
 r->dir = cria_filho(r,info); 
 else 
 r->dir = abb_insere(r->dir,info); 
 } 
 return r; 
} 
 
P1 INF1010-Estruturas de Dados Avançadas 2011.1 
13abr2011 Página 7/7 
5) (1.5 pontos.) A sequencia de Fibonacci é uma sequencia de números definida do seguinte modo: 
�� � 0, �� � 1,… , �� � ���� 
 ����	����	� � 2 
Considere os dois algoritmos mostrados abaixo. 
Algoritmo 1: 
long int fibonacci_a1(long int n){ 
 if (n==0) 
 return 0; 
 else if (n==1) 
 return 1; 
 else { 
 long int j,anterior=0,atual=1; 
 for (j=1;j<n;j++) { 
 long int proximo=atual+anterior; 
 anterior=atual; 
 atual=proximo; 
 } 
 return atual; 
 } 
} 
 
Algoritmo 2: 
long int fibonacci_a2(long int n){ 
 if (n==0) return 0; 
 else if (n==1)return 1; 
 else return fibonacci_a2(n-2)+fibonacci_a2(n-1); 
} 
 
a) Qual a complexidade do Algoritmo 1? 
b) Quantas chamadas recursivas ocorrem no Algoritmo 2 para n=5? 
c) Na sua avaliação qual dos dois algoritmos é mais eficiente? Porque? 
 
a) A complexidade do Alg. 1 é O(n). É um laço de for apenas 
 
 
b) 14 chamadas! 
 
c) O alg. 1 é bem mais eficiente. Ele calcula apenas uma vez os numero de Fibonacci menores 
que o enésimo. Veja no exemplo do item anterior quantas vezes o alg2 calcula F(2), 3!