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

題型與配分

全卷 8 頁、25 題、100 分。系所組別為「資訊工程學系」，不再分甲組。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。第 1 至第 24 題為複選題（可選多個選項），題目標明全部答對才給分，沒有部分給分，合計 91 分。

第 1–10 題與第 25 題是 C/C++ 題，合計 50 分。

逐題考點

• 第 1 題（3%）｜要存 string literal "123456"，哪些 char array 宣告可以成功存下
• 第 2 題（3%）｜一段本意輸出 The sum is: 30 的 C 程式，用 printf("The sum is:" + a + b)，哪些敘述正確說明了錯誤
• 第 3 題（4%）｜五個關於 C 運算子的敘述：後置遞增、% 用於 floating point、兩個邏輯運算式的值、關係運算子與算術運算子的優先順序
• 第 4 題（5%）｜int num[2][3] = {6,5,4,3,2,1}，要讓 array 內容變成 {6,5,0,3,2,0}，C 程式中三個空格要填什麼
• 第 5 題（5%）｜五個關於位元運算子的敘述，16 位元無號整數的 <<、>>、^、|
• 第 6 題（5%）｜struct item（name、date）與 Shelf（含 product[2] 與 row），要讓程式正確印出，兩個空格要填什麼成員存取寫法
• 第 7 題（4%）｜類別 constructor 的回傳型別
• 第 8 題（4%）｜關於特殊變數 this，哪些敘述不成立
• 第 9 題（4%）｜關於 template 函式的敘述
• 第 10 題（4%）｜哪一個描述「memory leak」
• 第 11 題（5%）｜dynamic array 滿了就加倍、使用率降到四分之一以下就減半，哪一個操作序列的平均 amortized cost 最高
• 第 12 題（5%）｜stack 支援 push、pop、multipop(k)，potential function 為 stack 大小，push 成本 2、pop 成本 0、multipop 成本為實際彈出的個數，multipop(k) 的 amortized cost g(k)
• 第 13 題（5%）｜一張 S-t flow network，已用三條 augmenting path 後 residual graph 中有一條容量為 7 的反向邊，判斷幾個敘述
• 第 14 題（10%）｜給一張九個頂點（A、B、C、D、E、F、G、H、I）的 simple graph 與邊集合，哪些是 biconnected component
• 第 15 題（2%）｜9 格 hash table，h(k) = k mod 9，linear probing，依序插入 8, 17, 26, 35, 44, 0, 9，選出對應的 array
• 第 16 題（2%）｜給 quicksort 第一次 partition 後的 array 5, 2, 8, 11, 20, 18, 14, 12，哪些關於 quicksort 的敘述不正確
• 第 17 題（2%）｜從頂點 A 開始 DFS，同層選字母順序最小的先走，dfn 從 1 開始，A 到 I 九個頂點的 dfn
• 第 18 題（2%）｜承第 17 題，各頂點的 low 值
• 第 19 題（2%）｜承第 17、18 題，這張圖的 articulation point
• 第 20 題（3%）｜給一個完全括號化的運算式（運算元為 A 到 I，含 AB、CD、E/F、H/I 等項），畫出 expression tree 並求 pre-order
• 第 21 題（3%）｜給一張專案網路（節點為事件、邊為活動與時間），求 critical path
• 第 22 題（3%）｜給 KMP 的 failure function 定義與長度 13 的字串 AAABAAAABAAAB，求整串的 failure 值
• 第 23 題（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 後刪除節點 D，求刪除後的 level-order traversal
• 第 24 題（3%）｜一張七個頂點的圖，從頂點 A 開始，相同暫定距離時選字母順序小的，求 Dijkstra 選取頂點的順序
• 第 25 題（9%）｜Operator Overloading：vector_2d 類別有私有的 x、y，要以成員函式實作 operator+=，使 a += b 之後 a 成為 <x1+x2, y1+y2>，b 不變，程式碼不超過 5 行

作答時要注意的地方

1. 第 1 至第 24 題是複選題，題目標明沒有部分給分，合計 91 分。
2. 第 25 題限制寫在 5 行以內，並指定以成員函式實作。
3. 第 17、18、19 題要依序使用前一題的結果，第 17 題從頂點 A 開始。
4. 第 21 題與 111 第 17.1 題是同一張圖。

準備方向

• 全卷的複選題都要全對（115 第 1–24 題），每個選項都要判斷。
• amortized analysis（115 第 11、12 題），中正 106–115 年只有 115 年考。
• 位元運算（115 第 5 題），111 第 4 題、114 第 13 題也有。
• pointer 與 array（115 第 4 題），108 第 14 題、111 第 2、3 題、112 第 2 題、113 第 11 題也有。
• constructor 與 this（115 第 7、8 題），115 第 7 題選項與 112 第 7 乙相同，第 8 題的前三個選項與 112 第 6 甲相同、改問哪個不正確。
• template（115 第 9 題），111 第 9 題也有。
• articulation point 的 dfn 與 low（115 第 17–19 題），110 第 3 題、111 第 16 題也有。
• AOE 網路的 critical path（115 第 21 題），111 第 17.1 題是同一張圖。
• KMP failure function（115 第 22 題），109 第 11 題、110 第 6 題、113 第 6 題也有。
• 由 in-order 與 post-order 重建 binary tree（115 第 23 題），110 第 4 題、113 第 7 題用同一組序列。
• Dijkstra 的頂點順序（115 第 24 題），107、108、110、111、113 也有。
• Quicksort 的性質（115 第 16 題），109 第 12 題、114 第 5 題也有。
• 手寫程式（115 第 25 題 operator+=），106、107、109、110、111、113 也有手寫或填空的程式題。
• max flow（115 第 13 題），109 第 14 題、112 第 12 題、113 第 22 題、114 第 6、10 題也有。