113 年國立成功大學人工智慧科技碩士學位學程《程式設計（含資料結構與演算法）》考古題與詳解

Question 1

1. [3%, 2%] You are given an empty binary search tree (BST). i) [Step 1] Please successively insert the data pairs containing the following keys 15, 8, 13, 18, 17, 6, 11, 14, 5 into the tree. What is the level of the node containing 5 in the resultant BST? Note: In a tree, each step from top to bottom is called as level of a tree. The level count starts with 1 and increments by 1 at each level or step. (A) 1 (B) 2 (C) 3 (D) 4 (E) None of the above ii) [Step 2] After Step 1 is executed, please delete the node containing 15 from the BST. To delete a nonleaf node, the pair to be deleted should be replaced by the largest pair in its left subtree or the smallest one in the right subtree. Which of the following keys is a suitable key to replace 15? (A) 8 (B) 13 (C) 17 (D) 18 (E) None of the abov…

Accepted Answer

核心觀念 本題考查二元搜尋樹（Binary Search Tree, BST）的： 1. 插入規則：左子樹所有鍵值小於節點，右子樹所有鍵值大於節點。 2. 節點層級：根節點為第 1 層，往下一層增加 1。 3. 非葉節點刪除：以左子樹的最大鍵值，或右子樹的最小鍵值取代被刪節點。 --- i) 插入後，鍵值 5 的層級 依序插入： - $15$：成為根節點。 - $8<15$：插入 $15$ 的左子樹。 - $13<15$ 且 $138$：插入 $8$ 的右子樹。 - $1815$：插入 $15$ 的右子樹。 - $1715$ 且 $17<18$：插入 $18$ 的左子樹。 - $6<15$ 且 $6<8$：插入 $8$ 的左子樹。 - $11<15,\ 118,\ 11<13$：插入 $13$ 的左子樹。 - $14<15,\ 148,\ 1413$：插入 $13$ 的右子樹。 - $5<15,\ 5<8,\ 5<6$：插入 $6$ 的左子樹。 形成的 BST 為： 從根節點到鍵值 $5$ 的路徑為： $$15\rightarrow 8\rightarrow 6\rightarrow 5$$ 共有四個節點，因此鍵值 $5$ 位於第 $4$ 層。 選項分析 - (A) 1：錯。第 1 層只有根節點 $15$。 - (B) 2：錯。鍵值 $5$ 不在 $15$ 的直接子節點位置。 - (C) 3：錯。鍵值 $5$ 的父節點是 $6$，而 $6$ 位於第 3 層，因此 $5$ 位於第 4 層。 - (D) 4：對。

Question 2

2. [1%, 1%, 3%] Considering the data pairs with keys in the given order: 20, 5, 10, 18, 4, 22, 11, 32, 21, as inputs to create a tree. i) If you create a max heap for them, what is the level of the node containing 5? (A) 1 (B) 2 (C) 3 (D) 4 (E) None of the above ii) If you create a min heap for them, which of the following statements is true? (A) The node containing 11 is in the left subtree of the root. (B) The node containing 18 is in the right subtree of the root. (C) The node containing 20 is the root. (D) The node containing 21 is at level 3. (E) None of the above. iii) If you create a symmetric min-max heap for them, which of the following statements is true? (A) To delete the node containing 5, the node containing 21 is used to replace the deleted node. (B) There are two nodes at le…

Accepted Answer

i) 最大堆 依序以「插入 → 上浮」方式建立： | 插入次序 | 堆陣列 (1‑基) | |---|---| |20|[20]| |5|[20,5]| |10|[20,5,10]| |18|[20,18,10,5]| |4|[20,18,10,5,4]| |22|[22,18,20,5,4,10]| |11|[22,18,20,5,4,10,11]| |32|[32,22,20,18,4,10,11,5]| |21|[32,22,20,21,4,10,11,5,18]| 5 位於索引 $8$，層級 $= \lfloor\log2 8\rfloor+1=4$。 【答案】D --- ii) 最小堆 同樣以「插入 → 上浮」建立，最終陣列：

Question 3

