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

題型與配分

全卷 5 頁、12 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。第 5、6、7 題標明複選，沒有部分給分，合計 21 分。第 11 題標明只答 yes 或 no 不給分。

第 1–7 題是 C/C++ 題，合計 50 分。

逐題考點

• 第 1(a) 題（5%）｜寫一行 C 敘述式，以八進位格式並在前面加 0 的方式顯示十進位數值 100
• 第 1(b) 題（5%）｜寫一行 C 敘述式，連續讀入字元到 array n 中，直到遇到一個非數字字元為止
• 第 2 題（10%）｜char array s[] = "01234" 與 pointer p = s，五個 printf 分別對 *p++、*++p、*(++p)、*(p++)、(*p)++ 輸出字元，求螢幕上的結果
• 第 3 題（5%）｜x = 3, n = 6 的雙層迴圈，內層依 i + j 等於 2、3、4 分別給 x 加 3、4、5，求輸出的 x
• 第 4 題（4%）｜John 決定在整數 array 最後加 4 個 NULL byte 當結尾，就像字串一樣，問除了多佔空間之外還有什麼問題
• 第 5 題（3%）｜哪些是宣告而不是定義：int i;、int i=1;、int foo(int);、int foo(int i);、typedef string my_string;，複選且沒有部分給分
• 第 6 題（12%）｜複選，沒有部分給分，每小題 3 分。甲：特殊變數 this 的性質。乙：類別 Thing 裡隱含的 this 的型別。丙：const 變數的性質。丁：哪些敘述會造成 string 被複製
• 第 7 題（6%）｜複選，沒有部分給分。甲 3%：constructor 的性質。乙 3%：constructor 的回傳型別
• 第 8 題（10%）｜五個是非題，每題 2 分：九層 binary tree 的最大節點數、f₁(n)、f₂(n) 與 g(n) 之間 asymptotic notation 的推論、comparison sort 最壞情況時間的下界、biconnected 圖的定義、preorder 與 postorder 序列能否唯一決定 binary tree
• 第 9 題（15%）｜五題選擇題，每題 3 分。(1) 從節點 1 做 DFS 的 traversal 序列（編號小的先走）；(2) 把整數 array {19, 5, 27, 3, 16, 11, 69, 18} 用 bottom-up 在 O(n) 時間內建成 max heap；(3) 依序加入 89, 70, 52, 4, 25, 99, 59, 20, 79, 62, 44, 38 建 AVL tree；(4) 8 個節點的相異 binary tree 個數；(5) 依序插入 50, 10, 80, 90, 70, 60, 65, 62 建 red-black tree
• 第 10 題（8%）｜四個是非題，每題 2 分：(a) quicksort 是否漸進最佳；(b) quicksort 每層 partition 都最不平衡時，對應的 decision tree 是否為 full binary tree；(c) insertion sort 是否 in-place 但不 stable；(d) counting sort 是否同時 stable 且 in-place
• 第 11 題（11%）｜一張有 negative-weight edge 的圖，每小題要寫出理由，只答 yes 或 no 不給分。(a) 2%：找 a 到 d 的 shortest path，Dijkstra 是否適用。(b) 2%：所有邊權重都是 1 時，BFS 是否適用。(c) 2%：所有邊權重都是 1 時，topological sort 是否適用。(d) 5%：reweighting 使所有邊非負
• 第 12 題（6%）｜對一張 flow network 執行 Ford-Fulkerson，輸出為何，要寫出推導

作答時要注意的地方

1. 第 5、6、7 題明訂複選題沒有部分給分，第 11 題只答 yes 或 no 不給分。
2. 第 1 題要求單行 C 敘述式。
3. 第 9 題是五個四選一，每題 3 分。
4. 第 12 題要寫出推導過程。

準備方向

• 單行 C 敘述式與 printf 格式（112 第 1(a) 題），113 第 10 題、114 第 11、13 題也考 printf 格式。
• pointer 運算（112 第 2 題），111 第 3 題、113 第 11 題、115 第 4 題也有。
• const 與 this（112 第 6 題），110 第 1.2 題、114 第 12 題、115 第 8 題也有。
• constructor 的回傳型別與 this 的性質（112 第 6 甲、7 乙），115 第 7 題選項與 112 第 7 乙相同，115 第 8 題的前三個選項與 112 第 6 甲相同、改問哪個不正確。
• red-black tree 插入 50, 10, 80, 90, 70, 60, 65, 62（112 第 9(5) 題），109 第 10 題是同一組數字。
• binary tree 形狀的計數（112 第 9(4) 題），109 第 9 題也有。
• Heap 的 bottom-up 建構（112 第 9(2) 題），108、111、114 也有 heap 相關題目。
• 排序是否漸進最佳（112 第 10(a) 題），108 第 9 題、111 第 18 題也有。
• 負權圖與 reweighting（112 第 11 題），110 第 5、11 題、111 第 19 題連續出現，107 第 12 題也把 negative-weight edge 轉成非負。
• max flow（112 第 12 題），109 第 14 題、113 第 22 題、115 第 13 題也有。