Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
C
Chapter: 8
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
Correct Answer:
A
Chapter: 8
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
Correct Answer:
B
Chapter: 8
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
Correct Answer:
C
Chapter: 8
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)
Correct Answer:
B
Chapter: 8
Q289:
The weight of a path in a graph is the _______ of the constituent edges.
A. sum
B. product
C. difference
D. average
Correct Answer:
A
Chapter: 8
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)
Correct Answer:
B
Chapter: 8
Q291:
Which type of graph does Dijkstra's algorithm not handle properly?
A. Directed graphs
B. Weighted graphs
C. Graphs with negative edge weights
D. Undirected graphs
Correct Answer:
C
Chapter: 8
Q292:
The algorithm that works by merging two trees together to form a minimum spanning tree is called _______.
A. Prim's algorithm
B. Dijkstra's algorithm
C. Kruskal's algorithm
D. BFS
Correct Answer:
C
Chapter: 8
Q293:
Which step is NOT part of the Prim's algorithm process?
A. Initializing key values
B. Extracting the minimum key vertex
C. Calculating edge weights
D. Updating predecessor pointers
Correct Answer:
C
Chapter: 8
Q294:
In the context of Dijkstra's algorithm, the predecessor pointer is used to _______.
A. Track the path taken
B. Store the shortest edge weight
C. Determine the cycle in a graph
D. Count the number of edges
Correct Answer:
A
Chapter: 9
Q295:
What design paradigms are commonly used in algorithmic problem solving?
A. Divide-and-conquer, greedy, dynamic programming
B. Linear programming, brute force, backtracking
C. Greedy, exhaustive search, divide-and-conquer
D. Dynamic programming, binary search, randomization
Correct Answer:
A
Chapter: 9
Q296:
What happens when an algorithm runs in exponential time?
A. It terminates quickly for large inputs
B. It runs indefinitely for large inputs
C. It has a constant running time
D. It is easy to solve for all inputs
Correct Answer:
B
Chapter: 9
Q297:
A problem that can be solved in polynomial time is considered:
A. Easy
B. Hard
C. Unsolvable
D. NP-complete
Correct Answer:
A
Chapter: 9
Q298:
Decision problems typically have outputs of:
A. Strings
B. Integers
C. Yes/No
D. Arrays
Correct Answer:
C
Chapter: 9
Q299:
Class P contains problems that can be solved in:
A. Exponential time
B. Constant time
C. Polynomial time
D. Logarithmic time
Correct Answer:
C
Chapter: 9
Q300:
Which of the following is a characteristic of NP-complete problems?
A. They are easy to solve
B. They can be solved in polynomial time
C. If one can be solved in polynomial time, all can be
D. They are not solvable
Correct Answer:
C