高雄醫學大學 113 年 《計算機概論與程式設計》

核心觀念

Virtualization（虛擬化）是利用軟體、韌體與硬體支援，將一台實體電腦的運算資源抽象化，分割成多個彼此獨立的虛擬環境。

負責管理實體硬體並建立虛擬機器的軟體稱為 Hypervisor（虛擬機器監控器）。每個虛擬機器（Virtual Machine, VM）都能配置自己的：

• 作業系統
• 虛擬 CPU
• 虛擬記憶體（RAM）
• 虛擬硬碟
• 虛擬網路介面卡

因此，同一台實體機器能同時執行不同作業系統，例如 Windows、Linux 與 macOS 的虛擬環境。

解題方法

本題採用「逐項比對虛擬化的功能與限制」的方法判斷。

判斷重點有三項：

1. 虛擬化不只存在於軟體層，也涵蓋硬體、儲存設備、網路等層面。
2. 虛擬化通常會增加管理與轉譯所需的資源，不是減少執行程式所需的計算資源。
3. 虛擬化的核心效果是資源抽象化、隔離與多工共享，使一台實體機器能形成多台邏輯機器。

選項分析

(A) Virtualization is only applicable on software layer.

錯誤。

虛擬化並非只適用於軟體層。常見類型包括：

• Server virtualization：將一台實體伺服器切分成多台虛擬伺服器。
• Storage virtualization：將多個實體儲存設備整合成單一邏輯儲存空間。
• Network virtualization：建立虛擬交換器、虛擬網路、VLAN、VPN 等。
• Hardware-assisted virtualization：利用 CPU 的 Intel VT-x、AMD-V 等硬體功能支援虛擬機器。

所以，虛擬化涉及軟體、硬體與基礎設施多個層面。

(B) Virtualization takes less computing resources to run programs.

錯誤。

虛擬化需要額外的資源管理與硬體指令轉譯，因此通常會產生一定的效能負擔，例如：

• Hypervisor 需要分配 CPU、記憶體與 I/O 資源。
• 虛擬機器的指令執行可能需要額外轉譯。
• 虛擬硬碟與虛擬網路需要額外的 I/O 管理。

現代處理器提供硬體虛擬化支援後，效能損失可大幅降低，但不能因此說虛擬化「需要較少計算資源」。虛擬化的主要優點是提高資源利用率、隔離環境與方便管理，而非降低單一程式的基本運算需求。

核心觀念

本題考查電腦架構中的「管線化」（pipelining）。

管線化是將一條指令的執行工作切分成多個階段，使不同指令可以同時處於不同階段中。典型的五級管線包括：

1. IF（Instruction Fetch）：擷取指令
2. ID（Instruction Decode）：解碼並讀取暫存器
3. EX（Execute）：執行運算或計算位址
4. MEM（Memory Access）：存取資料記憶體
5. WB（Write Back）：將結果寫回暫存器

例如，當指令 $I_1$ 在 EX 階段執行時，指令 $I_2$ 可同時在 ID 階段解碼，指令 $I_3$ 則可在 IF 階段擷取。

因此，管線化的重點不是讓「單一指令」執行得更快，而是讓多條指令的不同執行階段彼此重疊，以提高整體指令完成率，也就是 throughput（吞吐量）。

---

解題方法

判斷管線化的關鍵是尋找以下概念：

• 多條指令同時執行
• 指令處於不同的執行階段
• 各階段彼此重疊
• 提高處理器的整體吞吐量

若沒有管線化，三條指令各需經過五個階段，必須依序完成：

$$I_1: IF \rightarrow ID \rightarrow EX \rightarrow MEM \rightarrow WB$$ $$I_2: IF \rightarrow ID \rightarrow EX \rightarrow MEM \rightarrow WB$$ $$I_3: IF \rightarrow ID \rightarrow EX \rightarrow MEM \rightarrow WB$$

若每一階段耗時一個時脈週期，未採用管線化時，三條指令約需：

$$3 \times 5 = 15$$

個時脈週期。

採用五級管線後，執行情形如下：

時脈週期	第 1 條指令	第 2 條指令	第 3 條指令
1	IF
2	ID	IF
3	EX	ID	IF
4	MEM	EX	ID
5	WB	MEM	EX
6		WB	MEM
7			WB

三條指令只需約：

$$5 + (3-1) = 7$$

個時脈週期即可完成。當指令數量增加時，理想情況下每個時脈週期可完成一條指令，吞吐量大幅提升。

---

選項分析

(A) Pipelining refers to the movement of data between memory and the processor.

錯誤。

記憶體與處理器之間搬移資料，主要涉及資料傳輸、記憶體存取與匯流排運作，並不是管線化的定義。管線化著重於將指令執行切分為多個階段，並讓多條指令的階段重疊進行。

---

(B) Pipelining involves the parallel execution of instructions within a single stage.

錯誤。

核心觀念

本題考查有號數（signed number）與無號數（unsigned number）的表示方式。

• **Unsigned numbers（無號數）**沒有符號位元，所有位元都用來表示數值，因此只能表示 $0$ 與正整數。
• **Signed numbers（有號數）**會保留 1 個位元表示正負號，通常是最高有效位元（Most Significant Bit, MSB），其餘位元表示數值；現代電腦多採用二補數（two’s complement）表示負數。

若使用 $n$ 位元：

無號數的表示範圍為

$$0 \sim 2^n-1$$

採用二補數的有號數表示範圍為

$$-2^{n-1} \sim 2^{n-1}-1$$

因此，在位元數相同時，無號數能表示較大的正數；有號數則能同時表示正數、零與負數。

---

解題方法

判斷本題可掌握三個重點：

1. 有號數需要符號位元表示正負。
2. 符號位元通常位於最高有效位元，而不是最低有效位元。
3. 無號數沒有符號位元，全部位元都用於表示數值。

符合上述定義的選項即為正確答案。

---

選項分析

(A) 錯誤

選項將 signed 與 unsigned 的定義顛倒。

無號數只能表示正數與零，不能表示負數；有號數才能表示正數與負數。

---

(B) 錯誤

有號數確實使用一個 sign bit 表示正負，但該位元通常位於最高有效位元，不是 least significant position（最低有效位置）。

核心觀念

本題考查管線化 CPU 中三個概念的交互作用：

1. 平行處理（parallelism）
   管線將指令分成多個階段，例如：

$\text{IF} \rightarrow \text{ID} \rightarrow \text{EX} \rightarrow \text{MEM} \rightarrow \text{WB}$

不同指令可同時處於不同階段，以提高指令吞吐量。

2. 管線危障（pipeline hazards）
   當指令重疊執行造成衝突，使下一個時脈週期無法安全執行時，稱為危障，主要包括：

• Data hazard：資料相依造成的衝突。
• Control hazard：分支、跳躍或例外改變控制流程造成的衝突。
• Structural hazard：多個指令同時爭用同一硬體資源。

3. 例外（exception）
   例外是 CPU 執行指令時發生的特殊事件，例如非法指令、除以零、記憶體存取錯誤等；中斷（interrupt）則通常由外部硬體或系統事件觸發。CPU 必須保存適當的執行狀態，轉移至例外處理常式，確保程式執行結果正確。

例外發生時，管線中尚未完成的指令可能必須停止、清除或重新導向，因而影響原本的平行執行，也可能形成控制危障。

解題方法

判斷本題的關鍵，是找出最完整描述「例外如何影響管線平行性與控制流程」的選項。

例外處理的一般流程如下：

1. CPU 偵測到例外或中斷。
2. 暫停原本程式的正常指令流程。
3. 保存程式計數器（PC）及必要的處理器狀態。
4. 將控制權轉移至例外處理常式。
5. 清除或修正管線中不應繼續執行的指令。
6. 例外處理完成後，恢復原程式或終止程式。

因此，例外會使原本的指令平行執行受到暫停或重導向，並造成控制流程上的危障。這正是選項（D）的描述。

選項分析

（A）錯誤

Data hazard 是由指令間的資料相依性所造成，例如：

ADD R1, R2, R3
SUB R4, R1, R5

