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

核心觀念

本題考查排序演算法的時間複雜度、資料初始有序程度對實際執行時間的影響，以及 Quick Sort 的 pivot 選取如何影響分割平衡。

• Insertion Sort 的時間取決於資料中的逆序數；越接近有序，所需移動越少。最佳情況為 $\Theta(n)$，平均與最差情況為 $\Theta(n^2)$。
• Merge Sort 不受初始排列影響，最佳、平均及最差時間皆為 $\Theta(n\log n)$；但通常需要 $\Theta(n)$ 額外空間。
• Quick Sort 平均時間為 $\Theta(n\log n)$，最差為 $\Theta(n^2)$；效能關鍵在 pivot 是否能將資料切分得平衡。

解題方法

（一）近乎有序資料的效能比較

資料筆數為 $n=10^6$，其中約九成已排序。假設這表示資料整體只需少量插入或移動即可恢復排序，則 Insertion Sort 的執行成本可用逆序數 $I$ 估計：比較與移動量大致與 $n+I$ 成正比，而不是一律達到 $n^2$。

若另外假設其餘一成資料是分散在整筆資料中的隨機亂序元素，且這些元素各自可能與約九成的已排序元素形成逆序，則逆序數量級可達 $0.1n\times0.9n=\Theta(n^2)$。因此「90% 已排序」本身不足以保證 Insertion Sort 只有線性時間；實際效能仍取決於亂序元素的位置與逆序數。

以 $n=10^6$ 估算，$n^2=10^{12}$，而 $n\log_2 n\approx 2.0\times10^7$。因此，若亂序部分足以造成大量逆序，Insertion Sort 的時間成本會遠高於兩種 $n\log n$ 排序法。

最適合的選擇：Merge Sort。 題目未精確界定「約 90% 已排序」如何分布，不能單憑此比例保證逆序數少，也不能保證 Quick Sort 的 pivot 分割平衡。Merge Sort 有 $\Theta(n\log n)$ 的最壞時間保證，效能不受輸入順序影響，適合作為穩定可靠的選擇。若已確認逆序數很少，Insertion Sort 才可能憑藉低額外空間與近線性執行時間勝出。

核心觀念

Dijkstra 演算法適用於邊權重非負的有向圖。從來源點 $s$ 出發，演算法以暫定距離最小的未確定頂點為順序，逐步確定最短距離，並記錄各頂點的前驅，以形成最短路徑樹（SPT）。

權重改變後，舊的距離標籤與前驅關係可能失效。若每次都從頭執行 Dijkstra，需重新掃描圖並重建整棵 SPT，無法利用上次計算結果；但這是「重複計算成本高」，不是 Dijkstra 在動態權重下必然無法執行。

（一）權重變動時的增量式更新

解題方法

維護目前的最短距離 $d[v]$、前驅 $\operatorname{pred}[v]$，以及 SPT。權重更新時，只處理受影響的邊與頂點，並將新的距離改善沿出邊傳播。

對一條更新邊 $(u,v)$，新權重為 $w'(u,v)$：

1. 權重減少或新增邊：以 $d[u]+w'(u,v)$ 檢查是否改善 $d[v]$。若改善，更新 $d[v]$ 與前驅，並將 $v$ 放入最小優先佇列。接著反覆取出距離最小的頂點，鬆弛其出邊，直到沒有更短距離可傳播。
2. 權重增加或刪除邊：若該邊不在 SPT 中，原 SPT 的路徑不使用它，原距離維持不變。若它是 SPT 邊，則其子樹內頂點的原最短路徑失效；將受影響子樹標記為待重算，並從未受影響部分的邊界尋找替代路徑，再向子樹內傳播更新。若找不到替代路徑，相關頂點距離設為 $\infty$。

權重增加可能使原本不在 SPT 中的邊成為替代路徑，因此受影響子樹的重算須納入所有可連接該子樹的候選邊。若同一批更新同時包含增減或刪除，應先依更新後的權重處理受影響區域，再傳播距離變化。

正確性與效率

每次鬆弛都檢查候選距離是否較小：

因此，距離改善會沿著可能受影響的路徑傳播。若只有少數邊更新且影響範圍有限，演算法只需處理局部區域；最壞情況下，更新可能影響全圖，成本仍會退化至接近重新執行 Dijkstra。

（二）Fibonacci heap 與 binary heap

令 $|V|$ 為頂點數、$|E|$ 為邊數。使用最小優先佇列執行 Dijkstra 時：

核心觀念

本題考查資料庫隔離等級如何限制並行交易的讀取結果，以及三種常見讀取異常的定義。

