.. . .. . ..計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)模擬試題（第一套）一、單項(xiàng)選擇題：第1～40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符合試題要求。1．假設(shè) n 是描述問題規(guī)模的非負(fù)整數(shù) ，下面程序片段的時(shí)間復(fù)雜度為 （ ）。voidfun(intn){inti,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++){k=1;while(k<=n)k=5*k;}A．O(n2log2n)B．O(nlog5n)C．O(n2log5n)D．O(n3)2．以下說法正確的是（）。Ⅰ．帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L為空的條件是：L->prior==L&&L->next==LⅡ．線性表的插入和刪除總是伴隨著大量數(shù)據(jù)的移動(dòng)Ⅲ．只有刪除靜態(tài)鏈表的尾結(jié)點(diǎn)才不需要移動(dòng)元素Ⅳ．若線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，要求內(nèi)存中可用存儲(chǔ)單元的地址必須不連續(xù)A．僅ⅠB．僅Ⅰ、ⅡC．僅Ⅱ、ⅢD．Ⅰ、Ⅱ、Ⅲ和Ⅳ3．循環(huán)隊(duì)列用數(shù)組A[0?.-m1]存放其元素值，已知其頭尾指針分別是front和rear（且隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)元素），則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）。A．(rear-front+m)%mB．(rear-front+1)%mC．rear-front-1D．rear-front4．下列關(guān)于二叉樹的敘述中正確的是（）。Ⅰ．對(duì)于任何一棵二叉樹，葉子結(jié)點(diǎn)數(shù)都是度為2的結(jié)點(diǎn)數(shù)加1Ⅱ．二叉樹的左右子樹不. 專業(yè)學(xué)習(xí)資料 ... . .. . ..可以任意地交換. 專業(yè)學(xué)習(xí)資料 ... . .. . ..Ⅲ．二叉樹只適合使用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ) ，不可能用順序結(jié)構(gòu)存儲(chǔ) Ⅳ．結(jié)點(diǎn)按層序編號(hào)的二叉樹 ，第i個(gè)結(jié)點(diǎn)的左孩子 （假設(shè)存在）的編號(hào)為 2iA．僅Ⅰ、ⅡB．僅ⅡC．僅Ⅱ、Ⅳ D．僅Ⅱ、Ⅲ5．已知一棵深度為 k的平衡二叉樹，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為 0，則該樹共有結(jié)點(diǎn)總數(shù)為（ ）。A．2k1-1 B．2k1+1C．2k-1 D．2k+16．根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的赫夫曼編碼不可能是（）。A．000，001，010，011，1B．0000，0001，001，01，1C．000，001，01，10，11D．00，100，101，110，1117．在具有n個(gè)頂點(diǎn)的圖G中，若最小生成樹不唯一，則（）。Ⅰ．G的邊數(shù)一定大于n-1Ⅱ．G的權(quán)值最小的邊一定有多條Ⅲ．G的最小生成樹代價(jià)不一定相等A．僅ⅠB．僅Ⅰ、ⅢC．僅Ⅰ、ⅡD．僅Ⅲ8．以下哪些方法可以判斷出一個(gè)有向圖是否有環(huán)（）。Ⅰ．深度優(yōu)先遍歷Ⅱ．求最短路徑Ⅲ．拓?fù)渑判颌簦箨P(guān)鍵路徑A．僅Ⅰ、ⅢB．僅Ⅰ、Ⅲ、ⅣC．僅Ⅰ、Ⅱ、ⅢD．Ⅰ、Ⅱ、Ⅲ和Ⅳ9．在一棵二叉排序樹上，查找關(guān)鍵字為35的結(jié)點(diǎn)，依次比較的關(guān)鍵字有可能是（）。A．28，36，18，46，35B．18，36，28，46，35C．46，28，18，36，35D．46，36，18，28，3510．排序趟數(shù)與序列的原始狀態(tài)無關(guān)的排序方法是（）。Ⅰ．直接插入排序Ⅱ．簡(jiǎn)單選擇排序Ⅲ．冒泡排序Ⅳ．基數(shù)排序A．僅Ⅰ、ⅢB．僅Ⅰ、Ⅱ、ⅣC．僅Ⅰ、Ⅱ、ⅢD．僅Ⅰ、Ⅳ11下．列關(guān). 專業(yè)學(xué)習(xí)資料 ... . .. . ..于外部排序說法正確的是 （ ）。A．內(nèi)存與外設(shè)交換信息的時(shí)間只是外排序總時(shí)間的一小部分 B．外部排序就是在外存上進(jìn)行排序 ，無需內(nèi)存參與 C．?dāng)≌邩涫且豢猛耆鏄銬．置換-選擇排序得到的初始?xì)w并段長(zhǎng)度一定相等12．圖 1-1 中計(jì)算機(jī)硬件系統(tǒng)基本組成部件 ①、②、③、④ 和⑤的名稱分別是 （ ）。A．①控制器、②運(yùn)算器、③存儲(chǔ)器、④輸入設(shè)備、⑤輸出設(shè)備. 專業(yè)學(xué)習(xí)資料 ... . .. . ..B．①運(yùn)算器、②控制器、③存儲(chǔ)器、④輸入設(shè)備、⑤輸出設(shè)備C．①運(yùn)算器、②存儲(chǔ)器、③控制器、④輸入設(shè)備、⑤輸出設(shè)備D．①運(yùn)算器、②控制器、③存儲(chǔ)器、④輸出設(shè)備、⑤輸入設(shè)備圖1-1 計(jì)算機(jī)硬件系統(tǒng)基本組成部件13．已知小寫英文字母 “的a”ASCII碼值為61H，現(xiàn)字母“g被”存放在某個(gè)存儲(chǔ)單元中 ，若采用偶校驗(yàn)（假設(shè)最高位作為校驗(yàn)位 ），則該存儲(chǔ)單元中存放的十六進(jìn)制數(shù)是 （ ）。A．167H B．E6H C．67H D．E7H14．頁式存儲(chǔ)系統(tǒng)的邏輯地址是由頁號(hào)和頁內(nèi)地址兩部分組成的 。假定頁面的大小為 4KB，地址變換過程如圖 1-2 所示，圖中邏輯地址用十進(jìn)制數(shù)表示 。邏輯地址經(jīng)過變換后 ，十進(jìn)制數(shù)物理地址 a 應(yīng)為（ ）。A．33220 B．8644 C．4548 D．2500圖1-2 頁式存儲(chǔ)系統(tǒng)的邏輯地址變換過程15．下列關(guān)于 ROM和RAM的說法中，正確的是（ ）。Ⅰ．CD-ROM 與EPROM都采用隨機(jī)存儲(chǔ)方式Ⅱ．SRAM讀后不需要刷新 ，而DRAM讀后需要刷新Ⅲ．Cache可以由ROM或者RAM組成A．Ⅰ、Ⅱ和Ⅲ B．僅Ⅱ和Ⅲ. 專業(yè)學(xué)習(xí)資料 ... . .. . ..C．僅Ⅲ D．僅Ⅱ16．下列關(guān)于 Flash 存儲(chǔ)器的說法正確的是 （ ）。A．Flash存儲(chǔ)器屬于易失性存儲(chǔ)器. 專業(yè)學(xué)習(xí)資料 .........B．Flash存儲(chǔ)器不具備寫功能C．Flash存儲(chǔ)器是不可擦除的存儲(chǔ)器D．Flash存儲(chǔ)器同時(shí)具有ROM和RAM的功能17．某機(jī)器采用16位單字長(zhǎng)指令，采用定長(zhǎng)操作碼，地址碼為5位，現(xiàn)已定義60條二地址指令，那么單地址指令最多有（）條。A．4B．32C．128D．25618．指令（）從主存中讀出。A．總是根據(jù)程序計(jì)數(shù)器（PC）B．有時(shí)根據(jù)PC，有時(shí)根據(jù)轉(zhuǎn)移指令C．根據(jù)地址寄存器D．有時(shí)根據(jù)PC，有時(shí)根據(jù)地址寄存器19．當(dāng)有中斷源發(fā)出請(qǐng)求時(shí)，CPU可執(zhí)行相應(yīng)的中斷服務(wù)程序，以下可以提出中斷請(qǐng)求的是（）。Ⅰ．外部事件Ⅱ．CacheⅢ．浮點(diǎn)運(yùn)算下溢Ⅳ．浮點(diǎn)運(yùn)算上溢A．僅Ⅰ、ⅢB．僅Ⅱ、Ⅲ、ⅣC．僅Ⅰ、ⅣD．僅Ⅰ、Ⅲ、Ⅳ20．某數(shù)碼相機(jī)內(nèi)置128MB的存儲(chǔ)空間，拍攝分辨率設(shè)定為1600×1200像素，顏色深度為24位，若不采用壓縮存儲(chǔ)技術(shù)，使用內(nèi)部存儲(chǔ)器最多可以存儲(chǔ)（）張照片。A．12B．25C．13D．2321．下面關(guān)于PCI總線的基描述中，錯(cuò)．誤．的有（）。Ⅰ．PCI總線是一個(gè)與處理器性能相關(guān)的高速外圍總線Ⅱ．PCI總線可對(duì)傳輸信息進(jìn)行奇偶校驗(yàn)Ⅲ．PCI設(shè)備一定是主設(shè)備Ⅳ．系統(tǒng)中允許有多條PCI總線A．僅Ⅰ、ⅡB．僅Ⅱ、ⅢC．僅Ⅲ和ⅣD．僅Ⅰ、Ⅲ22．下列說法正確的是（）。A．在統(tǒng)一編址方式下，訪問主存儲(chǔ)器和訪問I/O設(shè)備是通過不同的指令來區(qū)分的B．計(jì)算機(jī)的外圍設(shè)備就是指輸入和輸出設(shè)備C．中斷隱指令屬于程序控制型指令D．在中斷服務(wù)程序中，恢復(fù)現(xiàn)場(chǎng)之前需要關(guān)中斷23．下列關(guān)于分時(shí)操作系統(tǒng). 專業(yè)學(xué)習(xí)資料 ... . .. . ..和實(shí)時(shí)操作系統(tǒng)說法錯(cuò)誤的是 （ ）。Ⅰ．分時(shí)操作系統(tǒng)的時(shí)間片固定 ，那么用戶數(shù)越多 ，響應(yīng)時(shí)間越長(zhǎng)Ⅱ．在主存容量為 M的多用戶分時(shí)操作系統(tǒng)中 ，當(dāng)注冊(cè)用戶數(shù)為 N時(shí)，每個(gè)用戶擁有的主存空間為 M/N. 專業(yè)學(xué)習(xí)資料 .........Ⅲ．對(duì)于實(shí)時(shí)操作系統(tǒng)而言，處理機(jī)效率一般不作為其設(shè)計(jì)目標(biāo)Ⅳ．鐵路信號(hào)系統(tǒng)、門禁系統(tǒng)和股票交易系統(tǒng)都需要實(shí)時(shí)操作系統(tǒng)支持A．Ⅰ、ⅣB．Ⅱ、ⅢC．只有ⅡD．只有Ⅳ24．以下服務(wù)中，能發(fā)揮多線程系統(tǒng)的特長(zhǎng)的是（）。Ⅰ．利用線程并發(fā)地執(zhí)行矩陣乘法運(yùn)算Ⅱ．Web服務(wù)器利用線程請(qǐng)求HTTP服務(wù)Ⅲ．鍵盤驅(qū)動(dòng)程序?yàn)槊恳粋€(gè)正在運(yùn)行的應(yīng)用配備一個(gè)線程，用來響應(yīng)相應(yīng)的鍵盤輸入Ⅳ．基于GUI的debugger用不同線程處理用戶的輸入、計(jì)算、跟蹤等操作A．Ⅰ、ⅢB．Ⅱ、ⅢC．Ⅰ、Ⅱ、ⅢD．Ⅰ、Ⅱ、Ⅳ25．現(xiàn)在有3個(gè)同時(shí)到達(dá)的作業(yè)J1、J2和J3，它們的執(zhí)行時(shí)間分別為T1、T2和T3，且T1<T2<T3。如果該系統(tǒng)中有兩個(gè)CPU，各自按照單道方式運(yùn)行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時(shí)間是（）。A．（T1+T2+T3）/3B．（2T1+T2+T3）/3C．（T1+2T2+T3）/3D．（2T1+T2+T3）/3或（T1+2T2+T3）/326．對(duì)計(jì)數(shù)型信號(hào)量S執(zhí)行V操作后，下列選項(xiàng)錯(cuò)誤的是（）。Ⅰ．當(dāng)S.value≤0時(shí)，喚醒一個(gè)阻塞隊(duì)列進(jìn)程Ⅱ．只有當(dāng)S.value<0時(shí)，喚醒一個(gè)阻塞隊(duì)列進(jìn)程Ⅲ．當(dāng)S.value≤時(shí)0，喚醒一個(gè)就緒隊(duì)列進(jìn)程Ⅳ．只有當(dāng)S.value<0時(shí)，喚醒一個(gè)就緒隊(duì)列進(jìn)程A．Ⅱ、ⅢB．Ⅱ、Ⅲ、ⅣC．Ⅰ、ⅢD．Ⅰ、Ⅲ、Ⅳ27．設(shè)有8頁的邏輯空間，每頁有1024B，它們被映射到32塊的物理存儲(chǔ)區(qū)中。那么邏輯地址的有效位是（），物理地址至少是（）位。A．10，12B．10，15C．13，15D．13，1228．某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁1KB，主29．假定有一個(gè)請(qǐng)存為16KB。假定某時(shí)刻用戶頁表中已調(diào)入主存的頁面的虛頁號(hào)和物求分頁存儲(chǔ)管理系理頁號(hào)對(duì)照表（見表1-1）。統(tǒng)，測(cè)得系統(tǒng)各相則與表1-2十六進(jìn)制虛地址對(duì)應(yīng)的物理地址為（）。關(guān)設(shè)備的A．1E5C，2A5CB．1E5C，缺頁中斷利用率如下：CPU利用C．125C，2A5CD．125C，缺頁中斷率為10%，磁盤交換區(qū). 專業(yè)學(xué)習(xí)資料 ... . .. . ..為99.7%：其他I/O設(shè)備為5%。試問：下面措施中將可能改進(jìn)CPU 利用率的是（ ）。Ⅰ．增大內(nèi)存的容量 Ⅱ．增大磁盤交換區(qū)的容量

