2013南京航空航天大學(xué)考研真題之?dāng)?shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)（專業(yè)學(xué)位）

1、科目代碼：922科目名稱：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)第1頁共3頁南京航空航天大學(xué)南京航空航天大學(xué)2013年碩士研究生入學(xué)考試初試試題（A卷）2013年碩士研究生入學(xué)考試初試試題（A卷）科目代碼:922科目名稱:數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)滿分:150分注意:①認(rèn)真閱讀答題紙上的注意事項；②所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上均無①認(rèn)真閱讀答題紙上的注意事項；②所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上均無效；③本試題紙須隨答題紙一起裝入

2、試題袋中交回！效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）數(shù)據(jù)結(jié)構(gòu)部分（75分）1.(1)（2分）推導(dǎo)二叉樹的性質(zhì)3：度為2的結(jié)點數(shù)與度為0的結(jié)點數(shù)的關(guān)系。(2)（3分）推導(dǎo)二叉樹的性質(zhì)4：求解N個結(jié)點完全二叉樹的高度。2.（10分）畫出下圖（1）所示樹的三種存儲結(jié)構(gòu)示意圖。3.（10分）試用Dijkstra算法，求下圖（2）中從V1到其余各頂點的最短路徑，寫出算法過程中每一步的狀態(tài)。（1）（2）4.（10分）已

3、知數(shù)據(jù)序列為(76582345161642842324102)，給出基數(shù)排序過程的示意圖。5.（10分）設(shè)稀疏矩陣用三元組順序表存儲，用下面例子說明快速轉(zhuǎn)置算法的執(zhí)行過程。A56=((138)(1568)(3112)(3452)(353)(4145)(5126))6（10分）已知有兩個帶頭結(jié)點的單鏈表A和B，元素值遞增有序，編寫函數(shù)，調(diào)整刪減A鏈表，使A鏈表結(jié)點的元素值為A、B的交集，并成為一個遞減有序的單鏈表。要求先給出算法思想，再寫

4、出相應(yīng)代碼。7.（10分）編寫函數(shù)，用非遞歸方法，求二叉鏈表表示的二叉樹T的高度。要求先給出算法思想，再寫出相應(yīng)代碼。8.（10分）編寫函數(shù)，判斷一個有向圖是否存在回路。要求先給出算法思想，再寫出相應(yīng)代碼。AECDIFGBHV2V4V5V6V1V312313710516科目代碼：922科目名稱：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)第3頁共3頁進(jìn)程最大資源需求ABCD當(dāng)前已分配到的資源ABCDP000120012P127502000P266560034P3

5、43562354P406520332（1）當(dāng)前系統(tǒng)是否是安全的？為什么？（2）假定此時P2發(fā)出請求向量為Request(0，1，0，0)，系統(tǒng)可否分配給它？為什么？4.(8分)進(jìn)程某時刻的頁表如下圖所示：頁號標(biāo)志主存塊號0141182031240510其中的數(shù)字為十進(jìn)制，頁號、塊號都以0開始，頁的大小為2K字節(jié)，標(biāo)志為1是在內(nèi)存，標(biāo)志為0表示不在內(nèi)存。請回答下列問題：(1)簡述分頁式虛擬存儲系統(tǒng)中，一個邏輯地址到物理地址的轉(zhuǎn)換過程（并畫

6、出地址轉(zhuǎn)換機(jī)構(gòu)圖）。(2)邏輯地址0x1830和0x206B對應(yīng)的物理地址是什么？5.(7分)說明LRU相比FIFO算法有何優(yōu)點。當(dāng)分配給進(jìn)程的物理頁個數(shù)分別為3和4，頁面訪問序列為432143543215，采用LRU算法分別給出頁面走向。6.(7分)設(shè)磁盤的IO請求隊列中的柱面號為：6568492810017016048194.磁頭初始位置為110，磁臂方向由小到大，請給出分別采用最短尋道時間優(yōu)先的磁盤調(diào)度算法和電梯磁盤調(diào)度算法的柱面