2009-2010年研究生考試計(jì)算機(jī)綜合真題(附參考答案)

1、.2009年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試卷一、單項(xiàng)選擇題(1-40小題,每小題2分,共80分,下列每小題給出的四個選項(xiàng)中,只有一項(xiàng)符合題目要求,把所選項(xiàng)前的字母填在題后的括號內(nèi).)(1)為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù).該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是(A)棧(B)隊(duì)列(C)樹(D)圖 (2)設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空,元素abcdefg依次進(jìn)入棧S.若每個元素出棧后立即進(jìn)入隊(duì)列Q,且7個元素出隊(duì)的順序是bdcfeag,則棧S的容量至少是(A)1(B)2(C)3(D)4

2、 (3)給定二叉樹圖所示.設(shè)N代表二叉樹的根,L代表根結(jié)點(diǎn)的左子樹,R代表根結(jié)點(diǎn)的右子樹.若遍歷后的結(jié)點(diǎn)序列為3,1,7,5,6,2,4,則其遍歷方式是(A)LNR(B)NRL(C)RLN(D)RNL (4)下列二叉排序樹中,滿足平衡二叉樹定義的是 (A)(B) (C)(D) (5)已知一棵完全二叉樹的第6層(設(shè)根為第1層)有8個葉結(jié)點(diǎn),則完全二叉樹的結(jié)點(diǎn)個數(shù)最多是(A)39(B)52 (C)111(D)119(6)將森林轉(zhuǎn)換為對應(yīng)的二叉樹,若在二叉樹中,結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn),則在原來的森林中,u和v可能具有的關(guān)系是.父子關(guān)系.兄弟關(guān)系.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系(A)只有(B

3、)和 (C)和(D)、和 (7)下列關(guān)于無向連通圖特性的敘述中,正確的是.所有頂點(diǎn)的度之和為偶數(shù).邊數(shù)大于頂點(diǎn)個數(shù)減1.至少有一個頂點(diǎn)的度為1(A)只有(B)只有 (C)和(D)和(8)下列敘述中,不符合m階B樹定義要求的是(A)根節(jié)點(diǎn)最多有m 棵子樹(B)所有葉結(jié)點(diǎn)都在同一層上(C)各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列(D)葉結(jié)點(diǎn)之間通過指針鏈接 (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,19(B)3,5,12,19,20,15,22,8,28(C)3,8,12,5,20,15,

4、22,28,19(D)3,12,5,8,28,20,15,22,19 (10)若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果,則該排序算法只能是(A)起泡排序(B)插入排序(C)選擇排序(D)二路歸并排序(11)馮·諾依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲器中,CPU區(qū)分它們的依據(jù)是(A)指令操作碼的譯碼結(jié)果(B)指令和數(shù)據(jù)的尋址方式(C)指令周期的不同階段(D)指令和數(shù)據(jù)所在的存儲單元(12)一個C語言程序在一臺32位機(jī)器上運(yùn)行.程序中定義了三個變量xyz,其中x和z是int 型,y為short型.當(dāng)x=127,y=-

5、9時,執(zhí)行賦值語句z=x+y后,xyz的值分別是(A)X=0000007FH,y=FFF9H,z=00000076H(B)X=0000007FH,y=FFF9H,z=FFFF0076H(C)X=0000007FH,y=FFF7H,z=FFFF0076H(D)X=0000007FH,y=FFF7H,z=00000076H (13)浮點(diǎn)數(shù)加減運(yùn)算過程一般包括對階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出步驟.設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示,且位數(shù)分別為5位和7位(均含2位符號位).若有兩個數(shù)X=27×29/32,Y=25×5/8,則用浮點(diǎn)加法計(jì)算X+Y的最終結(jié)果是(A)00111 1

6、100010(B)00111 0100010(C)01000 0010001(D)發(fā)生溢出(14)某計(jì)算機(jī)的Cache共有16塊,采用2路組相聯(lián)映射方式(即每組2塊).每個主存塊大小為32字節(jié),按字節(jié)編址.主存129號單元所在主存塊應(yīng)裝入到的Cache 組號是 (A)0(B)2 (C)4(D)6 (15)某計(jì)算機(jī)主存容量為64KB,其中ROM區(qū)為4KB,其余為RAM區(qū),按字節(jié)編址.現(xiàn)要用2K×8位的ROM芯片和4K×4位的RAM芯片來設(shè)計(jì)該存儲器,則需要上述規(guī)格的ROM芯片數(shù)和RAM芯片數(shù)分別是(A)1、15(B)2、15 (C)1、30(D)2、30(16)某機(jī)器字長16

7、位,主存按字節(jié)編址,轉(zhuǎn)移指令采用相對尋址,由兩個字節(jié)組成,第一字節(jié)為操作碼字段,第二字節(jié)為相對位移量字段.假定取指令時,每取一個字節(jié)PC自動加1.若某轉(zhuǎn)移指令所在主存地址為2000H,相對位移量字段的內(nèi)容為06H,則該轉(zhuǎn)移指令成功轉(zhuǎn)以后的目標(biāo)地址是(A)2006H(B)2007H (C)2008H(D)2009H(17)下列關(guān)于RISC的敘述中,錯誤的是(A)RISC普遍采用微程序控制器(B)RISC大多數(shù)指令在一個時鐘周期內(nèi)完成 (C)RISC的內(nèi)部通用寄存器數(shù)量相對CISC多(D)RISC的指令數(shù)、尋址方式和指令格式種類相對CISC少(18)某計(jì)算機(jī)的指令流水線由四個功能段組成,指令流經(jīng)各

8、功能段的時間(忽略各功能段之間的緩存時間)分別是90ns、80ns、70ns 和60ns,則該計(jì)算機(jī)的CPU時鐘周期至少是(A)90ns(B)80ns(C)70ns(D)60ns(19)相對于微程序控制器,硬布線控制器的特點(diǎn)是(A)指令執(zhí)行速度慢,指令功能的修改和擴(kuò)展容易(B)指令執(zhí)行速度慢,指令功能的修改和擴(kuò)展難(C)指令執(zhí)行速度快,指令功能的修改和擴(kuò)展容易(D)指令執(zhí)行速度快,指令功能的修改和擴(kuò)展難(20)假設(shè)某系統(tǒng)總線在一個總線周期中并行傳輸4字節(jié)信息,一個總線周期占用2個時鐘周期,總線時鐘頻率為10MHz,則總線帶寬是(A)10MB/s(B)20MB/s(C)40MB/s(D)80MB

9、/s(21)假設(shè)某計(jì)算機(jī)的存儲系統(tǒng)由Cache和主存組成,某程序執(zhí)行過程中訪存1000次,其中訪問Cache缺失(未命中)50 次,則Cache的命中率是(A)5%(B)9.5%(C)50%(D)95%(22)下列選項(xiàng)中,能引起外部中斷的事件是(A)鍵盤輸入(B)除數(shù)為0(C)浮點(diǎn)運(yùn)算下溢(D)訪存缺頁(23)單處理機(jī)系統(tǒng)中,可并行的是. 進(jìn)程與進(jìn)程. 處理機(jī)與設(shè)備. 處理機(jī)與通道. 設(shè)備與設(shè)備(A)、和 (B)、和 (C)、和 (D)、和(24)下列進(jìn)程調(diào)度算法中,綜合考慮進(jìn)程等待時間和執(zhí)行時間的是(A)時間片輪轉(zhuǎn)調(diào)度算法(B)短進(jìn)程優(yōu)先調(diào)度算法 (C)先來先服務(wù)調(diào)度算法(D)高響應(yīng)比優(yōu)先調(diào)

10、度算法(25)某計(jì)算機(jī)系統(tǒng)中有8臺打印機(jī),有K個進(jìn)程競爭使用,每個進(jìn)程最多需要3臺打印機(jī).該系統(tǒng)可能會發(fā)生死鎖的K的最小值是(A)2(B)3 (C)4(D)5(26)分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是(A)界地址保護(hù)(B)程序代碼保護(hù) (C)數(shù)據(jù)保護(hù)(D)棧保護(hù)(27)一個分段存儲管理系統(tǒng)中,地址長度為32位,其中段號占8位,則最大段長是(A)28字節(jié)(B)216字節(jié) (C)224字節(jié)(D)232字節(jié)(28)下列文件物理結(jié)構(gòu)中,適合隨機(jī)訪問且易于文件擴(kuò)展的是(A)連續(xù)結(jié)構(gòu)(B)索引結(jié)構(gòu)(C)鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定長(D)鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長(29)假設(shè)磁頭當(dāng)前位于第105道,正在向磁道序號增加的

11、方向移動.現(xiàn)有一個磁道訪問請求序列為35,45,12,68,110,180,170,195,采用SCAN調(diào)度(電梯調(diào)度)算法得到的磁道訪問序列是(A)110,170,180,195,68,45,35,12(B)110,68,45,35,12,170,180,195(C)110,170,180,195,12,35,45,68(D)12,35,45,68,110,170,180,195(30)文件系統(tǒng)中,文件訪問控制信息存儲的合理位置是(A)文件控制塊(B)文件分配表(C)用戶口令表(D)系統(tǒng)注冊表(31)設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為1,先建立F1的符號鏈接(軟鏈接)文件F2,再建立F1的硬鏈接文

12、件F3,然后刪除F1.此時,F2和F3的引用計(jì)數(shù)值分別是(A)0、1(B)1、1(C)1、2(D)2、1(32)程序員利用系統(tǒng)調(diào)用打開I/O 設(shè)備時,通常使用的設(shè)備標(biāo)識是(A)邏輯設(shè)備名(B)物理設(shè)備名(C)主設(shè)備號(D)從設(shè)備號(33)在OSI參考模型中,自下而上第一個提供端到端服務(wù)的層次是(A)數(shù)據(jù)鏈路層(B)傳輸層(C)會話層(D)應(yīng)用層(34)在無噪聲情況下,若某通信鏈路的帶寬為3kHz,采用4 個相位,每個相位具有4種振幅的QAM調(diào)制技術(shù),則該通信鏈路的最大數(shù)據(jù)傳輸速率是 (A)12kbps(B)24 kbps (C)48 kbps(D)96 kbps (35)數(shù)據(jù)鏈路層采用了后退N

13、幀(GBN)協(xié)議,發(fā)送方已經(jīng)發(fā)送了編號為07的幀.當(dāng)計(jì)時器超時時,若發(fā)送方只收到0、2、3號幀的確認(rèn),則發(fā)送方需要重發(fā)的幀數(shù)是(A)2(B)3 (C)4(D)5(36)以太網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時使用的PDU地址是(A)目的物理地址(B)目的IP地址 (C)源物理地址(D)源IP地址(37)在一個采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中,傳輸介質(zhì)是一根完整的電纜,傳輸速率為1Gbps,電纜中的信號傳播速度是200 000km/s.若最小數(shù)據(jù)幀長度減少800比特,則最遠(yuǎn)的兩個站點(diǎn)之間的距離至少需要(A)增加160m(B)增加80m (C)減少160m(D)減少80m(38)主機(jī)甲和主機(jī)乙間已建立一個TCP連

14、接,主機(jī)甲向主機(jī)乙發(fā)送了兩個連續(xù)的TCP段,分別包含300字節(jié)和500字節(jié)的有效載荷,第一個段的序列號為200,主機(jī)乙正確接收到兩個段后,發(fā)送給主機(jī)甲的確認(rèn)序列號是(A)500(B)700(C)800(D)1000(39)一個TCP連接總是以1KB的最大段發(fā)送TCP段,發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送.當(dāng)擁塞窗口為16KB時發(fā)生了超時,如果接下來的4個RTT(往返時間)時間內(nèi)的TCP段的傳輸都是成功的,那么當(dāng)?shù)?個RTT時間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時,擁塞窗口大小是(A)7KB(B)8KB(C)9KB(D)16KB(40)FTP客戶和服務(wù)器間傳遞FTP命令時,使用的連接是(A)建立在TCP

