110 地方特考四等 電子工程 計算機概要 考古題詳解

核心觀念

本題考查快取記憶體（cache）位址的切割方式。一般 byte-addressable cache 的記憶體位址可分為：

其中：

• Block Offset：指定資料位於 cache block 內的哪一個 byte。
• Set Index：指定資料所對應的 set。
• Tag：辨識同一個 set 中不同記憶體區塊的高位址部分。

因此：

解題方法

1. 計算 cache 中共有多少個 block：

2. 因為是 4-way set associative，每個 set 包含 4 個 block，因此 set 數量為：

所以 Set Index 需要 $9$ bits。

3. 每個 cache block 為 $16$ Byte：

因此 Block Offset 需要 $4$ bits。

4. 處理器具有 32-bit 記憶位址，所以：

核心觀念

本題考查十進制整數轉換為二進制表示法。二進制各位數的權值由右至左依序為：

若以 8 位元表示，權值排列為：

其中二進制位元為 $1$ 表示該權值要計入，為 $0$ 表示不計入。

解題方法

將 $105$ 拆解為 $2$ 的冪次和：

依照 $128$ 至 $1$ 的權值排列判斷：

因此：

也可用十進制除以 $2$ 連續取餘數驗證：

核心觀念

本題考查作業系統中「多個處理器同時執行程序」的術語辨識。

當電腦系統具有多個處理器（processors），並讓各處理器在同一時間分別執行程序（processes）時，稱為 Multiprocessing（多處理）。其重點是：

• 系統中有多個處理器。
• 多個程序可在不同處理器上同時執行。
• 屬於硬體平行處理與作業系統程序管理的概念。

解題方法

題幹的關鍵語句是：

「使用多個處理器」 「在同一時間」 「在各自處理器上運行程序」

其中「多個處理器」直接對應 Multiprocessing；「同一時間在各自處理器上執行」則表示真正的平行處理，而非單一處理器快速切換工作。

因此，本題選擇 (A) Multiprocessing。

選項分析

(A) Multiprocessing：正確

Multiprocessing 是指電腦系統使用兩個以上的處理器，使多個程序能夠同時在不同處理器上執行。

例如，處理器 $P_1$ 執行程序 $P_A$，處理器 $P_2$ 同時執行程序 $P_B$，此種架構即屬於 Multiprocessing。

(B) Multiprogramming：錯誤

Multiprogramming（多重程式設計）是將多個程序放在主記憶體中，由單一處理器在某一程序等待輸入／輸出時，改執行其他程序，以提高處理器使用率。

其核心是：

• 記憶體中同時存在多個程序。
• 處理器在程序間切換執行。
• 不以多個處理器為必要條件。

因此，題幹強調「多個處理器」與「同一時間」執行，不是 Multiprogramming 的主要定義。

核心觀念

本題考查馮紐曼（von Neumann）模型所定義的電腦基本子系統。

馮紐曼模型通常包含下列主要部分：

1. 記憶體（Memory）：儲存指令、資料及運算結果。
2. 算術邏輯單元（ALU）：執行算術運算與邏輯運算。
3. 控制單元（Control Unit）：解碼指令，並控制各單元依序執行。
4. 輸入／輸出單元（I/O）：與外部裝置或使用者交換資料。

其中，中央處理單元（CPU）主要由控制單元與算術邏輯單元組成。

解題方法

判斷各選項是否屬於馮紐曼模型的「功能性子系統」即可：

• 若是負責運算、控制、儲存或輸入輸出的功能單元，屬於模型中的子系統。
• 若只是承載或連接硬體元件的實體電路板，並非馮紐曼模型所定義的功能性子系統。

因此，應選出不屬於上述功能分類的硬體名稱。

選項分析

(A) 主機版（Motherboard）

主機版是電腦中的實體電路板，提供處理器、記憶體、儲存裝置及輸入／輸出介面之間的連接與供電功能。

然而，主機版是現代電腦的硬體組裝平台，並非馮紐曼模型中的基本功能子系統。馮紐曼模型關注的是「運算、控制、記憶與輸入／輸出」等功能，不以主機版作為模型組成單元。

因此，(A) 不屬於馮紐曼模型定義下的子系統。

(B) 算術邏輯單元（Arithmetic Logic Unit, ALU）

核心觀念

循序電路（sequential circuit）的輸出，不只取決於當下輸入，也取決於電路過去所儲存的狀態。因此，循序電路必須包含記憶元件，例如：

• Flip-Flop（正反器）
• Latch（閂鎖）
• 暫存器（Register）
• 計數器（Counter）

典型循序電路具有時脈訊號（clock），並透過回授將目前狀態送回邏輯電路，形成下一個狀態。

相對地，組合電路（combinational circuit）的輸出只由當下輸入決定，不具備狀態儲存功能。

解題方法

逐一觀察各選項是否包含：

1. Flip-Flop 或 Latch 等記憶元件；
2. clock 時脈輸入；
3. 狀態輸出回授至邏輯電路，產生下一狀態。

只要電路中出現 D 型正反器等記憶元件，即具備儲存狀態的能力，可判定為循序電路。

選項分析

(A) 錯誤

(A) 由 AND gate、OR gate 與 NOT gate 組成，所有元件皆為組合邏輯閘。

電路中沒有 Flip-Flop、Latch 或 clock，也沒有狀態儲存機制。因此其輸出 $E$ 僅由當下的 $A、B、C、D$ 決定，屬於組合電路。

(B) 錯誤

(B) 雖然包含多個 AND gate、OR gate 與 NOT gate，且線路排列較複雜，但圖中沒有任何正反器、閂鎖或時脈控制元件。

線路交會及回繞不代表具有記憶功能；只要沒有儲存元件，電路仍屬組合電路。因此輸出 $D$ 只取決於當下輸入 $A、B、C$。

核心觀念

多工器（Multiplexer，MUX）是一種「多輸入、單輸出」的數位電路，功能是利用選擇控制線，從多個輸入通道中選出其中一個，送至唯一的輸出端。

若多工器具有 $n$ 條選擇控制線，可表示的選擇狀態數為：

本題有 $4$ 條選擇控制線，因此最多可選擇：

個輸入通道。多工器的輸出端通常為 $1$ 個，因此本題為「至多 16 個輸入通道、1 個輸出通道」。

