114 年 國立中央大學企業管理學系碩士班戊組《資料結構》

核心觀念

本題考查單向鏈結串列（Singly Linked List）的環狀結構檢測（Cycle Detection），核心演算法為 Floyd's Cycle-Finding Algorithm（弗洛伊德尋環演算法），又常稱為龜兔賽跑演算法（Tortoise and Hare Algorithm）或快慢指標法（Fast and Slow Pointers）。

1. 環狀鏈結串列定義：
   若單向鏈結串列中存在環（Cycle），則串列中某個節點的 next 指標會指向先前的某個節點，導致串列無法到達 termination node (nullptr)。
2. 相對速度定理：
   • 設定兩個指標同時從串列開頭出發：慢指標（slow）每次向前移動 $1$ 個節點，快指標（fast）每次向前移動 $2$ 個節點。
   • 若串列無環，fast 必先抵達末端 (nullptr)。
   • 若串列存在環，當兩指標皆進入環後，以 slow 為參考座標系，fast 相對於 slow 的相對移動速度為每次向前接近 $1$ 個節點（即 $2 - 1 = 1$）。由於環是封閉結構，fast 必然會在有限步數內追上 slow 並重合（即指向同一記憶體位址）。

解題方法

1. 演算法推導與步驟說明

• Step 1 (初始化)：宣告兩指標 slow 與 fast，初值皆指向頭節點 head。
• Step 2 (迴圈條件與邊界檢查)：檢查 fast != nullptr 且 fast->next != nullptr。若不滿足，代表已抵達串列末端，串列無環，傳回 false。
• Step 3 (指標移動)：
  • slow = slow->next（向前走 $1$ 步）
  • fast = fast->next->next（向前走 $2$ 步）
• Step 4 (相遇判定)：若移動後 slow == fast，代表快指標在環內追上慢指標，串列存在環，傳回 true。

2. C++ 風格偽代碼 (C++ Style Pseudocode)

// 單向鏈結串列節點結構
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    /**
     * 檢測單向鏈結串列中是否存在環
     * @param head 鏈結串列頭節點指標
     * @return bool 若存在環傳回 true，否則傳回 false
     */
    bool hasCycle(ListNode* head) {
        // 邊界條件判斷：空串列或僅有一個節點且無環
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        // 當快指標及其下一個節點皆有效時持續推進
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // 慢指標走 1 步
            fast = fast->next->next;    // 快指標走 2 步

            // 兩指標指向相同記憶體位址，代表存在環
            if (slow == fast) {
                return true;
            }
        }

        // 快指標抵達末端 nullptr，代表無環
        return false;
    }
};

3. 時間與空間複雜度分析

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）之核心操作，包含中序追蹤（In-order Traversal）與度數為 2 之節點刪除與重構（Node Deletion and Restructuring）。

1. 二元搜尋樹（BST）之定義：
   對樹中任意節點 $V$：
   • 其左子樹中所有節點的值皆小於 $V$ 的值。
   • 其右子樹中所有節點的值皆大於 $V$ 的值。
2. 中序追蹤（In-order Traversal）：
   追蹤順序為：左子樹（Left） $\rightarrow$ 根節點（Node） $\rightarrow$ 右子樹（Right）。
   對任何符合定義的二元搜尋樹進行中序追蹤，其輸出結果必為**遞增排序（Ascending Order）**序列。
3. 二元搜尋樹之節點刪除規則：
   刪除節點時，依被刪除節點的**度數（Degree，即子節點個數）**分為三種處理情況：
   • 度數 $= 0$（葉節點）：直接移除該節點。
   • 度數 $= 1$：將該節點移除後，由其唯一的子節點直接頂替其位置。
   • 度數 $= 2$：該節點同時擁有左右子樹。必須尋找其**中序後繼者（In-order Successor，右子樹的最小值）或中序前驅者（In-order Predecessor，左子樹的最大值）**來取代被刪除節點的值，再將原後繼者（或前驅者）位置之節點刪除（該節點之度數必為 0 或 1）。

解題方法與詳細推導

(a) 中序追蹤（In-order Traversal）之順序推導

