Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IF-MT 2024

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qg240636
Banca
IF-MT
Órgão
IF-MT
Ano
2024
Nível
Superior
Cargo
Professor do Ensino Básico, Técnico e Tecnológico - Informática
Em relação a algoritmos de grafos, segundo Cormen (2012):I – Se o grafo contém um ciclo, nenhuma ordenação topológica é possível.II – O algoritmo de Kruskal é usado para encontrar a árvore geradora mínima em um grafo.III – O algoritmo de caminhos mínimos de Dijkstra considera que todos os pesos de arestas no grafo de entrada são não negativos.CORMEN, Thomas H. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 2012.Assinale a alternativa CORRETA:
  1. AApenas a afirmação I é correta.
  2. BAs afirmações I e II são corretas.
  3. CApenas a afirmação II é correta.
  4. DAs afirmações II e III são corretas.
  5. EAs afirmações I, II e III são corretas.
Revelar gabarito e comentário

GabaritoE — As afirmações I, II e III são corretas.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Algoritmos de grafos (Cormen)

Gabarito: letra E. As três afirmações estão corretas: ordenação topológica requer grafo acíclico direcionado (DAG); Kruskal é um algoritmo de árvore geradora mínima; Dijkstra funciona apenas com pesos não negativos.

1Ordenação topológica
Requer DAG (acíclico)
Ciclo → impossível
2Árvore geradora mínima
Kruskal
Arestas em ordem crescente
Evita ciclos
3Caminhos mínimos
Dijkstra (fonte única)
Pesos não negativos
Peso negativo → falha
Algoritmos de grafos (Cormen)
LEVELsoulevel.com.br
Algoritmos de grafos (Cormen): Ordenação topológica (Requer DAG (acíclico), Ciclo → impossível); Árvore geradora mínima (Kruskal, Arestas em ordem crescente, Evita ciclos); Caminhos mínimos (Dijkstra (fonte única), Pesos não negativos, Peso negativo → falha)

Item I — ✅ Correto

Ordenação topológica é uma ordem linear dos vértices de um grafo direcionado. Se há um ciclo, não é possível ordenar, pois a relação de precedência seria circular. Logo, a afirmação está correta.

Item II — ✅ Correto

O algoritmo de Kruskal é um dos métodos para encontrar a árvore geradora mínima (MST) em um grafo conexo ponderado. Ele seleciona arestas em ordem crescente de peso, evitando ciclos.

Item III — ✅ Correto

O algoritmo de Dijkstra resolve o problema de caminhos mínimos de fonte única, mas exige que todos os pesos das arestas sejam não negativos (≥0). Caso contrário, a estratégia gulosa pode falhar.

Conclusão: I, II e III são verdadeiros → Gabarito: letra E.

Link permanente: /questoes/qg240636