第二條指令需要第一條指令產生的 $R1$，若第一條指令尚未完成，便會發生資料危障。

資料危障的核心是讀寫資料的時間衝突，不是「依賴例外的結果」。例外可能影響控制流程與指令提交順序，但並非 Data hazard 的定義，因此本選項錯誤。

（B）錯誤

Control hazard 通常出現在條件分支或跳躍指令，例如：

BEQ R1, R2, LABEL

CPU 在尚未知道分支結果前，可能先猜測下一個 PC，這稱為**分支預測（branch prediction）與推測執行（speculative exec

核心觀念

本題考查作業系統中的「程序狀態轉換」與「程序切換」原因。

程序執行時，若目前程序無法繼續使用 CPU，作業系統會觸發程序切換，並依原因將程序放入不同佇列：

• Ready queue（就緒佇列）：程序已具備執行條件，只等待 CPU。
• Wait queue／Blocked queue（等待／阻塞佇列）：程序正在等待 I/O、計時器、硬體中斷等事件。
• Running state（執行狀態）：程序目前正在 CPU 上執行。

常見狀態轉換如下：

$$\text{Running} \rightarrow \text{Waiting}$$

表示程序因等待 I/O、睡眠或某項事件而暫停。

$$\text{Running} \rightarrow \text{Ready}$$

表示程序仍可繼續執行，但因時間配額用完等原因暫時離開 CPU。

本題要找的是：哪一種情況不會使目前正在執行的程序被加入等待／就緒佇列，進而造成這類程序切換。

解題方法

逐一判斷各選項是否會使目前執行中的程序：

1. 因為等待某個事件而進入等待佇列；
2. 因為失去 CPU 使用權而進入就緒佇列；
3. 或只是建立新的子程序，但目前程序本身仍可繼續執行。

只要目前程序仍能繼續執行，建立子程序本身通常不會使目前程序進入等待／就緒佇列，因此可判定為不符合其他選項的程序切換原因。

選項分析

(A) I/O request

I/O request 是指程序提出輸入／輸出要求，例如讀取檔案、等待磁碟資料或接收網路資料。

I/O 裝置的處理速度通常比 CPU 慢。若程序提出同步 I/O 要求，必須等待 I/O 完成，無法繼續執行，因此會發生：

$$\text{Running} \rightarrow \text{Waiting}$$

該程序會被移至等待佇列，CPU 則交給其他就緒程序使用。

因此，(A) 會造成程序進入等待佇列，為錯誤選項。

(B) Sleep execution

Sleep execution 是指程序執行睡眠操作，主動暫停一段指定時間。

睡眠期間，程序不需要佔用 CPU，會進入等待狀態，直到計時器到期後再回到就緒狀態：

$$\text{Running} \rightarrow \text{Waiting}$$

計時器到期後：

$$\text{Waiting} \rightarrow \text{Ready}$$

因此，睡眠操作會使目前程序暫時離開 CPU 並進入等待佇列。

所以，(B) 會造成程序切換，為錯誤選項。

(C) Time slice expired

在分時系統或搶先式多工系統中，每個程序只能連續使用 CPU 一段時間，稱為 time slice（時間片）。

當時間片用完時，目前程序通常不再具有優先使用 CPU 的資格，但它仍然可以繼續執行。因此狀態通常由：

核心觀念

本題考查作業系統中的 Semaphore（號誌），用於控制多個行程或執行緒對共享資源、臨界區（critical section）的存取。

Semaphore 具有一個整數計數值，並透過兩個具原子性的操作管理資源：

• wait、P 或 down：要求資源。若計數值大於零，將其減一並繼續執行；若無可用資源，行程必須等待。
• signal、V 或 up：釋放資源，使計數值加一，並喚醒等待中的行程。

基本概念可表示為：

$$wait(S):\quad S \leftarrow S-1$$

當 $S=0$ 時，執行 wait(S) 的行程必須等待，不能進入受保護的區域。

$$signal(S):\quad S \leftarrow S+1$$

因此，Semaphore 能限制同一時間可進入臨界區的行程數量，達到行程同步與共享資源管理的目的。

若使用二元號誌（binary semaphore），其值通常為 $0$ 或 $1$，可用來實現互斥鎖：

$$\text{進入臨界區前： } wait(S)$$ $$\text{離開臨界區後： } signal(S)$$

解題方法

判斷本題的關鍵是確認哪個選項正確描述 Semaphore 的主要機轉：

1. 是否使用計數器管理可用資源？
2. 是否限制同時進入臨界區的行程數量？
3. 是否透過等待與喚醒完成同步？
4. 是否誤把 Semaphore 的功能描述成消除同步、解決死結或單純依靠硬體中斷？

Semaphore 的核心正是「以計數值表示可用資源數量，搭配 wait 與 signal 控制存取」，因此選擇 (B)。

選項分析

(A) 錯誤

Semaphores expedite process execution by enabling all waiting processes to access the critical section simultaneously if the semaphore count is positive.

此敘述錯在「所有等待中的行程都能同時進入臨界區」。

當 Semaphore 計數值為正數時，一次執行 wait 通常只會使計數值減一，代表只允許一個行程取得一份資源。若計數值為 $k$，最多只能同時允許 $k$ 個行程取得資源，而不是讓所有等待中的行程同時進入。

此外，Semaphore 的目的不是加速行程執行，而是控制資源存取、避免競爭條件（race condition）並完成同步。

(B) 正確

Semaphores use a counter to manage how many processes can simultaneously access a critical section of code, effectively ensuring mutual exclusion and synchronization.

此選項正確描述 Semaphore 的基本機轉：

• 使用計數器記錄可用資源數量。
• 透過 wait 取得資源，使計數值減一。
• 透過 signal 釋放資源，使計數值加一。
• 當資源不足時，行程必須等待。
• 配合二元號誌時，可確保互斥。
• 配合計數型號誌時，可限制同時使用資源的行程數量。
• 透過等待與喚醒機制完成行程同步。

因此，本題官方答案為 (B)。

核心觀念

本題考查 Preemptive-Priority Scheduling（可搶先式優先權排程）。

• 處理程序到達後，會依優先權決定執行順序。
• 新程序到達時，若其優先權較高，便會搶占目前正在執行的程序。
• 本題依官方答案採用：Priority 數值越大，優先權越高。
• 等待時間公式為：

$$\text{Waiting Time} = \text{Completion Time} - \text{Arrival Time} - \text{Burst Time}$$

---

解題方法

依到達時間與優先權建立執行順序：

1. $t=0$：A 開始執行。
2. $t=3$：B 到達，但 B 的優先權 $2<3$，無法搶占 A。
3. $t=6$：A 執行完畢。
4. $t=6\sim 7$：CPU 暫時閒置。
5. $t=7$：C 開始執行。
6. $t=8$：D 到達，且 D 的優先權 $4>1$，搶占 C。
7. $t=8\sim17$：D 執行完畢。
8. $t=17\sim21$：C 繼續執行剩餘的 4 ms，於 $t=21$ 完成。

甘特圖如下：

$$\text{A}(0\sim6) \rightarrow \text{Idle}(6\sim7) \rightarrow \text{C}(7\sim8) \rightarrow \text{D}(8\sim17) \rightarrow \text{C}(17\sim21)$$

各程序等待時間：

核心觀念

本題考查快取記憶體（cache）的 miss penalty 與有效 CPI（effective CPI）計算。

基本公式為：

$$\text{Effective CPI} = \text{Base CPI} + \text{Instruction Cache Miss Penalty} + \text{Data Cache Miss Penalty}$$

其中：

• Base CPI：假設所有記憶體參考皆命中主記憶體時的基本 CPI。
• Miss rate：快取未命中的比例。
• Miss penalty：發生 miss 時，額外需要的處理時間。
• 主記憶體存取時間為 $100$ 個 clock cycles，且題目說明已包含完整 miss handling，因此每次 cache miss 的 penalty 採 $100$ cycles。

題目中的「data instruction cache」應依題意及官方答案解讀為 data cache（資料快取）的 miss rate。

解題方法

1. 計算指令快取造成的額外 CPI

每一條指令都需要從 instruction cache 取得指令，因此每條指令都有機會發生 instruction cache miss。

