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

1. (15分) Run the Breadth-First Search (BFS) algorithm to generate a BFS searching tree which has the nodes as its root. Run the algorithm step by step.

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