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

核心觀念

本題考查字典（dictionary）資料結構與雜湊表（hash table）的基本定義及運作方式。

字典資料結構以「鍵（key）—值（value）」儲存資料，例如：

• 鍵：學生學號
• 值：學生姓名與成績

雜湊表使用雜湊函數（hash function）將鍵轉換成陣列索引：

$$index=h(key)$$

資料便可依照該索引存入表格中。查詢時，再對相同的鍵套用雜湊函數，即可快速找到資料。

例如表格大小為 $10$，雜湊函數為：

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

若鍵值為 $123$：

$$h(123)=123\bmod 10=3$$

因此資料會被放入索引 $3$ 的位置。

雜湊碰撞

不同的鍵可能產生相同的索引，例如：

$$h(123)=3,\qquad h(133)=3$$

這種情況稱為雜湊碰撞（collision）。常見處理方式包括：

1. 鏈結法（separate chaining）：每個表格位置連接一個串列，碰撞資料放在同一串列中。
2. 開放定址法（open addressing）：發生碰撞時，依照線性探測、平方探測等方式尋找其他空位。

在雜湊函數良好、資料分布均勻的情況下，插入、查詢、刪除的平均時間複雜度通常為：

$$O(1)$$

若碰撞嚴重，最壞情況可能退化為：

$$O(n)$$

空間複雜度通常為：

$$O(m)$$

其中 $m$ 為雜湊表的容量。

解題方法

判斷選項是否正確時，抓住雜湊表的三個關鍵特徵：

1. 使用雜湊函數。
2. 將鍵映射到表格位置。
3. 透過鍵快速取得對應的值。

只有描述「使用 hash function 將 keys 對應到 values，並快速取回資料」的選項，符合雜湊表的正式定義。

選項分析

(A) 正確

“A hash table is a data structure that uses a hash function to map keys to values, allowing for fa

核心觀念

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

過度擬合是指模型過度記憶訓練資料中的細節與雜訊，因此在訓練資料上表現很好，面對未看過的新資料時，預測能力卻下降。

常見現象如下：

• Training accuracy 高
• Validation／test accuracy 低
• Training loss 持續下降，但 validation loss 開始上升

降低過度擬合的基本方向，是限制模型複雜度、增加泛化能力，或利用驗證資料及早發現模型開始過度學習。

---

解題方法

逐一判斷各選項是否具有降低過度擬合的作用：

1. 是否限制模型複雜度？
2. 是否對模型參數加入懲罰？
3. 是否防止模型在訓練過久？
4. 是否降低神經網路對特定神經元的依賴？
5. 是否利用驗證資料選擇較具泛化能力的模型？

若某方法反而增加模型表達能力，使模型更容易記憶訓練資料，便是「不能避免過度擬合」的選項。

---

選項分析

(A) Increasing layers / number of units per layer

此選項表示增加神經網路的層數，或增加每層的神經元數量。

增加層數與神經元數會提高模型容量，使模型能表達更複雜的函數。模型參數數量增加後，雖然有機會提升訓練資料上的準確率，但也更容易學習訓練資料中的雜訊與特殊模式。

因此，模型複雜度過高時，過度擬合風險會上升：

$$\text{模型容量增加} \Rightarrow \text{記憶訓練資料的能力增加}$$

在沒有搭配正則化、Dropout、資料增強等控制措施時，單純增加層數或單層神經元數量不能避免過度擬合。

本選項為正確答案。

---

(B) Using Lasso / Ridge regularization

Lasso 與 Ridge 都屬於正則化方法，會在損失函數中加入對模型參數的懲罰項。

Ridge regularization

Ridge 使用 $L_2$ 正則化：

$$J(\theta) = \text{Loss}(\theta) + \lambda \sum_i \theta_i^2$$

其中 $\lambda$ 控制正則化強度。較大的權重會受到較大的懲罰，使模型傾向使用較小且較平滑的參數。

Lasso regularization

Lasso 使用 $L_1$ 正則化：

$$J(\theta) = \text{Loss}(\theta) + \lambda \sum_i |\theta_i|$$

Lasso 會促使部分參數變成 $0$，因此具有特徵選擇與降低模型複雜度的效果。

兩者都能抑制模型過度依賴訓練資料，降低過度擬合。

本選項能協助避免過度擬合，為錯誤選項。

---

(C) Early stopping while training model

核心觀念

本題考查 8 位元二補數（two’s complement）表示法。

二補數表示負整數的標準步驟：

1. 先寫出該正整數的二進位。
2. 將所有位元反相，$0 \leftrightarrow 1$。
3. 最後加上 $1$。
4. 結果限制在指定的位元數內。

8 位元二補數可表示的整數範圍為：

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

因此，$-22$ 可以用 8 位元二補數表示。

解題方法

先將 $22$ 轉換成 8 位元二進位：

$$22=16+4+2$$

所以：

$$22_{10}=0001\ 0110_2$$

接著逐位反相：

$$0001\ 0110 \longrightarrow 1110\ 1001$$

再加上 $1$：

$$\begin{array}{r} 1110\ 1001\\ +0000\ 0001\\ \hline 1110\ 1010 \end{array}$$

因此：

$$-22 = 1110\ 1010$$

選項分析

• (A) 0001 0101

最高位為 $0$，代表這是正數。其值為：

$$0001\ 0101_2=16+4+1=21$$

這代表 $+21$，不是 $-22$，因此錯誤。

• (B) 0001 0110

最高位為 $0$，代表正數，且：

$$0001\ 0110_2=22$$

這是 $+22$ 的 8 位元表示，不是 $-22$，因此錯誤。

核心觀念

本題考查布林代數的化簡、Karnaugh map（卡諾圖）分組，以及「乘積項數」的判定。

原函數為

$$F=AB'C'+BCD'+CD+B'C'D'$$

每一個乘積項代表一組使 $F=1$ 的輸入組合。化簡時，利用相鄰最小項合併，消去不必要的變數，目標是以最少的 SOP（Sum of Products）乘積項表示函數。

---

解題方法：利用布林代數化簡

先處理中間兩項：

$$BCD'+CD$$

提出 $C$：

$$BCD'+CD=C(BD'+D)$$

利用布林定律

$$X+X'Y=X+Y$$

可得

$$D+BD'=B+D$$

因此

