109 專技高考高等考試 資訊技師 資料結構與資料庫及資料探勘 考古題詳解

核心觀念

本題評量**分治法（Divide-and-Conquer）**在排序演算法中的經典應用——合併排序法（Merge Sort）。其核心概念包含三個步驟：

1. 分割（Divide）：將目前長度為 $n$ 的數列從正中間切分為長度各為 $\lfloor n/2 \rfloor$ 與 $\lceil n/2 \rceil$ 的兩個子數列，持續遞迴分割，直到每個子數列長度均為 $1$。
2. 征服（Conquer）：長度為 $1$ 的子數列視為已排序完成，此為遞迴終止條件（Base Case）。
3. 結合（Combine / Merge）：將兩兩相鄰且已各自排序好的子數列，透過雙指標（Two Pointers）由小到大依序比對，合併成一個較大且已排序的新數列，重複此步驟直至還原成完整數列。

複雜度與特性：

• 時間複雜度：分割階段建立高度為 $\lceil \log_2 n \rceil + 1$ 的二元遞迴樹；每一層合併需花費 $\mathcal{O}(n)$ 的比對時間。因此最佳、最差與平均時間複雜度皆為 $\mathcal{O}(n \log_2 n)$。
• 空間複雜度：合併過程中需要額外配置輔助陣列存放暫存資料，空間複雜度為 $\mathcal{O}(n)$。
• 穩定性（Stability）：屬於穩定排序（Stable Sort）；比對數值相同時，優先取左側子數列之元素，即可保證鍵值相同元素的原始相對順序不變。

解題方法

給定數列共有 $8$ 個元素： $A = [8, 70, 19, 3, 50, 25, 30, 10]$

依標準由上而下（Top-Down）遞迴方式推導：

一、分割階段（Divide Phase）

• 第 0 層（原始數列）：$[8, 70, 19, 3, 50, 25, 30, 10]$
• 第 1 次二分：對半切分為左半部 $[8, 70, 19, 3]$ 與右半部 $[50, 25, 30, 10]$。
• 第 2 次二分：
• 左半部切為 $[8, 70]$ 與 $[19, 3]$。
• 右半部切為 $[50, 25]$ 與 $[30, 10]$。
• 第 3 次二分（基礎情況）：各子數列切為長度 $1$ 的單一元素： $[8], [70], [19], [3], [50], [25], [30], [10]$

二、合併階段（Merge Phase）

• 第 1 次合併（長度 $1 \to 2$）：
• $\text{Merge}([8], [70]) \implies [8, 70]$
• $\text{Merge}([19], [3]) \implies [3, 19]$
• $\text{Merge}([50], [25]) \implies [25, 50]$
• $\text{Merge}([30], [10]) \implies [10, 30]$
• 第 2 次合併（長度 $2 \to 4$）：
• $\text{Merge}([8, 70], [3, 19]) \implies [3, 8, 19, 70]$
• $\text{Merge}([25, 50], [10, 30]) \implies [10, 25, 30, 50]$
• 第 3 次合併（長度 $4 \to 8$）：

核心觀念

二元搜尋樹（Binary Search Tree, BST）遵守以下順序性質：每個節點的左子樹鍵值小於該節點，右子樹鍵值大於該節點。插入時從根節點開始逐層比較，直到找到空位置；刪除時則依被刪節點的子節點數處理：

• 沒有子節點：直接刪除。
• 只有一個子節點：以該子節點接替被刪節點。
• 有兩個子節點：以中序後繼（右子樹最小值）或中序前驅（左子樹最大值）接替。

解題方法

依原圖，初始 BST 如下：

 30
 / \
 3 60
 \ \
 10 70
 / /
 5 65
 \
 7
 / \
 6
 /
 20
 / \
 15 25
 \
 17

原圖中 $20$ 是 $10$ 的右子節點，$15$ 是 $20$ 的左子節點，$17$ 是 $15$ 的右子節點。依實際連線整理後，完整樹形為：

 30
 / \
 3 60
 \ \
 10 70
 / \ /
 5 20 65
 \ / \
 7 15 25
 / \
 6 17

一、依序插入 $68、4$

插入 $68$：

比較路徑為 $68>30$、$68>60$、$68<70$、$68>65$，因此插入 $65$ 的右子節點。

 30
 / \
 3 60
 \ \
 10 70
 / \ /
 5 20 65
 \ / \ \
 7 15 25 68
 / \
 6 17

接著插入 $4$：

核心觀念

