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

核心觀念與解題方法

本題為名詞解釋，涵蓋資料探勘、排序、統計分類、資料庫索引與正規化，以及字串資料結構。作答時，逐一說明名詞的定義、核心性質與主要用途；容易混淆的概念則補充比較或例子。

（一）Apriori-property

Apriori-property（先驗性質）是關聯規則探勘中用來剪枝的性質：

若一個項目集是頻繁項目集，則它的每一個非空子集也必為頻繁項目集。

等價地說，若某個項目集不頻繁，則包含它的所有更大項目集都不可能頻繁。

設最小支持度門檻為 $\text{minsup}$，項目集 $X$ 的支持度為 $\text{support}(X)$。若 $X$ 不滿足 $\text{support}(X)\geq \text{minsup}$，則任何包含 $X$ 的項目集 $Y\supset X$ 均可直接排除。這是 Apriori 演算法逐層產生候選項目集時，減少計數工作的依據。

例如，若 $\{A,B\}$ 不頻繁，則 $\{A,B,C\}$、$\{A,B,D\}$ 等超集都不必再計算支持度。

**解題技巧：**記住「頻繁則子集頻繁；不頻繁則超集不頻繁」。這項性質針對支持度的反單調性，不可誤套到信賴度等其他指標。

（二）Bucket-Sort

Bucket-Sort（桶排序）是將資料依數值範圍分配到多個桶（bucket），在各桶內排序，再依桶的順序串接結果的排序法。

典型流程如下：

1. 根據資料的值域建立多個桶。
2. 將每筆資料放入對應的桶。
3. 分別排序各桶中的資料。
4. 依桶的順序串接，得到排序結果。

若 $n$ 筆資料大致均勻分布於 $k$ 個桶，平均每桶約有 $n/k$ 筆；採用桶內比較排序時，平均時間可達 $O(n+k)$（適當選擇桶數且分布均勻時）。最壞情況下，若資料集中在同一桶，時間可能退化為桶內排序的時間，例如使用比較排序時為 $O(n\log n)$。空間需求通常為 $O(n+k)$。

**解題技巧：**桶排序的高效率仰賴資料範圍可切分、分布較均勻；不可把平均效率直接當成任何輸入下的保證。

（三）False-negative（type-2 error）

False-negative（偽陰性、第二型錯誤）是指實際狀態為陽性，檢測或分類結果卻判定為陰性。

以假設檢定表示，虛無假設 $H_0$ 為真時拒絕它，稱為第一型錯誤；$H_0$ 為假時未拒絕它，稱為第二型錯誤。第二型錯誤機率記為 $\beta$，檢定力（power）為：

在疾病篩檢中，病人被判定為未患病即為偽陰性；在垃圾郵件分類中，垃圾郵件被判定為正常郵件也屬偽陰性。

**解題技巧：**以「實際陽性、判定陰性」記憶 false-negative；勿與 false-positive（實際陰性、判定陽性）混淆。

（四）叢集索引

叢集索引（clustered index）是依索引鍵值的順序，安排資料記錄在資料檔中的實體儲存順序的索引。由於資料本身通常只能依一種順序排列，一個資料表通常至多有一個叢集索引。

叢集索引適合用於依索引鍵進行範圍查詢或排序輸出，因為相鄰鍵值的記錄在實體儲存上也較接近，可減少磁碟存取。若索引鍵不是唯一值，資料庫系統會以額外資訊或內部排序方式處理相同鍵值的記錄。

相對地，非叢集索引另行儲存索引鍵及指向資料列的參照，不決定資料列本身的實體排列順序；同一資料表可以建立多個非叢集索引。

核心觀念

最大堆積（max-heap）是一棵完全二元樹，且每個節點的鍵值都不小於其子節點。以陣列表示時，若使用 1 起算的索引，索引 $i$ 的父節點為 $\lfloor i/2\rfloor$，左、右子節點分別為 $2i$、$2i+1$。

