Gabarito-Tvc2-LabII-2011-3

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 – 04/11/2011
ALUNO (A) __________________________________________________________________________ Turma:______ 
ATENÇÃO: A prova deve ser feita na linguagem C.
1) Considerando as definições do TAD Pilha e dado o programa abaixo, indique o que será impresso. Considere as 
funções Pilha* cria_pilha(void) e int vazia_pilha(Pilha *p) implementadas. (30)
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 = 0; i < 16; i++) {
 if(i % 3 == 0)
 func1(p1, i);
 else if(i % 4 == 0)
 func1(p2, i);
 }
 printf("p1: "); func3(p1);
 printf("p2: "); func3(p2);
 while(!vazia_pilha(p1)) {
 int v = func2(p1); 
 if(v % 2 != 0)
 func1(p2, v);
 }
 printf("p1: "); func3(p1);
 printf("p2: "); func3(p2);
 return 0;
}
Primeira impressão: p1: 15 12 9 6 3 0 (10)
 p2: 8 4 (10)
Segunda impressão: p1: vazia (5)
 p2: 3 9 15 8 4 (5)
2) Considerando as definições abaixo do TAD Lista Contígua (capacidade m e quantidade de nós n), desenvolver as 
funções maiores (retorna quantos elementos são maiores que v) e elimina_k (exclui e retorna o valor contido na 
posição k da lista). 
struct listaCont
{
 int m, n;
 float *x;
};
typedef struct listaCont ListaCont;
a) int maiores(ListaCont *l, float v); (15)
b) float elimina_k(ListaCont *l, int k); (15)
int maiores(ListaCont *l, float v)
{
 int i, cont = 0;
 for(i = 0; i < l->n; i++) (5) para o for
 {
 if(l->x[i] > v) (5) para o conteúdo do for
 cont++;
 }
 return cont; (5) para o retorno e outros (inicialização, protótipo etc)
UNIVERSIDADE FEDERAL DE JUIZ DE FORA
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
}
float elimina_k(ListaCont *l, int k)
{
 int i;
 if( k < 0 || k >= l->n) (2) para o teste
 {
 printf("Indice invalido!\n");
 exit(0);
 }
 float v = l->x[k]; (2) para armazenar o valor
 for(i = k; i < l->n-1; i++) (3) para o for
 l->x[i] = l->x[i+1]; (3) para o conteúdo do for
 l->n--; (3) para o decremento
 return v; (2) para o retorno
}
3) Abaixo encontram-se as definições que implementam o TAD Fila. Desenvolver as funções cria_fila (cria uma fila 
vazia), primeiro (retorna o valor do primeiro elemento da fila, sem retirá-lo!) e intersecao (cria uma fila como 
sendo a interseção de 2 filas – assuma que, em cada fila, não existam valores repetidos). Considere a função void 
enfileira(Fila *f, int v) implementada.
struct no
{
 int info;
 struct no *prox;
};
typedef struct no No;
struct fila
{
 No *inicio;
 No *fim;
};
typedef struct fila Fila;
a) Fila* cria_fila(void); (10)
b) int primeiro(Fila *f); (10)
c) Fila* intersecao(Fila *f1, Fila *f2); (20)
Fila* cria_fila(void)
{
 Fila *f = (Fila*) malloc(sizeof(Fila)); (5)
 f->inicio = NULL; (3) para as inicializações
 f->fim = NULL;
 return f; (2) para o retorno
}
int primeiro(Fila *f)
{
 if(f->inicio == NULL) (2) para o teste
 {
 printf("Fila vazia!\n");
 exit(0);
 }
 return f->inicio->info; (8) para o retorno
}
UNIVERSIDADE FEDERAL DE JUIZ DE FORA
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
Fila* intersecao(Fila *f1, Fila *f2)
{
 Fila *f3 = cria_fila(); (3) para criar f3
 No *p = f1->inicio;
 while(p != NULL) (5) para percorrer f1
 {
 No *q = f2->inicio;
 while(q != NULL) 
 {
 if(p->info == q->info) (7) para a busca do valor comum
 {
 enfileira(f3, p->info); (3) para o correto enfileiramento
 break;
 }
 q = q->prox;
 }
 p = p->prox;
 }
 return f3; (2) para o retorno
}