108 中山資工所考古題詳解｜軟體考點分析

題型與配分

全卷 2 頁、5 大題、25 小題、100 分，考試時間 100 分鐘，不可使用計算機，全部是問答申論題。每大題 5 個小題，每小題 4 分。

資料結構佔 40 分（第 1、2 題），作業系統佔 60 分（第 3、4、5 題）。

逐題考點

第 1 題｜基礎資料結構（20%）

• (1) 4%｜把 prefix 運算式 + + (18) × (17) (16) × + × (15) (14) (13) (12) 轉成 infix 並計算結果
• (2) 4%｜simple uniform hashing 的定義；m 個槽、n 筆資料、用 chaining 處理 collision 時，失敗搜尋的期望時間
• (3) 4%｜除了每個節點非紅即黑，還要怎麼處理，BST 才會成為 red-black tree
• (4) 4%｜n 個物件排序時，heap sort、insertion sort、bubble sort、quick sort 的平均時間
• (5) 4%｜給 7 個頂點（A、B、C、D、E、F、S）undirected graph 的 adjacency matrix，寫出 BFS 與 DFS traversal 的節點順序，有多個選擇時依字母順序

第 2 題｜進階資料結構（20%）

• (1) 4%｜directed graph G = (V, E) 的 strongly connected component 是什麼
• (2) 4%｜用 B-tree 管理磁碟 block 為什麼能降低磁碟存取成本
• (3) 4%｜B⁺-tree 與 B*-tree 的差別
• (4) 4%｜binomial heap 的兩個性質
• (5) 4%｜給一個 Fibonacci heap（根為 10、20、40，其餘節點的 key 為 26、19、25、23、41、43、28、50、32、54、37），把 key 50 降為 18、再把 key 37 降為 7，畫出結果

第 3 題｜process 與 synchronization（20%）

• (1) 4%｜race condition 是什麼、如何解決
• (2) 4%｜deadlock prevention 與 deadlock avoidance 的差別
• (3) 4%｜什麼時候需要用 condition variable
• (4) 4%｜對目標 thread 的 asynchronous cancellation 與 deferred cancellation 的差別
• (5) 4%｜造成 process 終止的四個常見條件

第 4 題｜記憶體與 I/O（20%）

• (1) 4%｜paging 的兩個好處
• (2) 4%｜working set 與 thrashing
• (3) 4%｜external fragmentation 與 internal fragmentation 的差別
• (4) 4%｜synchronous I/O 與 asynchronous I/O 的差別
• (5) 4%｜I/O 裝置的四個常見 register

第 5 題｜保護與安全（20%）

• (1) 4%｜principle of least privilege 是什麼、Solaris 10 如何實作
• (2) 4%｜電腦病毒與電腦 worm 的差別
• (3) 4%｜處理 UNIX 中 setuid-on 問題的兩個常見方法
• (4) 4%｜masquerading 與 replay attack
• (5) 4%｜authentication 的目的、non-repudiation 是什麼

作答時要注意的地方

1. 全卷 25 個小題，每小題 4 分，卷面沒有標示倒扣。
2. 第 5 題 20 分整題是保護與安全，109 到 111 年的卷子沒有這個主題。
3. 第 2(5) 題要依題目給的圖做兩次 decrease-key，畫出最後的結果。
4. 卷面沒有印「題目不清楚可自行假設」的說明，106 年與 109 到 114 年有，107 年也沒有。

準備方向

• Hash 與 chaining（108 第 1(2) 題），110 第 8 題、115 第 7 題也有 hash table。
• balanced tree 與 BST（108 第 1(3) 題的 red-black tree），107 第 5(4) 題與第 1(3) 題相同，110 第 9 題、114 第 3 題有 AVL tree，111 第 3 題有 BST 刪除，112 第 3 題有 optimal BST。
• 排序的複雜度（108 第 1(4) 題），106 第 9 題、107 第 5(5) 題、109 第 9 題、112 第 2 題、113 第 3 題、114 第 2 題、115 第 9 題也有。
• BFS 與 DFS traversal（108 第 1(5) 題）。
• 運算式轉換（108 第 1(1) 題），106 第 10 題、107 第 5(2) 題也有。
• 進階 heap（108 第 2(4)(5) 題的 binomial heap 與 Fibonacci heap），107 第 6(3) 題考 binomial tree，111 第 4 題也有 heap。
• strongly connected component 與 B-tree 家族（108 第 2(1)(2)(3) 題），107 第 6(1)(2) 題也考 B-tree 樹高與 B*-tree。
• process 與 synchronization、deadlock（108 第 3 題），107 第 1 題也問 race condition 與 deadlock prevention、avoidance 的差別，112 第 5、8 題，114 第 6 題，115 第 3 題也有。
• 記憶體與 I/O 的名詞解釋（108 第 4 題），第 4(1) 題與 107 第 2(2) 題相同，107 第 2、3 題、112 第 6 題、113 第 8 題、114 第 7 題也有同類題目。
• 資訊安全（108 第 5 題），107 第 4 題 15 分也整題是保護與安全，第 4(1) 題與 108 第 5(1) 題相同；112 第 9(c) 題、113 第 8 題 (h)(i)(j)、115 第 1 題 (i)(j) 以名詞或填空的形式出現。