南京航空航天大學(xué)2014年計(jì)算機(jī)專業(yè)基礎(chǔ)考研真題

1、科目代碼：829科目名稱：計(jì)算機(jī)專業(yè)基礎(chǔ)第1頁共5頁南京航空航天大學(xué)南京航空航天大學(xué)20142014年碩士研究生入學(xué)考試初試試題年碩士研究生入學(xué)考試初試試題（A卷）科目代碼:829滿分:150分科目名稱:計(jì)算機(jī)專業(yè)基礎(chǔ)注意:①認(rèn)真閱讀答題紙上的注意事項(xiàng)認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫在所有答案必須寫在答題紙答題紙上，寫在本試題紙或草稿紙上均無寫在本試題紙或草稿紙上均無效；③本試題紙須隨答題紙一起裝入試題袋中交回本試題紙須隨答

2、題紙一起裝入試題袋中交回?。ㄒ弧?shù)據(jù)結(jié)構(gòu)部分50分）1.（10分）解釋哈希表工作原理。將關(guān)鍵字序列（75，54，48，90，18，22，84，63）存儲(chǔ)在長度為10的哈希表中，使用哈希函數(shù)H(key)=Key%10，并采用二次探測再散列法解決沖突，畫出哈希表示意圖。2.（10分）試用Floyd算法，求解下圖中各頂點(diǎn)之間的最短路徑，寫出算法過程中每一步的狀態(tài)。3.（10分）設(shè)有6個(gè)字符，其權(quán)值為（12，40，16，8，14，10），給出進(jìn)

3、行Huffman編碼的數(shù)據(jù)結(jié)構(gòu)和執(zhí)行過程示意圖。4（10分）設(shè)一個(gè)帶頭結(jié)點(diǎn)的單鏈表L，數(shù)據(jù)元素為（a1a2a3a4...an）編寫函數(shù)，調(diào)整該鏈表，使得數(shù)據(jù)元素次序?yàn)椋╝1a3...an...a4a2）要求T(n)=O(n)，先給出算法思想，再寫出相應(yīng)代碼。5.（10分）設(shè)有一家譜樹T，用二叉鏈表結(jié)構(gòu)存儲(chǔ)（孩子兄弟表示法），樹中的結(jié)點(diǎn)信息為成員名字。編寫函數(shù)，輸出家譜中共有多少代以及最后一代人數(shù)和成員名字。要求先給出算法思想，再寫出相應(yīng)

4、代碼。（二、操作系統(tǒng)部分50分）一填空題(共10小題，每小題1分，共10分)1下列關(guān)于操作系統(tǒng)的四種陳述中，正確的是：_________。（A）批處理操作系統(tǒng)必須在響應(yīng)時(shí)間內(nèi)處理完一個(gè)任務(wù)（B）實(shí)時(shí)操作系統(tǒng)必須在規(guī)定時(shí)間內(nèi)處理完來自外部的事件（C）分時(shí)操作系統(tǒng)必須在周轉(zhuǎn)時(shí)間內(nèi)處理完來自外部的事件（D）分時(shí)操作系統(tǒng)必須在調(diào)度時(shí)間內(nèi)處理完來自外部的事件V2V4V1V31223715科目代碼：829科目名稱：計(jì)算機(jī)專業(yè)基礎(chǔ)第3頁共5頁（A）S

5、POOLING（B）虛擬存儲(chǔ)技術(shù)（C）通道技術(shù)（D）覆蓋技術(shù)二、簡要分析題(共2小題，每小題5分，共10分)1從操作系統(tǒng)設(shè)計(jì)角度談?wù)勥M(jìn)程控制塊的作用。2解釋靜態(tài)鏈接和動(dòng)態(tài)鏈接是現(xiàn)代操作系統(tǒng)中兩種重要的鏈接方式，試比較同一程序經(jīng)過靜態(tài)鏈接和動(dòng)態(tài)鏈接后的可執(zhí)行文件大小，如果有不同分析原因。三綜合應(yīng)用題（共5小題，共30分）1（6分）某操作系統(tǒng)采用分頁式虛擬存儲(chǔ)管理方法，現(xiàn)有一個(gè)進(jìn)程需要訪問的地址序列(字節(jié))分別是：115，228，120，8

6、8，446，102，321，432，260，167，假設(shè)該進(jìn)程的第0頁已經(jīng)裝入內(nèi)存，并分配給該進(jìn)程300字節(jié)內(nèi)，頁的大小為100字節(jié)，試回答以下問題：（1）按LRU調(diào)度算法將產(chǎn)生多少次頁面置換，依次淘汰的頁號是什么？頁面置換率為多少？（2）LRU頁面置換算法的基本思想是什么？2.（6分）設(shè)磁盤的IO請求隊(duì)列中的柱面號分別為：155158139118190260250138284，磁頭初始位置為200，磁臂方向由小到大。（1）請給出采用S

7、STF的磁盤調(diào)度算法的磁頭的柱面移動(dòng)次數(shù)。（2）SSTF的磁盤調(diào)度算法有何缺點(diǎn)？3.（6分）簡述消息緩沖隊(duì)列通信機(jī)制，并用信號量和wait，signal操作實(shí)現(xiàn)消息緩沖隊(duì)列通信機(jī)制中的發(fā)送和接受原語.4（6分）設(shè)系統(tǒng)中有三種類型的資源（A，B，C）和五個(gè)進(jìn)程（P1，P2，P3，P4，P5），A的資源的數(shù)量為17，B的資源的數(shù)量為5，C的資源的數(shù)量為20，在T0時(shí)刻狀態(tài)如下：最大資源需求量已分配資源需求量ABCABCP1559212P25