Algoritmos e Estrutura de Dados · FGV · 2024 | Questão sqc-fg085909

Algoritmos e Estrutura de DadosEstrutura de Dados

Código: fg085909
Banca: FGV
Órgão: INPE
Ano: 2024
Nível: Superior

Cargo: Tecnologista Júnior I - Operação de Sistemas Espaciais Embarcados

A Notação Polonesa Reversa (RPN, do inglês Reverse Polish Notation) foi desenvolvida como uma forma de escrever expressões lógicas e aritméticas sem usar parênteses. Essa notação ganhou popularidade ao ser implementada em calculadoras científicas, onde permite reduzir a quantidade de acionamento de teclas no cálculo de expressões.Quando uma calculadora opera no modo RPN, os operandos são inseridos previamente em uma estrutura de dados e, ao utilizar-se um operador (soma, subtração, ...), a quantidade de operandos necessários são retirados da estrutura na ordem inversa da inserção e, após o cálculo da operação, o resultado é inserido na estrutura de dados. Assim, por exemplo, caso se deseje calcular a expressão A + (B – C)*D em uma calculadora operando no modo RPN, pode-se seguir o seguinte procedimento:• Insere A• Insere B• Insere C• Realiza a operação de subtração• Insere D• Realiza a operação de multiplicação• Realiza a operação de somaDe acordo com a descrição acima, assinale a opção que indica a estrutura de dados que melhor caracteriza a utilizada pelo modo RPN para armazenar os operandos e resultados.

ALista duplamente encadeada.
BLista encadeada circular.
CPilha.
DFila.
EÁrvore.

Revelar gabarito e comentário

GabaritoC — Pilha.

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”.

Notação Polonesa Reversa (RPN) e estrutura de dados subjacente

Gabarito: letra C. A RPN utiliza uma estrutura LIFO (Last In, First Out) para armazenar operandos e resultados intermediários, caracterizando uma pilha. No exemplo dado, os operandos são inseridos sequencialmente e os operadores retiram os dois últimos valores inseridos (ordem inversa), operam e empilham o resultado – comportamento típico de uma pilha.

A banca testa o conhecimento do comportamento das estruturas de dados lineares. A descrição do enunciado (inserir e retirar na ordem inversa) é a definição operacional de uma pilha.

Estruturas de dados lineares: Pilha (LIFO) (Inserção e remoção no topo, RPN usa pilha); Fila (FIFO) (Primeiro a entrar, primeiro a sair, Não serve para RPN); Lista duplamente encadeada (Acesso bidirecional, Não impõe LIFO); Lista encadeada circular (Acesso em qualquer ponto, Não impõe LIFO); Árvore (Estrutura hierárquica não linear, Inadequada para RPN)

Alternativa A — ❌ Incorreta

Lista duplamente encadeada permite inserção e remoção em qualquer posição, não impõe a ordem LIFO. Embora possa ser usada para implementar uma pilha, sua característica principal é o acesso bidirecional, o que não é necessário nem específico para a RPN.

Alternativa B — ❌ Incorreta

Lista encadeada circular tem os mesmos problemas da lista duplamente encadeada: permite acesso em qualquer ponto, mas não restringe a ordem a LIFO.

Alternativa C — ✅ Correta ⟵ GABARITO

Pilha é a estrutura que segue estritamente a disciplina LIFO: as operações de inserção (push) e remoção (pop) ocorrem sempre no topo, exatamente como descrito no funcionamento da RPN.

Alternativa D — ❌ Incorreta

Fila opera em FIFO (First In, First Out): o primeiro elemento inserido é o primeiro a ser removido. Isso contraria a exigência da RPN de retirar os operandos na ordem inversa da inserção.

Alternativa E — ❌ Incorreta

Árvore é uma estrutura hierárquica não linear, inadequada para o armazenamento sequencial LIFO exigido pela RPN.

Gabarito: letra C (Pilha).

Link permanente: /questoes/fg085909