111 年 國立成功大學會計學研究所乙組《計算機概論》

核心觀念
Unicode 為全球統一的字符編碼系統，採用 21 位元（21 bits）的編碼空間。

• 最大可表示的碼點範圍為 $U+0000$ ~ $U+10FFFF$，即十六進位的 $0x10FFFF$。
• 十六進位 $0x10FFFF$ 轉為十進位為 $1,114,112$，因此 Unicode 理論上可容納 $1,114,112$ 個不同符號（code point）。
• 實務上會保留部分碼點作為保留、私人使用或特殊用途，已分配（assigned）給具體字符的數量大約在 1 百萬左右，常見教材會以約 $1,046,476$ 作為「已分配」的數字。

解題方法

1. 先回想 Unicode 的編碼規則：使用 21 bits 能夠表示 $2^{21}=2,097,152$ 個不同組合。
2. 觀察 Unicode 標準限制碼點上限為 $U+10FFFF$（十六進位），計算其十進位值：
   $0x10FFFF_{16}=1 \times 16^{5}+0 \times 16^{4}+F \times 16^{3}+F \times 16^{2}+F \times 16^{1}+F \times 16^{0}=1,114,112.$
3. 由此可得理論上可編碼的最大符號數為 $1,114,112$，但已分配的實際符號數量（題目常用的敘述）約為 $1,046,476$。

這題考的是作業系統 (Operating System, OS) 的核心功能。作業系統扮演著電腦硬體與使用者應用程式之間的橋樑，負責管理電腦的各種資源，並提供使用者一個方便的介面來操作電腦。

作業系統的主要角色包括：

1. 資源管理 (Resource Management)：這是作業系統最核心的功能之一。它負責管理 CPU 時間、記憶體空間、I/O 裝置等硬體資源，並將這些資源分配給同時執行的多個程式。選項 (A)「控制機器資源的分配」正是此一功能。
2. 處理器管理 (Processor Management)：負責排程 CPU 的使用，決定哪個程序在何時獲得 CPU 的執行權。
3. 記憶體管理 (Memory Management)：負責分配和回收記憶體空間給程序，並確保各程序之間的記憶體互不干擾。
4. 檔案系統管理 (File System Management)：負責管理儲存在硬碟、SSD 等儲存裝置上的檔案和目錄。這包括檔案的建立、刪除、讀取、寫入、存取權限控制等。選項 (C)「維護儲存在大量儲存中的檔案記錄」就是檔案系統管理的一部分。
5. 裝置管理 (Device Management)：負責管理電腦連接的各種外部設備（如印表機、鍵盤、滑鼠、網路卡等），並協調它們與 CPU 及記憶體之間的溝通。
6. 使用者介面 (User Interface)：提供使用者與電腦互動的方式，可以是命令列介面 (CLI) 或圖形使用者介面 (GUI)。

這題考的是「即時處理 (Real-time Processing)」的概念。即時處理是指系統必須在嚴格的時間限制內對輸入做出反應，否則將會導致系統失效或產生嚴重後果。即時系統通常用於需要快速回應的應用，例如控制系統、通訊系統、金融交易系統等。

即時系統可以分為兩類：

1. 硬式即時系統 (Hard Real-time Systems)：必須在絕對的時間限制內完成任務，任何延遲都可能導致災難性的後果。例如，飛機的飛行控制系統、工業自動化中的關鍵控制迴路。
2. 軟式即時系統 (Soft Real-time Systems)：雖然有時間限制，但偶爾的延遲是可以容忍的，只是會降低系統的效能或使用者體驗。例如，視訊串流、線上遊戲。

我們來分析各個選項：
(A) 使用文字處理器打字 (Typing a document with a word processor)：當你打字時，你期望鍵盤輸入能立即顯示在螢幕上。如果出現延遲，會影響你的打字流暢度和效率，但不會造成災難性的後果。這種情況屬於「軟式即時」或甚至嚴格來說不算嚴格的即時處理，因為用戶可以容忍短暫延遲，但希望能有即時的回應。然而，與其他選項相比，它的即時性要求最低。

這題考的是 TCP/IP 協定堆疊 (protocol stack) 的組成。TCP/IP 協定堆疊是網際網路的基礎，它將網路通訊的功能劃分為不同的層級，每一層都定義了一組協定。典型的 TCP/IP 模型包含四層或五層。

我們來分析各個選項：
(A) POP3 (Post Office Protocol version 3)：POP3 是一個應用層協定，用於從郵件伺服器下載電子郵件到使用者的電腦。它工作在 TCP/IP 協定的最上層，依賴於底層的 TCP 和 IP 協定。
(B) UDP (User Datagram Protocol)：UDP 是一個傳輸層協定。它提供了一種簡單的、無連接的、不可靠的資料傳輸服務。UDP 協定與 TCP 協定共同工作在傳輸層，並將資料傳遞給應用層。
(C) TCP (Transmission Control Protocol)：TCP 是一個傳輸層協定。它提供了一種可靠的、面向連接的資料傳輸服務，確保資料能夠按順序、無丟失、無重複地送達。TCP 是 TCP/IP 協定堆疊中最核心的協定之一。
(D) IP (Internet Protocol)：IP 是一個網路層協定。它負責將資料封包從源主機路由到目標主機，是網際網路的基礎。IP 協定在 TCP/IP 模型中扮演著關鍵的路由角色。

這題考的是網路通訊中，如何將接收到的資料封包正確地遞送到目標應用程式。當一個資料封包到達主機時，主機的作業系統需要知道這個封包是屬於哪個應用程式的，以便將其轉發給正確的處理程序。

我們來分析各個選項：
(A) 協定 (Protocol)：協定（如 TCP, UDP）定義了資料傳輸的規則和格式，但它本身並不直接指定是哪個應用程式接收資料。例如，一個 TCP 封包可能來自一個網頁伺服器，也可能來自一個 FTP 伺服器。
(B) 連接埠號 (Port number)：在 TCP/IP 模型中，連接埠號 (Port number) 是用來識別特定應用程式的。每個執行中的應用程式都會被分配一個唯一的連接埠號（在一個主機上）。

這題考的是程式設計中控制流程的概念，特別是關於重複執行 (iteration) 或重複呼叫 (recursion) 的方法。

我們來分析各個選項：
(A) Pretest loop (前測迴圈)：也稱為「當型迴圈 (while loop)」。在迴圈體執行之前，先檢查條件。如果條件為真，則執行迴圈體；如果條件為假，則跳出迴圈。這是一種重複執行指令區塊的方式。
(B) Posttest loop (後測迴圈)：也稱為「直到型迴圈 (do-while loop)」。先執行一次迴圈體，然後檢查條件。如果條件為假，則繼續執行迴圈體；如果條件為真，則跳出迴圈。

這題考的是物件導向程式設計 (Object-Oriented Programming, OOP) 的核心概念。物件導向程式設計強調將現實世界的物件抽象化為程式中的類別 (class)，並利用類別來創建物件 (object)。

我們來分析各個選項：
(A) Inheritance (繼承)：繼承是物件導向程式設計的一個重要特性。它允許一個類別（子類別或衍生類別）繼承另一個類別（父類別或基底類別）的屬性（資料成員）和方法（成員函數）。這使得子類別能夠重用父類別的程式碼，同時也能夠定義自己獨有的屬性和方法，或者修改（覆寫）父類別的方法。透過繼承，我們可以建立一系列具有共同特徵但又有所區別的類別，這正是題目所描述的「定義相似但不同的類別」。

這題考的是軟體工程中，如何管理和控制軟體系統的複雜性。複雜性是軟體開發中的一個主要挑戰，有效的管理策略對於開發出高品質、可維護的軟體至關重要。

我們來分析各個選項：
(A) CRC cards (Class-Responsibility-Collaboration cards)：CRC 卡片是一種物件導向設計的工具，用於在早期階段識別類別、它們的職責 (Responsibilities) 以及它們之間的協作關係 (Collaborations)。它有助於理解和設計系統的物件結構，從而幫助管理物件導向設計的複雜性。
(B) Modularity (模組化)：模組化是將一個大型軟體系統分解成一系列獨立、可交換的模組（或稱為組件、單元）的設計原則。每個模組負責系統的一部分功能，並且模組之間通過定義良好的介面進行交互。模組化有助於：
* 降低複雜性：將複雜的系統分解成較小的、易於理解和管理的單元。
* 提高可維護性：修改或除錯一個模組時，對其他模組的影響最小。
* 促進重用：獨立的模組可以被其他專案重複使用。

這題考的是二維陣列在記憶體中的儲存方式，特別是「逐列主序 (Row-Major Order)」的概念。

二維陣列 $X$ 可以表示為 $X[rows][columns]$。在記憶體中，二維陣列的元素是連續儲存的。儲存的順序取決於採用的是逐列主序還是逐行主序 (Column-Major Order)。

• 逐列主序 (Row-Major Order)：元素是按照「列」為單位，由上而下，由左至右的順序儲存。也就是說，第一列的所有元素會先儲存，然後是第二列的所有元素，依此類推。
• 逐行主序 (Column-Major Order)：元素是按照「行」為單位，由左至右，由上而下的順序儲存。也就是說，第一行的所有元素會先儲存，然後是第二行的所有元素，依此類推。

假設陣列 $X$ 的維度是 $m \times n$，即有 $m$ 列 (rows) 和 $n$ 行 (columns)。
對於一個元素 $X[i][j]$，其中 $i$ 是列索引，$j$ 是欄索引。

在逐列主序 (Row-Major Order) 下，元素 $X[i][j]$ 的記憶體位址計算公式通常是：
Base_Address + (i * number_of_columns + j) * element_size
(這裡假設索引是從 0 開始，如果從 1 開始，公式會略有調整)

核心觀念

本題考查二元樹的「根節點」定義：

• 根節點是樹中唯一沒有父節點的節點。
• 子節點必須由父節點向下連接。
• 二元樹中，每個節點最多有兩個子節點。
• 樹必須保持連通，且不能形成循環。

題目指出 W 與 X 都是 Y 的子節點，因此 Y 是 W、X 的父節點。

解題方法

由題意可建立關係：

其中箭頭代表「父節點指向子節點」。

Z 沒有子節點，表示 Z 是葉節點。但葉節點不等於根節點；根節點的判斷標準是「沒有父節點」。

若 Y 不是根節點，Y 必須有另一個父節點。題目中的其他節點為 W、X、Z：

• W、X 已經是 Y 的子節點，不可能同時成為 Y 的父節點，否則會形成循環。
• Z 沒有子節點，因此不能是 Y 的父節點。

所以 Y 沒有父節點，必定是根節點。

樹的結構為：

核心觀念
本題考查二維陣列的記憶體位址計算。

• 陣列的儲存方式：通常採用 row‑major（逐列儲存）或 column‑major（逐欄儲存）。
• 位址公式（以 row‑major 為例）：
  $\text{Addr}(A_{i,j}) = \text{Base} + \big[(i-1)\times N + (j-1)\big]\times s$
  其中
  • $\text{Base}$：$A_{1,1}$ 的起始位址
  • $N$：每列的元素個數（欄數）
  • $s$：單一元素佔用的位元組數（byte）

解題方法

1. 先判斷儲存方式與元素大小
   • 已知 $A(2,3)$ 位於 1756，$A(3,3)$ 位於 1760，兩者位址相差 4。
   • 若採用 row‑major，則同一欄、相鄰列的位址差為 $N\times s$。
   • 因相差 4，最簡的假設是 $s=1\,$byte、$N=4$（即每列 4 個元素）。
   • 若 $s$ 為 4 byte，則 $N$ 會是 1，與題目中欄號 3 不合；故排除。
   • 因此 假設每個元素 1 byte，且採 row‑major。

核心觀念

本題考查關聯式資料庫的兩個基本操作：

1. JOIN（連接）：依指定條件，將兩個關聯中符合條件的資料列配對。
2. PROJECT（投影）：從關聯中選取指定欄位，形成新的關聯。

連接條件為：

投影欄位為：

因此，先找出 $X.A$ 與 $Y.D$ 相等的資料列，再從連接結果中保留 $X.B$ 與 $Y.C$。

解題方法

1. 比對連接條件

關聯 $X$：

關聯 $Y$：

逐列檢查 $X.A = Y.D$：

• $X.A=2$ 時，$Y.D=2$ 的資料列為 $(C=w,D=2)$，符合條件。
• $X.A=5$ 時，$Y$ 中沒有 $D=5$ 的資料列，不產生配對。

這題考的是一個極簡化的程式語言「Bare Bones」的程式邏輯。Bare Bones 語言只有四個指令：

• clear var: 將變數 var 的值設為 0。
• incr var: 將變數 var 的值加 1。
• decr var: 將變數 var 的值減 1。
• while var not 0 do; ... end;: 條件迴圈。只要 var 的值不為 0，就執行迴圈體內的指令。一旦 var 的值變為 0，就跳出迴圈。

題目給定的程式碼和初始條件：

• 變數 X 的初始值是 3。
• 程式碼：

  clear Y;
  decr X;
  while X not 0 do;
    decr X;
    incr Y;
  end;
  

我們來逐步模擬程式的執行：

初始狀態:

• $X = 3$
• $Y$ 的值未定義，但第一行指令 clear Y; 會將其設為 0。

執行 clear Y;:

• $X = 3$
• $Y = 0$

執行 decr X;:

• $X$ 的值減 1。
• $X = 3 - 1 = 2$
• $Y = 0$

進入 while X not 0 do; ... end; 迴圈:

• 第一次迴圈檢查: $X$ 的值是 2。 $2 \neq 0$，所以條件為真。進入迴圈體。

這題考的是 RSA 非對稱式加密演算法的解密過程。

RSA 加密和解密的基本原理是基於模冪運算。

• 加密：明文 $M$ 被加密成密文 $C$，公式為 $C = M^e \pmod{n}$，其中 $e$ 是公鑰的指數，$n$ 是模數。
• 解密：密文 $C$ 被解密成明文 $M$，公式為 $M = C^d \pmod{n}$，其中 $d$ 是私鑰的指數，$n$ 是模數。

題目給定的資訊：

• 私鑰指數 $d = 5$。
• 模數 $n = 133$。
• 密文 $C$ 的位元模式是 11。這裡的「位元模式」指的就是密文的數值，即 $C = 11$。

我們需要計算明文 $M$，使用解密公式：
$M = C^d \pmod{n}$
$M = 11^5 \pmod{133}$

現在我們需要計算 $11^5 \pmod{133}$。
我們可以逐步計算：
$11^1 \pmod{133} = 11$
$11^2 \pmod{133} = 121$
$11^3 \pmod{133} = 11^2 \times 11 \pmod{133} = 121 \times 11 \pmod{133}$
$121 \times 11 = 1331$
$1331 \div 133$：
$1331 = 10 \times 133 + 1$
所以，$11^3 \pmod{133} = 1$。

現在我們可以利用 $11^3 \equiv 1 \pmod{133}$ 來簡化計算 $11^5 \pmod{133}$：
$11^5 = 11^3 \times 11^2$
$11^5 \pmod{133} = (11^3 \pmod{133}) \times (11^2 \pmod{133}) \pmod{133}$

核心觀念

本題考查上下文無關文法的遞迴產生式與語法分析樹。依圖中的語法圖，Leak 可由下列規則產生：

第一條是遞迴的基底；第二條會在原有的 Leak 後面再接上一個 drip。

解題方法

由開始符號 Leak 出發，連續使用遞迴規則兩次，最後使用基底規則：

因此可畫出下列語法分析樹：