Instruction cache miss rate 為：

$$0.2\%=0.002$$

每次 miss 額外耗費 $100$ 個 clock cycles，因此：

$$\text{Instruction miss contribution} = 0.002\times 100 = 0.2$$

2. 計算資料快取造成的額外 CPI

題目指出 $60\%$ 的指令會存取資料記憶體，因此每執行一條指令，平均有 $0.6$ 次資料存取。

Data cache miss rate 為：

$$1\%=0.01$$

所以每條指令平均發生的 data cache miss 次數為：

$$0.6\times 0.01=0.006$$

核心觀念

本題考查 IPv4 Class C 網路的子網路切割（subnetting）。

原始網路為：

$$192.168.113.0$$

Class C 網路的預設遮罩為：

$$255.255.255.0=/24$$

因此最後一個八位元組原本全部屬於主機位元。若要切割成至少 6 個「可使用的子網路」，需借用主機位元中的 $n$ 個作為子網路位元：

$$2^n-2\geq 6$$

其中減去的 2 個子網路是傳統規則中的 subnet zero 與 all-ones subnet。

當 $n=3$ 時：

$$2^3-2=6$$

所以需借用 3 個位元，新的子網路遮罩為：

$$/27=255.255.255.224$$

每個子網路的區塊大小為：

$$256-224=32$$

因此每個子網路涵蓋 32 個連續位址，其中可配置給主機的位址數為：

$$2^5-2=30$$

---

解題方法

最後一個八位元組以每 32 個位址為一個區塊切割：

子網路範圍	子網路位址	廣播位址	可用主機範圍
$0\sim31$	.0	.31	.1～.30
$32\sim63$	.32	.63	.33～.62
$64\sim95$	.64	.95	.65～.94
$96\sim127$	.96	.127	.97～.126
$128\sim159$	.128	.159	.129～.158
$160\sim191$	.160	.191	.161～.190
$192\sim223$	.192	.223	.193～.222
$224\sim255$	.224	.255	.225～.254

傳統題目要求 6 個可使用子網路，因此排除 .0～.31 與 .224～.255 這兩個特殊子網路，保留：

$$.32\sim63,\ .64\sim95,\ .96\sim127,\ .128\sim159,\ .160\sim191,\ .192\sim223$$

只要一組位址落在同一個 32 位址區塊，即位於同一子網路。

---

選項分析

(A) $(192.168.113.1,\ 192.168.113.254)$

• .1 落在 .0～.31 區塊。
• .254 落在 .224～.255 區塊。

核心觀念

本題考查 TCP/IP 協定組合中的基本功能，以及 OSI 分層、TCP 與 UDP 的通信特性、ARP 與 NAT 的差異。

重點如下：

• TCP：傳輸層的連線導向、可靠傳輸協定。
• UDP：傳輸層的無連線、低負擔傳輸協定。
• Router：主要依據 IP 位址進行封包轉送，屬於 OSI 第 3 層裝置。
• ARP：將區域網路中的 IP 位址解析成 MAC 位址。
• NAT：將私有 IP 位址轉換成公有 IP 位址。
• TCP flags：用來表示 TCP 連線建立、傳輸、終止等狀態與控制功能。

解題方法

逐一比對每個選項中的「協定名稱、OSI 層級、主要功能與通信特性」。

其中只要選項把兩種協定的功能混淆，或把 ARP、NAT 的用途混淆，即可判定錯誤。最後確認 TCP flags 是否確實與 TCP 對話期間的狀態控制有關。

選項分析

(A) TCP is called a connectionless communication while UDP is called a connection-oriented communication.

錯誤。

TCP 是 connection-oriented protocol，使用連線導向通信。在正式傳輸資料前，必須先建立連線，典型程序是 TCP three-way handshake：

1. 用戶端傳送 SYN
2. 伺服器回覆 SYN + ACK
3. 用戶端傳送 ACK

TCP 也提供排序、確認、重傳及流量控制，因此屬於可靠傳輸。

UDP 則是 connectionless protocol，不需事先建立連線，也沒有 TCP 的完整確認與重傳機制，適合即時影音、DNS 查詢等重視速度與低負擔的情境。

本選項將 TCP 與 UDP 的性質完全顛倒，因此錯誤。

---

(B) Router is an OSI Layer 2 device which can only forward data based on the MAC address.

錯誤。

Router 屬於 OSI Layer 3，也就是網路層裝置，主要根據目的地 IP 位址及路由表決定封包的轉送路徑。

MAC 位址主要用於同一個區域網路內的資料鏈結層傳輸，典型的 Layer 2 裝置是 Switch。Switch 主要根據 MAC address table 轉送 Ethernet frame。

Router 在實際轉送過程中也會處理 MAC 位址，但它的跨網路路由判斷依據是 IP 位址，不是「只能」根據 MAC 位址。因此本選項在裝置層級與轉送依據兩方面都錯誤。

---

(C) ARP (Address Resolution Protocol) can be used to change several private addresses under the LAN (Local Area Network) to a single public IP address.

錯誤。

ARP 的功能是將 IPv4 位址解析成同一區域網路中的 MAC 位址。例如主機知道閘道器的 IP 位址，卻不知道其 MAC 位址時，會發送 ARP Request，詢問「哪一台設備使用這個 IP 位址？」對方再回覆 ARP Reply，提供自己的 MAC 位址。

核心觀念

本題考查 SQL 中下列子句的作用與執行順序：

• WHERE：先篩選個別資料列。
• GROUP BY：依 category 分組。
• COUNT(animalid)：計算每組的資料筆數。
• HAVING：分組、聚合計算後，再篩選群組。
• ORDER BY：依聚合結果及欄位排序。

本題要求：

1. 只保留 born > '2023-02-14' 的動物。
2. 依 category 分組。
3. 只顯示數量至少為 $2$ 的類別。
4. 依數量遞減、類別字母遞增排序。

---

解題方法

先執行日期條件：

animalid	category	born	是否保留
1	dog	2023-04-18	是
2	cat	2023-03-12	是
3	dog	2023-03-29	是
4	cat	2023-04-04	是
5	bird	2023-02-13	否
6	fish	2023-03-25	是
7	fish	2022-12-24	否
8	dog	2023-02-11	否
9	bird	2023-02-21	是
10	dog	2023-04-12	是
11	bird	2023-02-28	是

分組計數如下：

category	筆數
dog	3
cat	2
fish	1
bird	2

再使用 HAVING count(animalid) >= 2，刪除 fish 群組，最後依數量遞減、類別遞增排序：

category	countaid
dog	3
bird	2
cat	2

因此正確指令為：

SELECT category, count(animalid) AS countaid
FROM animal
WHERE born > '2023-02-14'
GROUP BY category
HAVING count(animalid) >= 2
ORDER BY count(animalid) DESC, category ASC;

---

選項分析

(A) 錯誤

WHERE born > '2023-02-14' AND count(animalid) >= 2

WHERE 是針對單筆資料列進行篩選，不能直接使用尚未分組計算的聚合函數 count(animalid)。群組計數條件必須放在 HAVING。

核心觀念

本題考查二元樹的三種走訪順序：

• Prefix order（Preorder，前序）：根節點 → 左子樹 → 右子樹
• Infix order（Inorder，中序）：左子樹 → 根節點 → 右子樹
• Postfix order（Postorder，後序）：左子樹 → 右子樹 → 根節點

已知：

• 前序：ABCDEF
• 中序：CBDAEF

要求後序排列。

解題方法

前序排列的第一個節點必定是整棵樹的根，因此：

$$\text{根節點}=A$$

在中序排列 CBDAEF 中，將 $A$ 分開：

• $A$ 左側：CBD，屬於左子樹
• $A$ 右側：EF，屬於右子樹

因此樹的結構可先表示為：

 A
 / \
 CBD EF

接著依照前序排列分配左右子樹：

• 左子樹的前序為 BCD
• 右子樹的前序為 EF

處理左子樹：

• 前序 BCD 的根為 $B$
• 中序 CBD 中，$B$ 左側為 C，右側為 D

所以左子樹為：

 B
 / \
 C D