$$C(BD'+D)=C(B+D)=BC+CD$$

所以原式可化為

$$F=AB'C'+BC+CD+B'C'D'$$

目前得到四個乘積項：

$$AB'C',\quad BC,\quad CD,\quad B'C'D'$$

接著判斷這四項是否還能繼續合併。

• $AB'C'$ 負責涵蓋 $A=1,B=0,C=0$ 的情況。
• $B'C'D'$ 負責涵蓋 $B=0,C=0,D=0$ 的情況。
• $BC$ 負責涵蓋 $B=1,C=1$ 的情況。
• $CD$ 負責涵蓋 $C=1,D=1$ 的情況。

四個區域各自都有無法由其他項完整涵蓋的最小項，因此不能再刪除任何一項。

故化簡後需要四個乘積項：

$$F=AB'C'+BC+CD+B'C'D'$$

---

以卡諾圖觀察必要項

原式涵蓋的最小項為：

$$\begin{aligned} AB'C'&\rightarrow m_8,m_9\\ BCD'&\rightarrow m_6,m_{14}\\ CD&\rightarrow m_3,m_7,m_{11},m_{15}\\ B'C'D'&\rightarrow m_0,m_8 \end{aligned}$$

可形成的主要群組為：

核心觀念

本題考查作業系統的「分頁（Paging）」與「頁面置換（Page Replacement）」演算法。當頁面參考字串中的頁面不在目前的 4 個頁框（frame）中時，會發生一次 page fault；若頁面已在頁框中，則為 page hit。

三種演算法定義如下：

• FIFO（First In First Out）：置換最早載入頁框的頁面，不考慮最近是否使用。
• LRU（Least Recently Used）：置換最久未被使用的頁面。
• OPT（Optimal）：置換未來最晚才會再次使用，或未來不會再使用的頁面。此法需要預知未來，因此主要用於理論上的最佳比較。

頁面參考字串為：

$$1,2,3,4,5,1,3,1,6,3,2,3$$

頁框數為 $4$。

---

解題方法：FIFO

FIFO 依照頁面進入頁框的先後順序置換，使用佇列概念追蹤。

次序	參考頁面	頁框內容	結果
1	1	1	Fault
2	2	1, 2	Fault
3	3	1, 2, 3	Fault
4	4	1, 2, 3, 4	Fault
5	5	2, 3, 4, 5	Fault，置換 1
6	1	3, 4, 5, 1	Fault，置換 2
7	3	3, 4, 5, 1	Hit
8	1	3, 4, 5, 1	Hit
9	6	4, 5, 1, 6	Fault，置換 3
10	3	5, 1, 6, 3	Fault，置換 4
11	2	1, 6, 3, 2	Fault，置換 5
12	3	1, 6, 3, 2	Hit

因此：

$$\text{FIFO page faults}=9$$

---

解題方法：LRU

LRU 每次發生頁面錯誤時，置換「最近最久沒有被使用」的頁面。

次序	參考頁面	頁框內容	結果
1	1	1	Fault
2	2	1, 2	Fault
3	3	1, 2, 3	Fault
4	4	1, 2, 3, 4	Fault
5	5	2, 3, 4, 5	Fault，置換最久未用的 1
6	1	3, 4, 5, 1	Fault，置換 2
7	3	3, 4, 5, 1	Hit
8	1	3, 4, 5, 1	Hit
9	6	3, 5, 1, 6	Fault，置換最久未用的 4
10	3	3, 5, 1, 6	Hit
11	2	3, 1, 6, 2	Fault，置換最久未用的 5
12	3	3, 1, 6, 2	Hit

因此：

$$\text{LRU page faults}=8$$

---

解題方法：OPT

OPT 查看每次置換點之後的未來參考字串，置換未來最晚才會使用或永遠不再使用的頁面。

前四次載入：

$$1,2,3,4$$

第 5 次參考頁面 $5$ 時，頁框為 $1,2,3,4$。未來的參考字串為：

$$1,3,1,6,3,2,3$$

其中：

核心觀念

本題考查虛擬記憶體中的「有效存取時間」（Effective Access Time, EAT）與「page fault rate」之間的關係。

• 一般記憶體存取時間：$250$ ns
• Page fault handling time：$70$ μs
• 要求有效存取時間小於：$270$ ns
• Page fault rate：設為 $p$

發生 page fault 時，處理時間遠大於一般記憶體存取時間，因此少量的 page fault 也會顯著增加平均存取時間。

---

解題方法

先統一時間單位：

$$70\ \mu s=70,000\ ns$$

若未發生 page fault，存取時間為 $250$ ns；若發生 page fault，處理時間約為 $70,000$ ns。因此有效存取時間可表示為：

$$EAT=(1-p)(250)+p(70,000)$$

題目要求：

$$(1-p)(250)+p(70,000)<270$$

展開：

$$250-250p+70,000p<270$$ $$69,750p<20$$ $$p<\frac{20}{69,750}$$ $$p<0.0002867$$

換算成百分比：

$$p<0.0002867\times 100\%$$ $$p<0.02867\%$$

因此，page fault rate 必須低於約 $0.0287\%$。選項中最接近此上限的是：

$$\boxed{0.02\%}$$

所以依官方公布答案選 (B)。

---

選項分析

(A) 0.002%

核心觀念

本題考查神經網路輸出層的 activation function（啟動函數）與分類任務的對應關係。

在「多分類（multi-class classification）」問題中，每筆資料只能屬於多個類別中的一類，例如：

• 貓、狗、鳥三選一
• 多個疾病類別中擇一
• 手寫數字 $0$～$9$ 擇一

此時輸出層通常使用 Softmax，將各類別的原始輸出值轉換成總和為 $1$ 的機率分布。

Softmax 函數定義如下。若輸出層共有 $K$ 個神經元，第 $i$ 個神經元的原始輸出為 $z_i$，則：

$$\operatorname{Softmax}(z_i) = \frac{e^{z_i}}{\displaystyle\sum_{j=1}^{K}e^{z_j}}$$

其輸出具有以下特性：

1. 每個輸出值皆介於 $0$ 與 $1$ 之間。
2. 所有類別的輸出值總和為 $1$。
3. 輸出值可解釋為各類別的預測機率。
4. 通常選擇機率最高的類別作為預測結果。

例如，某輸出層得到：

$$[2.0,\ 1.0,\ 0.1]$$

經過 Softmax 後，會轉換為三個總和為 $1$ 的機率，代表三個類別的相對信心。

解題方法

判斷輸出層的啟動函數時，先確認分類任務的類型：

• 多分類：通常使用 Softmax。
• 二元分類：通常使用 Sigmoid。
• 多標籤分類：每個類別可同時成立，通常對各輸出分別使用 Sigmoid。
• 隱藏層：常使用 ReLU、Leaky ReLU 或 Tanh。

題目明確指出是「multi-class classification problems」，因此應選擇能將多個類別輸出轉換成總和為 $1$ 的機率分布之函數，即 Softmax。

選項分析

(A) Softmax：正確

Softmax 最常用於多分類問題的輸出層。它會將多個神經元的原始輸出轉換為機率分布：

$$\sum_{i=1}^{K}p_i=1$$

其中 $p_i$ 代表輸入屬於第 $i$ 類別的預測機率。因此符合題目所描述的「輸出層」與「多分類問題」。

(B) Leaky ReLU：錯誤

Leaky ReLU 通常用於隱藏層，目的是改善 ReLU 在輸入值小於 $0$ 時梯度為零的問題。其函數為：

核心觀念

本題考查多執行緒程式中的 race condition（競爭條件）。

競爭條件是指：

多個執行緒同時存取共享資料，其中至少一個執行緒會修改資料，且程式未使用適當同步機制，導致結果取決於執行順序。

因此，程式結果可能因執行緒排程不同而改變，造成資料錯誤或結果不一致。

常見需要同步保護的共享資源包括：

• 全域變數
• 共用記憶體
• 檔案
• 資料庫資料
• 共用計數器或佇列

解題方法

判斷 race condition 可依序檢查：

1. 是否有兩個以上執行緒同時執行？
2. 是否存取同一份共享資料？
3. 是否至少有一個執行緒會修改該資料？
4. 是否缺乏 mutex、lock、semaphore 等同步機制？

符合以上條件，即屬於競爭條件。

例如以下程式：

int count = 0;

void *worker(void *arg) {
 count = count + 1;
 return NULL;
}

表面上 count = count + 1 是一個動作，實際上通常可拆成：

1. 讀取 count
2. 將讀取值加 $1$
3. 寫回 count

假設兩個執行緒同時執行，初始值為 $0$：

執行順序	Thread 1	Thread 2	count
1	讀取 $0$		$0$
2		讀取 $0$	$0$
3	計算 $0+1$		$0$
4		計算 $0+1$	$0$
5	寫回 $1$		$1$
6		寫回 $1$	$1$

理想結果應為 $2$，實際結果卻可能是 $1$。這種因執行順序造成的結果不確定性，就是 race condition。

若加入互斥鎖：

lock(mutex);
count = count + 1;
unlock(mutex);

同一時間只有一個執行緒能修改 count，即可避免此問題。

選項分析

(A) A thread waiting indefinitely for a resource.

錯誤。

此敘述描述的是執行緒長時間等待資源，可能涉及：

• starvation（飢餓）：執行緒持續無法取得所需資源。
• blocking（阻塞）：執行緒暫停，等待某項條件成立。

它本身沒有指出多個執行緒未同步存取共享資料，因此不是 race condition 的定義。

(B) A deadlock caused by two threads trying to acquire each other's locks.

錯誤。

此敘述是 deadlock（死結）。

例如：

核心觀念

本題考的是 CPU 排程（CPU Scheduling）中，各演算法對「平均等待時間（average waiting time）」的影響。

• 等待時間（Waiting Time）：程序在就緒佇列（ready queue）中等待 CPU 的總時間。
• 平均等待時間：

$$\text{Average Waiting Time} = \frac{\sum \text{各程序等待時間}}{\text{程序總數}}$$

**Shortest-Job-First（SJF，最短工作優先）**會優先執行 CPU burst time 最短的程序。在所有程序同時到達、且已知各程序 CPU burst time 的條件下，SJF 能使所有程序的平均等待時間最小。

---

解題方法

判斷重點是：哪一種排程方式能讓「較短的工作先完成」，以降低後續程序累積的等待時間。

假設三個程序同時到達，CPU burst time 如下：

程序	CPU burst time
P1	8
P2	4
P3	2

若採用 FCFS

執行順序為：

$$P1 \rightarrow P2 \rightarrow P3$$

各程序等待時間：

• P1：$0$
• P2：$8$
• P3：$8+4=12$

平均等待時間：

$$\frac{0+8+12}{3} = \frac{20}{3} \approx 6.67$$

若採用 SJF

執行順序為：

$$P3 \rightarrow P2 \rightarrow P1$$

各程序等待時間：

• P3：$0$
• P2：$2$
• P1：$2+4=6$

平均等待時間：

$$\frac{0+2+6}{3} = \frac{8}{3} \approx 2.67$$

SJF 讓短工作先完成，避免短程序被長程序阻塞，因此平均等待時間最低。

從兩個相鄰程序來看，若先執行工作時間較長的程序 $L$，再執行較短的程序 $S$，兩者對總等待時間的貢獻為：

$$0+L=L$$

若改成先執行短程序 $S$，再執行長程序 $L$，總等待時間為：

$$0+S=S$$

因為 $S<L$，所以先執行短工作能降低總等待時間。將此原則套用到所有程序，即得到 SJF 的排序方式。

---

選項分析

(A) First-Come-First-Served

錯誤。

FCFS 按照程序到達順序執行，具有公平、實作簡單的優點，但不考慮 CPU burst time。

若長程序先到達，後面的短程序必須長時間等待，會產生 convoy effect（護航效應），使平均等待時間增加。因此 FCFS 不保證平均等待時間最短。

(B) Priority scheduling

錯誤。

Priority scheduling 依照優先權執行程序，優先權高的程序先獲得 CPU。

核心觀念

本題考查 OSI 模型各層資料單位（Protocol Data Unit, PDU）的名稱，以及資料在不同網路層級進行封裝（encapsulation）後的稱呼。

在資料鏈結層（Data Link Layer）中，上一層交付下來的資料會被加上：

• 資料鏈結層標頭（header）
• 資料鏈結層尾端資訊（trailer），通常包含錯誤偵測用的 FCS（Frame Check Sequence）

其完整格式為：

$$\text{Frame} = \text{Data-link Header} + \text{Payload} + \text{Data-link Trailer}$$

因此，經過資料鏈結層標頭與尾端封裝後所形成的資料單位，稱為 Frame（訊框）。

解題方法

題幹的關鍵字是：

data-link layer headers and trailers

只要看到「資料鏈結層」以及「標頭與尾端」，即可直接判斷資料單位是 Frame。

常見的 OSI 各層資料單位如下：

OSI 層級	常見資料單位
Transport Layer 傳輸層	Segment
Network Layer 網路層	Packet
Data Link Layer 資料鏈結層	Frame
Physical Layer 實體層	Bits

資料由上而下傳送時，會逐層加上控制資訊：

$$\text{Application Data} \rightarrow \text{Segment} \rightarrow \text{Packet} \rightarrow \text{Frame} \rightarrow \text{Bits}$$

本題指定的是資料鏈結層封裝完成後的名稱，所以答案為 Frame。

選項分析

(A) Data

「Data」是較泛稱的資料，常用來描述應用層或上層交付的原始內容，並非資料鏈結層加入 header 與 trailer 後的標準 PDU 名稱。

因此錯誤。

(B) Chunk

核心觀念

本題考查：

1. 由主網路切割子網路（subnetting）
2. 子網路遮罩的前綴長度（CIDR notation）
3. 子網路可容納的主機數量
4. VLSM（Variable Length Subnet Mask，變動長度子網路遮罩）

題目給定：

• 網路位址：192.168.1.64
• 子網路遮罩：255.255.255.192

將遮罩換成 CIDR 表示法：

$$255.255.255.192 = /26$$

因此原始網路為：

$$192.168.1.64/26$$

其位址範圍為：

$$192.168.1.64 \sim 192.168.1.127$$

其中：

• 網路位址：192.168.1.64
• 廣播位址：192.168.1.127
• 可用主機位址：192.168.1.65～192.168.1.126
• 可用主機數：$2^6-2=62$

---

解題方法

第一步：計算 10 hosts 所需的子網路大小

可用主機數公式為：

$$2^h-2 \geq \text{所需主機數}$$

其中 $h$ 是主機位元數。

對於 10 台主機：

$$2^h-2 \geq 10$$

當 $h=4$ 時：

$$2^4-2=14$$

因此 10 台主機需要：

• 主機位元：4 bits
• 網路前綴：$32-4=28$
• 子網路：$/28$
• 每個子網路可用主機數：14

---

第二步：計算 18 hosts 所需的子網路大小

對於 18 台主機：

$$2^h-2 \geq 18$$

當 $h=5$ 時：

$$2^5-2=30$$

因此 18 台主機需要：

• 主機位元：5 bits
• 網路前綴：$32-5=27$
• 子網路：$/27$
• 每個子網路可用主機數：30

---

第三步：在原本的 /26 網路中進行切割

原始網路是：

$$192.168.1.64/26$$

一個 /26 網路可以切成兩個 /27 網路：

子網路	位址範圍	可用主機數
192.168.1.64/27	192.168.1.64～192.168.1.95	30
192.168.1.96/27	192.168.1.96～192.168.1.127	30

為了配置 18 台與 10 台主機，可將其中一個 /27 再切成兩個 /28：

• 192.168.1.64/27：容納 18 台主機
• 192.168.1.96/28：容納 10 台主機
• 192.168.1.112/28：剩餘子網路，可供未來使用

因此完整配置可以是：

用途	子網路	可用主機範圍
18 hosts	192.168.1.64/27	192.168.1.65～192.168.1.94
10 hosts	192.168.1.96/28	192.168.1.97～192.168.1.110

選項中列出的 192.168.1.64/27 正是可容納 18 台主機的主要子網路，因此依官方答案選 B。

---

選項分析

(A) 192.168.1.16/28

/28 的確可以提供：

$$2^4-2=14$$

可用主機位址，足以容納 10 台主機。

核心觀念

本題考查 TCP/IP Internet Protocol Suite 中，TCP、IP 與 UDP 的基本特性：

• TCP（Transmission Control Protocol）：傳輸層、具連線導向（connection-oriented）、可靠、依序傳輸。
• IP（Internet Protocol）：網路層、無連線（connectionless）、採最佳努力傳遞（best-effort delivery）。
• UDP（User Datagram Protocol）：傳輸層、無連線、低額外負擔，但不保證可靠傳輸。
• TCP 三向交握（three-way handshake）：建立 TCP 連線時使用的程序。

本題要求找出「INCORRECT」，因此只要找出與上述定義矛盾的選項即可。

解題方法

逐一比對各選項與 TCP/IP 的標準特性：

1. TCP/IP 是否為網際網路通訊協定組合？
2. TCP 是否具備連線導向與可靠傳輸特性？
3. IP 是否採無連線與最佳努力傳遞？
4. TCP 是否以三向交握建立連線？
5. UDP 的可靠性是否高於 TCP？

前四項皆符合標準定義，第五項將 UDP 與 TCP 的可靠性關係倒置，因此為錯誤敘述。

選項分析

(A) TCP/IP is a suite of protocols for communication over the internet.

正確。

TCP/IP 並非單一協定，而是一組用於網路通訊的協定集合，包含不同層級的協定，例如：

• 應用層：HTTP、DNS、FTP
• 傳輸層：TCP、UDP
• 網路層：IP、ICMP
• 網路存取層：Ethernet、Wi-Fi 等

因此，TCP/IP 確實是用於網際網路通訊的協定組合。

(B) TCP is a connection-oriented protocol that guarantees reliable delivery of data.

正確。

TCP 是連線導向協定。資料傳送前，雙方必須先建立連線；資料傳送期間，TCP 會透過多種機制提高可靠性，包括：

• 序號（Sequence Number）：確保資料可依序重組。
• 確認應答（Acknowledgment）：接收端回覆已收到的資料。
• 逾時重傳（Retransmission）：資料遺失時重新傳送。
• 流量控制（Flow Control）：避免接收端緩衝區溢位。
• 壅塞控制（Congestion Control）：降低網路壅塞造成的封包遺失。

因此，在一般計算機網路的考試定義中，TCP 被視為提供可靠的資料傳輸服務。

嚴格而言，TCP 無法保證在主機故障、網路完全中斷等情況下資料必定送達；此敘述中的「guarantees」是採用考試常見的標準化表述，意指 TCP 相較於 UDP 提供可靠傳輸機制。

核心觀念

本題考查：

1. 由 pre-order traversal 與 in-order traversal 還原 BST。
2. BST 的性質：

• 左子樹所有鍵值小於根節點。
• 右子樹所有鍵值大於根節點。

3. BST 插入與刪除：

• 插入時，從根節點逐層比較。
• 刪除只有一個子節點的節點時，由其唯一子節點接替原位置。
• 刪除有兩個子節點的節點時，題目指定以左子樹最大值取代。

---

解題方法：先還原原始 BST

Pre-order 的第一個元素一定是根節點，因此根為 $31$。

In-order 中，$31$ 左側的元素屬於左子樹，右側的元素屬於右子樹：

• 左子樹：$12,21,25,27,29,30$
• 右子樹：$33,38,41$

依照 pre-order 順序，可逐層建立：

• $31$ 的左子樹根為 $27$
• $31$ 的右子樹根為 $38$
• $27$ 的左子樹根為 $21$
• $27$ 的右子樹根為 $30$
• $21$ 的左子節點為 $12$
• $21$ 的右子節點為 $25$
• $30$ 的左子節點為 $29$
• $38$ 的左子節點為 $33$
• $38$ 的右子節點為 $41$

原始 BST 為：

 31
 / \
 27 38
 / \ / \
 21 30 33 41
 / \ /
12 25 29

---

插入鍵值 $36$

依照 BST 插入規則逐步比較：

1. $36 < 31$ 不成立，因此往右走至 $38$。
2. $36 < 38$，往左走至 $33$。
3. $36 > 33$，往右插入。

插入後：

 31
 / \
 27 38
 / \ / \
 21 30 33 41
 / \ / \
12 25 29 36

關鍵插入程式可表示為：

insert(root, key):
 if root == null:
 return new Node(key)

 if key < root.key:
 root.left = insert(root.left, key)
 else:
 root.right = insert(root.right, key)

 return root

鍵值 $36$ 的追蹤路徑為：

$$31 \rightarrow 38 \rightarrow 33 \rightarrow 36$$

因此，$36$ 的父節點是 $33$。

---

選項分析

(A) The key value 38 is the parent of key value 36.

錯誤。

插入 $36$ 時，雖然先由 $31$ 走到 $38$，但因為 $36 < 38$，必須進入 $38$ 的左子樹；接著因為 $36 > 33$，最後插入為 $33$ 的右子節點。

因此：

$$\operatorname{parent}(36)=33$$

$38$ 是 $36$ 的祖先，但不是直接父節點。

---

(B) The key value 30 has two children.

錯誤。

節點 $30$ 的左子節點是 $29$，右側沒有子節點：

30
/
29

插入 $36$ 發生在 $33$ 的右子樹，不會改變節點 $30$ 的結構。因此 $30$ 只有一個子節點。

---

核心觀念

本題考查：

1. **Max-heap（最大堆積）**的性質：每個父節點的值都大於或等於其子節點。
2. 以陣列表示二元堆積，且根節點位於索引 $1$。
3. 插入元素時的上濾（sift-up / bubble-up）：

• 新元素先放在陣列最後。
• 與父節點比較。
• 若新元素大於父節點，便交換並繼續向上比較。

由於根節點位於索引 $1$，所以索引 $i$ 的父節點為：

$$\operatorname{parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

索引 $i$ 的左、右子節點分別為：

$$2i,\qquad 2i+1$$

本題要求的是最後陣列中索引 $2$ 的節點值。

解題方法與逐步追蹤

採用標準最大堆積插入法：每次將新數字加到陣列尾端，再向上與父節點比較。

插入 $8$

陣列為：

$$[8]$$

$8$ 位於根節點，無須上濾。

插入 $12$

先放在索引 $2$：

$$[8,12]$$

索引 $2$ 的父節點是索引 $1$，比較：

$$12>8$$

交換後：

$$[12,8]$$

插入 $12$

先放在索引 $3$：

$$[12,8,12]$$

索引 $3$ 的父節點是索引 $1$，比較：

$$12=12$$

最大堆積允許父子節點相等，因此不必交換。

目前陣列為：

$$[12,8,12]$$

插入 $9$

先放在索引 $4$：

$$[12,8,12,9]$$

索引 $4$ 的父節點為：

$$\left\lfloor \frac{4}{2}\right\rfloor=2$$

比較索引 $4$ 與索引 $2$：

$$9>8$$

交換：

$$[12,9,12,8]$$

此時索引 $2$ 的父節點為索引 $1$，比較：

$$9<12$$

停止上濾。

插入 $10$

先放在索引 $5$：

$$[12,9,12,8,10]$$

索引 $5$ 的父節點為索引 $2$：

$$10>9$$

交換後：

$$[12,10,12,8,9]$$

索引 $2$ 的值為 $10$，且：

$$10<12$$

因此停止上濾。

插入 $11$

核心觀念

本題考查 SQL 的 JOIN，以及資料表之間透過外鍵欄位進行配對的方式。

查詢語句為：

SELECT * FROM AGE_TABLE
JOIN STUDENT_TABLE
ON STUDENT_TABLE.S_ID = AGE_TABLE.STID;

此處未指定 INNER、LEFT 等類型時，JOIN 預設為 INNER JOIN。執行機制如下：

1. 取出 AGE_TABLE 的一筆資料。
2. 以 AGE_TABLE.STID 對照 STUDENT_TABLE.S_ID。
3. 兩欄數值相等時，合併兩表該筆資料。
4. SELECT * 會顯示兩個資料表的所有欄位。

解題方法

依照 STID = S_ID 逐筆配對：

T_ID	Age	STID	對應 S_ID	Name	Sex
1	18	2	2	Peter	Male
2	20	4	4	Emma	Female
3	21	1	1	David	Male
4	24	5	5	Jack	Male
5	28	3	3	John	Male

因此，合併後的重要資料為：

• Peter：18 歲
• Emma：20 歲
• David：21 歲
• Jack：24 歲
• John：28 歲

選項分析

(A) Peter’s age is 20

Peter 的 S_ID = 2，需尋找 AGE_TABLE.STID = 2 的資料。

對應資料為：

$$T\_ID=1,\quad Age=18$$

所以 Peter 的年齡是 18 歲，不是 20 歲。此選項錯誤。

---

(B) The average age of Male is 21.75

性別為 Male 的學生為：

核心觀念

本題考查「in-place sorting（原地排序）」的定義。

原地排序是指：

• 直接在原陣列上 rearrange（重新排列）元素；
• 只使用固定大小或相對很小的額外記憶體；
• 不需建立與輸入資料量 $n$ 同階的輔助陣列。

判斷重點不是只看時間複雜度，而是看排序過程是否需要額外的 $O(n)$ 空間。

常見排序法比較如下：

排序法	典型時間複雜度	典型額外空間	是否通常為原地排序
Bubble sort	$O(n^2)$	$O(1)$	是
Insertion sort	$O(n^2)$	$O(1)$	是
Merge sort	$O(n\log n)$	$O(n)$	否
Heap sort	$O(n\log n)$	$O(1)$	是
Quick sort	平均 $O(n\log n)$	平均 $O(\log n)$ 堆疊	通常視為是

因此，官方答案為 (C) Merge sort。

---

解題方法

判斷每個排序演算法的典型實作是否需要一個與輸入資料量 $n$ 同階的輔助陣列。

Merge sort 的基本流程是：

1. 將陣列分成左右兩半；
2. 遞迴排序左右兩半；
3. 將兩個已排序的子陣列合併。

合併時，典型實作會配置暫存陣列：

mergeSort(A, left, right):
 if left >= right:
 return

 mid = (left + right) / 2
 mergeSort(A, left, mid)
 mergeSort(A, mid + 1, right)
 merge(A, left, mid, right)

典型的 merge：

merge(A, left, mid, right):
 temp = new array of size right - left + 1

 i = left
 j = mid + 1
 k = 0

 while i <= mid and j <= right:
 if A[i] <= A[j]:
 temp[k] = A[i]
 i = i + 1
 else:
 temp[k] = A[j]
 j = j + 1
 k = k + 1

 copy remaining elements from A[i...mid] into temp
 copy remaining elements from A[j...right] into temp

 copy temp back to A[left...right]

每一層遞迴的合併工作總量為 $O(n)$，共有 $O(\log n)$ 層，因此時間複雜度為：

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)=O(n\log n)$$

但是 temp 陣列最多需要儲存 $n$ 個元素，因此額外空間為：

$$S(n)=O(n)$$

這使得典型 Merge sort 不符合原地排序的分類。

---

Merge sort 的逐步追蹤

假設輸入為：

$$[8, 3, 5, 4]$$

分割階段：

[8, 3, 5, 4]
 / \
 [8, 3] [5, 4]
 / \ / \
[8] [3] [5] [4]

合併階段：

merge([8], [3]) -> temp = [3, 8]
merge([5], [4]) -> temp = [4, 5]

最後合併：

merge([3, 8], [4, 5])

比較 3 與 4：取 3
比較 8 與 4：取 4
比較 8 與 5：取 5
剩下 8

結果為 [3, 4, 5, 8]

過程中的 temp 就是典型 Merge sort 的 $O(n)$ 額外空間來源。

---

選項分析

(A) Bubble sort

Bubble sort 反覆比較相鄰元素，若順序錯誤就交換：

核心觀念

本題考查神經網路中全連接層（fully connected layer, FC layer）與卷積層（convolutional layer, convolutional layer）的連接方式與結構差異。

• 全連接層：每一個輸入神經元都與每一個輸出神經元相連。若輸入有 $n$ 個神經元、輸出有 $m$ 個神經元，權重數量通常為 $n \times m$，另加上 $m$ 個偏置。
• 卷積層：每個輸出神經元只與輸入資料中的局部區域相連，這個局部區域稱為感受野（receptive field）。卷積核會在輸入資料上滑動，重複使用同一組權重，因此具有局部連接與權重共享的特性。

卷積層的設計特別適合影像資料，因為影像中相鄰像素通常具有較強的空間關聯性。

---

解題方法

判斷本題的關鍵是比較兩種層的「連接範圍」：

1. 全連接層採取全域連接，每個輸入神經元都連到每個輸出神經元。
2. 卷積層採取局部連接，每個輸出神經元只查看輸入資料的一小部分區域。
3. 因此，描述「全連接」與「局部連接」差異的選項即為正確答案。

例如，輸入資料有 $100$ 個神經元，輸出層有 $10$ 個神經元：

• 全連接層需要連接 $100 \times 10 = 1000$ 條權重。
• 卷積層的每個輸出位置只使用局部感受野，例如每次只查看 $9$ 個輸入值，因此不會讓每個輸入直接連接到每個輸出位置。

---

選項分析

(A) Fully connected layers are only used in supervised learning, while convolutional layers are used in unsupervised learning.

錯誤。

全連接層與卷積層都是神經網路的組成元件，並不限定只能用於特定的學習方式。

• 全連接層可以用於監督式學習、非監督式學習及自編碼器等模型。
• 卷積層也可以用於監督式影像分類、非監督式特徵學習、生成模型等。

因此，兩者的差異不是監督式學習與非監督式學習的區分。

---

(B) Fully connected layers require less computation than convolutional layers.

錯誤。

一般情況下，全連接層需要大量參數與乘加運算，尤其當輸入資料維度很高時，計算量通常相當可觀。

全連接層的參數數量約為：

$$N_{\text{FC}} = n_{\text{in}} \times n_{\text{out}} + n_{\text{out}}$$

卷積層則使用較小的卷積核，並在不同位置共享相同權重。例如卷積核大小為 $k \times k$、輸入通道數為 $c_{\text{in}}$、輸出通道數為 $c_{\text{out}}$，其參數數量約為：

$$N_{\text{Conv}} = k^2 \times c_{\text{in}} \times c_{\text{out}} + c_{\text{out}}$$

核心觀念

本題考查 Ackermann function 的遞迴定義，以及程式中巢狀遞迴呼叫的執行方式。

函式定義為：

$$A(0,n)=n+1$$ $$A(m,0)=A(m-1,1)$$ $$A(m,n)=A(m-1,A(m,n-1))$$

本題要求：

$$A(1,3)$$

由於 $m=1$，且 $n>0$，必須套用第三個遞迴規則：

$$A(1,n)=A(0,A(1,n-1))$$

而 $A(0,x)=x+1$，因此可逐步計算。

解題方法與逐步推導

先從 $n=0$ 開始：

$$A(1,0)=A(0,1)=1+1=2$$

接著計算 $A(1,1)$：

$$\begin{aligned} A(1,1) &=A(0,A(1,0))\\ &=A(0,2)\\ &=2+1\\ &=3 \end{aligned}$$

計算 $A(1,2)$：

$$\begin{aligned} A(1,2) &=A(0,A(1,1))\\ &=A(0,3)\\ &=3+1\\ &=4 \end{aligned}$$

計算 $A(1,3)$：

$$\begin{aligned} A(1,3) &=A(0,A(1,2))\\ &=A(0,4)\\ &=4+1\\ &=5 \end{aligned}$$

因此：

$$\boxed{A(1,3)=5}$$

程式碼逐步追蹤

關鍵程式碼為：

else if (n==0)
 return A(m-1,1);
else
 return A(m-1,A(m,n-1));

對 $A(1,3)$ 的主要追蹤如下：

$$\begin{aligned} A(1,3) &\to A(0,A(1,2))\\ &\to A(0,A(0,A(1,1)))\\ &\to A(0,A(0,A(0,A(1,0))))\\ &\to A(0,A(0,A(0,A(0,1))))\\ &\to A(0,A(0,A(0,2)))\\ &\to A(0,A(0,3))\\ &\to A(0,4)\\ &\to 5 \end{aligned}$$

核心觀念

本題考 Floyd’s Cycle Detection Algorithm（龜兔賽跑演算法）：

• 指標 a 每次前進 $1$ 個節點，作為慢指標。
• 指標 b 每次前進 $2$ 個節點，作為快指標。
• 若 linked list 有 cycle，兩個指標最後一定會在環內相遇。
• 若沒有 cycle，快指標會先到達 NULL。

因此應填入：

Q1: a = a -> next;
Q2: b = b -> next -> next;

---

解題方法與逐步追蹤

原程式設定：

ListNode *a = head;
ListNode *b = head->next;

在每次迴圈中：

a = a -> next; // a 前進 1 步
b = b -> next -> next; // b 前進 2 步

以圖中 Example 1：

$$3 \rightarrow 2 \rightarrow 0 \rightarrow -4$$

且 $-4$ 又指回 $2$。

指標移動如下：

迴圈階段	a	b
初始	$3$	$2$
第 1 次移動後	$2$	$-4$
第 2 次移動後	$0$	$0$

兩個指標在節點 $0$ 相遇，因此回傳 true。

以沒有 cycle 的 Example 2：

$$1 \rightarrow 2 \rightarrow 0 \rightarrow -4 \rightarrow NULL$$

當 b 移動到尾端時，條件

if(b == NULL || b->next == NULL)
 return false;

會成立，因此回傳 false。

---

為什麼選 E 正確

Q1: a = a -> next;
Q2: b = b -> next -> next;

a 每次走一步，b 每次走兩步，符合 Floyd 演算法的設計：

• 有環：快慢指標在環內必定相遇。
• 無環：b 會先抵達 NULL，程式安全回傳 false。

所以官方答案為 E。

核心觀念

本題考查 C 語言的：

• 指標（pointer）與取值運算子 *
• 位址運算子 &
• 指標所指向變數的連動關係
• 指派運算對變數值的影響
• 運算式的括號與算術運算順序

程式中的宣告為：

int i = 15, j = 9, *s = &i, *t = &j;

其意義如下：

• i 的初始值為 $15$
• j 的初始值為 $9$
• s 儲存變數 i 的位址，因此 *s 代表 i
• t 儲存變數 j 的位址，因此 *t 代表 j

因此：

$$*s=i,\qquad *t=j$$

解題方法與逐步追蹤

先依照程式執行順序建立變數狀態：

執行階段	i	j	*s	*t
初始宣告後	15	9	15	9
執行 i = 3; 後	3	9	3	9

關鍵在於：s 儲存的是 i 的位址，而不是把 i 當時的數值複製一份。因此，執行：

i = 3;

會直接改變 i 的內容；之後透過 *s 取值時，取得的是最新的 i 值 $3$。

接著計算 printf 中的運算式：

10 * (*s + *t) + 3

代入：

$$*s=3,\qquad *t=9$$

因此：

$$10\times(3+9)+3$$ $$=10\times12+3$$ $$=120+3=123$$

所以程式輸出：

123

選項分析

核心觀念

本題考查 C 語言函式內部的 static 區域變數。

int foo(int x) {
 static int y = 0;
 y += x;
 return y;
}

static int y = 0; 具有以下特性：

• y 只在第一次執行到宣告時初始化為 $0$。
• y 的作用域仍限定在函式 foo 內，函式外無法直接存取。
• y 的生命週期持續整個程式執行期間。
• 函式 foo 返回後，y 的值不會消失；下一次呼叫會沿用前一次的值。

因此，三次呼叫並非每次都從 $0$ 開始計算。

解題方法與逐步追蹤

依照程式執行順序追蹤 y、函式回傳值及變數內容：

呼叫	傳入的 x	執行 y += x 後的 y	回傳值	接收變數
foo(2)	$2$	$0+2=2$	$2$	a = 2
foo(4)	$4$	$2+4=6$	$6$	b = 6
foo(6)	$6$	$6+6=12$	$12$	c = 12

所以：

$$a+b+c=2+6+12=20$$

程式最後執行：

printf("%d\n", a + b + c);

輸出為：

20

選項分析

(A) The program will not compile because of an error in the function foo.

錯誤。函式中的 static 區域變數宣告方式完全合法：

static int y = 0;

y += x; 及 return y; 也都是合法的 C 語法，程式可以正常編譯與執行。

核心觀念

本題考查 C 語言中的：

1. 指標與位址：

• s 指向變數 i
• t 指向變數 j
• *s 代表 i 的值
• *t 代表 j 的值

2. 整數除法：

• (*s+*t)/2 的運算結果為整數，因此小數部分會被捨去。

3. 前置與後置遞增：

• (*s)++：先使用原值，再使 *s 加 1。
• ++(*t)：先使 *t 加 1，再使用新值。

初始狀態為：

$$i=8,\qquad j=7$$

因為：

int i=8, j=7, *s=&i, *t=&j;

所以：

*s == i == 8
*t == j == 7

解題方法與逐步追蹤

第 1 個 printf

printf("%d ", (*s+*t)/2);

代入初始值：

$$\frac{*s+*t}{2} = \frac{8+7}{2} = \frac{15}{2} = 7$$

C 語言的整數除法會捨去小數部分，因此輸出：

7

此時變數值不變：

$$i=8,\qquad j=7$$

---

第 2 個 printf

printf("%d ", *s-*t);

代入數值：

$$*s-*t=8-7=1$$

輸出：

1

此時：

$$i=8,\qquad j=7$$

---

第 3 個 printf

printf("%d ", (*s)++);

(*s)++ 是後置遞增，先輸出原本的 *s，再將 *s 加 1。

因此先輸出：

$$*s=8$$

輸出後：

$$i=9$$

此時：

$$i=9,\qquad j=7$$

---

第 4 個 printf

printf("%d ", ++(*t));

++(*t) 是前置遞增，先將 *t 加 1，再輸出新值。

原本：

$$*t=j=7$$

遞增後：

$$j=8$$

因此輸出：

8

此時：

$$i=9,\qquad j=8$$

---

核心觀念

本題考查 SQL Injection（SQL 注入）攻擊與防禦方法。

SQL Injection 是指攻擊者將惡意 SQL 語句或條件，插入應用程式原本要執行的 SQL 指令中，使資料庫執行非預期操作，例如：

• 繞過登入驗證
• 讀取機密資料
• 修改或刪除資料
• 取得資料庫管理權限

其根本原因通常是：應用程式直接將使用者輸入串接到 SQL 語句中，導致「程式指令」與「外部資料」混在一起。

例如不安全的寫法：

SELECT * FROM users
WHERE username = '使用者輸入'
AND password = '使用者輸入';

若未妥善處理輸入內容，攻擊者可能輸入特殊字串，使原本的查詢條件遭到改變。

防禦 SQL Injection 的常見方法包括：

1. 使用參數化查詢（prepared statements）
2. 使用適當設計的 stored procedures（預存程序）
3. 進行輸入驗證
4. 限制資料庫帳號權限
5. 避免將錯誤訊息暴露給使用者

解題方法

判斷各選項是否能防止 SQL Injection，重點在於確認該方法是否能避免使用者輸入直接改變 SQL 指令結構。

若方法能將 SQL 指令與使用者資料分離，便具有防禦效果；若只是將資料直接存放、改名，或完全忽略驗證，則無法解決注入問題。

本題官方答案為 B，因為設計良好的 stored procedures 可以將資料庫操作封裝在預先定義的程序中，並透過參數傳遞使用者資料，降低輸入內容被當成 SQL 指令執行的風險。

選項分析

(A) Concatenating user input with SQL queries.

錯誤。

將使用者輸入直接與 SQL 查詢串接，是 SQL Injection 最典型的成因。例如：

query = "SELECT * FROM users WHERE name = '" + userInput + "'";

此寫法未將輸入內容與 SQL 指令分離。若使用者輸入包含引號、註解符號或額外的 SQL 條件，就可能改變原本查詢語句的意義。

因此，直接串接使用者輸入不但不能防禦 SQL Injection，反而會提高遭受攻擊的風險。

(B) Using stored procedures.

正確，為本題官方答案。

Stored procedure（預存程序）是事先儲存在資料庫中的程式化 SQL 操作。應用程式呼叫預存程序時，可將使用者輸入作為參數傳入，而不是直接將輸入字串拼接到 SQL 語句中。

概念上可寫成：

CREATE PROCEDURE GetUser
 @username VARCHAR(50)
AS
BEGIN
 SELECT *
 FROM users
 WHERE username = @username;
END;

應用程式呼叫：

核心觀念

本題考查「對稱式加密」與「非對稱式加密」的特性及應用。

比較項目	對稱式加密	非對稱式加密
金鑰數量	使用同一把共享金鑰加密與解密	使用公開金鑰與私密金鑰成對運作
速度	快，適合大量資料	較慢，不適合直接加密大量資料
主要用途	大量資料加密、即時通訊	數位簽章、金鑰交換、數位信封
金鑰分配	須安全傳遞共享金鑰	公開金鑰可公開，私密金鑰須保密

非對稱式加密常見的金鑰用途如下：

• 機密性：寄件者使用收件者的公開金鑰加密，只有收件者能用自己的私密金鑰解密。
• 數位簽章：寄件者使用自己的私密金鑰簽署，收件者使用寄件者的公開金鑰驗證。
• 數位信封：以非對稱式加密保護對稱式加密所使用的工作金鑰，再以對稱式加密處理大量內容。

解題方法

判斷各選項是否正確時，抓住三個核心特徵：

1. 非對稱式加密使用「公開金鑰＋私密金鑰」，不是同一把金鑰。
2. 非對稱式加密運算較慢，通常不直接用來加密大量資料。
3. 非對稱式加密的重要應用包括數位簽章與數位信封。

符合上述特徵的選項即為正確答案。

選項分析

(A) 錯誤

選項聲稱非對稱式加密「非常有效率地加密大量資料」，並且是雲端儲存的主要選擇。

非對稱式加密涉及複雜的數學運算，例如大數運算，速度通常比對稱式加密慢，因此不適合直接加密大量檔案或大量資料。

雲端儲存常採用混合式加密：

1. 產生一把隨機的對稱式工作金鑰。
2. 使用對稱式加密處理實際的大量資料。
3. 使用非對稱式加密保護這把對稱式工作金鑰。

因此，非對稱式加密主要用來保護金鑰，而非直接高效率地加密大量資料。

(B) 正確

非對稱式加密廣泛應用於：

• 數位簽章（digital signature）：簽署者使用私密金鑰產生簽章，驗證者使用其公開金鑰驗證簽章，可確認資料來源及內容是否遭到竄改。
• 數位信封（digital envelope）：使用對稱式加密快速加密資料，再使用收件者的公開金鑰加密對稱式工作金鑰，以兼顧效率與安全性。

數位信封的基本流程可表示為：

$$C_{\text{data}}=\operatorname{Enc}_{K_s}(M)$$

其中 $M$ 是原始資料，$K_s$ 是對稱式工作金鑰。

接著使用收件者的公開金鑰加密工作金鑰：

核心觀念

本題考查分散式阻斷服務攻擊（Distributed Denial of Service, DDoS）的定義與運作機制。

DDoS 的主要目的，是在短時間內由「多個來源」向目標伺服器、網路設備或服務大量傳送請求與封包，使目標的下列資源被耗盡：

• 網路頻寬
• CPU 與記憶體
• 連線數量
• 應用程式處理能力
• 防火牆、負載平衡器等網路設備資源

當正常使用者的請求無法獲得處理時，目標服務便會變慢、中斷，甚至完全無法提供服務。

攻擊者通常會先控制大量受感染的電腦、伺服器、物聯網裝置或其他網路設備，形成殭屍網路（botnet），再要求這些裝置同時對目標發動流量攻擊。因此，DDoS 的關鍵特徵是：

1. 攻擊目標是服務可用性。
2. 攻擊流量來自多個來源。
3. 主要手段是大量流量或請求造成資源超載。

解題方法

判斷本題可抓住題幹中的兩個關鍵描述：

• 「consume the target’s resources」：消耗目標資源。
• 「cannot provide service」：使目標無法提供服務。

再對照選項，只有選項 (C) 同時包含：

• overload：使伺服器或網路超載；
• traffic from multiple sources：流量來自多個來源。

這正是 DDoS 的核心定義與運作方式，因此選擇 (C)。

選項分析

(A) A type of malware that infects multiple machines and spreads through a network.

錯誤。

此選項描述的是一種可感染多部電腦並透過網路散播的惡意程式，較接近電腦病毒、蠕蟲或其他惡意軟體的概念。

DDoS 本身是「攻擊行為或攻擊型態」，不是惡意軟體。攻擊者確實可能利用惡意軟體感染多部機器，再建立 botnet 發動 DDoS；但感染機器、散播惡意程式只是攻擊前置手段，並非 DDoS 的定義。

校方釋疑也指出，選項 (A) 所描述的惡意軟體可被用來進行 DDoS，但它並沒有定義 DDoS 攻擊本身。

(B) A type of cyber attack that targets an individual user's personal information.

錯誤。

此選項描述的是以個人資料為目標的攻擊，例如竊取帳號、密碼、身分資料或信用卡資訊。其主要影響是資訊機密性與個人隱私。

DDoS 的主要目標則是服務的可用性，重點在於讓伺服器或網路無法正常服務，而不是竊取個人資料。

核心觀念

RSA 加密使用公開金鑰 $(e,N)$，其加密公式為：

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

其中：

• $M$：明文（plaintext）
• $C$：密文（ciphertext）
• $e$：公開指數
• $N$：模數

本題給定：

$$e=5,\qquad N=77,\qquad M=4$$

因此需計算：

$$C\equiv 4^5\pmod{77}$$

---

解題方法

直接套用 RSA 加密公式：

$$C\equiv 4^5\pmod{77}$$

先計算次方：

$$4^5=1024$$

再求 $1024$ 除以 $77$ 的餘數：

$$1024=77\times 13+23$$

所以：

$$4^5\equiv 23\pmod{77}$$

因此密文為：

$$C=23$$

---

快速計算與逐步追蹤

也可使用模運算逐步化簡：

$$4^2=16$$ $$4^4\equiv 16^2=256\equiv 25\pmod{77}$$

因為：

$$256=77\times 3+25$$

接著：

$$4^5\equiv 4^4\cdot 4 \equiv 25\cdot 4 =100 \equiv 23\pmod{77}$$

因為：

$$100=77+23$$

故仍得到：

$$C=23$$

此方法屬於模冪運算。若使用快速冪演算法，指數為 $e$ 時，乘法次數約為 $O(\log e)$，額外空間複雜度為 $O(1)$。

---

選項分析

• (A) 7：錯誤。
  $7$ 不是 $4^5$ 除以 $77$ 所得的餘數。正確餘數為 $23$。

核心觀念

Big O notation（大 O 記號）用來描述演算法的漸近成長率，也就是當輸入規模 $n$ 很大時，演算法的執行時間或記憶體使用量如何成長。

若某演算法的執行時間為

$$T(n)=3n^2+5n+10$$

當 $n$ 增大時，主導成長的是 $n^2$ 項，因此可表示為

$$T(n)=O(n^2)$$

在漸近分析中，會忽略：

1. 固定的乘法常數，例如 $3n^2$ 中的 $3$。
2. 較低階的項，例如 $5n$、$10$ 相對於 $n^2$ 的影響。

因此，Big O 主要反映演算法的成長趨勢，不代表實際執行秒數。

解題方法

逐一檢查各選項對 Big O 的描述是否符合定義：

• Big O 是否表示精確執行時間？
• Big O 是否只適用於相似演算法？
• Big O 是否表示最佳情況？
• Big O 是否忽略常數與低階項？
• Big O 是否只用於排序問題？

符合 Big O 漸近分析定義的選項，即為正確答案。

選項分析

(A) Big O notation provides the exact running time of an algorithm.

錯誤。

Big O 不提供演算法的精確執行時間，只描述其成長率上界。例如：

$$T(n)=100n+50$$

可寫成

$$T(n)=O(n)$$

但 $O(n)$ 並未指出實際需要多少秒，也沒有反映處理器速度、程式語言、編譯器與硬體環境等因素。

因此，Big O 是漸近複雜度表示法，不是精確計時工具。

(B) Big O notation can be used to compare algorithms only if they are similar algorithms.

錯誤。

Big O 可用來比較解決相同問題的不同演算法，即使它們的設計方法完全不同。例如，排序演算法可比較：

• Bubble Sort：$O(n^2)$
• Merge Sort：$O(n\log n)$
• Heap Sort：$O(n\log n)$

這些演算法的核心機制不同，但仍可透過時間複雜度比較其輸入規模增大時的效率。

嚴格而言，演算法比較通常應建立在「解決相同問題」及「相同輸入條件」上，而不是要求演算法本身相似。

(C) Big O notation provides the best-case running time of an algorithm.