中央 114 年資管所 資料結構 參考答案

slow 每次走 1 步、fast 每次走 2 步；有環時兩者會相遇，無環時 fast 先走到 nullptr。

bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   // 相遇即有環
    }
    return false;                        // fast 走到底，無環
}

時間 $O(n)$，空間 $O(1)$。

8, 10, 12, 15, 17, 20, 25。

15 有兩個子節點，以右子樹最小值（inorder successor）17 取代 15，再刪除原來的葉節點 17。

（如簡答圖）

60 放在陣列尾端（20 的右子），與 20 交換，再與 50 交換，升到 root。最終陣列：[60, 30, 50, 10, 15, 5, 20]。

移除 root 60，尾端 20 移到 root，與較大的子節點 50 交換後即滿足 heap。最終陣列：[50, 30, 20, 10, 15, 5]。

DFS spanning tree 的邊：$b\text{-}a,a\text{-}d,d\text{-}e,e\text{-}g,e\text{-}h,h\text{-}c$。

BFS spanning tree 的邊：$b\text{-}a,b\text{-}c,b\text{-}d,b\text{-}g,c\text{-}h,d\text{-}e$。

加入順序：$b\text{-}c,c\text{-}h,e\text{-}h,a\text{-}d,b\text{-}d,b\text{-}g$，總權重 88。

起點 $b$，加入順序：$b\text{-}c,c\text{-}h,h\text{-}e,b\text{-}d,d\text{-}a,b\text{-}g$，總權重 88。

(a) 1508。

(b) 1532。

$x=55$，$xmod7=6$。

1. 以點查詢為主、熱門 key 集中：B-tree 內部節點即存資料，可能在淺層命中；B+ tree 必須走到 leaf。
2. 空間吃緊且不需範圍查詢：B-tree 每個 key 只存一份；B+ tree 內部節點的 key 會在 leaf 層重複存放。

選 B+ tree。

i. 空間效率：內部節點只存 key，fanout 高、樹較矮，I/O 較少。

ii. 讀寫效能：資料都在 leaf 且深度一致，點查詢時間穩定；leaf 以 linked list 相連，範圍查詢可循序讀取。

iii. 維護複雜度：插入刪除都在 leaf 層進行再向上 split／merge；B-tree 刪除內部節點的 key 還需找替代值，較複雜。

• Block size 變大：fanout 增加，樹高 $\approx {\log }_{\text{fanout}}N$ 下降，I/O 次數減少。
• 過大：每次 I/O 讀入多餘資料，浪費頻寬，節點內搜尋成本上升。
• 過小：樹高增加，I/O 次數過多。
• 實務上 node size 對齊磁碟區塊（如 4 KB），一次節點讀取對應一次 I/O。

Operation 1（insert 26）：根 [5, 13, 22, 35]；葉 [1, 4] [6, 7, 8, 11] [14, 18] [25, 26, 27, 30, 31] [50, 60]

Operation 2（insert 29）：葉 [25, 26, 27, 30, 31] 分裂，27 上升。根 [5, 13, 22, 27, 35]；葉 [1, 4] [6, 7, 8, 11] [14, 18] [25, 26] [29, 30, 31] [50, 60]

Operation 3（insert 2）：根已滿先分裂，22 成為新根。根 [22]；第二層 [5, 13]、[27, 35]；[5, 13] 的子節點 [1, 2, 4] [6, 7, 8, 11] [14, 18]；[27, 35] 的子節點 [25, 26] [29, 30, 31] [50, 60]

Operation 4（insert 10）：根 [22]；第二層 [5, 13]、[27, 35]；[5, 13] 的子節點 [1, 2, 4] [6, 7, 8, 10, 11] [14, 18]；[27, 35] 的子節點 [25, 26] [29, 30, 31] [50, 60]

Operation 5（insert 9）：葉 [6, 7, 8, 10, 11] 分裂，8 上升。根 [22]；第二層 [5, 8, 13]、[27, 35]；[5, 8, 13] 的子節點 [1, 2, 4] [6, 7] [9, 10, 11] [14, 18]；[27, 35] 的子節點 [25, 26] [29, 30, 31] [50, 60]