15、之上的控制連接(B)建立在TCP之上的數(shù)據(jù)連接(C)建立在UDP之上的控制連接(D)建立在UDP之上的數(shù)據(jù)連接二、綜合應(yīng)用題(41-47小題,共70分,請將答案寫在答題紙指定位置上.)(41)(10分)帶權(quán)圖(權(quán)值非負(fù),表示邊連接的兩頂點(diǎn)間的距離)的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑.假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑,現(xiàn)有一種解決該問題的方法:設(shè)最短路徑初始時僅包含初始頂點(diǎn),令當(dāng)前頂點(diǎn)u為初始頂點(diǎn);選擇離u 最近且尚未在最短路徑中的一個頂點(diǎn)v,加入到最短路徑中,修改當(dāng)前頂點(diǎn)u=v;重復(fù)步驟,直到u是目標(biāo)頂點(diǎn)時為止.請問上述方法能否求得最短路徑?若該方法可行,請證明之;

16、否則,請舉例說明.(42)(15分)已知一個帶有表頭結(jié)點(diǎn)的單鏈表,結(jié)點(diǎn)結(jié)構(gòu)為datalink假設(shè)該鏈表只給出了頭指針list.在不改變鏈表的前提下,請?jiān)O(shè)計(jì)一個盡可能高效的算法,查找鏈表中倒數(shù)第k個位置上的結(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ì)語言描述算法(使用C或C+或JAVA語言實(shí)現(xiàn)),關(guān)鍵之處請給出簡要注釋.(43)(8分)某計(jì)算機(jī)的CPU主頻為500MHz,CPI為5(即執(zhí)行每條指令平均需5個時鐘周期).假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB

17、/s,采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送,以32位為傳輸單位,對應(yīng)的中斷服務(wù)程序包含18條指令,中斷服務(wù)的其他開銷相當(dāng)于2條指令的執(zhí)行時間.請回答下列問題,要求給出計(jì)算過程.(1)在中斷方式下,CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比是多少?(2)當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到5MB/s時,改用DMA方式傳送數(shù)據(jù).假設(shè)每次DMA傳送大小為5000B,且DMA預(yù)處理和后處理的總開銷為500個時鐘周期,則CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比是多少?(假設(shè)DMA與CPU之間沒有訪存沖突)(44)(13分)某計(jì)算機(jī)字長16位,采用16位定長指令字結(jié)構(gòu),部分?jǐn)?shù)據(jù)通路結(jié)構(gòu)如圖所示.圖中所

18、有控制信號為1時表示有效、為0時表示無效.例如控制信號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)容所指主存單元中保存.控制信號圖例三態(tài)門及其控制信號寄存器輸入控制信號數(shù)據(jù)通路結(jié)構(gòu)下表給出了上述指令取值和譯碼階段每個節(jié)拍(時鐘周期)的功能和有效控制信號,請按表中描述方式用表格列出指令執(zhí)行階段每個節(jié)拍的功能和有效控制信號.功能和控制信號時鐘功能有效控制信號C1MAR(PC)P

19、Cout,MARinC2MDRM(MAR)PC(PC)+1MemR,MDRinEPC+1C3IR(MDR)MDRout,IRinC4指令譯碼無(45)(7分)三個進(jìn)程P1、P2、P3互斥使用一個包含N(N>0)個單元的緩沖區(qū).P1每次用produce()生成一個正整數(shù)并用put()送入緩沖區(qū)某一空單元中;P2每次用getodd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計(jì)奇數(shù)個數(shù);P3每次用geteven()從該緩沖區(qū)中取出一個偶數(shù)并用counteven()統(tǒng)計(jì)偶數(shù)個數(shù).請用信號量機(jī)制實(shí)現(xiàn)這三個進(jìn)程的同步與互斥活動,并說明所定義的信號量的含義.要求用偽代碼描述.(46)(8分)

