107 國安局特考三等 資訊組(選試英文) 計算機概論 考古題詳解

核心觀念

本題評量計算機概論中「數字系統（Number Systems）與進位制轉換」之基礎核心觀念：

1. 進位制（Positional Numeral System）基本定義：以基底（Base 或 Radix）為核心，包含數字符號集合（Digits）、進位規則（逢 $R$ 進一）與位值權重展開式（$N = \sum d_i \times R^i$）。
2. 八進位（Octal）與十六進位（Hexadecimal）的特性：

• 八進位基底為 $8 = 2^3$，每一位八進位數字等價於 $3$ 個二進位位元（bits）。
• 十六進位基底為 $16 = 2^4$，每一位十六進位數字等價於 $4$ 個二進位位元（bits）。

3. 快速轉換橋樑（以二進位為中介）：

• 八進位轉十六進位時，標準且快速的方法是先將八進位各數位展開為 $3$ 位二進位，再以小數點為基準，向左、向右每 $4$ 位分為一組轉換為十六進位。

4. 小數點位元分組補零規則：

• 整數部分：從小數點由右向左每 $4$ 位分組，最高位（最左端）不足 $4$ 位時向左補 $0$。
• 小數部分：從小數點由左向右每 $4$ 位分組，最低位（最右端）不足 $4$ 位時向右補 $0$。

解題方法

(一) 請問 Octal 意義為何？

說明與定義：

1. 名稱與基底：Octal 即「八進位制」（Base-8 或 Radix-8），是以 $8$ 為基底的位值記數系統。
2. 符號集合與進位規則：使用 $0, 1, 2, 3, 4, 5, 6, 7$ 共 $8$ 個阿拉伯數字作為數字符號，運算規則為「逢八進一」。
3. 位值權重：任意八進位數值的大小依其所在數位決定，整數部分由小數點向左第 $i$ 位（$i = 0, 1, 2, \dots$）之權重為 $8^i$；小數部分由小數點向右第 $j$ 位（$j = 1, 2, \dots$）之權重為 $8^{-j}$。
4. 計算機應用意義：因 $8 = 2^3$，計算機中每 $1$ 個八進位數字剛好對應 $3$ 個二進位位元（bits），常作為精簡表示二進位資料的輔助工具（例如 Unix/Linux 檔案存取權限標記）。

(二) 請問 Hexadecimal 意義為何？

說明與定義：

1. 名稱與基底：Hexadecimal 即「十六進位制」（Base-16 或 Radix-16），是以 $16$ 為基底的位值記數系統。
2. 符號集合與進位規則：使用 $16$ 個符號，包含阿拉伯數字 $0 \sim 9$ 以及英文字母 $\text{A} \sim \text{F}$（不分大小寫），分別代表十進位的數值 $10, 11, 12, 13, 14, 15$。其運算規則為「逢十六進一」。
3. 位值權重：整數部分由小數點向左第 $i$ 位權重為 $16^i$；小數部分由小數點向右第 $j$ 位權重為 $16^{-j}$。
4. 計算機應用意義：因 $16 = 2^4$，每 $1$ 個十六進位數字恰好對應 $4$ 個二進位位元（即 $1$ 個半字節 Nibble，$2$ 個十六進位數剛好為 $1$ 個 Byte），廣泛應用於表示記憶體位址、機器語言指令、網路 MAC/IPv6 位址及色碼表示（RGB）。

(三) 此例中 Octal 中的 $4116$，換算成十進位，其值為何？

推導步驟： 將八進位整數 $(4116)_8$ 依位值權重展開為十進位： $(4116)_8 = 4 \times 8^3 + 1 \times 8^2 + 1 \times 8^1 + 6 \times 8^0$ 各項數值計算： $4 \times 512 = 2048$ $1 \times 64 = 64$ $1 \times 8 = 8$ $6 \times 1 = 6$ 各項累加： $2048 + 64 + 8 + 6 = 2126$ 因此，$(4116)_8$ 換算成十進位之值為 $2126$。

(四) 此例如果將 Octal 中的 $4116$ 改為 $6114$，請問 Hexadecimal 中的 $84E$，會改為何值？

推導步驟： 原題目示意圖之原理是藉由二進位作為中介轉換橋樑（$1$ 位八進位轉 $3$ 位二進位，再由 $4$ 位二進位轉 $1$ 位十六進位）。

