107 地方特考三等 電力工程 計算機概論 考古題詳解

核心觀念

本題考查計算機概論與資料結構中極具代表性的兩個基礎演算法典範：迭代（Iteration）​與遞迴（Recursion），重點包含：

1. 迴圈追蹤（Loop Tracing）與邊界條件：追蹤 while 迴圈執行過程中的變數狀態更新，特別是迴圈終止時控制變數的數值（避免 Off-by-one error）。
2. 迭代解法（Iteration Solution）的定義與特性：利用重複控制結構（如迴圈）與狀態變數累進求值。
3. 遞迴解法（Recursive Solution）的定義與要件：函式自我呼叫（Self-calling），必須包含終止條件（Base case）與遞迴關係式（Recursive step）。
4. 系統呼叫堆疊（Call Stack）與空間複雜度（Space Complexity）：遞迴呼叫時，作業系統為維護各層函式活動紀錄（Activation Record / Stack Frame）所耗用的記憶體空間評估。

解題方法

(一) 計算呼叫 $Factorial(6)$ 時，最後 $F$ 的值

本演算法採用 while 迴圈計算階乘，初始值為 $F \leftarrow 1$、$i \leftarrow 1$。 當傳入 $n = 6$ 時，迴圈每次判斷條件 $(i \leq 6)$，成立則依序執行 $F \leftarrow F \times i$ 與 $i \leftarrow i + 1$。

執行追蹤（Trace Table）如下：

• 初始狀態：$F = 1,\; i = 1$
• 第 1 次迴圈：$i = 1 \leq 6$ 成立 $\implies F = 1 \times 1 = 1,\; i = 2$
• 第 2 次迴圈：$i = 2 \leq 6$ 成立 $\implies F = 1 \times 2 = 2,\; i = 3$
• 第 3 次迴圈：$i = 3 \leq 6$ 成立 $\implies F = 2 \times 3 = 6,\; i = 4$
• 第 4 次迴圈：$i = 4 \leq 6$ 成立 $\implies F = 6 \times 4 = 24,\; i = 5$
• 第 5 次迴圈：$i = 5 \leq 6$ 成立 $\implies F = 24 \times 5 = 120,\; i = 6$
• 第 6 次迴圈：$i = 6 \leq 6$ 成立 $\implies F = 120 \times 6 = 720,\; i = 7$
• 終止判斷：$i = 7 \leq 6$ 不成立，跳出迴圈。

執行至 return F 時，$F$ 的值為 $720$（即 $6! = 720$）。

(二) 承上題，計算最後 $i$ 的值

由第 (一) 小題的追蹤歷程可知： 當 $i = 6$ 進入迴圈運算後，執行敘述 $i \leftarrow i + 1$，使 $i$ 遞增為 $7$。 接著回到迴圈開頭評估條件 $(i \leq 6)$，此時 $7 \leq 6$ 為偽（False），迴圈終止並跳出。 因此，當程式執行到 return F 時，$i$ 的值為 $7$。

(三) 何謂「iteration solution」（迭代解法）

迭代解法（Iteration Solution）​是指利用重複性控制結構（如 for、while、do-while 迴圈）來解決問題的方法。其主要特性如下：

1. 狀態累進更新：在演算法執行過程中，透過一組或多組狀態變數（如本題中的累乘器 $F$ 與計數器 $i$），在每次迴圈反覆運算中不斷更新數值，逐步逼近或計算出最終解答。
2. 依賴終止條件結束：每一次的執行都依賴明確的布林條件判斷式來決定是否繼續或跳出迴圈。
3. 記憶體空間效率佳：迭代通常在固定的變數空間內原地更新數值，不需額外建立系統呼叫堆疊，輔助空間複雜度通常為常數空間 $O(1)$。

(四) 何謂「recursive solution」（遞迴解法）

核心觀念

本題評量數值系統轉換、浮點數表示法及演算法邊界條件處理：

