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

核心觀念

本題考查機器學習二元分類的評估指標，尤其是「實際有問題的螺絲，有多少被模型成功找出來」。

將資料分類如下：

• 實際有瑕疵，且被模型正確辨識：True Positive，簡寫為 $TP$
• 實際有瑕疵，但未被模型辨識：False Negative，簡寫為 $FN$
• 實際無瑕疵，但被模型誤判為有瑕疵：False Positive，簡寫為 $FP$
• 實際無瑕疵，且被模型正確判定無瑕疵：True Negative，簡寫為 $TN$

題目指出：

• 所有實際有瑕疵的螺絲共有 $P$ 顆
• 其中有 $n$ 顆被 ML 演算法辨識出來

因此，$P$ 是實際的正類總數：

$$P=TP+FN$$

而成功辨識出的瑕疵螺絲數 $n$ 對應於 $TP$，所以：

$$n=TP$$

題目所描述的比例為：

$$\frac{n}{P} = \frac{TP}{TP+FN}$$

這正是 Recall。

解題方法

Recall，又稱為召回率、敏感度，衡量的是：

在所有實際為正類的樣本中，模型成功找出的比例。

其公式為：

$$\text{Recall} = \frac{TP}{TP+FN}$$

套用本題：

• 實際有瑕疵的螺絲總數為 $P$
• 成功辨識出的瑕疵螺絲數為 $n$
• 未被辨識出的瑕疵螺絲數為 $P-n$

因此：

$$\text{Recall} = \frac{n}{P}$$

所以正確選項為 (D) Recall。

選項分析

(A) F1-score

F1-score 是 Precision 與 Recall 的調和平均數：

$$F1 = \frac{2 \cdot \text{Precision}\cdot\text{Recall}} {\text{Precision}+\text{Recall}}$$

其中：

$$\text{Precision} = \frac{TP}{TP+FP}$$

核心觀念

二元樹的後序走訪（post-order traversal）順序固定為：

$$\text{左子樹} \rightarrow \text{右子樹} \rightarrow \text{根節點}$$

本題樹的根節點為 $49$。

解題方法

依照「左、右、根」逐層走訪：

1. 走訪 $49$ 的左子樹，以 $35$ 為根：

• $35$ 的左子樹為 $8$，而 $8$ 的右子節點為 $31$，所以順序為 $31, 8$。
• $35$ 的右子節點為 $47$。
• 因此左子樹的後序結果為：

$31, 8, 47, 35$

2. 走訪 $49$ 的右子樹，以 $84$ 為根：

• $84$ 的左子樹為 $83$，而 $83$ 的左子節點為 $61$，所以順序為 $61, 83$。
• $84$ 的右子樹為 $96$，而 $96$ 的左子節點為 $91$，所以順序為 $91, 96$。
• 因此右子樹的後序結果為：

$61, 83, 91, 96, 84$

3. 最後拜訪整棵樹的根節點 $49$。

完整結果為：

$$31, 8, 47, 35, 61, 83, 91, 96, 84, 49$$

因此選擇 (B)。

選項分析

核心觀念

本題考查機器學習與類神經網路的基本概念，包括：

• 訊號處理在資料前處理中的角色
• 訓練誤差、測試誤差與過度擬合
• 神經網路的連結權重
• 最佳化方法與全域最小值
• Batch learning 與 sequential learning 的梯度估計

題目問的是 INCORRECT，因此應找出敘述不正確的選項。

---

解題方法

判斷各選項是否符合機器學習的基本定義：

1. 訊號處理是否可作為資料前處理工具。
2. 訓練與測試誤差的變化，是否能正確代表 overfitting。
3. 神經元間的 connection weights 是否為神經網路儲存知識的核心。
4. 最佳化方法是否通常難以保證找到 global minimum。
5. Batch 與 sequential learning 所計算的梯度，哪一種較接近真正的整體梯度。

其中第 5 點可由梯度公式直接判斷。假設總誤差函數為

$$E(\mathbf{w})=\frac{1}{N}\sum_{i=1}^{N}E_i(\mathbf{w}),$$

則完整資料的梯度為

$$\nabla E(\mathbf{w})=\frac{1}{N}\sum_{i=1}^{N}\nabla E_i(\mathbf{w}).$$

Batch learning 使用全部 $N$ 筆資料計算梯度，因此可得到整體誤差函數的精確梯度；sequential learning 通常每次只使用一筆資料或一小批資料，得到的是帶有隨機誤差的梯度估計。

---

選項分析

(A) 正確

訊號處理方法可以作為機器學習的重要資料前處理工具。

例如對聲音、影像或感測器資料，可以使用：

• 去除雜訊
• 濾波
• Fourier transform
• 頻譜分析
• 特徵擷取
• 正規化

這些處理能改善資料品質、降低雜訊，並將原始訊號轉換成較適合模型學習的特徵。因此，signal processing methods 確實可以是非常有價值的 data pre-processing tool。

---

(B) 正確，但敘述有用語上的爭議

在神經網路訓練過程中，若誤差持續變大，代表目前的訓練可能使模型表現惡化。此時停止訓練，可以避免模型繼續朝錯誤方向更新。

一般常用 early stopping 來避免過度擬合，其基本做法是：