1. 八進位轉換為二進位： 將 $(6114)_8$ 的每一位數轉為 $3$ 位二進位：

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

2. 二進位重新分組為十六進位： 自最低位（最右側）向左每 $4$ 位分為一組： $\underbrace{1100}_{\text{高位}} \quad \underbrace{0100}_{\text{中位}} \quad \underbrace{1100}_{\text{低位}}$ 轉換各組為十六進位數：

• $(1100)_2 = 12_{10} = \text{C}_{16}$
• $(0100)_2 = 4_{10} = 4_{16}$
• $(1100)_2 = 12_{10} = \text{C}_{16}$

合併各組得 Hexadecimal 值為 $\text{C}4\text{C}$（或表示為 $\text{C}4\text{C}_{16}$）。

核心觀念

本題評量二元搜尋法（Binary Search）​的演算法運作機制、搜尋樹（Decision Tree）結構推演與平均比較次數（Average Number of Comparisons）的計算。

1. 二元搜尋法基本原理： 在已由小到大排序的陣列 $A[0:n-1]$ 中，給定搜尋範圍的左右邊界指標 $first$ 與 $last$。每一回合（Round）取中間位置 $mid$，並比較目標值 $Target$ 與 $A[mid]$：

• 若 $Target = A[mid]$：搜尋成功，找到目標位置。
• 若 $Target < A[mid]$：目標位於左半段，更新右邊界 $last \leftarrow mid - 1$。
• 若 $Target > A[mid]$：目標位於右半段，更新左邊界 $first \leftarrow mid + 1$。

2. 中間索引計算公式： 採用無條件捨去（Floor）的整數除法： $mid = \lfloor \frac{first + last}{2} \rfloor$
3. 二元搜尋決策樹（Decision Tree）： 將二元搜尋的每一次比較節點繪製為二元樹，第 $k$ 回合找到的節點即為該樹深度的第 $k$ 層節點。
4. 平均搜尋回合數（平均成功比較次數）： 若各元素被尋找的機率相等（均勻分佈），平均回合數為各元素找到所需回合數的期望值： $E = \sum_{i=0}^{n-1} P(A[i]) \times \text{回合數}(A[i]) = \frac{1}{n} \sum_{i=0}^{n-1} \text{回合數}(A[i])$

解題方法

給定已排序陣列： $A[0:11] = [4, 7, 8, 10, 14, 21, 22, 36, 62, 77, 81, 91]$

(一) 計算 $mid$ 的公式

初始狀態 $first = 0$、$last = 11$。 依據整數除法（無條件捨去小數）： $mid = \lfloor \frac{first + last}{2} \rfloor$ 代入數值： $mid = \lfloor \frac{0 + 11}{2} \rfloor = \lfloor 5.5 \rfloor = 5$ 故求出 $5$ 的公式為 $mid = \lfloor \frac{first + last}{2} \rfloor$（亦可表示為整數除法 $(first + last) \text{ div } 2$ 或程式語言中的 (first + last) / 2）。

(二) 與 (三) 各回合搜尋樹展開與 Target 值分析

依二元搜尋規則逐層推導搜尋決策樹：

• 第 1 回合：

• 區間 $[0, 11]$：$mid = \lfloor \frac{0 + 11}{2} \rfloor = 5$，$A[5] = 21$。

• 第 1 回合找到的 Target：$21$。

• 第 2 回合：

• 左子區間 $[0, 4]$：$mid = \lfloor \frac{0 + 4}{2} \rfloor = 2$，$A[2] = 8$。

• 右子區間 $[6, 11]$：$mid = \lfloor \frac{6 + 11}{2} \rfloor = 8$，$A[8] = 62$。

• 第 2 回合找到的所有 Target 值：$8, 62$。此即第 (三) 小題答案。

• 第 3 回合：

• 由區間 $[0, 4]$（$mid=2$）分裂：

• 左子區間 $[0, 1]$：$mid = \lfloor \frac{0 + 1}{2} \rfloor = 0$，$A[0] = 4$。

• 右子區間 $[3, 4]$：$mid = \lfloor \frac{3 + 4}{2} \rfloor = 3$，$A[3] = 10$。

