111 中興資工所考古題詳解｜軟體考點分析

題型與配分

全卷 9 頁、100 分，不得使用計算機。112 年起甲組拆成離散數學與線性代數、資料結構與演算法、計算機組織與作業系統三科，111 年是資訊概論的最後一年。PART I 與 PART II 的順序與 110 年對調，PART I 是軟體。卷面沒有標示倒扣，簡答題要寫出答案。

PART II 的內容見硬體 111 年頁。

PART I 第 1 題組：單選（12%）

• 1-I｜用 selection sort 排序 n 個元素，最壞情況需要的交換次數
• 1-II｜quick sort 固定取 array 中間元素當 pivot，最壞情況效能最緊的上界，選項有 O(n²)、O(n log n)、Θ(n log n)、Θ(n²)
• 1-III｜四個 array 哪一個是 binary max-heap
• 1-IV｜假設 P ≠ NP，哪個敘述為真
• 1-V｜Q₁ 可多項式時間 reduction 到 3-SAT，3-SAT 可多項式時間 reduction 到 Q₂，哪個敘述與此一致
• 1-VI｜帶權 connected undirected graph 的邊權皆相異且為正，每條邊的權重都加上同一個值後，P「minimum spanning tree 不變」、Q「任兩點間的最短路徑不變」哪些為真

PART I 第 2 題組：單選（10%）

• 2-I｜關於橋（bridge）的敘述，橋是移除後會使 connected graph 變成 disconnected 的邊
• 2-II｜以 array 實作 queue，ENQUEUE 與 DEQUEUE 的時間複雜度
• 2-III｜給一張圖，哪個序列不是 Kruskal 演算法加入 MST 的邊序列
• 2-IV｜n 個圓盤 Tower of Hanoi 最佳執行時間的 recurrence
• 2-V｜把方陣 A 的 A[i][j] 與 A[j][i] 以暫存變數對調的雙層迴圈（i、j 都從 1 到 n），最後輸出的內容

PART I 第 3 題組：簡答（28%，每小題 4%）

• 3-I｜20 個頂點的 bipartite graph 最多有幾條邊
• 3-II｜五個節點 N1–N5 使用 Distance Vector Routing，距離向量已收斂：(1) N2–N3 的成本降為 2 之後，下一輪更新完成後 N3 的新距離向量；(2) 接著 N1–N2 斷線，N2 立刻把該成本改為 ∞，再經過下一輪更新後 N3 到 N1 的成本
• 3-III｜keys 12、18、13、2、3、23、5、15 依序插入長度 10 的空 hash table，h(k) = k mod 10、open addressing、linear probing，求最後的 hash table
• 3-IV｜undirected graph G 有 n 個節點 V₁…V_n，V_i 與 V_j 相連若且唯若 0 < |i − j| ≤ 2，邊 (V_i, V_j) 的權重為 i + j，求 MST 的總成本
• 3-V｜一張 directed graph 中 S 到 T 有多條 shortest path，Dijkstra 演算法會回報哪一條，條件是只有找到嚴格更短的路徑才更新
• 3-VI｜BST 的 preorder traversal 為 30、20、10、15、25、23、39、35、42，求 postorder traversal
• 3-VII｜int f(int &x, int c)，第一個參數傳參考、第二個參數傳值，求 f(5, 5) 的回傳值

作答時要注意的地方

1. 卷面沒有標示倒扣，簡答題要直接寫出答案。
2. 1-II 要看清楚選項問的是 O 還是 Θ。
3. 1-VI 的 P、Q 兩個敘述要分別判斷。
4. 2-V 兩層迴圈的 i、j 都從 1 跑到 n。
5. 3-II 分兩段，先降低成本、再斷線，每段各更新一輪。
6. 3-V 的更新規則是只有找到嚴格更短的路徑才更新。
7. 3-VII 的第一個參數傳參考，第二個參數傳值。

準備方向

• 排序與 quick sort 的最壞情況：111 第 1-I、1-II 題，109 第 9 題、110 第 8-B 題、113 第 12 題、114 第 1、2、7 題也有。
• heap 的判斷：111 第 1-III 題，110 第 7-C 題、114 Part 2 第 5 題也有。
• NP 理論與 reduction：111 第 1-IV、1-V 題，110 第 9-E 題、112 D-V 題、113 B-2 第 2 題、114 第 5 題也有。
• 邊權加常數的影響：111 第 1-VI 題，110 第 10-D 題也有。
• Kruskal 與 MST：111 第 2-III、3-IV 題，110 第 7-A、9-C 題、113 B-1 第 6 題、114 Part 2 第 4 題也有。
• Tower of Hanoi recurrence：111 第 2-IV 題，108 填空 ⑥ 與 111 數學計算題第 2 題也有。
• hash table linear probing：111 第 3-III 題，110 第 6-B 題也有。
• Dijkstra 與 shortest path：111 第 3-V 題，109 第 8 題、110 第 9-D 題、113 第 14 題、114 第 4 題也有。
• BST traversal：111 第 3-VI 題，113 第 6–8 題、113 B-2 第 1 題、114 Part 2 第 3 題也有。
• 距離向量路由與網路：111 第 3-II 題，108 第 8 題考 TCP/IP 分層。
• 傳參考的遞迴：111 第 3-VII 題，109 第 6 題、110 第 7-D 題、112 B 第 3、4 題、113 第 10 題也有遞迴求值。