AV 1 - FMU- 2017 - Estrutura de Dados Avançadas

Prévia do material em texto

Estrutura de Dados Avançadas
Questão 1 (3,0 pontos) Vetores são estruturas de dados mais simples que são empregadas em algoritmos variados que solucionam problemas diversos do cotidiano dos cidadãos. Uma das extensões dos vetores são as listas ligadas. Considerando os códigos a seguir, responda: 
int rotina1 (int a, int n, int v[]) { R: q void rotina8(int i, int a, int n, int v[]) {inti; i=n-1;if(i==n) v[n]=a; R: N while (v[i] != a && i >= 0) R: inverter && else {
i -= 1;v[n] = v[n-1];return i; funcao8(i, a, n -1, v); R: rotina8 }}}
int rotina2 (int a, int v[]) { R: q inti=0; v[n]=a; R: n não declarado void rotina9 (int a, elemento *L){while (v[i] != a)elemento *p; R:I p=L; 
i++;return i; while (p != NULL && p -> conteudo != a)} p=p->prox;return p; 
int rotina3 (int a, int n, int v[]) { R: M }if (n == 0) return -1;if (a == v[n-1]) return n-1;void rotina10 (int a, elemento *L){
return funcao3 (a, n-1, v); } R: rotina3 elemento *N; R: K 
void rotina4 (char s[]) { R: P N = malloc (sizeof(elemento));int c,i,j;N -> conteudo = a;for (i=0, j=strlen(s)-1;i<j;i++,j--) {N -> prox = L -> prox;
c = s[i]; s[i] = s[j]; s[j] = c; } L -> prox = N; }} 
void rotina5 (int x, int y) { R: L void rotina11 (elemento *L){int temp; R: usar apontador * elemento *R; R: J temp=x; x=y; y=temp; 
} 	R = L -> proximo;L -> proximo = R -> proximo;
void rotina6 (int i, int n, int v[]) { free(R); int j; R: R }for (j = i+1; j < n; ++j)
v[j-1] = v[j]; void rotina12(elemento r) {} if (r != NULL) { R:A erd erd(r -> esq );
void rotina7 (int i, int a, int n, int v[]){ printf("%d\n", r -> conteudo);int j;erd(r -> dir); for (j = n; j > i; --j) R:S en-1 }
v[j] = v[j-1];}v[i] = a; } 
a) Identifique quais dos algoritmos abaixo são implementados em cada uma das rotinas acima (1,8 pontos). 
A. Imprime árvore binária H. remoção em fila 	O. Remove recursiva 
B. Insere árvore binária I. Pesquisa lista ligada 	P. inverte cadeia 
C. Remove em árvore B J. Remove lista ligada 	Q. pesquisa em vetor 
D. hashing 	K. Insere lista ligada R. Remove em vetor 
E. Insere em pilha 	L. Troca apontadores S. Insere em vetor 
F. Remove em pilha 	M. Pesquisa recursiva T. Imprime em vetor 
G. inserção em fila 	N. Insere recursiva 
1 
b) 	Encontre e corrija os 8 erros destes algoritmos (1,2 pontos). Em vermelho ao lado de cada rotina acima 
Questão 2 (2,0 pontos) Na espera por atendimento em agência bancária, alunos da FMUconversam sobre estruturas de dados avançadas. Lembram que implementações de fila consistem em estruturas que permitem inserções e remoções e são regidas pela regra: umaremoção sempre retira o elemento que está há mais tempo na estrutura. Ou seja, o primeiroelemento inserido será o primeiro elemento removido (FIFO First-In-First-Out). 
O aluno mais jovem do grupo vai além. Ele considera que as seguintes regras devem tambémser válidas para uma estrutura de dados fila do tipo linear, se implementada através de um vetor v[0..n-1] de tamanho n, tipo de dados inteiro, para o trecho em uso (no vetor) iniciando em ini e terminando em fim-1. 
A. 	O primeiro elemento da fila ocupa a posição ini e o último ocupa a posição fim-1. 
B. 	A fila estará vazia se ini == fim.E cheia se fim == n. 
C. 	Para remover um elemento, basta fazer a = v[fim++];
D. 	Para inserir um elemento a, basta v[ini++] = a; 
Considerando o posicionamento do aluno acima, pede-se:
a) Qual das alternativas abaixo está correta? (1,0 ponto). 
	A) Errada, pois fim; B) Correta. C) Correta. D) Errada, pois v[ini]=a 
	A) Correta. B) Errada, pois fim +1 == n. C) Correta. D) Errada, pois v[ini++]=a 
	A) Correta. B) Correta. C) Errada, falta teste vazia e v[ini++]. D) Errada, faltateste cheia e v[fim++]. 
	A) Correta. B) Correta. C) Errada, falta teste cheia e v[fim++]. D) Errada, faltateste vazia e v[ini++].
