P4_2015_1_INF1007 - Prog 2

Prévia do material em texto

Disciplina: INF1005 - Programação I
Avaliação:	 P1	Data: 12/09/2014
Algumas funções de bibliotecas que podem ser usadas nesta prova, em qualquer questão, encontram-se relacionadas na última folha.
	
Questão 1) (2.0 pontos) Para preservar o sigilo, uma empresa transmite o primeiro nome de um cliente intercalando os caracteres deste nome com os 6 (seis) caracteres que representam a data de nascimento deste cliente. A cadeia de caracteres gerada é sempre completada com os caracteres restantes do nome ou da data. Por exemplo, nome = “ANA”e data = “261281” geram a cadeia “A2N6A1281”, enquanto que nome = “CRISTINA” e data = “261281” geram “C2R6I1S2T8I1NA”. Escreva a função mistura que:
 - recebe o nome e a data e ;
 - retorna uma nova cadeia de caracteres a ser transmitida. Caso não seja possível alocar a nova cadeia a 
 função retorna NULL. Entre todas as funções da biblioteca string, apenas a strlen pode ser usada.
Questão 2.0) (totalizando 3.0 pontos) Considere a representação de polinômios 
anxn + an-1xn+1 +.. + a2x2 + a1xn+ anx0
através de uma lista encadeada , onde cada nó tem um ponteiro para um termo do polinômio e um ponteiro para o próximo nó da lista. Um termo tem coeficiente inteiro e um grau (potência) inteiro.
A lista encadeada encontra-se ordenada decrescentemente pelo grau do termo. Considere os tipos estruturados abaixo:
struct termo
{	int coef;
	int grau;
};
typedef struct termo Termo;
struct no
{	Termo *te; /* ponteiro para um termo */
	struct no *prox; /* ponteiro para o próximo nó da lista */
};
typedef struct no No;
2.A) (2.0 ponto) Escreva a função insereTermo que:
- recebe (o endereço do primeiro nó de ) uma lista de termos, um coeficente e um grau (potência) de um novo termo. Caso na lista não exista termo com o grau recebido, deve ser inserido um novo nó na lista, com novo termo com o coeficiente e o grau recebidos. Caso já exista termo de mesmo grau na lista, deve ser feita apenas a atualização do coeficiente. A função deve levar em conta e manter a ordenação da lista;
- retorna (o endereço do primeiro nó da) lista atualizada ou NULL se ocorrerem problemas.
2.B) (1.0 ponto) Escreva a função RECURSIVA exibePolinômio, que:
	- recebe (o endereço do primeiro nó de) uma lista de termos e exibe coeficiente e grau de cada termo.
Questão 3) (2.0 pontos) Considere o tipo estruturado Livro (aqui não é TAD) abaixo, que representa um livro de uma livraria:
typedef struct livro Livro;
struct livro
{	char	autor[51];
	char 	titulo[31];
	int	estoque; /* quantidade de livros */
};
Considere também a existência do TAD PilhaDeLivros e do TAD FilaDeLivros. 
TAD PilhaDeLivros: guarda endereços de livros e a interface é apresentada a seguir:
typedef struct pilhaDeLivros PilhaDeLivros;
	função:
	descrição:
	PilhaDeLivros *piCria(void);
	cria e retorna (um ponteiro para) uma pilha de livros
	void piPush(PilhaDeLivros *pi, Livro *liv);
	recebe (um ponteiro para) uma pilha de livros e o endereço de um livro criado, inserindo o endereço desse livro na pilha
	Livro * piPop (PilhaDeLivros *pi);
	recebe (um ponteiro para) uma pilha de livros e retira o endereço do livro que está no topo da pilha, retornando-o
	int piVazia (PilhaDeLivros *pi);
	recebe (um ponteiro para) uma pilha de livros e retorna 1, se a pilha está vazia, ou 0, em caso contrário
	void piLibera (PilhaDeLivros *pi);
	recebe (um ponteiro para) uma pilha de livros e libera o espaço em memoria ocupado pela pilha
