107 調查局特考三等 電子科學組 計算機概論 考古題詳解

核心觀念

本題評量計算機概論中「數值系統與進位制轉換」（Number Systems and Base Conversion）的基本定義與互轉運算：

1. 位置記數法（Positional Numeral System）之權值展開： 基數為 $R$ 的數值，小數點以左第 $i$ 位（$i \ge 0$）的權值為 $R^i$；小數點以右第 $j$ 位（$j \ge 1$）的權值為 $R^{-j}$。任意進位數轉十進位皆可透過權值展開多項式求得： $N_{10} = \sum_{k} d_k \times R^k$
2. 以二進位為橋樑之快速轉換法（Binary Bridge Method）：

• 由於 $8 = 2^3$，故每一位八進位數字恰可一對一映射為 3 個二進位位元（bits）。
• 由於 $16 = 2^4$，故每一位十六進位數字恰可一對一映射為 4 個二進位位元（bits）。
• 八進位與十六進位互轉時，最標準且不易出錯的途徑為：$\text{Octal} \longleftrightarrow \text{Binary} \longleftrightarrow \text{Hexadecimal}$。

解題方法

(一) Octal 的意義

1. 定義與基數：Octal 即「八進位制」（Base-8 或 Radix-8），是以 $8$ 為基數的位置記數系統，計數規則為「逢 8 進一」。
2. 符號集合：採用 8 個阿拉伯數字符號表示數值，數碼集為 $\{0, 1, 2, 3, 4, 5, 6, 7\}$。
3. 數值權重：位置權值以 $8$ 的整數次方遞增或遞減，小數點以左權值依序為 $8^0, 8^1, 8^2, \dots$，小數點以右權值依序為 $8^{-1}, 8^{-2}, \dots$。
4. 計算機應用：因 $8 = 2^3$，每一位八進位數恰可精確對應 3 個二進位位元（bits），在早期計算機系統及 Unix/Linux 檔案權限設定（如 chmod 755）中廣泛作為精簡二進位長度的表示法。

(二) Hexadecimal 的意義

1. 定義與基數：Hexadecimal 即「十六進位制」（Base-16 或 Radix-16），是以 $16$ 為基數的位置記數系統，計數規則為「逢 16 進一」。
2. 符號集合：採用 16 個符號表示數值，包含數字 $0 \sim 9$ 以及 6 個英文字母 $\text{A} \sim \text{F}$（不分大小寫），其中 $\text{A}=10, \text{B}=11, \text{C}=12, \text{D}=13, \text{E}=14, \text{F}=15$。
3. 數值權重：位置權值以 $16$ 的整數次方遞增或遞減，小數點以左權值依序為 $16^0, 16^1, 16^2, \dots$，小數點以右權值依序為 $16^{-1}, 16^{-2}, \dots$。
4. 計算機應用：因 $16 = 2^4$，每一位十六進位數恰好對應 4 個二進位位元（即 1 個半字節 Nibble，兩位十六進位數即為 1 Byte）。現代計算機系統普遍使用十六進位表示記憶體實體位址（Memory Address）、網頁色碼（RGB HEX）以及機器碼資料傾印（Hex Dump）。

(三) 將八進位 $(4116)_8$ 換算為十進位

利用八進位的權值展開式直接計算： $(4116)_8 = 4 \times 8^3 + 1 \times 8^2 + 1 \times 8^1 + 6 \times 8^0$ 計算各項權值數值：

• $4 \times 8^3 = 4 \times 512 = 2048$
• $1 \times 8^2 = 1 \times 64 = 64$
• $1 \times 8^1 = 1 \times 8 = 8$
• $6 \times 8^0 = 6 \times 1 = 6$

加總求得十進位值： $2048 + 64 + 8 + 6 = 2126$

(四) 將八進位 $(6114)_8$ 換算為十六進位

採用題幹示意圖之「二進位橋樑法」：

1. Octal 轉 Binary（每 1 位八進位展開為 3 位二進位）：

• $6_8 = 110_2$
• $1_8 = 001_2$
• $1_8 = 001_2$
• $4_8 = 100_2$
• 合併為二進位：$(110001001100)_2$

2. Binary 轉 Hexadecimal（由右向左每 4 位劃分一組）：

• 第一組（最低位 4 bits）：$1100_2 = 12_{10} = \text{C}_{16}$

