AED-I-Lista-2

Prévia do material em texto

1 
Algoritmos e Estruturas de Dados I IBm1014 
Departamento de Computação e Matemática 2º Semestre/2012 
 Prof. Dr. José Augusto Baranauskas 2ª Lista de Exercícios 
 
1. Desenhe a seqüência de empilhamento de caixas (exemplo visto em aula) mostrando cada fase dos 
seguintes segmentos de código (S é uma pilha de caracteres e x, y, z são variáveis). 
 
a) S.Push(´a´); 
S.Push(´b´); 
S.Push(´c´); 
S.Pop(x); 
S.Pop(y); 
S.Pop(z); 
b) S.Push(´a´); 
S.Push(´b´); 
S.Push(´c´); 
S.Pop(x); 
S.Pop(y); 
S.Push(x); 
S.Push(y); 
S.Pop(z); 
c) S.Push(´a´); 
S.Push(´b´); 
S.Clear(); 
S.Push(´c´); 
S.Pop(x); 
S.Push(´a´); 
S.Pop(y); 
S.Push(´b´); 
S.Pop(z); 
d) S.Push(´a´); 
S.Push(´b´); 
S.Push(´c´); 
while (! S.Empty()) 
 S.Pop(x); 
 
2. Utilizando a representação contígua de uma pilha, formule os seguintes métodos: 
a) Print que imprime todo o conteúdo da pilha, iniciando pelo topo, sem alterá-la; 
b) Get para obter seu i-ésimo elemento sem eliminá-lo; 
c) Change para alterar o valor do i-ésimo elemento contido na pilha para o valor contido na variável x; 
 
3. Ainda considerando a representação contígua de uma pilha, a implementação vista em aula inicia a 
inserção de elementos a partir do elemento de índice um no vetor, desperdiçando um item (índice zero). 
Implemente os métodos de manipulação de pilhas em C++ considerando que: 
a) os elementos são armazenados a partir do elemento de índice zero; 
b) os elementos são armazenados a partir do final do vetor (assim, a pilha cresce do final do vetor em 
direção ao início). 
Houve alteração na complexidade dos algoritmos? 
 
4. Usando o método Print definido no exercício anterior, execute as seqüências de comandos do exercício 
1, colocando entre cada comando uma chamada ao método Print. Confira com a representação (desenho) 
que você fez. 
 
5. Elabore os mesmo métodos solicitados no exercício 2 para pilhas encadeadas. 
 
6. O método ~Stack() não precisa ser implementado para uma pilha contígua. Por quê? 
 
7. Considerando a implementação encadeada de pilhas, altere a implementação do destruidor ~Stack() de 
modo mais eficiente, usando ponteiro diretamente, ou seja, sem utilizar os métodos já existentes como 
Empty e Pop. Altere também a implementação para incluir um campo que armazena a quantidade de 
elementos existentes na pilha. 
 
8. Em uma pilha encadeada, o método Full sempre retorna false. Por quê? 
 
9. Implemente e teste o procedimento ReverseRead visto em aula usando uma pilha contígua. 
 
10. Altere o programa ReverseRead do exercício anterior para utilizar a pilha encadeada. Houve alguma 
alteração no programa? Qual? 
 
11. Considere o conjunto infinito de cadeias: 
 
c, aca, bcb, abcba, bacab, abbcbba, abacaba, aabcbaa, ... 
 
Uma cadeia típica neste conjunto pode ser especificada como wcwr, onde w contém a sequência de a’s e 
b’s e wr é o reverso de w. Por exemplo, se w = ’ab’, então wr = ’ba’. Dada uma cadeia x de entrada, 
 2 
formular um programa C++ que usa uma pilha para determinar se x pertence ou não ao conjunto de 
cadeias, como descrito por wcwr. 
 
12. Escreva um programa C++ usando pilhas que leia uma linha e verifique se todos os parênteses, colchetes 
e chaves encontrados estão apropriadamente em pares, ou seja, para cada (, [ e { deve haver um ), ] e } 
do mesmo tipo corretamente aninhado. Se uma construção do tipo (... {... )... } é encontrada ou se um dos 
símbolos não possui seu par correspondente, o programa deve escrever uma mensagem de erro, 
indicando a posição na linha onde foi encontrada a falha. 
 
13. Seja S uma pilha de inteiros e x um inteiro. Use os métodos Push, Pop, Empty e Full para escrever 
procedimentos que realizem as seguintes tarefas (declare variáveis e uma segunda pilha se seus 
procedimentos precisarem): 
a) Faça x ser o novo topo da pilha S e deixe o antigo topo de S sem alteração. 
b) Coloque x como o terceiro elemento a partir do topo de S, desde que S possua ao menos 3 inteiros. 
Se não, atribua 9999 a x e deixe S inalterada. 
c) Coloque x como o último elemento da pilha (fundo) ou atribua 9999 a x se S estiver vazia, deixando-
a inalterada. Dica: use uma segunda pilha. 
d) Remova todas as ocorrências de x em S, deixando os demais elementos de S na mesma ordem. 
 
14. Uma importante função teórica, conhecida como função de Ackermann é definida como: 
 
A m n
n m
A m n
A m A m n
( , ) ( , )
( , ( , ))
=
+ =
− =
− −





1 0
11 0
1 1
se 
se 
caso contrario
 
 
a) Defina uma função recursiva para esta função; 
b) Defina uma função não recursiva para esta função. (Sugestão: use uma pilha para armazenar os 
resultados intermediários). 
 
15. Em alguns casos, um programa requer o uso de duas pilhas contendo o mesmo tipo de dados. Se duas 
pilhas são armazenadas em arrays separados, então uma pilha pode estourar enquanto a outra possui 
espaço não utilizado disponível. Uma maneira de evitar esse problema consiste em colocar as duas pilhas 
num único array, sendo que uma pilha cresce da direita para a esquerda e a outra pilha cresce da 
esquerda para a direita, uma em direção à outra. Assim, se uma pilha cresce demais e a outra não, as duas 
caberão no array e não haverá estouro até que todo o espaço realmente seja usado. Declare um novo tipo 
DoubleStack que inclui um array e dois índices TopA e TopB e escreva as operações neste tipo de 
pilha bem como PushA, PushB, PopA e PopB para manipular duas pilhas dentro de uma DoubleStack. 
 
 ... 
→ TopA TopB ← 
 
16. Considere uma rede de desvio ferroviário: 
 
1, 2, ..., n1, 2, ..., n
 
 
 3 
Carros ferroviários numerados 1, 2, 3, ..., n estão do lado direito. Cada carro é trazido dentro da pilha e 
removido a qualquer momento. Por exemplo, se n = 3, pode-se mover para dentro o primeiro, depois o 
segundo e depois o terceiro. Então, em seguida, pode-se retirar os carros produzindo a nova seqüência 3, 
2, 1. Quais são as possíveis permutações, para n=3 e 4 que pode-se obter para os carros? Existem 
permutações que não sejam possíveis? Tente encontrar uma fórmula para o número de movimentos 
necessários para inverter a ordem de n carros.