107 地方特考四等 資訊處理 資料處理概要 考古題詳解

核心觀念

本題評量資料結構的兩大基本線性結構——堆疊（Stack）​與佇列（Queue），及其在樹狀結構走訪（Tree Traversal）演算法中的對應與應用。

1. 資料結構特性：

• 堆疊（Stack）：遵循後進先出（LIFO, Last-In-First-Out）​原則，資料的插入（Push）與刪除（Pop）皆發生在同一端（Top）。
• 佇列（Queue）：遵循先進先出（FIFO, First-In-First-Out）​原則，資料自後端（Rear）加入（Enqueue），由前端（Front）移出（Dequeue）。

2. 走訪演算法特性：

• 深度優先走訪（Depth-First Search, DFS）：從根節點出發，沿著分支不斷深入直到葉節點（Leaf），無法繼續前進時則進行回溯（Backtracking），轉向另一個分支繼續探尋。
• 廣度優先走訪（Breadth-First Search, BFS）：又稱階層走訪（Level-Order Traversal），從根節點（第 $0$ 層）開始，依序將第 $k$ 層的所有節點走訪完畢後，才進入第 $k+1$ 層繼續走訪。

解題方法

(一) 深度優先走訪（DFS）何者較適合與原因說明

• 適用結構：堆疊（Stack）​較適合。
• 原因說明：

1. 符合後進先出（LIFO）之探索順序： DFS 的核心策略是「優先探索最深層的節點」。當走訪至某一節點時，其產生的子節點（更深一層）必須優先於其兄弟節點（同層節點）被探訪。堆疊具備 LIFO 特性，最後被推入堆疊的子節點會最先被彈出（Pop）處理，恰好能實現「朝深處持續探索」的機制。
2. 完美支援回溯（Backtracking）機制： 當某一分支探訪至底（葉節點）時，演算法必須回到最近一個還有未走訪分支的分歧點。在堆疊中，前一個分歧節點的未訪子節點剛好位於目前頂端之下，當底部節點處理完畢彈出後，頂端自然暴露出上一層的未處理節點，天然支援回溯操作。
3. 程式實作對應： 若以「遞迴（Recursion）」實作 DFS，底層仰賴的是作業系統的呼叫堆疊（Call Stack）；若改寫為非遞迴的迭代寫法，程式設計師則必須在程式碼中明確宣告並維護一個自訂的堆疊（Explicit Stack）。

(二) 廣度優先走訪（BFS）何者較適合與原因說明

• 適用結構：佇列（Queue）​較適合。
• 原因說明：

1. 符合先進先出（FIFO）之階層順序： BFS 的目標是實現逐層走訪（Level-Order）。所有在深度為 $k$ 的節點，都必須先於深度為 $k+1$ 的節點被處理。佇列的 FIFO 特性保證了「較早被發現的節點，必定較早被取出處理」。
2. 保持子節點的處理時序：

核心觀念

本題主要測驗資料結構與資料庫系統中的雜湊（Hashing）技術，包含兩大主題：

1. 靜態雜湊（Static Hashing）：

• 雜湊表的位址空間（籃子數量 $B$）在初始化時即固定，透過雜湊函數 $h(key)$ 將鍵值映射至特定籃子（Bucket）。
• 當資料量增加且某個籃子存滿（達到容量上限）時，會發生溢位（Overflow），需藉由溢位鏈結（Overflow Chaining）或開放定址法（Open Addressing）等機制處理，搜尋效能可能由 $O(1)$ 退化。若預留過多空間則會造成記憶體浪費。

2. 動態雜湊（Dynamic Hashing / 可延伸雜湊 Extendible Hashing）：

• 為解決靜態雜湊無法靈活調整大小的問題，動態雜湊允許儲存空間隨資料量動態增減。
• 本題以最廣泛採用的可延伸雜湊（Extendible Hashing）​為標準解法：利用鍵值的二進位位元（由最高有效位元 MSB 開始），透過目錄（Directory）​與資料籃（Bucket）​的雙層結構進行索引。
• 核心參數：
• 全域深度（Global Depth, $d$）：目錄目前使用的二進位前綴位元數，目錄項目總數為 $2^d$。
• 區域深度（Local Depth, $d'$）：各別籃子所依據的二進位前綴位元數。當某籃子容量滿且發生碰撞時，若 $d' = d$，目錄必須倍增擴充（$d \leftarrow d+1$）；若 $d' < d$，則僅需將該籃子分裂（Split），目錄大小維持不變。

解題方法

(一) 靜態雜湊計算與觀念說明

