1. Which of the following is the primary technique used in Dynamic Programming (DP)?

a) Greedy
b) Divide and Conquer
c) Bottom-up approach
d) Depth-First Search
Answer: c) Bottom-up approach

2. What is the main difference between Greedy and Dynamic Programming algorithms?

a) Greedy algorithms solve the problem in stages; DP solves in a single step.

b) DP considers optimal solutions of subproblems, greedy doesn’t.
c) Greedy always results in an optimal solution, DP may not.
d) DP is faster than Greedy algorithms.
Answer: b) DP considers optimal solutions of subproblems, greedy doesn’t.

3. Which of the following problems can be solved using DP?

a) Knapsack Problem
b) Fibonacci Sequence
c) Longest Common Subsequence
d) All of the above
Answer: d) All of the above

4. Which of the following is not a characteristic of Dynamic Programming?

a) Optimal substructure
b) Overlapping subproblems
c) Subproblems are independent
d) Memoization
Answer: c) Subproblems are independent

5. The complexity of solving a problem using DP is determined by:

a) The number of states

b) The number of subproblems
c) The number of iterations needed to solve the problem
d) All of the above
Answer: d) All of the above

6. Which of the following is a typical use case of dynamic programming?

a) Sorting
b) Searching
c) Counting paths in a graph
d) Finding the minimum spanning tree
Answer: c) Counting paths in a graph

7. In the context of Dynamic Programming, the process of storing the result of a

subproblem to avoid recomputation is called:

a) Dividing
b) Memoization
c) Recursion
d) Greedy selection
Answer: b) Memoization

8. Which of the following problems can be solved using the 0/1 Knapsack problem
algorithm?

a) Fibonacci sequence
b) Subset sum problem
c) Longest common subsequence
d) Matrix chain multiplication
Answer: b) Subset sum problem

9. Which of the following is a typical characteristic of a problem suitable for DP?

a) A solution to a problem can be built from solutions to smaller subproblems

b) The problem can be solved by dividing it into two parts
c) The problem involves sequential decision-making
d) The problem does not involve optimization
Answer: a) A solution to a problem can be built from solutions to smaller subproblems

10. Which of the following is the correct recurrence relation for the Fibonacci sequence?

a) F(n) = F(n-1) + F(n-2)

b) F(n) = F(n-1) * F(n-2)
c) F(n) = F(n-1) - F(n-2)
d) F(n) = F(n-1) / F(n-2)
Answer: a) F(n) = F(n-1) + F(n-2)

11. The Time Complexity of the DP approach to solving the Longest Common
Subsequence (LCS) problem is:

a) O(n^2)
b) O(n^3)
c) O(nlogn)
d) O(2^n)
Answer: a) O(n^2)

12. Which technique is used to solve the subset-sum problem efficiently in dynamic
programming?

a) Matrix exponentiation
b) Memoization
c) Iterative dynamic programming
d) Binary search
Answer: c) Iterative dynamic programming

13. In the DP solution of the coin change problem, what is the time complexity if the
number of coins is m and the total amount is n?

a) O(m * n)
b) O(n^2)
c) O(m)
d) O(nlogn)
Answer: a) O(m * n)

14. The number of ways to partition a set into two subsets with equal sum is a variant of
which DP problem?

a) Longest Palindromic Subsequence

b) Knapsack problem
c) Partition problem
d) Longest Increasing Subsequence
Answer: c) Partition problem

15. What is the optimal time complexity for solving the Longest Increasing Subsequence
(LIS) problem using DP?

a) O(nlogn)
b) O(n^2)
c) O(n^3)
d) O(n)
Answer: a) O(nlogn)

16. Which of the following is a property of a tree?

a) It is a connected acyclic graph.

b) It contains no cycles.
c) It has n-1 edges for n nodes.
d) All of the above
Answer: d) All of the above
17. In a directed graph, if there is an edge from vertex u to vertex v, it is represented by:

a) (u, v)
b) [u, v]
c) (v, u)
d) [v, u]
Answer: a) (u, v)

18. What is the space complexity of an adjacency matrix for representing a graph with n
vertices?

a) O(n)
b) O(n^2)
c) O(nlogn)
d) O(2^n)
Answer: b) O(n^2)

19. Which traversal algorithm is used to find the shortest path in an unweighted graph?

a) Depth First Search (DFS)

b) Breadth First Search (BFS)
c) Dijkstra's Algorithm
d) Floyd-Warshall Algorithm
Answer: b) Breadth First Search (BFS)

20. Which of the following algorithms can be used to find the shortest path in a weighted
graph?

a) Kruskal's Algorithm
b) Dijkstra's Algorithm
c) Bellman-Ford Algorithm
d) Both b and c
Answer: d) Both b and c

21. Which of the following is a condition for a graph to contain a cycle?

a) The graph is connected

b) The graph is acyclic
c) The graph contains at least one cycle
d) The graph is undirected
Answer: c) The graph contains at least one cycle

22. The time complexity of Depth First Search (DFS) on a graph with V vertices and E
edges is:
a) O(V + E)
b) O(V^2)
c) O(E)
d) O(V)
Answer: a) O(V + E)

23. Which of the following graph representations is more efficient for sparse graphs?

a) Adjacency Matrix
b) Adjacency List
c) Incidence Matrix
d) Edge List
Answer: b) Adjacency List

24. What does Dijkstra’s algorithm guarantee when used on a weighted graph with
non-negative edge weights?

a) It finds the longest path.

b) It finds the shortest path from the source vertex to all other vertices.
c) It finds the shortest path to a single vertex.
d) It finds a spanning tree.
Answer: b) It finds the shortest path from the source vertex to all other vertices.

25. What is the purpose of Topological Sorting in a Directed Acyclic Graph (DAG)?

a) To find the shortest path

b) To find a cycle in the graph
c) To arrange vertices in a linear order
d) To check whether the graph is connected
Answer: c) To arrange vertices in a linear order

26. What is the space complexity of storing a graph using an adjacency list?

a) O(n)
b) O(V + E)
c) O(n^2)
d) O(V)
Answer: b) O(V + E)

27. Which of the following is true for a strongly connected graph?

a) Every vertex can reach every other vertex.

b) The graph is connected in both directions.
c) There are no disconnected components.
d) Both a and b.
Answer: d) Both a and b
28. Which algorithm is used to find the Minimum Spanning Tree (MST) of a graph?

a) Dijkstra’s Algorithm
b) Kruskal’s Algorithm
c) Floyd-Warshall Algorithm
d) Prim’s Algorithm
Answer: b) Kruskal’s Algorithm

29. What is the time complexity of Kruskal's Algorithm for finding the Minimum Spanning
Tree?

a) O(E log E)
b) O(V^2)
c) O(V log V)
d) O(E + V)
Answer: a) O(E log E)

30. Which of the following is true for a bipartite graph?

a) It contains no cycles.
b) The graph can be colored with two colors.
c) Every vertex is connected to every other vertex.
d) All vertices have an odd degree.
Answer: b) The graph can be colored with two colors.

31. Which of the following is the recurrence relation for the Rod Cutting problem?

a) dp[i] = max(dp[i-1], price[i] + dp[i-k])

b) dp[i] = dp[i-1] + price[i]
c) dp[i] = dp[i-1] - price[i]
d) dp[i] = max(dp[i-1], price[i] - dp[i-k])
Answer: a) dp[i] = max(dp[i-1], price[i] + dp[i-k])

32. The Longest Palindromic Subsequence (LPS) problem can be solved using dynamic
programming. The time complexity of this approach is:

a) O(n)
b) O(n^2)
c) O(nlogn)
d) O(n^3)
Answer: b) O(n^2)

33. Which of the following algorithms is a dynamic programming solution for the "Matrix
Chain Multiplication" problem?
a) Divide and Conquer
b) Memoization
c) Bottom-up DP
d) Brute Force
Answer: c) Bottom-up DP

34. In the 0/1 Knapsack problem, if the weight of an item exceeds the current capacity of
the knapsack, the item:

a) Should not be included

b) Should be included with a reduced capacity
c) Can still be included with no penalty
d) Should be counted twice
Answer: a) Should not be included

35. The Longest Increasing Subsequence (LIS) problem can be solved using dynamic
programming in:

a) O(nlogn)
b) O(n^2)
c) O(n^3)
d) O(n)
Answer: b) O(n^2)

36. The solution to the "Matrix Chain Multiplication" problem involves finding the optimal
parenthesization of the matrix chain. This is done by minimizing:

a) The number of matrix multiplications

b) The number of additions
c) The total matrix dimensions
d) The number of recursive calls
Answer: a) The number of matrix multiplications

37. Which of the following is the best approach to solve the "Longest Common
Subsequence (LCS)" problem?

a) Greedy approach
b) Recursion with memoization
c) Divide and Conquer
d) Dynamic Programming
Answer: d) Dynamic Programming

38. Which of the following is an example of a problem where a bottom-up DP approach is

often used?
a) Fibonacci sequence
b) Longest Increasing Subsequence
c) Longest Palindromic Subsequence
d) All of the above
Answer: d) All of the above

39. The Minimum Edit Distance problem is used to calculate the difference between two
strings. What is the time complexity of solving this using DP?

a) O(n)
b) O(n^2)
c) O(n^3)
d) O(2^n)
Answer: b) O(n^2)

40. Which of the following is the primary advantage of using dynamic programming over
brute force recursion?

a) Faster execution time due to reduced overlap of subproblems

b) Easier implementation
c) More memory consumption
d) Simpler code structure
Answer: a) Faster execution time due to reduced overlap of subproblems

41. In a graph, the shortest path problem can be solved by using:

a) Dijkstra's Algorithm
b) Bellman-Ford Algorithm
c) Floyd-Warshall Algorithm
d) All of the above
Answer: d) All of the above

42. What is the time complexity of performing a Breadth-First Search (BFS) on a graph
with V vertices and E edges?

a) O(V^2)
b) O(E + V)
c) O(V + E)
d) O(E)
Answer: c) O(V + E)

43. What is the space complexity of storing a graph using an adjacency matrix?

a) O(V + E)
b) O(V^2)
c) O(E)
d) O(V)
Answer: b) O(V^2)

44. In a weighted graph, Dijkstra's algorithm cannot be applied if:

a) The graph contains negative weights

b) The graph is not connected
c) The graph contains cycles
d) All of the above
Answer: a) The graph contains negative weights

45. Which of the following statements is true for Prim’s Algorithm?

a) It works only on directed graphs

b) It always finds the shortest path
c) It finds the Minimum Spanning Tree (MST)
d) It does not work on weighted graphs
Answer: c) It finds the Minimum Spanning Tree (MST)

46. In the context of graph traversal, what is a key difference between DFS and BFS?

a) BFS uses a queue, while DFS uses a stack

b) DFS explores the graph level by level, while BFS explores deep into the graph first
c) BFS is more memory-efficient than DFS
d) DFS is faster than BFS
Answer: a) BFS uses a queue, while DFS uses a stack

47. Which of the following algorithms can detect a negative-weight cycle in a graph?

a) Dijkstra's Algorithm
b) Bellman-Ford Algorithm
c) Floyd-Warshall Algorithm
d) Prim’s Algorithm
Answer: b) Bellman-Ford Algorithm

48. Which of the following data structures is used in Kruskal’s Algorithm to find the
Minimum Spanning Tree?

a) Queue
b) Stack
c) Union-Find (Disjoint Set)
d) Priority Queue
Answer: c) Union-Find (Disjoint Set)

49. What is the primary purpose of a topological sort in a directed acyclic graph (DAG)?
a) To find the shortest path
b) To arrange the vertices in a linear order
c) To find a cycle
d) To identify the strongly connected components
Answer: b) To arrange the vertices in a linear order

50. Which of the following is the correct property of a strongly connected graph?

a) Every vertex can reach every other vertex

b) The graph is connected in both directions
c) The graph has no disconnected components
d) Both a and b
Answer: d) Both a and b

51. The Egg Dropping Problem is a well-known problem that can be solved using
dynamic programming. The goal is to minimize the number of drops to find the highest
floor from which an egg can be dropped without breaking. What is the time complexity of
the DP solution?

a) O(n^2)
b) O(n log n)
c) O(n)
d) O(n^3)
Answer: a) O(n^2)

52. In the Coin Change problem, which of the following dynamic programming strategies
is commonly used to solve it optimally?

a) Greedy
b) Bottom-up approach
c) Divide and Conquer
d) Branch and Bound
Answer: b) Bottom-up approach

53. The Longest Common Subsequence (LCS) problem can be solved using dynamic
programming with the time complexity of:

a) O(n^3)
b) O(n^2)
c) O(nlogn)
d) O(n)
Answer: b) O(n^2)

54. Which of the following is the correct recurrence relation for the Longest Common
Subsequence (LCS) problem using dynamic programming?
a) dp[i][j] = dp[i-1][j-1] + 1
b) dp[i][j] = max(dp[i-1][j], dp[i][j-1])
c) dp[i][j] = min(dp[i-1][j], dp[i][j-1])
d) dp[i][j] = dp[i-1][j-1] - 1
Answer: b) dp[i][j] = max(dp[i-1][j], dp[i][j-1])

55. In the Knapsack Problem, which of the following strategies can be used to find the
optimal solution?

a) Brute Force
b) Greedy
c) Dynamic Programming
d) All of the above
Answer: c) Dynamic Programming

56. Which of the following is the space complexity of solving the 0/1 Knapsack problem
using dynamic programming?

a) O(n)
b) O(n * W)
c) O(W)
d) O(n^2)
Answer: b) O(n * W)

57. In the Rod Cutting problem, what is the time complexity of the bottom-up dynamic
programming solution?

a) O(n)
b) O(n^2)
c) O(n log n)
d) O(n^3)
Answer: b) O(n^2)

58. Which of the following is an example of a problem that can be solved using dynamic
programming and involves a decision process with multiple choices at each step?

a) Fibonacci Sequence
b) Longest Common Subsequence
c) 0/1 Knapsack Problem
d) All of the above
Answer: d) All of the above

59. Which of the following is the main advantage of using dynamic programming over
recursion?
a) It requires more space but less time
b) It avoids repeated computation of the same subproblems
c) It requires fewer function calls
d) It solves the problem in fewer steps
Answer: b) It avoids repeated computation of the same subproblems

60. The Maximum Subarray Sum problem can be efficiently solved using dynamic
programming with the time complexity of:

a) O(n^2)
b) O(n)
c) O(logn)
d) O(n log n)
Answer: b) O(n)

61. Which of the following problems is an example of an optimization problem that can be
solved using dynamic programming?

a) Longest Palindromic Subsequence

b) Longest Common Subsequence
c) 0/1 Knapsack
d) All of the above
Answer: d) All of the above

62. Which of the following is the optimal time complexity of solving the Longest Common
Subsequence (LCS) problem using dynamic programming?

a) O(n^3)
b) O(nlogn)
c) O(n^2)
d) O(n)
Answer: c) O(n^2)

63. In the Rod Cutting problem, which of the following is the correct approach to find the
maximum obtainable revenue?

a) Brute Force
b) Greedy
c) Dynamic Programming
d) Backtracking
Answer: c) Dynamic Programming

64. Which of the following is the space complexity of the dynamic programming solution
to the 0/1 Knapsack problem?
a) O(n)
b) O(W)
c) O(n * W)
d) O(n^2)
Answer: c) O(n * W)

65. Which of the following problems can be solved using dynamic programming?

a) Subset Sum Problem

b) Longest Increasing Subsequence
c) Longest Common Subsequence
d) All of the above
Answer: d) All of the above

66. What is the space complexity of the DP solution for the Fibonacci Sequence
problem?

a) O(1)
b) O(n)
c) O(n^2)
d) O(logn)
Answer: a) O(1)

67. In the Matrix Chain Multiplication problem, dynamic programming is used to

determine the optimal order of matrix multiplications by minimizing the:

a) Number of scalar multiplications

b) Number of matrices
c) Number of recursive calls
d) Number of matrix dimensions
Answer: a) Number of scalar multiplications

68. What is the time complexity of solving the Subset Sum problem using dynamic
programming?

a) O(n^2)
b) O(n * W)
c) O(n * logn)
d) O(W)
Answer: b) O(n * W)

69. In the Coin Change problem, the goal is to find the minimum number of coins needed
to make a particular amount. What is the time complexity of solving this problem using
DP?
a) O(n * amount)
b) O(n^2)
c) O(amount)
d) O(n)
Answer: a) O(n * amount)

70. In dynamic programming, if a solution to a problem involves solving many

overlapping subproblems, it is an indication that the problem can be solved efficiently
using:

a) Divide and conquer

b) Greedy algorithms
c) Dynamic programming
d) Brute force
Answer: c) Dynamic programming

71. Which of the following is true about a complete graph with n vertices?

a) It contains no cycles
b) It contains exactly n-1 edges
c) Every pair of distinct vertices is connected by an edge
d) All vertices have an odd degree
Answer: c) Every pair of distinct vertices is connected by an edge

72. Which of the following is the correct time complexity of Dijkstra’s algorithm when
implemented using a priority queue (min-heap)?

a) O(V^2)
b) O(E + VlogV)
c) O(E log V)
d) O(V^2 log V)
Answer: b) O(E + VlogV)

73. Which traversal technique is used to generate a topological sort of a Directed Acyclic
Graph (DAG)?

a) Depth-First Search (DFS)

b) Breadth-First Search (BFS)
c) Dijkstra’s Algorithm
d) Prim’s Algorithm
Answer: a) Depth-First Search (DFS)

74. In an undirected graph, the degree of a vertex is defined as:

a) The number of vertices that are connected to it

b) The number of edges incident on it
c) The number of edges that are not incident on it
d) The number of vertices that are not connected to it
Answer: b) The number of edges incident on it

75. Which of the following is an example of a problem that can be solved by finding the
Minimum Spanning Tree (MST) of a graph?

a) Traveling Salesman Problem

b) Longest Path Problem
c) Network Design Problem
d) All of the above
Answer: c) Network Design Problem

76. Which of the following algorithms is used to find the Minimum Spanning Tree (MST)
of a graph?

a) Dijkstra’s Algorithm
b) Floyd-Warshall Algorithm
c) Kruskal’s Algorithm
d) Bellman-Ford Algorithm
Answer: c) Kruskal’s Algorithm

77. What is the space complexity of storing a graph using an adjacency list
representation?

a) O(V)
b) O(E)
c) O(V + E)
d) O(V^2)
Answer: c) O(V + E)

78. Which of the following is true about a bipartite graph?

a) It contains only even-length cycles

b) It contains only odd-length cycles
c) It contains no cycles
d) It can be colored using only three colors
Answer: a) It contains only even-length cycles

79. The Floyd-Warshall algorithm computes the shortest paths between all pairs of
vertices in a graph. What is its time complexity?

a) O(V^2)
b) O(V^3)
c) O(V * E)
d) O(V log V)
Answer: b) O(V^3)

80. Which of the following is used to check if a graph is bipartite?

a) BFS
b) DFS
c) Dijkstra’s Algorithm
d) Both a and b
Answer: d) Both a and b

81. Which of the following problems can be efficiently solved using a memoized
recursive approach?

a) Fibonacci Sequence
b) 0/1 Knapsack Problem
c) Longest Common Subsequence
d) All of the above
Answer: d) All of the above

82. In dynamic programming, the overlapping subproblems property refers to the fact
that:

a) The problem cannot be broken down into subproblems

b) The subproblems are solved independently
c) The subproblems overlap and are solved multiple times
d) The subproblems are solved in a greedy manner
Answer: c) The subproblems overlap and are solved multiple times

83. Which of the following is an example of a problem where dynamic programming helps
optimize performance by avoiding recomputation?

a) Fibonacci sequence
b) Longest Common Subsequence
c) Matrix Chain Multiplication
d) All of the above
Answer: d) All of the above

84. What is the time complexity of solving the Longest Increasing Subsequence (LIS)
problem using dynamic programming with memoization?

a) O(n^2)
b) O(nlogn)
c) O(n^3)
d) O(n)
Answer: a) O(n^2)
85. The Bellman-Ford algorithm can be used to find the shortest paths in graphs with
negative edge weights, but it cannot handle negative weight cycles. The time complexity
of Bellman-Ford is:

a) O(E + V)
b) O(V^2)
c) O(V * E)
d) O(VlogV)
Answer: c) O(V * E)

86. Which of the following algorithms can solve the All-Pairs Shortest Path problem?

a) Dijkstra’s Algorithm
b) Floyd-Warshall Algorithm
c) Bellman-Ford Algorithm
d) Prim’s Algorithm
Answer: b) Floyd-Warshall Algorithm

87. In dynamic programming, what does the term "state" refer to?

a) A specific subproblem to solve

b) The current value of the subproblem solution
c) The number of recursive calls
d) The final answer of the problem
Answer: b) The current value of the subproblem solution

88. Which of the following is a characteristic of divide and conquer algorithms that
distinguishes them from dynamic programming?

a) Subproblems overlap in divide and conquer

b) Subproblems are independent in divide and conquer
c) Divide and conquer always guarantees optimal solutions
d) None of the above
Answer: b) Subproblems are independent in divide and conquer

89. Which problem is solved using dynamic programming where you need to find the
longest sequence of non-decreasing elements in an array?

a) Longest Increasing Subsequence

b) Longest Decreasing Subsequence
c) Longest Common Subsequence
d) Maximum Subarray Sum
Answer: a) Longest Increasing Subsequence

90. Which of the following is a key feature of dynamic programming?

a) It always works optimally
b) It stores results of subproblems to avoid recomputation
c) It is not applicable to optimization problems
d) It does not involve recursion
Answer: b) It stores results of subproblems to avoid recomputation

91. Which of the following problems is an example of a combinatorial optimization

problem that can be solved using dynamic programming?

a) Coin Change Problem

b) 0/1 Knapsack Problem
c) Matrix Chain Multiplication
d) All of the above
Answer: d) All of the above

92. What is the primary advantage of memoization over the bottom-up approach in
dynamic programming?

a) It requires more memory

b) It computes subproblems in a top-down manner
c) It guarantees an optimal solution
d) It requires fewer function calls
Answer: b) It computes subproblems in a top-down manner

93. In the 0/1 Knapsack Problem, the recursive solution has overlapping subproblems.
Which technique is used to optimize it?

a) Greedy Algorithm
b) Dynamic Programming
c) Divide and Conquer
d) Backtracking
Answer: b) Dynamic Programming

94. Which of the following is the time complexity of solving the Longest Common
Subsequence (LCS) problem using dynamic programming with memoization?

a) O(n)
b) O(n^2)
c) O(n^3)
d) O(logn)
Answer: b) O(n^2)

95. What is the space complexity of the DP solution to the Longest Common
Subsequence (LCS) problem when using a 2D table?
a) O(n)
b) O(n^2)
c) O(nlogn)
d) O(n * m)
Answer: b) O(n^2)

96. In the Rod Cutting problem, which of the following is used to compute the optimal
cut?

a) Greedy approach
b) Dynamic programming
c) Divide and conquer
d) Brute force
Answer: b) Dynamic programming

97. Which of the following is an optimal solution for the Fibonacci Sequence problem
using dynamic programming?

a) Recursive solution
b) Bottom-up DP approach
c) Brute force solution
d) Divide and conquer approach
Answer: b) Bottom-up DP approach

98. In the Subset Sum problem, dynamic programming can be used to find if a subset
with a given sum exists in a set of numbers. The time complexity of the solution is:

a) O(n * sum)
b) O(n^2)
c) O(sum)
d) O(nlogn)
Answer: a) O(n * sum)

99. Which of the following is a key advantage of using dynamic programming over a
recursive solution?

a) It reduces the space complexity significantly

b) It guarantees an optimal solution
c) It requires fewer recursive calls
d) It avoids recomputation by storing the results of subproblems
Answer: d) It avoids recomputation by storing the results of subproblems

100. The Egg Dropping Problem is often solved using dynamic programming. What is the
time complexity of the DP solution when there are k eggs and n floors?
a) O(n^2)
b) O(k * n)
c) O(k * logn)
d) O(k * n^2)
Answer: b) O(k * n)

101. Which of the following algorithms can be used to find the shortest path in a graph
with negative weights (but no negative weight cycles)?

a) Dijkstra’s Algorithm
b) Floyd-Warshall Algorithm
c) Bellman-Ford Algorithm
d) A* Algorithm
Answer: c) Bellman-Ford Algorithm

102. In Kruskal’s Algorithm for Minimum Spanning Tree (MST), which data structure is
used to detect cycles?

a) Stack
b) Queue
c) Union-Find (Disjoint Set)
d) Priority Queue
Answer: c) Union-Find (Disjoint Set)

103. What is the time complexity of Dijkstra's Algorithm using a binary heap for finding
the shortest path?

a) O(V^2)
b) O(E + VlogV)
c) O(VlogV)
d) O(VlogV + E)
Answer: b) O(E + VlogV)

104. In the Prim’s Algorithm for finding Minimum Spanning Tree (MST), which data
structure is used to efficiently select the minimum weight edge?

a) Queue
b) Stack
c) Priority Queue
d) Array
Answer: c) Priority Queue

105. Which of the following is true for Eulerian Circuit in an undirected graph?

a) All vertices must have an even degree

b) All vertices must have an odd degree
c) There must be exactly one vertex with an even degree
d) All edges must be directed
Answer: a) All vertices must have an even degree

106. Which of the following algorithms is used to solve the Maximum Flow problem in a
flow network?

a) Bellman-Ford Algorithm
b) Ford-Fulkerson Algorithm
c) Dijkstra’s Algorithm
d) Kruskal’s Algorithm
Answer: b) Ford-Fulkerson Algorithm

107. What is the time complexity of Breadth-First Search (BFS) on a graph with V vertices
and E edges?

a) O(V^2)
b) O(E + V)
c) O(V log V)
d) O(E)
Answer: b) O(E + V)

108. Which of the following is true for a bipartite graph?

a) It has an even number of edges

b) It can be colored with two colors
c) It has no cycles
d) It has a Hamiltonian cycle
Answer: b) It can be colored with two colors

109. Which of the following is used to represent the adjacency matrix of a graph?

a) A 2D array where A[i][j] = 1 if there is an edge between vertex i and vertex j

b) A linked list for each vertex
c) A stack
d) A priority queue
Answer: a) A 2D array where A[i][j] = 1 if there is an edge between vertex i and
vertex j

110. Which of the following is the correct approach for detecting a cycle in an undirected
graph?

a) Use Depth-First Search (DFS)

b) Use Breadth-First Search (BFS)
c) Use Dijkstra’s Algorithm
d) Use Kruskal’s Algorithm
Answer: a) Use Depth-First Search (DFS)

111. Which of the following problems can be solved using dynamic programming?

a) Longest Common Subsequence (LCS)

b) Matrix Chain Multiplication
c) Edit Distance Problem
d) All of the above
Answer: d) All of the above

112. In the Knapsack problem, the recurrence relation to solve it using dynamic
programming is:

a) dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)

b) dp[i][w] = dp[i-1][w] + wi
c) dp[i][w] = min(dp[i-1][w], dp[i-1][w+wi] - vi)
d) dp[i][w] = dp[i-1][w]
Answer: a) dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)

113. Which of the following problems is solved using dynamic programming with
overlapping subproblems and optimal substructure properties?

a) Longest Increasing Subsequence

b) Fibonacci Sequence
c) 0/1 Knapsack
d) All of the above
Answer: d) All of the above

114. The Bellman-Ford Algorithm can be used to detect negative weight cycles in a
graph. What is the time complexity of Bellman-Ford Algorithm?

a) O(V^2)
b) O(V + E)
c) O(V * E)
d) O(E^2)
Answer: c) O(V * E)

115. In the Coin Change Problem, the goal is to find the minimum number of coins
required to make a given amount. What is the time complexity of the DP solution?

a) O(amount * n)
b) O(amount^2)
c) O(n)
d) O(amount)
Answer: a) O(amount * n)

116. Which of the following is a valid optimization strategy in dynamic programming?

a) Divide the problem into smaller subproblems and solve them independently
b) Store results of already solved subproblems to avoid recomputation
c) Solve subproblems in a bottom-up manner
d) All of the above
Answer: d) All of the above

117. In dynamic programming, tabulation refers to which of the following approaches?

a) Using a recursive approach with memoization

b) Using a bottom-up approach to fill a table iteratively
c) Using brute force to solve subproblems
d) Using greedy approaches to solve subproblems
Answer: b) Using a bottom-up approach to fill a table iteratively

118. Which of the following problems can be solved using dynamic programming with
overlapping subproblems and optimal substructure?

a) Matrix Chain Multiplication

b) Longest Increasing Subsequence
c) Fibonacci Sequence
d) All of the above
Answer: d) All of the above

119. In the Matrix Chain Multiplication problem, the optimal parenthesization is

determined by minimizing the:

a) Number of matrix multiplications

b) Number of matrices
c) Number of recursive calls
d) Total dimensions of matrices
Answer: a) Number of matrix multiplications

120. What is the time complexity of solving the Longest Palindromic Subsequence
problem using dynamic programming?

a) O(n^2)
b) O(n^3)
c) O(nlogn)
d) O(n)
Answer: a) O(n^2)
121. In the Longest Common Subsequence (LCS) problem, what is the recurrence
relation used to compute the solution?

a) dp[i][j] = max(dp[i-1][j], dp[i][j-1])

b) dp[i][j] = dp[i-1][j-1] + 1
c) dp[i][j] = dp[i-1][j] + dp[i][j-1]
d) dp[i][j] = min(dp[i-1][j], dp[i][j-1])
Answer: a) dp[i][j] = max(dp[i-1][j], dp[i][j-1])

122. Which of the following is true for the Fibonacci Sequence when solved using
dynamic programming (memoization)?

a) The time complexity is O(n)

b) The time complexity is O(n^2)
c) The space complexity is O(1)
d) The space complexity is O(n^2)
Answer: a) The time complexity is O(n)

123. The Edit Distance problem involves finding the minimum number of operations
required to convert one string into another. What is the time complexity of the dynamic
programming solution?

a) O(m * n)
b) O(n)
c) O(m + n)
d) O(m^2 + n^2)
Answer: a) O(m * n)

124. Which of the following is true about the Unbounded Knapsack problem?

a) Items can only be chosen once

b) There is an upper bound on the number of items that can be chosen
c) Items can be chosen multiple times
d) It cannot be solved using dynamic programming
Answer: c) Items can be chosen multiple times

125. In the Rod Cutting problem, the value of dp[i] represents:

a) The maximum profit from cutting a rod of length i

b) The total length of the rod
c) The number of pieces in the rod
d) The maximum number of rods of length i
Answer: a) The maximum profit from cutting a rod of length i
126. In dynamic programming, bottom-up and top-down refer to the following
approaches:

a) Bottom-up refers to solving the problem from the base case up to the final solution, while
top-down solves it recursively.
b) Top-down is more efficient than bottom-up.
c) Both approaches are used only in greedy algorithms.
d) Bottom-up refers to solving subproblems recursively.
Answer: a) Bottom-up refers to solving the problem from the base case up to the final
solution, while top-down solves it recursively.

127. In the Fibonacci Sequence problem, the bottom-up approach reduces the time
complexity by avoiding:

a) Overlapping subproblems
b) Recursive calls
c) Storing intermediate results
d) None of the above
Answer: a) Overlapping subproblems

128. Which of the following is a property of a connected graph?

a) There is a path between every pair of vertices

b) It has exactly one edge
c) It contains no cycles
d) It is a tree
Answer: a) There is a path between every pair of vertices

129. Which of the following algorithms can be used to find the shortest path from a
source to all other vertices in a weighted graph with non-negative weights?

a) Bellman-Ford
b) Dijkstra
c) Floyd-Warshall
d) Prim's Algorithm
Answer: b) Dijkstra

130. Which of the following is the correct approach to find the strongly connected
components (SCCs) in a directed graph?

a) Dijkstra’s Algorithm
b) Kosaraju’s Algorithm
c) Bellman-Ford Algorithm
d) Kruskal’s Algorithm
Answer: b) Kosaraju’s Algorithm
131. Which of the following is true for a tree data structure?

a) It is a connected acyclic graph

b) It contains cycles
c) It can have multiple edges between nodes
d) It is always directed
Answer: a) It is a connected acyclic graph

132. What is the time complexity of Breadth-First Search (BFS) in a graph with V vertices
and E edges?

a) O(V^2)
b) O(E + V)
c) O(E log V)
d) O(V log V)
Answer: b) O(E + V)

133. In a directed acyclic graph (DAG), which algorithm can be used to find the
topological sort?

a) Depth-First Search (DFS)

b) Breadth-First Search (BFS)
c) Dijkstra’s Algorithm
d) Prim’s Algorithm
Answer: a) Depth-First Search (DFS)

134. Which of the following is the main difference between Dijkstra's Algorithm and the
Bellman-Ford Algorithm?

a) Dijkstra’s algorithm works only for graphs with positive weights, while Bellman-Ford works
with negative weights
b) Bellman-Ford can only handle graphs with negative weights
c) Dijkstra’s algorithm is used to find the shortest path from a single source to all other vertices,
whereas Bellman-Ford works for all pairs of vertices
d) None of the above
Answer: a) Dijkstra’s algorithm works only for graphs with positive weights, while
Bellman-Ford works with negative weights

135. Which of the following is true for Kruskal’s Algorithm for finding the Minimum
Spanning Tree (MST)?

a) It always starts with the heaviest edge

b) It uses a greedy approach to select edges in increasing weight
c) It guarantees a spanning tree for disconnected graphs
d) It requires that the graph is directed
Answer: b) It uses a greedy approach to select edges in increasing weight

136. Which of the following is used to check for negative weight cycles in a graph?

a) Dijkstra’s Algorithm
b) Bellman-Ford Algorithm
c) Floyd-Warshall Algorithm
d) Prim’s Algorithm
Answer: b) Bellman-Ford Algorithm

137. What is the time complexity of Kruskal's Algorithm for finding the Minimum
Spanning Tree (MST)?

a) O(E log V)
b) O(V^2)
c) O(V log V + E log E)
d) O(V + E)
Answer: a) O(E log V)

138. Which of the following is a key characteristic of a complete graph?

a) It has exactly one edge between every pair of vertices

b) It contains no cycles
c) It has multiple edges between vertices
d) It is directed
Answer: a) It has exactly one edge between every pair of vertices

139. In a graph with V vertices and E edges, what is the maximum number of edges in a
simple undirected graph?

a) V * (V - 1)
b) V * (V - 1) / 2
c) V * E
d) E * (V - 1)
Answer: b) V * (V - 1) / 2

140. Which of the following is used to find the minimum spanning tree (MST) in a
connected weighted graph?

a) Prim’s Algorithm
b) Dijkstra’s Algorithm
c) Floyd-Warshall Algorithm
d) Bellman-Ford Algorithm
Answer: a) Prim’s Algorithm
141. Which of the following is true about the Longest Common Subsequence (LCS)
problem?

a) LCS is the longest subsequence common to both strings

b) LCS must include all characters from both strings
c) LCS is a substring, not a subsequence
d) The LCS is always unique
Answer: a) LCS is the longest subsequence common to both strings

142. The Knapsack problem can be solved using dynamic programming. Which of the
following is the recurrence relation for the 0/1 Knapsack problem?

a) dp[i][w] = dp[i-1][w]
b) dp[i][w] = dp[i-1][w - wt[i]] + val[i]
c) dp[i][w] = max(dp[i-1][w], dp[i-1][w+wt[i]] + val[i])
d) dp[i][w] = min(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
Answer: b) dp[i][w] = dp[i-1][w - wt[i]] + val[i]

143. Which technique is used to avoid recalculating the results of overlapping

subproblems in dynamic programming?

a) Recursion
b) Memoization
c) Divide and Conquer
d) Greedy Approach
Answer: b) Memoization

144. In the Fibonacci Sequence problem, how can you reduce the time complexity to
O(n)?

a) By using recursion
b) By using dynamic programming with memoization
c) By using a greedy algorithm
d) By brute-force iteration
Answer: b) By using dynamic programming with memoization

145. What is the space complexity of the Knapsack problem solution when using
dynamic programming with a 2D table?

a) O(1)
b) O(n)
c) O(w)
d) O(n * w)
Answer: d) O(n * w)
146. In the Longest Increasing Subsequence (LIS) problem, the dynamic programming
solution has a time complexity of:

a) O(n)
b) O(nlogn)
c) O(n^2)
d) O(n^3)
Answer: c) O(n^2)

147. Which of the following statements is true about the Coin Change Problem?

a) The problem can be solved using greedy algorithms

b) It is a combinatorial optimization problem
c) The solution does not require dynamic programming
d) It does not have overlapping subproblems
Answer: b) It is a combinatorial optimization problem

148. Which of the following problems can be solved using dynamic programming with a
bottom-up approach?

a) Matrix Chain Multiplication

b) 0/1 Knapsack
c) Longest Common Subsequence (LCS)
d) All of the above
Answer: d) All of the above

149. In the Rod Cutting Problem, what is the goal of the dynamic programming solution?

a) To find the minimum cost to cut the rod

b) To find the maximum profit by cutting the rod into smaller pieces
c) To calculate the total number of possible cuts
d) To decide which pieces can be sold
Answer: b) To find the maximum profit by cutting the rod into smaller pieces

150. In dynamic programming, when solving an optimization problem, what does the term
optimal substructure mean?

a) The problem can be broken into smaller problems, but their solutions are not optimal
b) The problem's optimal solution depends on the optimal solutions of its subproblems
c) The subproblems have no dependencies
d) The optimal solution is found by brute-force
Answer: b) The problem's optimal solution depends on the optimal solutions of its
subproblems

151. What is the time complexity of Depth-First Search (DFS) on a graph with V vertices
and E edges?
a) O(V^2)
b) O(V + E)
c) O(E log V)
d) O(V log V)
Answer: b) O(V + E)

152. Which of the following is true for a bipartite graph?

a) It can be colored with at least three colors

b) It contains at least one cycle
c) It can be colored using two colors
d) It is always a tree
Answer: c) It can be colored using two colors

153. Which of the following is a necessary condition for the existence of an Eulerian
Circuit in an undirected graph?

a) The graph must be connected

b) Every vertex must have an even degree
c) The graph must contain no cycles
d) All edges must be directed
Answer: b) Every vertex must have an even degree

154. Which of the following algorithms is used to solve the All-Pairs Shortest Path
(APSP) problem?

a) Dijkstra’s Algorithm
b) Floyd-Warshall Algorithm
c) Bellman-Ford Algorithm
d) Prim’s Algorithm
Answer: b) Floyd-Warshall Algorithm

155. Which of the following algorithms is typically used to find the shortest path in a
graph with non-negative edge weights?

a) Bellman-Ford Algorithm
b) Dijkstra’s Algorithm
c) Floyd-Warshall Algorithm
d) Kruskal’s Algorithm
Answer: b) Dijkstra’s Algorithm

156. Which of the following algorithms can be used to find a Maximum Matching in a
Bipartite Graph?

a) Bellman-Ford Algorithm
b) Ford-Fulkerson Algorithm
c) Hopcroft-Karp Algorithm
d) Dijkstra’s Algorithm
Answer: c) Hopcroft-Karp Algorithm

157. In a directed graph, a strongly connected component (SCC) is a subgraph in which:

a) There is a path from every vertex to every other vertex within the subgraph
b) All vertices have an even degree
c) All vertices have a degree of 1
d) The graph contains no cycles
Answer: a) There is a path from every vertex to every other vertex within the subgraph

158. Which of the following algorithms is used to solve the Minimum Spanning Tree
(MST) problem for a graph with weighted edges?

a) Kruskal’s Algorithm
b) Floyd-Warshall Algorithm
c) Bellman-Ford Algorithm
d) Dijkstra’s Algorithm
Answer: a) Kruskal’s Algorithm

159. Which of the following graph traversal methods is used to find a cycle in an
undirected graph?

a) Depth-First Search (DFS)

b) Breadth-First Search (BFS)
c) Dijkstra’s Algorithm
d) Kruskal’s Algorithm
Answer: a) Depth-First Search (DFS)

160. Which of the following is the time complexity of the Floyd-Warshall Algorithm for
finding shortest paths between all pairs of vertices?

a) O(V^2)
b) O(V^3)
c) O(E log V)
d) O(V + E)
Answer: b) O(V^3)

161. In Prim’s Algorithm, what is the initial step when constructing the Minimum
Spanning Tree (MST)?

a) Choose an arbitrary vertex and mark it as part of the MST

b) Start with the heaviest edge
c) Pick the smallest weight edge and connect all vertices to it
d) None of the above
Answer: a) Choose an arbitrary vertex and mark it as part of the MST

162. Which of the following is used to represent the adjacency list of a graph?

a) A matrix where A[i][j] = 1 if there is an edge between vertex i and vertex j

b) A list of lists, where each list contains the neighbors of a vertex
c) A queue
d) A stack
Answer: b) A list of lists, where each list contains the neighbors of a vertex

163. Which of the following is a greedy algorithm used to solve the Interval Scheduling
problem?

a) Huffman Coding
b) Prim’s Algorithm
c) Dijkstra’s Algorithm
d) Activity Selection Algorithm
Answer: d) Activity Selection Algorithm

164. In a directed graph, an Eulerian Path exists if:

a) All vertices have an even degree

b) At most one vertex has an odd degree
c) Every vertex must have exactly one incoming edge
d) The graph must be a tree
Answer: b) At most one vertex has an odd degree

165. What is the space complexity of storing an adjacency matrix for a graph with V
vertices?

a) O(V)
b) O(E)
c) O(V^2)
d) O(V + E)
Answer: c) O(V^2)

166. Which of the following statements is true for the Subset Sum Problem?

a) It can be solved with a greedy approach

b) It can be solved using dynamic programming
c) It cannot be solved optimally
d) It is only solvable using brute force
Answer: b) It can be solved using dynamic programming
167. Which of the following is the time complexity of the Knapsack problem (0/1) using
dynamic programming?

a) O(n^2)
b) O(n * W)
c) O(W)
d) O(n * log W)
Answer: b) O(n * W)

168. What is the goal of the Longest Common Substring (LCS) problem in dynamic
programming?

a) Find the longest sequence that is common to both strings

b) Find the longest sequence that appears in the same order in both strings
c) Find the longest substring in a single string
d) None of the above
Answer: a) Find the longest sequence that is common to both strings

169. In dynamic programming, the space optimization technique is used to:

a) Reduce the overall time complexity of the algorithm

b) Use less memory by storing only the previous state of a DP array
c) Make the algorithm easier to understand
d) Eliminate the need for recursion
Answer: b) Use less memory by storing only the previous state of a DP array

170. The Matrix Chain Multiplication problem is an example of a problem that can be
solved by dynamic programming using:

a) Greedy Approach
b) Brute Force
c) Bottom-Up Approach
d) Divide and Conquer
Answer: c) Bottom-Up Approach

171. What is the space complexity of the dynamic programming solution for the 0/1
Knapsack problem using a 2D array?

a) O(W)
b) O(n)
c) O(n * W)
d) O(n^2)
Answer: c) O(n * W)

172. Which of the following statements is true for the Longest Palindromic Subsequence
problem?
a) It is solved using a greedy algorithm
b) It involves dynamic programming to store solutions to subproblems
c) It requires recursive backtracking to find the subsequence
d) It is only solved using brute force
Answer: b) It involves dynamic programming to store solutions to subproblems

173. What is the time complexity of the dynamic programming solution for the 0/1
Knapsack problem with n items and capacity W?

a) O(n * W)
b) O(n^2)
c) O(W)
d) O(n log W)
Answer: a) O(n * W)

174. Which of the following problems is an example of optimal substructure in dynamic

programming?

a) Longest Common Subsequence

b) Longest Increasing Subsequence
c) 0/1 Knapsack
d) All of the above
Answer: d) All of the above

175. In Depth-First Search (DFS), which data structure is used to store the nodes that are
yet to be explored?

a) Queue
b) Stack
c) Priority Queue
d) Linked List
Answer: b) Stack

176. Which of the following is true for a tree data structure?

a) It is always a connected, acyclic graph

b) It must have exactly one root
c) It can have cycles
d) It always has exactly one edge between any two vertices
Answer: a) It is always a connected, acyclic graph

177. Which of the following is used to represent a directed graph?

a) Adjacency Matrix
b) Adjacency List
c) Both a and b
d) Neither a nor b
Answer: c) Both a and b

178. Which of the following algorithms can be used to find the connected components in
an undirected graph?

a) Breadth-First Search (BFS)

b) Depth-First Search (DFS)
c) Union-Find Algorithm
d) All of the above
Answer: d) All of the above

179. In Dijkstra’s Algorithm, which data structure is used to store the vertices for the
shortest path?

a) Queue
b) Stack
c) Priority Queue
d) Linked List
Answer: c) Priority Queue

180. In Kruskal's Algorithm for Minimum Spanning Tree (MST), what does the Union-Find
data structure do?

a) It finds the shortest path between two vertices

b) It ensures no cycles are formed in the MST
c) It helps find the maximum spanning tree
d) It sorts the edges by weight
Answer: b) It ensures no cycles are formed in the MST

181. Which of the following algorithms is used to find the Shortest Path between all pairs
of vertices in a graph?

a) Dijkstra’s Algorithm
b) Bellman-Ford Algorithm
c) Floyd-Warshall Algorithm
d) Prim’s Algorithm
Answer: c) Floyd-Warshall Algorithm

182. Which of the following is true for Prim’s Algorithm for finding Minimum Spanning
Tree (MST)?

a) It starts with an arbitrary node and expands to adjacent nodes with the smallest weights
b) It always finds the largest weight edge
c) It needs to process each edge only once
d) It uses breadth-first search to explore the graph
Answer: a) It starts with an arbitrary node and expands to adjacent nodes with the
smallest weights

183. Which algorithm can be used to find the strongly connected components (SCC) in a
directed graph?

a) Dijkstra’s Algorithm
b) Kosaraju’s Algorithm
c) Floyd-Warshall Algorithm
d) Kruskal’s Algorithm
Answer: b) Kosaraju’s Algorithm

184. In a weighted directed graph, which algorithm would you use to find the shortest
path from a single source to all other vertices?

a) Bellman-Ford Algorithm
b) Dijkstra’s Algorithm
c) Floyd-Warshall Algorithm
d) Prim’s Algorithm
Answer: b) Dijkstra’s Algorithm

185. Which of the following is a necessary condition for a graph to contain an Eulerian
Path?

a) The graph must be connected

b) At most two vertices can have an odd degree
c) All vertices must have an even degree
d) Both a and b
Answer: d) Both a and b

186. What is the time complexity of the Dijkstra’s Algorithm when implemented using a
binary heap?

a) O(V^2)
b) O(E + V log V)
c) O(V log V)
d) O(V log E)
Answer: b) O(E + V log V)

187. Which of the following is used to check if a graph contains a cycle?

a) Depth-First Search (DFS)

b) Breadth-First Search (BFS)
c) Kruskal’s Algorithm
d) Dijkstra’s Algorithm
Answer: a) Depth-First Search (DFS)
188. In a directed graph, a topological sort of vertices exists if and only if the graph is:

a) A directed acyclic graph (DAG)

b) A complete graph
c) A bipartite graph
d) A tree
Answer: a) A directed acyclic graph (DAG)

189. Which of the following is a minimum spanning tree (MST) algorithm that works by
adding edges in increasing order of weight?

a) Bellman-Ford Algorithm
b) Prim’s Algorithm
c) Kruskal’s Algorithm
d) Dijkstra’s Algorithm
Answer: c) Kruskal’s Algorithm

190. Which of the following is a correct representation of an edge in an adjacency list?

a) A list where each node stores all its neighbors

b) A matrix where rows and columns represent nodes
c) A single list of all edges
d) A graph with only a single node
Answer: a) A list where each node stores all its neighbors