113 中正資工所軟體考點分析｜國立中正大學

全卷 23 題、題數最多的一年。C 程式輸出改用中文出題（含 printf 格式、指標、字串反轉），最後 6 題連續考遞迴式與圖論演算法的適用性判斷。

題型與配分

系所組別「資訊工程學系－甲組」，科目名稱：軟體設計，全卷 7 頁、23 題、100 分。

資料結構與運算式（4–9）

第 4 題（3%）｜由運算式建運算式樹，求 level-order 走訪。題目特別說明「同優先序的運算子由左至右依序計算」
第 5 題（3%）｜同一個運算式的 prefix form
第 6 題（3%）｜字串 AAABAAAABAAA（12 字元）的 KMP failure function 完整值
第 7 題（3%）｜給 in-order A,B,G,E,D,I,J,F,H,C 與 post-order G,E,J,I,H,F,D,C,B,A，求 pre-order（與 110 年第 4 題同一組序列）
第 8 題（2%）｜從頂點 A 跑 Dijkstra，頂點被選取的順序
第 9 題（2%）｜同一張圖的拓撲排序（字母序小的優先）

C／C++ 程式（10–14，共 45%）

第 10 題（10%，兩項輸出各 5%）｜num = 250，求 printf("%X\n", num)（十六進位 FA）與 printf("%.2f\n", (float)num)（250.00）
第 11 題（10%）｜陣列 {10,20,30,40,50}，只累加偶數索引的元素，求 sum（10+30+50 = 90）
第 12 題（5%）｜fun1 是字串反轉函式，"13579" 反轉成 "97531"，再 atoi 後取 % 10（答案 1）
第 13 題（5%）｜C++ 程式填空求最大真因數：(A) 2% 讀入數字的那一行 (B) 3% while 迴圈的條件 number % factor != 0
第 14 題（20%）｜C++ 名詞配對：function declaration／if-else／break／pass by value／local variable／void／float／cast／promotion／overloaded function 對應到 10 個描述。這是全卷配分最高的一題，也是純記憶分

演算法理論（15–23）

第 15–17 題（各 2%）｜三條遞迴式的解：T(n) = 3T(n/5) + n、T(n) = 4T(n/2) + n log n、T(n) = 4T(n/2) + n²
第 18 題（2%）｜是非：「有向圖的 s-t 最小割沒有多項式時間演算法」（假 —— max-flow min-cut 定理）
第 19 題（2%）｜是非：merge sort 的 Merge 與 quicksort 的 Partition 是否都是線性時間（真）
第 20 題（2%）｜是非：比較模型下找 n 個元素的中位數是否需要 Ω(n log n)（假 —— median of medians 是 O(n)）
第 21 題（2%）｜是非：MST 上 s 到 t 的路徑是否就是最短路徑（假 —— 經典陷阱）
第 22 題（3%）｜給一個流量指派，判斷是否已達最大流；若是要說明如何導出，若否要算出最大流
第 23 題（8%）｜給一張圖，判斷 8 種演算法各自能否用來求「使用者指定的頂點對」的最短路徑：Kruskal、Dijkstra、Ford-Fulkerson、Johnson、Bellman-Ford、Jarvis's march（凸包演算法，明顯不行）、Floyd-Warshall、Huffman（編碼演算法，不行）

第 14 題（20 分）的名詞配對看似簡單，但 10 個描述與 10 個名詞要一一對應，其中 promotion（char→int、float→double 的隱式轉換）與 cast（顯式轉換）很容易混淆。
第 10 題的 %X 與 %.2f 考的是 printf 格式化：250 的十六進位是 FA（大寫），而 (float)250 印成 250.00。
第 23 題的 8 個演算法中混入了 Jarvis's march（凸包）與 Huffman（編碼），要能認出它們與最短路徑無關。
第 21 題的「MST 路徑不是最短路徑」與成大 108、109 的是非題完全相同，是跨校共通陷阱。

C++ 名詞的精確定義（113 第 14 題佔 20 分）是中正最穩的得分區，pass by value、promotion、cast、overloaded function 這些要能精準對應
printf 的格式指定符（%X、%.2f、%d、%s）在中正 113 直接考輸出，建議整理一份
三條遞迴式（第 15–17 題）都可以用 Master theorem 直接解，是送分題
「MST 上的路徑不是最短路徑」「找中位數是 O(n) 不是 Ω(n log n)」是必記的兩個反直覺結論