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

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