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

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

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

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

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

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

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

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

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

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