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

核心觀念

1. 進位制與位置記數法（Positional Numeral System）：

• 數值表示法以基底（Base 或 Radix，$r$）為核心。任一數值皆可按位置權重展開為多項式：數值 $=\sum d_i \cdot r^i$。
• 八進位（Octal, $r=8$）：採用 $0, 1, 2, 3, 4, 5, 6, 7$ 共 8 個符號，逢八進一，各數位權重由小數點向左依序為 $8^0, 8^1, 8^2, \dots$；向右依序為 $8^{-1}, 8^{-2}, \dots$。
• 十六進位（Hexadecimal, $r=16$）：採用 $0 \sim 9$ 與 $\text{A} \sim \text{F}$ 共 16 個符號（$\text{A} \sim \text{F}$ 分別代表十進位的 $10 \sim 15$），逢十六進一，各數位權重由小數點向左依序為 $16^0, 16^1, 16^2, \dots$；向右依序為 $16^{-1}, 16^{-2}, \dots$。

2. 以二進位為中介之轉換原理：

• 因 $8 = 2^3$，每一位八進位數字恰可精確對應 $3$ 位二進位數字（$3\text{ bits}$）。
• 因 $16 = 2^4$，每一位十六進位數字恰可精確對應 $4$ 位二進位數字（$4\text{ bits}$，即 $1\text{ nibble}$）。
• 八進位與十六進位之間的轉換，最有效且不易出錯的方法是以二進位作為中介橋樑進行位元展開與重新分組。

3. 小數點對齊分組原則：

• 重組二進位位元串時，必須以「小數點（Radix Point）」為基準點向兩側分組：
• 整數部分：從小數點由右向左每 4 位一組，最高位不足 4 位時於最左側補 $0$。
• 小數部分：從小數點由左向右每 4 位一組，最低位不足 4 位時於最右側補 $0$。

解題方法與推導

(一) Octal 意義為何？

• 定義與基底：Octal 即「八進位制」（Base-8），基底為 8。
• 使用符號與進位規則：使用 $0, 1, 2, 3, 4, 5, 6, 7$ 共 8 個數字符號，逢八進一。數值大小依位置記數法決定，整數由右至左權重為 $8^0, 8^1, 8^2, \dots$。
• 計算機科學中的意涵：由於 $8 = 2^3$，每一位八進位數字恰對應 3 個二進位位元（bits）。在早期計算機系統（如 PDP 系列大型/迷你主機）與 Unix 系統的檔案權限表示法（如 chmod 755）中，常利用八進位精簡表示二進位資料。

(二) Hexadecimal 意義為何？

• 定義與基底：Hexadecimal 即「十六進位制」（Base-16），基底為 16。
• 使用符號與進位規則：使用 16 個符號，包含阿拉伯數字 $0 \sim 9$ 以及英文字母 $\text{A, B, C, D, E, F}$（分別代表十進位數值 $10, 11, 12, 13, 14, 15$），逢十六進一。
• 計算機科學中的意涵：由於 $16 = 2^4$，每一位十六進位數字恰好對應 4 個二進位位元（半位元組，Nibble）。現代計算機體系以 8 位元（1 Byte）為基本定址單位，2 位十六進位數即可完整表達 1 個 Byte（$00_{16} \sim \text{FF}_{16}$），因此廣泛應用於記憶體位址、機械碼指令、色彩編碼（RGB）及網路 MAC/IPv6 位址等領域。

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

