This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “MSD Radix Sort”.
1. How many comparisons will be made to sort the array arr = {1, 5, 3, 8, 2} using MSD radix sort?
a) 5
b) 7
c) 9
d) 0
View Answer
Explanation: As MSD radix sort is an example of non comparison sort so it is able to sort an array without making any comparison. So the answer should be 0.
2. What is the full form of MSD in MSD radix sort?
a) most significant digit
b) many significant digit
c) more significant digit
d) must significant digit
View Answer
Explanation: MSD stands for Most Significant Digit. It is named so because in this algorithm the processing begins from the most significant digit.
3. Which of the following combines qualities of MSD radix sort and LSD radix sort?
a) in-place MSD radix sort
b) stable MSD radix sot
c) 3 way radix quick sort
d) forward radix sort
View Answer
Explanation: Forward radix sort combines the qualities of MSD and LSD radix sort. The sorting is done by separating the strings into groups.
4. Which of the following is the most suitable definition of radix sort?
a) It is a non comparison based integer sort
b) It is a comparison based integer sort
c) It is a non comparison based non integer sort
d) It is a comparison based non integer sort
View Answer
Explanation: Radix sort is a non-comparison based integer sort. It sorts the given data by grouping keys which share the same significant position value.
5. Which of the following is an alternate name of MSD radix sort?
a) bottom up radix sort
b) top down radix sort
c) forward radix sort
d) backward radix sort
View Answer
Explanation: Top down radix sort is an alternate name of MSD radix sort. It is because in this algorithm the processing starts from the most significant digit and end at least significant digit.
6. Which of the following is not true about MSD radix sort?
a) its processing starts from the most significant digit
b) it is not a stable sort
c) it is an in place sorting algorithm
d) it is non comparison based sort
View Answer
Explanation: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.
7. MSD radix sort should be preferred over LSD radix sort when we have to maintain the original relative order.
a) True
b) False
View Answer
Explanation: MSD radix sort is not a stable sort whereas LSD radix sort is stable. So when we require to preserve the original order then in that case we should prefer LSD radix sort.
8. What is the average time complexity of MSD radix sort (w= bits required to store each key)?
a) O(n + w)
b) O(n.w)
c) O(n2)
d) O(n log n)
View Answer
Explanation: Time complexity of radix sort is O(n.w). It performs better than quick sort when we have log n bits for every digit.
9. MSD radix sort is an in place sorting algorithm.
a) True
b) False
View Answer
Explanation: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.
10. Which of the following statement is not a stable sorting algorithm?
a) LSD radix sort
b) MSD radix sort
c) Counting sort
d) Pigeonhole sort
View Answer
Explanation: MSD radix sort is not a stable sort. It is because the elements with identical values do not appear in the same order in the output array as they were in the input array.
11. Which of the following is not true about radix sort?
a) Radix sort performs better than quick sort when we have log n bits for every digit
b) Radix sort has better cache performance than quick sort
c) Radix sort has higher values of constant factor in asymptotic notation
d) Radix sort takes more space than quick sort
View Answer
Explanation: Quick sort has a better cache performance than radix sort. Radix sort also takes more space as compared to quick sort.
12. What is the advantage of radix sort over quick sort?
a) radix sort performs better than quick sort when we have log n bits for every digit
b) radix sort has lesser space complexity
c) radix sort is not a comparison based sorting technique
d) radix sort has better cache performance than quick sort
View Answer
Explanation: Radix sort performs better than quick sort when we have log n bits for every digit. But radix sort takes more space as compared to quick sort.
13. What will be the order of elements of the array arr = {23, 67, 143, 654, 43} after first iteration of MSD sort is complete?
a) 23, 43, 67, 143, 654
b) 23, 67, 43, 143, 654
c) 23, 67, 143, 654, 43
d) 23, 143, 43, 654, 67
View Answer
Explanation: In the first iteration the array is sorted according to the most significant digit I.e. hundreds place value. So the order of elements will be 23, 67, 43, 143, 654.
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
- Practice Programming MCQs
- Practice Computer Science MCQs
- Check Programming Books
