數(shù)據(jù)結(jié)構(gòu)第八章考試題庫

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第八章 動態(tài)存儲管理一、選擇題1. 動態(tài)存儲管理系統(tǒng)中，通?？捎校?）種不同的分配策略?！鹃L沙鐵道學院 1998 三、3 (2分)】A 1 B. 2 C. 3 D. 4 E. 5二、判斷題在伙伴系統(tǒng)中的伙伴是指任意兩塊大小相同、位置相鄰的內(nèi)存塊。（ ）【北京郵電大學 2000 一、8(1分)】在動態(tài)存儲管理系統(tǒng)中做空間分配時，最佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。（ ）【東南大學 2001 一、1-1 （1分）】【中山大學 1994 = 1 * CHI

2、NESENUM3 一、1（2分）】三、填空題1起始地址為480,大小為8的塊,其伙伴塊的起始地址是_;若塊大小為32,則其伙伴塊的起始地址為_?！颈狈浇煌ù髮W 1999 二、1（4分）】2二進制地址為0，大小為（4）10和（16）10塊的伙伴地址分別為：_、_?！旧虾４髮W 2002 = 2 * CHINESENUM3 二、2（2分）】無用單元是指_,例_【北方交通大學 1999 二、6（4分）】四、應用題1伙伴空間（名詞解釋）【西北工業(yè)大學 1999 一、4（3分）】2設(shè)內(nèi)存中可利用空間已連成一個單鏈表，對用戶的存儲空間需求，一般有哪三種分配策略？【北京科技大學 1999 = 1 * CHIN

3、ESENUM3 一、6（2分）】3計算起始二進制地址為0，長度為4（十進制）的塊的伙伴地址是多少？【中山大學1999 = 1 * CHINESENUM3 一、2(3分)】4在一個伙伴系統(tǒng)中，已知某存儲塊的始址（0）2，大小為4，則它的伙伴塊的始址是多少？【北方交通大學 1996 一、1（5分）】5地址為（1664）10大小為（128）10的存儲塊的伙伴地址是什么？地址為（2816）10大小為（64）10的存儲塊的伙伴地址是什么？【清華大學 1996 四、】6 試敘述動態(tài)存儲分配伙伴系統(tǒng)的基本思想，它和邊界標識法不同點是什么？【青島大學 2000 十、（10分）】【中國人民大學 2000 = 1

4、 * CHINESENUM3 一、1（4分）】7組織成循環(huán)鏈表的可利用空間表附加什么條件時，首次適配策略就轉(zhuǎn)變?yōu)樽罴堰m配策略？【北方交通大學 1998 四、（8分）】8已知一個大小為512個字長的存儲，假設(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)。【清華大學1998三(15分)】【同濟大學 1999

5、】9下圖所示的伙伴系統(tǒng)中，回收兩塊首地址分別為768及128，大小為27的存儲塊，請畫出回收后該伙伴系統(tǒng)的狀態(tài)圖?！颈本┼]電大學 1996 二、（10分）】 10假設(shè)利用邊界標識法，并以首次擬合策略分配，已知在某個時刻可利用空間表的狀態(tài)如下圖所示：（注：存儲塊頭部size域的值和申請分配的存儲量均包括頭部和尾部的存儲空間。）請畫出：（1）當系統(tǒng)回收一個起始地址為559，大小為45的空閑塊之后的鏈表狀態(tài)；（2）系統(tǒng)繼而在接受存儲塊大小為100的請求后，又回收一個起始地址為515，大小為44的空閑塊之后的鏈表狀態(tài)?！旧虾４髮W 2002 = 2 * CHINESENUM3 二、3（8分）】第10題圖

6、：可利用空間表的狀態(tài)圖動態(tài)存儲管理一選擇題 1C二判斷題 1錯誤 2正確三填空題1（1）480+8=488（480 %23+1=0） （2）480-32=448 2（1）0 （2）03用戶不再使用而系統(tǒng)沒有回收的結(jié)構(gòu)和變量。例如，p=malloc(size)；，p=null；四應用題在伙伴系統(tǒng)中，無論占用塊或空閑塊，其大小均為2的k(k為0的正整數(shù))次冪。若內(nèi)存容量為2m，則空閑塊大小只能是20，21，22，2m。由同一大塊分裂而得的兩個小塊互稱“伙伴空間”，如內(nèi)存大小為210的塊分裂成兩個大小為29的塊。只有兩個“伙伴空間”才能合并成一個大空間。起始地址為p，大小為2k的內(nèi)存塊，其伙伴的起始

