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

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

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

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

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

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

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