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

題型與配分

全卷 6 頁、10 題、100 分，每題 10 分，題目標為 Question 1 到 Question 10，作答於答案卷，卷面沒寫倒扣。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。

逐題考點

• 第 1 題（10%）｜給 1-D convolutional neural network 前向傳播的 pseudo-code（輸入 X ∈ R^C_in×L、參數 W ∈ R^{C_out×C_in×k}，迴圈依序跑 i、j、c、m 四層加上累加），在 k ≪ L 的條件下，以 Θ 表示最壞執行時間，式子中含 C_in、C_out、k、L
• 第 2 題（10%）｜n 個頂點的 undirected graph G，對每一對頂點（包含 u = w 的情況）各以 50% 的機率決定該邊是否加入邊集合 E，以 |V| 表示邊數的期望值
• 第 3 題（10%）｜給 Rabin-Karp 的 pseudo-code，P = 12、基數 r = 10（字串只含數字 0 到 9）、q = 11，找出一個恰好 8 位數的 T，使得 0 ≤ i < length(T) − 1 的每個 T[i..i+1] 都發生 spurious hit
• 第 4 題（10%）｜用 max-heap 的 priority queue 可以讓 MAX-HEAP-INSERT 與 HEAP-EXTRACT-MAX 的最壞時間複雜度都是 O(log n)。說明如何建出修改版的 priority queue，支援 MAX-HEAP-INSERT 與新的 HEAP-EXTRACT-FIRST-QUARTILE（回傳第 ⌈n/4⌉ 大的元素，n 是目前的元素個數），兩個操作的最壞執行時間都要是 O(log n)
• 第 5 題（10%）｜Tree sort 先建 binary search tree，再做 in-order traversal。以沒有自平衡機制的 BST 實作，以 Θ 表示最佳情況與最壞情況的執行時間，並各舉一個例子說明
• 第 6 題（10%）｜選擇題，f(n) 與 g(n) 是漸近為正的函數，下列猜想哪些是對的，答案必須完全正確才得分：(A) f(n) = O(g(n)) 蘊含 g(n) = Ω(f(n)) (B) f(n) = O(g(n)) 蘊含 2^f(n) = O(2^g(n)) (C) f(n) + o(f(n)) = Θ(f(n)) (D) f(n) = Θ(f(n/2)) (E) f(n) = O((f(n))²)
• 第 7 題（10%）｜MATRIX-CHAIN-ORDER 的 pseudo-code 給在 Figure 1，R(i,j) 是在計算其他表格項目時 m[i,j] 被參照的次數，以 n 表示整個表格的參照總數 ΣΣ R(i,j)
• 第 8 題（10%）｜DFS 後，邊可以分成 tree、back、forward、cross 四類。對 Figure 2 的 directed graph（節點 0 到 12，以節點 0 為起點）做 DFS，依編號由小到大 traverse，求 tree edge 與 back edge 各有幾條
• 第 9 題（10%）｜對 Figure 3 的圖（節點 a 到 f，圖說寫 undirected，圖上的邊畫有箭頭）執行 Floyd-Warshall，在答案卷上用與 Table 1 相同的格式更新 shortest path 距離表，直到演算法結束
• 第 10 題（10%）｜Huffman code。題目以 2025 年台灣年度代表字票選為背景，字串為 MMMMMMAAAASSSSSRRRRRRRRREECCCCCCCCL，頻率較低的永遠放在 binary tree 的左葉並編為 0。兩小題都是 (A) 到 (D) 的選擇題：(1) 字元 A 與 S 的 Huffman code (2) 把 101101001001010010000 依 Huffman code 解碼得到的明文

作答時要注意的地方

1. 每題 10 分，沒有小題配分。
2. 第 3 題 T 要恰好 8 位數。
3. 第 4 題兩個操作的最壞執行時間都要是 O(log n)。
4. 第 5 題要各舉一個最佳與最壞情況的例子。
5. 第 6 題的卷面寫「you'll earn the point once your answer is exactly correct」，選項要完全正確才得分。
6. 第 8 題要依編號由小到大 traverse。
7. 第 9 題要用 Table 1 的格式作答。
8. 第 10 題規定頻率較低的放左葉並編為 0。

準備方向

• 複雜度分析：115 第 1、5、6 題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、108 第 4(a)(b) 題、109 第一(8)、四(c)、六(a)題、110 第 1、2 題、111 第 4、5 題、112 第 1(b)、8(a) 題、113 第 8(a)(b) 題、114 第三、五題也有。
• 隨機圖的期望邊數：115 第 2 題。
• string matching（Rabin-Karp）：115 第 3 題。
• Heap 與 priority queue：115 第 4 題；106 第 5 題、107 第 3(b) 題、108 第 1.6、1.7 題、109 第一(1)、一(6)、一(9)題、110 第 2(c)(d)、5 題、111 第 4 題、112 第 5 題、114 第三(三)題也有。
• 排序演算法：115 第 5 題；106 第 3 題、107 第 1(a)(b) 題、108 第 1.11 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、111 第 2 題、112 第 5、7 題、114 第二(二)題也有。
• binary tree 與 BST：115 第 5 題；107 第 3(a) 題、108 第 1.1、1.8、1.10、1.12 題、109 第一(2)、一(7)、二題、110 第 2(a)、3-5、8 題、111 第 1 題、112 第 3 題、113 第 8、10 題、114 第三(二)(四)題也有。
• asymptotic notation 的猜想：115 第 6 題。
• DP（rod cutting／knapsack／LCS／matrix chain）：115 第 7 題；106 第 7 題、108 第 4 題、111 第 6 題、112 第 8 題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：115 第 8 題；106 第 4(1) 題、107 第 2(b) 題、108 第 1.3、1.5、3、5(a) 題、110 第 6 題、111 第 3 題、112 第 6 題、113 第 9、13(a) 題、114 第四題也有。
• shortest path：115 第 9 題；106 第 4(2)、8 題、107 第 4、6 題、110 第 10、11 題、111 第 7 題、113 第 12 題、114 第七(二)題也有。
• Huffman 與最佳合併：115 第 10 題；112 第 9、10 題、114 第二(一)題也有。