112 高普考高考三級 資訊處理 資料結構 考古題詳解

核心觀念

本題考查「兩層優先權佇列」的排程：

1. 每個工作依序於第 $1$ 至第 $8$ 天放入佇列。
2. 高優先佇列的優先權高於低優先佇列。
3. 同一佇列內採先進先出（FIFO）。
4. 工作一旦開始執行即連續完成，不因新工作到達而中斷。
5. 只有在高優先佇列沒有待執行工作時，才可執行低優先佇列工作。

解題方法

各工作到達時間如下：

依照「高優先佇列優先」規則排程：

說明如下：

核心觀念

本題考：

1. 有向無環圖（DAG）的拓樸排序。
2. Kahn 演算法：反覆選取入度為 $0$ 的頂點，將其列入順序並刪除其出邊。
3. 拓樸排序存在的必要條件：圖中不可存在有向循環。
4. 總運送成本為所有有向連線標示成本的總和。

由圖可讀得各邊如下：

（一）拓樸排序與總運送成本

各頂點初始入度為：

依序執行：

1. 頂點 $1$ 入度為 $0$，列入排序；刪除 $1\to3$、$1\to2$。
2. 頂點 $3$ 入度變為 $0$，列入排序；刪除 $3\to2$、$3\to4$。
3. 頂點 $4$ 入度變為 $0$，列入排序；刪除 $4\to2$、$4\to5$、$4\to6$。
4. 頂點 $2$ 入度變為 $0$，列入排序；刪除 $2\to6$。
5. 頂點 $6$ 入度變為 $0$，列入排序；刪除 $6\to5$、$6\to7$。
6. 頂點 $5$ 入度變為 $0$，列入排序；刪除 $5\to7$、$5\to8$。
7. 頂點 $7$ 入度變為 $0$，列入排序；刪除 $7\to8$。
8. 頂點 $8$ 入度變為 $0$，列入排序。

因此拓樸排序為：

總運送成本為所有邊成本相加：

核心觀念

本題的核心觀念在於運用**二元字典樹（Binary Trie / Bitwise Trie）**解決字串與二進位鍵值（Key）的檢索問題。在計算機網路與路由器轉送表（Forwarding Table）的設計中，這是最具代表性的資料結構之一。

1. 二元字典樹（Binary Trie）定義：

• 樹中的每個節點包含兩個子指標：左指標代表位元 $0$，右指標代表位元 $1$。
• 鍵值（IP 位址）不直接儲存在單一節點內部，而是由樹根（Root）到該節點的路徑（Path）所決定。
• 葉節點（Leaf Node）或特定終端節點存放對應的資料內容（本題為「對應裝置代號」）。

2. 查詢複雜度特性：

• 線性搜尋（逐筆比對）：若有 $m$ 筆資料且每筆長度為 $W$ 位元，最壞情況需要比對 $m \times W$ 次位元，時間複雜度為 $O(m \times W)$。
• Trie 搜尋：搜尋時間僅取決於鍵值的位元長度 $W$，與資料筆數 $m$ 無關。本題鍵值長度固定為 $W = 8$ 位元，因此由樹根向下走訪最多只需經過 $8$ 個分支，時間複雜度嚴格維持在 $O(W) = O(8) = O(1)$ 常數時間。

解題方法

一、樹狀資料結構設計

設計一棵高度為 $8$ 的「二元字典樹」（Binary Trie）：

1. 節點結構（Node Structure）：

• LeftChild：指向位元為 $0$ 的子節點。
• RightChild：指向位元為 $1$ 的子節點。
• Device：儲存對應的裝置代號（若為非終端的中繼節點則為空值 null；於深度為 $8$ 的葉節點儲存 A、B、C、D、E 等標籤）。

2. 分支規則：

• 從最高有效位元（Most Significant Bit, 位元 0）至最低有效位元（Least Significant Bit, 位元 7）逐一位元檢驗。
• 當前位元為 $0$ 則走訪左分支；為 $1$ 則走訪右分支。

二、建立樹狀結構（以題目 5 個 IP 為例）

將題目所提供的 5 個 8 位元 IP 位址依序插入 Binary Trie：

• 裝置 A：0 0 1 1 1 1 0 0
• 裝置 B：0 0 1 1 0 0 1 1
• 裝置 C：1 1 0 0 0 0 1 1
• 裝置 D：1 1 0 0 1 1 0 0
• 裝置 E：1 1 0 1 1 1 0 0