20、請求分頁管理系統(tǒng)中,假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示.頁表內(nèi)容頁號頁框(Page Frame)號有效位(存在位)0101H1102254H1頁面大小為4KB,一次內(nèi)存的訪問時間是100ns,一次快表(TLB)的訪問時間是10ns,處理一次缺頁的平均時間為108ns(已含更新TLB和頁表的時間),進(jìn)程的駐留集大小固定為2,采用最近最少使用置換算法(LRU)和局部淘汰策略.假設(shè)TLB初始為空;地址轉(zhuǎn)換時先訪問TLB,若TLB未命中,再訪問頁表(忽略訪問頁表之后的TLB更新時間);有效位為0表示頁面不在內(nèi)存,產(chǎn)生缺頁中斷,缺頁中斷處理后,返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行.設(shè)虛地址訪問序列2362H、

21、1565H、25A5H,請問:(1)依次訪問上述三個虛地址,各需多少時間?給出計(jì)算過程.(2)基于上述訪問序列,虛地址1565H 的物理地址是多少?請說明理由.(47)(9分)某公司網(wǎng)絡(luò)拓?fù)鋱D如下圖所示,路由器R1通過接口E1、E2分別連接局域網(wǎng)1、局域網(wǎng)2,通過接口L0連接路由器R2,并通過路由器R2連接域名服務(wù)器與互聯(lián)網(wǎng).R1的L0接口的IP地址是;R2的L0接口的IP地址是,L1接口的IP地址是,E0接口的IP地址是;域名服務(wù)器的IP地址是.某公司網(wǎng)絡(luò)拓?fù)鋱DR1 和R2 的路由

22、表結(jié)構(gòu)為:目的網(wǎng)絡(luò)IP地址子網(wǎng)掩碼下一跳IP地址接口(1)將IP地址空間/24 劃分為2個子網(wǎng),分別分配給局域網(wǎng)1、局域網(wǎng)2,每個局域網(wǎng)需分配的IP地址數(shù)不少于120個.請給出子網(wǎng)劃分結(jié)果,說明理由或給出必要的計(jì)算過程.(2)請給出R1的路由表,使其明確包括到局域網(wǎng)1的路由、局域網(wǎng)2的路由、域名服務(wù)器的主機(jī)路由和互聯(lián)網(wǎng)的路由.(3)請采用路由聚合技術(shù),給出R2到局域網(wǎng)1和局域網(wǎng)2的路由.2010年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試卷一、單項(xiàng)選擇題(1-40小題,每小題2分,共80分,下列每小題給出的四個選項(xiàng)中,只有一項(xiàng)符合題目要求,把所選項(xiàng)前的字母填在題后

23、的括號內(nèi).)(1)若元素a、b、c、d、e、f依次進(jìn)棧,允許進(jìn)棧、退棧操作交替進(jìn)行,但不允許連續(xù)三次進(jìn)行退棧工作,則不可能得到的出棧序列是(A)dcebfa(B)cbdaef(C)bcaefd(D)afedcb(2)某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作,但僅允許在一端進(jìn)行出隊(duì)操作,則不可能得到的順順序是(A)bacde(B)dbace(C)dbcae(D)ecbad (3)下列線索二叉樹中(用虛線表示線索),符合后序線索樹定義的是(A)(B)(C)(D) (4)在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹,在新平衡二叉樹中,關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是(A)1

24、3,48(B)24,48 (C)24,53(D)24,90 (5)在一棵度數(shù)為4的樹T中,若有20個度為4的結(jié)點(diǎn),10個度為3的結(jié)點(diǎn),1個度為2的結(jié)點(diǎn),10個度為1的結(jié)點(diǎn),則樹T的葉結(jié)點(diǎn)個數(shù)是(A)41(B)82 (C)113(D)122(6)對n(n>=2)個權(quán)值均不相同的字符構(gòu)成哈弗曼樹,關(guān)于該樹的敘述中,錯誤的是(A)該樹一定是一棵完全二叉樹(B)樹中一定沒有度為1的結(jié)點(diǎn) (C)樹中兩個權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)(D)樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值(7)若無向圖G=(V,E)中含7個頂點(diǎn),則保證圖G在任何情況下都是連通的,則需要的邊數(shù)最少是(A)6(B)15

25、 (C)16(D)21(8)對下圖進(jìn)行拓?fù)渑判?可以得到不同的拓?fù)湫蛄械膫€數(shù)是(A)4(B)3(C)2(D)1 (9)已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列,若采用折半查找法查找一個不存在的元素,則比較次數(shù)最多的是(A)4(B)5(C)6(D)7(10)采用遞歸方式對順序表進(jìn)行快速排序,下列關(guān)于遞歸次數(shù)的敘述中,正確的是(A)遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關(guān)(B)每次劃分后,先處理較長的分區(qū)可以減少遞歸次數(shù)(C)每次劃分后,先處理較短的分區(qū)可以減少遞歸次數(shù)(D)遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)(11)對一組數(shù)據(jù)(2,12,16,88,5,10)進(jìn)行排序,若前三趟排序結(jié)果

