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

題型與配分

系所「資訊科學與工程學系 甲組」，科目：資訊概論，全卷 5 頁、14 大題、100 分，不得使用計算機。

這是 108–111 四年裡唯一一份全申論的資訊概論，沒有任何選擇題、沒有倒扣，但也沒有任何部分猜對的機會——每題都要從頭寫。

軟體佔 75 分，是 108–111 四年裡比重最高的一年。 前四題硬體只佔 25 分，後面十題全部是軟體。

逐題考點

計算機組織（1–4，25%）

• 第 1 題（6%）｜MIPS 記憶體定址：給一段 lw／sw／add／sub 的程式與記憶體初始內容，逐條指令列出執行結果
• 第 2 題（6%）｜指令格式：(a) R／I／J 三種格式下，immediate、displacement、PC-relative branch 各自的最大範圍；(b) 判斷三條指令分別是哪一型
• 第 3 題（6%）｜記憶體階層的平均存取時間：cache 10 ns、未命中要 30 ns 載入後重來、不在主記憶體要 12 ms 從磁碟抓。(a) 3%：cache 命中率 0.9、主記憶體命中率 0.6，求平均存取時間；(b) 3%：說明作業系統在等磁碟的 12 ms 時如何提高 CPU 使用率（行程切換）
• 第 4 題（7%）｜(a) addu 與 add 在 0x40000000 + 0x7FFFFFFF 下的差別（溢位例外）；(b) 寫出 1-bit full adder 的 CarryOut 與 Sum 邏輯函數

軟體（5–14，75%）

• 第 5 題（6%）｜Java 運算式的輸出：(0+15)/2 的整數除法、2.0e-6 * 100000000.1 的浮點表示、true && false || true && true 的優先順序（&& 先於 ||）
• 第 6 題（4%）｜遞迴的求值順序：Test(n) 先算 s = Test(n-3) + n + Test(n-2) + n 再檢查 n <= 0。終止條件寫在遞迴呼叫之後，所以求 Test(3) 要小心展開順序
• 第 7 題（10%）｜證明 sink-based（由下往上）建堆最多用 2N 次比較、N 次交換。這是證明題，要用「高度 h 的節點最多有 ⌈N/2^h+1⌉ 個」配上 Σ h/2^h = 2 的級數
• 第 8 題（10%）｜最短路徑表格找錯：給 Providence／Westerly／New London／Norwich 四城市的「最短距離表」，其中一格是錯的，要找出來改正，並補一張表說明各組最短路徑怎麼走。實際上是在考三角不等式與 Floyd-Warshall 的概念
• 第 9 題（5%）｜哪些排序是穩定的（多選）：Quick／Selection／Shell／Merge／Heap
• 第 10 題（10%）｜行程排程：P1(0.0, 8)、P2(0.4, 4)、P3(1.0, 1)，非搶佔式。(a) 3%：FCFS 平均周轉時間；(b) 3%：SJF 平均周轉時間；(c) 4%：先讓 CPU 閒置 1 單位再用 SJF（題目稱之為 future-knowledge scheduling），算平均周轉時間 —— 這一問是要你發現故意閒置反而更好
• 第 11 題（10%）｜名詞解釋各 2 分：Semaphore、Race Condition、Thrashing、Demand Paging、Fragmentation
• 第 12 題（10%）｜3-way quicksort 排序 [19, 3, 5, 1, 2, 4, 6, 7, 11, 10, 8, 0]，要寫出過程
• 第 13 題（5%）｜死結的四個必要條件（互斥、持有並等待、不可搶奪、循環等待）
• 第 14 題（5%）｜給一組相異整數，計算有多少三元組滿足「兩數之和等於第三數」，要求寫出 O(n²) 的做法（先排序，再對每個 c 用雙指標掃）

這份考卷的難點

1. 第 7 題是真正的證明題，不是計算。要能寫出「高度 h 的節點數 ≤ ⌈N/2^h+1⌉」再對 h 求和，這在資料結構課本通常只是一行結論，平常沒推過就寫不出來。
2. 第 6 題的遞迴把終止條件放在遞迴呼叫後面，是刻意設計的陷阱 —— 照著程式碼字面展開會無限遞迴，要看出 n <= 0 那一行其實永遠不會擋住前面的呼叫。
3. 第 8 題要自己發現表格哪裡錯。四個城市的表有 12 個非對角格，要逐組驗證三角不等式（Westerly–Norwich = 101 明顯大於繞經 New London 的路徑），先找矛盾再修正。
4. 第 10(c) 的「故意閒置」反直覺。很多人算完 (a)(b) 就跳過 (c)，但這一問 4 分，而且是整份卷子唯一考「排程演算法的資訊不完全」的地方。
5. 全申論、14 大題、5 頁、不能用計算器——時間分配是最大壓力，第 11 題的五個名詞解釋 10 分最好拿，要先寫。

準備建議

• 這一年沒有倒扣但也沒有選項可選，練習時要習慣從零寫出完整過程
• 建堆的複雜度證明（sink-based O(N)）是跨校高頻考點，要能寫出級數推導而不只是背結論
• 行程排程的周轉時間／等待時間在 109、110、111 三年連續出現，FCFS／SJF／SRTF 的甘特圖要畫得快
• 穩定排序的清單（Insertion、Bubble、Merge、Counting 穩定；Quick、Selection、Heap、Shell 不穩定）要背死，109 年直接考，111 年也考排序性質
• 死結四條件與 OS 名詞解釋幾乎是送分題，但要能用中興慣用的英文術語作答