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

題型與配分

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

逐題考點

• 第一(1)題｜7 個整數做 heapsort，建完 heap 之後 array 可能的樣子（五個選項）
• 第一(2)題｜給一棵 BST（5、3、9、4、7、12、6、8、20），哪一個插入序列不會產生這棵樹
• 第一(3)題｜以 adjacency matrix 表示的圖，traversal 終止於某頂點的所有邊所需的期望操作數（n 個頂點、m 條邊終止於該點）
• 第一(4)題｜array 5 3 8 9 1 7 0 2 6 4，以 5 為 pivot 做 quicksort 的 partition，結束後的 array
• 第一(5)題｜大小 9 的 hash table，hash function 為 k % 9，linear probing，依序插入 5、29、20、0、27、18，求結果
• 第一(6)題｜array 10 8 6 2 1 4 5 組成 heap，做兩次 deleteMax 後的 array
• 第一(7)題｜給一棵 binary tree，preorder traversal 的結果
• 第一(8)題｜八個函數 8n² + 1、n! + 2ⁿ、100、2ⁿ + n + 10、2n³ + n² + 1、10n、3n log n、7n + log n，依 big-O 由小到大排列
• 第一(9)題｜合併兩個 leftist heap 的結果
• 第二題（6%）｜空的 AVL tree：(a) 3% 依序插入 61、23、92、33、54、77、20、11 (b) 3% 再插入 31、47
• 第三題（5%）｜用 stack 把 (A-2)*((B+C)-D*E)*A 轉成 postfix，要逐步說明
• 第四題（8%）｜circular linked list：(a) 3% pointer a 指向第一個節點時，用 pseudo code 刪除第一個節點 (b) 3% pointer a 指向最後一個節點時，同樣刪除第一個節點 (c) 2% 有 n 個節點時，(a) 與 (b) 的時間複雜度
• 第五題（4%）｜8 個頂點、10 條邊的 AOE 網路，邊以 (Vi, Vj, W) 三元組給出，起點 V0、終點 V7，找出 critical activities
• 第六題（15%，3 小題各 5%）｜merge sort：(a) 合併兩個長度 n/2 的已排序 array，最壞情況要幾次元素比較 (b) 和暴力排序（例如 bubble sort）相比，merge sort 省略了哪些計算 (c) merge sort 是否 stable，簡述理由
• 第七題（20%，4 小題各 5%）｜Prim：(a) 用途 (b) 對題目給的圖執行 Prim (c) 說明 Prim 的 greedy 選擇為什麼會得到最佳解 (d) 輸入圖有負權重時會怎樣
• 第八題（15%，3 小題各 5%）｜給網路 G 與流 f，每條邊標 (流量 / 容量)：(a) 寫出 f 導出的 residual network (b) f 是否為 max flow，是的話標出容量等於流量的 cut 來證明，不是的話說明如何得到更大的流 (c) 多個源點與匯點的 max flow 問題如何轉成單一源點與匯點

作答時要注意的地方

1. 第一題 9 小題各 3 分，卷面沒寫倒扣，選擇題要寫在作答區。
2. 第一(2)題問的是哪一個序列「不會」產生這棵樹。
3. 第一(8)題要排的是 big-O 由小到大的順序。
4. 第三題要逐步說明 stack 的變化，不是只寫結果。
5. 第四題 (a)(b) pointer a 指的位置不同，要分開寫。
6. 第七(b)題題目沒有指定起點。
7. 第八(b)題要先判斷是不是最大值，兩種情況要做的事不同。
8. 第一(3)、一(4)、一(5)、一(6)題與 110 年第 3-1、3-3、4、5 題相同。

準備方向

• Heap 與 priority queue：109 第一(1)、一(6)、一(9)題；106 第 5 題、107 第 3(b) 題、108 第 1.6、1.7 題、110 第 2(c)(d)、5 題、111 第 4 題、112 第 5 題、114 第三(三)題、115 第 4 題也有。
• binary tree 與 BST：109 第一(2)、一(7)、二題；107 第 3(a) 題、108 第 1.1、1.8、1.10、1.12 題、110 第 2(a)、3-5、8 題、111 第 1 題、112 第 3 題、113 第 8、10 題、114 第三(二)(四)題、115 第 5 題也有。
• 圖的表示法：109 第一(3)題；108 第 1.3 題、110 第 3-1、3-2 題、112 第 6(a) 題、113 第 9 題、114 第三(一)、四題也有。
• 排序演算法：109 第一(4)、六題；106 第 3 題、107 第 1(a)(b) 題、108 第 1.11 題、110 第 3-3、3-4、9 題、111 第 2 題、112 第 5、7 題、114 第二(二)題、115 第 5 題也有。
• Hash（linear probing）：109 第一(5)題；110 第 4 題也有。
• 複雜度分析：109 第一(8)、四(c)、六(a)題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、108 第 4(a)(b) 題、110 第 1、2 題、111 第 4、5 題、112 第 1(b)、8(a) 題、113 第 8(a)(b) 題、114 第三、五題、115 第 1、5、6 題也有。
• Stack 與 queue 的應用（運算式轉換、迷宮、BFS）：109 第三題；106 第 2(2) 題、108 第 1.2、1.4 題、112 第 3 題也有。
• Linked list、stack 與 queue 的實作：109 第四題；106 第 2(1) 題、108 第 1.9、2(a) 題、110 第 7 題、112 第 2 題、113 第 11 題、114 第一題也有。
• AOE 網路與 critical activity：109 第五題；107 第 5 題也有。
• minimum spanning tree（Prim／Kruskal）：109 第七題；110 第 10 題、112 第 4 題、114 第七(一)題也有。
• 負權重對演算法的影響：109 第七(d)題；106 第 8(c) 題、107 第 6(c) 題、110 第 11(a) 題、111 第 7(c) 題、114 第七題也有。
• max flow 與 bipartite matching：109 第八題；113 第 13 題也有。