114 中央資工所考古題詳解｜軟體考點分析

題型與配分

全卷 7 頁、20 題複選、每題 5 分、共 100 分，禁用計算器。

全部答對才給分，答錯倒扣 1 分。

與 115 年同型的題目

逐題考點

手動模擬（1–6）

• 第 1 題｜11 格 hash table，quadratic probing 雙向探測（h(k) + i 與 h(k) − i）mod 11，給定插入 8 個項目後的最終表格，問哪些輸入序列可能成立
• 第 2 題｜Infix、postfix、prefix 三種表示法互轉：(a+b)/(c−d)+e 的 postfix、b+a*c/d 的 postfix、一個 postfix 的 infix 與 prefix 形式
• 第 3 題｜輸入 L = [28, 203, 16, 37, 127, 521, 63, 528, 210, 216, 941, 45]，LSD radix sort 第一趟、第二趟結束後指定位置的元素
• 第 4 題｜由 inorder ILOVENCU 與 postorder ILVNCUEO 重建 binary tree，問 level-order 的第五、第六個字母、樹高、C 是否為葉節點
• 第 5 題｜同一段程式碼 push(I)、pop()、push(E) 等，分別套用 standard stack、standard queue、min heap、max heap，問容器內元素的排列
• 第 6 題｜Red-black tree，初始 level order 為 50, 30, 80, 90：節點 30 的顏色、插入 70 與 75 後的 level order 與節點 90 的顏色、插入 70、60、65 後節點 65 的顏色

Floyd–Warshall（7）

• 第 7 題｜給出 Floyd–Warshall 的完整 pseudo-code（D^(k)[i,j] 與 D^(k−1) 的比較更新），問「k 在最短路徑上」與 D 的 recurrence 條件之間的關係，四個選項分別是 if 與 if…then 的不同方向

UAV 加油問題（8–10）

UAV 帶 F 單位燃料，要走 target 公里，沿途有 n 個加油站，加油時站內燃料全部轉入，每公里耗 1 單位，求最少加油次數。

• 第 8 題｜while (F < target) 迴圈中，把加油站放進容器 Q 的 for 迴圈條件 L1 該填什麼
• 第 9 題｜容器 Q 可以是 stack、priority queue、max heap 還是 min heap
• 第 10 題｜Refuel 演算法的時間複雜度與這個加油問題本身的時間複雜度，選項有 Θ(n² log n) 與 Θ(n log n)

觀念判斷（11–20）

• 第 11 題｜Hashing：好的 hash function 是否應均勻分布、h(k) = k mod m 在 m 有因數 d 時的影響、probe sequence h(k,0), …, h(k,m−1) 是否應為 {1,…,m} 的 permutation、perfect hashing 是否存在
• 第 12 題｜LCS：暴力法的複雜度、c[i,j] 的定義與 recurrence 在 x[i] ≠ y[j] 時的寫法、DP 是否為指數複雜度、LCS 的前綴是否為前綴的 LCS
• 第 13 題｜MST：spanning tree 是否唯一、Prim 與 Kruskal 優化後的最壞時間是否相同、disjoint-set 是否用來優化 Prim、Fibonacci heap 是否用來優化 Kruskal
• 第 14 題｜Maximum Flow：source 與 sink 的流入流出、每條邊的順向流與逆向流、Ford–Fulkerson 的 O(Ef)、max flow 與所有 cut 中最大容量的關係
• 第 15 題｜single-source shortest path：negative cycle 時 shortest path 是否存在、子路徑是否也是 shortest path、Dijkstra 在非 negative cycle 圖上、Dijkstra 用 binary heap 的最壞時間、所有邊權相同時是否有更快的演算法
• 第 16 題｜證明決策問題 D 是 NP-complete 的必要步驟：D reduction 到 NPC 問題、指數時間的 nondeterministic 演算法、多項式時間的 nondeterministic 演算法、多項式時間的 deterministic 演算法、NP-hard 問題 reduction 到 D
• 第 17 題｜NP-hard 與 NP-complete 的 reduction：X reduction 到 NP-hard 問題、NPC 問題 reduction 到 X、NP-hard 問題 reduction 到任何 NP-hard 問題、所有 NP 問題 reduction 到任何 NPC 問題、所有 NP 問題 reduction 到任何 NP-hard 問題
• 第 18 題｜asymptotic notation：f(n) = 3n⁴ + 8n − 1666 是否為 O(n⁴)、Ω(n³)、O(2ⁿ) 等
• 第 19 題｜DP：是否用來解可拆成 overlapping subproblems 的問題、LCS 的 DP 時間複雜度、是否一定用二維表、memoization、是否只能用於有 greedy choice property 的問題
• 第 20 題｜搜尋策略：BFS 與 DFS 是否為 uninformed、A* 在 admissible 且 consistent 的 heuristic 下是否保證最佳解、hill climbing 能否跳出區域最佳、branch and bound 的上下界剪枝、Dijkstra 在有 cycle 的圖上

作答時要注意的地方

1. 全對才給分，答錯倒扣 1 分。
2. 第 7 題的四個選項在 D^(k) 與 D^(k−1) 的位置與 if、if…then 的方向上不同。
3. 第 10 題分別問「這個演算法」與「這個問題」的時間複雜度。
4. 第 6 題的 red-black tree 有兩組插入序列。

準備方向

• Hash 的 quadratic probing 與反推插入順序（114 第 1 題），115 第 12 題同型，107、108、109、110、111、112、113 也有 hash。
• 運算式轉換（114 第 2 題），115 第 16 題同型。
• LSD radix sort（114 第 3 題），115 第 14 題同型，112 第 4 題也有。
• 由 inorder 與 postorder 重建 binary tree（114 第 4 題），115 第 18 題同型，106、109、113 也有樹的 traversal。
• Red-black tree（114 第 6 題），115 第 15 題同型。
• Floyd–Warshall（114 第 7 題），107、108、112、115 也有。
• greedy 加 heap 的 LeetCode 型題目（114 第 8–10 題），115 第 19 題同型。
• LCS 與 DP（114 第 12、19 題），106、107、108、111、113、115 也有。
• MST（114 第 13 題），107、109、111、113、115 也有。
• max flow（114 第 14 題）只出現這一年。
• single-source shortest path（114 第 15 題），106、107、110、113、115 也有 shortest path。
• NP 理論（114 第 16、17 題），106、107、109、110、111、112、115 也有。
• asymptotic notation（114 第 18 題），113、115 也有。
• 搜尋策略（114 第 20 題），106 第 6 題也有 BFS、DFS、hill climbing、best-first search。