Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q261: A fill-in-the-blank for the DFS algorithm states: When we first discover a vertex, we store a counter in ______.
- A: d[u]
- B: f[u]
- C: color[u]
- D: none of the above
View Answer
A
Q262: The time stamp "2/5" indicates that a vertex was discovered at time ______ and finished processing at time ______.
- A: 2 and 5
- B: 5 and 2
- C: 1 and 10
- D: None of the above
View Answer
A
Q263: In the precedence constraint graph for CS courses, what does an edge from C2 to C4 represent?
- A: Course C2 must be taken before C4
- B: Course C4 must be taken before C2
- C: Courses are unrelated
- D: None of the above
View Answer
A
Q264: For undirected graphs, edges are typically classified as ______.
- A: Tree edges only
- B: Back edges only
- C: Forward edges only
- D: Back edges (by convention)
View Answer
D
Q265: What is a digraph?
- A: An undirected graph
- B: A directed graph
- C: A weighted graph
- D: A cyclic graph
View Answer
B
Q266: A digraph is strongly connected if ______.
- A: Every vertex can reach every other vertex
- B: At least one vertex can reach another vertex
- C: There are no isolated vertices
- D: All vertices have the same degree
View Answer
A
Q267: The strongly connected components of a digraph can be found using which algorithm?
- A: Depth-First Search
- B: Prim's Algorithm
- C: Kruskal's Algorithm
- D: None of the above
View Answer
A
Q268: In a strongly connected digraph, every vertex must appear in ______.
- A: The same DFS tree
- B: A different DFS tree
- C: Any tree structure
- D: Only one tree
View Answer
A
Q269: When merging vertices in a strong component, the resulting graph is called ______.
- A: Component digraph
- B: Directed acyclic graph
- C: Equivalence graph
- D: Adjacency list
View Answer
A
Q270: The maximum finish times of components in a digraph are related to ______.
- A: The component DAG
- B: Graph colorings
- C: Spanning trees
- D: Cycle detection
View Answer
A