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

核心觀念

本題考查**對稱式加密（symmetric encryption）與非對稱式加密（asymmetric encryption）**的分類。

1. 對稱式加密

對稱式加密使用同一把秘密金鑰進行加密與解密：

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

其中：

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

加密者與解密者必須事先安全地共享金鑰。其特點是速度快，適合大量資料加密，但金鑰配送與管理較困難。

2. 非對稱式加密

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

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

公開金鑰可公開，私密金鑰必須保密。以保密傳輸為例：

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

這兩把金鑰在數學上相關，但不能視為同一把共享秘密金鑰。RSA 即屬於非對稱式加密演算法。

---

解題方法

判斷各選項所屬的加密類型即可：

1. DES：對稱式分組加密。
2. AES：對稱式分組加密。
3. Caesar Cipher：使用同一個位移量加密與解密，屬於對稱式加密。
4. RSA：使用公開金鑰與私密金鑰，屬於非對稱式加密。
5. Playfair Cipher：使用同一個密鑰方格進行加密與解密，屬於對稱式加密。

因此，不是對稱式演算法的是 RSA。

---

選項分析

(A) DES

DES（Data Encryption Standard）是對稱式分組加密演算法。

DES 將資料切成固定大小的區塊，使用同一把秘密金鑰進行加密與解密。其核心架構為 Feistel network，標準金鑰長度為 56 位元。

因此，DES 是對稱式演算法，選項正確但不是本題答案。

---

(B) AES

AES（Advanced Encryption Standard）是對稱式分組加密演算法。

AES 使用相同的秘密金鑰進行加密與解密，支援 128、192、256 位元金鑰長度，資料區塊大小固定為 128 位元。

因此，AES 是對稱式演算法，選項正確但不是本題答案。

---

(C) Caesar Cipher

Caesar Cipher（凱薩密碼）是古典的對稱式替換加密法。

假設英文字母以 $0$ 到 $25$ 編號，加密位移量為 $k$，則：

$$C=(P+k)\bmod 26$$

解密時使用相反方向的位移：

$$P=(C-k)\bmod 26$$

加密與解密所使用的是同一個位移密鑰 $k$，因此屬於對稱式加密。

核心觀念

本題考「ping 工具所使用的網路協定」。

ping 用來測試目的主機是否可達，以及估算封包往返時間。其運作機制是：

1. 本機送出 ICMP Echo Request。
2. 目的主機收到後回傳 ICMP Echo Reply。
3. 本機根據回覆封包計算往返時間（Round-Trip Time, RTT），並判斷封包是否遺失。

因此，ping 使用的是 ICMP（Internet Control Message Protocol，網際網路控制訊息協定）。

ICMP 位於網路層，通常搭配 IP 使用；它不像 TCP 或 UDP 一樣透過連接埠（port）傳輸應用程式資料。

解題方法

看到題目問「Ping implemented by which protocol」，直接聯想到 ICMP 的兩種訊息：

• Echo Request：回應請求
• Echo Reply：回應封包

其基本流程可表示為：

$$\text{主機 A} \xrightarrow{\text{ICMP Echo Request}} \text{主機 B}$$ $$\text{主機 B} \xrightarrow{\text{ICMP Echo Reply}} \text{主機 A}$$

若主機 B 成功回覆，主機 A 便可確認目的地具有網路可達性，並計算：

$$\text{RTT} = t_{\text{收到回覆}} - t_{\text{送出請求}}$$

所以正確協定為 ICMP。

選項分析

(A) IGMP

IGMP（Internet Group Management Protocol，網際網路群組管理協定）用於管理主機與 IPv4 多播群組之間的關係，例如：

• 主機加入多播群組
• 主機離開多播群組
• 路由器查詢群組成員

IGMP 的用途是多播群組管理，不是測試單一主機是否可達，因此錯誤。

核心觀念

本題考查 平均 CPI（Average Cycles Per Instruction） 的計算。

CPI 是每一類指令平均需要的時脈週期數。由於不同指令類別的 CPI 不同，平均 CPI 必須按照各類別的實際執行次數加權平均：

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

其中：

$$\text{總時脈週期數} = \sum_i \left(\text{第 }i\text{ 類指令數}\times\text{第 }i\text{ 類 CPI}\right)$$

題目給出的 $100\text{ MHz}$ 時脈率，是計算程式執行時間時使用的資訊；計算平均 CPI 時不需要使用。

解題方法

各類指令的執行資訊如下：

指令類別	CPI	執行次數	所需時脈週期
A	1	10	$10\times1=10$
B	3	1	$1\times3=3$
C	2	1	$1\times2=2$

因此，總指令數為：

$$10+1+1=12$$

總時脈週期數為：

$$10+3+2=15$$

平均 CPI 為：

$$\text{平均 CPI} = \frac{15}{12} = 1.25$$

所以正確選項為 (C)。

選項分析

• (A) 4：錯誤。
  $4$ 並非依據加權平均公式計算出的平均 CPI，也不是各類 CPI 的正確合併結果。

核心觀念

本題考查 C 語言基本資料型態的「可表示最大值」以及整數型態與浮點型態的差異。

主要比較：

• int：有號整數
• signed int：與 int 相同
• unsigned int：無號整數
• long：長整數，通常為有號整數
• double：雙精度浮點數，可表示非常大的數值

在一般 C 語言實作與考試常見環境中：

• 整數型態的最大值通常落在 $10^9$ 或 $10^{18}$ 的量級。
• double 的最大有限值約為 $1.8 \times 10^{308}$。

因此，double 的最大可表示值遠大於其他選項。

---

解題方法

先區分資料型態：

1. 整數型態

對一個使用 $n$ 位元儲存的有號整數，通常有 $1$ 位元作為符號位元，因此最大值為：

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

對相同位元數的無號整數，所有位元皆用於表示數值，最大值為：

$$2^n-1$$

所以在位元數相同時：

$$\text{unsigned int} > \text{int} = \text{signed int}$$

2. 浮點型態

double 通常採用 IEEE 754 雙精度格式，使用：