依各 IP 的位元路徑逐步建構，所得之樹狀結構如下圖所示（括號數字代表所在深度/位元層級）：

 [Root] (層級 0)
 / \
 bit0=0/ \bit0=1
 / \
 (N1) (N2)
 / \bit1=1
 bit1=0/ \
 / (N3)
 (N4) /
 \bit2=1 bit2=0/
 \ /
 (N5) (N6)
 / bit3=/ \bit3=1
 bit3=1/ / \
 / (N7) (N8)
 (N9) / \ \bit4=1
 / \ bit4=0 / \ \
 bit4=0/ \bit4=1 / bit4=1\ (N13)
 / \ (N10) (N11) \bit5=1
 (N14) (N15) \ \ \
 / \ bit5=0\ bit5=1 \ (N16)
 bit5=0/ bit5=1 \ \ \ /
 / \ (N12) (N12')\bit6=0
 (N17) (N18) \ \ /
 \ / bit6=1 \ bit6=0 \/
 bit6=1\ bit6=0/ \ \
 \ / (N19) (N20)
 (N21) (N22) \ \
 \bit7=1 \bit7=0 bit7=1 \ bit7=0 \
 \ \ \ \
 [ B ] [ A ] [ C ] [ D, E 共用路徑終點 ]
 ├── bit3=0 支線：[ D ]
 └── bit3=1 支線：[ E ]

完整精確路徑展開驗證：

1. 路徑 A（IP: 00111100）： $\text{Root} \xrightarrow{0} \text{位元0} \xrightarrow{0} \text{位元1} \xrightarrow{1} \text{位元2} \xrightarrow{1} \text{位元3} \xrightarrow{1} \text{位元4} \xrightarrow{1} \text{位元5} \xrightarrow{0} \text{位元6} \xrightarrow{0} \text{位元7} \to \text{裝置 A}$
2. 路徑 B（IP: 00110011）： $\text{Root} \xrightarrow{0} \text{位元0} \xrightarrow{0} \text{位元1} \xrightarrow{1} \text{位元2} \xrightarrow{1} \text{位元3} \xrightarrow{0} \text{位元4} \xrightarrow{0} \text{位元5} \xrightarrow{1} \text{位元6} \xrightarrow{1} \text{位元7} \to \text{裝置 B}$
3. 路徑 C（IP: 11000011）：

核心觀念

1. 雜湊函數（Hash Function）： 依題目定義，$h(x) = \text{密碼之英文字母及數字加總}$。其中字母採代號數值轉換（$\text{a} = 1, \text{b} = 2, \dots, \text{z} = 26$），數字則直接取其數值（$0 \sim 9$）累加。
2. 2-3 樹（2-3 Tree）之定義與性質：

• 為 3 階 B 樹（B-tree of order 3）的特例，是內部節點均為 2-節點（2-node）或 3-節點（3-node）的高度平衡搜尋樹。
• 2-節點：包含 1 個鍵值（Key）及 2 棵子樹；左子樹所有鍵值小於該鍵值，右子樹所有鍵值大於該鍵值。
• 3-節點：包含 2 個鍵值（$K_1 < K_2$）及 3 棵子樹；左子樹鍵值 $< K_1$、中子樹鍵值介於 $K_1$ 與 $K_2$ 之間、右子樹鍵值 $> K_2$。
• 平衡性質：所有葉節點（Leaf Nodes）必在同一深度。
• 插入與分裂機制（Bottom-Up Insertion & Split）：新資料一律自葉節點插入。若節點已滿（含有 2 個鍵值，插入後成為暫時的 4-節點 / 含有 3 個鍵值），則取中間鍵值（Median）向上提升（Promote）至父節點，左右鍵值各自獨立分裂為 2-節點。若父節點亦滿則遞迴向上分裂；若根節點分裂，樹高增加 1。

3. 儲存排序基準： 題目要求「依使用者帳號英文字母順序儲存」，因此 2-3 樹的搜尋鍵值（Key）為「使用者帳號」，其大小依英文字典順序比較；雜湊後的密碼為隨同儲存之關聯資料（Satellite Data）。

解題方法

（一）計算雜湊後的密碼資料

依定義 $h(x) = \sum \text{數字} + \sum \text{字母數值}$，逐一計算各使用者密碼：

1. 使用者帳號 AA（密碼：234abc） $h(\text{"234abc"}) = (2 + 3 + 4) + (1 + 2 + 3) = 9 + 6 = 15$
2. 使用者帳號 BB（密碼：123bcd） $h(\text{"123bcd"}) = (1 + 2 + 3) + (2 + 3 + 4) = 6 + 9 = 15$
3. 使用者帳號 CD（密碼：aa012） $h(\text{"aa012"}) = (1 + 1) + (0 + 1 + 2) = 2 + 3 = 5$
4. 使用者帳號 AC（密碼：555be） $h(\text{"555be"}) = (5 + 5 + 5) + (2 + 5) = 15 + 7 = 22$
5. 使用者帳號 BD（密碼：45fdd） $h(\text{"45fdd"}) = (4 + 5) + (6 + 4 + 4) = 9 + 14 = 23$
6. 使用者帳號 CA（密碼：712ccc） $h(\text{"712ccc"}) = (7 + 1 + 2) + (3 + 3 + 3) = 10 + 9 = 19$

（二）建立 2-3 樹之完整步驟

節點資料格式表示為 (帳號, 雜湊密碼)。依題目表格由上而下順序依序插入：

• 步驟 1：插入 (AA, 15)
• 樹為空，建立根節點：

[(AA, 15)]

• 步驟 2：插入 (BB, 15)
• $\text{AA} < \text{BB}$，放入同一節點，形成 3-節點：

[(AA, 15), (BB, 15)]

• 步驟 3：插入 (CD, 5)
• $\text{AA} < \text{BB} < \text{CD}$，放入根節點後暫時形成含有 3 個鍵值的溢位節點： [(AA, 15), (BB, 15), (CD, 5)]
• 觸發分裂：取中位數 (BB, 15) 提升為新根節點，左右鍵值分裂為兩個 2-節點：

[(BB, 15)]
/ \
[(AA, 15)] [(CD, 5)]

• 步驟 4：插入 (AC, 22)
• 與根節點比較：$\text{AC} < \text{BB}$，向左搜尋至葉節點 [(AA, 15)]。