本題評量關聯式資料庫系統（DBMS）在「交易管理（Transaction Management）」與「並行控制（Concurrency Control）」領域的核心知識。

1. 交易的隔離性（Isolation）： 在多使用者環境下，多筆交易同時執行（Interleaved Execution）時，若未加適當控制，交易之間會互相干擾，破壞 ACID 特性中的隔離性與一致性（Consistency）。
2. 讀寫衝突（Conflict Types）與異常對應： 並行排程（Schedule）中的資料干擾本質上來自非受控的讀寫衝突：

• 寫入－寫入衝突（$W-W$ Conflict）：對應「遺失更新（Lost Update）」。
• 寫入－讀取衝突（$W-R$ Conflict）：對應「未確認相依（Uncommitted Dependency / Dirty Read）」。
• 讀取－寫入衝突（$R-W$ Conflict）：對應「不一致分析（Inconsistent Analysis / Non-repeatable Read）」。

解題方法

針對申論題型的名詞與現象說明，最佳解答結構應包含三要素：

1. 精準定義：指出衝突發生的條件與機制。
2. 時序範例（Interleaved Schedule）：使用標準交易符號（$R_i(X)$ 表示交易 $T_i$ 讀取 $X$；$W_i(X)$ 表示交易 $T_i$ 寫入 $X$）搭配具體數值變化，證明干擾過程。
3. 影響後果：說明該現象對資料一致性造成的破壞。

解題技巧

1. 二元對應速記法：

• 遺失更新：$W \to W$（後寫蓋前寫，前功盡棄）。
• 未確認相依（髒讀）：$W \to R \to \text{Abort}$（讀了別人後來反悔放棄的暫存資料）。
• 不一致分析（模糊讀取）：$R \to W \to R$（統計過程中資料被別人竄改，前後算不攏）。

2. 版面排版竅門： 在國家考試試卷上，單純純文字描述不易拿滿分。利用「時間軸／時序表格」呈現 $T_1$ 與 $T_2$ 的執行先後順序，能讓閱卷委員一眼看清衝突點，為高分關鍵。
3. 延伸對應（加分亮點）： 可點出 ANSI SQL 隔離層級（Read Committed、Repeatable Read、Serializable）與兩階段鎖定協議（2PL）如何預防此類問題。

【答案】

資料庫管理系統在缺乏適當並行控制機制時，因交易交錯執行所產生的三種資料干擾問題說明如下：

一、遺失更新（Lost Update）

1. 定義與成因： 當交易 $T_1$ 與 $T_2$ 同時讀取同一筆資料項 $X$，各自在記憶體緩衝區進行修改後先後寫回資料庫。後寫入的交易（$T_2$）覆蓋了先寫入的交易（$T_1$）所做的更新結果，導致 $T_1$ 的更新如同從未發生過，形成寫入－寫入衝突（$W-W$ Conflict）。

2. 時序範例： 假設帳戶餘額 $X = 100$ 元，$T_1$ 欲存入 20 元，$T_2$ 欲扣除 10 元（正確結果應為 $100 + 20 - 10 = 110$ 元）：

核心觀念

本題測驗關聯式資料庫管理系統（RDBMS）中 SQL 語法（ANSI SQL-92 標準）與關聯代數（Relational Algebra）的「合併運算」（Join Operation）核心機制。

1. 內部合併（Inner Join）：僅保留兩資料表中符合連接條件（Join Predicate / Condition）的交集成對元組（Tuples），未匹配的元組將全數被捨棄。
2. 外部合併（Outer Join）：為了解決懸空元組（Dangling Tuples / Unmatched Tuples）在內部合併中遺失的問題，外部合併允許保留特定或全部資料表中未匹配的資料，並對未對應到的欄位自動填補空值（NULL）。
3. 關聯代數定義：

• 內部合併：$R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)$
• 左外部合併：$R ⟕_{\theta} S$
• 右外部合併：$R ⟖_{\theta} S$
• 全外部合併：$R ⟗_{\theta} S$

解題方法

本題分為兩大作答核心：

1. 列出三種外部合併指令：標註中文全名、標準 SQL 關鍵字及關聯代數符號。
2. 比較四種合併方式的差異：由集合論邏輯切入，說明未匹配資料的處理方式，並設計一組簡易資料表實例對比查詢結果。

1. 外部合併（Outer Join）的三種指令

SQL 標準中，外部合併依據「保留未匹配資料的資料表來源」分為以下三種：