解題方法

設四條選擇線為 $S_3,S_2,S_1,S_0$，其組合數為：

共有 $16$ 種選擇狀態。每一種狀態可指定一個輸入端連接至輸出端，例如：

• $S_3S_2S_1S_0=0000$：選取第 0 個輸入
• $S_3S_2S_1S_0=0001$：選取第 1 個輸入
• $\cdots$
• $S_3S_2S_1S_0=1111$：選取第 15 個輸入

因此，四條選擇控制線最多控制 $16$ 個輸入通道，而輸出端為單一通道，符合選項 (D)。

選項分析

(A) 該多工器有 1 個輸入通道、（至多）4 個輸出通道

核心觀念

本題考查 8-bit 整數的二補數表示法。二補數表示負整數時，計算步驟為：

1. 先將正數的二進位表示寫出。
2. 所有位元逐位反相。
3. 反相結果加 $1$。

8-bit 二補數可表示的整數範圍為：

也就是 $-128$ 至 $127$，因此 $-72$ 可以用 8-bit 二補數表示。

解題方法

先將 $72$ 轉換為 8-bit 二進位：

所以：

接著逐位反相：

最後加 $1$：

因此，整數 $-72$ 的 8-bit 二補數表示法為：

選項分析

• (A) 01001000

此位元組的最高位為 $0$，表示正數，直接換算為：

$2^6+2^3=64+8=72$

因此它表示 $+72$，不是 $-72$，錯誤。

• (B) 11001000

最高位為 $1$，代表負數。將其轉回十進位：

先反相：

$11001000\longrightarrow00110111$

核心觀念

本題考查「虛擬記憶體（Virtual Memory）」與「分頁（Paging）」的基本概念。

虛擬記憶體將程式所使用的虛擬位址，分成：

主記憶體則分成大小相同的頁框（Frame）。作業系統利用 Page Table 記錄「虛擬頁」目前對應到哪一個「實體頁框」：

頁內位移不需轉換，直接沿用。因此，虛擬記憶體的主要作用是讓程式擁有較大的「虛擬位址空間」，並透過主記憶體與輔助儲存裝置之間的頁面交換，執行容量大於實體記憶體的程式。

解題方法

判斷本題各選項時，應區分下列兩個概念：

1. 虛擬記憶體可以擴大程式可使用的「邏輯／虛擬記憶體空間」。
2. 虛擬記憶體不會增加電腦實際安裝的 DRAM 容量。

虛擬記憶體通常以硬碟或 SSD 作為後援儲存空間。當程式需要某一頁而該頁不在主記憶體時，作業系統會產生 Page Fault，將所需頁面載入某個可用頁框；不常用的頁面則可被移出主記憶體。

因此，虛擬記憶體是「管理與延伸記憶體使用方式的機制」，不是增加實體 DRAM 的硬體設備。

選項分析

(A) 使用 Page Table 可以將虛擬記憶體位址的頁碼（page number）轉換成實體位址的頁框碼（frame number）

正確。

Page Table 的主要功能就是記錄虛擬頁碼與實體頁框碼的對應關係。CPU 產生虛擬位址後，記憶體管理單元（MMU）會查詢 Page Table，將頁碼轉換為頁框碼，再加上原本的頁內位移，形成實體位址：

實際系統中也可能先查詢 TLB，以加速頁碼到頁框碼的轉換，但基本的對應資料仍由 Page Table 提供。

(B) Page Table 的內容（或部分內容）可以放在主記憶體

正確。

核心觀念

本題考查「虛擬機器（Virtual Machine, VM）軟體佈建」的主要效益。

虛擬機器是在同一部實體主機上，透過虛擬化軟體建立多個彼此隔離的虛擬運算環境。每個虛擬機器可執行不同的作業系統與應用程式，常見優點包括：

• 提高硬體資源使用率。
• 減少實體伺服器數量。
• 提供作業系統與軟體的隔離環境。
• 方便建立、複製、還原測試環境。
• 降低軟體對特定硬體的依賴，改善部署相容性。

解題方法

判斷各選項是否屬於虛擬機器的典型效益即可。

若選項描述的是「資源整合、環境隔離、快速建立測試環境、提升部署彈性」，通常屬於虛擬化的優點；若宣稱能直接提升網路服務的反應速度，則不屬於虛擬機器本身必然提供的效益。

因此，本題應選出「不是虛擬機器軟體佈建好處」的選項。

選項分析

(A) 加快網路點擊服務的反應時間

錯誤。本項不是虛擬機器軟體佈建的直接或典型好處。

虛擬機器需要經由虛擬化層分配處理器、記憶體、儲存設備及網路介面，通常還會產生一定的管理與效能負擔。虛擬化的主要目的在於資源整合、環境隔離及部署彈性，並非直接加快網路服務的回應時間。

網路點擊服務的反應速度主要受下列因素影響：

• 網路頻寬與延遲。
• 伺服器處理能力。
• 資料庫查詢效率。
• 程式設計與快取機制。
• 服務架構及負載平衡配置。

若搭配負載平衡、資源動態配置、快取等完整架構，虛擬化環境可能間接改善服務效能；但「加快反應時間」並非虛擬機器佈建本身必然具備的好處。依官方答案，本題選 A。

(B) 提升單機的相容性

正確。虛擬機器可在同一部實體主機上執行不同作業系統及應用程式，並透過標準化的虛擬硬體介面降低軟體對特定實體硬體的依賴。

核心觀念

資料壓縮可分為：

• 無損壓縮（lossless compression）：解壓縮後可完全還原原始資料，適合文字、程式、資料庫等。
• 損耗壓縮（lossy compression）：壓縮時捨棄部分人眼或人耳較不易察覺的資訊，解壓縮後無法完全還原原始資料，但通常能取得較高壓縮率。

本題要辨識各種壓縮技術的基本分類。

解題方法

判斷重點在於：解壓縮後是否能逐位元還原原始資料。

Run-length encoding、Huffman coding 與 Lempel-Ziv encoding 都是利用資料中的重複性或統計特性重新編碼，不捨棄原始資訊，因此屬於無損壓縮。

