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

核心觀念
在作業系統中，多工 (multiprogramming) 指的是在同一時間內允許多個程序佔有 CPU，藉由切換讓 CPU 繼續執行。依照是否允許 交換 (swapping) 產生的差異，可將多工分為兩種：

1. 不使用交換 (no‑swapping)：所有已載入記憶體的程序必須同時佔有實體記憶體，系統只能在已佔用的記憶體區塊內切換。這種方式常稱為 partitioning（分割），因為記憶體被劃分成固定的分區，每個分區一個程序。
2. 使用交換 (with‑swapping)：當記憶體不足時，系統可將暫時不執行的程式或程式部份「換出」至磁碟，再在需要時換回。此機制支援 paging（分頁） 或 segmenting（分段），但在教材與考試中，多數把「有交換」的多工對應到 paging（因分頁是最典型的交換實作）。

解題方法
題目給出四個選項，屬於概念填空題。解題步驟：

1. 先回想「不使用交換」的多工如何運作：只在實體記憶體內分配固定區塊 → partitioning。
2. 再回想「使用交換」的多工常見實作方式：把程式切成固定大小的頁面，換出/換入 → paging。
3. 把上述兩個正確概念對照選項，找出同時符合的組合。

選項分析

| 選項 | 前半部 (without swapping) | 後半部 (with swapping) | 判斷 |

本題考查作業系統中資源管理與進程調度的問題。

• 資源限制（resource restrictions）的目的：作業系統會對進程（process）施加資源限制，以防止某些不良情況發生。最常見的不良情況是「死鎖」（deadlock），即兩個或多個進程互相等待對方釋放資源，導致所有進程都無法繼續執行。另一個不良情況是「耗盡」（starvation），即一個進程因為持續無法獲得所需資源而永遠無法執行。
• 過多的資源限制的後果：然而，如果作業系統設定了過於嚴格或過多的資源限制，可能會導致「耗盡」（starvation）的情況。例如，如果一個進程被設置了極低的優先級或嚴格的 CPU 時間片限制，它可能永遠無法獲得足夠的資源來完成任務。
• Thrashing（抖動）：Thrashing 是指系統因為不斷進行換頁（paging）操作，導致 CPU 大部分時間都在處理換頁，而實際的有用工作卻很少，系統效能急劇下降的現象。這通常發生在記憶體不足時，過多的進程競爭有限的記憶體空間。
• Segmentation（分段）：Segmentation 是一種記憶體管理技術，將程式的記憶體空間劃分為邏輯段。它與資源限制的直接後果關聯不大。

選項分析：

• (a) thrash, segmentation：Thrashing 通常與記憶體管理有關，而 segmentation 是記憶體管理的一種方式。這兩者都不是資源限制的主要目的或過度限制的直接後果。
• (b) segmentation, thrash：同上，關聯性不大。

本題考查資料庫或集合論中的運算符（operator）的性質。運算符根據其操作數（operand）的數量分為單元運算符（unary operator）和二元運算符（binary operator）。

• 單元運算符（Unary Operator）：只需要一個操作數的運算符。
• 二元運算符（Binary Operator）：需要兩個操作數的運算符。

在關係型資料庫（Relational Database）或集合論的上下文中，我們常見的運算符包括：

• Intersection（交集）：需要兩個關係（或集合）作為操作數，返回它們共有的元組（或元素）。例如，$R \cap S$。這是二元運算符。
• Difference（差集）：需要兩個關係（或集合）作為操作數，返回第一個關係中有而第二個關係中沒有的元組（或元素）。例如，$R - S$。這是二元運算符。
• Union（聯集）：需要兩個關係（或集合）作為操作數，返回它們所有元組（或元素）的集合。例如，$R \cup S$。這是二元運算符。
• Cartesian Product（笛卡兒積）：需要兩個關係（或集合）作為操作數，返回所有可能的組合。例如，$R \times S$。這是二元運算符。
• Selection/Filter（選擇/篩選）：作用於一個關係（或集合），根據條件選出滿足條件的元組（或元素）。例如，$\sigma_{condition}(R)$。這是一個單元運算符（作用於一個關係）。
• Projection（投影）：作用於一個關係（或集合），選出指定的屬性（列）。例如，$\pi_{A,B}(R)$。這是一個單元運算符（作用於一個關係）。
• Join（連接）：通常需要兩個關係作為操作數，並根據某個條件將它們連接起來。

本題考查備份（backup）的種類。備份是為了防止資料丟失，將資料複製到另一位置。常見的備份策略包括完整備份、差異備份和增量備份。

• Full Backup（完整備份）：備份所有選定的資料。
• Incremental Backup（增量備份）：只備份自上次「任何類型」備份（完整備份或增量備份）以來發生變更的檔案。每次增量備份只包含自上次備份以來變更的檔案。
• Differential Backup（差異備份）：只備份自上次「完整備份」以來發生變更的檔案。每次差異備份都包含自上次完整備份以來所有變更的檔案，因此差異備份檔案的大小會逐漸增大。

題目描述：「____ backup copies the files that have changed since the last full backup.」

本題考查 NoSQL 資料庫的特性。NoSQL（Not Only SQL）資料庫是一類與傳統關係型資料庫（SQL databases）不同的資料庫。

• a. Does not require a fixed schema（不需要固定綱要）：這是 NoSQL 資料庫的一個關鍵特徵。許多 NoSQL 資料庫（如文件型、鍵值型）採用彈性綱要（flexible schema）或無綱要（schema-less）設計，允許資料結構的變化，這使得開發更加靈活，尤其是在處理結構不斷變化的半結構化或非結構化資料時。
• b. Horizontally scalable（水平可擴展）：NoSQL 資料庫通常被設計為能夠通過增加更多的伺服器節點來擴展其容量和處理能力，這就是水平擴展（horizontal scaling）。這與傳統關係型資料庫通常依賴於更強大的單一伺服器（垂直擴展）不同，水平擴展更適合處理大規模數據和高流量。

本題考查記憶體（memory）的類型及其特性。題目問的是哪種記憶體「能夠提供相關資訊」。這句話暗示了記憶體不是通過位址來存取，而是通過內容來存取。

• Associative Memory（關聯式記憶體）：關聯式記憶體（也稱為內容定址記憶體，Content-Addressable Memory, CAM）是一種特殊的記憶體，它允許使用者通過記憶體內容來搜尋資料，而不是通過記憶體的物理位址。當給定一個搜尋鍵（search key）時，關聯式記憶體會同時檢查記憶體中的所有儲存單元，並返回與搜尋鍵匹配的內容所在的位址或內容本身。

本題考查 CPU 處理資料時，不同層級記憶體的存取速度和可用性。CPU 在執行指令時，需要快速存取資料和指令。為了提高效率，CPU 內部或非常靠近 CPU 的地方設有多層次的記憶體。

• a. Random-access memory (RAM)：隨機存取記憶體，是主記憶體，速度比快閃記憶體快，但比快取和暫存器慢。
• b. Read-only memory (ROM)：唯讀記憶體，用於儲存啟動程式等固定資料，速度通常較慢，且無法寫入。
• c. Cache：快取記憶體，位於 CPU 和主記憶體之間，速度比主記憶體快得多，用於暫存 CPU 最近或最常使用的資料和指令，以減少 CPU 存取主記憶體的次數。

本題考查物件導向程式設計（Object-Oriented Programming, OOP）的核心概念。OOP 的主要特徵是：

• Encapsulation（封裝）：將資料（屬性）和操作（方法）綁定在一起，形成一個物件。同時，它也提供了資訊隱藏（information hiding）機制，將物件的內部實現細節對外部隱藏，只暴露必要的介面。
• Inheritance（繼承）：允許一個類別（子類別）繼承另一個類別（父類別）的屬性和方法，從而實現程式碼的重用，並建立類別之間的層次關係。
• Polymorphism（多型）：允許不同類別的物件對同一訊息做出不同的響應。

本題考查統一塑模語言（Unified Modeling Language, UML）的組成部分。UML 是一種標準化的通用塑模語言，用於視覺化、規範、建構和記錄軟體密集型系統的成品，特別是軟體系統。

UML 圖表主要分為兩大類：

1. 結構圖（Structure Diagrams）：描述系統的靜態結構，包括類別、物件、介面、元件、節點等。常見的結構圖包括：
   • 類別圖（Class Diagram）
   • 物件圖（Object Diagram）
   • 元件圖（Component Diagram）
   • 部署圖（Deployment Diagram）
   • 封裝圖（Package Diagram）
   • 組合結構圖（Composite Structure Diagram）
   • 輪廓圖（Profile Diagram）
2. 行為圖（Behavior Diagrams）：描述系統的動態行為，包括系統的內部流程、物件之間的互動、狀態變化等。常見的行為圖包括：
   • 用例圖（Use Case Diagram）
   • 活動圖（Activity Diagram）
   • 狀態機圖（State Machine Diagram）

本題考查資料分析技術，特別是針對客戶交易資料來找出產品之間的關聯性。

• a. Accumulated analysis（累積分析）：這通常指將資料逐步累積並進行分析，但它並非專門用於找出產品關聯性的技術。
• b. Acustomed analysis（習慣分析）：這不是一個標準的資料分析術語。可能是拼寫錯誤，例如 "Accustomed analysis"（習慣性分析），但仍然不是專門用於找出產品關聯性的術語。

本題考查演算法的時間複雜度分析，特別是關於優先佇列（priority queue）的操作。

題目要求計算將 N 個隨機數插入一個空的優先佇列（priority queue）的時間複雜度，並用 big-O 符號表示。

優先佇列通常可以使用以下資料結構來實現：

1. 二元堆積（Binary Heap）：這是最常見且效率較高的實現方式。
   • 插入操作（insert）的時間複雜度是 $O(\log k)$，其中 $k$ 是堆積中的元素數量。
   • 刪除最小/最大元素（extract-min/max）的時間複雜度也是 $O(\log k)$。
2. 排序陣列（Sorted Array）：
   • 插入操作需要找到插入位置並移動元素，時間複雜度是 $O(k)$。
   • 刪除最小/最大元素是 $O(1)$。
3. 未排序陣列（Unsorted Array）：
   • 插入操作是 $O(1)$。
   • 刪除最小/最大元素需要遍歷整個陣列查找，時間複雜度是 $O(k)$。

在大多數情況下，優先佇列的實現是指使用二元堆積。
我們需要將 N 個元素逐一插入一個空的優先佇列。

• 第一次插入：優先佇列是空的，插入第一個元素。時間複雜度是 $O(\log 1) = O(1)$。
• 第二次插入：優先佇列中有 1 個元素，插入第二個元素。時間複雜度是 $O(\log 2)$。
• 第三次插入：優先佇列中有 2 個元素，插入第三個元素。時間複雜度是 $O(\log 3)$。
• ...
• 第 N 次插入：優先佇列中有 $N-1$ 個元素，插入第 N 個元素。時間複雜度是 $O(\log N)$。

本題考查二元樹（Binary Tree）的遍歷（traversal）及其應用。題目給出了一棵二元樹的中序遍歷（inorder traversal）序列，要求繪製出這棵樹。

中序遍歷（Inorder Traversal） 的順序是：左子樹（Left Subtree） → 根節點（Root） → 右子樹（Right Subtree）。
對於一個二元樹，中序遍歷的結果是所有節點按遞增順序排列（如果樹是二元搜尋樹 BST）。

題目給出的節點序列是：KSGJVOLTN。
由於這只是中序遍歷結果，我們無法僅憑藉中序遍歷就唯一確定一棵二元樹。例如，單獨的中序遍歷序列 ABC 可以對應多種不同的二元樹結構。

要唯一確定一棵二元樹，我們通常需要結合兩種遍歷序列，例如：

• 中序遍歷 + 前序遍歷（Preorder Traversal）
• 中序遍歷 + 後序遍歷（Postorder Traversal）

前序遍歷（Preorder Traversal） 的順序是：根節點 → 左子樹 → 右子樹。
後序遍歷（Postorder Traversal） 的順序是：左子樹 → 右子樹 → 根節點。

但是，題目並沒有提供第二個遍歷序列。 這意味著，這道題目可能存在一些隱含的假設，或者說，它可能要求畫出 一種 滿足該中序遍歷的二元樹，而不是 唯一 的二元樹。

最常見的隱含假設是，這是一個二元搜尋樹（Binary Search Tree, BST）。
如果我們假設這是一棵二元搜尋樹，那麼節點在中序遍歷中是按字母順序排列的。
序列 KSGJVOLTN 依字母順序排列是：G J K L N O S T V。
然而，給定的序列 KSGJVOLTN 並不是按字母順序排列的。這排除了它是標準 BST 的可能性（除非字母順序被重新定義）。

另一種可能性是，題目可能要求畫出一個「最簡單」或「最平衡」的樹結構，或者只是隨意畫一種可能的樹。

假定題目要求畫出 一種 滿足中序遍歷的二元樹：
我們可以選擇一個節點作為根，然後將其左側的節點構成左子樹，右側的節點構成右子樹。

例如，我們可以選擇序列中的第一個字母 'K' 作為根。
那麼左子樹的節點是空，右子樹的節點是 'SGJVOLTN'。
如果我們選擇 'S' 作為根，那麼左子樹是 'KGJVOLT'，右子樹是 'N'。
如果我們選擇 'G' 作為根，那麼左子樹是 'KSJ'，右子樹是 'VOLTN'。

最常見的「隨意畫法」是選擇序列的中心元素作為根。
序列 KSGJVOLTN 有 9 個節點。中心節點是第 5 個，即 'V'。
如果 'V' 是根：
左子樹節點序列：KSGJVOLT
右子樹節點序列：N

現在，我們處理左子樹 KSGJVOLT。它有 8 個節點。
我們可以選擇中間的兩個節點之一作為根，例如 'J' 或 'O'。
如果選擇 'J' 作為根：
左子樹節點序列：KSG
右子樹節點序列：VOLT

現在，我們處理左子樹 KSG。它有 3 個節點。選擇 'S' 作為根。
左子樹節點序列：K
右子樹節點序列：G

現在，我們處理右子樹 VOLT。它有 4 個節點。選擇 'O' 作為根。
左子樹節點序列：VOL
右子樹節點序列：T

現在，我們處理左子樹 VOL。它有 3 個節點。選擇 'O' 作為根。
左子樹節點序列：V
右子樹節點序列：L

現在，我們處理右子樹 N。它只有一個節點，所以 'N' 是葉節點。
現在，我們處理左子樹 K。它只有一個節點，所以 'K' 是葉節點。
現在，我們處理右子樹 G。它只有一個節點，所以 'G' 是葉節點。
現在，我們處理左子樹 V。它只有一個節點，所以 'V' 是葉節點。
現在，我們處理右子樹 L。它只有一個節點，所以 'L' 是葉節點。
現在，我們處理右子樹 T。它只有一個節點，所以 'T' 是葉節點。

根據這種「選擇中心節點作為根」的策略，我們得到以下樹結構：

根節點：V
左子樹根：J
左子樹根：S
左子樹根：K (葉節點)
右子樹根：G (葉節點)
右子樹根：O
左子樹根：V (葉節點)
右子樹節點：L (葉節點)
右子樹根：T
左子樹根：N (葉節點)
右子樹根：(空)

這個樹的結構是：
V
/
J T
/ \ /
S O N
/ \ /
K G V L

本題考查二元樹（Binary Tree）的遍歷（traversal）及其應用。題目給出了一棵二元樹的後序遍歷（postorder traversal）序列，要求繪製出這棵樹。

後序遍歷（Postorder Traversal） 的順序是：左子樹（Left Subtree） → 右子樹（Right Subtree） → 根節點（Root）。

題目給出的節點序列是：DLZSHFCOE。
與中序遍歷類似，僅憑藉後序遍歷序列也無法唯一確定一棵二元樹。要唯一確定一棵二元樹，通常需要結合另外一種遍歷序列（如前序或中序）。

但是，題目並沒有提供第二個遍歷序列。 這意味著，這道題目可能要求畫出 一種 滿足該後序遍歷的二元樹，而不是 唯一 的二元樹。

最常見的「隨意畫法」是選擇序列的最後一個元素作為根。 這是因為後序遍歷的最後一個元素必定是整棵樹的根節點。

序列 DLZSHFCOE 有 9 個節點。最後一個節點是 'E'。
所以，'E' 是這棵樹的根節點。

根節點：E

後序遍歷的順序是 L → R → Root。
所以，根節點 'E' 左邊的節點序列 DLZSHFC 構成左子樹，右邊的節點序列（空）構成右子樹。

現在我們需要處理左子樹的節點序列 DLZSHFC。
我們再次選擇該序列的最後一個元素作為左子樹的根。
序列 DLZSHFC 的最後一個節點是 'C'。
所以，'C' 是左子樹的根節點。

根節點：E
左子樹根：C
左子樹的節點序列：DLZSHF
右子樹的節點序列：(空)

現在我們需要處理左子樹 DLZSHF。
選擇該序列的最後一個元素作為根。
序列 DLZSHF 的最後一個節點是 'F'。
所以，'F' 是左子樹的根節點。

根節點：E
左子樹根：C
左子樹根：F
左子樹的節點序列：DLZSH
右子樹的節點序列：(空)

現在我們處理左子樹 DLZSH。
選擇該序列的最後一個元素作為根。
序列 DLZSH 的最後一個節點是 'H'。
所以，'H' 是根節點。

根節點：E
左子樹根：C
左子樹根：F
左子樹根：H
左子樹的節點序列：DLZS
右子樹的節點序列：(空)

現在我們處理左子樹 DLZS。
選擇該序列的最後一個元素作為根。
序列 DLZS 的最後一個節點是 'S'。
所以，'S' 是根節點。

根節點：E
左子樹根：C
左子樹根：F
左子樹根：H
左子樹根：S
左子樹的節點序列：DLZ
右子樹的節點序列：(空)

現在我們處理左子樹 DLZ。
選擇該序列的最後一個元素作為根。
序列 DLZ 的最後一個節點是 'Z'。
所以，'Z' 是根節點。

根節點：E
左子樹根：C
左子樹根：F
左子樹根：H
左子樹根：S
左子樹根：Z
左子樹的節點序列：DL
右子樹的節點序列：(空)

現在我們處理左子樹 DL。
選擇該序列的最後一個元素作為根。
序列 DL 的最後一個節點是 'L'。
所以，'L' 是根節點。

根節點：E
左子樹根：C
左子樹根：F
左子樹根：H
左子樹根：S
左子樹根：Z
左子樹根：L
左子樹的節點序列：D
右子樹的節點序列：(空)

現在我們處理左子樹 D。
序列 D 只有一個節點，所以 'D' 是葉節點。

核心觀念

本題考查作業系統的五狀態程序模型。程序會隨著建立、獲得處理器、等待事件或完成執行，在不同狀態間轉換。圖中要填入的四個狀態與四種轉換如下。

解題方法

先依箭頭方向辨認狀態：新程序進入就緒狀態；就緒程序被派發後開始執行；執行中的程序可被搶先、等待事件或結束；等待事件完成後則回到就緒狀態。

• (a) 結束（Terminated／Exit）：程序已完成執行，或因錯誤等原因被作業系統終止。
• (b) 就緒（Ready）：程序已具備執行條件，正等待取得 CPU。
• (c) 執行（Running）：程序目前正在 CPU 上執行。
• (d) 等待／阻塞（Waiting／Blocked）：程序正在等待 I/O 完成或其他事件，暫時無法繼續執行。

本題要求比較卷積神經網路（Convolutional Neural Network, CNN）和循環神經網路（Recurrent Neural Network, RNN）在四個不同方面的差異。

a) Definitions (定義)

• CNN (卷積神經網路)：

  • 定義：一種專門設計用於處理具有網格狀拓撲結構資料（如圖像）的神經網路。它通過使用卷積層（convolutional layers）來自動學習空間層級特徵。卷積層通過應用可學習的濾波器（kernels）來提取局部特徵。
  • 核心思想：利用權重共享（weight sharing）和局部感受野（local receptive fields）來減少參數數量，並有效捕捉空間局部性。

• RNN (循環神經網路)：

  • 定義：一種設計用於處理序列資料的神經網路。它具有內部「記憶體」（hidden state），可以捕捉序列中先前時間步長的資訊，並將其傳遞到後續時間步長。
  • 核心思想：通過循環連接（recurrent connections）在時間上共享權重，使得網路能夠處理變長序列，並學習序列中的時間依賴性。

b) Type of data (資料類型)

• CNN：

  • 主要處理：網格狀數據，最典型的是二維圖像（圖片）。也可以應用於一維數據（如音訊訊號、文本序列，但通常需要特定結構）或三維數據（如影片、醫學影像）。
  • 特點：擅長捕捉空間上的局部模式和空間層級結構。

• RNN：

  • 主要處理：序列數據，即具有時間順序或語義順序的數據。例如：
    • 時間序列數據（股票價格、天氣預報）
    • 自然語言文本（句子、段落）
    • 語音訊號
    • 影片幀序列
  • 特點：擅長捕捉序列中的時間依賴性和上下文關係。

c) Length of input (輸入長度)

• CNN：

  • 輸入長度：通常處理固定長度的輸入。對於圖像，通常是固定尺寸的圖像。如果輸入尺寸不同，通常需要通過填充（padding）或縮放（resizing）使其統一。雖然可以通過池化層（pooling layers）來適應不同大小的輸入，但網路本身通常設計為處理特定尺寸的輸入。
  • 處理方式：通過卷積和池化層逐步提取特徵，最終通常會連接全連接層進行分類或預測。

• RNN：

  • 輸入長度：能夠處理**變長度（variable-length）**的輸入序列。這是 RNN 的一個重要優勢。其循環結構允許它在每個時間步長處理一個輸入，並根據需要迭代任意次數。
  • 處理方式：按時間順序逐個處理序列中的元素，並維護一個隱藏狀態（hidden state）來傳遞資訊。

d) Applications (應用)