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

題型與配分

全卷 5 頁、14 大題、100 分，不得使用計算機。除第 9 題是多重選擇外，其餘都是申論題，卷面沒有計分規則的標示。

第 1–4 題的內容見硬體 109 年頁。

軟體考點（5–14，75%）

• 第 5 題（6%）｜Java 三個運算式的輸出：整數除法 (0 + 15) / 2、floating point 運算 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 heap construction 最多使用 2N 次比較與 N 次交換
• 第 8 題（10%）｜Providence、Westerly、New London、Norwich 四個城市的最短距離表中有一格是錯的，要改正，並補一張表說明如何走出各組 shortest path
• 第 9 題（5%）｜哪些排序演算法是 stable：Quick、Selection、Shell、Merge、Heap
• 第 10 題（10%）｜P1（到達 0.0、burst 8）、P2（到達 0.4、burst 4）、P3（到達 1.0、burst 1），nonpreemptive scheduling：
• 10(a)（3%）｜FCFS 的平均 turnaround time
• 10(b)（3%）｜SJF 的平均 turnaround time
• 10(c)（4%）｜CPU 先閒置 1 個單位再用 SJF（題目稱為 future-knowledge scheduling）的平均 turnaround time
• 第 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%）｜導致 deadlock 的必要條件
• 第 14 題（5%）｜給一組相異整數，計算有多少個三元組滿足其中兩數之和等於第三數，要求寫出時間複雜度 O(n²) 的程式

作答時要注意的地方

1. 除第 9 題外都是申論，沒有選項可以猜，每題都要寫出過程。
2. 第 7 題要求證明，不是計算。
3. 第 6 題把 n <= 0 的檢查寫在遞迴呼叫之後。
4. 第 8 題要找出表中錯誤的一格，並補上 shortest path 的走法。
5. 第 10(c) 明訂先閒置 1 個單位再 schedule。
6. 第 11 題五個名詞解釋共 10 分。

準備方向

• 建 heap 與 heap 的操作：109 第 7 題，110 第 7-C 題、111 第 1-III 題、114 Part 2 第 5 題也有 heap。
• shortest path：109 第 8 題，110 第 9-D 題、111 第 3-V 題、113 第 14 題、114 第 4 題也有。
• 排序的 stability 與性質：109 第 9 題，110 第 8-B 題、111 第 1-I、1-II 題、113 第 12 題、114 第 1、2、7 題也有。
• process scheduling 的 turnaround time 與 waiting time：109 第 10 題，110 第 1-D 題、111 第 6-III 題也有。
• deadlock 與 OS 名詞：109 第 11、13 題，110 第 2-B 題也有 deadlock。
• Quick sort 的變體：109 第 12 題，111 第 1-II 題也有 quick sort。
• 遞迴函式求值：109 第 6 題，110 第 7-D 題、111 第 3-VII 題、112 B 第 3、4 題、113 第 10 題也有。
• 程式設計題與時間複雜度：109 第 14 題，114 Part 2 第 6 題要求設計 dynamic array。