MPEG encoding 則主要應用於影像、影片及聲音壓縮，會利用人類視覺與聽覺不敏感的特性，刪除部分資訊，以換取較高的壓縮效率，因此在本題分類下屬於損耗壓縮。

選項分析

(A) Run-length encoding

Run-length encoding，簡稱 RLE，將連續重複的資料表示為「資料值＋重複次數」。

例如：

解碼時可依照重複次數完整還原原始資料，因此不會造成資料內容損失，屬於無損壓縮。本選項錯誤。

(B) MPEG encoding

MPEG 是 Moving Picture Experts Group 所制定的一系列影音壓縮標準。其壓縮通常會運用：

核心觀念

本題考查關聯式資料庫的基本關聯運算，重點是判斷如何從同一個關聯表中，依照屬性條件篩選出符合條件的元組。

關聯代數中的 選取（selection） 運算，以條件篩選資料表中的元組，記作：

本題要篩選出 gender 欄位值為 male 的男性員工，因此可表示為：

此運算會保留 Employee 中符合條件的元組，並產生只包含男性員工的新關聯表。

解題方法

題目要求的是：

• 資料來源：Employee 關聯表
• 篩選條件：gender = male
• 操作結果：只保留符合條件的員工元組

這是典型的「依條件篩選元組」問題，應使用關聯代數中的選取（selection）運算。

須注意：

• 選取運算是針對「元組」進行篩選。
• 投影（projection）運算則是選擇特定「屬性欄位」。
• 本題並非要刪除欄位，而是要依性別條件篩選員工資料。

因此正確選項為 (A) select。

選項分析

(A) select：正確

select 即選取運算，用來根據指定條件篩選關聯表中的元組。

本題可寫成：

結果只會包含 gender 欄位值為 male 的員工資料。

(B) intersection：錯誤

核心觀念

本題考查關聯式代數（relational algebra）中，不同集合運算與結合運算的基本條件。

兩個關係要進行 union、intersection、difference 等集合運算，通常必須符合「聯集相容」（union-compatible）：

1. 兩個關係的屬性數目相同。
2. 對應位置的屬性具有相容的資料型態或值域。
3. 屬性通常需能一一對應。

相較之下，join 是依據某些屬性間的關聯條件，將兩個關係中的資料列結合，兩個原關係不必具有完全相同的屬性集合。

解題方法

判斷關鍵在於區分：

• 集合運算：要求兩個關係結構相容。
• 結合運算：依條件配對資料，可整合不同結構的關係。

join 的結果通常包含來自兩個原關係的屬性。例如：

關係 $R(A,B)$ 與關係 $S(B,C)$ 可依據共同屬性 $B$ 進行自然結合：

結果關係可包含屬性：

可見 $R$ 與 $S$ 的屬性集合並不相同，但仍能透過共同屬性 $B$ 建立結合。因此，原關係屬性集合不需一致的是 join。

選項分析

(A) difference：錯誤

difference 是差集運算，表示找出出現在第一個關係、但未出現在第二個關係中的資料列：

由於必須逐列比較兩個關係，$R$ 與 $S$ 必須符合聯集相容條件，包含相同數目的屬性，且對應屬性值域相容。若屬性集合不一致，資料列無法直接比較。

(B) intersection：錯誤

核心觀念

本題考查三維陣列的元素總數與記憶體空間計算。

陣列範圍 $A[0:5, 3:10, 1:5]$ 表示三個維度的索引範圍皆包含起點與終點，因此各維度的元素數量為：

• 第一維：$5-0+1=6$
• 第二維：$10-3+1=8$
• 第三維：$5-1+1=5$

三維陣列的元素總數為各維度元素數量的乘積，再乘以每個元素所需的記憶體容量，即可得到總記憶體空間。

解題方法

第一步，計算三個維度的元素數量：

因此，陣列共有 $240$ 個元素。

第二步，每個元素需要 $4$ Bytes，故總記憶體需求為：

選項分析

• (A) 240 個位元組：錯誤。 $240$ 是陣列的元素總數，尚未乘上每個元素所需的 $4$ Bytes。

核心觀念

本題考查後置式（Postfix Expression，又稱逆波蘭表示法）的運算規則。

後置式的特徵是：

• 運算子寫在運算元之後。
• 遇到數值或變數時，先放入堆疊。
• 遇到運算子時，從堆疊取出兩個運算元：
• 先取出的為右運算元。
• 後取出的為左運算元。
• 計算結果再放回堆疊。

已知：

解題方法

逐一將後置式轉換為中置式，再計算其結果。後置式中，運算子的作用對象是它前方最近且尚未使用的兩個運算元或運算結果。

選項分析

(A) $ij+k*$

先處理 $i$ 與 $j$：

再與 $k$ 相乘：

代入數值：

因此，選項 (A) 的結果為：

(B) $ijk*+$

先處理 $j$ 與 $k$ 的乘法：

再與 $i$ 相加：

代入數值：

因此，選項 (B) 的結果為：

(C) $ij*k+$

核心觀念

佇列（Queue）遵循「先進先出」（FIFO, First In First Out）原則：

• 元素從佇列的末端加入，稱為入佇列（Enqueue）。
• 元素從佇列的前端移除，稱為出佇列（Dequeue）。

以鏈結串列實作時，通常將：

• 鏈結串列開頭視為佇列前端（Front）
• 鏈結串列末尾視為佇列末端（Rear）

因此，新元素應插入鏈結串列的末尾。

解題方法

假設佇列原本為：

$A \rightarrow B \rightarrow C$

其中 $A$ 是佇列前端，$C$ 是佇列末端。若加入新元素 $D$，為維持先進先出原則，應形成：

$A \rightarrow B \rightarrow C \rightarrow D$

如此一來，原先進入的 $A$ 仍然最先被取出，新加入的 $D$ 排在最後，符合 Queue 的定義。

因此，新元素應插入鏈結串列的末尾，正確選項為 (B)。

若鏈結串列額外維護指向末尾節點的 rear 指標，插入末尾可在 $O(1)$ 時間完成；若未維護 rear 指標，則必須從開頭走訪至末尾，時間複雜度為 $O(n)$。

選項分析

核心觀念

本題考查圖形資料結構中的廣度優先搜尋（Breadth-first search，BFS）。