針對給定之 BST：

      15
     /  \
    10   20
   / \   / \
  8  12 17 25

遵循 $L \rightarrow N \rightarrow R$ 之遞迴順序進行追蹤：

1. 從根節點 $15$ 開始，先進入其左子樹（以 $10$ 為根）。
2. 對以 $10$ 為根的子樹進行中序追蹤：
   • 進入 $10$ 的左子樹（葉節點 $8$），存取並輸出：8
   • 回到根節點 $10$，存取並輸出：10
   • 進入 $10$ 的右子樹（葉節點 $12$），存取並輸出：12
   • 左子樹輸出序列為：8, 10, 12
3. 回到主樹根節點 $15$，存取並輸出：15
4. 進入 $15$ 的右子樹（以 $20$ 為根）：
   • 進入 $20$ 的左子樹（葉節點 $17$），存取並輸出：17
   • 回到根節點 $20$，存取並輸出：20
   • 進入 $20$ 的右子樹（葉節點 $25$），存取並輸出：25
   • 右子樹輸出序列為：17, 20, 25

將上述結果依序組合，最終輸出序列為：$8, 10, 12, 15, 17, 20, 25$。

(b) 刪除節點 15 之重構步驟說明

被刪除的節點為根節點 $15$，其擁有左右兩個子節點（$10$ 與 $20$），屬於度數為 2 之刪除情況。

標準教科書（如 Horowitz / CLRS）主要採用**中序後繼者（In-order Successor）**替代法（亦可採用中序前驅者替代法，兩者皆能維持合法 BST 結構）。

方法一：採用「中序後繼者（In-order Successor）」替代（標準做法）

核心觀念

最大堆是完全二元樹，且每個父節點的值都大於或等於其子節點。以陣列從 1 開始編號時，索引為 $i$ 的節點，其父節點索引為 $\lfloor i/2 \rfloor$，左、右子節點索引分別為 $2i$、$2i+1$。

插入時，先放到完全二元樹的下一個空位，再向上調整；刪除最大值時，將最後一個節點移至根節點並刪除原位置，再向下調整。

解題方法

原卷圖中的初始最大堆有 6 個節點：根節點為 50，第二層為 30、20；第三層為 10、15、5，其中 5 是 20 的左子節點。因此，第 7 個位置是 20 的右子節點。

(a) 插入 60

先將 60 放入第 7 個位置，也就是 20 的右子節點：

接著向上調整：

1. 60 大於父節點 20，交換兩者：

2. 60 大於父節點 50，再交換：

60 已到根節點，且所有父節點都大於或等於子節點，調整完成。

核心觀念

本題考查無向圖的深度優先搜尋（DFS）、廣度優先搜尋（BFS），以及最小生成樹（MST）的 Kruskal 與 Prim 演算法。

DFS 沿著尚未拜訪的鄰點深入，無法再前進時才回溯；BFS 則使用佇列，依距離起點的層次逐一拜訪。兩者依題意都從 $b$ 開始，並按字母順序檢查鄰點。

Kruskal 每次挑選權重最小且不會形成環的邊；Prim 每次挑選連接目前生成樹與樹外頂點的最小權重邊。含 $|V|$ 個頂點的生成樹須有 $|V|-1$ 條邊。

解題方法

圖的鄰接關係如下：

• $a$：$b,d$
• $b$：$a,c,d,g$
• $c$：$b,h$
• $d$：$a,b,e$
• $e$：$d,g,h$
• $g$：$b,e$
• $h$：$c,e$

(a) DFS 與 BFS 生成樹

**DFS：**從 $b$ 出發，依字母順序逐層深入。拜訪路徑為

因此 DFS 生成樹的邊為

**BFS：**先拜訪 $b$ 的鄰點 $a,c,d,g$，再依序處理這些頂點。$c$ 發現 $h$，$d$ 發現 $e$；$g$ 的鄰點 $e$ 已被發現。因此 BFS 生成樹的邊為

(b) Kruskal 演算法

依權重由小至大排列邊：

依序加入不會形成環的邊：

