2. (10分) Run the merge sort on the following array: (5,1,8,3,6,4,7,2) step by step.

3. (10分) Give an asymptotic upper bound for the function \( T(n) \) where \( T(n) \) satisfies the recurrent equation \( T(n) = 3T(\lfloor n / 4 \rfloor) + n^2 \) for integer \( n > 2 \) and \( T(2) \) is a constant.

4. (15分) We have a set of n open intervals \( S = \{(ai, bi): i = 1, \dots, n\} \). We want to choose a largest subset \( S' \subseteq S \) such that the selected intervals in \( S' \) are mutually disjoint. Please give an O(nlog n)-time algorithm to solve this problem.

(5分) (A)在C語言中，int list[5]和intplist[5]的有何不同，要如何将intplist[5]實作為2維陣列？

(20 分) (B)將此 inorder statement : AB+C(D-E)/(F+H) 轉為 postorder，並畫出它的二元樹。須按照以左到右讀取順序來做，以達到單一解答。同時，設計一個算法使用 stack 來實現上述 inorder 轉 postorder，並且以上述 statement 說明如何使用 stack 來做轉換。

6. (10 分) 使用 linked list 實作 stack，運用以下 C 語言程式：typedef struct node { int value; node *next;}void push (node **top, int new_value) { // assume top is not nullnode new_node = (node ) malloc (sizeof (node));// 實作以下敘述// add new_node to stack by top}int pop (node **top) { // assume top is not nullint value;node deleting_node = top;// 實作以下敘述// remove the deleting node from stack, get the value of deleting nodefree(deleting_node);return value;}

7. (15 分) 使用 stack 解決老鼠走迷宮問題 (Maze path search)，設計並描述如何實作，包含 (A) 如何搜尋八個方向來移動 (B) 如何找到合法移動和出口 (C) 解決死路問題

1. (15分) Run the Prim's algorithm to generate a minimum spanning tree for the following graph. It is required that the initial vertex is s. Run the algorithm step by step to generate your tree. What is the tree weight?

2. (15 分) Given a file, we found that it consists of seven symbols a,b,c,d,e,f,g and their frequencies are as follows. Use Huffman coding to encode these 7 symbols to achieve the minimum file size.

3. (5分) Give an asymptotic upper bound for the function \( \mathrm{T}(\mathfrak{n}) \) where \( \mathrm{T}(\mathfrak{n}) \) satisfies the recurrent equation \( \mathrm{T}(\mathfrak{n}) = 5\mathrm{T}(\mathfrak{n} / 4) + \mathfrak{n} \).

4. (15分) Let \( k \) be \( O(n) \). Describe an \( O(n) \)-time algorithm that, given a set \( S \subseteq \{1, \ldots, k\} \) of \( n \) integers and another integer \( x \), determines whether or not there exist two elements in \( S \) whose product is exactly \( x \).

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

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

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

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

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

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

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

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

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

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