07 - ESTRUTURA DE DADOS - FILA

Prévia do material em texto

1a Questão 
 
 
 Considere uma fila simples F de inteiros, do tipo Fila definido abaixo. Tal fila deverá armazenar códigos 
de agentes de uma firma de espionagem, desde que haja espaço para um novo agente. Assinale a opção 
que corretamente desenfileira o código de um agente, sabendo que a fila F foi inicializada de acordo com 
o trecho de código abaixo. 
struct Fila { in t v[100], inicio, fim; } ; 
Fila F; 
F. inicio = 0; 
F.fim = -1; 
 
 
 
 
 void desenfileirar(Fila &F) { 
 if (F.inicio > F.fim) 
 cout << "Não há agentes para retirar. " << endl; 
 else { 
 cout << "Removido o agente " << F.v[F.inicio]; 
 F.inicio++; 
 } 
} 
 
 
void desenfileirar(Fila &F) { 
 if (F.fim == -1 && F.inicio == 0) 
 cout << "Não há agentes para retirar. " << endl; 
 else { 
 cout << "Removido o agente " << F.v[F.inicio]; 
 F.inicio++; 
 } 
} 
 
 
 
void desenfileirar(Fila F) { 
 cout << "Removido o agente " << F.v[F.inicio]; 
 F.inicio--; 
 } 
 
 
 
void desenfileirar(Fila F) { 
 if (F.inicio > F.fim) 
 cout << "Não há agentes para retirar. " << endl; 
 else { 
 cout << "Removido o agente " << F.v[F.inicio]; 
 F.inicio++; 
 } 
} 
 
 
void desenfileirar(Fila &F) { 
 if (F.inicio > F.fim) 
 cout << "Não há agentes para retirar. " << endl; 
 else { 
 cout << "Removido o agente " << F.v[F.inicio]; 
 } 
} 
 
 
Gabarito 
Coment. 
 
 
 
 
 2a Questão 
 
 
Seja Q uma estrutura de dados do tipo fila, em que ENQUEUE(X) significa a adição do elemento X à Q e 
que DEQUEUE(), a retirada de um elemento. Q está inicialmente vazia e sofre a seguinte sequencia de 
operações: 
ENQUEUE(1) 
ENQUEUE(2) 
DEQUEUE() 
ENQUEUE(3) 
ENQUEUE(4) 
DEQUEUE() 
DEQUEUE() 
ENQUEUE(5) 
Ao final da sequencia, a soma dos elementos de que (Q) será? 
 
 
 
5 
 9 
 
15 
 
0 
 6 
 
 
Gabarito 
Coment. 
 
 
 
 
 3a Questão 
 
 
Marque a afirmativa que represente uma Lista Circular Simplesmente Encadeada: 
 
 
 
Cada ponteiro possui um só endereço que referencia o "primeiro" nó da lista. 
 
Cada nó possui um só ponteiro que referencia o próximo nó da lista. 
 
Além do campo relativo ao dado, cada nó possui dois ponteiros, 
 O ponteiro do "último" nó não é NULL, mas sim aponta de volta para o "primeiro" nó da lista. 
 
O ponteiro do "primeiro" nó não é NULL, mas sim aponta de volta para o "último" nó da lista, 
formando um ciclo. 
 
 
Gabarito 
Coment. 
 
 
 
 
 4a Questão 
 
 
Considere uma estrutura de dados, representada pela variável P, com procedimentos de inclusão, exclusão 
e consulta do próximo elemento (e) disponível na estrutura, obedecendo às seguintes propriedades: 
 
 Pode-se concluir, então, que P corresponde à seguinte estrutura de dados? 
 
 
 
LISTA 
 
PONTEIRO 
 
CONJUNTO 
 
STRUCT 
 PILHA 
 
 
Explicação: 
Pela estrutura apresentada verifica-se ser a de uma Pilha. 
 
 
 
 
 
 5a Questão 
 
 
Complete os espaços na afirmativa abaixo e assinale a alternativa que apresenta as respostas corretas: O 
escalonamento .................... é do tipo.................., em que o processo que chegar primeiro na fila de 
pronto é o escolhido para ser executado. 
 
 
 
Circular, não-preemptivo. 
 FIFO, não-preemptivo. 
 
SJF (Shortest-Job-First), preemptivo. 
 
LIFO, não-preemptivo. 
 