3. [2%, 3%] Given a binary tree with the following postfix and infix patterns. postfix: Z, P, C, L, Y, K, S, W, R, Q infix: Z, Y, P, L, C, Q, K, R, W, S i) What is the result of level-order traversal for the tree? (A) C, S, R, Z, L, K, W, Q, Y, P (B) Q, Y, R, Z, L, K, W, P, C, S (C) Q, R, Y, W, K, L, Z, S, C, P (D) Y, K, R, Z, Q, L, W, C, P, S (E) None of the above ii) What is the result of preorder traversal for the tree? (A) Q, Y, Z, L, P, C, R, K, W, S (B) P, Z, C, Y, L, Q, K, R, W, S (C) Q, Y, Z, L, P, C, R, K, S, W (D) P, Z, C, Y, L, Q, K, R, S, W (E) None of the above

Accepted Answer

i) 層序遍歷結果為 Q, Y, R, Z, L, K, W, P, C, S → 選項 (B)

Question 4

4. [2%, 3%] Given the following weighted undirected graph. 🖼️【此處有附圖，請對照原卷】 i) Which of the following statements is correct? (A) When performing a depth first search of this graph, the next node to visit can be D after visiting A, C, I, N, M, and H. (B) When performing a breath first search of this graph, the next node to visit can be D after visiting A, C, I, N, M, and H. (C) When performing a depth first search of this graph, the next node to visit can be K after visiting B, E, and F. (D) When performing a breath first search of this graph, the next node to visit can be K after visiting B, E, and F. (E) None of the above ii) After generating a maximum cost spanning tree from this graph, which of the following statements is correct? (A) The degree of the node F in the resultant maximum co…

Accepted Answer

=== 第 4 題 === i) 觀念與推導 選項 (A) 與 (B)：若從 $A$ 開始進行 DFS 或 BFS，因 $D$ 為 $A$ 的鄰接節點（第一層），在 BFS 中勢必在造訪第二層的 $I, N, M, H$ 之前即先被造訪；而在 DFS 中，若走 $A 	o C 	o I 	o N$ 後回溯至 $I 	o M 	o H$，此時 $H$ 與 $M$ 已無未造訪鄰點，回溯至 $I$ 時，其未造訪鄰點還有 $J$，故必須先造訪 $J$ 才能回溯到 $C$ 進而造訪 $D$。因此下一節點皆不可能為 $D$。 選項 (C)：若 DFS 起點為 $B$，走訪路徑可以為 $B 	o E 	o F$。此時在 $F$ 節點上，其未造訪的鄰接節點有 $G, J, K$，因此下一個造訪的節點可以選擇 $K$。此敘述正確。 選項 (D)：若為 BFS，走訪完 $B$（第 0 層）與 $E$（第 1 層）後，必須先將 $E$ 的所有鄰接節點（$D$ 與 $F$）皆加入佇列並造訪，不可能跳過 $D$ 直接造訪第 3 層的 $K$。 【答案】：(C) --- ii) 觀念與推導 使用 Kruskal 演算法由大到小選取邊以建構最大生成樹（MCST）： 1. 排序所有邊的權重：$(G, L)=15$, $(F, K)=14$, $(J, I)=13$, $(K, L)=12$, $(F, G)=11$, $(E, F)=10$, $(C, I)=9$, $(G, K)=9$, $(C, D)=8$, $(E, B)=8$, $(D, E)=7$, $(D, J)=6$, $(A, D)=5$, $(I, M)=5$, $(O, P)=5$, $(F, J)=4$, $(H, M)=4$,

Question 5

5. [3%, 2%] Given the following bloom filter. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 i) Assume that the bloom filter has 3 hash functions fi(k), f2(k), and f3(k): fi(k) = (3k) mod m, f2(k) = (2k+1) mod m, f3(k) = k mod m, where k represents the key and m is the size of bit array for the bloom filter. Which of the following statements is true? (A) When inserting k=12, the bits in the bloom filter are not changed. (B) To delete k=2, the bits at indices 4, 5, and 6 are changed to 0. (C) When querying the bloom filter for k=15, the answer is "yes." (D) When querying the bloom filter for k=8, the answer is "yes." (E) None of the above. ii) Considering that the elements in the bloom filter is 5. To minimize the false positive probability, w…

Accepted Answer