處理右子樹：

• 前序 EF 的根為 $E$
• 中序 EF 中，$E$ 右側有 $F$

所以右子樹為：

 E
 \
 F

完整二元樹如下：

 A
 / \
 B E
 / \ \
 C D F

後序走訪規則為「左子樹 → 右子樹 → 根節點」：

1. $B$ 的左子樹為 $C$，右子樹為 $D$，最後訪問 $B$：CDB
2. $E$ 的右子樹為 $F$，最後訪問 $E$：FE
3. 最後訪問根節點 $A$

因此：

$$\text{Postorder}=CDBFEA$$

逐步追蹤

核心觀念

本題考查 IP address（網際網路協定位址）的定義，以及 IPv4 與 IPv6 的位元長度差異。

IP address 是配置給主機或網路設備網路介面的數值識別位址，用於在網路中辨識其邏輯位置，協助資料封包進行傳送與路由。此處的「location」是指網路上的邏輯位置，並非實際地理位置。

兩種主要版本如下：

• IPv4：使用 $32$ 位元位址。
• IPv6：使用 $128$ 位元位址。

可表示的位址數量為：

$$\text{IPv4：}2^{32}\approx 4.29\times 10^9$$ $$\text{IPv6：}2^{128}\approx 3.4\times 10^{38}$$

IPv4 通常以四組十進位數字表示，例如 192.168.1.1；IPv6 通常以八組十六進位數字表示，例如 2001:db8::1。雖然表示形式可能包含英文字母，但 IP address 的本質是數值位址。

解題方法

本題可抓住兩個關鍵判斷點：

1. IP address 是「numerical identifier」，即數值識別碼，而非一般意義的英數字元代碼。
2. 位址長度為：

$$\text{IPv4}=32\text{ bits},\qquad \text{IPv6}=128\text{ bits}$$

逐一比對選項後，只有選項 A 同時符合 IP address 的定義，以及 IPv4、IPv6 的正確位元長度。

選項分析

(A) 正確

An IP address is a numerical identifier that identifies the location of a host or network device on a network. IPv4 addresses are 32-bit addresses, while IPv6 addresses are 128-bit addresses.

此敘述包含兩項正確內容：

• IP address 是在網路中識別主機或網路設備邏輯位置的數值識別碼。
• IPv4 為 $32$ 位元，IPv6 為 $128$ 位元。

因此選項 A 正確。

(B) 錯誤

An IP address is an alphanumeric code used to identify the location of a device on the Internet. IPv4 addresses are 32-bit addresses, while IPv6 addresses are 64-bit addresses.

錯誤在於 IPv6 並非 $64$ 位元，而是：

核心觀念

本題考查關聯式資料庫中的：

• 主鍵（Primary Key）
• 外來鍵（Foreign Key）
• 表格間的關聯與基數（Cardinality）
• SQL 查詢條件與集合運算

圖中三個資料表的欄位關係如下：

• Supplier.SID 可作為 Supplier 的主鍵。
• Employee.EID 可作為 Employee 的主鍵。
• Purchase.PID 可作為 Purchase 的主鍵。
• Purchase.SID 可參照 Supplier.SID，因此是外來鍵。
• Purchase.EID 可參照 Employee.EID，因此也是外來鍵。

其中，Purchase 表中的 EID 可重複，例如員工 319 出現在兩筆購買紀錄中。

---

解題方法

判斷各選項時，依序檢查：

1. 是否存在可建立的外來鍵。
2. 欄位值是否具備唯一性，能否擔任主鍵。
3. 兩個資料表之間的資料筆數關係。
4. 主鍵、外來鍵的功能是否混淆。
5. SQL 查詢是否應使用 IN、JOIN 或 UNION。

由資料可知：

Employee
EID
214
319
823

Purchase
PID SID EID
1234 123 319
1238 123 214
2219 364 319
2654 279 823

一名員工可以出現在多筆 Purchase 紀錄中，例如員工 319 對應 PID = 1234 與 PID = 2219。因此，Employee 與 Purchase 之間是「一對多」關係：

$$\text{一名 Employee} \longrightarrow \text{多筆 Purchase}$$

而每筆 Purchase 紀錄只對應一名員工。

---

選項分析

(A) There is no possible foreign key that can be used in “Purchase” table.

錯誤。

Purchase 表至少有兩個欄位可以作為外來鍵：

• Purchase.SID 參照 Supplier.SID
• Purchase.EID 參照 Employee.EID

因此，Purchase 表確實可以使用外來鍵來連結其他資料表。

---

(B) EID can be regarded as a primary key in “Purchase” table.

錯誤。

主鍵必須能唯一識別資料表中的每一筆資料，但 Purchase.EID 並不唯一：

• EID = 319 出現於 PID = 1234
• EID = 319 也出現於 PID = 2219

核心觀念

本題考查廣度優先搜尋（Breadth-First Search, BFS）。

BFS 的核心規則是：

1. 從起點開始。
2. 先拜訪距離起點較近的節點。
3. 使用佇列（Queue），遵守「先進先出」（FIFO）。
4. 同一層的節點，其先後順序可能依鄰接串列或圖形方向而定，但不能先拜訪下一層節點。

由圖可得，從 $H$ 出發的主要連線為：

• $H$ 連接 $G$
• $G$ 連接 $A$
• $A$ 連接 $J$
• $J$ 連接 $B$、$C$
• $C$ 連接 $D$、$E$
• $E$ 連接 $F$、$I$

因此各節點距離起點 $H$ 的層級為：

層級	節點
0	$H$
1	$G$
2	$A$
3	$J$
4	$B, C$
5	$D, E$
6	$F, I$

解題方法

依照 BFS 的佇列流程：

1. 從 $H$ 開始，拜訪 $H$，加入鄰接點 $G$。
2. 拜訪 $G$，加入 $A$。
3. 拜訪 $A$，加入 $J$。
4. 拜訪 $J$，加入尚未拜訪的 $B$、$C$。
5. 依序拜訪 $B$、$C$。
6. 拜訪 $C$ 時加入 $D$、$E$。
7. 拜訪 $D$、$E$，再由 $E$ 加入 $F$、$I$。
8. 最後拜訪 $F$、$I$。

所以 BFS 順序為：

$$H \rightarrow G \rightarrow A \rightarrow J \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F \rightarrow I$$

選項分析

(A) $H\rightarrow G\rightarrow A\rightarrow J\rightarrow B\rightarrow C\rightarrow D\rightarrow E\rightarrow F\rightarrow I$

正確。節點依距離起點的層級依序拜訪，且同一層的節點也符合圖中鄰接順序，是 BFS 的路徑。

(B) $B\rightarrow J\rightarrow C\rightarrow E\rightarrow F\rightarrow I\rightarrow D\rightarrow A\rightarrow G\rightarrow H$

核心觀念

本題考查不同函數的漸近成長率（asymptotic growth rate）。當 $n\to\infty$ 時，比較的是各函數「最終誰成長最快」，而不是比較某個小數值下的大小。

常見成長率由慢至快可排列為：

$$\log n < n^k < a^n < n!$$

其中 $k$ 為固定常數、$a>1$。本題中的 $n^{200}$ 與 $n^{1000}$ 都是多項式成長，$2^n$ 是指數成長，而 $n!$ 的成長速度最終會超過固定底數的指數函數。

---

解題方法

可分別比較各類函數的成長速度。

1. 比較 $n\log n$ 與多項式

因為 $\log n$ 的成長速度比任何正次方的 $n$ 慢，所以：

$$n\log n \ll n^{200}$$

更正式地，

$$\lim_{n\to\infty}\frac{n\log n}{n^{200}} = \lim_{n\to\infty}\frac{\log n}{n^{199}} =0$$

因此 $n\log n$ 比 $n^{200}$ 成長慢。

2. 比較 $n^{200}$ 與 $n^{1000}$

$$\frac{n^{200}}{n^{1000}} = \frac{1}{n^{800}} \to 0$$

所以：

$$n^{200}\ll n^{1000}$$

3. 比較固定次方與指數函數 $2^n$

任何固定次方的多項式，最終都會被指數函數超越：

