112 中正資工所軟體考點分析
C++ 部分改為「全對才給分」的複選題（this 指標、const、建構子），資料結構部分則是標準的 DFS／heapify／AVL／紅黑樹四連發。
題型與配分
系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，全卷 5 頁、12 題、100 分。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1–5 | C++ 基礎 | 約 32% |
| 6 | this 指標與 const（全對才給分） | 12% |
| 7 | 建構子（全對才給分） | 6% |
| 8 | 資料結構是非題（5 題） | 10% |
| 9 | 資料結構單選（5 題） | 15% |
| 10 | 排序性質是非題 | 8% |
| 11 | 負權圖的 yes/no 論證 | 11% |
| 12 | Ford-Fulkerson | 6% |
第 6、7 題明訂「Check all that apply. NO partial credit is given.」 —— 複選題全對才給分，共 18 分。
逐題考點
C++ 部分（1–7）
- 第 5 題｜哪些是合法的宣告（
int i;、int i=1;、int foo(int);、int foo(int i);、typedef string my_string;） - 第 6 題（12%，4 小題各 3%，全對才給分）
- 甲｜關於
this指標：是否為 reference、能否在方法內改變它指向的對象、是否指向呼叫該方法的實例 - 乙｜對類別
Thing，隱含的this的型別是什麼（答案取決於成員函式是否為 const） - 丙｜關於 const 變數：能否透過關聯的參考賦值、是否必須在宣告時初始化、能否對非 const 變數的參考加上 const
- 丁｜哪些寫法會真的複製字串（
const string &x = y不複製、string *x = &y不複製 …） - 第 7 題（6%，2 小題各 3%，全對才給分）｜建構子的性質（何時被呼叫、能否多載、是否只在
new時呼叫）、建構子的回傳型別（沒有回傳值）
資料結構與演算法部分（8–12）
- 第 8 題（10%，5 小題各 2%）｜是非題：
- (1) 九層二元樹的最大節點數是否為 511（真，29−1）
- (2) f1 = O(g) 且 f2 = O(g) 是否推出 f1 = f2（假）
- (3) 比較式排序的最壞下界是否為 Ω(n log n)（真）
- (4) bi-connected graph 是否為「有兩個關節點的連通圖」（假 —— 是沒有關節點）
- (5) 每棵二元樹是否都能由 pre-order 與 post-order 唯一決定（假）
- 第 9 題（15%，5 小題各 3%）｜
- (1) 從節點 1 開始的 DFS 走訪序列（小 ID 優先）
- (2)
{19, 5, 27, 3, 16, 11, 69, 18}用 bottom-up O(n) heapify 成 max heap 的結果 - (3) 依序插入 12 個整數到 AVL 樹的結果
- (4) 8 個節點的相異二元樹個數（Catalan C8 = 1430）
- (5) 依序插入 50, 10, 80, 90, 70, 60, 65, 62 到紅黑樹的結果（與 109 年第 10 題同一組數字）
- 第 10 題（8%，4 小題各 2%）｜排序性質是非題：quicksort 是否漸進最佳、最不平衡分割時的決策樹是否為 full binary tree、insertion sort 是否 in-place 但不穩定（假 —— 它是穩定的）、counting sort 是否同時穩定且 in-place（假 —— 穩定但不 in-place）
- 第 11 題（11%）｜含負權邊的圖，yes/no 並寫出理由（「單純答 yes/no 不給分」）：
- (a) 2%｜能否用 Dijkstra 求 a 到 d 的最短路徑
- (b) 2%｜若所有邊權為 1，能否用 BFS
- (c) 2%｜若所有邊權為 1，能否做拓撲排序
- (d) 5%｜重新配權使所有邊非負
- 第 12 題（6%）｜對給定的圖套用 Ford-Fulkerson，寫出輸出與推導
這份考卷的難點
- 第 6、7 題合計 18 分全對才給分，而且考的是 C++ 最細的角落：
this的型別（Thing* const或const Thing* const，取決於成員函式是否為 const）、哪些寫法會複製字串。 - 第 10(c)(d) 的排序性質是常見誤解：insertion sort 是穩定的、counting sort 穩定但不是 in-place。
- 第 8(4) 的 bi-connected graph 定義寫反了 —— 雙連通圖是沒有關節點的圖。
- 第 11 題明訂「單純答 yes/no 不給分」，11 分全靠論證。
準備建議
- C++ 的
this指標型別與 const 成員函式的關係要弄清楚：非 const 成員函式的 this 是Thing* const，const 成員函式是const Thing* const - 排序演算法的四個性質表（時間複雜度／穩定性／in-place／漸進最佳）建議整理成一張表，中正 108、109、110、111、112 每年都考
- 紅黑樹插入同一組數字（50, 10, 80, 90, 70, 60, 65, 62）在 109、112 考了兩次 —— 中正也有重複出題的習慣
- 負權圖的處理（Dijkstra 失效、重新配權）是中正 110、111、112 連三年的共同主題