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

題型與配分

全卷 6 頁、6 大題、100 分，作答於答案卷，卷面沒寫倒扣。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。第 1 題旁邊另有提醒：「選擇題請於『作答區』作答，勿答於『評分欄』以免扣分」。

逐題考點

• 第 1.1 題（2%）｜depth first search 相當於 binary tree 的哪一種 traversal
• 第 1.2 題（2%）｜用 stack 把 infix 4 + 3*(6*3-12) 轉成 postfix，stack 上同時最多有幾個符號
• 第 1.3 題（2%）｜6×6 adjacency matrix 表示的圖有幾個 component
• 第 1.4 題（2%）｜breadth first search 用的是哪一種資料結構
• 第 1.5 題（2%）｜給 A 到 E 五個頂點的圖，拿掉哪一條邊會變成 bipartite graph
• 第 1.6 題（2%）｜4、8、7、5、6、3、9 存在 T[1] 到 T[7]，heap sort 先調整成 max heap，問 T[3] 的數字
• 第 1.7 題（2%）｜接續 1.6，交換 T[1] 與 T[7] 後把 T[1] 到 T[6] 重新調整成 max heap，4 會在哪個位置
• 第 1.8 題（2%）｜binary tree 只有葉節點與 degree 2 的節點，葉節點 101 個，degree 2 的節點有幾個
• 第 1.9 題（3%，複選）｜只有 head pointer 的無序 singly linked list，前端插入、尾端插入、刪除第一個、刪除最後一個節點，哪些能在 O(1) 完成
• 第 1.10 題（3%，複選）｜四棵樹中哪些滿足 AVL tree 的性質
• 第 1.11 題（3%，複選）｜八個整數做完 quicksort 的第一次 partition 後是 3 5 1 6 8 11 9 10，哪些數可能是 pivot
• 第 1.12 題（3%，複選）｜以 array 表示 complete binary tree，存在索引 w 的節點，其子節點的索引是哪些（六個選項）
• 第 2(a) 題（5%）｜補完以遞迴反向印出 linked list 的 C 函式 fun1，一個空格
• 第 2(b) 題（5%）｜補完 n×n 矩陣乘法三層迴圈中 c[i][j] 那一行
• 第 2(c) 題（5%）｜補完 iterative binary search 的兩個空格（題目程式是 Java 寫法，public static int、arr.length）
• 第 3 題（7%）｜6 個頂點（0 到 5）的 undirected graph 以 adjacency matrix 給出：(a) 3% 找出 articulation points (b) 4% 從 0 出發的 DFS 與 BFS，有多個相鄰頂點時先走編號小的
• 第 4 題（25%）｜LCS，題目以 ABABCA 與 ABCBA 為例：(a) 10% 描述暴力解法並分析時間複雜度 (b) 10% 描述 DP 解法，寫出 recurrence 並分析時間複雜度 (c) 5% 用 (b) 的 recurrence 填表，求 ABABCA 與 ABCBA 的 LCS
• 第 5 題（15%，3 小題各 5%）｜給 a 到 h 八個頂點的 directed graph：(a) 從 a 開始 DFS，鄰居依字母順序處理 (b) 寫出一個 topological sort (c) 說明 topological sort 無解的情況
• 第 6 題（10%）｜X 可以在多項式時間驗證，Y 是 P 問題、Z 是 NP-complete 問題，給四種 reduction（X ≤P Y、Y ≤P X、X ≤P Z、Z ≤P X）：(a) 5% 要證明 X 是 NP-complete，該做哪一個，為什麼 (b) 5% 要證明 X 是 computationally tractable，該做哪一個，為什麼

作答時要注意的地方

1. 第 1 題 1.1–1.8 單選各 2 分、1.9–1.12 複選各 3 分，卷面沒寫倒扣，也沒寫複選題怎麼給分。
2. 第 1.6 題題目前面用 T[ ]、問題寫 tree[3]，指的是同一個 array。
3. 第 1.11 題卷面把 pivot 印成 pilot。
4. 第 2 題三段程式各 5 分，(c) 是 Java 語法。
5. 第 3(b) 題與第 5(a) 題都規定了相鄰頂點的處理順序。
6. 第 5(b) 題答案不唯一，題目要求寫出其中一個。
7. 第 6 題兩小題都要說明理由。
8. 第 4 題 (a)(b)(c) 的架構與 112 年第 8(a)(b)(c) 題相同（暴力解、recurrence、填表）。

準備方向

• binary tree 與 BST：108 第 1.1、1.8、1.10、1.12 題；107 第 3(a) 題、109 第一(2)、一(7)、二題、110 第 2(a)、3-5、8 題、111 第 1 題、112 第 3 題、113 第 8、10 題、114 第三(二)(四)題、115 第 5 題也有。
• Stack 與 queue 的應用（運算式轉換、迷宮、BFS）：108 第 1.2、1.4 題；106 第 2(2) 題、109 第三題、112 第 3 題也有。
• 圖的表示法：108 第 1.3 題；109 第一(3)題、110 第 3-1、3-2 題、112 第 6(a) 題、113 第 9 題、114 第三(一)、四題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：108 第 1.3、1.5、3、5(a) 題；106 第 4(1) 題、107 第 2(b) 題、110 第 6 題、111 第 3 題、112 第 6 題、113 第 9、13(a) 題、114 第四題、115 第 8 題也有。
• Heap 與 priority queue：108 第 1.6、1.7 題；106 第 5 題、107 第 3(b) 題、109 第一(1)、一(6)、一(9)題、110 第 2(c)(d)、5 題、111 第 4 題、112 第 5 題、114 第三(三)題、115 第 4 題也有。
• Linked list、stack 與 queue 的實作：108 第 1.9、2(a) 題；106 第 2(1) 題、109 第四題、110 第 7 題、112 第 2 題、113 第 11 題、114 第一題也有。
• 排序演算法：108 第 1.11 題；106 第 3 題、107 第 1(a)(b) 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、111 第 2 題、112 第 5、7 題、114 第二(二)題、115 第 5 題也有。
• C 程式的填空、追蹤與手寫：108 第 2 題；106 第 2(1)、3(1)、4(2)、5(1) 題、107 第 1(c)(d) 題、110 第 7、8 題、112 第 1、2、6 題、113 第 1–4、6、7、8(c)、11、12 題、114 第一題也有。
• binary search 與循序搜尋：108 第 2(c) 題；107 第 1(c)(d) 題也有。
• 複雜度分析：108 第 4(a)(b) 題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、109 第一(8)、四(c)、六(a)題、110 第 1、2 題、111 第 4、5 題、112 第 1(b)、8(a) 題、113 第 8(a)(b) 題、114 第三、五題、115 第 1、5、6 題也有。
• DP（rod cutting／knapsack／LCS／matrix chain）：108 第 4 題；106 第 7 題、111 第 6 題、112 第 8 題、115 第 7 題也有。
• topological sort：108 第 5(b)(c) 題。
• P、NP 與 NP-complete：108 第 6 題；107 第 8 題也有。