Quickselect Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: d
Explanation: 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.
advertisement
advertisement

4. What is the auxiliary space requirement of the quickselect algorithm?
a) O(n2)
b) O(n)
c) O(n log n)
d) O(1)
View Answer

Answer: d
Explanation: 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
View Answer

Answer: a
Explanation: 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(n2)
c) O(n)
d) O(log n)
View Answer

Answer: c
Explanation: 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
View Answer

Answer: b
Explanation: 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.
advertisement

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

Answer: b
Explanation: 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(n2).

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

Answer: c
Explanation: 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).
advertisement

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
View Answer

Answer: d
Explanation: Quickselect has a poor worst case time complexity of O(n2). 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

b)

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

c)

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

d)

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
Explanation: 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.
 
 

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.