Para organizar dependências entre tarefas de um projeto (cada tarefa pode depender de várias anteriores), qual…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para organizar dependências entre tarefas de um projeto (cada tarefa pode depender de várias anteriores), qual estrutura de dados indicada por algoritmos permite detectar ciclos e gerar uma ordem válida de execução? Explique sucintamente.
- A) Representar tarefas como uma árvore binária.
- B) Usar um grafo direcionado; aplicar DFS para detectar ciclos e ordenação topológica.
- C) Usar uma lista encadeada de tarefas na ordem de chegada.
- D) Representar dependências apenas como um conjunto (set) de tarefas.
- E) Modelar execução por uma pilha LIFO de tarefas.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado pede a estrutura que representa dependências entre tarefas, em que cada tarefa pode depender de várias outras, e que permita detectar ciclos e gerar uma ordem válida de execução. Essa situação é modelada por um grafo direcionado: cada tarefa é um vértice e cada dependência é uma aresta orientada da tarefa prerequisito para a tarefa que depende dela.
- Para detectar ciclos, aplica-se a busca em profundidade (DFS). Se durante a DFS for encontrada uma aresta que aponta para um vértice ainda em processamento (na pilha de recursão), existe um ciclo, ou seja, dependências circulares que tornariam o projeto impossível de executar.
- Quando o grafo é acíclico (DAG), a ordenação topológica produz uma sequência em que toda tarefa aparece depois de todas as suas dependências. Essa sequência é a ordem válida de execução. A ordenação topológica pode ser obtida pela DFS, com a ordem inversa do término dos vértices, ou pelo algoritmo de Kahn.
- Por que as outras estão erradas: A) árvore binária não representa bem dependências múltiplas e arbitrárias entre tarefas, pois cada nó tem no máximo dois filhos e não há noção geral de ciclo. C) uma lista encadeada na ordem de chegada ignora as dependências, portanto não garante a ordem correta. D) um conjunto não guarda relações entre tarefas, então não permite detectar ciclos nem ordenar. E) uma pilha LIFO define apenas a ordem de empilhamento e desempilhamento, não modela dependências múltiplas nem detecta ciclos.
- Conclusão: a alternativa correta é a B, que é coerente com o gabarito oficial.
💡 Dica: Identifique a estrutura de dados e suas características.
Alternativa por alternativa
Acredita que a hierarquia de uma árvore binária basta para expressar dependências entre tarefas, sem perceber que cada tarefa pode depender de várias outras e que árvores não representam ciclos nem múltiplos pais.
Por que engana: Confundir a representação de tarefas como uma árvore binária, que não é adequada para representar dependências complexas entre tarefas.
Tarefas são nós e dependências, arestas direcionadas; busca em profundidade detecta ciclos e a ordenação topológica fornece uma sequência válida ou sinaliza impossibilidade.
Supõe que a ordem em que as tarefas chegaram define a ordem de execução, ignorando que as dependências devem ser respeitadas independentemente da sequência de chegada.
Imagina que agrupar tarefas em um conjunto é suficiente para registrar quem depende de quem, sem perceber que um conjunto não guarda relações entre elementos.
Associa execução de tarefas a uma pilha por confundir a ordem de empilhamento com a ordem de dependência, sem perceber que a pilha não representa relações entre tarefas nem detecta ciclos.
Raio-X da questão
estruturas de dados em algoritmos
avaliacao
estruturas de dados · algoritmos de ordenação
Revisar conceitos de grafos e ordenação topológica.
Confundir a representação de tarefas como uma árvore binária, que não é adequada para representar dependências complexas entre tarefas.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, pilha/fila) para um programa que gerencie…
- Você precisa agendar tarefas com dependências direcionais e detectar se há ciclo antes de executar. Que estrutura de…
- Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos…
- Em um projeto de programação, a equipe precisa guardar as tarefas a fazer em uma sequência na qual seja possível incluir…
- Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
- Justifique a escolha da estrutura de dados mais adequada para um projeto de gerenciamento de tarefas.
🔎 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