1. 基底小數轉換法（乘基取整法）：將十進位小數轉換為 $R$ 進位小數時，連續將純小數部分乘以基底 $R$（$R=2$ 或 $R=16$），每次相乘後取出其整數部分作為該位數的值，並保留剩餘的小數部分重複此步驟，直到小數部分為 $0$ 或達到所需精確度為止。取出的整數依先後順序由高位（小數點後第一位 $R^{-1}$）排列至低位。
2. 二進位有限小數與無限小數之條件：十進位有限小數能否精準表示為二進位有限小數，取決於其化為最簡分數後的分母質因數是否僅包含 $2$。若含有非 $2$ 的質因數（如 $0.3 = \frac{3}{10}$，分母含有因數 $5$），轉換為二進位必為無限循環小數。
3. IEEE-754 實數表示法之誤差來源：電腦記憶體位元數有限，IEEE-754 標準定義之單精度（32-bit，尾數含隱含位共 24 bits）與雙精度（64-bit，尾數含隱含位共 53 bits）僅能儲存有限長度的假數（Mantissa/Significand）。面對無限循環小數時，必須進行截斷或捨入（Rounding），進而產生表現誤差（Representation Error）。
4. 演算法終止條件（Termination Condition）之健全性：數值轉換演算法若僅以「小數部分為 $0$」作為終止條件，遇到無限小數時會引發無窮迴圈（Infinite Loop）。實務上必須加入「最大精度位數限制」或「循環狀態偵測」。

解題方法

(一) 將十進位小數 $0.6875$ 轉換為二進位小數

採用「乘 2 取整法」連續乘以 2，分離整數與小數部分：

1. $0.6875 \times 2 = 1.375$ $\rightarrow$ 整數部分為 $1$，剩餘小數部分為 $0.375$
2. $0.375 \times 2 = 0.75$ $\rightarrow$ 整數部分為 $0$，剩餘小數部分為 $0.75$
3. $0.75 \times 2 = 1.5$ $\rightarrow$ 整數部分為 $1$，剩餘小數部分為 $0.5$
4. $0.5 \times 2 = 1.0$ $\rightarrow$ 整數部分為 $1$，剩餘小數部分為 $0.0$（小數部分為 0，結束）

轉換過程示意圖：

 0.6875
 × 2
 ────────
 1.3750 ───> 取出整數 1 (小數第 1 位，權值 2^-1)
 0.3750
 × 2
 ────────
 0.7500 ───> 取出整數 0 (小數第 2 位，權值 2^-2)
 0.7500
 × 2
 ────────
 1.5000 ───> 取出整數 1 (小數第 3 位，權值 2^-3)
 0.5000
 × 2
 ────────
 1.0000 ───> 取出整數 1 (小數第 4 位，權值 2^-4，小數為 0 結束)

依序由上而下讀取整數部分，得轉換結果為 $0.1011_{(2)}$。

(二) 將十進位小數 $0.3$ 轉換為二進位小數與遭遇之困難

採用「乘 2 取整法」連續乘以 2：

1. $0.3 \times 2 = 0.6$ $\rightarrow$ 取出整數 $0$，剩餘小數 $0.6$
2. $0.6 \times 2 = 1.2$ $\rightarrow$ 取出整數 $1$，剩餘小數 $0.2$
3. $0.2 \times 2 = 0.4$ $\rightarrow$ 取出整數 $0$，剩餘小數 $0.4$
4. $0.4 \times 2 = 0.8$ $\rightarrow$ 取出整數 $0$，剩餘小數 $0.8$
5. $0.8 \times 2 = 1.6$ $\rightarrow$ 取出整數 $1$，剩餘小數 $0.6$（此處小數 $0.6$ 重複出現，進入循環）
6. $0.6 \times 2 = 1.2$ $\rightarrow$ 取出整數 $1$，剩餘小數 $0.2$（開始重複循環節 $0110$）