BFS 從起點開始，依照「距離起點的層級」逐層訪問：

• 第 0 層：起點 $A$
• 第 1 層：由 $A$ 直接連出的節點
• 第 2 層：由第 1 層節點延伸出的節點

BFS 使用佇列（Queue），遵守先進先出（FIFO）原則。因此，所有距離起點較近的節點，必須先於距離較遠的節點被訪問。

由圖可得主要有向邊：

• $A \to B,D,G$
• $B \to C$
• $D \to C,E$
• $G \to F$
• $E \to F$

所以各節點距離 $A$ 的層級為：

同一層內的訪問順序，則可能因鄰接節點排列順序不同而有所變化。

解題方法

若依照 $A$ 的鄰接節點順序 $B,D,G$ 進行 BFS：

1. 先訪問 $A$，將 $B,D,G$ 放入佇列。
2. 訪問 $B$，發現尚未訪問的 $C$，將 $C$ 加入佇列。
3. 訪問 $D$，$C$ 已被發現，不能重複加入；再將 $E$ 加入佇列。
4. 訪問 $G$，將 $F$ 加入佇列。
5. 依序訪問佇列中的 $C,E,F$。

因此訪問順序為：

即：

選項分析

• (A) ABCDEFG：錯誤

核心觀念

本題比較「一般樹」與「左子右兄弟樹（Left child-right sibling, LCRS）」的指標表示法。

• 一般樹：每個節點可直接連結其所有子節點。
• 左子右兄弟樹：每個節點通常以兩個主要指標表示：
• left-child：指向最左邊的子節點。
• right-sibling：指向下一個兄弟節點。

因此，LCRS 能以固定數量的指標表示任意度數的樹，但代價是同一層的兄弟節點必須沿著兄弟鏈逐一走訪。

解題方法

判斷各選項時，分別比較兩種結構的：

1. 指標欄位是否會浪費空間。
2. 從節點走到根節點所需的指標走訪次數。
3. 判斷兩節點是否具有父子關係的難易度。
4. 查詢父子關係時的效率。

LCRS 的優點是每個節點使用固定數量的指標；但在查找特定子節點、兄弟節點或確認父子關係時，可能必須沿著兄弟鏈逐一檢查，因此不一定比一般樹有效率。

選項分析

(A) 正確

一般樹若使用固定個數的欄位儲存子節點指標，必須預先決定每個節點可容納的子節點數量。

例如設定每個節點保留 $k$ 個子指標，但某些節點實際上只有一、兩個子節點，剩餘欄位便會閒置，造成空間浪費。

因此，選項所述「容易造成空間的浪費」正確。

(B) 正確

在一般樹中，從節點沿著父指標往根節點移動，每一層通常只需走訪一個父子連結。

LCRS 雖然能表示父子關係，但節點在樹中的實際位置可能需要透過左子指標與右兄弟指標逐層尋找。尤其當目標節點不是某父節點的最左子節點時，必須沿著兄弟鏈移動後，才能找到對應的父子關係。

核心觀念

本題考查無向圖的「握手定理」（Handshaking Lemma）：

其中，$\deg(v)$ 表示頂點 $v$ 的分支度，$|E|$ 表示圖中邊的數量。每一條無向邊都連接兩個端點，因此會對兩個頂點的分支度各貢獻 $1$，使所有頂點分支度的總和必為偶數。

由此可推出：無向圖中，具有奇數分支度的頂點個數必為偶數。

解題方法

直接套用握手定理即可。由於

右側是 $2$ 的倍數，因此左側必為偶數。

將所有頂點分成兩類：

• 偶數分支度頂點：其分支度總和為偶數。
• 奇數分支度頂點：若有 $k$ 個，這些奇數相加的奇偶性會與 $k$ 相同。

整體分支度總和必為偶數，所以奇數分支度頂點的數量 $k$ 必須是偶數。

選項分析

(A) 具有奇數分支度的頂點個數是奇數

錯誤。根據握手定理，具有奇數分支度的頂點個數必為偶數，不可能是奇數。

例如一條邊連接兩個頂點時，兩個頂點的分支度都是 $1$，奇數分支度頂點共有 $2$ 個。

核心觀念

本題考查二元搜尋法（Binary Search）的搜尋效率。

二元搜尋法適用於「資料已經排序」的情況，每次比較都檢查中間位置的資料，並依比較結果排除約一半的搜尋範圍。因此，搜尋範圍大小每次大約減半，最差比較次數為對數級 $O(\log_2 n)$，而不是逐筆檢查的 $O(n)$。

解題方法

資料共有 $n=100$ 筆。二元搜尋法每比較一次，搜尋範圍約縮小為原來的一半。

可用二元搜尋樹的節點數估算：若最多進行 $x$ 次比較，最多可以涵蓋的資料筆數為

要涵蓋 100 筆資料，必須滿足

因此

由於

所以最差情況最多需要

次比較。

即使採用不同的中間位置取法或整數除法規則，最差比較次數仍會落在 7 次左右，必定小於 10 次。因此官方答案為 (A)。

核心觀念

本題考「線上排序」（online sorting）與「離線排序」的差異。

• 線上排序：資料尚未全部到齊時，資料可逐筆進入，演算法能立即將新資料整合至目前的排序結果。
• 離線排序：通常必須先取得完整資料集合，再進行排序。

題目描述「可能來自網路一次送來一個資料」，重點是資料以逐筆方式到達，因此需要能夠動態維持排序結果的演算法。

**Insertion sort（插入排序法）**可以先將已收到的資料維持排序，新的資料到達後，再將它插入適當位置，因此最符合題意。

解題方法

假設資料依序到達：

使用 Insertion sort 的處理方式如下：

1. 收到 $7$：目前排序結果為 $[7]$。
2. 收到 $3$：將 $3$ 插入 $7$ 前方，成為 $[3,7]$。
3. 收到 $9$：將 $9$ 插入尾端，成為 $[3,7,9]$。
4. 收到 $2$：將 $2$ 插入最前方，成為 $[2,3,7,9]$。

每當一筆新資料到達，只需將它插入目前已排序的序列，不必等待所有資料完整蒐集後才開始處理。

因此，最適合的選項是 Insertion sort。

選項分析

(A) Insertion sort

正確。

