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

南京航空航天大學(xué)2021年[計算機專業(yè)基礎(chǔ)]考研真題[數(shù)據(jù)結(jié)構(gòu)部分]1．（10分）給定n個村莊之間的交通圖，邊上的值表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短？試選擇或構(gòu)造一種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)并設(shè)計一個算法，并應(yīng)用該算法解答下圖所示的實例，給出算法執(zhí)行過程示意圖。2．（10分）詳細解釋哈希表的工作原理。以此為例，將關(guān)鍵字序列（51，83，43，15，62，59，74，61）存儲在長度為10的哈希表中，使用哈希函數(shù)H(key)=Key%10，并采用鏈地址法解決沖突，畫出哈希表示意圖。3．（10分）設(shè)有一批需實時處理的數(shù)據(jù)元素組成集合S，實時處理開始后，每隔一秒鐘收到一個新的數(shù)據(jù)元素加入S?，F(xiàn)要求在每次接收一個新元素之前，找出S中現(xiàn)有的最小元素并將其輸出（從S中刪除）。試選擇或構(gòu)造一種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)并設(shè)計一個算法，盡可能高效地完成上述任務(wù)。例如：S=(59,31,29,18,78,26,48,10,65,35)，新接受的數(shù)據(jù)為39，12，46….。以此為例說明算法執(zhí)行過程示意圖。4．（10分）設(shè)一個帶頭結(jié)點的單鏈表L，數(shù)據(jù)元素為整數(shù)，其中大部分為正數(shù)，少數(shù)為負(fù)數(shù)，編寫函數(shù)，采用高效的算法調(diào)整鏈表，實現(xiàn)將負(fù)數(shù)結(jié)點移到鏈表尾部，并返回調(diào)整后鏈表中的第一個負(fù)數(shù)結(jié)點位置。先給出算法思想，再寫相應(yīng)代碼。5.（10分）設(shè)二叉樹T，用二叉鏈表結(jié)構(gòu)存儲，元素值為整數(shù)且互不相同。編寫非遞歸函數(shù)，對給定的2個整數(shù)，若2個都不是T的元素，輸出-2；若1個不是T的元素，輸出-1；若2個都是T的元素，輸出兩者所在的層數(shù)的間隔數(shù)。要求先給出算法思想，再寫代碼。組成原理部分（50分）6.(8分）如下為一流水和一非流水處理器的參數(shù)，請按要求計算：若一程序有20%的ALU指令,10%的控制指令和70%的訪存指令，上述哪種設(shè)計更快？請用合適的指標(biāo)評估。7.（10分）若有一源程序hello.c文件：1)簡述如何生成相應(yīng)的可執(zhí)行程序；2）簡述該可執(zhí)行程序如何在計算機上執(zhí)行的過程。8.（10分）對于一n位運算器，通常得到其運算結(jié)果F的同時也輸出相應(yīng)的標(biāo)志信號如ZF（零標(biāo)志位），SF（符號標(biāo)志位），CF（進位標(biāo)志位）和OF（溢出標(biāo)志位）等：1）請用邏輯表達式表示出上述各標(biāo)志信號如何根據(jù)運算結(jié)果F的相應(yīng)位產(chǎn)生并做出解釋；2）若需完成兩有符號數(shù)比大小，請問需采用何種運算且如何利用上述標(biāo)志位判別；9.（10分）假定計算機系統(tǒng)主存空間大小為32Kx16位，且有一個4K字的4路組相聯(lián)Cache，主存和Cache之間的數(shù)據(jù)交換塊的大小為64字。假定Cache開始為空，處理器順序地從存儲單元0、1、…、4351中取數(shù)，一共重復(fù)10次。設(shè)Cache比主存快10倍。采用LRU算法。試分析Cache的結(jié)構(gòu)和主存地址的劃分。說明采用Cache后速度提高了多少？10.(12分）如圖所示的單周期數(shù)據(jù)通路執(zhí)行如下MIPS32指令A(yù)ddress(Byte)Instruction100beq$R2,$R4,7#TheaddressofregisterRnisn執(zhí)行上述指令前各寄存器的內(nèi)容如下表：1）（2分）將上述指令轉(zhuǎn)換為2進制表示的32位機器碼，其中操作碼對應(yīng)的機器編碼可以相同位數(shù)的*號代替，請按照MIPS32指令的格式區(qū)分各部分以方便查閱。2）（10分）除非特別聲明，請以10進制方式填寫下表中執(zhí)行該指令時的數(shù)據(jù)通路信號值和控制信號值，若值未知或不需要，可用x表示。[操作系統(tǒng)部分]11.填空題（2分x7=14分)1）操作系統(tǒng)的兩大特征是（）。2）單道系統(tǒng)中，假設(shè)一批作業(yè)同時到達，若想平均周轉(zhuǎn)時間最短，采用()調(diào)度算法。3）時間片輪轉(zhuǎn)調(diào)度算法中，如果時間片無窮大，該算法變成了（）調(diào)度算法。4）在某系統(tǒng)中有5個并發(fā)進程，都需要同類資源6個，問該系統(tǒng)肯定不會發(fā)生死鎖時最少資源數(shù)是（）。5）對于首次適應(yīng)算法、最佳適應(yīng)算法和循環(huán)首次適應(yīng)算法，可以保留高地址部分的大空閑區(qū)的算法是（）。6）有m個進程共享同一臨界資源，若使用信號量機制實現(xiàn)對一臨界資源的互斥訪問，則信號量的變化范圍是（）。7）裝入時動態(tài)鏈接和運行時動態(tài)鏈這兩種方式，（）更節(jié)約內(nèi)存。12.（9分）多道程序系統(tǒng)有一個CPU和兩臺獨占設(shè)備，即IO1和IO2，現(xiàn)在有3個優(yōu)先級別從高到低的作業(yè)J1、J2、J3到達，它們使用資源的先后順序和占用時間分別是：J1：IO2（60）；CPU（20）；IO1（60）；CPU（20）J2：IO1（40）；CPU（40）；IO2（80）J3：CPU（60）；IO1（40）假設(shè)處理機調(diào)度采用可搶占的優(yōu)先級算法，設(shè)備不能搶占，忽略調(diào)度時間，時間單位為分鐘。計算下列問題：1）分別計算3個作業(yè)的周轉(zhuǎn)時間（3分）2）3個作業(yè)全部完成時CPU的利用率（3分）3）3個作業(yè)全部完成時IO1的利用率（3分）13.（9分）磁盤請求柱面按10,22,20,2,40,6,38的次序到達，當(dāng)前磁頭在柱面20上。1）磁盤訪問時間由哪幾部組成，如何計算？（3分）2）計算采用SSTF，SCAN算法（先由小到大）磁頭移動順序。（3分）3）如何應(yīng)用RAID(廉價磁盤冗余陣列)提高磁盤的訪問速度，請畫圖示意。（3分）14.（9分）五個進程P1，P2，P3，P4，P5均需要使用資源A、B、C。其中，A、B、C資源的總數(shù)分別為10，5，7。當(dāng)前已分配資源情況和各進程的最大資源需求如下表所示。1)什么是安全狀態(tài)？（2分）2)系統(tǒng)進入不安全狀態(tài)是否一定會產(chǎn)生死鎖？（3分）3)P1請求資源（1,0,2），請根據(jù)銀行家算法判斷是否應(yīng)該為