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

1. We have n activities \( a1, a2, \ldots, an \). Each activity \( ai \) has a start time \( si \) and a finish time \( fi \) where \( 0 \leq si < fi \). If \( ai \) is selected, activity \( ai \) takes place during the half-open time interval \( [si, fi] \). Activities \( ai \) and \( aj \) are compatible if the intervals \( [si, fi] \) and \( [sj, fj] \) do not overlap. In the Activity Selection Problem, we try to select a maximum-size subset of mutually compatible activities. Design an O(nlog n)-time algorithm to solve this problem. (15分)

2. Run the Prim's algorithm to find the minimum spanning tree for the following graph step by step. The starting vertex is the node a. (15分)

3. Run Radix sort on the following array: (329,457,657,839,436,720,355) step by step. (10分)

4. Let \( X[1 \ldots n] \) and \( Y[1 \ldots n] \) be two sorted arrays each containing \( n \) elements. Give an \( O(\log n) \)-time algorithm to find the median of all \( 2n \) elements of \( X \) and \( Y \). (10分)

5. (A) 使用 quick sort 排序數列 60 80 45 2 36 98 11 47 52 89 75 63 7。並且說明每次移動數字時，所使用的條件和基準。(5分) (B) 說明 system stack 的內容與運作方式。(5分)

(A) 將此 inorder statement: \( \mathbf{A}^{}\mathbf{B} + \mathbf{C}^{}(\mathbf{D} - \mathbf{E}) / (\mathbf{F} + \mathbf{H}) \) 轉為 postorder，並畫出它的二元樹。須按照以左到右讀取順序來做，以達到單一解答。(5分)

(B) 設計一個算法使用 stack 來實現上述 inorder 轉 postorder，並且以上述 statement 說明如何使用 stack 來做轉換。(10分)

7. 使用 linked list 實作 stack，運用以下 C 語言程式：
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));
// (A) 實作以下敘述(5分)
// add new_node to stack by top
}
int pop (node **top) { // assume top is not null
int value;
node deleting_node = top;
// (B) 實作以下敘述(5 分)
// remove the deleting node from stack, get the value of deleting node
free(deleting_node);
return value;
}

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