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

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%)

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%)

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%)