Descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, pilha/fila) para um programa que…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Descrever com precisão a solução de um problema, construindo o programa que implementa a solução descrita.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, pilha/fila) para um programa que gerencie dependências entre tarefas de um projeto escolar e produza uma ordem válida de execução; inclua como detectar ciclos.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Representar cada tarefa como um registro (id, nome, duração) e as dependências como arestas dirigidas num grafo G. Para gerar ordem válida: usar ordenação topológica. Opção A (Kahn): calcular grau de entrada de cada nó, enfileirar nós com grau 0, remover e reduzir graus dos vizinhos, enfilear novos grau 0; a fila implementa nós prontos; se número processado < total, existe ciclo. Opção B (DFS): usar DFS recursiva com marcações (não visitado, visitando, visitado); ao completar um nó, empilhá-lo; detectar ciclo ao encontrar nó em estado "visitando" (back-edge). Escolher registros para armazenar metadados, lista de adjacência para grafo, e fila ou pilha conforme o método; ambos têm complexidade O(V+E).
Explicação
A resposta apresenta uma abordagem clara e estruturada para gerenciar dependências entre tarefas, utilizando um grafo para representar as relações entre elas. As duas opções de ordenação topológica propostas (Kahn e DFS) são métodos reconhecidos e eficientes para resolver o problema, além de incluir a detecção de ciclos, que é essencial para garantir a viabilidade da execução das tarefas. A escolha das estruturas de dados, como registros e listas de adjacência, é apropriada para otimizar o armazenamento e a manipulação das informações.
Raio-X da questão
gerenciamento de tarefas
avaliacao
estruturas de dados · algoritmos de ordenação
Revisar conceitos de algoritmos e estruturas de dados, especialmente sobre grafos e detecção de ciclos.
O aluno pode confundir a implementação de um grafo com uma lista encadeada, não reconhecendo a necessidade de representar dependências corretamente.
ciencia_tecnologia
pensamento_critico
cotidiano
Questões parecidas com resolução
- Para organizar dependências entre tarefas de um projeto (cada tarefa pode depender de várias anteriores), qual estrutura…
- Você precisa agendar tarefas com dependências direcionais e detectar se há ciclo antes de executar. Que estrutura de…
- Descreva uma solução computacional colaborativa que modele dependências entre atividades de um projeto interdisciplinar…
- Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos…
- Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
- Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
🔎 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