• 訓練誤差持續下降時，模型仍在學習。
• 驗證誤差或測試誤差開始上升時，表示模型可能開始記憶訓練資料。
• 此時停止訓練，保留誤差最低時的模型。

嚴格而言，典型的 overfitting 型態是：

$$\text{training error下降，但 testing error上升}.$$

因此，題目所寫的「training and testing errors 都 becoming larger and larger」並不是最標準的過度擬合判準。若訓練誤差與測試誤差同時上升，較可能表示學習率過大、最佳化不穩定或模型訓練失敗。

不過依本題官方答案，(B) 被視為可接受的「誤差持續惡化時停止訓練」敘述；真正被判定為錯誤的是 (E)。

---

(C) 正確

在類神經網路中，神經元之間的連結通常以權重 $w_{ij}$ 表示。神經元接收到輸入後，會先進行加權總和：

$$z=\sum_i w_i x_i+b,$$

核心觀念

本題考查作業系統的虛擬記憶體與頁面置換（page replacement），指定使用最近最少使用（Least Recently Used, LRU）策略，且記憶體有 $5$ 個 page frames。

LRU 的規則是：

• 若參考頁面已在 frame 中，稱為 page hit，不發生 page fault。
• 若參考頁面不在 frame 中，稱為 page fault。
• 當 $5$ 個 frame 已滿時，淘汰「最久沒有被使用」的頁面。

本題的參考字串為：

$$1,3,6,7,2,4,6,2,5,6,9,1,2,1,4,3,4,5,7,8$$

---

解題方法

以「最久未使用者在左、最新使用者在右」記錄 frame 內容。每次命中後，將該頁面移到最右側；發生置換時，淘汰最左側頁面。

次序	參考頁	結果	LRU frames（左側最久未使用）	置換 fault 次數
1	1	Fault	1	0
2	3	Fault	1, 3	0
3	6	Fault	1, 3, 6	0
4	7	Fault	1, 3, 6, 7	0
5	2	Fault	1, 3, 6, 7, 2	0
6	4	Fault，淘汰 1	3, 6, 7, 2, 4	1
7	6	Hit	3, 7, 2, 4, 6	1
8	2	Hit	3, 7, 4, 6, 2	1
9	5	Fault，淘汰 3	7, 4, 6, 2, 5	2
10	6	Hit	7, 4, 2, 5, 6	2
11	9	Fault，淘汰 7	4, 2, 5, 6, 9	3
12	1	Fault，淘汰 4	2, 5, 6, 9, 1	4
13	2	Hit	5, 6, 9, 1, 2	4
14	1	Hit	5, 6, 9, 2, 1	4
15	4	Fault，淘汰 5	6, 9, 2, 1, 4	5
16	3	Fault，淘汰 6	9, 2, 1, 4, 3	6
17	4	Hit	9, 2, 1, 3, 4	6
18	5	Fault，淘汰 9	2, 1, 3, 4, 5	7

核心觀念

本題考查三種深度學習模型的基本功能與訓練方式：

• Auto-encoder：透過較少的潛在特徵重建原始輸入。
• GAN（Generative Adversarial Network）：由 Generator 產生樣本，Discriminator 判別樣本是真實資料或生成資料。
• CNN（Convolutional Neural Network）：利用卷積運算擷取局部特徵，卷積本質上可視為一種 filtering operation。
• RNN（Recurrent Neural Network）：處理序列資料，訓練時通常須沿時間展開並使用 Backpropagation Through Time（BPTT）。

解題時只要判斷各選項是否符合上述模型的定義與訓練機制，即可找出不正確的敘述。

---

解題方法

逐一檢查各敘述：

1. Auto-encoder 是否使用較少特徵重建輸入？
2. GAN 的 Discriminator 是否同時接觸真實與生成樣本？
3. RNN 的訓練是否比 CNN 容易？
4. GAN 的 Generator 是否提供生成樣本給 Discriminator 判別？
5. CNN 的 convolution 是否具有 filtering 的功能？

其中第 3 項與深度學習的訓練特性相反。RNN 通常因時間序列反向傳播與梯度消失問題，訓練難度高於一般 CNN，因此選 (C)。

---

選項分析

(A) The basic objective of auto-encoder is to reproduce its inputs by using a smaller set of features.

此敘述正確。

Auto-encoder 通常包含：

1. Encoder：將輸入 $x$ 壓縮成較低維度的特徵表示 $z$。
2. Decoder：由 $z$ 重建輸出 $\hat{x}$。

可表示為：

$$z = f_{\theta}(x), \qquad \hat{x} = g_{\phi}(z)$$

訓練目標是使重建結果 $\hat{x}$ 儘可能接近原始輸入 $x$，例如最小化重建誤差：

$$L(x,\hat{x}) = \|x-\hat{x}\|^2$$

當潛在特徵 $z$ 的維度小於輸入維度時，模型必須學習保留資料中最重要的資訊，因此選項所述符合 auto-encoder 的基本概念。

---

(B) In generative adversarial network (GAN), the discriminator often has access to both the synthetic and real sample. Its task is to try to differentiate them as accurate as possible.

此敘述正確。

GAN 由兩個模型組成：

• Generator $G$：根據隨機雜訊 $z$ 產生假樣本 $G(z)$。
• Discriminator $D$：判斷輸入樣本是真實資料，或是 Generator 產生的假資料。

