南航2012年數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)專業(yè)考研真題答案

1、航空航天大學(xué)2012 年科目代碼：922科目名稱：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專業(yè)學(xué)位）入學(xué)試題數(shù)據(jù)結(jié)構(gòu)1.（1）2(n-1)-1= 691 lchild!=NULL) EnQueue(S,q-lchild); in+;if(q-rchild!=NULL) EnQueue(q-rchild!=NULL);in+;if(out=tq)temp =q;if(tempwedth) wedth=temp; tq=in;return wedth;void main()wedth=0;CreateBiTiree(T); wedth = Wedth(T);pr f(“樹的寬度%d”,wedth);數(shù)據(jù)結(jié)構(gòu)：type

2、def struct Nodedata;struct Node *next;Node,*pNode;算法：Void sort(pNode &L)pNode pre,p,q; pre=L;p=pre-next;q=p-next; While(p)if(p-data=0) pre=p;p=q;q=p-next; If(p-datanext=q;p-next=L-next; L-next=p;p=q;q=p-next;87535129874628746287462897531751615121755128750389750317050361611081.程調(diào)度 存調(diào)度高級(jí)調(diào)度作業(yè)調(diào)度2.準(zhǔn)則：空閑讓

3、進(jìn)， 無(wú)進(jìn)程進(jìn)入臨界區(qū)，就允許請(qǐng)求進(jìn)程進(jìn)入臨界區(qū)忙則等待， 若臨界區(qū)有進(jìn)程，則必須等待有限等待， 在有限的時(shí)間內(nèi)進(jìn)入臨界區(qū)，以免“死等”讓權(quán)等待， 進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，立即處理機(jī)，以免“忙等”代碼應(yīng)該是跟第題一個(gè)程序，那就應(yīng)該把a(bǔ) 設(shè)為臨界區(qū)：因?yàn)閮蓚€(gè)進(jìn)程都會(huì)對(duì)a 進(jìn)行修改，進(jìn)程推進(jìn) 的順序不同，修改的時(shí)間不同，造成兩個(gè)進(jìn)程同時(shí)執(zhí)行的結(jié)果不一樣，所以a 必須設(shè)為臨界區(qū)。違背了讓權(quán)等待同步準(zhǔn)則，syn_nc()就好比于 P,V 原語(yǔ)中的wait(mutex)操作，一般 P,V 原語(yǔ)是成對(duì)使用的，這里只使用了P 原語(yǔ)，沒有V 原語(yǔ)，所以在進(jìn)程 1 占用 mutex 信號(hào)量時(shí)，用完不a=a-1 后

4、就無(wú)限等待。，進(jìn)程 2 在執(zhí)行3.(1)產(chǎn)生死鎖的原因：一組進(jìn)程的每個(gè)進(jìn)程都在等待該組其他進(jìn)程的資源，并且每個(gè)進(jìn)程只有在執(zhí)行完才能資源，造成了死鎖。死鎖的四個(gè)條件，互斥條件請(qǐng)求和保持條件不可搶占條件循環(huán)等待條件，換句話說(shuō)，死鎖就是因?yàn)闈M足了這四個(gè)必要的條件才的。（2）處理死鎖就是要破壞死鎖產(chǎn)生的必要的四個(gè)條件。防止死鎖避免死鎖死鎖的檢測(cè)與解除靜態(tài)分配：是把資源所需的所有資源都分配給進(jìn)程才可以讓進(jìn)程進(jìn)行的分配方式。這就破壞了死鎖的第個(gè)條件：請(qǐng)求和保持條件，所以是方法防止死鎖。而家算法在分配中進(jìn)行安全檢測(cè)，尋找安全序列，屬于第二個(gè)方法：避免死鎖。低級(jí)調(diào)度進(jìn)資源進(jìn)程MaxNeedAllocation

