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

題型與配分

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

逐題考點

• 第 1 題（10%）｜編譯器的符號表要支援 Search、Insert、Delete，五種資料結構：(a) array 存的無序 linear list (b) array 存的有序 linear list (c) linked list 存的有序 linear list (d) 高度平衡的 binary search tree (e) 大小遠大於資料量、幾乎不 collision 的 hash table。五小題問哪些結構能用 binary search、哪些 Insert 是 O(1)、哪些 Search 是 O(log n)、一般而言搜尋最差的是哪個、最常用來建符號表的是哪個，每小題答案可能不只一個
• 第 2(1) 題｜六個以 C++ 寫成、變數名稱沒有對應語意的函式（function1 到 function6），分別實作 stack、queue、circular queue 的 Add 或 Delete，選出最可能是 (i) stack 的 Add (ii) queue 的 Delete (iii) circular queue 的 Add 的函式
• 第 2(2) 題｜迷宮找路徑、infix 轉 postfix、圖的 breadth first search 各需要 stack 還是 queue
• 第 3(1) 題｜遞迴 quicksort 的 C++ 函式，pivot 取 list[left]，補完 SWAP 的兩個參數與第一個遞迴呼叫的兩個參數，共四個空格
• 第 3(2) 題｜說明 quicksort 的時間複雜度，並各舉一個最佳情況與最壞情況的例子
• 第 4(1) 題（4%）｜8 個節點（0 到 7）的 undirected graph 以 cost matrix 給出，不存在的邊為 ∞，找出所有 bi-connected components
• 第 4(2) 題（6%）｜同一個 cost matrix，給 C++ 函式 shortestpath（以 found[] 標記、每輪呼叫 choose_min），以 v = 1 呼叫，寫出 for 迴圈每一輪之後 distance[] 的內容
• 第 5(1) 題（3%）｜依序把 10、3、8、12、5、7、20、4 用題目給的 insert_min_heap 插入空的 min heap，畫出結果
• 第 5(2) 題（2%）｜依序插入 n 個數到 min heap 的時間複雜度
• 第 5(3) 題（3%）｜說明從 (1) 的 heap 刪除最小值後如何調整
• 第 6 題（15%）｜selection problem：在 n 個相異數中找比恰好 i − 1 個元素大的元素，給 RANDOMIZED-SELECT 的 pseudo-code：(a) 5% 第 4 行的 k 代表什麼 (b) 5% 最壞執行時間 (c) 5% 用它在 {3, 2, 9, 0, 7} 中選最小元素，描述一個造成最壞情況的 partition 序列
• 第 7 題（15%）｜rod cutting，給 BOTTOM-UP-CUT-ROD 的 pseudo-code：(a) 5% 第 8 行存的是什麼 (b) 5% 長度 5 的 rod，價格表為長度 1 到 5 依序 2、5、6、9、10，演算法的輸出 (c) 5% 修改演算法，讓它也回傳最佳切法
• 第 8 題（20%）｜給 Floyd-Warshall 的 pseudo-code：
• 第 8(a) 題（5%）｜說明 d_ij^(k) 的意義
• 第 8(b) 題（4%）｜給 4×4 的權重矩陣 W，填出 D⁽¹⁾ 中標成「?」的兩個元素
• 第 8(c) 題（6%）｜如何用演算法的輸出偵測負權重的 cycle
• 第 8(d) 題（5%）｜把上標全部拿掉、只用一個 D 原地更新，使空間降到 Θ(n²)，修改後的演算法是否仍正確，簡述理由

作答時要注意的地方

1. 第 1 題每小題的答案可能不只一個資料結構。
2. 第 2(1) 題的六個函式變數名稱沒有語意，function2 的參數是 p，函式內卻用 *top 判斷，卷面就是這樣印的。
3. 第 2 題 12 分、第 3 題 10 分，卷面沒有標小題配分。
4. 第 3(2) 題最佳與最壞情況都要舉例。
5. 第 4(2) 題要寫出每一輪迴圈之後的 distance[]，不是只寫最後結果。
6. 第 8(b) 題只要填 D⁽¹⁾ 中的兩個「?」。
7. 第 8(d) 題要說明理由。
8. 第 8(a) 題與 111 年第 7(a) 題相同，兩年的 (b) 都是填 D⁽¹⁾。

準備方向

• 符號表的資料結構選擇：106 第 1 題。
• C 程式的填空、追蹤與手寫：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 題、114 第一題也有。
• Linked list、stack 與 queue 的實作：106 第 2(1) 題；108 第 1.9、2(a) 題、109 第四題、110 第 7 題、112 第 2 題、113 第 11 題、114 第一題也有。
• Stack 與 queue 的應用（運算式轉換、迷宮、BFS）：106 第 2(2) 題；108 第 1.2、1.4 題、109 第三題、112 第 3 題也有。
• 排序演算法：106 第 3 題；107 第 1(a)(b) 題、108 第 1.11 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、111 第 2 題、112 第 5、7 題、114 第二(二)題、115 第 5 題也有。
• 複雜度分析：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 第 1、5、6 題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：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 第四題、115 第 8 題也有。
• shortest path：106 第 4(2)、8 題；107 第 4、6 題、110 第 10、11 題、111 第 7 題、113 第 12 題、114 第七(二)題、115 第 9 題也有。
• Heap 與 priority queue：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 第 4 題也有。
• Selection 問題（randomized select）：106 第 6 題。
• DP（rod cutting／knapsack／LCS／matrix chain）：106 第 7 題；108 第 4 題、111 第 6 題、112 第 8 題、115 第 7 題也有。
• 負權重對演算法的影響：106 第 8(c) 題；107 第 6(c) 題、109 第七(d)題、110 第 11(a) 題、111 第 7(c) 題、114 第七題也有。