108 中正資工所軟體考點分析
科目是「軟體設計」，C++ 語法佔 25%、資料結構與演算法佔 75%。第 8 題是全卷唯一設倒扣的小題（答錯扣 1 分）。
題型與配分
系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，第 2 節，全卷 6 頁、14 題、100 分。
中正的軟體考科叫「軟體設計」，真的會考 C/C++ 語法。 這和台清交成的「資料結構與演算法」不同 —— 第 1 題（25%）與第 12–14 題（25%）合計 50% 是程式語言與程式除錯，只準備資料結構會失去一半分數。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | C++ 語法單選（11 小題） | 25% |
| 2 | BST 加 leftSize 欄位求第 k 小 | 8% |
| 3 | Max heap 與 heap sort | 6% |
| 4 | Dijkstra 與 BFS | 4% |
| 5 | Hash（linear probing） | 2% |
| 6 | k-ary tree 的節點數上界＋證明 | 5% |
| 7 | NP 理論是非題 | 6% |
| 8 | 穩定排序（有倒扣） | 5% |
| 9 | 排序是否漸進最佳 | 8% |
| 10–11 | 圖的表示法與 Johnson 演算法 | 6% |
| 12 | 程式輸出 | 10% |
| 13 | 程式除錯 | 7% |
| 14 | 陣列宣告錯誤與指標運算 | 8% |
逐題考點
第 1 題｜C++ 語法（25%，11 小題）
cout 是什麼（物件）、bool 的正確用法、private 成員的存取範圍、哪些函式能真正遞增傳入的 double（考 reference 與 pointer 的差別）、new int[100] 對應的 delete[]、預設引數的合法宣告順序、copy constructor 何時被呼叫、pure virtual function 的寫法、cin >> i >> d >> c >> str 搭配輸入 3040 King Dome 的結果、reference 參數的別名效應、ifstream 讀取失敗的偵測方式
第 2–6 題｜資料結構
- 第 2 題（8%）｜BST 節點多一個 leftSize 欄位（左子樹節點數 +1），依序插入 65, 50, 80, 70, 60, 62, 90, 10：(a) 3% 畫出樹並標出每個節點的 leftSize (b) 5% 說明如何用 leftSize 在 O(log n) 找第 k 小的元素。這就是 order statistic tree
- 第 3 題（6%）｜依序插入 7, 16, 49, 82, 5, 31, 6, 2, 44 建 max heap：(a) 插入完成後的狀態 (b) heap sort 第 5 次迭代後的堆積與已排序陣列
- 第 4 題（4%）｜給邊權有向圖：(a) 2% Dijkstra 處理頂點的順序 (b) 2% 從頂點 0 的 BFS（優先選最小邊）
- 第 5 題（2%）｜17 格雜湊表、h(k) = k % 17、linear probing，依序插入 6, 12, 34, 29, 28, 11, 23, 7, 0, 33，填出最終表格
- 第 6 題（5%）｜(a) 2% 高度 h 的 k 元樹最多有幾個節點 (b) 3% 證明你的答案
第 7–11 題｜演算法理論
- 第 7 題（6%）｜三個是非題，答錯要寫出正確的部分，單純否定不給分：任意多條序列的 LCS 是否為 P 問題（否，是 NP-hard）、非負權圖上的最長簡單路徑是否 NP-hard、BFS 能否走遍所有邊並分類
- 第 8 題（5%）｜哪些排序是穩定的（counting／quick／merge／insertion／heap）。本題答錯每個選項倒扣 1 分，最多扣到 5 分 —— 這是全卷唯一有倒扣的地方
- 第 9 題（8%）｜bubble／quick／merge／heap sort 各自是否為漸進最佳（asymptotically optimal）
- 第 10 題（1%）｜給一個含負權的矩陣，問這是什麼圖的表示法
- 第 11 題（5%）｜承上，Johnson 演算法對這張圖做了什麼、結果為何，要寫出過程
第 12–14 題｜C 程式（25%）
- 第 12 題（10%）｜(a) 3% dangling else 的陷阱（
if...if...else的 else 配對誰） (b) 7%sizeof(struct node)的結構對齊與指標複製後的字串輸出 - 第 13 題（7%）｜修正程式錯誤，使輸出為
AppleAppleApple。問題包括：q未配置記憶體、text是陣列不能做text +=、strcpy應改為strcat、for 迴圈用逗號而非分號 - 第 14 題（8%）｜(a) 2% 指出陣列宣告的錯誤（用
(...)而非{...}） (b) 6% 迴圈執行後 A 的最終內容（char *p = A的型別不符會影響指標算術）
這份考卷的難點
- C/C++ 語法佔 50%，而且考得很細：copy constructor 的三種觸發時機、pure virtual function 的語法、預設引數的順序規則、
cin >>遇到空白的行為、結構對齊。 - 第 13 題的除錯要同時抓出四個以上的錯誤（記憶體未配置、陣列不可賦值、strcpy vs strcat、逗號 vs 分號）。
- 第 8 題有倒扣，而且是「每個錯誤選項扣 1 分」，五個選項全猜等於期望值為負。
- 第 11 題的 Johnson 演算法要寫出完整過程（加超級源點、Bellman-Ford 求 h、重新配權），只寫名字不夠。
準備建議
- 中正的「軟體設計」必須準備 C/C++ 語法，而且是物件導向（class、繼承、虛擬函式、copy constructor）與指標記憶體兩大塊
- 程式除錯題是中正的招牌（108 第 13 題、109 第 4 題、110 以後每年都有），建議實際寫過 C 程式才抓得到
- Order statistic tree（leftSize 欄位）在中正 108 出現，台大 115 第 20 題也考過，是跨校主題
- 排序的穩定性與漸進最佳性（第 8、9 題共 13 分）是純記憶分，務必背熟