Discriminator 會接收真實樣本 $x$ 與生成樣本 $G(z)$，並嘗試提高判別正確率。典型的 GAN 目標函數為：

$$\min_G \max_D V(D,G) = \mathbb{E}_{x\sim p_{\text{data}}} [\log D(x)] + \mathbb{E}_{z\sim p_z} [\log(1-D(G(z)))]$$

因此，Discriminator 的確會同時接觸 real samples 與 synthetic samples，並學習區分兩者。

---

核心觀念

本題考查雜湊表的：

1. 除法雜湊法（division hash algorithm）
2. 雜湊函數 $h(k)=k\bmod m$
3. 碰撞（collision）處理
4. 依雜湊表索引 $0$ 到 $6$ 依序讀取資料

雜湊表共有 $7$ 個位置，因此雜湊函數為：

$$h(k)=k\bmod 7$$

當不同鍵值算出相同索引時，就會發生碰撞。本題採用鏈結法（separate chaining）處理碰撞，同一索引中的資料依插入順序排列。

---

解題方法

依序計算各鍵值的雜湊位置：

插入順序	鍵值 $k$	$k\bmod 7$	所在索引
1	24	$24\bmod 7=3$	3
2	30	$30\bmod 7=2$	2
3	3	$3\bmod 7=3$	3
4	18	$18\bmod 7=4$	4
5	15	$15\bmod 7=1$	1
6	21	$21\bmod 7=0$	0
7	9	$9\bmod 7=2$	2

因此雜湊表內容如下：

索引	鏈結內容
0	21
1	15
2	30 → 9
3	24 → 3
4	18
5	空
6	空

依索引 $0$ 到 $6$ 讀取，得到：

$$21,\ 15,\ 30,\ 9,\ 24,\ 3,\ 18$$

這正是選項（E）。

---

選項分析

（A）24, 30, 3, 18, 15, 21, 9

此順序等同於原始插入順序，並非依索引 $0$ 到 $6$ 讀取。

例如：

• 24 應在索引 3，卻排在最前面
• 21 應在索引 0，卻排在倒數第二個位置

因此錯誤。

（B）3, 9, 15, 18, 21, 24, 30

此順序接近依鍵值大小排列，並非依雜湊索引排列。

例如：

核心觀念

本題考的是磁碟排程中的 Elevator algorithm，也就是 SCAN 演算法。

SCAN 的運作方式如下：

1. 磁碟讀寫頭依目前方向移動。
2. 沿途服務該方向上的所有請求。
3. 到達磁碟邊界後反向。
4. 再服務另一方向的請求。
5. 總 seek operations 通常是指讀寫頭移動的總磁軌距離，而不是請求筆數。

本題已知：

• Request sequence：$\{182,70,29,60,95,7,41,120\}$
• Initial head position：$50$
• Direction：left
• 磁碟左側邊界視為磁軌 $0$

因此，讀寫頭會先向左移動至磁軌 $0$，再反向向右服務其餘請求。

---

解題方法

先將請求依照初始位置 $50$ 分成左右兩側：

• 左側請求：$41,29,7$
• 右側請求：$60,70,95,120,182$

由於初始方向為 left，服務順序為：

$$50\rightarrow41\rightarrow29\rightarrow7\rightarrow0 \rightarrow60\rightarrow70\rightarrow95\rightarrow120\rightarrow182$$

其中，$0$ 是 SCAN 演算法向左移動時所到達的磁碟邊界。

逐段計算讀寫頭移動距離：

移動路徑	Seek 距離
$50\rightarrow41$	$50-41=9$
$41\rightarrow29$	$41-29=12$
$29\rightarrow7$	$29-7=22$
$7\rightarrow0$	$7-0=7$
$0\rightarrow60$	$60-0=60$
$60\rightarrow70$	$70-60=10$
$70\rightarrow95$	$95-70=25$
$95\rightarrow120$	$120-95=25$
$120\rightarrow182$	$182-120=62$

總 seek 距離為：

$$9+12+22+7+60+10+25+25+62 =232$$

也可以用區段法快速計算：

• 向左：$50\rightarrow0$，距離為 $50$
• 反向向右：$0\rightarrow182$，距離為 $182$

因此：

$$50+182=232$$

題目問的是完成所有請求的總移動距離，因此讀寫頭服務到最後一個請求磁軌 $182$ 即可停止，不必再移動到右側磁碟邊界。

---

逐步追蹤 Trace

步驟	讀寫頭位置	動作
0	$50$	初始位置，方向向左
1	$41$	服務請求 $41$
2	$29$	服務請求 $29$
3	$7$	服務請求 $7$
4	$0$	到達左側邊界，反向
5	$60$	服務請求 $60$
6	$70$	服務請求 $70$
7	$95$	服務請求 $95$
8	$120$	服務請求 $120$

核心觀念

本題考的是作業系統中的 虛擬記憶體（virtual memory）。

虛擬記憶體讓程式使用的「邏輯記憶體空間」大於電腦實際安裝的 RAM。作業系統會將程式分成數個區塊，僅把目前執行所需的部分載入 RAM，其餘部分暫存在硬碟等輔助儲存裝置中；當程式需要尚未載入的區塊時，再將其換入 RAM。