26、如下:第一趟:2,12,16,5,10,88第二趟:2,12,5,10,16,88第三趟:2,5,10,12,16,88則采用的排序方法可能是(A)冒泡排序法(B)希爾排序法(C)歸并排序法(D)基數(shù)排序法(12)下列選項(xiàng)中,能縮短程序執(zhí)行時間的措施是. 提高CPU時鐘頻率. 優(yōu)化通過數(shù)據(jù)結(jié)構(gòu). 優(yōu)化通過程序(A)僅和(B)僅和 (C)僅和(D)、 (13)假定有4個整數(shù)用8位補(bǔ)碼分別表示r1=FEH,r2=F2H,r3=90H,r4=F8H,若將運(yùn)算結(jié)果存放在一個8位寄存器中,則下列運(yùn)算會發(fā)生益處的是(A)r1×r2(B)r2×r3(C)r1×r4(D)r2&#

27、215;r4(14)假定變量i,f,d數(shù)據(jù)類型分別為int, float, double(int用補(bǔ)碼表示,float和double用IEEE754單精度和雙精度浮點(diǎn)數(shù)據(jù)格式表示),已知i=785,f=1.5678e3,d=1.5e100,若在32位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式,則結(jié)果為真的是. i=(int)(float)i. f=(float)(int)f. f=(float)(double)f. (d+f)-d=f(A)僅和(B)僅和 (C)僅和(D)僅和(15)假定用若干個2K×4位芯片組成一個8K×8為存儲器,則0B1FH所在芯片的最小地址是(A) 0000H(B)

28、0600H (C) 0700H(D) 0800H(16)下列有關(guān)RAM和ROM得敘述中正確的是. RAM是易失性存儲器,ROM是非易失性存儲器. RAM和ROM都是采用隨機(jī)存取方式進(jìn)行信息訪問. RAM和ROM都可用做Cache. RAM和ROM都需要進(jìn)行刷新(A)僅和(B)僅和 (C)僅、(D)僅、(17)下列命令組合情況,一次訪存過程中,不可能發(fā)生的是(A)TLB未命中,Cache未命中,Page未命中(B)TLB未命中,Cache命中,Page命中(C)TLB命中,Cache未命中,Page命中(D)TLB命中,Cache命中,Page未命中(18)下列寄存器中,反匯編語言程序員可見的是

29、(A)存儲器地址寄存器(MAR)(B)程序計(jì)數(shù)器(PC)(C)存儲區(qū)數(shù)據(jù)寄存器(MDR)(D)指令寄存器(IR)(19)下列不會引起指令流水阻塞的是(A)數(shù)據(jù)旁路(B)數(shù)據(jù)相關(guān)(C)條件轉(zhuǎn)移(D)資源沖突(20)下列選項(xiàng)中的英文縮寫均為總線標(biāo)準(zhǔn)的是(A)PCI、CRT、USB、EISA(B)ISA、CPI、VESA、EISA(C)ISA、SCSI、RAM、MIPS(D)ISA、EISA、PCI、PCI-Express(21)單級中斷系統(tǒng)中,中斷服務(wù)程序執(zhí)行順序是.保護(hù)現(xiàn)場.開中斷.關(guān)中斷.保存斷點(diǎn).中斷事件處理.恢復(fù)現(xiàn)場.中斷返回(A)->->->->(B)->-

30、>->(C)->->->->(D)->->->->(22)假定一臺計(jì)算機(jī)的顯示存儲器用DRAM芯片實(shí)現(xiàn),若要求顯示分辨率為1600*1200,顏色深度為24位,幀頻為85HZ,現(xiàn)實(shí)總帶寬的50%用來刷新屏幕,則需要的顯存總帶寬至少約為(A)245Mbps(B)979Mbps(C)1958Mbps(D)7834Mbps(23)下列選項(xiàng)中,操作S提供的給應(yīng)程序的接口是(A)系統(tǒng)調(diào)用(B)中斷(C)庫函數(shù)(D)原語(24)下列選項(xiàng)中,導(dǎo)制創(chuàng)進(jìn)新進(jìn)程的操作是.用戶登陸成功.設(shè)備分配.啟動程序執(zhí)行(A)僅和(B)僅和 (C)僅和(D)、(25)

31、設(shè)與某資源相關(guān)聯(lián)的信號量初值為3,當(dāng)前值為1,若M表示該資源的可用個數(shù),N表示等待該資源的進(jìn)程數(shù),則M,N分別是(A)0,1(B)1,0 (C)1,2(D)2,0(26)下列選項(xiàng)中,降低進(jìn)程優(yōu)先權(quán)級的合理時機(jī)是(A)進(jìn)程的時間片用完(B)進(jìn)程剛完成I/O,進(jìn)入就緒列隊(duì) (C)進(jìn)程長期處于就緒列隊(duì)(D)進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)(27) 進(jìn)行PO和P1的共享變量定義及其初值為:boolean flag2;int turn=0;flag0=false; flag1=false;若進(jìn)行P0和P1訪問臨界資源的類C代碼實(shí)現(xiàn)如下:void p0() / 進(jìn)程p0void p1() / 進(jìn)程p1 whil

32、e (TRUE)                                          while (TRUE) flag0=TRUE; turn=1; flag0=TRUE;