$$\lim_{n\to\infty}\frac{n^{1000}}{2^n}=0$$

因此：

$$n^{1000}\ll 2^n$$

4. 比較 $2^n$ 與 $n!$

將階乘與 $2^n$ 相除：

$$\frac{n!}{2^n} = \frac{1}{2}\cdot\frac{2}{2}\cdot\frac{3}{2}\cdots\frac{n}{2}$$

當 $n$ 足夠大時，乘積中會有大量大於 $1$ 的因子，因此整體會持續快速增加。更正式地，使用 Stirling's approximation：

$$n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

因此：

$$\frac{n!}{2^n} \sim \sqrt{2\pi n}\left(\frac{n}{2e}\right)^n \to\infty$$

因為 $\frac{n}{2e}$ 會隨著 $n$ 增加而趨近無限大，所以：

核心觀念

本題考查：

• C 語言函式遞迴（recursion）
• if...else if...else 條件判斷
• 三元運算子 ?:
• 奇偶數判斷：n % 2 == 0
• 整數除法與函式回傳值
• 依遞迴結果計算最終的 printf 輸出

函式 test(n) 可理解為：將整數 $n$ 轉換成 $1$ 所需的最少操作次數。

其規則為：

• $n=1$：回傳 $0$
• $n=2$：回傳 $1$
• $n$ 為偶數：先除以 $2$，操作次數加 $1$
• $n$ 為奇數：分別考慮加 $1$、減 $1$ 兩條路徑，取較小值，再加 $2$

因此：

$$test(n)= \begin{cases} 0, & n=1\\ 1, & n=2\\ test(n/2)+1, & n\text{ 為偶數}\\ \min\left(test\left(\frac{n+1}{2}\right),test\left(\frac{n-1}{2}\right)\right)+2, & n\text{ 為奇數} \end{cases}$$

---

解題方法與逐步追蹤

主程式設定：

int number = 15;
printf("%d\n", integerReplacement(number));

因此必須計算：

$$integerReplacement(15)$$

因為 $15\ne 1$，所以：

$$integerReplacement(15)=test(15)$$

1. 計算 test(15)

$15$ 是奇數，因此執行：

return min(test((n + 1) / 2), test((n - 1) / 2)) + 2;

代入 $n=15$：

$$test(15)=\min(test(8),test(7))+2$$

---

2. 計算 test(8)

$8$ 是偶數：

$$test(8)=test(4)+1$$

$4$ 也是偶數：

$$test(4)=test(2)+1$$

又因為：

$$test(2)=1$$

所以：

$$test(4)=1+1=2$$ $$test(8)=2+1=3$$

---

3. 計算 test(7)

$7$ 是奇數：

$$test(7)=\min(test(4),test(3))+2$$

已知：

$$test(4)=2$$

接著計算 test(3)。

$3$ 是奇數：

$$test(3)=\min(test(2),test(1))+2$$

代入基本情況：

$$test(3)=\min(1,0)+2=0+2=2$$

因此：

$$test(7)=\min(2,2)+2=4$$

---

4. 回到 test(15)

$$test(15)=\min(test(8),test(7))+2$$ $$test(15)=\min(3,4)+2$$ $$test(15)=3+2=5$$

所以：

integerReplacement(15)

回傳 $5$，printf 輸出：

5

---

遞迴呼叫樹

核心觀念

本題考查程式語言中「指標（pointer）」的主要用途。

指標是一種儲存「記憶體位址（memory address）」的變數。一般變數直接保存資料本身；指標則保存資料所在的位置，再透過解參照運算子 * 取得該位置中的資料。

例如：

int x = 10;
int *p = &x;

其意義如下：

• x：整數變數，內容為 10
• &x：取得變數 x 的記憶體位址
• p：指標變數，儲存 x 的位址
• *p：解參照，取得 p 所指向位置的內容，也就是 10

因此，指標的核心功能是「透過記憶體位址間接存取資料」，也能用於陣列、動態記憶體配置、函式參數傳遞與資料結構。

解題方法

判斷指標的主要用途，可直接抓住兩個關鍵字：

1. 指標儲存記憶體位址。
2. 指標可透過位址間接存取變數與陣列元素。

以陣列為例：

int a[3] = {10, 20, 30};
int *p = a;

在 C 語言中，陣列名稱 a 通常會轉換成指向第一個元素的位址，因此：

• p 指向 a[0]
• *p 的值為 10
• *(p + 1) 的值為 20
• *(p + 2) 的值為 30

指標運算可以讓程式以位址為基礎逐一存取陣列元素，這正是選項 B 所描述的功能。

程式追蹤（trace）

int x = 10;
int *p = &x;

printf("%d\n", *p);

*p = 25;

printf("%d\n", x);

逐步追蹤：

步驟	程式敘述	x 的內容	p 的內容	*p 的值
1	int x = 10;	10	尚未設定	—
2	int *p = &x;	10	x 的位址	10
3	printf("%d", *p);	10	x 的位址	10
4	*p = 25;	25	x 的位址	25

核心觀念

本題考查遞迴定義與 Fibonacci-like 數列的計算。

題目給定：

$$f(0)=2,\qquad f(1)=3$$

當 $x\geq 2$ 時：

$$f(x)=f(x-1)+f(x-2)$$

也就是每一項等於前兩項的和。與標準 Fibonacci 數列相比，本題只有初始值不同。

---

解題方法

依照遞迴公式，從 $f(0)$、$f(1)$ 依序往後計算：

$$\begin{aligned} f(2)&=f(1)+f(0)=3+2=5\\ f(3)&=f(2)+f(1)=5+3=8\\ f(4)&=f(3)+f(2)=8+5=13\\ f(5)&=f(4)+f(3)=13+8=21\\ f(6)&=f(5)+f(4)=21+13=34\\ f(7)&=f(6)+f(5)=34+21=55\\ f(8)&=f(7)+f(6)=55+34=89\\ f(9)&=f(8)+f(7)=89+55=144 \end{aligned}$$

因此：

$$f(9)=144$$

---

逐步追蹤表（Trace）

$x$	計算方式	$f(x)$
0	初始值	2
1	初始值	3
2	$2+3$	5
3	$3+5$	8
4	$5+8$	13
5	$8+13$	21
6	$13+21$	34
7	$21+34$	55
8	$34+55$	89
9	$55+89$	144

---

關鍵程式碼

採用迭代法時，只需保留前兩項：

a = 2 // f(0)
b = 3 // f(1)

for i = 2 to 9:
 c = a + b
 a = b
 b = c

答案為 b

逐次更新如下：

核心觀念

本題考查「二分搜尋法（Binary Search）」的搜尋範圍定義與索引邊界。

二分搜尋法適用於已排序的串列。每次取搜尋範圍的中間位置：

$$\text{mid}=\left\lfloor\frac{\text{left}+\text{right}}{2}\right\rfloor$$

再根據 arr[mid] 與 target 的大小關係，捨棄一半不可能包含答案的區域。

本程式採用「包含左右端點」的搜尋範圍：

$$[\text{left},\text{right}]$$

因此：

• 最左索引為 $0$
• 最右索引為 $\text{len(arr)}-1$
• 搜尋條件應為 left <= right

---

解題方法

原程式為：

def binary_search(arr, target):
 left, right = 0, len(arr)
 while left <= right:
 mid = (left + right) // 2
 if arr[mid] == target:
 return mid
 elif arr[mid] < target:
 left = mid + 1
 else:
 right = mid - 1
 return -1

Python 串列的索引範圍是：

$$0,1,2,\ldots,\text{len(arr)}-1$$

若 arr 有 $n$ 個元素，合法索引最大值為 $n-1$，而不是 $n$。

原程式設定：

right = len(arr)

會使搜尋範圍包含不存在的索引 len(arr)。因此當 mid 計算到該位置時，執行 arr[mid] 會發生 IndexError。

修正為：

right = len(arr) - 1

完整正確程式碼如下：

def binary_search(arr, target):
 left, right = 0, len(arr) - 1
 while left <= right:
 mid = (left + right) // 2

 if arr[mid] == target:
 return mid
 elif arr[mid] < target:
 left = mid + 1
 else:
 right = mid - 1

 return -1

