2024年考研計(jì)算機(jī)統(tǒng)考《408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合》題庫(kù)【歷年考研真題＋章節(jié)題庫(kù)＋模擬試題】

第一部分歷年考研真題2009年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解一、單項(xiàng)選擇題：1～40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中。只有一個(gè)選項(xiàng)是最符合題目要求的。1為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。A．棧B．隊(duì)列C．樹(shù)D．圖【答案】B查看答案【解析】這類(lèi)問(wèn)題一般都先分析題目中的數(shù)據(jù)具有什么操作特性或是結(jié)構(gòu)特性比如“先進(jìn)后出”、“先進(jìn)先出”等再判斷其邏輯結(jié)構(gòu)。棧和隊(duì)列是操作受限的線性表，棧具有先進(jìn)后出的特性而隊(duì)列具有先進(jìn)先出的特性。由于本題中先進(jìn)入打印數(shù)據(jù)緩沖區(qū)的文件先被打印，因此打印數(shù)據(jù)緩沖區(qū)具有先進(jìn)先出性，則它的邏輯結(jié)構(gòu)應(yīng)該是隊(duì)列。2設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a，b，c，d，e，f，g依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是b，d，c，f，e，a，g，則棧S的容量至少是（）。A．1B．2C．3D．4【答案】C查看答案【解析】由于棧具有先進(jìn)后出的特性，隊(duì)列具有先進(jìn)先出的特性，出隊(duì)順序即為人隊(duì)順序。在本題中，每個(gè)元素出棧S后立即進(jìn)入隊(duì)列Q，出棧順序即為入隊(duì)順序，所以本題中隊(duì)列的作用形同虛設(shè)，根據(jù)題意出隊(duì)順序即為出棧順序。根據(jù)出棧順序可以分析各個(gè)元素進(jìn)出棧的過(guò)程：第一個(gè)出棧元素為b，表明棧內(nèi)還有元素a，b出棧前的深度為2；第二個(gè)出棧元素為d，棧內(nèi)元素為a和c，d出棧前的深度為3；c出棧后，剩余元素為a，c出棧前的深度為2；f出棧后，剩余元素為a和e，f出棧前的深度為3；e出棧后，剩余元素為a，e出棧前的深度為2；a出棧后，無(wú)剩余元素，a出棧前的深度為1；g出棧后，無(wú)剩余元素，g出棧前的深度為1。所以棧容量至少是3。3給定二叉樹(shù)如下圖所示。設(shè)N代表二叉樹(shù)的根，L代表根結(jié)點(diǎn)的左子樹(shù)，R代表根結(jié)點(diǎn)的右子樹(shù)。若遍歷后的結(jié)點(diǎn)序列為3，1，7，5，6，2，4，則其遍歷方式是（）。A．LRNB．NRLC．RLND．RNL【答案】D查看答案【解析】對(duì)“二叉樹(shù)”而言，一般有三條搜索路徑：①先上后下的按層次遍歷；②先左（子樹(shù)）后右（子樹(shù)）的遍歷；③先右（子樹(shù)）后左（子樹(shù)）的遍歷。其中第1種搜索路徑方式就是常見(jiàn)的層次遍歷，第2種搜索路徑方式包括常見(jiàn)的先序遍歷NLR、中序遍歷LNR、后序遍歷LRN，第3種搜索路徑方式則是不常使用的NRL、RNL、RLN。本題考查的是第3種搜索路徑方式的一種情況。根據(jù)遍歷的序列以及樹(shù)的結(jié)構(gòu)圖，可以分析出該遍歷的順序是先右子樹(shù)再跟結(jié)點(diǎn)最后左子樹(shù)，故答案為D。4下列二叉排序樹(shù)中，滿足平衡二叉樹(shù)定義的是（）?！敬鸢浮緽查看答案【解析】平衡二叉樹(shù)是指左右子樹(shù)高度差（平衡因子）的絕對(duì)值不超過(guò)1的二叉樹(shù)。A項(xiàng)中根結(jié)點(diǎn)的平衡因子是2；B項(xiàng)中每個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值均不超過(guò)1；C項(xiàng)中根結(jié)點(diǎn)的平衡因子是－2；D項(xiàng)中根結(jié)點(diǎn)的平衡因子是3。5已知一棵完全二叉樹(shù)的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是（）。A．39B．52C．111D．119【答案】C查看答案【解析】完全二叉樹(shù)的一個(gè)特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層。題目中沒(méi)有說(shuō)明完全二叉樹(shù)的高度，首先由完全二叉樹(shù)的特點(diǎn)確定題目中樹(shù)的高度。根據(jù)題意，一棵完全二叉樹(shù)的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，可知此二叉樹(shù)的高度是6或7。題目中求二叉樹(shù)的結(jié)點(diǎn)數(shù)最多的情況，因此此完全二叉樹(shù)的高度為7。由于高度為7的完全二叉樹(shù)的前6層是一棵滿二叉樹(shù)，根據(jù)二叉樹(shù)的性質(zhì)2可知，高度為6的滿二叉樹(shù)的結(jié)點(diǎn)數(shù)是26－1＝63。又根據(jù)二叉樹(shù)的性質(zhì)1可知，題目中二叉樹(shù)的第6層結(jié)點(diǎn)數(shù)是25＝32個(gè)結(jié)點(diǎn)，已知有8個(gè)葉子結(jié)點(diǎn)，那么其余32－8＝24個(gè)結(jié)點(diǎn)均為分支結(jié)點(diǎn)，這些結(jié)點(diǎn)在第7層上最多有48個(gè)子結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）。所以此二叉樹(shù)的結(jié)點(diǎn)數(shù)最多可達(dá)26－1＋（25－8）×2＝111。6將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來(lái)的森林中，u和v可能具有的關(guān)系是（）。Ⅰ．父子關(guān)系Ⅱ．兄弟關(guān)系Ⅲ．u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ)．只有ⅠB．Ⅰ和ⅡC．Ⅰ和ⅢD．Ⅰ、Ⅱ和Ⅲ【答案】B查看答案【解析】首先，在二叉樹(shù)中，若結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，那么u和v的關(guān)系有如下4種情況：接下來(lái)，根據(jù)森林與二叉樹(shù)的轉(zhuǎn)換規(guī)則，將這4種情況還原成森林中結(jié)點(diǎn)的關(guān)系。其中：情況（1），在原來(lái)的森林中u是v的父結(jié)點(diǎn)的父結(jié)點(diǎn)；情況（2），在森林中u是v的父結(jié)點(diǎn)；情況（3），在森林中u是v的父結(jié)點(diǎn)的兄弟；情況（4），在森林中u與v是兄弟關(guān)系。由此可知，題目中的Ⅰ、Ⅱ是正確的。7下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（）。Ⅰ．所有的頂點(diǎn)的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1Ⅲ．至少有一個(gè)頂點(diǎn)的度為1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ【答案】A查看答案【解析】在圖中，頂點(diǎn)的度TD（Vi）之和與邊的數(shù)目滿足關(guān)系式：其中，n為圖的總結(jié)點(diǎn)數(shù)，e為總邊數(shù)。因此，Ⅰ項(xiàng)正確。對(duì)于Ⅱ、Ⅲ項(xiàng)中的特性不是一般無(wú)向連通圖的特性，可以輕松地舉出反例。“至少有一個(gè)頂點(diǎn)的度為1”的反例如下圖（1）所示，“邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1”的反例如下圖（2）所示。（1）（2）8下列敘述中，不符合m階B樹(shù)定義要求的是（）。A．根結(jié)點(diǎn)最多有m棵子樹(shù)B．所有葉結(jié)點(diǎn)都在同一層上C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點(diǎn)之間通過(guò)指針鏈接【答案】D查看答案【解析】B樹(shù)就是指B-樹(shù)。根據(jù)B-樹(shù)的定義，m階B-樹(shù)中每個(gè)結(jié)點(diǎn)最多有m個(gè)分支，因此，根結(jié)點(diǎn)最多有m棵子樹(shù)，A項(xiàng)正確；B-樹(shù)中所有葉結(jié)點(diǎn)都在最底層，位于同一層，B項(xiàng)正確；結(jié)點(diǎn)內(nèi)各關(guān)鍵字互不相等且有序排列，C項(xiàng)正確。但是，所有葉子結(jié)點(diǎn)之間通過(guò)指針鏈接，是B＋樹(shù)的定義，而B(niǎo)-樹(shù)中沒(méi)有。因此，D項(xiàng)是錯(cuò)誤的。9已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，19【答案】A查看答案【解析】在堆中插入或刪除一個(gè)元素后，將不再滿足堆的性質(zhì)。為了使其成為新堆，在輸出堆頂元素后，需要調(diào)整剩余元素。具體過(guò)程如圖（1）～（5）所示，（1）為原堆，（2）為插入3后，（3）、（4）為調(diào)整過(guò)程，（5）為調(diào)整后的小根堆。10若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（）。A．起泡排序B．插入排序C．選擇排序D．二路歸并排序【答案】B查看答案【解析】經(jīng)過(guò)兩趟排序后，A項(xiàng)起泡排序的結(jié)果是兩個(gè)最小或最大的元素放到了序列的最終位置；B項(xiàng)插入排序的結(jié)果是前三個(gè)數(shù)有序即可；C項(xiàng)選擇排序結(jié)果是兩個(gè)最小的元素在最前面按順序排好；D項(xiàng)二路歸并排序的結(jié)果是長(zhǎng)度為4的子序列有序，即前4個(gè)數(shù)排好序，接下來(lái)的4個(gè)數(shù)排好序。顯然題目中的元素序列只能是插入排序第二趟排序后的結(jié)果，因此，B項(xiàng)正確。11馮·諾依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中，CPU區(qū)分它們的依據(jù)是（）。A．指令操作碼的譯碼結(jié)果B．指令和數(shù)據(jù)的尋址方式C．指令周期的不同階段D．指令和數(shù)據(jù)所在的存儲(chǔ)單元【答案】C查看答案【解析】在馮·諾依曼結(jié)構(gòu)計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在同一個(gè)存儲(chǔ)器中，CPU可以根據(jù)指令周期的不同階段來(lái)區(qū)分是指令還是數(shù)據(jù)，通常在取指階段取出的是指令，其他階段（分析取數(shù)階段、執(zhí)行階段）取出的是數(shù)據(jù)。所以，CPU區(qū)分指令和數(shù)據(jù)的依據(jù)是指令周期的不同階段。12一個(gè)C語(yǔ)言程序在一臺(tái)32位機(jī)器上運(yùn)行。程序中定義了3個(gè)變量x、Y和z，其中x和z為int型，Y為short型。當(dāng)x＝127，Y＝－9時(shí)，執(zhí)行賦值語(yǔ)句z＝x＋Y后，x、Y和z的值分別是（）。A．x＝0000007FH，Y＝FFFFFFF9H，z＝00000076HB．x＝0000007FH，Y＝FFFFFFF9H，z＝FFFF0076HC．x＝0000007FH，Y＝FFFFFFF7H，z＝FFFF0076HD．x＝0000007FH，Y＝FFFFFFF7H，z＝00000076H【答案】D查看答案【解析】當(dāng)兩個(gè)不同長(zhǎng)度的數(shù)據(jù)，要想通過(guò)算術(shù)運(yùn)算得到正確的結(jié)果，必須將短字長(zhǎng)數(shù)據(jù)轉(zhuǎn)換成長(zhǎng)字長(zhǎng)數(shù)據(jù)，這被稱為“符號(hào)擴(kuò)展”。例如，x和z為int型，數(shù)據(jù)長(zhǎng)32位，Y為short型，數(shù)據(jù)長(zhǎng)16位，因此首先應(yīng)將y轉(zhuǎn)換成32位的數(shù)據(jù)，然后再進(jìn)行加法運(yùn)算。運(yùn)算采用補(bǔ)碼的形式，而x的補(bǔ)碼是0000007FH，Y的補(bǔ)碼是FFFFFFF7H，所以x＋Y＝00000076H。13浮點(diǎn)數(shù)加、減運(yùn)算一般包括對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出等步驟。設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示，且位數(shù)分別為5位和7位（均含2位符號(hào)位）。若有兩個(gè)數(shù)X＝27×29/32，Y＝25×5/8，則用浮點(diǎn)加法計(jì)算X＋Y的最終結(jié)果是（）。A．001111100010B．001110100010C．010000010001D．發(fā)生溢出【答案】D查看答案【解析】浮點(diǎn)數(shù)加、減運(yùn)算一般包括對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出等步驟，難點(diǎn)在對(duì)階、規(guī)格化、判溢出這三步。X和Ｙ的階碼不同，所以應(yīng)該先對(duì)階，對(duì)階原則為：小階向大階看齊。因此將Y對(duì)階后得到：Y＝27×5/32，然后將尾數(shù)相加，得到尾數(shù)之和為：34/32。因?yàn)檫@是兩個(gè)同號(hào)數(shù)相加，尾數(shù)大于1，則需要右規(guī)，階碼加1。由于階碼的位數(shù)為5位，且含兩位符號(hào)位，即階碼的表示范圍在－8～＋7之間。而階碼本身等于7，再加1就等于8。因此，最終結(jié)果發(fā)生溢出。14某計(jì)算機(jī)的Cache共有16塊，采用2路組相聯(lián)映射方式（即每組2塊）。每個(gè)主存塊大小為32字節(jié)，按字節(jié)編址。主存129號(hào)單元所在主存塊應(yīng)裝入到的Cache組號(hào)是（）。A．0B．2C．4D．6【答案】C查看答案【解析】首先根據(jù)主存地址計(jì)算所在的主存塊號(hào)，然后根據(jù)組相聯(lián)映射的映射關(guān)系K＝ImodQ（K代表Cache的組號(hào)，I代表主存的塊號(hào)，Q代表Cache的組數(shù)）來(lái)計(jì)算Cache的組號(hào)。由于每個(gè)主存塊大小為32字節(jié)，按字節(jié)編址，那么主存129號(hào)單元所在的主存塊號(hào)是4，Cache共有16塊，采用2路組相聯(lián)映射方式（即每組2塊），故Cache有8組，按照上面的公式可以計(jì)算得到Cache的組號(hào)＝4mod8＝4。15某計(jì)算機(jī)主存容量為64KB，其中ROM區(qū)為4KB，其余為RAM區(qū)，按字節(jié)編址?，F(xiàn)要用2K×8位的ROM芯片和4K×4位的RAM芯片來(lái)設(shè)計(jì)該存儲(chǔ)器，則需要上述規(guī)格的ROM芯片數(shù)和RAM芯片數(shù)分別是（）。A．1、15B．2、15C．1、30D．2、30【答案】D查看答案【解析】主存儲(chǔ)器包括RAM和ROM兩部分，由于ROM區(qū)為4KB，則RAM區(qū)為60KB。存儲(chǔ)容量的擴(kuò)展方法有字?jǐn)U展、位擴(kuò)展、字和位同時(shí)擴(kuò)展三種。選用2K×8位的ROM芯片，只需采用2片芯片進(jìn)行字?jǐn)U展便可得到4KB的ROM區(qū)；選用4K×4位的RAM芯片，需采用（60）/4*2片芯片進(jìn)行字和位同時(shí)擴(kuò)展便可得60KB的RAM區(qū)。16某機(jī)器字長(zhǎng)16位，主存按字節(jié)編址，轉(zhuǎn)移指令采用相對(duì)尋址，由兩個(gè)字節(jié)組成，第1字節(jié)為操作碼字段，第2字節(jié)為相對(duì)位移量字段。假定取指令時(shí)，每取一個(gè)字節(jié)PC自動(dòng)加1。若某轉(zhuǎn)移指令所在主存地址為2000H，相對(duì)位移量字段的內(nèi)容為06H，則該轉(zhuǎn)移指令成功轉(zhuǎn)移后的目標(biāo)地址是（）。A．2006HB．2007HC．2008HD．2009H【答案】C查看答案【解析】相對(duì)尋址方式的有效地址EA＝（PC）＋D，其中PC為程序計(jì)數(shù)器，D為相對(duì)偏移量。主存按字節(jié)編址，取指令時(shí)，每取一個(gè)字節(jié)PC值自動(dòng)加1。由于轉(zhuǎn)移指令由兩個(gè)字節(jié)組成，取出這條轉(zhuǎn)移指令之后的PC值自動(dòng)加2，為2002H，故轉(zhuǎn)移的目標(biāo)地址為2002H＋06H＝2008H。17下列關(guān)于RISC的敘述中，錯(cuò)誤的是（）。A．RISC普遍采用微程序控制器B．RISC大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成C．RISC的內(nèi)部通用寄存器數(shù)量相對(duì)CISC多D．RISC的指令數(shù)、尋址方式和指令格式種類(lèi)相對(duì)CISC少【答案】A查看答案【解析】B項(xiàng)、C項(xiàng)、D項(xiàng)都是RISC的特點(diǎn)之一，所以它們都是正確的，只有A項(xiàng)是CISC的特點(diǎn)，因?yàn)镽ISC的速度快，所以普遍采用硬布線控制器，而非微程序控制器。18某計(jì)算機(jī)的指令流水線由4個(gè)功能段組成，指令流經(jīng)各功能段的時(shí)間（忽略各功能段之間的緩存時(shí)間）分別為90ns、80ns、70ns和60ns，則該計(jì)算機(jī)的CPU時(shí)鐘周期至少是（）。A．90nsB．80nsC．70nsD．60ns【答案】A查看答案【解析】對(duì)于各功能段執(zhí)行時(shí)間不同的指令流水線，計(jì)算機(jī)的CPU時(shí)鐘周期應(yīng)當(dāng)以最長(zhǎng)的功能段執(zhí)行時(shí)間為準(zhǔn)。19相對(duì)于微程序控制器，硬布線控制器的特點(diǎn)是（）。A．指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展容易B．指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展難C．指令執(zhí)行速度快，指令功能的修改和擴(kuò)展容易D．指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難【答案】D查看答案【解析】在同樣的半導(dǎo)體工藝條件下，硬布線（組合邏輯）控制器的速度比微程序控制器的速度快。這是因?yàn)橛膊季€控制器的速度主要取決于邏輯電路的延遲，而微程序控制器增加了一級(jí)控制存儲(chǔ)器，執(zhí)行的每條微指令都要從控制存儲(chǔ)器中讀取，影響了速度。由于硬布線控制器一旦設(shè)計(jì)完成就很難改變，所以指令功能的修改和擴(kuò)展難。因此，硬布線控制器的特點(diǎn)是指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難。20假設(shè)某系統(tǒng)總線在一個(gè)總線周期中并行傳輸4字節(jié)信息，一個(gè)總線周期占用2個(gè)時(shí)鐘周期，總線時(shí)鐘頻率為10MHz，則總線帶寬是（）。A．10MB/sB．20MB/sC．40MB/sD．80MB/s【答案】B查看答案【解析】因?yàn)橐粋€(gè)總線周期占用2個(gè)時(shí)鐘周期，完成一個(gè)32位數(shù)據(jù)的傳送。總線時(shí)鐘頻率為10MHz，時(shí)鐘周期為0.1μs，總線周期占用2個(gè)時(shí)鐘周期，為0.2μs。一個(gè)總線周期中并行傳輸4字節(jié)信息，則總線帶寬是4B÷0.2μs＝20MB/s。21假設(shè)某計(jì)算機(jī)的存儲(chǔ)系統(tǒng)由Cache和主存組成。某程序執(zhí)行過(guò)程中訪存1000次，其中訪問(wèn)Cache缺失（未命中）50次，則Cache的命中率是（）。A．5%B．9.5%C．50%D．95%【答案】D查看答案【解析】Cache的命中率H＝N1/（N1＋N2）,其中N1為訪問(wèn)Cache的次數(shù)，N2為訪存主存的次數(shù)，程序總訪存次數(shù)為N1＋N2，程序訪存次數(shù)減去失效次數(shù)就是訪問(wèn)Cache的次數(shù)N1，。所以根據(jù)公式可得：H＝（1000－50）/1000＝95%。22下列選項(xiàng)中，能引起外部中斷的事件是（）。A．鍵盤(pán)輸入B．除數(shù)為0C．浮點(diǎn)運(yùn)算下溢D．訪存缺頁(yè)【答案】A查看答案【解析】所謂外部中斷是指由外部事件引起的中斷，在這4個(gè)選項(xiàng)中，只有鍵盤(pán)輸入是真正由外部事件引起的中斷。23單處理機(jī)系統(tǒng)中，可并行的是（）。Ⅰ．進(jìn)程與進(jìn)程Ⅱ．處理機(jī)與設(shè)備Ⅲ．處理機(jī)與通道Ⅳ．設(shè)備與設(shè)備A．Ⅰ、Ⅱ和ⅢB．Ⅰ、Ⅱ和ⅣC．Ⅰ、Ⅲ和ⅣD．Ⅱ、Ⅲ和Ⅳ【答案】D查看答案【解析】注意區(qū)分并發(fā)和并行。在單處理機(jī)系統(tǒng)中，進(jìn)程只能并發(fā)。微觀上同一時(shí)刻占用處理機(jī)的進(jìn)程只有一個(gè)，因此，進(jìn)程之間不是并行的。通道是獨(dú)立于CPU控制的輸入/輸出的設(shè)備，處理機(jī)與通道兩者是可以并行。顯然，設(shè)備和設(shè)備之間也是可以并行的。24下列進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是（）。A．時(shí)間片輪轉(zhuǎn)調(diào)度算法B．短進(jìn)程優(yōu)先調(diào)度算法C．先來(lái)先服務(wù)調(diào)度算法D．高響應(yīng)比優(yōu)先調(diào)度算法【答案】D查看答案【解析】時(shí)間片輪轉(zhuǎn)法和先來(lái)先服務(wù)算法都是公平的方法，并未考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間，而短進(jìn)程優(yōu)先考慮的是進(jìn)程執(zhí)行時(shí)間。最高響應(yīng)比優(yōu)先調(diào)度算法是最先執(zhí)行響應(yīng)比最高的進(jìn)程（響應(yīng)比＝1＋等待時(shí)間/估計(jì)運(yùn)行時(shí)間）。該算法綜合了先來(lái)先服務(wù)（FCFS）和短作業(yè)優(yōu)先（SJF）算法，F(xiàn)CFS只考慮每個(gè)作業(yè)的等待時(shí)間，而未考慮執(zhí)行時(shí)間的長(zhǎng)短。SJF只考慮執(zhí)行時(shí)間的長(zhǎng)短，而未考慮等待時(shí)間的長(zhǎng)短，HRRN算法則同時(shí)考慮執(zhí)行時(shí)間和等待時(shí)間。25某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，由K個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K最小值是（）。A．2B．3C．4D．5【答案】C查看答案【解析】死鎖的抽屜原理一般描述是：將5個(gè)蘋(píng)果放進(jìn)4個(gè)抽屜，那么，必然有1個(gè)抽屜中至少有2個(gè)蘋(píng)果。計(jì)算機(jī)系統(tǒng)的資源分配充分體現(xiàn)了這一原理?？疾爝M(jìn)程運(yùn)行的特點(diǎn)，只要有一個(gè)進(jìn)程能夠運(yùn)行，則運(yùn)行結(jié)束后必然會(huì)歸還資源，其余的進(jìn)程也就會(huì)得到滿足從而可以執(zhí)行（這里考慮的資源主要是可重用的資源，不可重用的資源會(huì)消失，就不可用上述方法分析）。所以最少需要4個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程占用2臺(tái)打印機(jī)，此時(shí)會(huì)產(chǎn)生死鎖。26分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是（）。A．界地址保護(hù)B．程序代碼保護(hù)C．?dāng)?shù)據(jù)保護(hù)D．棧保護(hù)【答案】A查看答案【解析】對(duì)于連續(xù)分配算法，無(wú)論固定分區(qū)或動(dòng)態(tài)分區(qū)方法，程序都必須全部調(diào)入內(nèi)存，不同的進(jìn)程放于不同的內(nèi)存塊中，相互之間不可越界，因此需要進(jìn)行界地址保護(hù)。通常的界地址保護(hù)方法采用軟硬件結(jié)合的方法?？忌⒁獗绢}與虛擬存儲(chǔ)方法的區(qū)別。27一個(gè)分段存儲(chǔ)管理系統(tǒng)中，地址長(zhǎng)度為32位，其中段號(hào)占8位，則最大段長(zhǎng)是（）。A．28字節(jié)B．216字節(jié)C．224字節(jié)D．232字節(jié)【答案】C查看答案【解析】段內(nèi)位移的最大值就是最大段長(zhǎng)。段號(hào)長(zhǎng)度占了8位，剩下32－8＝24位是段內(nèi)位移空間，因此最大段長(zhǎng)為224B。28下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問(wèn)且易于文件擴(kuò)展的是（）。A．連續(xù)結(jié)構(gòu)B．索引結(jié)構(gòu)C．鏈?zhǔn)浇Y(jié)構(gòu)且磁盤(pán)塊定長(zhǎng)D．鏈?zhǔn)浇Y(jié)構(gòu)且磁盤(pán)塊變長(zhǎng)【答案】B查看答案【解析】連續(xù)結(jié)構(gòu)的優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，缺點(diǎn)是不易于文件擴(kuò)展，不易隨機(jī)訪問(wèn)。鏈?zhǔn)浇Y(jié)構(gòu)的優(yōu)點(diǎn)是文件易于擴(kuò)展，缺點(diǎn)是不易隨機(jī)訪問(wèn)。索引結(jié)構(gòu)的優(yōu)點(diǎn)是具有鏈?zhǔn)浇Y(jié)構(gòu)的優(yōu)點(diǎn)并克服了它的缺點(diǎn)，可隨機(jī)存取，易于文件擴(kuò)展。29假設(shè)磁頭當(dāng)前位于第105道，正在向磁道序號(hào)增加的方向移動(dòng)?，F(xiàn)有一個(gè)磁道訪問(wèn)請(qǐng)求，序列為35，45，12，68，110，180，170，195，采用SCAN調(diào)度（電梯調(diào)度）算法得到的磁道訪問(wèn)序列是（）。A．110，170，180，195，68，45，35，12B．110，68，45，35，12，170，180，195C．110，170，180，195，12，35，45，68D．12，31，45，68，110，170，180，195【答案】A查看答案【解析】SCAN算法類(lèi)似電梯工作原理，即朝一個(gè)固定方向前進(jìn)，經(jīng)過(guò)的磁道有訪問(wèn)請(qǐng)求則馬上服務(wù)，直至到達(dá)一端頂點(diǎn)，再掉頭往回移動(dòng)以服務(wù)經(jīng)過(guò)的磁道，并這樣在兩端之間往返。因此，當(dāng)磁頭從105道向序號(hào)增加的方向移動(dòng)時(shí)，便會(huì)服務(wù)所有大于105的磁道號(hào)（從小到大的順序）；往回返時(shí)又會(huì)按照從大到小的順序進(jìn)行服務(wù)。注意與循環(huán)掃描算法的區(qū)別，所以SCAN算法的訪問(wèn)序列是：110，170，180，195，68，45，35，12。30文件系統(tǒng)中，文件訪問(wèn)控制信息存儲(chǔ)的合理位置是（）。A．文件控制塊B．文件分配表C．用戶口令表D．系統(tǒng)注冊(cè)表【答案】A查看答案【解析】文件控制塊是文件存在的標(biāo)志，文件的相關(guān)信息（基本信息、存取控制信息以及使用信息）都存儲(chǔ)在文件控制塊中，系統(tǒng)對(duì)文件的管理全是依靠文件控制塊里的信息。31設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為1，先建立F1的符號(hào)鏈接（軟鏈接）文件F2，再建立F1的硬鏈接文件F3，然后刪除F1。此時(shí)，F(xiàn)2和F3的引用計(jì)數(shù)值分別是（）。A．0、1B．1、1C．1、2D．2、1【答案】B查看答案【解析】為了使文件實(shí)現(xiàn)共享，通常在使用該形式文件系統(tǒng)的文件索引節(jié)點(diǎn)中設(shè)置一個(gè)鏈接計(jì)數(shù)字段，用來(lái)表示鏈接到本文件的用戶目錄項(xiàng)的數(shù)目（引用計(jì)數(shù)值），這是共享的一種方法。當(dāng)新文件建立時(shí)，一般默認(rèn)引用計(jì)數(shù)值為1。硬鏈接可以看作是已存在文件的另一個(gè)名字，新文件和被鏈接文件指向同一個(gè)節(jié)點(diǎn)，引用計(jì)數(shù)值加1。當(dāng)刪除被鏈接文件時(shí)，只是把引用計(jì)數(shù)值減1，直到引用計(jì)數(shù)值為0時(shí)，才能真正刪除文件。軟鏈接又叫符號(hào)鏈接，在新文件中只包含了被鏈接文件的路徑名，新文件和被鏈接文件指向不同的節(jié)點(diǎn)。建立軟鏈接文件時(shí)，文件的引用計(jì)數(shù)值不會(huì)增加。在這種方式下，當(dāng)被鏈接文件刪除時(shí)，新文件仍然是存在的，只不過(guò)是不能通過(guò)新文件的路徑訪問(wèn)被鏈接文件而已。因此，在本題中，當(dāng)建立F2時(shí)，F(xiàn)1和F2的引用計(jì)數(shù)值都為1。當(dāng)再建立F3時(shí)，F(xiàn)1和F3的引用計(jì)數(shù)值就都變成了2。當(dāng)后來(lái)刪除F1時(shí)，F(xiàn)3的引用計(jì)數(shù)值為2－1＝1。F2的引用計(jì)數(shù)值仍然保持不變，所以F2和F3的引用計(jì)數(shù)值分別是：1，1。32程序員利用系統(tǒng)調(diào)用打開(kāi)I/O設(shè)備時(shí)，通常使用的設(shè)備標(biāo)識(shí)是（）。A．邏輯設(shè)備名B．物理設(shè)備名C．主設(shè)備號(hào)D．從設(shè)備號(hào)【答案】A查看答案【解析】設(shè)備管理具有設(shè)備獨(dú)立性的特點(diǎn)，操作系統(tǒng)以系統(tǒng)調(diào)用方式提供給應(yīng)用程序使用邏輯設(shè)備名來(lái)請(qǐng)求使用某類(lèi)設(shè)備時(shí)，調(diào)用中使用的是邏輯設(shè)備名，例如LPT1或COM1等。而操作系統(tǒng)內(nèi)部管理設(shè)備使用的是設(shè)備編號(hào)。33在OSI參考模型中，自下而上第一個(gè)提供端到端服務(wù)的層次是（）。A．?dāng)?shù)據(jù)鏈路層B．傳輸層C．會(huì)話層D．應(yīng)用層【答案】B查看答案【解析】題目中指明了這一層能夠?qū)崿F(xiàn)端到端傳輸，也就是端系統(tǒng)到端系統(tǒng)的傳輸，數(shù)據(jù)鏈路層主要負(fù)責(zé)傳輸路徑上相鄰結(jié)點(diǎn)間的數(shù)據(jù)交付，這些結(jié)點(diǎn)包括了交換機(jī)和路由器等數(shù)據(jù)通信設(shè)備，這些設(shè)備不能被稱為端系統(tǒng)，因此數(shù)據(jù)鏈路層不滿足題意。題目中指明了這一層能夠?qū)崿F(xiàn)傳輸，會(huì)話層只是在兩個(gè)應(yīng)用進(jìn)程之間建立會(huì)話而已，應(yīng)用層只是提供應(yīng)用進(jìn)程之間通信的規(guī)范，都不涉及傳輸。所以本題答案應(yīng)該是B項(xiàng)。在OSI模型中網(wǎng)絡(luò)層提供的是主機(jī)到主機(jī)的通信服務(wù)。34在無(wú)噪聲情況下，若某通信鏈路的帶寬為3kHz，采用4個(gè)相位，每個(gè)相位具有4種振幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是（）。A．12kbpsB．24kbpsC．48kbpsD．96kbps【答案】B查看答案【解析】首先要根據(jù)信道有無(wú)噪聲來(lái)確定是否采用奈奎斯特定理。解題難點(diǎn)在于離散數(shù)值的確定，先確定調(diào)制技術(shù)的碼元數(shù)，此處為4個(gè)相位乘以4種振幅，共16種，即該通信鏈路的最大數(shù)據(jù)傳輸速率＝2×3×log2（4×4）＝6×4＝24kbps。35數(shù)據(jù)鏈路層采用后退N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號(hào)為0～7的幀。當(dāng)計(jì)時(shí)器超時(shí)，若發(fā)送方只收到0、2、3號(hào)幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是（）。A．2B．3C．4D．5【答案】C查看答案【解析】后退N幀協(xié)議，即GO-BACK—N策略的基本原理是，當(dāng)接收方檢測(cè)出失序的信息幀后，要求發(fā)送方重發(fā)最后一個(gè)正確接收的信息幀之后的所有未被確認(rèn)的幀；或者當(dāng)發(fā)送方發(fā)送了N個(gè)幀后，若發(fā)現(xiàn)該N幀的前一個(gè)幀在計(jì)時(shí)器超時(shí)后仍未返回其確認(rèn)信息，則該幀被判為出錯(cuò)或丟失，此時(shí)發(fā)送方就不得不重新發(fā)送出錯(cuò)幀及其后的N幀。本題收到3號(hào)幀的確認(rèn)，說(shuō)明0，1，2，3號(hào)幀已經(jīng)收到，丟失的是4，5，6，7號(hào)幀，共4幀。因此答案為C項(xiàng)。36以太網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時(shí)使用的PDU地址是（）。A．目的物理地址B．目的IP地址C．源物理地址D．源IP地址【答案】A查看答案【解析】交換機(jī)會(huì)監(jiān)測(cè)發(fā)送到每個(gè)端口的數(shù)據(jù)幀，通過(guò)數(shù)據(jù)幀中的有關(guān)信息（源結(jié)點(diǎn)的MAC地址、目的結(jié)點(diǎn)的MAC地址），就會(huì)得到與每個(gè)端口所連接結(jié)點(diǎn)的MAC地址，并在交換機(jī)的內(nèi)部建立一個(gè)“端口-MAC地址”映射表。建立映射表后，當(dāng)某個(gè)端口接收到數(shù)據(jù)幀后，交換機(jī)會(huì)讀取出該幀中的目的結(jié)點(diǎn)的MAC地址，并通過(guò)“端口-MAC地址”的對(duì)應(yīng)關(guān)系，迅速將數(shù)據(jù)幀轉(zhuǎn)發(fā)到相應(yīng)的端口，注意這里的交換機(jī)工作在數(shù)據(jù)鏈路層，因此關(guān)于IP地址的選項(xiàng)是不對(duì)的，因此答案為A。37在一個(gè)采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為1Gbps，電纜中的信號(hào)傳播速度是200000km/s。若最小數(shù)據(jù)幀長(zhǎng)度減少800bit，則最遠(yuǎn)的兩個(gè)站點(diǎn)之間的距離至少需要（）。A．增加160mB．增加80mC．減少160mD．減少80m【答案】D查看答案【解析】以太網(wǎng)采用CSMA/CD訪問(wèn)協(xié)議，在發(fā)送的同時(shí)要進(jìn)行沖突檢測(cè)，這就要求在能檢測(cè)出沖突的最大時(shí)間內(nèi)數(shù)據(jù)包不能夠發(fā)送完畢，否則沖突檢測(cè)不能有效地工作。所以，當(dāng)發(fā)送的數(shù)據(jù)包太短時(shí)必須進(jìn)行填充。最小幀長(zhǎng)度＝碰撞窗口大小×報(bào)文發(fā)送速率，本題最小數(shù)據(jù)幀長(zhǎng)度減少800b，那么碰撞的窗口也要減少，因此距離也要減少，從而（800×2×108）/（1×109）＝160m，由于時(shí)間延時(shí)存在兩倍的關(guān)系，因此減少的距離為80m。38主機(jī)甲和主機(jī)乙間已建立一個(gè)TCP連接，主機(jī)甲向主機(jī)乙發(fā)送了兩個(gè)連續(xù)的TCP段，分別包含300字節(jié)和500字節(jié)的有效載荷，第一個(gè)段的序列號(hào)為200，主機(jī)乙正確接收到兩個(gè)段后，發(fā)送給主機(jī)甲的確認(rèn)序列號(hào)是（）。A．500B．700C．800D．1000【答案】D查看答案【解析】TCP使用滑動(dòng)窗口流控協(xié)議，窗口大小的單位是字節(jié)，本題中分別包含300字節(jié)和500字節(jié)的有效載荷，第一個(gè)段的序列號(hào)為200，那么確認(rèn)序列號(hào)為200＋300＋500＝1000。39一個(gè)TCP連接總是以1KB的最大段發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，如果接下來(lái)的4個(gè)RTT（往返時(shí)間）時(shí)間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是（）。A．7KBB．8KBC．9KBD．16KB【答案】C查看答案【解析】回顧TCP流量控制和擁塞控制（慢啟動(dòng)）的知識(shí)點(diǎn)，從第一個(gè)MSS開(kāi)始，每次發(fā)送成功，擁塞窗口值翻倍，四次以后，應(yīng)該為16，但是由于擁塞閾值變?yōu)?6/2＝8，故三次成功后為8，以后為線性增長(zhǎng)，故為8＋1＝9，答案為C。40FTP客戶和服務(wù)器間傳遞FTP命令時(shí)，使用的連接是（）。A．建立在TCP之上的控制連接B．建立在TCP之上的數(shù)據(jù)連接C．建立在UDP之上的控制連接D．建立在UDP之上的數(shù)據(jù)連接【答案】A查看答案【解析】對(duì)于FTP，為了保證可靠性，選擇TCP。FTP應(yīng)用需要建立兩條TCP連接：一條為控制連接，另一條為數(shù)據(jù)連接。FTP服務(wù)器打開(kāi)21號(hào)端口，被動(dòng)的等待客戶的連接建立請(qǐng)求。客戶則以主動(dòng)方式與服務(wù)器建立控制連接，客戶通過(guò)控制連接將命令傳給服務(wù)器，而服務(wù)器則通過(guò)控制連接將應(yīng)答傳給客戶，命令和響應(yīng)都是以NVTASCII形式表示的。二、綜合應(yīng)用題：41～47小題。共70分。41（10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問(wèn)題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑，假設(shè)從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問(wèn)題的方法：①該最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)為初始頂點(diǎn)；②選擇離υ最近且尚未在最短路徑中的頂點(diǎn)ν，加入到最短路徑中，修改當(dāng)前頂點(diǎn)υ＝ν；③重復(fù)步驟②，直到υ是目標(biāo)頂點(diǎn)時(shí)為止。請(qǐng)問(wèn)上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則請(qǐng)舉例說(shuō)明。解：題目中方法不一定能（或不能）求得最短路徑。舉例說(shuō)明：圖（a）中，假設(shè)初始頂點(diǎn)1到目標(biāo)頂點(diǎn)4之間有一條邊，權(quán)值x＝2。顯然圖（a）中這頂點(diǎn)1和頂點(diǎn)4之間的最短路徑長(zhǎng)度為2。若按照題目中給定的方法找到的路徑為初始頂點(diǎn)1經(jīng)過(guò)中間結(jié)點(diǎn)2、3到目標(biāo)頂點(diǎn)4，即初始頂點(diǎn)1—2—3一目標(biāo)頂點(diǎn)4，所經(jīng)過(guò)的邊的權(quán)值分別為y1＝1、y2＝1、y3＝1。顯然，y1＋y2＋y3＝3大于2。因此按照題目中給定的方法所求得的路徑并不是這兩個(gè)頂點(diǎn)之間的最短路徑。圖（b）中，假設(shè)初始頂點(diǎn)為1、目標(biāo)頂點(diǎn)為4，欲求從頂點(diǎn)1到頂點(diǎn)4之間的最短路徑。顯然，按照題目中給定的方法無(wú)法求出頂點(diǎn)1到頂點(diǎn)4的路徑，而事實(shí)上頂點(diǎn)1到頂點(diǎn)4的最短路徑為1到4。42（15分）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為，假設(shè)該鏈表只給出了頭指針1ist。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設(shè)計(jì)思想；（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟；（3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法（使用C或C＋＋或JAVA語(yǔ)言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。解：（1）算法的基本設(shè)計(jì)思想定義兩個(gè)指針變量p和q，初始時(shí)均指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。p指針沿鏈表移動(dòng)；當(dāng)p指針移動(dòng)到第k個(gè)結(jié)點(diǎn)時(shí)，q指針開(kāi)始與p指針同步移動(dòng)；當(dāng)p指針移動(dòng)到鏈表最后一個(gè)結(jié)點(diǎn)時(shí)，因?yàn)閜和q相隔k，故q指針?biāo)冈貫榈箶?shù)第k個(gè)結(jié)點(diǎn)。以上過(guò)程對(duì)鏈表僅進(jìn)行一遍掃描。（2）算法的詳細(xì)實(shí)現(xiàn)步驟①count＝0，p和q指向鏈表表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)；②若p為空，轉(zhuǎn)⑤；，③若count等于k，則q指向下一個(gè)結(jié)點(diǎn)；否則，count＝count＋1；④p指向下一個(gè)結(jié)點(diǎn)，轉(zhuǎn)步驟②；⑤若count等于k，則查找成功，輸出該結(jié)點(diǎn)的data域的值，返回1；否則，查找失敗，返回0；⑥算法結(jié)束。（3）算法實(shí)現(xiàn)43（8分）某計(jì)算機(jī)的CPU主頻為500MHz，CPI為5（即執(zhí)行每條指令平均需要5個(gè)時(shí)鐘周期）。假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB/s，采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送，以32位為傳輸單位，對(duì)應(yīng)的中斷服務(wù)程序包含18條指令，中斷服務(wù)的其他開(kāi)銷(xiāo)相當(dāng)于2條指令的執(zhí)行時(shí)間。請(qǐng)回答下列問(wèn)題，要求給出計(jì)算過(guò)程。（1）在中斷方式下，CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少？（2）當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到5MB/s時(shí)，改用DMA方式傳送數(shù)據(jù)。假定每次DMA傳送塊大小為5000B，且DMA預(yù)處理和后處理的總開(kāi)銷(xiāo)為500個(gè)時(shí)鐘周期，則CPU用于該外設(shè)I/O時(shí)間占整個(gè)CPU時(shí)間的百分比是多少？（假設(shè)DMA與CPU之間沒(méi)有訪存沖突）解：（1）已知主頻為500MHz，則時(shí)鐘周期＝1÷500MHz＝2ns，因?yàn)镃PI＝5，所以每條指令平均5×2＝10ns。又已知每中斷一次傳送32位（4個(gè)字節(jié)），數(shù)據(jù)傳輸率為0.5MB/s，所以傳送時(shí)間＝4÷O.5MB/s＝8μs。CPU用于該外設(shè)I/O共需20條指令（中斷服務(wù)程序包括18條指令＋其他開(kāi)銷(xiāo)折合2條指令），花費(fèi)時(shí)間＝20×10＝200ns。CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比＝200/8000×100%＝0.025×100%＝2.5%。（2）改用DMA方式傳送數(shù)據(jù)，數(shù)據(jù)傳輸率為5MB/s，傳送5000B的時(shí)間＝5000B÷5MB/s＝1ms。預(yù)處理和后處理的總開(kāi)銷(xiāo)時(shí)間＝500×2ns＝1μs。CPU用于該外設(shè)I/O時(shí)間占整個(gè)CPU時(shí)間的百分比＝預(yù)處理和后處理的總開(kāi)銷(xiāo)時(shí)間÷傳送數(shù)據(jù)的時(shí)間＝1/1000×100%＝0.001×100%＝0.1%。44（13分）某計(jì)算機(jī)字長(zhǎng)16位，采用16位定長(zhǎng)指令字結(jié)構(gòu)，部分?jǐn)?shù)據(jù)通路結(jié)構(gòu)如下圖所示，圖中所有控制信號(hào)為1時(shí)表示有效，為0時(shí)表示無(wú)效，例如控制信號(hào)MDRinE為1表示允許數(shù)據(jù)從DB打入MDR，MDRin為1表示允許數(shù)據(jù)從內(nèi)總線打入MDR。假設(shè)MAR的輸出一直處于使能狀態(tài)。加法指令“ADD（R1），R0”的功能為（R0）＋（（R1））一（R1），即將R0中的數(shù)據(jù)與R1的內(nèi)容所指主存單元的數(shù)據(jù)相加，并將結(jié)果送入R1的內(nèi)容所指主存單元中保存。下表給出了上述指令取指和譯碼階段每個(gè)節(jié)拍（時(shí)鐘周期）的功能和有效控制信號(hào)，請(qǐng)按表中描述方式用表格列出指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào)。解：執(zhí)行階段每個(gè)節(jié)拍（時(shí)鐘周期）的功能和有效控制信號(hào)見(jiàn)下表。45（7分）三個(gè)進(jìn)程P1、P2，P3互斥使用一個(gè)包含N（N＞0）個(gè)單元的緩沖區(qū)。P1每次用produce（）生成一個(gè)正整數(shù)并用put（）送入緩沖區(qū)某一空單元中；P2每次用getodd（）從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd（）統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個(gè)偶數(shù)并用counteven（）統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng)，并說(shuō)明所定義信號(hào)量的含義。要求用偽代碼描述。解：定義信號(hào)量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產(chǎn)者與消費(fèi)者之間的同步；mutex控制進(jìn)程間互斥使用緩沖區(qū)，程序如下：46（8分）請(qǐng)求分頁(yè)管理系統(tǒng)中，假設(shè)某進(jìn)程的頁(yè)表內(nèi)容如下表所示：頁(yè)面大小為4KB，一次內(nèi)存的訪問(wèn)時(shí)間是100ns，一次快表（TLB）的訪問(wèn)時(shí)間是10ns，處理一次缺頁(yè)的平均時(shí)間為108ns（已含更新TLB和頁(yè)表的時(shí)間），進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設(shè)①TLB初始為空；②地址轉(zhuǎn)換時(shí)先訪問(wèn)TLB，若TLB未命中，再訪問(wèn)頁(yè)表（忽略訪問(wèn)頁(yè)表之后的TLB更新時(shí)間）；③有效位為0表示頁(yè)面不在內(nèi)存，產(chǎn)生缺頁(yè)中斷，缺頁(yè)中斷處理后，返回到產(chǎn)生缺頁(yè)中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問(wèn)序列2362H、1565H、25A5H，請(qǐng)問(wèn)：（1）依次訪問(wèn)上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過(guò)程。（2）基于上述訪問(wèn)序列，虛地址1565H的物理地址是多少？請(qǐng)說(shuō)明理由。解：（1）210ns；108ns；110ns。頁(yè)面大小為4KB，因此，虛地址的低12位是頁(yè)內(nèi)偏移，其余高位是頁(yè)號(hào)。訪問(wèn)虛地址2362H，虛頁(yè)號(hào)為2，頁(yè)內(nèi)偏移362H。查找TLB，TLB初始為空，未命中，耗時(shí)10ns；訪問(wèn)頁(yè)表，2號(hào)頁(yè)面所在頁(yè)框號(hào)為254H，耗時(shí)100ns；計(jì)算得到的物理地址254362H，訪問(wèn)內(nèi)存，耗時(shí)100ns。因此，總共用時(shí)10＋100＋100＝210ns。訪問(wèn)虛地址1565H，虛頁(yè)號(hào)為1，頁(yè)