國立中山大學 114 年 《計算機概論與程式設計》

核心觀念

本題考查無向加權圖的最小生成樹（Minimum Spanning Tree, MST）。

• 生成樹：包含圖中所有頂點，且不含任何環的樹。
• 若圖有 $|V|$ 個頂點，其生成樹必定包含 $|V|-1$ 條邊。
• 最小生成樹：在所有生成樹中，總邊權重最小者。
• 常用的求法包括 Kruskal 演算法與 Prim 演算法。本題邊數少，使用 Kruskal 演算法最直接。

本圖有 $4$ 個頂點，因此最小生成樹必須選取：

$$4-1=3$$

條邊。

解題方法：Kruskal 演算法

Kruskal 演算法的步驟是：

1. 將所有邊依權重由小到大排序。
2. 依序選取邊。
3. 若加入該邊不會形成環，就加入生成樹。
4. 選滿 $|V|-1$ 條邊後停止。

各邊依權重排序如下：

邊	權重
$(1,2)$	$5$
$(1,3)$	$6$
$(2,3)$	$7$
$(2,4)$	$8$
$(3,4)$	$9$
$(1,4)$	$10$

依序處理：

1. 選取 $(1,2)$，權重為 $5$。目前沒有形成環，加入。
2. 選取 $(1,3)$，權重為 $6$。目前形成的結構仍無環，加入。
3. 處理 $(2,3)$，權重為 $7$。頂點 $2$ 與 $3$ 已經可以透過 $2\to1\to3$ 互相連通，若再加入 $(2,3)$ 會形成環，因此跳過。
4. 選取 $(2,4)$，權重為 $8$。頂點 $4$ 尚未連入目前的樹，加入。

此時已選取 $3$ 條邊，涵蓋全部 $4$ 個頂點，形成最小生成樹：

$$\{(1,2),(1,3),(2,4)\}$$

其總權重為：

$$5+6+8=19$$

因此最小生成樹的總權重為 $19$。

選項分析

核心觀念

本題考查現代處理器中的 Branch Prediction（分支預測） 與 Speculative Execution（推測執行）。

處理器遇到條件分支，例如：

if (condition)
 A;
else
 B;

在 condition 尚未完成計算、分支方向尚未確定前，處理器必須決定下一步要抓取與執行哪一條指令。若停下來等待分支結果，會造成 pipeline stall，降低指令管線的利用率。

Branch prediction 會根據靜態規則或過去的執行歷史，預測分支將採取的方向，例如：

• branch taken：跳轉成立
• branch not taken：不跳轉

處理器接著依照預測結果，在分支真正解析前推測性地執行後續指令。若預測正確，就能節省等待時間；若預測錯誤，則丟棄錯誤路徑上已推測執行的指令，並從正確路徑重新執行，這稱為 branch misprediction penalty。

因此，分支預測的主要目的，是降低分支造成的停頓與控制相依性對效能的影響。

解題方法

判斷各選項是否正確時，掌握兩個關鍵：

1. 分支預測是「預測」，不是保證正確。
2. 預測結果可讓處理器在分支解析前進行推測執行，以提升 pipeline throughput。

符合這兩點的選項為：

Branch prediction boosts performance by speculatively executing instructions before branch resolution.

因此官方答案為 (D)。

選項分析

(A) Branch prediction eliminates all the need for pipeline stalls.

錯誤。

分支預測可以減少因控制相依造成的 pipeline stalls，但不能消除所有停頓，原因包括：

• 分支預測可能錯誤；
• 分支目標位址可能尚未計算完成；
• 發生 cache miss；
• 資料相依或資源衝突；
• 指令解碼、記憶體存取等階段可能產生延遲。

若分支預測錯誤，處理器必須清除錯誤路徑上的指令，重新填滿 pipeline，因而產生額外停頓。因此「eliminates all」過度絕對。

(B) Branch prediction always guarantees correct predictions for all branches in a program.

錯誤。

Branch prediction 的本質是根據資訊進行預測，不可能保證所有分支都正確。

即使使用複雜的 dynamic branch predictor，仍可能遇到：

• 第一次執行某個分支時缺乏歷史資料；
• 分支行為具有高度不規則性；
• 程式輸入改變，使過去的模式失效；
• 迴圈結束時的分支方向與前幾次不同。

預測錯誤時會造成 pipeline flush 與重新取指，因此「always guarantees」不成立。

(C) Static branch prediction is more effective than dynamic branch prediction.

錯誤。

Static branch prediction 主要依據固定規則，例如：

• 一律預測 branch not taken；
• 依分支位置預測；
• 編譯器提供分支提示。

核心觀念

SQL 的 GROUP BY 子句用來依照指定欄位，將查詢結果中的資料列分成多個群組，通常搭配聚合函數使用，例如：

• COUNT：計算筆數
• SUM：加總
• AVG：平均值
• MAX：最大值
• MIN：最小值

基本語法如下：

SELECT 欄位名稱, 聚合函數(欄位名稱)
FROM 資料表
GROUP BY 欄位名稱;

例如，資料表 Sales 包含以下欄位：

Department | Amount
------------|-------
A | 100
A | 200
B | 150
B | 300

查詢各部門的銷售總額：

SELECT Department, SUM(Amount)
FROM Sales
GROUP BY Department;

執行結果為：

Department | SUM(Amount)
-----------|------------
A | 300
B | 450

GROUP BY Department 會將相同 Department 的資料列歸入同一群組，再由 SUM(Amount) 分別計算每一組的總額。

因此，GROUP BY 的核心功能是「依指定欄位分組」，常用於對各群組進行統計分析。

解題方法

判斷各選項所描述的功能，並與 SQL 常見子句的用途比對：

• 改變結果順序：ORDER BY
• 依條件篩選資料列：WHERE
• 依欄位分組並進行群組統計：GROUP BY
• 移除重複資料列：DISTINCT

題目問的是 GROUP BY，其關鍵字是「group」，即將資料依指定欄位分成群組。故正確選項為 C。

選項分析

(A) To change the order of query results

錯誤。改變查詢結果排列順序是 ORDER BY 的功能。

例如：

SELECT *
FROM Students
ORDER BY Score DESC;

此語句會按照 Score 由高到低排序，但不會將資料分組。

(B) To filter records based on conditions

錯誤。依條件篩選資料列是 WHERE 的功能。

例如：

SELECT *
FROM Students
WHERE Score >= 60;

核心觀念

本題考查不同檔案系統的設計目標，以及高解析度 MRI 影像對儲存系統的需求。

高解析度 MRI 影像通常具有以下特性：

• 單一檔案可能很大，需要支援大型檔案。
• 影像資料不能任意損毀，必須重視資料完整性。
• 醫療影像常需長期保存、備份、快照與容量擴充。
• 多個影像檔案可能需要集中管理，並具備容錯能力。

在這些選項中，ZFS（Zettabyte File System）具備大型儲存容量、資料完整性驗證、儲存池管理、快照及容錯設計，因此最符合題目所描述的高解析度 MRI 影像儲存需求。

解題方法

判斷這類題目的切入點，是比較各檔案系統的「主要設計特色」，而不是只看它是否能儲存影像檔。

可依下列順序判斷：

1. 高解析度 MRI 影像需要支援大型檔案。
2. 醫療資料需要降低檔案損毀與靜默資料錯誤的風險。
3. 儲存系統最好具備容量管理、備份、快照及容錯能力。
4. 比較各選項後，ZFS 的整體功能最符合這些需求。

因此，依本題官方答案，選擇 ZFS。

選項分析

(A) FAT32

FAT32 是相容性很高、結構較簡單的檔案系統，常見於隨身碟、記憶卡及舊式作業系統環境。

其主要缺點是單一檔案大小上限約為 $4\ \text{GB}$。高解析度 MRI 影像可能以大型 3D、4D 或多序列資料儲存，容易超過此限制。此外，FAT32 缺乏現代檔案系統常見的日誌、權限、快照及完整性驗證機制。

因此，FAT32 不適合做為高解析度 MRI 影像的主要儲存檔案系統。

(B) NTFS