1. 二進位轉十進位與雜湊值計算： 依題意，雜湊函數為 $h(key) = key \bmod 4$。

• $1000_2 = 1 \times 2^3 = 8_{10} \implies 8 \bmod 4 = 0$
• $0000_2 = 0_{10} \implies 0 \bmod 4 = 0$
• $0010_2 = 1 \times 2^1 = 2_{10} \implies 2 \bmod 4 = 2$
• $1001_2 = 1 \times 2^3 + 1 \times 2^0 = 9_{10} \implies 9 \bmod 4 = 1$
• $1011_2 = 1 \times 2^3 + 1 \times 2^1 + 1 \times 2^0 = 11_{10} \implies 11 \bmod 4 = 3$
• $0100_2 = 1 \times 2^2 = 4_{10} \implies 4 \bmod 4 = 0$
• $1110_2 = 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 = 14_{10} \implies 14 \bmod 4 = 2$
• $0111_2 = 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 7_{10} \implies 7 \bmod 4 = 3$

2. 區分至各籃子（每個籃子容量上限為 3 筆資料）：

• Bucket 0（雜湊值 $0$）：Lee (8)、Chen (0)、Chao (4)，共 3 筆（容量達上限已滿）。
• Bucket 1（雜湊值 $1$）：Hwang (9)，共 1 筆。
• Bucket 2（雜湊值 $2$）：Wang (2)、Liao (14)，共 2 筆。
• Bucket 3（雜湊值 $3$）：Lu (11)、Chang (7)，共 2 筆。

3. 以本例說明靜態雜湊（Static Hashing）：

• 固定位址結構：由於雜湊函數為 $\bmod 4$，系統事先配置且固定只有 4 個籃子（Bucket $0 \sim 3$）。
• 溢位問題（Bucket Overflow）：在本例中，Bucket 0 剛好填滿 3 筆資料。若未來再有一筆雜湊值為 $0$ 的資料（例如鍵值為 $12$）要加入，由於籃子無法動態擴充，將立即發生溢位，必須額外建立溢位鏈結串列（Overflow Chain）來存放，導致存取該資料時需多次磁碟/記憶體讀取，降低效能。
• 空間利用率不均：此時 Bucket 1 僅存 1 筆資料（尚有 2 筆空位），空間配置無法隨資料量彈性調節，這正是靜態雜湊的典型限制。

(二) 動態雜湊（可延伸雜湊）逐步建構

• 條件設定：籃子容量最多存 2 筆資料（$c = 2$）。利用二進位鍵值由左至右（最高有效位元 MSB，Prefix）進行動態索引。
• 資料依序插入步驟：

1. 插入 Lee (1000) 與 Chen (0000)：

• 初始全域深度 $d=0$，單一籃子（$d'=0$）。
• 存入兩筆資料，該籃子達到上限 2 筆：[1000 Lee, 0000 Chen]。

2. 插入 Wang (0010)：

• 籃子已滿且 $d'=d=0$，目錄擴充至全域深度 $d=1$（目錄項目：0、1）。
• 籃子依據第 1 位元（MSB）分裂：
• 目錄 0 $\to$ Bucket A（$d'=1$）：[0000 Chen, 0010 Wang]（已滿）
• 目錄 1 $\to$ Bucket B（$d'=1$）：[1000 Lee]

3. 插入 Hwang (1001)：

• MSB 為 1，指向 Bucket B。
• Bucket B 尚有空間，直接存入：[1000 Lee, 1001 Hwang]（已滿）。

4. 插入 Lu (1011)：

• MSB 為 1，指向 Bucket B。此時 Bucket B 已滿且其區域深度 $d'=1$ 等於全域深度 $d=1$。
• 目錄翻倍，全域深度增加為 $d=2$（目錄項目：00、01、10、11）。
• Bucket B 依前兩位元分裂：
• 目錄 10 $\to$ Bucket B（$d'=2$）：[1000 Lee, 1001 Hwang]
• 目錄 11 $\to$ Bucket C（$d'=2$）：[1011 Lu]

核心觀念

本題評量考生對現代資訊通訊技術中「網路架構階層」、「應用服務」及「智慧感測互連」三大概念的層次區隔與範疇界定：

