MSD Radix Sort Multiple Choice Questions and Answers (MCQs)

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

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

Answer: a
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

Answer: d
Explanation: Forward radix sort combines the qualities of MSD and LSD radix sort. The sorting is done by separating the strings into groups.
advertisement
advertisement

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

Answer: a
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

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

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

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

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

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

Answer: b
Explanation: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.
advertisement

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

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

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

Answer: a
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

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

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.