核心觀念 Bloom filter 使用 $m$ 個位元與多個雜湊函數： - 插入元素：將所有雜湊位置的位元設為 $1$。 - 查詢元素：只要其中一個對應位元為 $0$，必定不存在；全部為 $1$ 時回答「是」，但可能是假陽性。 - 一般 Bloom filter 不支援刪除：直接將位元設為 $0$，可能同時影響其他元素。 本題位元陣列大小為： $$ m=15 $$ 目前各索引的位元為： $$ [1,1,0,1,1,1,1,1,0,1,0,0,0,1,0] $$ i) 各選項判斷 選項（A） 插入 $k=12$ 時： $$ f1(12)=(3	imes 12)\bmod 15=36\bmod 15=6 $$ $$ f2(12)=(2	imes 12+1)\bmod 15=25\bmod 15=10 $$ $$ f3(12)=12\bmod 15=12 $$ 對應位元為： - 索引 $6$：原本為 $1$ - 索引 $10$：原本為 $0$ - 索引 $12$：原本為 $0$ 因此索引 $10$、$12$ 會由 $0$ 變成 $1$，位元陣列會改變。 所以（A）錯誤。 選項（B） 對 $k=2$ 計算雜湊位置： $$ f1(2)=6,\qquad f2(2)=5,\qquad f3(2)=2 $$ 正確位置為 $2$、$5$、$6$，不是選項所說的 $4$、$5$、$6$。 此外，一般 Bloom filter 不可直接刪除元素，因為索引 $5$、$6$ 的位元可能也是其他元素所設為 $1$。任意清除位元會造成假陰性。 所以（B）錯誤。 選項（C） 對 $k=15$ 計算： $$ f1(15)=45\bmod 15=0 $$ $$ f2(15)=31\bmod 15=1 $$ $$ f3(15)=15\bmod 15=0 $$ 需要檢查索引 $0$ 與 $1$： $$ B[0]=1,\qquad B[1]=1 $$ 所有對應位元皆為 $1$，因此查詢結果為「是」。 所以（C）正確。 選項（D） 對 $k=8$ 計算： $$ f1(8)=24\bmod 15=9 $$ $$ f2(8)=17\bmod 15=2 $$

Question 6

6. [5%] Given the following height-based leftist tree. 🖼️【此處有附圖，請對照原卷】 After deleting the minimum element from the leftist tree, which of the following statement is true? (A) The number of nodes in the right subtree of the root is 7. (B) The node containing 15 is at level 3. (C) The shortest path from the root to the external node contains 2 edges. (D) The node containing 16 is in the right subtree of the root. (E) None of the above

Accepted Answer

根據 leftist tree 的合併與刪除最小元素（Delete-Min）步驟：

刪除根節點：刪除根節點 $4$ 後，需合併左子樹 $A$ （以 $9$ 為根）與右子樹 $B$ （以 $7$ 為根）。
合併過程：
- 比較 $9$ 與 $7$ ，因 $7 < 9$ ，以 $7$ 為新根，遞迴合併其右子樹（以 $16$ 為根）與樹 $A$ （以 $9$ 為根）。
- 比較 $16$ 與 $9$ ，因 $9 < 16$ ，以 $9$ 為根，遞迴合併其右子樹（以 $14$ 為根）與樹（以 $16$ 為根）。
- 比較 $14$ 與 $16$ ，因 $14 < 16$ ，以 $14$ 為根，遞迴合併其右子樹（空節點 $\text{null}$ ）與樹（以 $16$ 為根），結果為 $16$ 成為 $14$ 的右子樹。
更新 $s$ -value（最短外路徑長度）與調整：
- 節點 14：左子樹為 $17$ （ $s=1$ ），右子樹為 $16$ （ $s=1$ ）。不需交換，更新 $s(14) = 1 + \min(1, 1) = 2$ 。
- 節點 9：左子樹為 $16$ （ $s=2$ ），右子樹為 $14$ （ $s=2$ ）。

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

Question 7

7. [5%] Given an initial empty Fibonacci heap (F heap). After a sequence of insertion operations and delete-min operations, the Fibonacci heap becomes as follows: 🖼️【此處有附圖，請對照原卷】 Then, please proceed to perform operations in the following order: decrease the key 14 by 5, decrease the key 21 by 14, delete the key 12, insert the key 14, delete the minimum key. Considering these operations, which of the following statements is true? (A) After performing "delete the key 12", the F heap has two min trees. (B) A cascading cut occurs when performing "decrease the key 14 by 5." (C) The resultant F heap has 4 min trees. (D) The resultant F heap has 2 min trees. (E) None of the above.

Accepted Answer