1. 網際網路（Internet）：屬於網路基礎設施（Infrastructure）。指利用 TCP/IP 協定家族，將全球各地不同架構、不同技術的區域網路（LAN）與廣域網路（WAN）相互串聯所形成的「網路之網路」（Network of Networks）。
2. 全球資訊網（World Wide Web, WWW / Web）：屬於建立在 Internet 之上的應用層服務（Application Service）。由 Tim Berners-Lee 提出，以超文件傳輸協定（HTTP/HTTPS）、超文件標示語言（HTML）及統一資源定位符（URL）為技術基石，透過超連結（Hyperlink）提供分散式的圖文多媒體資訊存取與瀏覽。
3. 物聯網（Internet of Things, IoT）：屬於 Internet 的延伸應用與實體感知整合（Extended Ecosystem）。將傳統僅連接電腦、伺服器或智慧手機的網際網路，延伸至具備感測、辨識、運算與通訊能力的各式實體物件（如感測器、RFID、家電、車載裝置），透過機器對機器（M2M）通訊實現環境感知、資料彙整與智慧化控制。

解題方法

針對本題 10 分的申論/簡答配分，應採取「定義說明 $\rightarrow$ 多維度比較表格 $\rightarrow$ 階層涵蓋關係圖解」之三段式架構：

1. 先破題定義：各用 1 至 2 句話精準指出三者的技術本質（基礎建設 vs. 資訊應用服務 vs. 感知擴展架構）。
2. 結構化對比（表格化）：從「架構層級」、「核心協定與技術」、「連接對象」、「傳輸內容」四大構面進行水平對照，條理分明便於閱卷委員給分。
3. 釐清從屬與包容性：點出「WWW 是 Internet 上的眾多服務之一」與「IoT 是以 Internet（及其他無線通訊）為骨幹傳輸神經的實體延伸」。

選項分析

本題為非選擇題（申論／簡答題），無選擇題選項。以下就閱卷評分之核心概念重點進行辨析：

• 網際網路（Internet）之正確認知：答題時不可將其窄化為「網頁」，其涵蓋網路層、傳輸層至應用層底層通訊架構，是所有網路應用（包括 Email、FTP、DNS、VoIP、Web 等）的骨幹平台。
• 全球資訊網（WWW）之正確認知：僅為 Internet 眾多應用服務之一。將「上網（Access Internet）」等同於「瀏覽網頁（Surf the Web）」是典型觀念混淆，作答時必須明確指出兩者的「底層架構與上層服務」從屬關係。
• 物聯網（IoT）之正確認知：並非獨立於現有網路之外的全新實體網路，其網路層核心依然依賴 Internet（包含 IPv6 等技術）及各類短距離通訊（ZigBee、Bluetooth、Wi-Fi、LoRa），其突破點在於「終端節點由人所操作的終端，擴展至具備感知能力的客觀萬物」。

解題技巧

1. 形象化比喻記憶法（精準破題）：

• Internet 猶如「公路系統」：包含柏油路面、高架橋、交通號誌等底層基礎建設。
• WWW 猶如跑在公路上的「客運巴士」：運送的是特定的乘客與圖文貨物（超文件資訊），是公路上的眾多車輛之一（其他還有郵務車 Email、貨車 FTP）。

核心觀念

1. 候選鍵（Candidate Key）與屬性分類：

• 主屬性（Prime Attribute / 關鍵欄位）：包含於任一候選鍵中的欄位。
• 非主屬性（Non-prime Attribute / 非關鍵欄位）：不屬於任何候選鍵的欄位。

2. 第二正規化（2NF）：

• 關連已符合第一正規化（1NF）。
• 消除部分功能相依（Partial Functional Dependency）：每個「非主屬性」都必須完全功能相依於候選鍵，不可僅相依於候選鍵的真子集。

3. 第三正規化（3NF）：

• 關連已符合第二正規化（2NF）。
• 消除遞移功能相依（Transitive Functional Dependency）：不可存在非主屬性藉由另一個非主屬性間接相依於候選鍵（即若 $X \rightarrow Y$ 為非 trivial FD，則 $X$ 必須為超鍵（Superkey），或 $Y$ 必須為主要屬性）。

解題方法

步驟一：求原始關連的候選鍵與屬性分類

給定關連 $R(A, B, C, D, E)$，功能相依集合 $F = \{CE \rightarrow ABD,\ A \rightarrow D,\ E \rightarrow B\}$。

1. 尋找候選鍵：

• 檢視 $F$ 中所有相依關係的右側（決定值）：$A, B, D$ 皆曾出現在右側，而 $C$ 與 $E$ 從未出現在任何相依關係的右側。
• 依據功能相依性質，從未出現在右側的欄位必為候選鍵的必要組成，故候選鍵必包含 $\{C, E\}$。
• 計算閉包 $(CE)^+$： $(CE)^+ = \{C, E\}$ 由 $CE \rightarrow ABD$ 可擴展得： $(CE)^+ = \{A, B, C, D, E\}$
• 由於 $CE$ 之閉包已涵蓋關連的所有欄位，且其真子集閉包：
• $C^+ = \{C\}$
• $E^+ = \{B, E\}$（由 $E \rightarrow B$ 得） 均無法決定所有欄位，因此 $CE$ 具有最小性，為此關連唯一的候選鍵（Candidate Key）。

