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

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. | Alphabet | a | b | c | d | e | f | g | | --- | --- | --- | --- | --- | --- | --- | --- | | Frequency in the file | 12 | 26 | 43 | 13 | 9 | 5 | 15 | 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 \).

5. (5分) (A)使用quick sort排序數列60804523698114752897563.7。並且說明每次移動數字時，所使用的條件和基準。

(5分) (B)將此inorder statement: \( A^{*}(B + C) + E^{*}F - H / I \) 轉為 postorder，並畫出它的二元樹。

(10分) (C)設計一個算法使用 stack 來實現上述 inorder 轉 postorder，需解釋如何處理括號和運算式的優先權。

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

7. (20分)使用stack運用C語言實作老鼠走迷宮問題 (Maze path search)： void path() { // assume int maze[30][30] and offsets move[8] has been set in main function // typedef struct {int v; int h;} offsets; int i, row, col, next_row, next_col, dir, found = 0, top =0, mark[30][30]; typedef struct { int row; int col; int dir;} element element position, stack[100]; mark[1][1] = 1; stack[0].row = 1; stack[0].col = 1; stack[0].dir = 0; //實作以下敘述 // Use stack to get current row, col, dir // Use dir to calculate next_row, next_col // Use next_row, next_col to check this move (1) arrive exit, or // (2) become a legal move; add this move into the stack, or // (3) check other dir }