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

題型與配分

全卷 5 頁、15 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。第 1、2、6–10 題題目標明複選（Select multiple correct answers），第 3、4、5 題為單選（Choose one best answer）。卷面沒有寫明複選題的計分方式。

第 11–15 題是 C/C++ 題，合計 50 分。

逐題考點

• 第 1 題（5%）｜複選：100 個節點的 AVL tree 可能的高度（單一節點的高度為 1，題目給 log₁₀2 ≈ 0.3010），選項 5 到 10
• 第 2 題（5%）｜複選：2-3-4 tree 是否為 order 5 的 B-tree、red-black tree 是否為 2-3 tree 的 binary tree 形式、B-tree 的外部節點是否在同一層、order m 的 B-tree 中非根內部節點的子節點數下界
• 第 3 題（5%）｜單選：整數 array {52, 21, 40, 33, 88, 57, 46, 71} 用 O(n) 的 bottom-up 方法建成 max heap 後的樣子
• 第 4 題（5%）｜單選：依序插入 40, 60, 55, 15, 20, 5, 25, 30 建 red-black tree，紅色節點的數值總和
• 第 5 題（5%）｜單選：整數 array {52, 21, 40, 88, 33, 57, 46, 71} 用 two-pointer 版的 quicksort，把第一個 pivot（52）移到正確位置後 array 的樣子，兩個 pointer 分別從 21 與 71 開始
• 第 6 題（5%）｜複選：(a) 有 negative-weight edge 但無 negative cycle 的 dense graph 上，Johnson 是否比 Floyd-Warshall 快；(b) NP 是否包含可在多項式時間解決的問題；(c) halting problem 是否為 NP-hard；(d) Ford-Fulkerson 能否用來找所給圖的 maximum matching；(e) 該圖的 maximum matching 大小是否為 4
• 第 7 題（5%）｜複選：insertion sort 是否 in-place、unweighted graph 的 longest simple path 能否用 divide and conquer 解、recursion tree 是否為 full binary tree、quicksort 是否不是漸進最佳、程式碼行數較少的演算法時間複雜度是否較低
• 第 8 題（5%）｜複選：五個 recurrence 及其漸近上界的敘述。(a) T(n) = 16T(n/4) + n²。(b) T(n) = 4T(n/5) + n^4/3。(c) T(n) = T(n/4) + T(n/2) + n²。(d) T(n) = 2T(⁴√n) + √(log n)。(e) T(n) = T(n−1) + 1/n
• 第 9 題（5%）｜複選：給一張分成 Stage 0 到 Stage 3 的圖，從 V₀ 到 V₃ 找 shortest path，判斷 greedy 演算法是否適用、DP 是否適用、分階段看是否具有 optimal substructure，以及 V₀ 到 V₃ 的最小權重
• 第 10 題（5%）｜複選：給一張有六個頂點（A–F）的 directed graph，判斷 Kruskal 是否適用、Floyd-Warshall 是否比 Bellman-Ford 耗時、以 A 為來源 D 為匯點執行 Edmonds-Karp 的結果、topological sort 是否適用、B、C、E、F 是否構成 strongly connected component
• 第 11 題（5%）｜int num1 = 025; int num2 = num1; printf("%X\n", num2); 的輸出
• 第 12 題（10%）｜modifyValues(const int *ptr1, int *const ptr2) 對 ptr2 所指的值乘 2，主程式用 p1、p2 呼叫後 printf 輸出 a 與 b
• 第 13 題（10%）｜unsigned int a = 0xFFFF0101，轉成 unsigned char b、char *c = (char *)&a、unsigned int *p，執行 *p <<= 6; 後輸出 b 與 *c（十六進位）
• 第 14 題（9%）｜把 overloading（2%）、coercion（2%）、aliasing（2%）、polymorphism（3%）四個詞與四段描述配對
• 第 15 題（16%）｜類別 B 有兩個 virtual function m(int) 與 m(double)，類別 D inheritance B 並只覆寫 m(int)。主程式用 D*、B*、B 物件與 B& 呼叫 m(1)、m(2.0)，問 Line A 到 Line H 共八行各印出什麼，每行 2 分

作答時要注意的地方

1. 第 1、2、6 至 10 題可以選多個答案，第 3、4、5 題只選一個最佳答案。
2. 第 11、12、13、15 題要寫出程式執行後螢幕上的輸出，第 14 題每個詞填 1 到 4 的數字。
3. 第 5 題兩個 pointer 分別從 21 與 71 開始。
4. 第 1 題題目提供 log₁₀2 ≈ 0.3010 作為提示。

準備方向

• AVL、B-tree 與 red-black tree 的性質（114 第 1、2、4 題），109 第 10 題、111 第 10 題、112 第 9 題、113 第 1–3 題也有 balanced tree。
• 2-3-4 tree 與 B-tree 的關係（114 第 2 題），四個敘述裡有三個與成大 112 軟體第 6 題相同。
• Max heap 的 bottom-up 建構（114 第 3 題），112 第 9(2) 題也有。
• Quicksort 的逐步動作（114 第 5 題），109 第 12 題、115 第 16 題也有。
• P、NP、NP-hard 與 reduction（114 第 6 題），108 第 7 題、109 第 13(5) 題也有。
• recurrence 的解（114 第 8 題），106 第 9 題、110 第 7、8 題、113 第 15–17 題也有。
• max flow 與 matching（114 第 6、10 題），109、112、113、115 也有 max flow。
• const pointer（114 第 12 題），110 第 1.2 題、112 第 6 題也有。
• 位元運算與 printf 格式（114 第 11、13 題），111 第 4 題、113 第 10 題、115 第 5 題也有。
• virtual function 與函式隱藏（114 第 15 題），110 第 2 題也有 virtual function。
• 名詞配對（114 第 14 題），111 第 7 題、113 第 14 題也有。