110年 - 110 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#145491

(a) To give the inorder traversal of the tree. (5%)

(b) To give the postorder traversal of the tree. (5%)

(c) To give the preorder traversal of the tree. (5%)

(d) To give the level-order of the tree. (5%)

(a) To give h(k) by using the “shift folding” method. (5%)

(b) To give h(k) by using the “folding at the boundaries” method. (5%)

3. Suppose that we are going to sort 10 numbers in the range [0, 999]. We use LSD radix sort with radix r = 10 and pass d = 3 to sort the numbers in an ascending order. The input list is linked, and the numbers are 179, 208, 306, 93, 859, 984, 55, 9, 271, and 33. To write the first-pass, second-pass, and third-pass resulting chains when performing the LSD radix sort. (20%)

4. What is a heap? Explain how to implement a priority queue using heaps. (10%)

5. Compare the differences between B+-trees and B-trees. What are the advantages of B+ -trees over B-trees? Explain your answer. (20%)

6. Show that QuickSort takes O(n2 ) time when the input list is already in sorted order. (20%)