NTFS 是 Windows 常用的檔案系統，支援大型檔案、檔案權限、壓縮、加密及日誌功能，實際上可以儲存 MRI 影像。

但 NTFS 的主要定位是一般用途及 Windows 系統儲存，並非特別針對大型資料池、端到端資料完整性、儲存層級容錯與快照管理而設計。相較之下，ZFS 更強調大容量儲存與資料可靠性。

因此，NTFS 並非完全不能使用，但不是本題最符合「最佳化儲存高解析度 MRI 影像」的答案。

(C) Ext4

Ext4 是 Linux 常用的通用檔案系統，支援大型檔案、日誌、延伸屬性及良好的穩定性，也能實際儲存醫療影像資料。

然而，Ext4 本身主要是單一主機的通用檔案系統，資料完整性校驗、儲存池、RAID 管理、快照等功能通常需要搭配其他工具或儲存層實現。它不像 ZFS 將檔案系統與儲存管理、校驗及容錯功能整合在一起。

核心觀念

本題考查 DNS（Domain Name System，網域名稱系統）的功能。

DNS 是網路中的「名稱解析服務」，負責將人類容易記憶的網域名稱，例如 www.example.com，解析成電腦通訊所需的 IP 位址，例如 93.184.216.34。使用者輸入網址後，裝置通常會先向 DNS 伺服器查詢對應的 IP 位址，再依該 IP 位址與目標主機建立連線。

DNS 採用階層式、分散式架構，常見的解析流程包含：

1. 用戶端向 DNS resolver 查詢網域名稱。
2. Resolver 依序查詢根網域、頂級網域及權威名稱伺服器。
3. 權威名稱伺服器回傳該網域的 DNS 紀錄。
4. 用戶端取得 IP 位址後，使用 IP 進行網路連線。

最常見的是將網域名稱解析為 IPv4 的 A 紀錄或 IPv6 的 AAAA 紀錄。

解題方法

判斷網路服務功能時，可將選項中的工作分成幾類：

• 「名稱」與「IP 位址」之間的轉換：DNS。
• 「分配 IP 位址」：DHCP。
• 「確認資料正確傳輸」：檢查碼、TCP 等機制。
• 「加密資料」：TLS、SSL 或 VPN 等安全機制。
• 「觀察流量與頻寬」：網路監控工具。

題目詢問 DNS server 的 purpose，與 DNS 定義完全相符的敘述是「將 domain names 轉換成 IP addresses」，因此選擇 B。

選項分析

(A) Assign IP addresses to devices.

錯誤。自動分配 IP 位址通常是 DHCP（Dynamic Host Configuration Protocol，動態主機設定協定）的功能。DHCP 可提供裝置 IP 位址、子網路遮罩、預設閘道及 DNS 伺服器位址等設定，但這不是 DNS 的主要功能。

(B) Translate domain names into IP addresses.

正確。DNS 將人類可讀的網域名稱解析為 IP 位址，使瀏覽器或其他網路應用程式能找到目標主機。例如：

核心觀念

本題考查：

1. C 語言的位元 OR 運算子 $|$
2. 負整數的二補數表示法
3. 二進位位元逐位運算
4. 二補數位元模式如何轉回十進位整數

位元 OR 的規則如下：

位元 1	位元 2	OR 結果
0	0	0
0	1	1
1	0	1
1	1	1

只要其中一個位元是 $1$，結果位元就是 $1$。

---

解題方法

程式中的關鍵運算為：

int k = 18;
printf("%d\n", k | (-k));

已知：

$$k=18$$

將 $18$ 寫成二進位。以常見的 $8$ 位元表示：

$$18=(00010010)_2$$

接著求 $-18$ 的二補數：

1. 先將 $18$ 的位元全部反相：

$$00010010 \longrightarrow 11101101$$

2. 再加 $1$：

$$11101101+1=11101110$$

因此：

$$-18=(11101110)_2$$

進行位元 OR：

$$\begin{array}{r} 00010010\\ \mathbin{|}\ 11101110\\ \hline 11111110 \end{array}$$

所以：

$$18\mathbin{|}(-18)=(11111110)_2$$

判斷 $11111110$ 為負數，利用二補數轉回十進位：

1. 反相：

$$11111110\longrightarrow00000001$$

2. 加 $1$：

$$00000001+1=00000010$$ $$(00000010)_2=2$$

由於原本是負數，因此：

$$(11111110)_2=-2$$

所以程式輸出：

-2

---

關鍵程式追蹤（Trace）

步驟	運算或數值	結果
1	k = 18	$18$
2	-k	$-18$
3	$18$ 的二進位	00010010
4	$-18$ 的二補數	11101110
5	`00010010	11101110`

核心觀念

ACID 是資料庫交易（database transaction）必須具備的四項重要性質：

• Atomicity（原子性）：交易中的所有操作必須全部成功，或全部取消，不允許只完成一部分。
• Consistency（一致性）：交易執行前後，資料庫都必須符合既定的完整性限制與規則。
• Isolation（隔離性）：同時執行的交易彼此隔離，一個交易的中間狀態不應被其他交易讀取。
• Durability（持久性）：交易一旦完成並提交（commit），其結果即使發生系統故障，也必須保留。

因此，ACID 的完整展開為：

$$\text{Atomicity, Consistency, Isolation, Durability}$$

解題方法

本題屬於資料庫基本名詞辨識題。直接將 ACID 的四個字母依序對應資料庫交易的標準性質：

字母	性質	中文意義
A	Atomicity	原子性
C	Consistency	一致性
I	Isolation	隔離性
D	Durability	持久性

四者完全符合選項 (B)，因此選 B。

選項分析

(A) Aggregation, Control, Integrity, Data

錯誤。這四個詞並不是資料庫交易 ACID 的標準定義。雖然 Integrity 與資料庫完整性有關，Control、Data 也可能出現在資料庫相關語境中，但不構成 ACID 的正式展開。

(B) Atomicity, Consistency, Isolation, Durability

正確。

核心觀念

本題考查 C++ std::vector 的資料結構特性與常用成員函式：

• size：目前實際儲存的元素數量。
• capacity：目前已配置、可容納的元素數量。
• reserve：預先配置容量，不改變實際元素數量。
• push_back：在尾端加入元素，通常具有攤銷 $O(1)$ 時間複雜度。
• std::vector：元素儲存在連續記憶體區域，因此可與 C-style array 的指標介面搭配。

關鍵判斷在於：選項敘述是否符合 std::vector 的標準定義，以及是否使用了「always」這類過度絕對的字眼。

解題方法

逐一檢查各選項：

1. 比較 size 與 capacity 是否必然相等。
2. 判斷 vector 對元素型別是否要求 default constructor。
3. 分辨 push_back 的「攤銷複雜度」與「單次最壞情況複雜度」。
4. 確認 reserve 影響的是容量還是元素數量。
5. 判斷 vector 的儲存位置是否連續。

符合標準定義且沒有錯誤限制的選項，即為正確答案。

選項分析

(A) The size of a std::vector is always equal to its capacity.

錯誤。

size 表示目前已有多少個元素，capacity 表示目前配置的儲存空間最多可容納多少個元素，兩者不一定相等。

例如：

std::vector<int> v;
v.reserve(10);

此時：

v.size == 0
v.capacity == 10

因此：

$$\text{size} \leq \text{capacity}$$

只有在容量剛好用滿時，兩者才會相等。

(B) std::vector can only store objects that have a default constructor.

錯誤。

std::vector 不要求元素型別一定具有 default constructor。只要使用的操作符合該型別所需的建構、複製或移動條件即可。

例如：

class A {
public:
 A(int x) {}
 A = delete;
};

std::vector<A> v;
v.emplace_back(5);

A 沒有 default constructor，但仍可使用 emplace_back(5) 建立元素。

需要注意的是，某些特定操作，例如：

std::vector<A> v(10);

可能要求 A 能夠以預設方式建構；這是該操作的要求，不代表所有 std::vector 元素都必須具有 default constructor。

(C) The push_back function always has $O(1)$ time complexity.

錯誤。

push_back 在通常情況下只需將元素放到現有容量的尾端，因此單次操作常為 $O(1)$。

但是，當目前容量不足時，vector 必須：

