2010-2018年南京某航空航天大學(xué)《922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》歷年考研真題匯總

目錄TOC\o"1-5"\h\z2010年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)（專(zhuān)業(yè)學(xué)位）考研真題 42011年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)（專(zhuān)業(yè)學(xué)位）考研真題 72012年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 102013年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 142014年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 172015年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 222016年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 252017年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 282018年南京航空航天大學(xué)922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）考研真題 32南京航空航天大學(xué)二。一O年碩士研究生入學(xué)考試試題考試科目：數(shù)據(jù)結(jié)構(gòu)（專(zhuān)業(yè)學(xué)位）說(shuō)明：答案一律寫(xiě)在答題紙上，寫(xiě)在試卷上無(wú)效一、單項(xiàng)選擇題（共30分，15題，每題2分）1.一個(gè)算法具有以下5個(gè)重要特性。（ ）A.有窮性、確定性、可行性、輸入、輸出B.可行性、可移植性、可擴(kuò)充性、輸入、輸出C.確定性、有窮性、穩(wěn)定性、輸入、輸出D.易讀性、穩(wěn)定性、安全性、輸入、輸出2.若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）（l<=i<=n+l）.A.0（0）B.0（1） C.0（n） D.0（n2）.一個(gè)棧的輸入序列為1,2,3…，n,若輸出序列的第一個(gè)元素是n,輸出第i（l<=i〈=n）個(gè)元素是（）.A.不確定B.n-iC.iD.n-i+1.循環(huán)隊(duì)列存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，當(dāng)前隊(duì)列的長(zhǎng)度是（）.A.rear-front+lB.rear-frontC.（rear-front+m）%mD.（rear-front）%m.數(shù)組A[L.5,1..6]的每個(gè)元素占4個(gè)字節(jié)，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[4,4]的地址是（）.A.1175 B.1180 C.1088 D.1084.已知一棵二叉樹(shù)的先序遍歷為ABCDEF,中序遍歷為CBAEDF,則后序遍歷為（ ）。A.CBEDFAB.FEDCBAC.CBEFDAD.不定.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的樹(shù)高度（深度）是（ ）A.Llog2nJB.log2n+lC.LlogziiJ+1D.log2n-l8.若一棵二叉樹(shù)具有15個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）。A.16 B.25 C.40D.不確定一棵完全二叉樹(shù)上有2001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。A.500B.501C.1000D.100110.一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（）。A.n+1 B.nA.n+1 B.n11.下面說(shuō)法不正確的是（ ）?A.廣義表的表頭總是一個(gè)廣義表C.廣義表難以用順序存儲(chǔ)結(jié)構(gòu)C.n-1 D.nlogn;B.廣義表的表尾總是一個(gè)廣義表D.廣義表可以是一個(gè)多層次的結(jié)構(gòu)TOC\o"1-5"\h\z12.適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（ ）。A.順序方式存儲(chǔ)，元素?zé)o序 B.順序方式存儲(chǔ)，元素有序C.鏈接方式存儲(chǔ)，元素?zé)o序 D.鏈接方式存儲(chǔ)，元素有序13.下列排序算法中，平均時(shí)間復(fù)雜度不為O（nlog'n）的是（ ）。A.快速排序 B.堆排序C.歸并排序 D.希爾排序14.下列排序算法中，其中（ ）是穩(wěn)定的。。A.快速排序 B.起泡排序 C.堆排序D.希爾排序15.Floyd算法是用來(lái)求解（ ）。D.任意兩點(diǎn)間最短距離A.拓?fù)渑判駼.關(guān)鍵路徑C.D.任意兩點(diǎn)間最短距離二、解答題（共80分，8題，每題10分）16.應(yīng)用棧操作求解算術(shù)表達(dá)式：（18-24/4）*（3+9）,畫(huà)出棧的變化過(guò)程。.畫(huà)出下圖所示樹(shù)的二種存儲(chǔ)結(jié)構(gòu)示意圖。（1）帶雙親的孩子鏈表表示法（2）孩子兄弟鏈表表示法.詳細(xì)解釋哈希表的工作原理，以及常見(jiàn)的哈希函數(shù)構(gòu)造方法和解決沖突方法，舉例說(shuō)明。.已知在一份電文中只使用了6個(gè)字符A,B,C,D,E,F,其頻率分別為5,29,7,8,12,畫(huà)出哈夫曼樹(shù)，并寫(xiě)出每個(gè)字符對(duì)應(yīng)的哈夫曼編碼。.已知數(shù)據(jù)序列為（36,74,8,50,18,6,40,30）,給出建立二叉排序樹(shù)的過(guò)程示意圖，再給出刪除74,8后的二叉排序樹(shù)。.求下圖中的關(guān)鍵路徑，寫(xiě)出算法求解過(guò)程中每一步的狀態(tài)。.已知輸入數(shù)據(jù)序列為(36,56,50,24,62,18,40,80,30,12),給出建立3階B-樹(shù)示意圖.再給出刪除30,50后的B-樹(shù)。.已知數(shù)據(jù)序列為(86,8,234,50,116,64,68,453,24,142),給出基數(shù)排序過(guò)程的示意圖.三、編程題(共40分，4題，每題10分)用C或C++或JAVA語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法.編寫(xiě)函數(shù)，將單鏈表中具有相同元素值的結(jié)點(diǎn)刪除(只保留一個(gè))，分析時(shí)間復(fù)雜度.寫(xiě)出算法思想。.已知一棵二叉鏈表表示的二叉樹(shù)T,編寫(xiě)函數(shù)，實(shí)現(xiàn)二叉樹(shù)的層次遍歷.寫(xiě)出算法思想。.無(wú)向圖G用鄰接矩陣存儲(chǔ)，編寫(xiě)程序，輸出G的每一連通分量的頂點(diǎn)值。寫(xiě)出算法思想。.設(shè)有一整數(shù)序列由正數(shù)、負(fù)數(shù)組成，編寫(xiě)程序，通過(guò)一趟掃描處理，將所有的負(fù)數(shù)移到正數(shù)前面，只能用一個(gè)輔助單元。寫(xiě)出算法思想。南京航空航天大學(xué)2011年碩士研究生入學(xué)考試初試試題（ A卷）科目代碼： 922 、廿科目名稱(chēng). 數(shù)據(jù)結(jié)構(gòu)（-業(yè)學(xué)位）麗必-"注意：①認(rèn)女閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在僭題紙|上,寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！一、單項(xiàng)選擇題（共30分，15題，每題2分）.如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.單鏈表B,雙鏈表C.單循環(huán)鏈表D.順序表.在一個(gè)雙鏈表中，在*P結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是（）□p->prior=q；q->next=p；p->prior->next=q；q->prior=p->prior；q->prior=p->prior；p->prior->next=q；q->next=p；p->prior=q->next；q->next=p；p->next=q；q->prior->next=q；q->next=p；p->prior->next=q；q->next=p；q->prior=p->prior；p->prior=q；.一個(gè)棧的進(jìn)棧序列是abode,則棧的輸出序列不可能的是（）。A.edcbaB.decbaC.dceabD.abode.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd.環(huán)形隊(duì)列qu的隊(duì)空條件是（）o（qu.rear+1）%MaxSize=（qu.front+1）%MaxSize；（qu.rear+1）%MaxSize=qu.front+1；（qu.rear+1）%MaxSize==qu.front；qu.rear==qu.front；.一棵高度為h的完全二叉樹(shù)至少有（）結(jié)點(diǎn)。A.2h-1B,2^'-1C. D.2h.任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì).根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是（）oA.000,001,010,011,1B.0000,0001,001,01,1C.000,001,01,10,11D,00,100,101,110,1119.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的（）倍。A.1/2B.1C.2D.4

