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

題型與配分

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

逐題考點

• 第 1 題（12%，4 小題各 3%）｜array 6、3、8、1、4、5、9、2 由小到大排序：(a) selection sort 主迴圈前 5 輪之後的 array (b) insertion sort 主迴圈前 5 輪之後的 array (c) 補完遞迴 binary search 的 C/C++ 程式（middle 的算式與兩個遞迴呼叫的範圍，共三個空格） (d) 寫出 sequential search 的 C/C++ 程式
• 第 2(a) 題（4%）｜5×5 sparse matrix M，畫出能有效存取同一列與同一行非零項的鏈結表示
• 第 2(b) 題（4%）｜把 M 當成 5 個節點（N0 到 N4）directed graph 的 adjacency matrix，M[i, j] 是邊權，從 N0 出發，依邊的方向寫出 DFS 與 BFS 的拜訪順序
• 第 3(a) 題（4%）｜binary tree 以 array（索引 0 到 15，「-」是空）表示，題目給 parent、left child、right child 的索引公式，寫出 inorder 與 postorder traversal 結果
• 第 3(b) 題（6%）｜依序插入 4、10、20、40、2、15、3、1、18 到 max heap，寫出每次插入後的 heap
• 第 4 題（10%）｜3 個節點的 directed graph 以 adjacency matrix 給出：(a) 6% 寫出求 all-pairs shortest paths 的 pseudo-code (b) 4% 寫出這張圖的結果
• 第 5 題（10%）｜AOE 網路，起點 V0、終點 V8，12 個活動 a1 到 a12 的成本以表格給出：(a) 6% 求每個活動的 earliest 與 latest starting time，要說明計算過程 (b) 4% 找出位於所有 critical path 上的 critical activities
• 第 6 題（15%，3 小題各 5%）｜給 Dijkstra 的 pseudo-code：(a) 演算法算的是什麼 (b) 為什麼可以算是 greedy 演算法 (c) 舉一個 Dijkstra 不適用的條件，並用例子說明
• 第 7 題（25%）｜maximum subarray 問題，題目以 −9、10、−9、10、−5、4 為例：
• 第 7(a) 題（5%）｜描述暴力解法並說明時間複雜度
• 第 7(b) 題（8%）｜divide and conquer 把 A[low…high] 從 mid 分開，maximum subarray 可能整個在左半、整個在右半或跨過中點，描述在線性時間內找出跨過中點的 maximum subarray 的方法
• 第 7(c) 題（5%）｜寫出 divide and conquer 執行時間的 recurrence 並求解
• 第 7(d) 題（7%）｜以 DP 的想法（從左往右掃、記錄目前為止的 maximum subarray）設計非遞迴、線性時間的演算法，回傳最大和
• 第 8 題（10%）｜假設 P ≠ NP，畫出 P、NP、NP-complete、NP-hard 的 Venn 圖

作答時要注意的地方

1. 第 1(a)(b) 題問的是主迴圈前 5 輪之後的 array。
2. 第 1(c) 題卷面的條件寫成 x <= a[middle] 接遞迴、x > a[middle] 接遞迴，最後才 return middle，程式碼照卷面印的。
3. 第 2(b) 題要照邊的方向 traverse。
4. 第 3(b) 題要寫出每次插入後的 heap，共 9 個。
5. 第 5(a) 題要說明計算過程；(b) 問的是位於所有 critical path 上的活動。
6. 第 6(c) 題要附例子。
7. 第 7(d) 題要求非遞迴、線性時間，回傳的是最大和。

準備方向

• 排序演算法：107 第 1(a)(b) 題；106 第 3 題、108 第 1.11 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、111 第 2 題、112 第 5、7 題、114 第二(二)題、115 第 5 題也有。
• C 程式的填空、追蹤與手寫：107 第 1(c)(d) 題；106 第 2(1)、3(1)、4(2)、5(1) 題、108 第 2 題、110 第 7、8 題、112 第 1、2、6 題、113 第 1–4、6、7、8(c)、11、12 題、114 第一題也有。
• binary search 與循序搜尋：107 第 1(c)(d) 題；108 第 2(c) 題也有。
• sparse matrix 的表示與 transpose：107 第 2(a) 題；112 第 1 題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：107 第 2(b) 題；106 第 4(1) 題、108 第 1.3、1.5、3、5(a) 題、110 第 6 題、111 第 3 題、112 第 6 題、113 第 9、13(a) 題、114 第四題、115 第 8 題也有。
• binary tree 與 BST：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 第三(二)(四)題、115 第 5 題也有。
• Heap 與 priority queue：107 第 3(b) 題；106 第 5 題、108 第 1.6、1.7 題、109 第一(1)、一(6)、一(9)題、110 第 2(c)(d)、5 題、111 第 4 題、112 第 5 題、114 第三(三)題、115 第 4 題也有。
• shortest path：107 第 4、6 題；106 第 4(2)、8 題、110 第 10、11 題、111 第 7 題、113 第 12 題、114 第七(二)題、115 第 9 題也有。
• AOE 網路與 critical activity：107 第 5 題；109 第五題也有。
• 負權重對演算法的影響：107 第 6(c) 題；106 第 8(c) 題、109 第七(d)題、110 第 11(a) 題、111 第 7(c) 題、114 第七題也有。
• 複雜度分析：107 第 7(a)(c) 題；106 第 3(2)、5(2)、6(b) 題、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 第 1、5、6 題也有。
• maximum subarray（暴力、divide and conquer、DP）：107 第 7 題。
• P、NP 與 NP-complete：107 第 8 題；108 第 6 題也有。