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