10.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中的（）oA.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)的回路C.最長(zhǎng)的回路D.最短的回路11.索引順序表是將表分成若干子表（或稱(chēng)塊），據(jù)此建立索引表，并要求關(guān)鍵字（）oA.塊內(nèi)A.塊內(nèi)有序，塊間有序B.塊內(nèi)無(wú)序，塊間有序C.塊內(nèi)有序，塊間無(wú)序D.塊內(nèi)無(wú)序，塊間無(wú)序12.穩(wěn)定的排序方法是（）oA.直接插入排序B,直接選擇排序 C.堆排序D.快速排序13.以下序列是堆的是（）oA.B.C.D.(75,65,30,15,25,45,20.10)(75,65,45,10,30,25,20,15)(75,45,65,30,15,25,20,10}{75,45,65,10,25,30,20,15}A.B.C.D.4.m階B-樹(shù)任一個(gè)結(jié)點(diǎn)最多有（ ）個(gè)關(guān)鍵字。A.mB,m-1C.m+1D,任意.歸并排序算法的時(shí)間復(fù)雜度是()。A.0(Iog2n)B.0(n)C.0(n2)D.0(nIog2n)二、解答題（共80分，8題，每題10分）.應(yīng)用棧操作求解算術(shù)表達(dá)式：（12+28）*2-（68-14）/9，畫(huà)出棧的變化過(guò)程。.輸入關(guān)鍵字序列{16,3,7,11,9,26,18,14,15.12},給出構(gòu)造一棵平衡二叉樹(shù)的步驟。.已知世界6大城市：北京⑻、紐約（N）、巴黎（P）、倫敦（L）、東京⑴、墨西哥城（M）。試在下表給出的交通網(wǎng)中確定最小生成樹(shù)，并說(shuō)明所使用的方法和時(shí)間復(fù)雜度。表：世界6大城市交通里程網(wǎng)絡(luò)表（單位：100km）BNPLTMB109828121124N109585510832P825839792L815539589T211089795113M124329289113.對(duì)于下圖所示的帶權(quán)有向圖，采用Dijkstra算法求解從頂點(diǎn)1到其他頂點(diǎn)的最短路徑,要求給出求解過(guò)程。.關(guān)鍵字序列為{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12.14.18,19.15},創(chuàng)建一棵5階B-樹(shù)。對(duì)于該B-樹(shù)，刪除8,16,15,4等4個(gè)關(guān)鍵字的過(guò)程。.已知在一份電文中只使用了8個(gè)字符A,B,C,D,E,F,G,H,其頻率分別為(36,10,18,8,2,16,4,12),畫(huà)出哈夫曼樹(shù)，并寫(xiě)出每個(gè)字符對(duì)應(yīng)的哈夫曼編碼。.已知哈希函數(shù)H(k)=2*kmod11,用開(kāi)放定址法處理沖突：H,(k)=(H(k)+d.)mod11i=1,2,其中：d,=1,4“=(7d,+3)mod11(i>1)o試在。?10的哈希地址空間中對(duì)關(guān)鍵字序列(6,8,10,17,20,23,53,41,54,57)構(gòu)造哈希表。.已知序列［503,87.512,61.908,170,897,275,653,462},寫(xiě)出采用堆排序法對(duì)該序列作降序排序時(shí)的每一趟的結(jié)果。三、編程題(共40分，4題，每題10分)用C或C++或JAVA語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法.編寫(xiě)程序，實(shí)現(xiàn)在帶頭結(jié)點(diǎn)的單鏈表L中刪除一個(gè)最小值結(jié)點(diǎn)的算法。寫(xiě)出算法思想。.假設(shè)二叉樹(shù)T采用二叉鏈存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序，求二叉樹(shù)T的寬度。(即具有結(jié)點(diǎn)數(shù)最多的那一層上的結(jié)點(diǎn)個(gè)數(shù))。寫(xiě)出算法思想。.假設(shè)無(wú)向圖G采用鄰接表存儲(chǔ)，編寫(xiě)程序，判斷圖G是否是連通圖。若是連通圖返回1,否則返回0。寫(xiě)出算法思想。.已知二叉樹(shù)T采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，編寫(xiě)程序，對(duì)二叉樹(shù)T進(jìn)行非遞歸先序遍歷。寫(xiě)出算法思想。

南京航空航天大學(xué)2012年碩士研究生入學(xué)考試初試試題（A卷）科目代碼：科目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）滿(mǎn)分:150分注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在國(guó)酬上，寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！

數(shù)據(jù)結(jié)構(gòu)部分（75分）（5分）已知一棵完全二叉樹(shù)共有691個(gè)結(jié)點(diǎn).結(jié)點(diǎn)從1開(kāi)始，自上而下自左而右層序編號(hào)，試求以下問(wèn)題，并給出推導(dǎo)過(guò)程。（1）樹(shù)的高度； （2）葉子結(jié)點(diǎn)的數(shù)目；（3）分支為1的結(jié)點(diǎn)數(shù)目：（4）最后一個(gè)非終端結(jié)點(diǎn)的編號(hào)；（5）還差多少個(gè)結(jié)點(diǎn)就可以構(gòu)造成相同高度的滿(mǎn)二叉樹(shù)。（10分）畫(huà)出廣義表L=（f,（b,e）,（（c,d）,a））的兩種存儲(chǔ)結(jié)構(gòu)圖.（10分）如圖1所示的AOE網(wǎng)，試求完成工程最少需要多少天（設(shè)邊上的權(quán)值為天數(shù)），并說(shuō)明哪些是關(guān)鍵活動(dòng)。要求給出規(guī)范的計(jì)算過(guò)程。圖1第3題圖（10分）已知輸入數(shù)據(jù)序列為{38,66,18,80,58,52,26,42,28,16},給出建立3階B■樹(shù)示意圖，再給出刪除28,52后的3樹(shù)。（10分）已知序列{108,170,503,87,512,161,175,53,897,462},寫(xiě)出采用堆排序法對(duì)該序列作降序排序時(shí)的每一趟結(jié)果。（10分）設(shè)L為帶頭結(jié)點(diǎn)的單鏈表，元素值為整數(shù)。設(shè)計(jì)一個(gè)算法，調(diào)整結(jié)點(diǎn)的位置，將所有元素值為負(fù)數(shù)的結(jié)點(diǎn)移動(dòng)到元素值為正數(shù)的結(jié)點(diǎn)之前，要求時(shí)間夏雜度T（n）=CKn）。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（10分）設(shè)樹(shù)采用孩子兄弟鏈表結(jié)構(gòu)進(jìn)行存儲(chǔ)，設(shè)計(jì)一個(gè)算法，求樹(shù)的寬度（即具有結(jié)點(diǎn)數(shù)最多的那一層上的結(jié)點(diǎn)個(gè)數(shù)）.要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（10分）設(shè)二叉排序樹(shù)T的key值為整數(shù)，高度為k,對(duì)任意給定的整數(shù)x,查找元素值小于x且最接近x的結(jié)點(diǎn)并返回結(jié)點(diǎn)指針，如該結(jié)點(diǎn)不存在則返回指針為空，要求用非遞歸算法實(shí)現(xiàn)且時(shí)間更雜度T（n）=O（k）.要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。

