107 鐵路特考員級 資訊處理 資料處理概要 考古題詳解

核心觀念

本題評量實體關聯模型（Entity-Relationship Model, ER Model）轉換為關聯式綱要（Relational Database Schema）​的標準設計能力，涵蓋關聯式資料庫設計的核心規範：

1. 實體（Entity）轉換規則：將獨立實體直接轉換為關聯表（Relation），以其識別屬性作為主鍵（Primary Key, PK）。
2. 一對多（$1:N$）關聯轉換規則：

• 判斷基數比（Cardinality Ratio）的「一端（$1$）」與「多端（$N$）」。
• 正規化標準做法是將「一端」的主鍵，作為外來鍵（Foreign Key, FK）置入「多端」的資料表中，以滿足第一正規化（1NF）並避免資料重複。

3. 多對多（$M:N$）關聯轉換規則：

• 關聯式架構無法直接在任一實體表中記錄多對多關係（否則會產生多值屬性，違反 1NF）。
• 必須建立獨立的關聯資料表（Associative / Bridge Relation），由兩端實體的主鍵共同構成複合主鍵（Composite Primary Key），且兩者分別為外來鍵指向各自的原實體表。

4. 參考完整性限制（Referential Integrity Constraint）：外來鍵的值必須在其所參考的主鍵值中存在，或者為空值（Null，若業務規則允許）。

---

解題方法

依題意逐項推導各實體表與關聯之設計切入點：

1. 實體表定義（第 (一)、(二)、(三) 點）：

• 客戶（Customer）：屬性包含客戶編號、客戶姓名、地址。主鍵為「客戶編號」。
• 貸款（Loan）：屬性包含貸款帳號、貸款金額。主鍵為「貸款帳號」。
• 存款（Deposit）：屬性包含存款帳號、存款餘額。主鍵為「存款帳號」。

2. 客戶與存款關聯分析（第 (四) 點）：

• 題目條件：「一個客戶只能有一個存款帳號，但一個存款帳號可以由多個客戶共用。」
• 此關聯為存款對客戶的 $1:N$ 關聯（一筆存款對應多個客戶；一個客戶對應一筆存款）。
• 「客戶」端為多端（$N$），「存款」端為一端（$1$）。因此，外來鍵應設計在客戶資料表中，加入屬性「存款帳號」，並參考「存款資料表」的主鍵「存款帳號」。

3. 客戶與貸款關聯分析（第 (五) 點）：

• 題目條件：「一個客戶可以貸多筆款，而多個客戶可以共同貸同一筆款。」
• 此關聯為客戶對貸款的 $M:N$ 關聯。
• 必須建立獨立的關聯資料表，命名為「客戶貸款」（或「貸戶」），其屬性包含「客戶編號」與「貸款帳號」。
• 主鍵為 (客戶編號, 貸款帳號) 構成之複合主鍵；「客戶編號」為外來鍵參考客戶表，「貸款帳號」為外來鍵參考貸款表。

---

題目各要點分析

本題為非選擇題，以下針對題目給定之五項條件進行規格對應與落實分析：

• (一) 客戶資料：屬於獨立實體，落實為資料表 客戶，欄位包含 客戶編號、客戶姓名、地址，以 客戶編號 為 PK。

核心觀念

本題評量關聯式資料庫結構化查詢語言（SQL）的核心操作能力，涵蓋關聯綱目參照、多表連接、群組聚合統計與子查詢篩選。涉及的關鍵概念如下：

1. 關聯綱目假設（依據前一題設計）：

• 客戶資料表 Customer(CustID, CustName, Phone, Address)，主鍵為 CustID。
• 存款帳戶資料表 Account(AccNo, CustID, Balance)，主鍵為 AccNo，外鍵為 CustID（參照 Customer）。
• 貸款資料表 Loan(LoanNo, CustID, Amount)，主鍵為 LoanNo，外鍵為 CustID（參照 Customer）。

2. 聚合函數與分組（Aggregate Functions & GROUP BY）：使用 COUNT 計算筆數、SUM 計算加總值，並依據非聚合欄位進行 GROUP BY 群組化。
3. 外部連接（Outer Join）與空值處理：題目要求統計「每一個客戶」，語意上包含無貸款或無存款紀錄的客戶，須使用 LEFT OUTER JOIN 確保所有客戶皆被納入，並使用 COALESCE 或 COUNT(欄位名) 妥善處理 NULL 值。
4. 集合交集與子查詢（Intersection & Subquery）：運用巢狀子查詢 IN 或集合運算子 INTERSECT，找出同時具備兩種關聯紀錄（有存款且有貸款）的資料列。

---

解題方法

