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

核心觀念

1. 比較器（Comparator）定義：比較兩組二進位數值大小的組合邏輯電路。本題為 $1$-bit 比較器，輸入為 $a, b \in \{0, 1\}$，輸出 $c$ 僅在條件 $a > b$ 成立時為 $1$，其餘情況為 $0$。
2. 真值表（Truth Table）與布林代數（Boolean Algebra）：將所有輸入組合列出，找出輸出為 $1$ 的最小項（Minterm），進而導出最簡積之和（Sum of Products, SOP）布林表示式。
3. 基本邏輯閘集合：限定僅使用 $\text{AND}$、$\text{OR}$、$\text{NOT}$ 三種基本邏輯閘實現電路。

---

解題方法

步驟一：建立真值表 列出輸入 $a$ 與 $b$ 的 4 種組合，並比對大小關係求得輸出 $c$：

輸入 $a$	輸入 $b$	大小關係判定	輸出 $c$ ($a > b$)	最小項
0	0	$0 = 0$（不成立）	0	$m_0$
0	1	$0 < 1$（不成立）	0	$m_1$
1	0	$1 > 0$（成立）	1	$m_2 = a\overline{b}$
1	1	$1 = 1$（不成立）	0	$m_3$

步驟二：推導布林代數表示式 由真值表可知，僅在 $a = 1$ 且 $b = 0$（即最小項 $m_2$）時，輸出 $c$ 為 $1$： $c = a \cdot \overline{b}$

步驟三：邏輯電路設計 該布林式僅需使用邏輯閘集合 $\{\text{AND}, \text{OR}, \text{NOT}\}$ 中的 1 個 $\text{NOT}$ 閘與 1 個 $\text{AND}$ 閘即可實現，完全符合題目限制：

1. 輸入 $b$ 經由一個 $\text{NOT}$ 閘反向，輸出為 $\overline{b}$。
2. 輸入 $a$ 與反向後的 $\overline{b}$ 同時輸入至一個雙輸入 $\text{AND}$ 閘。
3. 該 $\text{AND}$ 閘之輸出端即為 $c$。

電路接線圖示意：

a -------------------\
 )--- AND ---> c
b --->[ NOT ]-- b' --/

---

解題技巧

• 陷阱注意：題目敘述「只能利用基本的三種邏輯閘 AND、OR、NOT」，意指邏輯閘元件庫僅限於此三者（不得使用 $\text{XOR}$、$\text{NAND}$、$\text{NOR}$ 等複合閘）。若電路化簡後只需使用其中的 $\text{AND}$ 與 $\text{NOT}$ 即可達成，不需強行加入無意義的 $\text{OR}$ 閘（如 $c = a\overline{b} + 0$）。
• 快速驗算：
• 代入 $a=1, b=0 \implies c = 1 \cdot \overline{0} = 1 \cdot 1 = 1$（符合）。
• 代入其他三種組合，因 $a=0$ 或 $\overline{b}=0$，乘積必為 $0$（符合）。

---

第 (二) 小題

核心觀念

1. $n$-bit 二補數（2's Complement）數值表示範圍： $[-2^{n-1}, \, 2^{n-1}-1]$ 當 $n=4$ 時，可表示之整數範圍為 $[-2^3, \, 2^3-1] = [-8, \, +7]$。
2. 正整數之二補數編碼：正數的二補數表示法與一般無號二進位相同，最高位元（Most Significant Bit, MSB）為符號位元（Sign Bit），正數之符號位元必為 $0$。
3. 二補數加法溢位（Overflow）判斷：

• 符號判別法：兩同號數相加，若運算結果之符號位元與加數相反，代表發生溢位。

核心觀念

1. 函式程式語言（Functional Programming）與 Scheme 語法特性：

• S-運算式（S-expression）與前序表示法（Prefix Notation）：運算子或函式名稱置於最前端，緊接運算元，形式為 (function arg1 arg2 ...)。
• 條件分支指令：
• cond 語法：(cond (條件1 傳回值1) (條件2 傳回值2) ... (else 預設值))。
• if 語法：(if 條件 成立傳回值 不成立傳回值)。