• 1 位元符號位元
• 11 位元指數欄位
• 52 位元有效數字欄位

其最大有限值約為：

$$1.7976931348623157 \times 10^{308}$$

這個數值遠超過一般整數型態的最大值。

例如常見的 64 位元 long 最大值為：

$$2^{63}-1 = 9,223,372,036,854,775,807 \approx 9.22 \times 10^{18}$$

比較數量級：

$$10^{308} \gg 10^{18}$$

所以最大值最大的是 double。

---

選項分析

(A) int

int 是有號整數型態。

若 int 使用 32 位元，最大值為：

$$2^{31}-1=2,147,483,647$$

即約為：

$$2.1 \times 10^9$$

小於 double 的最大值，因此錯誤。

---

(B) unsigned int

unsigned int 是無號整數型態。若使用 32 位元，最大值為：

$$2^{32}-1=4,294,967,295$$

雖然它比同樣位元數的 int 大，但仍只有約 $4.3 \times 10^9$，遠小於 double 約 $1.8 \times 10^{308}$ 的

核心觀念

機器學習依訓練資料是否具有標籤，可分為：

• 監督式學習（Supervised Learning）：訓練資料包含輸入資料與正確答案標籤，模型學習輸入與輸出之間的關係，常見任務為分類與迴歸。
• 非監督式學習（Unsupervised Learning）：訓練資料沒有標籤，模型自行從資料中找出群組、結構或分布特徵，常見任務為分群與降維。

本題問的是「從未標記資料中學習模式」的技術，因此應判斷各選項是否屬於非監督式學習。

---

解題方法

逐一判斷各演算法的訓練方式：

1. 是否需要事先提供正確答案標籤？
2. 主要用途是分類、迴歸，還是分群？
3. 是否由模型自行發現資料中的群組結構？

其中，若演算法將資料分成數個群組，且不需要事先知道每筆資料所屬類別，通常就是非監督式學習。

---

選項分析

(A) Decision tree

Decision tree（決策樹）通常是監督式學習方法。

在分類問題中，決策樹利用具有標籤的訓練資料，依據特徵切分資料。例如，根據體溫、咳嗽與年齡等特徵，判斷病人是否感染某種疾病。每筆訓練資料都必須有已知答案，模型才能學習切分規則。

決策樹也可用於迴歸問題，同樣需要已知的目標值。因此本選項不符合題目所問的非監督式學習。

---

(B) K-means clustering

K-means clustering（K 平均分群）是典型的非監督式學習方法，故為正確答案。

K-means 不需要資料標籤，只需指定欲分成的群數 $K$。演算法會依據資料點之間的距離，自動將相似資料分到同一群。

基本流程如下：

1. 指定群數 $K$。
2. 隨機選取 $K$ 個初始群中心。
3. 將每筆資料分配至距離最近的群中心。
4. 分別計算每一群資料的平均值，更新群中心。
5. 重複步驟 3 與步驟 4，直到群組分配穩定或群中心變化很小。

其最佳化目標通常是最小化群內平方距離：

$$J=\sum_{i=1}^{K}\sum_{x\in C_i}\|x-\mu_i\|^2$$

其中：

• $K$：群組數量
• $C_i$：第 $i$ 群的資料集合
• $\mu_i$：第 $i$ 群的中心
• $\|x-\mu_i\|^2$：資料點與群中心之間的平方距離

因為訓練資料不需要預先提供類別標籤，而是由演算法自行找出資料群組，所以 K-means 屬於非監督式學習。

核心觀念

本題考「前序表示法」（prefix expression，也稱 Polish notation）。

前序表示法的規則是：

• 運算子寫在運算元之前。
• 本題所有運算子皆為二元運算子。
• 每個運算子必須搭配其後的兩個完整子運算式。
• 符號 $\times$ 表示乘法，符號 $+$ 表示加法。

題目中的前序式為：

$$+ \quad + \quad 9 \quad \times \quad 8 \quad 7 \quad \times \quad + \quad \times \quad 6 \quad 5 \quad 4 \quad 3$$

---

解題方法

由最外層的第一個 $+$ 開始解析：

$$+ \; [\text{左子式}] \; [\text{右子式}]$$

左子式從第二個 $+$ 開始：

$$+ \quad 9 \quad \times \quad 8 \quad 7$$

因此：

$$9+\left(8\times 7\right) =9+56 =65$$

右子式為：

$$\times \quad + \quad \times \quad 6 \quad 5 \quad 4 \quad 3$$

先解析其中的加法子式：

$$+ \quad \times \quad 6 \quad 5 \quad 4$$

其結果為：

$$(6\times 5)+4 =30+4 =34$$

再乘以 $3$：

$$34\times 3=102$$

最後計算最外層加法：

$$65+102=167$$

所以完整的中序表示為：

$$\left[9+(8\times 7)\right] + \left[\left((6\times 5)+4\right)\times 3\right]$$

---

逐步追蹤（Trace）

也可以由右至左掃描前序式，遇到運算元就放入堆疊，遇到運算子就取出最靠近的兩個值計算：

掃描內容	動作	堆疊結果
$3$	放入	$[3]$
$4$	放入	$[3,4]$
$5$	放入	$[3,4,5]$
$6$	放入	$[3,4,5,6]$
$\times$	$6\times5=30$	$[3,4,30]$
$+$	$30+4=34$	$[3,34]$
$\times$	$34\times3=102$	$[102]$

核心觀念

本題考查電腦儲存階層（memory hierarchy）中，各類記憶體或儲存裝置的存取速度與反應時間。

一般而言，距離 CPU 越近、容量越小、成本越高的儲存元件，反應時間越短。由快至慢可排列為：

$$\text{Processor registers} \;>\; \text{CPU cache} \;>\; \text{Main memory} \;>\; \text{Solid-state drive} \;>\; \text{Floppy disk drive}$$

此處的「反應時間」可理解為 CPU 或系統提出資料需求後，元件開始提供資料所需的時間，也就是存取延遲（access latency）。

