This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Tree Sort”.
1. Which of the following data structure is required for the implementation of tree sort?
a) any ordinary tree
b) balanced tree
c) binary search tree
d) unbalanced tree
View Answer
Explanation: Tree sort uses a binary search tree for sorting the given elements. Tree sort can also be performed by using an unbalanced binary search tree.
2. Tree sort is an online sorting algorithm.
a) True
b) False
View Answer
Explanation: Tree sort does not require the entire input data at the beginning itself in order to sort the array. It rather creates a partial solution in every step, so future elements are not required to be considered. Hence it is an online sorting algorithm.
3. Which of the following traversal in a binary search tree results in a sorted output?
a) in order traversal
b) pre order traversal
c) post order traversal
d) breadth first traversal
View Answer
Explanation: Tree sort uses a binary search tree for sorting the given elements. First a BST is formed by using the input data elements and then the BST is traversed in an in order fashion which gives a sorted output.
4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Tree sort
d) Heap sort
View Answer
Explanation: Out of the given options Tree sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.
5. Which of the following sorting algorithm uses a binary search tree?
a) radix sort
b) tree sort
c) odd-even sort
d) bead sort
View Answer
Explanation: Tree sort makes use of a binary search tree. It is because every time when a BST is traversed in an in order fashion it gives a sorted output.
6. Which of the following is a comparison based sort?
a) tree sort
b) radix sort
c) counting sort
d) pigeonhole sort
View Answer
Explanation: In tree sort, we need to compare elements as we insert them in the binary search tree. Thus it qualifies as a comparison based sort.
7. What is the average case time complexity of tree sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: As on an average every element takes log n time for insertion in a binary search tree so for n elements O(n log n) time will be required on an average.
8. What is the best case time complexity of tree sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The best case time complexity of tree sort is the same as its average case complexity. So best case time complexity is O(n log n).
9. What is the worst case time complexity of tree sort (when implemented with a balanced tree)?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The worst case time complexity of tree sort depends on whether the tree used in the implementation is balanced or not. If the tree is balanced then the worst case complexity is O(n log n).
10. What is the worst case time complexity of tree sort (when implemented with an unbalanced tree)?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The worst case time complexity of tree sort depends on whether the tree used in the implementation is balanced or not. If the tree is unbalanced then the worst case complexity is O(n2).
11. What is the auxiliary space complexity of tree sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Explanation: Tree sort requires auxiliary space for maintaining a binary search tree. So the auxiliary space complexity of tree sort is O(n).
12. In which of the following case does a tree sort become adaptive?
a) when implemented with an unbalanced tree
b) when implemented with a balanced tree
c) when implemented with a splay tree as BST
d) when implemented with AVL tree as BST
View Answer
Explanation: Tree sort becomes an adaptive sort when it is implemented with a splay tree as a BST. In such a case the best case time complexity is better than (n log n).
13. Which of the following is not true about tree sort?
a) it is not an in place sorting algorithm
b) its every implementation is adaptive
c) it requires in order traversal of BST for sorting input elements
d) it is a stable sort
View Answer
Explanation: Every implementation of tree sort is not adaptive. It becomes adaptive only when implemented with a splay tree as BST.
14. Which of the following sorting algorithm is not in place?
a) insertion sort
b) quick sort
c) tree sort
d) gnome sort
View Answer
Explanation: Out of the given options tree sort is the only algorithm which is not in place. It is because the auxiliary space required by tree sort is O(n).
15. The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree.
a) True
b) False
View Answer
Explanation: The time complexity of tree sort is affected when implemented with an unbalanced tree or a balanced tree. In case of a balanced tree it is O(n log n) and in case of unbalanced tree it is O(n2).
16. Which of the following is not an advantage of tree sort?
a) it has a low space complexity
b) it has good time complexity for balanced BST
c) it is an online sorting algorithm
d) it is stable sorting algorithm
View Answer
Explanation: Tree sort has a linear time complexity O(n) which makes it inefficient. This the main reason why sorting algorithms like quick sort, heap sort etc. are preferred over it.
17. Which of the following version of tree sort will have the highest worst case time complexity?
a) using AVL tree as BST
b) using red black tree as BST
c) using splay tree as BST
d) using ordinary BST
View Answer
Explanation: Out of the given options tree sort has the highest worst case time complexity with ordinary BST as it may not be balanced in every case. Whereas all other options have self balancing BST.
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]
- Check Computer Science Books
- Practice Programming MCQs
- Check Programming Books
- Check Design and Analysis of Algorithms Books
- Apply for Computer Science Internship