5、Work+AllocationFinishABCABCABCABCP4425221204437trueP54241103147411trueP513trueP2536truevoid search()dowait(Smutex);if(count=0) signal(Umuetx); count+;signal(Smutex);perform the operation wait(Smutex);count-;if(countAvailable(2,3,3)不予分配(c)可以，T0 時(shí)刻的安全序列就是 P4 第一個(gè)分配的，所以可以分配(d)不安全，先給P4 分配，修改相應(yīng)的數(shù)據(jù)： Availa

6、ble(0,3,2)=Available(2,3,3)-Request(2,0,1) Need(0,2,0)=Need(2,2,1)-Request(2,0,1) Allocation(4,0,5)=Allocation(2,0,4)+Request(2,0,1)這是 P4 分配后對(duì) P4 進(jìn)程的修改現(xiàn)在對(duì)P1 請(qǐng)求作出判斷： Request(0,2,0)Need(3,4,7) Request(0,2,0)Available(0,3,2)嘗試分配，數(shù)據(jù)修改 Available(0,1,2)=Available(0,3,2)-Request(0,2,0)A,B,C 的資源（0,1,2）已不再滿足

7、任何進(jìn)程，不安全4.（1）優(yōu)點(diǎn)有調(diào)高內(nèi)存利用率減少內(nèi)存碎片的產(chǎn)生（2）a.溢出相加段表012物理地址b.0,430,段號(hào)為 0，430660，內(nèi)存地址為：219+430=649 1,10,段號(hào)為 1，10100，超過(guò)段長(zhǎng)，溢出中斷 3,400,段號(hào)為 3，400580，內(nèi)存地址為：1237+400=1637c.至少兩次， 第一次找到段表指定段的物理塊號(hào)，再講塊號(hào)頁(yè)內(nèi)偏移量拼接，形成物理地址，第二次，才是從第一次所得的物理地址找到所需的數(shù)據(jù)。提高訪存速度可以設(shè)置一個(gè)塊表5.（1）原理：根據(jù)局部性原理可知，程序執(zhí)行時(shí)，對(duì)特定區(qū)域的指令，在特定時(shí)間，調(diào)用頻率頻繁，而對(duì)其他指令調(diào)用很少，這就可實(shí)現(xiàn)將部

8、分頁(yè)面或者段提前裝入內(nèi)存，其余部分在需要時(shí)中斷請(qǐng)求，從外存調(diào)用即可。從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充。（2）程序a：因?yàn)锳 數(shù)組按行存取而程序a 取數(shù)的順序是按列的順序所以每取一個(gè)數(shù)據(jù)就會(huì)中斷一次 共缺頁(yè)：256256=216 次程序b：取數(shù)的順序是按行，與存取的順序一致而只有兩個(gè)工作集，每次最多一次只能調(diào)入 2 個(gè)頁(yè)面，所以每取一頁(yè)（256 個(gè)數(shù)據(jù)），中斷一次共缺頁(yè)：256 次注：工作集只是用來(lái)分配內(nèi)存的，內(nèi)存最多可以放入兩個(gè)頁(yè)面，沒有數(shù)據(jù)的頁(yè)面就要調(diào)入調(diào)出，程序順序與取數(shù)順序若不同，速度不同?？磃or 循環(huán)，是先行還是列，i 跟j 不要混了。6.（1）磁盤時(shí)間=平均尋道時(shí)間+平均等待時(shí)間從第 1

9、53#開始下一磁道距離14047下一磁道距離段號(hào)段內(nèi)地址段表長(zhǎng)度P3401100640517520true（2）7.（1）直接地址 09 可存放：10 個(gè)一次間址 10：256 個(gè)二次間址 11：256256 個(gè)三次間址 12：256256256 個(gè)文件最大長(zhǎng)度：1KB（10+256+256256+256256256）=16843018KB(2) 4MB/1KB=4K=4096（盤塊號(hào)）補(bǔ)充查找具體的塊號(hào)地址：10+256409610+256+2562564096-(10+256)=38303830/256=14246從 FCB 的第 11 個(gè)地址項(xiàng)，即第二次間址項(xiàng)中得到第二次間址塊的地址，并從第二次間址塊的第 14項(xiàng)中獲得一個(gè)第一次間址塊的地址，再?gòu)脑摰谝淮伍g址塊的第 246 項(xiàng)中獲得物理盤塊號(hào)塊內(nèi)的偏移量 0. 8.（1）引入索引結(jié)點(diǎn)前，目錄項(xiàng)的目錄即文件控制塊12864/256=32 個(gè)盤塊平均啟動(dòng)（1+32）/2=16.5 次引入索引結(jié)點(diǎn)后，目錄項(xiàng)中只需存放文件名和索引結(jié)點(diǎn)128（8+2）/256=5