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

核心觀念

選擇排序法（selection sort）的作法是：每一回合都在尚未排序的部分中找出最小值，與該部分的第一個元素交換。完成一回合後，最前面已排序的範圍便增加一個元素。

本題數列共有 $6$ 個元素，因此需要進行 $5$ 回合；最後剩下的元素自然位於正確位置。排序過程中，已排序區由左至右逐步擴大。

解題方法與排序過程

初始數列為：

**第 1 回合：**在全部元素中找最小值。最小值為 $3$，與第一個元素 $67$ 交換：

此時 $3$ 已排定。

**第 2 回合：**在尚未排序的部分 $[25,\ 67,\ 79,\ 88,\ 6]$ 中找最小值。最小值為 $6$，與該部分第一個元素 $25$ 交換：

此時 $3、6$ 已排定。

**第 3 回合：**在尚未排序的部分 $[67,\ 79,\ 88,\ 25]$ 中找最小值。最小值為 $25$，與 $67$ 交換：

核心觀念

$2$-$3$-$4$ 樹是一種自平衡搜尋樹，也稱為階數為 $4$ 的 B 樹。每個節點可存放一至三個由小到大排列的鍵值，並依鍵值數量分成三種：

• 2-節點：有 $1$ 個鍵值、$2$ 個子樹。
• 3-節點：有 $2$ 個鍵值、$3$ 個子樹。
• 4-節點：有 $3$ 個鍵值、$4$ 個子樹。

各子樹的鍵值範圍由節點中的鍵值決定。例如，含有 $[a,b]$ 的 3-節點，其三個子樹依序存放小於 $a$、介於 $a$ 與 $b$ 之間、大於 $b$ 的鍵值。

$2$-$3$-$4$ 樹須符合以下性質：

1. 每個節點最多有 $3$ 個鍵值，最多有 $4$ 個子樹。
2. 除根節點外，每個節點至少有 $1$ 個鍵值。
3. 所有葉節點都位於相同深度，因此樹高保持平衡。
4. 鍵值遵守搜尋樹的大小順序。

解題方法

題目未指定插入時採用自底向上或自頂向下的分裂程序；這兩種標準程序插入相同數列後，都會得到相同的最終鍵值配置。依序插入 $10$ 至 $100$，節點若超過 $3$ 個鍵值，就將中間鍵值提升至父節點，並把其餘鍵值分成左右兩個節點。

關鍵分裂步驟如下：

核心觀念

決策樹（Decision Tree）是一種用樹狀結構表示分類或預測規則的監督式學習方法。它從已標記結果的訓練資料中學習如何依據特徵逐步切分資料，最後預測新資料所屬的類別或數值。

決策樹由下列部分組成：

• 根節點：第一個用來切分資料的特徵或條件。
• 內部節點：後續的特徵測試，例如「年齡是否大於 30 歲」。
• 分支：測試結果所導向的路徑。
• 葉節點：輸出預測結果；分類樹輸出類別，迴歸樹輸出數值。

每一條從根節點走到葉節點的路徑，都能轉寫成一條「若……則……」的規則。

解題方法

回答此題可依「定義、建樹方式、評估指標、實例、優缺點」說明：

1. 選擇切分特徵：在目前節點的資料中，挑選能使子集合更純的特徵。常見方法包括資訊增益、增益率與基尼不純度。
2. 依特徵值切分資料：類別特徵可依類別分支；連續特徵常以門檻值切分，例如「年齡 $\leq 30$」與「年齡 $>30$」。
3. 遞迴建立子樹：對各分支重複選擇切分特徵，直到符合停止條件，例如資料已足夠純、樣本數太少或達到最大深度。
4. 剪枝：移除對預測幫助有限的枝節，降低過度配適（overfitting），提升對新資料的泛化能力。

以 ID3 演算法為例，可用熵與資訊增益評估切分效果。若資料集合 $S$ 中有 $k$ 個類別，熵為：

以特徵 $A$ 切分後的資訊增益為：

