考研計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合-7-1

考研計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合-7-1（總分：139.96,做題時(shí)間：90分鐘）一、{{B}}單項(xiàng)選擇題{{/B}}（總題數(shù):40,分?jǐn)?shù):80.00）.下列說(shuō)法中，正確的是。I.假設(shè)某有序表的長(zhǎng)度為n,則可以在1?（n+1）的位置上插入元素.在單鏈表中，無(wú)論是插入還是刪除操作，都必須找到其前驅(qū)結(jié)點(diǎn).刪除雙鏈表的中間某個(gè)結(jié)點(diǎn)時(shí)，只需修改兩個(gè)指針域.將兩個(gè)各有n和m個(gè)元素的有序表（遞增）歸并成一個(gè)有序表，仍保持其遞增有序，則最少的比較次數(shù)是m+n-1。A.僅i、n、mB.i、n、m、ivc.僅n、md.僅i、m、v（分?jǐn)?shù)：2.00）V解析：［解析］I：有序表插入的時(shí)候是不能指定位置的，因?yàn)檫@樣可能使得插入后的表不再是有序表。正確的插入思想是：先通過(guò)元素比較找到插入的位置，再在該位置上插入，故I錯(cuò)誤。II：從單鏈表插入和刪除的語(yǔ)句描述中可以看出，無(wú)論是插入還是刪除操作，都必須找到其前驅(qū)結(jié)點(diǎn)，故I正確。m：刪除雙鏈表中間某個(gè)結(jié)點(diǎn)時(shí)，需要修改前后兩個(gè)結(jié)點(diǎn)的各一個(gè)指針域，共計(jì)兩個(gè)指針域，故m正確。V：當(dāng)一個(gè)較短的有序表中所有元素均小于另一個(gè)較長(zhǎng)的有序表中所有的元素，所需比較次數(shù)最少。假如一個(gè)有序表為1、3、4,另一個(gè)有序表為5、6、7、8、12,這樣只需比較3次即可，故答案應(yīng)該是n和m中較小者，即min（n,m）,故V錯(cuò)誤。2.下列關(guān)于棧的說(shuō)法中，正確的是。I.若進(jìn)棧順序?yàn)閍、b、c,則通過(guò)出棧操作可能得到5個(gè)a、b、c的不同排列II?鏈?zhǔn)綏５臈ｍ斨羔樢欢ㄖ赶驐５逆溛瞞.兩個(gè)棧共享一個(gè)向量空間的好處是減少了存取時(shí)間A.僅IB.僅I、IIC.僅Id.僅n、m（分?jǐn)?shù)：2.00）V解析：［解析］I：該選項(xiàng)旨在讓考生知道一個(gè)公式。對(duì)于n個(gè)不同元素進(jìn)棧，出棧序列的個(gè)數(shù)為［*］可以馬上得出，當(dāng)n=3時(shí)，出棧序列個(gè)數(shù)為［*］故I正確。II：鏈?zhǔn)綏Ｒ话悴捎脝捂湵?，棧頂指針即為鏈頭指針。進(jìn)棧和出棧均在鏈頭進(jìn)行，每次都要修改棧項(xiàng)指針，鏈空即?？?top==NULL),故H錯(cuò)誤。III：由于棧中數(shù)據(jù)的操作只有入棧和出棧，且時(shí)間復(fù)雜度均為0(1),因此并沒(méi)有減少存取時(shí)間，故I錯(cuò)誤。兩個(gè)棧共享一個(gè)數(shù)組A［0...MaxSize-1］的空間，從而構(gòu)成共享?xiàng)?。?shù)組A的兩端是固定的，而棧底也是固定的，為此將下標(biāo)為0的一端作為棧1的棧底，其棧頂指針為topi,將下標(biāo)為MaxSize-1的一端作為棧2的棧底，其棧頂指針為top2,如圖所示。［*］棧1的四要素如下：①?？諚l件：top1==-1。②棧滿條件：top1==top2-1。③元素x進(jìn)棧:top1++；將元素x插入A［top1］處。④出棧元素：彈出A［top1］元素;top1--。棧2的四要素如下：①棧空條件：top2==MaxSize。②棧滿條件：top2==top1+1。③元素x進(jìn)棧：top2--；將元素x插入A［top2］處。④出棧元素：彈出A［top2］元素；top2++。注：以上都默認(rèn)指針指向當(dāng)前元素的下一個(gè)位置。3.若將n階上三角矩陣A按照列優(yōu)先順序存放在一維數(shù)組B［0,1,…，{nX(n+1)/2}-1］中，第一個(gè)非零元素a(1,1)存于B［0］中，則存放到B［k］中的非零元素a(i,j)(1WiWn,1WjWn)的下標(biāo)i、j與k的對(duì)應(yīng)關(guān)系是。A.k=iX(i+1)/2+jB.k=iX(i-1)/2+j-1C.k=jX(j+1)/2+iD.k=jX(j-1)/2+i-1(分?jǐn)?shù)：2.00)V解析：［解析］對(duì)于元素a(i,j)而言，前面有j-1歹U，第1列到第j-1列的元素個(gè)數(shù)分別為1?j-1個(gè)，由等差數(shù)列求和公式可算得一共有j*(j-1)/2個(gè)元素，故k=jX(j-1)/2+i-1(注意B數(shù)組是從0開始存元素，因此要減去1)。4.已知一棵二叉樹的先序、中序、后序的部分序列如下，其中有些位置沒(méi)有給出其值，則原二叉樹的中序遍歷序列為。先序：A_CDEF_H_J中序：C_EDA_GFI后序：C__BHGJI__A.CBEDAHGFIJB.CHEDABGFIJC.CBEDAJGFIHD.CJEDAHGFIB(分?jǐn)?shù)：2.00)V解析：［解析］對(duì)于一棵二叉樹(包括子樹)，它的遍歷序列對(duì)應(yīng)的結(jié)構(gòu)應(yīng)該是：先序遍歷：|根|左子樹|右子樹I,中序遍歷：|左子樹|根|右子樹1,后序遍歷：|左子樹|右子樹|根|,由題目中給出的先序序列的第一個(gè)結(jié)點(diǎn)我們找到樹的根A,然后在中序序列中找到A,并以A為分界將中序序列劃分為|C_ED|A|_GFI_1,所以C_ED為左子樹，_GFI_為右子樹，再對(duì)應(yīng)到后序遍歷序列上，這里左子樹結(jié)點(diǎn)的個(gè)數(shù)等于中序遍歷序列中左子樹結(jié)點(diǎn)的個(gè)數(shù)，因此C__B為左子樹，HGJI_為右子樹，這樣把中序序列和后續(xù)序列中的左右子樹一對(duì)比，則C{{U}}B{{/U}}ED為左子樹，F(xiàn){{U}}G{{/U}}H{{U}}I{{/U}}J為右子樹。答案選A。5.設(shè)某赫夫曼樹的高度為5,若已對(duì)兩個(gè)字符編碼為1和01,則最多還可以對(duì)個(gè)字符編碼。TOC\o"1-5"\h\zA.3B.4C.5D.6（分?jǐn)?shù)：2.00）V解析：［解析］首先，赫夫曼編碼遵循的原則為：一個(gè)編碼不能是任何其他編碼的前綴。比如1和10就不行，因?yàn)?是10的前綴。既然1和01已經(jīng)使用了，所以1和01開頭的碼字不能再使用。又由于赫夫曼樹的高度為5,故赫夫曼編碼的長(zhǎng)度不能超過(guò)4,只剩下0000、0001、0010、0011等4種編碼（這種編碼方式可得到最多），故選B選項(xiàng)。6.下列說(shuō)法中，正確的是。I.在含有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為n2-2e.若鄰接表中有奇數(shù)個(gè)邊表結(jié)點(diǎn)，則該圖一定是有向圖.對(duì)于采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷算法類似于二叉樹的中序遍歷.使用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先遍歷算法，則每個(gè)頂點(diǎn)進(jìn)隊(duì)列的次數(shù)可能大于1a.僅i、mb.僅n、m、ivC.僅I、II、IVD.僅I、II（分?jǐn)?shù)：2.00）V解析：［解析］I：總結(jié)如下：①對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣大小是m。②在含有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩陣中，非零元素的個(gè)數(shù)為2e。③在含有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為m-2e。④在含有n個(gè)頂點(diǎn)e條邊的有向圖的鄰接矩陣中，非零元素的個(gè)數(shù)為e。⑤在含有n個(gè)頂點(diǎn)e條邊的有向圖的鄰接矩陣中，零元素的個(gè)數(shù)為m-e。根據(jù)⑧，故I正確。II：無(wú)向圖采用鄰接表表示時(shí)，每條邊存儲(chǔ)兩次，所以其邊表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，故邊表結(jié)點(diǎn)為奇數(shù)只能是有向圖，故I正確。I：深度優(yōu)先遍歷算法是先訪問(wèn)一個(gè)頂點(diǎn)v,然后是離開頂點(diǎn)越遠(yuǎn)越優(yōu)先訪問(wèn)，即相當(dāng)于二叉樹的先序遍歷，故m錯(cuò)誤。V：采用廣度優(yōu)先遍歷算法遍歷一個(gè)圖時(shí)，每個(gè)頂點(diǎn)僅遍歷一次，所以最多只能進(jìn)隊(duì)1次，故V錯(cuò)誤。7.下列關(guān)于生成樹的說(shuō)法中，正確的是。A.最小生成樹是指權(quán)值之和為最小的生成樹，且唯一B.某圖的廣度優(yōu)先生成樹的高度一定大于等于深度優(yōu)先生成樹的高度C.Prime算法和Kruskual算法構(gòu)造的最小生成樹一定一樣D.Prime算法適用于求邊稠密的圖的最小生成樹(分?jǐn)?shù)：2.00)V解析：［解析］A：最小生成樹是指權(quán)值之和為最小的生成樹，但是不唯一，故A選項(xiàng)錯(cuò)誤。B：由廣度優(yōu)先遍歷和深度優(yōu)先遍歷算法可知，深度優(yōu)先算法構(gòu)造的生成樹的樹高大于等于廣度優(yōu)先算法構(gòu)造的生成樹的樹高，故B選項(xiàng)錯(cuò)誤。C：當(dāng)最小生成樹不唯一時(shí)，這兩種算法構(gòu)造的最小生成樹可能相同，也可能不同，故C選項(xiàng)錯(cuò)誤。D：Prime算法的時(shí)間復(fù)雜度為O(m),適合稠密圖；Kruskual算法的時(shí)間復(fù)雜度為O(eloge),適合稀疏圖，2故D選項(xiàng)正確。8.下列關(guān)于m階B+樹的說(shuō)法中，正確的是。I.具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)至少含有n+l棵子樹所有葉子結(jié)點(diǎn)包含全部關(guān)鍵字B+樹支持隨機(jī)索引B+樹可用于文件的索引結(jié)構(gòu)a.僅m、ivb.僅n、ivc.僅i、m、ivD.僅I、II、IV(分?jǐn)?shù)：2.00)V解析：［解析］一棵m階B+樹滿足下列條件：①每個(gè)分支結(jié)點(diǎn)至多有m棵子樹。②根結(jié)點(diǎn)或者沒(méi)有子樹，或者至少有兩棵子樹。③除根結(jié)點(diǎn)外，其他每個(gè)分支結(jié)點(diǎn)至少有［*］棵子樹。④具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有n棵子樹。⑤所有葉子結(jié)點(diǎn)包含全部關(guān)鍵字及指向相應(yīng)記錄的指針，而且葉子結(jié)點(diǎn)按關(guān)鍵字的大小順序鏈接。⑥所有分支結(jié)點(diǎn)中僅包含它的各個(gè)子結(jié)點(diǎn)中最大關(guān)鍵字及指向子結(jié)點(diǎn)的指針。⑦B+樹中，所有非終端結(jié)點(diǎn)可以看成是索引部分，故可用于文件的索引結(jié)構(gòu)。由于B+樹為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，所以不支持隨機(jī)檢索。綜上所述，可知n、iv正確，i、m錯(cuò)誤，故選B選項(xiàng)。9.利用逐點(diǎn)插入建立序列(50,72,43,85,75,20,35,45,65,30)對(duì)應(yīng)的二叉排序樹以后，要查找元素30要進(jìn)行次元素間的比較。TOC\o"1-5"\h\zA.4B.5C.6D.7(分?jǐn)?shù)：2.00)V

