算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機械工業(yè)出版社 課后答案 第8章 動態(tài)存儲管理

課后答案網(wǎng) 8 章 動態(tài)存儲結(jié)構(gòu) 在伙伴系統(tǒng)中的伙伴是指任意兩塊大小相同、位置相鄰的內(nèi)存塊。這種說法對嗎？ 【解答】不對。只有同一內(nèi)存塊分裂的兩塊才互稱伙伴。 佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。這種說法對嗎？ 【解答】對。 內(nèi)存中可利用空間已連成一個單鏈表，對用戶的存儲空間需求，一般有哪三種分配策略？ 【解答】 首次擬合法；從鏈表頭指針開始查找，找到第一個大于等于所需空間的結(jié)點即分配。 最佳擬合法：鏈表結(jié)點大小增序排列，找到第一個大于等于所需空間的結(jié)點即分配 。 最差擬合法：鏈表結(jié)點大小逆序排列，總從第一個結(jié)點開始分配，將分配后結(jié)點所剩空間插入到鏈表適當位置。 首次擬合法適合事先不知道請求分配和釋放信息的情況 ,分配時需查詢 ,釋放時插在表頭。 最佳擬合法適用于請求分配內(nèi)存大小范圍較寬的系統(tǒng) ,釋放時容易產(chǎn)生存儲量很小難以利用的內(nèi)存碎片 ,同時保留那些很大的內(nèi)存塊以備將來可能發(fā)生的大內(nèi)存量的需求，分配與回收均需查詢。 最差擬合法適合請求分配內(nèi)存大小范圍較窄的系統(tǒng) ,分配時不查詢 ,回收時查詢 ,以便插入適當位置。 算起始二進制地址為 011011110000，長度為 4（十進制）的塊的伙伴地址是多少？ 【解答】 011011110100 址為（ 1664） 10大小為（ 128） 10的存儲塊的伙伴地址是什么？ 地址為（ 2816） 10大小為（ 64） 10的存儲塊的伙伴地址是什么？ 【解答】 （ 1） 664,7)=1664536 （ 2） 816,6)=2816+64=2880 敘述動態(tài)存儲分配伙伴系統(tǒng)的基本思想，它和邊界標識法不同點是什么？ 【解答】 動態(tài)存儲分配伙伴系統(tǒng)的基本思想是：在伙伴系統(tǒng)中，無論占用塊或空閑塊 ，其大小均為 2的 k(k 為 0 的正整數(shù) )次冪。若內(nèi)存容量為 2m，則空閑塊大小只能是 20， 21， 22， 2m。由同一大塊分裂而得的兩個小塊互稱“伙課后答案網(wǎng) 空間”，如內(nèi)存大小為 210的塊分裂成兩個大小為 29的塊。只有兩個“伙伴空間”才能合并成一個大空間。 起始地址為 p，大小為 2伙伴的起始地址為： 邊界標識法在每塊的首尾均有“占用” /“空閑”標志，空閑塊合并方便?；锇橄到y(tǒng)算法簡單，速度快，但只有互為伙伴的兩個空閑塊才可合并，因而易產(chǎn)生雖空閑但不能歸并的碎片。 12個字長的存儲，假 設(shè)先后有 6個用戶申請大小分別為 23，45， 52， 100， 11和 19 的存儲空間，然后再順序釋放大小為 45， 52， 11 的占用塊。假設(shè)以伙伴系統(tǒng)實現(xiàn)動態(tài)存儲管理。 （ 1） 畫出可利用空間表的初始狀態(tài)。 （ 2） 畫出為 6 個用戶分配所需要的存儲空間后可利用空間表的狀態(tài)以及每個用戶所得到的存儲塊的起始地址。 （ 3） 畫出在回收 3 個占用塊之后可利用空間表的狀態(tài)。 【解答】 因為 512=29,可利用空間表的初始狀態(tài)圖如 8 當用戶申請大小為 23 的內(nèi)存塊時 ,因 2423=25,但沒有大小為 25的塊 ,只有大小為 29的塊 ,故將 29的塊分裂成兩個大小為 28的塊 ,其中大小為 28的一塊掛到可利用空間表上 ,另一塊再分裂成兩個大小為 27的塊。又將其中大小為 27的一塊掛到可利用空間表上 ,另一塊再分裂成兩個大小為 26的塊 ,一塊 26的塊掛到可利用空間表上 ,另一塊分裂成兩個大小為 25的塊 ,其中一塊掛到可利用空間表上 ,另一塊分給用戶 (地址 0 31)。如此下去 ,最后每個用戶得到的存儲空間的起始地址如圖 86 個用戶分配所需要的存儲空間后可利用空間表的狀態(tài)如圖 8 在回收時 ,因為給申請 45的用戶分配了 26,其伙伴地址是 0,在占用中 ,不能合 并 ,只能掛到可利用空間表上。在回收大小為 52的占用塊時 ,其伙伴地址是 192,也在占用?；厥沾笮?11的占用塊時 ,其伙伴地址是 48,可以合并為大小 25的塊 , 掛到可利用空間表上?；厥?3個占用塊之后可利用空間表的狀態(tài)如圖 8 圖 8 圖 8儲大小 起始地址 23 0 45 64 52 128 100 256 11 32 19 192 課后答案網(wǎng) 注：在圖 圖 上了占用塊，從原理上，只有空閑塊才出現(xiàn)在“可利用空間表”中。） 圖 8 圖 8圖所示的伙伴系統(tǒng)中，回收兩塊首地址分別為 768 及 128，大小為 27的存儲塊，請畫出回收后該伙伴系統(tǒng)的狀態(tài)圖。 【解答】 因為 768 % 27+1=0，所以 768 和 768+27=896 互為伙伴 , 伙伴合并后 ,首址為 768,塊大小為 28。因為 768 % 28+1=28,所以 ,所以首址 768 大小為 28