33、turn=0; While (flag1&&(turn=1) While (flag0&&(turn=0);臨界區(qū); 臨界區(qū);flag0=FALSE; flag1=FALSE; 則并發(fā)執(zhí)行進(jìn)程PO和P1時產(chǎn)生的情況是(A)不能保證進(jìn)程互斥進(jìn)入臨界區(qū),會出現(xiàn)”饑餓”現(xiàn)象(B)不能保證進(jìn)程互斥進(jìn)入臨界區(qū),不會出現(xiàn)”饑餓”現(xiàn)象(C)能保證進(jìn)程互斥進(jìn)入臨界區(qū),會出現(xiàn)”饑餓”現(xiàn)象(D)能保證進(jìn)程互斥進(jìn)入臨界區(qū),不會出現(xiàn)”饑餓”現(xiàn)象(28)某基于動態(tài)分區(qū)存儲管理的計(jì)算機(jī),其主存容量為55Mb(初始為空),采用最佳適配(Best Fit)算法,分配和釋放的順序?yàn)椋悍峙?5Mb

34、,分配30Mb,釋放15Mb,分配6Mb,此時主存中最大空閑分區(qū)的大小是(A)7Mb(B)9Mb(C)10Mb(D)15Mb(29)某計(jì)算機(jī)采用二級頁表的分頁存儲管理方式,按字節(jié)編制,頁大小為210字節(jié),頁表項(xiàng)大小為2字節(jié),邏輯地址結(jié)構(gòu)為頁目錄號頁號頁內(nèi)偏移量邏輯地址空間大小為210頁,則表示整個邏輯地址空間的頁目錄表中包含表項(xiàng)的個數(shù)至少是(A)64(B)128(C)256(D)512(30)設(shè)文件索引節(jié)點(diǎn)中有7個地址項(xiàng),其中4個地址為直接地址索引,1個地址項(xiàng)是二級間接地址索引,每個地址項(xiàng)的大小為4字節(jié),若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié),則可表示的單個文件最大長度是(A)33KB(B

35、)519KB(C)1057KB(D)16513KB(31)設(shè)當(dāng)前工作目錄的主要目的是(A)節(jié)省外存空間(B)節(jié)省內(nèi)存空間(C)加快文件的檢索速度(D)加快文件的讀寫速度(32)本地用戶通過鍵盤登陸系統(tǒng)是,首先獲得鍵盤輸入信息的程序時(A)命令解釋程序(B)中斷處理程序(C)系統(tǒng)調(diào)用程序(D)用戶登錄程序(33)下列選項(xiàng)中,不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是(A)網(wǎng)絡(luò)的層次(B)每一層使用的協(xié)議(C)協(xié)議的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)(D)每一層必須完成的功能(34)在下圖所表示的采用”存儲-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中所有的鏈路的數(shù)據(jù)傳輸速度為100Mbps,分組大小為1000B,其中分組頭大小為20B若主機(jī)H

36、1向主機(jī)H2發(fā)送一個大小為980000的文件,則在不考慮分組拆裝時間和傳播延遲的情況下,從H1發(fā)送到H2接受完為止,需要的時間至少是(A)80ms(B)80.08ms (C)80.16ms(D)80.24ms(35)某自治系統(tǒng)采用RIP協(xié)議,若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含的信息<net1,16>,則可能得出的結(jié)論是(A)R2可以經(jīng)過R1到達(dá)net1,跳數(shù)為17(B)R2可以到達(dá)net1,跳數(shù)為16 (C)R1可以經(jīng)過R2到達(dá)net1,跳數(shù)為17(D)R1不能經(jīng)過R2到達(dá)net1(36) 若路由器R因?yàn)閾砣麃G棄IP分組,則此時R可向發(fā)出該IP分組的源主

37、機(jī)的ICMP報(bào)文件的類型是(A)路由重定向(B)目的不可達(dá) (C)源抑制(D)超時(37)某網(wǎng)絡(luò)的IP地址空間為/24采用長子網(wǎng)劃分,子網(wǎng)掩碼為48,則該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)為(A)32,8(B)32,6 (C)8,32(D)8,30(38)下列網(wǎng)絡(luò)設(shè)備中,能夠抑制網(wǎng)絡(luò)風(fēng)暴的是.中繼器.集線器.網(wǎng)橋.路由器(A)僅和(B)僅 (C) 僅和(D)僅(39)主機(jī)甲和主機(jī)乙之間建立一個TCP連接,TCP最大段長度為1000字節(jié),若主機(jī)甲的當(dāng)前擁塞窗口為4000字節(jié),在主機(jī)甲向主機(jī)乙連續(xù)發(fā)送2個最大段后,成功收到主機(jī)乙發(fā)送的