利用八進位位置權值展開多項式： $(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 中的 $84\text{E}$，會改為何值？

利用二進位作為中介進行轉換：

1. 八進位轉二進位（每一位八進位數拆解為 3 位二進位數）：

核心觀念

1. 二元搜尋法（Binary Search）： 適用於已排序陣列（Sorted Array）的高效搜尋演算法，採用分治法（Divide-and-Conquer）策略。每次藉由比對中央元素 $A[mid]$ 與目標值 $Target$，可將搜尋範圍縮減一半。
2. 中央索引公式： 在整數索引的陣列中，以搜尋範圍起點 $first$ 與終點 $last$ 計算中點，通常採用無條件捨去（向下取整，Floor）：

3. 二元搜尋決策樹（Binary Decision Tree）： 二元搜尋的比較過程可對應為一棵二元樹。樹中的每一層代表一個「回合」（比較次數）：

• 樹根（第 1 層）：需要 1 個回合找到。
• 第 2 層：需要 2 個回合找到。
• 第 3 層：需要 3 個回合找到。
• 第 4 層：需要 4 個回合找到。

4. 平均成功搜尋長度（Average Successful Search Length, ASL）： 在各元素被搜尋機率均等的情形下，平均搜尋回合數為所有元素所需回合數的算術平均值：

其中 $N$ 為元素總數，$C_i$ 為找到第 $i$ 個元素所需的比較回合數。

解題方法

(一) 計算 $mid$ 的公式推導

• 初始範圍為 $first = 0$、$last = 11$。
• 兩者平均值為 $\frac{0 + 11}{2} = 5.5$。由於陣列索引必須為整數，且題意指定第一次 $mid$ 設定值為 $5$，可知此演算法採用「向下取整」（即整數除法無條件捨去小數）：

或以程式語言常見的整數除法（Integer Division）表示：

（亦可寫為防溢位形式：$mid = first + \left\lfloor \frac{last - first}{2} \right\rfloor$）。

(二) 與 (三) 二元搜尋決策樹之建立與各回合元素推導

根據公式 $mid = \lfloor (first + last) / 2 \rfloor$ 與二元搜尋規則（若 $Target < A[mid]$ 則 $last = mid - 1$；若 $Target > A[mid]$ 則 $first = mid + 1$），可建立完整的搜尋決策流程：

1. 第 1 回合：

• 搜尋區間 $[0, 11]$： $mid = \left\lfloor \frac{0 + 11}{2} \right\rfloor = 5 \implies A[5] = 21$
• 第 1 回合找到的元素：$21$。

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$（即 $A[2]$ 與 $A[8]$）。

3. 第 3 回合：

• 由 $A[2]=8$ 分支：
• 左子區間 $[0, 1]$：$mid = \lfloor (0 + 1) / 2 \rfloor = 0 \implies A[0] = 4$
• 右子區間 $[3, 4]$：$mid = \lfloor (3 + 4) / 2 \rfloor = 3 \implies A[3] = 10$
• 由 $A[8]=62$ 分支：
• 左子區間 $[6, 7]$：$mid = \lfloor (6 + 7) / 2 \rfloor = 6 \implies A[6] = 22$（即題目所述之 Target=$22$）
• 右子區間 $[9, 11]$：$mid = \lfloor (9 + 11) / 2 \rfloor = 10 \implies A[10] = 81$
• 第 3 回合找到的所有元素為：$4$、$10$、$22$、$81$。

核心觀念

本題主要測驗計算機科學中「程式語言分類與設計典範（Programming Paradigms）」以及「程式語言抽象層次（Abstraction Levels）」的基礎核心理論：

1. 指令式與程序式典範（Imperative & Procedural Paradigm）：以指令序列、狀態改變與函式模組化為核心，注重「如何做（How to do）」。
2. 物件導向典範（Object-Oriented Paradigm）：以封裝、繼承與多型為支柱，將資料與行為整合成獨立物件，提高軟體復用性與維護性。
3. 函數式典範（Functional Paradigm）：立基於 $\lambda$-演算（Lambda calculus），以數學函數求值為本，強調純函數、不可變性（Immutability）與無副作用（No side effects）。
4. 宣告式／邏輯式典範（Declarative / Logic Paradigm）：強調「做什麼（What to do）」，透過宣告事實（Facts）與規則（Rules），交由推論引擎（Inference Engine）自動求解。
5. 抽象層次對比（High-level vs. Low-level Languages）：評估語言對硬體的相依性、可讀性、移植性（Portability）以及轉譯需求（編譯器／直譯器／組譯器）。

解題方法

本題屬於定義與比較型之申論題，作答時採取「標準定義 $\rightarrow$ 核心特徵與運作原理 $\rightarrow$ 代表語言與優勢」之結構切入，使層次分明：

1. 子題(一)至(四)：先對該程式語言典範給出嚴謹定義，列舉其核心機制（如 Procedural 的狀態變化與模組切割、OOP 的三大特性、Functional 的參照透明性、Declarative 的推論求解），並緊扣題目所附之代表性語言（C、C++、LISP、Prolog）作對應說明。
2. 子題(五)：以系統結構觀點切入，從「抽象層級與語意」、「硬體相依性與可移植性」、「轉譯方式」以及「執行效能與開發效率」四個維度，對比高階語言（High-level）與低階語言（Low-level）的本質差異。

選項分析

本題為申論問答題，非選擇題，故無個別選項之正誤排除。各子題評析重點如下：

• 子題(一) 程序式語言：常見盲點在於與一般的「指令式語言」混淆。作答須強調其將指令結構化為「程序（Procedures）」或「函式（Functions）」之模組化概念，以及明確依賴全域或區域狀態的修改。
• 子題(二) 物件導向語言：不能僅回答「以物件為主」，必須具體列出物件由「狀態（屬性）」與「行為（方法）」構成，且必須明確提及封裝（Encapsulation）、繼承（Inheritance）與多型（Polymorphism）三大支柱。
• 子題(三) 函數式語言：不可僅寫「使用函式」，須點出源自數學函數的概念，核心在於「一級公民函式（First-class functions）」、「無副作用（No side effects）」與「不可變性（Immutability）」，並以遞迴取代傳統狀態改變的迴圈。
• 子題(四) 宣告式語言：最關鍵的區別在於「宣告做什麼（What）」而非「逐步指示如何做（How）」。Prolog 特別仰賴一階邏輯、事實、規則，並透過單一化（Unification）與反駁歸結（Resolution）之回溯（Backtracking）機制完成求解。
• 子題(五) 高階與低階語言比較：低階語言涵蓋機器語言（Machine Language）與組合語言（Assembly Language）；高階語言則是獨立於硬體架構的語言。須由硬體依賴度、人類可讀性、轉譯中介等系統層面建立對比。

解題技巧

1. 對稱關鍵字記憶法：

• Procedural 與 OOP：著重於「演算法與資料結構分離（How）」vs.「演算法與資料結構封裝（Data + Methods）」。
• Imperative vs. Declarative：核心在於「How to do」vs.「What to do」。
• Functional vs. Imperative：核心在於「無狀態／無副作用（Stateless / Pure Functions）」vs.「變更記憶體狀態（State Mutations）」。

2. 低階 vs. 高階語言比較表格化：在申論作答時，除條列說明外，輔以對照表格或對稱點，可協助閱卷老師迅速掌握評分要點。

【答案】

(一) Procedural Language（程序式語言）

1. 定義：程序式語言屬於「指令式程式設計（Imperative Programming）」的一種分支，其程式架構建立在「程序呼叫（Procedure Call）」的觀念上。程式由一系列循序執行的指令序列所組成，透過逐步改變記憶體中的變數與狀態來解決問題。
2. 核心特徵：

• 重視流程與步驟（How to do）：強調演算法的執行順序，透過循序（Sequence）、選擇（Selection）與重複（Iteration）三大控制結構導引執行流程。

核心觀念

本題評量計算機概論中「資料壓縮（Data Compression）」的核心架構與經典演算法分類：

1. 無失真壓縮（Lossless Compression）與失真壓縮（Lossy Compression）的本質差異：資訊是否可完全逆向無損還原、壓縮比大小，以及人體感知系統對不同媒介的容錯程度。
2. 文字與程式碼的資料完整性要求：程式碼與文字檔案對語法（Syntax）與語意（Semantics）具備嚴格的零容錯特性（Zero-tolerance to errors）。
3. 經典無失真壓縮演算法之圖形特徵辨識：

• 遊程編碼（Run-length Encoding, RLE）：以連續重複出現的符號與其長度計數進行替換。
• 字典編碼（Dictionary-based Encoding，如 Lempel-Ziv 系列）：動態維護字串字典（Dictionary），以索引編號（Index）與後續符號替代已出現的樣式。
• 霍夫曼編碼（Huffman Coding）：基於出現頻率構建二元樹（Huffman Tree），指派變動長度碼（Variable-length code）。

解題方法

(一) 無失真壓縮（Lossless methods）與失真壓縮（Lossy methods）的差異

兩者主要差異可歸納為以下四個面向：

1. 解壓縮還原度（Reversibility）：

• Lossless methods：解壓縮後的資料與原始輸入資料在位元層級上完全一致（Bit-for-bit identical），完全不遺失任何原始資訊。
• Lossy methods：解壓縮後的資料與原始資料存在差異，部分次要或高頻細節已遭永久捨棄，無法還原為原始狀態。

2. 壓縮比（Compression Ratio）：

• Lossless methods：受限於資訊熵（Information Entropy），壓縮比相對有限，一般約介於 $2:1$ 至 $4:1$。
• Lossy methods：可大幅去除冗餘資訊，壓縮比極高，常見達 $10:1$ 至 $50:1$ 甚至更高。

3. 消除冗餘的類型（Redundancy Type）：

• Lossless methods：專注於去除「統計冗餘（Statistical/Coding Redundancy）」與「結構冗餘（Interpixel/Spatial Redundancy）」。
• Lossy methods：進一步利用「心理視覺模型（Psycho-visual Model）」或「心理聲學模型（Psycho-acoustic Model）」去除人體感覺器官不易察覺的「感知冗餘（Perceptual Redundancy）」。

4. 應用媒介：

• Lossless methods：適用於文字文件（Text）、程式碼與執行檔（Programs）、資料庫數據等不允許任何誤差之資料。
• Lossy methods：適用於靜態影像（JPEG）、視訊（MPEG）及數位音訊（MP3）等多媒體檔案。

(二) 文字（Text）或程式（Programs）通常使用無失真壓縮的原因

1. 語法與邏輯的零容錯性（Syntactic and Semantic Fragility）： 程式原始碼或機器執行檔具有絕對嚴謹的語法規則與指令格式。在執行檔中，即使僅有單一位元（1 bit）因失真壓縮被竄改或遺失，即會造成指令解碼錯誤（Opcode error）、定址偏差或記憶體區段錯誤（Segmentation fault），導致程式崩潰或執行出非預期結果；文字檔案若遺失或改變字元，會造成文意扭曲、數值錯誤或無法閱讀。
2. 缺乏感知容錯空間（Absence of Perceptual Tolerance）： 多媒體訊號（如聲音、影像）是給人類感官接收的類比離散化資訊，微小色差或音質損失可被人類神經感知忽略；但文字與程式碼屬於離散的符號邏輯系統，不存在「近似即可」的容許模糊度，必須保證解壓縮後的資料能精確重構，因此必須採用無失真壓縮。

(三) 示意圖所屬演算法判斷

題目給定之對照結構為：

• a. Original Data（原始資料）
• b. Compressed Data（壓縮資料）

該圖示代表的是 Run-length（遊程編碼）。 判斷理由： 在標準教材架構中，此示意圖呈現原始資料中出現連續大量相同的字元或位元序列（稱為 Run），編碼器將這段重複序列轉換為「重複出現的符號」加上「重複長度次數（Count）」的壓縮資料格式。此一「原始連續串列 $\rightarrow$ 符號與長度對」的轉換示意圖，為 Run-length encoding 最具代表性的圖示。

(四) 步驟示意圖所屬演算法判斷

題目給定特徵包含：

• 未壓縮字串（Uncompressed）
• 已解析字串（Parsed String）
• 字典編號與條目（1: B, 2: A, 3: AB）
• 目前輸出序列：B、A、2B

該演算法屬於 Lempel Ziv（簡稱 LZ 演算法，圖中為 LZ78 / LZW 體系）。 判斷理由： 此演算法的核心在於動態建立字串字典。初始時字元 B 編為號碼 1，字元 A 編為號碼 2。