Projete um algoritmo e descreva as estruturas de dados para implementar operações de desfazer/refazer…
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 um algoritmo e descreva as estruturas de dados para implementar operações de desfazer/refazer (undo/redo) em um editor de texto simples. Explique como registrar cada operação, aplicar undo e redo e a complexidade envolvida.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Use duas pilhas: undo_stack e redo_stack. Representar cada operação como um delta (tipo da operação, posição, conteúdo afetado) e também seu inverso. Ao executar uma edição: aplicar o delta no texto, empilhar o delta inverso em undo_stack e limpar redo_stack. Para undo: desempilhar inverso de undo_stack, aplicar no texto e empilhar o inverso desse inverso em redo_stack (ou seja, o delta original). Para redo: desempilhar de redo_stack, aplicar e empilhar o inverso em undo_stack. Essa abordagem permite O(k) por operação, onde k é o tamanho do delta (tipicamente O(1) para uma inserção/exclusão de caractere); operações de push/pop em pilha são O(1). Para reduzir memória, armazenar deltas compactos (por exemplo, intervalos e strings) e, se necessário, criar checkpoints periódicos para limitar profundidade histórica.
Explicação
A utilização de duas pilhas permite gerenciar eficientemente as operações de desfazer e refazer, garantindo que cada ação possa ser revertida ou repetida de forma organizada. A representação das operações como deltas facilita a aplicação das mudanças no texto e a recuperação do estado anterior, mantendo a complexidade das operações em níveis aceitáveis. Além disso, a estratégia de armazenamento compacto e a criação de checkpoints ajudam a otimizar o uso de memória e a performance do algoritmo.
Raio-X da questão
algoritmo de desfazer/refazer
avaliacao
estruturas de dados · algoritmos básicos
Revisar conceitos de estruturas de dados e algoritmos de controle de histórico.
O aluno pode confundir as operações de desfazer e refazer, não registrando corretamente as ações realizadas no editor.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para implementar o histórico de desfazer e refazer (undo/redo) em um editor, qual estrutura de dados técnica é mais…
- Projete e descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, hash) para implementar um…
- “Uma fala apagada por engano não pode desaparecer do acervo”, observou a responsável pela digitalização de depoimentos…
- Descreva um projeto de programação que utilize uma estrutura de dados para resolver um problema real. Explique a escolha…
- Descreva como você implementaria um programa que organiza uma lista de tarefas diárias, mencionando as estruturas de…
- Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
🔎 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