1. 配置更大的連續記憶體。
2. 將原有元素複製或移動到新空間。
3. 釋放舊空間。
4. 將新元素加入尾端。

若目前有 $n$ 個元素，擴容時搬移元素需要 $O(n)$，因此單次 push_back 的最壞情況為：

$$O(n)$$

核心觀念

本題考查 AVL tree 的二元搜尋樹性質、平衡因子與旋轉操作。

1. 二元搜尋樹（BST）：

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

2. AVL tree：

• 每個節點的平衡因子為
  $BF=\text{左子樹高度}-\text{右子樹高度}$
• 必須滿足
  $BF\in\{-1,0,1\}$

3. 插入新節點後，若某節點的平衡因子變成 $2$ 或 $-2$，必須透過旋轉恢復平衡。旋轉可能是：

• LL：右旋
• RR：左旋
• LR：先左旋，再右旋
• RL：先右旋，再左旋

---

解題方法

依題意依序插入：

$46,\ 45,\ 48,\ 42,\ 41$

依官方答案所採用的樹形，最後結構為：

 46
 / \
 42 48
 / \
 41 45

各節點層級如下：

• $46$：level 1
• $42,48$：level 2
• $41,45$：level 3

因此：

• $42$ 是 $46$ 的左子節點，且位於 level 2。
• $48$ 是 $46$ 的右子節點，位於 level 2。
• $41$ 是 $42$ 的左子節點，位於 level 3。
• $45$ 是 $42$ 的右子節點，位於 level 3。

---

選項分析

(A) 42 is at level 2, and 42 is the left child of 46.

$42$ 位於根節點 $46$ 的左下方，層級為 level 2，且確實是 $46$ 的左子節點。

因此本選項正確。

---

(B) 41 is at level 4, and 41 is the left child of 42.

$41$ 確實是 $42$ 的左子節點，但由樹形可知：

$46\rightarrow42\rightarrow41$

核心觀念

本題考查醫療人工智慧中的 ensemble learning（集成學習）。

集成學習是將多個模型的預測結果加以整合，形成一個整體模型。常見方法包括：

• Bagging：訓練多個模型後投票或平均，例如 Random Forest。
• Boosting：依序訓練模型，逐步修正前一個模型的錯誤。
• Stacking：由另一個模型學習如何整合多個基礎模型的輸出。

其核心思想是：不同模型具有不同的錯誤模式，將它們適當整合後，可以降低單一模型的預測偏差或變異，使預測結果更穩定、更準確。

在醫療 AI 中，資料常具有影像差異大、病人個體差異高、誤判成本高等特性。集成學習可整合多個分類器、神經網路或不同訓練資料所產生的模型，以提升疾病分類、影像判讀及風險預測的可靠度。

解題方法

判斷本題可直接抓住 ensemble learning 的定義：

Ensemble learning 的主要目的，是結合多個模型的預測結果，以改善整體模型的預測表現。

因此，選項中直接描述「結合多個模型以獲得更好的預測準確度」者，即符合定義。

集成模型的預測可簡化表示如下：

分類問題常使用多數決：

$$\hat{y}=\operatorname{mode}\left(f_1(x),f_2(x),\ldots,f_M(x)\right)$$

迴歸問題則常使用平均：

$$\hat{y}=\frac{1}{M}\sum_{i=1}^{M}f_i(x)$$

其中 $f_i(x)$ 代表第 $i$ 個模型對輸入資料 $x$ 的預測，$M$ 代表模型數量。透過整合多個模型，整體預測通常比單一模型更穩定。

選項分析

(A) To combine multiple models for better prediction accuracy

核心觀念

本題考查兩個重點：

1. C++ 參照（reference）傳遞
2. 函式參數的傳值與區域變數作用域

函式定義為：

int f(int &x, int y)

• int &x：x 是參照參數，直接連結到主程式中的 a。修改 x 就等同於修改 a。
• int y：y 是傳值參數，函式取得 b 的副本。修改 y 不會影響主程式中的 b。

---

解題方法與逐步追蹤

主程式初始狀態：

$$a=4,\qquad b=1$$

呼叫：

f(a, b)

因此：

• x 參照 a
• y 取得 b 的副本，初值為 $1$

依照函式內容逐行追蹤：

第 1 行

x = y * 2;

代入 $y=1$：

$$x=1\times 2=2$$

由於 x 是 a 的參照，因此：

$$a=2$$

此時：

$$x=2,\qquad y=1,\qquad a=2,\qquad b=1$$

第 2 行

y = x + 3;

代入 $x=2$：

$$y=2+3=5$$

此處只修改函式內的區域副本 y，不會修改主程式中的 b，所以：

$$a=2,\qquad b=1$$

第 3 行

return x + y;

$$x+y=2+5=7$$

因此函式回傳 $7$。

在本題官方採用的解讀下，printf 輸出：

7 2 1

---

選項分析

(A) 7 2 1

正確。

• f(a,b) 回傳 $7$
• x 透過參照修改 a，使 $a=2$
• y 是 b 的副本，修改後不影響 $b$，因此 $b=1$

所以輸出為：

$$\boxed{7\ 2\ 1}$$

(B) 7 2 5

錯誤。

核心觀念

本題考查不同機器學習模型對「序列資料（sequential data）」的處理能力。

序列資料具有明顯的時間或先後順序，前後資料點通常彼此相關。例如：

• 病人的連續心電圖訊號
• 逐日血糖、血壓紀錄
• 病歷事件的發生順序
• ICU 生命徵象時間序列
• 症狀、檢驗結果與用藥紀錄的時間變化

分析這類資料時，模型需要保留先前時間點的資訊，才能判斷目前資料的意義。Recurrent Neural Network（RNN，循環神經網路）會透過「隱藏狀態（hidden state）」傳遞過去的資訊，具備處理序列與時間依賴關係的設計。

RNN 的基本概念可表示為：

$$h_t = f(W_x x_t + W_h h_{t-1} + b)$$

其中：

• $x_t$：第 $t$ 個時間點輸入的資料
• $h_{t-1}$：前一個時間點的隱藏狀態
• $h_t$：目前時間點更新後的隱藏狀態
• $W_x, W_h$：權重矩陣
• $b$：偏差
• $f$：啟動函數，例如 $\tanh$

由於 $h_t$ 同時受到目前輸入 $x_t$ 與過去狀態 $h_{t-1}$ 影響，RNN 能夠在分析目前資料時納入歷史資訊。

解題方法

判斷本題的關鍵在於辨認「sequential medical data」的特徵：

1. 資料具有時間順序。
2. 前面資料可能影響後面資料的解讀。
3. 模型需要某種形式的記憶機制，保存過去時間點的資訊。

四個主要選項中，RNN 是專門針對序列資料設計的神經網路。它會逐步讀取：

$$x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow \cdots \rightarrow x_T$$

並在每一步更新隱藏狀態，使後續預測能參考先前資料。因此依照本題官方答案，正確選項為 D。

在實務上，RNN 的改良架構包括 LSTM（Long Short-Term Memory）與 GRU（Gated Recurrent Unit），可改善長序列中的記憶與梯度消失問題。題目雖未列出這些模型，但 RNN 仍是最符合題意的選項。

選項分析

(A) Convolutional Neural Network（CNN）

CNN 主要利用卷積運算擷取局部特徵，常用於：

• 影像辨識
• 醫學影像分析
• X 光、CT、MRI 影像分類
• 具有局部模式的訊號分析

CNN 也能應用於一維時間序列，例如心電圖波形，因此它並非完全不能分析醫療序列資料。然而，傳統 CNN 的核心設計是擷取局部區域特徵，通常不具備像 RNN 那樣明確的遞迴記憶機制，對長時間範圍的前後依賴關係處理較不直接。

因此，在題目詢問「最適合分析序列資料」且選項包含 RNN 時，CNN 不是最佳答案。

(B) Feedforward Neural Network

核心觀念

本題考查排序資料的 Merge（合併）程序及其時間複雜度。

兩個已排序的病患 ID 清單，可以使用兩個指標分別指向兩個清單目前尚未處理的元素：

