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

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

2、交回！效；③本試題紙須隨答題紙一起裝入試題袋中交回?。ㄒ弧?shù)據(jù)結(jié)構(gòu)部分50分）1.(1)（2分）推導(dǎo)二叉樹(shù)的性質(zhì)3：度為2的結(jié)點(diǎn)數(shù)與度為0的結(jié)點(diǎn)數(shù)的關(guān)系。(2)（3分）推導(dǎo)二叉樹(shù)的性質(zhì)4：求解N個(gè)結(jié)點(diǎn)完全二叉樹(shù)的高度。(3)（5分））將關(guān)鍵字序列（75，24，8，10，28，64，16，35）存儲(chǔ)在長(zhǎng)度為10的哈希表中，使用哈希函數(shù)H(key)=Key%10，并采用二次探測(cè)再散列法解決沖突，說(shuō)明關(guān)鍵字存儲(chǔ)位置的計(jì)算方法，畫(huà)出哈希表示意圖

3、。2.（10分）試用Dijkstra算法，求下圖中從V1到其余各頂點(diǎn)的最短路徑，寫(xiě)出算法過(guò)程中每一步的狀態(tài)。3.（10分）設(shè)稀疏矩陣用三元組順序表存儲(chǔ)，用下面例子說(shuō)明快速轉(zhuǎn)置算法的執(zhí)行過(guò)程。A56=((138)(1568)(3112)(3452)(353)(4145)(5126))4（10分）已知有兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，元素值遞增有序，編寫(xiě)函數(shù)，調(diào)整刪減A鏈表，使A鏈表結(jié)點(diǎn)的元素值為A、B的交集，并成為一個(gè)遞減有序的單鏈表。要求先

4、給出算法思想，再寫(xiě)出相應(yīng)代碼。5.（10分）編寫(xiě)函數(shù)，用非遞歸方法，求二叉鏈表表示的二叉樹(shù)T的高度。要求先給出算法思想，再寫(xiě)出相應(yīng)代碼。（二、操作系統(tǒng)部分50分）1.簡(jiǎn)答題（20分，每題5分）（1）為什么要引入線程，線程和進(jìn)程有何區(qū)別？V2V4V5V6V1V31231377516科目代碼：829科目名稱：計(jì)算機(jī)專業(yè)基礎(chǔ)第3頁(yè)共4頁(yè)標(biāo)志為0表示不在內(nèi)存。請(qǐng)回答下列問(wèn)題：(1)簡(jiǎn)述分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，一個(gè)邏輯地址到物理地址的轉(zhuǎn)換過(guò)程（并畫(huà)

5、出地址轉(zhuǎn)換機(jī)構(gòu)圖）。(2)邏輯地址0x1830和0x206B對(duì)應(yīng)的物理地址是什么？5.(6分)設(shè)磁盤(pán)的IO請(qǐng)求隊(duì)列中的柱面號(hào)為：6568492810017016048194.磁頭初始位置為110，磁臂方向由小到大，請(qǐng)給出分別采用最短尋道時(shí)間優(yōu)先的磁盤(pán)調(diào)度算法和電梯磁盤(pán)調(diào)度算法的柱面移動(dòng)次數(shù)，并給出操作系統(tǒng)采用何種磁盤(pán)調(diào)度算法更好，為什么？（三、計(jì)算機(jī)組成原理部分50分）1（10分）若某機(jī)內(nèi)部浮點(diǎn)機(jī)器數(shù)的階碼和尾數(shù)分別用移碼和補(bǔ)碼表示，設(shè)

6、階碼4位，階符1位，尾數(shù)14位，尾數(shù)符號(hào)1位，偏置常數(shù)為16（格式如下）：數(shù)符階符階碼尾數(shù)1位1位4位14位（1）把十進(jìn)制數(shù)x=(128.75)2－2寫(xiě)成該格式表示的浮點(diǎn)機(jī)器數(shù)［x］?。ㄒ?6進(jìn)制表示）。（2）若已知另一個(gè)機(jī)器數(shù)[y]浮=D9F00H，求xy的和所對(duì)應(yīng)的機(jī)器數(shù)[xy]?。ㄒ?6進(jìn)制表示）。2（10分）總線鏈?zhǔn)脚袃?yōu)是集中式總線仲裁方案的一種，請(qǐng)回答一下問(wèn)題：（1）簡(jiǎn)述總線鏈?zhǔn)脚袃?yōu)控制方式的優(yōu)缺點(diǎn)。（2）除了鏈?zhǔn)脚袃?yōu)外還有哪

7、兩種方案屬于集中式總線仲裁？（3）設(shè)總線的時(shí)鐘頻率為80MHz，一個(gè)總線周期等于一個(gè)時(shí)鐘周期。如果一個(gè)總線周期中并行傳送32位數(shù)據(jù)，求該總線的帶寬。3（10分）設(shè)CPU有20根地址線，8根數(shù)據(jù)線。并用IOM作訪存控制信號(hào)。RD為讀命令，WR為寫(xiě)命令。現(xiàn)有8K8位ROM以及8K8位RAM若干以及譯碼器和門(mén)電路芯片若干。（1）系統(tǒng)可訪問(wèn)的最大存儲(chǔ)空間是多少？（2）要求最小16K為系統(tǒng)程序區(qū)，最后32K為用戶程序區(qū)，請(qǐng)分別寫(xiě)出系統(tǒng)程序區(qū)及用戶