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

核心觀念

本題屬於「資訊技師」考試中「資料結構」與「資料庫系統」基礎核心名詞測驗，主要評量考生對經典電腦科學架構的定義精確度與深度理解：

1. Balanced Tree（平衡樹）：涉及二元搜尋樹（BST）之退化問題與高度控制，核心定理在於確保樹高維持在 $O(\log n)$，避免時間複雜度退化至 $O(n)$。
2. Record in database（資料庫記錄）：涉及資料儲存階層（Data Hierarchy）與關聯式模型（Relational Model）之對應，核心在於描述單一實體個體的資料屬性集合。
3. Perfect hashing（完全雜湊）：涉及雜湊理論中的碰撞（Collision）控制與空間時間權衡，核心在於對靜態鍵值集合達到最差情況 $O(1)$ 的無碰撞映射。
4. Entity-Relationship model（實體關聯模型）：涉及概念資料塑模（Conceptual Data Modeling）理論，核心在於透過實體、屬性、關聯三大抽象元件對現實世界進行語意表達。

解題方法

針對「名詞解釋題」（每小題 5 分，共 20 分），答題結構必須具備閱卷委員期待的三大層次，切忌僅以口語化一句話帶過：

1. 精確學術定義（2 分）：定義其本質、提出者或數學性質。
2. 內部結構與關鍵機制（2 分）：說明核心限制、運作特性（如時間複雜度、構成要素、演算法策略）。
3. 經典範例與實務應用（1 分）：舉出最具代表性的演算法、資料結構或應用場景。

各名詞子題分析

• （一）Balanced Tree：考點在於「高度控制」與「動態調整機制」。若只回答「左右兩邊長得差不多」無法取得滿分，必須明確提及樹高 $h$ 與節點數 $n$ 的對數關係，以及常見的平衡方式（如旋轉操作）。
• （二）Record（in database）：考點在於「資料階層概念」與「關聯式架構的對應」。應指出它在關聯模型中對應為 Tuple（元組）或 Row（列），並說明其由欄位（Field/Attribute）組成以代表單一實體實例。
• （三）Perfect hashing：考點在於「Collision-free（無碰撞）」及「最差情況時間複雜度保證為 $O(1)$」。進階分析需補充「最小完全雜湊（Minimal Perfect Hashing）」之差別，展現專業深度。
• （四）Entity-Relationship model：考點在於「概念資料模型層級」與「三大構成要素」。應指出其提出者（Peter Chen）與圖形符號表示法，並說明其在資料庫設計生命週期中的角色（轉換為關聯綱要）。

解題技巧

1. 版面控制與給分點配置：每小題 5 分，建議書寫行數約 4～6 行，採「條列式（定義、特性、實例）」排版，讓閱卷委員一眼看見關鍵術語。
2. 善用英文專有名詞輔助：在中文名詞後標註精確的英文術語（如 $O(\log n)$、Tuple、Collision-free、Entity/Attribute/Relationship），強化作答專業度。
3. 避開常見陷阱：

• 誤將 Balanced Tree 僅視為 Complete Binary Tree（完全二元樹僅是其中一種結構，AVL 與紅黑樹允許一定程度的高度差）。
• 誤將 Perfect Hashing 視為動態萬用雜湊（Perfect Hashing 主要用於靜態集合，若資料動態異動維持成本極高）。

【答案】

（一）Balanced Tree（平衡樹）

1. 定義：一種藉由特定演算法規則控制節點深度，使任意節點之左右子樹高度差維持在常數範圍內的樹狀搜尋結構。其設計目的在於防止二元搜尋樹因不當插入順序退化為線性串列（Skewed Tree）。
2. 特性與機制：

核心觀念

本題測驗考生對「現代資料治理（Data Governance）」與「數位政府／資料工程」基礎名詞的理解深度。主要涵蓋以下核心觀念與法規標準（以命題當年民國 111 年之標準與規範為準）：

1. 開放資料（Open Data）之定義：依據國際開放知識基金會（Open Knowledge Foundation, OKF）發布之《開放定義》（Open Definition），資料必須具備「技術性開放」（機器可讀、無專有格式限制）與「法律性開放」（允許任何人自由使用、再利用、重新散布，最多僅要求標示出處或以相同方式分享）。在國內實務上，則參照行政院發布之「政府資料開放作業原則」與「政府資料開放授權條款（OGDL）」。
2. 公共資料（Public Data）之定義：指由政府機關或公共組織基於公權力、法定職責所產製、蒐集，並依法向公眾揭露之資料（如依《政府資訊公開法》主動公開或人民申請提供之資料）。其本質在於落實施政透明與民眾知的權利。
3. 兩者之本質差異：包含「資料來源範疇」、「資料技術格式（機器可讀性）」、「授權許可與再利用權利」及「取得門檻／成本」。

