250+ TOP MCQs on Quickselect and Answers [2024]

Data Structures & Algorithms Multiple Choice Questions on “Quickselect”.

1. Which of the following is an alternative name of the quickselect algorithm?
a) quick sort
b) hoare’s selection algorithm
c) tony’s selection algorithm
d) kruskal’s algorithm
Answer: b
Clarification: Quick select is a selection algorithm. It was developed by Tony Hoare, thus it is also known as Hoare’s selection algorithm.

2. Quickselect is an example of ___________
a) sorting algorithm
b) selection algorithm
c) greedy algorithm
d) searching algorithm
Answer: b
Clarification: Quickselect is an example of a selection algorithm. It finds the kth smallest element from the given list.

3. What will be the output if quickselect algorithm is applied to the array arr={1,5,4,3,7} with k given as 4?
a) 1
b) 3
c) 4
d) 5
Answer: d
Clarification: Quickselect algorithm finds the kth smallest element from the given list. So as here the given value of k is 4 so we need to find the fourth smallest element which is 5 in the given array.

4. What is the auxiliary space requirement of the quickselect algorithm?
a) O(n²)
b) O(n)
c) O(n log n)
d) O(1)
Answer: d
Clarification: Quickselect algorithm requires no extra space in order to calculate the desired result. It performs manipulations in the given array itself so its auxiliary space requirement will be O(1).

5. Quickselect is an in-place algorithm?
a) true
b) false
Answer: a
Clarification: Quickselect’s auxiliary space requirement is O(1). So quickselect qualifies as an in-place algorithm.

6. What is the best case time complexity of quickselect?
a) O(n log n)
b) O(n²)
c) O(n)
d) O(log n)

Answer: c
Clarification: Best case time complexity of quickselect is O(n). It is observed in the case where good pivots are chosen consistently then the array size decreases exponentially and thus the required element is found in linear time.

7. Quickselect’s algorithm is similar to which of the following algorithm?
a) Merge sort
b) Quicksort
c) Selection sort
d) Counting sort
Answer: b
Clarification: Both quicksort and quickselect algorithms are closely related. They were developed by the same person. Like quicksort, quickselect also works by choosing a pivot and partitioning array.

8. What is the worst case time complexity of quickselect?
a) O(n log n)
b) O(n²)
c) O(n)
d) O(log n)

Answer: b
Clarification: Worst case complexity occurs in the case where bad pivots are chosen consistently due to which the size of the array decreases in the steps of 1 only. This leads to a time complexity of O(n²).

9. What is the average case time complexity of quickselect?
a) O(n log n)
b) O(n²)
c) O(n)
d) O(log n)

Answer: c
Clarification: In quickselect, we don’t recur for both portions of the array. Only that portion is considered where the smallest element lies. So this causes the average time complexity to be O(n).

10. Which of the following is a disadvantage of quickselect?
a) Poor space complexity
b) Poor best case time complexity
c) Poor average case time complexity
d) Poor worst case time complexity

Answer: d
Clarification: Quickselect has a poor worst case time complexity of O(n²). There are algorithms which have O(n) time complexity in the worst case.

11. Which of the following correctly represent the algorithm of quickselect?
a)

function quickSelect(list, left, right, k)
   if left = right
      return list[left]
   Select a pivotIndex between left and right
   pivotIndex := partition(list, left, right,  pivotIndex) 
   if k = pivotIndex
      return list[k]
   else if k < pivotIndex
      right := pivotIndex - 1
   else
      left := pivotIndex + 1

function quickSelect(list, left, right, k)
   if left = right
      return list[right]
   Select a pivotIndex between left and right
   pivotIndex := partition(list, left, right,  pivotIndex)
   if k = pivotIndex
      return list[k]
   else if k > pivotIndex
      right := pivotIndex - 1
   else
      left := pivotIndex + 1

function quickSelect(list, left, right, k)
   if left = right
      return list[left]
   Select a pivotIndex between left and right
   pivotIndex := partition(list, left, right,  pivotIndex)
   if k = pivotIndex
      return list[k]
   else if k < pivotIndex
      right := pivotIndex +1
   else
      left := pivotIndex -1

function quickSelect(list, right,left, k)
   if left = right
      return list[left]
   Select a pivotIndex between left and right
   pivotIndex := partition(list, left, right,  pivotIndex)
   if k = pivotIndex
      return list[k]
   else if k < pivotIndex
      right := pivotIndex - 1
   else
      left := pivotIndex + 1

View Answer

Answer: a
Clarification: In quickselect algorithm if index of partitioned element is more than k, then we recur for left part. If index is same as k, we have found the kth smallest element and we return. If index is less than k, then we recur for right part.

Leave a Reply Cancel reply