3. Convert the following infix expression to postfix notation: (10%)

$$(P + Q - R) \times (A - B)$$

4. A binary search tree (BST) can be uniquely reconstructed from its postorder traversal. Draw the BST that corresponds to the following postorder traversal sequence: (10%) $$A \rightarrow C \rightarrow B \rightarrow E \rightarrow G \rightarrow F \rightarrow D \rightarrow H$$

5. Build a max heap by inserting the following elements one by one into an empty heap: 10, 14, 33, 27, 35, 19, 42. Show the state of the heap after each insertion step. (10%) 6. An array with 8 elements is being sorted using quicksort. After the first partition step (including pivot placement), the array becomes [4, 6, 9, 3, 10, 15, 12, 22]. List all possible values that could have been chosen as the pivot in this first partition step. (10%)

7. Using the left-child right-sibling method, change the forest in Figure 3 into one binary tree. (10%) tree1 tree2 tree3 Figure 3

8. Use Kruskal's algorithm to find the minimum cost spanning tree (MCST) of the graph in Figure 4. Show your work step by step and draw the graph at each step. (10%) Figure 4

9. Select all statements that are correct about sorting algorithms. (10%) (a) Insertion sort works best when the input list is already sorted in increasing order, and the target sequence is also in increasing order.

(b) If average-case time complexity is the most important factor, quick sort is a good choice.

(c) If worst-case time complexity is important, heap sort and merge sort are better choices than quick sort.

(d) Quick sort is not a stable sorting algorithm.

(e) The lower bound of time complexity for any comparison-based sorting algorithm is \(\Omega (\mathfrak{n}\log \mathfrak{n})\)

10. Insert the key 57 into the AVL tree shown in Figure 5. (10%) Figure 5

115年 - 115 國立臺北大學_日間學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147430

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

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

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

112年 - 112 國立臺北大學_日間學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147429

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

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

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

110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844

110年 - [非官方正解]110 國立高雄科技大學_碩士班招生考試_電腦與通訊工程系：資料結構(乙組)#110488