1. 比較兩個指標所指的 ID。
2. 將較小者放入結果清單。
3. 被選出的清單指標向後移動一格。
4. 當其中一個清單處理完畢，將另一個清單剩餘元素直接接到結果尾端。

由於兩個清單本身已排序，不需要重新排序全部資料。

解題方法

假設兩個清單長度分別為 $m$ 與 $n$，合併程序的概念程式碼如下：

i = 0
j = 0
result = []

while i < m and j < n:
 if list1[i] <= list2[j]:
 append list1[i] to result
 i = i + 1
 else:
 append list2[j] to result
 j = j + 1

append list1[i ... m-1] to result
append list2[j ... n-1] to result

每次迴圈至少會讓 $i$ 或 $j$ 增加 $1$，因此每個元素最多被處理一次。合併後共有 $m+n$ 個元素，所以最多需要進行與 $m+n$ 成正比的操作：

$$T(m,n)=O(m+n)$$

若題目以 $n$ 表示兩個清單的總資料量，則：

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

即使兩個清單各有 $n$ 個元素，總操作數為 $O(2n)$，依大 $O$ 定義仍可化簡為：

$$O(2n)=O(n)$$

逐步追蹤範例

假設兩個已排序的病患 ID 清單為：

list1 = [101, 105, 110]
list2 = [102, 104, 111]

處理過程如下：

比較	選出的 ID	結果清單
$101$ 與 $102$	$101$	$[101]$
$105$ 與 $102$	$102$	$[101,102]$

核心觀念

本題考查 **Real-time Transport Protocol（RTP，實時傳輸協定）**的功能、所在網路層級，以及它與 UDP、RTCP 的關係。

RTP 是設計來傳送即時多媒體資料的協定，例如：

• 語音
• 影像
• 視訊會議
• 網路電話
• 線上影音串流

RTP 通常運作於應用層，並以 UDP 作為下層傳輸協定。RTP 封包通常包含：

• Sequence number：協助接收端判斷封包順序與遺失情況
• Timestamp：協助播放時序與媒體同步
• Payload type：標示資料格式，例如音訊編碼或視訊編碼
• Synchronization Source identifier：識別資料來源

RTP 的設計重點是「即時性」，而不是可靠性。即時通訊通常寧可捨棄遺失或過晚的封包，也不長時間等待重傳。

解題方法

判斷各選項時，可從三個方向切入：

1. RTP 是否用於音訊、視訊等即時資料？
2. RTP 是否提供可靠且依序的傳輸保證？
3. RTP 屬於哪一個網路層，以及是否限定某種網路型態？

RTP 的核心用途是提供即時資料傳輸所需的封包格式與時序資訊，因此與音訊、視訊傳送直接相關。至於可靠傳輸、流量控制與壅塞控制，則不是 RTP 本身的主要責任。

選項分析

(A) RTP provides end-to-end delivery services for real-time data such as audio and video.

此選項正確。

RTP 提供端點到端點的即時資料傳送支援，適用於音訊與視訊等連續媒體資料。它透過序號、時間戳記與資料格式標示，使接收端能夠：

• 判斷封包順序
• 偵測封包遺失
• 依適當時間播放資料
• 處理不同媒體資料格式

因此，依本題官方答案，RTP 的主要功能符合此選項描述。

須注意，「提供 delivery services」不代表 RTP 保證可靠傳輸。RTP 提供的是即時媒體傳送所需的控制資訊與封包結構，而非 TCP 式的可靠傳輸服務。

(B) RTP guarantees in-order delivery.

此選項錯誤。

RTP 不保證封包依序抵達。網際網路採用封包交換，封包可能因不同路徑、壅塞或排程差異而：

• 延遲
• 失序
• 遺失
• 重複

RTP 標頭中的 sequence number 可以讓接收端知道封包的順序，並偵測是否有封包遺失，但它本身不會保證封包依序抵達，也不一定負責重新傳送遺失封包。

「能辨識失序」與「保證依序交付」是不同概念。

(C) RTP is a transport-layer protocol that runs directly on top of IP.

此選項錯誤。

核心觀念

本題考查「加權圖上的最短路徑演算法」。

將道路網路視為圖（Graph）：

• 頂點（Vertex）：醫院、路口、事故地點等位置。
• 邊（Edge）：兩個位置之間的道路。
• 邊權重（Weight）：行車時間、距離或成本。
• 目標：找出從起點到目的地的最小總旅行時間。

道路行車時間通常為非負數，因此適合使用 Dijkstra’s Algorithm 求解單一起點到各頂點的最短路徑。

若路徑為：

$$A \rightarrow B \rightarrow C$$

其總旅行時間為：

$$w(A,B)+w(B,C)$$

Dijkstra 演算法的核心是：每次選出目前「暫定距離最小」且尚未確定的頂點，將其最短距離確定，再利用它更新鄰接頂點的距離。

---

解題方法

題目中的關鍵字是：

• graph algorithm：圖演算法
• ambulance routes：救護車路線
• minimal travel time：最小旅行時間

因此要尋找的是「加權圖最短路徑演算法」。

Dijkstra 演算法流程

設起點為 $S$：

1. 將起點距離設為 $0$，其他頂點設為 $\infty$。
2. 選出目前距離最小且尚未處理的頂點。
3. 以該頂點更新其鄰接點：

$$\operatorname{dist}(v) = \min\left(\operatorname{dist}(v),\operatorname{dist}(u)+w(u,v)\right)$$

4. 重複上述步驟，直到目的地的最短距離確定。

簡單追蹤

假設道路時間如下：

• $A \rightarrow B = 4$
• $A \rightarrow C = 2$
• $C \rightarrow B = 1$
• $B \rightarrow D = 5$
• $C \rightarrow D = 8$

從 $A$ 出發：

步驟	確定頂點	$A$ 到各點的暫定時間
初始	無	$A=0,\ B=\infty,\ C=\infty,\ D=\infty$
1	$A$	$B=4,\ C=2,\ D=\infty$
2	$C$	經由 $C$ 到 $B=2+1=3$，因此 $B=3$；到 $D=2+8=10$
3	$B$	經由 $B$ 到 $D=3+5=8$，因此 $D=8$
4	$D$	最短時間確定

所以最短路徑為：

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

最小旅行時間為：

$$2+1+5=8$$

這正是救護車路線最佳化所需的功能。

關鍵虛擬碼

核心觀念

本題考查深度學習模型的訓練方式，以及「最佳化演算法」與「機器學習模型」的區別。

深度學習通常先定義損失函數 $L(\theta)$，其中 $\theta$ 代表模型的參數，例如權重與偏差。訓練目標是找出能使損失函數最小的參數：

$$\min_{\theta} L(\theta)$$

Gradient Descent（梯度下降法）利用損失函數對參數的梯度，判斷損失增加最快的方向，再朝相反方向更新參數。

---

解題方法

梯度 $\nabla_{\theta}L(\theta)$ 指向損失函數上升最快的方向，因此最小化損失時，參數應沿著負梯度方向更新：

$$\theta_{t+1} = \theta_t-\eta\nabla_{\theta}L(\theta_t)$$

其中：

• $\theta_t$：第 $t$ 次更新前的模型參數
• $\eta$：學習率（learning rate）
• $\nabla_{\theta}L(\theta_t)$：損失函數對參數的梯度
• $\theta_{t+1}$：更新後的模型參數

在深度學習中，梯度通常透過反向傳播（backpropagation）計算，再使用 Gradient Descent 的變形方法更新參數，例如：

• Batch Gradient Descent
• Stochastic Gradient Descent（SGD）
• Mini-batch Gradient Descent
• Adam

因此，題目問「常用來最小化深度學習模型損失的最佳化演算法」，正確切入點是 Gradient Descent。

---

選項分析

(A) Gradient Descent：正確

Gradient Descent 是深度學習中最基本且常見的損失最小化方法。它透過計算梯度，逐步調整神經網路參數，使損失函數下降。

實際使用的 SGD、Mini-batch SGD 與 Adam，皆可視為以梯度資訊為基礎的參數最佳化方法。因此官方答案為 A。

(B) K-means：錯誤

K-means 是非監督式學習中的分群演算法，目標是將資料分成 $k$ 個群集，並最小化資料點與所屬群中心之間的平方距離：

