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

優點：大小可動態成長、不需連續記憶體、已知位置時插入刪除 $O(1)$。

缺點：不支援隨機存取（$O(n)$）、每節點多一份指標、cache 局部性差。

(a) 依 $z\to y\to x$ 分層：

• $z^1$：$y^2$ 下 $x^5$（係數 5）；$y^3$ 下 $x^2$（係數 1）
• $z^2$：$y^1$ 下 $x^3$（係數 2）
• $z^6$：$y^4$ 下 $x^3$（係數 7）

(b) 額外的 tag 與指標欄位佔用記憶體；不支援隨機存取，須逐層走訪；相加、相乘等運算須逐層比對次方，實作複雜。

最終陣列：[24, 12, 21, 9, 6, 18, 1, 4, 5]（bottom-up 建堆）。

（如簡答圖）

(a) MST 邊集合 $=\{a\text{-}f(3),b\text{-}h(5),b\text{-}c(7),h\text{-}d(9),f\text{-}e(11),b\text{-}g(16),a\text{-}b(20)\}$，總權重 71。

(b) Kruskal's：依權重遞增加入 $a\text{-}f,b\text{-}h,b\text{-}c,h\text{-}d,f\text{-}e,b\text{-}g,a\text{-}b$（$d\text{-}c$、$g\text{-}d$ 形成 cycle，跳過）。

(c) Prim's：依序加入 $a\text{-}f,f\text{-}e,a\text{-}b,b\text{-}h,b\text{-}c,h\text{-}d,b\text{-}g$。

(a) -+*/+abcde5

(b) abc/-xy/z-*

(a) 函式在定義中呼叫自己，把問題拆成較小的同構子問題，並以 base case 終止。

(b) 程式簡潔易讀，適合分治類問題，貼近問題的數學定義。

(c) 每層呼叫佔用 stack frame，過深會 stack overflow；呼叫開銷使其通常慢於迭代；重複計算子問題時效率差。

25→5；35：5 占用→6；14→4；5：5、6 占用→7；16：6、7 占用→8；26：6、7、8 占用→9；19：9 占用→0。

Collision：兩個相異 key 經雜湊函數算出同一 slot。

Separate chaining：同一 slot 的 key 以 linked list 串接。例：$N=5$，12、22、7 皆落在 slot 2，串成 12 → 22 → 7。

• 優點：表不會滿（$\alpha$ 可 $>1$）、刪除簡單。
• 缺點：指標佔額外記憶體、cache locality 差、單鏈過長退化為 $O(n)$。

Open addressing：碰撞時在表內探測下一個空 slot。例：linear probing ${\text{index}}_i=(h(k)+i)modN$，$N=5$ 時 12→2、22→3、7→4。

• 優點：無指標開銷、cache locality 佳。
• 缺點：$\alpha \le 1$，表滿無法插入；$\alpha$ 接近 1 時效能急降；linear probing 有 primary clustering；刪除須用 tombstone。

以 Patient ID 為 key，節點存 key 與指向完整病歷的指標。

Insert（$O(\log n)$）：依 BST 規則插入，沿路往上檢查 BF，第一個 $|BF|>1$ 的節點依 LL／RR／LR／RL 旋轉。例：已有 100、200，插入 300 時於 100 觸發 RR，左旋後 200 成為 root。

Delete（$O(\log n)$）：依 BST 刪除三種情況移除（degree-2 以 inorder successor 頂替），再由父節點往上逐層修正失衡，可能需多次旋轉。