P2-2014Um-Alunos

Prévia do material em texto

P2 Programação II 2014.1 Departamento de Informática/PUC-Rio 
Aluno: _______________________________________________________
Valor
Nota
Q1A
2.5
Q1B
3.0
Q1C
3.0
Q2
1.5
Total
10.0
Matrícula: _______________		Turma: _______
A prova é sem consulta e sem perguntas. A interpretação do enunciado faz parte da prova.
A prova deve ser completamente resolvida nas folhas que constam deste caderno, utilizando-se frente e/ou verso;
A prova pode ser feita utilizando-se lápis ou caneta (azul ou preta);
O aluno só pode manter junto a si lápis, borracha, e caneta. O empréstimo deste tipo de material para outro aluno é estritamente proibido.
Todo papel diferente do distribuído pelo fiscal (independentemente do conteúdo) e/ou qualquer dispositivo eletrônico (celular, tablet, etc.) (ligado ou não) encontrados junto ao aluno implicará no recolhimento imediato da prova e a atribuição de nota ZERO à mesma.
Algumas Funções de Bibliotecas (NESTA PROVA VOCE PODE USÁ-LAS EM QUALQUER QUESTÃO)
stdio.h:
int scanf (char* formato, ...);
int printf (char* formato, ...);
FILE* fopen (char* nome, char* modo);
int fclose (FILE* fp);
int fscanf (FILE* fp, char* formato, ...);
int fprintf (FILE* fp, char* formato, ...);
char*fgets(char* str, int size, FILE* fp);
int sscanf(char* str, char* formato, ...);
stdlib.h:
void* malloc (int nbytes);
void free (void* p);
math.h:
double sqrt (double x);
double pow (double x, double exp);
double cos (double radianos);
double sin (double radianos);
string.h:
int strlen (char* s);
int strcmp (char* s, char *t);
char* strcpy (char* destino, char* fonte);
char* strncpy (char* destino, char* fonte, int n);
char* strcat (char* destino, char* fonte);
char* strdup (char* s);
void qsort (void *v, int n, int tam, int (*cmp)(const void*, const void*));
void * bsearch(void * info, void * v, int n, int tam, int (*cmp)(const void *, const void *));
Para todas as questões desta prova considere os tipos estruturados abaixo:
- Bolsista, que representa um aluno que recebe uma bolsa numa certa universidade:
struct data
{	int mes; /* mês de ingresso na universidade */
 	int ano; /* ano de ingresso na universidade */
};
typedef struct data Data;
struct bolsista
{	int matricula; /* numero de matricula do aluno */
	char nome[51]; /* nome do aluno */
	char tipoDaBolsa[21]; /* “soc”, “ic”, “mest”, “dout” */
	Data dataInicio; /* data de ingresso na universidade */
};
typedef struct bolsista Bolsista;
- Pedido, que representa um pedido de bolsa por um aluno:
struct pedido
{	int matricula; /* matricula do aluno que solicita a bolsa */
	char tipoDoPedido[21]; /* “soc”, “ic”, “mest”, “dout” */
 	struct pedido *prox; /* ponteiro para o proximo pedido */
};
typedef struct pedido Pedido;
Questão 1.a) (2.5 pontos ) Considere um vetor de ponteiros para Bolsista ordenado em ordem crescente (alfabética) por tipoDaBolsa. Para um mesmo tipo de bolsa, o vetor encontra-se ordenado crescentemente por matricula (ver exemplo na Figura 1). Escreva uma função EhBolsista que usando a técnica de busca binária verifica se já existe um determinado bolsista neste vetor, isto é, para um tipo de bolsa e uma matrícula. Você deve obrigatoriamente escrever uma função auxiliar de comparação.
Figura 1
Questão 1.b) (3.0 pontos) Considere a existência de uma lista simplesmente encadeada com pedidos de bolsa. O tipo que representa o nó encadeado é o tipo estruturado Pedido (ver exemplo na Figura 2).
Figura 2
Usando obrigatoriamente a função desenvolvida na questão anterior, escreva a função eliminaPedidosRepetidos que elimina da lista os pedidos já existentes no vetor de ponteiros para Bolsista e retorna a lista alterada. Note que é para alterar a lista recebida e não fazer uma nova lista. Exemplo: dado o vetor da Figura 1 e a lista da Figura 2, a função deve retornar a lista da Figura 3.
Figura 3
Questão 1.c) (3.0 pontos) Considerando apenas o tipo estruturado Bolsista, escreva a função ordenaDataInicio que ordena o vetor de ponteiros para Bolsista, pelo método de quick sort (ordenação rápida), de modo que os bolsistas mais antigos precedam os mais recentes. No caso de mesmo ano e mês de início da bolsa, os bolsistas devem ficar ordenados crescentemente por nome. Você deve obrigatoriamente escrever uma função auxiliar de comparação. Se você preferir, você pode usar a função qsort da biblioteca. Exemplo:
	Original
	Após Ordenação
	Vetor de Bolsistas:
410 Duda dout 6 2010
411 Paulo dout 2 2014
201 Gina ic 6 2011
202 Andre ic 3 2011
203 Carlos ic 6 2010
301 Bia mest 5 2010
101 Ana soc 5 2010
102 Bela soc 6 2010
	Vetor de Bolsistas:
101 Ana soc 5 2010
301 Bia mest 5 2010
102 Bela soc 6 2010
203 Carlos ic 6 2010
410 Duda dout 6 2010
202 Andre ic 3 2011
201 Gina ic 6 2011
411 Paulo dout 2 2014
Figura 4
Questão 2 (1.5 ponto): Considere o tipo estruturado Pedido, que representa um nó de uma lista simplesmente encadeada de pedidos. Assumindo que a lista não está ordenada, escreva a função RECURSIVA maiorMatricula que recebe a lista (ou seja , o ponteiro para o primeiro elemento da lista) e retorna a maior matrícula (ou seja, a matrícula de maior valor). Caso não exista nenhum pedido a função retorna -1. Exemplo: para uma lista de pedidos como a da Figura 2, a função retorna o valor 415.