Exercícios de Fila

Prévia do material em texto

Exercícios de Fila
João Pedro Galvão de Oliveira
1. Módulo de implementação de fila (versão 1). Escreva um módulo
filadeints.c que implemente uma fila de números inteiros em um vetor alocado
estaticamente. O módulo deve conter as funções criafila, colocanafila, tiradafila,
filavazia e filacheia. O vetor que abriga a fila bem como os índices que indicam o
início e o fim da fila devem ser variáveis globais do módulo. Escreva também uma
interface filadeints.h para o módulo.
2. Escreva uma função que devolva o comprimento (ou seja, o número de
elementos) da fila.
3. Suponha que, diferentemente da convenção adotada acima, a parte do
vetor ocupada pela fila é fila[p..u]. Escreva o código das funções colocanafila,
tiradafila, filavazia e filacheia.
4. Suponha que, diferentemente da convenção adotada acima, a parte do
vetor ocupada pela fila é fila[0..u]. Escreva o código das funções colocanafila,
tiradafila, filavazia e filacheia.
5. Tamanho da fila. O espaço alocado para o vetor fila é suficiente? A
instrução colocanafila (j) não provocará o transbordamento da fila?
6. Alocação dinâmica. Escreva uma versão da função distancias que tenha o
número de cidades como um dos parâmetros. (Portanto, N não é definido por um
#define.).
7. O algoritmo está correto. Prove que a função distancias está correta, ou
seja, que calcula as distâncias corretas a partir de c.
8. Faça uma versão da função distancias que devolva a distância de uma
cidade a a outra b.
9. Imagine um tabuleiro quadriculado com m×n casas dispostas em m linhas
e n colunas. Algumas casas estão livres e outras estão bloqueadas. As casas livres
são marcadas com - e as bloqueadas com #. Há um robô na casa (1,1), que é livre. O
robô só pode andar de uma casa livre para outra. Em cada passo, só pode andar
para a casa que está ao norte, a leste, ao sul ou a oeste. Ajude o robô a encontrar a
saída, que está na posição (m,n). (Sugestão: Faça uma moldura de casas
bloqueadas.).
10. Imagine uma implementação circular de fila em um vetor fila[0..9] que
contém
16 17 18 19 20 11 12 13 14 15
Suponha que o primeiro elemento da fila está na posição de índice 5 e o
último está na posição de índice 4. Essa fila está cheia?
11. Considere a implementação circular de uma fila em um vetor. Escreva o
código das funções colocanafila, tiradafila, filavazia e filacheia. Escreva uma função
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#source-file
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#header-file
que devolva o comprimento (ou seja, o número de elementos) da fila.
12. Módulo de implementação de fila (versão 2). Escreva um módulo
filadeints.c que faça uma implementação circular de uma fila de números inteiros
em um vetor. O módulo deve conter as funções criafila, colocanafila, tiradafila,
filavazia e filacheia. O vetor e as variáveis que indicam o início e o fim da fila
devem ser globais no módulo. Escreva também uma interface filadeints.h para o
módulo. (Inspire-se num dos exercícios acima.).
13. Módulo de implementação de fila (versão 3). Escreva um módulo
filadeints.c que implemente uma fila de números inteiros num vetor com
redimensionamento. O módulo deve conter as funções criafila, colocanafila,
tiradafila, filavazia, liberafila. (Nessa versão, a função filacheia não faz sentido.)
Trate os parâmetros da fila como variáveis globais do módulo. Escreva também
uma interface filadeints.h para o módulo.
14. Módulo de implementação de fila (versão 4). Escreva um módulo
filadechars.c que implemente uma fila de bytes.
15. Implemente uma fila em uma lista encadeada circular sem célula-cabeça.
(Basta manter o endereço u da última célula; a primeira célula será apontada por
u->prox. A lista encadeada estará vazia se e somente se u == NULL.).
16. Implemente uma fila em uma lista encadeada não circular com
célula-cabeça. Será preciso manter o endereço c da célula-cabeça e o endereço u
da última célula.
17. Implemente uma fila em uma lista encadeada não circular sem
célula-cabeça. Será preciso manter um ponteiro p para a primeira célula e um
ponteiro u para a última.
18. Módulo de implementação de fila (versão 5). Escreva um módulo
filadeints.c que implemente uma fila de números inteiros numa lista encadeada
(escolha lista circular ou não circular, com ou sem cabeça). O módulo deve conter
as funções criafila, colocanafila, tiradafila, filavazia, liberafila. Trate os
parâmetros da fila como variáveis globais do módulo. Escreva também uma
interface filadeints.h para o módulo. (Inspire-se num dos exercícios acima.).
19. Lista duplamente encadeada. Implemente uma fila em uma lista
duplamente encadeada sem célula-cabeça. Use um ponteiro p para a primeira
célula e um ponteiro u para a última.
20. Deque. Uma fila dupla (= deque, pronuncia-se deck) permite inserção e
remoção em qualquer das duas extremidades da fila. Implemente uma fila dupla
(em um vetor ou uma lista encadeada) e escreva as funções de manipulação da
estrutura.
21. Considere uma pilha P vazia e uma fila F não vazia. Utilizando apenas os
testes de fila e pilha vazias, as operações Enfileira, Desenfileira, Empilha,
Desempilha, e uma variável aux do TipoItem, escreva uma função que inverta a
ordem dos elementos da fila.
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#source-file
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#header-file
https://www.ime.usp.br/~pf/algoritmos/aulas/fila.html#filadeints-module-simple
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#source-file
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#header-file
https://www.ime.usp.br/~pf/algoritmos/aulas/bytes.html#byte
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#source-file
https://www.ime.usp.br/~pf/algoritmos/apend/compilation.html#header-file
https://www.ime.usp.br/~pf/algoritmos/aulas/fila.html#filadeints-module-resized
https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html#other-kinds
https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html#other-kinds
22. Para um dado número inteiro n > 1, o menor inteiro d > 1 que divide n é
chamado de fator primo. É possível determinar a fatoração prima de n achando-se
o fator primo d e substituindo n pelo quociente n / d, repetindo essa operação até
que n seja igual a 1. Utilizando um dos TADs vistos em sala (Lista, Pilha ou Fila) para
auxiliá-lo na manipulação de dados, implemente uma função que compute a
fatoração prima de um número imprimindo os seus fatores em ordem
decrescente. Por exemplo, para n=3960, deverá ser impresso 11 * 5 * 3 * 3 * 2 * 2 * 2.
Justifique a escolha do TAD utilizado.
23. Considere a implementação de filas usando arranjos “circulares”. Escreva
uma função FuraFila(TipoFila* pFila, TipoItem x) que insere um item na primeira
posição da fila. O detalhe é que seu procedimento deve ser O(1), ou seja, não pode
movimentar os outros itens da fila. (observe que este neste caso, estaremos
desrepeitando o conceito de FILA – primeiro a entrar é o primeiro a sair).
24. Existem partes de sistemas operacionais que cuidam da ordem em que os
programas devem ser executados. Por exemplo, em um sistema de computação
de tempocompartilhadao (“time-shared”) existe a necessidade de manter um
conjunto de processos em uma fila, esperando para serem executados. Escreva
um programa que seja capaz de ler uma série de solicitações para: a. Incluir novos
processos na fila de processo; b. Retirar da fila o processo com o maior tempo de
espera; c. Imprimir o conteúdo da lista de processo em determinado momento.
Assuma que cada processo é representado por um registro composto por um
número identificador do processo.
25. Que conjunto de condições é necessário e suficiente para que uma
sequência de operações de Enfileira e Desenfileira sobre uma única fila vazia deixa
a fila vazia sem provocar underflow (tentativa de executar Desenfileira com a fila
vazia)? Que conjunto de condições é necessário e suficiente para que essa
sequência deixe inalterada uma fila não vazia?
26. Se um fila representadapor arranjos (vetores) não é considerada circular,
sugere-se que cada operação Desenfileira deve deslocar para “frente” todo
elemento restante de uma fila. Um método alternativo é adiar o deslocamento até
que “tras” seja igual ao último índice do vetor. Quando essa situação ocorre e faz-se
uma tentativa de inserir um elemento na fila, a fila inteira é deslocada para
“frente”, de modo que o primeiro elemento da fila fique na primeira posição do
vetor, ou posição 0, caso a implementação seja em C/C++/Java. Quais são as
vantagens desse método sobre um deslocamento em cada operação Desenfileira?
Quais as desvantagens? Reescreva as funções Desenfileira, Enfileira e Vazia
usando esse novo método.
27. Como você implementaria uma fila de pilhas? Uma pilha de filas? Uma fila
de filas? Escreva rotinas para implementar as operações corretas para cada uma
destas estruturas de dados.
28. Implemente uma fila de inteiros em C/C++, usando uma implementação
por arranjos (um vetor queue[100]), onde queue[0] e queue[1] são usados para
representar a posição inicial e final da fila respectivamente e queue[2] a queue[99]
são usados para conter os elementos do vetor. Demonstre como inicializar esse
vetor de modo a representar a fila vazia e escreva funções Desenfileira, Enfileira e
Vazia para tal implementação.
29. Implemente uma fila em C/C++, onde cada item da fila consista em um
número variável de inteiros.
30. Um deque é um conjunto de itens a partir do qual podem ser eliminados e
inseridos itens em ambas as extremidades. Chame as duas extremidades de um
deque esq e dir. Como um deque pode ser representado como um vetor em
C/C++? Escreva quatro funções em C/C++,
RemDir, RemEsq, InsDir, InsEsq,
para remover e inserir elementos nas extremidades esquerda e direita de um
deque. Certifique-se de que as funções funcionem corretamente para o deque
vazio e detectem o estouro e o underflow (tentativa de remoção quando a fila está
vazia). Quais as desvantagens dessa implementação com relação a
implementação por encadeamento/alocação dinâmica?