EngComp2016 EID001EstruturasdeDados P24 GABARITO

Prévia do material em texto

1 
 
AVALIAÇÃO PRESENCIAL 
CADERNO DE PERGUNTAS 
curso: Engenharia de Computação bimestre: 9º bimestre ano: 2018 | 2sem 
CÓDIGO DA PROVA 
P24 
 Preencha atentamente o cabeçalho de TODAS AS FOLHAS DE RESPOSTA que você utilizar. 
 Ao término da prova, entregue apenas a folha de resposta ao aplicador. Leve este caderno de 
perguntas consigo. 
Boa prova! 
disciplina: EID001 – Estrutura de Dados 
 
 
Questão 1 (2,5 pontos) 
Considere uma lista sequencial estática, definida a seguir: 
 
#define MAX 100 
struct aluno { 
 int matricula; 
 char nome[30]; 
 float nota; 
}; 
typedef struct lista Lista; 
struct lista { 
 int qtd; 
 struct aluno dados[MAX]; 
}; 
 
Implemente uma função que insira de forma ordenada um novo aluno na lista. Essa função deve obedecer 
ao seguinte protótipo: int insere_lista_ordenada (Lista* li, struct aluno al). 
 
 
Questão 2 (2,5 pontos) 
A tabela a seguir deve ilustrar uma lista duplamente encadeada de cores, estruturada sobre os cinco 
elementos de um vetor. 
 
 
Dado que a ordem correta das cores é Branco-Verde-Azul-Vermelho-Amarelo, a coluna Cor, na tabela 
acima, deveria apresentar, de cima para baixo, os seguintes valores: 
a) Branco-Vermelho-Amarelo-Azul-Verde; 
b) Azul-Branco-Verde-Vermelho-Amarelo; 
c) Amarelo-Azul-Branco-Vermelho-Verde; 
d) Azul-Vermelho-Amarelo-Verde-Branco; 
e) Verde-Azul-Vermelho-Branco-Amarelo. 
2 
 
Questão 3 (2,5 pontos) 
Considere um sistema que armazena o caminho entre dois pontos como uma lista encadeada de dados do 
tipo Local, descrita a seguir: 
 struct local { 
 char nome[51]; 
 struct local *prox; 
}; 
typedef struct local Local; 
 
Considere também um tipo abstrato de dados Pilha, definido para armazenar ponteiros para cadeias de 
caracteres e que implementa as seguintes funções: 
 
Pilha* pilha_cria (void) //Retorna o ponteiro para uma nova pilha alocada dinamicamente. 
char* pilha_pop (Pilha* p); //Retira um elemento do topo de uma pilha. 
void pilha_push (Pilha* p, char* x); //Insere um elemento no topo de uma pilha. 
int pilha_vazia (Pilha* p); //Verifica se a pilha está vazia. Retorno é 1, se a pilha está vazia. 
void pilha_libera (Pilha* p); //Esvazia e libera a memória alocada para uma pilha. 
 
Implemente uma função que recebe dois caminhos e verifique se um é o inverso do outro usando Pilha, ou 
seja, compare as duas listas que armazenam caminhos. Essa função deve obedecer ao seguinte protótipo: 
int compara_caminhos (Local* lc1, Local* lc2). 
 
 
Questão 4 (2,5 pontos) 
Considere os estados inicial e final da pilha a seguir, na qual top corresponde ao topo da pilha. 
 
 
Para atingir o estado final dessa pilha, deve-se usar a seguinte sequência de operações básicas: 
a) pop(), pop(), push(9), push(3). 
b) push(2), push(8), pop(), pop(). 
c) push(), push(), pop(8), pop(2). 
d) pop(3), push(), pop(9), push(). 
e) pop(3), pop(9), push(), push(). 
 
 
 
 
3 
 
GABARITO 
curso: Engenharia de Computação bimestre: 9º bimestre P24 
 
Questão 1 
int insere_lista_ordenada (Lista* li, struct aluno al) { 
 if (li == NULL) 
 return 0; 
 if (li->qtd == MAX) 
 return 0; 
 int k, i = 0; 
 while (i < li->qtd && li->dados[i].matricula < al.matricula ) 
 i++; 
 for (k = li->qtd-1; k >= i; k--) 
 li->dados[k+1] = li->dados[k]; 
 li->dados[i] = al; 
 li->qtd++; 
 return 1; 
} 
 
 
Questão 2 
Alternativa D. 
 
 
disciplina: EID001 – Estrutura de Dados 
4 
 
Questão 3 
int compara (Local* lc1, Local* lc2) 
{ 
 Local *ptr; 
 *p = pilha_cria(); 
 for (ptr=lc1; ptr!=NULL; ptr = ptr->prox) 
 pilha_push (p, ptr->nome); 
 for (ptr=lc2; ptr!=NULL; ptr = ptr->prox) { 
 if (pilha_vazia(p)) 
 return 0; 
 if ( strcmp(ptr->nome, pilha_pop(p))!=0 ){ 
 pilha_libera(p); 
 return 0; } 
 } 
 if (!pilha_vazia(p)) 
 return 0; 
 pilha_libera(p); 
 return 1; 
} 
 
Questão 4 
Alternativa A.