09年計(jì)算機(jī)考研真題解析

2009年全國(guó)碩士研究生入學(xué)統(tǒng)一考試

計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試卷

一、單項(xiàng)選擇題，每小題2分。

1.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(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)均為空，元素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

3.給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)

點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,1,7,5,6,2,4＞則其遍歷方式是（）

A.LRNB.NRLC.RLND.RNL

4.下列二叉排序樹中，滿足平衡二叉樹定義的是（）

5.已知?棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹

的結(jié)點(diǎn)個(gè)數(shù)最多是（）

A.39B.52C.IllD.119

6.將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，

則在原來的森林中，u和v可能具有的關(guān)系是（）

I.父子關(guān)系工I.兄弟關(guān)系III.U的父結(jié)點(diǎn)與V的父結(jié)點(diǎn)是兄弟關(guān)系

A.只有工工B.I和工IC.I和IIID.1、II和I工工

7.下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（）

I.所有頂點(diǎn)的度之和為偶數(shù)

口.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1

:ni.至少有一個(gè)頂點(diǎn)的度為1

A.只有1B.只有IIC.I和IID.I和III

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,19B.3,5,12,19,20,15,22,8,28

C.3,8,12,5,20,15,22,28,19D.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)制形式存放在存儲(chǔ)器中,CPU區(qū)分它們的依

據(jù)是()

(A)指令操作碼的譯碼結(jié)果(B)指令和數(shù)據(jù)的尋址方式

(C)指令周期的不同階段(D)指令和數(shù)據(jù)所在的存儲(chǔ)單元

(12)一個(gè)C語(yǔ)言程序在一臺(tái)32位機(jī)器上運(yùn)行.程序中定義了三個(gè)變量xyz,其中x和z是

int型,y為short型.當(dāng)x=127,y=-9時(shí),執(zhí)行賦值語(yǔ)句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)算過程?般包括對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出步驟.設(shè)浮點(diǎn)

數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示,且位數(shù)分別為5位和7位(均含2位符號(hào)位).若有兩個(gè)數(shù)

X=27x29/32,Y=25x5/8,則用浮點(diǎn)加法計(jì)算X+Y的最終結(jié)果是()

(A)OOHl1100010(B)OOlll0100010

(C)OIOOO0010001(D)發(fā)生溢出

(14)某計(jì)算機(jī)的Cache共有16塊，采用2路組相聯(lián)映射方式(即每組2塊).每個(gè)主存塊大

小為32字節(jié)，按字節(jié)編址.主存129號(hào)單元所在主存塊應(yīng)裝入到的Cache組號(hào)是()

(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ì)該存儲(chǔ)器，則需要上述規(guī)格的ROM芯片

數(shù)和RAM芯片數(shù)分別是()

(A)l、15(B)2、15(C)k30(D)2、30

(16)某機(jī)器字長(zhǎng)16位，主存按字節(jié)編址，轉(zhuǎn)移指令采用相對(duì)尋址，由兩個(gè)字節(jié)組成,第一字

節(jié)為操作碼字段,第二字節(jié)為相對(duì)位移量字段.假定取指令時(shí),每取一個(gè)字節(jié)PC自動(dòng)加1.若某

轉(zhuǎn)移指令所在主存地址為2000H,相對(duì)位移量字段的內(nèi)容為06H,則該轉(zhuǎn)移指令成功轉(zhuǎn)以后的

目標(biāo)地址是()