解題方法

判斷此題時，依據各元件與 CPU 的距離及其硬體功能進行比較：

1. Processor registers 位於 CPU 內部，直接供算術邏輯單元與控制單元使用。
2. CPU cache 位於 CPU 內部或緊鄰 CPU，但仍須經由快取控制機制搜尋資料。
3. Main memory 通常指 RAM，位於 CPU 外部，需透過記憶體匯流排存取。
4. Solid-state drive 使用非揮發性快閃記憶體，需經由儲存控制器與輸入輸出介面存取。
5. Floppy disk drive 使用機械式磁碟與讀寫磁頭，機械移動造成很大的延遲。

因此，反應時間最短的是直接位於 CPU 內部的處理器暫存器。

選項分析

(A) Main memory

Main memory 主要是 RAM，用於存放目前執行中的程式與資料。它的速度比 SSD 與軟碟快，但位於 CPU 外部，CPU 必須透過記憶體控制器與匯流排存取，因此反應時間長於 CPU 內部的暫存器。

所以此選項錯誤。

(B) CPU cache

CPU cache 使用速度較快的記憶體技術，存放 CPU 最近使用或預測即將使用的資料，以減少存取主記憶體的次數。

雖然快取比主記憶體快，但 CPU 仍須依照快取階層進行標籤比對與資料搜尋。處理器暫存器直接位於 CPU 的運算路徑中，存取時間通常更短。

所以此選項錯誤。

(C) Processor registers

核心觀念

本題考查 C 語言中：

1. rand 產生的亂數範圍。
2. %（取餘數）運算子的結果範圍。
3. 迴圈如何將亂數依序存入陣列。

在 C 語言中，rand 會產生介於 $0$ 與 RAND_MAX 之間的非負整數：

$$0 \leq \texttt{rand} \leq \texttt{RAND\_MAX}$$

本題的指定運算為：

rand % 100

對任何非負整數取 $100$ 的餘數，結果只能是：

$$0,1,2,\ldots,99$$

因此，myList[i] 的亂數範圍為 $0$ 到 $99$。

---

解題方法

令：

$$r=\texttt{rand}$$

則：

r % 100

代表 $r$ 除以 $100$ 後的餘數。根據餘數定義：

$$0 \leq r \bmod 100 < 100$$

因為餘數必須小於除數 $100$，所以：

$$0 \leq \texttt{rand} \% 100 \leq 99$$

程式會將這些數值依序指定給：

myList[0], myList[1], ..., myList[ARRAY_SIZE - 1]

因此陣列中的每個元素都會被初始化為 $0$ 到 $99$ 之間的整數。

---

程式逐步追蹤（Trace）

假設某次執行時，rand 依序產生下列數值：

rand 的結果	計算	myList[i] 的值
135	$135 \bmod 100=35$	35
802	$802 \bmod 100=2$	2
99	$99 \bmod 100=99$	99
1000	$1000 \bmod 100=0$	0

可見結果包含 $0$，也包含 $99$，但不會出現 $100$。

程式中的迴圈：

for (int i = 0; i < ARRAY_SIZE; i++)
{
 myList[i] = rand % 100;
}

其執行流程為：

1. i=0，將一個 $0\sim99$ 的亂數存入 myList[0]。
2. i=1，將一個 $0\sim99$ 的亂數存入 myList[1]。
3. 持續執行至 i=ARRAY_SIZE-1。

核心觀念

本題考查「多執行緒行程（multithreaded process）」的記憶體配置與資源共享方式。

同一個 process 內可以包含多個 threads。這些 threads 通常共享 process 的資源，但每個 thread 仍須保有自己的執行狀態，才能獨立執行。

典型區分如下：

資源或區段	同一 process 內的 threads 是否共享
Code section	共享
Data section	共享
Heap	通常共享
Stack	不共享，各 thread 擁有自己的 stack
Registers	不共享，各 thread 擁有自己的 registers
Program counter	不共享，各 thread 擁有自己的 program counter

---

解題方法

判斷本題可採用「process 共用資源、thread 個別執行狀態」的切入方式。

同一個 process 中的 threads：

1. 共同執行同一份程式，因此共享 code section。
2. 各自可能執行到不同指令，因此必須擁有自己的 program counter。
3. 各自需要保存不同的暫存資料，因此必須擁有自己的 registers。
4. 各自擁有函式呼叫與區域變數所需的執行堆疊，因此通常各自擁有自己的 stack。
5. 動態配置的記憶體通常位於 heap，同一 process 內的 threads 可以共同存取。

依本題官方公布答案，命題者欲測驗的標準答案是「threads 共享同一份程式碼」，因此選擇 (A) code。

---

選項分析

(A) code：正確

Code section 儲存程式的指令內容。同一個 process 中的多個 threads 通常執行同一份程式碼，因此共享相同的 code section。

例如，一個 process 中有多個 threads 執行同一個函式，各 thread 可以位於該函式的不同執行位置，但所使用的指令仍來自同一份 code。

因此依官方答案，(A) 為正確選項。

---

(B) registers：錯誤

Registers 用來保存 thread 當下執行所需的資料，例如：

• 運算中的暫存值
• 函式參數
• 暫存器位址
• 執行狀態資訊

每個 thread 必須有自己的 registers 狀態。若所有 threads 共用同一組 registers，thread 切換時就無法保存各自的執行進度。

核心觀念

本題考查：

• C 語言的整數減法
• 位元運算 &
• 有號整數右移 >>
• 二補數表示法
• 位元技巧判斷兩數大小

在一般考試所採用的 32 位元整數、二補數系統中：

• 正整數右移 31 位後為 $0$
• x & 0 的結果一定為 $0$

---

解題方法與逐步追蹤

題目函式為：

int f(int a, int b)
{
 return a - ((a - b) & ((a - b) >> 31));
}

代入 $a=12$、$b=-20$。

先計算：

$$a-b=12-(-20)=32$$

因此原式變為：

return 12 - (32 & (32 >> 31));

將 $32$ 寫成二進位：