Insertion sort 的核心作法是：

1. 將資料分成「已排序區」與「尚未處理區」。
2. 每次取出一筆新資料。
3. 在已排序區中尋找適當位置。
4. 將資料插入該位置。

因此，它可以隨著資料逐筆到達，持續維持目前的排序結果，適合處理尚未完整蒐集的資料。

其一般時間複雜度如下：

• 最佳情況：$O(n)$
• 平均情況：$O(n^2)$
• 最壞情況：$O(n^2)$
• 額外空間：$O(1)$

本題著重的是「資料可逐筆輸入」的特性，不是單純比較所有排序法的平均效率。

(B) Quick sort

錯誤。

核心觀念

二元搜尋樹（Binary Search Tree, BST）必須符合：

• 每一節點左子樹的所有鍵值均小於該節點。
• 每一節點右子樹的所有鍵值均大於該節點。
• 此規則須對每個節點遞迴成立。

本題圖中的數字即為節點鍵值，判斷各圖是否符合上述大小關係。

解題方法

由根節點開始，檢查左右子節點及其子樹是否符合大小規則：

• 左側必須小於根節點。
• 右側必須大於根節點。
• 子樹中的節點也必須同時符合祖先節點的限制。

選項分析

(A)

根節點為 $8$，其左子節點為 $1$，右子節點為 $5$。

雖然 $1<8$，但右子節點應大於 $8$，實際上：

$5<8$

因此節點 $5$ 位於 $8$ 的右子樹卻小於 $8$，違反二元搜尋樹定義。故 (A) 不是二元搜尋樹。

(B)

根節點為 $8$，右子節點為 $9$，符合：

$9>8$

核心觀念

循序搜尋（Sequential Search）是按照資料排列順序，從第 1 個數字開始逐一比較，直到找到目標數字為止。

題目問的是「成功搜尋」時的平均比較次數。假設特定數字出現在 $n$ 個位置中的機率相同，則：

• 出現在第 $1$ 個位置：比較 $1$ 次
• 出現在第 $2$ 個位置：比較 $2$ 次
• $\cdots$
• 出現在第 $n$ 個位置：比較 $n$ 次

解題方法

所有可能的比較次數為 $1,2,3,\ldots,n$，因此平均比較次數為等差數列平均值：

也可由總和除以可能位置數得到：

因此正確答案為 $(n+1)/2$。

選項分析

• (A) $n$：錯誤。 $n$ 是目標數字位於最後一個位置時的比較次數，代表最壞情況，不是平均比較次數。

核心觀念

本題考查 C 語言的位元運算：

• &：位元 AND（位元且）
• |：位元 OR（位元或）
• ^：位元 XOR（位元互斥或）

將整數視為二進位的每一個位元逐位運算：

題目給定：

解題方法

逐一將 $x$ 與選項中的常數進行位元運算，觀察運算結果是否仍等於 $100$。

選項分析

(A) x&0

因此：

結果由 $100$ 變成 $0$，不等於原本的 $x$，故本選項錯誤。

(B) x|1

將 $1$ 寫成二進位：

進行 OR 運算：

而：

因此：

結果不等於 $100$，故本選項錯誤。

(C) x^0

XOR 與 $0$ 運算時，每一位元都保持原值：

核心觀念

本題考查 C++ 的四項基本技術：

• Inheritance（繼承）：衍生類別取得基底類別的成員。
• Encapsulation（封裝）：將資料與操作資料的函式包裝在類別中，並透過 private、public 等權限控制存取。
• Overriding（覆寫）：衍生類別重新定義基底類別中具有相同介面的方法。
• Template（樣板）：以型別參數化的通用程式設計，例如 template <class T>。

題目要求判斷程式中「未使用」的技術。

解題方法

直接逐一對照程式碼中的語法與各技術定義：

1. 是否有類別繼承語法？
2. 是否有資料封裝與存取權限？
3. 是否有衍生類別重新定義基底類別函式？
4. 是否出現 template 宣告或樣板參數？

程式中：

class B : A

表示 B 繼承自 A。

類別 A 將成員分成：

private:
 int x;
public:
 int y;
 int get(void) {return x;}

表示資料成員與函式被包裝在類別中，並透過存取權限控制，因此具有封裝概念。

類別 B 再定義一個同名的 get 函式：

int get(void) {return y+2;}

依本題命題慣例，視為衍生類別重新定義基底類別函式，具有覆寫概念。

程式中沒有任何 template 宣告、型別參數或樣板類別，因此未使用樣板技術。

選項分析

(A) inheritance：錯誤選項

程式中的：

class B : A

表示類別 B 繼承類別 A，因此使用了繼承技術。

補充而言，class B : A 未明確寫出繼承權限。由於 B 是 class，預設採用 private inheritance。基底類別 A 的 public 成員在 B 中會轉為 private，但在 B 的成員函式內仍可存取 y。

(B) encapsulation：錯誤選項

類別 A 將資料成員與相關函式集中在同一個類別中，並使用：

private:
 int x;

核心觀念

本題考查 C 語言 for 迴圈的執行順序、break 敘述，以及餘數運算子 %。

for 迴圈每次執行順序為：

1. 判斷條件
2. 執行迴圈本體
3. 執行遞增敘述 i++
4. 回到條件判斷

當 i % 5 == 0 成立時，執行 break，立即結束迴圈，後續敘述不再執行。

解題方法

初始值為：

逐次計算如下：

當 $i=5$ 時，因為：

程式直接執行 break，因此不會執行：

count *= (i+1);

所以迴圈結束後：

之後執行主程式最後的：

printf("%d", count);

輸出值仍為 120。

核心觀念

本題考查 C/C++ 的 switch 選擇結構，重點包括：

1. switch(a) 會依照 a 的值尋找相同的 case 標籤。
2. 找到符合的 case 後，會從該處開始依序執行後續敘述。
3. case 本身不會自動形成區塊，也不會在執行完後自動跳出。
4. 必須使用 break 才能離開 switch 結構。

程式碼中各個 case 之間都沒有 break，因此會發生「貫穿執行」（fall-through）。

解題方法

初始值為：

程式執行 switch(a) 時，尋找與 $a$ 值相同的標籤，因此從：

case 2: printf("2#");

開始執行。

