計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)（動(dòng)態(tài)存儲(chǔ)管理歷年真題試卷匯編1(分：34.00做題時(shí)間：分鐘)一、單項(xiàng)擇(總題數(shù)：1，數(shù)2.00)1.動(dòng)態(tài)存儲(chǔ)管理系中，通?？捎?種不同的分配策略。長(zhǎng)沙鐵道學(xué)院1998三3(2分)A.1B.2C.3D.4E.5

√二、填空(總題數(shù)：3，分?jǐn)?shù)6.00)2.起始地址為480，小8的塊，其伙伴塊的起始地址_________；若塊大32，則其伙伴塊的起始地址為_(kāi)________?！颈狈浇煌ù髮W(xué)、1(4)__________________________________________________________________________________________正確答案：(確答案：480+8=488(480％23+1=0)480—3.二進(jìn)制地址011011110000大為(4)10和16)10塊的伙伴地址分別為_(kāi)________上海大學(xué)2002二、分)】__________________________________________________________________________________________正確答案：(確答案：011011110100．100000)4.無(wú)用單元是_________，例如，。北方交通大學(xué)1999二6(4)__________________________________________________________________________________________正確答案：(確答案：用戶不再使用而系統(tǒng)沒(méi)有回收的結(jié)構(gòu)和變量，；，p=null；)三、判斷(總題數(shù)：2，分?jǐn)?shù)4.00)5.在伙伴系統(tǒng)中的伴是指任意兩塊大小相同位置相鄰的存塊(【京郵電大學(xué)2000一8(1分A.確B.誤

√6.在動(dòng)態(tài)存儲(chǔ)管理統(tǒng)中做空間分配時(shí)佳適配法與最先適配法相比者容易增加閑置空間的碎片)【東南大學(xué)2001一、1-1(1分【中山大學(xué)一、1(2分)A.確B.誤

√四、綜合(總題數(shù)：10，分?jǐn)?shù)：22.00)7.伙伴空間。名解釋西北工業(yè)大學(xué)一4(3分)__________________________________________________________________________________________正確答案：(確答案：在伙伴系統(tǒng)中，無(wú)論占用塊還是空閑塊，其大小均為的K(k為≥正整數(shù))次冪。若內(nèi)存容量為2

，則空閑塊大小只能是2，2，2，…，2

。由同一大塊分裂而得的兩個(gè)小塊互稱“伙伴空間”，如內(nèi)存大小為

的塊分裂成兩個(gè)大小為29

的塊。只有兩個(gè)“伙伴空間”才能合并成一個(gè)大空間。起始地址為大小為

的內(nèi)存塊，其伙伴的起始地址為：buddy(p，k)=p+2

(若％2

=0)，或，k)=p一(若％=2

))8.設(shè)內(nèi)存中可利用間已連成一個(gè)單鏈表，對(duì)用戶的存儲(chǔ)空間需求一有哪三種分配策略【北京科技大學(xué)1999一、分)】__________________________________________________________________________________________正確答案確答案次擬合法鏈表頭指針開(kāi)始查找到第一個(gè)大于等于所需空間的結(jié)點(diǎn)即分配。最佳擬合法：鏈表結(jié)點(diǎn)大小增序排列，找到第一個(gè)大于等于所需空間的結(jié)點(diǎn)即分配。最差擬合法：鏈表結(jié)

點(diǎn)大小逆序排列，總從第一個(gè)結(jié)點(diǎn)開(kāi)始分配，將分配后結(jié)點(diǎn)所?？臻g插入鏈表適當(dāng)位置。首次擬合法適合事先不知道請(qǐng)求分配和釋放信息的情況，分配時(shí)需查詢，釋放時(shí)插在表頭。最佳擬合法適用于請(qǐng)求分配內(nèi)存大小范圍較寬的系統(tǒng)，釋放時(shí)容易產(chǎn)生存儲(chǔ)量很小、難以利用的內(nèi)存碎片，同時(shí)保留那些很大的內(nèi)存塊以備將來(lái)可能發(fā)生的大內(nèi)存量的需求，分配與回收均需查詢。最差擬合法適合請(qǐng)求分配內(nèi)存大小范圍較窄的系統(tǒng)，分配時(shí)不查詢，回收時(shí)查詢，以便插入適當(dāng)位置。9.計(jì)算起始二進(jìn)制址為011011110000，長(zhǎng)度為4(進(jìn)制)的塊的伙伴地址是少?中山大學(xué)一2(3)__________________________________________________________________________________________正確答案：(確答案：110111101)10.在個(gè)伙伴系統(tǒng)中，已知某存儲(chǔ)塊的始址X=(011011110000)2，大小2

，則它的伙伴塊的始址是多少?北方交通大學(xué)1996、1(5分__________________________________________________________________________________________正確答案：(確答案：110111)11.地為1664)

大小為(128)

的存儲(chǔ)塊的伙伴地址是什么?址為(2816)

大小為(64)

