Part I

1. Please convert the infix expression: \((\mathrm{A} + \mathrm{B}) \times \mathrm{C} + (\mathrm{D} - \mathrm{E}) \times (\mathrm{F} + \mathrm{G})\) into postfix notation and draw the corresponding binary expression tree. (10%)

2. A binary search tree (BST) can be uniquely determined from its postorder traversal. Please draw the BST that corresponds to the following postorder sequence: \(\mathrm{B}\rightarrow \mathrm{A}\rightarrow \mathrm{D}\rightarrow \mathrm{C}\rightarrow \mathrm{H}\rightarrow \mathrm{G}\rightarrow \mathrm{F}\rightarrow \mathrm{E}\). (10%)

3. An array containing 10 elements is sorted using quicksort. After the first partition and pivot exchange, the array becomes [8, 4, 13, 11, 16, 20, 19, 24, 18, 29]. Which element(s) could have been chosen as the pivot in the first step? (10%)

4. Starting with an empty max-heap, perform the following 8 operations in order: (Insert 8), (Insert 4), (Insert 9), (Insert 6), (Extract-Max), (Insert 13), (Insert 17), (Extract-Max). Please draw the resulting max-heap tree after all operations are completed. \((10\%)\)

5. Given the AVL tree shown in Figure 1, insert key 2 and then key 8. After each insertion, please draw the resulting tree once rebalancing has been performed to preserve the AVL property. (10%)

Figure 1 Part II 6. Use Dijkstra algorithm step to step to find a shortest path from S to T in the following graph. (10%)

7. Use Kruskal and Prim algorithms to find the minimum spanning tree step by step of the following graph. (20%)

8. A problem called "Edit Distance" is defined as: Given two strings str1 and str2; edit operations: Insertion, Deletion and Substitution. We can use dynamic programming to find minimum number of operations required to convert str1 to str2. The definitions of operations are as follows: Insertion: insert a new character Deletion: delete a character Substitution: replace on character by another Please write the recursive formula. (5%)

Given str1 = INTENTION and str2 = EXECUTION, use the above recursive formula to calculation an edit distance. (5%)

9. Step by step to build the Huffman Code tree and list Huffman codes for all characters as the following alphabets and their frequencies: [A:5, B:12, C:33, D:19, E:40, F:41]. (10%)

115年 - 115 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147260

114年 - 114 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147250

110年 - [非官方正解]110 國立臺灣大學_碩士班招生考試_電信工程研究所丙組:資料結構與演算法(B)#113108

110年 - [非官方正解]110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890

109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850

104年 - [非官方正解]104 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113199