111 中興資工所軟體考點分析

題型與配分

系所「資訊工程學系 甲組」（系名這一年從「資訊科學與工程學系」改為「資訊工程學系」），科目：資訊概論，全卷 9 頁、100 分，不得使用計算機。

111 年是「資訊概論」的最後一年。112 年起甲組拆成「離散數學與線性代數」「資料結構與演算法」「計算機組織與作業系統」三科，軟體才有了自己的獨立考卷。

PART I 有 28 分是簡答題（要寫答案、不是選擇），和 110 年的全選擇不同。同樣沒有倒扣，但簡答題沒寫就是 0 分。

PART I 第 1 題組：單選（12%，每題 2 分）

• I｜selection sort 最壞情況的交換次數（每輪最多一次交換 → O(n)，與比較次數 O(n²) 不同，這是最常被搞混的一題）
• II｜quick sort 固定取中間元素當 pivot 時，最壞情況的最緊上界（仍是 O(n²)，注意題目在問 O 還是 Θ）
• III｜四個陣列裡哪一個是 binary max-heap
• IV｜假設 P ≠ NP，下列何者為真（NP-complete ∩ P = ∅）
• V｜Q₁ 可多項式時間歸約到 3-SAT、3-SAT 可歸約到 Q₂，問 Q₁、Q₂ 各屬於什麼（Q₁ ∈ NP、Q₂ 是 NP-hard —— 歸約的方向決定難度的方向）
• VI｜每條邊的權重都加上同一個值後：P「MST 不變」、Q「任兩點的最短路徑不變」，哪些為真（只有 P —— MST 的邊數固定所以不變，但最短路徑的邊數不同，加權後可能換路徑）

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

• I｜關於橋（bridge）的正確敘述（橋不可能是簡單環的一部分）
• II｜用陣列實作 queue，ENQUEUE 與 DEQUEUE 的複雜度（環狀陣列下兩個都是 O(1)）
• III｜給一張圖，問哪一個不可能是 Kruskal 加邊的順序（要逐一驗證邊權的非遞減順序與是否成環）
• IV｜河內塔的遞迴式（T(n) = 2T(n−1) + 1）
• V｜一段把 A[i][j] 與 A[j][i] 對調的雙層迴圈（i、j 都從 1 跑到 n），問輸出是什麼（每一組都被交換兩次，所以還原成原矩陣 A）

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

• I｜20 個頂點的二分圖最多幾條邊（10 × 10 = 100）
• II｜距離向量路由（Distance Vector Routing）：五個節點 N1–N5 的距離向量已收斂，(1) N2–N3 的成本降為 2 後，下一輪 N3 的距離向量是什麼；(2) 接著 N1–N2 斷線（N2 對 N1 的成本立刻變 ∞），再一輪後 N3 到 N1 的成本是多少 —— 這一問在考 count-to-infinity
• III｜雜湊表開放定址＋線性探測：keys 12, 18, 13, 2, 3, 23, 5, 15 插入長度 10 的表，h(k) = k mod 10，畫出最後的表
• IV｜無向圖 G 有 n 個節點，V_i 與 V_j 相連 iff 0 < |i − j| ≤ 2，邊權為 i + j，求 MST 的總成本（要先看出貪婪會挑哪些邊，再推出通式）
• V｜給一張有向圖，S 到 T 有多條等長最短路徑，問 Dijkstra 實際會回報哪一條（規則是「只有嚴格更短才更新」，所以先被鬆弛的那條會留下）
• VI｜BST 的前序是 30, 20, 10, 15, 25, 23, 39, 35, 42，求後序（先由前序＋BST 性質重建樹，再走一次）
• VII｜int f(int &x, int c)，第一個參數傳參考、第二個傳值，求 f(5, 5) 的回傳值。傳參考讓 x 在遞迴回溯時已經被改過，return f(x, c) * x 的兩個 x 不是同一個值

PART II：計算機組織與作業系統（50%）

六個題組共 21 個單選，分佈是 4(8%)、5(6%)、6(8%)、7(8%)、8(12%)、9(8%)：

• cache 與記憶體｜block size 的取捨、兩層 cache 的平均存取時間（L1 1 ns／L2 10 ns／主記憶體 500 ns）、4-way set associative 的 tag 位元數
• pipeline｜一段程式的 RAW／WAR／WAW 相依數量、operand forwarding 下的 cycle 數、四階段管線跑 1000 次迴圈的 cycle 數、pipeline 效率反推級數
• 虛擬記憶體｜32-bit 位址 1 KB 分頁為何不能用單層頁表、三層頁表各層需要幾個位元、最少要配幾個 frame
• 行程與同步｜SRT 排程下 P2 的總等待時間、兩個行程的臨界區方法是否滿足 mutual exclusion 與 progress、user-level thread 與 kernel thread 的比較
• I/O 與中斷｜DMA 模式與中斷機制的組合、同步／非同步 I/O 的 ISR、memory-mapped 與 isolated I/O
• 其他｜re-order buffer 的性質、microprogram 的定義

這份考卷的難點

1. 第 3-II 的距離向量路由是中興唯一一次考計算機網路。距離向量本身不難，但 count-to-infinity 那一問要理解「N3 是從 N2 學到通往 N1 的路」，斷線後 N3 會從別的鄰居學回一條假路徑，不是單純變成 ∞。
2. 第 3-VII 的傳參考遞迴是全卷最容易算錯的一題。return f(x, c) * x; 裡，左邊的遞迴呼叫會改掉 x 的值，等右邊的 x 求值時已經是新的值——求值順序決定答案。
3. 第 1-I 的「交換次數」不是「比較次數」。selection sort 每一輪只做一次交換，所以交換是 O(n)、比較才是 O(n²)。題目故意問交換。
4. 第 1-VI 的「每條邊加同一個值」：MST 不變（因為任何生成樹都恰好有 V−1 條邊，整體加同一個常數），但最短路徑會變（路徑長度不同，加的總量不同）。這兩個結論要一起記，只記一半就會答錯。
5. 第 2-V 的雙重交換要看出迴圈跑了完整的 n×n 而不是上三角，所以每一對都被換兩次，結果等於沒換。

準備建議

• 111 是「資訊概論」格式的收尾，與 110 並排看能看出中興軟體的固定範圍：排序性質、heap、BST、圖論（MST／最短路徑／bridge）、雜湊、遞迴、NP
• 簡答題佔 28 分，練習時要習慣寫出雜湊表、寫出後序序列、寫出距離向量，不能只會選答案
• 歸約方向決定難度方向（A 歸約到 B 表示 B 至少和 A 一樣難）是 NP 題組的核心，111、112、113、114 四年都考
• 雜湊表線性探測在 110（第 6-B 題）與 111（第 3-III 題）連兩年出現，一年問插入順序、一年問最後結果，兩種問法都要練
• 河內塔遞迴式同年在「基礎數學 A」的計算題也考了一次（111 數學計算第 2 題），兩科同時出現