Projete em pseudocódigo uma função recursiva merge_sorted(L1,L2) que recebe duas listas ordenadas não…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete em pseudocódigo uma função recursiva merge_sorted(L1,L2) que recebe duas listas ordenadas não decrescentes de inteiros e retorna uma lista ordenada não decrescente contendo todos os elementos; não use estruturas iterativas e preserve a ordem relativa (estabilidade).
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
funcao merge_sorted(L1, L2): se L1 == [] entao retorne L2 se L2 == [] entao retorne L1 se L1[0] <= L2[0] entao retorne concatenar([L1[0]], merge_sorted(L1[1:], L2)) senao retorne concatenar([L2[0]], merge_sorted(L1, L2[1:])) Observações: - A comparação com <= preserva estabilidade (elementos iguais de L1 mantêm-se antes dos de L2). - Complexidade de tempo: O(n+m), onde n e m são os tamanhos de L1 e L2; cada elemento é processado uma vez. - Espaço: O(n+m) para a lista resultante e profundidade de recursão O(n+m) no pior caso.
Explicação
A solução apresentada utiliza recursão para combinar duas listas ordenadas, garantindo que a ordem relativa dos elementos seja preservada ao comparar os primeiros elementos de cada lista. A função retorna a lista resultante de forma eficiente, processando cada elemento uma única vez, o que resulta em uma complexidade de tempo linear. Além disso, a abordagem recursiva permite que a profundidade da pilha de chamadas se mantenha dentro dos limites, evitando iterações que poderiam complicar a implementação.
Raio-X da questão
função recursiva
avaliacao
funções recursivas · listas ordenadas
Revisar conceitos de recursão e manipulação de listas.
O aluno pode confundir a lógica de mesclagem, não mantendo a ordem relativa dos elementos das listas originais.
ciencia_tecnologia
criatividade
abstrato
Questões parecidas com resolução
- Em pseudocódigo, ao implementar um algoritmo recursivo que percorre uma lista L processando exatamente um elemento por…
- Descreva como seria um algoritmo que, utilizando recursão, calcula a soma dos números de 1 a n. Detalhe as etapas e como…
- Explique o conceito de recursão em programação e forneça um exemplo de uma função recursiva para calcular a soma de uma…
- Identifique qual das opções abaixo descreve uma função recursiva em programação.
- Em uma estufa, um programa analisa a umidade de cinco canteiros, na ordem indicada, e aciona a irrigação quando a…
- Na feira cultural da escola, um grupo criou uma lista com as músicas que tocarão no palco: abertura, apresentação de…
Todas as questões de Programação - Programação com listas e recursã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