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
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);	(1oids�� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic �� PAGE \*Arabic 0)
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
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
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;
}
