Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESGRANRIO 2021

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
cg016236
Banca
CESGRANRIO
Órgão
Banco do Brasil
Ano
2021
Nível
Médio
Cargo
Agente de Tecnologia
Em um determinado treinamento de pessoal de TI, para facilitar o aprendizado sobre o funcionamento da estrutura de dados PILHA, utilizou-se o jogo de trocas, cujas regras são apresentadas a seguir.JOGO DAS TROCAS - REGRASPara começar o jogo, o jogador recebe duas pilhas, P1 e P2.P1 está preenchida com quatro fichas, identificadas por nomes fictícios e empilhadas em ordem alfabética CRESCENTE a partir do topo.P2 está inicialmente vazia.Uma ficha desempilhada de P1 é imediatamente empilhada em P2.A operação (P2,pop) acarreta impressão do nome que está na ficha desempilhada e descarte da ficha.Para ganhar o jogo, o jogador precisa determinar corretamente, dentre sequências derivadas da sequência inicial, por troca da posição de seus elementos, qual delas poderia ser impressa com essas operações.No início do jogo, foram dadas as pilhas P2, vazia, e P1 preenchida com as seguintes operações de empilhamento: push(P1,Zeus); push(P1,Hades); push(P1,Cibele); push(P1, Apolo).Considerando-se esse cenário, qual seria a sequência possível de ser impressa, da esquerda para a direita, de acordo com as regras do JOGO DAS TROCAS?
  1. AApolo, Zeus, Cibele, Hades
  2. BHades, Apolo, Zeus, Cibele
  3. CZeus, Cibele, Apolo, Hades
  4. DHades, Apolo, Cibele, Zeus
  5. ECibele, Hades, Apolo, Zeus
Revelar gabarito e comentário

GabaritoE — Cibele, Hades, Apolo, Zeus

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Estrutura de dados: Pilha (Jogo das Trocas)

Gabarito: letra E. A sequência Cibele, Hades, Apolo, Zeus é a única que pode ser obtida a partir dos movimentos permitidos entre as duas pilhas, conforme simulação do processo de empilhamento e desempilhamento.

O problema simula duas pilhas: P1 contém inicialmente as fichas Apolo (topo), Cibele, Hades, Zeus (base). P2 está vazia. As operações permitidas são: desempilhar de P1 e empilhar imediatamente em P2 (operação M), e desempilhar de P2 imprimindo o nome (operação I). A sequência impressa é a ordem de saída de P2. Para verificar se uma sequência é possível, simula-se o processo: sempre que o topo de P2 for o próximo nome desejado, imprime-se; caso contrário, move-se de P1 para P2 até que o topo de P2 coincida ou P1 se esgote.

Alternativa A — ❌ Incorreta

Apolo, Zeus, Cibele, Hades. Após mover todas as fichas para P2, a ordem de impressão seria Zeus, Hades, Cibele, Apolo. A sequência pedida exigiria imprimir Zeus antes de Cibele, mas Apolo e Cibele já estariam abaixo de Zeus em P2, tornando impossível.

Alternativa B — ❌ Incorreta

Hades, Apolo, Zeus, Cibele. Para imprimir Hades primeiro, seria necessário mover Apolo, Cibele e Hades para P2. Depois, ao imprimir Hades, o topo de P2 seria Cibele, não Apolo. A tentativa de mover Zeus não resolve, pois Zeus ficaria no topo.

Alternativa C — ❌ Incorreta

Zeus, Cibele, Apolo, Hades. Zeus está na base de P1, portanto só pode ser impresso após todos os outros terem sido movidos para P2. Mas, ao movê-los, a ordem em P2 seria Hades, Cibele, Apolo, e Zeus no topo. Após imprimir Zeus, o topo seria Hades, não Cibele.

Alternativa D — ❌ Incorreta

Hades, Apolo, Cibele, Zeus. Similar à B: após imprimir Hades, o topo de P2 é Cibele, impedindo Apolo. Mover Zeus não ajuda.

Alternativa E — ✅ Correta ⟵ GABARITO

Cibele, Hades, Apolo, Zeus. Simulação:

  1. Mover Apolo para P2. P2: [Apolo]

  2. Mover Cibele para P2. P2: [Apolo, Cibele]

  3. Topo = Cibele → imprime Cibele. P2: [Apolo]

  4. Mover Hades para P2. P2: [Apolo, Hades]

  5. Topo = Hades → imprime Hades. P2: [Apolo]

  6. Topo = Apolo → imprime Apolo. P2: []

  7. Mover Zeus para P2. P2: [Zeus]

  8. Topo = Zeus → imprime Zeus. P2: []

Sequência obtida: Cibele, Hades, Apolo, Zeus.

Gabarito: letra E

Link permanente: /questoes/cg016236