轉換過程示意圖：

 0.3
 × 2
 ─────
 0.6 ───> 取出整數 0 (2^-1)
 0.6
 × 2
 ─────
 1.2 ───> 取出整數 1 (2^-2) <──┐
 0.2 │
 × 2 │
 ───── │
 0.4 ───> 取出整數 0 (2^-3) │ 循環節：0110
 0.4 │
 × 2 │
 ───── │
 0.8 ───> 取出整數 0 (2^-4) │
 0.8 │
 × 2 │
 ───── │
 1.6 ───> 取出整數 1 (2^-5) │
 0.6 │
 × 2 │
 ───── │
 1.2 ───> 取出整數 1 (2^-6) ───┘ (小數 0.2 重複，進入無限循環)

結果為無限循環小數：$0.01001100110011\dots_{(2)} = 0.0\overline{0110}_{(2)}$。

發生的困難：

1. 小數部分永遠無法等於 0：因為 $0.3 = \frac{3}{10}$ 化為最簡分數後分母包含質因數 $5$，無法表示為有限項的 $2^{-k}$ 總和，因此二進位轉換永不終止。

核心觀念

本題測驗多媒體資料處理中標準靜態影像壓縮協定 JPEG（Joint Photographic Experts Group） 基準循序模式（Baseline Sequential Mode）的處理管線架構與運算原理：

1. 空間分割（Block Preparation）：將影像空間域像素分割為固定大小的微小正方形子區塊，以利捕捉局部空間相關性並降低二維轉換的運算複雜度。
2. 離散餘弦轉換（Discrete Cosine Transform, DCT）：將影像從「空間域（Spatial Domain）」轉換至「頻率域（Frequency Domain）」，利用能量集中特性（Energy Compaction），將能量匯聚於少數低頻係數。
3. 量化（Quantization）：結合人類視覺系統（Human Visual System, HVS）對高頻不敏感的生理特性，進行非均勻有損壓縮，為 JPEG 壓縮管線中唯一造成失真（Lossy）與決定壓縮比率的核心步驟。
4. 無失真熵編碼（Lossless Compression / Entropy Coding）：以 Zig-zag 掃描重新排列量化係數，並結合差分編碼（DPCM，用於 DC 係數）、行程長度編碼（Run-Length Encoding, RLE，用於 AC 係數）與霍夫曼編碼（Huffman Coding），在不流失任何現有資訊的條件下消除統計編碼冗餘。

解題方法

(一) 圖像區塊「Blocked Image」的像素數量

• 切入點：JPEG 演算法的基礎設計單元規範。
• 解析： 在標準 JPEG 演算法中，輸入的每個顏色分量（如 YCbCr 中的各通道）會先被分割為 $8 \times 8$ 的非重疊矩陣區塊（Pixel Block）。 因此，每一個較小圖像區塊包含的像素數量為： $8 \times 8 = 64\text{ 個像素}$

(二) DCT 的英文全名

• 切入點：正交頻譜轉換英文專有名詞。
• 解析： DCT 的英文全名為 Discrete Cosine Transform（繁體中文稱為「離散餘弦轉換」）。

(三) 第三步驟 Lossless Compression 中「Lossless」的意思

• 切入點：資訊理論中壓縮可逆性之定義。
• 解析： 「Lossless」即為無失真（或無損）。其意涵為：資料經過壓縮與解壓縮（還原）後，解碼還原的資料與壓縮前的輸入資料完全一致，沒有遺失任何位元或資訊。 在 JPEG 第三步驟中，此階段負責將量化後產生的整數矩陣進行熵編碼（Entropy Coding，通常為 Huffman Coding 或 Arithmetic Coding），此編碼與解碼過程完全可逆（Reversible），解碼時能 $100\%$ 還原量化後的整數係數。

(四) JPEG 壓縮比率可大可小的理由

• 切入點：量化矩陣與品質因數（Quality Factor）的調節機制。
• 解析： JPEG 的壓縮比率可由使用者自由調節，其關鍵原因在於量化（Quantization）階段的量化步階（Step Size）可以依需求縮放調整：

1. JPEG 透過品質因數（Quality Factor, $Q$）​來縮放量化表（Quantization Table）中的各項權重係數。

