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

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

2、試題袋中交回！效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（75分）數(shù)據(jù)結(jié)構(gòu)部分（75分）1.（5分）給出廣義表G=(（ea)((b，（）d)c)f)的以表頭表尾形式的鏈式存儲結(jié)構(gòu)示意圖。2.（10分）解釋哈希表工作原理。將關(guān)鍵字序列（75，54，48，90，18，22，84，63）存儲在長度為10的哈希表中，使用哈希函數(shù)H(key)=Key%10，并采用二次探測再散列法解決沖突，畫出哈希表示意圖。3.（10分）試用Flo

3、yd算法，求解下圖中各頂點之間的最短路徑，寫出算法過程中每一步的狀態(tài)。4.（10分）已知數(shù)據(jù)序列為(5558849958808170797275653460)，給出堆排序過程的示意圖。5.（10分）設(shè)有6個字符，其權(quán)值為（12，40，16，8，14，10），給出進行Huffman編碼的數(shù)據(jù)結(jié)構(gòu)和執(zhí)行過程示意圖。6（10分）設(shè)一個帶頭結(jié)點的單鏈表L，數(shù)據(jù)元素為（a1a2a3a4...an）編寫函數(shù)，調(diào)整該鏈表，使得數(shù)據(jù)元素次序為（a1a3

4、...an...a4a2）要求T(n)=O(n)，先給出算法思想，再寫出相應(yīng)代碼。7.（10分）設(shè)有一家譜樹T，用二叉鏈表結(jié)構(gòu)存儲（孩子兄弟表示法），樹中的結(jié)點信息為成員名字。編寫函數(shù)，輸出家譜中共有多少代以及最后一代人數(shù)和成員名字。要求先給出算法思想，再寫出相應(yīng)代碼。8.（10分）編寫函數(shù)，給有向無環(huán)圖G的每一個頂點賦以一個整數(shù)編號，要求：若頂點vV2V4V1V31223715（專業(yè)學(xué)位）（專業(yè)學(xué)位）科目代碼：922科目名稱：數(shù)據(jù)結(jié)構(gòu)

5、與操作系統(tǒng)第3頁共5頁C.實時調(diào)度算法也要考慮作業(yè)的長短問題。D.高相應(yīng)比者優(yōu)先調(diào)度算法既有利于短作業(yè)又兼顧長作業(yè)的作業(yè)還實現(xiàn)了先來先服務(wù)。6.操作系統(tǒng)中產(chǎn)生死鎖的根本原因是（）。A.資源分配不當和CPU太慢B.系統(tǒng)資源數(shù)量不足C.作業(yè)調(diào)度不當和進程推進順序不當D.用戶數(shù)太多和CPU太慢7內(nèi)存管理中把作業(yè)地址空間中使用的邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存中的物理地址稱為()。A.鏈接B.裝入C.重定位D.虛擬化8IO設(shè)備管理是操作系統(tǒng)的重要功能，那么下

6、列對設(shè)備屬性的描述正確的是()。A.字符設(shè)備的基本特征是可尋址到字節(jié)，即能指定輸入的源地址或輸出的目標地址。B.共享設(shè)備必須是可尋址的和可隨機訪問的設(shè)備。C.共享設(shè)備是指同一時間內(nèi)運行多個進程同時訪問的設(shè)備。D.在分配共享設(shè)備和獨占設(shè)備時都可能引起進程死鎖。9程序設(shè)計時需要調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用，被調(diào)用的系統(tǒng)調(diào)用命令經(jīng)過編譯后，形成若干參數(shù)和()。A.訪管指令或軟中斷B.啟動IO指令C.屏蔽中斷指令D.通道指令10.以時間換空間或者

7、以空間換時間是操作系統(tǒng)的基本技術(shù)，以下以空間換時間的機制是()。A.SPOOLINGB.虛擬存儲技術(shù)C.通道技術(shù)D.覆蓋技術(shù)二、簡要分析題(共4小題，每小題5分，共20分)1從操作系統(tǒng)設(shè)計角度談?wù)勥M程控制塊的作用。2解釋靜態(tài)鏈接和動態(tài)鏈接是現(xiàn)代操作系統(tǒng)中兩種重要的鏈接方式，試比較同一程序經(jīng)過靜態(tài)鏈接和動態(tài)鏈接后的可執(zhí)行文件大小，如果有不同分析原因。3試比較磁盤高速緩存和虛擬盤，提高文件系統(tǒng)性能的通常有哪些方法？4舉例說明線性檢索法檢索過