1. 加入 $(b,c)$，權重 $8$。
2. 加入 $(c,h)$，權重 $10$。
3. 加入 $(e,h)$，權重 $11$。
4. 加入 $(a,d)$，權重 $13$。

核心觀念

本題考驗多維陣列在記憶體中的定址計算（Array Address Mapping），包含**以列為主（Row-Major Order）與以行為主（Column-Major Order）**兩種記憶體配置順序。

記憶體本質上是一維連續空間，將多維陣列對映至一維記憶體位址時，核心在於計算目標元素之前累積了多少個元素（即位址偏移量 $\text{Offset}$）。

定義與通用公式如下：
設三維陣列 $C[d_1:u_1, d_2:u_2, d_3:u_3]$，基底位址為 $\text{Base}(C[d_1, d_2, d_3])$，每個元素占用 $S$ 個位元組（Bytes）。
各維度的長度（大小）分別為：
$L_1 = u_1 - d_1 + 1, \quad L_2 = u_2 - d_2 + 1, \quad L_3 = u_3 - d_3 + 1$

對於目標元素 $C[i, j, k]$：

1. 以列為主（Row-Major Order）：最右側維度（高維度）變動最快。前方累積的元素數量為：
   $\text{Offset}_{\text{row}} = (i - d_1) \times (L_2 \times L_3) + (j - d_2) \times L_3 + (k - d_3)$
   記憶體位址公式為：
   $\text{Address}(C[i, j, k]) = \text{Base} + \text{Offset}_{\text{row}} \times S$

2. 以行為主（Column-Major Order）：最左側維度（低維度）變動最快。前方累積的元素數量為：
   $\text{Offset}_{\text{col}} = (k - d_3) \times (L_1 \times L_2) + (j - d_2) \times L_1 + (i - d_1)$
   記憶體位址公式為：
   $\text{Address}(C[i, j, k]) = \text{Base} + \text{Offset}_{\text{col}} \times S$

解題方法

1. 整理已知條件

• 陣列維度與範圍：$C[1:4, 1:5, 1:6]$
  • 第一維度長度 $L_1 = 4 - 1 + 1 = 4$
  • 第二維度長度 $L_2 = 5 - 1 + 1 = 5$
  • 第三維度長度 $L_3 = 6 - 1 + 1 = 6$
• 起始元素位址：$\text{Base}(C[1,1,1]) = 1344$
• 單一元素大小：$S = 2 \text{ bytes}$
• 目標元素：$C[i, j, k] = C[3, 4, 5]$
  • 索引偏移：$i - d_1 = 3 - 1 = 2$、$j - d_2 = 4 - 1 = 3$、$k - d_3 = 5 - 1 = 4$

2. 計算步驟

(a) 以列為主（Row-Major Order）位址推導

• 計算目標元素前方累積的元素個數：
  $\text{Offset}_{\text{row}} = 2 \times (5 \times 6) + 3 \times 6 + 4$
  $\text{Offset}_{\text{row}} = 2 \times 30 + 18 + 4 = 60 + 18 + 4 = 82$
• 代入位址計算公式：
  $\text{Address}(C[3,4,5]) = 1344 + 82 \times 2 = 1344 + 164 = 1508$

(b) 以行為主（Column-Major Order）位址推導

• 計算目標元素前方累積的元素個數：

核心觀念

本題旨在考驗考生對 堆疊（Stack）資料結構 在 後序運算式求值（Postfix Expression Evaluation） 中的應用，以及基礎 模數運算（Modulus Operation） 的能力。

1. 後序運算式（Postfix Expression / Reverse Polish Notation）：運算子位於運算元之後，不需要括號即可明確定義運算優先順序。
2. 堆疊（Stack）求值規則：
   • 遇到 運算元（Operand）：將其推入（Push）堆疊。
   • 遇到 二元運算子（Binary Operator）：從堆疊中彈出（Pop）兩個運算元，先彈出者為 右運算元（$op_2$），後彈出者為 左運算元（$op_1$），執行運算 $op_1 \text{ op } op_2$ 後，將計算結果推回（Push）堆疊。