$$32=(00000000\ 00000000\ 00000000\ 00100000)_2$$

因為 $32$ 是正數，右移 31 位後：

$$32>>31=0$$

所以：

$$32\ \&\ 0=0$$

最後：

$$f(12,-20)=12-0=12$$

因此正確選項為：

$$\boxed{\text{(D) }12}$$

---

這段程式的位元意義

令：

$$d=a-b$$

在 32 位元二補數系統中：

• 若 $d\geq 0$，則 $d>>31=0$
• 若 $d<0$，則 $d>>31=-1$，其二進位通常為全 $1$

因此：

• $d\geq 0$ 時，$d\ \&\ 0=0$，函式回傳 $a$
• $d<0$ 時，$d\ \&\ (-1)=d$，函式回傳 $a-d=b$

本題中：

$$12>-20$$

因此函式回傳較大的數 $12$。這也是官方答案為 D 的原因。

---

選項分析

• (A) -32：錯誤

核心觀念

本題考查 C 語言的：

• 後置遞增運算子 a++、b++
• 前置遞增運算子 ++a、++b
• 遞增運算後，變數值如何改變
• 運算式中各項的計算與累加

定義如下：

• a++：先取出 a 的原值參與運算，再將 a 加 $1$。
• ++a：先將 a 加 $1$，再以新值參與運算。

依本題官方答案採用的命題慣例，將同一行的運算項依由左至右順序追蹤。

---

解題方法與逐步追蹤

初始值為：

$$a=10,\qquad b=5$$

一、計算 $x$

程式碼為：

x = (a++) + (a++) + (b++);

依序計算：

運算項	參與運算的值	運算後變數值
第一個 a++	$10$	$a=11$
第二個 a++	$11$	$a=12$
b++	$5$	$b=6$

因此：

$$x=10+11+5=26$$

執行完第一行後：

$$a=12,\qquad b=6,\qquad x=26$$

二、計算 $y$

程式碼為：

y = (++a) + (++a) + (++b);

此時從 $a=12$、$b=6$ 開始。

依序計算：

運算項	先遞增後取值	運算後變數值
第一個 ++a	$a=13$	$a=13$
第二個 ++a	$a=14$	$a=14$
++b	$b=7$	$b=7$

因此：

$$y=13+14+7=34$$

最後結果為：

$$x=26,\qquad y=34$$

---

核心觀念

本題考查 SQL 的「邏輯查詢處理順序」。SQL 語句的書寫順序，與資料庫處理查詢時的邏輯順序不同。

題目列出的各階段，在一般考試規範下可排列為：

$$\text{FROM} \rightarrow \text{WHERE} \rightarrow \text{GROUP BY} \rightarrow \text{SELECT [DISTINCT]} \rightarrow \text{ORDER BY}$$

各階段功能如下：

1. FROM：決定資料來源，建立初步資料集合。
2. WHERE：篩選資料列，移除不符合條件的 records。
3. GROUP BY：依指定欄位分組，形成群組。
4. SELECT [DISTINCT]：決定輸出哪些欄位；DISTINCT 負責去除重複結果。
5. ORDER BY：將最後產生的結果排序。

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

---

解題方法

判斷 SQL 邏輯處理順序時，可依「資料由來源逐步變成最後輸出」的流程思考：

第一步：先決定資料從哪裡來

必須先執行 FROM，才能知道要查詢哪些資料表。

FROM Student

此時資料庫先取得 Student 資料表的資料。

第二步：篩選資料列

接著執行 WHERE，只保留符合條件的資料。

WHERE score >= 60

此條件會先排除不及格資料，因此後續分組只針對篩選後的資料進行。

第三步：進行分組

若查詢包含 GROUP BY，資料會依指定欄位分成不同群組。

GROUP BY department

例如依系所分組後，才能計算各系所的平均成績、筆數或總和。

第四步：決定輸出欄位

SELECT 負責指定最後要顯示的欄位或運算結果。

SELECT department, AVG(score)

此時才形成查詢結果的欄位內容。若使用 DISTINCT，還會去除重複的輸出列。

第五步：排序最後結果

ORDER BY 通常作用在已經產生的結果上。

ORDER BY AVG(score) DESC

因此排序位於最後。

綜合以上流程：

$$\boxed{\text{FROM} \rightarrow \text{WHERE} \rightarrow \text{GROUP BY} \rightarrow \text{SELECT [DISTINCT]} \rightarrow \text{ORDER BY}}$$

對應選項為 (B)。

---

範例說明

考慮以下 SQL：

SELECT department, AVG(score) AS average_score
FROM Student
WHERE score >= 60
GROUP BY department
ORDER BY average_score DESC;

其邏輯處理流程如下：

1. 從 Student 資料表取得資料。
2. 保留 score >= 60 的資料列。
3. 依 department 分組。
4. 對每組計算 AVG(score)，並輸出 department 與平均分數。
5. 按照 average_score 由大到小排序。

若將 SELECT 放在 FROM 之前理解，便無法正確說明資料來源、篩選與分組的先後關係。

---

選項分析

(A) SELECT, WHERE, GROUP BY, FROM, ORDER BY

錯誤。

核心觀念

本題考查二元樹的前序走訪（pre-order traversal）。

前序走訪順序固定為：

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

每個節點都依照「先訪問自己，再完整走訪左子樹，最後走訪右子樹」的規則處理。

解題方法

依圖可讀出二元樹結構：

• 根節點為 $43$
• $43$ 的左子樹根為 $12$，右子樹根為 $99$
• $12$ 的左子節點為 $5$，右子節點為 $36$
• $5$ 的右子節點為 $7$
• $36$ 的左、右子節點分別為 $28$、$40$
• $99$ 的左子節點為 $81$
• $81$ 的左、右子節點分別為 $49$、$96$
• $49$ 的右子節點為 $50$
• $50$ 的右子節點為 $79$
• $96$ 的左子節點為 $86$

依前序走訪逐步排列：

1. 先訪問根節點：$43$
2. 走訪 $43$ 的左子樹：

