Exercícios sobre TAD Fila

Prévia do material em texto

Universidade Tecnológica Federal do Paraná (UTFPR)
Departamento Acadêmico de Informática (DAINF)
Estrutura de dados I
Professor: Rodrigo Minetto
(rminetto@dainf.ct.utfpr.edu.br)
Lista de exerćıcios - TAD Fila
1) Perito Criminal - Informática - NUCEPE - 2018 - Acerca da estrutura
de dados do tipo filas, considere as operações de inserção e remoção de uma
fila F abaixo: 1. enfileira (‘amarelo’, F) 2. enfileira (‘branco’, F) 3. enfileira
(‘verde’, F) 4. enfileira (‘vermelho’, F) 5. desenfileira (F) 6. desenfileira (F)
7. enfileira (‘azul’, F) 8. enfileira (desenfileira (F), F). O resultado final das
operações resulta em:
• (A) [verde, azul, vermelho].
• (B) [branco, azul, amarelo].
• (C) [verde, azul].
• (D) [amarelo, branco].
• (E) [vermelho, azul, verde].
2) Supondo uma fila circular implementada com o aux́ılio de um vetor,
escreva uma função verifica fila, que dado um certo elemento é desejado
retornar a posição no vetor que o armazena. Por exemplo, suponha que em
uma fila de tamanho 6, são adicionados os seguintes elementos: 2, 4, 6, 8, 10
e são retirados três elementos e então adicionados os elementos 12, 14 e 16.
Logo, a posição do elemento 16 nessa fila é 1. Se um elemento não existir
sua posição é -1.
int busca_posicao (Queue *q, int elem) {
/*Nesta funcao voce pode usar os atributos de
fila como ini, fim, vetor, e o simbolo ->!*/
...
}
1
int main () {
int tam = 5;
Fila *f = criar_fila (tam + 1);
inserir (f, 2);
inserir (f, 4);
inserir (f, 6);
inserir (f, 8);
inserir (f, 10);
remover (f);
remover (f);
remover (f);
inserir (f, 12);
inserir (f, 14);
inserir (f, 16);
int elem = 16;
printf("O elemento %d esta na posicao %d\n", elem, busca_posicao (f, elem));
elem = 20;
printf("O elemento %d esta na posicao %d\n", elem, busca_posicao (f, elem));
destruir_fila (f);
return 0;
}
3) O Merge-Sort é um algoritmo muito importante para ordenar elemen-
tos. Um de seus passos consiste em unir dois conjuntos já classificados em
apenas um. Escreva uma função que recebe como entrada duas filas f1 e f2
com os elementos ordenados crescentemente, retira os elementos dessas filas
para produzir como sáıda uma terceira fila f3 com todos os elementos de f1
e f2 e também ordenada crescentemente.
Por exemplo, suponha as entradas: f1 = [1 3 5 7] e f2 = [2 4 5 6 8 9
10]. Sáıda : f3 = [1 2 3 4 5 5 6 7 8 9 10]. (Dica: crie um função que mostra
o primeiro elemento da fila mas não o retira). As filas F1 e F2 devem ficar
vazias e serem deletadas no final da função.
Utilize o seguinte protótipo para a sua função:
Fila* concatena (Fila *f1, Fila *f2) {
2
/*Nao use "->", nem os atributos ini, fim e vetor aqui dentro dessa
funcao apenas operacoes de fila como inserir, remover, vazia, etc. */
...
return *f3;
}
Sua função deve utilizar somente operações enfileirar (enqueue), desenfi-
leirar (dequeue) e vazio (empty) (ou seja, não acesse diretamente os atributos
internos do TAD Fila, como por exemplo fila→tam, fila→ini, fila→fim ou
fila→vetor). No entanto, se achar necessário, você pode trabalhar com os
atributos internos para criar uma nova função para o TAD Fila que mostra
o primeiro elemento da fila mas não o retira e para retornar o tamanho da
fila.
4) Seja uma variante da brincadeira de criança “batata-quente”. Suponha
que um conjunto de n crianças formam um ćırculo, a brincadeira consiste em
passar a batata por m−1 crianças, sendo que a m-ésima criança que recebe a
batata é eliminada da brincadeira. A criança eliminada então deixa a batata
para a próxima criança no ćırculo, e isso acontece até que não sobre nenhuma
criança. Sendo que a última criança é a vencedora. Descreva um algoritmo
que imprime a sequência de crianças eliminadas. Por exemplo se n = 5,
suponha que a brincadeira começa em n = 1, e m = 3, então a sequência de
eliminações é dado por: 3, 1, 5, 2, 4, pois
1 2 3 4 5
1 2 *3 4 5 (1 iteraç~ao - elimina o 3)
*1 2 *3 4 5 (2 iteraç~ao - elimina o 1)
*1 2 *3 4 *5 (3 iteraç~ao - elimina o 5)
*1 *2 *3 4 *5 (4 iteraç~ao - elimina o 2)
*1 *2 *3 *4 *5 (5 iteraç~ao - elimina o 4)
Importante: é obrigatório o uso de operações de alto ńıvel de uma
Fila. Não use ”→”, nem os atributos ini, fim e vetor para resolver
essa questão. Use apenas as funções inserir, remover, vazia, etc.
3