Tvc2-LabII-2012-1.Turma.C

Prévia do material em texto

UNIVERSIDADE FEDERAL DE JUIZ DE FORA - INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
2º TVC de Laboratório de Programação II – 22/10/2012
ALUNO (A) __________________________________________________________________________ Turma:______ 
(1) Considerando as definições do TAD Pilha e dado o programa abaixo, indique exatamente o que será impresso (a ordem importa!). Considere as funções Pilha* cria_pilha(void) e int vazia_pilha(Pilha *p) implementadas. (30 pontos)	
	struct no
{
 int info;
 struct no *prox;
};
typedef struct no No;
	struct pilha
{
 No *topo;
};
typedef struct pilha Pilha;
	void func1(Pilha *p, int v) {
  No *q = (No*) malloc(sizeof(No));
 q->info = v;
 q->prox = p->topo;
 p->topo = q;
}
int func2(Pilha *p) {
   No *q = p->topo;
 int v = q->info;
 p->topo = q->prox;
 free(q);
 return v;
} 
void func3(Pilha *p) {
 No *q = p->topo;
 while(q != NULL){
 printf("%d ", q->info);
 q = q->prox;
 }
 printf("\n");
}
	int main()
{
 int i;
 Pilha *p1 = cria_pilha();
 Pilha *p2 = cria_pilha();
 for(i = 12; i < 25; i++) {
    if(i % 2 == 0)
 func1(p1, i);
 else if(i % 3 == 0)
 func1(p2, i);
 }
 printf("P1: "); func3(p1);
 printf("P2: "); func3(p2);
 while(!vazia_pilha(p1)) {
 int v = func2(p1); 
    if(v % 4 == 0) func1(p2, v);
 }
 printf("P1: "); func3(p1);
 printf("P2: "); func3(p2);
 return 0;
}
(2) Considerando as definições abaixo do TAD Fila, desenvolver (i) a função básica de enfileiramento (dada uma fila e um valor x, inserir x na fila), (ii) uma função para criar uma nova fila apenas com os elementos pares e (iii) uma função para intercalar duas filas (os elementos de cada fila passada como parâmetro são inseridos na nova fila alternadamente). Nas letras b) e c), a nova fila deve ser independente das filas originais. Considere que a função Fila* criaFila() já está implementada. (30 pontos)
	struct no
{
 int info;
 struct no *prox;
};
typedef struct no No;
	struct fila
{
 No *inicio;
 No *fim;
};
typedef struct fila Fila;
	Protótipos:
a) void enfileira(Fila *f, int x); 	(10)
b) Fila* criaFilaPares(Fila *f); 	 (10)
c) Fila* intercala(Fila *f1, Fila f2);
�
�
(3) Abaixo encontra-se a definição do tipo que implementa o TAD Árvore Binária de Busca. Desenvolver um procedimento para imprimir o maior valor da árvore. Além disso, desenvolver uma função que retorna a quantidade de alunos com notas no intervalo fechado [50, 80] (atenção à propriedade fundamental das ABBs) e uma função que retorna a soma dos nós que formam o caminho que vai da raiz até um nó que contenha o valor contido na variável x (Dica: não use recursividade). (40 pontos)
	struct abb
{
 int valor;
 struct abb *esq;
 struct abb *dir;
};
typedef struct abb Abb;
	Protótipos:
a) void imprimeMaior(Abb *a);	(1oids1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 1�� PAGE \*Arabic 10)
b) int contaNotas(Abb *a);	(15)
c) int somaNosCaminho(Abb *a, int x);
�
