Quiz-2 on Unit-2
1. Which of the following is not an example of the divide and
conquer approach?
A) Merge Sort
B) Quick Sort
C) Binary Search
D) Prim’s Algorithm
Answer: D) Prim’s Algorithm
2. Which of the following problems cannot be solved using divide
and conquer?
A) Matrix Multiplication
B) Tower of Hanoi
C) Finding the maximum element in an array
D) Shortest path in graphs using Dijkstra’s Algorithm
Answer: D) Shortest path in graphs using Dijkstra’s Algorithm
3. Binary Search algorithm falls under which algorithm design
technique?
A) Greedy
B) Dynamic Programming
C) Divide and Conquer
D) Backtracking
Answer: C) Divide and Conquer
4. What is the key idea behind Divide and Conquer strategy?
A) Use brute force
B) Solve sub-problems and combine results
C) Use heuristic methods
D) Apply dynamic programming
Answer: B) Solve sub-problems and combine results
5. Which of the following recurrence relations represents Merge
Sort?
A) T(n) = 2T(n/2) + O(n)
B) T(n) = T(n-1) + O(1)
C) T(n) = T(n-1) + T(n-2) + O(1)
D) T(n) = T(n/2) + O(1)
Answer: A) T(n) = 2T(n/2) + O(n)
6. In the context of divide and conquer, what does the "conquer"
step typically involve?
A) Breaking down the problem
B) Merging the solutions of sub-problems
C) Finding the base case
D) Selecting the pivot element
Answer: B) Merging the solutions of sub-problems
7. What is the worst-case time complexity of Quick Sort?
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
Answer: B) O(n²)
8. What is the average time complexity of Merge Sort?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n²)
Answer: C) O(n log n)
9. What is the main idea behind brute force algorithms?
A) Use divide and conquer strategy
B) Use dynamic programming
C) Try all possible solutions
D) Use greedy strategy
Answer: C) Try all possible solutions
10. Which of the following problems is typically solved using brute
force?
A) Binary Search
B) Travelling Salesman Problem (TSP)
C) Merge Sort
D) Prim’s Algorithm
Answer: B) Travelling Salesman Problem (TSP)
Brut
11. Brute force algorithm is most suitable when:
A) The input size is very large
B) The problem has no optimal solution
C) The input size is small
D) The problem is recursive
Answer: C) The input size is small
12. Which of the following is true about brute force approach?
A) Always gives the fastest solution
B) Never guarantees a correct result
C) Explores all possible solutions
D) Works only on linear problems
Answer: C) Explores all possible solutions
13. Divide and Conquer works by __________ the problem into
subproblems, solving them recursively, and then combining their
solutions.
Answer: dividing
14. In Quick Sort, the element around which the array is partitioned is
called the __________.
Answer: pivot
15. The time complexity of Merge Sort is __________.
Answer: O(n log n)
16. The base case in Divide and Conquer is typically a subproblem that is
__________ to solve directly.
Answer: small
17. The Divide and Conquer approach uses __________ recursion.
Answer: recursive (or divide-and-conquer)
18. Quick Sort has a worst-case time complexity of __________.
Answer: O(n²)
19. The height of the recursion tree in Merge Sort is __________.
Answer: log n
20. Merge Sort is a stable sorting algorithm, while Quick Sort is __________.
Answer: unstable
21. Matrix multiplication using Strassen’s algorithm is an application of
the __________ strategy.
Answer: Divide and Conquer
22. The performance of Quick Sort greatly depends on the choice of the
__________ element.
Answer: pivot
23. When input size increases, brute force becomes __________.
Answer: inefficient
24. The Travelling Salesman Problem solved by brute force requires
checking all __________ of cities.
Answer:Feasible solutions(permutations)
25.
25. The efficiency of Divide and Conquer algorithms depends on how
evenly the problem is __________.
Answer: divided