核心觀念

UPS 是 Uninterruptible Power Supply（不斷電系統） 的縮寫，主要功能是在市電中斷、電壓不穩或瞬間停電時，立即由電池提供備援電力，使醫院伺服器與儲存設備能持續運作一段時間。

UPS 可避免伺服器突然關機，讓系統：

• 維持關鍵服務運作；
• 將尚未寫入磁碟的資料完成寫入；
• 讓管理人員有時間安全關機；
• 降低檔案損毀、資料遺失與硬體損壞的風險。

因此，本題將 UPS 的主要目的概括為「停電時防止資料遺失」。

解題方法

判斷各選項是否屬於 UPS 的功能即可。UPS 的關鍵字是：

停電備援、電池供電、不斷電、安全關機

它不是用來提升伺服器的運算效能、加密資料、冷卻設備或阻擋惡意程式。

當醫院伺服器室停電時，UPS 會在極短時間內切換至電池供電，避免伺服器立即斷電。伺服器若突然關機，可能造成資料尚未完成寫入，進而發生檔案損毀或資料遺失；UPS 正是用來降低這類風險。

選項分析

(A) Speed up data processing

錯誤。UPS 的工作是提供穩定且不中斷的電力，不會增加 CPU、記憶體、硬碟或網路設備的處理速度。伺服器效能通常取決於處理器、記憶體、儲存裝置與軟體設計等因素。

(B) Prevent data loss during power outages

核心觀念

TCP/IP 模型通常分為四層，由上到下如下：

1. Application layer（應用層）：提供網路應用服務，例如 HTTP、FTP、DNS、SMTP。
2. Transport layer（傳輸層）：提供端點到端點的資料傳輸，例如 TCP、UDP，負責分段、流量控制與可靠性。
3. Internet layer（網際網路層）：負責邏輯定址與封包路由，例如 IP、ICMP。
4. Data link layer（資料鏈結層）：負責同一網路鏈結上的資料傳輸、框架封裝與媒體存取，例如 Ethernet、Wi-Fi。

因此，由模型頂端到底端的正確順序是：

$$\text{Application} \rightarrow \text{Transport} \rightarrow \text{Internet} \rightarrow \text{Data Link}$$

題目編號對應為：

$$3 \rightarrow 2 \rightarrow 1 \rightarrow 4$$

解題方法

直接依照 TCP/IP 四層模型的階層順序判斷：

• 最上層是 application layer，編號 3。
• 應用程式的資料交給 transport layer，編號 2。
• 傳輸層資料再交給 internet layer，編號 1。
• 最後由 data link layer 傳送到實體網路，編號 4。

所以正確排列為：

$$3,2,1,4$$

選項分析

• (A) 2, 3, 1, 4：錯誤

此選項將 transport layer 放在 application layer 之上。實際上，應用層使用傳輸層提供的服務，因此 application layer 應位於 transport layer 之上，正確開頭應為 $3,2$。

• (B) 3, 2, 1, 4：正確

核心觀念

本題考查 C 語言的：

• 前置遞增運算子 ++x
• 後置遞減運算子 y--
• 運算式求值與指定敘述
• printf 輸出變數目前的值

兩種運算子的差異如下：

• ++x：先將 x 加 $1$，再使用增加後的值。
• y--：先使用 y 原本的值，再將 y 減 $1$。

解題方法與逐步追蹤

原始程式碼可整理如下：

int x = 6;
int y = 23;
int z = ++x + y--;

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

依序追蹤：

1. 初始值：

$$x=6,\quad y=23$$

2. 計算 ++x：

x 先遞增：

$$x=6+1=7$$

因此 ++x 在加法中所提供的值為 $7$。

3. 計算 y--：

y-- 先取出原本的值 $23$ 作為運算值，再將 y 減 $1$：

$$y=23-1=22$$

因此 y-- 在加法中所提供的值為 $23$。

4. 計算 z：

$$z=++x+y--=7+23=30$$

5. 執行 printf 時，三個變數的值為：

$$x=7,\quad y=22,\quad z=30$$

所以輸出為：

7 22 30

運算順序的補充說明

C 語言不保證 + 左右兩側一定按照由左至右的順序求值。不過本題中：

• ++x 只修改 x
• y-- 只修改 y

兩者操作的是不同變數，因此不會造成同一變數的衝突。無論先處理哪一側，最後仍然得到：

$$x=7,\quad y=22,\quad z=30$$

核心觀念

本題考查 SQL 中「清空資料表內容」與「刪除資料表本身」的差異。

若要求：

• 移除資料表中的全部紀錄；
• 保留資料表結構，例如欄位、資料型別、索引與資料表名稱；

標準答案為 TRUNCATE TABLE。

其基本語法為：

TRUNCATE TABLE table_name;

執行後，資料表仍然存在，但其中的所有資料列會被移除。

---

解題方法

判斷重點在於區分以下三種操作：

1. TRUNCATE TABLE：清空資料表中的所有紀錄，但保留資料表結構。
2. DELETE FROM：刪除資料列；未加 WHERE 時可刪除全部資料。
3. DROP TABLE：連資料表結構一併刪除。

題目明確要求「remove all records from a table but keep the structure」，最直接對應的 SQL 指令是：

TRUNCATE TABLE table_name;

因此依照本題官方公布答案，選擇 (A)。

---

選項分析

(A) TRUNCATE TABLE——正確

TRUNCATE TABLE 用來快速移除資料表中的全部資料列，但不刪除資料表本身。

例如：

TRUNCATE TABLE Student;

執行後：

• Student 資料表仍存在；
• 欄位定義仍保留；
• 資料表中的所有紀錄被清除；
• 通常不能搭配 WHERE 指定只刪除部分資料。

這正好符合題目要求。

---

(B) DROP TABLE——錯誤

DROP TABLE 會刪除整個資料表，包括：

• 資料表中的所有資料；
• 欄位結構；
• 索引；
• 約束；
• 資料表物件本身。

例如：

DROP TABLE Student;

執行後，Student 資料表不再存在，因此不符合「保留結構」的要求。

---

(C) DELETE FROM——依題意有爭議，官方答案不選此項

DELETE FROM 用於刪除資料列。例如：

DELETE FROM Student;

未加上 WHERE 條件時，確實會刪除 Student 資料表中的全部紀錄，而且資料表結構仍然保留。

核心觀念

Huffman code（霍夫曼編碼）是一種無失真資料壓縮方法，利用不同符號出現頻率的差異，配置不同長度的二進位碼：

• 出現頻率高的符號，使用較短的編碼。
• 出現頻率低的符號，使用較長的編碼。
• 編碼具有 prefix-free（前綴無關）特性，任何符號的編碼都不是另一符號編碼的前綴，因此能夠唯一解碼。

Huffman code 的目標是降低每個符號的平均編碼長度，進而減少資料所需的儲存位元數：

$$L=\sum_{i=1}^{n}p_i l_i$$

其中：

• $p_i$：第 $i$ 個符號的出現機率
• $l_i$：第 $i$ 個符號的編碼長度
• $L$：平均編碼長度

平均編碼長度越低，代表相同資料所需的儲存空間越少。

---

解題方法

題目問的是：

What is the purpose of Huffman code?

判斷關鍵在於 Huffman code 的功能。它根據符號頻率建立二元樹，讓高頻率符號使用短碼、低頻率符號使用長碼，以降低資料的平均位元數。

基本建立步驟如下：

1. 統計每個符號的出現頻率。
2. 將頻率最低的兩個節點合併。
3. 將合併後的頻率重新放回節點集合。
4. 重複合併，直到形成一棵二元樹。
5. 從根節點到各符號的路徑產生二進位編碼。

例如，若符號頻率如下：

符號	頻率
A	0.50
B	0.25
C	0.125
D	0.125

Huffman 編碼可配置為：

符號	編碼	長度
A	0	1
B	10	2
C	110	3
D	111	3

平均編碼長度為：

$$L=(0.50)(1)+(0.25)(2)+(0.125)(3)+(0.125)(3)$$ $$L=0.5+0.5+0.375+0.375=1.75\text{ bits/symbol}$$