(一) 統計出每一個客戶的貸款筆數與總共的貸款金額

• 切入點：因需列出「每一個客戶」，若直接使用 INNER JOIN 或僅從 Loan 表查詢，無貸款之客戶將被遺漏。因此以 Customer 為主表，對 Loan 表進行 LEFT JOIN。
• 計算處理：
• 貸款筆數：計算 COUNT(L.LoanNo)。若該客戶無貸款，L.LoanNo 為 NULL，計算結果為 $0$；若誤用 COUNT(*) 則會將 NULL 列計為 $1$ 筆。
• 總貸款金額：計算 SUM(L.Amount)，並使用 COALESCE(SUM(L.Amount), 0) 將無貸款者的 NULL 轉為 $0$。
• 分組原則：SELECT 清單中的非聚合欄位（C.CustID, C.CustName）必須全數列入 GROUP BY 子句中。

(二) 找出在銀行有存款也有貸款的客戶姓名

• 切入點：尋找「客戶編號同時存在於 Account 與 Loan」的交集條件。
• 實作方式：使用 WHERE 子句搭配雙重 IN 子查詢（或 EXISTS），語意最為直觀且能自動消除重複客戶名稱，亦可避免多對多關聯連接所產生的笛卡兒積冗餘。

(三) 列出每一個客戶的編號、姓名、存款帳號和餘額

• 切入點：將 Customer 與 Account 依客戶編號進行關聯。
• 連接選擇：題幹強調「每一個客戶」，嚴謹做法係採用 LEFT JOIN，使尚未開立存款帳號的客戶亦能列出其編號與姓名，其帳號與餘額則以 NULL 顯示；若僅列出已開戶者，則採用 INNER JOIN。

---

選項分析（語法元件與替代解法剖析）

本題為非選擇題（SQL 程式設計題），各子題核心元件與替代寫法評析如下：

• 子題 (一) 語法分析：
• LEFT JOIN vs INNER JOIN：使用 LEFT JOIN 才能保證「從未貸款的客戶」也以 0 筆、金額 0 元列出，符合「每一個客戶」之嚴格語意；

核心觀念

本題旨在評量堆疊（Stack）​在算術運算式解析與求值（Arithmetic Expression Parsing and Evaluation）​之實務應用。核心概念包含：

1. 堆疊的運作特性： 堆疊為後進先出（LIFO, Last-In-First-Out）​之線性資料結構，所有插入（Push）與刪除（Pop）皆在頂端（Top）進行。
2. 運算子優先權（Operator Precedence）與結合性（Associativity）：

• 乘除（$\times$、$/$）之優先權高於加減（$+$、$-$）。
• 當讀入新運算子的優先權小於或等於堆疊頂端運算子之優先權時，堆疊頂端的運算子必須先彈出執行運算。

3. 雙堆疊求值機制（Two-Stack Algorithm）： 解析中序運算式（Infix Expression）一般採用兩個堆疊協同運作：

• 運算元堆疊（Operand Stack）：儲存數值資料（運算元）。
• 運算子堆疊（Operator Stack）：暫存運算符號，確保運算順序符合先乘除後加減。
• 當彈出二元運算子 $\theta$ 時，運算元堆疊依序彈出兩數 $B$（先彈出，為右運算元）與 $A$（後彈出，為左運算元），計算 $A\ \theta\ B$ 後，將結果推回運算元堆疊。

---

解題方法

題目運算式為： $8\times9+6=$

依序讀入的符號（Token）共有 6 個：8 $\to$ * $\to$ 9 $\to$ + $\to$ 6 $\to$ =。

以下繪圖詳細展示每讀入一個符號時，運算元堆疊（Operand Stack）​與運算子堆疊（Operator Stack）​的內部資料儲存變化：

步驟 1：讀入運算元 8

• 規則：運算元直接推入運算元堆疊。

 [運算元堆疊] [運算子堆疊]
 ┌─────────┐ ┌─────────┐
 │ 8 │<─Top │ (空) │
 └─────────┘ └─────────┘

步驟 2：讀入運算子 *

• 規則：運算子堆疊為空，直接將 * 推入運算子堆疊。

 [運算元堆疊] [運算子堆疊]
 ┌─────────┐ ┌─────────┐
 │ 8 │<─Top │ * │<─Top
 └─────────┘ └─────────┘

步驟 3：讀入運算元 9

• 規則：運算元直接推入運算元堆疊。

 [運算元堆疊] [運算子堆疊]
 ┌─────────┐ ┌─────────┐
 │ 9 │<─Top │ * │<─Top
 ├─────────┤ └─────────┘
 │ 8 │
 └─────────┘