2. 欄位分類：

• 關鍵欄位（主屬性）：$C, E$
• 非關鍵欄位（非主屬性）：$A, B, D$

(一) 第二正規化（2NF）處理

1. 理由分析：

• 候選鍵為組合鍵 $CE$。
• 檢視功能相依 $E \rightarrow B$：決定者 $E$ 為候選鍵 $CE$ 的真子集，而被決定者 $B$ 為非關鍵欄位。這表示非關鍵欄位 $B$ 僅相依於部分候選鍵，構成了部分功能相依（Partial Functional Dependency），違反 2NF。
• 另一相依 $A \rightarrow D$ 之決定者 $A$ 不是候選鍵的真子集，不構成部分相依。

2. 分解過程：

• 將造成部分相依的屬性獨立拆解為一個新關連，其餘屬性留在原關連中並保留外來鍵連結：
• 獨立部分相依關係：取 $E \rightarrow B$，組成關連 $R_1(B, E)$。
• 剩餘屬性：從原關連扣除被決定的非主屬性 $B$，組成關連 $R_2(A, C, D, E)$。
• 檢驗分解後的關連：
• 在 $R_1(B, E)$ 中，功能相依為 $E \rightarrow B$，候選鍵為 $E$。
• 在 $R_2(A, C, D, E)$ 中，功能相依為 $\{CE \rightarrow AD,\ A \rightarrow D\}$，候選鍵仍為 $CE$。非關鍵欄位 $\{A, D\}$ 均完全相依於 $CE$（因為 $C$ 或 $E$ 單獨皆無法決定 $A$ 或 $D$），不存在部分功能相依。

3. 關鍵欄位標示：

• $R_1$ 之關鍵欄位為：$E$
• $R_2$ 之關鍵欄位為：$C, E$（複合主鍵 $CE$）

(二) 第三正規化（3NF）處理

1. 理由分析：

• 檢視經 2NF 處理後的兩個關連：
• 關連 $R_1(B, E)$：相依關係為 $E \rightarrow B$，決定者 $E$ 為候選鍵（超鍵），已符合 3NF。
• 關連 $R_2(A, C, D, E)$：候選鍵為 $CE$。存在相依鏈 $CE \rightarrow A$ 與 $A \rightarrow D$。

核心觀念

本題評量關聯式資料庫結構化查詢語言（SQL）的核心操作，重點涵蓋：

1. 多資料表連接（Table Join）：以主鍵（Primary Key）與外來鍵（Foreign Key）建立關聯，包含內部連接（INNER JOIN）與外部連接（LEFT OUTER JOIN）的選用時機。
2. 重複資料的消除（Deduplication）：一對多關聯查詢下，使用 DISTINCT 或子查詢（IN / EXISTS）避免重複列出母表實體。
3. 資料群組化與聚合函數（Grouping & Aggregation）：GROUP BY 子句與 COUNT 函數的配合，以及 SELECT 欄位與 GROUP BY 欄位的語法相容性規則。
4. 外部連接與聚合函數的邊界處理：當需要統計「包含 $0$ 次」的事件時，必須使用 LEFT JOIN 搭配「欄位計數」COUNT(欄位名)，而非「列數計數」COUNT(*)。

解題方法

第 (一) 題：年齡大於 $60$ 歲且於 20180101 下單之客戶姓名與地址

1. 資料表關聯與切入點：

• 篩選目標「年齡」位於 客戶 資料表；「訂貨日期」位於 訂單 資料表。
• 兩表透過 身分證字號 關聯。

2. 關鍵邏輯與防重複設計：

• 一位客戶在 20180101 當天可能訂購多筆貨品（在 訂單 資料表產生多筆紀錄）。若僅使用單純的 JOIN，查詢結果會出現重複的客戶資料。
• 為符合關聯式資料庫查詢規範，必須使用 DISTINCT 消除重複列，或利用 WHERE ... IN (子查詢) 僅自 客戶 表單向檢索符合條件之實體。

3. 推薦實作（JOIN 寫法）：

SELECT DISTINCT C.姓名, C.地址
FROM 客戶 C
JOIN 訂單 O ON C.身分證字號 = O.身分證字號
WHERE C.年齡 > 60 
AND O.訂貨日期 = '20180101';

