本文整理《數據結構題集》(嚴蔚敏、吳偉民版) 第 8 章「動態存儲管理」全套習題解析，涵蓋基礎知識題 1-10、算法設計題 11-16，包含邊界標識法、伙伴系統、廣義表引用計數、存儲緊縮等核心考點。
文檔目錄：數據結構\▼配套習題解析\▼08 動態存儲管理
(1) 回收地址 559、大小 45 的塊：檢查前後相鄰塊 tag，合併相鄰空閒塊，更新鏈表指針。
(2) 分配 100 → 回收地址 515、大小 44：首次適配分割塊，再回收合併。注意頭尾部大小域包含自身空間。
答案：附加「按空閒塊大小遞增排序」條件。首次適配在有序表中即為最佳適配。
(1) 最佳適配能滿足、首次適配不能：申請 100, 100, 100。最佳適配用 200 塊分兩次 100，首次適配用 100 塊後剩 200 只能再分一個 100。
(2) 首次適配能滿足、最佳適配不能：申請 60, 60, 80, 100。首次適配在 100 取 60 剩 40，200 取 60 剩 140→80→60；最佳適配在 100 取 60 剩 40，200 取 80 剩 120→60→60 失敗。
答案：邊界標識法利用塊首尾標識，回收時 O(1) 檢查相鄰塊 tag 並合併；圖示結構需遍歷鏈表尋找相鄰塊，O(n)。
(1) 數據結構：最佳適配需按大小排序（或維護多鏈表），首次適配僅需地址序。
(2) 分配：首次適配首滿足即用；最佳適配需遍歷尋找最小滿足塊。
(3) 回收：邏輯相同（合併相鄰空閒），最佳適配額外需維護大小序。
大小 4 (2²)：地址 011011110000 ⊕ 100 = 011011110100 (第 2 位翻轉)
大小 16 (2⁴)：地址 ⊕ 10000 = 011011010000 (第 4 位翻轉)
初始：512 塊 → 分配 23→32、45→64、52→64、100→128、11→16、19→32 → 釋放 45,52,11 → 合併伙伴 → 更新鏈表。
可用空間 25，序列使 a1+...+an 最小且 an 失敗。答案涉及伙伴分裂與外部碎片分析。
(1) L=(L1,L3), L1=(L2,L3,L4), L2=(L3), L3=(), L4=(L2) → 繪製帶計數器結構，L3 計數 3，L2 計數 2 等。
(2) 刪除 L1：遞減 L1 及其子表計數，計數歸 0 者釋放。L3 計數 3→2 不釋放，L4 計數 1→0 釋放，L2 計數 2→1 不釋放。
(3) L2=(L3,L4)：出現循環引用 (L2→L4→L2)，引用計數法無法回收循環結構，導致記憶體洩漏。
給出緊縮前佔用/空閒塊分布表，要求列出緊縮後所有佔用塊前移、空閒塊合併的新格局表。
數據結構：單棧指標 + 分配記錄棧。分配：指標前移，記錄大小入棧。釋放：棧頂必為最新分配，指標回退，出棧。
檢查前塊 tag(尾部標識)、後塊 tag(首部標識)，四種合併情況，更新鏈表前驅後繼指針。
計算伙伴地址 (地址 ⊕ 大小)，檢查伙伴是否空閒且同大小，是則合併雙倍大小，遞歸向上合併；否則插入對應大小鏈表。
掃描 [lowbound, highbound] 區間，tag=0 的塊按地址遞增鏈接成空閒表，塊大小 cellsize。
掃描堆，將佔用塊向低地址緊湊移動 (memmove)，更新地址映射表，尾部形成大空閒塊。
| 方法 | 核心數據結構 | 分配策略 | 回收合併 | 優點 | 缺點 |
|---|---|---|---|---|---|
| 邊界標識法 | 雙向鏈表 + 首尾標識 | 首次/最佳/最差適配 | O(1) 檢查相鄰 | 合併快、外部碎片少 | 內部碎片、管理開銷 |
| 伙伴系統 | 按大小分類的空閒鏈表陣列 | 向上取整至 2^k | 伙伴地址 XOR 合併 | 無外部碎片、合併快 | 內部碎片大、大小受限 |
| 存儲緊縮 | 堆指標 + 塊描述表 | 指標遞增 | 批量移動合併 | 空間利用率高 | 移動開銷大、需重定位 |
| 引用計數 | 表頭計數域 | 創建時增 | 刪除時減，歸0釋放 | 即時回收、簡單 | 循環引用洩漏、開銷 |
原文鏈接：[來源地址]
