107 關務特考三等 電機工程 計算機概論 考古題詳解

核心觀念

1. 基底轉換（Radix Conversion）：

• 除基取餘法（Repeated Division by $r$）：整數由十進位轉換至 $r$ 進位時，將十進位數連續除以基底 $r$，直到商為 $0$ 為止；各步驟之餘數由最後一次除法（最高有效位元，MSB）往第一次除法（最低有效位元，LSB）反向排列，即為目標進位數。
• 二進位與十六進位快速對應：由於 $16 = 2^4$，四個二進位位元（Bit）恰可對應一個十六進位位元（Hex Digit），可直接利用分組方式進行轉換。

2. 補數系統（Complement System）： 對於基底為 $r$ 的 $n$ 位數 $N$：

• 基底減 1 補數（Diminished Radix Complement）：二進位中稱為 $1$ 之補數（1's complement），公式為 $(r^n - 1) - N$。實作上即為將二進位數的每個位元「反相」（Bitwise NOT，$0$ 變 $1$、$1$ 變 $0$）。
• 基底補數（Radix Complement）：二進位中稱為 $2$ 之補數（2's complement），公式為 $r^n - N = ((r^n - 1) - N) + 1$。實作上即為其 $1$ 之補數加 $1$。
• 位元寬度（Word Size / Bit-width）與符號意涵：在數位邏輯運算中，求一個數的補數運算通常指取其「反相」與「反相加 1」（此結果亦代表負數 $-N$ 在補數系統中的編碼）。由於題目未指明暫存器長度，標準作法需以容納該數所需的最小位元數（12 位元）為基礎計算，並補充電腦系統常見之標準 16 位元（2 Bytes）格式，以求完整。

---

解題方法

(一) 求二進位數及其 $1$ 之補數與 $2$ 之補數

1. 十進位轉二進位（連續除以 2 取餘數）：

$$\begin{aligned} 3428 \div 2 &= 1714 \quad \dots \text{餘 } 0 \quad (\text{LSB}) \\ 1714 \div 2 &= 857 \quad \dots \text{餘 } 0 \\ 857 \div 2 &= 428 \quad \dots \text{餘 } 1 \\ 428 \div 2 &= 214 \quad \dots \text{餘 } 0 \\ 214 \div 2 &= 107 \quad \dots \text{餘 } 0 \\ 107 \div 2 &= 53 \quad \dots \text{餘 } 1 \\ 53 \div 2 &= 26 \quad \dots \text{餘 } 1 \\ 26 \div 2 &= 13 \quad \dots \text{餘 } 0 \\ 13 \div 2 &= 6 \quad \dots \text{餘 } 1 \\ 6 \div 2 &= 3 \quad \dots \text{餘 } 0 \\ 3 \div 2 &= 1 \quad \dots \text{餘 } 1 \\ 1 \div 2 &= 0 \quad \dots \text{餘 } 1 \quad (\text{MSB}) \end{aligned}$$

由下往上記錄餘數，得二進位數為： $(3428)_{10} = (110101100100)_2$ （共需 12 個位元表示）

2. 求 $1$ 之補數（1's complement）：

• 以最小位元長度（12 位元）計算： 將 $(110101100100)_2$ 每個位元各自反相（$0 \to 1, 1 \to 0$）： $110101100100 \xrightarrow{\text{反相}} 001010011011_2$
• 以標準 16 位元（2 Bytes）長度計算： 若將原數擴展為 16 位元無號格式：$(0000\,1101\,0110\,0100)_2$， 其各個位元反相後為：$(1111\,0010\,1001\,1011)_2$。

3. 求 $2$ 之補數（2's complement）：

• 以最小位元長度（12 位元）計算： 取其 $1$ 之補數加 $1$： $001010011011_2 + 1 = 001010011100_2$
• 以標準 16 位元（2 Bytes）長度計算： 取其 16 位元之 $1$ 之補數加 $1$： $1111001010011011_2 + 1 = 1111001010011100_2$

(註：若依帶符號數表示法觀點，正數本身於補數系統中之表示式與原碼相同；上述求得之補數結果即為代表其相反數 $-(3428)_{10}$ 之補數編碼。)

---

(二) 求三進位數及十六進位數

1. 十進位轉三進位（連續除以 3 取餘數）：

核心觀念

本題評量計算機系統結構中的核心主題——記憶體階層架構（Memory Hierarchy）與儲存媒體之底層物理特性。

1. 記憶體階層設計原則：在計算機架構中，存取速度越快的儲存元件，單位容量成本越高、容量越小，故需藉由多層次配置，兼顧 CPU 高速運算需求與大容量儲存成本。
2. 存取延遲的數量級差異：存取時間由快到慢跨越不同數量級：

• 奈秒級（$1\text{ ns} = 10^{-9}\text{ s}$）：暫存器、快取、主記憶體
• 微秒級（$1\ \mu\text{s} = 10^{-6}\text{ s}$）：隨身碟（快閃記憶體）
• 毫秒級（$1\text{ ms} = 10^{-3}\text{ s}$）：機械硬碟、光碟

3. 物理運作原理與瓶頸：儲存裝置的反應速度根本上取決於資料讀寫所依賴的物理現象。純電子態（電荷／電流控制）的反應速度遠高於涉及巨觀質量位移的機械運動（馬達旋轉與讀寫臂位移）。

---

解題方法

解題分為兩大維度循序切入：

1. 速度排序切入點（記憶體階層）：

• 先由「離 CPU 核心之邏輯與實體距離」區分內部儲存（暫存器 $\to$ 快取 $\to$ 主記憶體）與輔助儲存（隨身碟 $\to$ 硬碟 $\to$ 光碟）。
• 各層級以典型存取時間（Access Time / Latency）為客觀基準排定先後順序。

2. 物理機制解釋切入點（物理特性與運動瓶頸）：

• 明確回答「是」，裝置的快慢差異確實直接源自於所涉及的物理原理。
• 將裝置按「純電子學」、「電磁學＋機械運動」、「光學＋機械運動」分類，論述電子流動與機械位移在時間尺度上的巨大落差。

---

各項硬體特性與物理機制分析

本題所列六項記憶元件，依存取速度由快至慢逐一分析其技術原理與物理機制：

1. 暫存器（Register）

• 速度等級：$< 1\text{ ns}$（通常僅需 1 個時脈週期，如 $0.2\sim 0.5\text{ ns}$）。
• 物理機制（電子學）：直接整合於 CPU 核心內部，通常由 D 型正反器（Flip-Flop）或超高速靜態隨機存取記憶體（SRAM）晶胞組成，透過電晶體邏輯閘的電子導通與截止直接讀寫狀態，無電容充放電延遲，速度最快。

2. 快取記憶體（Cache）

• 速度等級：約 $1\sim 20\text{ ns}$（L1 快取約 $1\sim 4$ 個週期，L3 快取約 $20\sim 40$ 個週期）。
• 物理機制（電子學）：採用 6 顆電晶體（6T）組成的 SRAM 晶胞，利用正反器雙穩態電路鎖定電位儲存二進位訊號。相較於暫存器，快取容量較大且需經由解碼與標籤比對（Tag Match）電路，速度略次於暫存器。

3. 主記憶體（Main Memory）

• 速度等級：約 $50\sim 100\text{ ns}$。
• 物理機制（電子學）：普遍採用動態隨機存取記憶體（DRAM），單一晶胞由 1 顆電晶體與 1 個微型電容（1T1C）構成。因資料以電容儲存電荷，存取時有電容充放電時間，且漏電問題需要週期性充電刷新（Refresh），加上匯流排與記憶體控制器排程延遲，存取時間顯著大於 SRAM。

4. 隨身碟（USB Drive）

• 速度等級：隨機存取約 $25\sim 100\ \mu\text{s}$，資料傳輸率數十至數百 $\text{MB/s}$。
• 物理機制（電子學）：內部為非揮發性 NAND 快閃記憶體（Flash Memory），利用浮閘電晶體（Floating Gate）或電荷捕捉（Charge Trap）技術，以穿隧效應（Fowler-Nordheim Tunneling）注入或抽離電子來改變臨界電壓。讀寫均為純固態電子操作，無機械構造；但因塊區（Block）抹除與頁面（Page）程式化機制的物理化學限制，延遲落於微秒級，慢於主記憶體，但遠快於機械裝置。

5. 硬碟（Hard Disk, HDD）

• 速度等級：約 $5\sim 15\text{ ms}$。

本題布林式於試題文本擷取時缺失變數上方之反相橫線（NOT 符號），致使各積項均呈現同相乘積；依題文字面資訊合理假設，所有變數皆為原態，直接以題目給定之布林式進行卡諾圖化簡。

核心觀念

1. 布林代數等冪律（Idempotent Law）： 對於任意布林運算元 $X$，滿足： $X + X = X$ 當邏輯和（OR）表示式中包含多個完全相同的乘積項時，可化簡為單一項。
2. 最小項（Minterm）定義： 在 $n$ 個布林變數的系統中，由所有變數各自以原態（True）或反相（Complement）形式相乘所構成的乘積項稱為最小項。對於四變數 $A, B, C, D$，乘積項 $ABCD$ 對應二進位數值 $1111_2$，即最小項 $m_{15}$。
3. 四變數卡諾圖（Karnaugh Map）之結構與相鄰性：

• 四變數卡諾圖包含 $2^4 = 16$ 個方格，橫軸與縱軸編碼必須依循**格雷碼（Gray Code）**順序（$00, 01, 11, 10$），確保幾何相鄰的方格在邏輯上僅有一個變數狀態改變。
• 圈選化簡原則：在圖中標示所有值為 $1$ 的方格，將相鄰的 $1$ 合併為大小為 $2^k$（$k = 0, 1, 2, 3, 4$）之最大矩形方塊。方塊包含的方格數越多，可消去的變數越多；每增加一倍方格數，即消去一個變數。

---

解題方法

步驟一：整理與化簡原始布林式

題目給定之布林函數為： $F(A,B,C,D) = A\,BC\,D + ABCD + ABCD + ABC\,D + ABCD + ABCD + ABC\,D$

式中各積項之組成變數均為 $A, B, C, D$ 的邏輯乘積（AND）。依布林代數乘法交換律與結合律，各項實質皆為同相乘積項 $ABCD$。 應用布林代數等冪律 $X + X = X$，將 7 個完全相同的乘積項相加化簡為單一項： $F(A,B,C,D) = ABCD$

對應之最小項表示法為： $F(A,B,C,D) = \sum m(15)$ 即僅當輸入組合為 $(A, B, C, D) = (1, 1, 1, 1)$ 時，函數輸出為 $1$。

步驟二：繪製並填入四變數卡諾圖

以列表示變數 $AB$、行表示變數 $CD$，建立 $4 \times 4$ 卡諾圖。編碼軸依格雷碼編列為 $00, 01, 11, 10$。 將最小項 $m_{15}$（對應列 $AB=11$、行 $CD=11$）填入 $1$，其餘 15 個最小項方格皆填入 $0$：

核心觀念

本題評量重點為**分治法（Divide-and-Conquer）與遞迴演算法（Recursive Algorithm）**的設計與複雜度分析。

1. 分治策略（Divide-and-Conquer）： 將大問題拆解為數個同性質的小問題，遞迴求解後再合併結果。欲將 $n$ 個盤子由來源木樁移至目的木樁，本質上可拆解為三個步驟：

• 先將上方 $n-1$ 個盤子移至輔助木樁。
• 將底層最大盤子（第 $n$ 個盤子）直接移至目的木樁。
• 再將位於輔助木樁的 $n-1$ 個盤子移至目的木樁。

2. 終止條件（Base Case）： 當 $n = 1$ 時，直接將該盤子從來源木樁移至目的木樁，無須再遞迴。
3. 時間複雜度與遞迴關係式： 設移動 $n$ 個盤子的總步數為 $T(n)$： $T(n) = 2T(n-1) + 1,\quad T(1) = 1$ 展開推導： $T(n) = 2(2T(n-2) + 1) + 1 = 2^2 T(n-2) + 2 + 1 = \cdots = 2^{n-1}T(1) + \sum_{k=0}^{n-2} 2^k = 2^n - 1$ 故時間複雜度為 $\mathcal{O}(2^n)$；遞迴呼叫堆疊深度最大為 $n$，空間複雜度為 $\mathcal{O}(n)$。

---

解題方法

1. 演算法邏輯架構

定義函數介面為 Hanoi(n, source, auxiliary, target)，代表將 $n$ 個盤子由 source（來源柱）藉由 auxiliary（輔助柱）移動到 target（目的柱）：

• 步驟 1（Base Case）：若 $n = 1$，直接執行「將盤子從 source 移到 target」，結束本層呼叫。
• 步驟 2（遞迴第一階段）：呼叫 Hanoi(n - 1, source, target, auxiliary)，將前 $n-1$ 個盤子從 source 移至 auxiliary，此時 target 作為暫存輔助。
• 步驟 3（核心移動）：執行「將盤子從 source 移到 target」（此為第 $n$ 個最大盤）。
• 步驟 4（遞迴第二階段）：呼叫 Hanoi(n - 1, auxiliary, source, target)，將位在 auxiliary 的 $n-1$ 個盤子移至 target，此時 source 作為暫存輔助。

2. 演算法虛擬碼（Pseudocode）