核心觀念 本題評量作業系統（Operating System, OS）的基礎架構與核心模組運作機制，主要涵蓋下列核心觀念：

1. 作業系統雙層架構：Kernel（核心，特權模式執行、常駐記憶體）與 Shell（外殼，使用者空間執行之命令解譯介面）之分工與溝通（透過 System Call）。
2. 使用者介面型態：User Interface 包含命令列介面（CLI）與圖形化使用者介面（GUI）。
3. 工作與行程之差異：Job（靜態/批次提交之任務單位，由長程排程器管理）與 Process（動態/載入記憶體執行之程式實體，擁有獨立 PCB，由短程排程器管理）之生命週期與資源層次。
4. 虛擬記憶體與分頁機制：Paging 系統下 Page Table 之 Valid/Invalid bit 狀態檢測、Page Fault（缺頁）中斷之觸發條件與作業系統中斷處理流程（Interrupt Service Routine, ISR）。

解題方法 針對題目所列五個子題，依作業系統標準理論架構逐一精準定義並對比核心要點：

• 第(一)小題（Kernel）：從「地位與常駐性」、「核心功能（硬體資源管理與抽象化）」以及「運作模式（Kernel Mode / 特權等級）」三個構面給予完整定義。
• 第(二)小題（Shell）：定位為「使用者與核心間的橋樑（命令直譯器）」，說明其接收指令、語法解析、透過 System Call 請求 Kernel 執行並回傳結果之運作流程。
• 第(三)小題（GUI）：寫出國際通用的標準英文全名，並確保拼字完全正確。
• 第(四)小題（Process vs. Job）：從「概念層次（靜態任務 vs. 動態執行）」、「存放位置與生命週期」、「排程器管理層次（Long-term vs. Short-term）」三個關鍵維度列表或條列對比。
• 第(五)小題（Page Fault Interrupt）：明確點出「觸發時機（存取未在實體記憶體中的分頁）」、「硬體偵測（Valid bit = 0）」以及「作業系統的六步驟處理流程（Trap $\to$ 合法性檢查 $\to$ 尋找或置換 Frame $\to$ 磁碟 I/O 讀取 $\to$ 更新分頁表 $\to$ 指令重啟）」。

選項分析 本題為申論問答題，非選擇題，故無個別選項之對錯分析。評分焦點在於名詞定義的完整性、專業術語的使用精準度，以及系統運作流程是否具備邏輯連貫性。

解題技巧

1. 名詞簡稱之英文大小寫與拼寫：GUI 必須寫成標準名詞 Graphical User Interface，避免拼錯或誤寫為 Graphic 或 Interphase。
2. 區別 Job 與 Process 的口訣：

• 「Job 偏靜態、在硬碟、屬使用者端視角、歸長程排程（Job Scheduler）」。
• 「Process 偏動態、在記憶體、屬系統資源分配視角、歸短程排程（CPU Scheduler）」。

3. Page Fault 的作答關鍵字：必須包含「虛擬記憶體（Virtual Memory）」、「分頁表（Page Table）」、「無效位元（Invalid bit）」、「硬體觸發 Trap」以及「自磁碟載入至實體框架（Frame）並重新執行指令」。

【答案】

(一) 作業系統的 Kernel（核心） Kernel 是作業系統中最核心且最重要的常駐程式（Resident Program）。其主要特徵與功能如下：

1. 系統心臟與常駐性：在電腦開機啟動（Booting）時即被載入至主記憶體中，並在系統運作期間全程常駐於記憶體內。
2. 硬體資源抽象與管理：直接與底層硬體溝通，負責管理四大核心資源：處理程序管理（Process Management）、記憶體管理（Memory Management）、檔案系統（File System）及 I/O 設備管理（Device Management）。
3. 特權模式與安全屏障：運行於硬體的特權模式（Kernel Mode / Supervisor Mode），提供系統呼叫介面（System Call Interface）供應用程式請求底層服務，防止使用者程式直接破壞硬體或其他行程。