因此，即使實體 RAM 容量較小，電腦仍能執行大小超過 RAM 的程式。

虛擬記憶體常搭配下列機制實作：

• Paging（分頁）：將虛擬記憶體切成固定大小的 page，將實體記憶體切成固定大小的 frame。
• Page table（頁表）：記錄虛擬頁面與實體頁框的對應關係。
• Page fault（頁面錯誤）：程式存取的頁面不在 RAM 時，由作業系統從磁碟載入。

概念上可表示為：

$$\text{虛擬記憶體空間} = \text{RAM 可用空間} + \text{磁碟上的暫存空間}$$

這個關係是概念性描述，並非表示磁碟與 RAM 的存取速度相同。磁碟速度遠低於 RAM，因此過度使用虛擬記憶體會造成效能下降。

解題方法

題幹關鍵是：

allows a computer with small RAM to execute a program of much bigger size

題目描述「實體 RAM 很小，但仍能執行遠大於 RAM 的程式」，直接對應到虛擬記憶體的功能。

判斷步驟如下：

1. 找出題幹的功能描述：以較小 RAM 執行較大程式。
2. 判斷這需要將程式的一部分暫存於磁碟，並依需求載入 RAM。
3. 這種由作業系統提供較大邏輯記憶體空間的技術稱為 virtual memory。
4. 因此選擇 (B)。

選項分析

(A) paging

**Paging（分頁）**是記憶體管理機制，將記憶體切割成固定大小的頁面與頁框，以便於配置及搬移資料。

分頁確實常是虛擬記憶體的實作基礎，但「分頁」本身主要描述記憶體配置方式，不直接完整表達「利用磁碟空間延伸可用記憶體，使大型程式得以執行」這項功能。

因此，本題若詢問虛擬記憶體採用的管理方式，paging 可成為相關答案；但題目詢問的是整體技術名稱，官方答案為 virtual memory，所以 (A) 不選。

(B) virtual memory

核心觀念

本題考查「不同進位制數字轉換為十進位」的位值表示法。

在 $r$ 進位中，三位數 $(654)_r$ 的各位值分別為：

• $6$ 位於 $r^2$ 位
• $5$ 位於 $r^1$ 位
• $4$ 位於 $r^0$ 位

因此：

$$(654)_r=6r^2+5r+4$$

題目給定：

$$(654)_r=(333)_{10}$$

所以可列出方程式：

$$6r^2+5r+4=333$$

---

解題方法

將方程式整理：

$$6r^2+5r-329=0$$

由選項逐一代入驗算即可。

代入 $r=7$：

$$6(7^2)+5(7)+4 =6(49)+35+4 =294+35+4 =333$$

因此：

$$(654)_7=333_{10}$$

故正確答案為 $r=7$。

也可使用公式解二次方程式：

$$r=\frac{-5\pm\sqrt{5^2-4(6)(-329)}}{2(6)}$$ $$r=\frac{-5\pm\sqrt{7921}}{12} =\frac{-5\pm89}{12}$$

得到：

$$r=7 \quad \text{或} \quad r=-\frac{47}{6}$$

進位制必須為正整數，因此只有 $r=7$ 合理。

---

選項分析

• (A) $r=5$：錯誤

核心觀念

本題考查 8-bit 二補數（2’s complement）有號整數的表示範圍與溢位（overflow）判斷。

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

$$-2^{7}\sim 2^{7}-1=-128\sim127$$

判斷二補數加法是否溢位的規則：

• 兩個正數相加，結果變成負數：溢位。
• 兩個負數相加，結果變成正數：溢位。
• 一正一負相加：不會發生有號整數溢位。

也可以使用位元規則判斷：若兩個加數的最高位相同，但結果的最高位不同，即發生 overflow。

---

解題方法

先將各選項的 8-bit 二補數轉換成十進位，再檢查加總結果是否超出 $-128$ 到 $127$ 的範圍。

負數的二補數轉換方式：

1. 將位元反相。
2. 加 $1$。
3. 加上負號。

---

選項分析

(A) $00000001, 11111111$

• $00000001=1$
• $11111111$ 為負數，其絕對值：

$$00000000+1=00000001$$

因此：

$$11111111=-1$$

相加：

$$1+(-1)=0$$

結果為 $0$，在表示範圍 $-128\sim127$ 內，且一正一負相加不會 overflow。

所以 (A) 錯誤。

---

(B) $00000001, 10000000$

• $00000001=1$
• $10000000$ 是 8-bit 二補數中最小值：

$$10000000=-128$$

相加：

$$1+(-128)=-127$$

二進位加法為：

$$00000001+10000000=10000001$$

$10000001$ 代表 $-127$，仍在 $-128\sim127$ 的範圍內，因此沒有 overflow。

所以 (B) 錯誤。

---

(C) $10000001, 10101010$

兩個數的最高位皆為 $1$，表示兩者都是負數。

對 $10000001$：

$$01111110+1=01111111$$

因此：

$$10000001=-127$$

對 $10101010$：

$$01010101+1=01010110=86$$

因此：

$$10101010=-86$$

實際加總為：

$$-127+(-86)=-213$$

核心觀念

本題考查三個 C 語言觀念：