3. 模數運算（Modulus）：$x \bmod m$ 代表 $x$ 除以 $m$ 的餘數，滿足 $x = q \cdot m + r$（其中 $0 \le r < m$）。

解題方法

步驟一：已知變數數值對照

根據題目給定：
$A = 3$, $B = 4$, $C = 5$, $D = 7$, $E = 9$, $F = -12$

步驟二：後序運算式堆疊求值

待求值的後序運算式為：A B + D * E F A D * + / + C +

利用堆疊由左至右依序掃描符號並進行計算：

1. A：Push $3$ $\rightarrow$ Stack: [3]
2. B：Push $4$ $\rightarrow$ Stack: [3, 4]
3. +：Pop $4$, Pop $3$ $\rightarrow$ 計算 $3 + 4 = 7$ $\rightarrow$ Push $7$ $\rightarrow$ Stack: [7]
4. D：Push $7$ $\rightarrow$ Stack: [7, 7]
5. *：Pop $7$, Pop $7$ $\rightarrow$ 計算 $7 \times 7 = 49$ $\rightarrow$ Push $49$ $\rightarrow$ Stack: [49]
6. E：Push $9$ $\rightarrow$ Stack: [49, 9]
7. F：Push $-12$ $\rightarrow$ Stack: [49, 9, -12]
8. A：Push $3$ $\rightarrow$ Stack: [49, 9, -12, 3]
9. D：Push $7$ $\rightarrow$ Stack: [49, 9, -12, 3, 7]
10. *：Pop $7$, Pop $3$ $\rightarrow$ 計算 $3 \times 7 = 21$ $\rightarrow$ Push $21$ $\rightarrow$ Stack: [49, 9, -12, 21]
11. +：Pop $21$, Pop $-12$ $\rightarrow$ 計算 $(-12) + 21 = 9$ $\rightarrow$ Push $9$ $\rightarrow$ Stack: [49, 9, 9]

核心觀念

本題旨在考驗檔案系統（File Systems）中兩大核心樹狀索引結構——B-tree（B 樹） 與 B+ tree（B+ 樹） 的結構差異、磁碟 I/O 特性、檢索效能及維護成本。

1. 結構定義與資料儲存位置：

   • B-tree：所有節點（包含內部節點與葉子節點）均同時儲存搜尋鍵（Key）與對應的資料指標（Data Pointer）。
   • B+ tree：僅底層葉子節點（Leaf Nodes）儲存完整的 Key 與 Data Pointer；內部節點（Internal Nodes）僅儲存 Key 與子節點指標（Child Pointer）作為路由導引（Routing Index）。此外，所有葉子節點之間以雙向鏈結串列（Doubly Linked List）相連。

2. 分支度（Branching Factor / Fan-out）與樹高（Tree Height）推導：
   設磁碟區塊（Disk Page）大小固定為 $B$ 位元組，鍵值長度為 $k$，子節點指標長度為 $p$，資料指標長度為 $d$：

   • B-tree 內部節點容量公式：$m_{\text{B}} \cdot p + (m_{\text{B}} - 1) \cdot (k + d) \le B \implies m_{\text{B}} \approx \frac{B - k}{k + p + d} + 1$
   • B+ tree 內部節點容量公式：$m_{\text{B+}} \cdot p + (m_{\text{B+}} - 1) \cdot k \le B \implies m_{\text{B+}} \approx \frac{B - k}{k + p} + 1$

   由於 $d > 0$，故分支度 $m_{\text{B+}} \gg m_{\text{B}}$。給定總筆數 $N$，樹高 $h \approx \lceil \log_{m} N \rceil$，故 B+ tree 的樹高顯著低於 B-tree（$h_{\text{B+}} \le h_{\text{B}}$）。

3. 檢索複雜度與磁碟 I/O：

   • 點查詢（Point Lookup）：B-tree 最佳為 $O(1)$、最壞為 $O(h_{\text{B}})$；B+ tree 恆為 $O(h_{\text{B+}})$（延遲極度穩定）。
   • 範圍查詢（Range Query）：B-tree 需執行中序走訪（In-order Traversal），產生 $O(K \log N)$ 的隨機磁碟 I/O（Random I/O）；B+ tree 僅需 $O(\log N)$ 找到起始頁面，後續 $K$ 筆資料以 $O(K)$ 執行順序磁碟 I/O（Sequential I/O）。

