Tvc3-EDLII-1-11-Tarde.Gabarito

Prévia do material em texto

UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
3º TVC de Estrutura de Dados e Laboratório de Programação II – 04/07/2011 
ALUNO (A) _______________________________________________________________ Turma Lab:_____ ED:_____ 
ATENÇÃO: 
 Estrutura de Dados: questões de 1 a 4. Laboratório de Programação II: questões de 3 a 5. 
 Sempre que necessário, apresentar as definições das estruturas de dados. 
 Para as questões 2, 3, 4 e 5, considerar os tipos definidos a seguir: 
struct arv { 
 int info; 
 struct arv *esq; struct arv *dir; }; 
typedef struct arv Arv; 
tipo Arv = ref NO; 
tipo NO = reg(R: ESQ, int: INFO, R: DIR); 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
 
1) Definir a altura de um nó qualquer x em uma árvore e a altura de uma árvore. (15) 
- A altura de um nó x em uma árvore é é o número de passos do mais longo caminho que leva de x até uma 
folha. 
- Altura (ou profundidade) da árvore é o nível do nó folha que tem o mais longo caminho até a raiz. 
 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
 
2) Considerando uma árvore binária de números inteiros, fazer um procedimento para imprimir os valores dos 
nós múltipos do inteiro n fazendo um percurso em pós-ordem. Protótipo do procedimento: 
 void imp_n(Arv *a, int n) ou proc imp_n(Arv: A, int: N) (20) 
 
Em C: Em pseudolinguagem: 
void imp_n(Arv *a, int n) 
{ 
 if(!vazia(a)){ 
 imp_n(a->esq, n); 
 imp_n(a->dir, n); 
 if(a->info % n == 0) 
 printf(“%d\n”,a->info); 
 } 
} 
proc imp_n(Arv: A, int: N) 
 se não vazia(A) 
 imp_n(A.ESQ, N); 
 imp_n(A.DIR, N); 
 se A->INFO mod n = 0 
 imprima(A->INFO); 
 fim-se; 
 fim-se; 
fim-proc; 
 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
 
3) Desenvolver o procedimento imp para imprimir os valores de todos os nós da árvore binária de busca abb 
que estão dentro do intervalo fechado [x, y]. Considerar x menor que y e usar a propriedade fundamental de 
árvore binária de busca. (35) 
Protótipo em C: Protótipo em pseudolinguagem: 
void imp(Arv *abb, int x, int y) proc imp(Arv: ABB, int:X, int:Y) 
 
Em C: Em pseudolinguagem: 
void imp(Arv *abb, int x, int y) 
{ 
 if(abb != NULL) { 
 if(x > abb->info) 
 imp(abb->dir, x, y); 
 else if(y < abb->info) 
 imp(abb->esq, x, y); 
 else{ 
 imp(abb->esq, x, y); 
 imp(abb->dir, x, y); 
 printf(“%d\n”,abb->info); 
 } 
 } 
} 
proc imp(Arv: ABB, int:X, int:Y) 
 se ABB ≠ nil entao 
 se X > ABB->INFO entao 
 imp(ABB.DIR, X, Y); 
 senao se Y < ABB->INFO entao 
 imp(ABB.ESQ, X, Y); 
 senao 
 imp(ABB->ESQ, X, Y); 
 imp(ABB->DIR, X, Y); 
 imprima(ABB->INFO); 
 fim-se; 
 fim-se; 
 fim-se; 
fim-proc; 
 
 
 
 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
 
4) Dado o programa abaixo (em C e em pseudolinguagem): 
Arv* montaArv(int *v, int i, int f) 
//monta e retorna uma ABB com seus valores 
{ 
 int m; 
 Arv *a; 
 m = (i + f) / 2; 
 if(i<=f) 
 { 
 a = (Arv*)malloc(sizeof(Arv)); 
 a->info = v[m]; 
 a->esq = montaArv(v, i, m-1); 
 a->dir = montaArv(v, m+1, f); 
 } 
 else 
 a = NULL; 
 return a; 
} 
tipo TVET = vet[0..9]int; 
função montaArv(TVET:V, int:I, int: F):Arv 
//monta e retorna uma ABB com seus valores 
 int: M; 
 Arv: A; 
 M  (I + F) div 2; 
 se I<=F então 
 aloque(A); 
 A.INFO  V[M]; 
 A.ESQ  montaArv(V, I, M-1); 
 A.DIR  montaArv(V, M+1, F); 
 senão 
 A  nil; 
 fim-se; 
 montaArv  A; 
fim-função; 
int main() { 
 Arv *abb; 
 int v1[] = {7,9,13,21,22,25,26,32,35,50}; 
 abb = montaArv(v1,0,9); 
 return 0; } 
inicio 
 Arv: ABB; 
 TVET: V1  {7,9,13,21,22,25,26,32,35,50}; 
 ABB  montaArv(V1, 0, 9); 
fim; 
a) representar graficamente a árvore binária de busca abb (ou ABB) gerada após a execução do programa acima; 
b) representar graficamente a árvore binária de busca abb (ou ABB) do item (a) após a remoção do nó com valor 
22. (30) 
 
 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
 
5) Fazer o procedimento cont_i1f em C que calcula, para uma árvore binária: 
 o número de nós com valor impar; 
 o número de nós com um único filho. 
O procedimento cont_i1f deve percorrer a árvore binária APENAS UMA VEZ fazendo um percurso em pré 
ordem. Protótipo do procedimento: 
 
 void cont_i1f(Arv *ab, int *nimpar, int *n1filho) 
 
Cuidado com a inicialização e atualização dos parâmetros passados por referência em C. (35) 
 
 
 
 
 
 
 
 
 
 
 
 
a) b) 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
Em C: 
//é necessário inicializar os valores nimpar e n1filho com zero. Para tanto 
//será criado um procedimento que realiza esta tarefa e chama, então, o 
//procedimento cont_i1f. 
void cont_inic_i1f(Arv *ab, int *nimpar, int *n1filho) 
{ 
 *nimpar = 0; 
 *n1filho = 0; 
 cont_i1f(ab, nimpar, n1filho); 
} 
 
void cont_i1f(Arv *ab, int *nimpar, int *n1filho) 
//percorre a árvore em pré ordem 
{ 
 if(ab != NULL) { 
 if(ab->info % 2 == 1) //conta nó com valor impar 
 (*nimpar)++; 
 if(tem_filho_unico(ab)) //conta nó com um único filho 
 (*n1filho)++; 
 
 cont_i1f (ab->dir, nimpar, n1filho); 
 cont_i1f (ab->esq, nimpar, n1filho); 
 } 
} 
 
//esta funcao retorna 1 se o nó tem um único filho ou zero caso contrário 
int tem_filho_unico(Arv *a){ 
 if(((ab->dir == NULL)&&(ab->esq != NULL)) || 
 ((ab->dir != NULL)&&(ab->esq == NULL)) ) 
 return 1; 
 return 0; 
} 
 
//obs: na funcao acima poder-se-ia usar o operador lógico xor (tem em C?): 
// if((ab->dir == NULL) xor (ab->esq == NULL))