Em um projeto de programação, uma equipe precisa calcular o termo de número n da sequência de Fibonacci usando…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um projeto de programação, uma equipe precisa calcular o termo de número n da sequência de Fibonacci usando recursão com memoização. Como n pode chegar a 100, os resultados já calculados devem ser guardados nas posições correspondentes aos índices 0, 1, 2, ..., n. A cada nova chamada recursiva, o programa deve verificar diretamente se o resultado de determinado índice já está armazenado, evitando recalcular esse termo. Com base nessa implementação, qual estrutura de dados é mais adequada para armazenar os resultados intermediários?
- A) Uma pilha encadeada
- B) Uma lista indexada
- C) Uma variável isolada
- D) Uma matriz bidimensional
- E) Uma fila encadeada
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado descreve que os resultados devem ser guardados nas posições correspondentes aos índices 0, 1, 2, ..., n, e que a verificação deve ser direta, ou seja, consultar a posição do índice sem percorrer a estrutura. Isso exige acesso por índice em tempo constante.
- Uma lista indexada (vetor ou array unidimensional) permite exatamente isso: o valor do termo i fica na posição i, e a consulta 'já foi calculado?' é feita diretamente pelo índice, em tempo O(1).
- Por que as outras estão erradas: a pilha encadeada só permite acesso ao topo, não a uma posição arbitrária pelo índice; a variável isolada guarda apenas um valor e não armazena n+1 resultados; a matriz bidimensional é desnecessária, pois o problema tem apenas uma dimensão de índices; a fila encadeada também acessa apenas o início e o fim, sem acesso direto por posição.
- Conclusão: a resposta correta é a alternativa B, que coincide com o gabarito oficial.
💡 Dica: Relacione o acesso direto por índice à estrutura que armazena um valor em cada posição.
Alternativa por alternativa
O aluno pode ter associado a memoização à ideia de empilhar chamadas recursivas, pensando que a pilha é a estrutura natural da recursão. Porém, a pilha só dá acesso ao topo, impedindo a consulta direta a um índice específico.
A lista indexada é a estrutura mais adequada porque os resultados correspondem diretamente aos índices dos termos da sequência. Assim, o programa pode armazenar o resultado do termo i na posição i e consultá-lo diretamente durante a memoização. O enunciado define uma sequência unidimensional de posições conhecidas, tornando desnecessárias estruturas com relações, remoção em ordem ou múltiplas dimensões.
O aluno pode ter imaginado que bastaria uma única variável para guardar o último resultado calculado. Isso ignora que a memoização precisa guardar todos os termos de 0 a n para evitar recálculos.
O aluno pode ter achado que, por haver uma sequência de chamadas, seria necessária uma tabela com duas dimensões. Mas o problema possui apenas um índice (n), dispensando a segunda dimensão.
Por que engana: Confundir estruturas de acesso sequencial, como pilhas e filas, com uma lista indexada, que permite consultar diretamente o resultado pelo índice.
O aluno pode ter confundido a ordem de processamento das chamadas recursivas com o comportamento FIFO da fila. A fila só acessa o início e o fim, não uma posição pelo índice.
Raio-X da questão
Lista indexada e memoização
avaliacao
Acesso por índices · Recursão em algoritmos
Revise estruturas indexadas, acesso por posição e uso de memoização em algoritmos recursivos.
Confundir estruturas de acesso sequencial, como pilhas e filas, com uma lista indexada, que permite consultar diretamente o resultado pelo índice.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Ao projetar um algoritmo recursivo que recalcula repetidamente os mesmos subproblemas, qual técnica baseada em armazenar…
- Analise a função recursiva que calcula o fatorial de um número. Qual é a estrutura de dados mais adequada para armazenar…
- Uma equipe desenvolve uma central meteorológica para regiões remotas. O microcontrolador do equipamento possui apenas 1…
- Ao generalizar um algoritmo recursivo que calcula custo mínimo em uma rede (grafo) para múltiplas instâncias, qual…
- Um programa guarda muitos números, precisa inserir e remover números com frequência e fazer buscas rápidas, sem…
- Em um projeto de programação, a equipe precisa guardar as tarefas a fazer em uma sequência na qual seja possível incluir…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog