109 專技高考高等考試 電子工程技師 電子計算機原理 考古題詳解

核心觀念

本題評量數位邏輯與計算機組織中最基礎且關鍵的「數字系統基底轉換（Radix Conversion）」，主要涵蓋以下兩大數學與邏輯原理：

1. 加權展開法（Weighted Positional Representation）： 任何基底為 $r$ 的整數 $N_r = (d_{n-1}d_{n-2}\dots d_1d_0)_r$，轉換為等值十進位數值時，採用位值權重展開求和： $N_{10} = \sum_{i=0}^{n-1} d_i \times r^i$

2. 以二進位為樞紐之位元分組對應法（Bit Grouping Method）： 因為八進位與十六進位之基底皆為 2 的次方倍數（$8 = 2^3$、$16 = 2^4$）：

• 八進位 $\leftrightarrow$ 二進位：每一位八進位數字對應固定 3 位元（bits） 的二進位數。
• 二進位 $\leftrightarrow$ 十六進位：由最低有效位元（LSB）向最高有效位元（MSB），每 4 位元（bits） 分為一組對應一位十六進位數字（不足 4 位元時於高位補 0）。
• 八進位 $\leftrightarrow$ 十六進位：最簡捷的路徑是透過「二進位」作為中繼橋樑，無需經由十進位進行反覆除法，大幅降低運算錯誤率。

---

解題方法

題目給定八進位數字 $23456_8$，最佳解題順序為：先轉二進位，再轉十六進位，最後計算十進位。

步驟一：轉換為二進位（八進位 $\rightarrow$ 二進位）

將 $23456_8$ 的每一個位數個別以 3 位元二進位碼表示：

• $2_8 = 010_2$
• $3_8 = 011_2$
• $4_8 = 100_2$
• $5_8 = 101_2$
• $6_8 = 110_2$

由高位至低位串接得： $(010)(011)(100)(101)(110)_2 = 010011100101110_2$ 去除最高位不具實質數值的無效 $0$，得到二進位結果： $10011100101110_2$

步驟二：轉換為十六進位（二進位 $\rightarrow$ 十六進位）

將上述二進位數由最右端（LSB）起，向左每 4 位元分成一組，最高位不足 4 位元者於前方補 0：

• 第 1 組（最低 4 位）：$1110_2 = 14_{10} = \text{E}_{16}$
• 第 2 組：$0010_2 = 2_{16}$
• 第 3 組：$0111_2 = 7_{16}$
• 第 4 組（最高位）：$0010_2$（由 $10_2$ 高位補 0 形成）$= 2_{16}$

核心觀念

1. 輔助記憶體（Auxiliary Storage / Secondary Storage） 在計算機記憶體階層（Memory Hierarchy）中，輔助記憶體位處主記憶體（Main Memory）之下，具備非揮發性（Non-volatile）、單位成本低、容量龐大等特點，用於長期儲存程式與資料。
2. 資料存取方式（Data Access Methods） 依計算機結構（Computer Architecture）之定義，輔助記憶體最常見的兩種存取方式為：

• 循序存取（Sequential Access）：存取記錄必須依照特定的實體線性順序依次前進。
• 直接存取（Direct Access）：系統可根據資料的實體位址（如磁柱、磁軌、磁區），直接將讀寫機構移至目標區塊附近再進行存取。

3. 存取時間特性

• 循序存取的時間與目標資料相對於目前讀寫頭的位置高度相依，具高度變異性。
• 直接存取的存取時間主要取決於硬體定位時間（尋道時間與旋轉延遲），但不需要依序掃描前方所有的無關資料。

---

解題方法

本題為典型的計算機系統儲存機制問答題，切入點應分為兩大主軸：

1. 精確定義兩種主要存取方式並給出最具代表性的儲存媒介。
2. 由「硬體運作架構」、「存取時間結構」、「應用場景與優缺點」三面向深入剖析其工作特性。

---

一、 循序存取（Sequential Access）

1. 代表媒介與實例：磁帶（Magnetic Tape）。
2. 工作原理：

• 資料係以連續的實體記錄（Physical Records）依序排列於儲存媒體上，記錄之間常以記錄間隙（Inter-Record Gap, IRG）區隔。
• 讀寫頭為固定位置，媒體（磁帶）透過馬達機械軸帶動進行單向或雙向線性移動。

3. 工作特性：

• 存取時間具強烈位置相關性：欲讀取第 $n$ 筆資料，必須先掠過前 $n-1$ 筆資料。若目前磁頭在起點，存取第 $n$ 筆資料的時間 $T_{\text{access}}$ 與 $n$ 成正比： $T_{\text{access}} \propto n$
• 隨機查找效率極低：不適合即時性（Real-time）或交談式（Interactive）查詢，倒帶（Rewind）與快轉（Fast Forward）均耗費龐大機械時間。
• 連續傳輸吞吐量高且成本低廉：連續讀寫大批資料時，磁帶移動速度穩定，能提供穩定的資料串流（Streaming）。
• 適用情境：巨量資料的離線封存（Cold Storage Archive）、災難復原備份（Backup）等批次處理作業。

---

二、 直接存取（Direct Access）

1. 代表媒介與實例：硬式磁碟機（Hard Disk Drive, HDD）或傳統光碟（Optical Disc）。
2. 工作原理：

• 儲存表面劃分為同心圓的「磁軌（Tracks）」與徑向分割的「磁區（Sectors）」，垂直堆疊的多片磁碟構成「磁柱（Cylinders）」。
• 每筆資料或資料區塊（Block）擁有唯一的實體硬體位址（Cylinder, Head, Sector, 即 CHS 模式）或邏輯區塊位址（Logical Block Addressing, LBA）。

3. 工作特性：

• 以區塊為單位直接跳躍定址：存取目標區塊時，無須線性掃描該區塊前的所有資料，磁頭臂可直接移至目標磁柱。
• 存取時間由三大機械延遲構成： $T_{\text{access}} = T_{\text{seek}} + T_{\text{latency}} + T_{\text{transfer}}$

核心觀念

本題考查作業系統（Operating Systems）之程序管理與並行控制（Concurrency Control）核心課題——**死結（Deadlock）**的基礎理論。

1. 死結定義：一組程序（Processes）處於相互永久等待事件（通常為釋放已被獨占之資源）的停滯狀態。
2. 死結之四大必要條件（Coffman Conditions）：1971 年由 Edward G. Coffman Jr. 等人提出，任何死結的發生必須同時滿足四個條件：互斥（Mutual Exclusion）、持有並等待（Hold and Wait）、不可搶先（No Preemption）以及循環等待（Circular Wait）。

---

解題方法

本題為標準的國家考試計算機原理申論題，作答應採「定義 $\to$ 實例 $\to$ 四大條件」三段式架構：

1. 定義界定：精確定義何謂死結，點出「一組程序」、「互相等待」、「無法推進執行」等關鍵要件。
2. 實例呈現：採用作業系統中經典之兩程序（$P_1, P_2$）爭奪兩不可共用資源（$R_1, R_2$）之資源分配衝突模型，具體展示死結形成的因果時序。
3. 四大必要條件論述：依序寫出四項條件之英文專有名詞、定義內涵與在死結形成中所扮演的角色。

---

選項分析

本題為申論問答題，無選擇題選項。試題要求分列三項子要件：死結定義、實例說明、四個必要條件，作答時須各自獨立標號，層次分明以利閱卷委員逐項核分。

---

解題技巧

1. 記憶口訣： 四大條件可記為「互、持、不、循」：

• 互：互斥（Mutual Exclusion）
• 持：持有並等待（Hold and Wait）
• 不：不可搶先／不可剝奪（No Preemption）
• 循：循環等待（Circular Wait）

2. 常見陷阱與評分關鍵：

• 「必要條件」非「充分條件」：當各資源只有單一單元（Single Instance）時，循環等待是死結的充分必要條件；但在資源擁有多單元（Multiple Instances）的系統中，即使出現循環等待亦不必然發生死結。題目問的是「必要條件」，強調死結存在時四者必同時成立。
• 名詞辨析：切勿將死結與「飢餓（Starvation，程序長期得不到資源但理論上可能解套）」或「活結（Livelock，程序狀態持續變更但無法取得實質進展）」混為一談。

---

【答案】

核心觀念

1. 基數排序法（Radix Sort）原理： 基數排序屬於非比較型排序演算法（Non-comparison sort）。實務與國考上最普遍採用的是由最低有效位向最高有效位排序的 LSD（Least Significant Digit） 方式。
2. 穩定排序（Stable Sort）之必要性： 每一回合針對單一位數（Digit）進行分桶時，底層必須採用穩定排序（通常使用先進先出的佇列 FIFO Queue 或計數排序 Counting Sort），以確保前一回合排好的相對順序在當前位數相同時不被破壞。
3. 複雜度分析：

• 時間複雜度：$O(d \cdot (n + r))$，其中 $n$ 為資料筆數（本題 $n = 10$），$d$ 為最大位數（本題 $d = 3$），$r$ 為基數（十進位 $r = 10$）。
• 空間複雜度：$O(n + r)$，需配置 $r$ 個分桶暫存資料。

---

解題方法

本題資料為十進位正整數，最大數值為 $945$（共 3 位數），因此排序共需進行 $3$ 回合（$d = 3$）。 位數不足 3 位者，高位以 $0$ 補齊：

• 原數列：$101, 023, 945, 712, 500, 009, 028, 654, 166, 111$

---

第一回合：依「個位數（$10^0$）」分配與收集

將各元素依個位數的值放入對應的桶子（Bucket 0 至 9），同桶內按原數列出現順序（FIFO）排列：

桶子編號	放入之數值（依先進先出順序）
0	$50\mathbf{0}$
1	$10\mathbf{1},\ 11\mathbf{1}$
2	$71\mathbf{2}$
3	$02\mathbf{3}$
4	$65\mathbf{4}$
5	$94\mathbf{5}$
6	$16\mathbf{6}$
7	（無）
8	$02\mathbf{8}$
9	$00\mathbf{9}$

• 依序由 Bucket 0 至 9 收集後結果： $500,\ 101,\ 111,\ 712,\ 23,\ 654,\ 945,\ 166,\ 28,\ 9$

---

第二回合：依「十位數（$10^1$）」分配與收集

根據第一回合產生的新順序，檢視十位數並放入對應桶子：

桶子編號	放入之數值（依先進先出順序）
0	$5\mathbf{0}0,\ 1\mathbf{0}1,\ 0\mathbf{0}9$

核心觀念

水桶排序（Bucket Sort）是一種**非比較型（或混合型）分散—收集（Scatter-Gather）**排序演算法，核心思想在於「空間換取時間」與「分而治之（Divide and Conquer）」。

1. 基本假設：輸入資料必須能映射至有限數量的區間內，且資料在該值域上需大致呈現均勻分佈（Uniform Distribution）。典型假設為輸入由隨機獨立且均勻分佈於區間 $[0, 1)$ 的實數構成。
2. 分桶機制：透過數值散列函數（Hash Function），將資料值域切分為若干個大小相等的子區間（即「水桶」），將元素分流至對應的水桶中。
3. 分群排序與串接：因資料均勻分佈，各水桶內分配到的元素量極少，桶內可搭配傳統排序（通常為插入排序 Insertion Sort）以常數時間完成排序，最後依水桶順序串接（Concatenate）輸出。
4. 穩定性（Stability）：只要分桶時維持先進先出（FIFO）順序，且桶內排序採用穩定演算法（如插入排序），水桶排序即為穩定排序（Stable Sort）。

---

解題方法

本題為經典申論題，作答應依序鋪陳「工作原理」、「演算法流程步驟」、「排序效率（含嚴謹複雜度推導）」。

一、 工作原理

水桶排序將排序程序拆解為「分割散列」、「局部排序」與「線性收集」三部曲：

1. 數值空間分割：若待排序陣列大小為 $n$，配置 $n$ 個有序的水桶（編號 $0$ 至 $n-1$）。
2. 元素映射分派：設定映射函數 $f(x) = \lfloor n \times x \rfloor$，將值域 $[0, 1)$ 等分為長度 $1/n$ 的 $n$ 個子區間，每個元素可於 $O(1)$ 時間內直接定位其所屬水桶。
3. 桶內獨立排序：由於各水桶彼此區間互斥且有序（若 $i < j$，則桶 $i$ 內的所有數值必定小於桶 $j$ 內的所有數值），只需對各桶內部進行局部排序，無須進行跨桶比較。
4. 依序串接輸出：各桶排序完畢後，由低索引桶至高索引桶依序巡訪，將內部節點串接即得全域排序結果。

---

二、 演算法流程

假設待排序陣列為 $A[0 \dots n-1]$，元素均滿足 $0 \le A[i] < 1$：

1. 初始化水桶（Create Buckets）： 建立一個大小為 $n$ 的指標陣列 $B[0 \dots n-1]$，每個位置初始化為空的鏈結串列（Linked List）或動態陣列。
2. 分散分派（Scatter Phase）： 依序讀取元素 $A[i]$（$i = 0$ 至 $n-1$）：

• 計算該元素應置入之水桶索引：$index = \lfloor n \times A[i] \rfloor$。
• 將 $A[i]$ 插入水桶鏈結串列 $B[index]$ 的尾端（保持插入順序）。

3. 桶內排序（Sort Phase）： 巡訪水桶陣列 $B[0 \dots n-1]$：

• 對每一個非空水桶 $B[j]$，調用插入排序（Insertion Sort）將其內部元素由小至大排序。

4. 串接合併（Gather Phase）： 依序由 $B[0]$ 到 $B[n-1]$ 取出排序好的元素，逐一覆寫回原陣列 $A$（或循序輸出至結果陣列）。

---

三、 排序效率分析

設輸入資料筆數為 $n$，配置水桶個數為 $k$（標準配置通常取 $k = n$）。

1. 時間複雜度（Time Complexity）

整體執行時間由四個部分相加組成： $T(n) = \Theta(k) + \Theta(n) + \sum_{i=0}^{k-1} T_{\text{sort}}(n_i) + \Theta(n)$ 其中 $n_i$ 代表分配至水桶 $i$ 的元素數量，滿足 $\sum_{i=0}^{k-1} n_i = n$；桶內採用插入排序時，$T_{\text{sort}}(n_i) = O(n_i^2)$。

• 最佳情況（Best Case）：$O(n)$
• 條件：輸入資料完全均勻分佈，每個水桶恰好只分配到 1 個元素（即所有 $n_i \le 1$）。
• 計算：各桶內排序耗時 $O(1)$，總耗時為分散 $\Theta(n)$ 加上收集 $\Theta(n)$，時間複雜度為 $O(n)$。

核心觀念

本題主要測驗物件導向程式語言（Java）的底層執行機制與語法特性，涵蓋以下核心觀念：

1. 物件參考與記憶體模型（Object Reference & Memory Model）：

• Java 的變數若宣告為類別型態（如 Name p1），其本質為儲存於堆疊區（Stack）的物件參考（Reference），指向實際配置於堆積區（Heap）的物件實體。
• 物件的指派運算（Assignment）僅複製參考位址，而非複製物件本體。

2. 傳值呼叫機制（Pass by Value）：

• Java 嚴格採用傳值呼叫。將物件參考傳入方法時，傳遞的是「參考位址的複本」。
• 透過該參考複本存取並修改物件成員變數（如 p.name = name）會實質改變堆積區中的物件狀態；但若對參數變數本身重新賦值（如 name = "Cindy"），僅改變方法內的區域變數，對呼叫端毫無影響。

3. 方法多載（Method Overloading）：

• 類別中定義了兩個同名方法 x2：x2(String) 與 x2(Name, String)，編譯器依據呼叫時傳入引數的型態與個數決定呼叫目標。

4. this 關鍵字與靜態方法（Static Method）差異：

• 靜態方法 x1 屬於類別，無隱式 this 參考，需直接藉由傳入的參數操作物件。
• 實體方法 x2 透過 this 指向當前觸發呼叫的物件實體。

5. 運算式求值順序（Argument Evaluation Order）：

• Java 規範引數之求值順序嚴格由左至右（Left-to-Right）。巢狀呼叫中，必須先求出子運算式的值（伴隨副作用），再將結果代入外層方法執行。

---

解題方法：執行過程詳細追蹤

為求精確追蹤，將堆積區（Heap）中先後建立之物件標記為 $\text{Obj}_A, \text{Obj}_B, \text{Obj}_C, \dots$。

階段一：物件初始化

Name p1 = new Name("Mary", 10);
Name p2 = new Name("Ann", 20);
Name p3 = new Name("Sara", 60);

• $\text{Obj}_A$：{name: "Mary", age: 10}，由參考變數 p1 指向。
• $\text{Obj}_B$：{name: "Ann", age: 20}，由參考變數 p2 指向。
• $\text{Obj}_C$：{name: "Sara", age: 60}，由參考變數 p3 指向。

---

階段二：執行 Name.x1(p2, p1);

• 呼叫靜態方法 x1(Name n1, Name n2)：
• 參數對應：n1 指向 $\text{Obj}_B$，n2 指向 $\text{Obj}_A$。
• 執行敘述：

1. n2.age = n1.age;：$\text{Obj}_A.\text{age} = \text{Obj}_B.\text{age} = 20$。
2. n1.name = n2.name;：$\text{Obj}_B.\text{name} = \text{Obj}_A.\text{name} = \text{"Mary"}$。

• 當前狀態：
• p1 $\rightarrow \text{Obj}_A$：{name: "Mary", age: 20}
• p2 $\rightarrow \text{Obj}_B$：{name: "Mary", age: 20}
• p3 $\rightarrow \text{Obj}_C$：{name: "Sara", age: 60}

---

階段三：執行 p2 = p3.x2("Jill");

• 呼叫實體方法 x2(String name)，由 p3（$\text{Obj}_C$）發動，傳入 "Jill"：

1. this 為 $\text{Obj}_C$。
2. Name p1 = new Name(this.name, 30);：

• this.name 當前為 "Sara"。
• 於 Heap 建立新物件 $\text{Obj}_D$：{name: "Sara", age: 30}。

3. this.name = name;：$\text{Obj}_C.\text{name}$ 更新為 "Jill"。
4. return p1;：回傳 $\text{Obj}_D$ 的參考。

• 回傳值指派給 p2，使 p2 改向指向 $\text{Obj}_D$（原 $\text{Obj}_B$ 失去 p2 之參照）。
• 當前狀態：
• p1 $\rightarrow \text{Obj}_A$：{name: "Mary", age: 20}
• p2 $\rightarrow \text{Obj}_D$：{name: "Sara", age: 30}
• p3 $\rightarrow \text{Obj}_C$：{name: "Jill", age: 60}

---