109 中正資工所軟體考點分析
程式題比重達 45%（除錯 20 分＋手寫程式 25 分），要求實際寫出 linked list 插入、swap 與讀檔程式。第 13 題的六個是非題全是演算法理論。
題型與配分
系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，第 2 節，全卷 4 頁、14 題、100 分。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1–3 | C++ 類別是非題 | 5% |
| 4 | Bubble sort 程式除錯 | 20% |
| 5 | 手寫 linked list 插入 | 10% |
| 6 | 手寫 swap 函式 | 5% |
| 7 | 手寫讀檔求最長行 | 10% |
| 8 | Infix 轉 postfix | 4% |
| 9 | 二元樹的個數 | 4% |
| 10 | AVL 與紅黑樹 | 8% |
| 11 | KMP failure 函式 | 4% |
| 12 | Quick sort 逐趟 | 5% |
| 13 | 演算法是非題（6 題） | 18% |
| 14 | 最大流與瓶頸邊 | 7% |
手寫程式與除錯合計 45 分，是中正十年間比重最高的一年。
逐題考點
- 第 1–3 題（5%）｜C++ 類別的是非題：一個類別能否有多個衍生類別（真）、能否有多個解構子（假）、未定義建構子時編譯器是否提供預設建構子（真）
- 第 4 題（20%）｜給一支有大量 bug 的 bubble sort 程式，要指出並修正所有錯誤，且「盡可能少改」。錯誤包括：
SwapIntegers傳值而非傳參考、temp = b應為b = temp、迴圈i++應為i--、比較與索引i+1應為j+1、vector缺型別參數、intVector(intArray, intArray+9)少一個元素、BubbleSort(&intVector)多了取址、i <= size()越界、cout >>應為<<。這是全卷配分最高的一題 - 第 5 題（10%）｜手寫 linked list 的插入函式（節點有 32 bytes 的 name 欄位與 link 欄位），新節點插到最前面，回傳 head 指標。要自己宣告資料結構
- 第 6 題（5%）｜補完
swap()使 main 中的 x、y 真的交換 —— 考傳指標（或傳參考） - 第 7 題（10%）｜手寫程式從 stdin 讀資料並輸出最長的一行，題目指定必須用
fgets()，多行等長時輸出第一行 - 第 8 題（4%）｜兩個 infix 轉 postfix
- 第 9 題（4%）｜2、3、4、5 個節點的相異二元樹個數（Catalan number：2, 5, 14, 42）
- 第 10 題（8%）｜依序插入 50, 10, 80, 90, 70, 60, 65, 62 到 AVL 樹與紅黑樹，各畫出最終結果
- 第 11 題（4%）｜給 KMP 的
fail()程式，求abaabaab與abcababcabc的 failure array。注意這個版本的 failure[0] = −1，與標準 π 函數不同 - 第 12 題（5%）｜對 55, 45, 25, 35, 85, 95, 65, 75, 105, 15 做 quick sort（永遠取子串列第一個元素當 pivot），寫出每一趟的數列
- 第 13 題（18%，6 小題各 3%）｜是非題，答錯要寫出正確的部分：
- (1) Counting Sort 的執行時間是否為輸入大小 n 的多項式（假 —— 與數值範圍有關，是 pseudo-polynomial）
- (2) Heap Sort 是否為多項式（真）
- (3) 用 adjacency matrix 表示時 DFS 是否 Θ(V2)（真）
- (4) 任何 DP 是否都能轉成 DAG 上的最短路徑
- (5) X 可歸約到已知 NP-hard 問題，X 是否必為 NP-hard（假 —— 方向錯了）
- (6) Ford-Fulkerson 用 DFS 找增廣路徑能否降低複雜度（假 —— 用 BFS 才是 Edmonds-Karp）
- 第 14 題（7%）｜給流網路：(a) 3% 求最大流與最小割 (b) 2% 畫出殘餘圖，標出從 S 可達的頂點與可達 T 的頂點 (c) 2% 列出所有瓶頸邊（bottleneck edge） —— 增加其容量會讓最大流增加的邊
這份考卷的難點
- 第 4 題（20 分）的除錯有將近十個 bug，而且要求「盡可能少改」—— 找不全就大量失分。
- 第 5、7 題要真的手寫完整程式（含資料結構宣告、
fgets的用法、緩衝區處理），紙筆寫 C 對很多人是挑戰。 - 第 13(5) 的歸約方向是最經典的陷阱：要證明 X 是 NP-hard，必須是「已知 NP-hard 歸約到 X」，而不是反過來。
- 第 14(c) 的瓶頸邊不只是最小割上的邊 —— 要同時考慮所有最小割，一條邊要在每一個最小割中才是瓶頸邊。
準備建議
- 手寫 C 程式的能力是中正的硬需求：linked list 操作、字串處理、
fgets／strcpy／指標，要能在紙上寫對 - 程式除錯題（109 第 4 題 20 分）建議找有 bug 的程式碼練習，訓練「逐行比對規格」的習慣
- 歸約方向（109 第 13(5) 題）在中正、成大、台大都反覆出現，畫一張圖記清楚
- Catalan number（109 第 9 題）與 KMP failure function（109 第 11 題）是跨校高頻題