1. 初始狀態： 根節點為 $8$。其子節點為 $10$、$15$、$21$。 $10$ 的子節點為 $14$、$12$，其中 $14$ 的子節點為 $30$。 $15$ 的子節點為 $18$。 $21$ 無子節點。 此時無任何節點被標記（marked）。 2. 操作一：decrease the key 14 by 5 $14$ 減少 $5$ 變為 $9$。 因 $9 < 10$（其父節點），將 $9$ 自 $10$ 切斷（cut）並移至根 list。 $10$ 失去第一個子節點，標記 $10$（$10$ 變為 marked）。無 cascading cut 發生（選項 (B) 錯誤）。 根 list：[8, 9] 3. 操作二：decrease the key 21 by 14 $21$ 減少 $14$ 變為 $7$。 因 $7 < 8$（其父節點），將 $7$ 自 $8$ 切斷並移至根 list。 根 list：[8, 9, 7] 4. 操作三：delete the key 12 將 $12$ 的鍵值降為 $-\infty$。 將 $-\infty$ 自其父節點 $10$ 切斷並移至根 list。 因 $10$ 先前已被標記，觸發 cascading cut：將 $10$ 自其父節點 $8$ 切斷並移至根 list，並將 $10$ 取消標記（unmarked）。因 $8$ 為根節點，級聯剪下停止。

Question 8

8. [5%] Given the following red-black tree, where the dark color indicates a black node and white color indicates a red node. 🖼️【此處有附圖，請對照原卷】 After inserting 62, which of the followings is true? (A) (B) (C) (D) (E) None of the above.

Accepted Answer

在紅黑樹中插入節點 $62$ 的步驟如下： 1. 搜尋與插入： 根據二元搜尋樹的性質，將新節點 $62$ 插入為 $47$ 的右子節點，且新插入節點 $62$ 初始顏色為紅色。 2. 第一次修正（Recoloring）： 此時 $62$ 的雙親節點 $47$ 為紅色，發生雙紅衝突（Double Red violation）。 $62$ 的叔叔節點 $32$ 為紅色。 根據紅黑樹規則（叔叔節點為紅色），進行重新著色（Recoloring）： 將雙親節點 $47$ 與叔叔節點 $32$ 改為黑色。 將祖父節點 $36$ 改為紅色。 此步驟無須旋轉。

Question 9

9. [5%] Given the following B⁺-tree of order 4 (2-3-4 tree). The capacity of a data node is 3 and a data node has at least two elements. (A) After inserting the element whose key is 49 into the B⁺-tree, 45 becomes in the root. (B) After deleting 72 from the B⁺-tree, the number of keys in node E is 2. (C) After inserting the element whose key is 28 into the B⁺-tree, the key in node C is 16. (D) After deleting 45 from the B+-tree, the keys in node D are 33, 41, and 45. (E) None of the above

Accepted Answer

B⁺‑Tree 基本規則 - Order = 4 → 每個內部節點最多 3 個鍵，最少 ⌈4/2⌉‑1 = 1 個鍵。 - 資料節點（葉節點）容量 = 3 → 每個葉節點最多 3 個鍵，最少 2 個鍵。 判斷各選項 | 選項 | 推理 | 結論 | |------|------|------| | (A) 插入鍵 49 後，45 成為根節點 | 根節點僅在原根節點 滿（已有 3 個鍵）且 分裂 時才會改變。分裂時提升的是 中間鍵，若提升的是 45，根節點仍會保留原有其他鍵，根不會只剩 45。故 45 不可能單獨成為根。 | 錯誤 |

Question 10

10. [5%] A binary trie can be transformed to Patricia. Considering the following binary trie, which of the Patricia is a correct transformation result? 🖼️【此處有附圖，請對照原卷】 (A) 🖼️【此處有附圖，請對照原卷】 (B) 🖼️【此處有附圖，請對照原卷】 (C) 🖼️【此處有附圖，請對照原卷】 (D) 🖼️【此處有附圖，請對照原卷】 (E) None of the above.

Accepted Answer