核心觀念

本題評量二元搜尋法（Binary Search）​的執行機制、中間索引計算、搜尋決策樹（Binary Decision Tree / Comparison Tree）之展開，以及成功搜尋時的平均比較回合數（Average Successful Search Length, ASL）。

1. 二元搜尋法基本原理： 二元搜尋法適用於已排序陣列。每一回合取目前搜尋範圍的中央索引 $mid$，比較目標值 $Target$ 與 $A[mid]$：

• 若 $Target = A[mid]$：搜尋成功，立即終止。
• 若 $Target < A[mid]$：目標若存在必在左半部，縮減範圍至 $[first, mid - 1]$。
• 若 $Target > A[mid]$：目標若存在必在右半部，縮減範圍至 $[mid + 1, last]$。

2. 中間索引計算公式： 當初值 $first = 0, last = 11$，題意給定第一次之 $mid = 5$，顯示其計算採向下取整（Floor）​的整數除法： $mid = \left\lfloor \frac{first + last}{2} \right\rfloor$
3. 二元決策樹結構： 二元搜尋各回合所檢驗的節點可建構為一棵二元搜尋樹（Binary Search Tree）。樹的深度（根節點為深度 1）即為找到該節點所需的「回合數」。
4. 平均成功搜尋回合數（Average Search Length, $ASL_{succ}$）： 當各元素被搜尋機率皆相等（即均為 $\frac{1}{N}$）時，平均回合數為所有元素被找到所需回合數的算術平均值： $ASL = \frac{1}{N} \sum_{i=1}^{k} (i \times N_i)$ 其中 $N_i$ 為第 $i$ 個回合所找到的元素個數。

解題方法與詳細推導

陣列長度 $N = 12$，內容為： $A[0:11] = [4, 7, 8, 10, 14, 21, 22, 36, 62, 77, 81, 91]$

(一) 計算 $mid$ 之公式