(A)2006H(B)2007H(Q2008H(D)2009H

(17)下列關(guān)于RISC的敘述中，錯(cuò)誤的是()

(A)RISC普遍采用微程序控制器

(B)R1SC大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成

(C)RISC的內(nèi)部通用寄存器數(shù)量相對(duì)CISC多

(D)RISC的指令數(shù)、尋址方式和指令格式種類相對(duì)CISC少

(18)某計(jì)算機(jī)的指令流水線由四個(gè)功能段組成，指令流經(jīng)各功能段的時(shí)間(忽略各功能段

之間的緩存時(shí)間)分別是90ns、80ns、70ns和60ns,則該計(jì)算機(jī)的CPU時(shí)鐘周期至少是()

(A)90ns(B)80ns(C)70ns(D)60ns

(19)相對(duì)于微程序控制器，硬布線控制器的特點(diǎn)是()

(A)指令執(zhí)行速度慢,指令功能的修改和擴(kuò)展容易

(B)指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展難

(C)指令執(zhí)行速度快,指令功能的修改和擴(kuò)展容易

(D)指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難

(20)假設(shè)某系統(tǒng)總線在一個(gè)總線周期中并行傳輸4字節(jié)信息，一個(gè)總線周期占用2個(gè)時(shí)鐘

周期，總線時(shí)鐘頻率為10MHz,則總線帶寬是()

(A)10MB/s(B)20MB/s(C)40MB/s(D)80MB/s

(21)假設(shè)某計(jì)算機(jī)的存儲(chǔ)系統(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)訪存缺頁(yè)

(23)單處理機(jī)系統(tǒng)中，可并行的是()

1.進(jìn)程與進(jìn)程n.處理機(jī)與設(shè)備

III.處理機(jī)與通道IV.設(shè)備與設(shè)備

(A)I、n和in(B)I、n和w

(C)I、in和w(D)H、iii和w

(24)下列進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是()

(A)時(shí)間片輪轉(zhuǎn)調(diào)度算法(B)短進(jìn)程優(yōu)先調(diào)度算法

(C)先來先服務(wù)調(diào)度算法(D)高響應(yīng)比優(yōu)先調(diào)度算法

(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)2(B)3(C)4(D)5

(26)分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是()

(A)界地址保護(hù)(B)程序代碼保護(hù)

(C)數(shù)據(jù)保護(hù)(D)棧保護(hù)

(27)一個(gè)分段存儲(chǔ)管理系統(tǒng)中，地址長(zhǎng)度為32位，其中段號(hào)占8位,則最大段長(zhǎng)是()

(AR8字節(jié)(B)216字節(jié)(CR24字節(jié)(DR32字節(jié)

(28)下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問且易于文件擴(kuò)展的是()

(A)連續(xù)結(jié)構(gòu)(B)索引結(jié)構(gòu)

(C)鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定長(zhǎng)(D)鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長(zhǎng)

(29)假設(shè)磁頭當(dāng)前位于第1()5道，正在向磁道序號(hào)增加的方向移動(dòng).現(xiàn)有一個(gè)磁道訪問請(qǐng)

求序列為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)中，文件訪問控制信息存儲(chǔ)的合理位置是()

(A)文件控制塊(B)文件分配表

(C)用戶口令表(D)系統(tǒng)注冊(cè)表

(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、1(B)l、1(C)l、2(D)2、1

(32)程序員利用系統(tǒng)調(diào)用打開I/O設(shè)備時(shí)，通常使用的設(shè)備標(biāo)識(shí)是()

(A)邏輯設(shè)備名(B)物理設(shè)備名(C)主設(shè)備號(hào)(D)從設(shè)備號(hào)

(33)在OSI參考模型中,自下而上第一個(gè)提供端到端服務(wù)的層次是()

(A)數(shù)據(jù)鏈路層(B)傳輸層(C)會(huì)話層(D)應(yīng)用層

(34)在無(wú)噪聲情況下，若某通信鏈路的帶寬為3kHz,采用4個(gè)相位，每個(gè)相位具有4種振

幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是()

(A)12kbps(B)24kbps(C)48kbps(D)96kbps

(35)數(shù)據(jù)鏈路層采用了后退N幀(GBN)協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號(hào)為0~7的幀.當(dāng)計(jì)時(shí)

器超時(shí)時(shí)，若發(fā)送方只收到0、2、3號(hào)幀的確認(rèn),則發(fā)送方需要重發(fā)的幀數(shù)是()

(A)2(B)3(C)4(D)5

(36)以太網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時(shí)使用的PDU地址是()

(A)目的物理地址(B)目的IP地址(C)源物理地址(D)源IP地址

(37)在一個(gè)采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為

IGbps,電纜中的信號(hào)傳播速度是200OOOkm/s.若最小數(shù)據(jù)幀長(zhǎng)度減少800比特,則最遠(yuǎn)的兩個(gè)

站點(diǎn)之間的距離至少需要()

(A)增加160m(B)增加80m(C)減少160m(D)減少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)500(B)700(C)800(D)1000

(39)一個(gè)TCP連接總是以1KB的最大段發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送.當(dāng)

擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，如果接下來的4個(gè)RTT(往返時(shí)間)時(shí)間內(nèi)的TCP段的傳輸

都是成功的，那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小

是()

(A)7KB(B)8KB(C)9KB(D)16KB

(40)FTP客戶和服務(wù)器間傳遞FTP命令時(shí)，使用的連接是()

(A)建立在TCP之上的控制連接(B)建立在TCP之上的數(shù)據(jù)連接

(C)建立在UDP之上的控制連接(D)建立在UDP之上的數(shù)據(jù)連接

二、綜合應(yīng)用題(41Y7小題，共70分，請(qǐng)將答案寫在答題紙指定位置上.)

(41)(10分)帶權(quán)圖(權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離)的最短路徑問題是找出從初

始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑.假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種

解決該問題的方法：

①設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；

②選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v,加入到最短路徑中,修改當(dāng)前頂點(diǎn)

u=v;

③重復(fù)步驟②，直到U是目標(biāo)頂點(diǎn)時(shí)為止.

請(qǐng)問上述方法能否求得最短路徑?若該方法可行，請(qǐng)證明之;否則，請(qǐng)舉例說明.

(42)(15分)已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為

data|link

假設(shè)該鏈表只給出了頭指針list.在不改變鏈表的前提下，請(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)要注釋.

(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ù)的其他開銷相當(dāng)于2條指令的執(zhí)行時(shí)間.

請(qǐng)回答下列問題，要求給出計(jì)算過程.

(1)在中斷方式下,CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少？

(2)當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到5MB/S時(shí)，改用DMA方式傳送數(shù)據(jù).假設(shè)每次DMA傳送

大小為5000B,且DMA預(yù)處理和后處理的總開銷為500個(gè)時(shí)鐘周期，則CPU用于該外設(shè)I/O

的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少?(假設(shè)DMA與CPU之間沒有訪存沖突)

(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”的功能為(RO)+((R1))—(RI),即將R0中的數(shù)據(jù)與R1的

內(nèi)容所指主存單元的數(shù)據(jù)相加,并將結(jié)果送入R1的內(nèi)容所指主存單元中保存.

控制信號(hào)圖例

A——三態(tài)門及其控制信號(hào)

4—寄存器輸入控制信號(hào)

數(shù)據(jù)通路結(jié)構(gòu)

下表給出了上述指令取值和譯碼階段每個(gè)節(jié)拍(時(shí)鐘周期)的功能和有效控制信號(hào)，請(qǐng)按

表中描述方式用表格列出指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào).

功能和控制信號(hào)

時(shí)鐘功能有效控制信號(hào)

C1MAR—(PC)PCout,MARin

C2MDR-M(MAR)MemR,MDRinE

PC-(PC)+1PC+1

C3IR—(MDR)MDRoutJRin

C4指令譯碼無(wú)

(45)(7分)三個(gè)進(jìn)程Pl、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),并說明

所定義的信號(hào)量的含義.要求用偽代碼描述.

(46)(8分)請(qǐng)求分頁(yè)管理系統(tǒng)中，假設(shè)某進(jìn)程的頁(yè)表內(nèi)容如下表所示.

頁(yè)表內(nèi)容

頁(yè)號(hào)頁(yè)框(PageFrame)號(hào)有效位(存在位)

0101H1

1一0

2254H1

頁(yè)面大小為4KB,一次內(nèi)存的訪問時(shí)間是100ns,一次快表(TLB)的訪問時(shí)間是10ns,處理

一次缺頁(yè)的平均時(shí)間為108ns(已含更新TLB和頁(yè)表的時(shí)間)，進(jìn)程的駐留集大小固定為2,采用

最近最少使用置換算法(LRU)和局部淘汰策略.假設(shè)①TLB初始為空;②地址轉(zhuǎn)換忖先訪問

TLB,若TLB未命中，再訪問頁(yè)表(忽略訪問頁(yè)表之后的TLB更新時(shí)間);③有效位為0表示頁(yè)

面不在內(nèi)存,產(chǎn)生缺頁(yè)中斷，缺頁(yè)中斷處理后，返回到產(chǎn)生缺頁(yè)中斷的指令處重新執(zhí)行.設(shè)虛地

址訪問序列2362H、1565H、25A5H,請(qǐng)問：

(1)依次訪問上述三個(gè)虛地址，各需多少時(shí)間?給出計(jì)算過程.

(2)基于上述訪問序列,虛地址1565H的物理地址是多少?請(qǐng)說明理由.

(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地址是202,118.3.1;域名服務(wù)器的IP地址是.

R1和R2的路由表結(jié)構(gòu)為:

目的網(wǎng)絡(luò)IP地址子網(wǎng)掩碼下一跳IP地址接口

(1)將IP地址空間/24劃分為2個(gè)子網(wǎng)，分別分配給局域網(wǎng)1、局域網(wǎng)2,每個(gè)

局域網(wǎng)需分配的IP地址數(shù)不少于120個(gè).請(qǐng)給出子網(wǎng)劃分結(jié)果，說明理由或給出必要的計(jì)算過

程.

(2)請(qǐng)給出R1的路由表，使其明確包括到局域網(wǎng)1的路由、局域網(wǎng)2的路由、域名服務(wù)

器的主機(jī)路由和互聯(lián)網(wǎng)的路由.

(3)請(qǐng)采用路由聚合技術(shù)，給出R2到局域網(wǎng)1和局域網(wǎng)2的路由.

2009年計(jì)算機(jī)考研試題詳細(xì)解析

1.B

分析：打印機(jī)取出數(shù)據(jù)的順序與數(shù)據(jù)被寫入緩沖區(qū)的順序相同，為先進(jìn)先出結(jié)構(gòu)，即隊(duì)

列。

2.C

分析：當(dāng)a,c,d同時(shí)在S中及a,e,f同時(shí)在S中時(shí)，棧的存儲(chǔ)量達(dá)到最大值，因此

容量至少為3。

3.D

分析：根據(jù)遍歷結(jié)果，很容易看出右子樹先被訪問，雖有是子樹的根將讀點(diǎn)，最后是左

子樹，相當(dāng)于左右顛倒的中序遍歷。

4.B

分析：根據(jù)平衡二叉樹的定義，任意結(jié)點(diǎn)左右子樹的高度差的絕對(duì)值不超過1。選項(xiàng)

A,C,D的根結(jié)點(diǎn)左右子樹差都不滿足定義。

5.C

分析：根據(jù)完全二叉樹的定義，此樹的前6層應(yīng)該是滿二叉樹，共有26-1=63個(gè)結(jié)點(diǎn)：

第6層有8個(gè)葉子結(jié)點(diǎn)，說明另外32-8=24個(gè)結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，最多各有2個(gè)孩子結(jié)點(diǎn),

而該樹不可能有第8層存在，所以結(jié)點(diǎn)總數(shù)最多時(shí)63+24X2=111個(gè)結(jié)點(diǎn).

6.B

分析：若u和V的關(guān)系如圖a所示，則根據(jù)左孩子右兄弟原則，v跟自己的父結(jié)點(diǎn)是

兄弟關(guān)系，都是u的孩子。所以圖a對(duì)應(yīng)的是工：父子關(guān)系。

若u和v的關(guān)系如圖b所示，則根據(jù)左孩子右兄弟原則，v跟自己的父結(jié)點(diǎn)以及u是

兄弟關(guān)系，都是u的父結(jié)點(diǎn)的孩子。所以圖b對(duì)應(yīng)的是"兄弟關(guān)系。

圖b

若在森林中（注意不是在二叉樹中）U的父結(jié)點(diǎn)與V的父結(jié)點(diǎn)是兄弟關(guān)系。則轉(zhuǎn)換成二

叉樹后，它們形成單邊右斜的關(guān)系，而U和V分別在他們各自的左子樹內(nèi)，不可能在同一

條路徑上，所以工工工是不可能的。

7.A

分析：三個(gè)命題中，工工顯然不對(duì)，當(dāng)圖是一棵樹的時(shí)候，正好有邊數(shù)等于頂點(diǎn)個(gè)數(shù)減

K工I工也不對(duì)，例如一個(gè)連接所有頂點(diǎn)的環(huán)，邊數(shù)等于頂點(diǎn)個(gè)數(shù)，每個(gè)頂點(diǎn)的度都是2。

8.D

分析:D項(xiàng)是B+樹的特點(diǎn)，而不是B樹的特點(diǎn)。

9.A

圖a原始堆圖b插入3圖c調(diào)整結(jié)束

10.B

分析：若是起泡排序或者選擇排序，則第二趟后應(yīng)有2個(gè)最大或者最小的元素正確排

列，而結(jié)果不符。二路歸并排序第二趟后，應(yīng)形成2個(gè)長(zhǎng)度為4的有序子序列，結(jié)果也不

符合。所以答案只能是插入排序。兩次插入后，前3個(gè)數(shù)子的順序是對(duì)的。

11.C

指令與數(shù)據(jù)都是以同樣的方式存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)器中。處理器先讀入指令，根據(jù)指令再

讀/寫數(shù)據(jù)。

12.D

z顯然應(yīng)該是正確的。對(duì)于16進(jìn)制負(fù)數(shù)的補(bǔ)碼換算，可以用FFFG去減去負(fù)數(shù)絕對(duì)值,

其中G表示16,只要算到最右邊一個(gè)非0位即可。

13.D

1110100+10100=10001000,規(guī)格化后,指數(shù)=+8,尾數(shù)=1.10001。指數(shù)+8,溢出，

本例如果尾數(shù)按照工EEE754的原碼方式，應(yīng)該還是可以表示：指數(shù)=+7,尾數(shù)=1.0001。

整數(shù)部分的1不必記憶。

14.C

129=(10000001)2塊內(nèi)32字節(jié)5位；cache總共16塊8組，需要3位索引；其余

為Tag。因此1000001->0,100,00001,即組號(hào)為4,組內(nèi)偏移為1,Tag為0。

15.D

這類計(jì)算注意單位一致，位或字節(jié)或字。芯片數(shù)=總要求容量/單片容量。

ROM：4KB/2KB=2；RAM:(64K-4K)X8b/(4KX4b)=30/?

16.C

指令的相對(duì)尋址都是以當(dāng)前指令的下一條指令為基準(zhǔn)點(diǎn)確定位移量的。當(dāng)前轉(zhuǎn)移指令為

2字節(jié)，下?一條指令地址為2002H,加上位移量，為2008Ho

17.A

RISC講究的是指令的短小精悍，大多在一個(gè)時(shí)鐘周期內(nèi)完成。所有操作數(shù)都在寄存器

內(nèi)，所以需要較多的寄存器。相對(duì)來說尋址方式較少，指令的格式，種類也較少。微程序需

要多次讀控制存儲(chǔ)器CM,即使用Cache,執(zhí)行也比較慢，簡(jiǎn)單控制還是直接用組合邏輯較

好。

18.A

每個(gè)CPU周期應(yīng)該考慮到所有的操作，自然應(yīng)該選最長(zhǎng)的。

19.D

微程序相當(dāng)于軟件，每條指令相當(dāng)于若干條微指令，就要讀若干次控制存儲(chǔ)器CM,自

然就比較慢。但存儲(chǔ)器的內(nèi)容修改方便，所以擴(kuò)展相對(duì)容易。而硬布線相當(dāng)于硬件，剛好相

反：執(zhí)行塊，修改難。

20.B

2個(gè)時(shí)鐘4字節(jié)，每個(gè)時(shí)鐘周期2字節(jié)，2BX10MHz=20MB/s

21.D

總是大一點(diǎn)的命中率好。太低就沒必要使用Cache。

命中|率=命|中次數(shù)/,總訪可次數(shù)=（1000-50）/1000=950/1000=95,

22.A

只有鍵盤是外設(shè)。B,C是處理器內(nèi)部異常，D屬于操作系統(tǒng)。

23.D

分析：在單處理機(jī)不考慮多核情況下，某時(shí)刻處理機(jī)只能執(zhí)行一個(gè)進(jìn)程，所以進(jìn)程與進(jìn)

程之間不能并行執(zhí)行。處理器，通道，設(shè)備都能并行執(zhí)行。

24.D

分析：高響應(yīng)比優(yōu)先調(diào)度算法中，計(jì)算每個(gè)進(jìn)程，響應(yīng)比最高的先獲得CPU,響應(yīng)比

計(jì)算公式：響應(yīng)比=（進(jìn)程執(zhí)行時(shí)間+進(jìn)程等待時(shí)間）/進(jìn)程執(zhí)行時(shí)間。

25.C

分析：假設(shè)k=3,3個(gè)進(jìn)程共享8臺(tái)打印機(jī)，每個(gè)進(jìn)程最多可以請(qǐng)求3臺(tái)打印機(jī)，若3

個(gè)進(jìn)程都分別得到2臺(tái)打印機(jī)，系統(tǒng)還剩下2臺(tái)打印機(jī)，接下去無(wú)論哪個(gè)進(jìn)程申請(qǐng)打印機(jī),

都可以得到滿足，3個(gè)進(jìn)程都可以順利執(zhí)行完畢，這種情況下不會(huì)產(chǎn)生死鎖。假設(shè)k=4,4

個(gè)進(jìn)程共享8臺(tái)打印機(jī)，都得不到滿足，產(chǎn)生了互相等待，可能會(huì)發(fā)生死鎖。因此答案是C。

26.A

分析：B,C,D都不是存儲(chǔ)保護(hù)的措施。使用界限寄存器可以實(shí)現(xiàn)分區(qū)分配內(nèi)存管理方

法的存儲(chǔ)保護(hù)。

27.C

分析：段式存儲(chǔ)管理系統(tǒng)中的邏輯地址分成兩部分：段號(hào)和位移量。段號(hào)8位，則位

移量用24位來表示，位移量的大小決定了每段的長(zhǎng)度，所以每段的最大長(zhǎng)度是22八

28.C

分析：根據(jù)外存儲(chǔ)分配方法，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)適合順序訪問，不適合隨機(jī)訪問；連續(xù)和索

引存儲(chǔ)結(jié)構(gòu)適合隨機(jī)訪問，但連續(xù)存儲(chǔ)結(jié)構(gòu)不適合文件的動(dòng)態(tài)增長(zhǎng)，索引存儲(chǔ)結(jié)構(gòu)適合隨機(jī)

訪問。

29.C

分析：SCAN算法的基本思想：磁頭從磁盤的一端開始向另一端移動(dòng)，沿途響應(yīng)訪問請(qǐng)

求，直到到達(dá)了磁盤的另一端，此時(shí)磁頭反方向移動(dòng)并繼續(xù)響應(yīng)服務(wù)請(qǐng)求。根據(jù)SCAN算法，

可以得到訪問序列是Ao

30.A

分析：文件系統(tǒng)為實(shí)現(xiàn)“按名存取”，為每個(gè)文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，

這個(gè)數(shù)據(jù)結(jié)構(gòu)稱為文件控制塊FCB。未見控制塊FCB包含文件名，文件物理地址，訪問權(quán)

限等信息。

31.B

分析：在Unix/Linux系統(tǒng)中，創(chuàng)建符號(hào)鏈接文件時(shí)，該文件有自己的inode結(jié)構(gòu)，

而硬鏈接文件和FI標(biāo)文件共享inode結(jié)構(gòu)；在刪除文件時(shí)，引用計(jì)數(shù)器減1,當(dāng)引用計(jì)數(shù)

器為0時(shí)，才真正刪除，并釋放inode結(jié)構(gòu)。創(chuàng)建文件F2后，其文件引用計(jì)數(shù)器為1；

創(chuàng)建文件F3后，其文件引用計(jì)數(shù)器為2,刪除文件F1,引用計(jì)數(shù)器減1,此時(shí)文件F3引

用計(jì)數(shù)器為lo所以F1和F3兩個(gè)文件引用計(jì)數(shù)器都是lo

32.A

分析:在操作系統(tǒng)的設(shè)備管理中，用戶程序不直接使用物理設(shè)備名（或設(shè)備的物理地址），

而使用邏輯設(shè)備名；系統(tǒng)在實(shí)際執(zhí)行時(shí)，將邏輯設(shè)備名轉(zhuǎn)換為某個(gè)具體的物理設(shè)備名，實(shí)施

工/0操作。邏輯設(shè)備是實(shí)際物理設(shè)備屬性的抽象，它并不限于某個(gè)具體設(shè)備。

33.B

分析：在osi參考模型中，在傳輸層提供了端口號(hào)，實(shí)現(xiàn)了為應(yīng)用進(jìn)程之間提供了端到

端的邏輯通信，故選【B］。雖然選項(xiàng)中沒有網(wǎng)絡(luò)層，但是還是要提示一下，網(wǎng)絡(luò)層僅僅是為

主機(jī)之間提供邏輯通信。

34.B

分析：假設(shè)原始信號(hào)中的最大頻率為f,那么采樣頻率f都必須大于等于f的兩倍，才

能保證采樣后的數(shù)字信號(hào)完整保留原始信號(hào)的信息。題目中已經(jīng)給出最大頻率為3kHz（在

模擬信號(hào)中，帶寬可以看成是最大頻率），所以需要6kHz的采樣頻率；題目中說采用4個(gè)相

位，并且每個(gè)相位有4種振幅，也就是說可以表示16種狀態(tài)，故一個(gè)碼元可以攜帶4bit

（24=16）的信息，所以該通信鏈路的最大數(shù)據(jù)傳輸速率Cmax=fSffXlog216=24kbps,故選【B】。

35.C

分析：想要準(zhǔn)確的做出該題需要懂得兩個(gè)知識(shí)點(diǎn)：（1）只要收到ACKn就認(rèn)為前面n：

幀一定全部收到；（2）后退N幀重發(fā)思想：發(fā)送方超時(shí)后需重發(fā)該出借幀及其后續(xù)所有的

幀。從題中我們可以看出收到了3號(hào)確認(rèn)幀（盡管沒有收到1號(hào)確認(rèn)幀），就可以認(rèn)為0,1,

2,3號(hào)幀接收方都已經(jīng)收到，而4號(hào)幀的確認(rèn)沒有收到，發(fā)送方就應(yīng)該發(fā)送4號(hào)幀以及后

續(xù)所有的幀，即重傳4,5,6,7號(hào)幀，即幀數(shù)為4,故選【C】。

其實(shí)這道題目如果將選項(xiàng)D改為7,這樣就更具有迷惑性，相信會(huì)有不少考生認(rèn)為應(yīng)該

從1號(hào)幀開始重傳，即需要重傳1，2,3,4,5,6,7共計(jì)7幀，這樣就會(huì)誤選D,但是一

看到選項(xiàng)沒有7,估計(jì)才會(huì)想到只要收到ACKn就認(rèn)為前面n-l幀一定全部收到。

需要提醒的一點(diǎn)：前面我們講過某個(gè)幀的確認(rèn)沒有收到是否一定要重發(fā)此幀？這個(gè)題目恰好

是一個(gè)反例，在發(fā)送方超時(shí)之前收到了比1號(hào)幀更高的確認(rèn)，所以不需要重發(fā)1號(hào)幀。

補(bǔ)充一道大綱樣題：在選擇重傳協(xié)議中，當(dāng)幀的序號(hào)字段為3bit時(shí)，且接收窗口與發(fā)送窗

口尺寸相同，發(fā)送窗口的最大值為（）

A.2B.4C.6D.8

【解析】本題考查了選擇重傳協(xié)議，假設(shè)幀的序號(hào)字段為nbit時(shí)，選擇重傳協(xié)議的發(fā)

送窗口最大尺寸為：2nl；將n=3代入，可以得到答案【B】。

36.A

分析：首先交換機(jī)是工作在數(shù)據(jù)鏈路層的設(shè)備，所以進(jìn)行轉(zhuǎn)發(fā)決策時(shí)，是不可能使用IP

地址的，故排序選項(xiàng)B和D；其次，在進(jìn)行轉(zhuǎn)發(fā)的過程中，都是使用目的地址，不可能用源

地址進(jìn)行轉(zhuǎn)發(fā)，故選【A】。

另一種思路：以太網(wǎng)交換機(jī)其實(shí)就是多端口網(wǎng)橋，網(wǎng)橋是根據(jù)目的物理地址轉(zhuǎn)發(fā)幀的，

所以以太網(wǎng)交換機(jī)也是根據(jù)FI的物理地址轉(zhuǎn)發(fā)幀的。

37.D

分析：首先可以計(jì)算出減少800bit后，節(jié)省了多少發(fā)送時(shí)間，即800bit/1000000

也就是說最大往返時(shí)延可以允許減少或者說最大端到端單

000bit/s=0.8X10-6S,0.8X10-65,

程時(shí)延可以減少0.4X10%,要使得單程時(shí)延減少，且傳播速度不變，只有將最遠(yuǎn)的兩個(gè)站

點(diǎn)之間的距離減少才能滿足要求，并且需要減少：0.4X10-6sX200000000m/s=80m,故選【D】。

補(bǔ)充一道大綱樣題：根據(jù)CSMA/CD協(xié)議的工作原理，下列情形中，需要提高最短幀長(zhǎng)度的

是（）

A.網(wǎng)絡(luò)傳輸速率不變，沖突域的最大距離變短

B.沖突域的最大距離不變，網(wǎng)絡(luò)傳輸速率提高

C.上層協(xié)議使用TCP的概率增加

D.在沖突域不變的情況下減少線路中的中繼器數(shù)量

【解析】本題仍然是考查最短幀的相關(guān)知識(shí)；如果網(wǎng)絡(luò)傳輸速率不變（網(wǎng)絡(luò)傳輸速率是

指發(fā)送速率，不是指在信道的傳播速率），沖突域的最大距離變短，說明來回往返時(shí)延小了，

也就是說發(fā)送比特的時(shí)間也縮短了，且發(fā)送速率不變，所以最短幀必定要變短，故排除A

選項(xiàng)；如果沖突域的最大距離不變，網(wǎng)絡(luò)傳輸速率提高，此時(shí)也就是說發(fā)送比特的時(shí)間不變，

但是發(fā)送速率提高了，所以此時(shí)最短幀肯定變長(zhǎng)了，故選【B】。選項(xiàng)C和D是迷惑選項(xiàng)，

沒有任何關(guān)系。

38.D

分析：ACKn的意思是前n-l號(hào)的幀都已經(jīng)收到，請(qǐng)發(fā)送方繼續(xù)發(fā)送第n號(hào)幀。在這題

中，主機(jī)甲發(fā)送的第一個(gè)段的序號(hào)為200到499,第二段的序列號(hào)為500到999,主機(jī)乙正

確接收到兩個(gè)段后，應(yīng)該希望主機(jī)甲接下來發(fā)送1000號(hào)幀，所以主機(jī)乙發(fā)送給主機(jī)甲的確

認(rèn)序列號(hào)是1000,故選【D1

39.C

分析：當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，后面?zhèn)鬏數(shù)拈T限值將變成8KB,后面4次成

