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

題型與配分

全卷 9 頁、26 題、100 分，不可使用計算機。

選擇題若有多個答案，必須全部選到才算對。卷面沒有提到倒扣。非選擇題明訂答案必須寫得整齊清楚，否則不予評分。

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

• 第 1 題（3%）｜依序插入 4, 5, 6, 1, 2, 3, 7 到 AVL tree，判斷根節點、層級、祖先與兄弟關係
• 第 2 題（3%）｜四條 recurrence 的解：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 的 incident edge 權重總和、邊數
• 第 4 題（3%）｜Kruskal 與 Prim 的比較：各自關注邊還是頂點、dense graph 時哪個較好、能否用於負權 undirected graph、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%）｜圖的表示法與 traversal：adjacency matrix 與 list、BFS 與 DFS 各用什麼資料結構、BFS 求 shortest path、DFS 判斷 strongly connected 與 cycle
• 第 8 題（4%）｜有 negative-weight edge 的 directed graph 跑 Bellman-Ford，判斷最小與最大 shortest path 權重與總和
• 第 9 題（3%）｜給一段把 {1..n, 1..n} merge sort 的 pseudo-code，填 L1、L2 兩處
• 第 10 題（3%）｜M 個節點的 red-black tree（含內外部節點）：至少有幾個紅節點、至少有幾個黑節點、左右子樹高度差的限制
• 第 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) 分別在第幾步被彈出
• 第 14 題（3%）｜給一棵 binary tree 與兩條巢狀的 parent、left、right 運算式，反推 w 與 y 是哪兩個節點
• 第 15 題（3%）｜5 個節點的 binary tree，preorder 與 postorder 結果分別為 {x₁..x₅}、{y₁..y₅}，滿足 Σ|x_i−y_i| = 6 的是哪些樹
• 第 16 題（4%）｜X[] = {1, 2, …, n} 用 insertion sort 排成降冪，問 Line L（搬移那一行）執行幾次

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

• 第 17 題（2%）｜兩段分別是 O(n log n) 與 Θ(n log n) 的演算法，總時間該用哪個 asymptotic notation 並說明理由
• 第 18 題（9%）｜Median of medians：(a) 4% 證明分成 ⌈n/5⌉ 組後可以丟掉的集合 S 滿足 |S| ≥ n/4 (b) 5% 能不能改成 ⌈n/3⌉ 組？為什麼
• 第 19 題（6%）｜直線上 n 個使用者要架 wifi，路由器數量不限但要最小化功率（訊號半徑）。(a) 4% 設計 divide and conquer 演算法 (b) 2% 分析複雜度
• 第 20 題（8%）｜用兩個 stack 實作 FIFO queue：(a) 2% enQueue 的 pseudo-code (b) 2% deQueue 的 pseudo-code (c) 4% 證明 deQueue 的 amortized cost
• 第 21 題（4%）｜Vertex cover 與 matching：(a) 2% 證明或反證 |M| ≤ |U| (b) 2% 對給定的圖找出 maximum matching 與 minimum vertex cover
• 第 22 題（4%）｜給 residual network 跑 Ford-Fulkerson：(a) 2% 寫出用到的 augmenting path (b) 2% 找出一個 minimum s-t cut
• 第 23 題（6%）｜尋找 peak（a_i ≥ max(a_i−1, a_i+1)）：(a) 2% 找出給定序列的所有 peak (b) 2% 寫出 O(log n) 的程序 (c) 2% 簡述正確性
• 第 24 題（2%）｜證明或反證：complete graph 上任一 MST 的成本永遠不超過任一 TSP tour 的成本
• 第 25 題（4%）｜Knapsack：(a) 2% 「每次挑單位價值最高」的 greedy 法對 0-1 knapsack 是否正確？若否，給出物品數最少的反例 (b) 2% 用給定的 recurrence 填出 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) 的雙變數 recurrence

作答時要注意的地方

1. 非選擇題明訂答案必須寫得整齊清楚，否則不予評分。
2. 第 18 題 9 分，是非選擇題中配分最高的一題。
3. 非選擇題有五題要求證明或反證：第 18(a)、20(c)、21(a)、23(c)、24 題。
4. 第 26 題要寫出 A(i,j) 與 B(i,j) 兩個變數的 recurrence。

準備方向

• median of medians 與分組大小：110 第 30 題、112 第 18 題都考。
• 兩個 stack 實作 queue 與 amortized analysis（112 第 20 題）。
• bipartite graph 的 maximum matching 與 minimum vertex cover（112 第 21 題）。
• 非選擇題以設計演算法與證明為主。選擇題與非選擇題的比重：112、113 年各 50 分，114 年 51／49，115 年變成 24／76。