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
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
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
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.
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
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
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
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
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.
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
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
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).
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
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
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Data Structure MCQ
- Check Computer Science Books
- Apply for Computer Science Internship
- Check Design and Analysis of Algorithms Books
- Practice Programming MCQs