功傳輸將分別以1個(gè)報(bào)文段、2個(gè)報(bào)文段、4個(gè)報(bào)文段、8個(gè)報(bào)文段作為擁塞窗口的大小，

其中第四次成功的傳輸已經(jīng)達(dá)到了門限值8KB,第五次開始擁塞窗口就需要線性增長(zhǎng)，等于

8KB+1KB=9KB,故選【口。

40.A

分析：首先FTP協(xié)議需要保證可靠，故需要用到可靠的TCP協(xié)議，而不使用不可靠的

UDP協(xié)議，故排除選項(xiàng)C和D；顯然傳輸命令用控制連接，傳輸數(shù)據(jù)用數(shù)據(jù)連接，故選【A】。

41

分析：該方法求得的路徑不一定是最短路徑。例如，對(duì)于下圖所示的帶權(quán)圖，如果按照

題中的原則，從A到C的最短路徑為A-B-C,事實(shí)上其最短路徑為A-.D-.Co

42

(1)算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當(dāng)前結(jié)點(diǎn)的前k個(gè)

結(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)結(jié)點(diǎn)時(shí)，指針P所指向的結(jié)點(diǎn)即為所查找的結(jié)點(diǎn)。

(2)詳細(xì)實(shí)現(xiàn)步驟：增加兩個(gè)指針變量和?個(gè)整型變量，從鏈表頭向后遍歷，其中指

