112 中興資工所軟體考點分析
甲組第一份獨立的「資料結構與演算法」考卷。選擇只佔 21%，79% 是簡答：KMP failure function、把審稿分配建成流網路、十個問題判 P／NP-hard。
題型與配分
系所「資訊工程學系 甲組」，科目：資料結構與演算法，全卷 4 頁、100 分，不得使用計算機。
這是中興甲組第一份獨立的軟體考卷。111 年以前軟體與計算機組織合卷在「資訊概論」裡，112 年起拆成「離散數學與線性代數」「資料結構與演算法」「計算機組織與作業系統」三科。
中興官方的歷屆試題資料庫沒有收錄這一年的「資料結構與演算法」，但完整試題冊裡確實有這一科。查資料庫查不到不代表沒考。
| 區段 | 內容 | 配分 | 作答處 |
|---|---|---|---|
| PART 1 Data Structures — A | 選擇題 2 題 | 6%（每題 3 分） | — |
| PART 1 Data Structures — B | 簡答題 6 大題 | 44% | — |
| PART 2 Algorithms — C | 單選題 3 題 | 15%（每題 5 分） | — |
| PART 2 Algorithms — D | 簡答題 5 大題 | 35% | 答案卷（卷上註明「請於答案卷上作答，否則不予計分」） |
選擇題只佔 21%，簡答佔 79%。這是中興軟體三年（112–114）裡申論比重最高的一份，113 年降到 36%、114 年 40%。沒有倒扣，但也幾乎沒有猜的空間。
PART 1-A：選擇題（6%）
- 第 1 題（3%）｜二維陣列的 row-major 位址：
student[100][4]、student[1][1]在位址 1000、每元素佔 1 格，求student[5][3]。這題與 108 年「資訊概論」PART 1 第 2 題一字不差 - 第 2 題（3%）｜哪個時間複雜度最高：O(n100)、O(n!)、O(n2log2n)、O(2n) → O(n!)
PART 1-B：資料結構簡答（44%）
- 第 1 題（6%）｜BST 的搜尋路徑：要找 43，五組 probe sequence 中哪些是可能的。每一組都要驗證「走左邊時後續值必須更小、走右邊時必須更大」的區間收斂。113 年第 9 題用同樣的手法再考一次（BST 存 1–100、搜尋 46）
- 第 2 題（6%）｜Floyd-Warshall 的 Ak 矩陣：給一張 5 節點有向加權圖，求 A1 中非無窮大元素的最大值。要清楚 A1 代表「只允許經過索引 ≤ 1 的中介點」
- 第 3 題（5%）｜遞迴函式求值：
Q(a,b) = 0 (a < b)、Q(a−b, b) + 1 (b ≤ a)，求 Q(5861, 7)。看出這是輾轉相減求商就是 ⌊5861/7⌋ = 837，硬展開要遞迴 837 層 - 第 4 題（10%）｜方形堆疊杯子：第 N 層是 N×N 的正方形。(a) 5%：補完 C 遞迴程式的空格（
return N*N + crystal(N-1);）；(b) 5%：crystal(6) = 1+4+9+16+25+36 = 91 - 第 5 題（9%）｜AOE 網路：S→T(6)、S→X(8)、S→Y(5)、T→X(4)、T→Z(6)、X→Y(3)、X→Z(7)、X→W(5)、Y→W(4)、Z→E(5)、W→E(3)。(a) 3%：關鍵路徑（S→T→X→Z→E，長度 22）；(b) 6%：X、Y、W 的最早與最晚時間（X：10／10、Y：13／15、W：17／19）
- 第 6 題（8%）｜BST 的期望比較次數：給一棵 7 節點的 BST（根 10，左 5→4，右 20→15→11、30），隨機搜尋樹中一個既有的鍵，求期望比較次數（各節點深度 1,2,2,3,3,3,4，(1+2+2+3+3+3+4)/7 = 18/7 ≈ 2.57，題目要求四捨五入到小數第二位）
PART 2-C：演算法單選（15%）
三題都是 C 語言的鏈結串列與指標：
- I（5%）｜
join(node* m, node* n)用while (p->next != NULL)走到尾端再接上 m，問結果。當 n 是 NULL 時會 null pointer dereference，所以答案是「要嘛崩潰、要嘛把 m 接到 n 後面」 - II（5%）｜
move_to_front把單向串列的最後一個節點搬到最前面，選出空格該填哪三行（順序是q->next = NULL; p->next = head; head = p;） - III（5%）｜用雙指標
a、b從兩端夾擠求陣列最大值，問 while 的迴圈條件（a != b）
PART 2-D：演算法簡答（35%，寫在答案卷）
- I（5%）｜KMP 的 failure function：pattern 是
a b a a b a a a a（index 0–8），填完整張表（0, 0, 1, 1, 2, 3, 4, 1, 1） - II（10%）｜把審稿分配建成流網路：6 篇論文、3 位審稿人，R1 = {P1,P3,P5,P6}、R2 = {P1,P2,P4}、R3 = 全部；每篇論文要 2 位不同審稿人、每人最多審 4 篇，求最多能有效分配幾篇。(1) 5%：畫出標好容量的流網路；(2) 5%：最大篇數（瓶頸在 R3 —— P2、P3、P4、P5、P6 這五篇都非 R3 不可，但 R3 上限 4，所以最多 5 篇）
- III（5%）｜矩陣鏈乘法：10×11、11×25、25×40、40×2，求最佳加括號方式與最少乘法次數（A1(A2(A3A4))，2770 次）
- IV（5%）｜求 (x1,…,x5) 使 x1+…+x5 最大，條件是 xi ≤ 0。注意：題目說的「following constraints」在試卷上漏印了，只剩 xi ≤ 0 這一條——在這個條件下最大值就是 0（全取 0）。遇到這種題目要把自己的解讀寫在答案卷上
- V（10%）｜十個問題各判 P（1）／NP-hard 或 NP-complete（2）／兩者皆非（3），這是全卷最值得練的一題：
| 問題 | 答案 |
|---|---|
| (1) 正權圖的最長簡單路徑 | NP-hard |
| (2) 含負環的有向圖求最短簡單路徑 | NP-hard |
| (3) 找負權有向環 | P（Bellman-Ford） |
| (4) 找正權有向環 | P（把權重取負再找負環） |
| (5) 單位權圖的最長環 | NP-hard（Hamiltonian cycle） |
| (6) 單位權圖的最短環（girth） | P |
| (7) 流網路的最大割 | NP-hard（Max-Cut） |
| (8) 流網路的最小割 | P（最大流最小割定理） |
| (9) 區間圖的最大獨立集 | P（貪婪：依結束時間排序） |
| (10) 2-CNF-SAT | P（蘊含圖找強連通元件） |
這份考卷的難點
- 第 V 題刻意把成對的問題放在一起：最長 vs 最短、負環 vs 正環、最大割 vs 最小割、2-SAT vs 3-SAT。「看起來對稱的兩個問題難度天差地遠」就是這題的全部重點 —— 最小割是 P、最大割是 NP-hard；最短環是 P、最長環是 NP-hard。
- 第 II 題的流網路要自己設計，不是給圖求流。關鍵是論文節點到 sink 的容量設成 2（每篇要兩位審稿人）、source 到審稿人的容量設成 4（每人最多四篇），方向與容量放錯就整題錯。
- 第 1-B 第 3 題若沒看出是整數除法，就要展開 837 層遞迴。禁用計算器下 5861 ÷ 7 還要手算。
- 第 1-B 第 5 題的 AOE 要同時算 earliest 與 latest。earliest 是正向取 max、latest 是反向取 min，X 的 earliest = 10 是走 S→T→X（6+4）而不是 S→X（8），這一步錯就後面全錯。
- 79% 的簡答且明訂「請於答案卷上作答，否則不予計分」——寫在試題卷上不計分，這種規定每年都要先確認。
準備建議
- 112 是三年獨立軟體卷裡申論最重的一份（79%），練習時要能把 AOE 的兩組時間、KMP 的失敗函數、流網路的容量標記完整畫出來
- P／NP-hard 的成對辨析（最長／最短、最大割／最小割、2-SAT／3-SAT）是中興連四年的考點，112 第 V 題、113 B-2 第 2 題、114 第 5 題、111 第 1-IV/V 題都在考
- row-major 陣列位址在 108 與 112 完全重複，中興會重複使用舊題，108–111 的資訊概論一定要看
- BST 的 probe sequence 判斷在 112、113 連兩年出現，練到能直接用區間收斂判斷
- 矩陣鏈乘法在 110（資訊概論第 9-B 題）與 112 都考，DP 表格要能手畫
- C 語言的鏈結串列與指標是中興軟體的固定班底（112 PART 2-C 三題、113 B-1 第 1、2 題），要能逐行追蹤指標