插入新值時，先放在陣列末端以維持完全二元樹形狀，再將它與父節點比較；若新值較大，就一路交換（上浮），直到符合最大堆積性質。堆積排序輸出最大值時，先取出根節點，再將末端元素移到根部並向下調整（下沉）。

解題方法

（一）依序插入並上浮

下表中的陣列採層序排列；每次插入後，括號內列出上浮交換。

核心觀念

Naïve Bayes（樸素貝氏分類）利用貝氏定理，計算測試資料在各類別下的後驗機率，再選擇機率較大的類別。它假設在已知類別後，各屬性彼此條件獨立：

其中 $P(C)$ 是類別的先驗機率，$P(x_i\mid C)$ 是屬性值在該類別中的條件機率。本題測試資料為「Give Birth = yes、Can Fly = no、Live in Water = yes、Have Legs = no」。

解題方法

表中共有 20 筆資料，其中 mammals 有 7 筆，non-mammals 有 13 筆，因此：

計算 mammals 的分數

在 7 筆 mammals 中，Give Birth = yes 有 6 筆、Can Fly = no 有 6 筆、Live in Water = yes 有 2 筆、Have Legs = no 有 2 筆：

計算 non-mammals 的分數

核心觀念

本題考查關聯式資料庫的分組聚合、日期篩選、自我關聯，以及以「所有日期均相同」表示集合相等。Location.LPID 指向上層位置的 Location.LID，因此可用自我連結取得上層區域。

以下以標準 SQL 表示；假設 Date 是日期型別，且「共同出現在同樣上層區域」是指兩支電話在同一天、同一上層區域都至少有一筆簡訊紀錄。此題不涉及法條。

（一）同日於 LID = 10 出現超過兩次的電話號碼

SELECT phoneNum
FROM Message
WHERE LID = 10
 AND Date = '2021-05-10'
GROUP BY phoneNum
HAVING COUNT(*) > 2;

先篩選指定位置與日期，再依電話號碼分組；HAVING COUNT(*) > 2 保留當日紀錄筆數至少為 3 的號碼。「超過兩次」不等於「兩次以上」。

（二）指定期間內，與 09XX555666 在 LID = 10 的到訪日期完全相同之電話號碼

WITH TargetDays AS (
 SELECT DISTINCT Date
 FROM Message
 WHERE LID = 10
 AND phoneNum = '09XX555666'
 AND Date BETWEEN '2021-05-10' AND '2021-05-17'
),
OtherDays AS (
 SELECT DISTINCT phoneNum, Date
 FROM Message
 WHERE LID = 10
 AND phoneNum <> '09XX555666'
 AND Date BETWEEN '2021-05-10' AND '2021-05-17'
)
SELECT o.phoneNum
FROM OtherDays AS o
GROUP BY o.phoneNum
HAVING COUNT(*) = (SELECT COUNT(*) FROM TargetDays)
 AND NOT EXISTS (
 SELECT 1
 FROM TargetDays AS t
 WHERE NOT EXISTS (
 SELECT 1
 FROM OtherDays AS x
 WHERE x.phoneNum = o.phoneNum
 AND x.Date = t.Date
 )
 );

「到訪日期均相同」表示兩者在期間內的日期集合相等，而非單純有任一天重疊。先用 DISTINCT 排除同日多筆簡訊造成的重複日期，再以 NOT EXISTS 確認目標電話的每個日期都出現在候選電話的日期集合中。日期數量相等則可排除候選電話另有額外日期的情況。

（三）指定電話於期間內出現過的所有上層區域

SELECT DISTINCT parent.LID, parent.Lname
FROM Message AS m
JOIN Location AS child
 ON m.LID = child.LID
JOIN Location AS parent
 ON child.LPID = parent.LID
WHERE m.phoneNum = '09XX555666'
 AND m.Date BETWEEN '2021-05-10' AND '2021-05-17'
 AND child.LPID <> 0;