111 中正資工所軟體考點分析
全卷 20 題、涵蓋面最廣的一年。C++ 觀念配對與字串型別比較佔 25%，圖論部分連考 articulation point、AOE critical path、Floyd-Warshall 與 Johnson。
題型與配分
系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，全卷 6 頁、20 題、100 分。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1–5 | C 基礎單選 | 10% |
| 6 | 手寫反轉整數的程式 | 15% |
| 7 | C++ 名詞配對 | 14% |
| 8 | char\* 與 string 的五項比較 | 10% |
| 9 | C++ template | 1% |
| 10–15 | 資料結構單選 | 17% |
| 16 | Articulation point | 4% |
| 17 | AOE critical path＋Dijkstra | 4% |
| 18 | 排序是否漸進最佳 | 4% |
| 19 | 負權圖的最短路徑（4 小題） | 17% |
| 20 | 三元 Huffman code | 4% |
逐題考點
C/C++ 部分（1–9，共 52%）
- 第 1–5 題（各 2%）｜2000 元素二分搜尋的最大比較次數（11）、
sizeof(r)/sizeof(int)求陣列元素數、b[3]的等價指標寫法*(bPtr+3)、x <<= 1; x >>= 1;的效果（最左位元被清成 0，因為算術右移會補符號）、遞迴階乘mystery(4)的回傳值（24） - 第 6 題（15%）｜手寫 C 程式反轉 32-bit 整數的位數，溢位時回傳 0。要處理負數、尾端 0 與溢位偵測（這是 LeetCode 7）
- 第 7 題（14%）｜C++ 名詞配對：constructor／destructor／data member／member function／private／public／recursive 對應到 9 個描述
- 第 8 題（10%）｜**動態配置的 char\* 與 string 物件的五項性質比較：能否含 null 字元、記憶體是否自動釋放、內容能否修改、能否 O(1) 存取第 k 個字元、
=是否做深拷貝** - 第 9 題（1%）｜C++ template 的用途（讓同一份泛型程式碼處理不同型別的資料）
資料結構與演算法部分（10–20，共 48%）
- 第 10 題（3%）｜依序插入 51, 26, 11, 6, 8, 4, 7 建 AVL 樹，以陣列表示時的內容
- 第 11 題（3%）｜給 post-order 序列與各節點的子節點個數，問樹是否唯一、pre-order 為何
- 第 12 題（3%）｜10 個數字建 max-heap 後，heap sort 輸出前兩大之後的陣列狀態
- 第 13 題（2%）｜表大小 11、division method、linear probing，插入 25, 42, 96, 101, 102, 162, 197, 201 後的表格
- 第 14 題（3%）｜給一般樹的括號表示法
(A(B(E(K,L),F), C(G), D(H(M),I,J)))，轉成二元樹（left-child right-sibling）後的 post-order - 第 15 題（3%）｜一長串運算式的 prefix form
- 第 16 題（4%，3 小題）｜從頂點 B 開始的 DFS 生成樹、low 值、articulation point（與 110 年第 3 題同型）
- 第 17 題（4%，2 小題）｜(17.1) AOE network 的 critical path (17.2) 同一張圖跑 Dijkstra 時頂點被選取的順序
- 第 18 題（4%）｜論證 quicksort 與 mergesort 是否為漸進最佳，要寫出理由
- 第 19 題（17%，4 小題）｜含負權邊的圖：
- (a) 2%｜指定源點跑 Dijkstra 會輸出什麼？寫出理由
- (b) 4%｜重新配權（reweight）這張圖
- (c) 8%｜用 Floyd-Warshall 求出距離矩陣與前驅矩陣，要寫出推導
- (d) 3%｜給定圖 G，如何判斷 Floyd-Warshall 與 Johnson 哪個理論上更快（比較 O(V3) 與 O(V2log V + VE)，關鍵在圖的稠密度）
- 第 20 題（4%）｜推導 7 個符號的最佳三元（ternary）Huffman code。注意三元 Huffman 要先補虛擬符號使 (n−1) mod 2 = 0
這份考卷的難點
- 第 19 題（17 分）是全卷核心，一次串起「Dijkstra 為何在負權圖失效 → 重新配權 → Floyd-Warshall 的完整矩陣 → Johnson 與 Floyd 的取捨」，四小題層層遞進。
- 第 6 題要在紙上寫出能處理溢位的整數反轉，邊界條件（負數、尾端 0、超出 int 範圍）都要照顧到。
- 第 20 題的三元 Huffman 需要知道「符號數不足時要補機率為 0 的虛擬符號」這個細節，直接用二元的作法會錯。
- 第 8 題的五項比較很細，例如「string 的
=是深拷貝、char\* 的=只是複製指標」。
準備建議
- 中正連兩年考 articulation point 的 dfn／low（110 第 3 題、111 第 16 題），這個演算法要練到能機械化執行
- 負權圖的處理三連（Dijkstra 失效 → 重新配權 → Floyd/Johnson）是中正 110、111 的共同主題
- 三元 Huffman code 是少見但會考的變形，「補虛擬符號」的規則要記
- 手寫程式題每年都有（109 的 linked list／讀檔、111 的整數反轉），紙筆寫 C 的能力必須練