38、第一段的確認(rèn)段,確認(rèn)段中通告的接收窗口大小為2000字節(jié),則此時主機(jī)甲還可以向主機(jī)乙發(fā)送的最大字節(jié)數(shù)是(A)1000(B)2000(C)3000(D)4000(40)如果本地域名服務(wù)無緩存,當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域名時,用戶主機(jī)本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為(A)1條,1條(B)1條,多條(C)多條,1條(D)多條,多條二、綜合應(yīng)用題(41-47小題,共70分,請將答案寫在答題紙指定位置上.)(41)(10分)將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲到散列表中,散列表的存儲空間是一個下標(biāo)從0開始的一個一維數(shù)組散列,函數(shù)為:H(key)=(key×3

39、)MOD T,處理沖突采用線性探測再散列法,要求裝載因子為0.7.問題: (1)請畫出所構(gòu)造的散列表.(2)分別計(jì)算等概率情況下,查找成功和查找不成功的平均查找長度.(42)(13分)設(shè)將n(n>1)個整數(shù)存放到一維數(shù)組R中.設(shè)計(jì)一個在時間和空間兩方面盡可能高效的算法.將R中的序列循環(huán)左移P(0<P<n)個位置,即將R中的數(shù)據(jù)由(X0,X1,Xn-1)變換為(Xp,Xp-1,Xn-1,X0,X1,Xp-1).要求:(1)給出算法的基本設(shè)計(jì)思想.(2)根據(jù)設(shè)計(jì)思想,采用C或C+或JAVA語言描述算法,關(guān)鍵之處給出注釋.(3)說明你所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度.(43)(1

40、1分) 某計(jì)算機(jī)字節(jié)長為16位,主存地址空間大小為128KB,按字編址.采用字長指令格式,指令名字段定義如下： 15 12 11 6 5 0OPMSRSMdRd源操作數(shù) 目的操作數(shù)轉(zhuǎn)移指令采用相對尋址,相對偏移是用補(bǔ)碼表示,尋址方式定義如下:Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=(Rn)001B寄存器間接(Rn)操作數(shù)=(Rn)010B寄存器間接、自增(Rn)+操作數(shù)=(Rn),(Rn)+1->Rn011B相對D(Rn)轉(zhuǎn)移目標(biāo)地址=(PC)+(Rn)注:(X)表示有存儲地址X或寄存器X的內(nèi)容,請回答下列問題:(1)該指令系統(tǒng)最多可有多少指令?該計(jì)算機(jī)最多有多少個通用

41、寄存器?存儲地址寄存器(MAR)和存儲數(shù)據(jù)寄存器(MDR)至少各需多少位?(2)轉(zhuǎn)移指令的目標(biāo)地址范圍是多少?(3) 若操作碼0010B表示加法操作(助記符為add),寄存器R4和R5得編號分別為100B何101B,R4的內(nèi)容為1234H,R5的內(nèi)容為5678H,地址1234H中的內(nèi)容為5678H,5678H中的內(nèi)容為1234H,則匯編語言為add(R4),(R5) (逗號前為源操作符,逗號后目的操作數(shù))對應(yīng)的機(jī)器碼是什么(用十六進(jìn)制)?該指令執(zhí)行后,哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么?(44)(12分) 某計(jì)算機(jī)的主存地址空間大小為256M,按字節(jié)編址。指令Cache分離,

42、均有8個Cache行,每個Cache行大小為64MB,數(shù)據(jù)Cache采用直接映射方式,現(xiàn)有兩個功能相同的程序A和B,其偽代碼如下:程序A:int a256256;.int sum_array1() int i, j, sum = 0; for (i = 0; i < 256; i+) for (j= 0; j < 256; j+) sum += aij; return sum;程序B:int a256256;.int sum_array2() int i, j, sum = 0; for (j = 0; j < 256; j+) for (i= 0; i < 256;

43、i+) sum += aij; return sum;假定int類型數(shù)據(jù)用32位補(bǔ)碼表示,程序編譯時i,j,sum均分配在寄存器中,數(shù)組a按行優(yōu)先方式存放,其地址為320(十進(jìn)制).請回答,要求說明理由或給出計(jì)算過程. (1)若不考慮用于Cache一致維護(hù)和替換算法的控制位,則數(shù)據(jù)Cache的總?cè)萘繛槎嗌? (2)數(shù)組元素a031和a11各自所在的主存塊對應(yīng)的Cache行號分別是多少(Cache行號從0開始) (3)程序A和B得數(shù)據(jù)訪問命中率各是多少?哪個程序的執(zhí)行時間短?(45)(7分) 假設(shè)計(jì)算機(jī)系統(tǒng)采用CSCAN(循環(huán)掃描)磁盤調(diào)度策略,使用2KB的內(nèi)存空間記錄16384個磁盤的空閑狀態(tài)

44、.(1)請說明在上述條件如何進(jìn)行磁盤塊空閑狀態(tài)的管理.(2)設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn),每個磁道有100個扇區(qū),相臨磁道間的平均移動的時間為1ms.若在某時刻,磁頭位于100號磁道處,并沿著磁道號增大的方向移動(如下圖所示),磁道號的請求隊(duì)列為50,90,30,120對請求隊(duì)列中的每個磁道需讀取1個隨機(jī)分布的扇區(qū),則讀完這個扇區(qū)點(diǎn)共需要多少時間?需要給出計(jì)算過程.(46)(8分) 設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為64KB,按字節(jié)編址.某進(jìn)程最多需要6頁數(shù)據(jù)存儲空間,頁的大小為1KB,操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框.頁號頁框號裝入時間訪問位07130

45、1142301222001391601當(dāng)該進(jìn)程執(zhí)行到時刻260時,要訪問邏輯地址為17CAH的數(shù)據(jù).請回答下列問題:(1)該邏輯地址對應(yīng)的頁號時多少?(2)若采用先進(jìn)先出(FIFO)置換算法,該邏輯地址對應(yīng)的物理地址?要求給出計(jì)算過程.(3)采用時鐘(Clock)置換算法,該邏輯地址對應(yīng)的物理地址是多少?要求給出計(jì)算過程.(設(shè)搜索下一頁的指針按順時針方向移動,且指向當(dāng)前2號頁框,示意圖如下)(47)(9分) 某局域網(wǎng)采用CSMA/CD協(xié)議實(shí)現(xiàn)介質(zhì)訪問控制,數(shù)據(jù)傳輸率為100M/S,主機(jī)甲和主機(jī)已的距離為2KM,信號傳播速度是200000KM/S請回答下列問題,并給出計(jì)算過程.(1)若主機(jī)甲和主

