Projete um algoritmo em pseudocódigo que mescle duas listas ordenadas (A e B) em uma única lista ordenada…

Questão

Projete um algoritmo em pseudocódigo que mescle duas listas ordenadas (A e B) em uma única lista ordenada crescente. Explique como sua solução manipula variáveis e nós/registros e analise a complexidade temporal e espacial, considerando listas encadeadas e vetores.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Resposta modelo (sintética): 1) Listas encadeadas — reutilizando nós: pa?A.cabeça; pb?B.cabeça; head?null; tail?null while pa?null and pb?null: if pa.valor=pb.valor: node?pa; pa?pa.next else: node?pb; pb?pb.next if head==null: head?node; tail?node else: tail.next?node; tail?node if pa?null: tail.next?pa if pb?null: tail.next?pb Variáveis: pa,pb,head,tail são ponteiros; ajuste de next reaproveita nós. Tempo: O(n+m). Espaço extra: O(1) (apenas ponteiros). 2) Vetores — criando novo vetor C de tamanho n+m: i?0;j?0;k?0 while i<n and j<m: C[k++]? (A[i]=B[j] ? A[i++] : B[j++]) copy restante Variáveis: índices i,j,k; usa-se espaço adicional O(n+m). Tempo: O(n+m).

Explicação

A solução apresentada para listas encadeadas utiliza ponteiros para percorrer e mesclar as listas sem a necessidade de alocar novos nós, garantindo eficiência em espaço. Para vetores, a abordagem cria um novo vetor que armazena os elementos mesclados, utilizando índices para controlar a posição, o que é adequado para listas de tamanho fixo. Ambas as implementações têm complexidade temporal O(n+m), mas diferem em complexidade espacial, sendo O(1) para listas encadeadas e O(n+m) para vetores.

Raio-X da questão

Questões parecidas com resolução

• 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…
• Projete em pseudocódigo uma função recursiva merge_sorted(L1,L2) que recebe duas listas ordenadas não decrescentes de…
• Em um algoritmo que mescla duas listas ordenadas, qual subtarefa — envolvendo variáveis de índice — garante que a ordem…
• Projete um algoritmo em pseudocódigo que recebe dois vetores unidimensionais de registros 'estoqueA' e 'estoqueB' (cada…
• Dadas duas listas ordenadas de números, qual algoritmo e estrutura de dados usar para produzir uma única lista ordenada…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.