操作系統(tǒng)部分(75分)1、(8分)(1)處理機(jī)的調(diào)度有哪三個(gè)層次？(2)假設(shè)一操作系統(tǒng)以單道批處理方式運(yùn)行，現(xiàn)有四道作業(yè)，進(jìn)入系統(tǒng)的時(shí)間及運(yùn)行時(shí)間如下表所示，試用響應(yīng)比高者優(yōu)先算法進(jìn)行調(diào)度，請(qǐng)給出這組作業(yè)的運(yùn)行順序、平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間(小時(shí))17:002.0027:500.5038:000.1048:500.202、27分)(1)實(shí)現(xiàn)進(jìn)程同步機(jī)制必須遵循哪幾條準(zhǔn)則，含義是什么？(2)以下程序中，哪些代碼應(yīng)該設(shè)為臨界區(qū)？(3)假設(shè)操作系統(tǒng)采用非搶占調(diào)度策略，sys_nc()是主動(dòng)放棄CRJ的系統(tǒng)函數(shù)。對(duì)于以下程序代碼，可能違反什么同步準(zhǔn)則？inta;進(jìn)程1(){sys_nc();a=a+l;)進(jìn)程2(){a=a-l;sys_nc();)(4)采用信號(hào)量來(lái)進(jìn)行進(jìn)程同步可以很好地滿(mǎn)足進(jìn)程同步準(zhǔn)則。現(xiàn)假設(shè)有一個(gè)共享數(shù)據(jù)庫(kù),允許進(jìn)程對(duì)數(shù)據(jù)庫(kù)進(jìn)行查詢(xún)和更新兩種操作，規(guī)則是查詢(xún)操作可以允許多個(gè)進(jìn)程同時(shí)查詢(xún)，但更新必須是排他性的，即每次只允許一個(gè)進(jìn)程更新數(shù)據(jù)庫(kù)，請(qǐng)用信號(hào)量和P、V操作來(lái)完成這一進(jìn)程同步問(wèn)題(要求：必須首先給出所設(shè)置信號(hào)量的意義及初值)3、(10分)(1)產(chǎn)生死鎖的主要原因是什么？(2)有哪些處理死鎖的基本方法？靜態(tài)分配資源的方法屬于哪種處理死鎖的方法？而銀行家算法屬于哪種死鎖處理方法？(3)設(shè)系統(tǒng)中有三種類(lèi)型的資源(A,B,C)和五個(gè)進(jìn)程(Pl,P2,P3,P4,P5),A的資源的數(shù)量為17,B的資源的數(shù)量為5,C的資源的數(shù)量為20,在T0時(shí)刻狀態(tài)如下：

ABCABcP1559212P2536402P34011405P4425204P5424314最大資源需求量已分配資源需求量剩余資源數(shù)ABC233系統(tǒng)采用銀行家算法實(shí)施死鎖處理策略。（a）TO時(shí)刻是否為安全狀態(tài)？若是請(qǐng)給出安全序列。（b）在TO時(shí)刻，若進(jìn)程P2請(qǐng)求資源（0,3,4）,是否能實(shí)施資源分配？為什么？（c）在（2）基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2,0,1）,是否能實(shí)施資源分配？為什么？（d）在（3）基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0,2,0）,是否能實(shí)施資源分配？為什么？4、（10分）（1）分頁(yè)和分段屬于離散型的存儲(chǔ)管理方式，相對(duì)于連續(xù)內(nèi)存管理方法的主要優(yōu)點(diǎn)是什么？（2）某操作系統(tǒng)采用段式存儲(chǔ)管理，假設(shè)有如下段表：（注意：其中數(shù)字為十進(jìn)制表示）段號(hào)段的長(zhǎng)度（字節(jié)）主存起始地址06602191143300210090358012374961952試解決下列問(wèn)題：（a）給定段號(hào)和段內(nèi)地址，完成段式管理中的地址變換過(guò)程（并用圖示）。（b）計(jì)算[0,430],[1,10],[2,500],[3,400]的內(nèi)存地址，其中方號(hào)內(nèi)的第一元素為段號(hào)，第二元素為段內(nèi)地址。（c）存取內(nèi)存中的一條指令或數(shù)據(jù)至少要訪(fǎng)問(wèn)幾次內(nèi)存？如何提高地址轉(zhuǎn)換的效率？5、（8分）（1）操作系統(tǒng)中虛擬存儲(chǔ)器的基本原理是什么？（2）頁(yè)面置換算法是虛擬存儲(chǔ)器的支撐軟件方法，現(xiàn)假設(shè)某頁(yè)式虛擬內(nèi)存系統(tǒng)中，程序代碼位于虛空間0頁(yè)，A為256x256的數(shù)組，在虛空間以行為主序進(jìn)行存儲(chǔ)(A(l,l),A(l,2),A(l,3)……)，每頁(yè)存放256個(gè)數(shù)組元素?，F(xiàn)工作集大小為2個(gè)頁(yè)框，假設(shè)代碼已經(jīng)在內(nèi)存中，用以下兩種代碼對(duì)數(shù)組A進(jìn)行初始化，都必須進(jìn)行頁(yè)面置換，問(wèn)兩個(gè)代碼各自的缺頁(yè)次數(shù)為多少？程序(a)fbrj:=lto256dofori:=1to256doA(ij)：=0;程序(b)fbri:=lto256dofbrj=1to256doA(ij)=0;6、(6分)1)磁盤(pán)訪(fǎng)問(wèn)時(shí)間由哪幾部分組成？2)若當(dāng)前磁頭在153號(hào)磁道，進(jìn)程請(qǐng)求訪(fǎng)問(wèn)的磁道為96,157,101,187,104,160,112,185,140。請(qǐng)用SCAN調(diào)度算法給出訪(fǎng)問(wèn)順序。(磁頭方向?yàn)橛尚〉酱?7、(8分)某操作系統(tǒng)的文件系統(tǒng)采用索引節(jié)點(diǎn)的結(jié)構(gòu)進(jìn)行文件管理，即文件所占用的盤(pán)塊號(hào)放在該文件的索引結(jié)點(diǎn)的13個(gè)地址頁(yè)中，前10個(gè)為直接尋址，后三個(gè)分別為一次間址，二次間址和三次間尋址。假設(shè)盤(pán)塊大小為1KB,每個(gè)間址放256個(gè)盤(pán)塊地址。問(wèn)：(1)這種文件系統(tǒng)可存放的最大文件為多少字節(jié)？(2)一個(gè)4MB大小的文件，要占用多少磁盤(pán)空間(多少盤(pán)塊)？8、(8分)(1)在某文件系統(tǒng)中，每個(gè)盤(pán)塊為256字節(jié)，文件控制塊占64個(gè)字節(jié)，其中文件名占8個(gè)字節(jié)。如果索引結(jié)點(diǎn)編號(hào)占2個(gè)字節(jié)，對(duì)一個(gè)存放在磁盤(pán)上的128個(gè)目錄項(xiàng)的目錄，試比較引入索引節(jié)點(diǎn)前后，為找到其中一個(gè)文件，平均啟動(dòng)磁盤(pán)的次數(shù)。(2)常用的提高文件系統(tǒng)性能的方法有哪些？南京航空航天大學(xué)2013年碩士研究生入學(xué)考試初試試題（ A卷）科目代碼：922科目名稱(chēng):_數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位） 酒7r型力注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在懵題紙?上,寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）（1）（2分）推導(dǎo)二叉樹(shù)的性質(zhì)3：度為2的結(jié)點(diǎn)數(shù)與度為。的結(jié)點(diǎn)數(shù)的關(guān)系。（2）（3分）推導(dǎo)二叉樹(shù)的性質(zhì)4：求解N個(gè)結(jié)點(diǎn)完全二叉樹(shù)的高度。（10分）畫(huà)出下圖（1）所示樹(shù)的三種存儲(chǔ)結(jié)構(gòu)示意圖。（10分）試用Dijkstra算法，求下圖（2）中從V1到其余各頂點(diǎn)的最短路徑,寫(xiě)出算法過(guò)程中每一步的狀態(tài)。過(guò)程中每一步的狀態(tài)。（10分）已知數(shù)據(jù)序列為（76,58.234,5,16,164,28,423,24,102）,給出基數(shù)排序過(guò)程的示意圖。（10分）設(shè)稀疏矩陣用三元組順序表存儲(chǔ)，用下面例子說(shuō)明快速轉(zhuǎn)置算法的執(zhí)行過(guò)程。A5x6=（（1.3,8）,（1,5,68）,（3,1,12）,（3,4,52）.（3,5,3）,（4,1,45）,（5,1,26））（10分）已知有兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B,元素值遞增有序，編寫(xiě)函數(shù)，調(diào)整刪減A鏈表，使A鏈表結(jié)點(diǎn)的元素值為A、B的交集，并成為一個(gè)遞減有序的單鏈表。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（10分）編寫(xiě)函數(shù)，用非遞歸方法，求二叉鏈表表示的二叉樹(shù)T的高度。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（10分）編寫(xiě)函數(shù),判斷一個(gè)有向圖是否存在回路。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。