1. 指標傳址

• foo(&a, a) 將變數 a 的位址傳入 ptr。
• 因此 *ptr 就是 a 本身，函式內修改 *ptr 會直接改變主程式中的 a。

2. 遞迴函式

if (num == 1)
return 1;
else
return num + foo(ptr, num-1);

3. 等差級數累加

• a 每次增加目前的 num。
• foo 的回傳值則是從 $1$ 累加到初始的 num。

---

解題方法

設初始值為 $X$。

一、計算 a 的最後值

初始時：

int a = X;
int b = foo(&a, a);

第一次呼叫時，num=X。之後依序遞迴：

$$X,\ X-1,\ X-2,\ \ldots,\ 1$$

每次執行：

*ptr = *ptr + num;

因為 ptr 指向 a，所以 a 總共增加：

$$X+(X-1)+(X-2)+\cdots+1 = \frac{X(X+1)}{2}$$

因此最後的 a 為：

$$Y=X+\frac{X(X+1)}{2}$$

二、計算 b 的回傳值

令 $F(n)$ 表示 foo(ptr,n) 的回傳值，則：

$$F(1)=1$$

且當 $n>1$ 時：

$$F(n)=n+F(n-1)$$

因此：

$$F(X)=X+(X-1)+\cdots+1 =\frac{X(X+1)}{2}$$

所以：

$$Z=\frac{X(X+1)}{2}$$

---

以 $X=5$ 逐步追蹤

初始：

a = 5

遞迴呼叫	執行加法後的 a	回傳值
foo(&a, 5)	$5+5=10$	$5+F(4)$
foo(&a, 4)	$10+4=14$	$4+F(3)$
foo(&a, 3)	$14+3=17$	$3+F(2)$
foo(&a, 2)	$17+2=19$	$2+F(1)$
foo(&a, 1)	$19+1=20$	$1$

回溯計算：

$$F(1)=1$$ $$F(2)=2+1=3$$ $$F(3)=3+3=6$$

核心觀念

本題考查不同指令類別混合執行時的「平均 CPI（Cycles Per Instruction，每指令週期數）」。

各指令類別的 CPI 不同，因此整段程式的 CPI 不能直接取算術平均，而要依照各類別的指令數量加權計算：

$$\text{平均 CPI} = \frac{\text{總執行週期數}}{\text{總指令數}}$$

其中：

$$\text{總執行週期數} = \sum (\text{各類指令數} \times \text{該類指令 CPI})$$

---

解題方法

Code sequence 1

指令數量如下：

• A 類：$1$ 條，每條需要 $3$ cycles
• B 類：$1$ 條，每條需要 $2$ cycles
• C 類：$3$ 條，每條需要 $5$ cycles

總執行週期數：

$$1 \times 3 + 1 \times 2 + 3 \times 5 =3+2+15 =20$$

總指令數：

$$1+1+3=5$$

因此 Code sequence 1 的 CPI 為：

$$\text{CPI}_1=\frac{20}{5}=4$$

---

Code sequence 2

指令數量如下：

• A 類：$1$ 條，每條需要 $3$ cycles
• B 類：$4$ 條，每條需要 $2$ cycles
• C 類：$2$ 條，每條需要 $5$ cycles

總執行週期數：

$$1 \times 3 + 4 \times 2 + 2 \times 5 =3+8+10 =21$$

總指令數：

$$1+4+2=7$$

因此 Code sequence 2 的 CPI 為：

$$\text{CPI}_2=\frac{21}{7}=3$$

所以兩組程式的 CPI 依序為：

$$(\text{CPI}_1,\text{CPI}_2)=(4,3)$$

---

選項分析

(A) $(4,3)$

正確。

• Code sequence 1：

$\frac{1(3)+1(2)+3(5)}{1+1+3}=4$

• Code sequence 2：

核心觀念

RSA 解密使用私密金鑰 $(d,N)$，其公式為：

$$M \equiv C^d \pmod N$$

其中：

• $C$：密文（ciphertext）
• $M$：明文（plaintext）
• $d$：私密指數
• $N$：模數

題目給定：

$$C=11,\qquad d=5,\qquad N=21$$

因此明文為：

$$M \equiv 11^5 \pmod{21}$$

解題方法

直接計算模指數：

$$11^2=121$$

將 $121$ 除以 $21$：

$$121=21\times5+16$$

所以：

$$11^2\equiv16\pmod{21}$$

接著計算四次方：

$$11^4\equiv16^2=256\pmod{21}$$

由於：

$$256=21\times12+4$$

因此：

$$11^4\equiv4\pmod{21}$$

最後：

$$11^5=11^4\cdot11$$

所以：

$$11^5\equiv4\cdot11=44\equiv2\pmod{21}$$

因為：

$$44=21\times2+2$$

故對應的明文為：

$$M=2$$

金鑰關係驗證

RSA 中通常要求：

$$ed\equiv1\pmod{\varphi(N)}$$

因為：

$$N=21=3\times7$$

所以：

核心觀念

本題考查 Karnaugh map（卡諾圖）中相鄰最小項的合併，以及布林代數的化簡規則。

原式可讀為：

$$X=ABC+A\overline{B}C+AB\overline{C}D+\overline{A}B\overline{C}\overline{D} +\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}$$

