Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q241: What kind of path is a simple path?
- A: A path that returns to the starting vertex
- B: A path where all vertices are distinct
- C: Any path in the graph
- D: A path with the fewest edges
View Answer
B
Q242: Fill in the blank: In a directed graph, the number of edges coming in is called the ________.
- A: in-degree
- B: out-degree
- C: incident edges
- D: degree
View Answer
A
Q243: What do the numbers d[u] and f[u] represent in the DFS algorithm?
- A: Time stamps for vertex discovery and completion
- B: Time stamps for edge discovery and completion
- C: Colors assigned to vertices
- D: None of the above
View Answer
A
Q244: In the DFS algorithm, when is a vertex marked as "black"?
- A: When it is first discovered
- B: When it is fully processed
- C: When it is not reachable
- D: When it is in the stack
View Answer
B
Q245: In a DFS traversal, if an edge (u, v) is classified as a back edge, what does this imply?
- A: v is an ancestor of u
- B: v is a descendant of u
- C: u and v are unrelated
- D: None of the above
View Answer
A
Q246: The time complexity of the DFS algorithm is _____.
- A: O(V)
- B: O(E)
- C: O(V + E)
- D: None of the above
View Answer
C
Q247: In the context of DFS, what does the term "DFS forest" refer to?
- A: A collection of DFS trees formed during traversal
- B: A single tree from a directed graph
- C: An undirected graph structure
- D: None of the above
View Answer
A
Q248: What happens when a vertex u is visited for the first time in DFS?
- A: It is marked as gray and its discovery time is recorded
- B: It is marked as black and its finish time is recorded
- C: It is immediately removed from the graph
- D: None of the above
View Answer
A
Q249: A directed acyclic graph (DAG) has at least one ______.
- A: Cycle
- B: Back edge
- C: Topological sort
- D: None of the above
View Answer
C
Q250: If a DFS traversal reveals a back edge, what can be inferred about the graph?
- A: The graph contains a cycle
- B: The graph is a tree
- C: The graph is a forest
- D: None of the above
View Answer
A