操作系統(tǒng)部分（75分）一.簡(jiǎn)答（每題5分，共25分）1）為什么要引入線(xiàn)程，線(xiàn)程和進(jìn)程有何區(qū)別？2）為什么多道批處理操作系統(tǒng)可以提高資源利用率？什么是通道，通道經(jīng)常采用如圖所示的交叉連接，為什么？什么是通道，通道經(jīng)常采用如圖所示的交叉連接，為什么？4）簡(jiǎn)述操作系統(tǒng)引入緩沖的原因？5）何謂文件的物理結(jié)構(gòu)，可分為哪幾類(lèi)，比較其優(yōu)缺點(diǎn)？計(jì)算題共50分（10分）假設(shè)有個(gè)南北向的胡同很窄，僅能容同方向的人順序走過(guò)，相對(duì)方向的兩個(gè)人則無(wú)法通過(guò)?，F(xiàn)在胡同南北入口都有過(guò)路人?，F(xiàn)把每個(gè)過(guò)路人當(dāng)成一個(gè)進(jìn)程，用PV操作實(shí)現(xiàn)管理。（10分）設(shè)在批處理系統(tǒng)中有四道作業(yè)，它們進(jìn)入系統(tǒng)的時(shí)間及運(yùn)行時(shí)間如表所示。作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間（小時(shí)）18：002.0028:500.5039：000.1049:500.20設(shè)系統(tǒng)每次只選擇一個(gè)作業(yè)裝入主機(jī)，分別給出在下列算法中這組作業(yè)的運(yùn)行順序、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。（1）FCFS算法;（2）SJF算法。（8分）設(shè)系統(tǒng)有五個(gè)進(jìn)程（P0,PI,P2,P3,P4）和四類(lèi)資源（A,B,C,D］各種資源的數(shù)量分別為2,1,0,0,在T0時(shí)刻資源分配情況如下表：