因此本題官方答案為 (A)。

---

逐步追蹤

以已排序串列：

arr = [2, 5, 8, 12, 16, 23, 38]
target = 16

為例。

串列長度為 $7$，合法索引為 $0$ 到 $6$。

第一次搜尋

left = 0
right = 6
mid = (0 + 6) // 2 = 3
arr[3] = 12

因為 $12<16$，目標值只可能出現在右半部：

left = mid + 1 = 4

第二次搜尋

left = 4
right = 6
mid = (4 + 6) // 2 = 5
arr[5] = 23

因為 $23>16$，目標值只可能出現在左半部：

right = mid - 1 = 4

第三次搜尋

left = 4
right = 4
mid = (4 + 4) // 2 = 4
arr[4] = 16

找到目標值，回傳：

4

若搜尋範圍縮小到 left > right，代表所有合法位置都已排除，程式回傳 -1，表示找不到目標值。

---

選項分析

(A) Change len(arr) to len(arr)-1

正確。

核心觀念

AES 在 $\operatorname{GF}(2^8)$ 中進行運算，每個位元組代表一個最高次不超過 $7$ 的二元多項式：

• $\{53\}_{\mathrm{hex}}=\texttt{0101 0011}_2$
• $\{A4\}_{\mathrm{hex}}=\texttt{1010 0100}_2$

因此：

$$\{53\}_{\mathrm{hex}}=x^6+x^4+x+1$$ $$\{A4\}_{\mathrm{hex}}=x^7+x^5+x^2$$

所有係數皆在 $\operatorname{GF}(2)$ 中，因此：

• 加法等同 XOR。
• 乘法先依多項式乘法進行。
• 超過 $x^7$ 的項，必須利用不可約多項式

$$m(x)=x^8+x^4+x^3+x+1$$

進行模除。

因為在 $\operatorname{GF}(2)$ 中，加法與減法相同，所以：

$$x^8+x^4+x^3+x+1=0$$

可得：

$$x^8=x^4+x^3+x+1$$

這就是 AES 中 xtime 運算的數學基礎。

---

解題方法：使用 AES 的 xtime 逐次乘以 $x$

將 $\{53\}_{\mathrm{hex}}$ 分別乘上 $x,x^2,x^4,\ldots$，再依 $\{A4\}_{\mathrm{hex}}$ 的二進位位元選取相應結果。

1. 求 $\{53\}\cdot x$

$\{53\}$ 的最高位元為 $0$，因此左移一位即可：

$$\{53\}\cdot x=\{A6\}$$

2. 求 $\{53\}\cdot x^2$

$\{A6\}$ 的最高位元為 $1$，左移後產生 $x^8$ 項，需 XOR $\{1B\}$ 消除：

$$\{A6\}\cdot x = \{4C\}\oplus\{1B\} = \{57\}$$

因此：

$$\{53\}\cdot x^2=\{57\}$$

依此繼續計算：

$$\begin{array}{c|c} \text{乘冪} & \{53\}\cdot x^k \\ \hline x^0 & \texttt{53}\\ x^1 & \texttt{A6}\\ x^2 & \texttt{57}\\ x^3 & \texttt{AE}\\ x^4 & \texttt{47}\\ x^5 & \texttt{8E}\\ x^6 & \texttt{07}\\ x^7 & \texttt{0E} \end{array}$$

其中每次左移後：

• 原最高位元為 $0$：直接保留左移結果。
• 原最高位元為 $1$：左移結果再 XOR $\texttt{1B}$。

---

3. 依 $\{A4\}$ 的位元選取項目

$$\{A4\}_{\mathrm{hex}} = \texttt{1010 0100}_2 = x^7+x^5+x^2$$

因此：

核心觀念

本題考查兩個 C 語言函式傳遞機制：

1. 指標傳遞（以位址模擬傳址）

• cubecomp1(&number) 傳入 number 的記憶體位址。
• 函式內的 *nP 可直接修改主程式中的 number。

2. 值傳遞（pass by value）

• cubecomp2(number) 將 number 的值複製給函式的區域變數 n。
• 函式內修改 n，不會影響主程式的 number。

---

解題方法與逐步追蹤

初始狀態：

int number = 2;

因此：

$$number = 2$$

第一步：執行 cubecomp1(&number)

呼叫時傳入 number 的位址：

cubecomp1(&number);

函式內容：

void cubecomp1(int *nP) {
 *nP = *nP * *nP * *nP;
}

因為 nP 指向 number，所以 *nP 就是 number 本身：

$$* nP = 2 \times 2 \times 2 = 8$$

此時主程式中的變數已被修改為：

$$number = 8$$

第二步：執行 cubecomp2(number)

此時呼叫為：

cubecomp2(8);

函式參數 n 是 number 的複本：

$$n = 8$$

函式內執行：

n = n * n * n;

因此：

$$n = 8 \times 8 \times 8 = 512$$

接著執行：

printf("%d ", n);

輸出：

512

由於 n 是複本，這項修改不會影響主程式中的 number，所以：

$$number = 8$$

第三步：主程式輸出 number

printf("%d ", number);

輸出：

8

完整輸出為：

512 8

---

程式中的 int cubecomp2(int n) 注意事項

cubecomp2 宣告為 int，但函式結尾沒有寫 return：

核心觀念

本題考查資料隱私保護中的 差異隱私（differential privacy）。

差異隱私的核心思想，是讓資料分析結果不會因為某一位個人的資料是否存在於資料集中，而產生可明顯辨識的差異。如此一來，攻擊者即使觀察到分析結果，也難以推斷特定個人是否提供資料，進而降低個人紀錄遭揭露的風險。

實務上，差異隱私通常在統計查詢或分析結果中加入經過設計的隨機雜訊，例如 Laplace noise 或 Gaussian noise。其概念可表示為：

