Prova Antiga Algoritmo e Estrutura de Dados c

Parte 1 de 5 Questão 1 197 20 Pontos Questão 1 de 1 197 20 Pontos Assumindo a implementação de uma pilha S de caracteres por meio de um vetor de tamanho 5 elementos complete os diagramas fornecidos de forma que representem a sequência numerada de operações represente nos diagramas elementos que não fazem mais parte da pilha com o símbolo Indique também ao final de cada passo onde se encontra o topo da pilha nos diagramas bem como o valor da variável x não utilize apóstrofos nas respostas nas operações pop As duas primeiras linhas do diagrama já se encontram devidamente preenchidas Stack s char x 1 SpushA 2 SpushB 3 SpushC 4 Spopx 5 SpushD 6 SpushE 7 Spopx 8 SpushF 9 SpushG 10 Spopx 11 Spopx 12 Spopx 1 2 3 4 5 1 A topo 1 1 2 3 4 5 2 A B topo 2 1 2 3 4 5 3 A B C topo 3 1 2 3 4 5 4 A B topo 2 x C 1 2 3 4 5 5 A B D topo 3 1 2 3 4 5 6 A B D E topo 4 1 2 3 4 5 7 A V D topo 3 x E 1 2 3 4 5 8 A B D E topo 4 1 2 3 4 5 9 A B D E G topo 5 1 2 3 4 5 10 A B D E topo 4 x G 1 2 3 4 5 11 A B D topo 3 x E 1 2 3 4 5 A B topo 2 x D Resposta Correta A B C 3 A B 2 C A B D 3 A B D E 4 A B D 3 E A B D F 4 A B D F G 5 A B D F 4 G A B D 3 F A B 2 D Parte 2 de 5 Questão 2 2020 Pontos Na figura seguinte encontrase uma simulação de uma pilha encadeada utilizando um vetor contendo dois campos a primeira coluna armazena a parte dos dados e a segunda coluna armazena o próximo elemento Os índices do vetor assumem valores inteiros maiores ou iguais a zero O valor 1 indica final do encadeamento Com base na figura responda as seguintes perguntas entry nextNode 66 1 25 1 9 0 33 8 11 1 10 9 7 2 18 4 21 6 48 7 Ao atravessar a segundapilha a partir do topo quais os elementos entry e em que ordem são visitados Represente elementos que não fazem parte da pilha com o símbolo Início da segundapilha 10 48 18 11 25 2 2 2 2 2 Resposta Correta 10 48 18 11 25 Ao atravessar a primeirapilha a partir do topo indique quais os elementos entry e em que ordem são visitados Represente elementos que não fazem parte da pilha com o símbolo Início da primeirapilha 33 21 7 9 66 2 2 2 2 2 Resposta Correta 33 21 7 9 66 Parte 3 de 5 Questão 3 2020 Pontos Para sua referência junto a esta questão está sendo fornecida a implementação de uma fila em um vetor circular Queueh include iostream include cstdlib using namespace std ifndef QUEUEH define QUEUEH typedef char QueueEntry class Queue public Queue void appendQueueEntry x void serveQueueEntry x bool empty void clear bool full void getFrontQueueEntry x void getRearQueueEntry x long int size private static const long int MaxQueue 5 numero maximo de elementos long int head inicio da fila long int tail final da fila long int count no de elementos fila QueueEntry entryMaxQueue1 vetor com elementos endif Queuecpp include Queueh QueueQueue clear bool Queueempty return count 0 bool Queuefull return count MaxQueue void QueueappendQueueEntry x if full cout Fila Cheia endl abort tail tail MaxQueue 1 entrytail x void QueueserveQueueEntry x if empty cout Fila Vazia endl abort count count 1 x entryhead head head MaxQueue1 void Queueclear count 0 head 1 tail MaxQueue void QueuegetFrontQueueEntry x if empty cout Fila vazia endl abort x entryhead void QueuegetRearQueueEntry x if empty cout Fila vazia endl abort x entrytail long int Queuesize return count 3 Qservex 4 Qservex 5 QappendC 6 QappendD 7 QappendE 8 QappendF 9 QappendG 10 Qservex 11 Qservex 12 Qservex 1 2 3 4 5 1 A head 1 tail 1 1 2 3 4 5 2 A B head 1 tail 2 Resposta Correta A 1 1 A B 1 2 B 2 2 A 3 2 B C 3 3 C D 3 4 C D E 3 5 F C D E 3 1 F G C D E 3 2 F G D E 4 2 C F G E 5 2 D F G 1 2 E Parte 4 de 5 Questão 4 2020 Pontos Para sua referência junto a esta questão está sendo fornecida a implementação de uma fila em um vetor físico Queueh include iostream include cstdlib using namespace std ifndef QUEUEH define QUEUEH typedef char QueueEntry class Queue public Queue void appendQueueEntry x void serveQueueEntry x void clear bool full bool empty void getFrontQueueEntry x void getRearQueueEntry x long int size private static const long int MaxQueue 5 numero maximo de elementos long int tail final da fila QueueEntry entryMaxQueue1 vetor com elementos endif Queuecpp include Queueh QueueQueue tail 0 bool Queueempty return tail 0 bool Queuefull return tail MaxQueue void QueueappendQueueEntry x if full cout Fila Cheia endl abort tail entrytail x void QueueserveQueueEntry x int i if empty cout Fila Vazia endl abort x entry1 fori1 itail i entryi entryi1 tail void Queueclear tail 0 void QueuegetFrontQueueEntry x ifempty cout Fila vazia endl abort x entry1 void QueuegetRearQueueEntry x ifempty cout Fila vazia endl abort x entrytail long int Queuesize return tail Questão 1 de 1 2020 Pontos Assuma a implementação de uma fila de caracteres por meio de um vetor físico de tamanho 5 elementos complete os diagramas fornecidos de forma que representem a sequência numerada de operações represente nos diagramas elementos que não fazem mais parte da fila pelo símbolo Indique também ao final de cada passo onde se encontra o índice de final tail da fila física Não utilize apóstrofos em sua resposta Queue Q char x 1 QappendA 2 QappendB 3 QappendC 4 Qservex 1 2 3 4 5 3 B head 2 tail 2 x A 1 2 3 4 5 4 head 3 tail 2 x B 1 2 3 4 5 5 C head 3 tail 3 1 2 3 4 5 6 C D head 3 tail 4 1 2 3 4 5 7 C D E head 3 tail 5 1 2 3 4 5 8 E C D E head 3 tail 1 1 2 3 4 5 9 E G C D E head 3 tail 2 1 2 3 4 5 10 E G D E head 4 tail 2 x C 1 2 3 4 5 11 E G E head 5 tail 2 x D 1 2 3 4 5 12 E G head 1 tail 2 x E tail 5 QappendD QappendE Qservex QappendF QappendG Qservex Qservex Qservex tail 1 tail 2 tail 3 tail 5 tail 4 tail 3 tail 2 Resposta Correta A 1 A B 2 A B C 3 B C 2 B C D E 4 C D E 3 C D E F 4 C D E F G 5 D E F G 4 E F G 3 F G 2 Parte 5 de 5 Questão 5 1920 Pontos 1920 Pontos Questão 1 de 1 Usando apenas as operações métodos em pilhas ou seja sem saber detalhes sobre como a pilha foi implementada escreva um procedimento em C que esvazia uma pilha colocando no topo de outra pilha 3 que pode não estar vazia 4 de forma que as entradas que estavam na primeira pilha mantém a mesma ordem relativa Ao escrever o procedimento verifique os casos de estruturas cheias ou vazias conforme apropriado Sua solução não deve fazer uso de vetores ou matrizes O número de elementos em cada pilha é variável e cada elemento é do tipo StackEntry um tipo do dado definido pelo usuário por meio de typedef void esvaziarStack s1 Stack s2 Pré São dadas duas pilhas s1 e s2 que podem estar vazias ou não contendo elementos do tipo StackEntry Pós O conteúdo da pilha s1 é movido para a pilha s2 mantendose a mesma ordem relativa dos elementos Ao final a pilha s1 encontrarseá vazia A seguir é dado um exemplo da funcionalidade desejada para este método Situação antes da chamada de esvaziar s1s2 topo s2 30 20 10 200 100 topo s1 s1 s2 vazia Situação após a chamada de esvaziar s1s2 Feedback void esvaziarStack s1 Stack s2 Stack s3 StackEntry x while s1Empty s3Full s1Popx s3Pushx while s3Empty s2Full s3Popx s2Pushx