習題集解析部分

第8章 動態存儲管理

——《數據結構題集》-嚴蔚敏.吳偉民版

       源碼使用說明  鏈接☛☛☛ 《數據結構-C語言版》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明

       課本源碼合輯  鏈接☛☛☛ 《數據結構》課本源碼合輯

       習題集全解析  鏈接☛☛☛ 《數據結構題集》習題解析合輯

      相關測試數據下載  鏈接☛ 數據包

      本習題文檔的存放目錄：數據結構\▼配套習題解析\▼08 動態存儲管理

      文檔中源碼的存放目錄：數據結構\▼配套習題解析\▼08 動態存儲管理\▼習題測試文檔-08

      源碼測試數據存放目錄：數據結構\▼配套習題解析\▼08 動態存儲管理\▼習題測試文檔-08\Data

一、基礎知識題

8.1❷假設利用邊界標識法首次適配策略分配，已知在某個時刻的可利用空間表的狀態如下圖所示：

(1)畫出當系統回收一個起始地址為559、大小為45的空閑塊之後的鏈表狀態；

(2)畫出系統繼而在接受存儲塊大小為100的請求之後，又回收一塊起始地址為515、大小為44的空閑塊之後的鏈表狀態。

註意：存儲塊頭部中大小域的值和申請分配的存儲量均包括頭和尾的存儲空間。

8.2❷組織成迴圈鏈表的可利用空間表可附加什麼條件時，首次適配策略就轉變為最佳適配策略?

8.3❸設兩個大小分別為100和200的空閑塊依次順序鏈接成可利用空間表。設分配一塊時，該塊的剩餘部分在可利用空間表中保持原鏈接狀態，試分別給出滿足下列條件的申請序列:

(1)最佳適配策略能夠滿足全部申請而首次適配策略不能；

(2)首次適配策略能夠滿足全部申請而最佳適配策略不能。

8.4❶在變長塊的動態存儲管理方法中，邊界標誌法的演算法效率為什麼比以下圖所示的結點結構組織的可利用空間表的演算法效率高?

8.5❸考慮邊界標誌法的兩種策略(最佳適配和首次適配)：

(1)數據結構的主要區別是什麼?

(2)分配演算法的主要區別是什麼?

(3)回收演算法的主要區別是什麼?

8.6❶二進位地址為011011110000，大小為(4)₁₀的塊的伙伴的二進位地址是什麼?若塊大小為(16)₁₀時又如何?

8.7❸已知一個大小為512字的記憶體，假設先後有6個用戶提出大小分別為23，45，52，100，11和19的分配請求，此後大小為45，52和11的占用塊順序被釋放。假設以伙伴系統實現動態存儲管理，

(1)畫出可利用空間表的初始狀態；

(2)畫出6個用戶進入之後的鏈表狀態以及每個用戶所得存儲塊的起始地址；

(3)畫出在回收三個用戶釋放的存儲塊之後的鏈表狀態。

8.8❸試求一個滿足以下條件的空間申請序列a1，a2，…，an：從可用空間為25的伙伴管理系統的初始狀態開始，a1，a2，…，an-1均能滿足，而an不能滿足，並使a1+a2+…+an最小。

8.9❹設有五個廣義表：L=(L1, L3)，L1=(L2, L3, L4)，L2=(L3)，L3=( )，L4=(L2)。若利用訪問計數器實現存儲管理，則需對每個表或子表添加一個表頭結點，併在其中設一計數域。

(1)試畫出表L的帶計數器的存儲結構；

(2)從表L中刪除子表L1時，鏈表中哪些結點可以釋放？各子表的計數域怎樣改變？

(3)若L2=(L3, L4)，將會出現什麼現象？

8.10❷假設利用“堆”結構進行動態存儲管理。執行存儲緊縮過程之前，存儲器的格局如下表所示。請用表格方式給出存儲緊縮過程執行之後的存儲器格局。

轉載註明出處：原文鏈接

二、演算法設計題

8.11❸考慮空間釋放遵從“最後分配者最先釋放（棧）”規則的動態存儲管理問題，並設每個空間申請中都指定所申請的空閑塊大小。

(1)設計一個適當的數據結構實現動態存儲管理;

(2)寫一個為大小為n的空間申請分配存儲塊的演算法。

8.12❸同8.11題條件，寫一個回收釋放塊的演算法。

邊界標誌法

8.13❸試完成邊界標誌法和依首次適配策略進行分配相應的回收釋放塊的演算法。

伙伴系統

8.14❺試完成伙伴管理系統的存儲回收演算法。

無用單元搜集

8.15❸設被管理空間的上下界地址分別由變數highbound和lowbound給出，形成一個由同樣大小的塊組成的“堆”。試寫一個演算法，將所有tag域的值為0的塊按始址遞增順序鏈接成一個可利用空間表（設塊大小域為cellsize）。

存儲緊縮

8.16❹試完成教科書中8.6節所述的存儲緊縮演算法。