2. 串列（List）核心操作函式：

• null?：述詞函式（Predicate），判斷串列是否為空串列（'），若是則回傳真值 #t，否則回傳假值 #f。
• car：取出串列的第一個元素（Head）。
• cdr：取出除去第一個元素後剩下的其餘子串列（Tail）。

3. 結構性遞迴（Structural Recursion）：

• 串列處理的標準遞迴架構包含：
• 基準條件（Base Case）：當串列為空時停止遞迴並回傳初值（此處為 0）。
• 遞迴條件（Recursive Case）：透過 (cdr input-list) 縮小問題規模，逐步向空串列逼近。

4. 階乘（Factorial）的數學遞迴定義： $n! = \begin{cases} 1, & \text{若 } n = 0 \text{ 或 } n = 1 \\ n \times (n-1)!, & \text{若 } n > 1 \end{cases}$

---

解題方法

(一) 函式呼叫追蹤（Trace）

欲求 (mystery (list 4 5 6)) 之結果，將引數代入遞迴展開如下：

1. 第一層呼叫：input-list 為 (4 5 6)

• (null? '(4 5 6)) 為 #f。
• 進入 else 分支：(+ 1 (mystery (cdr '(4 5 6))))
• 因 (cdr '(4 5 6)) 得到 (5 6)，展開為：(+ 1 (mystery '(5 6)))

2. 第二層呼叫：input-list 為 (5 6)

• (null? '(5 6)) 為 #f。
• 展開為：(+ 1 (+ 1 (mystery '(6))))

3. 第三層呼叫：input-list 為 (6)

• (null? '(6)) 為 #f。
• 展開為：(+ 1 (+ 1 (+ 1 (mystery '))))

4. 第四層呼叫（終止條件）：input-list 為 ``（空串列）

核心觀念

本題評量作業系統（Operating System）中「虛擬記憶體（Virtual Memory）」管理機制之兩大經典考點：

1. 分頁定址架構（Paging Address Translation）：

• 電腦通常以位元組（Byte）為基本定址單位（Byte-addressable）。
• 分頁大小（Page Size） 決定頁內位移量（Page Offset, $d$）之位元數，且分頁與實體框（Frame）大小相等，故邏輯位址與實體位址之位移量位元數完全相同。
• 邏輯位址（Logical Address） 由「分頁編號（Page Number, $p$）」與「位移量（$d$）」組成；分頁編號位元數由邏輯分頁總數決定。
• 實體位址（Physical Address） 由「框編號（Frame Number, $f$）」與「位移量（$d$）」組成；框編號位元數由實體記憶體框總數決定。

2. 需求分頁（Demand Paging）與 LRU 取代演算法：

• 需求分頁在分頁被存取且尚未載入實體記憶體時，會觸發分頁錯誤（Page Fault），作業系統需將該分頁從輔助記憶體（磁碟）載入實體框中。
• LRU（Least Recently Used，最近最少使用演算法）：當實體框已滿又發生分頁錯誤時，選擇「最長時間未被存取」的分頁作為犧牲者（Victim Page）淘汰。

---

解題方法

(一) 計算邏輯位址與實體位址位元數

1. 計算位移量（Offset, $d$）位元數：

• 每個分頁大小為 $4\text{ KB} = 4 \times 1024\text{ Bytes} = 4096\text{ Bytes} = 2^{12}\text{ Bytes}$。
• 頁內位移量所需位元數為： $d = \log_2(4096) = 12\text{ bits}$
• 分頁大小等於框大小，因此邏輯位址與實體位址之位移量皆為 $12\text{ bits}$。

2. 計算分頁編號（Page Number, $p$）與邏輯位址大小：

• 邏輯位址空間共有 $256$ 個分頁： $p = \log_2(256) = \log_2(2^8) = 8\text{ bits}$
• 邏輯位址總位元數為分頁編號與位移量之和： $\text{邏輯位址} = p + d = 8 + 12 = 20\text{ bits}$

3. 計算框編號（Frame Number, $f$）與實體位址大小：

• 實體記憶體共有 $64$ 個框： $f = \log_2(64) = \log_2(2^6) = 6\text{ bits}$
• 實體位址總位元數為框編號與位移量之和： $\text{實體位址} = f + d = 6 + 12 = 18\text{ bits}$

---

(二) 追蹤需求分頁與 LRU 取代過程

系統具備 $3$ 個分頁框，初始為空。分頁參考序列共 $20$ 次存取： $7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1$

以下逐步追蹤記憶體內 3 個框之內容變化與 LRU 淘汰決策：

步驟	參考分頁	框 1	框 2	框 3	結果	淘汰分頁 (Victim) / 說明
1	7	7	-	-	Page Fault	初始空框載入（冷啟動）
2	2	7	2	-	Page Fault	初始空框載入（冷啟動）
3	3	7	2	3	Page Fault	初始空框載入（冷啟動，框已滿）
4	1	1	2	3	Page Fault	框已滿，最久未使用為 7，淘汰 7
5	2	1	2	3	Hit	2 已在記憶體中，更新 2 為最新存取
6	5	1	2	5	Page Fault	過去存取順序為 3(步3) < 1(步4) < 2(步5)，最久未使用為 3，淘汰 3
7	3	3	2	5	Page Fault	過去存取順序為 1(步4) < 2(步5) < 5(步6)，最久未使用為 1，淘汰 1

核心觀念

1. 無階級網際網域路由（CIDR）與子網路遮罩（Subnet Mask）：

• 符號 $/27$ 代表前 27 個位元為網路識別碼與子網路識別碼（Network/Subnet ID），後續剩餘位元為主機識別碼（Host ID）。
• IPv4 位址長度共 32 位元，因此主機位元數為 $32 - 27 = 5$ 個位元。

2. 區塊大小（Block Size / Increment）：

• 每一個子網域所容納的總 IP 數量（區塊大小）為 $2^5 = 32$ 個。

3. 位址類型定義：

• 子網路位址（Network Address）：主機位元全為 $0$，代表該網段本身。
• 廣播位址（Broadcast Address）：主機位元全為 $1$，用於該網段內的所有主機廣播。
• 可用主機 IP 範圍（Usable Host IP Range）：介於子網路位址與廣播位址之間的 IP，數量為 $2^5 - 2 = 30$ 個。

---

解題方法

1. 求子網路遮罩：

• 前 24 位元皆為 1（即前三組數字為 $255.255.255$）。
• 第四個八位元組（4th octet）佔用 3 個位元： $11100000_2 = 128 + 64 + 32 = 224$
• 故子網路遮罩為 $255.255.255.224$。

2. 計算第四個八位元組的子網路區間：

• 區塊增量為 $2^{32 - 27} = 2^5 = 32$。
• 第四個八位元組的子網路起始點依序為：$0, 32, 64, 96, 128, 160, 192, 224$。
• 題目給定 IP 為 $167.188.170.83$，其第四個數字為 $83$。
• 由於 $64 \le 83 < 96$，該 IP 落於起點為 $64$ 的子網段中。
• 亦可透過二進位逐位元 AND 運算驗證： $83 = 01010011_2$ $224 = 11100000_2$ $83 \text{ AND } 224 = 01000000_2 = 64$

3. 推導網段界限：

• 子網路位址：$167.188.170.64$
• 廣播位址：$167.188.170.64 + 32 - 1 = 167.188.170.95$（主機位元全為 1：$01011111_2 = 95$）
• 完整子網域位址範圍：$167.188.170.64 \sim 167.188.170.95$
• 可用主機 IP 範圍：$167.188.170.65 \sim 167.188.170.94$

---

解題技巧

• 魔術數字法（Magic Number）：直接以 $256 - \text{遮罩最後一組數值} = 256 - 224 = 32$。接著用 IP 最後一碼除以 $32$：$83 \div 32 = 2 \dots 19$，商數為 2，故子網路起點為 $32 \times 2 = 64$，終點為 $64 + 32 - 1 = 95$。10 秒內即可快速驗算完畢。
• 作答完整性：國家考試中問及「子網域範圍」，務必同時列出「完整網段範圍（含網路與廣播位址）」以及「可用主機 IP 範圍」，確保不被閱卷委員扣分。

---

第二題：媒介存取控制（MAC）協定分析

核心觀念

1. 隨機存取協定（Random Access / Contention-based Protocols）：

• 節點隨時可能嘗試存取通道，沒有中央控制器協調，亦無事先保留時間或頻率。
• 當站台數極多且負載沉重時，多個節點同時傳輸的機率急遽上升，造成**大量封包碰撞（Collision）**與重傳。通道充斥無效訊號與退避等待，導致吞吐量雪崩式驟降，甚至發生「壅塞崩潰（Congestion Collapse）」。

2. 通道劃分協定（Channel Partitioning Protocols）：

• 將通道頻寬在時間、頻率或編碼上靜態切割並專屬分配給各節點（如 TDMA、FDMA、CDMA）。
• 節點只在專屬資源內傳輸，完全不會發生碰撞，系統吞吐量在高負載時仍能維持穩定。

---

解題方法

檢視各選項協定之運作架構，辨別何者屬於「無預先劃分通道、依賴競爭之隨機存取協定」，並針對高站台數量下的碰撞行為進行分析。

---

核心觀念

1. 後序表示式（Postfix / Reverse Polish Notation, RPN）求值： 後序表示式的運算子位於運算元之後，具有無需括號即可唯一確定運算順序的特性。計算機底層通常利用**堆疊（Stack）**資料結構來實作：由左至右依序讀入符號，若為運算元則推入（Push）堆疊；若為二元運算子則從堆疊彈出（Pop）兩個運算元進行計算，並將結果推回（Push）堆疊。

2. 二元樹（Binary Tree）走訪與重構：

• 後序走訪（Postorder: Left $\to$ Right $\to$ Root）：最後走訪的節點必為該樹（或子樹）之根節點（Root）。
• 中序走訪（Inorder: Left $\to$ Root $\to$ Right）：根節點左側的所有節點必屬於左子樹，右側的所有節點必屬於右子樹。
• 藉由「後序定根節點、中序切分左右子樹」的遞迴原則，可唯一還原出原始二元樹結構。

---

解題方法

(一) 後序表示式求值

給定後序算式：$2\ 3\ 4\ +\ *\ 5\ +$

運算規則： 由左至右依序掃描算式，遇到數值即 Push 入堆疊；遇到運算子時，Pop 兩元素 $op_2$（先彈出者，右運算元）與 $op_1$（後彈出者，左運算元），計算 $op_1 \text{ 運算子 } op_2$，將計算結果 Push 回堆疊。

堆疊追蹤步驟表：

步驟	讀入符號	動作說明	堆疊內容（由底至頂）
1	2	運算元，Push 2	$[2]$
2	3	運算元，Push 3	$[2, 3]$
3	4	運算元，Push 4	$[2, 3, 4]$
4	+	彈出 4 與 3，計算 $3 + 4 = 7$，Push 7	$[2, 7]$
5	*	彈出 7 與 2，計算 $2 \times 7 = 14$，Push 14	$[14]$
6	5	運算元，Push 5	$[14, 5]$
7	+	彈出 5 與 14，計算 $14 + 5 = 19$，Push 19	$[19]$

式子處理完畢，堆疊頂端之數值即為最終計算結果：$19$。

---

(二) 二元樹重構

給定走訪順序：

• 後序走訪（Postorder）：H G D B F E C A
• 中序走訪（Inorder）：H D G B A C F E

推導步驟：

1. 確定整棵樹之樹根與左右子樹分割：

• 由後序最後一個字母可知，整棵樹的根節點為 $A$。
• 對照中序 H D G B A C F E，以 $A$ 為中心分割：
• 左子樹節點集合：$\{H, D, G, B\}$（共 4 個節點）
• 右子樹節點集合：$\{C, F, E\}$（共 3 個節點）