110 中正資工所考古題詳解｜軟體考點分析

題型與配分

全卷 6 頁、15 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。

第 1、2、13、14、15 題是 C/C++ 題，合計 50 分。

逐題考點

• 第 1.1 題（4%）｜判斷 int &* a1; 與 int *& a2; 兩行能不能編譯，每行 2 分
• 第 1.2 題（6%）｜const int* cip 之下，const int** b1 = &cip;、int* const * b2 = &cip;、int ** const b3 = &cip; 三行的結果是 Compiles、Invalid syntax 或 Violates const-ness，每行 2 分
• 第 2(a) 題（3%）｜類別 A、B、C 的 inheritance 架構（A 有 f1、virtual 的 f2，B 有 f1、virtual 的 f3，C 有標明 virtual 的 f1 與沒有標明 virtual 的 f2）。執行 A* ap = new B; delete ap; 時，依序呼叫了哪些函式，含 constructor 與 destructor，要寫出完整的 Class::Function 名稱
• 第 2(b) 題（12%）｜給兩個物件 B b、C c 與三個 pointer A* ap1 = &c、B* bp1 = &b、B* bp2 = &c，六個呼叫（bp1->f1()、bp1->f2()、bp2->f2()、bp2->f3()、ap1->f1()、ap1->f3()）各自輸出什麼，或是 compiler error、runtime error，每個 2 分
• 第 3 題（9%）｜給一張七個頂點（A–G）的圖，從頂點 A 開始 DFS，同層選字母順序最小的先走。3.1（2%）深度優先 spanning tree 的邊；3.2（2%）各頂點的 dfn；3.3（3%）各頂點的 low；3.4（2%）articulation point
• 第 4 題（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），重建 binary tree 並寫出 pre-order
• 第 5 題（8%）｜給一張含 negative-weight edge 的 directed graph（頂點 A–G）。5.1（3%）從 A 跑 Dijkstra 的頂點選取順序；5.2（3%）各頂點的 shortest path 成本；5.3（2%）A 到 D 的 shortest path
• 第 6 題（5%）｜給 KMP 的 failure function 定義與長度 18 的字串 acacabacacabacacac，求 f(0)、f(3)、f(5)、f(10)、f(13)、f(17)
• 第 7 題（4%）｜用 substitution method 找 T(n) = T(n/4) + T(n/5) + 6n 的漸近上界
• 第 8 題（4%）｜用 substitution method 找 T(n) = 4T(n/2) + n² 的漸近下界
• 第 9 題（3%）｜證明或舉反例：每個 comparison sort 演算法的時間複雜度都是 Ω(n lg n)
• 第 10 題（3%）｜問題具有 optimal substructure 時，區域最佳解是否也是全域最佳解。只答 yes 或 no 不給分
• 第 11 題（5%）｜G 是含 negative-weight edge 的 DAG，論證 Johnson 的 reweighting 方法在 single-source shortest path 上是否比 Bellman-Ford 快。只答 yes 或 no 不給分
• 第 12 題（6%）｜k 個物品，重量 w₁ > w₂ > … > w_k，價值 v₁ < v₂ < … < v_k。判斷 (a) fractional knapsack 與 (b) 0-1 knapsack 各有沒有 (1) optimal substructure、(2) greedy choice、(3) overlapping subproblems
• 第 13 題（10%）｜修正一段讀入整數、判斷奇偶並輸出的 C 程式，並說明修改的理由
• 第 14 題（10%）｜手寫在 BST 中找 key 的函式，找到回傳節點位址，否則回傳 NULL。節點含字串 key 與兩個 pointer，要先宣告節點的資料結構
• 第 15 題（5%）｜說明兩個字串函式的功能、參數型別與回傳型別。(a) 2%：strcmp()。(b) 3%：strdup()

作答時要注意的地方

1. 第 10、11 題明訂只答 yes 或 no 不給分，要寫理由。
2. 第 3、4、5、6 題是選擇題，第 3.1–3.4 題與第 5.1–5.3 題的選項有 (f) 或 (e) none of the above。
3. 第 2(b) 的輸出可能是 compiler error 或 runtime error。
4. 第 13 題要說明修改的理由，第 14 題要先宣告節點的資料結構。

準備方向

• const pointer（110 第 1.2 題），112 第 6 題、114 第 12 題也有。
• virtual function 與 dynamic binding（110 第 2 題），108 第 1.8 題考 pure virtual，114 第 15 題也有。
• articulation point 的 dfn 與 low（110 第 3 題），111 第 16 題、115 第 17–19 題也有。
• 由 in-order 與 post-order 重建 binary tree（110 第 4 題），113 第 7 題、115 第 23 題用同一組序列。
• Dijkstra 的頂點順序與 negative-weight edge（110 第 5 題），107、108、111、113、115 也有 Dijkstra 的頂點順序。
• Johnson 與 reweighting（110 第 11 題），107 第 12 題、108 第 11 題、111 第 19 題、112 第 11 題也有。
• KMP failure function（110 第 6 題），109 第 11 題、113 第 6 題、115 第 22 題也有。
• recurrence（110 第 7、8 題要求用 substitution method），113 第 15–17 題、114 第 8 題也有 recurrence 的解。
• 手寫與除錯 C 程式（110 第 13、14 題），106 第 13 題手寫 BST，108 第 13 題、109 第 4–7 題、111 第 6 題、115 第 25 題也有。