• 由區間 $[6, 11]$（$mid=8$）分裂：

• 左子區間 $[6, 7]$：$mid = \lfloor \frac{6 + 7}{2} \rfloor = 6$，$A[6] = 22$（題目所提範例）。

• 右子區間 $[9, 11]$：$mid = \lfloor \frac{9 + 11}{2} \rfloor = 10$，$A[10] = 81$。

• 第 3 回合找到的所有 Target 值為：$4, 10, 22, 81$。

核心觀念 本題旨在測驗計算機概論中「程式語言分類（Programming Paradigms）」與「語言抽象層次（Levels of Abstraction）」的基礎理論：

1. 程式設計典範（Programming Paradigms）：

• 程序導向（Procedural）：屬於指令式語言（Imperative），以副程式／程序（Subroutine/Procedure）為基礎，依循演算法逐步改變記憶體狀態。
• 物件導向（Object-Oriented）：以物件（Object）為核心，將資料（屬性）與方法（操作）封裝結合，強調抽象、封裝、繼承與多型。
• 函數型（Functional）：基於 $\lambda$ 演算（Lambda Calculus），將運算視為數學函數求值，強調函數為一等公民（First-Class Citizens）與避免副作用（Side Effects）。
• 宣告型／邏輯型（Declarative/Logic）：以數理邏輯為根基，關注「做什麼（What to do）」而非「如何做（How to do）」，依賴推論引擎進行求解。

2. 抽象層次（Abstraction Levels）：

• 高階語言（High-Level Language）與低階語言（Low-Level Language，包含機器語言與組合語言）在硬體相依性、可攜性、轉譯方式及語意抽象上的本質差異。

解題方法

1. 整體架構：本題屬於標準的觀念問答題，各小題均佔 5 分。答題切入點應精準涵蓋「核心定義」、「核心運作機制／關鍵特性」與「代表範例／語言哲學」。
2. 小題開展脈絡：

• (一) 至 (四) 題：依循「典範定義 $\rightarrow$ 關鍵技術特徵 $\rightarrow$ 執行概念」的架構作答，嚴格區分 Imperative（Procedural、OO）與 Declarative（Functional、Logic）的根本差異。
• (五) 題：採用維度對比法（硬體相依性、抽象化程度、可攜性、轉譯機制、開發維護難度與執行效能），並佐以對照表呈現，結構分明且利於閱卷給分。

選項分析 本題為申論問答題，無選擇題選項。依據試卷所給之分類圖形與子題，逐項深度剖析如下：

• 題目圖形架構分析：原卷附圖為經典計算機科學教科書中的程式語言四大典範分類體系。高階語言主要分為四大類：
• Procedural Language（以 C 為代表）
• Object-Oriented Language（以 C++ 為代表）
• Functional Language（以 LISP 為代表）
• Declarative Language（以 Prolog 為代表，特指邏輯宣告型）
• 各小題作答切入重點：
• 第 (一) 題（Procedural）：強調以程序（Procedure/Function）為核心模組，採取由上而下（Top-Down）的結構化設計，著重敘述指令的先後順序與狀態修改。
• 第 (二) 題（Object-Oriented）：必須明確點出「物件＝資料（狀態）＋方法（行為）」，並列出封裝（Encapsulation）、繼承（Inheritance）、多型（Polymorphism）三大核心支柱。
• 第 (三) 題（Functional）：強調純函數（Pure Function）、不可變性（Immutability）、無副作用，以及函數具備一等公民身分（可作為引數傳遞、回傳值返回），以遞迴取代傳統迴圈。
• 第 (四) 題（Declarative）：區別於指令式語言的「How」，宣告式語言僅定義「What」。以 Prolog 為例，是透過事實（Facts）與規則（Rules）建構知識庫，透過合一（Unification）與回溯（Backtracking）推導目標。
• 第 (五) 題（高階 vs. 低階）：必須區分低階語言包含機器語言（0 與 1 二進位碼）與組合語言（助記碼），並從「硬體相依度」、「可讀性與開發效率」、「可攜性」、「編譯／組譯轉換需求」等維度完整比較。

解題技巧

1. 典範區隔口訣（How vs. What）：

• 指令式（Procedural, OO）：告訴電腦「一步一步怎麼做（How to do it）」。
• 宣告式（Functional, Declarative/Logic）：告訴電腦「問題是什麼、規則是什麼（What is wanted / What is true）」。