核心觀念 Patricia 樹會把二元 trie 中只有一個分支的路徑壓縮，只保留真正能區分鍵值的位元位置。沿搜尋路徑，位元位置必須依序遞增；若某條連結回到位元位置較小或相同的節點，就是線索連結，搜尋會在位元位置不再遞增時停止，並核對目前節點的鍵值。 解題方法 原圖的六個鍵值是 0000、0010、0011、1000、1100、1101。以由左至右的第 1 至第 4 位計算，0000 與 0010 在第 3 位不同，0010 與 0011 在第 4 位不同；1000 與 1100 在第 2 位不同，1100 與 1101 在第 4 位不同。根部的第 1 位則區分 0xxx 與 1xxx。 因此，正確的 Patricia 樹必須保留這些分歧位置，並在第 4 位正確區分 1100 和 1101。判斷選項時，可沿各鍵值的搜尋路徑追蹤位元測試，並確認最後停下時核對到的鍵值正確。 選項分析 - (A) 正確。 此圖保留了必要的分歧位元。搜尋 1100 時，第 4 位為 0，會回指 1100；搜尋 1101 時，第 4 位為 1，會到達 1101。搜尋所得鍵值與輸入相符。

Question 11

11. (10%) Consider three $n	imes n$ matrices, denoted as $A$, $B$, and $C$. Each of these matrices is partitioned into four $n/2	imes n/2$ submatrices. Assuming that $n$ is an exact power of 2, we can guarantee that, for $n\ge 2$, the dimension $n/2$ is an integer. The subdivisions for matrix $A$ yield $A{11}$, $A{12}$, $A{21}$, and $A{22}$. Similarly, matrix $B$ is decomposed into $B{11}$, $B{12}$, $B{21}$, and $B{22}$, while matrix $C$ undergoes division into $C{11}$, $C{12}$, $C{21}$, and $C{22}$. We have the following procedure: $$ \begin{aligned} F(A,B):\quad & n=A.\mathrm{rows}\ &	ext{if }n==1\ &\quad C{11}=a{11}\cdot b{11}\ &	ext{else}\ &\quad C{11}=F(A{11},B{11})+F(A{12},B{21})\ &\quad C{12}=F(A{11},B{12})+F(A{12},B{22})\ &\quad C{21}=F(A{21},B{11})+F(A{22},B{21})\ &\qua…

Accepted Answer

核心觀念

本題考查分治演算法的遞迴式與主定理。若每次將問題縮小為原來的 $1/2$ ，產生 $a$ 個子問題，並在每層額外花費 $f(n)$ 時間，遞迴式可寫成：

T(n)=aT(n/2)+f(n)

解題方法

逐一計算程序中的遞迴呼叫數，以及矩陣加法的成本：

$C_{11}$ 有 2 次遞迴呼叫，兩個結果相加。
$C_{12}$ 有 2 次遞迴呼叫，兩個結果相加。
$C_{21}$ 有 2 次遞迴呼叫，兩個結果相加。
$C_{22}$ 只有 1 次遞迴呼叫，依題意不再補上第二次呼叫。

因此，每次處理 $n\times n$ 矩陣時，總共有 $2+2+2+1=7$ 次、每次規模為 $n/2$ 的遞迴呼叫。

前三個子矩陣各需要一次矩陣加法，共 3 次。每次矩陣加法處理 $(n/2)\times(n/2)$ 個元素，成本為 $\Theta((n/2)^2)=\Theta(n^2)$ 。所以遞迴式為：

T(n)=7T(n/2)+\Theta(n^2)

基底情況為 $T(1)=\Theta(1)$ 。

套用主定理， $a=7$ 、 $b=2$ ，而：

n^{\log_b a}=n^{\log_2 7}

Question 12

12. (10%) Consider a neural network with $n$ layers of fully connected layers, where the first layer is the input layer, the $n$th layer is the output layer, and the rest are hidden layers. The $i$th layer has $Pi$ neurons, where $1\le i\le n$. Each neuron in the $i$th layer is connected to every neuron in the $(i+1)$th layer, where $1\le i<n$. Let $w{j,k}^{i}$ represent the weight of the connection from the $j$th neuron in the $i$th layer to the $k$th neuron in the $(i+1)$th layer. Let $[v1^i\ v2^i\ \cdots\ v{Pi}^i]^T$ be the values of neurons in the $i$th layer, where $1\le i\le n$. Then, we can obtain $vk^{i+1}=\sum{j=1}^{Pi}w{j,k}^{i}vj^i$, where $1\le k\le P{i+1}$. Given that $(P1,P2,P3,P4,P5,P6)=(10,6,12,5,50,3)$, we want to achieve the result from the input layer to the output layer…

