Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros (com repetições possíveis) e retorne…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Elaborar algoritmos que envolvam instruções sequenciais, de repetição e de seleção usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros (com repetições possíveis) e retorne uma nova lista contendo apenas os elementos distintos na mesma ordem de ocorrência. Use uma estrutura auxiliar para obter complexidade esperada O(n). Explique escolha, pseudocódigo e análise de complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Escolha: usar um conjunto (hash set) como estrutura auxiliar para checagem em tempo esperado O(1). Pseudocódigo: saida <- lista vazia seen <- conjunto vazio para cada x em L faça se x ? seen então append(saida, x) inserir(seen, x) fim se fim para retornar saida Análise: cada elemento é processado uma vez => tempo esperado O(n); operações no conjunto esperadas O(1) cada; espaço extra O(n) para 'seen' e O(k) para 'saida' (k = número de distintos).
Explicação
A escolha de um conjunto como estrutura auxiliar permite a verificação rápida de elementos já vistos, garantindo que apenas os distintos sejam adicionados à lista de saída. O pseudocódigo processa cada elemento da lista original uma única vez, resultando em uma complexidade de tempo linear. A utilização do conjunto para armazenar elementos vistos requer espaço proporcional ao número de distintos, mantendo a eficiência do algoritmo.
Raio-X da questão
algoritmo em pseudocódigo
avaliacao
estruturas de dados · pseudocódigo
Revisar conceitos de estruturas de dados e algoritmos de ordenação.
O aluno pode confundir a lógica de remoção de duplicatas com a simples cópia da lista original, não utilizando a estrutura auxiliar corretamente.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para inscrever estudantes no clube de leitura, a biblioteca da escola usa um formulário digital. O formulário solicita…
- Em uma planilha com várias turmas, uma mesma fórmula foi inserida na primeira linha e copiada para as demais para manter…
- Uma turma quer registrar em ordem as etapas para calcular a média das notas em um programa educacional. — Que recurso de…
- Em uma atividade de programação, o estudante percebe que vai repetir a mesma conta várias vezes para diferentes valores…
- No terminal de empréstimo de bicicletas de um parque urbano, cada devolução é registrada em um painel de leitura. O…
- Em uma frase, defina o que é um algoritmo em computação.
🔎 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