111 關務特考三等 電機工程 計算機概論 考古題詳解

核心觀念

本題考驗計算機概論中二進位整數表示法（Binary Number Representation）的核心觀念，特別是**2 的補數表示法（Two's Complement Representation）**之位元結構、數值範圍推導以及符號定義。

1. 位元結構與符號位元（Sign Bit）： 在 $n$ 位元的 2 的補數系統中，最高有效位元（Most Significant Bit, MSB）作為符號位元：

• MSB 為 $0$：代表正數或 $0$。
• MSB 為 $1$：代表負數。

2. 權重定義與二進位轉十進位公式： 對於一個 $n$ 位元的二進位數字 $B = (b_{n-1}b_{n-2}\dots b_1 b_0)_2$，其在 2 的補數表示法下的十進位數值 $V$ 公式為： $V = -b_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} b_i \cdot 2^i$ 對於 $n = 8$ 位元而言，MSB（即 $b_7$）的權重為 $-2^7 = -128$，其餘位元 $b_6 \dots b_0$ 的權重依次為 $2^6, 2^5, \dots, 2^0$。

3. 數值範圍（Range of Representation）： $n$ 位元 2 的補數系統所能表示的整數範圍為 $[-2^{n-1}, 2^{n-1} - 1]$。當 $n = 8$ 時，表示範圍為： $[-2^{8-1}, 2^{8-1} - 1] = [-2^7, 2^7 - 1] = [-128, 127]$

---

解題方法

(一) 所能表示的最大二進位數字與對應十進位數值

• 切入點： 欲得到最大正整數，符號位元（MSB）必須為 $0$（代表非負數），且其餘所有數值位元皆須填入最大值 $1$，使正權重之累加值達到最大。
• 關鍵步驟與推導：

1. 二進位表示：最高位元填 $0$，其餘 7 個位元填 $1$，即 $01111111_2$。
2. 十進位轉換： $V_{\max} = -0 \cdot 2^7 + (1 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0)$ 利用等比級數求和公式 $2^7 - 1$ 計算： $V_{\max} = 2^7 - 1 = 128 - 1 = 127$

(二) 所能表示的最小（負數）二進位數字與對應十進位數值

• 切入點： 欲得到極限最小之負數，符號位元（MSB）必須為 $1$（代表負數，提供 $-2^7 = -128$ 的負權重），且其餘數值位元必須全部填 $0$（不增加任何正數數值），從而得到絕對值最大的負數。
• 關鍵步驟與推導：

1. 二進位表示：最高位元填 $1$，其餘 7 個位元填 $0$，即 $10000000_2$。
2. 十進位轉換： $V_{\min} = -1 \cdot 2^7 + \sum_{i=0}^{6} 0 \cdot 2^i = -128 + 0 = -128$

(三) 等於十進位數字 0 的二進位數字

核心觀念

本題考查電腦網路與資料通訊實體層（Physical Layer）中的奈奎斯特定理（Nyquist Theorem / Nyquist Bit Rate Formula）。

在**無雜訊頻道（Noiseless Channel）**環境下，頻道能傳送的最大資料速率（Bit Rate）受限於頻道的頻寬（Bandwidth, $B$）以及傳輸訊號所使用的電位階數（Signal Levels, $L$）。

奈奎斯特極限傳送速率公式如下： $\text{Bit Rate} = 2 \times B \times \log_2(L) \quad (\text{bps})$

變數定義說明：

• $B$：頻道頻寬或傳送頻率（單位：$\text{Hz}$）。
• $L$：離散訊號的電位種類數量（Signal Levels）。
• $\log_2(L)$：每個電位（Signal Element / Symbol）所能攜帶的資料位元數（$\text{bits/symbol}$）。
• $2 \times B$：無雜訊頻道下傳輸訊號的最高符號率／波特率（Maximum Baud Rate / Symbol Rate）。

---

解題方法

(一) 使用 $2$ 種不同電位時的最高傳送速率

1. 已知條件：

• 頻道傳送頻率 $B = 2000\text{ Hz}$
• 電位階數 $L = 2$（分別代表 $0$ 與 $1$）

2. 計算過程與推導：