進(jìn)程最大資源需求A當(dāng)前已分配到的資源ABCDBCDP000120012P127502000P266560034P343562354P406520332(1)當(dāng)前系統(tǒng)是否是安全的？為什么？(2)假定此時(shí)P2發(fā)出請(qǐng)求向量為Request(0,1,0,0),系統(tǒng)可否分配給它？為什么？4.(8分)進(jìn)程某時(shí)刻的頁(yè)表如下圖所示：頁(yè)號(hào)標(biāo)志主存塊號(hào)0141182031240510其中的數(shù)字為十進(jìn)制，頁(yè)號(hào)、塊號(hào)都以0開(kāi)始，頁(yè)的大小為2K字節(jié)，標(biāo)志為1是在內(nèi)存，標(biāo)志為。表示不在內(nèi)存。請(qǐng)回答下列問(wèn)題：(1)簡(jiǎn)述分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，一個(gè)邏輯地址到物理地址的轉(zhuǎn)換過(guò)程(并畫(huà)出地址轉(zhuǎn)換機(jī)構(gòu)圖)。⑵邏輯地址0x1830和0x206B對(duì)應(yīng)的物理地址是什么？(7分)說(shuō)明LRU相比FIFO算法有何優(yōu)點(diǎn)。當(dāng)分配給進(jìn)程的物理頁(yè)個(gè)數(shù)分別為3和4,頁(yè)面訪(fǎng)問(wèn)序列為4,3,2,1,43,5,4,3,2,1,5,采用LRU算法分別給出頁(yè)面走向。(7分)設(shè)磁盤(pán)的I/O請(qǐng)求隊(duì)列中的柱面號(hào)為:65,68,49,28,100,170,160,48,194.磁頭初始位置為110,磁臂方向由小到大，請(qǐng)給出分別采用最短尋道時(shí)間優(yōu)先的磁盤(pán)調(diào)度算法和電梯磁盤(pán)調(diào)度算法的柱面移動(dòng)次數(shù)，并給出操作系統(tǒng)采用何種磁盤(pán)調(diào)度算法更好，為什么？南京航空航天大學(xué)2014年碩士研究生入學(xué)考試初試試題（ A卷）科目代碼：922 分 分科目名稱(chēng)」數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）滿(mǎn)7r坨萬(wàn)注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在僭題綱上,寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）（5分）給出廣義表G=（（e,a）,（（b,（）,d）,c）,f）的以表頭表尾形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不意圖。（10分）解釋哈希表工作原理。將關(guān)鍵字序列（75,54.48.90,18,22.84.63）存儲(chǔ)在長(zhǎng)度為10的哈希表中，使用哈希函數(shù)H（key）=Key/10,并采用二次探測(cè)再散列法解決沖突，畫(huà)出哈希表示意圖。（10分）試用Floyd算法，求解下圖中各頂點(diǎn)之間的最短路徑，寫(xiě)出算法過(guò)程中每一步的狀態(tài)。（10分）已知數(shù)據(jù)序列為（555,88,499,58,808,170,797,275,653,460）,給出堆排序過(guò)程的示意圖。（10分）設(shè)有6個(gè)字符，其權(quán)值為（12,40,16,8,14,10）,給出進(jìn)行Huffman編碼的數(shù)據(jù)結(jié)構(gòu)和執(zhí)行過(guò)程示意圖。（10分）設(shè)一個(gè)帶頭結(jié)點(diǎn)的單鏈表L數(shù)據(jù)元素為（a1,a2,a3,a4 an）,編寫(xiě)函數(shù),調(diào)整該鏈表，使得數(shù)據(jù)元素次序?yàn)椋╝l.a3 an a4,a2）,要求T（n）=0（n）,先給出算法思想.再寫(xiě)出相應(yīng)代碼。（10分）設(shè)有一家譜樹(shù)T,用二叉鏈表結(jié)構(gòu)存儲(chǔ)（孩子兄弟表示法），樹(shù)中的結(jié)點(diǎn)信息為成員名字。編寫(xiě)函數(shù)，輸出家譜中共有多少代以及最后一代人數(shù)和成員名字。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（10分）編寫(xiě)函數(shù)，給有向無(wú)環(huán)圖G的每一個(gè)頂點(diǎn)賦以一個(gè)整數(shù)編號(hào)，要求：若頂點(diǎn)v到頂點(diǎn)W之間有一條弧，則頂點(diǎn)V的編號(hào)小于頂點(diǎn)W的編號(hào)。先給出算法思想，再寫(xiě)出相應(yīng)代碼。操作系統(tǒng)部分（75分）選擇題（共10小題，每小題1分，共10分）.下列關(guān)于操作系統(tǒng)的四種陳述中，正確的是（）0A.批處理操作系統(tǒng)必須在響應(yīng)時(shí)間內(nèi)處理完一個(gè)任務(wù)B.實(shí)時(shí)操作系統(tǒng)必須在規(guī)定時(shí)間內(nèi)處理完來(lái)自外部的事件C.分時(shí)操作系統(tǒng)必須在周轉(zhuǎn)時(shí)間內(nèi)處理完來(lái)自外部的事件D.分時(shí)操作系統(tǒng)必須在調(diào)度時(shí)間內(nèi)處理完來(lái)自外部的事件.設(shè)有兩個(gè)進(jìn)程A、B,各按以下順序使用P,V操作進(jìn)行同步。A進(jìn)程：B進(jìn)程：al—*P(sl)a2—*P(s2)a3—?V(s2)a4TV(sl)a5—?bl~*P(s2)b2—*P(sl)b3-V(sl)b4—?V(s2)b5—?試問(wèn)在下列執(zhí)行順序中，哪種情況會(huì)發(fā)生死鎖？（）A.a1,a2,a3,a4- B.bl,b2,b3,b4,b5C.a1ta2,b1,b2,a3,b3- D.a1.b1.a2.b2,a3,b3-.在內(nèi)存管理中，內(nèi)存利用率高且保護(hù)和共享容易的是（ ）內(nèi)存管理方式。A.分區(qū)管理 B.分頁(yè)管理C.分段管理 D.段頁(yè)式管理.操作系統(tǒng)中，很多事件會(huì)引起調(diào)度程序的運(yùn)行，但下列事件中不一定引起操作系統(tǒng)調(diào)度程序運(yùn)行是（）0A.當(dāng)前運(yùn)行著的進(jìn)程出錯(cuò)。B.當(dāng)前運(yùn)行著的進(jìn)程請(qǐng)求輸入/輸出。C.有新的進(jìn)程進(jìn)入就緒狀態(tài)。D.當(dāng)前運(yùn)行的進(jìn)程時(shí)間片用完。5.操作系統(tǒng)中調(diào)度算法是核心算法之一，下列關(guān)于調(diào)度算法的論述中正確的是（）0A.先來(lái)先服務(wù)調(diào)度算法對(duì)即對(duì)長(zhǎng)作業(yè)有利也對(duì)段作業(yè)有利。B.時(shí)間片輪調(diào)度算法轉(zhuǎn)只對(duì)長(zhǎng)作業(yè)有利。C.實(shí)時(shí)調(diào)度算法也要考慮作業(yè)的長(zhǎng)短問(wèn)題。D.高相應(yīng)比者優(yōu)先調(diào)度算法既有利于短作業(yè)又兼顧長(zhǎng)作業(yè)的作業(yè)還實(shí)現(xiàn)了先來(lái)先服務(wù)。.操作系統(tǒng)中產(chǎn)生死鎖的根本原因是（）oA.資源分配不當(dāng)和CPU太慢 B.系統(tǒng)資源數(shù)量不足C.作業(yè)調(diào)度不當(dāng)和進(jìn)程推進(jìn)順序不當(dāng) D.用戶(hù)數(shù)太多和CPU太慢.內(nèi)存管理中把作業(yè)地址空間中使用的邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存中的物理地址稱(chēng)為（）。A.鏈接B.裝入C.重定位D.虛擬化.I/O設(shè)備管理是操作系統(tǒng)的重要功能，那么下列對(duì)設(shè)備屬性的描述正確的是（）oA.字符設(shè)備的基本特征是可尋址到字節(jié)，即能指定輸入的源地址或輸出的目標(biāo)地址。B.共享設(shè)備必須是可尋址的和可隨機(jī)訪(fǎng)問(wèn)的設(shè)備。C.共享設(shè)備是指同一時(shí)間內(nèi)運(yùn)行多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)的設(shè)備。D.在分配共享設(shè)備和獨(dú)占設(shè)備時(shí)都可能引起進(jìn)程死鎖。.程序設(shè)計(jì)時(shí)需要調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用，被調(diào)用的系統(tǒng)調(diào)用命令經(jīng)過(guò)編譯后，形成若干參數(shù)和（）。A.訪(fǎng)管指令或軟中斷B.后動(dòng)I/O指令C.屏蔽中斷指令 D.通道指令.以時(shí)間換空間或者以空間換時(shí)間是操作系統(tǒng)的基本技術(shù)，以下以空間換時(shí)間的機(jī)制是（）oA.SPOOLINGB.虛擬存儲(chǔ)技術(shù) C.通道技術(shù)D.覆蓋技術(shù)二、簡(jiǎn)要分析題（共4小題，每小題5分，共20分）.從操作系統(tǒng)設(shè)計(jì)角度談?wù)勥M(jìn)程控制塊的作用。.解釋靜態(tài)鏈接和動(dòng)態(tài)鏈接是現(xiàn)代操作系統(tǒng)中兩種重要的鏈接方式，試比較同一程序經(jīng)過(guò)靜態(tài)鏈接和動(dòng)態(tài)鏈接后的可執(zhí)行文件大小，如果有不同分析原因。.試比較磁盤(pán)高速緩存和虛擬盤(pán)，提高文件系統(tǒng)性能的通常有哪些方法？.舉例說(shuō)明線(xiàn)性檢索法檢索過(guò)程（例如查找/usr/ast/mbox）三.綜合應(yīng)用題（共7小題，共45分）（6分）設(shè)在批處理系統(tǒng)中有四道作業(yè)，它們進(jìn)入系統(tǒng)的時(shí)間及運(yùn)行時(shí)間如表所示。作業(yè)號(hào)進(jìn)入時(shí)間運(yùn)行時(shí)間（小時(shí)）19：002.0029：500.50310:000.10410：500.20設(shè)系統(tǒng)每次只選擇一個(gè)作業(yè)裝入主機(jī)。問(wèn)：采用SJF調(diào)度算法，給出這組作業(yè)的運(yùn)行順序、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間；（6分）某操作系統(tǒng)采用分頁(yè)式虛擬存儲(chǔ)管理方法，現(xiàn)有一個(gè)進(jìn)程需要訪(fǎng)問(wèn)的地址序列（字節(jié)）分別是：115,228,120,88,446,102,321,432,260,167,假設(shè)該進(jìn)程的第0頁(yè)已經(jīng)裝入內(nèi)存，并分配給該進(jìn)程300字節(jié)內(nèi)，頁(yè)的大小為100字節(jié)，試回答以下問(wèn)題：（1）按LRU調(diào)度算法將產(chǎn)生多少次頁(yè)面置換，依次淘汰的頁(yè)號(hào)是什么？頁(yè)面置換率為多少？LRU頁(yè)面置換算法的基本思想是什么？（6分）設(shè)磁盤(pán)的1/0請(qǐng)求隊(duì)列中的柱面號(hào)分別為：155,158,139,118,190,260,250,138,284,磁頭初始位置為200,磁臂方向由小到大。（1）請(qǐng)給出采用SSTF的磁盤(pán)調(diào)度算法的磁頭的柱面移動(dòng)次數(shù)。（2）SSTF的磁盤(pán)調(diào)度算法有何缺點(diǎn)。（6分）簡(jiǎn)述消息緩沖隊(duì)列通信機(jī)制，并用信號(hào)量和wait,signal操作實(shí)現(xiàn)消息緩沖隊(duì)列通信機(jī)制中的發(fā)送和接受原語(yǔ)。5.（6分）設(shè)系統(tǒng)中有三種類(lèi)型的資源（A,B,C）和五個(gè)進(jìn)程（P1,P2,P3,P4,P5）,A的資源的數(shù)量為17.B的資源的數(shù)量為5,C的資源的數(shù)量為20,在T0時(shí)刻狀態(tài)如下：最大資源需求量已分配資源需求量ABCABCP1559212P2536402P34011405P4425204P5424314剩余資源數(shù)ABC233系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。T0時(shí)刻是否為安全狀態(tài)？若是請(qǐng)給出安全序列。（2）在T0時(shí)刻，若進(jìn)程P2請(qǐng)求資源（0,3,4）,是否能實(shí)施資源分配？為什么？（3）在（2）基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2,0,1）,是否能實(shí)施資源分配？為什么？（6分）一個(gè)進(jìn)程某時(shí)刻的頁(yè)表如下圖所示頁(yè)號(hào)標(biāo)心內(nèi)存塊號(hào)0121021831140510本題中的數(shù)字均為十進(jìn)制，頁(yè)號(hào)、塊號(hào)都以0開(kāi)始，頁(yè)的大小為2K字節(jié)，標(biāo)志為1表示頁(yè)面在內(nèi)存，標(biāo)志為0表示不在內(nèi)存；請(qǐng)回答下列問(wèn)題：⑴簡(jiǎn)述分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，一個(gè)邏輯地址到物理地址的轉(zhuǎn)換過(guò)程（并畫(huà)出地址轉(zhuǎn)換機(jī)構(gòu)圖）⑵邏輯地址5188和3199對(duì)應(yīng)的物理地址是什么？（9分）進(jìn)程同步機(jī)制都應(yīng)遵循的準(zhǔn)則是什么？以下程序中，P1和P2并發(fā)執(zhí)行是否滿(mǎn)足進(jìn)程同步機(jī)制應(yīng)遵循的準(zhǔn)則,為什么？varstatusl,status2：boolean；/*進(jìn)程P1*/RepeatWhilestatus2dono-op；Statusl=true臨界區(qū)代碼；Statusl=false剩余區(qū)代碼；UntiIflase；/*進(jìn)程P2*/RepeatWhilestatusldono-op；Status2=true臨界區(qū)代碼；Status2=false剩余區(qū)代碼；UntiIflase；南京航空航天大學(xué)2015年碩士研究生入學(xué)考試初試試題（滿(mǎn)分：150滿(mǎn)分：150分科目名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位）注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在畫(huà)列上，寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）（5分）已知一棵完全二叉樹(shù)共有999個(gè)結(jié)點(diǎn)，試求以下問(wèn)題，并給出求解過(guò)程。（1）樹(shù)的高度（2）葉子結(jié)點(diǎn)數(shù)（10分）應(yīng)用棧操作求解算術(shù)表達(dá)式：（28+10*2）/（11-5）,畫(huà)出棧的變化過(guò)程。（10分）已知帶權(quán)圖如下所示，用Prim算法從頂點(diǎn)2開(kāi)始產(chǎn)生最小生成樹(shù)，說(shuō)明算法思想，并給出求解所需的數(shù)據(jù)結(jié)構(gòu)和每一步執(zhí)行過(guò)程的相關(guān)數(shù)據(jù)變化。（10分）已知輸入數(shù)據(jù)序列為（68,40,25,21,33,12,58,51,16,36）,給出建立3階B-樹(shù)示意圖，再給出刪除51,16后的B-樹(shù)。（10分））解釋希爾排序的算法思想。對(duì)以下的數(shù)據(jù)序列，給出希爾排序過(guò)程的示意圖。（46.8,36,50,6,24,18,78,12,10）（10分）設(shè)一個(gè)帶頭結(jié)點(diǎn)的單鏈表L,數(shù)據(jù)元素為整數(shù)，編寫(xiě)函數(shù)，通過(guò)調(diào)整該鏈表的結(jié)點(diǎn)指針，對(duì)該鏈表進(jìn)行簡(jiǎn)單選擇排序（元素值從小到大）。先給出算法思想，再寫(xiě)相應(yīng)代碼。（10分）設(shè)二叉樹(shù)T,用二叉鏈表結(jié)構(gòu)存儲(chǔ)。編寫(xiě)函數(shù)，輸出最長(zhǎng)一枝（根到葉子）上的所有結(jié)點(diǎn)值。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（10分）基于圖的廣度優(yōu)先搜索策略，編寫(xiě)函數(shù)，判別以鄰接表存儲(chǔ)的有向圖G中，是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑（iwj）。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。操作系統(tǒng)部分（75分）（30分）文件系統(tǒng)是操作系統(tǒng)的主要功能之一，請(qǐng)?jiān)O(shè)計(jì)一個(gè)文件系統(tǒng)，需給出以下信息：（1）給出描述文件的數(shù)據(jù)結(jié)構(gòu)（即文件控制塊）和目錄結(jié)構(gòu)；（5分）（2）以索引節(jié)點(diǎn)為文件系統(tǒng)的物理文件組織結(jié)構(gòu)，圖示索引節(jié)點(diǎn)結(jié)構(gòu)，說(shuō)明其優(yōu)點(diǎn)；（5分）（3）以線(xiàn)性檢索法作為此文件系統(tǒng)的文件檢索方法，以實(shí)例方式給出檢索一個(gè)文件的過(guò)程（例如查找/usr/ast/mbox）;（10分）（4）為該文件系統(tǒng)設(shè)計(jì)幾個(gè)必要的系統(tǒng)調(diào)用，選其中一個(gè)為例，詳細(xì)說(shuō)明實(shí)現(xiàn)該系統(tǒng)調(diào)用的方法和過(guò)程（注意要使用以上設(shè)計(jì)中的數(shù)據(jù)結(jié)構(gòu)）。（10分）（10分）某機(jī)場(chǎng)只有一條飛機(jī)跑道，為了提高效率和安全性，現(xiàn)規(guī)定：當(dāng)飛機(jī)跑道有飛機(jī)起飛時(shí)，不允許飛機(jī)降落.但此時(shí)可以讓多架飛機(jī)逐個(gè)利用跑道起飛；反之，當(dāng)有飛機(jī)降落進(jìn)入跑道時(shí)則不允許起飛飛機(jī)進(jìn)入跑道，但允許飛機(jī)依次降落在跑道上，然后駛出跑道。請(qǐng)解決以下問(wèn)題：（1）請(qǐng)利用信號(hào)量和P、V操作正確實(shí)現(xiàn)飛機(jī)在跑道上起降。（要求：說(shuō)明所設(shè)的信號(hào)量的意義及初值）；（2）若把飛機(jī)看作進(jìn)程，為了合理實(shí)現(xiàn)對(duì)飛機(jī)進(jìn)程的管理，給出描述飛機(jī)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)。3. （9分）某段式存儲(chǔ)管理系統(tǒng)中采用如下段表：（用十進(jìn)制）段號(hào)段的長(zhǎng)度（字節(jié)）主存起始地址0500150118080026001000316801850試回答：⑴給定段號(hào)和段內(nèi)地址，圖示說(shuō)明完成段式管理中的地址變換過(guò)程。（3分）⑵計(jì)算[0,150],[1,98],[2,601],[3,50]的內(nèi)存地址，其中方號(hào)內(nèi)的第一元素為段號(hào)，第二元素為段內(nèi)地址。（3分）⑶存取主存中的一條指令或數(shù)據(jù)至少要訪(fǎng)問(wèn)幾次內(nèi)存？如何提高速度？（3分）