解題方法

申論此題時，切入點不可僅停留在字面翻譯，必須採「定義拆解 $\to$ 核心要件檢驗 $\to$ 多維度矩陣比較 $\to$ 兩者交集關係」的標準論述架構：

1. 分別界定名詞內涵：

• 闡明 Open Data 的技術條件（結構化、開放格式）與法律條件（開放授權）。
• 闡明 Public Data 的行政與法制基礎（資訊公開、行政透明、公共利益）。

2. 架構化對比差異：從「來源主體」、「技術格式」、「法律授權與再利用權」、「取得成本與管道」、「政策目的」五大面向切入，並佐以比較表格，使閱卷委員一目了然。
3. 點出邏輯集合關係：論述「開放政府資料（Open Government Data, OGD）是 Public Data 與 Open Data 的交集」，釐清「公開不等於開放」的關鍵盲點。

選項分析

本題為專技高考之申論題，非選擇題型。在評閱評分標準上，若考生答題僅寫出一般性字面翻譯，難以取得高分；閱卷要點主要檢視考生能否精準剖析以下面向：

• 未提及「開放授權（Open License）」：若僅回答「免費給大眾看」，缺乏著作權、再利用（Re-use）及商業改作的授權說明，將大幅失分。
• 未提及「機器可讀（Machine-readable）」：若未將 PDF、掃描圖檔等「人類可讀格式」與 CSV、JSON、XML 等「結構化機器可讀格式」進行區隔，無法展現資訊技師的技術專業。
• 誤認 Open Data 僅限於政府產製：漏掉企業、社群、科研組織亦可發布 Open Data（如 OpenStreetMap、開源社群資料集），定義不夠全面。

解題技巧

1. 判斷竅門（黃金準則）：

• Open Data 的關鍵字：結構化、機器可讀（Machine-readable）、開放授權（如 CC BY、OGDL）、允許商業改作、API 介接。
• Public Data 的關鍵字：政府產製、法定義務公開（如《政府資訊公開法》）、施政透明、人類可讀（Human-readable）、受著作權保護且限制改作。

2. 常見陷阱：

• 誤以為「放在網路上公開供人瀏覽的政府資料」就是 Open Data。例如：政府將預算書以 PDF 掃描檔放在官網供民眾下載，這屬於 Public Data，但因不具備機器可讀性且未釋出開放再利用授權，絕非 Open Data。

3. 記憶架構（文氏圖概念）：

• Public Data 包含未開放格式的政府公開資訊；Open Data 包含民間發布的開源資料；

核心觀念

1. 氣泡排序法（Bubble Sort）定義： 屬於比較排序法（Comparison Sort）中的交換排序類別。其基本運作原理為：由陣列前端開始，重複走訪欲排序的數列，依序檢視「相鄰的兩個元素」，若兩者順序與目標排序方向（如遞增）不符則予以對調（Swap）。每完成一輪（Pass）的比較與交換，未排序區間中的「極值」（最大值或最小值）就會如同水中氣泡浮出水面般，移動至數列的最終正確位置。
2. 穩定性（Stability）與空間特性：

• 穩定排序（Stable Sort）：當兩相鄰元素鍵值相等時，若演算法不對其進行交換，即可保證相同鍵值的元素在排序前後的相對順序維持不變。
• 原地排序（In-place Sort）：僅需常數等級的輔助記憶體空間進行元素交換，額外空間複雜度為 $O(1)$。

3. 效能分析數學基礎：

• 等差級數求和公式： $\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$
• 漸近符號（Big-O）定義：若存在正實數常數 $c$ 與正整數 $n_0$，使得所有 $n \ge n_0$，演算法的基本運算次數 $T(n) \le c \cdot f(n)$ 均成立，則稱 $T(n) \in O(f(n))$。

解題方法

本題為典型的申論題型，解題步驟劃分為三大部分：虛擬碼設計（含提早結束最佳化機制）、實例追蹤（Tracing）與漸近效能（Big-O）嚴謹推導。

一、虛擬碼表示（Pseudo-code）

考量國家考試評分標準，提供具備「旗標檢驗（Flag Optimization）」的氣泡排序虛擬碼，以完整體現最佳情況（Best Case）之效能：

Algorithm BubbleSort(A, n)
 Input: 陣列 A（索引為 0 至 n - 1），長度 n >= 1
 Output: 由小至大排序完成之陣列 A

 for i = 0 to n - 2 do
 swapped = false
 // 第 i 回合：將未排序區間的最大值推至索引 n - 1 - i
 for j = 0 to n - 2 - i do
 if A[j] > A[j + 1] then
 // 交換相鄰元素
 temp = A[j]
 A[j] = A[j + 1]
 A[j + 1] = temp
 swapped = true
 end if
 end for
 // 若此回合完全未發生交換，代表數列已排序完畢，提早終止
 if swapped == false then
 break
 end if
 end for
 return A