• 每個電位載送之位元數： $\log_2(2) = 1\text{ bit/symbol}$
• 最高波特率（Baud Rate）： $\text{Baud Rate} = 2 \times B = 2 \times 2000 = 4000\text{ symbols/sec}$
• 帶入奈奎斯特公式求最高傳送速率（Bit Rate）： $\text{Bit Rate} = 2 \times 2000 \times \log_2(2) = 4000 \times 1 = 4000\text{ bps}$

(二) 使用 $4$ 種不同電位時的最高傳送速率

1. 已知條件：

• 頻道傳送頻率 $B = 2000\text{ Hz}$
• 電位階數 $L = 4$

2. 計算過程與推導：

• 每個電位載送之位元數： $\log_2(4) = 2\text{ bits/symbol}$
• 帶入奈奎斯特公式求最高傳送速率（Bit Rate）： $\text{Bit Rate} = 2 \times 2000 \times \log_2(4) = 4000 \times 2 = 8000\text{ bps}$

---

核心觀念

本題旨在考查資料結構（Data Structures）的基礎理論與實際應用能力。資料結構可分為線性結構（陣列、堆疊、佇列）與非線性結構（樹狀結構）。考生需掌握各種資料結構的記憶體配置方式、存取行為模式（Access Pattern）、時間複雜度（Time Complexity），並能精確對應至作業系統、編譯器、資料庫、網路與演算法等領域的實際應用場合。

---

解題方法

本題為國家考試 25 分之申論問答題。擬答時應採取**「結構化標題 + 特性剖析 + 具體應用場合實例 + 效能分析」**的切入點進行答題，以展現嚴密的邏輯與專業深度：

1. 定義與存取模式：明確說明該資料結構的運作原理（如 LIFO、FIFO、隨機存取或階層關係）。
2. 具體適用場合舉例：各提出 2 至 4 個代表性且具體具說服力的電腦系統與演算法應用場景。
3. 適用原因與優勢說明：結合時間複雜度（如 $O(1)$、$O(\log n)$）說明為何該場合最適宜使用此資料結構。

---

選項分析

本題屬問答申論題型，以下針對題目要求之四種資料結構（陣列、堆疊、佇列、樹狀結構）進行適性與應用場合之詳細逐項分析：

一、 陣列（Array）

1. 核心特性：採用連續記憶體空間儲存相同型態之資料項，具備**隨機存取（Random Access）**特性。已知基底位址與元素索引時，可直接經由位址偏移量公式 $\text{Address}(i) = \text{Base} + i \times \text{Size}$ 進行存取。
2. 適用場合與實例：

• 矩陣與影像處理：影像色彩（RGB 像素陣列）與線性代數矩陣運算，需以二維或多維陣列表示固定維度空間。
• 靜態查表（Look-up Table）：例如對照表（如月份天數、ASCII 字元對照表），資料量固定且無需頻繁插入或刪除。
• 高級資料結構的底層實現：如堆積（Heap）、雜湊表（Hash Table）的 Bucket 陣列，利用陣列提供快速存取。

3. 優缺點與效能：讀取與修改指定索引之時間複雜度為 $O(1)$；但大小固定且擴充困難，若於中間插入或刪除元素需搬移資料，時間複雜度為 $O(n)$。

二、 堆疊（Stack）

1. 核心特性：為一種限制性線性結構，遵循**後進先出（LIFO, Last-In-First-Out）**原則，資料之插入（Push）與刪除（Pop）皆僅能於頂端（Top）進行。
2. 適用場合與實例：

• 程式語言之函式呼叫（Function Call Stack）：當程式執行函式呼叫與遞迴（Recursion）時，作業系統使用 Call Stack 記錄區域變數、參數及返回位址（Return Address）。
• 運算式解析與求值（Expression Evaluation）：編譯器處理中序運算式轉後序運算式（Infix to Postfix）以及括號匹配檢查（Bracket Matching）。
• 應用程式之「復原/重做」（Undo / Redo）機制：文字編輯器將使用者操作依序壓入堆疊，按下 Undo 時即可取出最後一次操作進行撤銷。
• 圖形演算法之深度優先搜尋（DFS, Depth-First Search）：以堆疊記錄待訪節點，達到深入搜尋之目的。

