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

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

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

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

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

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