(註：亦可使用子查詢寫法：WHERE 年齡 > 60 AND 身分證字號 IN (SELECT 身分證字號 FROM 訂單 WHERE 訂貨日期 = '20180101'))

第 (二) 題：年齡低於 $20$ 歲客戶之姓名、電話及 2017 年下單次數

1. 題目意圖深入剖析（0 次下單之處理）：

• 題幹要求「找出年齡低於 $20$ 歲的客戶，列出他們的姓名、電話和在 2017 年裡下訂單的次數」。
• 嚴謹的題意解讀應涵蓋「所有」年齡低於 $20$ 歲的客戶。若該名年輕客戶在 2017 年從未下單，其訂單次數應正確顯示為 $0$，而非被整筆過濾排除。
• 為保留下單次數為 $0$ 的客戶，必須以 客戶 表為主表，對 訂單 表進行左外部連接（LEFT JOIN）。

2. 連接條件與篩選條件的位置（ON vs. WHERE）：

• 限制「2017 年」的條件必須放在 LEFT JOIN 的 ON 子句中： $20170101 \le \text{訂貨日期} \le 20171231$
• 若誤將訂貨日期篩選置於 WHERE 子句，因無訂單者的訂貨日期為 NULL，會被 WHERE 條件篩除，導致外部連接退化為內部連接。

3. 聚合計數的正確使用：

• 必須使用 COUNT(O.身分證字號) 或 COUNT(O.貨品編號)。

核心觀念

本題評量新興資訊科技中「分散式帳本技術（Distributed Ledger Technology, DLT）」的核心概念與架構特徵。考生必須掌握：

1. 區塊鏈的架構本質：由點對點（P2P）網路、密碼學雜湊（Cryptographic Hash）、非對稱加密與共識演算法共同組成的「分散式時間戳記帳本」。
2. 區塊鏈的四大本質特色：去中心化（Decentralization）、不可竄改性（Immutability）、透明與可追溯性（Transparency & Traceability）、基於共識機制的自治信任（Consensus & Trustless）。

解題方法

本題配分為 10 分，屬於標準的申論型觀念題。答題策略與版面配置建議如下：

1. 第一部分：定義說明（佔 2～3 分）

• 採「層次化定義法」：從「資料結構特徵」（由包含時間戳記與雜湊值的區塊循序串聯）提升至「分散式系統架構」（去中心化、多節點共享與驗證之帳本系統），避免僅以「比特幣的底層技術」等通俗口語草率帶過。

2. 第二部分：四大特色列舉與深入說明（佔 7～8 分）

• 採「主題標籤＋運作機制＋帶來的效益」三段式論述。
• 挑選最核心、最具區隔度的四項特質，不可將同義概念拆成兩點（例如不可將「可追溯性」與「公開透明」強行拆為各自獨立的兩大特色，以免內容重複單薄）。

選項分析

本題為申論問答題，無既定選項。評閱與得分關鍵剖析如下：

• 定義部分：必須精準提及「密碼學雜湊指針（Hash Pointer）」、「依時間序列串接」與「分散式共識記帳」。若僅回答「是一種網路資料庫」，缺乏密碼學與分散式結構要素，僅能得基本分數。
• 特色一（去中心化）：需說明節點地位對等，去除中介代理人（Intermediary），其核心優勢在於消除「單點失效（Single Point of Failure, SPOF）」風險。
• 特色二（不可竄改性）：需指明利用單向雜湊函數（如 SHA-256）的前後勾稽。若竄改某區塊資料，該區塊的雜湊值即改變，後續所有區塊雜湊值隨之連鎖失效，竄改成本極高，幾不可能成功。
• 特色三（公開透明與歷史可追溯性）：所有參與節點均保留完整帳本副本，每筆交易均有明確時間戳記，自創世區塊（Genesis Block）以來具備完整審計軌跡（Audit Trail）。
• 特色四（共識機制與無信任信任）：透過數學演算法（如 PoW、PoS）達成拜占庭容錯（BFT），讓彼此互不信任的節點在無中央機關擔保下，仍能達成一致性（Consistency）。

解題技巧

1. 關鍵字精準踩點：閱卷委員採「關鍵字計分法」，答題時務必出現「分散式帳本（DLT）」、「雜湊函數（Hash）」、「時間戳記（Timestamp）」、「單點失效（SPOF）」、「共識機制（Consensus Mechanism）」等專業名詞。
2. 避免混淆概念：區塊鏈是底層技術架構，加密貨幣（如比特幣）僅為其應用之一，答題切忌喧賓奪主、通篇只談虛擬貨幣買賣。