One Mark Multiple Choice Questions
Question 1:
Which of the following sorting algorithms is based on the divide-and-conquer paradigm?
A) Insertion Sort
B) Bubble Sort
C) Quick Sort
D) Selection Sort
Answer: C) Quick Sort
Explanation: Quick Sort is based on the divide-and-conquer paradigm. It divides the array
into sub-arrays around a pivot element and recursively sorts the sub-arrays.
Question 2:
What is the worst-case time complexity of Bubble Sort?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
Answer: B) O(n^2)
Explanation: In the worst-case scenario, Bubble Sort has to perform n-1 passes through the
array, with each pass involving multiple comparisons and swaps, resulting in O(n^2) time
complexity.
Question 3:
Which of the following sorting algorithms is not in-place?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) Insertion Sort
Answer: A) Merge Sort
Explanation: Merge Sort is not an in-place sorting algorithm as it requires additional space
for merging sub-arrays.
Question 4:
In which sorting algorithm is a binary heap used?
A) Quick Sort
B) Merge Sort
C) Selection Sort
D) Heap Sort
Answer: D) Heap Sort
Explanation: Heap Sort utilizes a binary heap data structure to sort elements. It builds a max
heap and then repeatedly extracts the maximum element.
Question 5:
Which sorting algorithm repeatedly selects the smallest element from the unsorted part and
moves it to the sorted part? A) Bubble Sort
B) Insertion Sort
C) Selection Sort
D) Quick Sort
Answer: C) Selection Sort
Explanation: Selection Sort works by selecting the smallest element from the unsorted part
of the array and swapping it with the first unsorted element, thereby growing the sorted part
of the array.
Two Marks Multiple Choice Questions
Question 1:
Given an array of n elements, how many comparisons does Insertion Sort make in the worst
case?
A) O(n log n)
B) O(n)
C) O(n^2)
D) O(log n)
Answer: C) O(n^2)
Explanation: In the worst case, each element in the array has to be compared with every
other element already sorted, resulting in O(n^2) comparisons.
Question 2:
What is the average-case time complexity of Quick Sort?
A) O(n^2)
B) O(n log n)
C) O(n)
D) O(log n)
Answer: B) O(n log n)
Explanation: In the average case, Quick Sort performs n log n comparisons, as the pivot
tends to divide the array into nearly equal parts, resulting in a logarithmic number of
divisions.
Question 3:
Which sorting algorithm is most efficient for a nearly sorted array?
A) Merge Sort
B) Bubble Sort
C) Quick Sort
D) Insertion Sort
Answer: D) Insertion Sort
Explanation: Insertion Sort is highly efficient for nearly sorted arrays, as it requires minimal
comparisons and shifts, resulting in near O(n) performance.
Question 4:
What is the main advantage of using Heap Sort over Quick Sort?
A) Heap Sort is stable
B) Heap Sort has a better average-case time complexity
C) Heap Sort is an in-place sorting algorithm
D) Heap Sort has a guaranteed O(n log n) worst-case time complexity
Answer: D) Heap Sort has a guaranteed O(n log n) worst-case time complexity
Explanation: The main advantage of Heap Sort over Quick Sort is that it guarantees an O(n
log n) time complexity in the worst case, while Quick Sort can degrade to O(n^2) in the worst
case.
Question 5:
Which of the following sorting algorithms is a comparison sort and also stable?
A) Heap Sort
B) Merge Sort
C) Quick Sort
D) Selection Sort
Answer: B) Merge Sort
Explanation: Merge Sort is a comparison-based sorting algorithm that is also stable,
meaning it preserves the relative order of equal elements in the sorted array
High Standard and Tough Multiple Choice Questions
One Mark Questions
Question 1:
Which sorting algorithm's performance is highly dependent on the choice of pivot element
and can degrade to O(n^2) in the worst case?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Insertion Sort
Answer: B) Quick Sort
Explanation: Quick Sort's performance is highly dependent on the choice of the pivot. If the
pivot is poorly chosen, it can degrade to O(n^2) in the worst case.
Question 2:
Which of the following sorting algorithms is best suited for sorting linked lists?
A) Bubble Sort
B) Selection Sort
C) Merge Sort
D) Quick Sort
Answer: C) Merge Sort
Explanation: Merge Sort is well-suited for sorting linked lists because it can be implemented
to use only O(1) extra space and doesn't require random access to elements.
Question 3:
Which of the following sorting algorithms uses a data structure called a "heap"?
A) Quick Sort
B) Merge Sort
C) Insertion Sort
D) Heap Sort
Answer: D) Heap Sort
Explanation: Heap Sort uses a binary heap data structure to sort elements. It builds a max
heap and then repeatedly extracts the maximum element to sort the array.
Question 4:
In which scenario is the best-case time complexity of Bubble Sort achieved?
A) When the array is completely unsorted
B) When the array is sorted in descending order
C) When the array is already sorted
D) When the array has all identical elements
Answer: C) When the array is already sorted
Explanation: Bubble Sort achieves its best-case time complexity of O(n) when the array is
already sorted, as it requires only one pass through the array without any swaps.
Question 5:
What is the primary advantage of the Merge Sort algorithm over Quick Sort?
A) Merge Sort is in-place
B) Merge Sort has better worst-case time complexity
C) Merge Sort is simpler to implement
D) Merge Sort uses less memory
Answer: B) Merge Sort has better worst-case time complexity
Explanation: Merge Sort has a guaranteed O(n log n) time complexity in both the worst and
average cases, whereas Quick Sort can degrade to O(n^2) in the worst case.
Two Marks Questions
Question 1:
Why is the Quick Sort algorithm generally faster in practice compared to other O(n log n)
algorithms?
A) It uses divide-and-conquer
B) It has lower constant factors in its time complexity
C) It uses less memory
D) It is a stable sort
Answer: B) It has lower constant factors in its time complexity
Explanation: Quick Sort is generally faster in practice because it has lower constant factors
and better cache performance compared to other O(n log n) algorithms like Merge Sort.
Question 2:
Consider the following array: [4, 5, 3, 7, 2]. What will be the array after the first pass of
Bubble Sort? A) [4, 5, 3, 7, 2]
B) [4, 3, 5, 7, 2]
C) [4, 5, 3, 2, 7]
D) [4, 3, 5, 2, 7]
Answer: D) [4, 3, 5, 2, 7]
Explanation: During the first pass of Bubble Sort, adjacent elements are compared and
swapped if they are in the wrong order. The array after the first pass will be [4, 3, 5, 2, 7].
Question 3:
What is the maximum number of comparisons required in Merge Sort to merge two sorted
arrays of lengths m and n?
A) m + n - 1
B) 2(m + n)
C) mn
D) m log n
Answer: A) m + n - 1
Explanation: To merge two sorted arrays of lengths m and n, Merge Sort requires at most m
+ n - 1 comparisons.
Question 4:
Given an array where all elements are distinct, which of the following sorting algorithms will
have the same worst-case and best-case time complexities?
A) Quick Sort
B) Bubble Sort
C) Merge Sort
D) Heap Sort
Answer: C) Merge Sort
Explanation: Merge Sort has the same worst-case and best-case time complexities of O(n
log n) regardless of the initial order of the elements.
Question 5:
Why is Heap Sort not considered stable, and how does this affect its performance?
A) It uses a binary heap, which doesn't preserve the relative order of equal elements
B) It has a higher time complexity
C) It requires additional space
D) It is not an in-place sort
Answer: A) It uses a binary heap, which doesn't preserve the relative order of equal elements
Explanation: Heap Sort is not stable because the binary heap data structure used does not
maintain the relative order of equal elements, which can affect the sorted output when
stability is required.