• 左外部合併（Left Outer Join）：關鍵字為 LEFT JOIN 或 LEFT OUTER JOIN。
• 右外部合併（Right Outer Join）：關鍵字為 RIGHT JOIN 或 RIGHT OUTER JOIN。
• 全外部合併（Full Outer Join）：關鍵字為 FULL JOIN 或 FULL OUTER JOIN。

2. 四者（Inner Join 與三種 Outer Join）之差異比較

四者根本差異在於「對不符合連接條件（Non-matching）之資料列的保留規則與補值行為」：

3. 範例說明

假設有資料表 $A$（員工表 Emp）與資料表 $B$（部門表 Dept），以 Emp.DeptID = Dept.DeptID 為合併條件：

• 資料表 $A$ (Emp)：
• (EmpID: 1, Name: '王小明', DeptID: 10)
• (EmpID: 2, Name: '李小華', DeptID: 20)
• (EmpID: 3, Name: '張大同', DeptID: NULL) （無部門）
• 資料表 $B$ (Dept)：
• (DeptID: 10, DeptName: '研發部')
• (DeptID: 20, DeptName: '人事部')
• (DeptID: 30, DeptName: '行銷部') （無所屬員工）

四種查詢結果差異如下：

1. 內部合併（Inner Join）：

• 僅產出匹配的 2 筆紀錄：王小明-研發部、李小華-人事部。
• 張大同與行銷部皆被捨棄。

2. 左外部合併（Left Outer Join）：

• 產出 3 筆紀錄：王小明-研發部、李小華-人事部、張大同-NULL。
• 保留左表（Emp）全部人員，未對應到的部門欄位填補 NULL。

3. 右外部合併（Right Outer Join）：

核心觀念

本題評量資料探勘（Data Mining）與機器學習領域中，二元分類（Binary Classification）模型之效能評估機制。其核心建立於混淆矩陣（Confusion Matrix）：

設定感興趣的目標類別為「正類（Positive）」，另一類別為「負類（Negative）」。本題目標為辨識人物照，故定義：

• 正類（Positive）：人物照
• 負類（Negative）：風景照（非人物照）

混淆矩陣之四種基本計數：

1. 真陽性（True Positive, $TP$）：實際為正類，且被模型正確預測為正類。
2. 假陽性（False Positive, $FP$）：實際為負類，但被模型誤判為正類（型 I 錯誤，Type I Error）。
3. 真陰性（True Negative, $TN$）：實際為負類，且被模型正確預測為負類。
4. 假陰性（False Negative, $FN$）：實際為正類，但被模型誤判為負類（型 II 錯誤，Type II Error）。

各項評估指標定義與公式如下：

• 正確率（Accuracy）：在所有樣本中，被正確預測（包含正類與負類）的比例。 $Accuracy = \frac{TP + TN}{TP + TN + FP + FN}$
• 精確率（Precision，又稱查準率）：在所有被模型「預測為正類」的樣本中，實際上真正為正類的比例。著重於「模型預測的正類中，有多少是準確的」。 $Precision = \frac{TP}{TP + FP}$
• 召回率（Recall，又稱查全率、靈敏度 Sensitivity）：在所有「實際為正類」的樣本中，成功被模型預測出來的比例。著重於「實際存在的正類中，有多少被成功撈出」。 $Recall = \frac{TP}{TP + FN}$

解題方法

第一部分：建構混淆矩陣

依題意拆解題目給定之各項數據：

1. 總樣本數：$1000$ 張。
2. 實際分佈：

• 實際為人物照（Actual Positive）$= TP + FN = 200$
• 實際為風景照（Actual Negative）$= TN + FP = 800$

3. 分類器預測結果：

• 預測為人物照（Predicted Positive）$= TP + FP = 400$
• 預測為非人物照（Predicted Negative）$= TN + FN = 600$

4. 關鍵誤判條件：

• 「被判斷為人物照的照片中有 $250$ 張實際上並非人物照」，即預測為正但實際為負（False Positive）： $FP = 250$

5. 推導其餘數值：

• 由 $TP + FP = 400$ 得： $TP = 400 - 250 = 150$
• 由 $TP + FN = 200$ 得： $FN = 200 - 150 = 50$
• 由 $TN + FP = 800$ 得： $TN = 800 - 250 = 550$

驗算預測為非人物照總數：$TN + FN = 550 + 50 = 600$，與題意相符。

將上述數值整理為混淆矩陣：

第二部分：計算評估指標

1. 正確率（Accuracy）：