針pl指向當(dāng)前遍歷的結(jié)點(diǎn)，指針p指向pl所指向結(jié)點(diǎn)的前k個(gè)結(jié)點(diǎn)，如果pl之前沒

有k個(gè)結(jié)點(diǎn)，那么p指向表頭結(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少個(gè)結(jié)點(diǎn)，當(dāng)i>k時(shí),

指針p隨著每次遍歷，也向前移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)遍歷完成時(shí)，p或者指向表頭結(jié)點(diǎn)，或者指

向鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)。

(3)算法描述：

intLocateElement(Linklistlistrintk)

{

pl=list->link;

p=list;i=l;

while(pl)

(

pl=pl->link;

i++；

if(i>k)p=p->next;//如果i>k,則p也往后移

}

if(p==list)return0;//說明鏈表沒有k個(gè)結(jié)點(diǎn)

else

(

printf(''%d\n'\p->data);

return1;

}

)

43

(i)解法一：

中斷方式下，CPU每次用于數(shù)據(jù)傳輸?shù)臅r(shí)鐘周期數(shù)：

5X18+5X2=100

為達(dá)到外設(shè)0.5MB/S的數(shù)據(jù)傳輸速率，外設(shè)每秒申請(qǐng)的中斷次數(shù)：

0.5MB/4B=125000