的存儲(chǔ)塊的伙伴地址是什么?清華大學(xué)四__________________________________________________________________________________________正確答案：(確答案：(1)buddy(1664，7)=1664128=1536(2)buddy(2816，6)=2816+64=2880)12.試述動(dòng)態(tài)存儲(chǔ)分配伙伴系統(tǒng)的基本思想，它和邊界標(biāo)識(shí)法的不同點(diǎn)是什?中國(guó)人民大學(xué)一1(4)【青島大學(xué)(10分)__________________________________________________________________________________________正確答案(確答案動(dòng)態(tài)存儲(chǔ)分配伙伴系統(tǒng)的基本思想請(qǐng)參見(jiàn)上面第題邊界標(biāo)識(shí)法在每塊的首尾均有“占用”／“空閑”標(biāo)志，空閑塊合并方便。伙伴系統(tǒng)算法簡(jiǎn)單，速度快，但只有互為伙伴的兩個(gè)空閑塊才可合并，因而易產(chǎn)生雖空閑但不能歸并的碎片。)13.組成循環(huán)鏈表的可利用空間表附加什么條件時(shí)，首次適配策略就轉(zhuǎn)變?yōu)樽罴堰m配策?北方交通大學(xué)1998四8分)】__________________________________________________________________________________________正確答案(確答案組織成循環(huán)鏈表的可利用空間表的結(jié)點(diǎn)大小按遞增序排列時(shí)，首次適配策略就轉(zhuǎn)變?yōu)樽罴堰m配策略。)14.已一個(gè)大小為512個(gè)字長(zhǎng)的存儲(chǔ)，假設(shè)先后有用戶申請(qǐng)大小分別23，45，52，100，1119的存儲(chǔ)空間，然后再順序釋放大小為，52，11的用塊。假設(shè)以伙伴系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)存儲(chǔ)管理。畫(huà)可利用空間表的初始狀態(tài)出為用戶分配所需要的存儲(chǔ)空間后可利用空間表的狀態(tài)以及每個(gè)用戶所得到的存儲(chǔ)塊的起始地址(3)畫(huà)出在回3占用塊之后可利用空間表的狀態(tài)【華大學(xué)三15分)【同濟(jì)大學(xué)1999】__________________________________________________________________________________________正確答案：(確答案：因?yàn)榭衫每臻g表的初始狀態(tài)圖如1)所示。當(dāng)用戶申請(qǐng)大小23的內(nèi)存塊時(shí)，因2

，但沒(méi)有大小為的塊，只有大小為的塊，故將2的塊分裂成兩個(gè)大小為

的塊，其中大小為2

的一塊掛到可利用空間表上，另一塊再分裂成兩個(gè)大小為2

的塊。又將其中大小為2

的一塊掛到可利用空間表上，另一塊再分裂成兩個(gè)大小為2

的塊，一塊

的塊掛到可利用空間表上，另一塊分裂成兩個(gè)大小為

的塊，其中一塊掛到可利用空間表上，另一塊分給用戶地址31)如此下去，最后每個(gè)用戶得到的存儲(chǔ)空間的起始地址如(2)示，6用戶分配所需要的存儲(chǔ)空間后，可利用空間表的狀態(tài)如圖(3)所示。在回收時(shí)，因?yàn)榻o申請(qǐng)45的用戶分配2

，其伙伴地址是0，在占用中，不能合并，只能掛到可利用空間表上。在回收大小為52的占用塊時(shí)，其伙伴地址是192，也在占用?；厥沾笮?1的占用塊時(shí)，其伙伴地址是48，可以合并為小為2個(gè)占用塊之后可利用空間表的狀態(tài)如圖(4)所示。)

的塊，掛到可利用空間表上?；厥?15.下所示的伙伴系統(tǒng)中，回收兩塊首地址分別為768及128大小為

的存儲(chǔ)塊，請(qǐng)畫(huà)出回收后該伙伴系統(tǒng)的狀態(tài)圖?！颈本┼]電大學(xué)二10分)__________________________________________________________________________________________

正確答案(確答案：因?yàn)?68％2

=0，所768和768+2

=896互伙伴，伙伴合并后，首址768塊大小為2

。因?yàn)?=2，所以，首址768大小為2的塊和首址512大小為2

的塊合并，成為首址512大小為2

的空閑塊。因?yàn)?28％=2，其伙伴地址為128—7

=0，將其插入可利用空間表中?；厥蘸笤摶锇橄到y(tǒng)的狀態(tài)圖如下圖。)假設(shè)利用邊界標(biāo)識(shí)法，并以首次擬合策略分配，已知在某個(gè)時(shí)刻可利用空間表的狀態(tài)如下圖所示。(注：存儲(chǔ)塊頭部size域的值和申請(qǐng)分配的存量均包括頭部和尾部的存儲(chǔ)空間請(qǐng)出：

（分?jǐn)?shù)）(1).系統(tǒng)回收一個(gè)起始地址為559，大小為45的空閑塊之后的鏈表狀態(tài)；__________________________________________________________________________________________正確答案：(確答案：系統(tǒng)回收一個(gè)起始地址為大小為45的空閑塊后，因右側(cè)起始地址為閑塊，應(yīng)與之合并。合并后，起始地址為大小為的空閑塊。鏈表狀態(tài)如圖(1)所。(2).系繼而在接受存儲(chǔ)塊大小為請(qǐng)求后，又回收一個(gè)起始地址為大小為44的空閑塊之后的鏈表狀態(tài)。【上海大學(xué)二、3(8分】_________________