115 台大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 7 頁、25 題、100 分，每題 4 分，全部單選，沒有非選擇題。

卷首沒有計分或倒扣說明，試卷第一頁直接從第 1 題開始。

逐題考點

基礎與複雜度（第 1–3 題）

• 第 1 題｜用 stack 求多項式值的 POLY(S,x) 填空
• 第 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 矩陣，問 divide and conquer 後 n×n 矩陣相乘的 O(n^k) 中 k 是多少

隨機與理論（第 4–7 題）

• 第 4 題｜哪一組 a、b 能讓 RANDOM-PERMUTE 產生均勻 random permutation
• 第 5 題｜哪一個 reduction 敘述已知為真（NP-hard 對 NP、NP-complete 對 NP、P 對 NP、EXP 對 NP）
• 第 6 題｜承上的變形，四個敘述中有幾個為真。第 5、6 題合計 8 分都在考 reduction 方向
• 第 7 題｜3 個工人對 3 件工作的 bipartite graph maximum matching，問 matching 大小、是否存在 perfect matching

字串與變換（第 8–9 題）

• 第 8 題｜字串 wuwvwuxv 的 KMP failure function π(0..7)，五個選項都是長度 8 的 array
• 第 9 題｜FFT（Cooley-Tukey）靠 root of unity 的哪一個性質達到加速

排序與選擇（第 10–13 題）

• 第 10 題｜[4, 5, 1, 10, 2, 7] 做 bottom-up BUILD-MAX-HEAP 後的 array
• 第 11 題｜哪種 pivot 選法最能避免 quicksort 的 O(n²) 最壞情況
• 第 12 題｜bucket sort 期望線性時間的前提假設
• 第 13 題｜哪個演算法能保證 O(n) 最壞時間找 median

資料結構（第 14–21 題）

• 第 14 題｜用兩個 stack 實作 queue 的 amortized cost
• 第 15 題｜separate chaining 的 hash table 為何需要在 load factor 超過門檻時擴張
• 第 16 題｜double hashing 要能走遍所有 m 格的充要條件。與 108 年第 6(c) 是同一個觀念
• 第 17 題｜BST 刪除節點 66（用 inorder successor 替代）後的 preorder 序列
• 第 18 題｜Huffman 演算法的 greedy 選擇由哪一個性質保證
• 第 19 題｜動態表格：容量滿了加倍、元素數低於容量 1/4 時減半。問哪個敘述正確
• 第 20 題｜red-black tree 擴充 size 欄位支援 order statistics：旋轉時需更新幾個節點的 size
• 第 21 題｜最小 degree t 的 B-tree 刪除內部節點 key 的正確做法

進階 DP 與圖論（第 22–25 題）

• 第 22 題｜計算 LCS 的相異個數 C[i][j] 的正確 recurrence，五個選項的差別在重複計數的扣除項
• 第 23 題｜disjoint set 的 linked list 表示法加 union by size：n 個單元素集合做 m 次操作的總時間
• 第 24 題｜directed graph BFS 的距離標記 d[v]，哪個敘述永遠為真
• 第 25 題｜MST 的 safe edge：哪個敘述永遠成立

作答時要注意的地方

1. 25 題裡第 8、10、17、22 題等十題以上要動手計算。
2. 第 15、19、24、25 題的選項敘述很像，差別常只在一個前提條件。
3. 第 22 題五個選項只差重複計數的扣除項。
4. 第 3 題以 AlphaTensor 為背景，題目看的是分塊方式對 recurrence 的影響。

準備方向

• 排序、hash、red-black tree、B-tree、amortized analysis、MST、BFS 這幾章在 115 年都有題目。
• 動態表格的 amortized analysis 在 113 第 3 題與 115 第 19 題連續兩年考，縮小門檻的設計理由要能講出來。
• KMP failure function 在 110、111、112、115 都出現。
• MST 的 cut property 的完整敘述，以及 double hashing 的條件。