3. 優缺點與效能：頂端元素之 Push 與 Pop 操作時間複雜度均為 $O(1)$，空間開銷小且邏輯明確。

三、 佇列（Queue）

1. 核心特性：為一種限制性線性結構，遵循**先進先出（FIFO, First-In-First-Out）**原則，資料自前端（Front/Head）刪除（Dequeue），自尾端（Rear/Tail）新增（Enqueue）。
2. 適用場合與實例：

• 作業系統資源排程（OS Scheduling & Buffering）：CPU 佇列（Ready Queue）、印表機列印工作佇列（Printer Spooling Queue）及 I/O 緩衝區。
• 圖形演算法之廣度優先搜尋（BFS, Breadth-First Search）：逐層走訪圖形節點時，使用佇列維護目前層級之鄰接節點。
• 分散式系統之訊息佇列（Message Queue）：如 Producer-Consumer 模式，解決系統間非同步處理與峰值流量削峰（Traffic Shaving）。

3. 優缺點與效能：前端刪除與尾端新增之時間複雜度均為 $O(1)$；確保資料處理之公平性與順序性。

核心觀念 本題考查計算機概論與程式設計的核心理論「結構化程式設計（Structured Programming）」與「Böhm-Jacopini 定理（Structured Program Theorem）」。重點包含：

1. 結構化程式設計的起源、核心定義與目標（提升可讀性、可維護性、防範義大利麵條式程式碼 Spaghetti Code）。
2. 三種基本控制結構：順序（Sequence）、選擇（Selection）、重複（Iteration）的意義與運作方式。
3. 無 goto 敘述之功能完整性：基於 Böhm-Jacopini 定理證明結構化流程的足夠性，說明不使用 goto 絕不受限於任何邏輯功能的實現。

---

解題方法 本題為經典的觀念申論題，切入點應分為三大層次撰寫：

1. 定義說明：精確定義「結構化程式設計」，強調「單一入口與單一出口（Single-Entry, Single-Exit, SESE）」原則及由上而下的模組化開發。
2. 結構列舉與說明：條列三種基本控制流程結構（順序、選擇、重複），並說明其控制流程與邏輯意義。
3. 理論論述與命題判斷：明確回答「否，不會無法達成某些功能」，並引述「Böhm-Jacopini 定理」作為理論依據，說明三種基本結構即可構成圖靈完備（Turing Completeness）的控制邏輯；最後簡述實務上不用 goto 的影響與替代方案。

---

選項分析 （本題為申論問答題，以下針對題目的三個核心提問區塊進行逐一解析與剖析）：

1. 第一部分：說明結構化程式設計（Structured Programming）的意義

• 意義與目標：結構化程式設計是一種程式設計範式，旨在透過限制控制跳躍，使程式碼的執行流程符合邏輯結構。其主要目標為：
• 提高程式可讀性與可維護性：程式碼由上而下順暢執行，除錯與修改時容易追蹤資料流與控制流。
• 消除 Spaghetti Code（義大利麵條式程式碼）：避免因無限制使用 goto 敘述造成控制流隨意跳躍、無法預測執行路徑的混亂現象。
• 單一入口與單一出口原則（Single-Entry, Single-Exit）：每一個模組或控制區塊均只有一個進入點與一個離開點，便於單元測試與邏輯驗證。
• 模組化設計（Modularity）：鼓勵採用由上而下（Top-Down）的逐步分解法，將複雜問題拆解為數個獨立的子程式或函數。

2. 第二部分：任舉至少三種基本的控制程式流程結構的意義 根據 Böhm-Jacopini 定理，任何程式邏輯均可由以下三種基本結構組合而成：

• (1) 順序結構（Sequence Structure）：
• 意義：程式敘述依據撰寫的先後順序，由上而下依次執行，前一個敘述執行完畢後方能執行下一個敘述。
• 範例：資料輸入、運算指派、資料輸出等連續指令。
• (2) 選擇結構（Selection / Conditional Structure）：
• 意義：根據條件運算式的判斷結果（真 True 或假 False），決定執行不同的程式分支區塊。
• 範例：if-else 分支敘述、switch-case 多重選擇敘述。