AED-I-Lista-3

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 3ª Lista de Exercícios 
 
1. Suponha que Q é uma fila contendo caracteres x, y e z são variáveis do tipo caractere. Mostre o conteúdo 
da fila Q em cada passo dos seguintes fragmentos de código bem como o valor das variáveis x, y e z: 
 
a) Q.Append(´a´); 
Q.Append(´b´); 
Q.Append(´c´); 
Q.Serve(x); 
Q.Serve(y); 
Q.Serve(z); 
b) Q.Append(´a´); 
Q.Append(´b´); 
Q.Append(´c´); 
Q.Serve(x); 
Q.Serve(y); 
Q.Append(x); 
Q.Append(y); 
Q.Serve(z); 
c) Q.Append(´a´); 
Q.Append(´b´); 
Q.Clear(); 
Q.Append(´c´); 
Q.Serve(x); 
Q.Append(´a´); 
Q.Serve(y); 
Q.Append(´b´); 
Q.Serve(z); 
d) Q.Append(´a´); 
Q.Append(´b´); 
Q.Append(´c´); 
while (! Q.Empty()) 
 Q.Serve(x); 
 
2. Usando as operações em pilhas e filas, escreva os procedimentos que realizam as seguintes tarefas. Ao 
escrever cada procedimento, verifique os casos de estruturas cheias ou vazias, conforme apropriado. 
a) Mover todas as entradas de uma pilha para uma fila; 
b) Mover todas as entradas de uma fila para uma pilha; 
c) Esvaziar uma pilha colocando no topo de outra pilha  que pode não estar vazia  de forma que as 
entradas que estavam na primeira pilha mantenham a mesma ordem relativa; 
d) Esvaziar uma pilha colocando no topo de outra pilha  que pode não estar vazia  de forma que as 
entradas que estavam na primeira pilha fiquem em ordem relativa reversa; 
e) Começando com uma fila e uma pilha vazia use a pilha para inverter a ordem de todas as entradas 
existentes na fila; 
f) Começando com uma pilha e uma fila vazia use a fila para inverter a ordem de todas as entradas 
existentes na pilha; 
 
3. Escreva os métodos que implementam filas pelo método simples, mas lento, de manter o início da fila 
(head) sempre na primeira posição de um vetor. 
 
4. Escreva os métodos que implementam filas num vetor com dois índices head e tail de modo que, quando 
tail atinge o final do vetor, todas as entradas são movidas para o começo do vetor. 
 
5. Escreva os métodos para o processamento de uma fila onde a implementação não mantém um contador 
(count) do número de entradas na fila, mas usa as condições especiais 
 
tail = 0 e head = 1 
 
para indicar uma fila vazia. 
 
6. Reescreva o conjunto de métodos vistos em aula, usando uma variável booleana full ao invés de um 
contador (count) de entradas de uma fila. 
 
7. Ainda considerando a representação contígua de uma fila, 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 filas 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 fila cresce do final do vetor em 
direção ao início). 
Houve alteração na complexidade dos algoritmos? 
 
8. Escreva os métodos para a implementação de filas num vetor quando pode-se assumir que a fila pode ser 
esvaziada sempre que necessário. Escreva um método Append que adiciona entradas na fila se houver 
espaço; se não houver, chamará outro método ServeAll que esvaziará a fila. Ao escrever ServeAll, 
 2
assuma a existência de um método auxiliar Service(QueueEntry x) que processa apenas uma única 
entrada que acabou de ser removida da fila. 
 
9. Escreva os métodos para o processamento de uma fila num vetor circular com uma entrada sem ser 
utilizada. Assim, considera-se que o vetor está cheio quando tail encontra-se duas posições atrás de 
head; quando tail está uma posição antes, indicará sempre uma fila vazia.