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

題型與配分

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

第 1–7 題是 C/C++ 題，合計 50 分，其中除錯 20 分、手寫程式 25 分。

逐題考點

• 第 1 題（1%）｜是非題：一個類別是否可以有多個 derived class
• 第 2 題（2%）｜是非題：一個類別是否可以有多個 destructor
• 第 3 題（2%）｜是非題：C++ 類別沒有寫 constructor 時，編譯器是否自動提供預設 constructor
• 第 4 題（20%）｜一支排序 10 個整數的 bubble sort 程式（使用 vector、SwapIntegers、BubbleSort，共 25 行），要求指出並修正所有錯誤，盡量少改，可以插入或刪除行，不要整行重寫
• 第 5 題（10%）｜手寫 linked list 的插入函式：節點有最多 32 bytes 的 name 欄位與 link 欄位，要自己宣告資料結構，新節點成為第一個節點，回傳 head pointer
• 第 6 題（5%）｜補完 swap 函式與呼叫，使 x = 10、y = 20 呼叫後輸出 x=20, y=10
• 第 7 題（10%）｜手寫程式從 stdin 讀資料並輸出最長的一行，指定要用 fgets()，有多行同樣長時輸出第一行
• 第 8 題（4%）｜infix 轉 postfix。(a) 2%：a*(b+c/d)-e。(b) 2%：(a+c)*b+d*e
• 第 9 題（4%）｜節點數為 2、3、4、5 的相異 binary tree 各有幾棵
• 第 10 題（8%）｜依序插入 50, 10, 80, 90, 70, 60, 65, 62，分別畫出 AVL tree 與 red-black tree 的最終結果
• 第 11 題（4%）｜給一段計算 KMP failure array 的 fail() 程式，求 abaabaab 與 abcababcabc 兩個 pattern 的 failure array
• 第 12 題（5%）｜對 55, 45, 25, 35, 85, 95, 65, 75, 105, 15 做 quick sort，每次取 sublist 的第一個元素當 pivot，寫出每一趟的數列
• 第 13 題（18%）｜六個是非題，每題 3 分，答錯要改正錯誤的部分，單純否定不給分
• 第 13(1) 題｜Counting sort 的執行時間是否為輸入大小 n 的多項式
• 第 13(2) 題｜Heap sort 的執行時間是否為輸入大小 n 的多項式
• 第 13(3) 題｜adjacency matrix 表示的圖上，DFS 是否花 Θ(V²) 時間
• 第 13(4) 題｜是否每個 DP 問題都能對應成子問題相依 DAG 上的 shortest path
• 第 13(5) 題｜問題 X 能 reduction 到某個已知的 NP-hard 問題，X 是否一定是 NP-hard
• 第 13(6) 題｜Ford-Fulkerson 用 DFS 找 augmenting path，是否能降低時間複雜度
• 第 14 題（7%）｜給一張 flow network。(a) 3%：max flow 與 min cut。(b) 2%：畫 residual graph，標出從 S 可達的頂點與可達 T 的頂點。(c) 2%：列出所有瓶頸邊（增加容量就能讓 max flow 增加的邊）

作答時要注意的地方

1. 第 4 題要求盡量少改，可以插入或刪除行，不要整行重寫。
2. 第 5 題要自己宣告資料結構，第 7 題指定用 fgets()。
3. 第 13 題答錯要改正錯誤的部分，單純否定不給分。
4. 第 11 題給的是一段 fail() 程式，要依這段程式的內容計算。

準備方向

• 手寫與除錯 C 程式（109 第 4、5、6、7 題），108 第 13 題、110 第 13、14 題、111 第 6 題、115 第 25 題也有。
• Bubble sort 之外的排序追蹤：quick sort 逐趟（109 第 12 題），114 第 5 題、115 第 16 題也有。
• AVL 與 red-black tree 的插入（109 第 10 題），red-black tree 插入的同一組數字在 112 第 9(5) 題；AVL 在 111、112、113、114 也有。
• KMP failure function（109 第 11 題），110 第 6 題、113 第 6 題、115 第 22 題也有。
• binary tree 形狀的計數（109 第 9 題），112 第 9(4) 題也有。
• Infix 轉 postfix（109 第 8 題），107 第 8 題也有，113、115 考 prefix 與 expression tree。
• max flow 與 min cut（109 第 14 題），112 第 12 題、113 第 22 題、115 第 13 題也有。
• reduction 方向與 NP-hard（109 第 13(5) 題），108 第 7 題、114 第 6 題也有。