二、實例說明（舉例示範）

給定包含 5 個元素的未排序陣列 $A = [5, 1, 4, 2, 8]$，長度 $n = 5$，欲進行遞增排序：

• 第 1 回合（Pass 0, $i = 0$）：內迴圈 $j$ 從 $0$ 到 $3$（比較 $n - 1 - 0 = 4$ 次）：

1. $j = 0$：比較 $A[0]=5$ 與 $A[1]=1$。因 $5 > 1$，交換 $\rightarrow [1, 5, 4, 2, 8]$
2. $j = 1$：比較 $A[1]=5$ 與 $A[2]=4$。因 $5 > 4$，交換 $\rightarrow [1, 4, 5, 2, 8]$
3. $j = 2$：比較 $A[2]=5$ 與 $A[3]=2$。因 $5 > 2$，交換 $\rightarrow [1, 4, 2, 5, 8]$
4. $j = 3$：比較 $A[3]=5$ 與 $A[4]=8$。因 $5 < 8$，不交換 $\rightarrow [1, 4, 2, 5, 8]$

• 結果：最大值 $8$ 已定位至末端 $A[4]$；有發生交換，swapped = true，繼續下一回合。

• 第 2 回合（Pass 1, $i = 1$）：內迴圈 $j$ 從 $0$ 到 $2$（比較 $3$ 次）：

1. $j = 0$：比較 $A[0]=1$ 與 $A[1]=4$。不交換 $\rightarrow [1, 4, 2, 5, 8]$
2. $j = 1$：比較 $A[1]=4$ 與 $A[2]=2$。因 $4 > 2$，交換 $\rightarrow [1, 2, 4, 5, 8]$
3. $j = 2$：比較 $A[2]=4$ 與 $A[3]=5$。不交換 $\rightarrow [1, 2, 4, 5, 8]$

• 結果：次大值 $5$ 已定位至 $A[3]$；有發生交換，繼續下一回合。

• 第 3 回合（Pass 2, $i = 2$）：內迴圈 $j$ 從 $0$ 到 $1$（比較 $2$ 次）：

1. $j = 0$：比較 $A[0]=1$ 與 $A[1]=2$。不交換 $\rightarrow [1, 2, 4, 5, 8]$
2. $j = 1$：比較 $A[1]=2$ 與 $A[2]=4$。不交換 $\rightarrow [1, 2, 4, 5, 8]$

• 結果：此回合未發生任何交換（swapped == false），觸發提早跳出機制（break）。
• 最終排序結果：$[1, 2, 4, 5, 8]$。

三、效能分析（Big-O 推導過程）

以元素比較次數（Comparisons）與交換次數（Swaps）作為主要計量指標：

核心觀念

本題考查關聯式資料庫的三種操作：

• 選擇（selection）：依條件篩選資料列，記為 $\sigma$。
• 投影（projection）：取出指定欄位，記為 $\pi$。
• 笛卡兒積（Cartesian product）：將兩個表的每一列互相配對，記為 $\times$。

SQL 的 SELECT 指定輸出欄位，WHERE 設定篩選條件；FROM 同時列出兩個表、卻沒有連接條件時，會形成笛卡兒積。一般 SQL 查詢會保留重複列，除非明確使用 DISTINCT。

解題方法

（一）SQL 語法一

依 WHERE 條件篩選 Part_number 落在 $1000$ 至 $5000$ 的列，再只輸出 Supplier：

因此包含選擇與投影操作。

（二）SQL 語法二

FROM Part_needs, Parts_inventory 列出兩個表，但沒有指定兩表間的連接條件，因此先形成笛卡兒積；接著以 Quantity ≤ 10 篩選，再輸出 Supplier：

因此包含笛卡兒積、選擇與投影操作。

（三）以 Table 1 執行語法一

符合 $1000 \leq \text{Part\_number} \leq 5000$ 的零件編號依序為：

核心觀念

本題出自資料探勘（Data Mining）領域之**關聯規則探勘（Association Rule Mining）**與 Apriori 演算法，為資訊技師與高考資訊類科歷年極高頻率之基本計算題型。解題所依據之核心定義與公式如下：