由於後面沒有 break，執行流程會繼續往下：

case 3: printf("3#");
default: printf("0#");

因此輸出順序為：

1. case 2 輸出 2#
2. case 3 輸出 3#
3. default 輸出 0#

完整輸出為：

2#3#0#

選項分析

• (A) 2#：錯誤

核心觀念

霍夫曼編碼（Huffman coding）是一種以「不等長編碼」降低平均編碼長度的無失真資料壓縮方法，基本原則如下：

• 出現頻率越高的符號，編碼長度越短。
• 出現頻率越低的符號，編碼長度越長。
• 建構霍夫曼樹時，每次合併頻率最小的兩個節點。
• 最終根節點至各符號葉節點的邊數，就是該符號的 code 長度。

本題四種符號的頻率為：

解題方法

依頻率由小到大排列：

每次取出頻率最小的兩個節點合併：

1. 合併 $D(6)$ 與 $A(7)$：

此時節點為：

2. 合併 $B(12)$ 與 $(D,A)(13)$：

此時節點為：

3. 合併 $25$ 與 $C(30)$，形成根節點：

霍夫曼樹的結構可表示為：

核心觀念

本題考查 C 語言的「遞迴函數」與階乘運算。

函數定義如下：

int f (int x){
 if (x <= 1) return 1;
 else return (x * f(x-1));
}

當 $x \leq 1$ 時，函數直接回傳 $1$，此條件稱為遞迴的「終止條件」或「基底條件」。

當 $x>1$ 時，函數回傳：

這正是階乘的遞迴定義，因此：

解題方法

題目要求計算 $f(4)$，依照函數呼叫關係逐層展開：

因為 $1\leq 1$，符合終止條件：

所以：

因此函數回傳值為 $24$。

選項分析

• (A) 1：錯誤

核心觀念

本題考查 C 語言的：

1. 遞迴函式執行順序。
2. 整數除法 $n/2$ 的結果。
3. 餘數運算子 $n\%2$。
4. 遞迴呼叫返回後，才執行後續的 putchar。

程式中的：

f(n/2);
putchar('0'+n%2);

表示必須先完成 f(n/2)，返回後才輸出目前這一層的位元。

解題方法

依照呼叫順序展開：

第 1 層：f(4)

因為 $4\neq 0$，先呼叫：

f(4/2) = f(2)

暫時不輸出。返回後輸出：

第 2 層：f(2)

因為 $2\neq 0$，先呼叫：

f(2/2) = f(1)

暫時不輸出。返回後輸出：

第 3 層：f(1)

因為 $1\neq 0$，先呼叫：

f(1/2) = f(0)

在 C 語言整數除法中：

第 4 層：f(0)

此時條件 n != 0 不成立，函式直接返回，不輸出任何字元。

接著依照遞迴返回順序輸出：

• f(1) 輸出 $1$
• f(2) 輸出 $0$
• f(4) 輸出 $0$

因此輸出為：

遞迴呼叫與輸出順序

可整理如下：

核心觀念

本題考查 Python 的：

• List（串列）索引：索引從 $0$ 開始。
• 串列元素交換。
• 多重指定（multiple assignment）。
• 函式接收串列後，直接修改原串列內容。

程式中的串列為：

input = [10, 20, 30]

其索引位置如下：

解題方法

呼叫函式：

unknown(input, 0, 1)

因此：

• p1 = 0
• p2 = 1

函式中的敘述為：

input[p1], input[p2] = input[p2], input[p1]

代入索引後：

input[0], input[1] = input[1], input[0]

原本：

input[0] = 10
input[1] = 20

交換後：

input[0] = 20
input[1] = 10

索引 $2$ 的元素不受影響，仍為 $30$，所以串列變為：

核心觀念

本題考查三個 C++ 基本觀念：

1. B 公開繼承 A，因此 B 的物件可以使用：

• B 自己的成員函式 FB
• 從 A 繼承而來的成員函式 FA

2. 函式呼叫會直接執行函式內的 return 運算式。

3. input 是 int 型別，因此 input/3 與 input/4 進行的是整數除法；運算結果再轉換成函式宣告的 float 回傳值。

解題方法

main 中建立：

B object1;

由於 B 公開繼承 A，所以 object1 同時可以呼叫 FB 與繼承自 A 的 FA。

先計算：

object1.FB(12)

FB 的定義為：

float FB (int input) {return input/4;}

代入 input = 12：

因此：

object1.FB(12)

輸出為 3。

再計算：

object1.FA(12)

FA 的定義為：

float FA (int input) {return input/3;}

代入 input = 12：

因此：

object1.FA(12)

輸出為 4。

cout 的完整敘述為：

核心觀念

本題考查 C++ 中：

1. 區域變數與資料成員同名時的「名稱遮蔽」。
2. this 指標對物件資料成員的存取。
3. 函式內區域變數的作用域與回傳值判定。

在成員函式中，若宣告區域變數 me，它會遮蔽同名的資料成員 me。因此：

• me 代表區域變數。
• this->me 明確代表目前物件的資料成員。

解題方法

程式碼如下：

int getMe {
 int me = 5;
 this->me = 10;
 return me;
}

依執行順序分析：

1. int me = 5;

宣告一個區域變數 me，其值為 $5$。

2. this->me = 10;

透過 this->me 指定目前物件的資料成員 me 為 $10$。

此時：

• 區域變數 `me = 5$
• 物件資料成員 `this->me = 10$

3. return me;

return 後未使用 this->，因此此處的 me 是區域變數，回傳值為 $5$。

所以：

核心觀念

本題考查網路設備的功能，以及 NAT（Network Address Translation，網路位址轉換）如何解決 IPv4 位址不足問題。

在一般區域網路中，多部主機會使用私有 IP 位址，例如：

• 192.168.x.x
• 172.16.x.x 至 172.31.x.x
• 10.x.x.x

這些私有 IP 位址無法直接在公用網際網路中路由。NAT 設備會在內部私有 IP 與外部公用 IP 之間進行轉換，使多部內部主機能共用同一個公用 IP 位址連接網際網路。

實務上常使用 PAT（Port Address Translation），也稱 NAPT，除了轉換 IP 位址外，也利用不同的通訊埠號辨識各個連線。

