南京航空航天大學922數(shù)據(jù)結(jié)構與操作系統(tǒng)真題2018年碩士研究生入學考試初試試題

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

2、試題紙須隨答題紙一起裝入試題袋中交回！效；③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構部分1（5分）設nn的矩陣A[1..n1..n]為三角特殊矩陣，其逆對角線以上為0，逆對角線以及逆對角線以下的所有元素按行序壓縮存儲在一維數(shù)組B[1..n(n1)2]中，根據(jù)i、j在滿足何種條件下，計算元素Aij的存儲位置，給出推導過程。2（10分）給出下圖所示樹的二種存儲結(jié)構示意圖。（1）帶雙親的孩子鏈表表示法（2）孩子兄弟表示法并說明這二種存

3、儲結(jié)構的優(yōu)缺點。3（10分）給定n個村莊之間的交通圖，邊上的值表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短？試選擇或構造一種適當?shù)臄?shù)據(jù)結(jié)構并設計一個算法，并應用該算法解答下圖所示的實例，給出算法執(zhí)行示意圖。4（10分）詳細解釋哈希表的工作原理。以此為例，將關鍵字序列（51，83，43，15，62，59，74，61）存儲在長度為10的哈希表中，使用哈希函數(shù)

4、H(key)=Key%10，并采用鏈地址法解決沖突，畫出哈希表示意圖。AEDCIKGBHFJV3V2V4V1346102科目代碼：922科目名稱：數(shù)據(jù)結(jié)構與操作系統(tǒng)(專業(yè)學位)第3頁共4頁3.（9分）多道程序系統(tǒng)有一個CPU和兩臺獨占設備，即IO1和IO2，現(xiàn)在有3個優(yōu)先級別從高到低的作業(yè)J1、J2、J3到達，它們使用資源的先后順序和占用時間分別是：J1：IO2（60）；CPU（20）；IO1（60）；CPU（20）J2：IO1（40）

5、；CPU（40）；IO2（80）J3：CPU（60）；IO1（40）假設處理機調(diào)度采用可搶占的優(yōu)先級算法，設備不能搶占，忽略調(diào)度時間，時間單位為分鐘。計算下列問題：（1）分別計算3個作業(yè)的周轉(zhuǎn)時間（3分）（2）3個作業(yè)全部完成時CPU的利用率（3分）（3）3個作業(yè)全部完成時IO1的利用率（3分）4.（9分）磁盤請求柱面按102220240638的次序到達，當前磁頭在柱面20上。（1）磁盤訪問時間由哪幾部組成，如何計算？（3分）（2）計算

6、采用SSTF，SCAN算法（先由小到大）磁頭移動順序。（3分）（3）如何應用RAID(廉價磁盤冗余陣列)提高磁盤的訪問速度，請畫圖示意。（3分）5.（9分）五個進程P1，P2，P3，P4，P5均需要使用資源A、B、C。其中，A、B、C資源的總數(shù)分別為10，5，7。當前已分配資源情況和各進程的最大資源需求如下表所示。進程最大需求資源已分配資源P1（753）（010）P2（322）（200）P3（902）（302）P4（222）（211）P