• $12$
• $12$ 的左子樹：$5 \rightarrow 7$
• $12$ 的右子樹：$36 \rightarrow 28 \rightarrow 40$

3. 走訪 $43$ 的右子樹：

• $99$
• $99$ 的左子樹：$81$
• $81$ 的左子樹：$49 \rightarrow 50 \rightarrow 79$
• $81$ 的右子樹：$96 \rightarrow 86$

因此前序走訪結果為：

核心觀念

RSA 使用兩個質數 $p,q$ 建立：

$$n=pq$$

並計算歐拉函數：

$$\varphi(n)=(p-1)(q-1)$$

公開金鑰指數 $e$ 與私密金鑰指數 $d$ 必須滿足：

$$ed\equiv 1\pmod{\varphi(n)}$$

本題給定：

$$p=3,\quad q=7,\quad d=23$$

要求公開金鑰中的指數 $e$。

解題方法

先計算模數與歐拉函數：

$$n=3\times 7=21$$ $$\varphi(n)=(3-1)(7-1)=2\times6=12$$

因此 $e$ 必須滿足：

$$23e\equiv1\pmod{12}$$

因為：

$$23\equiv11\pmod{12}$$

所以改寫為：

$$11e\equiv1\pmod{12}$$

觀察選項中的 $e=11$：

$$11\times11=121$$

而：

$$121=12\times10+1$$

因此：

$$121\equiv1\pmod{12}$$

符合 RSA 的互為模反元素條件，所以：

$$e=11$$

嚴格而言，RSA 公開金鑰是 $(e,n)$，本題選項只列出公開金鑰指數，因此公開金鑰為：

$$(e,n)=(11,21)$$

選項分析

• (A) 3：錯誤

$23\times3=69$

$69\equiv9\pmod{12}$

核心觀念

本題考查 C 語言的巢狀 for 迴圈，以及迴圈條件的判斷方式。

外層迴圈：

for (i = 1; i < 3; i++)

因此 $i$ 依序取 $1、2$。

內層迴圈：

for (j = 1; j < i * 2; j++)
 x += 3;

在每一個固定的 $i$ 值下，$j$ 都會從 $1$ 開始，持續執行到 $j < 2i$ 不成立為止。每執行一次內層迴圈，$x$ 增加 $3$。

---

解題方法：逐步追蹤

初始值為：

$$x=5$$

當 $i=1$

內層條件為：

$$j < i \times 2 = 1 \times 2 = 2$$

此時 $j$ 的執行狀況如下：

$j$	條件 $j<2$	執行結果
$1$	成立	$x=5+3=8$
$2$	不成立	離開內層迴圈

因此，$i=1$ 時，內層迴圈執行 $1$ 次。

當 $i=2$

內層條件為：

$$j < i \times 2 = 2 \times 2 = 4$$

此時 $j$ 的執行狀況如下：

$j$	條件 $j<4$	執行結果
$1$	成立	$x=8+3=11$
$2$	成立	$x=11+3=14$
$3$	成立	$x=14+3=17$
$4$	不成立	離開內層迴圈

因此，$i=2$ 時，內層迴圈執行 $3$ 次。

總共執行次數為：

$$1+3=4\text{ 次}$$

所以：

$$x=5+4\times 3=17$$

關鍵程式碼的執行流程可簡寫為：

核心觀念

本題考的是「矩陣鏈乘法最佳化」（Matrix Chain Multiplication）。

矩陣乘法具有結合律：

$$(AB)C=A(BC)$$

但不同括號化方式，所需的「純量乘法次數」不同。若矩陣 $X$ 為 $p\times q$、矩陣 $Y$ 為 $q\times r$，則計算 $XY$ 需要：

$$pqr$$

次純量乘法，結果矩陣大小為 $p\times r$。

本題矩陣大小如下：

$$A_{2\times3},\quad B_{3\times7},\quad C_{7\times2},\quad D_{2\times9},\quad E_{9\times4}$$

因此維度序列為：

$$2,3,7,2,9,4$$

---

解題方法：動態規劃

令 $m[i,j]$ 表示從第 $i$ 個矩陣乘到第 $j$ 個矩陣所需的最少純量乘法次數。

若最後一次分割在第 $k$ 個矩陣之後，則：

$$m[i,j] = \min_{i\le k<j} \left\{ m[i,k]+m[k+1,j]+p_{i-1}p_kp_j \right\}$$

其中 $p=(2,3,7,2,9,4)$。

第一層：兩個矩陣相乘

$$m[1,2]=2\times3\times7=42$$ $$m[2,3]=3\times7\times2=42$$ $$m[3,4]=7\times2\times9=126$$ $$m[4,5]=2\times9\times4=72$$

第二層：三個矩陣

對 $ABC$：

$$(AB)C: 42+2\times7\times2=70$$ $$A(BC): 42+2\times3\times2=54$$

所以：

$$m[1,3]=54$$

對 $BCD$：

$$(BC)D:42+3\times2\times9=96$$ $$B(CD):126+3\times7\times9=315$$

所以：

$$m[2,4]=96$$

對 $CDE$：

$$(CD)E:126+7\times9\times4=378$$ $$C(DE):72+7\times2\times4=128$$

所以：

$$m[3,5]=128$$

第三層：四個矩陣

對 $ABCD$：

$$A(BCD):0+96+2\times3\times9=150$$ $$(AB)(CD):42+126+2\times7\times9=294$$ $$(ABC)D:54+0+2\times2\times9=90$$

此處需注意括號化成本應為：

$$(ABC)D=54+2\times2\times9=90$$

所以：

$$m[1,4]=90$$

對 $BCDE$：

$$B(CDE):128+3\times7\times4=212$$ $$(BC)(DE):42+72+3\times2\times4=138$$ $$(BCD)E:96+3\times9\times4=204$$

所以：

$$m[2,5]=138$$

第四層：五個矩陣

計算 $ABCDE$ 的四種分割方式：

1. $A(BCDE)$

$$0+138+2\times3\times4=162$$

2. $(AB)(CDE)$

