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

題型與配分

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

規則：選擇題若有多個答案，必須全部選到才算對（沿用 108–111 年的精神），但沒有倒扣。

非選擇題明訂「答案必須寫得整齊清楚，否則不予評分」。

110、111 兩年的全選擇題只是過渡，112 年起交大回到手寫佔一半的結構，並且一路延續到 115 年。

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

• 第 1 題（3%）｜依序插入 4, 5, 6, 1, 2, 3, 7 到 AVL tree，判斷根節點、層級、祖先與兄弟關係
• 第 2 題（3%）｜四條遞迴式的解：T(n)=2T(n−1)+O(1)、T(n)=T(n/2)+O(1)、T(n)=T(n−1)+O(n)、T(n)=2T(n/2)+O(n)
• 第 3 題（3%）｜用 Kruskal 求 MST，判斷總權重、路徑、節點 d 的關聯邊權總和、邊數
• 第 4 題（3%）｜Kruskal 與 Prim 的比較：各自關注邊還是頂點、稠密圖時哪個較好、能否用於負權無向圖、Prim 換起點總權重會不會變（不會）
• 第 5 題（3%）｜依序插入 {6, 15, 3, 9, 4, 10, 8} 到 BST，判斷 pre-order／in-order、找 8 要經過幾條邊、哪些節點同層
• 第 6 題（3%）｜h(k)=k mod 7，插入 8, 12, 3, 11, 1, 2，在 linear probing／quadratic probing／h(k)+i+i²／chaining 四種策略下 key 2 各落在哪一格
• 第 7 題（3%）｜圖的表示法與走訪：adjacency matrix／list、BFS 用 queue、DFS 用 stack、BFS 求最短路徑、DFS 判斷強連通與環
• 第 8 題（4%）｜有負權邊的有向圖跑 Bellman-Ford，判斷最小／最大最短路徑權重與總和
• 第 9 題（3%）｜給一段把 {1..n, 1..n} 合併排序的 pseudo-code，填 L1、L2 兩處。關鍵在 <= 與 < 的差別會影響穩定性與正確性
• 第 10 題（3%）｜M 個節點的紅黑樹（含內外部節點）：至少有幾個紅節點、至少有幾個黑節點、左右子樹高度差是否至多 1（不是，那是 AVL）
• 第 11 題（3%）｜高度 h 的 max binary heap，存入 15 個元素後高度為 H：移除全部所需的 pop 次數上界、移除三層所需次數、取出第二小元素需要幾次 pop
• 第 12 題（3%）｜min heap 初始只有 10，依序存入 5, 4, 3, 2, 9, 7, 8, 6 後刪除節點 5，判斷結果樹的父子關係
• 第 13 題（3%）｜由 {2n−1, 2n−3, …, 1} 與 {2, 4, …, 2n} 交錯而成的序列全部 push 進 stack 再全部 pop，問 (n−1) 與 (n+1) 分別在第幾步被彈出。純推理題，要看出 stack 的反轉性質
• 第 14 題（3%）｜給一棵二元樹與兩條巢狀的 parent／left／right 運算式，反推 w 與 y 是哪兩個節點
• 第 15 題（3%）｜5 個節點的二元樹，preorder 與 postorder 結果分別為 {x₁..x₅}、{y₁..y₅}，滿足 Σ|x_i−y_i| = 6 的是哪些樹
• 第 16 題（4%）｜X[] = {1, 2, …, n} 用 insertion sort 排成降冪，問 Line L（搬移那一行）執行幾次。答案是 n(n−1)/2，因為升冪輸入排降冪是最壞情況

Part II 非選擇題考點（17–26）

• 第 17 題（2%）｜兩段分別是 O(n log n) 與 Θ(n log n) 的演算法，總時間該用哪個漸進記號並說明理由。考的是 O 與 Θ 的差異
• 第 18 題（9%）｜Median of medians
• (a) 4%｜證明分成 ⌈n/5⌉ 組後可以丟掉的集合 S 滿足 |S| ≥ n/4
• (b) 5%｜能不能改成 ⌈n/3⌉ 組？為什麼？ 這是全卷最經典的一問
• 第 19 題（6%）｜直線上 n 個使用者要架 wifi，路由器數量不限但要最小化功率（訊號半徑）。(a) 4% 設計分治演算法 (b) 2% 分析複雜度
• 第 20 題（8%）｜用兩個 stack 實作 FIFO queue：(a) 2% enQueue 的 pseudo-code (b) 2% deQueue 的 pseudo-code (c) 4% 證明 deQueue 的攤銷成本是 O(1)
• 第 21 題（4%）｜Vertex cover 與 matching：(a) 2% 證明或反證 |M| ≤ |U| (b) 2% 對給定的圖找出最大匹配與最小點覆蓋
• 第 22 題（4%）｜給殘餘網路跑 Ford-Fulkerson：(a) 2% 寫出用到的增廣路徑 (b) 2% 找出一個最小 s-t 割
• 第 23 題（6%）｜尋找 peak（a_i ≥ max(a_i−1, a_i+1)）：(a) 2% 找出給定序列的所有 peak (b) 2% 寫出 O(log n) 的程序 (c) 2% 簡述正確性
• 第 24 題（2%）｜證明或反證：完全圖上任一 MST 的成本永遠不超過任一 TSP tour 的成本
• 第 25 題（4%）｜Knapsack：(a) 2% 「每次挑單位價值最高」的貪婪法對 0-1 knapsack 是否正確？若否，給出物品數最少的反例 (b) 2% 用給定的遞迴式填出 4×6 的 A(i,w) 表並求最佳利潤
• 第 26 題（5%）｜巫師造塔：n 種法術 (a_i, b_i, k_i)，施放時塔高立刻 +a_i，之後連續 k_i 回合每回合 −b_i，效果可疊加，每回合最多施一個法術、每個法術最多用一次，求塔的最高紀錄高度。(a) 2% 給定 4 個法術求答案 (b) 3% 寫出 A(i,j) 與 B(i,j) 的雙變數遞迴式

這份考卷的難點

1. 第 26 題是全卷最難的一題。 要同時處理「選哪些法術」「用什麼順序」「效果疊加」三個維度，還要設計出兩個互相依賴的 DP 狀態。
2. 第 18(b) 的「能不能分 3 組」是經典中的經典 —— 分 3 組時能丟掉的比例降到 n/3 以下，遞迴式變成 T(n) ≤ T(n/3)+T(2n/3)+O(n)，解出是 O(n log n) 而非 O(n)。
3. 第 13 題的 stack 推理沒有公式可套，要自己追蹤 push／pop 的對應關係。
4. 手寫題有五題是「證明或反證」（18a、20c、21a、23c、24），寫作量很大。

準備建議

• median of medians 的分組大小為何是 5（112 第 18 題）與 110 年第 30 題是同一個觀念，交大連續兩年考，必須弄懂
• 兩個 stack 實作 queue 的攤銷證明要能寫出來（112 第 20(c) 題），這也是台大 107 的考點
• König 定理（二分圖中最大匹配 = 最小點覆蓋）與一般圖上 |M| ≤ |U| 的關係，第 21 題直接考
• 112 年起交大固定「選擇 50＋手寫 50」，手寫題的深度明顯高於選擇題，準備重心應該放在「設計演算法＋證明」而不是背誦