114 地方特考三等 統計類科 資料處理 考古題詳解

核心觀念

本題考查資訊安全中的雜湊函數與數位簽章。雜湊函數將任意長度的資料轉換為固定長度的摘要值，用來檢查資料是否遭到變更；數位簽章則運用公開金鑰密碼技術，提供訊息來源驗證、完整性檢查及不可否認性。

解題方法

作答時可依「雜湊函數做什麼、具備哪些特性、數位簽章如何簽署與驗證」三個部分說明，並釐清：雜湊本身不等於加密，也不能單獨證明訊息由誰傳送。

一、雜湊函數的功能與主要特性

雜湊函數（Hash Function）將長度不一的輸入訊息 $M$ 映射為固定長度的雜湊值（摘要）：

其主要用途是作為資料的「指紋」，供驗證資料完整性。接收者重新計算收到訊息的雜湊值，與原先取得的摘要比較；若不同，即表示訊息或摘要至少有一者已改變。

雜湊函數的主要特性如下：

1. 可處理任意長度輸入：輸入訊息可長可短。
2. 輸出長度固定：不論輸入資料長度如何，摘要長度固定。
3. 計算效率高：給定訊息後，能有效率地計算摘要。
4. 抗原像性：已知摘要 $h$，在計算上難以找出訊息 $M$ 使 $H(M)=h$。
5. 抗第二原像性：已知特定訊息 $M_1$，在計算上難以找出不同訊息 $M_2$，使 $H(M_1)=H(M_2)$。
6. 抗碰撞性：在計算上難以找到任意兩個不同訊息 $M_1$、$M_2$，使 $H(M_1)=H(M_2)$。
7. 雪崩效應：輸入即使只有極小變動，輸出的摘要也會大幅改變。

雜湊值長度固定，因此理論上不同輸入可能產生相同摘要，稱為「碰撞」；抗碰撞性是指要有效率地找出碰撞非常困難，並非數學上絕不可能發生。

二、數位簽章的運作過程

假設寄件者為甲、收件者為乙，甲持有私密金鑰 $SK_A$，公開金鑰為 $PK_A$。

核心觀念

本題考查三項資料處理基本操作：

• 中序式轉前序式：依運算子的優先順序與括號，先確定運算結構，再將運算子放到運算元之前。
• 二元樹後序走訪：依「左子樹、右子樹、根節點」的順序走訪。
• 最小堆積樹（Min Heap）：必須符合完全二元樹的形狀，且每個父節點的值小於或等於其子節點。插入時先放在下一個空位，再向上調整；刪除最小值時，以最後一個節點補到根，再向下調整。

解題方法與步驟

(1) 中序式轉前序式

原式為 $(A-B)*(C+D)/F$。乘除優先順序相同，依左結合規則，整體結構為：

先將各子運算轉為前序式：

• $(A-B)$：$-\,A\,B$
• $(C+D)$：$+\,C\,D$
• 兩者相乘：$*\,(-\,A\,B)\,(+\,C\,D)$
• 最後除以 $F$：$/\,(*\,(-\,A\,B)\,(+\,C\,D))\,F$

(2) 二元樹後序走訪

後序走訪依「左、右、根」進行。圖中 $F$ 的右子節點為 $H$。

• $B$ 子樹：先走訪 $D、E$，再走訪 $B$，得 $D、E、B$。
• $C$ 子樹：$F$ 子樹先走訪 $H、F$，再走訪 $G$，最後走訪 $C$，得 $H、F、G、C$。
• 最後走訪根節點 $A$。

(3) 依序插入數字建立最小堆積樹

按完全二元樹順序放入新數字，再與父節點比較，必要時向上交換：

核心觀念

資料庫正規化是依據資料間的相依關係，將資料表拆分為結構較合理的表格，以減少資料重複，並避免新增、修改及刪除資料時發生異常。判斷正規形式時，先確認資料表的候選鍵與函數相依，再逐階檢查是否符合條件。

若屬性集合 $X$ 能唯一決定屬性 $Y$，記為函數相依 $X \to Y$。候選鍵是能唯一識別資料列，且其任何真子集合都不能唯一識別資料列的最小屬性集合。主屬性是至少屬於一個候選鍵的屬性；非主屬性則不屬於任何候選鍵。

解題方法：由低階到高階檢查

依序檢查第一正規化（1NF）、第二正規化（2NF）、第三正規化（3NF）及 Boyce–Codd 正規化（BCNF）。每一階都建立在前一階已符合的基礎上；若違反條件，便依函數相依將資料表分解，降低重複與更新異常。

第一正規化（1NF）

每個欄位都必須存放單一、不可再分的值；每筆資料以列表示，且同一欄位不能在同一列中存放多個值或重複群組。

例如，若「電話」欄位存有「0912-345-678、0922-111-222」，便不符合 1NF；應拆成多筆資料，或另建電話資料表。

第二正規化（2NF）

資料表必須先符合 1NF，且每個非主屬性都必須完全依賴每一個候選鍵，不能只依賴複合候選鍵的一部分。這項要求是消除部分函數相依。

例如，資料表以「學號、課程代碼」作為複合鍵，但「姓名」只由學號決定，即有「學號 $\to$ 姓名」的部分相依。可將學生資料與選課資料分表，避免同一學生姓名在多筆選課紀錄中重複。

若候選鍵只有單一屬性，便沒有複合鍵的一部分可供部分相依，符合 1NF 的資料表通常也符合 2NF。

第三正規化（3NF）

核心觀念

本題考遞迴呼叫與字串串接的執行順序。程式先計算指定敘述右側的表達式，再執行函數主體中的 if 判斷。因此，即使 $n \le 0$ 時最後會回傳空字串，該次呼叫仍會先計算 n + Test(n - 1) + n + Test(n - 2)。

字串串接依序進行，+ 左右兩側只要有字串，數字也會轉成字串。題目未提供具體程式語言，但依 String、int 與此處的串接寫法，以下按 + 表示字串串接解讀。

解題方法

從 $Test(3)$ 展開呼叫，並由遞迴終止條件 $n \le 0$ 得知 $Test(0)$、$Test(-1)$、$Test(-2)$ 等呼叫最終都回傳空字串 ""。

先計算 $Test(1)$：

再計算 $Test(2)$：