Page 138 - Data Structures Handout_Neat

10.9 Exercise

Essay Questions

1. Define sorting and explain its importance in computer science.
2. Compare Bubble Sort, Selection Sort, and Insertion Sort in terms of efficiency and

use cases.

3. Explain how Merge Sort uses the divide and conquer strategy.

4. What is the worst-case scenario for Quick Sort, and how can it be avoided?

5. Implement Bubble Sort and Quick Sort in C++ and compare their performance.
6. Discuss the difference between comparison-based and non-comparison-based

sorting algorithms (e.g., Merge Sort vs. Counting Sort).

7. Explain the importance of stability in sorting algorithms with examples.
Multiple Choice Questions (MCQ)

Q1. What is the time complexity of Bubble Sort in the worst case?

a) ( ) b) ( ⁡ ) c) ( ) d) ( ⁡ )
Q2. Which sorting algorithm is most efficient for nearly sorted arrays?

a) Bubble Sort b) Selection Sort
c) Insertion Sort d) Quick Sort

Q3. Merge Sort is based on which strategy?

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

Q4. What is the worst-case time complexity of Quick Sort?

a) ( ) b) ( )

c) ( ) d) ( ⁡ )
Q5. Which of the following is a non-comparison-based sorting algorithm?
a) Merge Sort b) Quick Sort

c) Heap Sort d) Counting Sort

Q6. Which sorting algorithm uses a heap data structure?

a) Merge Sort
b) Quick Sort

c) Heap Sort

d) Radix Sort

138