• 初值 $first = 0, last = 11$，其算術平均為 $\frac{0 + 11}{2} = 5.5$。
• 題目明確指出第一次之 $mid = 5$，說明運算過程捨棄小數點取整數，即向下取整（Floor division）。
• 公式為： $mid = \left\lfloor \frac{first + last}{2} \right\rfloor \quad \text{或寫為程式語言之整數除法：} \quad mid = (first + last) \text{ // } 2$

(二) 與 (三) 各回合決策樹推導

依上述公式逐步展開各回合搜尋的範圍與 $mid$：

1. 第 1 回合：

• 區間 $[0, 11]$： $mid = \left\lfloor \frac{0 + 11}{2} \right\rfloor = 5 \implies A[5] = 21$
• 第 1 回合找到的 Target：$21$（共 1 個）

2. 第 2 回合：

• 若 $Target < 21$，左子區間為 $[0, 4]$： $mid = \left\lfloor \frac{0 + 4}{2} \right\rfloor = 2 \implies A[2] = 8$
• 若 $Target > 21$，右子區間為 $[6, 11]$： $mid = \left\lfloor \frac{6 + 11}{2} \right\rfloor = 8 \implies A[8] = 62$
• 第 2 回合找到的 Target：$8, 62$（共 2 個，即第 (三) 小題答案）

3. 第 3 回合：

• 來自 $[0, 4]$ 之 $mid = 2$：
• 若小於 $8$，區間變為 $[0, 1]$： $mid = \left\lfloor \frac{0 + 1}{2} \right\rfloor = 0 \implies A[0] = 4$
• 若大於 $8$，區間變為 $[3, 4]$： $mid = \left\lfloor \frac{3 + 4}{2} \right\rfloor = 3 \implies A[3] = 10$
• 來自 $[6, 11]$ 之 $mid = 8$：
• 若小於 $62$，區間變為 $[6, 7]$： $mid = \left\lfloor \frac{6 + 7}{2} \right\rfloor = 6 \implies A[6] = 22$ （此即題幹所示之 Target=$22$）
• 若大於 $62$，區間變為 $[9, 11]$： $mid = \left\lfloor \frac{9 + 11}{2} \right\rfloor = 10 \implies A[10] = 81$

核心觀念

本題評量程式語言範型（Programming Paradigms）的分類定義及其核心機制，並檢驗計算機系統階層中「高階語言（High-Level Language）」與「低階語言（Low-Level Language）」的本質差異。

1. 程式語言範型分類：

• 程序導向語言（Procedural Language）：以演算法的步驟分解為導向，強調控制流程與記憶體狀態的變更。
• 物件導向語言（Object-Oriented Language）：以真實世界的實體抽象化為導向，將資料與方法封裝於物件，強調封裝、繼承與多型。
• 函數導向語言（Functional Language）：以數學上的 $\lambda$-演算（Lambda Calculus）為理論基礎，將運算視為純函數求值，強調不變性與無副作用。
• 宣告式語言（Declarative Language）：以「陳述問題本質（What）」而非「逐步演算法控制（How）」為導向，依賴內建邏輯推論引擎進行求解。

2. 抽象層次與硬體相依性：

• 低階語言：貼近硬體暫存器與記憶體實體位址，具備高度硬體相依性（Machine-dependent）。
• 高階語言：遠離底層硬體細節，語法貼近人類自然語言與數學符號，具備跨平台可攜性（Machine-independent）。

解題方法

原卷所附圖形為高階程式語言之四大範型分類架構圖，圖中依據「命令式（Imperative）」與「宣告式（Declarative）」兩大主軸，分別細分為：

1. Procedural（程序導向，以 C 為代表）
2. Object-Oriented（物件導向，以 C++ 為代表）
3. Functional（函數導向，以 LISP 為代表）
4. Declarative / Logic（邏輯宣告式，以 Prolog 為代表）

解題切入點應針對每種語言範型提供精確的學術定義、運作機制及代表特性；對於第五小題的比較題，則採用多維度（硬體相依性、可攜性、轉譯方式、執行效能、開發維護成本）對比架構，條理分明地展現兩者的本質差異。

選項分析

本題為申論問答題，非選擇題，故無個別選項之對錯分析。評分標準著重於各子題定義的精準度、核心專有名詞之掌握度，以及高低階語言比較面向的完整性。

解題技巧

1. 掌握四大範型的對稱性與核心關鍵字：

• Procedural：記住「由上而下（Top-Down）」、「程序／函式分解」、「狀態改變」。
• Object-Oriented：必寫四大支柱「封裝（Encapsulation）、繼承（Inheritance）、多型（Polymorphism）、抽象（Abstraction）」。
• Functional：必寫「$\lambda$-演算」、「純函數（Pure Functions）」、「無副作用（No Side Effects）」、「一等公民函數（First-Class Functions）」。
• Declarative：記住「What to do vs. How to do」、「事實（Facts）與規則（Rules）」、「推論引擎（Inference Engine）」。

2. 低階 vs. 高階比較表格化： 比較題切忌通篇散文，應列出明確指標（硬體相依性、可攜性、轉譯器、開發效率、執行效率），便於閱卷委員在短時間內核對得分要點。

【答案】

(一) Procedural Language（程序導向語言）

1. 定義： 程序導向語言屬於命令式語言（Imperative Language）的分支，其核心精神在於將複雜的計算任務由上而下（Top-Down）分解為一系列具備特定功能的程序（Procedures）、副程式（Subroutines）或函式（Functions）。
2. 核心特性：

• 步驟導向（Step-by-step Execution）：程式著重於描述「如何做（How to do）」，依序由控制結構（循序、選擇、重複）引導程式計數器的推進。
• 可變狀態與副作用（Mutable State & Side Effects）：運算過程依賴對記憶體變數的指派與修改，程式的執行本質即為狀態的不斷轉移。
• 模組化設計：透過引數列傳遞資料與取得回傳值，降低主程式複雜度，提升程式碼模組化程度。

(二) Object-Oriented Language（物件導向語言）

1. 定義： 物件導向語言將問題領域中的實體抽象化為「物件（Object）」，軟體系統由多個能相互發送訊息（Message Passing）並協同運作的獨立物件所組成。

核心觀念

本題評量資料壓縮（Data Compression）之基礎分類體系與經典演算法原理，涵蓋資訊理論、資料完整性及編碼機制：

1. 無失真壓縮（Lossless Compression）與失真壓縮（Lossy Compression）之分類本質：

• 無失真壓縮：基於夏農熵（Shannon Entropy）原理，壓縮過程完全可逆（Reversible），解壓縮還原之資料與原始資料在二進位層級上百分之百相同（Bit-for-bit identical）。主要應用於不可容許任何誤差的純文字（Text）、原始碼與執行檔程式（Programs）。
• 失真壓縮：利用人類感知生理學（視覺與聽覺之感知冗餘，如心理視覺與心理聲學模型）去除人眼或人耳不敏感的高頻細節，壓縮過程不可逆（Irreversible），但能以微小品質損失換取極高的壓縮比（Compression Ratio）。主要應用於影像（JPEG）、視訊（MPEG）與音訊（MP3）。

2. 字典式編碼（Dictionary-Based Encoding）：

• 核心思想是以「字典索引（Index）」代替「重複出現之字串模式（Substrings/Phrases）」。在編碼與解碼端動態或靜態建立字典，將已出現的字詞存入字典中，後續重複出現時僅輸出字典索引與新符號，代表演算法為 Lempel-Ziv 系列（LZ77、LZ78、LZW）。

解題方法與詳細解析

(一) 請說明 lossless methods 和 lossy methods 的差別。（5 分）

兩者主要差異體現在以下三項核心指標：

1. 可逆性與資料保真度（Reversibility & Data Fidelity）：

• Lossless methods（無失真壓縮法）：為完全可逆程序。解壓縮還原後之資料與壓縮前之原始資料完全一致，沒有任何資訊遺失。
• Lossy methods（失真壓縮法）：為不可逆程序。壓縮過程中主動捨棄人類感官不易察覺的次要資訊，解壓縮後僅能還原出與原始資料相似的近似內容，原始細節無法復原。

2. 壓縮率（Compression Ratio）：

• Lossless methods：受到資訊熵理論極限之限制，壓縮比相對較低，通常介於 $2:1$ 至 $3:1$ 之間。
• Lossy methods：因容許捨棄冗餘資訊，不受無失真熵極限限制，可達到極高的壓縮比，常見範圍可達 $10:1$ 至 $50:1$ 甚至更高。

3. 應用領域（Application Domains）：

• Lossless methods：應用於對資料精確度要求絕對零容錯之環境，如文字文件（Text）、電腦程式執行檔或原始碼（Programs）、資料庫數據、醫學診斷影像等。
• Lossy methods：應用於人類感官具備容錯能力的多媒體資料，如靜態照片（JPEG）、數位視訊（MPEG）、數位音樂（MP3）等。

(二) 為什麼 text 或 programs 通常都使用 lossless methods 而不使用 lossy methods？（5 分）

1. 二進位語意與指令之零容錯性（Zero-Tolerance for Errors）：

• 程式（Programs）：程式的機器碼由嚴密的運算碼（Opcode）、運算元、暫存器位址及記憶體偏移量所構成。若採用 lossy methods 導致即便只有 $1$ 個 bit 發生位元翻轉或遺失，就會引發語法錯誤（Syntax error）、記憶體區段錯誤（Segmentation fault）或邏輯失控，導致程式完全無法編譯或執行崩潰。
• 文字（Text）：自然語言具備嚴謹的文法與語義。文字中遺失或改變單一字元、標點符號或數值（例如合約金額數字變更、否定詞 missing），將徹底顛覆整份文件的法律效力與原始意涵。

2. 缺乏感知冗餘（Absence of Perceptual Redundancy）：

• 多媒體訊號之所以能容許失真，是因為人類眼耳神經存在視覺暫留與遮蔽效應；而電腦之中央處理器（CPU）解讀程式與文字時，是以數位邏輯閘進行逐位元的二進位嚴格判定，不存在任何主觀容錯或模糊推論空間。

因此，text 與 programs 必須採用 lossless methods，以確保解壓縮後資料維持 $100\%$ 精確完整性。

(三) 下圖是某種資料壓縮法的示意圖，請問它是屬於 Run-length、Huffman、Lempel Ziv、JPEG、MPEG、MP3 這 6 種中的那一種？（5 分）

• 特徵比對與判定： 若圖中呈現「a. Original Data」與「b. Compressed Data」之直接對比，顯示原始資料中連續出現相同、重複的符號序列（Runs），經壓縮處理後轉換為記錄該符號及其連續出現次數（Run-length）之精簡表示法（如「計數＋字元」或「標記旗標＋長度＋字元」）。
• 在題目給定的 6 種方法中，直接以重複長度計數取代連續相同資料者，即為 Run-length（遊程編碼）。