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 projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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