115 師大資工所軟體考點分析
全卷 10 題、每題 10 分，結構最整齊的一年。第 1 題把 1-D 卷積神經網路當複雜度分析題，第 4 題要設計支援「取第 n/4 大」的優先佇列。
題型與配分
科目「軟體基礎」，適用系所：資訊工程學系，全卷 6 頁、10 題、100 分，每題 10 分。
這是師大六年來結構最整齊的一份（前幾年的配分都不均勻）。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | 1-D CNN 的複雜度 | 10% |
| 2 | 隨機圖的期望邊數 | 10% |
| 3 | Rabin-Karp 的 spurious hit 構造 | 10% |
| 4 | 支援「取第 n/4 大」的優先佇列 | 10% |
| 5 | Tree sort 的最佳／最壞複雜度 | 10% |
| 6 | 漸進記號的五個猜想 | 10% |
| 7 | Matrix-chain 表格的參照次數 | 10% |
| 8 | DFS 的邊分類 | 10% |
| 9 | Floyd-Warshall 完整表格 | 10% |
| 10 | Huffman 編碼與解碼 | 10% |
逐題考點
- 第 1 題（10%）｜給 1-D 卷積神經網路前向傳播的五層巢狀迴圈 pseudo-code，以 C_in、C_out、k、L 表示最壞情況的 Θ 複雜度（答案 Θ(C_out · C_in · k · (L−k+1))）
- 第 2 題（10%）｜隨機圖：每一對頂點（含自環）以 50% 機率放入邊集合，以 |V| 表示期望邊數。注意題目說「including the case when u == v」，所以是 C(|V|,2) + |V| 對，期望值為其一半
- 第 3 題（10%）｜Rabin-Karp：給 P = 12、radix = 10、q = 11，構造一個恰好 8 位數的 T，使得每一個位移都發生 spurious hit。關鍵：12 mod 11 = 1，要讓所有長度 2 的子字串模 11 都等於 1
- 第 4 題（10%）｜設計改良版優先佇列，同時支援
MAX-HEAP-INSERT與新的HEAP-EXTRACT-FIRST-QUARTILE（取第 ⌈n/4⌉ 大的元素），兩者都要 O(log n) 最壞情況。標準解：用兩個 heap（前 n/4 大的用 min-heap、其餘用 max-heap）並在插入時維持大小比例 - 第 5 題（10%）｜Tree sort（建 BST 後中序走訪）用不平衡 BST 時的最佳與最壞 Θ 複雜度，並各舉一個例子（最佳 Θ(n log n)：平衡插入順序；最壞 Θ(n2)：已排序輸入）
- 第 6 題（10%，全對才給分）｜五個漸進猜想何者為真：
- (A) f = O(g) ⇒ g = Ω(f)（真）
- (B) f = O(g) ⇒ 2f = O(2g)（假）
- (C) f + o(f) = Θ(f)（真）
- (D) f(n) = Θ(f(n/2))（假）
- (E) f = O(f2)（假，f 可能小於 1）
- 第 7 題（10%）｜計算
MATRIX-CHAIN-ORDER中表格項目 m[i,j] 被參照的總次數 Σ R(i,j)，以 n 表示。答案是 n3/3 − n/3（即 2·C(n+1,3) 的形式） - 第 8 題（10%）｜給有向圖從節點 0 做 DFS（依編號遞增走訪），數出 tree edge 與 back edge 各有幾條
- 第 9 題（10%）｜對給定的無向圖套用 Floyd-Warshall，依題目給的表格格式更新到演算法結束
- 第 10 題（10%，2 小題）｜對字串
MMMMMMAAAASSSSSRRRRRRRRREECCCCCCCCL建 Huffman code（題目規定頻率低的放左葉、編碼為 0）：(1) A 與 S 的碼字 (2) 解碼101101001001010010000得到的明文
這份考卷的難點
- 第 4 題（10 分）的「取第 n/4 大」優先佇列是全卷最需要設計的一題，要想到用兩個 heap 分割並在每次操作後重新平衡。
- 第 3 題要構造出全部位移都 spurious hit 的字串，必須理解 Rabin-Karp 的雜湊值計算與模運算的性質。
- 第 7 題的參照次數總和需要推導：m[i,j] 被參照的次數與 (i,j) 的位置有關，要算出封閉式。
- 第 6 題全對才給分，五個漸進猜想中有三個為假，(E) 的反例（f(n) = 1/n 類的函數）容易漏掉。
準備建議
- 115 年出現機器學習的情境包裝（1-D CNN），但實際上只是巢狀迴圈的複雜度分析 —— 不要被名詞嚇到
- 漸進記號的猜想判斷（115 第 6 題）在台大 115 第 2 題、交大 114 第 1 題同時出現，是跨校高頻題
- Rabin-Karp 與 spurious hit 是字串比對的進階內容，師大 115 首次考
- Huffman 的解碼（115 第 10(2) 題）要注意題目對「低頻放左、編碼 0」的規定，與一般習慣可能相反
- 師大六年來必考 Floyd-Warshall（111、115）與 Huffman（112、114、115），這兩個主題投報率最高