2. 常見名詞混淆陷阱：

• 陷阱一：誤將「Functional Language」解釋為「有寫 function 的語言」。C 語言主要建構單元也是 function，但 C 屬於 Procedural；Functional 語言的核心是「數學意義上的映射、無副作用、一等公民函數」。
• 陷阱二：誤將「Declarative Language」解讀為「有變數宣告（variable declaration）的語言」。Declarative 的宣告是指「宣告邏輯關係與目標條件」，而非記憶體型態宣告。

3. 對比題高分原則：解答高階與低階語言差異時，切忌僅以單一長段落敘述；以條列或表格化維度對比，能最快速凸顯知識點的完整度。

【答案】

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

1. 定義： 程序導向語言是指令式語言（Imperative language）的一種主要典範，以「程序（Procedure）」、「函式（Function）」或「副程式（Subroutine）」作為程式模組化的核心基本單元。
2. 核心特徵：

核心觀念

本題評量計算機科學中「資料壓縮（Data Compression）」的核心分類與演算法機制，涵蓋以下關鍵定義與理論：

1. 壓縮分類與資訊理論基礎：

• 無失真壓縮（Lossless Compression）：壓縮後資料解壓縮可 $100\%$ 還原為原始資料，不遺失任何位元資訊（熵不變）。適用於對精確度要求嚴格、容錯率為零的資料（如程式碼、文字）。
• 失真壓縮（Lossy Compression）：利用人類感知系統（視覺的心理視覺模型、聽覺的心理聲學模型）的生理極限，去除人耳或肉眼不易察覺的「感知冗餘（Perceptual Redundancy）」，解壓縮後資料與原始資料存在差異，但可獲得極高的壓縮比。

2. 六大壓縮方法特徵：

• Run-length Encoding (RLE)：利用連續重複出現之相同字元（Run），記錄「符號＋長度計數」以達到縮減。
• Huffman Coding：統計字元出現頻率，利用二元樹（Huffman Tree）建構「變動長度前綴碼（Variable-Length Prefix Code）」，頻率高者賦予短碼、頻率低者賦予長碼。
• Lempel Ziv (LZ 系列，如 LZ77, LZ78, LZW)：屬於字典編碼（Dictionary-based Encoding），在編碼過程中動態建立字串字典，利用字典中的索引值（Index/Pointer）取代重複出現的子字串。
• JPEG / MPEG / MP3：結合離散餘弦轉換（DCT）、量化（Quantization）、運動補償（Motion Compensation）及心理聲學模型之失真壓縮技術。

解題方法與各小題詳解

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

兩者的根本差異在於還原資料的精確性與資訊是否可逆，具體比較如下：

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

主要原因在於文字與程式對資料完整性具有「零容錯度（Zero-Tolerance）」的絕對要求：

1. 程式（Programs）的執行敏感性：

• 程式由嚴謹的機器指令（Machine Instructions）、記憶體位址、暫存器配置及運算元構成。
• 若使用失真壓縮導致任何單一「位元翻轉（Bit Flip）」或遺失，將造成作業系統解碼出無效指令（Illegal Opcode）、指標錯誤懸空（Dangling Pointer）或記憶體區段錯誤（Segmentation Fault），導致程式直接崩潰（Crash）無法執行。

2. 文字（Text）的語法與語意完整性：

• 原始碼、文字或法律文件依賴精確字元傳遞語意。遺失一個關鍵字元（例如程式碼中遺漏分號 ;、數值改變、引號不對稱），將引發編譯失敗（Compile Error）或產生完全錯誤的邏輯行為。

3. 缺乏感官平滑機制：

• 多媒體資料可依靠人腦的感官補償（如影像相鄰像素色彩些微偏移肉眼無法辨別）；但編譯器、組譯器與直譯器屬於離散邏輯系統，不存在任何主觀容錯空間，因此必須使用 lossless methods。

(三) 判定某種資料壓縮法示意圖之類別（5 分）

• 所屬方法：Run-length（或稱游程編碼，Run-length Encoding）。
• 判定依據：
• 圖中原始資料（Original Data）呈現連續重複出現的相同符號/字元序列（例如重複的位元群或同一字元的連續區段）；