例如：

雖然主機甲與主機乙對外使用同一個公用 IP 位址 203.0.113.5，NAT 仍可透過不同的埠號區分兩條連線。

解題方法

題幹的關鍵語句是「多個節點共用一個 IP 位址」。

判斷各設備功能如下：

1. 能否在內部與外部網路間轉換 IP 位址？
2. 能否使多個內部節點共用一個公用 IP？
3. 是否只是負責路由、配置位址或建立加密通道？

符合「多個內部節點共用一個公用 IP 位址」功能的設備，就是 NAT。

因此本題選擇：

選項分析

(A) VPN（Virtual Private Network）伺服器

VPN 伺服器主要功能是建立虛擬私有網路通道，通常提供：

• 遠端使用者安全連線
• 資料加密與身分驗證
• 內部網路資源存取
• 不同網路間的虛擬連線

核心觀念

本題考查 OSI 七層模型中各層的主要功能，關鍵字是：

• 「網路位址」
• 「決定路由（Routing）」

OSI 模型的**網路層（Network Layer）**負責在不同網路之間傳遞資料，主要工作包括：

1. 建立邏輯位址，例如 IP 位址。
2. 根據目的地位址選擇資料傳送路徑。
3. 進行封包（Packet）的轉送與路由選擇。
4. 處理不同網路間的互連。

路由器（Router）主要依據網路層的邏輯位址與路由表，決定封包應從哪一條路徑轉送，因此「位址」與「Routing」同時出現時，應優先判斷為網路層。

解題方法

依照題幹中的兩個功能逐一對照：

• 網路的位址：指 IP 等邏輯位址。
• 決定網路路由：指依目的地網路選擇封包傳送路徑。

這兩項均屬於 OSI 的網路層功能，因此選擇網路層。

在資料傳輸單位方面，網路層的資料通常稱為「封包（Packet）」；網路層設備則以路由器為代表。

選項分析

(A) 傳輸層（Transport Layer）錯誤

傳輸層負責端點到端點的資料傳輸，常見功能包括：

• 分割與重組資料。
• 流量控制。
• 錯誤控制與可靠傳輸。
• 連接管理。
• 依連接埠號（Port Number）識別應用程式。

TCP 與 UDP 均屬於傳輸層協定。傳輸層使用的是連接埠號，例如 TCP Port 80、UDP Port 53，並不負責依 IP 位址決定網路路由。

(B) 資料連結層（Data Link Layer）錯誤

資料連結層負責同一個區域網路或相鄰節點之間的資料傳輸，主要功能包括：

核心觀念

本題考查雙絞線（Twisted-Pair）的結構、抗干擾原理、網路拓樸，以及其在網路架構中的典型用途。

雙絞線是由兩條外層絕緣的銅導線，以固定節距相互纏繞而成。常見種類包括：

• UTP：非遮蔽雙絞線（Unshielded Twisted-Pair）
• STP：遮蔽雙絞線（Shielded Twisted-Pair）

雙絞線廣泛用於電話線路及乙太網路區域網路，但單一網路線段的傳輸距離通常受到標準與訊號衰減限制，例如一般乙太網路雙絞線單段常見上限約為 $100$ 公尺。因此，雙絞線通常用於使用者端至交換器之間的水平佈線，不是長距離網路骨幹的主要媒介。

解題方法

判斷本題的關鍵，在於分辨：

1. 雙絞線的基本結構是否正確。
2. 雙絞線的抗干擾原理是否正確。
3. 雙絞線能否配合網路設備形成星狀拓樸。
4. 雙絞線是否適合長距離傳輸並通常作為骨幹線路。

前三項皆符合雙絞線的特性，只有選項 A 將雙絞線描述成適合長距離傳輸、通常作為網路骨幹，與一般網路工程的典型用途不符，因此依官方答案選 A。

選項分析

(A) 適合長距離傳輸，因此通常為網路骨幹線路使用

錯誤。

雙絞線雖然成本低、施工容易，且適合一般區域網路使用，但其傳輸距離受到訊號衰減、電磁干擾及乙太網路標準的限制。以常見的乙太網路雙絞線為例，單段長度通常約為 $100$ 公尺。

網路骨幹需要連接不同樓層、不同建築物或較遠距離的網路設備，通常會優先採用光纖，因為光纖具有：

• 傳輸距離長
• 頻寬高
• 不受電磁干擾影響
• 適合樓層間及建築物間的主幹連接

因此，「適合長距離傳輸，因此通常為網路骨幹線路使用」不是雙絞線的典型特性，故 A 錯誤。

(B) 由兩條包覆的銅線相互纏繞之通訊傳輸媒介

正確。

核心觀念

本題考查 OSI 七層模型中「網路層（Network Layer）」的功能與服務特性。

網路層主要負責：

• 邏輯位址，例如 IP 位址。
• 路由選擇與封包轉送。
• 跨越不同網路傳遞資料。
• 封包分割與重組等功能。

在一般 IP 網路中，網路層採用「盡力傳送（Best-Effort Delivery）」方式，通常不保證：

• 封包一定抵達目的地。
• 封包不會損壞。
• 封包一定按照傳送順序抵達。
• 封包不會重複。

因此，網路層的封包傳送屬於不可靠傳送。

解題方法

判斷本題各選項時，先確認敘述所描述的功能屬於哪一層：

• Ethernet 的實體傳輸與訊框規格，主要屬於資料鏈結層。
• 封包路由與跨網路傳送，屬於網路層。
• 傳輸順序、可靠傳輸與錯誤控制，主要由傳輸層處理。
• UDP 雖然是不可靠協定，但它屬於傳輸層，不是網路層。

網路層只負責將封包盡力送往目的地，並不負責完整可靠性保證，所以正確選項為 (C)。

選項分析

(A) 錯誤

乙太網路（Ethernet）主要定義區域網路中的訊框格式、MAC 位址、媒體存取控制及資料鏈結層相關規格，並涉及實體層的傳輸媒介與訊號規範。

網路層使用 Ethernet 作為下層網路技術之一，但並非由網路層定義 Ethernet 的相關規格。因此本選項將資料鏈結層、實體層功能誤歸於網路層。

(B) 錯誤