固定長度編碼需要 $2$ bits/symbol，Huffman 編碼平均只需 $1.75$ bits/symbol，因此能節省儲存空間。

Huffman code 是無失真壓縮，解碼後可還原原始資料，不會像有失真壓縮造成影像或聲音內容的永久損失。

---

選項分析

(A) To increase data transmission speed

核心觀念

本題考查 diffusion models（擴散模型）在醫療人工智慧中的主要貢獻。

擴散模型通常包含兩個階段：

1. 前向擴散（forward diffusion）：逐步對原始影像加入高斯雜訊，使影像逐漸接近純雜訊。
2. 反向去噪（reverse denoising）：訓練模型學習如何逐步移除雜訊，從雜訊還原出清晰且合理的醫療影像。

其核心機率模型可概念化表示為：

$$x_t=\sqrt{\bar{\alpha}_t}x_0+\sqrt{1-\bar{\alpha}_t}\epsilon$$

其中：

• $x_0$：原始醫療影像
• $x_t$：加入雜訊後第 $t$ 步的影像
• $\epsilon$：高斯雜訊
• $\bar{\alpha}_t$：控制影像訊息保留程度的參數

模型學習反向過程，估計並移除影像中的雜訊，最後產生高品質影像。因此，擴散模型可應用於醫療影像的去噪、超解析度、影像重建、缺損修復及影像生成。

解題方法

本題問的是 diffusion models「如何貢獻於 medical AI」。判斷重點在於擴散模型最直接、最典型的功能。

擴散模型的主要運作機制就是逐步加噪，再學習逐步去噪。因此，在醫療影像處理中，能夠：

• 降低 MRI、CT、X-ray 等影像中的雜訊；
• 改善影像清晰度與視覺品質；
• 從低品質或不完整資料重建較高品質影像；
• 協助醫師及後續分類、分割模型辨識影像特徵。

所以最符合其核心貢獻的是：

By improving image quality through denoising

選項分析

(A) By replacing CNN-based classifiers

錯誤。擴散模型並非以取代 CNN 分類器為主要目的。

CNN 擅長從影像中擷取局部特徵，常用於：

• 腫瘤分類；
• 病灶辨識；
• 影像分割；
• 疾病診斷。

擴散模型主要是生成模型，重點在於學習資料分布、影像生成與去噪。它可以與 CNN 搭配使用，例如先用 diffusion model 改善影像品質，再交由 CNN 進行分類，但不代表必然取代 CNN-based classifiers。

(B) By eliminating the need for labeled datasets

錯誤。擴散模型的訓練通常不需要每張影像都具備人工標籤，這是其優勢之一，但不能說完全消除 labeled datasets 的需求。

在醫療 AI 中，分類、分割及診斷模型仍常需要標註資料進行監督式學習。擴散模型可透過無標籤影像學習影像分布，也可生成合成資料以擴充訓練集，減少對標註資料的依賴，但不是徹底消除標註資料需求。

核心觀念

本題考查 Merge Sort（合併排序）的基本性質，包括：

1. 時間複雜度
2. 穩定性（stability）
3. 是否為原地排序（in-place）
4. 對陣列與鏈結串列的適用性
5. 是否具備適應性（adaptiveness）

Merge Sort 採用 Divide and Conquer（分治法）：

• 將序列遞迴切成兩半。
• 分別排序左右兩半。
• 將兩個已排序序列合併。

其遞迴式為：

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

其中 $O(n)$ 來自每一層的合併操作，因此：

$$T(n)=O(n\log n)$$

Merge Sort 的典型額外空間複雜度為：

$$O(n)$$

---

解題方法

判斷本題的關鍵，是掌握標準 Merge Sort 的五項特徵：

性質	標準 Merge Sort
最佳時間複雜度	$O(n\log n)$
平均時間複雜度	$O(n\log n)$
最差時間複雜度	$O(n\log n)$
是否穩定	是
額外空間	通常為 $O(n)$
是否原地排序	通常否
是否具適應性	通常否

合併兩個已排序序列時，若左右兩側元素相等，優先取左側元素：

if left[i] <= right[j]:
 output.append(left[i])
 i += 1
else:
 output.append(right[j])
 j += 1

使用 <= 可保留相等元素原本的先後順序，因此具備穩定性。

---

關鍵程式碼與逐步追蹤

以下為標準 Merge Sort 的概念程式碼：

MergeSort(A):
 if length(A) <= 1:
 return A

 mid = length(A) // 2
 left = MergeSort(A[0:mid])
 right = MergeSort(A[mid:])

 return Merge(left, right)

合併程序如下：

Merge(left, right):
 result = []

 while left 非空 且 right 非空:
 if left[0] <= right[0]:
 將 left[0] 放入 result
 else:
 將 right[0] 放入 result

 將剩餘元素放入 result
 return result

以序列：

$$[6,3,8,2]$$

為例：

第一步：分割

$$[6,3,8,2] \rightarrow [6,3]\ [8,2]$$

繼續分割：

$$[6,3]\rightarrow [6]\ [3]$$ $$[8,2]\rightarrow [8]\ [2]$$

第二步：合併

合併 $[6]$ 與 $[3]$：

• 比較 $6$ 與 $3$，取 $3$
• 將剩下的 $6$ 放入

得到：

$$[3,6]$$

合併 $[8]$ 與 $[2]$：

$$[2,8]$$

最後合併 $[3,6]$ 與 $[2,8]$：

• 比較 $3$、$2$，取 $2$
• 比較 $3$、$8$，取 $3$
• 比較 $6$、$8$，取 $6$
• 放入剩餘的 $8$

結果為：

$$[2,3,6,8]$$

每一層合併所處理的元素總數為 $n$，遞迴層數為 $\log n$，因此總時間為 $O(n\log n)$。

---

選項分析

(A) Merge Sort has the worst-case time complexity of $O(n^2)$.

錯誤。

標準 Merge Sort 的最差時間複雜度為：

$$O(n\log n)$$

原因是無論輸入資料是否已排序，Merge Sort 都會將資料分割成約 $\log n$ 層；每一層的合併工作總量為 $O(n)$。

因此：

核心觀念

本題考查 NP、NP-hard 與 NP-complete 的定義及彼此關係。

• P：可在多項式時間內求解的決策問題集合。
• NP：給定一個候選解後，可以在多項式時間內驗證其正確性的決策問題集合。
• NP-hard：至少與 NP 中最困難的問題一樣難。NP-hard 問題不一定屬於 NP，也不一定是決策問題。
• NP-complete：同時滿足以下兩項的問題：

$$\text{NP-complete}=\text{NP}\cap\text{NP-hard}$$

因此，NP-complete 問題必須：

1. 屬於 NP，能在多項式時間內驗證候選解。
2. 屬於 NP-hard，所有 NP 問題都能在多項式時間內歸約至此問題。

---

解題方法

逐一檢查各選項是否符合 NP-complete 問題的定義與性質。

判斷重點是：

• NP-complete 問題本身不是「完全沒有解」的問題。
• 「能快速驗證」是 NP 的特徵。
• 「所有 NP 問題可歸約至它」是 NP-hard 的特徵。
• 若 $P=NP$，NP-complete 問題也會有多項式時間解法。

---

選項分析

(A) It has no solutions.

NP-complete 問題並不表示「沒有解」。

NP-complete 通常是決策問題，輸出為 Yes 或 No。例如 SAT 問題是在判斷某個布林公式是否存在滿足指派：

• 有滿足指派：答案為 Yes。
• 沒有滿足指派：答案為 No。

NP-complete 的意思是問題具有高度計算複雜度，而不是所有輸入都沒有解。某些輸入確實可能沒有解，但也有許多輸入具有解，因此「它沒有解」不是 NP-complete 問題的必然性質。

所以本選項不正確，符合官方答案。

---

(B) It can be verified in polynomial time.

此敘述正確。

NP-complete 問題屬於 NP。對於一個候選解，可以在多項式時間內檢查它是否正確。

例如在 Hamiltonian Cycle 問題中，候選解是一條頂點排列形成的循環，可以檢查：

