115 台大資工所軟體考點分析

題型與配分

科目「資料結構與演算法」（題號 276、節次 1），全卷 7 頁、25 題、100 分，每題 4 分，全部單選。

卷首沒有任何計分或倒扣說明 —— 試卷第一頁直接從第 1 題開始，沒有作答須知。沒有倒扣，每題都該作答。

這是台大十年來題數最多的一份軟體考卷（25 題），但也是單題配分最低的一份（4 分）。沒有非選擇題。

逐題考點

基礎與複雜度（1–3）

• 第 1 題｜用 stack 求多項式值的 POLY(S,x) 填空 —— 就是 Horner's rule，要填 v·x+u
• 第 2 題｜已知 f(n)=O(g(n)) 且 f(n)=Ω(1)，四個推論中有幾個為真：g=Ω(f)、f·log(1+f)=O(g·log(1+g))、2^f = O(2^g)（這個是假的）、(f)^k=O((g)^k) for 0<k<1
• 第 3 題｜2022 年 DeepMind 的 AlphaTensor 用 47 次乘法（而非 49 次）相乘兩個 4×4 矩陣，問分治後 n×n 矩陣相乘的 O(n^k) 中 k 是多少 —— 答案是 log₄47（因為切成 4×4 個區塊時，子問題規模是 n/4）

隨機與理論（4–7）

• 第 4 題｜哪一組 a、b 能讓 RANDOM-PERMUTE 產生均勻隨機排列 —— 這是 Fisher-Yates shuffle，正確是 a=i, b=n
• 第 5 題｜哪一個歸約敘述已知為真（NP-hard 對 NP、NP-complete 對 NP、P 對 NP、EXP 對 NP）
• 第 6 題｜承上的變形，四個敘述中有幾個為真 —— 第 5、6 題合計 8 分全在考歸約方向
• 第 7 題｜3 個工人對 3 件工作的二分圖最大匹配，問匹配大小、是否存在完美匹配

字串與變換（8–9）

• 第 8 題｜字串 wuwvwuxv 的 KMP failure function π(0..7)，五個選項都是長度 8 的陣列
• 第 9 題｜FFT（Cooley-Tukey）靠單位根的哪一個性質達到加速 —— 答案是 symmetry property（ω^k+n/2 = −ω^k），讓問題可切成奇偶兩半

排序與選擇（10–13）

• 第 10 題｜[4, 5, 1, 10, 2, 7] 做 bottom-up BUILD-MAX-HEAP 後的陣列
• 第 11 題｜哪種 pivot 選法最能避免 quicksort 的 O(n²) 最壞情況
• 第 12 題｜bucket sort 期望線性時間的前提假設（輸入均勻分布）
• 第 13 題｜哪個演算法能保證 O(n) 最壞時間找中位數 —— median of medians

資料結構（14–21）

• 第 14 題｜用兩個 stack 實作 queue 的攤銷成本（答案 Θ(1)）
• 第 15 題｜separate chaining 的雜湊表為何需要在 load factor 超過門檻時擴張 —— 考的是「避免鏈長隨元素數線性成長」，其他選項（避免載入因子達 1、排序、消除碰撞、記憶體連續）都是干擾
• 第 16 題｜double hashing 要能走遍所有 m 格的充要條件 —— gcd(h₂(k), m) = 1。與 108 年第 6(c) 同一個觀念
• 第 17 題｜BST 刪除節點 66（用中序後繼替代）後的 preorder 序列
• 第 18 題｜Huffman 演算法的貪婪選擇由哪一個性質保證 —— 「兩個最低頻符號必為碼樹最深層的兄弟節點」
• 第 19 題｜動態表格：容量滿了加倍、元素數低於容量 1/4 時減半。問哪個敘述正確 —— 關鍵是「若改成半滿就縮小，攤銷 O(1) 會被破壞」（可構造在門檻上反覆震盪的序列）
• 第 20 題｜紅黑樹擴充 size 欄位支援 order statistics：旋轉時需更新幾個節點的 size（答案是兩個，各以子節點的 size 重算，O(1)）
• 第 21 題｜最小度數 t 的 B-tree 刪除內部節點 key 的正確做法 —— 要視左右子節點是否至少有 t 個 key 決定用前驅或後繼替代

進階 DP 與圖論（22–25）

• 第 22 題｜計算 LCS 的相異個數 C[i][j] 的正確遞迴式，五個選項的差別在重複計數的扣除項。當 L[i−1][j] = L[i][j−1] 時要用排容原理扣掉 C[i−1][j−1]
• 第 23 題｜disjoint set 的串列表示法＋union by size：n 個單元素集合做 m 次操作的總時間 —— 答案是「每個元素的代表指標最多被更新 log n 次，所以所有 UNION 共 O(n log n)」
• 第 24 題｜有向圖 BFS 的距離標記 d[v]，哪個敘述永遠為真 —— 對每條邊 (u,v) 必有 d[v] ≤ d[u]+1
• 第 25 題｜MST 的 safe edge：哪個敘述永遠成立 —— 答案是「若割 (S,V∖S) respects A，則跨越該割的最輕邊對 A 是 safe 的」。其他選項刻意把「respects A」這個前提拿掉

這份考卷的難點

1. 題數多、時間緊。 25 題裡有 10 題以上需要實際計算（第 8、10、17、22 題都要動手跑），平均每題只能分到約 4 分鐘。
2. 選項互相干擾。 第 15、19、24、25 題的錯誤選項都寫得很像對的，差別往往只在一個前提條件（例如第 25 題的「respects A」）。
3. 第 22 題（相異 LCS 計數）是全卷最難的一題，要同時處理 DP 與排容原理，五個選項只差一個扣除項。
4. 第 3 題的 AlphaTensor 是時事包裝，重點在看出「4×4 分塊 ⇒ 底數是 4」而不是 2。

準備建議

• 115 年回到課本主幹，CLRS 的排序、雜湊、紅黑樹、B-tree、攤銷分析、MST、BFS 六章覆蓋了全卷八成
• 沒有倒扣，答案卡務必填滿。 台大近三年（113 有倒扣、114、115 無倒扣）規則不固定，進場先確認卷首
• 攤銷分析連兩年考動態表格（113 第 3 題、115 第 19 題），「1/4 縮小可以、1/2 縮小不行」的理由要能講出來
• KMP failure function 連五年出現（110、111、112、115），請練到能在兩分鐘內手算完長度 10 以內的字串
• Cut property 的完整敘述（「respects A」這個前提）、以及 double hashing 的互質條件，是這一年特別強調的細節