（8分）LRU算法的思想和依據(jù)是什么？請(qǐng)利用LRU算法解決下列問(wèn)題：在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假如系統(tǒng)分配給一個(gè)作業(yè)的物理塊數(shù)為3,此作業(yè)的頁(yè)面走向?yàn)?,4,3,3,8,3,6,8,4,3,8,3。試用LRU算法計(jì)算頁(yè)面置換次數(shù)。（5分）掃描算法（SCAN）是一種磁盤(pán)調(diào)度算法，它的優(yōu)化目標(biāo)是什么？設(shè)磁盤(pán)的I/O請(qǐng)求隊(duì)列中的柱面號(hào)依次為：35,58,40.28,80,160,143,38,204,磁頭初始位置為95,若采用SCAN（先由小到大開(kāi)始掃描）磁盤(pán)調(diào)度算法，磁頭移動(dòng)多少個(gè)磁道。9.6Kh/s送內(nèi)存送內(nèi)存-1位緩沖（5分）按照下圖說(shuō)明9.6Kh/s送內(nèi)存送內(nèi)存-1位緩沖⑻(b)(c)（8分）假設(shè)系統(tǒng)有五類(lèi)獨(dú)占資源：ri,r2,r3,r4,r5,各類(lèi)資源分別有：2,2,2,1,1個(gè)單位的資源，有五個(gè)進(jìn)程：P1,P2,P3,P4,P5,其中P1已占有2個(gè)單位的ri,且申請(qǐng)一個(gè)單位的r2和一個(gè)單位的r4；P2已占有一個(gè)單位的r2,且申請(qǐng)一個(gè)單位的ri;P3已占有一個(gè)單位的r2且申請(qǐng)一個(gè)單位的r2和一個(gè)單位的r3;P4已占有一個(gè)單位的r4和一個(gè)單位的r5,且申請(qǐng)一個(gè)單位的r3；P5已占有一個(gè)單位的r3且申請(qǐng)一個(gè)單位的r5o（1）試畫(huà)出該時(shí)刻的資源分配圖。（2）什么是死鎖定理，如何判斷（1）給出的資源分配圖中有無(wú)死鎖，給出判斷過(guò)程和結(jié)果。南京航空航天大學(xué)2016年碩士研究生招生考試初試試題（ A卷）科目代碼：922科目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位） 滿(mǎn)分：—分注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在牌題紙|上,寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）L（5分）解釋m階B-樹(shù)的5個(gè)特性。（10分）說(shuō)明基數(shù)排序的算法思想和數(shù)據(jù)結(jié)構(gòu)，對(duì)數(shù)據(jù)序列（130,6,458,92,12,836,250,59,525,272）,給出基數(shù)排序過(guò)程示意圖。（10分）求下圖中的關(guān)鍵路徑，給出算法思想和求解過(guò)程每一步的狀態(tài).（10分）輸入關(guān)鍵字序列（55,12,24,47,30,68,19）,建立平衡二叉樹(shù).說(shuō)明算法思想，給出插入和調(diào)整的具體過(guò)程示意圖.（10分）設(shè)稀琉矩陣用三元組順序表存儲(chǔ)，說(shuō)明快速轉(zhuǎn)置算法思想，并用下面例子解釋執(zhí)行過(guò)程。A5m6=（（1,3,21）,（2,1,16）,（2,3,9）,（3,3,16）,（4,2,58）,（4,5,8）,（5,1,66））（10分）設(shè)L為帶頭結(jié)點(diǎn)的單鏈表，元素值為整型.編寫(xiě)函數(shù)，刪除L中的重復(fù)結(jié)點(diǎn)（具有相同元素值的結(jié)點(diǎn)只保留一個(gè)）.先給出算法思想，再寫(xiě)出程序代碼.（10分）已知一棵二叉鏈表表示的二叉樹(shù)T,編寫(xiě)函數(shù)，判斷T是否是完全二叉樹(shù).先給出算法思想，再寫(xiě)出程序代碼。（10分）已知順序表（a“a”…a.）是小頂堆，編寫(xiě)函數(shù)，將（a,此???時(shí),aQ調(diào)整為小頂堆，要求T（n）=0（logm）.先給出算法思想，再寫(xiě)出相應(yīng)代碼.操作系統(tǒng)部分(75分)簡(jiǎn)答(25分.每題5分)(1)缺頁(yè)中斷與其他普通中斷的主要區(qū)別是什么？(2)開(kāi)發(fā)程序時(shí)用動(dòng)態(tài)鏈接庫(kù)有什么優(yōu)點(diǎn)？(3)在單緩沖情況下，為什么系統(tǒng)對(duì)一塊數(shù)據(jù)的處理時(shí)間為max(C,T)+M?(4)什么是通道，什么是通道的瓶頸問(wèn)題，如何處理此問(wèn)題，請(qǐng)畫(huà)出示意圖？(5)推動(dòng)I/O發(fā)展的動(dòng)力是什么，有哪幾個(gè)發(fā)展階段？(10分)回答下列問(wèn)題：(1)試說(shuō)明頁(yè)面置換算法在虛擬存儲(chǔ)管理中的重要性.(2分)FIFO算法適用于什么場(chǎng)合，又有何缺點(diǎn).(2分)(3)設(shè)頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5,當(dāng)物理頁(yè)框數(shù)分別是3和4時(shí)，試問(wèn)：采用FIFO、LRU置換算法產(chǎn)生的缺頁(yè)中斷分別是多少？(這里假設(shè)內(nèi)存開(kāi)始時(shí)都是空的并且只要是第一次用到的頁(yè)面都產(chǎn)生缺頁(yè)中斷)(6分)(10分)A、B兩個(gè)程序，程序A按順序使用CPU10秒，使用設(shè)備甲5秒，使用CPU5秒，使用設(shè)備乙10秒，最后使用CPU10秒，程序B按順序使用設(shè)備甲10秒，使用CPU10秒，使用設(shè)備乙10秒，使用CPU5秒，使用設(shè)備乙10秒.試問(wèn)：(1)在順序環(huán)境下執(zhí)行程序A和程序B,CPU的利用率是多少？(3分)(2)在多道程序環(huán)境下，CPU的利用率是多少？請(qǐng)畫(huà)出A、B程序的執(zhí)行過(guò)程.(4分)(3)多道批處理中，是否系統(tǒng)中并發(fā)的進(jìn)程越多，資源利用率越好，為什么？(3分)4.(10分)考慮5個(gè)進(jìn)程Pl、P2、P3、P4、P5,如下表，規(guī)定進(jìn)程的優(yōu)先級(jí)越小，優(yōu)先級(jí)越高，試計(jì)算在采用下述幾種調(diào)度算法時(shí)各個(gè)進(jìn)程周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間.假設(shè)忽略進(jìn)程的調(diào)度時(shí)間.(1)先來(lái)先服務(wù)調(diào)度算法(FCFS);(2)時(shí)間片輪轉(zhuǎn)調(diào)度算法(時(shí)間片為1ms)(RR);(3)最短作業(yè)優(yōu)先調(diào)度算法(SJF);(4)剝奪式優(yōu)先級(jí)調(diào)度算法(HPF).進(jìn)程提交時(shí)刻需要的CPU時(shí)間(ms)優(yōu)先級(jí)P1033P2265P3441