其中未出現的變數代表該變數可為 $0$ 或 $1$。

---

解題方法

將相鄰項兩兩合併。

第一組：

$$ABC+A\overline{B}C =AC(B+\overline{B}) =AC$$

因為 $B+\overline{B}=1$。

第二組：

$$AB\overline{C}D+\overline{A}B\overline{C}D =B\overline{C}D(A+\overline{A}) =B\overline{C}D$$

第三組：

$$\overline{A}\,\overline{B}\,\overline{C}\,\overline{D} +\overline{A}B\overline{C}\overline{D} =\overline{A}\,\overline{C}\,\overline{D} (\overline{B}+B) =\overline{A}\,\overline{C}\,\overline{D}$$

因此：

$$X=AC+B\overline{C}D+\overline{A}\,\overline{C}\,\overline{D}$$

這正是選項 (E)。

---

選項分析

(A) $X=ABC+B\overline{C}D+\overline{A}\,\overline{C}\,\overline{D}$

錯誤。第一組 $ABC+A\overline{B}C$ 應合併為 $AC$，不能只保留 $ABC$，否則會漏掉 $A\overline{B}C$ 的情況。

---

核心觀念

本題考查非搶先式最短工作優先排程（Non-Preemptive Shortest Job First, SJF）。

SJF 的規則是：每次 CPU 選擇「尚未執行且 CPU burst time 最短」的程序。非搶先式表示程序一旦開始執行，必須完成後，CPU 才能選擇下一個程序。

程序的等待時間定義為：

$$\text{Waiting Time}=\text{開始執行時間}-\text{到達時間}$$

本題所有程序均於時間 $0$ 到達，因此只需計算各程序開始執行的時間。

---

解題方法

各程序的 CPU burst time 如下：

Process	Burst time
P1	4
P2	6
P3	5
P4	1

依照 burst time 由小到大排序：

$$P4(1)\rightarrow P1(4)\rightarrow P3(5)\rightarrow P2(6)$$

因為所有程序都在時間 $0$ 到達，所以不需考慮後續到達的程序。

排程與等待時間如下：

執行順序	Process	Burst time	開始時間	等待時間
1	P4	1	0	$0-0=0$
2	P1	4	1	$1-0=1$
3	P3	5	5	$5-0=5$
4	P2	6	10	$10-0=10$

因此平均等待時間為：

$$\text{Average Waiting Time} =\frac{0+1+5+10}{4} =\frac{16}{4} =4$$

所以答案為選項 (A) 4。

---

選項分析

• (A) 4：正確。
  依非搶先式 SJF 排程順序 $P4\rightarrow P1\rightarrow P3\rightarrow P2$，平均等待時間為 $4$ 毫秒。

核心觀念

本題考查 IPv4 子網切割（subnetting）、CIDR 表示法與子網路遮罩的換算。

• /26 表示前 26 位為網路位元，原網路共有：

$$2^{32-26}=2^6=64$$

個 IP 位址。

• 要切成兩個子網路，每個子網路有 32 個位址：

$$32=2^5$$

因此主機位元需要保留 5 位，網路位元數為：

$$32-5=27$$

所以每個子網路應為 /27。

---

解題方法

原網路為：

$$192.115.227.128/26$$

要將 /26 切成兩個大小相同的子網路，相當於從主機位元借用 1 位：

$$/26 \rightarrow /27$$

/27 的遮罩為：

$$11111111.11111111.11111111.11100000$$

將二進位轉換為十進位：

$$255.255.255.224$$

因此兩個子網路的遮罩皆為：

$$\boxed{255.255.255.224}$$

原 /26 網段範圍為 192.115.227.128 至 192.115.227.191，切割後為：

子網路	位址範圍	位址數
第 1 個子網路	192.115.227.128～192.115.227.159	32
第 2 個子網路	192.115.227.160～192.115.227.191	32

題目特別註明忽略子網路位址、廣播位址等是否可配置，因此直接以每個子網路的總位址數 32 計算。

---

選項分析

(A) 255.255.255.248

最後一段 248 的二進位為：

$$248=11111000_2$$

共有 29 個網路位元，即 /29。每個子網路位址數為：

$$2^{32-29}=2^3=8$$

核心觀念

本題考查 SQL 的 INNER JOIN（內部連接）。

SELECT students.Name, math.Score
FROM students
INNER JOIN math
ON students.S_ID = math.S_ID;

INNER JOIN 只會保留兩個資料表中，連接欄位值相同的資料列。本題的連接條件為：

$$students.S\_ID = math.S\_ID$$

因此，必須比對兩表的 S_ID。

解題方法

逐筆比對 math 表中的 S_ID：

math.S_ID	math.Score	students 中是否有相同 S_ID	對應姓名
1010003	80	有	Sam
1010011	55	無	不列入
1010005	60	無	不列入
1010001	95	有	Jerry
1010006	73	無	不列入

因此，INNER JOIN 的結果只包含：

Name	Score
Sam	80
Jerry	95

題目已將 Jerry 的姓名與空格位置固定呈現為：

Name	Score
(A)	95
Jerry	(B)

所以：

• $(A) = \text{Sam}$
• $(B) = 80$

選項分析

