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

1. Design a randomized algorithm to find the i-th smallest element in a given array of length \( n \). The expected running time of your algorithm should be \( O(n) \). (15分)

2. Run the Floyd-Warshall algorithm on the following graph to find the all-pairs shortest paths step by step. You should generate five matrices according to the Floyd-Warshall algorithm. (15分)

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

4. Let us consider the recurrence \( T(n) = T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + 1 \) for any positive integer \( n \). Use mathematical induction to show that \( T(n) \leq cn \) for some positive number \( c \). (10分)

(A)使用 merge sort 排序數列 69 5 85 36 12 20 59 4 73 31 17。並且說明每次處理數字時，所使用的條件和基準。(5分)

(B)使用 binary search 在排序好的數列尋找數字，比如31，並說明為何能達到 \( O(\log N) \) 的速度，N是數列的數字個數。(5分)

(A)將此 inorder statement: \( \mathrm{A} * \mathrm{B} + \mathrm{C} * (\mathrm{D} - \mathrm{E}) / (\mathrm{F} + \mathrm{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 分)