C.D.解析：［解析］由題可以建立出如圖所示的一棵二叉排序樹。［*］查找元素30一次經(jīng)過(guò)比較的元素為50,43,20，35,30，共有5次元素間的比較，因此本題選B選項(xiàng)。10.用直接插入排序?qū)ο旅?個(gè)序列進(jìn)行遞增排序，元素比較次數(shù)最少的是。A.94,32,40，90，80，46,21，69B.32，40，21，46,69，94，90，80C.21，32，46，40，80，69，90，94D.90，69，80，46，21，32，94，40A.94,32,40，90，80，46,21，69B.32，40，21，46,69，94，90，80C.21，32，46，40，80，69，90，94D.90，69，80，46，21，32，94，40（分?jǐn)?shù)：2.00）V解析：［解析］對(duì)于直接插入排序，原始序列越接近有序，則比較次數(shù)越少，觀察序列，C選項(xiàng)最接近有序。說(shuō)明：本題目測(cè)即可，如果要嚴(yán)格來(lái)比較，則可用線性代數(shù)中求逆序數(shù)的方法，序列逆序數(shù)越小則越接近有序。對(duì)于序列中某個(gè)元素a,其逆序數(shù)為序列中a之后比a小的元素的個(gè)數(shù)，整個(gè)序列的逆序數(shù)為所有元素逆序數(shù)之和。對(duì)于A,各元素逆序數(shù)為：94:7；32:1；40:1；90:4；80:3；46:1；21:0；69:0。因此序列A的逆序數(shù)為：7+1+1+4+3+1+0+0=17。對(duì)于B,各元素逆序數(shù)為:32:1；40:1；21:0；46:0；69:0；94:2；90:1；80:0。因此序列A的逆序數(shù)為：1+l+0+0+0+2+1+0=5。對(duì)于C,各元素逆序數(shù)為：21:0；32:0；46:1；40:0；80:1；69:0；90:0；94:0。因此序列A的逆序數(shù)為：0+0+1+0+1+0+0+0=2。對(duì)于D,各元素逆序數(shù)為：90:6；69:4；80:4；46:3；21:0；32:0；94:0；40:0。因此序列A的逆序數(shù)為：6+4+4+3+0+0+0+0=17?？梢钥闯鯟選項(xiàng)逆序數(shù)最小，即C選項(xiàng)最接近有序，所需比較次數(shù)最少。11.在外部排序算法中，最佳歸并樹主要的作用是。A.產(chǎn)生初始?xì)w并段B.完成歸并排序C.對(duì)歸并排序進(jìn)行優(yōu)化D.增大歸并路樹（分?jǐn)?shù)：2.00）V解析：［解析］A：產(chǎn)生初始?xì)w并段的工作應(yīng)該由置換-選擇排序完成，故A選項(xiàng)錯(cuò)誤。設(shè)輸入的關(guān)鍵字滿足匕〉人〉…〉kn,緩沖區(qū)大小為m,用置換-選擇排序方法可產(chǎn)生困個(gè)初始?xì)w并段。B：因?yàn)樽罴褮w并樹是針對(duì)排序之后1的初始?xì)w并段操作，所以歸并排序不可能由最佳歸并樹完成，故B選項(xiàng)錯(cuò)誤。C：最佳歸并樹仿造赫夫曼樹的構(gòu)造過(guò)程，以初始?xì)w并段的長(zhǎng)度為權(quán)值，構(gòu)造具有最小帶權(quán)路徑長(zhǎng)度的赫夫曼樹，可以有效地減少歸并過(guò)程中的讀寫記錄數(shù)，以加快外部排序的速度，故C選項(xiàng)正確。D：增大歸并路數(shù)應(yīng)該是由敗者樹來(lái)完成的，故D選項(xiàng)錯(cuò)誤。12.下列說(shuō)法中，錯(cuò)誤的是。I.時(shí)鐘頻率和CPI成反比關(guān)系II.數(shù)據(jù)字長(zhǎng)等于MDR的位數(shù)A主機(jī)的CPU主頻高于B主機(jī)的CPU主頻，則前者運(yùn)算能力將會(huì)高于后者A.僅I、IIb.僅n、mc.僅i、mD.i、n、m(分?jǐn)?shù)：2.00)A.V解析：［解析］I：時(shí)鐘頻率和CPI并無(wú)關(guān)系。時(shí)鐘頻率的提高僅僅是將時(shí)鐘周期縮短，并沒(méi)有改變執(zhí)行一條指令所需要的時(shí)鐘周期數(shù)，故I錯(cuò)誤。II：一般來(lái)講，M=DR的位數(shù)和存儲(chǔ)字長(zhǎng)相等，而數(shù)據(jù)字長(zhǎng)是一次存取數(shù)據(jù)的長(zhǎng)度，可以和M=DR不相等，故I錯(cuò)誤。I：CPU的主頻是表示在CPU內(nèi)數(shù)字脈沖信號(hào)震蕩的次數(shù)，是衡量CPU運(yùn)算速度的重要參數(shù)，但不是唯一的參數(shù)。故不能直接根據(jù)主頻來(lái)比較運(yùn)算能力，故m錯(cuò)誤。13.假定采用IEEE754單精度浮點(diǎn)數(shù)格式表示一個(gè)數(shù)為45100000H,則該數(shù)的值是。A.(+1.125)X210B.(+1.125)X2iiC.(+0.125)X2iiD.(+O.125)X2i0(分?jǐn)?shù)：2.00)V解析：［解析］45i00000H的二進(jìn)制數(shù)為0i000i0i000i00000000000000000000,第i位為符號(hào)位，表示正數(shù)，隨后8位i000i0i0為用移碼表示的階碼，減去i27得到十進(jìn)制數(shù)ii,而IEEE754中單精度數(shù)在階碼不為0時(shí)隱含i,所以尾數(shù)為(i.00i0)2=i.i25。i4.一個(gè)8位的二進(jìn)制整數(shù)，若采用補(bǔ)碼表示，且由3個(gè)“1”和5個(gè)“0”組成，則最小值為。A.-i27B.-32C.-125D.-3(分?jǐn)?shù)：2.00)A.Vd.解析：［解析］8位補(bǔ)碼最小時(shí)必為負(fù)數(shù)，所以第一位（符號(hào)位）必須為1。而負(fù)數(shù)的數(shù)值位絕對(duì)值越大，則此負(fù)數(shù)越小。又負(fù)數(shù)的補(bǔ)碼表示的高位0相當(dāng)于原碼表示的1，故當(dāng)剩下的2個(gè)“1”在最低位，5個(gè)“0”在數(shù)值位的最高位時(shí)此負(fù)數(shù)最小。該負(fù)數(shù)的補(bǔ)碼為10000011，則原碼為11111101，轉(zhuǎn)換成十進(jìn)制為-125。15.一臺(tái)8位微機(jī)的地址總線為16條，其RAM存儲(chǔ)器容量為32KB，首地址為4000H，且地址是連續(xù)的，可用的最高地址為。A.BFFFHB.CFFFHC.DFFFHD.EFFFH（分?jǐn)?shù)：2.00）V解析：［解析］32KB存儲(chǔ)空間共占用15條地址線，若32KB的存儲(chǔ)地址起始單元為0000H，其范圍應(yīng)為0000?7FFFH,但現(xiàn)在的首地址為4000H，即首地址后移了，因此最高地址也應(yīng)該相應(yīng)后移。故最高地址為4000H+7FFFH=BFFFH。32KB的存儲(chǔ)空間是連續(xù)的，由于首地址發(fā)生變化，末地址也會(huì)跟著發(fā)生變化。16.有效容量為128KB的Cache,每塊16B,8路組相聯(lián)。字節(jié)地址為1234567H的單元調(diào)入該Cache,其Tag應(yīng)為。A.1234HB.2468HC.048DHD.12345H（分?jǐn)?shù)：2.00）V解析：［解析］因?yàn)閴K的大小為16B,所以塊內(nèi)地址字段為4位；又因?yàn)镃ache容量為128KB,8路組相聯(lián)，所以可以分為1024組（128KB/（8x16B）=1024）,對(duì)應(yīng)的組號(hào)字段10位；剩下為標(biāo)記字段。1234567H=0001001000110100010101100111,標(biāo)記字段為高14位，00010010001101=048DH,故選C選項(xiàng)。17.在單發(fā)射、按序流動(dòng)的普通流水線中，可能出現(xiàn)下列數(shù)據(jù)相關(guān)問(wèn)題。I.寫后讀相關(guān)RAWII.讀后寫相關(guān)WARIII.寫后寫相關(guān)WAWA.僅IB.僅I、IIC.僅Id.僅n、m（分?jǐn)?shù)：2.00）A.VB.C.D.解析：［解析］指令取操作數(shù)的動(dòng)作一定在寫回結(jié)果之前，故在按序流動(dòng)的單發(fā)射（普通標(biāo)量）普通流水線中，先進(jìn)入流水線的指令的取操作數(shù)和寫回結(jié)果的動(dòng)作一定位于后續(xù)指令寫回結(jié)果的動(dòng)作之前，故不可能出現(xiàn)WAR和WAW。唯一可能出現(xiàn)的數(shù)據(jù)相關(guān)問(wèn)題是后續(xù)指令在前一指令寫回結(jié)果之前讀相關(guān)的操作數(shù)，即RAW。18.在按字節(jié)編址的計(jì)算機(jī)中，一條指令長(zhǎng)16位，當(dāng)前分支轉(zhuǎn)移指令（采用相對(duì)尋址）地址為3000，指令地址的偏移量為-5,當(dāng)執(zhí)行完此轉(zhuǎn)移指令后，PC的值為。A.2996B.2997C.3001D.3002（分?jǐn)?shù)：2.00）V解析：［解析］首先給出解答步驟，當(dāng)前指令地址為3000,取完這條指令后，PC的值增加一個(gè)指令字長(zhǎng)度，即3002,加上偏移量-5,所以執(zhí)行完這條指令后，目標(biāo)地址為2997,然后將這個(gè)值覆蓋到PC當(dāng)中。19.以下給出的事件中，無(wú)須異常處理程序進(jìn)行中斷處理的是。A.缺頁(yè)故障B.訪問(wèn)Cache缺失C.地址越界D.除數(shù)為0（分?jǐn)?shù)：2.00）V解析：［解析］缺頁(yè)會(huì)導(dǎo)致缺頁(yè)中斷，缺頁(yè)中斷就是要訪問(wèn)的頁(yè)不在主存，現(xiàn)行程序無(wú)法往下走，需要操作系統(tǒng)采用缺頁(yè)處理程序?qū)⑵湔{(diào)入主存后再進(jìn)行訪問(wèn)；地址越界就是在采取地址訪問(wèn)時(shí)，由于不注意，你訪問(wèn)的地址超過(guò)了所允許訪問(wèn)的地址空間，這種操作肯定會(huì)導(dǎo)致結(jié)果錯(cuò)誤，所以是非法操作，產(chǎn)生異常；除數(shù)為0這是不合法的，因此要終止現(xiàn)行程序，產(chǎn)生異常;而訪問(wèn)Cache缺失僅僅是說(shuō)要訪問(wèn)的內(nèi)容不在Cache而已，但程序至少還可以繼續(xù)進(jìn)行下去（比如程序可以到主存中去找需要的內(nèi)容）。所以答案為B。20.假定一臺(tái)計(jì)算機(jī)的顯示存儲(chǔ)器用DRAM芯片實(shí)現(xiàn)，若要求顯示分辨率為1600X1200,顏色深度為24位，幀頻為85Hz,顯存總帶寬的50%用來(lái)刷新屏幕，則需要的顯存總帶寬至少約為。A.245Mbit/sB.979Mbit/sC.1958Mbit/sD.7834Mbit/s（分?jǐn)?shù)：2.00）A.V解析：［解析］首先一幀畫面的大小為1600X1200X24bit,又因?yàn)閹l為85Hz,即每秒要刷新畫面85次，因此每秒需要更新的容量為46080000bitX85=3916800000bit,占顯存總帶寬的50%,顯存的帶寬至少約為3916.8Mbit/sX2=7834Mbit/so21.總線寬度只與下列選項(xiàng)有關(guān)。I.控制線根數(shù)II.地址線根數(shù)III.數(shù)據(jù)線根數(shù)A.僅Ib.僅n、mc.僅mD.i、n、m（分?jǐn)?shù)：2.00）V解析：［解析］總線寬度又稱為總線位寬，它是總線上能夠同時(shí)傳輸?shù)臄?shù)據(jù)位數(shù)，通常是指數(shù)據(jù)總線的根數(shù)。22.在主機(jī)和外設(shè)的信息傳送中，沒(méi)有使用程序控制方式。A.程序查詢方式B.程序中斷方式C.DMA方式D.通道方式（分?jǐn)?shù)：2.00）V解析：［解析］程序查詢方式和程序中斷方式顯然是需要程序的干預(yù)，而通道方式也是要編制通道程序來(lái)控制，只有DMA方式是靠硬件電路實(shí)現(xiàn)的。23.下列關(guān)于操作系統(tǒng)結(jié)構(gòu)說(shuō)法中，正確的是oI.當(dāng)前廣泛使用的WindowsXP操作系統(tǒng)，采用的是分層式OS結(jié)構(gòu)II.模塊化的OS結(jié)構(gòu)設(shè)計(jì)的基本原則是：每一層都僅使用其底層所提供的功能和服務(wù)，這樣使系統(tǒng)的調(diào)試和驗(yàn)證都變得容易m.由于微內(nèi)核結(jié)構(gòu)能有效支持多處理機(jī)運(yùn)行，故非常合適于分布式系統(tǒng)環(huán)境IV.采用微內(nèi)核結(jié)構(gòu)設(shè)計(jì)和實(shí)現(xiàn)操作系統(tǒng)具有諸多好處，如添加系統(tǒng)服務(wù)時(shí)，不必修改內(nèi)核、使系統(tǒng)更高效等A.僅I、IIb.僅i、mc.僅md.僅m、iv(分?jǐn)?shù)：2.00)V解析：［解析］I錯(cuò)誤，當(dāng)前比較流行的、能支持多處理機(jī)運(yùn)行的OS,幾乎全部都采用微內(nèi)核結(jié)構(gòu)，包括WindowsXPOII錯(cuò)誤，模塊化OS結(jié)構(gòu)原則是：分解和模塊化。II中描述的是分層式結(jié)構(gòu)設(shè)計(jì)的基本原則。III正確。IV錯(cuò)誤，微內(nèi)核結(jié)構(gòu)將操作系統(tǒng)的很多服務(wù)移動(dòng)到內(nèi)核以外(如文件系統(tǒng))。且服務(wù)之間使用進(jìn)程間通信機(jī)制進(jìn)行信息交換，這種通過(guò)進(jìn)程間通信機(jī)制進(jìn)行信息交換影響了系統(tǒng)的效率，所以微內(nèi)核結(jié)構(gòu)設(shè)計(jì)并不會(huì)使系統(tǒng)更高效。由于內(nèi)核的內(nèi)服務(wù)變少了，且一般來(lái)說(shuō)內(nèi)核的服務(wù)越少肯定越穩(wěn)定。24.在有一個(gè)CPU和兩臺(tái)外設(shè)D1和D2,且能夠?qū)崿F(xiàn)搶占式優(yōu)先級(jí)調(diào)度算法的多道程序環(huán)境中，同時(shí)進(jìn)入優(yōu)先級(jí)由高到低的P1,P2,P3的3個(gè)作業(yè)，每個(gè)作業(yè)的處理程序和使用資源的時(shí)間如下：P1：D2(30ms),CPU(10ms),D1(30ms),CPU(10ms)P2：D1(20ms),CPU(20ms),D2(40ms)P3：CPU(30ms),D1(20ms)假設(shè)對(duì)于其他輔助操作時(shí)間忽略不計(jì)，CPU的利用率是。A.47.8%B.57.8%C.67.8%D.77.8%(分?jǐn)?shù)：2.00)V解析：［解析］搶占式優(yōu)先級(jí)調(diào)度算法，3個(gè)作業(yè)執(zhí)行的順序如圖所示。(還可以有一種畫法，即按照進(jìn)程來(lái)考慮，縱坐標(biāo)為P1、P2、P3。)［ A.4、8、11? B.4、6? C.6、8? D.4 A.4、8、11? B.4、6? C.6、8? D.4、8.設(shè)有如下兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2。信號(hào)量S1和S2的初值均為0,試問(wèn)P1、P2并發(fā)執(zhí)行結(jié)束后，z的值可能是。進(jìn)程P1：V=j；z=2；V(S1)；z=y+1；P(S2)；y=z+y；進(jìn)程P2：x=2；P(S1)；x=x+2；V(S2)；z=x+z；（分?jǐn)?shù)：2.00）A.B.C.D.V解析：［解析］這類題目其實(shí)不難，但這種題卻很容易答錯(cuò)，原因就是很容易漏掉某種情況。首先，將上述進(jìn)程分解成以下6個(gè)程序段：PS3：y=z+y；PS1：y=3；PS2：z=y+1；PS3：y=z+y；z=2；PS4：x=2；PS5：x=x+2；PS6：z=x+z；假設(shè)沒(méi)有PV操作的情況下。進(jìn)程并發(fā)執(zhí)行關(guān)系用前驅(qū)圖表示如圖1所示。加入了PV操作后用前驅(qū)圖表示如圖2所示。由于x的值只有PS4、PS5決定，且兩者順序關(guān)系確定，則易得x的值始終為4。又P2和P1共享的變量只有z,則PS6與PS1、PS2、PS3的關(guān)系決定了最終的y和z的值。又根據(jù)進(jìn)程前驅(qū)圖得，PS6在PS1之后。所以可能的情況有（PS4、PS5所處的順序有多種情況，但都不對(duì)最后結(jié)果產(chǎn)生影響，為了方便，我們統(tǒng)一把PS4、PS5放在PS1后面執(zhí)行）：PS1、PS4、PS5、PS6、PS2、PS3：PS1、PS4、PS5、PS2、PS6、PS3：PS1、PS4、PS5、PS2、PS3、PS6：這3種情況，計(jì)算過(guò)程如下表所示。困圖1進(jìn)程并發(fā)執(zhí)行關(guān)系的前驅(qū)圖

