Gabarito-Tvc3-LabII-2011-3_v2

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 Laboratório de Programação II – 02/12/2011
ALUNO (A) __________________________________________________________________________ Turma:______ 
ATENÇÃO: A prova deve ser feita na linguagem C.
1) Considerando as definições do TAD Árvore Binária e dado o programa abaixo, informe o que será impresso. Considere 
as funções Arv* cria(char c, Arv *sae, Arv *sad) e Arv* libera(Arv *a) implementadas. (30)
struct arv
{
 char info;
 struct arv *esq;
 struct arv *dir;
};
typedef struct arv Arv;
int main()
{
 Arv *a1, *a2, *a3, *a4, *a5, *a;
 a1 = cria('e', NULL, NULL);
 a2 = cria('w', NULL, a1);
 a3 = cria('u', NULL, NULL);
 a4 = cria('a', NULL, NULL);
 a5 = cria('c', a3, a4);
 a = cria('k', a2, a5);
 printf("Teste 1: "); func1(a);
 a->esq->esq = cria('q',
 cria('v', NULL, NULL),
 cria('t', NULL, NULL));
 a->dir->esq = libera(a->dir->esq);
 printf("\nTeste 2: "); func1(a);
 libera(a);
 return 0;
}
void func1(Arv *a)
{
 if(a != NULL)
 {
 func1(a->dir);
 printf("%c ", a->info);
 func1(a->esq);
 }
}
Resposta: 
Teste 1: a, c, u, k, e, w 
Teste 2: a, c, k, e, w, t, q, v 
Sugestão: 10 para cada teste, 5 para cada montagem de árvore
2) Considerando as definições abaixo do TAD Árvore Binária, desenvolver uma função para comparar se duas árvores 
são iguais (duas árvores binárias são iguais quando ambas são nulas ou quando os valores das raízes são iguais e as sub-
árvores esquerda e direita também são iguais) e uma função para verificar se uma árvore é estritamente binária (todos os 
nós têm 0 ou 2 filhos).
struct arv
{
 int info;
 struct arv *esq;
 struct arv *dir;
};
typedef struct arv Arv;
a) int compara(Arv *a1, Arv *a2); (15)
b) int estritamenteBinaria(Arv *a); (15)
Resposta:
2a)
int compara(Arv *a1, Arv *a2)
{
 if (a1 == NULL && a2 == NULL) (5)
 return 1;
 else 
 return a1->info == a2->info && compara(a1->esq, a2->esq) && compara(a1->dir, a2->dir); (10)
} 5 para percurso, 5 para teste e retorno
UNIVERSIDADE FEDERAL DE JUIZ DE FORA
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
2b)
int estritamenteBinaria(Arv *a)
{
 if(a != NULL) (2)
 {
 if( (a->esq == NULL && a->dir != NULL) || (a->esq != NULL && a->dir == NULL) ) (5)
 return 0;
 else
 {
 int v_esq = estritamenteBinaria(a->esq); (5)
 int v_dir = estritamenteBinaria(a->dir);
 if(v_esq && v_dir) (3)
 return 1;
 else
 return 0;
 }
 }
 else
 return 1;
}
3) Abaixo encontra-se a definição do tipo que implementa o TAD Árvore Binária de Busca que armazena os dados dos 
alunos de uma turma, sendo que o campo nota usado é para ordenação da árvore. Desenvolver um procedimento para 
imprimir os nomes dos alunos que fazem parte do caminho para achar a primeira ocorrência de uma dada nota x. Além do 
procedimento, desenvolver uma função que retorna a quantidade de alunos com notas no intervalor fechado [55, 85] 
(atenção à propriedade fundamental das ABBs) e uma função que retorna a quantidade de nós presentes em um dado nível 
k da árvore.
struct arv
{
 char nome[128];
 float nota;
 struct arv *esq;
 struct arv *dir;
};
typedef struct arv Arv;
a) void imprimeCaminhoNota(Arv *a, float x); (10)
b) int contaEntre55e85(Arv *a); (15)
c) int alunosNivelk(Arv *a, int k); (15)
Resposta:
3a)
void imprimeCaminhoNota(Arvb *a, float x)
{
 if(a != NULL) (2)
 {
 printf("%s", a->nome); (3)
 if(x < a->nota)
 imprimeCaminhoNota(a->esq);
 else if(x > a->nota)
 imprimeCaminhoNota(a->dir); (5)
 }
}
OU
UNIVERSIDADE FEDERAL DE JUIZ DE FORA
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
void imprimeCaminhoNota(Arvb *a, float x)
{
 while(x != a->nota && a != NULL) (3)
 {
 printf("%s", a->nome);
 if(a->nota < x) (5)
 a = a->dir;
 else
 a = a->esq;
 }
 
 if(a!=NULL) (2)
 printf(“%s”, a->nome);
}
3b)
int conta(Arv *a)
{
 if(a != NULL) (2)
 {
 if(a->nota < 55)
 return conta(a->dir);
 else if(a->nota > 85)
 return conta(a->esq); (5)
 else
 return 1 + conta(a->esq) + conta(a->dir); (8)
 }
 else
 return 0;
}
3c)
int alunosNivelk(Arvb *a, int k)
{
 if(a != NULL) (2)
 {
 if(k == 0) (5)
 return 1;
 else
 return alunosNivelk(a->esq, k-1) + alunosNivelk(a->dir, k-1); (8)
 }
 else
 return 0;
}
OU
UNIVERSIDADE FEDERAL DE JUIZ DE FORA
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
int alunosNivelK(Arv *a, int k)
{
 return alunosNivelK2(a, 0, k); (2)
}
int alunosNivelK2(Arv *a, int cor_n, int k)
{
 if(!vazia(a)) (2)
 {
 if(cor_n == k) (3)
 return 1;
 else
return alunosNivelK2(a->esq, cor_n+1, k) + alunosNivelK2(a->dir, cor_n+1, k); (8)
 }
 else
 return 0;
}