1. 是否每個頂點恰好出現一次。
2. 相鄰頂點之間是否存在邊。
3. 最後一個頂點是否能連回第一個頂點。

這些檢查都能在輸入大小的多項式時間內完成。

---

核心觀念

本題考查最小堆積（min-heap）的兩項性質：

1. 完全二元樹結構：新元素一律插入目前最底層、由左至右的第一個空位置。
2. 最小堆積性質：每個父節點的值必須小於或等於其子節點。若新插入的節點小於父節點，便向上調整（up-heap 或 bubble-up）。

以陣列表示堆積時，若索引從 $1$ 開始：

• 父節點索引：$\left\lfloor i/2 \right\rfloor$
• 左子節點索引：$2i$
• 右子節點索引：$2i+1$

題目規定根節點位於第 $1$ 層，因此：

• 索引 $1$：第 $1$ 層
• 索引 $2,3$：第 $2$ 層
• 索引 $4,5,6,7$：第 $3$ 層

解題方法

依序插入 $29,28,23,26,27$，每次插入後維持最小堆積性質。

插入 29

初始堆積：

$$[29]$$

樹狀結構：

29

插入 28

先放在下一個可用位置，即 29 的左子節點：

 29
 /
28

因為 $28<29$，兩者交換：

 28
 /
29

陣列表示為：

$$[28,29]$$

插入 23

先放在索引 $3$，即 28 的右子節點：

 28
 / \
29 23

因為 $23<28$，交換：

 23
 / \
29 28

陣列表示為：

$$[23,29,28]$$

插入 26

下一個位置為索引 $4$，是 29 的左子節點：

 23
 / \
 29 28
 /
26

先比較 26 與父節點 29：

$$26<29$$

因此交換：

 23
 / \
 26 28
 /
29

此時 26 的父節點是 23，而：

$$26>23$$

不需再向上調整。

陣列表示為：

$$[23,26,28,29]$$

插入 27

下一個位置為索引 $5$，是 26 的右子節點：

 23
 / \
 26 28
 / \
29 27

比較 27 與父節點 26：

$$27>26$$

已符合最小堆積性質，不需交換。

最終堆積為：

 23
 / \
 26 28
 / \
29 27

因此：

• 23 位於第 1 層
• 26、28 位於第 2 層
• 29、27 位於第 3 層
• 28 是 23 的右子節點
• 27 是 26 的右子節點

選項分析

核心觀念

本題考查 Bubble Sort（泡沫排序法） 的交換次數。

泡沫排序會反覆比較相鄰元素：

• 若前一個元素大於後一個元素，便交換兩者。
• 每一輪會將目前未排序部分的最大值移至最右側。
• 題目要求的是「swap（交換）操作」的次數，不是比較次數，也不是排序輪數。

---

解題方法：逐輪追蹤

原始序列：

$$[4,\ 8,\ 2,\ 5,\ 1]$$

第 1 輪

1. 比較 $4$ 與 $8$：$4<8$，不交換
   $[4,\ 8,\ 2,\ 5,\ 1]$

2. 比較 $8$ 與 $2$：$8>2$，交換 1 次
   $[4,\ 2,\ 8,\ 5,\ 1]$

3. 比較 $8$ 與 $5$：$8>5$，交換 1 次
   $[4,\ 2,\ 5,\ 8,\ 1]$

4. 比較 $8$ 與 $1$：$8>1$，交換 1 次
   $[4,\ 2,\ 5,\ 1,\ 8]$

第 1 輪交換次數：

$$3$$

第 2 輪

1. 比較 $4$ 與 $2$：$4>2$，交換 1 次
   $[2,\ 4,\ 5,\ 1,\ 8]$

2. 比較 $4$ 與 $5$：$4<5$，不交換

3. 比較 $5$ 與 $1$：$5>1$，交換 1 次
   $[2,\ 4,\ 1,\ 5,\ 8]$

第 2 輪交換次數：

$$2$$

第 3 輪

1. 比較 $2$ 與 $4$：$2<4$，不交換

2. 比較 $4$ 與 $1$：$4>1$，交換 1 次
   $[2,\ 1,\ 4,\ 5,\ 8]$

第 3 輪交換次數：

$$1$$

第 4 輪

1. 比較 $2$ 與 $1$：$2>1$，交換 1 次
   $[1,\ 2,\ 4,\ 5,\ 8]$

第 4 輪交換次數：

$$1$$

因此總交換次數為：

$$3+2+1+1=7$$

---

關鍵程式碼與逐步追蹤

典型的 Bubble Sort 程式碼如下：

核心觀念

本題考查 聯邦學習（Federated Learning, FL） 在醫療人工智慧中的意義。

傳統集中式機器學習會將各醫院或病人的資料集中到同一台伺服器，再進行模型訓練；聯邦學習則讓資料保留在原本的醫院、研究機構或裝置中，各參與端只利用本地資料訓練模型，之後回傳模型參數更新結果，由中央伺服器整合。

基本流程可表示如下：

$$\text{中央模型} \rightarrow \text{各醫療機構本地訓練} \rightarrow \text{回傳模型更新} \rightarrow \text{整合成新模型}$$

如此可以在不直接交換病歷、影像、基因資料等敏感資訊的情況下，讓模型學習多個資料來源的特徵。

醫療資料通常涉及病人隱私、個人識別資訊及法律規範，因此「不集中搬移原始病人資料，仍能共同訓練模型」是聯邦學習的重要價值。

---

解題方法

判斷本題的關鍵在於掌握聯邦學習的核心定義：

聯邦學習讓分散在不同位置的資料留在本地，各端共同訓練模型，只交換模型更新資訊，而非直接分享原始敏感資料。

因此，逐一檢查選項是否符合下列兩項特徵：

1. 資料是分散的，無須集中到同一處。
2. 可降低直接分享病人敏感資料的需求。

符合這兩項條件的選項即為正確答案。

---

選項分析

(A) It increases training speed by using only local datasets.

此選項錯誤。

聯邦學習確實會在各地使用本地資料訓練，但其主要目的不是單純提升訓練速度。聯邦學習需要處理：

• 多個裝置或醫療機構之間的通訊；
• 不同機構資料分布不一致；
• 模型更新的聚合；
• 網路延遲與設備運算能力差異；
• 隱私保護與安全機制。

因此，聯邦學習不一定比集中式訓練更快。選項把「使用本地資料」誤說成必然「增加訓練速度」，屬於錯誤因果關係。

(B) It enables AI models to learn from decentralized patient data without sharing sensitive information.

此選項正確。

聯邦學習能讓多家醫院分別使用本院病人資料訓練模型，原始資料不必離開各自的資料庫。中央伺服器主要接收模型參數或梯度更新，再將各端結果加以整合。

例如，三家醫院可分別以本院的醫療影像訓練同一個疾病分類模型：

核心觀念

本題考查圖論中的 Hamiltonian circuit（哈密頓迴路）、NP-complete 問題，以及其與 Traveling Salesperson Problem（TSP，旅行推銷員問題）的關係。

• Hamiltonian circuit：在圖中找出一條封閉路徑，使每個頂點恰好拜訪一次，最後回到起點。
• Hamiltonian circuit decision problem：判斷一個圖是否存在 Hamiltonian circuit。
• Complete graph（完全圖）：任意兩個不同頂點之間都有一條邊。
• Hamiltonian circuit 的重點是「每個頂點恰好一次」，不是「圖中的每條邊都走一次」。

---

解題方法

逐一判斷四個敘述：

1. 完全圖是否一定存在 Hamiltonian circuit？
2. Hamiltonian circuit decision problem 是否為 NP-complete？
3. Hamiltonian circuit problem 是否可視為 TSP 的特殊情況？
4. Hamiltonian circuit 是否要求每條邊都拜訪一次？

由於選項是敘述組合，必須先判定每一個敘述的正誤，再比對選項。

---

敘述 1：The graph has a Hamiltonian circuit if it is a complete graph.

此敘述在一般考試假設下為正確。

設完全圖有 $n$ 個頂點，且 $n \ge 3$。由於任意兩個頂點之間都有邊，因此可以任意排列頂點，例如：

$$v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow \cdots \rightarrow v_n \rightarrow v_1$$

