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

1、科目代碼：922科目名稱：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)第1頁(yè)共5頁(yè)南京航空航天大學(xué)南京航空航天大學(xué)2014年碩士研究生入學(xué)考試初試試題（A卷）2014年碩士研究生入學(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.（5分）給出廣義表G=(（ea)((b，（）d)c)f)的以表頭表尾形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。2.（10分）解釋哈希表工作原理。將關(guān)鍵字序列（75，54，48，90，18，22，84，63）存儲(chǔ)在長(zhǎng)度為10的哈希表中，使用哈希函數(shù)H(key)=Key%10，并采用二次探測(cè)再散列法解決沖突，畫出哈希表示意圖。3.（10分）試用Flo

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

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

5、與操作系統(tǒng)第3頁(yè)共5頁(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ù)。6.操作系統(tǒng)中產(chǎn)生死鎖的根本原因是（）。A.資源分配不當(dāng)和CPU太慢B.系統(tǒng)資源數(shù)量不足C.作業(yè)調(diào)度不當(dāng)和進(jìn)程推進(jìn)順序不當(dāng)D.用戶數(shù)太多和CPU太慢7內(nèi)存管理中把作業(yè)地址空間中使用的邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存中的物理地址稱為()。A.鏈接B.裝入C.重定位D.虛擬化8IO設(shè)備管理是操作系統(tǒng)的重要功能，那么下

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

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