107 中央資工所考古題解答｜軟體考點分析

全卷 22 題都是選擇題，三區都倒扣，其中 8 題是 pseudo-code 填空。範圍涵蓋 recurrence、圖論演算法與 NP 理論。

題型與配分

全卷 8 頁、22 題、100 分，禁用計算器，作答於答案卷（卡）。

演算法分析（1–2）

第 1 題｜遞迴排序演算法 E-SORT(A, i, j)：必要時交換 A[i] 與 A[j]，i + 1 ≥ j 時回傳，k = ⌊(j − i + 1)/3⌋，依序遞迴排序前 j − k、後 i + k 起、再前 j − k 三次。問呼叫 E-SORT(A, 1, n) 的時間複雜度
第 2 題｜承上，問該演算法使用的 auxiliary space

圖論（3–5）

第 3 題｜MST 的兩個敘述：最輕邊唯一時是否必在所有 MST 中（S_A）、含有唯一最輕邊的 cycle 中，該邊是否必在所有 MST 中（S_B）。題目聲明不要假設邊權重相異
第 4、5 題｜Floyd–Warshall，5 個頂點、9 條有向邊（含 negative-weight edge）：(1,2,3)、(1,3,8)、(1,5,−4)、(2,4,1)、(2,5,7)、(3,2,4)、(4,1,2)、(4,3,−5)、(5,4,0)。問 d⁽⁴⁾[2,3] 與 d⁽⁵⁾[1,4]，d^(k)[i,j] 是只用編號 ≤ k 的頂點時 i 到 j 的 shortest path 長度

DP 與遞迴（6–7）

第 6 題｜兩條長度 11 的字串 ABACBACBBAA 與 BDABCBACBDA 的 LCS 長度
第 7 題｜Tower of Hanoi 變形：初始盤子可任意分布在三根柱子 A、B、C 上，每根柱子上由大到小排列。給定 d[1] = A、d[2] = C、d[3] = C、d[4] = B、d[5] = B、d[6] = A，問把 6 個盤子全部移到 C 柱最少要幾步

程式填空（8–13）

第 8–10 題｜array A[1:n] 表示 binary tree，子節點在 A[2i]、A[2i+1]。adjust 與 heapsort 兩段程式有三個空格：下濾時的搬移 (B1)、迴圈結束後的收尾 (B2)、建 heap 迴圈的起始索引 (B3)
第 11–13 題｜Quick sort 的 partition，三個空格：兩個 do-while 之後交換的條件 (B4)、外層 do-while 的結束條件 (B5)、最後 pivot 歸位的交換對象 (B6)

hash（14）

第 14 題｜哪個關於 hash function 的敘述為假：偏斜使用、除數取 2^r、doubling 重建 hash table 的代價、dynamic hash、chaining 時比較的 key

多選（15–22）

第 15 題｜Maximum Contiguous Subsequence Sum 的 DP（MCSSDP），要選出哪些改動合起來能讓它允許空子序列（和為 0）
第 16、17 題｜NP、NP-hard、NP-complete 的定義與 reduction：nondeterministic 多項式演算法、NP-hard 問題的 reduction、NP-hard 能在多項式時間解出時的結論、Y reduction 到 X 與 X reduction 到 Y 時 Y 的類別
第 18 題｜Bellman–Ford（BFSP）的 pseudo-code，要選出哪幾項改動合起來能把它變成 negative cycle 偵測演算法（輸入權重可正可負，輸出 "yes" 或 "no"）
第 19 題｜Subset Sum 的 DP（SSDP）：時間複雜度 O(n·c)、O(n·c²)、是否為 pseudo-polynomial、subset sum 是 P 還是 NP-complete
第 20、21 題｜Floyd–Warshall（AllPairCost）的兩個空格 (B7)、(B8)
第 22 題｜AllPairCost 的適用性：非相鄰頂點的 C[u][v]、有 cycle 的圖、undirected graph、重邊

recurrence 與複雜度（107 第 1、2 題），110、113、115 也有 recurrence 求解。
MST 的性質判斷（107 第 3 題），113 第 15 題同型，109、111、113、114、115 也有 MST。
Floyd–Warshall（107 第 4、5、20–22 題），108、112、114、115 也有。
LCS 與其他 DP（107 第 6、15、19 題），106、108、111、113、114、115 也有 DP。
Heap 與 heapsort（107 第 8–10 題），106、108、109、112、114、115 也有。
Quick sort 的 partition（107 第 11–13 題），108、109、110、113、115 也有。
Hash function 的性質（107 第 14 題），108、109、110、111、112、113、114、115 也有 hash。
NP 理論（107 第 16、17、19 題），106、109、110、111、112、114、115 也有。
Bellman–Ford 與 negative cycle（107 第 18 題），113 第 11、12 題也有含 negative-weight edge 的 single-source shortest path。