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

題型與配分

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

逐題考點

• 第 1 題（5%）｜binary tree 的 17 個頂點為 a 到 q，給 post-order 與 in-order traversal 的結果，求 pre-order traversal
• 第 2 題（15%）｜分析 insertion sort 的平均時間複雜度：n 個相異整數（範圍 1 到 n）的序列，時間複雜度取決於 inversion 數，t(n) 為所有長度 n 序列的 inversion 總數，平均時間複雜度為 O(t(n)/n!)。已知 t(1) = 0、t(n) = a(n) + b(n)·t(n−1)（n ≥ 2），要填出 a(n)、b(n) 與 t(n)/n!。題目註明答案必須是 closed form，可用的基本運算是四則運算、階乘與 binomial coefficient
• 第 3 題（20%）｜給圖 G 的 traversal 程序 Search(G)，其中的資料結構 D 可以換成不同的實作。給兩個各用足夠大的 array 實作的資料結構 X、Y，兩者的 Initialize、Empty、Insert、Extract 都以 pseudo-code 給出，且大小遠大於 m+n：(a) X 是哪一種基礎資料結構 (b) 以 X 作為 D 時，Search 變成什麼搜尋程序 (c) Y 是哪一種基礎資料結構 (d) 以 Y 作為 D 時，Search 變成什麼搜尋程序
• 第 4 題（10%）｜給 Build-Max-Heap(A) 與 Heapify(A, i) 的 pseudo-code，分析 Build-Max-Heap(A) 的時間複雜度，題目要求說明結果是怎麼推導出來的
• 第 5 題（15%，3 小題各 5%）｜解 recurrence：(a) T(n) = T(n/3) + 1 (b) T(n) = T(n/3) + T(2n/3) + 3n (c) T(n) = T(n−2) + T(n−1) + 1
• 第 6 題（20%）｜0-1 Knapsack：
• 第 6(a) 題（7%）｜描述暴力解法並分析時間複雜度
• 第 6(b) 題（5%）｜DP 表 F[i,j]（前 i 個物品、容量為 j 的背包的最大價值）的 recurrence
• 第 6(c) 題（5%）｜背包容量 W = 6，物品 A（重 2、值 4）、B（重 3、值 2）、C（重 1、值 2）、D（重 4、值 3），每種物品各一個，填出 F 表
• 第 6(d) 題（3%）｜(c) 的實例中，下列哪些 greedy 選擇會得到最佳解（可複選）：取價值最高的物品、取重量最輕的物品、取價值／重量最高的物品
• 第 7 題（15%）｜給 Floyd-Warshall 的 pseudo-code：
• 第 7(a) 題（5%）｜說明 d_ij^(k) 的意義
• 第 7(b) 題（5%）｜給 5 個頂點的權重矩陣 W，寫出 D⁽¹⁾
• 第 7(c) 題（5%）｜輸入圖有負權重但沒有 negative cycle 時，Floyd-Warshall 是否仍給出正確結果，並簡述理由

作答時要注意的地方

1. 第 2 題要求 closed form 答案，可用的運算限於四則運算、階乘與 binomial coefficient。
2. 第 4 題要求說明結果是怎麼推導出來的。
3. 第 6(d) 是可複選的題目，針對 (c) 給定的實例作答。
4. 第 7(b) 要的是 D⁽¹⁾，不是 D⁽⁰⁾。
5. 第 7(c) 要求簡述理由。
6. 第 7(a) 題與 106 年第 8(a) 題相同，兩年的 (b) 都是填 D⁽¹⁾。

準備方向

• binary tree 與 BST：111 第 1 題；107 第 3(a) 題、108 第 1.1、1.8、1.10、1.12 題、109 第一(2)、一(7)、二題、110 第 2(a)、3-5、8 題、112 第 3 題、113 第 8、10 題、114 第三(二)(四)題、115 第 5 題也有。
• 排序演算法：111 第 2 題；106 第 3 題、107 第 1(a)(b) 題、108 第 1.11 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、112 第 5、7 題、114 第二(二)題、115 第 5 題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：111 第 3 題；106 第 4(1) 題、107 第 2(b) 題、108 第 1.3、1.5、3、5(a) 題、110 第 6 題、112 第 6 題、113 第 9、13(a) 題、114 第四題、115 第 8 題也有。
• 複雜度分析：111 第 4、5 題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、108 第 4(a)(b) 題、109 第一(8)、四(c)、六(a)題、110 第 1、2 題、112 第 1(b)、8(a) 題、113 第 8(a)(b) 題、114 第三、五題、115 第 1、5、6 題也有。
• Heap 與 priority queue：111 第 4 題；106 第 5 題、107 第 3(b) 題、108 第 1.6、1.7 題、109 第一(1)、一(6)、一(9)題、110 第 2(c)(d)、5 題、112 第 5 題、114 第三(三)題、115 第 4 題也有。
• DP（rod cutting／knapsack／LCS／matrix chain）：111 第 6 題；106 第 7 題、108 第 4 題、112 第 8 題、115 第 7 題也有。
• shortest path：111 第 7 題；106 第 4(2)、8 題、107 第 4、6 題、110 第 10、11 題、113 第 12 題、114 第七(二)題、115 第 9 題也有。
• 負權重對演算法的影響：111 第 7(c) 題；106 第 8(c) 題、107 第 6(c) 題、109 第七(d)題、110 第 11(a) 題、114 第七題也有。