Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de decomposição e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas aninhadas arbitrariamente e retorna uma nova lista com todos os inteiros na ordem de aparecimento. Especifique caso base, passo recursivo, assinatura e analise complexidade temporal e espacial.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo: flatten(L): result <- [] definir helper(x): se tipo(x) == inteiro então result.append(x) senao para cada y em x faça helper(y) helper(L) retorne result Caso base: item inteiro -> append em result. Passo recursivo: para cada sublista, percorrer chamando helper. Complexidade: tempo O(N) (N = total de elementos inteiros e listas visitadas); espaço: O(N) para o resultado + O(d) para a pilha de chamadas (d = profundidade de aninhamento).
Explicação
A função recursiva proposta utiliza um helper para percorrer a lista e suas sublistas, garantindo que todos os inteiros sejam coletados na ordem em que aparecem. O caso base trata diretamente os inteiros, enquanto o passo recursivo lida com sublistas, permitindo a exploração completa da estrutura aninhada. A análise de complexidade demonstra que o tempo e o espaço utilizados são proporcionais ao número total de elementos, refletindo a eficiência do algoritmo.
Raio-X da questão
função recursiva
avaliacao
funções recursivas · estruturas de dados
Revisar conceitos de recursão e análise de complexidade.
O aluno pode confundir a lógica de recursão, não implementando corretamente o caso base ou o passo recursivo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a lista de…
- Projete em pseudocódigo uma função recursiva profundidade(L) que recebe uma lista L que pode conter elementos e…
- Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior…
- Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma…
- Projete em pseudocódigo um algoritmo recursivo map_recursive(L,f) que recebe uma lista L e uma função f e retorna uma…
- Projete em pseudocódigo um algoritmo recursivo max_recursive(L) que recebe uma lista não vazia L de inteiros e retorna o…
Todas as questões de Estratégias de solução de problemas - Decomposiçã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