7、地址為：buddy(p,k)=p+2k (若p % 2k+1=0),或buddy(p,k)=p-2k (若p % 2k+1=2k)2首次擬合法；從鏈表頭指針開始查找，找到第一個所需空間的結(jié)點即分配。最佳擬合法：鏈表結(jié)點大小增序排列，找到第一個所需空間的結(jié)點即分配。最差擬合法：鏈表結(jié)點大小逆序排列，總從第一個結(jié)點開始分配，將分配后結(jié)點所?？臻g插入到鏈表適當位置。首次擬合法適合事先不知道請求分配和釋放信息的情況,分配時需查詢,釋放時插在表頭。 最佳擬合法適用于請求分配內(nèi)存大小范圍較寬的系統(tǒng),釋放時容易產(chǎn)生存儲量很小難以利用的內(nèi)存碎片,同時保留那些很大的內(nèi)存塊以備將來可能發(fā)生的大內(nèi)存量的需求，分配與

8、回收均需查詢。 最差擬合法適合請求分配內(nèi)存大小范圍較窄的系統(tǒng),分配時不查詢,回收時查詢,以便插入適當位置。3 0 405（1）buddy(1664,7)=1664-128=1536 （2）buddy(2816,6)=2816+64=28806動態(tài)存儲分配伙伴系統(tǒng)的基本思想請參見上面題1。邊界標識法在每塊的首尾均有“占用”/“空閑”標志，空閑塊合并方便?；锇橄到y(tǒng)算法簡單，速度快，但只有互為伙伴的兩個空閑塊才可合并，因而易產(chǎn)生雖空閑但不能歸并的碎片。7組織成循環(huán)鏈表的可利用空間表的結(jié)點大小按遞增序排列時, 首次適配策略就轉(zhuǎn)變?yōu)樽罴堰m配策略。8因為512=29,可利用空間表的初始狀態(tài)圖如8-1所示。

9、當用戶申請大小為23的內(nèi)存塊時,因2423=25,但沒有大小為25的塊,只有大小為29的塊,故將29的塊分裂成兩個大小為28的塊,其中大小為28的一塊掛到可利用空間表上,另一塊再分裂成兩個大小為27的塊。又將其中大小為27的一塊掛到可利用空間表上,另一塊再分裂成兩個大小為26的塊,一塊26的塊掛到可利用空間表上,另一塊分裂成兩個大小為25的塊,其中一塊掛到可利用空間表上,另一塊分給用戶(地址031)。如此下去,最后每個用戶得到的存儲空間的起始地址如圖8-2, 6個用戶分配所需要的存儲空間后可利用空間表的狀態(tài)如圖8-3。在回收時,因為給申請45的用戶分配了26,其伙伴地址是0,在占用中,不能合并

10、,只能掛到可利用空間表上。在回收大小為52的占用塊時,其伙伴地址是192,也在占用。回收大小為11的占用塊時,其伙伴地址是48,可以合并為大小25的塊, 掛到可利用空間表上?；厥?個占用塊之后可利用空間表的狀態(tài)如圖8-4。存儲大小起始地址 23 0 45 64 52 128 100 256 11 32 19 192圖8-2 圖8-1（注：在圖8.3和8.4畫上了占用塊，從原理上，只有空閑塊才出現(xiàn)在“可利用空間表”中。） 圖8-3 圖8-49 因為768 % 27+1=0，所以768和768+27=896互為伙伴, 伙伴合并后,首址為768,塊大小為28。因為768 % 28+1=28,所以,所以首址768大小為28的塊和首址512大小為28的塊合并,成為首址512大小為29的空閑塊。因為128 % 27+1=27，其伙伴地址為128-27=0, 將其插入可利用空間表中?；厥蘸笤摶锇橄到y(tǒng)的狀態(tài)圖如下。10（1）系統(tǒng)回收一個起始地址為559，大小為45的空閑塊后，因右側(cè)起始地址604為空閑塊，應與之合并。合并后，起始地址為559，大小為167的空閑塊。鏈表狀態(tài)如圖