114 交大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 7 頁、100 分，不可使用計算機。

計分規則：「選擇題每一題組須全答對才計分」，沿用 108、109、113 年的題組全對制。

Part I 選擇題考點（1–14）

• 第 1 題（5%）｜asymptotic notation 與 recurrence：Θ 與 O∩Ω 的等價、o 的正確定義、T(n)=2T(√n)+Θ(log n)、T(n)=8T(n/3+12)+n²、T(n)=2T(n/4)+√n
• 第 2 題（4%）｜Monge array：判斷驗證條件能否只檢查相鄰列、要改幾個元素才能讓給定 array 成為 Monge array，以及每列最左最小值的行索引的性質
• 第 3 題（6%）｜由 0-1 字串重建 permutation：給一支 findPermutation 的 C++ 程式，判斷各種輸入的回傳值、時間複雜度、是否所有輸入都有解
• 第 4 題（4%）｜modular inverse：p = 101、a = 55，求 b 使 ab ≡ 1 (mod p)，判斷 b 的位數、數字和等性質
• 第 5 題（5%）｜兩個 array A、B 用 permutation π 配對求 Σ A[i]·B[π(i)] 的最大值：重排不等式、能否 greedy 解、能否 O(n)
• 第 6 題（3%）｜MST 的基本性質：N 個節點的邊數、邊權互異時 MST 是否唯一、所有邊加常數 C 後 MST 是否不變、非 MST 邊權變動的影響
• 第 7 題（3%）｜給一張有重複邊權的 undirected graph，問總共有幾棵相異的 MST
• 第 8 題（3%）｜哪些問題能用 BFS 解：迷宮 shortest path、bipartite graph 判定、可達性、深度 k 的節點、connected component
• 第 9 題（3%）｜red-black tree 性質：是否自平衡 BST、根到葉的路徑長度的比例限制、根的顏色、刪除紅節點是否需要重平衡、旋轉的用途
• 第 10 題（3%）｜min heap 的 insert 填空：size++ 還是 ++size、父節點索引的寫法
• 第 11 題（3%）｜承第 10 題，依序插入 40, 15, 50, 10, 30, 20, 5, 12 後 data[1] 與 data[4] 的值
• 第 12 題（3%）｜依序插入 80, 40, 20, 100, 60, 30, 50, 70, 10, 25, 35 到 max degree 3 的 B-tree，問有幾個節點只含一個數字
• 第 13 題（3%）｜AVL、B-tree、B+-tree 的比較：B+-tree 的循序存取、AVL 與 B-tree 在減少磁碟存取上的比較，以及一組數字插入 AVL 後根的右子節點是誰
• 第 14 題（3%）｜給三支函式 foo1、foo2、foo3 與一張圖，判斷哪些能求出從頂點 4 到其他點的 shortest path

Part II 非選擇題考點（1–7）

• 第 1 題（10%）｜DAG 上的最大權重 simple path：(a) 描述 DP 解法，明確寫出 recurrence 與子問題定義 (b) 分析執行時間
• 第 2 題（6%）｜求輸入字串的最長回文子序列（例如 character → carac），要給多項式時間演算法並分析複雜度
• 第 3 題（10%）｜disjoint paths：(a) 4% 如何求源點到匯點的最多 edge-disjoint 路徑，並對給定例子算出答案 (b) 6% 如何求最多 node-disjoint 路徑
• 第 4 題（6%）｜給定黑高 h，推導 red-black tree 節點數的最小值 N_min(h) 與最大值 N_max(h)，要說明推理並給出公式
• 第 5 題（3%）｜大小 n 的 heap（索引從 0 開始），葉節點的索引範圍是多少
• 第 6 題（4%）｜Order statistic tree 的 OS-SELECT 填空，補完第 1 行
• 第 7 題（10%）｜給一支 C 函式 bar(N, X, Y, Z)，用代入法（substitution method）分析時間複雜度，要清楚寫出每一步

作答時要注意的地方

1. 選擇題採題組全對制，第 14 題的三支函式都要判斷正確才給分。
2. 非選擇題第 7 題指定用代入法分析。
3. 非選擇題第 3 題 (a) 求 edge-disjoint paths、(b) 求 vertex-disjoint paths，兩小題分開計分。
4. 第 10 題與第 11 題相連，第 11 題用到第 10 題的程式。

準備方向

• red-black tree 的節點數上下界（114 第 4 題）。
• edge-disjoint 與 vertex-disjoint paths（114 第 3 題），屬於 max flow 的應用。
• 給程式碼問是哪個演算法或在解什麼問題：112 第 9 題、113 第 6 題組、114 第 14 題。
• 最長回文子序列等經典 DP：113 考雙峰版、114 考回文版。
• 所有邊加常數對 MST 的影響（114 第 6 題）。