115 中正資工所軟體考點分析

題型與配分

系所組別「資訊工程學系」（首次不分甲組），科目名稱：軟體設計，全卷 8 頁、25 題、100 分。

第 1–24 題全部是複選題，卷面明訂：「Select multiple correct answers 複選題（可選多個選項）：Choose all (one or more) that apply. NO partial credit is given.」

91 分的區塊全對才給分，這是中正十年來最嚴苛的計分設計。

逐題考點

C 語言部分（1–6，26%）

• 第 1 題（3%）｜存放字串 "123456" 需要多大的 char 陣列（至少 7，含 \0）
• 第 2 題（3%）｜printf("The sum is:" + a + b) 為什麼錯 —— 字串常數與整數不能用 + 串接，應該用格式指定符與逗號
• 第 3 題（4%）｜C 運算子：a++ 的後置語意、% 能否用於 float（否）、兩個複雜布林運算式的值、關係運算子的優先序是否高於算術運算子（否）
• 第 4 題（5%）｜二維陣列 int num[2][3] 搭配陣列指標 int (*p)[3] 的三格填空
• 第 5 題（5%）｜位元運算：7 << 2、0x0010 >> 3、3 ^ 5、3 | 5、0x0030 的運算
• 第 6 題（5%）｜巢狀結構 Shelf 內含 struct item product[2]，用 . 與 -> 存取的正確寫法（s1_ptr->product[i].name 才對）

C++ 部分（7–10，16%）

• 第 7 題（4%）｜建構子的回傳型別（沒有回傳值）—— 與 112 年第 7 題乙完全相同
• 第 8 題（4%）｜關於 this 哪一個不正確 —— 與 112 年第 6 題甲同一組選項
• 第 9 題（4%）｜templated function 的性質（本身不是函式而是產生函式的方式、含 template 關鍵字、用模板參數代表呼叫型別）
• 第 10 題（4%）｜什麼是 memory leak（用 new 配置但沒有 delete）

攤銷分析（11–12，10%） —— 中正首次考攤銷分析

• 第 11 題（5%）｜動態陣列滿了加倍、元素數 ≤ 1/4 時減半，哪一種操作序列會造成最高的攤銷成本。（答案是「插入、刪除交替」會在門檻上反覆震盪 —— 但注意 1/4 的設計正是為了避免這件事）
• 第 12 題（5%）｜stack 支援 push（成本 2）、pop（成本 0）、multipop(k)（成本為實際彈出數），給定位能函數 Φ(S) = |S|，求 multipop(k) 的攤銷成本 g(k) 是 Θ(1) 還是 O(k)、是否與當前堆疊大小有關

圖論與資料結構（13–24）

• 第 13 題（5%）｜給流網路與其殘餘圖，已套用三條增廣路徑後殘餘圖有一條容量 7 的反向邊，判斷：目前是否為最大流、是否違反容量限制、反向邊的存在代表什麼（先前有增廣路徑正向用過該邊）
• 第 14 題（10%）｜給一張圖，找出所有 biconnected component
• 第 15 題（2%）｜9 格雜湊表、h(k) = k mod 9、linear probing，插入 8, 17, 26, 35, 44, 0, 9 後的陣列
• 第 16 題（2%）｜給第一次 partition 後的陣列，判斷哪些關於 Quicksort 的敘述不正確：是否穩定（不穩定）、最差 pivot 時是否仍正確、pivot 可能是誰、是否總是 O(n log n)（否）
• 第 17–19 題（各 2%）｜Articulation point 三連：從 A 開始的 dfn、各頂點的 low 值、關節點（與 110 年第 3 題、111 年第 16 題同型，連三次考）
• 第 20 題（3%）｜完全加括號的運算式建運算式樹，求 pre-order
• 第 21 題（3%）｜專案網路的 critical path（與 111 年第 17.1 題是同一張圖）
• 第 22 題（3%）｜字串 AAABAAAABAAAB（13 字元）的 KMP failure function（與 113 年第 6 題只差最後一個字元）
• 第 23 題（3%）｜由 in-order 與 post-order 重建二元樹（與 110 年第 4 題、113 年第 7 題同一組序列），刪除節點 D 後的 level-order
• 第 24 題（3%）｜從 A 出發的 Dijkstra 頂點選取順序

第 25 題（9%）｜手寫程式

為 vector_2d 類別以成員函式實作 operator+=，a += b 後 a 變成兩者之和、b 不變，限 5 行以內。標準答案要回傳 vector_2d& 並 return *this;

這份考卷的難點

1. 91 分的複選題全對才給分，第 14 題（10 分）與第 11、12、13 題（各 5 分）風險特別高。
2. 第 11、12 題的攤銷分析是中正首次出現，而且第 12 題直接給位能函數要你算攤銷成本，沒讀過 CLRS 第 17 章會完全無從下手。
3. 第 17–19 題的 articulation point 三連要完整跑 DFS 並算出九個頂點的 dfn 與 low，三小題連動。
4. 第 3 題的布林運算式要精確處理 &&、||、! 的優先序與短路求值。

準備建議

• 中正的 articulation point（dfn／low）在 110、111、115 考了三次，是十年最高頻的圖論題，必須練到機械化
• KMP failure function 在 109、110、113、115 考了四次，而且用的是 failure[0] = -1 的版本，與標準 π 函數不同
• 由 in-order + post-order 重建二元樹在 110、113、115 用了同一組序列（A,B,G,E,D,I,J,F,H,C / G,E,J,I,H,F,D,C,B,A）—— 中正重複出題的傾向非常明顯
• 攤銷分析（potential method）是 115 年新增的主題，CLRS 第 17 章建議補齊
• 全卷 91 分全對才給分，策略是把有把握的題目確認到底，而不是每題都選一點