困圖2加入PV操作后的前驅(qū)圖{{B}}計(jì)算過(guò)程{{/B}}xyzxyzxyzPS132PS132PS132PS42PS42PS42PS54PS54PS54PS66PS24PS24PS24PS68PS37PS37PS311PS684744118478綜上所述，z的值可能是4、8。.系統(tǒng)的資源分配圖在下列情況中，無(wú)法判斷是否處于死鎖的情況是I.出現(xiàn)了環(huán)路II.沒(méi)有環(huán)路.每種資源只有一個(gè)，并出現(xiàn)環(huán)路IV.每個(gè)進(jìn)程結(jié)點(diǎn)至少有一條請(qǐng)求邊A.i、n、m、ivb.僅i、mi、ivC.僅I、IVd.都能判斷（分?jǐn)?shù)：2.00）A.B.D.解析：［解析］首先要注意，本題的問(wèn)法比較拗口，是無(wú)法判斷的情況，不可理解錯(cuò)誤。本題的難點(diǎn)主要在于區(qū)分資源分配圖中的環(huán)路和系統(tǒng)狀態(tài)的環(huán)路有什么關(guān)系。資源分配圖中的環(huán)路通過(guò)分配資源，是可以消除的，即消邊。而系統(tǒng)狀態(tài)圖中的環(huán)路其實(shí)就是死鎖。兩者的關(guān)系其實(shí)可以理解為資源分配圖通過(guò)簡(jiǎn)化（消邊）后就是系統(tǒng)狀態(tài)圖。如果資源分配圖中不存在環(huán)路，則系統(tǒng)狀態(tài)圖無(wú)環(huán)路，則無(wú)死鎖；故n確定不會(huì)發(fā)生死鎖。反之，如果資源分配圖中存在環(huán)路，經(jīng)過(guò)簡(jiǎn)化（消邊）后，則系統(tǒng)狀態(tài)圖中可能存在環(huán)路，也可能不存在環(huán)路。根據(jù)資源分配圖算法，如果每一種資源類型只有一個(gè)實(shí)例且出現(xiàn)環(huán)路，那么無(wú)法簡(jiǎn)化（消邊），死鎖發(fā)生，故m可以確定死鎖發(fā)生。剩下I和iv都不能確定，因?yàn)樗鼈兊馁Y源分配圖中雖然存在環(huán)路，但是不能確定是否可以簡(jiǎn)化成無(wú)環(huán)路的系統(tǒng)狀態(tài)圖。所以本題選c選項(xiàng)。27.下列存儲(chǔ)管理方式中，會(huì)產(chǎn)生內(nèi)部碎片的是。I.分段虛擬存儲(chǔ)管理n.分頁(yè)虛擬存儲(chǔ)管理m.段頁(yè)式分區(qū)管理iv.固定式分區(qū)管理a.僅i、n、mb.僅m、ivc.僅nd.僅n、m、iv（分?jǐn)?shù)：2.00）V解析：［解析］只要是固定的分配就會(huì)產(chǎn)生內(nèi)部碎片，其余的都會(huì)產(chǎn)生外部碎片。如果固定和不固定同時(shí)存在（例如段頁(yè)式），物理本質(zhì)還是固定的，解釋如下：分段虛擬存儲(chǔ)管理：每一段的長(zhǎng)度都不一樣（對(duì)應(yīng)不固定），所以會(huì)產(chǎn)生外部碎片。分頁(yè)虛擬存儲(chǔ)管理：每一頁(yè)的長(zhǎng)度都一樣（對(duì)應(yīng)固定），所以會(huì)產(chǎn)生內(nèi)部碎片。段頁(yè)式分區(qū)管理：地址空間首先被分成若干個(gè)邏輯分段（這里的分段只是邏輯上的，而我們所說(shuō)的碎片都是物理上的真實(shí)存在的，所以是否有碎片還是要看每個(gè)段的存儲(chǔ)方式，所以頁(yè)才是物理單位），每段都有自己的段號(hào)，然后再將每個(gè)段分成若干個(gè)固定的頁(yè)。所以其仍然是固定分配，會(huì)產(chǎn)生內(nèi)部碎片。固定式分區(qū)管理：很明顯固定，會(huì)產(chǎn)生內(nèi)部碎片。綜上分析，本題選D選項(xiàng)。28.下列程序設(shè)計(jì)技術(shù)和數(shù)據(jù)結(jié)構(gòu)中，適合虛擬頁(yè)式存儲(chǔ)系統(tǒng)的有。I.堆棧II.Hash函數(shù)索引的符號(hào)表III.順序搜索IV.二分法查找V.純代碼W.矢量操作加.間接尋址血.矩陣操作A.i、m、v、w、加B.i、n、m、如c.n、v、w、加D.m、v、w、如（分?jǐn)?shù)：2.00）V解析：［解析］虛擬分頁(yè)存儲(chǔ)系統(tǒng)中，頁(yè)內(nèi)地址是連續(xù)的，而頁(yè)問(wèn)地址不連續(xù)。當(dāng)頁(yè)面不在內(nèi)存時(shí)，會(huì)引起缺頁(yè)中斷，相對(duì)消耗很多的時(shí)間。這類題解題思路起始都是應(yīng)該從局部性出發(fā)。I適合。棧頂操作一般是在當(dāng)前頁(yè)中進(jìn)行，此前已駐留內(nèi)存。只有當(dāng)棧頂跨頁(yè)面時(shí)，才會(huì)引起缺頁(yè)中斷。II不適合。Hash函數(shù)產(chǎn)生的索引地址是隨機(jī)的，可能會(huì)頻繁缺頁(yè)。III適合。搜索一般是在當(dāng)前頁(yè)中進(jìn)行，此前已駐留內(nèi)存。只有當(dāng)跨頁(yè)面搜索時(shí)，才會(huì)引起缺頁(yè)中斷。IV不適合。二分法查找是跳躍式的，可能會(huì)頻繁缺頁(yè)。V適合。純代碼基本上是順序執(zhí)行的。其跳轉(zhuǎn)指令全是相對(duì)跳轉(zhuǎn)的，范圍一般在一個(gè)頁(yè)面之內(nèi)。只有當(dāng)跨頁(yè)面跳轉(zhuǎn)時(shí)，才會(huì)引起缺頁(yè)中斷。W適合。一個(gè)矢量的各分量均順序排列，一般在同一頁(yè)面內(nèi)。如不適合。存放間接地址的頁(yè)面，存放直接地址的頁(yè)面，以及存放內(nèi)容的頁(yè)面沒(méi)有規(guī)律，它們可能不在同一個(gè)頁(yè)面。而適合。矩陣的各元素均順序排列，一般在同一頁(yè)面內(nèi)。29.下面關(guān)于文件的敘述中，錯(cuò)誤的是。I.打開文件的主要操作是把指定文件復(fù)制到內(nèi)存指定的區(qū)域II.對(duì)一個(gè)文件的訪問(wèn)，常由用戶訪問(wèn)權(quán)限和用戶優(yōu)先級(jí)共同限制I.文件系統(tǒng)采用樹形目錄結(jié)構(gòu)后，對(duì)于不同用戶的文件，其文件名應(yīng)該不同V.為防止系統(tǒng)故障造成系統(tǒng)內(nèi)文件受損，常采用存取控制矩陣方法保護(hù)文件A.僅Ib.僅i、mc.僅i、m、ivD.i、n、m、iv（分?jǐn)?shù)：2.00）A.V解析：［解析］I錯(cuò)誤，系統(tǒng)調(diào)用open把文件的信息目錄放到打開文件表中。II錯(cuò)誤，對(duì)一個(gè)文件的訪問(wèn)，常由用戶訪問(wèn)權(quán)限和文件屬性共同限制。m錯(cuò)誤，文件系統(tǒng)采用樹形目錄結(jié)構(gòu)后，對(duì)于不同用戶的文件，其文件名可以不同，也可以相同。V錯(cuò)誤，常采用備份的方法保護(hù)文件。而存取控制矩陣的方法是用于多用戶之間的存取權(quán)限保護(hù)。30.在PC-DOS中，某磁盤文件A與B,它們所占用的磁盤空間如下所示。試問(wèn)A、B文件在磁盤上各占簇。{{B}}表1FDT（文件目錄表）{{加}}……A002B003……{{B}}表2FAT（文件配置表）{{/B}}簇號(hào)FAT值000FFD001FFF002004003008004009005007006FFF007FFF008006009005……TOC\o"1-5"\h\zA.3, 3B.4, 5C.5, 3D.5, 4（分?jǐn)?shù)：2.00）A.VD.解析：［解析］當(dāng)查找文件在磁盤上的存放地址時(shí)，首先從目錄中找到文件的起始簇號(hào)，然后再到FIAT表的相應(yīng)表目中找到文件存放的下一個(gè)簇號(hào)，依此類推，直至遇到值為FFF的表項(xiàng)為止。文件A在磁盤上占用5簇，簇號(hào)依次為002、004、009、005、007。文件B在磁盤上占用3簇，簇號(hào)依此為003、008、006。31.某磁盤盤組共有10個(gè)盤面，每個(gè)盤面上有100個(gè)磁道，每個(gè)磁道有32個(gè)扇區(qū)，假定物理塊的大小為2個(gè)扇區(qū)，分配以物理塊為單位。若使用位圖（bitmap）管理磁盤空間，則位圖需要占用的空間大小是。A.2000BB.12000BC.6000BD.16000B（分?jǐn)?shù)：2.00）VC.D.解析：［解析］已知磁盤盤組共有10個(gè)盤面，每個(gè)盤面上有100個(gè)磁道，每個(gè)磁道有32個(gè)扇區(qū)，則一共有10X100X32=32000個(gè)扇區(qū)。題目又假定物理塊的大小為2個(gè)扇區(qū)，分配以物理塊為單位，即一共有16000個(gè)物理塊。因此，位圖所占的空間為16000/8B=2000B。32.關(guān)于SPOOLing技術(shù)的說(shuō)法，以下正確的是。SPOOLing系統(tǒng)中不需要獨(dú)占設(shè)備SPOOLing系統(tǒng)加快了作業(yè)完成的速度III.當(dāng)輸入設(shè)備忙時(shí)，SPOOLing系統(tǒng)中的用戶程序暫停執(zhí)行，待I/O空閑時(shí)再被喚醒執(zhí)行輸出操作IV.在采用SPOOLing技術(shù)的系統(tǒng)中，用戶的打印結(jié)果首先被送到內(nèi)存固定區(qū)域A.僅I、IIB.僅Ic.僅n、md.僅m、iv（分?jǐn)?shù)：2.00）V解析：［解析］I錯(cuò)誤，SPOOLing技術(shù)是將獨(dú)占設(shè)備改為共享設(shè)備，所以肯定需要獨(dú)占設(shè)備。II正確，SPOOLing技術(shù)通過(guò)在磁盤上開辟存儲(chǔ)空間模擬月兌機(jī)輸出，可以減少作業(yè)輸出等待時(shí)間，加快作業(yè)完成的速度。III錯(cuò)誤，引入SPOOLing技術(shù)的目的就是在輸入設(shè)備忙時(shí)，進(jìn)程不必等待I/O操作的完成。IV錯(cuò)誤，在SPOOLing系統(tǒng)中，用戶的輸出數(shù)據(jù)先送入輸出井，即磁盤固定區(qū)域。綜上分析，本題選B選項(xiàng)。A.5個(gè)沖突域，1個(gè)廣播域B.3個(gè)沖突域，3個(gè)廣播域C.4個(gè)沖突域，2個(gè)廣播域D.6個(gè)沖突域，2個(gè)廣播域（分?jǐn)?shù)：2.00）V解析：［解析］通常普通的集線器是一種工作在物理層，具有“共享沖突域、共享廣播域”特性的網(wǎng)絡(luò)互連設(shè)務(wù)。而將交換機(jī)和網(wǎng)橋稱為二層設(shè)備，它是一種工作在數(shù)據(jù)鏈路層，具有“隔離沖突域、共享廣播域”特性的網(wǎng)絡(luò)互連設(shè)備?？梢?jiàn)，交換機(jī)只能縮小沖突域，而不能縮小廣播域。將路由器稱為三層設(shè)備，它是一種工作在網(wǎng)絡(luò)層，具有“隔離沖突域、隔離廣播域”功能的網(wǎng)絡(luò)互連設(shè)備。在Internet等主干網(wǎng)上，路由器的主要作用是路由選擇。由以上分析可知，題圖所示的拓?fù)浣Y(jié)構(gòu)中共有4個(gè)沖突域，2個(gè)廣播域，具體如下圖所示。困其中，沖突域1和沖突域2屬于同一個(gè)廣播域，沖突域3和沖突域4屬于另外一個(gè)廣播域?？偨Y(jié)（見(jiàn)下表）：TOC\o"1-5"\h\z{{B}}各設(shè)備的沖突域與廣播域{{/B}}設(shè)備名稱隔離沖突域隔離廣播域集線器 X X中繼器 X X交換機(jī) V X網(wǎng)橋 V X路由器 V V34.長(zhǎng)度為1km,數(shù)據(jù)傳輸率為10Mbit/s以太網(wǎng)，電信號(hào)在網(wǎng)上的傳播速度是200m/〃s。假設(shè)以太網(wǎng)數(shù)據(jù)幀的長(zhǎng)度為256bit,其中包括64bit幀頭、檢驗(yàn)和及其他開銷。數(shù)據(jù)幀發(fā)送成功后的第一個(gè)時(shí)間片保留給接收方，用于發(fā)送一個(gè)64bit的確認(rèn)幀。假設(shè)網(wǎng)絡(luò)負(fù)載非常輕（即不考慮沖突的任何情形），則該以太網(wǎng)的有效數(shù)據(jù)傳輸速率為。A.4.21Mbit/sB.11.7Mbit/sC.6.09Mbit/sD.5.19Mbit/s(分?jǐn)?shù)：2.00)V解析：［解析］(1)發(fā)送256bit數(shù)據(jù)幀所用的發(fā)送時(shí)間=256bit/10Mbit/s=25.6ps；(2)數(shù)據(jù)幀在電纜線上的傳播時(shí)間=1000m/(200m/ps)=5ps；(3)發(fā)送64bit的確認(rèn)幀所用的發(fā)送時(shí)間=64bit/10Mbit/s=6.4ps：(4)確認(rèn)幀在電纜上的傳播時(shí)間=1000m/(200m/ps)=5ps； (5)為了保證沖突檢測(cè)機(jī)制能夠正常進(jìn)行，64位確認(rèn)幀要進(jìn)行填充，使得其傳輸時(shí)延等于往返傳播時(shí)延10Ps；有效數(shù)據(jù)傳輸率=發(fā)送的有效數(shù)據(jù)/發(fā)送有效數(shù)據(jù)所用的總時(shí)間，而有效數(shù)據(jù)=(256-64)bit=192bit,發(fā)送192bit的有效數(shù)據(jù)所占用的總時(shí)間=(25.6+5+6.4+5)ps=45.6ps；則該以太網(wǎng)的有效數(shù)據(jù)傳輸率為192bit/42ps=4.21Mbiffs。35.下面技術(shù)無(wú)法使10Mbit/s的以太網(wǎng)升級(jí)到100Mbit/s的是。A.幀長(zhǎng)保持不變，網(wǎng)絡(luò)跨距增加B.采用幀擴(kuò)展技術(shù)C.傳輸介質(zhì)使用高速光纖D.使用以太網(wǎng)交換機(jī)，引入全雙工流量控制協(xié)議(分?jǐn)?shù)：2.00)V解析：［解析］CSMA/CD協(xié)議要求每幀的發(fā)送時(shí)間不小于信號(hào)的往返時(shí)延。如果電纜線長(zhǎng)度增加，傳播時(shí)延增加，沖突檢測(cè)時(shí)間增加，幀長(zhǎng)保持不變，則發(fā)送速率應(yīng)減少，A錯(cuò)。幀擴(kuò)展技術(shù)解決了網(wǎng)絡(luò)跨距問(wèn)題，但可能影響短幀的傳輸性能，在千兆以太網(wǎng)標(biāo)準(zhǔn)中增加了幀突發(fā)技術(shù)，提高了網(wǎng)絡(luò)帶寬利用率，B對(duì)。高速光纖的使用大大提高了網(wǎng)絡(luò)的傳輸速率，使10Mbit/s升級(jí)到100Mbit/s和1Gbit/s成為可能，C對(duì)。全雙工的以太網(wǎng)交換機(jī)不執(zhí)行CSMA/CD協(xié)議，每幀的發(fā)送時(shí)間不受往返時(shí)延影響，D對(duì)。36.某端口的IP地址為172.16.7.131/26,則該IP地址所在網(wǎng)絡(luò)的廣播地址是。A.172.16.7.255B.172.16.7.129C.172.16.7.191D.172.16.7.252(分?jǐn)?shù)：2.00)V解析：［解析］首先要清楚廣播地址就是將主機(jī)位全部置為1,/26表示前3個(gè)字節(jié)都是網(wǎng)絡(luò)段，最后一個(gè)字節(jié)的頭兩位也是網(wǎng)絡(luò)段。前3個(gè)字節(jié)忽略，只解釋最后一個(gè)字節(jié)。將131以二進(jìn)制表示為10000011。根據(jù)廣播地址的定義，主機(jī)段全1即為廣播地址，即10111111,轉(zhuǎn)換為十進(jìn)制為191,故廣播地址為172.16.7.191。37.下列關(guān)于ARP的說(shuō)法中，錯(cuò)誤的是。ARP的請(qǐng)求報(bào)文是單播的ARP的響應(yīng)報(bào)文是單播的III.如果局域網(wǎng)A的主機(jī)1想和局域網(wǎng)B的主機(jī)2通信，但是主機(jī)1不知道主機(jī)2的物理地址，主機(jī)1通過(guò)發(fā)送ARP報(bào)文就可以解決A.僅IB.僅Ic.僅i、md.僅n、m（分?jǐn)?shù)：2.00）V解析：［解析］I：當(dāng)主機(jī)A要向本局域網(wǎng)上的某個(gè)主機(jī)B發(fā)送IP數(shù)據(jù)報(bào)時(shí)，如果在其ARP高速緩存中查詢不到主機(jī)B的物理地址，這時(shí)候ARP進(jìn)程就需要在本局域網(wǎng)上廣播發(fā)送一個(gè)ARP請(qǐng)求分組，所以ARP的請(qǐng)求報(bào)文是廣播的，不是單播的，故I錯(cuò)誤。II：接著上面的論述，此時(shí)應(yīng)該是本局域網(wǎng)上的所有主機(jī)都可以收到此ARP的請(qǐng)求分組，而主機(jī)B見(jiàn)到ARP分組中的IP地址是自己的IP時(shí)，就向主機(jī)A發(fā)送一個(gè)ARP響應(yīng)分組，所以ARP響應(yīng)分組是普通的單播，故I正確。I：這個(gè)一定要注意了，很多考生都誤認(rèn)為是正確的。記住一句話：ARP是解決同一局域網(wǎng)上的主機(jī)或路由器的IP地址和硬件地址的映射問(wèn)題，如果所要找的主機(jī)和源主機(jī)不在同一個(gè)局域網(wǎng)上，剩下的所有工作都應(yīng)該由下一跳的路由器來(lái)完成，故m錯(cuò)誤。注：ARP數(shù)據(jù)單元是被封裝在以太幀中。38.一個(gè)網(wǎng)段的網(wǎng)絡(luò)號(hào)為198.90.10.0/27,子網(wǎng)掩碼固定為255.255.255.224,最多可以分成個(gè)子塊，而每個(gè)子塊最多具有個(gè)有效的IP地址。A.8,30B.6,30C.16,14D.32,6（分?jǐn)?shù)：2.00）V解析：［解析］/27是引入無(wú)類別域間路由選擇（CIDR）后子網(wǎng)IP地址的表示方法，對(duì)應(yīng)的子網(wǎng)掩碼表示是255.255.255.224。地址的最后1個(gè)字節(jié)中有3位屬于子網(wǎng)號(hào)部分（物理網(wǎng)絡(luò)號(hào)共27位），主機(jī)號(hào)只有5位。198.90.10.0是C類地址，網(wǎng)絡(luò)號(hào)24位，最后1個(gè)字節(jié)中的子網(wǎng)號(hào)3位，最多可以分成8個(gè)子塊，主機(jī)號(hào)部分5位共32個(gè)地址，除了全1和全0,有30個(gè)有效的IP地址。39.A和B建立TCP連接，MSS為1KB。某時(shí)，慢開始門限值為2KB,A的擁塞窗口為4KB,在接下來(lái)的一個(gè)RTT內(nèi)，A向B發(fā)送了4KB的數(shù)據(jù)（TCP的數(shù)據(jù)部分），并且得到了B的確認(rèn)，確認(rèn)報(bào)文中的窗口字段的值為2KB,那么，請(qǐng)問(wèn)在下一個(gè)RTT中，A最多能向B發(fā)送數(shù)據(jù)。A.2KBB.4KBC.5KBD.8KB（分?jǐn)?shù)：2.00）V解析：［解析］首先，發(fā)送窗口應(yīng)該在擁塞窗口和接收窗口中取最小值，所以本題關(guān)鍵點(diǎn)在于求本RTT內(nèi)擁塞窗口和接收窗口的大小。在接下來(lái)的一個(gè)RTT內(nèi)，A向B發(fā)送了4KB的數(shù)據(jù)，且此時(shí)擁塞窗口為4KB,按照擁塞避免算法（因?yàn)榇藭r(shí)擁塞窗口大于慢開始門限值，所以采用擁塞避免算法），收到B的確認(rèn)報(bào)文后，擁塞窗口增加到5KB。另外，B發(fā)給A的確認(rèn)報(bào)文中的窗口字段的值為2KB,故此時(shí)接收窗口的大小為2KB,所以在下一個(gè)RTT中，A最多能向B發(fā)送2KB數(shù)據(jù)。40.在進(jìn)行域名解析的過(guò)程中，由獲取的解析結(jié)果耗時(shí)最短。A.主域名服務(wù)器B.輔域名服務(wù)器C.緩存域名服務(wù)器D.轉(zhuǎn)發(fā)域名服務(wù)器（分?jǐn)?shù)：2.00）V解析：［解析］緩存域名服務(wù)器是一種很特殊的DNS服務(wù)器，它本身并不管理任何區(qū)域，但是DNS客戶端仍然可以向它請(qǐng)求查詢。緩存域名服務(wù)器類似于代理服務(wù)器，它沒(méi)有自己的域名數(shù)據(jù)庫(kù)，而是將所有查詢轉(zhuǎn)發(fā)到其他DNS服務(wù)器處理。當(dāng)緩存域名服務(wù)器從其他DNS服務(wù)器收到查詢結(jié)果后，除了返回給客戶端外，還會(huì)將結(jié)果保存在緩存中。當(dāng)下一個(gè)DNS客戶端再查詢相同的域名數(shù)據(jù)時(shí)，就可以從高速緩存里得到結(jié)果，從而加快對(duì)DNS客戶端的響應(yīng)速度。二、{{B}}綜合應(yīng)用題{{/B}}（總題數(shù):6,分?jǐn)?shù):60.00）已知由n-1個(gè)關(guān)鍵字組成的序列（K1,',???,KJ是大頂堆，現(xiàn)在增加一個(gè)關(guān)鍵字Kn,要求將關(guān)鍵字序列（K/\,???,'/Kn）,重新調(diào)整為大頂堆。請(qǐng)完成以下要求：（分?jǐn)?shù)：12.99）.給出算法的基本設(shè)計(jì)思想。（分?jǐn)?shù)：4.33）正確答案：（基本設(shè)計(jì)思想：從根結(jié)點(diǎn)的父母結(jié)點(diǎn)的標(biāo)號(hào)［n/2］開始向上，對(duì)每個(gè)當(dāng)前結(jié)點(diǎn)和左右子樹進(jìn)行調(diào)整。最開始的時(shí)候要判斷n是左結(jié)點(diǎn)還是右結(jié)點(diǎn)，之后的情況一定是左右結(jié)點(diǎn)都有。每次把當(dāng)前結(jié)點(diǎn)的標(biāo)號(hào)除以2則得到當(dāng)前結(jié)點(diǎn)的父母結(jié)點(diǎn)的標(biāo)號(hào)。）解析：.根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。（分?jǐn)?shù)：4.33）正確答案：（算法實(shí)現(xiàn)如下：#definen100;//宏定義n常量，由用戶自定義結(jié)點(diǎn)個(gè)數(shù)intK［n］;//關(guān)鍵字序列Voidheap(){inti=n/2;〃找到最后一個(gè)結(jié)點(diǎn)的父母結(jié)點(diǎn)if(n%2==1)〃當(dāng)n是右結(jié)點(diǎn)時(shí){if(K[i]<K[n-1]&&K[n-1]〉K[n])swap(K[nT],K[i]);//swap()實(shí)現(xiàn)交換兩個(gè)元素if(K[i]<K[n]圖2獨(dú)占查詢方式下的I/O過(guò)程)解析：正確答案：（圖2獨(dú)占查詢方式下的I/O過(guò)程)解析：正確答案：（外層磁道的長(zhǎng)度為2nR=2X3.14X15.5cm=97.34cm每道信息量=600bit/cmX97.34cm=58404bit=7300.5B磁盤總?cè)萘?7300.5BX1320道=9636660B（非格式化容量）磁盤在使用之前要對(duì)其執(zhí)行格式化操作，要首先完成劃分磁道和扇區(qū)，設(shè)置文件目錄區(qū)等。非格式化容量是指一個(gè)盤片上可以記錄的二進(jìn)制位的總數(shù)量，而格式化容量通常是指用戶可用空間的二進(jìn)制位的總數(shù)量，前者比后者要大，因?yàn)橄到y(tǒng)要管理磁盤會(huì)占用一定的存儲(chǔ)空間，還要使用一個(gè)磁道用于同步，扇區(qū)之間還有間隔和一些為保存檢錯(cuò)糾錯(cuò)信息的空間，磁盤上往往還會(huì)留有一些備份磁道。在談到磁盤容量時(shí)，通常指的是格式化之后用戶可用的磁盤容量。）解析：（3）.將長(zhǎng)度超過(guò)一個(gè)磁道容量的文件記錄在同一個(gè)柱面上是否合理？（分?jǐn)?shù)：2.40）.說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。(分?jǐn)?shù)：4.33)正確答案：(時(shí)間復(fù)雜度分析：在循環(huán)當(dāng)中，我們可以看出每次都是對(duì)結(jié)點(diǎn)的父母結(jié)點(diǎn)進(jìn)行調(diào)整，因此操作次數(shù)正好是樹的高度，時(shí)間復(fù)雜度為O(log2i)。)解析：假設(shè)一個(gè)主頻為1GHz、CPI為5的CPU需要從某個(gè)成塊傳送的I/O設(shè)備讀取1000B的數(shù)據(jù)到主存緩沖區(qū)中，該I/O設(shè)備一旦啟動(dòng)即按50KB/s的數(shù)據(jù)傳輸率向主機(jī)傳送1000B數(shù)據(jù)，每個(gè)字節(jié)的讀取、處理并存入內(nèi)存緩沖區(qū)需要1000個(gè)時(shí)鐘周期，則以下4種方式下，在1000B的讀取過(guò)程中，CPU用在該設(shè)備的I/O操作上的時(shí)間分別為多少？占整個(gè)CPU時(shí)間的百分比分別是多少？(分?jǐn)?shù)：11.00).采用定時(shí)查詢方式，每次處理一個(gè)字節(jié)，一次狀態(tài)查詢至少需要60個(gè)時(shí)鐘周期。(分?jǐn)?shù)：2.20)正確答案：(定時(shí)查詢方式下的I/O過(guò)程如圖1所示。用戶可以設(shè)置每隔20000ns查詢一次，這樣使得查詢程序的開銷達(dá)到最小，即第一次讀取狀態(tài)時(shí)就可能會(huì)發(fā)現(xiàn)就緒，然后用1000個(gè)時(shí)鐘周期進(jìn)行相應(yīng)處理，因此，對(duì)于每個(gè)字節(jié)的傳送，CPU所用時(shí)鐘周期數(shù)為60+1000=1060。因此，在1000B的讀取過(guò)程中，CPU用在該設(shè)備的I/O操作上的時(shí)間至少為1000X1060X1ns=1.060ms,占整個(gè)CPU時(shí)間的百分比至少為1.060/20=5.3%。[正確答案：(獨(dú)占查詢方式下的I/O正確答案：(獨(dú)占查詢方式下的I/O過(guò)程如圖2所示。啟動(dòng)設(shè)備后，CPU就開始查詢，因?yàn)?33X60+20=20000,所以第一個(gè)字節(jié)傳送在第334次讀取狀態(tài)查詢時(shí)檢測(cè)到就緒，隨后用1000個(gè)時(shí)鐘周期進(jìn)行相應(yīng)的處理，然后繼續(xù)第二個(gè)字節(jié)的狀態(tài)查詢，因?yàn)?0+1000+316X60=20000,所以，第二個(gè)字節(jié)的傳送在第316次讀取狀態(tài)查詢時(shí)檢測(cè)到就緒，第一個(gè)和第二個(gè)字節(jié)的傳送過(guò)程如圖2a所示。每次檢測(cè)到就緒后，就進(jìn)行相應(yīng)的處理，然后周而復(fù)始地進(jìn)行查詢，因?yàn)?20000-1000)/60=316.7,所以，第317次狀態(tài)查詢時(shí)發(fā)現(xiàn)就緒。因?yàn)?000+60X317-20000=20,所以，每3B可多60個(gè)時(shí)鐘周期，正好進(jìn)行一次狀態(tài)查詢，因此，在剩下的998B的讀取過(guò)程中，前996B的傳送正好用了996X20000個(gè)時(shí)鐘周期，如圖2b所示。最后兩個(gè)字節(jié)的傳送過(guò)程如圖2c所示，因?yàn)?X(1000+60X317-20000)=40,此外，最后一個(gè)字節(jié)的處理還有1000個(gè)時(shí)鐘周期，所以最后兩個(gè)字節(jié)總的時(shí)間為2X20000+40+1000=41040個(gè)時(shí)鐘周期。綜上所述，CPU用在該設(shè)備的I/O操作上的總時(shí)間為1000X20000ns+1040X1ns=20.00104ms720ms,即在1000B的整個(gè)傳輸過(guò)程中，CPU一直為該設(shè)備服務(wù)，所用時(shí)間占整個(gè)CPU時(shí)間的100%。圖1定時(shí)查詢方式下的I/O過(guò)程)解析：[解析]主頻為1GHz,所以時(shí)鐘周期為1/1GHz=1ns。因?yàn)槊總€(gè)字節(jié)的讀取、處理并存入內(nèi)存緩沖區(qū)需要1000個(gè)時(shí)鐘周期，所以，對(duì)于像程序查詢和中斷等用軟件實(shí)現(xiàn)輸入/輸出的方式，CPU為每個(gè)字節(jié)傳送所用的時(shí)間至少為1000X1ns=1000ns=1ps。在50kB/s的數(shù)據(jù)傳輸率下，設(shè)備每隔1B/50kB/s=20ps=20000ns準(zhǔn)備好一個(gè)字節(jié)，因而讀取1000B的時(shí)間為1000X20ps=20ms。.采用獨(dú)占查詢方式，每次處理一個(gè)字節(jié)，一次狀態(tài)查詢至少需要60個(gè)時(shí)鐘周期。(分?jǐn)?shù)：2.20).采用中斷I/O方式，外設(shè)每準(zhǔn)備好一個(gè)字節(jié)發(fā)送一次中斷請(qǐng)求。每次中斷響應(yīng)需要2個(gè)時(shí)鐘周期，中斷服務(wù)程序的執(zhí)行需要1200個(gè)時(shí)鐘周期。（分?jǐn)?shù)：2.20）正確答案：（中斷方式下的I/O過(guò)程如圖3所示。中斷方式下，外設(shè)每準(zhǔn)備好一個(gè)字節(jié)請(qǐng)求一次中斷，每次中斷CPU所用時(shí)鐘周期數(shù)為2+1200=1202,因此CPU用在該設(shè)備的I/O操作上的時(shí)間為1000X1202X1ns=1.202ms,占整個(gè)CPU時(shí)間的百分比至少為1.202/20=6.01%。困圖3中斷方式下的I/O過(guò)程）解析：.采用周期挪用DMA方式，每挪用一次主存周期處理一個(gè)字節(jié)，一次DMA傳送完成1000B的傳送，DMA初始化和后處理的時(shí)間為2000個(gè)時(shí)鐘周期，CPU和DMA之間沒(méi)有訪存沖突。（分?jǐn)?shù)：2.20）正確答案：（DMA方式下，由于CPU和DMA沒(méi)有訪存沖突，所以不需考慮由于DMA而影響到CPU執(zhí)行其他程序。因此，傳送1000BCPU所用的時(shí)鐘周期數(shù)就是2000,在1000B的讀取過(guò)程中，CPU用在該設(shè)備的I/O操作上的時(shí)間為2000X1ns=2ps,占整個(gè)CPU時(shí)間的百分比為2/（1000X20）=0.01%。）解析：.如果設(shè)備的速度提高到5MB/s,則上述4種方式中，哪些是不可行的?為什么？對(duì)于可行的方式，計(jì)算出CPU在該設(shè)備I/O操作上所用的時(shí)間占整個(gè)CPU時(shí)間的百分比。（分?jǐn)?shù)：2.20）正確答案：（若設(shè)備數(shù)據(jù)傳輸率為5MB/s,則外設(shè)傳輸1000B所用時(shí)間為1000B/（5X108/s）=200ps。對(duì)于定時(shí)查詢和獨(dú)占查詢方式，傳送1000BCPU所用時(shí)間至少為1000X（60+1000）X1ns=1060ps；對(duì)于中斷方式，傳送1000BCPU所用時(shí)間為1000X（2+1200）X1ns=1202ps。上述3種方式下，CPU所用的時(shí)間都比設(shè)備所用時(shí)間長(zhǎng)得多，即設(shè)備的傳輸比CPU的處理快得多，因而發(fā)生數(shù)據(jù)丟失。因此，這3種方式都不能用于該設(shè)備的I/O操作。對(duì)于DMA方式，傳送1000BCPU所用時(shí)間為2000X1ns=2ps,占整個(gè)CPU時(shí)間的百分比為2/200=1%。這說(shuō)明可以使用DMA方式，不過(guò)由于外設(shè)傳輸速度加快，使得CPU頻繁進(jìn)行DMA預(yù)處理和后處理，因而CPU的開銷從0.01%上升到了1%。）解析：硬磁盤共有4個(gè)記錄面，存儲(chǔ)區(qū)域內(nèi)半徑為10cm,外半徑為15.5cm,道密度為60道/cm,外層位密度為600bit/cm,轉(zhuǎn)速為6000r/min。問(wèn)：（分?jǐn)?shù)：12.00）.硬磁盤的磁道總數(shù)是多少？（分?jǐn)?shù)：2.40）正確答案：（有效存儲(chǔ)區(qū)域=15.5cm-10cm=5.5cm,道密度=60道/cm,因此每個(gè)面60道/cmX5.5cm=330道，即有330個(gè)柱面，磁道總數(shù)=4X330道=1320道。）解析：.硬磁盤的容量是多少?磁盤的非格式化容量和格式化容量是一個(gè)什么概念，兩者之間有什么關(guān)系？（分?jǐn)?shù)：2.40）正確答案：（如果長(zhǎng)度超過(guò)一個(gè)磁道容量的文件，將它記錄在同一個(gè)柱面上比較合理，因?yàn)椴恍枰匦聦ふ掖诺?，這樣數(shù)據(jù)讀/寫速度快。）解析：.采用定長(zhǎng)數(shù)據(jù)塊記錄格式，直接尋址的最小單位是什么？尋址命令中磁盤地址如何表示？（分?jǐn)?shù)：2.40）正確答案：（采用定長(zhǎng)數(shù)據(jù)塊格式，直接尋址的最小單位是一個(gè)扇區(qū)，每個(gè)扇區(qū)記錄固定字節(jié)數(shù)目的信息，在定長(zhǎng)記錄的數(shù)據(jù)塊中，活動(dòng)頭磁盤組的編址方式可用如下格式：［*］此地址格式表示最多可以接4臺(tái)硬盤，每臺(tái)最多有8個(gè)記錄面，每面最多可有128個(gè)磁道，每道最多可有16個(gè)扇區(qū)。）解析：.假定每個(gè)扇區(qū)的容量512B，每個(gè)磁道有12個(gè)扇區(qū)，尋道的平均等待時(shí)間為10.5ms，試計(jì)算讀出磁盤一個(gè)扇區(qū)中數(shù)據(jù)的平均時(shí)間。（分?jǐn)?shù)：2.40）正確答案：（讀一個(gè)扇區(qū)中數(shù)據(jù)所用的時(shí)間為找磁道的時(shí)間+找扇區(qū)的時(shí)間+磁頭掃過(guò)一個(gè)扇區(qū)的時(shí)間找磁道時(shí)間是指磁頭從當(dāng)前所處磁道運(yùn)動(dòng)到目標(biāo)磁道的時(shí)間，一般選用磁頭在磁盤徑向方向上移動(dòng)1/2個(gè)半徑長(zhǎng)度所用時(shí)間為平均值來(lái)估算，題中給的是10.5ms。找扇區(qū)的時(shí)間是指磁頭從當(dāng)前所處扇區(qū)運(yùn)動(dòng)到目標(biāo)扇區(qū)的時(shí)間，一般選用磁盤旋轉(zhuǎn)半周的所用時(shí)間作為平均值來(lái)估算，題中給出的磁盤轉(zhuǎn)速為6000r/min，即100r/s，即磁盤轉(zhuǎn)一周用時(shí)為10ms，轉(zhuǎn)半周的時(shí)間是5ms。題中給出每個(gè)磁道有12個(gè)扇區(qū)，磁頭掃過(guò)一個(gè)扇區(qū)用時(shí)為10/12ms=0.83ms，計(jì)算結(jié)果應(yīng)該為10.5ms+5ms+0.83ms=16.33ms。為了減少尋找磁道和等待扇區(qū)所占時(shí)間的比例，磁盤通常應(yīng)該以多個(gè)扇區(qū)為單位進(jìn)行讀寫，一旦開始具體的讀寫操作，就對(duì)多個(gè)連續(xù)的扇區(qū)進(jìn)行順序讀寫，讀寫的數(shù)據(jù)首先保存到系統(tǒng)設(shè)置的一個(gè)緩存區(qū)中，CPU通常要經(jīng)過(guò)操作系統(tǒng)實(shí)現(xiàn)與這個(gè)緩沖區(qū)交換數(shù)據(jù)，而不是直接與磁盤設(shè)備本身交換數(shù)據(jù)。）解析：在一個(gè)段式存儲(chǔ)管理系統(tǒng)中，邏輯地址為32位，其中高16位為段號(hào)，低16位為段內(nèi)偏移，以下是段表（其中的數(shù)據(jù)均為十六進(jìn)制，見(jiàn)下表）。{{B}}段表{{/B}}段基地址長(zhǎng)度保護(hù)01000018C0只讀1119003FF只讀211D001FF讀-寫300禁止訪問(wèn)411F001000讀-寫500禁止訪問(wèn)600禁止訪問(wèn)713000FFF讀-寫以下是代碼段的內(nèi)容:mainsin240pushX[10108]360mov4+(sp),r2244callsin364pushr2248…366…488ret試問(wèn)：（分?jǐn)?shù):7.98）（1）.x的邏輯地址為10108,它的物理地址是多少？（分?jǐn)?shù)：1.33）正確答案：（高16位為段號(hào)，低16位為段內(nèi)偏移，則1為段號(hào)（對(duì)應(yīng)基址11900）,0108為段內(nèi)偏移，則邏輯地址11A08對(duì)應(yīng)的物理地址為基址加段內(nèi)偏移，即11900+0108=11A08。）解析：.棧指針的當(dāng)前地址是70FF0，它的物理地址是多少？（分?jǐn)?shù)：1.33）正確答案：（7為段號(hào)，0FF0為段內(nèi)偏移，13000+0FF0=13FF0。）解析：.第一條指令的邏輯地址和物理地址各為多少？（分?jǐn)?shù)：1.33）正確答案：（邏輯地址240，物理地址為基址加段內(nèi)偏移，即10000+240=10240。）解析：.pushx指令的執(zhí)行過(guò)程：將sP（堆棧寄存器）減4,然后存儲(chǔ)x的值。試問(wèn)x被存儲(chǔ)在什么地方（物理地址）？（分?jǐn)?shù)：1.33）正確答案：（知道SP對(duì)應(yīng)物理地址為13FF0，減4之后為13FEC，即x存儲(chǔ)地址為13FEC。）解析：.callsin指令的執(zhí)行過(guò)程：先將當(dāng)前PC值入棧，然后在PC內(nèi)裝入目標(biāo)PC值。試問(wèn)哪個(gè)值被壓入棧了?新的棧指針的值是多少?新的Pc值是多少？（分?jǐn)?shù)：1.33）正確答案：（PC在調(diào)用callsin命令之后，自增為248,所以邏輯