1. 交易資料庫（Transaction Database）： 設全體交易集合為 $D$，交易總筆數為 $|D|$。本題中 $|D| = 6$（交易 $A$ 至 $F$）。
2. 支援度計數（Support Count / Frequency）： 項目集（Itemset）$X$ 在交易資料庫中出現的交易次數，記為 $\sigma(X)$ 或 $\text{count}(X)$。
3. 支援度（Support）： 項目集 $X$ 在全體交易中出現的機率／比例： $\text{Support}(X) = P(X) = \frac{\sigma(X)}{|D|}$
4. 頻繁項目集（Frequent Itemsets）： 若項目集 $X$ 的支援度大於或等於預設之最低支援度門檻值（Minimum Support Threshold, $\text{min\_sup}$），即 $\text{Support}(X) \ge \text{min\_sup}$，則稱 $X$ 為頻繁項目集。

• Apriori 特性（向下封閉性，Downward-Closure Property）：頻繁項目集的所有非空子集（Subsets）亦必須為頻繁項目集；反之，若某項目集為非頻繁（Infrequent），則其所有超集（Supersets）必為非頻繁，可直接剪枝（Prune）。

5. 關聯規則之支援度與信賴度（Support & Confidence）： 對於關聯規則 $X \rightarrow Y$（其中 $X \cap Y = \emptyset$）：

• 支援度（Support）：包含前項與後項聯集 $X \cup Y$ 的交易比例： $\text{Support}(X \rightarrow Y) = P(X \cup Y) = \frac{\sigma(X \cup Y)}{|D|}$
• 信賴度（Confidence）：在購買 $X$ 的條件下，同時購買 $Y$ 的條件機率： $\text{Confidence}(X \rightarrow Y) = P(Y \mid X) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} = \frac{\sigma(X \cup Y)}{\sigma(X)}$

解題方法

資料庫基礎統計

全體項目宇集為 $U = \{\text{bread}, \text{milk}, \text{diapers}, \text{juice}, \text{eggs}, \text{beer}\}$，交易總筆數 $|D| = 6$。各交易內容如下：

• $A = \{\text{bread}, \text{milk}, \text{diapers}, \text{juice}\}$
• $B = \{\text{bread}, \text{milk}, \text{diapers}, \text{eggs}\}$
• $C = \{\text{milk}, \text{diapers}, \text{beer}, \text{eggs}\}$
• $D = \{\text{bread}, \text{beer}\}$
• $E = \{\text{milk}, \text{diapers}, \text{eggs}, \text{juice}\}$
• $F = \{\text{milk}, \text{diapers}, \text{beer}\}$

（一）求產品 $\text{diapers}$ 的 support 值

1. 計算支援度計數 $\sigma(\{\text{diapers}\})$： 檢驗包含 $\text{diapers}$ 的交易：

• $A$：包含
• $B$：包含
• $C$：包含
• $D$：無
• $E$：包含
• $F$：包含

因此，$\sigma(\{\text{diapers}\}) = 5$ 次（共出現在 $A, B, C, E, F$）。

2. 計算支援度： $\text{Support}(\{\text{diapers}\}) = \frac{\sigma(\{\text{diapers}\})}{|D|} = \frac{5}{6} \approx 0.8333\text{（即 } 83.33\% \text{）}$

（二）設定 support threshold 為 $0.6$，找出所有的 frequent itemsets

門檻值 $\text{min\_sup} = 0.6$，代表支援度計數門檻值為： $\text{min\_count} = |D| \times \text{min\_sup} = 6 \times 0.6 = 3.6$ 因為交易次數必須為整數，故項目集出現的交易次數必須大於等於 $4$ 次（$\frac{4}{6} \approx 0.667 \ge 0.6$；若為 $3$ 次則 $\frac{3}{6} = 0.5 < 0.6$）。

採用 Apriori 演算法 逐層推導：

1. 候選 1-項目集（Candidate 1-itemsets, $C_1$）頻率統計：

• $\{\text{bread}\}$：出現在 $A, B, D$ $\rightarrow \sigma = 3$（未達標，剪枝）
• $\{\text{milk}\}$：出現在 $A, B, C, E, F$ $\rightarrow \sigma = 5$（$\ge 4$，保留）
• $\{\text{diapers}\}$：出現在 $A, B, C, E, F$ $\rightarrow \sigma = 5$（$\ge 4$，保留）
• $\{\text{juice}\}$：出現在 $A, E$ $\rightarrow \sigma = 2$（未達標，剪枝）
• $\{\text{eggs}\}$：出現在 $B, C, E$ $\rightarrow \sigma = 3$（未達標，剪枝）
• $\{\text{beer}\}$：出現在 $C, D, F$ $\rightarrow \sigma = 3$（未達標，剪枝）

頻繁 1-項目集（$L_1$）： $L_1 = \{\{\text{milk}\}, \{\text{diapers}\}\}$