P4652P5824邏輯地址8 4 12段號(hào)內(nèi)號(hào)段頁(yè)邏輯地址8 4 12段號(hào)內(nèi)號(hào)段頁(yè)頁(yè)內(nèi)偏移01（1）說(shuō)明在段頁(yè)式系統(tǒng)中動(dòng)態(tài)地址變換過(guò)程.（4分）（2）計(jì)算虛地址200804（十進(jìn)制）的物理地址（用十進(jìn)制表示）（3分）.（3）計(jì)算物理地址32784（十進(jìn)制）的虛地址（用十進(jìn)制表示）（3分）.6.（10分）某工廠(chǎng)有兩個(gè)生產(chǎn)車(chē)間和一個(gè)裝配車(chē)間，生產(chǎn)車(chē)間生產(chǎn)A、B兩種零件，裝備車(chē)間把這兩種零件裝配成產(chǎn)品.生產(chǎn)車(chē)間甲把生產(chǎn)的A零件放到貨架F1上，生產(chǎn)車(chē)間乙把生產(chǎn)的B零件放到貨架F2上，假設(shè)兩個(gè)貨架的容量都是10個(gè)零件.裝配車(chē)間每次從貨架上取出一個(gè)A和一個(gè)B然后進(jìn)行裝配，請(qǐng)用P、V操作來(lái)進(jìn)行正確的三個(gè)車(chē)間管理.南京航空航天大學(xué)2017年碩士研究生入學(xué)考試初試試題（A卷）科目代碼：922 滿(mǎn)分. 分科目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位） 曬萬(wàn).但萬(wàn)注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在甌緞上，寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）（5分）已知帶權(quán)圖如下所示，用Kruskal算法產(chǎn)生最小生成樹(shù)，并說(shuō)明算法思想.（10分）為一個(gè)家譜管理程序設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，以一個(gè)四代人，11個(gè)家庭成員為例，（A有3個(gè)孩子Al、A2、A3;A1有2個(gè)孩子All、A12;A2無(wú)子,A3有3個(gè)孩子A31、A32,A33;All有1個(gè)孩子Alli;A32有1個(gè)孩子A321;其余尚無(wú)子），畫(huà)出家譜示意圖，給出所設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)示意圖，并給出在該存儲(chǔ)結(jié)構(gòu)上輸出第k代所有人員的算法思想.（10分）設(shè)有8個(gè)字符（a,b,c,d,e,f,g,h）,其權(quán)值為（48,15,20,12,6,61,8,10）,給出進(jìn)行Huffman編碼所用的數(shù)據(jù)結(jié)構(gòu)和求解過(guò)程數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)的最后結(jié)果。（10分）已知輸入數(shù)據(jù)序列為（58,68,42,10,88,32,70,52,55,46）,給出建立3階B-樹(shù)示意圖，再給出刪除55,70后的B-樹(shù)。（10分）試用Dijkstra算法，求下圖中從VI到其余各頂點(diǎn)的最短路徑，給出實(shí)現(xiàn)算法所用的數(shù)據(jù)結(jié)構(gòu)和求解過(guò)程中每一步的狀態(tài).（10分）設(shè)A、B為遞減有序（元素值為整型）的單鏈表，編寫(xiě)函數(shù)，利用原結(jié)點(diǎn)將它們合并成一個(gè)遞增有序的單鏈表，相同元素值只保留一個(gè)結(jié)點(diǎn).先給出算法思想，再寫(xiě)出相應(yīng)代碼.（10分）設(shè)二叉樹(shù)T,用二叉鏈表結(jié)構(gòu)存儲(chǔ).編寫(xiě)函數(shù)，對(duì)于每個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的空間.要求先給出算法思想，再寫(xiě)出相應(yīng)代碼.（10分）設(shè)有n個(gè)學(xué)生成績(jī)（0-100整數(shù)）的順序結(jié)構(gòu)線(xiàn)性表L,編寫(xiě)函數(shù)，將該線(xiàn)性表中調(diào)整為成績(jī)及格（大于等于60）在不及格之前，要求T（n）=O（n）,S（n）=O（l）。先給出算法思想，再寫(xiě)出相應(yīng)代碼.操作系統(tǒng)部分（75分）.單選題（10分，每題1分）.在下列系統(tǒng)中，（）是實(shí)時(shí)系統(tǒng).A.計(jì)算機(jī)激光照排系統(tǒng)B.軍用反導(dǎo)彈系統(tǒng)C.辦公自動(dòng)化系統(tǒng) D.計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng).引入多道程序的目的在于（）.A.充分利用CPU,減少CPU等待時(shí)間 B.提高實(shí)時(shí)響應(yīng)速度C.有利于代碼共享，減少主、輔存信息交換量 D.解放cpu對(duì)外設(shè)的管理.已經(jīng)獲得除（）以外的所有運(yùn)行所需資源的進(jìn)程處于就緒狀態(tài)A.存儲(chǔ)器B.打印機(jī)C.CPUD.磁盤(pán)空間.采用時(shí)間片輪轉(zhuǎn)法調(diào)度是為了（）.A.多個(gè)終端都能得到系統(tǒng)的及時(shí)響應(yīng) B.先來(lái)先服務(wù)C.優(yōu)先級(jí)較高的進(jìn)程得到及時(shí)調(diào)度 D.需CPU最短的進(jìn)程先做.在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪(fǎng)問(wèn)的資源，稱(chēng)為（）.A.共享資源 B.臨界區(qū)C.臨界資源D.共享區(qū).并發(fā)性是指若干事件在（）發(fā)生.A.同一時(shí)刻B.同一時(shí)間間隔內(nèi)C.不同時(shí)刻D.不同時(shí)間間隔內(nèi).管道通信是以（）進(jìn)行寫(xiě)入和讀出.A.消息為單位B.自然字符流C.文件D.報(bào)文.操作系統(tǒng)中有一組特殊的程序.它們不能被系統(tǒng)中斷，在操作系統(tǒng)中稱(chēng)為（）A.初始化程序B.原語(yǔ)C.子程序D.控制模塊.在分段管理中().A.以段為單位分配，每段是一個(gè)連續(xù)存儲(chǔ)區(qū)B.段與段之間必定不連續(xù)C.段與段之間必定連續(xù) D.每段是等長(zhǎng)的.通道是一種().A.I/O端口B.數(shù)據(jù)通道C.I/O專(zhuān)用處理機(jī) D.軟件工具.簡(jiǎn)答題(20分，每題4分).系統(tǒng)型線(xiàn)程和用戶(hù)型線(xiàn)程有何區(qū)別？.多級(jí)反饋隊(duì)列調(diào)度算法是如何工作的？.分段式系統(tǒng)和分頁(yè)式系統(tǒng)有何區(qū)別？.引入緩沖的目的是什么，有哪些常見(jiàn)的緩沖模式？.SPOOLING技術(shù)如何實(shí)現(xiàn)，在操作系統(tǒng)中起何作用？3.(9分)設(shè)有三道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間由下表給出：作業(yè)號(hào)提交時(shí)間執(zhí)行時(shí)間18.52.029.21.639.40.5(1)周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間的區(qū)別是什么，為何引入帶權(quán)周轉(zhuǎn)時(shí)間？(2分)(2)試計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間.(7分)(9分)某系統(tǒng)有A、B、C、D四類(lèi)資源可供五個(gè)進(jìn)程Pl、P2、P3、P4、P5共享.系統(tǒng)共有這四類(lèi)資源為：A類(lèi)3個(gè)、B類(lèi)14個(gè)、C類(lèi)12個(gè)、D類(lèi)12個(gè).進(jìn)程對(duì)資源的需求和分配情況如下:進(jìn)程已占有資源最大需求數(shù)ABCDABCDP100120012P210001750P313542356P406320652P500140656（1）現(xiàn)在系統(tǒng)是否處于安全狀態(tài)？（4分）（2）如果進(jìn)程P2提出需要A類(lèi)資源。個(gè)、B類(lèi)資源4個(gè)、C類(lèi)資源2個(gè)和D類(lèi)資源。個(gè),系統(tǒng)能否去滿(mǎn)足它的請(qǐng)求？（5分）（9分）某分頁(yè)系統(tǒng)，每個(gè)頁(yè)面長(zhǎng)為1KB,某時(shí)刻該用戶(hù)進(jìn)程的頁(yè)表如下：頁(yè)號(hào)物理塊號(hào)是否在快表中08是17是24否310否45否53是62是（1）請(qǐng)寫(xiě)出分頁(yè)系統(tǒng)的地址轉(zhuǎn)換過(guò)程（3分）（2）計(jì)算兩個(gè)邏輯地址：0AC5H、1AC5H對(duì)應(yīng)的物理地址（16進(jìn)制表示）.（3分）（3）已知主存的一次存取為2us,對(duì)于快表的查詢(xún)時(shí)間可以忽略，則訪(fǎng)問(wèn)上述兩個(gè)邏輯地址分別耗費(fèi)多少時(shí)間？（3分）（9分）在某請(qǐng)求分頁(yè)管理系統(tǒng)中，作業(yè)執(zhí)行時(shí)一次訪(fǎng)問(wèn)如下頁(yè)面：1,4,3,1,2,5,4,2,1,4,5,若分配給該作業(yè)的主存塊數(shù)為3.（1）頁(yè)面置換算法在虛擬存儲(chǔ)管理中的重要性.（2分））FIFO,LRU算法各適用于什么場(chǎng)合（3分）（3）計(jì)算FIFO,LRU,頁(yè)面置換算法，試求出缺頁(yè)中斷次數(shù).（4分）7.（9分）一家四口人，兒子喜歡吃蘋(píng)果，由父親負(fù)責(zé)購(gòu)買(mǎi)，女兒喜歡吃橘子，由母親負(fù)責(zé)購(gòu)買(mǎi).父親和母親購(gòu)買(mǎi)水果后放到家中的抽屜里，兒子和女兒從抽屜里取出水果。假設(shè)抽屜只能容納20個(gè)水果，同時(shí)只能一人開(kāi)關(guān)，用紀(jì)錄型信號(hào)量同步父母子女四個(gè)進(jìn)程。南京航空航天大學(xué)2018年碩士研究生入學(xué)考試初試試題（A卷）科目代碼：922 滿(mǎn)分.150分科目名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專(zhuān)業(yè)學(xué)位） 酒力.必方_注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫(xiě)在圈題園上,寫(xiě)在本試題紙或草稿紙上均無(wú)效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（5分）設(shè)n*n的矩陣A[l..n,l..n]為三角特殊矩陣，其逆對(duì)角線(xiàn)以上為0,逆對(duì)角線(xiàn)以及逆對(duì)角線(xiàn)以下的所有元素按行序壓縮存儲(chǔ)在一維數(shù)組B[l..n*（n+l）/2]中，根據(jù)i、j在滿(mǎn)足何種條件下，計(jì)算元素A”的存儲(chǔ)位置，給出推導(dǎo)過(guò)程.（1）帶雙親的孩子鏈表表示法（2）孩子兄弟表示法（1）帶雙親的孩子鏈表表示法（2）孩子兄弟表示法并說(shuō)明這二種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn).（10分）給定n個(gè)村莊之間的交通圖，邊上的值