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

題型與配分

全卷 4 頁、100 分，不得使用計算機。這是甲組第一份獨立的軟體考卷，112 年起甲組拆成離散數學與線性代數、資料結構與演算法、計算機組織與作業系統三科。卷面沒有標示倒扣。

PART 1-A：選擇題（6%）

• 第 1 題（3%）｜2D array student 為 100 列 4 行，student[1][1] 存在位址 1000、每個元素佔一個記憶體位置、row-major，求 student[5][3] 的位址
• 第 2 題（3%）｜哪個時間複雜度最高：O(n¹⁰⁰)、O(n!)、O(n² log₂ n)、O(2ⁿ)

PART 1-B：資料結構簡答（44%）

• 第 1 題（6%）｜用 BST 搜尋數字 43，判斷五組 probe sequence 哪些是可能的
• 第 2 題（6%）｜Floyd-Warshall：A^k[i][j] 是只經過編號不超過 k 的中間頂點時 i 到 j 的 shortest path 成本，給一張有向 weighted graph，求 A¹ 中非無窮大元素的最大值
• 第 3 題（5%）｜遞迴函式 Q(a, b)，a < b 時為 0，b ≤ a 時為 Q(a − b, b) + 1，求 Q(5861, 7)
• 第 4 題（10%）｜把杯子堆成每層為正方形的塔，第 N 層是 N × N 個杯子：(a) 5% 補完 C 語言函式 crystal(N) 缺少的一行；(b) 5% 求 crystal(6)
• 第 5 題（9%）｜給一個 AOE 網路（起點 S、終點 E，頂點 T、X、Y、Z、W）：(a) 3% 求 critical path；(b) 6% 求 X、Y、W 的 earliest time 與 latest time
• 第 6 題（8%）｜給一棵 BST，隨機搜尋樹中存在的一個鍵，求比較次數的期望值，四捨五入到小數第二位

PART 2-C：演算法單選（15%）

三題都是 C 語言的 linked list 與 pointer：

• C-I（5%）｜join(node* m, node* n) 先用 while (p->next != NULL) 走到 n 的尾端，再接上 m，問呼叫的結果
• C-II（5%）｜move_to_front 把 singly linked list 的最後一個節點搬到最前面，選出空白處該填的敘述
• C-III（5%）｜以兩個索引 a、b 從 array 兩端逼近求最大值，問 while 迴圈的條件

PART 2-D：演算法簡答（35%，寫在答案卷）

• D-I（5%）｜KMP 演算法需要 failure function，pattern 為 a b a a b a a a a（index 0–8），填完整張表
• D-II（10%）｜審稿分配：6 篇論文 P1–P6、3 位審稿人 R1–R3，R1 願意審 {P1, P3, P5, P6}、R2 願意審 {P1, P2, P4}、R3 願意審全部。一個分配有效的條件是每篇論文至少分給 2 位願意審它的不同審稿人，每位審稿人最多審 4 篇，目標是最大化有效分配的論文數：
• D-II(1)（5%）｜用 s-t flow network 建模，畫出標好容量的 flow network
• D-II(2)（5%）｜最多能有效分配幾篇論文
• D-III（5%）｜四個矩陣相乘，dimension 依序為 10×11、11×25、25×40、40×2，求最佳加括號方式與最少 scalar multiplication 次數
• D-IV（5%）｜求 (x₁, …, x₅) 使 x₁ + x₂ + x₃ + x₄ + x₅ 最大，其中 x_i ≤ 0，問最大值與對應的向量，題目寫的是 following constraints，但試卷上沒有印出限制式
• D-V（10%）｜假設 P ≠ NP，十個問題各判斷是 P 問題（答 1）、NP-hard 或 NP-complete（答 2）、或兩者皆非（答 3）：
• D-V(1)｜正權圖兩點間的 longest simple path
• D-V(2)｜含 negative cycle 的 directed graph 兩點間的 shortest simple path
• D-V(3)｜加權 directed graph 中找 negative-weight directed cycle
• D-V(4)｜加權 directed graph 中找 positive-weight directed cycle
• D-V(5)｜每條邊權重為 1 的圖中找最大的 cycle
• D-V(6)｜每條邊權重為 1 的圖中找最小的 cycle
• D-V(7)｜flow network 中找 maximum cut
• D-V(8)｜flow network 中找 minimum cut
• D-V(9)｜區間圖的 maximum independent set
• D-V(10)｜2-CNF-Satisfiability

作答時要注意的地方

1. 卷面沒有標示倒扣，簡答題要寫出答案。
2. D 部分卷面註明請於答案卷上作答，否則不予計分。
3. B 第 6 題要求四捨五入到小數第二位。
4. D-II 要自己設計 flow network 並標出容量，題目給了每位審稿人的上限與每篇論文的最低審稿數。
5. D-IV 題目沒有印出限制式。
6. D-V 要對十個問題逐一判斷。

準備方向

• row-major 2D array 位址：112 PART 1-A 第 1 題與 108 PART 1 選擇第 2 題是同一題。
• BST 的搜尋路徑：112 B 第 1 題，113 第 9 題也有。
• Floyd-Warshall：112 B 第 2 題，110 第 9-D、10-B 題也有。
• 遞迴函式求值：112 B 第 3、4 題，109 第 6 題、110 第 7-D 題、111 第 3-VII 題、113 第 10 題也有。
• AOE 網路與 critical path：112 B 第 5 題，110 第 8-A 題也有。
• BST 的搜尋成本：112 B 第 6 題。
• C 語言的 linked list 與 pointer：112 PART 2-C，110 第 6-A 題、113 B-1 第 1、2 題也有。
• KMP 的 failure function：112 D-I，114 第 6 題考 string matching 演算法的分類。
• flow network 建模與 max flow：112 D-II，110 第 8-C 題、113 B-1 第 4 題也有 max flow 與 min cut。
• 矩陣鏈乘法：112 D-III，110 第 9-B 題也有。
• P、NP-hard 的分類：112 D-V，111 第 1-IV、1-V 題、113 B-2 第 2 題、114 第 5 題也有。