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

題型與配分

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

逐題考點

• 第 1 題（5%）｜用 Big-Oh 寫出三段 pseudo-code 的最壞執行時間，答案必須從題目列出的 11 個選項中挑，同一個選項可以用在不只一小題。(a) 外層迴圈跑 n×100 次、內層有一個從 n 數到 1 的迴圈與一個跑 i 次的迴圈 (b) 每次呼叫做 n 次累加，再以 n−2 遞迴呼叫，n < 10 時停止 (c) j 每次除以 2，直到 j ≤ 2
• 第 2 題（5%）｜四個操作在最壞情況下的最緊上界：(a) 以 binary search tree 實作的 priority queue 找最小值 (b) 以 linked list 實作的 stack 做 pop (c) 以 binary min heap 實作的 priority queue 做 delete min (d) 在 binary min heap 中找最大值
• 第 3 題（15%，5 小題各 3%）｜選擇題
• 第 3-1 題｜adjacency matrix 表示的圖中，traversal 終止於某頂點的所有邊所需的期望操作數
• 第 3-2 題｜adjacency list 表示的圖，同樣的問題
• 第 3-3 題｜array 5 3 8 9 1 7 0 2 6 4，以 5 為 pivot 做 quicksort 的 partition，問結束後的 array
• 第 3-4 題｜insertion、selection、heap、bubble、quicksort 哪一個在最壞情況下不需要 O(n²) 步
• 第 3-5 題｜BST 不允許重複值，刪除有兩個子節點的節點時，若從左子樹挑替代節點，要找的是哪一個節點
• 第 4 題（5%）｜9 個 bucket、每個 bucket 一個 slot 的 hash table，hash function 為 k % 9，linear probing，依序插入 5、29、20、0、27、18，求結果
• 第 5 題（5%）｜array 10 8 6 2 1 4 5 組成 heap（priority queue），做兩次 deleteMax 後的 array
• 第 6 題（5%）｜8 個節點（0 到 7）、13 條有向邊的 directed graph，列出所有 strongly connected component
• 第 7 題（5%）｜給一段使用 middle、trail 兩個 pointer 並以 Head traversal 的 while 迴圈，畫出執行後的 linked list，並標出 Head、middle、trail 各指向哪些節點
• 第 8 題（5%）｜threaded binary tree 的節點宣告含 leftThread、rightThread、leftChild、rightChild、data，補完 insucc() 三個空格，以找出 inorder successor 且不使用 stack
• 第 9 題（20%，4 小題各 5%）｜輸入 array 有 n 個相異數字，(a) merge sort 的 divide 步驟在做什麼與其時間複雜度 (b) merge sort 的 conquer 步驟在做什麼與其時間複雜度 (c) quick sort 的 divide 步驟 (d) quick sort 的 conquer 步驟，兩者都要寫時間複雜度
• 第 10 題（10%）｜給 Dijkstra 的 pseudo-code：(a) 5% 第 5 行取出 u.d 最小的頂點 u，這個 u.d 代表什麼 (b) 5% Prim 演算法同樣是每次加一個頂點的 greedy 演算法，Dijkstra 與 Prim 的確切差異是什麼
• 第 11 題（20%）｜Johnson 演算法，圖中有 negative-weight edge，新增頂點 q 並以權重 0 的邊連到其他每個頂點：
• 第 11(a)i 題（3%）｜Bellman-Ford 求每個頂點的 h(v)，為什麼用 Bellman-Ford 而不是 Dijkstra
• 第 11(a)ii 題（2%）｜這張圖（含新增的頂點 q）需要幾趟處理
• 第 11(b) 題（5%）｜已知 h(a)=0、h(b)=0、h(c)=−4、h(d)=−3，新邊權為 w(u,v) + h(u) − h(v)，畫出 reweighting 後的圖
• 第 11(c) 題（5%）｜reweighting 後的圖以 a 為源點，求 δ(a,b)、δ(a,c)、δ(a,d)
• 第 11(d) 題（5%）｜Smith 教授提議令 c = min{w(u,v)}，把每條邊的權重改成 w(u,v) − c，這個 reweighting 方法有什麼問題

作答時要注意的地方

1. 第 1 題要從題目給的 11 個選項中選，同一個選項可以重複使用。
2. 第 3 題 5 小題各 3 分。
3. 第 9 題 4 小題都要寫時間複雜度。
4. 第 11 題的 h(a)、h(b)、h(c)、h(d) 由題目給定，(c) 要寫出 δ 的值，(d) 問的是 Smith 教授的 reweighting 方法。
5. 第 3-1、3-3、4、5 題與 109 年第一(3)、一(4)、一(5)、一(6)題相同。

準備方向

• 複雜度分析：110 第 1、2 題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、108 第 4(a)(b) 題、109 第一(8)、四(c)、六(a)題、111 第 4、5 題、112 第 1(b)、8(a) 題、113 第 8(a)(b) 題、114 第三、五題、115 第 1、5、6 題也有。
• Heap 與 priority queue：110 第 2(c)(d)、5 題；106 第 5 題、107 第 3(b) 題、108 第 1.6、1.7 題、109 第一(1)、一(6)、一(9)題、111 第 4 題、112 第 5 題、114 第三(三)題、115 第 4 題也有。
• binary tree 與 BST：110 第 2(a)、3-5、8 題；107 第 3(a) 題、108 第 1.1、1.8、1.10、1.12 題、109 第一(2)、一(7)、二題、111 第 1 題、112 第 3 題、113 第 8、10 題、114 第三(二)(四)題、115 第 5 題也有。
• 圖的表示法：110 第 3-1、3-2 題；108 第 1.3 題、109 第一(3)題、112 第 6(a) 題、113 第 9 題、114 第三(一)、四題也有。
• 排序演算法：110 第 3-3、3-4、9 題；106 第 3 題、107 第 1(a)(b) 題、108 第 1.11 題、109 第一(4)、六題、111 第 2 題、112 第 5、7 題、114 第二(二)題、115 第 5 題也有。
• Hash（linear probing）：110 第 4 題；109 第一(5)題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：110 第 6 題；106 第 4(1) 題、107 第 2(b) 題、108 第 1.3、1.5、3、5(a) 題、111 第 3 題、112 第 6 題、113 第 9、13(a) 題、114 第四題、115 第 8 題也有。
• C 程式的填空、追蹤與手寫：110 第 7、8 題；106 第 2(1)、3(1)、4(2)、5(1) 題、107 第 1(c)(d) 題、108 第 2 題、112 第 1、2、6 題、113 第 1–4、6、7、8(c)、11、12 題、114 第一題也有。
• Linked list、stack 與 queue 的實作：110 第 7 題；106 第 2(1) 題、108 第 1.9、2(a) 題、109 第四題、112 第 2 題、113 第 11 題、114 第一題也有。
• minimum spanning tree（Prim／Kruskal）：110 第 10 題；109 第七題、112 第 4 題、114 第七(一)題也有。
• shortest path：110 第 10、11 題；106 第 4(2)、8 題、107 第 4、6 題、111 第 7 題、113 第 12 題、114 第七(二)題、115 第 9 題也有。
• 邊權加減常數的影響：110 第 11(d) 題；114 第七題也有。
• 負權重對演算法的影響：110 第 11(a) 題；106 第 8(c) 題、107 第 6(c) 題、109 第七(d)題、111 第 7(c) 題、114 第七題也有。