114 高普考普通考試 統計 資料處理概要 考古題詳解

核心觀念

本題考查 ER 圖的實體、屬性、主鍵與基數性，以及將 ER 圖轉換成關聯表格的方法。訂單與產品是多對多關係，並且此關係本身有「訂購數量」屬性，因此需要以關聯表格表示。SQL 則考查多表連接、列層級金額計算及分組彙總。

解題方法

先依題意辨認三種實體：客戶、訂單、產品；再依唯一性指定主鍵。接著判斷兩組關係的基數：

• 客戶與訂單是一對多：一位客戶可有零張或多張訂單，每張訂單恰由一位客戶下訂。
• 訂單與產品是多對多：每張訂單至少包含一項產品，一項產品可出現在零張或多張訂單中。訂購數量屬於訂單與產品的配對，因此放在該關係的關聯表格。

（一）實體關聯圖

文字表示如下，基數以「最小值..最大值」標示：

客戶
 客戶編號（主鍵）
 姓名
 電話
 地址

客戶 1 ─── 0..* 訂單
 訂單必須且僅屬於一位客戶

訂單
 訂單編號（主鍵）
 購貨日期

訂單 1..* ─── 0..* 產品
 每張訂單至少包含一項產品；
 每項產品可未曾被訂購，或出現在多張訂單中

產品
 產品編號（主鍵）
 產品名稱
 單價

「訂單－產品」關係的屬性：訂購數量

若以常見 ER 圖符號表示，客戶與訂單為 $1:N$；訂單與產品為 $M:N$。題目未提供訂單項目編號，因此訂單與產品的配對可由兩者的主鍵共同識別。

（二）最簡化的關聯表格

將一對多關係的外來鍵放在「多」的一方；將多對多關係拆成一張關聯表格。

核心觀念

本題考查已排序資料的查詢。對遞增或遞減的有序串列，都可用二分搜尋：每次檢查中間位置，依 $D$ 與中間值的大小關係，排除不可能含有 $D$ 的一半區間。

因為要查詢 $D$ 是否存在於 $L_1$ 或 $L_2$，兩個串列都必須納入搜尋。可先搜尋較短的串列；若找到 $D$ 即可停止，否則再搜尋另一串列。

解題方法

以下使用 0 起始索引。對遞增串列 $L_1$，若中間值小於 $D$，則只需搜尋右半部；對遞減串列 $L_2$，若中間值大於 $D$，則只需搜尋右半部。兩者的比較方向不同，但每次都能將候選範圍縮小約一半。

搜尋(D, L1, L2):
 先對較短的串列執行二分搜尋
 若找到 D，回傳「存在」
 再對另一串列執行二分搜尋
 若找到 D，回傳「存在」
 否則回傳「不存在」

二分搜尋(遞增串列 L, D):
 low = 0, high = 長度(L) - 1
 while low <= high:
 mid = floor((low + high) / 2)
 if L[mid] == D: 回傳「找到」
 if L[mid] < D: low = mid + 1
 else: high = mid - 1
 回傳「未找到」

二分搜尋(遞減串列 L, D):
 low = 0, high = 長度(L) - 1
 while low <= high:
 mid = floor((low + high) / 2)
 if L[mid] == D: 回傳「找到」
 if L[mid] > D: low = mid + 1
 else: high = mid - 1
 回傳「未找到」

核心觀念

後序式（Postfix Expression）把運算子寫在運算元之後，因此不需要括號或優先順序判斷。計算時由左至右掃描，使用堆疊暫存尚未參與運算的數值：

• 遇到運算元，將其數值推入堆疊。
• 遇到二元運算子，依序取出堆疊頂端的兩個數值運算，再將結果推回堆疊。
• 運算時，先取出的數值是右運算元，後取出的數值是左運算元。

解題方法

以堆疊 $S$ 儲存數值，掃描運算式中的每個符號：

1. 若符號是數字 $d$，執行 push(S, d)。
2. 若符號是運算子 $op$：

• $b \leftarrow pop(S)$
• $a \leftarrow pop(S)$
• $r \leftarrow a\ op\ b$
• push(S, r)

3. 掃描結束後，堆疊中唯一的數值即為運算結果。

偽程式碼：

計算後序式(E):
 建立空堆疊 S

 由左至右掃描 E 中的每個符號 x:
 若 x 是數字:
 push(S, x)
 否則:
 b ← pop(S)
 a ← pop(S)
 r ← a 與 b 依 x 運算
 push(S, r)

 return pop(S)

以題目範例 $23*5+$ 為例：

核心觀念

本題考查資訊安全的四項目標，以及如何結合雜湊函式與 RSA 公開金鑰密碼法，安排加密與簽章。核心原則是：

• 機密性：用接收者的公鑰加密，只有持有相對應私鑰的接收者能解密。
• 完整性：比對資料雜湊值，確認資料傳送途中未遭竄改。
• 鑑別性：確認資料來自所宣稱的傳送者。
• 不可否認性：傳送者以自己的私鑰簽章，使其事後不能否認曾簽署該資料。

記號如下：A 的 RSA 金鑰為 $(PK_A, SK_A)$，B 的 RSA 金鑰為 $(PK_B, SK_B)$；$H(\cdot)$ 為安全雜湊函式。公開金鑰可供他人取得，但必須能確認公鑰確實屬於其名義上的持有人。

（一）四項安全目標

1. 機密性（confidentiality） 防止未經授權者讀取資料內容。傳送者使用接收者的公鑰加密，只有接收者持有私鑰可解密。

2. 完整性（integrity） 確保資料在儲存或傳輸過程中未被未授權地修改、刪除或插入。常以雜湊值或訊息鑑別碼檢查資料是否改變；若須防止攻擊者自行重算雜湊，還須搭配祕密金鑰或數位簽章。

3. 鑑別性（authenticity） 確認資料來源或傳送者的身分是真實且可信的。數位簽章可用簽署者的私鑰產生，並以其公鑰驗證，達成來源鑑別。

4. 不可否認性（non-repudiation） 使簽署者不能否認曾對特定資料簽章。數位簽章須能連結簽署者與簽署內容；實務上也須妥善管理私鑰，並確認簽署者公鑰及身分的對應關係。

（二）A 傳送機密資料 $D$ 給 B

解題方法

以 B 的公鑰加密資料，保障機密性；再由 A 對資料雜湊值簽章，讓 B 能驗證資料完整性與來源。加密與簽章所用的金鑰不同：加密使用 B 的公鑰，簽章使用 A 的私鑰。

傳送流程

1. A 計算資料的雜湊值： $h=H(D)$

2. A 使用自己的私鑰對雜湊值簽章： $S=\operatorname{Sign}_{SK_A}(h)$

3. A 將資料與簽章組合，再以 B 的公鑰加密： $C=\operatorname{Enc}_{PK_B}(D\parallel S)$

A 傳送密文 $C$ 給 B。

接收與驗證流程

1. B 使用自己的私鑰解密： $(D',S)=\operatorname{Dec}_{SK_B}(C)$

2. B 計算收到資料的雜湊值 $H(D')$，並以 A 的公鑰驗證簽章，取得或確認簽章所對應的雜湊值。

3. 若驗證簽章成功，且簽章對應的雜湊值等於 $H(D')$，則接受資料。

安全目標說明

• 機密性：只有持有 $SK_B$ 的 B 能解開 $C$。
• 完整性：若 $D'$ 被竄改，雜湊值將不一致，簽章驗證失敗。
• 鑑別性：簽章以 A 的私鑰產生，B 以 A 的公鑰驗證，可確認資料來自持有 $SK_A$ 的一方。