110 中正資工所軟體考點分析
C++ 的 const 指標與虛擬函式佔 25%，是十年間最硬的物件導向題。第 3 題完整考 articulation point 的 dfn/low 演算法，第 5 題則刻意在負權圖上跑 Dijkstra。
題型與配分
系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，全卷 6 頁、15 題、100 分。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | C++ 的參考與 const 指標 | 10% |
| 2 | C++ 虛擬函式與多型 | 15% |
| 3 | Articulation point（dfn／low） | 9% |
| 4 | 由中序＋後序求前序 | 3% |
| 5 | 負權圖上的 Dijkstra | 8% |
| 6 | KMP failure function | 5% |
| 7–8 | 代入法解遞迴式 | 8% |
| 9 | 排序下界的證明 | 3% |
| 10 | 最佳子結構與區域最佳 | 3% |
| 11 | Johnson 演算法在 DAG 上 | 5% |
| 12 | Knapsack 的三個性質 | 6% |
| 13 | 程式除錯 | 10% |
| 14 | 手寫 BST 搜尋 | 10% |
| 15 | 字串函式說明 | 5% |
逐題考點
C++ 部分（1、2、13、14、15，共 50%）
- 第 1 題（10%）｜1.1 4%｜
int &* a1（指向參考的指標，不合法）與int *& a2（指標的參考，合法）能否編譯 1.2 6%｜對const int* cip，判斷const int** b1 = &cip、int* const * b2 = &cip、int ** const b3 = &cip三者是可編譯／語法錯誤／違反 const 性。這是 C++ 最容易搞混的地方 - 第 2 題（15%）｜三層繼承 A → B → C，且
f1在 A 非虛擬、B 覆寫、C 宣告 virtual；f2在 A 是 virtual、C 覆寫： - (a) 3%｜
A* ap = new B; delete ap;會依序呼叫哪些函式（含建構子與解構子）。關鍵：A 的解構子非虛擬，所以 B 的解構子不會被呼叫 - (b) 12%｜六種指標呼叫（甲～己）各自的輸出，或是 compiler error／runtime error。考的是靜態繫結 vs 動態繫結
- 第 13 題（10%）｜程式除錯並解釋修正理由：
scanf("%d", X)少了&、X & 2 == 0的運算子優先序錯誤（==先於&），且判斷偶數應該用X % 2或X & 1 - 第 14 題（10%）｜手寫 BST 搜尋函式（key 是字串），找到回傳節點位址、否則回傳 NULL，要先宣告樹節點的資料結構
- 第 15 題（5%）｜說明
strcmp()與strdup()的功能、參數型別與回傳值型別
資料結構與演算法部分（3–12，共 50%）
- 第 3 題（9%，4 小題）｜Articulation point 的完整流程：從 A 開始做 DFS（字母序優先），問 (3.1) DFS 生成樹的邊 (3.2) 各頂點的 dfn (3.3) 各頂點的 low 值 (3.4) 哪些是關節點。四小題連動，是全卷最需要完整追蹤的一題
- 第 4 題（3%）｜給 in-order 與 post-order，求 pre-order
- 第 5 題（8%，3 小題）｜給一張含負權邊的有向圖跑 Dijkstra：(5.1) 頂點被選取的順序 (5.2) 各點的最短成本 (5.3) A 到 D 的路徑。這題的重點是「Dijkstra 在負權圖上會給出錯誤答案」 —— 要照演算法機械地跑，而不是算真正的最短路徑
- 第 6 題（5%）｜給 failure function 的定義與字串
acacabacacabacacac（18 字元），求 f(0)、f(3)、f(5)、f(10)、f(13)、f(17) - 第 7 題（4%）｜用代入法求 T(n) = T(n/4) + T(n/5) + 6n 的緊上界（O(n)）
- 第 8 題（4%）｜用代入法求 T(n) = 4T(n/2) + n2 的緊下界（Ω(n2 log n)）
- 第 9 題（3%）｜證明或舉反例：是否每個比較式排序都是 Ω(n lg n)（counting sort 不是比較式排序，但題目問的是比較式 —— 要小心陳述）
- 第 10 題（3%）｜若 DP 問題滿足最佳子結構，區域最佳解是否就是全域最佳解？題目明訂「只答 yes/no 不給分」
- 第 11 題（5%）｜在有負權邊的 DAG 上，Johnson 的重新配權是否比 Bellman-Ford 更快？（不會 —— DAG 上直接拓撲排序就是 O(V+E)）。同樣「只答 yes/no 不給分」
- 第 12 題（6%）｜當 w1 ≥ w2 ≥ … ≥ w_k 且 v1 ≤ v2 ≤ … ≤ v_k 時，fractional 與 0-1 knapsack 各自是否具備：(1) 最佳子結構 (2) 貪婪選擇性質 (3) 重疊子問題
這份考卷的難點
- 第 2 題（15 分）的 C++ 多型是全卷最硬的一題：要同時掌握「非虛擬函式的靜態繫結」「虛擬函式的動態繫結」「基底類別解構子非虛擬的後果」「透過 B* 無法呼叫 C 才有的函式」。
- 第 3 題的 dfn／low 四小題連動，DFS 走訪順序錯一步，後面三小題全錯。
- 第 5 題刻意在負權圖跑 Dijkstra —— 要照演算法跑出「錯誤」的答案，而不是算正確的最短路徑。很多人會下意識修正。
- 第 10、11 題明訂「只答 yes/no 不給分」，必須寫出完整論證。
準備建議
- C++ 的 const 指標與參考（
const int*/int* const/int**）建議畫表格整理，110 年考了 10 分 - 虛擬函式的繫結規則是中正的重點，「指標型別決定能呼叫哪些函式、物件型別決定虛擬函式呼叫誰」要非常清楚
- Articulation point 的 dfn／low 演算法要能完整手動跑一次，這是圖論裡最容易被跳過但中正會考的主題
- 代入法（substitution method）要練，中正 110 一次考了兩題（上界與下界），而且指定方法
- 中正很愛問「只答 yes/no 不給分」的論證題（第 10、11 題），練習用兩三句話講清楚理由