• Dirty read（髒讀）：讀取另一交易尚未提交的資料；若該交易回復，讀到的值便從未成為已提交資料。
• Non-repeatable read（不可重複讀）：同一交易對同一筆資料讀取兩次，中間有另一交易修改並提交，因而讀到不同值。
• Phantom read（幻讀）：同一交易以相同搜尋條件執行兩次範圍查詢，中間有另一交易新增或刪除符合條件的資料列，使查詢結果集合改變。

四種隔離等級由弱至強為：Read Uncommitted、Read Committed、Repeatable Read、Serializable。隔離等級愈高，能避免的並行異常愈多。

解題方法

追蹤題目中的兩次 Read(A)，並確認第二次讀取前，T2 的 Write(A=100) 是否已提交。題目表格列出 T2 在第二次讀取前 Commit，但沒有給定 A 的初值，因此以下以 T1 第一次讀到的值為 $A_0$；若 $A_0\ne100$，才會出現不同值。

Read Uncommitted 允許讀取未提交資料，但本題 T2 在 T1 第二次讀取前已提交，因此即使在此等級，第二次讀取也可讀到新值。Read Committed 每次讀取只保證讀到已提交資料，不保證同一交易兩次讀取相同，因此也可讀到 $100$。Repeatable Read 與 Serializable 則保證本例同一筆 A 在 T1 交易內重複讀取時維持原值。

異常現象分析

核心觀念

B+ Tree 的階（order）為 4，表示內部節點最多有 4 個子節點，因而最多有 3 個分隔鍵。除根節點外，內部節點至少有 2 個子節點。葉節點最多有 3 個資料鍵；除根節點外，至少須有 2 個資料鍵。資料鍵只存於葉節點，葉節點依鍵值遞增並以鏈結串接，供範圍查詢循序掃描。

內部節點的分隔鍵採右子樹最小鍵值：分隔鍵 $k$ 表示左側子樹鍵值小於 $k$，右側子樹鍵值大於或等於 $k$。以下依序插入題目所列鍵值，並以此分隔鍵慣例作答。

解題方法與建樹

依序插入 $5,9,12,15,18,21,25,31,33,38$。葉節點超過 3 個鍵時，分裂成兩個葉節點，並將右葉節點的最小鍵值複製至父節點作為分隔鍵；若父節點也溢位，則再向上分裂。

關鍵分裂過程如下：

1. 插入 $15$ 後，葉節點 $[5,9,12,15]$ 溢位，分裂為 $[5,9]$、$[12,15]$，將 $12$ 複製到根節點。
2. 插入 $21$ 後，葉節點 $[12,15,18,21]$ 溢位，分裂為 $[12,15]$、$[18,21]$，將 $18$ 插入根節點。
3. 插入 $31$ 後，葉節點 $[18,21,25,31]$ 溢位，分裂為 $[18,21]$、$[25,31]$，將 $25$ 插入根節點。
4. 插入 $38$ 後，葉節點 $[25,31,33,38]$ 溢位，分裂為 $[25,31]$、$[33,38]$，將 $33$ 插入根節點。根節點此時有 4 個分隔鍵而溢位，分裂後形成新的根節點。

最終結構為：

 [18]
 / \
 [12] [25 | 33]
 / \ / | \
 [5 | 9] [12 | 15] [18 | 21] [25 | 31] [33 | 38]

葉節點鏈結順序為：

[5 | 9] → [12 | 15] → [18 | 21] → [25 | 31] → [33 | 38]

範圍查詢：$10 \leq \text{key} \leq 30$

先從根節點依分隔鍵搜尋下界 $10$。根節點 $[18]$ 導向左子樹；接著在內部節點 $[12]$ 選擇右側葉節點 $[12|15]$。該葉節點中符合範圍者為 $12,15$。

再沿葉節點鏈結向右掃描：

• 訪問 $[18|21]$，其中 $18,21$ 符合範圍。
• 訪問 $[25|31]$，其中只有 $25$ 符合；$31>30$，停止掃描。

實際節點訪問順序為：

核心觀念

本題考查目標屬性 Class 的熵，以及以屬性 $A$ 分裂後的不純度變化。熵衡量類別分布的不確定性，資訊增益則衡量分裂後的不確定性減少多少。

若類別比例為 $p_i$，熵的公式為：

以屬性 $A$ 分裂的資訊增益為：

其中 $S_v$ 是 $A=v$ 的子資料集。

解題方法

全體共有 6 筆資料，正類 $+$ 有 3 筆，負類 $-$ 有 3 筆，因此：

整體熵為 1 bit。

依 $A$ 分裂：

• $A=T$：3 筆，其中 $+$ 有 2 筆、$-$ 有 1 筆。

• $A=F$：3 筆，其中 $+$ 有 1 筆、$-$ 有 2 筆。類別比例與 $A=T$ 相反，因此熵相同：

兩個子集各占全體一半，加權後的條件熵為：

所以資訊增益為：