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

本題考查錯誤修正碼 (Error-Correcting Code, ECC) 的基本概念，特別是漢明距離 (Hamming Distance) 與錯誤偵測/修正能力之間的關係。

核心概念：
漢明距離 $d$ 的錯誤修正碼，可以偵測最多 $d-1$ 個錯誤，以及修正最多 $\lfloor \frac{d-1}{2} \rfloor$ 個錯誤。

解題過程：
題目中提到，任意兩個編碼字 (code patterns) 之間的漢明距離為 8。
這表示 $d = 8$。

核心觀念

中央處理器（CPU）內部主要包含：

• 控制單元（Control Unit, CU）：控制指令擷取、解碼與各部件的運作。
• 算術邏輯單元（Arithmetic Logic Unit, ALU）：執行算術運算與邏輯／布林運算。
• 暫存器（Registers）：暫存指令、位址、資料與運算中間結果。

判斷某項活動是否「完全在 CPU 內進行」的關鍵，是看該活動是否需要和主記憶體或其他外部元件交換資料。

解題方法

逐一檢查各選項是否需要 CPU 外部的記憶體：

• 若只涉及 ALU、控制單元與暫存器，通常屬於 CPU 內部活動。
• 若需要從主記憶體取得資料或指令，就不是完全在 CPU 內進行。

指令擷取（instruction fetch）的基本流程為：

$$PC \rightarrow \text{主記憶體位址}$$ $$\text{主記憶體} \rightarrow IR$$

其中：

• $PC$（Program Counter）儲存下一個指令的位址。
• $IR$（Instruction Register）儲存目前擷取到的指令。

由於指令通常必須由主記憶體傳送至 CPU 的指令暫存器，因此指令擷取涉及 CPU 與主記憶體之間的資料傳輸，並非完全在 CPU 內進行。

選項分析

A. Fetch instructions

本題考查作業系統中的「上下文切換」(Context Switch) 概念。

核心概念：
上下文切換是指作業系統在 CPU 上從執行一個行程 (process) 切換到另一個行程的過程。這個過程需要保存當前行程的執行狀態（CPU 暫存器、程式計數器、記憶體映射等），並載入下一個要執行的行程的狀態。

解題過程：
我們分析各選項在上下文切換中的作用：
A. Interrupt (中斷)：中斷是觸發上下文切換的常見原因之一。當硬體設備（如定時器、I/O 設備）發出中斷信號時，CPU 會暫停當前行程的執行，轉而去處理中斷服務程序。在處理完中斷後，作業系統可能會決定進行上下文切換，以執行其他行程。

本題考查網路連接設備與網路架構的相關知識。

核心概念：
網路設備用於連接不同的網路或在網路內部傳輸資料。常見的網路連接設備包括交換器 (Switch)、路由器 (Router) 和橋接器 (Bridge)。伺服器 (Server) 則是一種提供服務的電腦，它本身不是連接網路的設備，而是連接到網路上的節點。

解題過程：
我們逐一分析選項：
A. Switch (交換器)：交換器是工作在資料鏈路層 (Layer 2) 的設備，用於在區域網路 (LAN) 內部連接多個設備，並根據 MAC 位址轉發資料幀 (frame)。它是一種連接設備。

本題考查排序演算法的時序複雜度 (Time Complexity)。

核心概念：
插入排序 (Insertion Sort) 是一種簡單的排序演算法，它將元素逐一插入到已排序的序列中。

• 在最好的情況下 (列表已排序)，插入排序的時間複雜度是 $\Theta(n)$。
• 在最壞的情況下 (列表反向排序)，插入排序的時間複雜度是 $\Theta(n^2)$。
• 在平均情況下，插入排序的時間複雜度也是 $\Theta(n^2)$。

常見的演算法時間複雜度類別：

• $\Theta(\lg n)$: 對數時間，例如二分搜尋。
• $\Theta(n)$: 線性時間，例如簡單遍歷。
• $\Theta(n \lg n)$: 準線性時間，例如合併排序 (Merge Sort)、堆積排序 (Heap Sort)、快速排序 (Quick Sort) 的平均情況。

本題考查編譯器 (Compiler) 的工作流程與輸出。

核心概念：
編譯器是將高階程式語言撰寫的原始碼 (Source Code) 翻譯成機器碼 (Machine Code) 或其他低階語言的程式。編譯過程通常包含詞法分析、語法分析、語意分析、中間碼生成、程式碼最佳化和目標碼生成等階段。

解題過程：
我們分析編譯器在各階段的產出：
A. Source code (原始碼)：這是編譯器的輸入，而不是編譯器「建構」的輸出。編譯器讀取原始碼，然後進行處理。
B. Symbol table (符號表)：編譯器在分析程式時，會建立一個符號表來記錄程式中使用的變數、函數、常數等識別符的資訊（如名稱、類型、作用域、記憶體位置等）。

本題考查著作權法 (Copyright Law) 的基本目的。

核心概念：
著作權法是保護創作者在其原創作品上的權利。其主要目的是在鼓勵創作和促進知識傳播之間取得平衡。

解題過程：
我們分析各選項：
A. to allow authors to distribute their work while maintaining certain ownership rights. (允許作者在保有特定所有權權利的同時，散佈其作品。)
這是著作權法的主要目的之一。著作權法賦予作者散佈、複製、修改其作品的獨佔權利，同時也確保他們能從中獲得收益或認可。

B. to allow authors to maintain ownership of their ideas. (允許作者保有其「想法」的所有權。)
著作權法保護的是「表達」的創作，而不是「想法」本身。想法是自由的，任何人都可以自由使用和傳播想法。

核心觀念

本題考查二元樹（Binary Tree）的節點數與葉節點數之關係，核心用到兩個定理：

定理一（Full Binary Tree 性質）：在一棵二元樹中，若所有內部節點（internal nodes）恰好都有兩個子節點，則：

$\text{葉節點數} = \text{內部節點數} + 1$

設葉節點數為 $L$、內部節點數為 $I$，則 $L = I + 1$，即 $I = L - 1$。

定理二（總節點最小化）：在葉節點數固定為 $L$ 的前提下，使整棵樹總節點數最少的結構，正是每個內部節點都有兩個子節點的 Full Binary Tree（又稱 Strictly Binary Tree）。此時總節點數為：

$N = L + I = L + (L - 1) = 2L - 1$

---

解題方法

題目指出：某棵二元樹的葉節點數為 $2^n$（$n$ 為正整數），問整棵樹至少含有幾個節點。

「至少」意味著求總節點數的最小值。

最小化的關鍵：每個內部節點有兩個子節點時，每新增一個內部節點就可帶出兩個葉節點；若某內部節點只有一個子節點（single child），等同浪費了一個節點位置，反而使樹需要更多節點才能達到相同的葉節點數。

因此，總節點數最小的結構 = Full Binary Tree。

代入 $L = 2^n$：

$I = L - 1 = 2^n - 1$

$N_{\min} = L + I = 2^n + (2^n - 1) = 2 \cdot 2^n - 1 = 2^{n+1} - 1$

---

選項分析

本題考查資料庫交易 (Database Transactions) 的並行控制 (Concurrency Control) 問題。

核心概念：
當多個交易同時存取和修改資料庫中的資料時，可能會發生一些問題，影響資料的一致性和正確性。為了避免這些問題，需要採用適當的交易管理和鎖定機制。

解題過程：
我們分析各選項：
A. Lost update problem (遺失更新問題)：當兩個交易讀取同一筆資料，然後都基於這個舊值進行修改並寫回時，其中一個交易的更新就會被另一個交易的更新所覆蓋，導致第一個交易的更新遺失。這是並行存取時可能發生的問題。
B. Clustering (叢集)：叢集通常是指將相關的資料儲存在一起，以提高存取效率。這是一種資料組織或儲存策略，本身並不是多個交易同時存取資料時「發生」的問題。

本題考查計算複雜度理論 (Computational Complexity Theory) 中的 NP 問題類別。

核心概念：

• P 問題 (Polynomial time problems)：可以在多項式時間內被確定型圖靈機 (Deterministic Turing Machine) 解決的問題類別。
• NP 問題 (Nondeterministic Polynomial time problems)：可以在多項式時間內被「非確定型圖靈機」(Nondeterministic Turing Machine) 驗證一個給定的解的問題類別。換句話說，如果一個問題的解是「對」的，那麼可以在多項式時間內找到一個證明。
• NP-complete 問題 (NP-complete problems)：屬於 NP 類別，並且是 NP 類別中最「困難」的問題，任何 NP 問題都可以在多項式時間內歸約 (reduce) 到 NP-complete 問題。

本題考查程式流程的理解與執行追蹤，特別是條件判斷 (if-else) 和變數操作。

核心概念：
程式流程圖的理解：程序從上到下執行，遇到條件判斷時，根據條件的真假選擇執行哪個分支。
變數的更新：當變數被賦值或進行運算後，其值會被更新。

解題過程：
程序 xxx(N) 的邏輯是：
如果輸入的 N 小於 7，則直接印出 N 的值。
否則 (如果 N 大於或等於 7)，則將 N 的值加上 3，然後印出更新後的值。

核心觀念

漢明距離（Hamming Distance）

兩個等長位元字串之間的漢明距離，定義為對應位置上位元值不同的個數。例如：

$d_H(011000,\ 011100) = 1$

（兩者僅第 4 位不同：$0 \neq 1$）

錯誤更正能力

若一組編碼系統的任意兩個合法碼字之間的最小漢明距離為 $d_{min}$，則：

• 偵錯能力：可偵測最多 $d_{min}-1$ 個位元錯誤
• 更正能力：可更正最多 $\lfloor \dfrac{d_{min}-1}{2} \rfloor$ 個位元錯誤

本題明示 $d_{min} = 3$，因此可更正 $\lfloor \dfrac{3-1}{2} \rfloor = 1$ 個位元錯誤。

解碼原則（最近鄰居解碼，Nearest Neighbor Decoding）

收到一個待解碼的樣式（pattern）時，計算它與每一個合法碼字的漢明距離，選擇距離最小的合法碼字作為解碼結果。

---

解題方法

對每個待解碼的 6 位元樣式，逐一與 A～H 的碼字進行位元比較，統計不同位元數即為漢明距離，取距離最小者作為答案。

為方便計算，採用逐位對齊比較的方式，以 $\oplus$（XOR）思維逐位比較，差異位數即距離。

---

解題過程

樣式一：010011

符號	碼字	與 010011 逐位比較	漢明距離
A	000000	010011 → 3位不同	3
B	001111	010011→ … 共3位	3
C	010011	每位完全相同	0 ✓
D	011100	第3、5、6位不同	3
E	100110	多位不同	4
F	101001	多位不同	4
G	110101	多位不同	5
H	111010	多位不同	4

010011 與 C 的漢明距離為 0，即完全吻合，直接解碼為 C。

---

樣式二：101010

符號	碼字	位元差異（標底線為不同位）	漢明距離
A	000000	101010 → 第1,3,5位不同	3
B	001111	第1,4,6位不同	3
C	010011	第1,2,3,6位不同	4
D	011100	第1,2,4,5位不同	4
E	100110	第3,4位不同	2
F	101001	第5,6位不同	2
G	110101	第2,3,4,5,6位不同	5
H	111010	僅第2位不同（0 vs 1）	1 ✓

詳細比對 101010 vs 111010：

$$\begin{array}{ccccccc} \text{位置} & 1 & 2 & 3 & 4 & 5 & 6 \\ \text{接收} & 1 & 0 & 1 & 0 & 1 & 0 \\ \text{H} & 1 & 1 & 1 & 0 & 1 & 0 \\ \text{差異} & & \times & & & & \\ \end{array}$$

距離為 1，推斷第 2 位發生單一位元翻轉錯誤，解碼為 H。

---

樣式三：011000

符號	碼字	位元差異	漢明距離
A	000000	第2,3位不同	2

本題考查算術表達式的轉換，特別是中序表達式 (Infix Expression) 到後序表達式 (Postfix Expression) 的轉換。

核心概念：
中序表達式：運算符位於兩個運算元之間 (例如 a + b)。
後序表達式：運算符位於兩個運算元之後 (例如 a b +)。
轉換規則：通常使用堆疊 (Stack) 來實現中序轉後序的轉換。轉換過程遵循運算符的優先級和結合性。

運算符優先級：

1. 括號 ()
2. 乘法 * 和 除法 / (同級，從左到右結合)
3. 加法 + 和 減法 - (同級，從左到右結合)

轉換步驟：
從左到右掃描中序表達式。

• 如果遇到運算元，直接加入後序表達式。
• 如果遇到左括號 (，將其壓入堆疊。
• 如果遇到右括號 )：將堆疊中所有運算符彈出並加入後序表達式，直到遇到左括號 (。然後將左括號 ( 彈出並捨棄。
• 如果遇到運算符 op1：
  • 當堆疊頂部的運算符 op2 的優先級高於或等於 op1 的優先級 (且 op2 不是左括號)，則將 op2 彈出並加入後序表達式。重複此步驟直到條件不滿足。
  • 然後將 op1 壓入堆疊。
• 掃描結束後，將堆疊中剩餘的所有運算符彈出並加入後序表達式。

解題過程：
中序表達式：(b+c)*5+(15*m+2)/7+6

1. 掃描 (：壓入堆疊。 Stack: (
2. 掃描 b：加入後序。 Postfix: b
3. 掃描 +：壓入堆疊。 Stack: ( +
4. 掃描 c：加入後序。 Postfix: b c
5. 掃描 )：彈出 +，加入後序。 Postfix: b c +。彈出 (，捨棄。 Stack: empty.
6. 掃描 *：壓入堆疊。 Stack: *
7. 掃描 5：加入後序。 Postfix: b c + 5
8. 掃描 +：
   • 堆疊頂部是 *，優先級高於 +。彈出 *，加入後序。 Postfix: b c + 5 *。
   • 堆疊變空。
   • 壓入 +。

核心觀念

本題考查兩個觀念：

1. 位元組合數量：若使用 $k$ 個位元表示資料，每個位元有 $0$、$1$ 兩種狀態，因此可形成 $2^k$ 種不同組合。
2. 指令格式與延伸操作碼：固定長度指令中，位址欄位所占位元越多，留給操作碼的位元越少。不同格式共存時，必須分配不重疊的操作碼編碼空間。

---

(a) 4 bytes 可表示的不同數字數量

解題方法

1 byte 等於 $8$ bits，因此 4 bytes 共包含：

$$4 \times 8 = 32 \text{ bits}$$

每一個 bit 有兩種狀態：$0$ 或 $1$。因此 32 個 bits 可形成的不同位元組合數為：

$$2^{32}$$

計算得：

$$2^{32}=4,294,967,296$$

在題目未指定特定浮點數格式、保留位元、正負號或特殊值的情況下，採用「每一種 32-bit 位元組合代表一個不同數字」的標準假設。

---

(b) 一位址指令的最大數量

1. 計算各種指令可使用的操作碼位元數

機器指令長度為 16 bits，每個位址需要 6 bits。

二位址指令

二位址指令需要兩個位址欄位：

$$6+6=12 \text{ bits}$$

因此操作碼欄位剩下：

$$16-12=4 \text{ bits}$$

若只考慮二位址指令，4-bit 操作碼最多可區分：

$$2^4=16$$

種指令。

一位址指令

一位址指令需要一個 6-bit 位址欄位，因此操作碼欄位有：

$$16-6=10 \text{ bits}$$

若全部用於一位址指令，最多可產生：

$$2^{10}=1024$$

個 10-bit 操作碼。

---

本題考查 RSA 加密演算法的基本原理，包括金鑰對的生成和使用。

核心概念：
RSA 加密演算法的安全性基於大數分解的困難性。其金鑰對的生成過程如下：

1. 選擇兩個不同的、足夠大的質數 $p$ 和 $q$。
2. 計算模數 $n = p \times q$。
3. 計算歐拉函數 $\phi(n) = (p-1)(q-1)$。
4. 選擇一個整數 $e$，滿足 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$。$e$ 是公鑰的一部分。
5. 計算 $d$，使得 $d \times e \equiv 1 \pmod{\phi(n)}$。$d$ 是私鑰的一部分。
   公鑰為 $(n, e)$，私鑰為 $(n, d)$。

Part A: Finding the two prime numbers (p and q)

解題過程：
我們已知公鑰中的模數 $n = 15$。
$n$ 是由兩個質數 $p$ 和 $q$ 相乘得到的。
我們需要找到兩個質數，它們的乘積是 15。
由於 15 是一個小數，我們可以很容易地進行因式分解：
$15 = 3 \times 5$。
檢查 3 和 5：它們都是質數。
因此，這兩個質數是 3 和 5。

【答案 A】3 和 5

Part B: Finding the decryption key (d)

解題過程：
我們已經找到 $p=3$ 和 $q=5$。

1. 計算 $\phi(n)$:
   $\phi(n) = (p-1)(q-1) = (3-1)(5-1) = 2 \times 4 = 8$。

2. 我們已知公鑰指數 $e = 13$。
   我們需要驗證 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$。

   • $1 < 13 < 8$：這個條件不滿足！ $13$ 並不小於 $8$。
   • 這表示題目中的 $e=13$ 可能有誤，或者 $n=15$ 和 $e=13$ 這組公鑰是不合法的。
   • 讓我們假設題目中的 $e=13$ 是正確的，並且我們需要找到 $d$ 使得 $d \times e \equiv 1 \pmod{\phi(n)}$。

   如果 $e=13$ 且 $\phi(n)=8$：
   我們需要找到 $d$ 使得 $13d \equiv 1 \pmod{8}$。
   由於 $13 \equiv 5 \pmod{8}$，原式變為 $5d \equiv 1 \pmod{8}$。
   我們可以嘗試不同的 $d$ 值（從 1 開始）：

   • $d=1: 5 \times 1 = 5 \not\equiv 1 \pmod{8}$
   • $d=2: 5 \times 2 = 10 \equiv 2 \pmod{8}$
   • $d=3: 5 \times 3 = 15 \equiv 7 \pmod{8}$
   • $d=4: 5 \times 4 = 20 \equiv 4 \pmod{8}$