Accepted Answer

核心觀念 本題考的是矩陣鏈乘法。依題目給定的公式，每一層都是線性運算，因此可將整個網路寫成矩陣與輸入向量的連乘，再選擇乘法順序以降低乘法次數。 兩個維度分別為 $a	imes b$ 與 $b	imes c$ 的矩陣相乘，需要 $abc$ 次乘法。矩陣鏈乘法的動態規劃遞迴式為： $$ m[i,j]=\min{i\le k<j} \left(m[i,k]+m[k+1,j]+d{i-1}dkdjight) $$ 其中 $d$ 是矩陣鏈的維度序列，$m[i,j]$ 表示將第 $i$ 個至第 $j$ 個矩陣相乘所需的最少乘法次數。 解題方法 令 $Wi$ 表示由第 $i$ 層連到第 $i+1$ 層的權重矩陣，則整個網路的輸出為： $$ W5W4W3W2W1\mathbf{v}^{1} $$ 各矩陣及輸入向量的尺寸依序為： $$ W5:3	imes50,\quad W4:50	imes5,\quad W3:5	imes12,\quad W2:12	imes6,\quad W1:6	imes10,\quad \mathbf{v}^{1}:10	imes1 $$ 因此維度序列為 $d=(3,50,5,12,6,10,1)$。將六個矩陣依序編號為 $A1,\ldots,A6$，其中 $A6=\mathbf{v}^{1}$，動態規劃結果如下： | 矩陣區間 | 最少乘法次數 | |---|---:| | $m[1,2],m[2,3],m[3,4],m[4,5],m[5,6]$ | $750,\ 3000,\ 360,\ 720,\ 60$ | | $m[1,3],m[2,4],m[3,5],m[4,6]$ | $930,\ 1860,\ 660,\ 132$ |

Question 13

13. (10%) Given two sequences $X=\langle x1,x2,\ldots,xm\rangle$ and $Y=\langle y1,y2,\ldots,yn\rangle$, define $c[i,j]$ to be the length of an LCS (longest common subsequence) of the sequences $Xi=\langle x1,x2,\ldots,xi\rangle$ and $Yj=\langle y1,y2,\ldots,yj\rangle$. Write the recursive formula to compute $c[i,j]$.

Accepted Answer

核心觀念 本題考查最長共同子序列（LCS）的動態規劃。子序列保留原有元素的相對順序，但不要求連續。 令 $c[i,j]$ 表示 $X$ 的前 $i$ 個元素與 $Y$ 的前 $j$ 個元素的 LCS 長度。計算時比較兩個前綴的最後一個元素 $xi$ 與 $yj$。 解題方法 若其中一個前綴為空，沒有共同子序列，因此： $$ c[i,0]=0 \quad (0\le i\le m),\qquad c[0,j]=0 \quad (0\le j\le n) $$ 接著分兩種情況： - 若 $xi=yj$，這個相同元素可接在 $X{i-1}$ 與 $Y{j-1}$ 的 LCS 後面，長度增加 $1$。 - 若 $xi
e yj$，LCS 不會同時以 $xi$ 和 $yj$ 結尾；分別略去其中一個末尾元素，取兩種結果中較大的長度。 因此遞迴公式為： $$ c[i,j]= \begin{cases} 0, & i=0	ext{ 或 }j=0,\ c[i-1,j-1]+1, & xi=yj,\ \max\{c[i-1,j],\,c[i,j-1]\}, & xi
e yj. \end{cases} $$ 關鍵程式碼與複雜度

Question 14

14. (10%) Given a sequence of $n$ numbers, what is the lower bound for sorting algorithms employing comparison and exchange operations?

Accepted Answer

核心觀念 本題考查比較式排序的下界。在只透過元素間的比較來判斷順序時，排序演算法必須能分辨輸入元素的不同排列。交換操作可以改變元素位置，但無法取代比較所提供的順序資訊。 以下假設 $n$ 個元素互異；若有重複元素，可能排列數會減少。 解題方法 $n$ 個互異元素共有 $n!$ 種排列。把排序過程表示成一棵決策樹：每次比較是一次分支，葉節點代表演算法判定的一種輸入排列。正確排序必須能區分全部 $n!$ 種排列，因此決策樹至少要有 $n!$ 個葉節點。 若樹的高度為 $h$，最多有 $2^h$ 個葉節點，故： $$ 2^h \ge n! $$ 取以 $2$ 為底的對數，可得最壞情況比較次數至少為： $$ h \ge \lceil \log2(n!) \rceil $$