其中每一步都有對應的邊，且每個頂點恰好出現一次，最後回到起點，因此形成 Hamiltonian circuit。

例如完全圖 $K_4$ 可形成：

$$v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_1$$

因此敘述 1 正確。

嚴格而言，若完全圖只有 $1$ 或 $2$ 個頂點，通常不符合標準 Hamiltonian circuit 的定義；但本題採用資訊科學教材中的通常假設，指的是具有足夠頂點數的完全圖。

---

敘述 2：The Hamiltonian circuit decision problem is NP-complete.

此敘述正確。

Hamiltonian circuit decision problem 可分成兩個部分：

1. 屬於 NP

若有人提供一條候選迴路，演算法可以在多項式時間內檢查：

• 是否從某個頂點出發並回到原點；
• 每一對相鄰頂點之間是否存在邊；
• 每個頂點是否恰好拜訪一次。

因此，候選解可以在多項式時間內驗證，故問題屬於 NP。

2. 為 NP-hard

Hamiltonian circuit decision problem 已知可由其他 NP-complete 問題在多項式時間內轉換而來，因此具有 NP-hard 性質。

綜合可得：

$$\text{Hamiltonian circuit decision problem} \in \mathrm{NP}$$

且

$$\text{Hamiltonian circuit decision problem} \text{ 是 NP-hard}$$

所以它是 NP-complete 問題。

因此敘述 2 正確。

---

敘述 3：The Hamiltonian circuit problem is a special case of the traveling salesperson problem.

依本題官方答案與命題慣例，此敘述判定為不正確。

兩者雖然都涉及「拜訪所有城市／頂點並返回起點」，但問題目標不同：

核心觀念

Database indexing（資料庫索引）是建立在資料表上的輔助資料結構，用來依照特定欄位快速定位資料列。索引通常儲存索引鍵值，以及對應資料位置的指標，常見實作包括：

• B-tree／B+ tree index：適合等值查詢、範圍查詢與排序。
• Hash index：適合等值查詢。
• Composite index（複合索引）：由多個欄位共同建立。

沒有索引時，資料庫可能必須逐筆掃描整張資料表，時間成本約為 $O(n)$。建立適當索引後，資料庫可透過索引快速縮小搜尋範圍；以平衡樹索引為例，查找平均可接近 $O(\log n)$，因此主要目的就是加速查詢執行。

解題方法

判斷資料庫索引的功能，應先抓住關鍵字 main purpose（主要目的）。

索引的核心作用是讓資料庫在執行 SELECT、WHERE、JOIN、ORDER BY 等操作時，能更快找到符合條件的資料，減少完整資料表掃描。因此正確敘述應與「提高查詢速度」直接相關。

題目選項中，只有：

To speed up query execution

直接描述索引的主要用途，所以選擇 (D)。

選項分析

(A) To store metadata

錯誤。Metadata 是描述資料結構的資料，例如資料表名稱、欄位名稱、資料型別、索引名稱與建立時間等。資料庫系統確實會保存索引相關的 metadata，但「儲存 metadata」不是建立索引的主要目的。

索引本身主要儲存的是：

1. 被索引欄位的值或索引鍵。
2. 對應資料列的位置、指標或資料頁資訊。
3. 維持搜尋結構所需的節點資訊。

因此，索引不是以儲存 metadata 為主要功能。

(B) To increase disk usage

錯誤。索引通常會額外佔用磁碟空間，這是建立索引的成本之一，但增加磁碟使用量不是目的，而是副作用。

索引的整體取捨如下：

核心觀念

本題考查 C++ STL 常用容器的：

• 是否允許重複鍵值
• 查找時間複雜度
• 插入操作的時間複雜度
• 元素排列規則
• 記憶體配置方式

常見容器比較如下：

容器	內部結構	鍵值／元素特性	查找複雜度
std::map	平衡搜尋樹，通常為紅黑樹	鍵值唯一且排序	$O(\log n)$
std::unordered_map	Hash table	鍵值唯一、不保證排序	平均 $O(1)$，最壞 $O(n)$
std::vector	連續記憶體陣列	支援隨機存取	索引存取 $O(1)$
std::set	平衡搜尋樹	元素唯一且排序	$O(\log n)$
std::list	雙向鏈結串列	節點分散配置	查找 $O(n)$

解題方法

逐項比對各容器的標準定義與複雜度：

1. map 是否允許重複鍵值。
2. unordered_map 與 map 的查找複雜度。
3. vector 在中間插入時是否需要搬移元素。
4. set 是否保存插入順序。
5. list 與 vector 的記憶體額外負擔。

其中 unordered_map 使用雜湊函數將鍵值映射至桶（bucket）。在雜湊分布良好時，查找平均為：

$$T_{\text{unordered\_map}} = O(1)$$

map 則以平衡樹維持排序，每次查找沿樹高進行：

$$T_{\text{map}} = O(\log n)$$

因此在大型資料集合中，依照題目的一般比較前提，unordered_map 的查找速度通常比 map 快。

選項分析

(A) std::map allows duplicate keys.

錯誤。

std::map 的每個鍵值必須唯一。例如：

std::map<int, std::string> m;
m[1] = "A";
m[1] = "B";

第二次使用鍵值 1 時，不會建立第二筆資料，而是修改原本鍵值 1 所對應的內容。

若需要同一鍵值對應多筆資料，應使用：

std::multimap<int, std::string> mm;

因此 std::map 不允許重複鍵值。

---

(B) std::unordered_map has faster lookups than std::map for large datasets.

正確，為本題答案。

std::unordered_map 使用雜湊表，平均查找複雜度為 $O(1)$；std::map 使用平衡搜尋樹，查找複雜度為 $O(\log n)$。

當資料量 $n$ 很大時：

$$O(1) < O(\log n)$$

所以在一般雜湊分布良好、雜湊碰撞不嚴重的前提下，unordered_map 的查找通常較快。

範例：

std::unordered_map<int, int> um;
std::map<int, int> om;

um[100] = 5;
om[100] = 5;

兩者都能依鍵值查找，但底層機制不同：

• unordered_map：計算雜湊值，再到對應桶中查找。
• map：由樹根逐層比較鍵值。

核心觀念

本題考查神經網路中的 Backpropagation（反向傳播）。

神經網路訓練的目標，是調整各層的權重，使損失函數 $L$ 降低。訓練流程通常包含：

1. Forward Propagation（前向傳播）：輸入資料經過各層計算，得到預測值。
2. 計算損失函數：比較預測值與真實答案。
3. Backpropagation（反向傳播）：利用微分的鏈鎖律，由輸出層往輸入層計算各權重對損失函數的梯度。
4. 更新權重：配合梯度下降法調整權重。

權重更新公式為：

$$w_{\text{new}}=w_{\text{old}}-\eta\frac{\partial L}{\partial w}$$

其中：

• $w$：神經網路中的權重
• $L$：損失函數
• $\frac{\partial L}{\partial w}$：損失函數對權重的梯度
• $\eta$：學習率

解題方法

判斷 Backpropagation 的關鍵，在於掌握兩個重點：

• 使用 chain rule（鏈鎖律） 計算梯度。
• 計算出的梯度用來更新神經網路權重。

假設單一神經元的計算為：

$$z=wx+b$$ $$\hat{y}=f(z)$$

損失函數為：

$$L=L(\hat{y},y)$$

根據鏈鎖律，權重的梯度可寫成：

$$\frac{\partial L}{\partial w} = \frac{\partial L}{\partial \hat{y}} \cdot \frac{\partial \hat{y}}{\partial z} \cdot \frac{\partial z}{\partial w}$$

由於：

$$\frac{\partial z}{\partial w}=x$$

因此可以逐層求得梯度，再使用梯度下降法更新權重。這正是反向傳播的核心機制。

因此，最完整且正確的敘述是：

Backpropagation uses the chain rule to compute gradients and update weights.

選項分析

(A) Backpropagation is a data preprocessing technique that normalizes inputs before training.

錯誤。

資料正規化、標準化與特徵縮放屬於 data preprocessing（資料前處理），例如將輸入調整至 $[0,1]$，或轉換為平均值為 $0$、標準差為 $1$ 的形式。