46、機(jī)已發(fā)送數(shù)據(jù)時發(fā)生沖突,則從開始發(fā)送數(shù)據(jù)時刻起,到兩臺主機(jī)均檢測到?jīng)_突時刻為止,最短經(jīng)過多長時間?最長經(jīng)過多長時間?(假設(shè)主機(jī)甲和主機(jī)已發(fā)送數(shù)據(jù)時,其它主機(jī)不發(fā)送數(shù)據(jù)) (2)若網(wǎng)絡(luò)不存在任何沖突與差錯,主機(jī)甲總是以標(biāo)準(zhǔn)的最長以太數(shù)據(jù)幀(1518字節(jié))向主機(jī)已發(fā)送數(shù)據(jù),主機(jī)已每成功收到一個數(shù)據(jù)幀后,立即發(fā)送下一個數(shù)據(jù)幀,此時主機(jī)甲的有效數(shù)據(jù)傳輸速率是多少?(不考慮以太網(wǎng)幀的前導(dǎo)碼)參考答案(2009)：一 選擇題 12345678910BCDBCBADAB11121314151617181920CDDCDCAADB21222324252627282930DADDCACBAA3132333435

47、3637383940BABBCADDCA二 綜合應(yīng)用題 41.該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則， 從A到C的最短路徑為ABC，事實(shí)上其最短路徑為 ADC。 42. （1）算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當(dāng)前節(jié)點(diǎn)的前K個節(jié)點(diǎn)。當(dāng)遍歷 到鏈表的最后一個節(jié)點(diǎn)時，指針P所指向的節(jié)點(diǎn)即為所查找的節(jié)點(diǎn)。 （2）詳細(xì)實(shí)現(xiàn)步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當(dāng) 前遍歷的節(jié)點(diǎn)，指針P指向P1所指向節(jié)點(diǎn)的前K個節(jié)點(diǎn)，如果P1之前沒有K個節(jié)點(diǎn)，那么P指向表頭 節(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少節(jié)點(diǎn)，當(dāng)i>

48、k時，指針p隨著每次遍歷，也向前移動一個節(jié) 點(diǎn)。當(dāng)遍歷完成時，p或者指向表頭就節(jié)點(diǎn)，或者指向鏈表中倒數(shù)第K個位置上的節(jié)點(diǎn)。 （3）算法描述： Int LocateElement(linklist list,int kP1=list->link; P=list; i=1; while(P1) P1=P1->link; i+; if(i>k) p=p->next; /如果i>k,則p也往后移if(p=list)return 0; /說明鏈表沒有k個結(jié)點(diǎn)else printf(“%dn“,p->data); return 1; 43. （1）在中斷方式下，每32位

49、（4B）被中斷一次，故每秒中斷 0.5MB/4B=0.5×106/4=12.5×104次 要注意的是，這里是數(shù)據(jù)傳輸率，所以1MB=106B。因?yàn)橹袛喾?wù)程序包含18條指令，中斷服務(wù)的 其他開銷相當(dāng)于2條指令的執(zhí)行時間，且執(zhí)行每條指令平均需5個時鐘周期，所以，1秒內(nèi)用于中斷 的時鐘周期數(shù)為 （18+2）×5×12.5×104=12.5×106 （2）在DMA方式下，每秒進(jìn)行DMA操作 5MB/5000B=5×106/5000=1×103 次因?yàn)镈MA預(yù)處理和后處理的總開銷為500個時鐘周期，所以1秒 鐘之內(nèi)用于DM

50、A操作的時鐘周期數(shù)為 500×1×103=5×105 故在DMA方式下，占整個CPU時間的百分比是 （5×105）/（500×106）×100%=0.1% 44.指令執(zhí)行階段每個節(jié)拍的功能和有效控制信號如下所示 時鐘功能有效控制信號C5MAR(R1)PCout,MARinC6MDRM(MAR)MemR,MDRinEC7A(R0)R0out,AinC8AC(MDR)+(A)MDRout,Addr,ACinC9MDR(AC)ACout,MDRinC10M(MAR) MDRMDRoutE,MemW45.定義信號量S1控制P1與P2之間的同步

51、；S2控制P1與P3之間的同步；empty控制生產(chǎn)者與消費(fèi)者 之間的同步；mutex控制進(jìn)程間互斥使用緩沖區(qū)。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce();/*生成一個數(shù)*/P(empty);/*判斷緩沖區(qū)是否有空單元*/P(mutex);/*緩沖區(qū)是否被占用*/Put();If x%2=0V(s2);/*如果是偶數(shù)，向P3發(fā)出信號*/elseV(s1);/*如果是奇數(shù)，向P2發(fā)出信號*/V(mutex);/*使用完緩沖區(qū)，釋放*/end.P2:beginP(s1);/*收到P1發(fā)來的信號，已產(chǎn)生一個奇數(shù)*/P(mutex);/*緩沖區(qū)是否