核心觀念

關聯規則是資料探勘中，用來找出資料項目之間經常共同出現關係的方法。常見應用包括購物籃分析，例如分析顧客購買某些商品時，是否也常購買另一項商品。

一筆交易可表示為一個項目集合。關聯規則寫成：

其中 $X$ 稱為前項（antecedent），$Y$ 稱為後項（consequent），且 $X \cap Y = \varnothing$。規則表示：在包含 $X$ 的交易中，常有交易也包含 $Y$；它描述資料中的共現關係，不代表因果關係。

重要衡量指標

設資料共有 $N$ 筆交易，$support(X)$ 表示包含項目集合 $X$ 的交易筆數占全部交易的比例。

• 支持度（support）：$X$ 與 $Y$ 同時出現的比例。

• 信賴度（confidence）：在包含 $X$ 的交易中，也包含 $Y$ 的比例。

• 提升度（lift）：衡量 $X$ 與 $Y$ 的共同出現程度相較於彼此獨立時的差異。

$lift>1$ 表示正向關聯；$lift=1$ 表示兩者獨立；$lift<1$ 表示負向關聯。支持度與信賴度常用來篩選規則；提升度則可避免只因後項本身很常見，就誤以為規則特別有力。

解題方法與例子

以 5 筆購物交易為例：

分析規則「牛奶 $\rightarrow$ 麵包」：

核心觀念

本題考查 SQL 的分組與彙總、群組篩選、子查詢及去除重複值。

• GROUP BY 依指定欄位將資料分組。
• COUNT(*) 計算每組的資料筆數。由於主鍵為 (E_ID, P_ID)，同一員工對同一專案最多只有一筆紀錄，因此每個專案的紀錄筆數就是投入該專案的員工人數。
• HAVING 用來篩選分組後的結果；WHERE 則是在分組前篩選個別資料列。
• DISTINCT 用來去除查詢結果中的重複值。

解題方法

（一）找出投入員工人數超過 50 人的專案

先依專案代碼 P_ID 分組，再計算每組的紀錄筆數。因為條件「超過 50 人」是針對分組後的人數，因此使用 HAVING 篩選：

SELECT P_ID, COUNT(*) AS EMPLOYEE_COUNT
FROM WORKS
GROUP BY P_ID
HAVING COUNT(*) > 50;

COUNT(*) > 50 是嚴格大於，因此恰有 50 位員工的專案不會列入結果。

（二）找出投入 PJ2255 且時數最高的員工代碼

先在 P_ID = 'PJ2255' 的紀錄中找出最大時數，再取出時數等於該最大值的員工代碼。使用 DISTINCT 確保結果不重複：

核心觀念

本題考查將 ERD 轉換為關聯綱要，以及依關係基數選擇轉換方式：

• 辦公室與教授是一對一關係，而且雙方都必須參與：每位教授恰有一間辦公室，每間辦公室也恰屬於一位教授。
• 教授與課程是多對多關係：教授可教多門課，課程也可由多位教授合授。
• 圖中底線屬性是各實體的主鍵：辦公室代碼、教授代碼、課程代碼。

解題方法

一對一且雙方都必須參與時，可將兩個實體合併為一個關聯綱要。這樣每筆資料都同時表示一位教授及其唯一辦公室；辦公室代碼設為唯一值，便能避免一間辦公室配給多位教授。

多對多關係則新增一個「授課」關聯綱要，將教授代碼與課程代碼組成複合主鍵，並各自作為外來鍵。

關聯綱要

教授辦公室

教授辦公室（教授代碼，教授姓名，教授電話，辦公室代碼，大樓名稱）

• 主鍵：教授代碼
• 候選鍵：辦公室代碼，並設為 UNIQUE
• 外來鍵：無
• 說明：合併教授與辦公室兩個實體。每筆資料包含一位教授及其一間辦公室；教授代碼及辦公室代碼皆唯一，因此兩者一對一，且雙方均有對應資料。