1秒內(nèi)用于中斷的開銷：

100X125000=12500000=12.5M個(gè)時(shí)鐘周期

CPU用于外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比：

12.5M/500MX100%=2.5%

解法二：

每次中斷需要100個(gè)周期，1秒可中斷5M次，而實(shí)際上只要0.5M/4=125000次就

夠了。實(shí)際所占的比例是：125000/5MX100%=2.5%

解法三：

一^a時(shí)鐘周期的時(shí)間為：2ns

一次中斷所需的時(shí)間為：100X2ns=200ns

一次傳輸允許的時(shí)間：Is/(0.5M/4)=8000ns

中斷所占的時(shí)間比例：200/8000X100%=2.5%

(2)外設(shè)數(shù)據(jù)傳輸率提高到5MB/S時(shí)，1秒內(nèi)需要產(chǎn)生的DMA次數(shù)為：

5MB/5000B=1000

cpu用于DMA處理的總開銷：

500X1000=500000=0.5M個(gè)時(shí)鐘周期

cpu用于外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比：

0.5M/500MX100%=0.5%

說明：傳榆速率與每次傳輸數(shù)據(jù)量的比就是傳榆次數(shù)，每次CPU所花的時(shí)間就是一次

中斷或者DMA的時(shí)間.注意，傳輸并不占用CPU時(shí)間.

