114 交大資工所軟體考點分析

題型與配分

科目「資料結構與演算法（8101）」，系所班別資訊聯招，考試日期 114 年 2 月 6 日第 1 節，全卷 7 頁、100 分，不可使用計算機。

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

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

• 第 1 題（5%）｜漸進記號與遞迴式：Θ 與 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（蒙日陣列）：判斷驗證條件能否只檢查相鄰列、要改幾個元素才能讓給定陣列成為 Monge array、以及每列最左最小值的行索引是否單調遞增（這是 Monge array 最重要的性質）
• 第 3 題（6%）｜由 0-1 字串重建排列：給一支 findPermutation 的 C++ 程式，判斷各種輸入的回傳值、時間複雜度、是否所有輸入都有解
• 第 4 題（4%）｜模反元素：p = 101、a = 55，求 b 使 ab ≡ 1 (mod p)，判斷 b 的位數、數字和等性質
• 第 5 題（5%）｜兩個陣列 A、B 用排列 π 配對求 Σ A[i]·B[π(i)] 的最大值：重排不等式（a≤b 且 c≤d ⇒ ac+bd ≥ ad+bc）、能否貪婪解、能否 O(n)
• 第 6 題（3%）｜MST 的基本性質：N 個節點是否 N−1 條邊、邊權互異時 MST 是否唯一、所有邊加常數 C 後 MST 是否不變（這題和最短路徑相反，MST 不變）、非 MST 邊權變動的影響
• 第 7 題（3%）｜給一張有重複邊權的無向圖，問總共有幾棵相異的 MST
• 第 8 題（3%）｜哪些問題能用 BFS 解：迷宮最短路徑、二分圖判定、可達性、深度 k 的節點、連通元件
• 第 9 題（3%）｜紅黑樹性質：是否自平衡 BST、根到葉的路徑長度最多差兩倍、根是否為紅（否）、刪除紅節點是否需要重平衡（否）、旋轉的用途
• 第 10 題（3%）｜min heap 的 insert 填空：size++ 還是 ++size、父節點索引是 cur/2 還是 (cur-1)/2（因為索引從 0 開始）
• 第 11 題（3%）｜承上，依序插入 40, 15, 50, 10, 30, 20, 5 後 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 到其他點的最短路徑。foo1 是 Bellman-Ford、foo2 是 Dijkstra、foo3 是 Floyd-Warshall —— 要能從程式碼認出來

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

• 第 1 題（10%）｜DAG 上的最大權重簡單路徑：(a) 描述 DP 解法，明確寫出遞迴式與子問題定義 (b) 分析執行時間
• 第 2 題（6%）｜求輸入字串的最長回文子序列（例如 character → carac），要給多項式時間演算法並分析複雜度
• 第 3 題（10%）｜互斥路徑：(a) 4% 如何求源點到匯點的最多邊互斥（edge-disjoint）路徑，並對給定例子算出答案 (b) 6% 如何求最多點互斥（node-disjoint）路徑。後者要用節點拆分技巧（把每個節點拆成 in／out 兩點、中間連容量 1 的邊）
• 第 4 題（6%）｜給定黑高 h，推導紅黑樹節點數的最小值 N_min(h) 與最大值 N_max(h)，要說明推理並給出公式
• 第 5 題（3%）｜大小 n 的 heap（索引從 0 開始），葉節點的索引範圍是多少
• 第 6 題（4%）｜Order statistic tree 的 OS-SELECT 填空，補完第 1 行（計算左子樹大小 r = size[left[x]] + 1）
• 第 7 題（10%）｜給一支 C 函式 bar(N, X, Y, Z)（河內塔），用代入法（substitution method）分析時間複雜度，要清楚寫出每一步

這份考卷的難點

1. 第 14 題要從程式碼認出三種最短路徑演算法，而且是題組全對制 —— 三支函式都要判斷正確。
2. 第 2 題的 Monge array 超出一般課本，要知道「最左最小值行索引單調」這個關鍵性質才答得出 (D)。
3. 第 3(b) 的點互斥路徑需要節點拆分技巧，只會邊互斥（直接跑 max flow）是不夠的。
4. 第 7 題指定用代入法，寫成遞迴樹或 Master theorem 不符合題意。
5. 第 10 題的 (cur-1)/2 是索引從 0 開始的陷阱，很多人直覺寫 cur/2。

準備建議

• 紅黑樹的節點數上下界（N_min(h)=2^h−1、N_max(h)=4^h−1）建議推過一次，114 第 4 題直接考推導
• 邊互斥與點互斥路徑（Menger 定理）是 max flow 的標準應用，節點拆分技巧要熟
• 交大近年大量出現「給程式碼，問它是哪個演算法／在解什麼問題」（113 第 6 題組、114 第 14 題、112 第 9 題），要練習讀程式而不是背名字
• 最長回文子序列（LPS）可化為原字串與其反轉的 LCS，這個轉換在 113、114 連兩年出現（113 是雙峰版、114 是回文版）
• 「所有邊加常數」對 MST 無影響、對最短路徑有影響 —— 這組對比在交大 114 與台大 112 同時出現