• (A) Name = Sam, Score = 80：正確。
  Sam 的 S_ID 為 1010003，而 math 表中有相同的 S_ID，其成績為 $80$。

核心觀念

本題考查排序演算法的「穩定性」（stability）。

若兩筆資料的排序鍵值相同，排序後仍維持它們在原始陣列中的先後順序，則稱為穩定排序；若相同鍵值的資料順序可能被交換，則稱為不穩定排序。

例如原始資料為：

$$[A(2),\ B(2),\ C(1)]$$

其中括號內是排序鍵值，$A$ 與 $B$ 的鍵值相同，且 $A$ 原本位於 $B$ 前面。

穩定排序後應為：

$$[C(1),\ A(2),\ B(2)]$$

若結果為：

$$[C(1),\ B(2),\ A(2)]$$

雖然鍵值已排序正確，但 $A$、$B$ 的相對順序改變，因此是不穩定排序。

---

解題方法

判斷排序演算法是否穩定，主要觀察：

1. 相同鍵值的元素是否可能互相交換。
2. 演算法是否會讓距離較遠的元素直接交換位置。
3. 合併或插入時，遇到相同鍵值是否保留原始先後順序。

本題依一般教科書中的標準實作判斷：

• Bubble Sort：穩定
• Heap Sort：不穩定
• Merge Sort：穩定
• Radix Sort：穩定，但前提是每一位所使用的排序方法穩定
• Insertion Sort：穩定

因此官方答案為 (B) Heap Sort。

---

選項分析

(A) Bubble Sort：錯誤

Bubble Sort 通常只在前一元素大於後一元素時交換：

if A[j] > A[j + 1]:
 swap(A[j], A[j + 1])

若兩元素鍵值相同，因為不滿足 $A[j] > A[j+1]$，所以不會交換。因此相同鍵值的元素會保留原本的相對順序。

所以標準 Bubble Sort 是穩定排序。

時間複雜度：

• 最佳情況：$O(n)$，已排序且採用提早終止
• 平均、最差情況：$O(n^2)$
• 額外空間：$O(1)$

---

(B) Heap Sort：正確

Heap Sort 透過建立 heap，反覆將 heap 的根節點與末端元素交換。

這種交換可能跨越多個元素，使相同鍵值的元素相對順序改變，因此 Heap Sort 不具穩定性。

例如原始資料為：

$$[A(2),\ B(2),\ C(1)]$$

此陣列已符合 max heap 的條件。進行第一次取出最大值時，根節點 $A(2)$ 與末端的 $C(1)$ 交換：

$$[A(2),\ B(2),\ C(1)] \rightarrow [C(1),\ B(2),\ A(2)]$$

接著調整 heap，並再次取出 $B(2)$。最後排序結果為：

$$[C(1),\ B(2),\ A(2)]$$

原本相同鍵值的順序是 $A$ 在 $B$ 前，排序後卻變成 $B$ 在 $A$ 前，故順序被改變。

時間複雜度：

$$O(n\log n)$$

額外空間通常為：

$$O(1)$$

Heap Sort 的重點是「原地排序且不穩定」。

---

(C) Merge Sort：錯誤

Merge Sort 的合併階段，若左右兩邊目前元素鍵值相同，優先取左邊元素即可保留原始順序：

核心觀念

本題考查完全二元樹（Complete Binary Tree）的結構、層數、樹高與葉節點數量。

完全二元樹具有以下特性：

1. 除最後一層外，其餘各層皆填滿。
2. 最後一層的節點由左至右連續排列。
3. 若節點沒有左子節點，則不可能有右子節點，因此該節點必為葉節點。
4. 若以陣列採「由根開始、逐層由左至右」編號，節點編號為 $i$ 時：

• 左子節點位置為 $2i$
• 右子節點位置為 $2i+1$
• 葉節點位置通常為 $\lfloor n/2 \rfloor+1$ 至 $n$

本題共有 $n=1000$ 個節點，且根節點編號為 $1$。

---

解題方法

1. 判斷節點 377 所在的 level

若根節點所在層定義為第 1 層，則第 $k$ 層包含的節點編號範圍為：

$$2^{k-1}\ \text{至}\ 2^k-1$$

第 9 層的編號範圍為：

$$2^8=256$$

至

$$2^9-1=511$$

因為：

$$256\leq 377\leq 511$$

所以節點 $377$ 位於第 9 層。

---

2. 判斷樹高

第 10 層的第一個節點編號為：

$$2^9=512$$

第 10 層最多可容納至：

$$2^{10}-1=1023$$

由於 $1000$ 落在 $512$ 至 $1023$ 之間，因此第 10 層有節點，樹的高度為 10 層。

也可利用：

$$\lfloor \log_2 1000\rfloor+1 = 9+1 = 10$$

---

3. 判斷葉節點數量

在以陣列表示的完全二元樹中，編號大於 $\lfloor n/2\rfloor$ 的節點沒有子節點，因此皆為葉節點。

本題：

$$\left\lfloor\frac{1000}{2}\right\rfloor=500$$

所以葉節點編號為：

$$501,502,\ldots,1000$$

數量為：

$$1000-500=500$$

因此不是 501 個，而是 500 個。

---

選項分析

核心觀念

本題考查圖論中的最短路徑問題（shortest path problem）及其常見演算法：