Por prioridades, preemptivo. 
 
 
Explicação: 
O algoritmo de escalonamento FIFO (First in, first out, em português: "O primeiro a entrar é o primeiro a 
sair, sigla PEPS), ou FCFS(First come, first served, em português: "O primeiro a chegar é o primeiro a ser 
servido") é conhecido popularmente por Algoritmo de Fila Simples, é uma estrutura de dados que 
apresenta o seguinte critério: O primeiro elemento a ser retirado é o primeiro que tiver sido inserido, é 
um algoritmo de escalonamento não preemptivo que entrega a CPU os processos pela ordem de chegada. 
Ele executa o processo como um todo do inicio ao fim não interrompendo o processo executado até ser 
finalizado, então quando um novo processo chega e existe um ainda em execução ele vai para uma fila de 
espera. Esta fila de espera nada mais é do que uma fila que organiza os processos que chegam até eles 
serem atendidos pela CPU. 
Neste escalonamento todos os processos tendem a serem atendidos (por isso evita o fenômeno 
do starvation) ao menos que um processo possua um erro ou loop infinito. O loop infinito irá parar a 
máquina, pois com o FIFO não terá como dar continuidade a execução dos processos que estão aguardando 
na fila de espera. 
O algoritmo FIFO não garante um tempo de resposta rápido pois é extremamente sensível a ordem de 
chegada de cada processo e dos antecessores (se existirem) e se processos que tendem a demorar mais 
tempo chegarem primeiro o tempo médio de espera e o turnaround acabam sendo aumentados. 
 
 
 
 
 
 6a Questão 
 
 
Considere as afirmativas a seguir: 
I. As estruturas de dados pilhas, filas e listas armazenam coleções de itens. A característica que as 
distinguem é a ordem em que podem ser retirados os itens dessas coleções em relação à ordem em que 
foram inseridos. 
II. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma fila. Necessariamente, o 
primeiro elemento a ser removido dessa fila é o elemento A. 
III. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma pilha. Necessariamente, o 
último elemento a ser removido dessa pilha é o elemento E. 
IV. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma lista. Necessariamente, o 
primeiro elemento a ser removido dessa lista é o elemento A. 
 
 
 Somente as afirmativas I e II são corretas. 
 
Somente as afirmativas I, II e III são corretas. 
 
Somente as afirmativas I e IV são corretas. 
 
Somente as afirmativas III e IV são corretas. 
 
Somente as afirmativas II, III e IV são corretas. 
 
 
Explicação: 
Analisando cada afirmativa : 
I. As estruturas de dados pilhas, filas e listas armazenam coleções de itens. A característica que as 
distinguem é a ordem em que podem ser retirados os itens dessas coleções em relação à ordem em que 
foram inseridos. 
Correto. Na pilha insere-se no topo e retira-se do topo. Na fila, insere-se no fim e retira-se do 
início. E na lsita, insere-se e retira-se de qualquer posição. 
II. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma fila. Necessariamente, o 
primeiro elemento a ser removido dessa fila é o elemento A. 
Correto. Fila segue a lógica FIFO, ou seja, o primeiro a entrar será o primeiro a sair. 
III. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma pilha. Necessariamente, o 
último elemento a ser removido dessa pilha é o elemento E. 
Errado. O último a entrar foi o E, logo o E terá que ser o primeiro a sair e não o último. Note 
que pilha segue a lógica LIFO. 
IV. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma lista. Necessariamente, o 
primeiro elemento a ser removido dessa lista é o elemento A. 
Errado. Qualquer elemento pode ser removido da lista. 
Logo, a resposta certa é Somente as afirmativas I e II são corretas. 
 
 
 
 
 
 7a Questão 
 
 
Considere uma fila simples F de inteiros,do tipo Fila definido abaixo. Tal fila deverá armazenar códigos 
de agentes de uma firma de espionagem, desde que haja espaço para um novo agente. Assinale a opção 
que corretamente enfileira o código de um agente, sabendo que a fila F foi inicializada de acordo com o 
trecho de código abaixo. 
struct Fila { in t v[100], inicio, fim; } ; 
Fila F; 
F. inicio = 0; 
F.fim = -1; 
 
 
 
 
 
 
void enfileirar(Fila &F, int codigo) { 
 F.v[F.fim] = codigo; 
 F.fim++; 
} 
 void enfileirar(Fila &F, int codigo) { 
 if (F.fim == 99) 
 cout << "Não há espaço na firma para mais agentes. " << endl; 
 else { 
 F.fim++; 
 F.v[F.fim] = codigo; 
 } 
} 
 
 void enfileirar(Fila &F, int codigo) { 
 if (F.fim == 99) 
 cout << "Não há espaço na firma para mais agentes. " << endl; 
 else 
 F.fim++; 
 F.v[F.fim] = codigo; 
} 
 
 
 void enfileirar(Fila F, int codigo) { 
 if (F.fim == 100) 
 cout << "Não há espaço na firma para mais agentes. " << endl; 
 else { 
 F.fim++; 
 F.v[F.fim] = codigo; 
 } 
} 
 
 void enfileirar(Fila F, int codigo) { 
 F.fim++; 
 F.v[F.fim] = codigo; 
} 
 
 
 
Gabarito 
Coment. 
 
 
 
 
 8a Questão 
 
 
IFMT - Técnico em Técnologia da Informação - 2013 
 Considere a função insere(x: inteiro), que recebe como parâmetro um número inteiro e o insere em 
uma Fila, e ainda, a função remove(), que retira um valor de uma Fila. 
 Dada a Fila [3-4-6-8-10], executam-se os comandos na ordem: insere(1), insere(2), remove(). 
 Após a execução desses comandos, qual será a Fila resultante? 
 
 
 
[3-4-6-8-10] 
 [4-6-8-10-1-2] 
 
[3-4-6-8-10-1] 
 
[2-3-4-6-8-10] 
 
[2-1-3-4-6-8]