表1-1 頁面映射表虛頁號(hào) 物理頁號(hào)0 51 102 43 7表1-2十六進(jìn)制虛地址對(duì)應(yīng)的物理地址模擬試題（第一套） 第5頁（共32頁）

虛地址 物理地址0A5C （1）1A5C （2）. 專業(yè)學(xué)習(xí)資料 .........Ⅲ．減少多道程序的道數(shù)Ⅳ．增加多道程序的道數(shù)Ⅴ．使用更快速的磁盤交換區(qū)Ⅵ．使用更快速的CPUA．Ⅰ、Ⅱ、Ⅲ、ⅣB．Ⅰ、ⅢC．Ⅱ、Ⅲ、ⅤD．Ⅱ、Ⅵ30下．面關(guān)于文件系統(tǒng)的說法正確的是（）。A．文件系統(tǒng)負(fù)責(zé)文件存儲(chǔ)空間的管理但不能實(shí)現(xiàn)文件名到物理地址的轉(zhuǎn)換B．在多級(jí)目錄結(jié)構(gòu)中對(duì)文件的訪問是通過路徑名和用戶目錄名進(jìn)行的C．文件可以被劃分成大小相等的若干物理塊且物理塊大小也可以任意指定D．邏輯記錄是對(duì)文件進(jìn)行存取操作的基本單位31．一個(gè)交叉存放信息的磁盤，信息存放方式如圖1-3所示。每個(gè)磁道有8個(gè)扇區(qū)，每個(gè)扇區(qū)512B，旋轉(zhuǎn)速度為3000轉(zhuǎn)/分。假定磁頭已在讀取信息的磁道上，0扇區(qū)轉(zhuǎn)到磁頭下需要1/2轉(zhuǎn)，且設(shè)備對(duì)應(yīng)的控制器不能同時(shí)進(jìn)行輸入/輸出，在數(shù)據(jù)從控制器傳送至內(nèi)存的這段時(shí)間內(nèi)，從磁頭下通過的扇區(qū)數(shù)為2，問依次讀取一個(gè)磁道上所有的扇區(qū)的數(shù)據(jù)到內(nèi)存平均傳輸速度為（）。A．57.1KB/sB．67.1KB/s圖1-3磁盤中信息存放方式C．77.1KB/sD．87.1KB/s32．假設(shè)T是從磁盤輸入一塊數(shù)據(jù)到緩沖區(qū)需要的時(shí)間，C是CPU對(duì)一塊數(shù)據(jù)進(jìn)行處理的時(shí)間，而M是將一塊數(shù)據(jù)從緩沖區(qū)傳送到用戶區(qū)的時(shí)間。當(dāng)一用戶進(jìn)程要按順序訪問的方式處理大量數(shù)據(jù)時(shí)，請(qǐng)問在單緩沖和雙緩沖的情況下，系統(tǒng)對(duì)一塊數(shù)據(jù)的處理時(shí)間分別是（）。A．max(T,C)+M,max(T,M+C)B．max(T,M+C),max(T,C)+MC．max(T,M)+C,max(T,M+C)D．max(T,M+C),max(T,M)+C33．計(jì)算機(jī)網(wǎng)絡(luò)可分為通信子網(wǎng)和資源子網(wǎng)，下列屬于通信子網(wǎng)的是（）。Ⅰ．網(wǎng)橋Ⅱ．交換機(jī)Ⅲ．計(jì)算機(jī)軟件Ⅳ．路由器A．Ⅰ、Ⅱ、ⅣB．Ⅱ、Ⅲ、ⅣC．Ⅰ、Ⅲ、ⅣD．Ⅰ、Ⅱ、Ⅲ34．用PCM對(duì)語音進(jìn)行數(shù)字化 ，如果將聲音分為 128個(gè)量化級(jí)，一個(gè)典型的電話通道是4kHz，那么一路話音需要的數(shù)據(jù)傳輸率為 （ ）。A．56kbit/s B．64kbit/sC．128kbit/s D．1024kbit/s35 ．在可靠傳輸機(jī)制中 ，發(fā)送窗口的. 專業(yè)學(xué)習(xí)資料 ... . .. . ..位置由窗口前沿和后沿的位置共同確定 ，經(jīng)過一段時(shí)間，發(fā)送窗口的后沿的變化情況可能為 （ ）。Ⅰ．原地不動(dòng) Ⅱ．向前移動(dòng) Ⅲ．向后移動(dòng)A．Ⅰ、Ⅲ B．Ⅰ、ⅡC．Ⅱ、Ⅲ D．都有可能. 專業(yè)學(xué)習(xí)資料 ... . .. . ..36．在IPv6 協(xié)議中，一個(gè)數(shù)據(jù)流可以由 （ ）進(jìn)行標(biāo)識(shí)。A．源地址、目的地址和流名稱 B．源地址、目的地址和流標(biāo)號(hào)C．源地址、端口號(hào)和流標(biāo)號(hào)D．MAC 地址、端口號(hào)和流名稱37．假定在一個(gè)局域網(wǎng)中計(jì)算機(jī) A發(fā)送了ARP請(qǐng)求分組，希望找出計(jì)算機(jī) B的硬件地址，局域網(wǎng)上的所有計(jì)算機(jī)都能接收到這個(gè)廣播發(fā)送的 ARP 請(qǐng)求分組。這時(shí)由（ ）使用ARP響應(yīng)分組進(jìn)行回應(yīng) 。A．計(jì)算機(jī) A B．計(jì)算機(jī)BC．路由器 D．不一定38．一個(gè)有50個(gè)路由器的網(wǎng)絡(luò) ，采用基于距離-向量的路由選擇算法 ，路由表的每個(gè)表項(xiàng)長(zhǎng)度為6B，每個(gè)路由器都有 3個(gè)鄰接路由器 ，每秒與每個(gè)鄰接路由器交換 1次路由表，則每條鏈路上由于路由器更新路由信息而耗費(fèi)的帶寬為 （ ）。A．2400bit/s B．3600bit/sC．4800bit/s D．6000bit/s39．設(shè)某TCP的擁塞窗口的慢啟動(dòng)門限值初始為 8（單位為報(bào)文段，且最大報(bào)文段長(zhǎng)度為1KB），當(dāng)擁塞窗口上升到 12時(shí)，網(wǎng)絡(luò)會(huì)發(fā)生超時(shí) 。按照以上給出的條件 ，第12次傳輸時(shí)，擁塞窗口的大小為 （ ）。A．5 B．6 C．7 D．840．關(guān)于 FTP 的工作過程，下面說法錯(cuò)誤的是 （ ）。A．每次數(shù)據(jù)傳輸結(jié)束后 ，F(xiàn)TP服務(wù)器同時(shí)釋放 21和20端口B．FTP的數(shù)據(jù)連接是非持久的C．FTP的文件傳輸需要兩條 TCP連接D．FTP協(xié)議可以在不同類型的操作系統(tǒng)之間傳送文件. 專業(yè)學(xué)習(xí)資料 ... . .. . ..參考答案一、單項(xiàng)選擇題1C2A3A4B5C6D7A8A9D10B11C12B13D14A15D16D17A18A19C20D21D22D23C24D25B26B27C28D29B30D31A32A33A34A35B36B37D38C39B40A1．C。首先抓基本運(yùn)算語句，即k=5*k;設(shè)其執(zhí)行時(shí)間為T（n）。對(duì)于j每循環(huán)一次，該語句的執(zhí)行次數(shù)為m，有5m≤n，即m≤log5n。所以，nnnn222T(n)i1j1mmi1nlog5nO(nlog5n)2．A。j1mnⅠ：循環(huán)雙鏈表為空時(shí)頭結(jié)點(diǎn)體現(xiàn)如圖1-6所示?？梢姰?dāng)滿足L→prior==L&&L→next==L時(shí)，雙鏈表為空，并且循環(huán)雙鏈表與循環(huán)單鏈表一樣，沒有空指針域，所以Ⅰ正確。Ⅱ：鏈表也是線性表，鏈表的插入和刪除操作不需要大量的數(shù)據(jù)移動(dòng)，所以Ⅱ錯(cuò)誤。圖1-6空循環(huán)雙鏈表Ⅲ：靜態(tài)鏈表盡管使用的是數(shù)組存儲(chǔ)方式，但是數(shù)據(jù)之間是靠指針（游標(biāo)）相互關(guān)聯(lián)的，故不管是刪除靜態(tài)鏈表中的哪一個(gè)結(jié)點(diǎn)，都不需要移動(dòng)元素，只需要修改指針即可，所以Ⅲ錯(cuò)誤。Ⅳ：線性表采用鏈表存儲(chǔ)，前驅(qū)和后繼之間的聯(lián)系需要依靠由前驅(qū)指向后繼的指針，而與. 專業(yè)學(xué)習(xí)資料 ... . .. . ..前驅(qū)和后繼在內(nèi)存中的物理位置無關(guān) ，因此對(duì)于整條鏈表的存儲(chǔ) ，不需要?jiǎng)澐忠粔K連續(xù)的存儲(chǔ)空間；但將鏈表中結(jié)點(diǎn)挨個(gè)連續(xù)存儲(chǔ)在一片空間中也未嘗不可 。對(duì)于線性表的鏈?zhǔn)酱鎯?chǔ) ，連續(xù)或者不連續(xù)的存儲(chǔ)空間都能滿足要求 ，所以Ⅳ錯(cuò)誤。3．A。因?yàn)槭茄h(huán)隊(duì)列 ，所以應(yīng)該分為 rear>front 和rear<front 兩種情況來討論 。（1）當(dāng)rear>front 時(shí)，隊(duì)列中元素個(gè)數(shù)為rear-front=(rear-front+m)%m因?yàn)?<rear-front<m ，所以rear-front+m 與m取余后結(jié)果還是 rear-front 。（2）當(dāng)rear<front 時(shí)，隊(duì)列中元素個(gè)數(shù)為m-（front-rear ）=rear-front+m= （rear-front+m)%m因?yàn)?<rear-front+m<m ，所以rear-front+m 與m取余后結(jié)果還是 rear-front+m 。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..綜合（1）、（2）可知，A選項(xiàng)正確。知識(shí)點(diǎn)總結(jié)：循環(huán)隊(duì)列的兩大狀態(tài)和兩大操作以及三大重點(diǎn)提醒。（1）兩大狀態(tài)（數(shù)學(xué)式子表示 ）1）隊(duì)空狀態(tài)：q.rear==q.front 。2）隊(duì)滿狀態(tài)：q.rear+1）%MAX==q.front。2）兩大操作1）元素x進(jìn)隊(duì)操作（移動(dòng)隊(duì)尾指針）。q.rear=(q.rear+1)%MAX ；q.data[q.rear]=x ；2）元素x出隊(duì)操作（移動(dòng)隊(duì)頭指針）。q.front=(qu.front+1)%MAX ；x=q.data[q.front] ；重點(diǎn)提醒 1：有些教材說循環(huán)隊(duì)列隊(duì)尾指針指向隊(duì)尾元素 ，有些教材說循環(huán)隊(duì)列隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)元素 。不同的說法可能導(dǎo)致很多題目的答案總是相差 1。所以如果在考研試卷中碰到 ，且題目沒有說明 （不過像考研試卷一般都會(huì)說明 ），一律認(rèn)為是循環(huán)隊(duì)列隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)元素 。重點(diǎn)提醒2：元素入隊(duì)時(shí)，先移動(dòng)指針，后存入元素；元素出隊(duì)時(shí)，也是先移動(dòng)指針，再取出元素。有些書上可能有不同的順序，其實(shí)本質(zhì)是一樣的，考生只需去適應(yīng)一種寫法，對(duì)于程序設(shè)計(jì)題目已經(jīng)足夠 。對(duì)于選擇題，則可根據(jù)題目描述確定是先存取元素 ，再移動(dòng)指針，還是其他處理順序 。重點(diǎn)提醒 3：循環(huán)隊(duì)列的隊(duì)尾指針 、隊(duì)頭指針、隊(duì)中元素個(gè)數(shù) ，知道其中任何兩者均可算出第三者。4．B。Ⅰ：Ⅰ的描述只有在 非空二叉樹的情況下才成立 ，所以考生在做這種概念題目的時(shí)候一定要先想到這種特殊情況 ，所以Ⅰ錯(cuò)誤。Ⅱ：二叉樹的左右子樹是有順序的 ，不能隨意交換 ，所以Ⅱ正確。Ⅲ：一般的二叉樹確實(shí)不能使用順序結(jié)構(gòu)存儲(chǔ) ，但是完全二叉樹和滿二叉樹一般都使用順序結(jié)構(gòu)存儲(chǔ)，所以Ⅲ錯(cuò)誤。Ⅳ：該結(jié)論只對(duì)完全二叉樹才成立 ，所以Ⅳ錯(cuò)誤。綜上所述，只有Ⅱ正確。5．C。每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為 0，說明了該平衡二叉樹為滿二叉樹 ，所以結(jié)點(diǎn)總數(shù)為2k-1?？偨Y(jié)：（1）設(shè)Nh表示深度為 h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù) ，則. 專業(yè)學(xué)習(xí)資料 .........N0=0，N1=1，N2=2，L，Nh=Nh1+Nh2+1例如，深度為5的平衡二叉樹中含有最少的結(jié)點(diǎn)數(shù)為N5=12。（2）二叉排序樹的查找效率取決于其深度 。對(duì)于結(jié)點(diǎn)個(gè)數(shù)相同的二叉排序樹 ，平衡二叉樹. 專業(yè)學(xué)習(xí)資料 .........的深度最小，因此效率最高。6．D。赫夫曼樹中只有度為0或2的結(jié)點(diǎn)，由D選項(xiàng)可以畫出對(duì)應(yīng)的二叉樹，如圖1-7所示。圖1-7 D 選項(xiàng)對(duì)應(yīng)的二叉樹由赫夫曼樹的性質(zhì)可知 ，樹中不應(yīng)該含度為 1的結(jié)點(diǎn)，因此D選項(xiàng)不可能。7．A。最小生成樹邊的權(quán)值之和最小 ，若兩棵樹同時(shí)為最小生成樹 ，那么它們的邊的權(quán)值之和一定相等，故Ⅲ錯(cuò)誤；既然最小生成樹不唯一 ，并且最小生成樹的邊都為 n-1 條，說明圖G的邊數(shù)一定會(huì)大于 n-1，故Ⅰ正確；最小生成樹不唯一 ，和G的權(quán)值最小的邊的條數(shù)沒有任何關(guān)系 ，故Ⅱ錯(cuò)誤。8．A。有兩種方法可以判斷有向圖中是否有回路 。用深度優(yōu)先遍歷的方法 ，如果從有向圖上某個(gè)頂點(diǎn)v出發(fā)的遍歷，在dfs(v)結(jié)束之前出現(xiàn)一條從頂點(diǎn) j到v的邊，由于j在生成樹上是 v的子孫，則圖中必定存在包含 v和j 的環(huán)，因此Ⅰ可以；用拓?fù)渑判虻姆椒?，在拓?fù)渑判蜻^程中 ，每次要?jiǎng)h去一個(gè)沒有前驅(qū)的頂點(diǎn) ，如果最后圖中所有頂點(diǎn)都被刪除 ，則表示沒有環(huán) ，否則有環(huán)，因此Ⅲ正確。而最短路徑和關(guān)鍵路徑 （建立在無環(huán)的 AOE 網(wǎng)的基礎(chǔ)之上）都是不可以判斷的 。補(bǔ)充：還有一個(gè)出題點(diǎn)是間接出題 ，即若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則斷定該有向圖一定有什么？想必90%以上的考生都會(huì)選擇有環(huán)，但是沒有環(huán)這個(gè)選項(xiàng)，只有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量這個(gè)選項(xiàng)，此時(shí)考生必須知道頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量就表明有環(huán)。9．D?？梢愿鶕?jù)選項(xiàng)畫出查找路線上的結(jié)點(diǎn) ，根據(jù)二叉排序樹的規(guī)定來排除不滿足條件的選項(xiàng)。根據(jù)題目選項(xiàng)所得查找路線如圖 1-8所示。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..圖1-8查找路線圖A選項(xiàng)中28的右子樹中出現(xiàn)了小于它的18，不滿足二叉排序樹規(guī)定，排除。B選項(xiàng)中36的左子樹中出現(xiàn)了大于它的46，不滿足二叉排序樹規(guī)定，排除。C選項(xiàng)中28的左子樹中出現(xiàn)了大于它的36，不滿足二叉排序樹規(guī)定，排除。補(bǔ)充：在關(guān)鍵字隨機(jī)分布的情況下，用二叉排序樹的方法進(jìn)行查找，其查找長(zhǎng)度相當(dāng)于折半查找的時(shí)間復(fù)雜度，即O(log2n)。平衡二叉樹的查找效率最高，因?yàn)槎鏄涞牟檎倚嗜Q于二叉樹的高度，對(duì)于結(jié)點(diǎn)個(gè)數(shù)相同的二叉樹，平衡二叉樹的高度最小。10．B。直接插入排序：每趟排序都是插入一個(gè)元素，所以排序趟數(shù)固定為n-1（n為元素?cái)?shù)）。簡(jiǎn)單選擇排序：每趟排序都是選出一個(gè)最?。ɑ蜃畲螅┑脑?，所以排序趟數(shù)固定為n-1（n為元素?cái)?shù)）。交換類的排序：其趟數(shù)和原始序列狀態(tài)有關(guān)，所以冒泡排序與初始序列有關(guān)?；鶖?shù)排序：每趟排序都要進(jìn)行“分配”和“收集”，排序趟數(shù)固定為d（d為組成元素的關(guān)鍵字位數(shù)）。綜上所述，Ⅰ、Ⅱ、Ⅳ都是無關(guān)的，所以選B。11．C。A：影響外排序時(shí)間的主要因素就是內(nèi)存與外設(shè)交換信息的總次數(shù)，所以A錯(cuò)誤。B：外部排序也是在內(nèi)存上進(jìn)行排序，只不過需要分為多步而已，所以B錯(cuò)誤。C：從敗者樹的構(gòu)建方式可知，敗者樹是一棵完全二叉樹，所以C正確。補(bǔ)充知識(shí)點(diǎn)：敗者樹和堆有什么區(qū)別？解析：外排序中敗者樹和堆排序的區(qū)別在于：（1）敗者樹是在雙親結(jié)點(diǎn)中記下剛進(jìn)行完的這場(chǎng)比賽的敗者，而讓勝者去參加更加高一層的比賽，便可得到一棵敗者樹。而堆排序可看做一種勝者樹，即雙親結(jié)點(diǎn)表示其左右孩子中的勝者。（2）在敗者樹中，參加比較的n個(gè)關(guān)鍵字全部為葉子結(jié)點(diǎn)，雙親即為其左、右子女的敗者，敗者樹中結(jié)點(diǎn)總數(shù)為2n-1，加上冠軍結(jié)點(diǎn)恰好為2n。而堆是由n個(gè)關(guān)鍵字組成的完全二叉樹，每個(gè)關(guān)鍵字作為樹中一個(gè)結(jié)點(diǎn)，根是n個(gè)關(guān)鍵字中的勝者，樹中結(jié)點(diǎn)總數(shù)為n。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..D：使用置換-選擇排序得到的初始?xì)w并段長(zhǎng)度不一定相等 ，從最佳歸并樹構(gòu)造赫夫曼樹的過程也可以得到答案 ，所以D錯(cuò)誤。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..外排序的基本過程 ：基于磁盤進(jìn)行的排序多使用歸并排序方法 。其排序過程主要分為兩個(gè)階段 ：（1）建立用于外排序的內(nèi)存緩沖區(qū) 。根據(jù)它們的大小將輸入文件劃分為若干段 ，用某種內(nèi)排序方法對(duì)各段進(jìn)行排序 。經(jīng)過排序的段叫做初始?xì)w并段 。當(dāng)它們生成后就被寫到外存中 。（2）按歸并樹模式 ，把（1）生成的初始?xì)w并段加以歸并 ，一趟趟擴(kuò)大歸并段和減少歸并段數(shù)，直到最后歸并成一個(gè)大歸并段為止 。例如：設(shè)有一個(gè)包含 4500 個(gè)記錄的輸入文件 ，現(xiàn)用一臺(tái)其內(nèi)存至多可容納 750個(gè)記錄的計(jì)算機(jī)對(duì)該文件進(jìn)行排序 。輸入文件放在磁盤上 ，磁盤每個(gè)頁塊可容納 250 個(gè)記錄，這樣全部記錄可存儲(chǔ)在 4500/250=18 個(gè)塊中。輸出文件也放在磁盤上 ，用以存放歸并結(jié)果 。由于內(nèi)存中可用于排序的存儲(chǔ)區(qū)域能容納 750 個(gè)記錄，所以內(nèi)存中恰好能存 3 個(gè)塊的記錄。在外排序一開始，把18 塊記錄每3塊一組讀入內(nèi)存 。利用某種內(nèi)排序方法進(jìn)行內(nèi)排序 ，形成初始?xì)w并段 ，再寫回外存?？偣部傻玫?6個(gè)初始?xì)w并段 。然后一趟一趟進(jìn)行歸并排序 ，如圖1-9所示。圖1-9 歸并排序12．B。圖中實(shí)線框?yàn)?CPU，而CPU包含五大部件中的運(yùn)算器和控制器 ，排除C選項(xiàng)。控制器為計(jì)算機(jī)提供工作統(tǒng)一的時(shí)鐘及其發(fā)出各種控制命令來協(xié)調(diào)計(jì)算機(jī)的各部件自動(dòng)地工作 ，所以控制器應(yīng)該與其他四大部件相連 ，可得①為運(yùn)算器，②為控制器。最后，根據(jù)數(shù)據(jù)的流向可以判斷，④為輸入設(shè)備，⑤為輸出設(shè)備。剩下③為存儲(chǔ)器。13．D。由于“a的”ASCII 碼值為61H，而“g是”第7 個(gè)字母，所以可以得到 “g的”ASCII碼值應(yīng)為. 專業(yè)學(xué)習(xí)資料 ... . .. . ..61H +6=67H=1100111B ?，F(xiàn)在“g的”ASCII 碼值中有5 個(gè)“1”按，照偶校驗(yàn)的規(guī)則，應(yīng)該在最高位上添加一個(gè) 1，使得“1的”個(gè)數(shù)為偶數(shù)個(gè) ，最后可得該存儲(chǔ)單元中存放的十六進(jìn) 制數(shù)為E7H11100111）。14．A。本題考查的是頁式存儲(chǔ)系統(tǒng)管理中的地址變換知識(shí) 。在頁式存儲(chǔ)系統(tǒng)管理中 ，邏輯地址除. 專業(yè)學(xué)習(xí)資料 ... . .. . ..以頁的大小，然后向下取整為頁號(hào) ，取余為頁內(nèi)地址 。本題頁面的大小為 4KB，邏輯地址 8644除以4096，取整為2，取余為452。頁號(hào)為2，查頁表得物理塊號(hào)為 8。因此，a的有效地址為8×4096+452=33220 。15．D。對(duì)于選項(xiàng)Ⅰ：首先，ROM和RAM都是采用隨機(jī)存取方式 。由于EPROM屬于ROM，故采用隨機(jī)存取方式 。而CD-ROM 屬于光盤，為非隨機(jī)存儲(chǔ) ，故Ⅰ錯(cuò)誤。對(duì)于選項(xiàng)Ⅱ：SRAM采用雙穩(wěn)態(tài)觸發(fā)器來記憶信息 ，因此不需要刷新 ；而DRAM采用電容存儲(chǔ)電荷的原理來存儲(chǔ)信息 ，只能維持很短的時(shí)間 ，因此需要刷新 ，故Ⅱ錯(cuò)誤。對(duì)于選項(xiàng)Ⅲ：Cache需要有信息的輸入和輸出 ，而ROM只可讀，不可輸入，因此不能作為Cache，故Ⅲ錯(cuò)誤。16．D。Flash存儲(chǔ)器是一種具有較高存儲(chǔ)容量 、較低價(jià)格、非易失性、可在線擦除與編程的新一代讀寫存儲(chǔ)器 。從基本工作原理上看 ，F(xiàn)lash存儲(chǔ)器屬于 ROM 型存儲(chǔ)器，但由于它又可以隨時(shí)改寫其中的信息，所以從功能上看 ，它又相當(dāng)于隨機(jī)存儲(chǔ)器 （RAM）。Flash存儲(chǔ)器與其他存儲(chǔ)器的區(qū)別總結(jié) （見表1-6）。表1-6 Flash 存儲(chǔ)器與其他存儲(chǔ)器區(qū)別內(nèi)存類型非易失性高密度可寫Flash存儲(chǔ)器是是是SRAM不是不是是DRAM不是是是ROM是是不是EPROM是是不是EEPROM是不是是17．A。首先可以計(jì)算出操作碼字段的長(zhǎng)度為16-5-5=6。所以一共可以定義26=64條指令，既然二地址指令占了60條，且是定長(zhǎng)操作碼，故單地址指令最多可以有64-60=4條，所以選A。如果此題將條件改為采用不定長(zhǎng)操作碼，答案又是什么？分析如下：如果采用不定長(zhǎng)（擴(kuò)展）操作碼，每條二地址指令可擴(kuò)展為32條單地址指令，那么單地址指令最多有32×4=128條。18．A。指令總是根據(jù)程序計(jì)數(shù)器 （PC）從主存中讀出（一定記?。？赡芸忌鷷?huì)想到 無條件轉(zhuǎn)移指令情況，認(rèn)為不一定總是根據(jù) PC讀出。實(shí)際上，正確的執(zhí)行順序是這樣的 ，當(dāng)前指令正在. 專業(yè)學(xué)習(xí)資料 ... . .. . ..執(zhí)行時(shí)，其實(shí)PC已經(jīng)是下一條指令的地址了 ，如果遇到了無條件轉(zhuǎn)移指令 ，則只需要簡(jiǎn)單地把跳轉(zhuǎn)的地址覆蓋 PC的內(nèi)容就可以了 ，最終的結(jié)果還是指令需要根據(jù)程序計(jì)數(shù)器從主存讀出 。19．C。Ⅰ：外部事件是可以提出中斷請(qǐng)求的 ，如可以通過敲擊鍵盤來終止現(xiàn)在正在運(yùn)行的程序，. 專業(yè)學(xué)習(xí)資料 ... . .. . ..這個(gè)就可以看做一個(gè)中斷 ，所以Ⅰ可以。Ⅱ：Cache是屬于存儲(chǔ)設(shè)備 ，不能提出中斷請(qǐng)求 ，所以Ⅱ不可以。Ⅲ、Ⅳ：浮點(diǎn)運(yùn)算下溢 ，可以當(dāng)做機(jī)器零處理 ，不需要中斷來處理 ；而浮點(diǎn)運(yùn)算上溢 ，必須中斷來做相應(yīng)的處理 ，所以Ⅲ不可以，Ⅳ可以。20．D。位圖像是典型的JPG圖片，RGB各占8位，合計(jì)3B。未經(jīng)壓縮的圖片大小=1600×1200×3B≈5.5MB，128MB/5.5MB=23.3 ，所以內(nèi)置的存儲(chǔ)空間最多可存儲(chǔ) 23 張照片。．D。PCI總線與CPU及時(shí)鐘頻率都無關(guān) ，故Ⅰ錯(cuò)誤；PCI總線支持即插即用并且可對(duì)數(shù)據(jù)和地址進(jìn)行奇偶校驗(yàn) ，并且 PCI總線采用猝發(fā)傳送方式 ，故Ⅱ正確；主設(shè)備指獲得總線控制權(quán)的設(shè)備，所以PCI設(shè)備不一定都是主設(shè)備 ，故Ⅲ錯(cuò)誤；系統(tǒng)中肯定允許有多條 PCI總線，以此來提升計(jì)算機(jī)的效率 ，故Ⅳ正確。22．D。A：在統(tǒng)一編址方式下 ，訪問主存儲(chǔ)器和訪問 I/O設(shè)備是通過不同的地址碼 來區(qū)分的；在獨(dú)立編址方式下 ，訪問主存儲(chǔ)器和訪問 I/O 設(shè)備是通過不同的指令來區(qū)分的，所以A錯(cuò)誤。B：除主機(jī)外的硬件裝置統(tǒng)稱為外圍設(shè)備或外部設(shè)備 ，包括輸入、輸出設(shè)備和外存儲(chǔ)器 ，所以B錯(cuò)誤。C：中斷隱指令并不是一條真正的指令 ，因此不可能把它預(yù)先編入程序中 ，只能在響應(yīng)中斷時(shí)由硬件直接控制執(zhí)行 ，它就好像是隱藏于機(jī)器中的指令 ，只有在響應(yīng)中斷時(shí)被執(zhí)行 。中斷隱指令不在指令系統(tǒng)中 ，不屬于程序控制指令 ，所以C錯(cuò)誤。補(bǔ)充：在中斷周期中，由中斷隱指令自動(dòng)完成保護(hù)斷點(diǎn)、尋找中斷服務(wù)程序入口地址以及硬件關(guān)中斷的操作。D：為了防止在恢復(fù)現(xiàn)場(chǎng)過程中又出現(xiàn)新的中斷 ，在恢復(fù)現(xiàn)場(chǎng)前需要增加關(guān)中斷操作 ，所以D正確。提醒：請(qǐng)注意區(qū)分，保護(hù)現(xiàn)場(chǎng)前的關(guān)中斷由中斷隱指令完成 ，但是恢復(fù)現(xiàn)場(chǎng)前的關(guān)中斷是由中斷服務(wù)程序完成 。23．C。Ⅰ正確。在分時(shí)操作系統(tǒng)中 ，響應(yīng)時(shí)間跟時(shí)間片和用戶數(shù)成正比 。響應(yīng)時(shí)間：從提交第一個(gè)請(qǐng)求到產(chǎn)生第一個(gè)響應(yīng)所用時(shí)間。在RR算法中，用戶作業(yè)時(shí)間片結(jié)束后，就認(rèn)為產(chǎn)生了第一個(gè)響應(yīng)。Ⅱ錯(cuò)誤。操作系統(tǒng)具有主存的共享性 ，因此每個(gè)用戶擁有的主存空間大小是由用戶程序的大小決定的。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..Ⅲ正確。實(shí)時(shí)操作系統(tǒng)要求在安全的情況下對(duì)時(shí)間的要求較苛刻 ，為保證系統(tǒng)的工作時(shí)效 ，犧牲效率也是必然的 。Ⅳ正確。鐵路信號(hào)系統(tǒng)需要實(shí)時(shí)調(diào)度車輛 ，延時(shí)會(huì)出事故 ；門禁系統(tǒng)需要及時(shí)響應(yīng)用戶的進(jìn)入請(qǐng)求；股票交易系統(tǒng)需要當(dāng)前的實(shí)時(shí)行情 ，上述應(yīng)用均要求使用實(shí)時(shí)操作系統(tǒng) 。綜上所述，本題選C。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..24．D。在多線程操作系統(tǒng)中 ，通常一個(gè)進(jìn)程中包括多個(gè)線程 ，每個(gè)線程都是作為利用 CPU的基本單位，是花費(fèi)最小開銷的實(shí)體 。線程具有下述屬性 ：（1）輕型實(shí)體。線程中的實(shí)體基本上不擁有系統(tǒng)資源 ，只是有一點(diǎn)必不可少的 ，即能保證獨(dú)立運(yùn)行的資源 。它包含了一個(gè)線程 ID、一個(gè)程序計(jì)數(shù)器 、一個(gè)寄存器組和一個(gè)堆棧 。2）獨(dú)立調(diào)度和分派的基本單位。3）可并發(fā)執(zhí)行。4）共享進(jìn)程資源。在同一進(jìn)程中的各個(gè)線程，都可以共享該進(jìn)程所擁有的資源，包括共享代碼段、數(shù)據(jù)段以及其他的操作系統(tǒng)資源（如打開的文件）等。多線程最大的優(yōu)點(diǎn)就是并發(fā)執(zhí)行 。在4個(gè)服務(wù)中，只有鍵盤操作是無法并發(fā)執(zhí)行的 ，因?yàn)檎麄€(gè)系統(tǒng)只有一個(gè)鍵盤 ，而且鍵盤輸入是人的操作 ，速度比較慢，完全可以使用一個(gè)線程來處理整個(gè)系統(tǒng)的鍵盤操作 ，所以選擇 D。25．B。J1、J2和J3同時(shí)在0時(shí)刻到達(dá)，按短作業(yè)優(yōu)先算法，選擇J1和J2執(zhí)行，則J1和J2等待時(shí)間為0。又因?yàn)門1<T2，所以J1先于J2完成，即在T2時(shí)刻，釋放CPU，J3開始，則J3的等待時(shí)間為T1。然后J2完成，最后J3完成。J1周轉(zhuǎn)時(shí)間為 T1。J2周轉(zhuǎn)時(shí)間為 T2。J3周轉(zhuǎn)時(shí)間為 T1+T3。所以平均周轉(zhuǎn)時(shí)間為 （2T1+T2+T3）/3。知識(shí)點(diǎn)回顧：周轉(zhuǎn)時(shí)間=等待時(shí)間+運(yùn)行時(shí)間=結(jié)束時(shí)間-到達(dá)時(shí)間26．B。提醒：計(jì)數(shù)型信號(hào)量就是記錄型信號(hào)量 ，不要被這個(gè)搞混了 。Ⅰ正確。當(dāng)執(zhí)行V操作后，S.value≤0，說明了在執(zhí)行 V操作之前S.value<0（此時(shí)S.value 的絕對(duì)值就是阻塞隊(duì)列中進(jìn)程的個(gè)數(shù) ），所以阻塞隊(duì)列必有進(jìn)程在等到 ，所以需要喚醒一個(gè)阻塞隊(duì)列的進(jìn)程。Ⅱ錯(cuò)誤。由Ⅰ的分析可知，S.value ≤就會(huì)0喚醒。因?yàn)榭赡茉趫?zhí)行 V操作前，只有一個(gè)進(jìn)程在阻塞隊(duì)列，也就是說 S.value=-1，執(zhí)行V 操作后，喚醒該阻塞進(jìn)程 ，S.value=0。Ⅲ和Ⅳ錯(cuò)誤。S.value的值和就緒隊(duì)列中的進(jìn)程沒有此層關(guān)系 ，所以全錯(cuò)。綜上所述，本題選B。27．C。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..對(duì)于邏輯地址結(jié)構(gòu) ，因?yàn)?8 頁=23頁，所以表示頁號(hào)的地址有 3位，又因?yàn)槊宽撚?024B=210B，所以頁內(nèi)偏移地址有 10位。因此總共邏輯地址有 13位。對(duì)于物理地址結(jié)構(gòu) ，因?yàn)轫撁娴拇笮『臀锢韷K的大小是一樣的 ，所以每個(gè)物理塊也是1024B，而內(nèi)存至少有 32塊物理塊，所以內(nèi)存大小至少是 32×1024B=215B。因此物理地址至少要15位，不然無法訪問內(nèi)存的所有區(qū)域 。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..28．D。每頁1KB，默認(rèn)字長(zhǎng)為 1B，那么頁內(nèi)地址需要 10位，則剩下的6位為虛頁號(hào)。計(jì)算過程如表1-7所示。表1-7 十六進(jìn)制虛地址及物理地址十六進(jìn)制虛地址 0A5C 1A5C二進(jìn)制虛地址 000010100101 000110100101二進(jìn)制虛頁號(hào) 000010 000110二進(jìn)制物理頁號(hào) 000100 缺頁中斷二進(jìn)制頁內(nèi)地址 1001011100二進(jìn)制物理地址 000100100101十六進(jìn)制物理地址 125C29．B。Ⅰ正確。增大內(nèi)存可使每個(gè)程序得到更多的頁面 ，能減少缺頁率 ，因而減少換入和換出過程，可提高CPU利用率。Ⅱ錯(cuò)誤。因?yàn)橄到y(tǒng)實(shí)際已處于頻繁的換入和換出過程中 ，不是因?yàn)榇疟P交換區(qū)容量不夠 ，因此增大磁盤交換區(qū)的容量無用 。Ⅲ正確。因?yàn)閺慕o定的條件中磁盤交換區(qū)的利用率為 99.7%，說明系統(tǒng)現(xiàn)在已經(jīng)處于頻繁的換入和換出過程中 ，可減少主存中的程序 。Ⅳ錯(cuò)誤。系統(tǒng)處于頻繁的換入和換出過程中 ，再增加主存中的用戶進(jìn)程數(shù) ，只能導(dǎo)致系統(tǒng)的換入和換出更頻繁 ，使性能更差。Ⅴ錯(cuò)誤。因?yàn)橄到y(tǒng)現(xiàn)在處于頻繁的換入和換出過程中 ，即使采用更快的磁盤交換區(qū) ，其換入和換出頻率也不會(huì)改變 ，因此沒用。Ⅵ錯(cuò)誤。系統(tǒng)處于頻繁的換入和換出過程中 ，CPU處于空閑狀態(tài)，利用率不高，提高CPU的速度無濟(jì)于事 。綜上所述，本題選B。30．D。圖1-10所示為文件系統(tǒng)模型。可將該模型分為3個(gè)層次，其最底層是對(duì)象及其屬性；中間層是對(duì)對(duì)象進(jìn)行操縱和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。其中對(duì)對(duì)象操縱和管理的軟件集合這個(gè)層次 ，是文件系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實(shí)現(xiàn)的 ，其中包括：對(duì)文件存儲(chǔ)空間的管理 、對(duì)文件目錄的管理 、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對(duì)文件讀和寫的管理以及對(duì)文件的共享與保護(hù)等功能 。. 專業(yè)學(xué)習(xí)資料 .........所以A選項(xiàng)是錯(cuò)誤的。圖1-10文件系統(tǒng)模型在多級(jí)目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條唯一的路徑。在該路徑上從樹的根（即主目錄）開始，把全部目錄文件名與數(shù)據(jù)文件名依次地用“/連”接起來，即構(gòu)成該數(shù)據(jù)文件的路徑名。系統(tǒng)中的每個(gè)文件都有唯一的路徑名。所以B選項(xiàng)的說法是不準(zhǔn)確的。對(duì)文. 專業(yè)學(xué)習(xí)資料 ... . .. . ..件的訪問只需要通過路徑名即可 。對(duì)于C選項(xiàng)的描述，錯(cuò)在物理塊大小是不可以任意指定的 ，它必須和外存分配方式相符合 ，所以C選項(xiàng)錯(cuò)誤。D選項(xiàng)正確?；谖募到y(tǒng)的概念 ，可以把數(shù)據(jù)組成分為數(shù)據(jù)項(xiàng) 、記錄和文件 3級(jí)。記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合 ，用于描述一個(gè)對(duì)象在某方面的屬性 。記錄是文件存取的基本單位 ，數(shù)據(jù)項(xiàng)是文件可使用的最小單位 。31．A。在數(shù)據(jù)從控制器傳送至內(nèi)存的這段時(shí)間內(nèi) ，從磁頭下通過的扇區(qū)數(shù)為 2。當(dāng)數(shù)據(jù)從控制器傳送至內(nèi)存后 ，磁頭開始讀數(shù)據(jù)時(shí) ，剛好轉(zhuǎn)到目標(biāo)扇區(qū) 。所以總時(shí)間為總時(shí)間=初始尋找0扇區(qū)時(shí)間+讀扇區(qū)總時(shí)間 +將扇區(qū)數(shù)據(jù)送入內(nèi)存總時(shí)間 由題中條件可知，旋轉(zhuǎn)速度為：3000轉(zhuǎn)/分=50轉(zhuǎn)/秒，即20ms/轉(zhuǎn)。讀一個(gè)扇區(qū)需要時(shí)間 ：20/8ms=2.5ms讀一個(gè)扇區(qū)并將扇區(qū)數(shù)據(jù)送入內(nèi)存需要時(shí)間 ：2.5×3ms=7.5ms讀出一個(gè)磁道上的所有扇區(qū)需要時(shí)間 ：20/2ms+8 ×7.5ms=70ms=0.07s每磁道數(shù)據(jù)量為8×512B=4KB數(shù)據(jù)傳輸速度為4KB/0.07s=57.1KB/s所以依次讀出一個(gè)磁道上的所有扇區(qū)需要 0.07s，其數(shù)據(jù)傳輸速度為 57.1KB/s。32．A。單緩沖工作示意圖和時(shí)序圖如圖 1-11 所示。從圖中可以看出 ：數(shù)據(jù)由 I/O 控制器到緩沖區(qū)和數(shù)據(jù)由緩沖區(qū)到工作區(qū)必須串行操作 ；同樣，數(shù)據(jù)從緩沖區(qū)到工作區(qū)和 CPU從工作區(qū)中取出數(shù)據(jù)進(jìn)行處理也需串行進(jìn)行 ；但由于在順序訪問時(shí)可采用預(yù)先讀的方式 ，即CPU在處理一塊數(shù)據(jù)（從工作區(qū)取數(shù)據(jù) ）的同時(shí)可從磁盤輸入下一塊數(shù)據(jù) ，所以系統(tǒng)對(duì)一塊數(shù)據(jù)的處理時(shí)間為max(T,C)+M。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..圖1-11 單緩沖工作示意圖與時(shí)序圖雙緩沖的工作示意圖和時(shí)序圖如圖 1-12 所示。由此可見，數(shù)據(jù)由I/O控制器到雙緩沖和數(shù)據(jù)由雙緩沖區(qū)到工作區(qū)可以并行工作 ，因此，系統(tǒng)對(duì)一塊數(shù)據(jù)的處理時(shí)間為 max(T,M+C)。33．A。從計(jì)算機(jī)網(wǎng)絡(luò)組成的角度來看 ，典型的計(jì)算機(jī)網(wǎng)絡(luò)從邏輯功能上可以分為兩部分 ：資源子網(wǎng)和通信子網(wǎng) 。資源子網(wǎng)：由主計(jì)算機(jī)系統(tǒng) 、終端、終端控制器、聯(lián)網(wǎng)外部設(shè)備 、各種軟件資源與信息資源等組成。資源子網(wǎng)負(fù)責(zé)全網(wǎng)的數(shù)據(jù)處理業(yè)務(wù) ，負(fù)責(zé)向網(wǎng)絡(luò)用戶提供各種網(wǎng)絡(luò)資源與網(wǎng)絡(luò)服務(wù) 。通信子網(wǎng)（包括物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層）：由通信控制處理機(jī)、通信線路與其他通信設(shè)備組成，完成網(wǎng)絡(luò)數(shù)據(jù)傳輸、轉(zhuǎn)發(fā)等通信處理任務(wù)。. 專業(yè)學(xué)習(xí)資料 ... . .. . ... 專業(yè)學(xué)習(xí)資料 ... . .. . ..圖1-12 雙緩沖工作示意圖與時(shí)序圖綜上所述，網(wǎng)橋、交換機(jī)、路由器都屬于通信子網(wǎng) ，而只有計(jì)算機(jī)軟件屬于資源子網(wǎng) 。34．A。PCM代表PulseCodeModulation （脈沖編碼調(diào)制 ）。補(bǔ)充：PCM 通常用在電話系統(tǒng)中對(duì)模擬數(shù)據(jù)進(jìn)行采樣 。一般都把 PCM 采樣時(shí)間設(shè)置成125 s，125 s的采樣時(shí)間對(duì)應(yīng)于每秒 8000 次采樣。一個(gè)典型的電話通道是 4kHz，根據(jù)奈奎斯特定理 ，為獲取在一個(gè) 4kHz通道中的全部信息需要每秒 8000 次的采樣頻率。128=27，每個(gè)采樣表示 7 個(gè)二進(jìn)制位。8000×7bit/s=56000bit/s=56kbit/s 。35．B。發(fā)送窗口的后沿的變化情況只能有兩種 ：（1）原地不動(dòng)（沒有收到新的確認(rèn) ）。（2）向前移動(dòng)（收到了新的確認(rèn) ）。 發(fā)送窗口不可能向后移動(dòng) ，因?yàn)椴豢赡艹蜂N已收到的確認(rèn)幀 。36．B。流就是 Internet 上從特定主機(jī)的源站到特定的目的站的單播或組播數(shù)據(jù)分組 ，所經(jīng)過的路徑上的路由器都能保證指定的服務(wù)質(zhì)量 。頭部中的源地址 、目的地址和流標(biāo)號(hào)字段唯一地標(biāo)識(shí)了一個(gè)流。37．D。需要分兩種情況 ，分析如下：第一種：假設(shè)計(jì)算機(jī) A和計(jì)算機(jī) B在同一個(gè)局域網(wǎng)內(nèi) ，那么應(yīng)該由計(jì)算機(jī)B使用ARP響應(yīng)分組將計(jì)算機(jī) B的硬件地址告訴計(jì)算機(jī) A。第二種：假設(shè)計(jì)算機(jī) A和計(jì)算機(jī) B不在同一個(gè)局域網(wǎng)內(nèi) ，則應(yīng)該由連接本網(wǎng)絡(luò)的路由器使用ARP響應(yīng)分組將自己的硬件地址告訴計(jì)算機(jī) A。綜上所述，由誰通過 ARP響應(yīng)分組回應(yīng)是不確定的 。38．C。在該網(wǎng)絡(luò)上共有 50個(gè)路由器，因此每個(gè)路由器的路由表大小為 6×8×50bit=2400bit 。在基于距離-向量的路由選擇算法中 ，每個(gè)路由器都定期地與所有相鄰的路由器交換整個(gè)路由表 ，并以此更新自己的路由表項(xiàng) 。由于每個(gè)路由器每秒與自己的每個(gè)鄰接路由器交換 1 次路由表，一條鏈路連接兩個(gè)路由器 ，所以每秒在一條鏈路上交換的數(shù)據(jù)為 2×2400bit=4800bit ，即由于更新路由信息而耗費(fèi)的帶寬為 4800bit/s 。39．B。在慢啟動(dòng)和擁塞避免算法中，擁塞窗口初始值為1，窗口大小開始按指數(shù)增長(zhǎng)。當(dāng)擁塞窗口大于慢啟動(dòng)門限后，停止使用慢啟動(dòng)算法，改用擁塞避免算法。此時(shí)，慢啟動(dòng)的門限值初始. 專業(yè)學(xué)習(xí)資料 ... . .. . ..為8，當(dāng)擁塞窗口增大到 8時(shí)改用擁塞避免算法 ，窗口大小按線性增長(zhǎng) ，每次增長(zhǎng)1個(gè)報(bào)文段。當(dāng)增加到 12時(shí)，出現(xiàn)超時(shí)，重新設(shè)置門限值為 6（12的一半），擁塞窗口再重新設(shè)為 1，執(zhí)行慢啟動(dòng)算法，到門限值為 6時(shí)執(zhí)行擁塞避免算法 。按照上面的算法 ，擁塞窗口的變化為 1、2、. 專業(yè)學(xué)習(xí)資料 ... . .. . ..4、8、9、10、11、12、1、2、4、6、7、8、9L，從該序列可以看出 ，第12次傳輸時(shí)擁塞窗口大小為6。注意：在以上的序列中 ，6被加粗，原因是很多考生直接從 4增加到8，導(dǎo)致誤選D選項(xiàng)。原因是擁塞窗口的大小是與門限值有關(guān)的 ，在慢開始算法中不能直接變化為大于門限值 ，所以4 只能最多增加到 6，之后再執(zhí)行擁塞避免算法 。40．A。FTP使用兩條TCP連接完成文件傳輸 ，一條是控制連接 ，另一條是數(shù)據(jù)連接 ，所以C選項(xiàng)正確；在FTP中，控制連接在整個(gè)用戶會(huì)話期間一直打開著 ，而數(shù)據(jù)連接有可能為每次文件傳送請(qǐng)求重新打開一次 ，即數(shù)據(jù)連接是非持久的 ，而控制連接是持久的 ，所以 A選項(xiàng)錯(cuò)誤，B選項(xiàng)正確；D選項(xiàng)顯然正確。二、綜合應(yīng)用題41．【答案要點(diǎn)】首先解答此題需要很清楚地知道 B-樹的基本定義 ，這個(gè)就不再一一列舉了 ，參考教材即可。另外，B-樹插入和刪除的詳細(xì)過程也請(qǐng)參考教材 ，以下的講解只是大概地描述幾個(gè)較為關(guān)鍵的步驟。（1）插入33：第一步需要定位 ，33應(yīng)該被插入 35和41的那個(gè)葉子結(jié)點(diǎn) 。由于該葉子結(jié)點(diǎn)沒有了空位置 （怎么檢測(cè)是否有空位置 ？m階B-樹最多只能有 m-1 個(gè)關(guān)鍵字），所以需要進(jìn)行分裂操作 。插入后的情況應(yīng)該是 35、41、33，那么怎么分裂 ？首先需要取一個(gè)新結(jié)點(diǎn) ，把原結(jié)點(diǎn)上的關(guān)鍵字按照升序排列 ，即33、35、41。從中間位置（即 m/2 之處）把關(guān)鍵字（不包括中間位置的關(guān)鍵字 ）分成兩部分，左部分所含的關(guān)鍵字放在舊結(jié)點(diǎn)中 ，右邊所含的關(guān)鍵字 放在新結(jié)點(diǎn)中 ，中間位置的關(guān)鍵字連同新結(jié)點(diǎn)的存儲(chǔ)位置插入到雙親結(jié)點(diǎn)中 ，如圖 1-13所示。如果雙親結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過分支數(shù)減 1，則要再分裂，再往上插，直至這個(gè)過程傳到根結(jié)點(diǎn)為止。從以上步驟可以得出插入 33之后的B-樹，如圖1-14所示。圖1-13. 專業(yè)學(xué)習(xí)資料 ... . .. . ..圖1-14插入33后的B-樹可能疑問點(diǎn)：結(jié)點(diǎn)下面的小方塊都是什么？解析：小方塊就是葉子結(jié)點(diǎn)，因?yàn)槿~子結(jié)點(diǎn)本身不帶有信息，所以有些教材都不畫出來，但是葉子結(jié)點(diǎn)這一層是一定要計(jì)入樹的高度 。另外，葉子結(jié)點(diǎn)一般也被認(rèn)為外部結(jié)點(diǎn) （類似于折半查找判定樹的外部結(jié)點(diǎn) ）或是查找失敗的結(jié)點(diǎn) 。插入97：過程與上面的一樣 ，最終結(jié)果如圖 1-15所示。圖1-15插入33和97后的B-樹2）B-樹的刪除過程與插入過程類似，只是稍微復(fù)雜一些。因?yàn)橐箘h除后的結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)≥ m/2 -1，這就將涉及結(jié)點(diǎn)的 “合并”問題。刪除66：首先需要根據(jù) B-樹的查找算法找到關(guān)鍵字所在的結(jié)點(diǎn) ，然后在該結(jié)點(diǎn)上刪除關(guān)鍵字，具體詳細(xì)過程參考教材 。找到66 所在的結(jié)點(diǎn)之后 ，發(fā)現(xiàn)刪除之后關(guān)鍵字個(gè)數(shù)不滿足 ≥m/2 -1，所以需要像兄弟結(jié)點(diǎn)借 ，但是兄弟結(jié)點(diǎn)只有一個(gè)關(guān)鍵字 97，借不了。那么唯一的辦法就是把當(dāng)初和它們分裂出去的關(guān)鍵字找回來 ，即88。但是，88找回來之后（也就是雙親結(jié) 點(diǎn)），雙親結(jié)點(diǎn)又不滿足 ≥ m/2 -1，只有繼續(xù)找更早以前被分裂出去的 60，最后的結(jié)果如圖 1-16 所示。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..圖1-16 刪除66后的B-樹42．【答案要點(diǎn)】1）基本設(shè)計(jì)思想：算法的策略是從數(shù)組的第一個(gè)元素位置和最后一個(gè)元素位置向數(shù)組的中部進(jìn)行遍歷。因此我們可以定義兩個(gè)變量，將它們當(dāng)作下標(biāo)來遍歷數(shù)組，第一個(gè)下標(biāo)一開始指向數(shù)組第一個(gè)元素 ，它只向后移動(dòng) ，第二個(gè)下標(biāo)一開始指向數(shù)組最后一個(gè)元素 ，它只向前移動(dòng)。在兩個(gè)下標(biāo)相遇之前 ，第一個(gè)下標(biāo)總是位于第二個(gè)下標(biāo)的前面 。如果第一個(gè)下標(biāo)指向的元素是偶數(shù)而第二個(gè)下標(biāo)指向的元素是奇數(shù) ，我們就交換這兩個(gè)元素 。（2）算法實(shí)現(xiàn)如下 ：voidReorderOddEven(int{intleft=0;intright=n-1;inttemp;while(left<right){if(a[left]%2!=0){left++;continue;}if(a[right]%2==0){

a[],n)定義指向數(shù)組第一個(gè)元素的下標(biāo)變量定義指向數(shù)組最后一個(gè)元素的下標(biāo)變量元素交換的中間變量當(dāng)兩個(gè)下標(biāo)相遇后才結(jié)束循環(huán)如果left指向的元素是奇數(shù)，則left下標(biāo)向后移動(dòng)一位//如果right 指向的元素是偶數(shù)，則 right 下標(biāo)向左移動(dòng)一位right--;. 專業(yè)學(xué)習(xí)資料 ... . .. . ..continue;}交換元素temp=a[left];a[left]=a[right];a[right]=temp;交換完成后，兩邊的下標(biāo)各移動(dòng)一位left++;right--;}}（3）時(shí)間復(fù)雜度分析 ：整個(gè)算法過程相當(dāng)于把數(shù)組遍歷了一遍 ，所以時(shí)間復(fù)雜度為 O(n)。空間復(fù)雜度分析 ：算法中只需要使用 temp 這一個(gè)臨時(shí)變量 ，所以空間復(fù)雜度為一常數(shù) ，表示為O(1)。43．【答案要點(diǎn)】（1）對(duì)于時(shí)間局部性來說 ：在程序段A、B和C中，每個(gè)數(shù)組元素都只被訪問一次，所以都沒有時(shí)間局部性。對(duì)于空間局部性來說：程序段A訪問順序和存放順序一致 ，所以空間局部性好 。程序段B訪問順序和存放順序不一致 ，所以空間局部性不好 。程序段C雖然訪問順序和存放順序一致 ，但同一個(gè)主存塊有兩次訪問 ，所以空間局部性不好。（2）Cache的行數(shù)為 512B/32B=16 ；數(shù)組首地址為 00000C80H ，因?yàn)?0000C80H 正好是主存第1100100B（100）塊的起始地址 ，所以數(shù)組從主存第 100 塊開始存放，一個(gè)數(shù)組元素占 4×4B=16B，每?jī)蓚€(gè)數(shù)組元素占用一個(gè)主存塊 。8×8的數(shù)組共占用 32 個(gè)主存塊，正好是Cache 數(shù)據(jù)區(qū)大小的兩倍 。因?yàn)?00mod16=4 ，所以主存第 100 塊映射到的 Cache 行號(hào)為4。主存中 的數(shù)組元素與 Cache 行的映射關(guān)系如圖 1-19所示。（3）對(duì)于程序段 A：每?jī)蓚€(gè)數(shù)組元素 （共涉及8次寫操作）裝入到一個(gè) Cache行中，總是第一次訪問時(shí)未命中 ，后面7次都命中，所以總的寫Cache操作次數(shù)為 64×4=256次，寫Cache不命中次數(shù)為 256×1/8=32 次，因而寫Cache缺失率為12.5%。對(duì)于程序段 B：每?jī)蓚€(gè)數(shù)組元素 （共涉及8次寫操作）裝入到一個(gè) Cache行中，但總是只有一個(gè)數(shù)組元素 （涉及4次寫操作）在被淘汰之前被訪問 ，并且總是第一次不命中 ，后面3次. 專業(yè)學(xué)習(xí)資料 ... . .. . ..命中，所以寫Cache不命中次數(shù)為 256×1/4=64 次，因而寫Cache缺失率為25%。. 專業(yè)學(xué)習(xí)資料 ... . .. . ..對(duì)于程序段 C：第一個(gè)循環(huán)共 64次訪問，每次裝入兩個(gè)數(shù)組元素 ，第一次不命中 ，第二次命中；第二個(gè)循環(huán)共訪問 64×3次，每?jī)蓚€(gè)數(shù)組元素 （共涉及 6次寫操作）裝入到一個(gè)Cache行中，并且總是第一次不命中，后面5次命中，所以總的寫Cache不命中次數(shù)為32+(3×64)×1/6=64次，因而寫Cache缺失率為25%。圖1-19 主存中的數(shù)組元素與 Cache行的映射關(guān)系44．【答案要點(diǎn)】（1）由于該微型計(jì)算機(jī)的尋址范圍為 64KB，所以地址線有 16根。CPU外接了8KB的RAM芯片，說明片內(nèi)的地址線為 13條，也就是說多出的 3根地址線恰好可以被用來對(duì) 8片RAM芯片進(jìn)行片選。片選電路邏輯圖如圖 1-20 所示。（2）第0片地址范圍（片選信號(hào)為 000）：0000000000000～0000H～1FFFH）第1片地址范圍（片選信號(hào)為 001）：0010000000000000 ～2000H～3FFFH）第2片地址范圍（片選信號(hào)為010）：第3片地址范圍（片選信號(hào)為0100000000000000～011）：01011111111111110110000000000000～（4000H～5FFFH）0111111111111111. 專業(yè)學(xué)習(xí)資料 .........（6000H～7FFFH）圖1-20片選電路邏輯圖第4片地址范圍（片選信號(hào)為100）：. 專業(yè)學(xué)習(xí)資料 ... . .. . ..1000000000000000 ～8000H～9FFFH）第5片地址范圍（片選信號(hào)為101）：1010000000000000 ～A000H～BFFFH）第6片地址范圍（片選信號(hào)為110）：110 0000000000000～C000H～DFFFH）第7片地址范圍（片選信號(hào)為111）：111 0000000000000～E000H～FFFFH）3）說明譯碼器有誤，因?yàn)槠x信號(hào)是低電平有效，所以第3片的片選信號(hào)始終為低電平，即無論選哪片RAM，與此同時(shí)第3片都會(huì)同時(shí)被選中。4）因?yàn)槠x信號(hào)是低電平有效，說明000端輸出始終為高電平，所以導(dǎo)致以0000H為起始地址的存儲(chǔ)芯片不能讀寫。5）第1、3、5、7片RAM的片選信號(hào)分別為：001、011、101、111，唯一的共性就是地址線A13都為1，說明地址線 A13始終為0導(dǎo)致故障。45．【答案要點(diǎn)】本題還是一個(gè)生產(chǎn)者 -消費(fèi)者的變型 ，與2009 年真題不同之處在于 ，2009 年真題是一個(gè)生產(chǎn)者，對(duì)應(yīng)兩個(gè)消費(fèi)者 ；本題是生產(chǎn)者 -消費(fèi)生產(chǎn)者-消費(fèi)者類型，其實(shí)質(zhì)是兩個(gè)生產(chǎn)者 -消費(fèi)者關(guān)系。R是生產(chǎn)者，M 是對(duì)應(yīng)消費(fèi)者，同時(shí)M 也充當(dāng)生產(chǎn)者，P是對(duì)應(yīng)的消費(fèi)者 。把這些進(jìn)程間的關(guān)系理清楚 ，是解題的基礎(chǔ) 。本題的緩沖區(qū) B可描述為charbufferB[n];（1）緩沖區(qū)是一互斥資源 ，因此設(shè)互斥信號(hào)量 mutex。（2）上述進(jìn)程的同步問題 ，需設(shè)置 3個(gè)信號(hào)量，其中 empty 對(duì)應(yīng)空閑的緩沖單元 ，初值為n；full_1 對(duì)應(yīng)緩沖區(qū)中待 M 處理的字符，初值為0；full_2 對(duì)應(yīng)緩沖區(qū)中已經(jīng)處理過而待. 專業(yè)學(xué)習(xí)資料 ... . .. . ..打印 輸出的字符，初值為 0。另外，還需定義 3個(gè)整型變量 in、out_1、out_2，分別用來指示下一 個(gè)可存放字符的緩沖單元 、下一個(gè)待 M 處理的緩沖單元及下一個(gè)待打印輸出的緩沖單元，它們的初值均為 0。過程如下：charbufferB[n]//緩沖區(qū)字符數(shù)組semaphoreempty=n;//空閑緩沖單元數(shù)semaphorefull_1=0;//待M處理的字符數(shù)semaphorefull_2=0;//待P取出打印字符數(shù)//semaphoremutex=1;緩沖區(qū)的互斥訪問信號(hào)量//指示可存放字符的緩沖單元intin=0;//指示下一個(gè)待M處理的緩沖單元intout_1=0;. 專業(yè)學(xué)習(xí)資料 ... . .. . ..int out_2=0; //指示下一個(gè)待 P取出打印的緩沖單元R(){charch;while(1){從輸入設(shè)備讀取一個(gè)字符到 ch中;P(empty); //檢查緩沖區(qū)是否有可以存放新讀入字符的緩沖單元P(mutex); //申請(qǐng)?jiān)L問緩沖區(qū)bufferB[in]=ch; //存放新讀入字符的緩沖單元V(mutex); //釋放緩沖區(qū)V(full_1); //待M處理的字符數(shù)增 1in=(in+1)%n; //in指針后移，遇末循環(huán)到 0單元}}M() //讀者可參照 R()自行寫出注釋{while(1){P(full_1);P(mutex);if(bufferB[out_1]=='')buffer[o