$$42+128+2\times7\times4=226$$

3. $(ABC)(DE)$

$$54+72+2\times2\times4=142$$

4. $(ABCD)E$

$$90+0+2\times9\times4=162$$

核心觀念

本題考查作業系統的 Shortest-Job-First（SJF，最短工作優先）排程演算法。

SJF 的規則是：CPU 每次從已到達、尚未執行的程序中，選擇 Burst time 最短者 執行。本題所有程序皆在時間 $0$ 到達，因此一開始即可比較五個程序的 Burst time。

本題採用非搶先式 SJF，因為題目未提及程序執行期間會被中斷。非搶先式 SJF 一旦選定程序，就會讓該程序執行完畢。

各程序的周轉時間定義為：

$$\text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time}$$

由於所有程序的到達時間皆為 $0$，所以：

$$\text{Turnaround Time} = \text{Completion Time}$$

Priority 欄位不是 SJF 的判斷依據，因此本題不使用 Priority 排序。

解題方法

1. 依 Burst time 排列執行順序

各程序資料如下：

Process	Burst time	Arrival time
P1	10	0
P2	1	0
P3	2	0
P4	1	0
P5	5	0

依 Burst time 由小到大排序：

$$P2(1) \rightarrow P4(1) \rightarrow P3(2) \rightarrow P5(5) \rightarrow P1(10)$$

P2 與 P4 的 Burst time 同為 $1$，因此依題目給定的到達順序，P2 先於 P4。

2. 繪製甘特圖

$$0 \quad\ \ 1 \quad\ \ 2 \quad\ \ 4 \quad\ \ 9 \quad\ \ 19$$ $$\boxed{P2}\ |\ \boxed{P4}\ |\ \boxed{P3}\ |\ \boxed{P5}\ |\ \boxed{P1}$$

各程序的完成時間如下：

Process	Burst time	執行區間	Completion time	Turnaround time
P2	1	$0 \sim 1$	1	$1-0=1$
P4	1	$1 \sim 2$	2	$2-0=2$
P3	2	$2 \sim 4$	4	$4-0=4$
P5	5	$4 \sim 9$	9	$9-0=9$

核心觀念

本題考查網路位址轉換（NAT, Network Address Translation），更精確地說，是 NAT 中的連接埠位址轉換（PAT, Port Address Translation），也常稱為 NAT overload。

內部網路使用私有 IP 位址，例如：

• $10.0.0.0/24$
• 可用位址範圍通常為 $10.0.0.1$ 至 $10.0.0.254$

這些私有 IP 位址不能直接在公 Internet 上路由。當封包離開區域網路時，NAT 路由器會將內部來源 IP 位址轉換成公有 IP 位址。

本題描述所有封包離開區域網路時：

• 來源 IP 都變成 $138.76.29.7$
• 來源埠號各不相同

其轉換概念如下：

$$10.0.0.2:5000 \longrightarrow 138.76.29.7:60001$$ $$10.0.0.3:5000 \longrightarrow 138.76.29.7:60002$$

雖然多台內部主機共用同一個公有 IP 位址，但透過不同的來源埠號，NAT 路由器仍能辨識各個連線，並將回傳封包送回正確的內部主機。

---

解題方法

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

1. 內部來源位址屬於 $10.0.0.0/24$，是私有 IP 網段。
2. 對外使用相同的公有 IP $138.76.29.7$，再以不同來源埠號區分連線。

這正是 PAT 的典型運作方式。NAT 路由器會維護轉換表，例如：

內部來源	對外來源	目的地
$10.0.0.2:5000$	$138.76.29.7:60001$	Web Server A
$10.0.0.3:5000$	$138.76.29.7:60002$	Web Server A

收到回應封包時，路由器根據目的埠號查表：

• 目的地為 $138.76.29.7:60001$，轉回 $10.0.0.2:5000$
• 目的地為 $138.76.29.7:60002$，轉回 $10.0.0.3:5000$

因此，本題所描述的機制屬於 NAT，精確名稱是 PAT。

---

選項分析

(A) NAT：正確

NAT 會將私有 IP 位址轉換成公有 IP 位址，使內部多台主機能共用一個或少數幾個公有 IP。

核心觀念

本題考查：

• for 迴圈的執行次數
• while 迴圈的執行次數
• 區域變數 b 每次外層迴圈重新初始化
• 變數 x 的累加運算

程式中：

int x = 5;

初始值為 $x=5$。

---

解題方法與逐步追蹤

1. 計算外層 for 迴圈次數

for (int a = 1; a < 6; a++)

變數 a 依序為：

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

因此外層迴圈共執行 $5$ 次。

2. 計算內層 while 迴圈次數

每次進入外層迴圈時，皆會執行：

int b = 1;

因此 b 每次都重新從 $1$ 開始。

while (b < 9)
{
 x += 2;
 b += 2;
}

b 的變化如下：

執行前的 b	是否滿足 b < 9	執行後的 b	x 增加量
1	是	3	2
3	是	5	2
5	是	7	2
7	是	9	2
9	否，停止	—	—

內層迴圈共執行 $4$ 次，因此每次外層迴圈中：

$$x \text{ 增加 } 4\times 2=8$$

3. 計算總累加結果

外層迴圈執行 $5$ 次，每次使 $x$ 增加 $8$：

$$x=5+5\times 8$$

核心觀念

本題考查中序表示法（infix）轉前序表示法（prefix）。

• 中序：運算子位於兩個運算元之間，例如 $A+B$
• 前序：運算子放在兩個運算元之前，例如 $+AB$
• 前序表示式的根運算子必須最先出現，接著依序排列左子樹與右子樹。

原式為：

$$(A+B)*C+D*(E-F)$$

依運算優先順序與括號，可寫成：

$$\bigl((A+B)*C\bigr)+\bigl(D*(E-F)\bigr)$$

最外層運算子是加法 $+$。

---

解題方法

先將中序表示式依照運算結構分成左右兩部分：

$$\bigl((A+B)*C\bigr)+\bigl(D*(E-F)\bigr)$$