步驟 4：讀入運算子 +

• 規則：

1. 比較優先權：讀入的 + 優先權低於堆疊頂端的 *。
2. 彈出運算子 *，並由運算元堆疊彈出右運算元 9 與左運算元 8。
3. 計算 $8 \times 9 = 72$，將運算結果 72 推回運算元堆疊。
4. 此時運算子堆疊已空，將 + 推入運算子堆疊。

核心觀念

合併排序法（Merge Sort）是典型的分治法（Divide and Conquer）​演算法，其核心思想包含三個主要步驟：

1. 分割（Divide）：將待排序的 $n$ 筆資料從中間切分為兩半，遞迴地將每個子數列繼續對分，直到每個子數列的長度為 $1$。
2. 解決（Conquer）：當子數列長度為 $1$ 時，視為天然已排序狀態（遞迴終止條件，Base Case）。
3. 結合／合併（Combine / Merge）：依序由底向上將兩個已排序的相鄰子數列，透過雙指針（Two Pointers）線性比對元素大小，合併為一個較大的有序數列，直至還原為長度為 $n$ 的完整已排序數列。

重要性質與評分要點：

• 時間複雜度：最差、最佳、平均皆為 $O(n \log_2 n)$。其遞迴關係式為 $T(n) = 2T(n/2) + O(n)$，樹狀高度為 $\lceil \log_2 n \rceil + 1$。
• 空間複雜度：$O(n)$（非原地排序 Out-of-place，合併時需要額外的暫存陣列）。
• 穩定性（Stability）：屬於穩定排序（Stable Sort）。題目中有兩筆鍵值相同的資料（$50$），在合併過程中，若兩端數值相等，應優先取出左側子數列的元素，以維持其原始相對位置。

---

解題方法

給定 $8$ 筆資料，為凸顯穩定排序特性，將兩筆數值為 $50$ 的資料分別標記為 $50_{(1)}$ 與 $50_{(2)}$： $[85,\ 24,\ 63,\ 50_{(1)},\ 17,\ 31,\ 96,\ 50_{(2)}]$

解題分為兩大階段推導並繪製架構圖：

1. 分割階段（Divide）

• Level 0（原始資料，長度 8）：$[85,\ 24,\ 63,\ 50_{(1)},\ 17,\ 31,\ 96,\ 50_{(2)}]$
• Level 1（對半切分，長度各 4）：
• 左半部：$[85,\ 24,\ 63,\ 50_{(1)}]$
• 右半部：$[17,\ 31,\ 96,\ 50_{(2)}]$
• Level 2（再度切分，長度各 2）：
• $[85,\ 24]$、$[63,\ 50_{(1)}]$、$[17,\ 31]$、$[96,\ 50_{(2)}]$
• Level 3（切分至基本單位，長度各 1）：
• $[85]$、$[24]$、$[63]$、$[50_{(1)}]$、$[17]$、$[31]$、$[96]$、$[50_{(2)}]$

2. 合併階段（Merge）

• 第一次合併（長度 $1 \to 2$）：
• $[85]$ 與 $[24]$ 合併 $\to [24,\ 85]$
• $[63]$ 與 $[50_{(1)}]$ 合併 $\to [50_{(1)},\ 63]$
• $[17]$ 與 $[31]$ 合併 $\to [17,\ 31]$
• $[96]$ 與 $[50_{(2)}]$ 合併 $\to [50_{(2)},\ 96]$
• 第二次合併（長度 $2 \to 4$）：
• $[24,\ 85]$ 與 $[50_{(1)},\ 63]$ 合併：比對首項元素依次取出 $24 \to 50_{(1)} \to 63 \to 85$，得 $[24,\ 50_{(1)},\ 63,\ 85]$
• $[17,\ 31]$ 與 $[50_{(2)},\ 96]$ 合併：比對首項元素依次取出 $17 \to 31 \to 50_{(2)} \to 96$，得 $[17,\ 31,\ 50_{(2)},\ 96]$
• 第三次合併（長度 $4 \to 8$，完成排序）：
• 比對 $[24,\ 50_{(1)},\ 63,\ 85]$ 與 $[17,\ 31,\ 50_{(2)},\ 96]$：

1. 比較 $24$ 與 $17 \to$ 取出 $17$
2. 比較 $24$ 與 $31 \to$ 取出 $24$
3. 比較 $50_{(1)}$ 與 $31 \to$ 取出 $31$
4. 比較 $50_{(1)}$ 與 $50_{(2)} \to$ 因左側優先（穩定性），取出 $50_{(1)}$
5. 比較 $63$ 與 $50_{(2)} \to$ 取出 $50_{(2)}$