• Dijkstra’s algorithm：適用於所有邊權重皆為非負數的圖。
• Bellman–Ford algorithm：可處理含有負邊權重的圖，並能偵測負權重循環。
• 最短路徑定義：在圖中尋找兩個頂點之間，使路徑上所有邊權重總和最小的路徑。

其中，若圖中存在可到達的負權重循環，最短距離可能沒有有限值，因為沿著負循環繞行即可使總權重無限減小。

---

解題方法

本題問的是 INCORRECT，也就是找出錯誤的敘述。

判斷重點在於各演算法能否處理負邊權重：

1. Dijkstra 需要邊權重皆為非負數。
2. Bellman–Ford 可處理負邊權重。
3. 最短路徑就是使邊權重總和最小的路徑。
4. 最短路徑問題可定義於無向圖、有向圖或混合圖。

因此，聲稱 Dijkstra 同時能處理非負與負邊權重的選項錯誤，答案為 (A)。

---

選項分析

(A) Dijkstra's algorithm solves the single-source shortest path problem with both non-negative and negative edge weights.

錯誤。

Dijkstra’s algorithm 的正確適用條件是：

$$w(u,v) \geq 0$$

也就是圖中的每一條邊權重都必須是非負數。

Dijkstra 的核心機制是：

1. 從尚未確定的頂點中，選出目前暫定距離最小的頂點。
2. 將該頂點標記為「最短距離已確定」。
3. 利用該頂點進行邊鬆弛（relaxation）。

這種「一旦選定就不必再修改」的貪婪策略，依賴於邊權重非負。若存在負邊，原本看似最短的路徑，之後可能透過負邊被進一步縮短，因此先前確定的距離可能不再正確。

例如：

S ──2──> A ──(-5)──> B
 \ 
 ──1──────────────────> B

直接由 $S$ 到 $B$ 的距離為 $1$，但經過 $A$ 的路徑距離為：

$$2+(-5)=-3$$

若演算法過早將 $B$ 的距離視為確定值，就可能得到錯誤結果。

因此，Dijkstra 一般不能處理負邊權重。本選項為本題錯誤敘述。

---

(B) Bellman–Ford algorithm solves the single-source problem with possible negative edge weights.

正確。

Bellman–Ford 可處理含有負邊權重的單一起點最短路徑問題（single-source shortest path problem）。

其主要作法是反覆對所有邊進行鬆弛：

$$d[v] \leftarrow \min\bigl(d[v],\, d[u]+w(u,v)\bigr)$$

若圖有 $|V|$ 個頂點，最多只需進行 $|V|-1$ 輪鬆弛，因為不包含循環的最短路徑最多經過 $|V|-1$ 條邊。

此外，Bellman–Ford 可以再進行一輪檢查：

• 若仍有任何距離可以被更新，表示圖中存在從起點可到達的負權重循環。

因此，Bellman–Ford 適合處理可能含有負邊權重的圖。

複雜度為：

核心觀念

本題考查三個重點：

1. Python 的布林運算：or、and、not
2. NumPy 陣列逐元素運算
3. XOR（互斥或）的判斷與陣列追蹤

函式中的核心敘述為：

c[i] = (a or b) and (not(a and b))

對於 $a,b \in \{0,1\}$：

• $(a \text{ or } b)$：至少一個為 $1$
• $(a \text{ and } b)$：兩個皆為 $1$
• $\text{not}(a \text{ and } b)$：不是兩個皆為 $1$

因此整體條件表示「恰有一個為 $1$」，也就是 XOR：

$$a \oplus b=(a\lor b)\land\neg(a\land b)$$

XOR 的真值表如下：

$a$	$b$	$a\oplus b$
0	0	0
0	1	1
1	0	1
1	1	0

所以 func(x, y) 等同於對兩個陣列逐項進行 XOR。

---

解題方法

四個陣列為：

$$d_1=[1,0,0,1,0,0]$$ $$d_2=[0,1,0,1,1,0]$$ $$d_3=[0,0,0,0,0,0]$$ $$d_4=[1,1,0,0,1,0]$$

計算 $\operatorname{func}(d_1,d_2)$

逐項 XOR：

索引 $i$	$d_1[i]$	$d_2[i]$	XOR 結果
0	1	0	1
1	0	1	1
2	0	0	0
3	1	1	0
4	0	1	1
5	0	0	0

因此：

$$\operatorname{func}(d_1,d_2) =[1,1,0,0,1,0] =d_4$$

所以：

$$\operatorname{func}(d_1,d_2)[2]=0$$

計算 $\operatorname{func}(d_2,d_4)$

$$\begin{aligned} \operatorname{func}(d_2,d_4) &=[0,1,0,1,1,0]\oplus[1,1,0,0,1,0]\\ &=[1,0,0,1,0,0]\\ &=d_1 \end{aligned}$$

因此它不等於 $d_3$。

計算 $\operatorname{func}(\operatorname{func}(d_1,d_4),d_2)$

先計算：

$$\begin{aligned} \operatorname{func}(d_1,d_4) &=[1,0,0,1,0,0]\oplus[1,1,0,0,1,0]\\ &=[0,1,0,1,1,0]\\ &=d_2 \end{aligned}$$

再代入外層函式：