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 Techniques），核心概念包含：

1. 靜態雜湊（Static Hashing）：

• 雜湊函數 $h(k)$ 與籃子（Bucket）的總數量在系統初始化時即固定。
• 使用除法雜湊法（Division Method）：$h(key) = key \bmod m$，雜湊值介於 $0$ 到 $m-1$ 之間。
• 若特定籃子內置放的筆數超過其容量上限（Bucket Capacity），會引發碰撞（Collision）​與溢位（Overflow），需透過鏈結法（Overflow Chaining）等方式處理。

2. 動態雜湊（Dynamic Hashing，以可延伸雜湊 Extendible Hashing 為代表）：

• 藉由目錄（Directory）與二進位鍵值的前綴位元（Prefix Bits），使籃子能隨資料量動態增加而進行分裂（Split），避免靜態雜湊產生長溢位鏈或全表重新雜湊（Rehashing）的缺點。
• 核心參數包含全域深度（Global Depth, $D$）（目錄所使用的前綴位元數，目錄項目數為 $2^D$）與各籃子的區域深度（Local Depth, $d$）（該籃子辨識資料所依據的前綴位元數）。
• 當籃子滿載且有新資料欲放入時，若區域深度小於全域深度（$d < D$），僅需將該籃子一分為二並增加區域深度；若 $d = D$，則目錄大小需倍增（全域深度 $D$ 加 $1$）。

解題方法

(一) 鍵值轉換、靜態分配與靜態雜湊特性

步驟 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：Lee ($8$), Chen ($0$), Chao ($4$)，共 3 筆（達上限，未溢位）
• Bucket 1：Hwang ($9$)，共 1 筆
• Bucket 2：Wang ($2$), Liao ($14$)，共 2 筆
• Bucket 3：Lu ($11$), Chang ($7$)，共 2 筆

步驟 3：說明什麼是靜態雜湊（Static Hashing） 以上述分配為例，靜態雜湊的特徵與運作如下：

1. 固定的配置結構：雜湊函數（$\bmod 4$）與實體籃子總數（固定為 4 個）在事前即確定，無論資料總量如何增減，位址空間始終維持 4 個主籃子。
2. 溢位（Overflow）困境：以本例而言，Bucket 0 目前已存放 3 筆資料（達容量上限）。若後續再插入一筆餘數為 $0$ 的新資料（如 $key = 12$），Bucket 0 就會發生溢位（Overflow），必須配置額外的溢位桶（Overflow Bucket）並以指標串接；若資料量劇增，溢位串列過長會使查詢時間從 $O(1)$ 退化為線性搜尋。
3. 儲存效率不均：若預先分配過多籃子會造成記憶體浪費；若分配過少則極易造成嚴重碰撞與溢位。

(二) 動態雜湊（以可延伸雜湊 Extendible Hashing 實作）

每個籃子容量上限為 2 筆資料。採用二進位前綴（Prefix Bits）由高位至低位（由左至右）進行可延伸雜湊：

步驟 1：分析 8 筆資料的前綴分佈

• 前綴為 0 的鍵值有 4 筆：$0000, 0010, 0100, 0111$（超過單一籃子容量 2）
• 前綴為 1 的鍵值有 4 筆：$1000, 1001, 1011, 1110$（超過單一籃子容量 2）
• 擴展至前 2 位元前綴：
• 00：$0000$ (Chen), $0010$ (Wang) $\implies$ 共 2 筆（可收容在容量為 2 的籃子中）
• 01：$0100$ (Chao), $0111$ (Chang) $\implies$ 共 2 筆（可收容在容量為 2 的籃子中）

核心觀念

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

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. 避免混淆概念：區塊鏈是底層技術架構，加密貨幣（如比特幣）僅為其應用之一，答題切忌喧賓奪主、通篇只談虛擬貨幣買賣。