最外層為：

$$+\quad \text{左子式：}(A+B)*C \quad \text{右子式：}D*(E-F)$$

左子式 $(A+B)*C$ 的運算樹為：

• 根運算子：$*$
• 左子樹：$A+B$
• 右子樹：$C$

因此其前序表示式為：

$$*+ABC$$

右子式 $D*(E-F)$ 的運算樹為：

• 根運算子：$*$
• 左子樹：$D$
• 右子樹：$E-F$

因此其前序表示式為：

$$*D-EF$$

最後，將最外層的 $+$ 放在最前面：

$$\boxed{+*+ABC*D-EF}$$

所以正確選項為：

$$\boxed{\text{(C)}}$$

---

運算樹表示

整個運算樹如下：

 +
 / \
 * *
 / \ / \
 + C D -
 / \ / \
 A B E F

按照前序走訪順序「根 → 左 → 右」：

$$+\ , *\ , +\ , A\ , B\ , C\ , *\ , D\ , -\ , E\ , F$$

串接後得到：

+*+ABC*D-EF

---

選項分析

(A) **A++BC-DEF

錯誤。

前序表示式的第一個運算子可以是 $+$、$-$、$*$ 等，但此選項開頭為兩個連續的乘法運算子：

* *

依前序結構，第一個 $*$ 的左子樹會以第二個 $*$ 開始，後續運算元排列無法形成原式的結構。原式最外層應為加法 $+$，不是乘法 $*$。

---

(B) ++A*BC-*DEF

錯誤。

此選項開頭為：

+ + A ...

表示最外層加法的左子樹又是一個加法，但原式的最外層結構是：

$$\bigl((A+B)*C\bigr)+\bigl(D*(E-F)\bigr)$$

核心觀念

本題考查 C 語言中的：

• 指標運算。
• 前置遞增 ++k 與後置遞增、遞減 k++、k-- 的差異。
• 運算子優先順序。
• 複合指定運算子，如 +=、-=。

關鍵解析如下：

• *k-- 會解讀為 *(k--)，因為後置遞減 -- 的優先順序高於解參照運算子 *。
• *(++k) 先將指標 k 遞增，再存取新位置。
• *(k++) 先存取目前位置，再將指標遞增。

初始狀態為：

$$\texttt{array} = \{100,215,321,254,165\}$$

且：

$$k = \&array[1]$$

---

解題方法：逐行追蹤

第 1 行

*k-- += 5;

等價於：

*(k--) += 5;

先使用原本的 k，因此修改 array[1]：

$$array[1] = 215 + 5 = 220$$

完成存取後，k 後置遞減：

$$k = \&array[0]$$

目前狀態：

array = {100, 220, 321, 254, 165}
k = &array[0]

第 2 行

*(++k) += 9;

先執行前置遞增，使：

$$k = \&array[1]$$

再修改 array[1]：

$$array[1] = 220 + 9 = 229$$

目前狀態：

array = {100, 229, 321, 254, 165}
k = &array[1]

第 3 行

*(k++) += 7;

先使用目前的 k，所以修改 array[1]：

$$array[1] = 229 + 7 = 236$$

完成存取後，k 後置遞增：

$$k = \&array[2]$$

目前狀態：

array = {100, 236, 321, 254, 165}
k = &array[2]

第 4 行

*k++ -= 15;

等價於：

*(k++) -= 15;

先修改目前 k 所指向的 array[2]：

$$array[2] = 321 - 15 = 306$$

完成存取後，k 遞增至：

$$k = \&array[3]$$

最終陣列為：

核心觀念

本題考查作業系統的 paging（分頁）記憶體管理及其優點。

分頁的基本機制如下：

• 將程序的邏輯記憶體切成固定大小的 page（頁）。
• 將實體記憶體切成相同大小的 frame（框）。
• 程序的各個 page 可以配置到不連續的 frame。
• 透過 page table（頁表） 將邏輯位址中的 page number 轉換為 frame number。

分頁的主要效果包括：

1. 固定大小的 page 與 frame 便於配置。
2. 不需要連續的實體記憶體，因此可避免外部碎裂。
3. 頁表項目可加入權限位元，實現記憶體保護。
4. 多個程序可共用相同的唯讀頁或共享函式庫，實現記憶體共享。
5. 由於配置單位固定，最後一頁未完全使用時可能產生內部碎裂。

其中：

• 外部碎裂（external fragmentation）：可用記憶體分散在許多不連續的小區塊，總空間足夠但無法配置連續區域。
• 內部碎裂（internal fragmentation）：已分配的記憶體區塊內部有未被使用的空間。

---

解題方法

判斷每個選項是否為 paging 的優點即可。

分頁將記憶體切成固定大小的 frame，程序也切成固定大小的 page。由於 page 可以放入任意可用的 frame，程序不必佔據連續的實體記憶體，因此能消除外部碎裂。

但是，固定大小的分頁配置也可能使最後一頁只使用一部分，剩餘空間仍被保留給該程序，形成內部碎裂。因此「防止內部碎裂」不是 paging 的優點。

---

選項分析

(A) same page size

正確。Paging 採用固定大小的 page，而實體記憶體也切成相同大小的 frame。page 與 frame 大小相同，才能進行直接配置與位址轉換。

固定大小的配置單位能簡化：

• 記憶體配置與回收；
• 頁表設計；
• 邏輯位址到實體位址的轉換；
• 頁面置換與磁碟交換。

因此，使用相同大小的 page 與 frame 是 paging 的重要設計優點。

(B) preventing internal fragmentation

錯誤。這是本題答案。

Paging 使用固定大小的 frame。若程序大小不是 page size 的整數倍，最後一頁通常無法完全填滿。例如 page size 為 $4\text{ KB}$，程序需要 $10\text{ KB}$，必須配置：

$$\left\lceil \frac{10}{4} \right\rceil = 3\text{ pages}$$

實際配置空間為：

$$3 \times 4 = 12\text{ KB}$$

其中有：

$$12 - 10 = 2\text{ KB}$$

