109 交大資工所軟體考點分析
沿用 108 年的題組全對制，15 個題組、36 小題。第 12 題組把雙處理器排程轉成最小割，是全卷最難也最漂亮的一題。
題型與配分
科目「資料結構與演算法（1101）」，系所班別資訊聯招，考試日期 109 年 2 月 4 日第 1 節，全卷 7 頁、15 個題組、36 小題、100 分，不可使用計算機，請使用答案卡作答。
計分規則與 108 年相同：同一題組全部小題都對才給該題組的滿分，錯任何一小題整組 0 分。題號旁有 † 記號者，每一小題可能有多個正確答案，必須全選才算對。
| 題組 | 主題 | 小題數 | 配分 |
|---|---|---|---|
| 1 † | DFS tree 與 articulation point | 2 | 6 |
| 2 | 圖著色問題的複雜度 | 3 | 6 |
| 3 † | Hamiltonian cycle 歸約 | 4 | 13 |
| 4 † | B-tree 性質 | 2 | 6 |
| 5 | MST 與邊權修改 | 3 | 7 |
| 6 | 負權圖的最低權重路徑 | 3 | 8 |
| 7 | Disjoint set 的三種啟發式 | 3 | 4 |
| 8 † | 遞迴數列與快速冪 | 3 | 6 |
| 9 † | Prefix-Sum 條件的 DP | 3 | 9 |
| 10 † | Hash／heap／樹的綜合性質 | 1 | 5 |
| 11 | 排序複雜度 | 2 | 5 |
| 12 † | 雙處理器排程 → 最小割 | 3 | 10 |
| 13 | Max heap 插入後的走訪 | 2 | 5 |
| 14 † | BST 的 successor 程式判讀 | 1 | 5 |
| 15 | 環狀雙向串列的指標運算 | 1 | 5 |
逐題考點
- 第 1 題組（†，6%）｜6 節點 8 邊的連通無向圖、r 在 G 中度數為 5：r 在 DFS tree 中可能的度數有哪些、r 是否必為 articulation point（答案是 Not necessary）
- 第 2 題組（6%）｜k-coloring 的最佳已知複雜度：k = 2（二分圖判定，多項式）、k = 3（NP-hard，超多項式）、k = 4（同樣超多項式）。考的是「2-colorable 容易、3-colorable 就 NP-hard」這個分界
- 第 3 題組（†，13%）｜配分最高的題組。已知
HamC(G)可在 O(nc) 判定 Hamiltonian cycle，要補完HamP2x3演算法的四個空格 —— 加入四個新節點 ℓ1–ℓ4 並接上適當的邊，使得「從 a1 或 a2 出發、走完其餘節點、停在 z1/z2/z3 之一」的路徑問題轉成 Hamiltonian cycle 問題。四小題全對才給 13 分 - 第 4 題組（†，6%）｜B-tree 的兩組性質判斷：每個節點最多幾個 key、葉的深度是否可不同、根節點是否可能少於 t 個子節點、以及分裂的相關敘述（是否繞中位數分裂、樹高何時增加）
- 第 5 題組（7%）｜給一張帶權圖：選出正確的 MST、把某一條邊的權重改成 1 後 MST 的最小可能總權重、刪掉某一條邊後 MST 的最大可能總權重
- 第 6 題組（8%）｜有負權邊的有向圖，求 A 到 F 的最低權重路徑，在三種不同限制下各求一次：同一節點最多走兩次、同一節點最多走一次、同一條邊最多走兩次。因為有負環，三個答案差很多
- 第 7 題組（4%）｜union by rank、path compression、weighted-union heuristic 三者各自的目的是什麼（配對題）
- 第 8 題組（†，6%）｜an + bn√3 = (1+2√3)n 的遞迴計算：判斷 a、b 的值與遞迴關係、演算法的最壞複雜度（O(n)）、以及能否用快速冪在 O(log n) 完成
- 第 9 題組（†，9%）｜Prefix-Sum 條件的子序列問題：選出最長的子序列使得每一項的前綴和都不超過該項的 6 倍。給輸入 2, 5, 3, 6, 2, 1, 2 求最大 k、判斷一個給定序列的性質、以及選出正確的 DP 遞迴式 D(i,s)
- 第 10 題組（†，5%）｜綜合性質判斷：chaining 的期望搜尋時間 O(1+α)、heap 中搜尋某個 key 的複雜度（陷阱：不是 O(log n)）、chaining 能否存超過 m 個 key、AVL 是否為 BST、紅黑樹中「有兩個子節點且其一為紅」的節點是否必為黑
- 第 11 題組（5%）｜BUBBLESORT 與 HEAPSORT 的最壞複雜度
- 第 12 題組（†，10%）｜雙處理器模組分配：N 個模組各有在處理器 1、2 上的執行成本 ai、bi，兩模組分在不同處理器時有通訊成本 cij，求總成本最小的分配。三小題分別問：給定表格的最佳解 X 的性質、如何把它建模成圖的割、以及可以用哪個演算法求解（答案是 Edmonds-Karp／Ford-Fulkerson，因為這是 min-cut）。這是全卷最漂亮的一題
- 第 13 題組（5%）｜max heap 插入 35 後，問 post-order 與 in-order 走訪的輸出
- 第 14 題組（†，5%）｜給一段找 BST successor 的程式碼，判斷執行後 y 與 x 的關係
- 第 15 題組（5%）｜環狀雙向串列存 3, 4, 5, 9, 7，一段迴圈跑 2019 次
next[next[x]]再做prev[prev[prev[x]]]，問最後value[x]。純模運算，要找出週期
這份考卷的難點
- 第 3 題組（13 分）與第 12 題組（10 分）合計 23 分，都是題組全對制。 第 3 題組有四個空格全要對，第 12 題組是複選且要全選。
- 第 12 題組的建模要看穿「把兩個處理器當成源點與匯點、模組當中間節點、通訊成本當邊權」—— 認不出是 min-cut 就完全無從下手。
- 第 6 題組的負環讓三個限制條件的答案差異極大，必須逐一小心枚舉。
- 第 10 題組的 heap 搜尋是常見陷阱：heap 只保證父子關係，搜尋任意 key 要 O(n) 而不是 O(log n)。
準備建議
- 交大連三年（107、108、109）考 Hamiltonian path／cycle 的歸約補空格，這是最值得針對性練習的題型
- 最小割的建模（109 第 12 題組、108 第 12 題組）是交大的高頻考點，「兩類選擇的最小成本分割 → min cut」這個套路要熟
- 題組全對制下，B-tree、AVL、MST 這些「一定考」的題組必須練到零失誤
- 進階內容（k-coloring 的複雜度分界、maximum adjacency ordering、scaling max flow）交大很敢考，讀 CLRS 時不要跳過選讀章節