網路層通常採用獨立封包傳送方式，每個封包可依當時的網路狀況選擇路徑。不同封包所經過的路由可能不同，因此封包抵達目的地時，順序不一定與傳送順序相同。

核心觀念

本題考查 CIDR 的子網路遮罩與網域範圍判定。

IP 位址 123.32.226.14/22 中，/22 表示：

• 網路部分：前 22 位元
• 主機部分：後 10 位元
• 子網路遮罩為：

第三個八位元組的遮罩值為 $252$，因此每個網域在第三個八位元組的區間大小為：

解題方法

將第三個八位元組依每 4 個數字劃分：

題目 IP 的第三個八位元組為 $226$，落在 $224\sim227$ 區間，因此：

• 網路位址：$123.32.224.0$
• 廣播位址：$123.32.227.255$
• 網域範圍：

凡是第三個八位元組介於 $224$ 至 $227$ 的 IP 位址，都屬於 123.32.226.14/22 網域。

選項分析

(A) 123.32.228.14

核心觀念

本題考查常見網際網路應用與網路診斷工具的功能：

• Streaming（串流）：影音資料以連續資料流方式傳送，接收端取得一部分資料並進行緩衝後即可播放，不必等待完整檔案下載完成。
• 社群網站平台：提供使用者建立帳號、發布內容、互動與社交功能的平台。
• tcpdump：封包擷取與分析工具，用於監看網路介面傳送與接收的封包。
• nslookup：透過 DNS 查詢網域名稱與 IP 位址的對應關係。
• 連接埠與服務探測：通常使用 nmap 等掃描工具，判斷主機開啟的連接埠及其服務。

解題方法

先辨識各工具的主要用途，再檢查選項是否把工具功能張冠李戴：

1. 影音串流是否能在完整下載前播放。
2. Facebook、Twitter 是否屬於社群網站。
3. tcpdump 是否具有連接埠與服務掃描功能。
4. nslookup 是否用於 DNS 查詢。

其中只有選項 C 將封包分析工具誤認為連接埠及服務探測工具，因此選 C。

選項分析

(A) 正確

YouTube 等網路影音平台使用串流技術傳送影音資料。影片通常會分成許多資料片段，播放器先接收一部分資料並存入緩衝區，達到播放條件後即可開始播放。

因此，使用者不必等到整部影片完整下載完畢，便能一邊接收、一邊播放。串流搭配緩衝機制，也有助於維持播放的連續性與流暢度。

(B) 正確

Facebook 與 Twitter 都提供使用者建立個人帳號、發布文字或多媒體內容、追蹤其他使用者及互動交流，屬於社群網站平台。

(C) 錯誤

核心觀念

本題考查 TLS 數位憑證的功能、內容與憑證信任機制。

數位憑證主要由憑證頒發機構（Certificate Authority, CA）簽發，用來：

1. 證明網站或伺服器的身分。
2. 綁定網站網域名稱與其公鑰。
3. 讓瀏覽器透過 CA 的信任鏈驗證憑證是否可信。
4. 在憑證失效或私鑰外洩時，提供撤銷機制。

數位憑證通常包含網站名稱、網域名稱、公鑰、有效期限、簽發者及 CA 的數位簽章等資訊，但不包含網站的私鑰。

解題方法

逐一檢查各選項是否符合數位憑證的基本特性：

• 自簽憑證是否具有與 CA 憑證相同的身分信任？
• 憑證內是否同時存放公鑰與私鑰？
• CA 是否能撤銷自己簽發的憑證？
• 略過瀏覽器憑證警告是否會影響安全性？

其中只要符合憑證管理機制的選項，即為正確答案。

選項分析

(A) 錯誤

自簽憑證是由憑證持有人自行簽署，沒有受到受信任 CA 的第三方驗證。

自簽憑證仍可用於加密傳輸，但瀏覽器無法藉由公開信任鏈確認該憑證確實屬於目標網站。因此，自簽憑證與受信任 CA 所簽發的憑證，在身分驗證與信任程度上並不具有相同安全性。

例如，攻擊者可以自行建立一張宣稱屬於某網站的自簽憑證，瀏覽器無法透過 CA 信任鏈判定其真偽。

(B) 錯誤

數位憑證中包含網站的公鑰，但不包含私鑰。

公鑰必須公開，供他人驗證數位簽章或建立加密連線；私鑰則必須由網站或憑證持有人秘密保存。若私鑰被放入憑證並公開傳送，任何人都能取得私鑰，將使加密與身分驗證失去安全性。

因此，正確關係是：

核心觀念

雜湊函數（Hash Function）是將任意長度的輸入資料，經由固定演算法轉換成固定長度的摘要值（Message Digest）。密碼學安全雜湊函數通常應具備下列特性：

1. 單向性（One-way Property）：由輸入資料計算雜湊值容易，但由雜湊值反推出原始資料，在計算上不可行。
2. 抗碰撞性（Collision Resistance）：難以找到兩個不同的輸入 $M_1 \ne M_2$，卻具有相同的雜湊值：

3. 抗第二原像攻擊（Second-preimage Resistance）：給定一個輸入 $M_1$，難以找出另一個不同輸入 $M_2$，使得：

雜湊函數本身通常不使用金鑰，主要用於資料完整性檢查、密碼儲存及數位簽章中的摘要運算。

解題方法

本題可從「雜湊函數的定義」及「與其他密碼技術的區別」切入：

• 判斷敘述是否描述雜湊函數的基本安全性質。
• 檢查是否將雜湊函數與對稱式加密、訊息驗證碼或數位簽章混淆。
• 特別注意「資料完整性」與「資料來源驗證」並不相同。

符合密碼學安全雜湊函數基本要求的敘述，即為正確選項。

選項分析

(A) 正確

安全的雜湊函數應具有單向性，使攻擊者難以由摘要值反推出原始訊息；同時也應具備抗碰撞性，使攻擊者難以找出兩個不同訊息產生相同摘要值。

因此，選項所述的「單向函數特性」及「抵抗碰撞攻擊」皆屬於密碼學安全雜湊函數的重要性質，故本選項正確。

(B) 錯誤

AES 與 SHA 的用途及類型不同：

• AES（Advanced Encryption Standard） 是對稱式區塊加密演算法，使用金鑰進行加密與解密。