Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
A
Chapter: 8
Q246:
The time complexity of the DFS algorithm is _____.
A. O(V)
B. O(E)
C. O(V + E)
D. None of the above
Correct Answer:
C
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
A
Chapter: 8
Q249:
A directed acyclic graph (DAG) has at least one ______.
A. Cycle
B. Back edge
C. Topological sort
D. None of the above
Correct Answer:
C
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
D
Chapter: 8
Q258:
The running time of the DFS algorithm is given as ______.
A. Θ(V)
B. Θ(E)
C. Θ(V + E)
D. Θ(V * E)
Correct Answer:
C
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
A