$$\Pr[M(D)\in S]\leq e^\varepsilon \Pr[M(D')\in S]$$

其中：

• $D$ 與 $D'$ 是只差一筆個人資料的相鄰資料集。
• $M$ 是加入隱私保護機制的分析演算法。
• $S$ 是可能的輸出結果集合。
• $\varepsilon$ 稱為隱私參數，數值越小，代表隱私保護越強，但輸出結果通常也會更不精確。

因此，差異隱私的代表性作法就是「加入適當雜訊，使個別紀錄不易被辨識」。

解題方法

判斷本題的關鍵，是辨識各選項所描述的資料安全技術：

• 加密：保護資料內容不被未授權者讀取。
• 匿名化：移除或修改身分識別資訊。
• 差異隱私：在資料或分析結果中加入隨機雜訊，降低個人紀錄被推測的可能性。
• 存取控制：限制哪些使用者可以取得資料。
• 身分驗證：確認使用者是否具有合法身分。

選項中只有 (C) 直接描述差異隱私的主要機轉，因此選擇 (C)。

選項分析

(A) Encrypting sensitive data using strong cryptographic algorithms

錯誤。此選項描述的是資料加密，利用密碼學演算法將明文轉換為密文，只有持有正確金鑰者才能解密。

加密主要防止資料在儲存或傳輸過程中遭未授權讀取，但它本身不處理統計分析結果中個人紀錄可被推測的問題，因此不是差異隱私。

(B) Anonymizing personally identifiable information to protect individuals’ identities

錯誤。此選項描述的是匿名化（anonymization），例如移除姓名、身分證字號、電話號碼等直接識別資訊。

匿名化與差異隱私都與個人隱私保護有關，但兩者機制不同。單純移除識別欄位，仍可能因為年齡、地點、職業等資料組合而被重新識別，這稱為重新識別風險。差異隱私則透過數學定義與隨機雜訊，限制單一個人對輸出結果的影響。

核心觀念

本題考查資訊安全中的加密技術，以及「共享密鑰」與「公開／私有金鑰」的差異。

**對稱式加密（Symmetric Encryption）**使用同一把秘密金鑰進行加密與解密：

$$C = E_K(P)$$ $$P = D_K(C)$$

其中：

• $P$：明文（Plaintext）
• $C$：密文（Ciphertext）
• $K$：共享秘密金鑰（Shared Secret Key）
• $E_K$：使用金鑰 $K$ 加密
• $D_K$：使用金鑰 $K$ 解密

因此，只有持有同一把共享秘密金鑰的接收者，才能將密文還原成明文，讀取傳送的資訊。

解題方法

題幹的關鍵字是：

“the recipient with the shared secret key can decrypt the ciphertext”

「shared secret key」指的是傳送者與接收者事先共享的秘密金鑰。這正是對稱式加密的核心特徵：

1. 傳送者使用共享金鑰將明文加密。
2. 密文透過網路傳送。
3. 接收者使用相同的共享金鑰解密。
4. 沒有該金鑰的人，即使取得密文，也無法直接讀取內容。

因此本題選擇 Symmetric Encryption。

選項分析

(A) Symmetric Encryption：正確

對稱式加密使用同一把共享秘密金鑰進行加密與解密。只要金鑰未遭洩漏，未持有該金鑰的第三者就無法解密密文。

常見演算法包括：

• AES
• DES
• 3DES
• ChaCha20

本題描述「只有擁有共享秘密金鑰的接收者才能解密」，完全符合對稱式加密的定義。

(B) Asymmetric Encryption：錯誤

非對稱式加密使用一對金鑰：

• 公開金鑰（Public Key）
• 私有金鑰（Private Key）

兩者不是同一把共享秘密金鑰。以機密傳輸為例，寄件者通常使用接收者的公開金鑰加密，接收者再使用自己的私有金鑰解密：

$$C = E_{K_{\text{public}}}(P)$$ $$P = D_{K_{\text{private}}}(C)$$

因此，非對稱式加密的特徵是「公開金鑰與私有金鑰配對」，不是題幹所說的 shared secret key。

常見演算法包括 RSA、ECC。非對稱式加密可解決對稱式加密中的金鑰分配問題，但運算速度通常較慢。

核心觀念

本題考查資訊安全中的 buffer overflow（緩衝區溢位）。

緩衝區（buffer）是記憶體中用來暫存資料、且具有固定容量的區域。當程式寫入的資料量超過緩衝區所能容納的範圍，就會將資料寫到相鄰的記憶體位置，造成：

• 記憶體內容遭到破壞
• 變數數值被覆寫
• 函式返回位址或控制流程資料被修改
• 程式當機
• 嚴重時被利用來執行攻擊者指定的程式碼

例如，若宣告只能容納 8 個字元的陣列，卻寫入超過 8 個字元的資料，即可能發生緩衝區溢位。

以 C 語言為例：

char buffer[8];
strcpy(buffer, input);

若 input 超過 7 個有效字元，還要加上字串結尾的 '\0'，strcpy 仍可能持續寫入，超出 buffer 的界線。

---

解題方法

判斷此題可先抓住關鍵字：

• fixed-size buffer：固定大小的緩衝區
• writing data beyond the bounds：寫入超出界線
• memory corruption：記憶體損毀

這三個概念正是 buffer overflow 的標準定義，因此直接選擇描述最完整的選項。

其機轉可表示為：

$$\text{輸入資料量} > \text{緩衝區容量} \Rightarrow \text{越界寫入} \Rightarrow \text{相鄰記憶體遭覆寫} \Rightarrow \text{記憶體損毀}$$

因此正確答案為 (D)。

---

選項分析

(A) Allowing unauthorized access to restricted files or directories

此選項描述的是未經授權存取受限制的檔案或目錄，較接近：

• 權限控管失效（broken access control）
• 路徑穿越（path traversal）
• 未授權檔案存取

其核心問題是「存取權限或路徑驗證不當」，不是資料寫入超過記憶體緩衝區的界線，因此錯誤。

(B) Executing arbitrary code by injecting malicious SQL queries

此選項描述的是將惡意 SQL 指令注入資料庫查詢，稱為 SQL injection（SQL 注入）。

攻擊者可能藉由修改查詢語句，讀取、竄改資料，甚至在特定環境下執行非預期操作。其攻擊對象是資料庫查詢語法，不是程式記憶體中的固定大小緩衝區，因此錯誤。

核心觀念

本題考查機器學習中的「過度擬合」（Overfitting）。

過度擬合是指模型過度學習訓練資料中的特徵，甚至把訓練資料中的雜訊與偶然誤差也視為規則，因此產生以下現象：

• 在訓練資料上的準確率很高，訓練誤差很低。
• 面對未見過的新資料時，預測表現明顯變差。
• 模型的泛化能力（generalization ability）不足。

可用訓練誤差與測試誤差表示：

$$\text{Training Error} \ll \text{Test Error}$$

題幹中的關鍵描述為：

matches too closely to the training data, performing excellently on the training data but poorly on new samples

意思是「模型與訓練資料貼合得過度，在訓練資料表現優異，但在新樣本上表現不佳」，正是 Overfitting 的定義。

解題方法

本題屬於定義辨識題。先抓題幹的現象，再與機器學習名詞比對：

1. 是否過度貼合訓練資料？是。
2. 是否在訓練資料表現很好？是。
3. 是否在新資料表現很差？是。
4. 這三項同時出現時，對應的概念就是 Overfitting。

因此正確選項為 (E) Overfitting。

選項分析

(A) Max Pooling

Max Pooling 是卷積神經網路中的池化技術，通常用於特徵圖降維。

例如在 $2 \times 2$ 區域中：

$$\begin{bmatrix} 1 & 5\\ 3 & 2 \end{bmatrix} \longrightarrow 5$$

它會選取區域中的最大值，以保留較顯著的特徵，同時減少資料量與計算量。

Max Pooling 是一種神經網路運算方式，不是「模型過度貼合訓練資料」的現象，因此錯誤。

(B) Random Forest

Random Forest 是由多棵決策樹組成的集成學習模型。它通常透過：

• 對訓練資料進行 bootstrap 抽樣；
• 每次分裂時隨機選取部分特徵；
• 綜合多棵決策樹的預測結果。

分類問題常使用多數決，迴歸問題則常使用平均值。

核心觀念

本題考查機器學習中的「正則化」（regularization）。

正則化是在原本的目標函數中加入額外的懲罰項，使模型參數不宜過大、模型複雜度受到限制，以降低模型對訓練資料的過度擬合（overfitting），提升對未知資料的泛化能力。

一般形式為：

$$\text{Objective} = \text{Training Loss} + \lambda \cdot \text{Regularization Term}$$

其中：

• $\text{Training Loss}$：模型在訓練資料上的誤差。
• $\lambda$：正則化強度，控制懲罰項的重要程度。
• $\text{Regularization Term}$：對模型參數大小或複雜度的懲罰。

常見正則化方法包括：

L2 正則化：

$$J(\theta)=L(\theta)+\lambda\sum_i\theta_i^2$$

L1 正則化：

$$J(\theta)=L(\theta)+\lambda\sum_i|\theta_i|$$

L2 正則化傾向使參數變小；L1 正則化則可能使部分參數變成零，產生特徵選擇效果。

---

解題方法

判斷正則化的關鍵有三點：

1. 目的在於降低 overfitting。
2. 做法是在目標函數中加入額外項目。
3. 額外項目通常用來限制模型參數大小或模型複雜度。

符合上述三點的是選項 (C)。

需要注意的是，正則化並非單純「降低訓練資料上的表現」，而是透過限制模型複雜度，換取較好的泛化能力。適度正則化通常會使訓練誤差略為增加，但測試表現可能改善。

---

選項分析

(A) 錯誤

Regularization is a technique to increase model complexity in order to improve its performance on training data.

正則化的主要作用是限制模型複雜度、抑制過度擬合，不是增加模型複雜度。

單純追求訓練資料上的高表現，容易使模型記住訓練資料中的雜訊，反而造成 overfitting。因此本選項的「increase model complexity」與正則化目的相反。

---

(B) 錯誤

Regularization is a technique to decrease model complexity in order to reduce its performance on training data.

本選項前半段「decrease model complexity」方向接近正確，但後半段將正則化的目的說成「降低訓練資料上的表現」，並非正確定義。

正則化確實可能使訓練資料上的表現略微下降，例如訓練誤差增加；但這是限制模型複雜度所產生的結果，不是最終目的。正則化的真正目的，是降低 overfitting 並改善模型對未知資料的泛化能力。

---

(C) 正確

核心觀念

本題考查 LoRaWAN 的技術定位與主要特色。

• LoRa：一種低功耗廣域網路使用的無線調變技術，常以 Chirp Spread Spectrum（CSS，啁啾展頻）為基礎。
• LoRaWAN：建立在 LoRa 等無線實體層技術之上的通訊協定與網路架構，負責裝置與閘道器之間的資料傳輸、媒體存取、裝置管理與安全性。

LoRaWAN 的核心特色是：

1. 低功耗（Low Power）：適合電池供電、需長時間運作的感測器。
2. 長距離（Long Range）：在適當環境下可達數公里，遠高於一般短距離無線通訊。
3. 低資料傳輸率（Low Data Rate）：適合傳送溫度、濕度、位置、電表讀值等少量資料。
4. 廣域網路（Wide Area Network）：可涵蓋城市、農業區、工業區等大範圍。
5. 適用於物聯網（IoT）：特別適合大量、分散、低頻率傳輸的裝置。

其典型架構如下：

$$\text{IoT 終端裝置} \rightarrow \text{LoRaWAN 閘道器} \rightarrow \text{網路伺服器} \rightarrow \text{應用伺服器}$$

終端裝置通常不直接彼此溝通，而是透過閘道器將資料送往後端伺服器。

解題方法

判斷此題可從三個關鍵字切入：

• Low-power：是否強調低功耗？
• Long-distance：是否具備長距離傳輸能力？
• IoT devices：是否主要服務物聯網裝置？

只要選項同時符合「無線通訊、低功耗、長距離、物聯網」這四項特徵，即符合 LoRaWAN 的基本定位。

因此，選項 (A) 完整描述 LoRaWAN 的主要特色。

選項分析

(A) 正確

LoRaWAN is a wireless radio frequency communication technology, characterized by providing low-power long-distance communication suitable for IoT devices.

此選項指出 LoRaWAN：

• 是無線射頻通訊技術；
• 具備低功耗特性；
• 能進行長距離通訊；
• 適合物聯網裝置。

這些都是 LoRaWAN 的核心應用特徵，因此符合官方答案。

嚴格而言，LoRaWAN 本身較精確的定義是「低功耗廣域網路通訊協定與網路架構」，而 LoRa 是其常使用的實體層無線技術。不過在一般考試與物聯網概論的敘述中，將 LoRaWAN 概括稱為低功耗、長距離的無線通訊技術，屬於可接受的描述。

(B) 錯誤

LoRaWAN is a cellular network technology, with no significant difference from traditional cellular networks.

LoRaWAN 不是傳統電信業者所使用的蜂巢式行動網路技術，也不是 4G、5G 或 LTE 的同類型系統。

LoRaWAN 與傳統蜂巢式網路的差異包括：

核心觀念

本題考查生成式人工智慧中的「自回歸式序列生成」（autoregressive sequence generation）與循環神經網路（Recurrent Neural Network, RNN）的概念。

模型會根據前面已出現的 token，預測下一個 token：

$$P(x_1,x_2,\ldots,x_T) = \prod_{t=1}^{T}P(x_t\mid x_1,x_2,\ldots,x_{t-1})$$

其中：

• $x_t$：第 $t$ 個 token。
• $x_1,\ldots,x_{t-1}$：目前已知的前文。
• $P(x_t\mid x_1,\ldots,x_{t-1})$：模型根據前文預測下一個 token 的機率分布。

訓練時，模型通常以交叉熵（cross-entropy）作為損失函數，讓預測的下一個 token 盡量接近訓練資料中的正確答案。

Long short-term memory networks，簡稱 LSTM，是一種具備記憶機制的循環神經網路，能依序讀取文字，保留前文資訊，並根據先前 token 預測下一個 token。因此依照本題官方答案，選擇 LSTM。

---

解題方法

判斷本題的關鍵在於找出「能處理序列、保留前文資訊，並預測下一個元素」的模型。

LSTM 在每個時間步驟會接收目前輸入 $x_t$、前一時間步驟的隱藏狀態 $h_{t-1}$ 與記憶細胞狀態 $c_{t-1}$，再產生新的狀態：

$$(h_t,c_t)=\operatorname{LSTM}(x_t,h_{t-1},c_{t-1})$$

之後利用隱藏狀態計算下一個 token 的機率：

$$P(x_{t+1}\mid x_1,\ldots,x_t) = \operatorname{softmax}(Wh_t+b)$$

因此，LSTM 的核心特性正是：

1. 依序處理資料。
2. 將過去資訊保存在隱藏狀態與記憶細胞中。
3. 根據前面 token 預測後續 token。

所以本題依官方公布答案選擇 (D)。

---

選項分析

(A) Reinforcement learning：錯誤

Reinforcement learning（強化學習）是透過「狀態、行動、獎勵」學習策略的方法。模型會根據行動結果得到 reward，再逐步改善決策策略。

其主要目標是最大化累積獎勵：

$$\max_{\pi} \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^t r_t\right]$$

強化學習本身不是專門用來根據前文預測下一個 token 的序列模型。生成式 AI 中確實可能使用 reinforcement learning from human feedback（RLHF）調整語言模型，但那是模型訓練完成後的對齊方法，不是本題所描述的下一 token 預測機制。

---

(B) Markov chain Monte Carlo sampling：錯誤

Markov chain Monte Carlo（MCMC）是一類從複雜機率分布取樣的方法，常用於 Bayesian inference 與統計推論。

其基本精神是建立一條馬可夫鏈，使長期抽樣結果接近目標分布。MCMC 的重點是「由機率分布進行取樣」，而不是建立一個神經網路來學習下一個 token。

雖然文字生成過程也需要從 token 機率分布中取樣，但 MCMC 並不是本題所描述的主要模型架構。

---

(C) Variational autoencoder：錯誤

Variational autoencoder（VAE，變分自編碼器）由 encoder 與 decoder 組成：

核心觀念

MQTT（Message Queuing Telemetry Transport）是專為物聯網（IoT）設計的輕量級通訊協定，採用「發布／訂閱」（Publish／Subscribe）架構，裝置通常透過 MQTT Broker 傳遞訊息。

MQTT 的主要特色包括：

• 訊息標頭短，通訊負擔低。
• 適合低頻寬、不穩定的網路環境。
• 裝置端所需的運算與記憶體資源較少。
• 適合電池供電、運算能力有限的 IoT 裝置。
• 支援不同程度的訊息傳遞可靠性，例如 QoS 0、QoS 1、QoS 2。

因此，MQTT 最具代表性的設計重點是「輕量、低負擔、低功耗」，官方答案選擇 B。

解題方法

判斷 MQTT 的關鍵，在於掌握其設計目的。IoT 裝置常具有以下限制：

1. 電池容量有限。
2. 處理器與記憶體資源有限。
3. 網路頻寬有限。
4. 通訊連線可能不穩定。

MQTT 以輕量級訊息格式與發布／訂閱模型降低通訊成本，讓裝置不必持續與每個接收端建立複雜的直接連線。因此，最符合 MQTT 核心特色的描述是：

提供有效率的低功耗通訊。

故選擇 (B)。

選項分析

(A) 錯誤：強調即時通訊

MQTT 可用於即時性要求較高的 IoT 應用，例如感測器資料更新與遠端監控，但「即時通訊」不是 MQTT 最主要的核心特色。

實際延遲會受到網路狀況、Broker 負載、QoS 設定與裝置處理速度影響，因此 MQTT 並不保證嚴格的即時性。即時通訊也不是 MQTT 專屬功能，其他通訊協定同樣能提供即時資料傳輸。

(B) 正確：強調高效率、低功耗通訊

MQTT 是輕量級協定，適合資源受限的 IoT 裝置。其訊息格式簡潔、通訊負擔低，能降低頻寬使用量與裝置的處理成本，特別適合電池供電的感測器與嵌入式設備。

這正是 MQTT 在物聯網環境中的主要設計特色，因此本選項正確。