Computação1º anoBNCC EF15CO02Difícil⏱ longo

Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e reorganize os nós…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF15CO02

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 um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e reorganize os nós in-place para mover todos os elementos com valor par para o início da lista, preservando a ordem relativa dos pares entre si e dos ímpares entre si (estabilidade). Use variáveis explícitas, não aloque novos nós e indique complexidade temporal e espacial.

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

Resposta esperada

Pseudocódigo: função partition_pares_estavel(head): if head == nulo: retorne head even_head = nulo; even_tail = nulo odd_head = nulo; odd_tail = nulo atual = head enquanto atual != nulo: proximo = atual.proximo atual.proximo = nulo se (atual.valor % 2) == 0: se even_head == nulo: even_head = atual; even_tail = atual senão: even_tail.proximo = atual even_tail = atual senão: se odd_head == nulo: odd_head = atual; odd_tail = atual senão: odd_tail.proximo = atual odd_tail = atual atual = proximo // concatenar listas mantendo estabilidade se even_head != nulo: even_tail.proximo = odd_head retorne even_head senão: retorne odd_head Explicação e justificativa do projeto: - Variáveis usadas: atual, proximo (iteração); even_head/even_tail para sublista de pares; odd_head/odd_tail para sublista de ímpares. - Invariante durante o laço: nós já visitados estão repartidos em duas sublistas (pares e ímpares), cada sublista preservando a ordem original. - Não são alocados novos nós; apenas ajustam-se ponteiros .proximo, logo o algoritmo é in-place no sentido de não criar nós adicionais. - Complexidade temporal: percorre a lista uma vez ? O(n). - Complexidade espacial extra: utiliza um número constante de ponteiros ? O(1) espaço extra. - Casos de borda: lista vazia, todos pares, todos ímpares, único nó; o pseudocódigo trata esses casos naturalmente. Observação: mantém estabilidade porque novos nós são sempre anexados no final das sublistas na ordem em que são visitados.

Explicação

O algoritmo separa os nós em duas sublistas, uma para pares e outra para ímpares, preservando a ordem original de cada grupo ao anexar novos nós ao final das sublistas. Ele opera in-place, ajustando apenas os ponteiros sem criar novos nós, o que garante eficiência em termos de espaço. A complexidade temporal é linear, pois percorre a lista uma vez, e a complexidade espacial é constante, utilizando um número fixo de ponteiros.

Raio-X da questão

Dificuldade Difícil

Bloom Criar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

listas ligadas

📌 Objetivo

avaliacao

🧱 Pré-requisitos

listas ligadas · algoritmos de ordenação

📚 Reveja

Revisar conceitos de listas ligadas e algoritmos de ordenação.

⚠️ Erro mais comum

O aluno pode confundir a reorganização in-place com a criação de uma nova lista, não respeitando a condição de não alocar novos nós.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

abstrato

Questões parecidas com resolução

Todas as questões de Algoritmos

🔎 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