2013南京航空航天大學考研真題之計算機專業(yè)基礎

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

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

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

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

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

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

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