核心觀念

本題考「應用層協定與 SSL/TLS 的關係」。

SSL/TLS 位於應用層協定與傳輸層 TCP 之間，主要提供：

• 加密，保護資料機密性
• 身分驗證，確認伺服器身分
• 完整性驗證，防止資料遭竄改

HTTPS 的全名是 HTTP Secure，本質上就是：

$$\text{HTTPS}=\text{HTTP over SSL/TLS}$$

也就是將 HTTP 訊息交由 SSL/TLS 加密後，再透過 TCP 傳送。現代標準主要使用 TLS，SSL 已屬過時技術，但考題常以「SSL/TLS」合稱。

解題方法

看到題目問「哪一個協定實作在 SSL/TLS 之上」，直接尋找明確由「HTTP + SSL/TLS」組成的協定名稱。

• HTTP：未加密的網頁傳輸協定
• HTTPS：在 HTTP 之上加入 SSL/TLS 安全層的協定

因此：

$$\boxed{\text{HTTPS}=\text{HTTP}+\text{SSL/TLS}}$$

故官方答案為 (B) HTTPS。

選項分析

(A) HTTP

HTTP 是用於傳送網頁資料的應用層協定，傳統 HTTP 通常透過 TCP 第 80 埠傳輸，內容以明文形式傳送。

HTTP 本身不包含 SSL/TLS 加密，因此不是本題所問的答案。當 HTTP 加上 SSL/TLS 後，才稱為 HTTPS。

(B) HTTPS

HTTPS 是 HTTP over SSL/TLS，表示 HTTP 訊息先經過 SSL/TLS 保護，再透過網路傳送，通常使用 TCP 第 443 埠。

因此 HTTPS 正是「實作在 SSL/TLS 之上」的協定。

此選項正確。

(C) POP3

POP3 是 Post Office Protocol version 3，用於電子郵件接收，通常使用 TCP 第 110 埠。

POP3 原本並非建立在 SSL/TLS 之上。若使用加密版本，常見形式包括：

核心觀念

本題考查 SQL 的三個基本機制：

1. INNER JOIN：依照指定條件，合併兩個資料表中能互相匹配的資料。
2. ORDER BY：依指定欄位排序；DESC 代表遞減排序，由大到小。
3. TOP 1：只擷取排序後的第一筆資料。

題目要求輸出：

movie	name
The Matrix	Keanu Reeves

也就是必須同時做到：

• 從 movies 取得電影名稱；
• 從 actors 取得演員姓名；
• 依演員薪資由高到低排序；
• 只保留薪資最高的第一筆。

---

解題方法與資料追蹤

movies.actor 對應 actors.id，因此連接條件為：

movies.actor = actors.id

逐筆比對：

movies.movie	movies.actor	是否在 actors.id 找到	對應姓名	薪資
The Matrix	a_002	是	Keanu Reeves	200M
Iron Man	a_010	否	無	無
Doctor Strange	a_003	是	Benedict Cumberbatch	150M

由於是 INNER JOIN，Iron Man 沒有對應的演員資料，因此會被排除。

連接後的結果為：

movie	name	salary
The Matrix	Keanu Reeves	200M
Doctor Strange	Benedict Cumberbatch	150M

接著依 actors.salary DESC 由高到低排序：

1. Keanu Reeves：200M
2. Benedict Cumberbatch：150M

最後使用 TOP 1 只取第一筆：

movie	name
The Matrix	Keanu Reeves

因此正確 SQL 為：

SELECT TOP 1 movies.movie, actors.name
FROM movies
INNER JOIN actors ON movies.actor = actors.id
ORDER BY actors.salary DESC

---

選項分析

(A) SELECT * FROM movies

錯誤。

此指令只查詢 movies 資料表，不會連接 actors 資料表，因此：

• 無法取得演員姓名；
• 會輸出 id、movie、year、actor 等欄位；
• 會列出 movies 中的所有三筆資料。

輸出欄位與資料內容都不符合 Table 5。

---

(B)

SELECT TOP 1 movies.movie, actors.name
FROM movies
INNER JOIN actors ON movies.actor = actors.id
ORDER BY actors.salary DESC

正確。

此指令的執行順序可概念化為：

核心觀念

本題考查圖形的深度優先搜尋（Depth-First Search, DFS）。

DFS 的規則是：

1. 從指定起點開始拜訪。
2. 查看目前節點的相鄰節點。
3. 若有尚未拜訪的相鄰節點，依字母順序選擇最前者，立即深入搜尋。
4. 目前節點沒有尚未拜訪的相鄰節點時，回溯至上一個節點。
5. 重複上述流程，直到所有節點都拜訪完畢。

圖上的邊權重只代表數值，與 DFS 的拜訪順序無關。

解題方法

從節點 $D$ 開始。其相鄰節點依字母排序為：

$B,\ F,\ G$

因此先拜訪 $B$。

依照 DFS 並採字母順序追蹤：

1. $D \rightarrow B$

• $B$ 的未拜訪相鄰節點中，$A$ 最先，因此拜訪 $A$。

2. $B \rightarrow A$

• $A$ 的未拜訪相鄰節點為 $C$，因此拜訪 $C$。

3. $A \rightarrow C$

• $C$ 的未拜訪相鄰節點為 $E$，因此拜訪 $E$。

4. $C \rightarrow E$

• $E$ 的未拜訪相鄰節點依字母排序為 $F、H$，先拜訪 $F$。

5. $E \rightarrow F$

• $F$ 的未拜訪相鄰節點為 $G$，因此拜訪 $G$。

6. $F \rightarrow G$

• $G$ 的未拜訪相鄰節點依字母排序為 $H、I$，先拜訪 $H$。

7. $G \rightarrow H$

• $H$ 的未拜訪相鄰節點為 $I$，因此拜訪 $I$。

8. $I$ 的相鄰節點皆已拜訪，搜尋結束。

因此拜訪順序為：

$D,\ B,\ A,\ C,\ E,\ F,\ G,\ H,\ I$

選項分析