44

解法一：

數(shù)據(jù)流：R1->MAR-MDR(R0-A)->(ALU)AC->MAR->Memory

時(shí)鐘功能有效控制信號(hào)

C5(RI)->MARRlout,MARin

M(MAR)->MDRMemR,MDRinE

C6

(RO)->ARout,Ain

C7(MAR)+(A)->ACMDRout,Add,ACin

C8(AC)->MDRACoutzMDRin

C9(MDR)->M(MAR)MDRourE,MemW

C6兩個(gè)操作在同一時(shí)鐘周期內(nèi)并行進(jìn)行，因?yàn)檫@兩個(gè)數(shù)據(jù)傳輸走的是不同的總線。MDR

走系統(tǒng)總線，而A走APU內(nèi)部總線?！埃≧0）->A”也可在C7:“（MDR）+（A）->AC”之前

單列的一個(gè)始終周期內(nèi)執(zhí)行。

解法二：

數(shù)據(jù)流：R1->MAR->MDR->A（RO）->（ALU）AC->MDR->Memory

忖鐘功能有效控制信號(hào)

C5(RI)->MARRlout,MARin

C6M(MAR)-〉MDRMemR,MDRinE

C7(MDR)->AMDRout,Ain

C8(A)+(RO)->ACROoutzAdd,ACin

C9(AC)->MDRACout,MDRin

CIO(MDR)->M(MAR)MDRourE,MemW

說明：本題是將RO中的數(shù)據(jù)與RI內(nèi)容所指主存單元的內(nèi)容相加，結(jié)果寫入R1內(nèi)容所

指的主存單元.

對(duì)于存儲(chǔ)器的讀寫，必須先將地址送到MAR,讀寫的數(shù)據(jù)必須經(jīng)過MDR.所以要讀寫R1

內(nèi)容所指的存儲(chǔ)單元，則必須先將R1送到MAR,而讀寫數(shù)據(jù)必須經(jīng)過MDR。

ALU一端是寄存器A,則從R0或從存儲(chǔ)器中讀出的數(shù)據(jù)，必有一個(gè)需先寫入A.另一個(gè)

可以是總線上的其他寄存器，如RO,R1,MDR等.

經(jīng)過同一總線，一個(gè)節(jié)拍只能傳榆一個(gè)數(shù)據(jù)。節(jié)拍之間，數(shù)據(jù)只能從狀態(tài)元件（寄存

器，存