Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q281: Which vertex color indicates that it is included in the current minimum spanning tree in Prim's algorithm?
- A: White
- B: Black
- C: Gray
- D: Red
View Answer
B
Q282: What is the main purpose of Dijkstra's algorithm?
- A: To find the minimum spanning tree
- B: To compute the shortest paths from a source vertex to all other vertices
- C: To find cycles in a graph
- D: To traverse all vertices
View Answer
B
Q283: Dijkstra's algorithm works on graphs with which type of edge weights?
- A: Negative weights
- B: Positive weights
- C: Any weights
- D: Zero weights
View Answer
B
Q284: What happens to the key value of a vertex in Prim's algorithm when a lighter edge is found?
- A: It remains the same
- B: It is set to 0
- C: It is updated to the new lighter edge weight
- D: It's deleted from the priority queue
View Answer
C
Q285: In Dijkstra's algorithm, what does the process of relaxation involve?
- A: Updating the path weight from source to vertex
- B: Checking for cycles
- C: Removing vertices from the queue
- D: Storing edges in a list
View Answer
A
Q286: In Prim's algorithm, when is a vertex marked as black?
- A: When it is the root vertex
- B: When it is added to the minimum spanning tree
- C: When it is processed
- D: When it is selected as the lightest edge
View Answer
B
Q287: In Dijkstra's algorithm, which data structure is used to efficiently select the vertex with the minimum distance?
- A: Stack
- B: Linked list
- C: Priority queue
- D: Array
View Answer
C
Q288: The complexity of Prim's algorithm is generally considered to be _______.
- A: Θ(V + E)
- B: Θ(E log V)
- C: Θ(V^2)
- D: Θ(E^2)
View Answer
B
Q289: The weight of a path in a graph is the _______ of the constituent edges.
- A: sum
- B: product
- C: difference
- D: average
View Answer
A
Q290: What is the time complexity for extracting a vertex from the priority queue in Dijkstra’s algorithm?
- A: O(1)
- B: O(log V)
- C: O(V)
- D: O(E)
View Answer
B