Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q251: Which of the following is a property of edges in a directed graph during DFS?
- A: Tree edges always point to descendants
- B: All edges are tree edges
- C: There are no cross edges
- D: None of the above
View Answer
A
Q252: In a precedence constraint graph, what do the edges represent?
- A: Tasks that must be completed in order
- B: Relationships between tasks
- C: Completed tasks
- D: None of the above
View Answer
A
Q253: The output of a topological sort on a DAG is a linear ordering of vertices such that for each edge (u, v), ______.
- A: u appears before v
- B: u appears after v
- C: u is unrelated to v
- D: None of the above
View Answer
A
Q254: In the topological sorting algorithm, when is a vertex added to the front of the linked list?
- A: When it is first discovered
- B: When it is marked gray
- C: When it is fully processed and marked black
- D: When it is adjacent to another vertex
View Answer
B
Q255: The order of dressing up in a suit can be represented as a ______.
- A: Graph
- B: Tree
- C: List
- D: None of the above
View Answer
A
Q256: If a directed graph has no back edges, it implies that the graph ______.
- A: Has cycles
- B: Does not have cycles
- C: Has at least one edge
- D: None of the above
View Answer
B
Q257: Which type of edge occurs when there is a directed edge (u, v) where v is a proper descendant of u?
- A: Tree edge
- B: Back edge
- C: Cross edge
- D: Forward edge
View Answer
D
Q258: The running time of the DFS algorithm is given as ______.
- A: Θ(V)
- B: Θ(E)
- C: Θ(V + E)
- D: Θ(V * E)
View Answer
C
Q259: In a graph traversal, if d[u] < d[v] and f[u] > f[v], what can be said about vertices u and v?
- A: u is a descendant of v
- B: v is a descendant of u
- C: u and v are unrelated
- D: None of the above
View Answer
B
Q260: The parenthesis lemma helps to determine ______.
- A: Ancestor-descendant relationships in a DFS tree
- B: The time complexity of a graph algorithm
- C: The classification of edges
- D: None of the above
View Answer
A