Data Structures & Algorithms Multiple Choice Questions on “Tree Sort”.
1. Which of the following data structure is required for the implementation of tree sort? Answer: c 2. Tree sort is an online sorting algorithm. Answer: a 3. Which of the following traversal in a binary search tree results in a sorted output? Answer: a 4. Which of the following sorting algorithm is stable? Answer: c 5. Which of the following sorting algorithm uses a binary search tree? Answer: b 6. Which of the following is a comparison based sort? Answer: a 7. What is the average case time complexity of tree sort? Answer: b 8. What is the best case time complexity of tree sort? Answer: b 9. What is the worst case time complexity of tree sort (when implemented with a balanced tree)? Answer: b 10. What is the worst case time complexity of tree sort (when implemented with an unbalanced tree)? Answer: c 11. What is the auxiliary space complexity of tree sort? Answer: b 12. In which of the following case does a tree sort become adaptive? Answer: c 13. Which of the following is not true about tree sort? Answer: b 14. Which of the following sorting algorithm is not in place? Answer: c 15. The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree. Answer: b 16. Which of the following is not an advantage of tree sort? 17. Which of the following version of tree sort will have the highest worst case time complexity? Answer: d
a) any ordinary tree
b) balanced tree
c) binary search tree
d) unbalanced tree
Clarification: 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.
a) True
b) False
Clarification: 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.
a) in order traversal
b) pre order traversal
c) post order traversal
d) breadth first traversal
Clarification: 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.
a) Selection sort
b) Quick sort
c) Tree sort
d) Heap sort
Clarification: 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.
a) radix sort
b) tree sort
c) odd-even sort
d) bead sort
Clarification: 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.
a) tree sort
b) radix sort
c) counting sort
d) pigeonhole sort
Clarification: 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.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Clarification: 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.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Clarification: 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).
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Clarification: 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).
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Clarification: 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).
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Clarification: Tree sort requires auxiliary space for maintaining a binary search tree. So the auxiliary space complexity of tree sort is O(n).
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
Clarification: 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).
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
Clarification: Every implementation of tree sort is not adaptive. It becomes adaptive only when implemented with a splay tree as BST.
a) insertion sort
b) quick sort
c) tree sort
d) gnome sort
Clarification: 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).
a) True
b) False
Clarification: 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).
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
Answer: a
Clarification: 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.
a) using AVL tree as BST
b) using red black tree as BST
c) using splay tree as BST
d) using ordinary BST
Clarification: 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.