Estruturas de Dados: Pilhas, Filas e Deques

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL 
INSTITUTO DE INFORMÁTICA 
Bacharelado em Ciência da Computação e 
Engenharia da Computação 
INF 01203 – Estruturas de Dados 
Profa. Renata Galante (galante@inf.ufrgs.br ) 
Pilhas, Filas e Deques 
01. Qual o modelo lógico (pilha, fila e deque) e modelo físico (LA, LAC, LSE, LSEC, 
LDE, LDEC) poderiam ser utilizados para representar cada um dos casos descritos a 
seguir? 
 
A – Imagine um colecionador de vinhos que compra vinhos recentes e guarda-os em 
uma adega para envelhecerem, e que a cada ocasião especial abre sempre sua última 
aquisição (para poupar os mais antigos). Imagine uma aplicação que possa: (i) incluir 
novos vinhos na adega; e (ii) informar qual vinho deve ser aberto em uma ocasião 
especial. 
Modelo Lógico: __________________________________________________________ 
Modelo Físico: ___________________________________________________________ 
 
B – Na maioria das linguagens de programação, os símbolos de parentização (), [] e {} 
devem ser balanceados e apropriadamente aninhados. Considere expressões na 
linguagem C, onde cada ( deve ter o correspondente ), e { deve ter o correspondente 
}. Qual é a estrutura de dados adequada para verificar indentações? Exemplos: 
• { [ ( ) ] } correto! 
• { [ ) ( ] } errado! 
• { [ ( ] ) } errado! 
• { ( ) { } [ ( ) ] } correto! 
Modelo Lógico: __________________________________________________________ 
Modelo Físico: ___________________________________________________________ 
 
C – Uma palavra é palíndromo se a sequencia de letras que a forma é a mesma, quer 
seja lida da esquerda para a direita ou da direita para a esquerda (exemplo: RAIAR). Qual 
o modelo físico e o modelo lógico adequados se o objetivo fosse implementar uma função 
para reconhecer se uma palavra é palíndromo ou não. 
Modelo Lógico: __________________________________________________________ 
Modelo Físico: ___________________________________________________________ 
 
 
02 – Insira os dados de entrada numa fila. Em seguida retire cada dado da fila e insira 
numa pilha. Mostre a pilha. Depois retire os dados da pilha e insira na fila. Mostre a fila. 
Dados de entrada: 11 – 12 – 23 – 14 – 25 – 50 – 8 – 18 – 29 – 10 
As estruturas mostradas ficam: 
I. PILHA: (topo) 10 – 29 – 18 – 8 – 50 – 25 – 14 – 23 – 12 – 11 
II. FILA: (início) 11 – 12 – 23 – 14 – 25 – 50 – 8 – 18 – 29 – 10 (fim) 
III. FILA: (início) 10 – 29 – 18 – 8 – 50 – 25 – 14 – 23 – 12 – 11 (fim) 
IV. PILHA: (topo) 11 – 12 – 23 – 14 – 25 – 50 – 8 – 18 – 29 – 10 
V. A FILA mostrada fica com os elementos em ordem invertida dos dados de 
entrada. 
VI. A PILHA mostrada fica com os elementos em ordem invertida dos dados de 
entrada. 
Está correto o que se afirma APENAS em: 
a) I, III, V e VI 
b) I, II, V e VI 
c) I, III, IV e VI 
d) I, IV, V e VI 
e) I, II, IV e V 
 
03 – Considere que, no trecho do programa abaixo, representado por seu pseudocódigo, 
seja fornecido para num, sucessivamente, os valores inteiros 1, 2, 3, 4, 5, 3 e 6. 
Nesse caso, ao final da execução do programa, o valor de x será igual a: 
Algoritmo pilha 
inicio 
{ iniciarPilha(s) 
 enquanto (não for final das entradas) faça 
 { ler num 
 Se (num != 3) 
 Então empilhar (s, num) 
 Senão { desempilhar(s) 
 X = topo(s) 
 } 
 } 
} 
 
 
a) 4 e a pilha terá os valores 6, 3, 5, 4, 3, 2 e 1 
b) 3 e a pilha terá os valores 6, 5 e 1 
c) 3 e a pilha terá os valores 6, 4 e 1 
d) 4 e a pilha terá os valores 6, 4 e 1 
e) 4 e a pilha terá os valores 6, 5, 4, 2 e 1 
 
 
 
4 – Em relação às estruturas de dados do tipo lista, considere as assertivas abaixo, 
assinalando V, se verdadeiras, ou F, se falsas. 
 
( ) Uma implementação de fila por meio de arranjos é circular delimitada pelos 
apontados Frente e Trás. Para enfileirar um item, basta mover o apontador Trás uma 
posição no sentido horário; para desenfileirar um item, basta mover o apontador 
Frente uma posição no sentido horário. 
( ) Em uma lista duplamente encadeada, todas as inserções são realizadas em um 
extremo da lista, enquanto as exclusões e acessos são realizados no outro extremo da 
lista. 
( ) Uma pilha é uma lista linear nas quais inserções, exclusões e acessos a itens 
ocorrem sempre em um dos extremos da lista. 
( ) Filas são utilizadas quando se deseja processar itens de acordo com a ordem 
“primeiro-que-chega, primeiro-atendido”. 
 
05 – Considere a existência de um tipo de dados abstrato Fila de número inteiros, cuja 
interface (protótipo) está definida no arquivo fila.h da seguinte forma: 
 
struct fila{ 
 int v; 
 struct fila *elo; 
}; 
typedef struct fila Fila; 
 
Fila* cria(void); // cria uma fila vazia 
int vazia(Fila *f); // retorna 1 se a fila estiver vazia e zero; caso contrário 
Fila* insere(Fila *f, int v); // insere o valor v no final da fila e devolve um ponteiro para o 
início da fila modificada 
Fila* exclui(Fila *f); // excluir o nó no início da fila e devolve um ponteiro para a fila modificada 
int consulta(Fila *f); // retorna o valor que está no início da fila 
Fila* libera (Fila *f); // desaloca todos os nós da fila 
 
Sem conhecer a representação interna do tipo de dados abstrato Fila e usando apenas as 
funções declaradas no arquivo fila.h, implemente em C uma nova função chamada 
excluiNo() que implemente uma função que exclui um nó da fila cujo valor é passado 
como parâmetro. 
Fila* excluiNo (Fila *f, int v);