南航2017考研真題922數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)

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

2、入試題袋中交回本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分?jǐn)?shù)據(jù)結(jié)構(gòu)部分（7575分）1（5分）已知帶權(quán)圖如下所示，用Kruskal算法產(chǎn)生最小生成樹，并說明算法思想。2（10分）為一個(gè)家譜管理程序設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，以一個(gè)四代人，11個(gè)家庭成員為例，（A有3個(gè)孩子A1、A2、A3；A1有2個(gè)孩子A11、A12；A2無子，A3有3個(gè)孩子A31、A32、A33；A11有1個(gè)孩子A111；A32有1個(gè)孩子A321；其余尚無子），畫出家譜

3、示意圖，給出所設(shè)計(jì)的存儲結(jié)構(gòu)示意圖，并給出在該存儲結(jié)構(gòu)上輸出第k代所有人員的算法思想。3.（10分）設(shè)有8個(gè)字符（abcdefgh），其權(quán)值為（48152012661810），給出進(jìn)行Huffman編碼所用的數(shù)據(jù)結(jié)構(gòu)和求解過程數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)的最后結(jié)果。4（10分）已知輸入數(shù)據(jù)序列為(58684210883270525546)，給出建立3階B樹示意圖，再給出刪除55，70后的B樹。5（10分）試用Dijkstra算法，求下圖中從V1到其余

4、各頂點(diǎn)的最短路徑，給出實(shí)現(xiàn)算法所用的數(shù)據(jù)結(jié)構(gòu)和求解過程中每一步的狀態(tài)。V2V4V5V6V1V37258610310V2V6V3V4V1V5215894183科目代碼：922科目名稱：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)(專業(yè)學(xué)位)第3頁共4頁（9）.在分段管理中()。A以段為單位分配，每段是一個(gè)連續(xù)存儲區(qū)B段與段之間必定不連續(xù)C段與段之間必定連續(xù)D每段是等長的（10）.通道是一種()。A.I／O端口B數(shù)據(jù)通道CI／O專用處理機(jī)D軟件工具2.簡答題（20分

5、，每題4分）（1）.系統(tǒng)型線程和用戶型線程有何區(qū)別？（2）.多級反饋隊(duì)列調(diào)度算法是如何工作的？（3）.分段式系統(tǒng)和分頁式系統(tǒng)有何區(qū)別？（4）.引入緩沖的目的是什么，有哪些常見的緩沖模式？（5）.SPOOLING技術(shù)如何實(shí)現(xiàn)，在操作系統(tǒng)中起何作用？3.（9分）設(shè)有三道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間由下表給出:作業(yè)號提交時(shí)間執(zhí)行時(shí)間18.52.029.21.639.40.5（1）周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間的區(qū)別是什么，為何引入帶權(quán)周轉(zhuǎn)時(shí)間？（2