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
- Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e remova todos os nós cujos…
- Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros e retorne uma nova lista em que todos os…
- Projete em pseudocódigo uma função recursiva remover_unicos(L) que recebe uma lista L de inteiros e retorna uma nova…
- Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a lista de…
- Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma…
- Projete em pseudocódigo um algoritmo que receba uma lista de nomes de alunos (dados) e retorne a mesma lista sem…
🔎 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