Question 15

15. (10%) Find the set of feasible solutions $\{x=(x1,x2,x3,x4,x5)\}$ or determine that no feasible solution exists for the following system of difference constraints: $$ \begin{aligned} x1-x3&\le 1\ x2-x3&\le 4\ x4-x5&\le -2\ x3-x4&\le 4\ x5-x1&\le 3\ x4-x2&\le -7\ x1-x2&\le -2\ x5-x3&\le 1 \end{aligned} $$

Accepted Answer

核心觀念 差分限制式的一般形式為 $xj-xi\le c$。可將它表示成有向邊 $i	o j$，邊權重為 $c$。差分限制式系統可行，等價於其限制圖中沒有負權重環；若能找出一組滿足所有限制的變數值，就能直接證明系統可行。 本題要求的是所有可行解，因此除了確認可行，也要描述各變數之間可取的範圍。 解題方法 由於每個限制只涉及變數的差值，所有變數同時加上相同常數仍是可行解。令 $x3=s$ 作為基準，並定義 $$ t=x4-x3,\qquad y=x2-x3,\qquad z=x1-x3,\qquad w=x5-x3. $$ 原限制式改寫為 $$ \begin{aligned} z&\le 1,\ y&\le 4,\ t-w&\le -2,\ -t&\le 4,\ w-z&\le 3,\ t-y&\le -7,\ z-y&\le -2,\ w&\le 1. \end{aligned} $$ 先由 $-t\le4$ 得 $t\ge-4$。又由 $t-y\le-7$ 得 $y\ge t+7$，搭配 $y\le4$ 可得 $t\le-3$。因此 $$ -4\le t\le -3,\qquad t+7\le y\le4. $$ 接著，$z\le1$ 且 $z-y\le-2$，所以 $z\le\min(1,y-2)$。為使 $w$ 同時滿足 $w\ge t+2$ 與 $w\le z+3$，必須有 $z\ge t-1$。因此

113 年國立成功大學人工智慧科技碩士學位學程《程式設計（含資料結構與演算法）》

第 1 題3 分

第 2 題1 分

第 3 題2 分

第 4 題2 分

i) 觀念與推導

ii) 觀念與推導

第 5 題3 分

核心觀念

i) 各選項判斷

選項（A）

選項（B）

選項（C）

選項（D）

第 6 題5 分

第 7 題5 分

第 8 題5 分

第 9 題5 分

第 10 題5 分

第 11 題10 分

核心觀念

解題方法

第 12 題10 分

核心觀念

解題方法

第 13 題10 分

核心觀念

解題方法

關鍵程式碼與複雜度

第 14 題10 分

核心觀念

解題方法

第 15 題10 分

核心觀念

解題方法

其他考古題

113 年成功大學的其他科目

成功大學《程式設計》其他年度

插入次序	堆陣列 (1‑基)
20	[20]
5	[20,5]
10	[20,5,10]
18	[20,18,10,5]
4	[20,18,10,5,4]
22	[22,18,20,5,4,10]
11	[22,18,20,5,4,10,11]
32	[32,22,20,18,4,10,11,5]
21	[32,22,20,21,4,10,11,5,18]

113 年 國立成功大學人工智慧科技碩士學位學程《程式設計（含資料結構與演算法）》

第 1 題3 分

第 2 題1 分

第 3 題2 分

第 4 題2 分

i) 觀念與推導

ii) 觀念與推導

第 5 題3 分

核心觀念

i) 各選項判斷

選項（A）

選項（B）

選項（C）

選項（D）

第 6 題5 分

第 7 題5 分

第 8 題5 分

第 9 題5 分

第 10 題5 分

第 11 題10 分

核心觀念

解題方法

第 12 題10 分

核心觀念

解題方法

第 13 題10 分

核心觀念

解題方法

關鍵程式碼與複雜度

第 14 題10 分

核心觀念

解題方法

第 15 題10 分

核心觀念

解題方法

其他考古題

113 年成功大學的其他科目

成功大學《程式設計》其他年度

113 年國立成功大學人工智慧科技碩士學位學程《程式設計（含資料結構與演算法）》