解題方法

本題分為兩子題，解題切入點如下：

• (a) 偏好 B-tree 的情境切入點：
  立足於 B-tree 「非葉節點即可直接命中資料」與「無重複鍵值儲存」的物理特性，尋找不需範圍查詢且強調特定熱點存取或無鍵值冗餘負擔的檔案系統情境。
• (b) 混合查詢情境之推薦與權衡分析切入點：
  明確推薦 B+ tree，並分別從 空間效率（分支度與樹高推導）、讀寫效能（點查詢安定性與順序 vs. 隨機 I/O）、維護複雜度（內部節點與葉子節點更新機制）三個面向進行數學與邏輯嚴謹的對比。

選項與子題深度剖析

(a) 偏好 B-tree 優於 B+ tree 的兩大檔案系統應用情境

1. 情境一：高存取局部性（Locality of Reference）且需「早期終止查詢（Early Search Termination）」的熱點資料檔案系統

   • 原理與分析：B-tree 的內部節點（含根節點與第一層節點）直接存放資料指標。若檔案系統具備強烈的存取局部性（例如系統組態檔、根目錄索引檔等高頻存取的熱點檔案），可經由調整置於較淺的內部節點中。
   • 效能優勢：點查詢在第 $1 \sim 2$ 次磁碟 Page 讀取時即可命中並傳回資料，搜尋時間複雜度最佳可達 $O(1)$。相對地，B+ tree 無論目標資料頻次高低，均被強制要求走訪至樹底葉子節點（固定需要 $h$ 次磁碟 I/O）。因此在熱點資料點查詢佔絕大多數的情境下，B-tree 具備更高的平均檢索速度。

2. 情境二：完全無範圍查詢需求、且鍵值（Key）極大之記憶體受限檔案系統

   • 原理與分析：B+ tree 的內部節點僅儲存 Key 作為分流導引，底層葉子節點仍需重複儲存一份相同的 Key，存在「鍵值冗餘（Key Duplication）」。
   • 效能優勢：當檔案系統僅執行精確點查詢（如 Hash-like 檔案檢索系統），且 Key（如長字串檔名或 UUID）佔用大量位元組時，B-tree 能完全消除鍵值重複儲存的開銷。在記憶體或快取空間極度受限的嵌入式檔案系統中，B-tree 能提供更精簡的整體索引空間佔用。

(b) 兼具點查詢與範圍查詢之結構推薦與權衡評估

【系統推薦】：強烈推薦選用 B+ tree。

i. 空間效率（Space Efficiency）

• B-tree：內部節點需同時容納 Key、Child Pointer 與 Data Pointer，導致節點分支度 $m_{\text{B}}$ 較小、樹高 $h_{\text{B}}$ 較高。

核心觀念：
本題考查檔案系統（File Systems）中外存儲存結構 B-tree 與 B+ tree 的效能關鍵要素，即 區塊大小（Block Size / Node Size） 與 磁碟 I/O 次數（Disk I/O Count） 之間的權衡關係（Trade-off）。

1. 磁碟 I/O 瓶頸：外存系統的效能瓶頸在於磁碟存取（Disk I/O），而非 CPU 計算時間。B-tree／B+ tree 的節點大小通常直接映射至作業系統的磁碟區塊大小（Block Size 或 Page Size，常見為 $4\text{ KB}$、$8\text{ KB}$ 或 $16\text{ KB}$），使一次節點讀寫正好對應一次物理磁碟 I/O。
2. 階數（Order / Degree $m$）與樹高（Tree Height $h$）：
   若區塊大小為 $B$，鍵值（Key）與指標（Pointer）大小分別為 $K$ 與 $P$，則內部節點可容納的最大分支數（即階數 $m$）滿足：
   • B+ tree 內部節點：$m \approx \frac{B + K}{K + P}$
   • B-tree 內部節點（含資料欄位或資料指標 $D$）：$m \approx \frac{B + P}{K + P + D}$
3. 搜尋複雜度：儲存 $N$ 筆資料時，檢索所需的最大磁碟 I/O 次數等於樹高 $h$：
   $h \approx O(\log_m N) = O\left(\frac{\log N}{\log m}\right)$
   分歧度（Branching Factor） $m$ 越大，樹高 $h$ 越矮，磁碟 I/O 次數越少。

解題方法：
分析 Block Size 對 B-tree 與 B+ tree 效能的影響時，應從「Block Size 過大 vs. 過小的權衡（Trade-off）」以及「B-tree 與 B+ tree 結構特性的差異」兩個維度切入推導：

1. 推導 Block Size 對樹高與磁碟 I/O 的直接控制：區塊越大 $\implies$ 單一節點可存放更多 Key 與指標 $\implies$ 階數 $m$ 增加 $\implies$ 樹高 $h$ 降低 $\implies$ 隨機搜尋磁碟 I/O 減少。
2. 比較 B-tree 與 B+ tree 的區塊空間利用率：
   • B+ tree 內部節點僅儲存路由 Key 與指標，不儲存實際資料（Data Record），因此在相同的 Block Size 下，B+ tree 能提供遠高於 B-tree 的階數 $m$，大幅降低樹高。
   • B+ tree 的葉節點（Leaf Nodes）包含全部資料並以串列（Linked List）相連，對範圍查詢（Range Query）可達成順序 I/O（Sequential I/O），極大化 Block Size 的預讀效能。
3. 歸納最佳區塊大小（Optimal Block Size）的選擇原則：區塊大小過大會帶來內部碎塊與記憶體快取負擔，過小則會引發樹高暴增；實務上必須與作業系統 Page Size 及磁碟扇區大小（Sector Size）保持對齊。

選項分析：
本題為問答題（非選擇題），以下針對「Block Size 過大」、「Block Size 過小」及「B-tree vs. B+ tree 結構差異」對效能的影響逐一進行深入剖析：

1. 選擇較大的區塊大小（Larger Block Size）之影響：
   • 正向影響（降低 Disk I/O）：
     節點容量大，使階數 $m$ 顯著提升。搜尋資料時樹高 $h \approx O(\log_m N)$ 變矮，存取資料所需的隨機磁碟 I/O 次數顯著減少，大幅提升檔案系統檢索速度。
   • 負向影響（空間與快取開銷）：
     • 內部碎塊（Internal Fragmentation）：B-tree/B+ tree 節點的填滿率下限通常為 $\lceil m/2 \rceil$，當 Block Size 過大時，未使用的空間增多，造成記憶體與磁碟空間浪費。

核心觀念

最小度數 $t=3$ 的 B-tree，每個節點最多有 $2t-1=5$ 個鍵；除根節點外，每個非根節點至少有 $t-1=2$ 個鍵。插入時，若往下走會遇到已滿的子節點，就先將其中位鍵升到父節點，並把其餘鍵分成左右兩個子節點。若根節點已滿，則先分裂根節點，建立新根。

解題方法與逐步結果

依序插入指定鍵。以下以「根節點；各內部節點的子節點由左至右」表示 B-tree。

操作 1：插入 26

$26$ 落在根節點 $[5,13,22,35]$ 之後、$[50,60]$ 之前，插入葉節點 $[25,27,30,31]$，得到：

• 根：$[5,13,22,35]$
• 子節點：$[1,4]$、$[6,7,8,11]$、$[14,18]$、$[25,26,27,30,31]$、$[50,60]$

操作 2：插入 29

目標葉節點 $[25,26,27,30,31]$ 已滿。先將中位鍵 $27$ 升至根，左右分成 $[25,26]$ 與 $[30,31]$；再將 $29$ 插入右側葉節點：

• 根：$[5,13,22,27,35]$
• 子節點：$[1,4]$、$[6,7,8,11]$、$[14,18]$、$[25,26]$、$[29,30,31]$、$[50,60]$

操作 3：插入 2

$2$ 落在葉節點 $[1,4]$，插入後為 $[1,2,4]$：