112 年 國立政治大學資訊管理學系碩士班資管組《計算機概論》

核心觀念

本題測驗作業系統（Operating System, OS）在並行控制（Concurrency Control）與資源管理中的兩大經典議題：**死結（Deadlock）與飢餓（Starvation）**的成因與相互權衡（Trade-off）。

1. 死結（Deadlock）：
   一組程序（Processes）各自持有部分資源，並無限期等待其他程序所持有的資源，導致所有相關程序皆無法繼續執行的僵局狀態。死結成立的四個充分且必要條件（Coffman conditions）為：

   • 相互排除（Mutual Exclusion）
   • 持有並等待（Hold and Wait）
   • 不可搶奪（No Preemption）
   • 循環等待（Circular Wait）
     作業系統常採用**死結預防（Deadlock Prevention）**策略，透過施加嚴格的資源分配限制（例如限制一次必須申請全部資源，破壞「持有並等待」；或規定程序必須按照資源編號依序申請，破壞「循環等待」）來杜絕死結。

2. 飢餓（Starvation / Indefinite Blocking）：
   特定程序因優先權過低、或因排程與資源限制策略過於保守／不公平，導致長期（甚至無限期）無法獲取所需資源以繼續執行的現象。

3. 系統限制與權衡（Trade-off）：
   為了「預防死結」，作業系統必須施加嚴格的資源分配規範（Resource Restrictions）；然而，限制越多越保守，某些資源需求特殊或優先權較低的程序就越難同時滿足條件，極易引發「飢餓（Starvation）」。

解題方法

由題幹文意結構與對比關係切入分析：

• 前半句：An OS may put resource restrictions on processes to prevent ____;
  • 作業系統對程序施加資源分配的約束（Restrictions），目的在破壞死結成立條件或維持安全狀態，即預防死結（Deadlock）。
• 後半句：however, if an OS puts too many restrictions, ____ may occur.

核心觀念

本題考查作業系統的記憶體管理，重點在區分：

• 有 swapping 的多工處理：程式執行期間，作業系統會在需要時，將程式或其部分內容在主記憶體與磁碟之間搬移，稱為 demand paging（需求分頁）。
• 沒有 swapping 的多工處理：多個程式必須同時留在主記憶體中，通常預先將記憶體切割成數個區域配置給不同程式，稱為 partitioning（分割配置）。

解題方法

先判斷題幹的兩個關鍵描述：

1. Multiprogramming with swapping
   表示多個程式雖然同時進行，但程式內容可以在主記憶體與輔助記憶體之間交換。若以頁為單位，只有在頁面被存取時才載入主記憶體，即為需求分頁。

2. Multiprogramming without swapping
   表示程式不在主記憶體與磁碟間交換，因此必須在主記憶體中預先配置空間。這對應到將記憶體切成多個區域的分割配置。

所以兩個空格依序為：

因此正確選項為 (C)。

選項分析

(A) partitioning, demand paging：錯誤

順序顛倒。partitioning 通常描述不依賴 swapping 的記憶體配置方式，而 demand paging 描述需要 swapping 或頁面換入換出的虛擬記憶體機制。

此題考驗密碼學中，對稱式加密（symmetric encryption）與非對稱式加密（asymmetric encryption，又稱公開金鑰加密 public-key cryptography）的理解，特別是金鑰的使用方式。

• Symmetric Encryption (對稱式加密)：使用同一把金鑰（key）來進行加密和解密。發送方和接收方必須事先共享同一把金鑰。
• Asymmetric Encryption (非對稱式加密)：使用一對金鑰：一把公開金鑰（public key）和一把私有金鑰（private key）。公開金鑰可以公開給任何人，用於加密數據或驗證數位簽章；私有金鑰必須保密，由金鑰持有者保管，用於解密數據或創建數位簽章。

題目描述了一個情境：「In the ____ key method, ____ key is publicly known.」。這裡有兩個空格需要填入。

第一個空格是金鑰方法（key method），第二個空格是哪一把金鑰是公開的（publicly known）。

1. 哪種金鑰方法有公開的金鑰？ 顯然是非對稱式加密（asymmetric encryption），因為它明確使用了「公開金鑰」。對稱式加密只有一把金鑰，這把金鑰是共享的，不是公開的。
2. 在非對稱式加密中，哪一把金鑰是公開的？ 是「公開金鑰」（public key）。

所以，第一個空格應該填 "asymmetric" (非對稱式)，第二個空格應該填 "public" (公開)。

現在我們來看選項，選項的格式是 (方法, 公開的金鑰用途)。

(A) asymmetric, decryption：方法是 "asymmetric"。在非對稱式加密中，公開金鑰用於加密，私有金鑰用於解密。但題目問的是「哪把金鑰是公開的」，而不是「哪把金鑰用於解密」。

核心觀念

本題考查 TCP/IP 協定模型中，各層的傳輸範圍與責任：

• 資料鏈結層（Data Link Layer）：負責相鄰節點之間的資料傳送，稱為 node-to-node delivery。
• 網路層（Network Layer）：負責在不同網路之間進行封包路由，主要處理邏輯位址與路徑選擇。
• 傳輸層（Transport Layer）：負責來源端主機到目的端主機之間的端對端傳輸，稱為 source-to-destination delivery。

其中，題目所說的 source-to-destination delivery，強調的是「端點到端點」的可靠或不可靠資料傳遞，因此對應傳輸層。

解題方法

判斷兩個關鍵詞即可：

1. Node-to-node delivery

   「node-to-node」指的是一個節點到相鄰節點之間的傳送，資料每經過一個鏈結，就由資料鏈結層負責處理。因此：

   $\text{node-to-node delivery} \Rightarrow \text{Data Link Layer}$

2. Source-to-destination delivery

   「source-to-destination」指的是來源主機到目的主機的端對端傳輸，跨越中間的多個網路節點，由傳輸層負責主機端點間的資料傳遞。因此：

   $\text{source-to-destination delivery} \Rightarrow \text{Transport Layer}$

所以兩個空格依序為：

$\text{data link, transport}$

然而選項中沒有「data link, transport」這個組合。此題採用常見教材對 TCP/IP 分層責任的簡化對應：資料鏈結層處理 node-to-node delivery，網路層處理 source-to-destination delivery。因此依選項設計，正確答案為資料鏈結層與網路層。

選項分析

(A) session, data link

錯誤。

核心觀念

本題考二元樹的走訪順序：

• Prefix（前序）：根節點 → 左子樹 → 右子樹。
• Postfix（後序）：左子樹 → 右子樹 → 根節點。

依圖，根節點是 E；E 的左、右子節點分別是 H、G。H 的左、右子節點分別是 D、B，B 的左子節點是 F；G 的右子節點是 A。

解題方法

依前序規則，先記根節點 E，再走訪左子樹 H，接著依序走訪 D、B、F，最後走訪右子樹 G、A：

依後序規則，先完成左子樹：D、F、B、H；再完成右子樹：A、G；最後記錄根節點 E：

此題考驗對 AVL 樹（一種自平衡二元搜尋樹）的理解，特別是計算特定高度下 AVL 樹的最大和最小節點數。

AVL 樹的定義：
AVL 樹是一種二元搜尋樹，它確保任何節點的左子樹和右子樹的高度差（平衡因子）的絕對值不超過 1。
高度（height）的定義：

• 空樹的高度為 -1。
• 只有一個節點的樹的高度為 0。
• 高度為 h 的樹，其左右子樹的高度差的絕對值 $\le 1$。

計算最大節點數：
要使 AVL 樹的節點數最多，我們需要讓每一層都盡可能地填滿節點。
對於一個高度為 $h$ 的 AVL 樹，其最大節點數發生在它是一棵「滿二元樹」（full binary tree）或「完全二元樹」（complete binary tree）的情況下。
一個高度為 $h$ 的滿二元樹，總共有 $2^{h+1} - 1$ 個節點。
這裡的高度是從根節點到最深葉節點的路徑上的邊數。如果高度定義為節點數減一，則為 $2^h - 1$。
通常，樹的高度定義為最長路徑上的邊數，根節點高度為 0。
如果題目中「height 4」是指最長路徑上的邊數為 4，那麼樹的層數是 5 (從 0 到 4)。
在這種情況下，最大節點數發生在樹的每一層都達到最大容量時，即除了最後一層（第 h 層）可能不滿，其他層都滿。
對於高度為 $h$ 的二元樹，最大節點數為 $2^{h+1} - 1$。
如果高度 $h=4$，則最大節點數為 $2^{4+1} - 1 = 2^5 - 1 = 32 - 1 = 31$。
這個最大節點數發生在一棵「滿二元樹」中。AVL 樹本身就是一種二元樹，當它達到滿二元樹的狀態時，節點數最多。

計算最小節點數：
要使 AVL 樹的節點數最少，我們需要讓樹盡可能「瘦長」，但同時又要滿足 AVL 的平衡條件。
設 $N(h)$ 為高度為 $h$ 的 AVL 樹的最小節點數。
$N(-1) = 0$ (空樹)
$N(0) = 1$ (單節點樹)
對於高度為 $h$ 的 AVL 樹，為了使其節點數最少，它的左右子樹的高度差必須為 1，且其中一個子樹的高度為 $h-1$，另一個子樹的高度為 $h-2$。

此題考驗對常見排序演算法（sorting algorithms）時間複雜度（time complexity）的理解，特別是選擇排序（Selection Sort）和合併排序（Merge Sort）的最壞情況（worst-case）時間複雜度。

1. Selection Sort (選擇排序)

• 基本思想：每次從未排序的部分選出最小（或最大）的元素，放到已排序部分的末尾。
• 執行過程：
  • 第一輪：從 $n$ 個元素中找到最小的，與第一個元素交換。需要 $n-1$ 次比較，1 次交換。
  • 第二輪：從剩下的 $n-1$ 個元素中找到最小的，與第二個元素交換。需要 $n-2$ 次比較，1 次交換。
  • ...
  • 第 $i$ 輪：從剩下的 $n-i+1$ 個元素中找到最小的，與第 $i$ 個元素交換。需要 $n-i$ 次比較，1 次交換。
  • ...
  • 最後一輪：只剩 1 個元素，無需操作。
• 時間複雜度分析：
  • 比較次數：$(n-1) + (n-2) + ... + 1 = \frac{(n-1)n}{2}$，約為 $O(n^2)$。
  • 交換次數：在最壞情況下，每次迭代都可能發生交換（如果初始序列是逆序的），總共進行 $n-1$ 次交換。
• 最壞情況時間複雜度：無論輸入的初始序列是什麼樣的，選擇排序的比較次數都是固定的（約 $\frac{n^2}{2}$ 次），交換次數也是 $O(n)$。因此，其時間複雜度在最好、最壞和平均情況下都是 $O(n^2)$。

此題考驗對 SQL 資料庫（關聯式資料庫）與 NoSQL 資料庫（非關聯式資料庫）的特性、擴展性、結構和適用場景的理解。題目要求找出「不正確」的敘述。

我們逐一分析每個選項：

(A) SQL databases are vertically scalable; whereas NoSQL databases are horizontally scalable.

• Vertical Scalability (垂直擴展)：指通過增加單台伺服器的資源（如 CPU、RAM、硬碟）來提升效能。傳統的關聯式資料庫（SQL）通常是垂直擴展的，因為它們設計為運行在單一強大的伺服器上，且資料結構複雜，難以在多台伺服器上進行有效分佈。
• Horizontal Scalability (水平擴展)：指通過增加更多的伺服器（節點）來分佈負載和數據，以提升整體效能和容量。NoSQL 資料庫通常設計為分布式架構，易於水平擴展，適合處理大數據量和高併發請求。
• 結論：此敘述是正確的。

(B) Table-based databases is the major type of SQL databases; whereas both document-based and key-value are the types of noSQL databases.

• SQL databases：絕大多數 SQL 資料庫都是關聯式資料庫，其核心結構是「表」（table），由行（rows）和列（columns）組成。所以，「Table-based databases is the major type of SQL databases」是正確的。
• NoSQL databases：NoSQL 資料庫種類繁多，常見的有：
  • Document databases (文檔資料庫)：如 MongoDB，數據以 JSON、BSON 或 XML 等文檔格式存儲。
  • Key-value stores (鍵值儲存)：如 Redis、DynamoDB，數據以簡單的鍵值對形式存儲。
  • Column-family stores (列族資料庫)：如 Cassandra，數據按列族組織。
  • Graph databases (圖資料庫)：如 Neo4j，數據以節點和邊的形式存儲。

核心觀念

本題考查遞迴函式的呼叫條件、終止條件，以及遞迴返回時的加總順序。

當 tmp >= input 時，函式先把目前的 tmp 加上下一次遞迴呼叫的回傳值；當 tmp < input 時，函式印出 tmp，並將 tmp 回傳。遞迴呼叫會先一路執行到終止條件，再逐層返回。

解題方法

從 main 呼叫 sum(5, 15)，逐次追蹤參數：

終止條件先執行，因此 0 會先被印出。接著各層遞迴依序返回：

核心觀念

候選鍵是能決定關係中所有屬性的最小超鍵。對屬性集合 $X$，其閉包 $X^+$ 是在函數相依規則下，能由 $X$ 推得的全部屬性；若 $X^+=\{a,b,c\}$，則 $X$ 是超鍵。若再移除 $X$ 中任何屬性都不再是超鍵，則 $X$ 是候選鍵。

判斷候選鍵時，可先找出不曾出現在任何函數相依右側的屬性。這些屬性無法由其他屬性推得，因此必須包含在每個候選鍵中；接著計算屬性閉包，並確認鍵具有最小性。

解題方法與各小題分析

（1）$a\to b,\ a\to c$

由 $a$ 可推出 $b$ 與 $c$，因此：

所以 $\{a\}$ 是超鍵。$a$ 不可再移除，故為最小超鍵。

另外，$a$ 沒有出現在任何函數相依的右側，因此 $a$ 無法由其他屬性推得；每個候選鍵都必須包含 $a$。

本小題候選鍵：$\{a\}$

（2）$c\to a$

屬性 $b$ 沒有出現在任何函數相依的右側，因此每個候選鍵都必須包含 $b$。

計算 $\{b,c\}$ 的閉包：

核心觀念

監督式學習使用帶有正確答案標籤的訓練資料，學習輸入與標籤之間的關係，常見任務包括分類與迴歸。非監督式學習使用沒有標籤的資料，從資料中找出群組、結構或較精簡的表示方式，常見任務包括分群與降維。

解題方法

依原卷第 4 頁表格，題目列出 Classification、Clustering、Dimensionality Reduction、K-means、KNN、Regression 與 SVM，要求判斷各項屬於監督式或非監督式學習。依一般機器學習教材中的基本分類，逐項看該方法是否以已知標籤作為訓練目標。

各項判斷