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

題型與配分

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

逐題考點

• 第一(一)題（4%）｜用 array 實作的 stack（MAX 為 1000，items[] 與 top），補完 isEmpty、push、pop 的 4 個空格，假設使用前先呼叫 initStack()
• 第一(二)題（6%）｜用 stack 檢查字串的括號是否平衡的 isBalanced，補完 3 個空格
• 第一(三)題（10%）｜合併兩條已排序的 linked list，結果以一個 dummy node 作為 head，list1 與 list2 都可能是 NULL，補完 mergeSortedLists 的 5 個空格
• 第二(一)題（4%）｜7 個已排序的檔案，大小為 1200、900、2500、3200、800、1800、1500，要用 2-way merge 合併多次，每次合併的結果 寫回檔案，決定合併的順序，使資料 I/O 的總量最小
• 第二(二)題（4%，兩小題各 2%）｜9 個數字的 array 4、10、1、18、2、9、20、7、12，給 (A) 到 (D) 四個中間狀態，哪一個是 insertion sort 可能的中間結果，哪一個是 iterative merge sort 可能的中間結果
• 第三題（12%，4 小題各 3%）｜選擇題
• 第三(一)題｜m 個頂點、n 條邊的圖用 adjacency matrix 表示，取得終止於某個頂點的所有邊的時間複雜度（單選）
• 第三(二)題｜n 個節點的 binary tree，求高度的最壞時間複雜度（單選）
• 第三(三)題｜n 個節點的 max heap 中尋找某個元素的時間複雜度（單選）
• 第三(四)題｜BST 的哪些 traversal 可以用來重建出相同的樹結構：preorder、inorder、postorder、level-order（多選）
• 第四題（10%）｜給圖 G 的 adjacency multi-list（頂點 V0 到 V6，邊 E1 到 E8）：(一) 3% 從 V3 出發的 BFS spanning tree (二) 4% 為了找 articulation point，從頂點 3 出發 traverse，寫出每個頂點的 dfn 與 low，有多個相鄰頂點時先走編號小的 (三) 3% 畫出依 articulation point 分開的 biconnected component
• 第五題（7%）｜array A[1:N]，前 n 個位置（n < N/2）存遞增（non-descending）排列的 n 個整數，其餘位置都存一個比 a_n 大的數 M。輸入是整數 y（y < M），設計 O(log n) 的演算法找出使 A[k] = y 的索引 k，或回報不存在。輸入只有 y，不包含 n 與 N
• 第六題（8%）｜Z_n 是模 n 的 multiplicative group，a 在 Z_n 中的 inverse 是使 a × b = 1 的 b（例如 Z₁₅ 中 2 的 inverse 是 8）。輸入兩個整數 a 與 n，設計有效率的演算法求 a 在 Z_n 中的 inverse
• 第七題（15%）｜帶權 undirected graph G = (V, E, w)，部分邊的權重為負：
• 第七(一)題（7%）｜能不能把所有權重加上同一個固定的數使其都不是負的，再執行演算法得到原圖正確的 minimum spanning tree
• 第七(二)題（8%）｜同樣的做法用在 shortest path 上是否可行
• 兩小題都要求：可行的話給證明或合理的理由，不可行的話給反例說明輸出會不同
• 第八題（20%）｜帶權 undirected graph G，|V| > 2，每條邊的權重 w(e) > 0，Hamiltonian cycle 是包含所有頂點的 simple cycle。方法是 (a) 求 G 的 minimum spanning tree T (b) 從任一頂點 v₀ 出發，取 T 的 depth first listing v₀, v₁, …, v_n−1 (c) 輸出 cycle C = v₀, v₁, …, v_n−1, v₀。假設 G 的邊權滿足 triangle inequality，C 是 G 的最佳 Hamiltonian cycle，依下列步驟證明 w(C) ≤ 2w(C)：
• 第八(一)題（9%）｜w(C) ≤ 2w(T)
• 第八(二)題（8%）｜C 中任一條邊 e，w(T) ≤ w(C − {e})
• 第八(三)題（3%）｜w(C) ≤ 2w(C*)

作答時要注意的地方

1. 第一題要標明空格編號，填空格內容即可。
2. 第二(二)題兩小題各要從 (A) 到 (D) 選一個。
3. 第三(四)題是多選題，其他三題是單選。
4. 第四題有多個相鄰頂點時，先走編號小的。
5. 第五題的輸入只有 y，不包含 n 與 N。
6. 第七題兩小題都要證明或給反例。
7. 第八題的證明分三步，配分是 9、8、3。

準備方向

• C 程式的填空、追蹤與手寫：114 第一題；106 第 2(1)、3(1)、4(2)、5(1) 題、107 第 1(c)(d) 題、108 第 2 題、110 第 7、8 題、112 第 1、2、6 題、113 第 1–4、6、7、8(c)、11、12 題也有。
• Linked list、stack 與 queue 的實作：114 第一題；106 第 2(1) 題、108 第 1.9、2(a) 題、109 第四題、110 第 7 題、112 第 2 題、113 第 11 題也有。
• 排序演算法：114 第二(二)題；106 第 3 題、107 第 1(a)(b) 題、108 第 1.11 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、111 第 2 題、112 第 5、7 題、115 第 5 題也有。
• Huffman 與最佳合併：114 第二(一)題；112 第 9、10 題、115 第 10 題也有。
• 複雜度分析：114 第三、五題；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) 題、115 第 1、5、6 題也有。
• 圖的表示法：114 第三(一)、四題；108 第 1.3 題、109 第一(3)題、110 第 3-1、3-2 題、112 第 6(a) 題、113 第 9 題也有。
• Heap 與 priority queue：114 第三(三)題；106 第 5 題、107 第 3(b) 題、108 第 1.6、1.7 題、109 第一(1)、一(6)、一(9)題、110 第 2(c)(d)、5 題、111 第 4 題、112 第 5 題、115 第 4 題也有。
• binary tree 與 BST：114 第三(二)(四)題；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 題、115 第 5 題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：114 第四題；106 第 4(1) 題、107 第 2(b) 題、108 第 1.3、1.5、3、5(a) 題、110 第 6 題、111 第 3 題、112 第 6 題、113 第 9、13(a) 題、115 第 8 題也有。
• 未知長度 array 上的搜尋：114 第五題。
• 模數下的 inverse：114 第六題。
• minimum spanning tree（Prim／Kruskal）：114 第七(一)題；109 第七題、110 第 10 題、112 第 4 題也有。
• shortest path：114 第七(二)題；106 第 4(2)、8 題、107 第 4、6 題、110 第 10、11 題、111 第 7 題、113 第 12 題、115 第 9 題也有。
• 邊權加減常數的影響：114 第七題；110 第 11(d) 題也有。
• 負權重對演算法的影響：114 第七題；106 第 8(c) 題、107 第 6(c) 題、109 第七(d)題、110 第 11(a) 題、111 第 7(c) 題也有。
• approximation algorithm（TSP）：114 第八題。