TAD FilaDeLivros: guarda endereços de livros e a interface é apresentada a seguir:
typedef struct filaDeLivros FilaDeLivros;
	função:
	descrição:
	FilaDeLivros *fiCria(void);
	cria e retorna (um ponteiro para) uma fila de livros
	void fiInsere(FilaDeLivros *fi, Livro *liv);
	recebe (um ponteiro para) uma fila de livros e o endereço de um livro criado, inserindo o endereço desse livro na fila
	Livro * fiRetira (FilaDeLivros * fi);
	recebe (um ponteiro para) uma fila de livros e retira o endereço do livro que está na frente da fila, retornando-o
	int fiVazia (FilaDeLivros * fi);
	recebe (um ponteiro para) uma fila de livros e retorna 1, se a fila está vazia, ou 0, em caso contrário
	void fiLibera (FilaDeLivros * fi);
	recebe (um ponteiro para) uma fila de livros e libera o espaço em memoria ocupado pela fila
Escreva a função invertePilha que:
	- recebe (um ponteiro para) uma pilha de livros e deixa na pilha os livros na ordem inversa a que eles estão originalmente, descartando (retirando) os livros com estoque igual a zero.
O tipo de retorno da função é void. A sua função deverá obrigatoriamente usar uma ou mais estrutura(s) auxiliar(es) (pilha e/ou fila), considerando a existência do TAD PilhaDeLivros e do TAD FilaDeLivros. 
Questão 4) (3.0 pontos) Considere o tipo estruturado NoInscrito abaixo, que representa um nó de uma lista simplesmente encadeada, com os dados de um inscrito aprovado em um concurso. Um inscrito tem número de inscricao (os números de inscrição variam de 1000 até 9999) e nota. 
typedef struct noIncrito NoInscrito;
struct noIncrito
{	int inscrição; /* numero de inscricao */
	float nota; 
	NoInscrito *prox; /* ponteiro para o próximo inscrito da lista */
};
Com o objetivo de tornar mais rápido o acesso aos dados de um inscrito, é mantido um vetor do tipo estruturado Entrada descrito abaixo, onde ficam “penduradas” as listas encadeadas:
typedef struct entrada Entrada;
struct entrada
{	int milharDaInsc; /*1000,2000,3000,4000,5000,6000,7000,8000,9000 */
	NoInscrito *lstInscritos; /* ponteiro para o primeiro nó de uma lista 
			 simplesmente encadeada de inscritos com número de 
inscricao correspondente a esse milhar. A lista se encontra ordenada crescentemente por inscricao */
};
1200
7.5
1000
2000
3000
4000
5000
6000
7000
8000
9000
7555
9.9
9198
8.0
8030
7.5
9100
9.5
6388
9.5
5300
8.5
4012
7.5
3000
8.5
7777
8.6
2444
9.5
3356
9.0
4100
7.5
5434
9.5
5600
9.5
7890
8.5
3555
9.5
1333
8.5
1888
8.5
2789
85
3789
7.5
4231
7.5
5800
8.5
6700
9.0
7905
9.5
8888
8.5
9899
9.0
Escreva a função obtemNotaDeUmInscrito que:
- recebe um vetor de Entrada, ordenado crescentemente por milhar, o número de entradas e um número de inscrição, e 
- retorna a nota do inscrito, se encontrado, ou -1, caso contrário. 
Obs: Para localizar primeiro a lista encadeada adequada, deverá ser considerada a ordenação do vetor de Entrada, sendo implementada e utilizada obrigatoriamente uma função de busca binária. A função de busca binária:
- recebe um vetor de entradas, ordenado crescentemente por milhar, o número de entradas e um milhar a ser procurado,
	- retorna a posição do elemento se encontrado ou -1 caso contrário.
Dica: para saber qual milhar procurar no vetor, basta fazer: milhar procurado = numero de inscricao/1000 *1000
Ao buscar o número de inscrição na lista encadeada deve também levar em consideração a ordenação da lista.
	ALGUMAS FUNÇÕES DE BIBLIOTECAS
	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, ...);
int sprintf(char* str, 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 *));
NESTA PROVA VOCE PODE USÁ-LAS EM QUALQUER QUESTÃO