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

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

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

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

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

5、43562354P406520332（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開始，頁(yè)的大小為2K字節(jié)，標(biāo)志為1是在內(nèi)存，標(biāo)志為0表示不在內(nèi)存。請(qǐng)回答下列問(wèn)題：(1)簡(jiǎn)述分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，一個(gè)邏輯地址到物理地址的轉(zhuǎn)換過(guò)程（并畫

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