GATE CSE Graph Algorithms & P/NP Completeness – Algorithms Practice Test

GATE CSE Graph Algorithms & P/NP Completeness – Algorithms Practice Test | Set 1

Questions 76-80 of 100

0% completed (0/100 answered)

Question 76

MSQ · Multiple Correct 2 mark

Which statements about DFS on a directed graph are CORRECT?

A DFS can be used as part of topological sorting. B A back edge implies a directed cycle. C Every cross edge is necessarily a back edge. D A DFS can be used to compute finishing times.

Question 77

MSQ · Multiple Correct 2 mark

Which statements about bridges and articulation points are CORRECT for an undirected graph?

A Every edge incident to an articulation vertex is a bridge. B They can both be found using DFS low-link information in O(V+E). C A bridge is an edge whose removal increases the number of connected components. D An articulation vertex is a vertex whose removal increases the number of connected components.

Question 78

MSQ · Multiple Correct 2 mark

Which statements about shortest paths are CORRECT?

A Dijkstra is correct when all edge weights are nonnegative. B Bellman-Ford can detect a reachable negative-weight cycle. C Floyd-Warshall is a single-source algorithm. D DAG shortest paths can be solved in linear time in the graph size.

Question 79

MSQ · Multiple Correct 2 mark

Which statements about MSTs are CORRECT?

A MST algorithms require all weights to be positive. B If all edge weights are distinct, the MST is unique. C A strictly heaviest edge on a cycle belongs to no MST. D A lightest edge crossing a cut belongs to some MST.

Question 80

MSQ · Multiple Correct 2 mark

Which statements about Kruskal and Prim are CORRECT?

A Prim grows one tree from a chosen start vertex. B Kruskal naturally uses DSU. C Kruskal processes edges globally in nondecreasing weight order. D Prim requires edge weights to be nonnegative.