Dadas duas listas ordenadas de números, qual algoritmo e estrutura de dados usar para produzir uma única lista…
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
Dadas duas listas ordenadas de números, qual algoritmo e estrutura de dados usar para produzir uma única lista ordenada de forma eficiente (complexidade linear)?
- A) Ordenação por inserção (insertion sort) das listas conjuntas.
- B) Média entre os elementos das duas listas.
- C) Utilizar uma tabela de hash para armazenar os elementos.
- D) Remoção de duplicatas antes da intercalação.
- E) Intercalação (merge) — usar duas listas ou vetores com ponteiros, comparar cabeças e anexar o menor; complexidade O(n+m).
✅ Resposta correta: alternativa E
Resolução passo a passo
- A questão pede um método para juntar duas listas já ordenadas em uma única lista ordenada, com custo linear, ou seja, proporcional ao total de elementos (n+m).
- A ideia central é que as duas listas já estão ordenadas. Basta manter um ponteiro em cada lista, comparar os dois elementos que estão nas 'cabeças' e anexar o menor à lista final, avançando o ponteiro daquela lista. Repetindo isso, cada elemento é visitado uma única vez, o que dá complexidade O(n+m).
- Esse procedimento é exatamente a intercalação (merge), etapa central do merge sort. A alternativa E descreve corretamente o algoritmo, a estrutura (listas ou vetores com ponteiros) e a complexidade.
- Por que as outras estão erradas: A usa insertion sort, que tem custo quadrático no pior caso e não aproveita o fato de as listas já estarem ordenadas; B calcula uma média, o que não produz uma lista ordenada com os mesmos elementos; C usa tabela de hash, que não preserva ordem e exigiria ordenar depois; D remove duplicatas, o que altera o conteúdo da lista e não a ordena.
- Conclusão: a resposta correta é a alternativa E, que coincide com o gabarito oficial.
💡 Dica: Considere a técnica de mesclagem de listas ordenadas.
Alternativa por alternativa
Acredita que a ordenação por inserção é a forma natural de juntar as listas, sem perceber que ela ignora a ordenação prévia e custa O(n^2) no pior caso.
Por que engana: Escolher a ordenação por inserção, acreditando que é a melhor forma de combinar as listas, sem considerar a eficiência da complexidade.
Confunde o problema de combinar listas ordenadas com cálculo de estatística, supondo que a média dos elementos gere uma lista ordenada.
Supõe que a tabela de hash resolve qualquer problema de organização de dados com rapidez, sem considerar que ela não mantém ordem.
Pensa que eliminar repetições é o passo necessário antes de unir as listas, sem perceber que isso não garante a ordenação do resultado.
O algoritmo de merge percorre cada lista uma vez, comparando os elementos atuais e avançando o ponteiro correspondente, evitando reordenação adicional e garantindo tempo linear.
Raio-X da questão
algoritmo de mesclagem
avaliacao
estruturas de dados · algoritmos de ordenação
Revisar algoritmos de ordenação e estruturas de dados.
Escolher a ordenação por inserção, acreditando que é a melhor forma de combinar as listas, sem considerar a eficiência da complexidade.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um algoritmo que mescla duas listas ordenadas, qual subtarefa — envolvendo variáveis de índice — garante que a ordem…
- Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
- Escreva em pseudocódigo um algoritmo que una duas listas ordenadas de números (listaA e listaB) em uma única lista…
- Escreva em pseudocódigo um algoritmo que, dadas duas listas ordenadas de números (listaA e listaB), retorne uma lista…
- Descreva um algoritmo que organize uma lista de números inteiros em ordem crescente. Quais estruturas de dados você…
- Projete um algoritmo em pseudocódigo que mescle duas listas ordenadas (A e B) em uma única lista ordenada crescente…
🔎 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