Resposta: 3 
b) Codifique as regras C (remover) e D (inserir) em Java ou C, conforme praticado nolaboratório. Lembre-se de informar o usuário com printf em caso de exceção (estrutura cheia / vazia) (1,0 ponto). 
Resposta:
C. Remoção: if (ini != fim) a = v[ini++]; else printf (“fila vazia (impossivelremover).\n”); 
D. Inserção: if (fim != n) v[fim++] = a; else printf (“fila cheia (impossível inserir).\n”); 
Questão 3 (2,0 pontos) Almoçando em um restaurante na Zona Norte de São Paulo, quatroalunos de graduação da FMU conversam sobre estruturas de dados avançadas. Consideram otrabalho dos funcionários do restaurante ao lavar os pratos utilizados pelos clientes, lembramda implementação de pilha (stack) que é uma estrutura de dados que permite inserção eremoção de elementos, e é regida pela regra “uma remoção elimina o elemento que está naestrutura há menos tempo”. O aluno mais velho da turma coloca esta regra de outra forma: “oprimeiro elemento inserido na pilha será o último removido -LIFO ( Last-In-First-Out)”. 
O aluno mais jovem considera que as estas regras devem também ser válidas para estruturasde pilha, se implemen-tada num vetor v[0..n-1] de tamanho n, tipo inteiro, com uso (no vetor) iniciando em 0 e terminando em t-1: 
A. O índice t indica topo da pilha. A próxima inserção de elemento ocorrerá em v[t+1]. 
B. A pilha estará vazia se t == 0.E cheia se t == n. 
C. Para remover um elemento a (desempilhar -pop), basta fazer a = v[--t];
D. Para inserir um elemento a (empilhar -push), basta v[t++] = a;
E. Uma consulta de elemento a, sem desempilhamento, é assim feita: a = v[t--]. 
Considerando o posicionamento destes alunos, pede-se:
a) Qual das alternativas abaixo está correta? (1,0 ponto). 
	A) Correta. B) Correta. C) Errada, pois v[t--]. D) Correta. E) Errada, pois v[t-1]. 
	A) Errada, pois v[t]. B) Correta. C) Correta. D) Errada, pois v[++t]. E) Errada, poisv[t-1]. 
	A) Errada, pois v[t-1]. B) Correta. C) Errada, falta teste cheia. D) Errada, faltateste vazia. E) Errada, pois v[--t]. 
	A) Errada, pois v[t]. B) Correta. C) Errada, falta teste vazia. D) Errada, falta teste cheia. E) Errada, pois v[t-1].
Resposta: 4 
b) Codifique as regras C e D em Java ou C, conforme praticado no laboratório. Lembre-se de informar o usuário com printf em caso de exceção (estrutura cheia / vazia)(1,0 ponto). 
Resposta: 
C. Remoção: if (t != 0) a = v[--t]; else printf (“pilha vazia (impossivel remover).\n”); 
D. Inserção: if (t != n) v[t++] = a; else printf (“pilha cheia (impossivel inserir).\n”);