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

計(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í)間復(fù)雜度是。

count=0;?

for(k=l;k<=n;k*=2)?

?for(j=i;j<=n;j++)??

count++;?

A.O(log2n)???B.O(n)??C.O(nlog2n)????D.O(n2)?

2.假設(shè)棧初始為空，將中綴表達(dá)式a/b+(c%-e*f)/g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式的過程中，

當(dāng)掃描到f時(shí)，棧中的元素依次是?。？

A4-9(9*9_7999R+9r>_9*9799C/94-9p*9_9*9990r)/94-9,7*9

3.循環(huán)隊(duì)列放在一維數(shù)組A0..M-1］中，endl指向隊(duì)頭元素，end2指向隊(duì)尾元素的

后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初

始時(shí)為空。下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是?。

?A.隊(duì)空：endl?==?end2；?隊(duì)滿：end1?==?(end2+1)mod?M?

B.隊(duì)空：endl?==?end2；?隊(duì)滿：end2?==?(end14-1)mod?(M-1)?

C.隊(duì)空：end2?==?(end1+1)mod?M；?隊(duì)滿：endl?==?(end2+1)mod?M?

D.隊(duì)空：cndl?二二?(end2+l)mod?M；?隊(duì)滿：cnd2?==?(end1+1)mod?(M-1)?

4.若對(duì)如下的二叉樹進(jìn)行中序線索化，則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分別是。？

A.e、c???B.e>a??C.d、c???D.b、a?

5.將森林F轉(zhuǎn)換為對(duì)應(yīng)的二叉樹T,F中葉結(jié)點(diǎn)的個(gè)數(shù)等于。？

A.T中葉結(jié)點(diǎn)的個(gè)數(shù)”?B.T中度為1的結(jié)點(diǎn)個(gè)數(shù)？

C.T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)?D.T中右孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)

?6.5個(gè)字符有如下4種編碼方案，不是前綴編碼的是?。

?A.01,0000,0001,001,1????

B.011,000,001,010,1?

C.000,001,010,011,100?

?D.(),100,110,1110,1100?

7.對(duì)如下所示的有向圖進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁?。?/p>

A.3,1,2,4,5,6??B.3,1,2,4,6,5?C.3』,4,2,5,6???D.3,1,4,2,6,57

8.用哈希(散列)方法處理沖突(碰撞)時(shí)可能出現(xiàn)堆積(聚集)現(xiàn)象，下列選項(xiàng)

中，會(huì)受堆積現(xiàn)象直接影響的是。

A.存儲(chǔ)效率B.散列函數(shù)C.裝填(裝載)因子D.平均查找長(zhǎng)度

9.在一棵具有15個(gè)關(guān)鍵字的4階B樹中，含關(guān)鍵字的結(jié)點(diǎn)個(gè)數(shù)最多是。

A.5B.6C.10D.15

10.用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為

9,1,4,13,7,8,20,23,15,則該趟排序采用的增量(間隔)可能是。

A.2B.3C.4D.5

11.下列選項(xiàng)中，不可能是快速排序第2趟排序結(jié)果的是。

A.2,3,5,4,6,7,9B.2,7,5,6,4,3,9C.3,2,5,4,7,6,9D.423,5,7,6,9

12.程序P在機(jī)器M上的執(zhí)行時(shí)間是2()秒，編譯優(yōu)化后，P執(zhí)行的指令數(shù)減少到原

來的70%,而CPI增加到原來的1.2倍，則P在M上的執(zhí)行時(shí)間是。

A.8.4秒B.11.7秒C.14秒D.16.8秒

13.若x=103,y=25,則下列表達(dá)式采用8位定點(diǎn)補(bǔ)碼運(yùn)算實(shí)現(xiàn)時(shí)，會(huì)發(fā)生溢出的是。

A.x+yB.-x+yC.x-yD.-x-y

14.float型數(shù)據(jù)據(jù)常用IEEE754單精度浮點(diǎn)格式表示。假設(shè)兩個(gè)float型變量x和y

分別存放在32位寄存器fl和f2中,若(fl尸CC900000H,(f2)=B0C00000H,則x和y之間

的關(guān)系為。

A.x<y且符號(hào)相同B.x<y且符號(hào)不同C.x>y且符號(hào)相同D.x>y且符號(hào)不同

15.某容量為256MB的存儲(chǔ)器由若干4Mx8位的DRAM芯片構(gòu)成，該DRAM芯片

的地址引腳和數(shù)據(jù)引腳總數(shù)是。

A.19B.22C.30D.36

16.采用指令Cache與數(shù)據(jù)Cache分離的主要目的是。

A.降低Cache的缺失損失B.提高Cache的命中率

C.降低CPU平均訪存時(shí)間D.減少指令流水線資源沖突

17.某計(jì)算機(jī)有16個(gè)通用寄存器，采用32位定長(zhǎng)指令字，操作碼字段(含尋址方式

位)為8位,Store指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址方式。

若基址寄存器可使用任一通用寄存器，且偏移量用補(bǔ)碼表示，則Store指令中偏移量的取

值范圍是。

A.-32768~+32767B.-32767~+32768

C.-65536?+65535D.-65535?+65536

18.某計(jì)算機(jī)采用微程序控制器，共有32條指令，公共的取指令微程序包含2條微

指令，各指令對(duì)應(yīng)的微程序平均由4條微指令組成，采用斷定法(下地址字段法)確定下

條微指令地址，則微指令中下址字段的位數(shù)至少是。

A.5B.6C.8D.9

19.某同步總線采用數(shù)據(jù)線和地址線復(fù)用方式，其中地址/數(shù)據(jù)線有32根，總線時(shí)鐘

頻率為66MHz,每個(gè)時(shí)鐘周期傳送兩次數(shù)據(jù)(上升沿和下降沿各傳送一次數(shù)據(jù))，該總線的

最大數(shù)據(jù)傳輸率(總線帶寬)是。

A.132MB/sB.264MB/sC.528MB/sD.1056MB/S

20.一次總線事務(wù)中，主設(shè)備只需給出一個(gè)首地址，從設(shè)備就能從首地址開始的若干

連續(xù)單元讀出或?qū)懭攵鄠€(gè)數(shù)據(jù)。這種總線事務(wù)方式稱為。

A.并行傳輸B.串行傳輸C.突發(fā)傳輸D.同步傳輸

21.下列有關(guān)I/O接口的敘述中，錯(cuò)誤.?的是。

A.狀態(tài)端口和控制端口可以合用同一個(gè)寄存器

B.I/O接口中CPU可訪問的寄存器稱為I/O端匚

C.采用獨(dú)立編址方式時(shí)，I/O端口地址和主存地址可能相同

D.采用統(tǒng)一編址方式時(shí)，CPU不能用訪存指令訪問I/O端口

22.若某設(shè)備中斷請(qǐng)求的響應(yīng)和處理時(shí)間為l()()ns,每4()0ns發(fā)出一次中斷請(qǐng)求，中

斷響應(yīng)所允許的最長(zhǎng)延遲時(shí)間為50ns,則在該設(shè)備持續(xù)工作過程中，CPU用于該設(shè)備的I/O

時(shí)間占整個(gè)CPU時(shí)間的百分比至少是。

A.12.5%B.25%C.37.5%D.50%

23.下列調(diào)度算法中，不可能導(dǎo)致饑餓現(xiàn)象的是c

A.時(shí)間片輪轉(zhuǎn)B.靜態(tài)優(yōu)先數(shù)調(diào)度

C.非搶占式短作業(yè)優(yōu)先D.搶占式短作業(yè)優(yōu)先

24.某系統(tǒng)有n臺(tái)互斥使用的同類設(shè)備，三個(gè)并發(fā)進(jìn)程分別需要3、4、5臺(tái)設(shè)備，可

確保系統(tǒng)不.發(fā)生.?死鎖的設(shè)備數(shù)n最小為。

A.9B.IOC.11D.12

25.下列指令中，不能..在用戶態(tài)執(zhí)行的是。

A.trap指令B.跳轉(zhuǎn)指令C.壓棧指令D.關(guān)中斷指令

26.一個(gè)進(jìn)程的讀磁盤操作完成后，操作系統(tǒng)針對(duì)該進(jìn)程必做的是。

A.修改進(jìn)程狀態(tài)為就緒態(tài)B.降低進(jìn)程優(yōu)先級(jí)

C.給進(jìn)程分配用戶內(nèi)存空間D.增加進(jìn)程時(shí)間片大小

27.現(xiàn)有一個(gè)容量為10GB的磁盤分區(qū)，磁盤空間以簇(Cluster)為單位進(jìn)行分配，簇的

大小為4KB,若采用位圖法管理該分區(qū)的空閑空間，即用一位(bil)標(biāo)識(shí)一個(gè)簇是否被分配,

則存放該位圖所需簇的個(gè)數(shù)為。

A.80B.320C.80KD.320K

28.下列措施中，能加快虛實(shí)地址轉(zhuǎn)換的是。

I.增大快表(TLB)容量n.讓頁表常駐內(nèi)存ni.增大交換區(qū)(swap)

A.僅IB.僅IIC.僅I、IID.僅H、III

29.在一個(gè)文件被用戶進(jìn)程首次打開的過程中，操作系統(tǒng)需做的是。

A.將文件內(nèi)容讀到內(nèi)存中B.將文件控制塊讀至J內(nèi)存中

C.修改文件控制塊中的讀寫權(quán)限D(zhuǎn).將文件的數(shù)據(jù)緩沖區(qū)首指針返回給用戶進(jìn)程

30.在頁式虛擬存儲(chǔ)管理系統(tǒng)中，采用某些頁面置換算法，會(huì)出現(xiàn)Belady異?，F(xiàn)象，

即進(jìn)程的缺頁次數(shù)會(huì)隨著分配給該進(jìn)程的頁框個(gè)數(shù)的增加而增加。下列算法中，可能出現(xiàn)

Belady異?，F(xiàn)象的是。

I.LRU算法H.FIFO算法HI.OPT算法

A.僅IIB.僅I、IIC.僅I、IIID.僅II、III

31.下列關(guān)于管道(Pipe)通信的敘述中，正確..的是。

A.一個(gè)管道可實(shí)現(xiàn)雙向數(shù)據(jù)傳輸

B.管道的容量?jī)H受磁盤容最大小限制

C.進(jìn)程對(duì)管道進(jìn)行讀操作和寫操作都可能被阻塞

D.一個(gè)管道只能有一個(gè)讀進(jìn)程或一個(gè)寫進(jìn)程對(duì)其操作

32.下列選項(xiàng)中，屬于多級(jí)頁表優(yōu)點(diǎn)的是。

A.加快地址變換速度B.減少缺頁中斷次數(shù)

C.減少頁表項(xiàng)所占字節(jié)數(shù)D.減少頁表所占的連續(xù)內(nèi)存空間

33.在OSI參考模型中，直接為會(huì)話層提供服務(wù)的是。

A.應(yīng)用層B.表示層C.傳輸層D.網(wǎng)絡(luò)層

34.某以太網(wǎng)拓?fù)浼敖粨Q機(jī)當(dāng)前轉(zhuǎn)發(fā)表如下圖所示，主機(jī)00-el-d5-()0-23-al向主機(jī)

00-el-d5-00-23-cl發(fā)送1個(gè)數(shù)據(jù)幀，主機(jī)00-el-d5-00-23-cl收到該幀后,向主機(jī)

00-el-d5-00-23-al發(fā)送1個(gè)確認(rèn)幀,交換機(jī)對(duì)這兩個(gè)幀的轉(zhuǎn)發(fā)端口分別是()。

A.{3}和{1}B.{2,3}#{1}C.{2,3}ff{l,2}D.{1,2,3}和{1}

35.下列因素中，不會(huì)影響信道數(shù)據(jù)傳輸速率的是。

A.信噪比B.頻率寬帶C.調(diào)制速率D.信號(hào)傳播速度

36.主機(jī)甲與主機(jī)乙之間使用后退N幀協(xié)議(GBN)傳輸數(shù)據(jù)，甲的發(fā)送窗口尺寸為

1(X)(),數(shù)據(jù)幀長(zhǎng)為1()0()字節(jié)，信道帶寬為100Mbps,乙每收到一個(gè)數(shù)據(jù)幀立即利用一個(gè)

短幀(忽略其傳輸延遲)進(jìn)行確認(rèn)，若甲乙之間的單向傳播延遲是50ms,則甲可以達(dá)到的最

大平均數(shù)據(jù)傳輸速率約為。

A.lOMbpsB.20MbpsC.80MbpsD.100Mbps

37.站點(diǎn)A、B、C通過CDMA共享鏈路,A、B、C的碼片序列(chippingsequence)

分別是(1,1,1,1)、(1,-1,1,-D^d,若C從鏈路上收到的序列是

(2,0,2,0,0,-2,0,-2,0,2,0,2),則C收至ljA發(fā)送的數(shù)據(jù)是。

A.OOOB.1O1C.HOD.Ill

38.主機(jī)甲和主機(jī)乙已建立了TCP連接，甲始終以MSS=1KB大小的段發(fā)送數(shù)據(jù)，并

一直有數(shù)據(jù)發(fā)送；乙每收到一個(gè)數(shù)據(jù)段都會(huì)發(fā)出一個(gè)接收窗口為10KB的確認(rèn)段。若甲在

t時(shí)刻發(fā)生超時(shí)時(shí)擁塞窗口為8KB,則從t時(shí)刻起，不再發(fā)生超時(shí)的情況下，經(jīng)過1（）個(gè)RTT

后，甲的發(fā)送窗口是。

A.10KBB.12KBC.14KBD.15KB

39.下列關(guān)于UDP協(xié)議的敘述中，正確..的是。

I.提供無連接服務(wù)II.提供復(fù)用/分用服務(wù)HI.通過差錯(cuò)校驗(yàn)，保障可靠數(shù)據(jù)傳輸

A.僅IB.僅I、IIC.僅II、IIID.I、II、III

40.使用瀏覽器訪問某大學(xué)Web網(wǎng)站主頁時(shí)，不可能使用到的協(xié)議是。

A.PPPB.ARPC.UDPD.SMTP

二、綜合應(yīng)用題：41-47小題，共70分。

41.（13分）二叉樹的帶權(quán)路徑長(zhǎng)度（WPL）是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。

給定一棵二叉樹T,采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為：

其中葉結(jié)點(diǎn)的weight城保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)root為指向T的根結(jié)點(diǎn)的指針，請(qǐng)

設(shè)計(jì)求T的WPL的算法，要求：

1）給出算法的基本設(shè)計(jì)思想；

2）使用C或C++語言，給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義；

3）根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。

42.（1（）分）某網(wǎng)絡(luò)中的路由器運(yùn)行OSPF路由協(xié)議，題42表是路由器R1維護(hù)的主要

鏈路狀態(tài)信息（LSI）,題42組是根據(jù)題42表及R1的接口名構(gòu)造出來的網(wǎng)絡(luò)拓?fù)洹?/p>

題42圖R1構(gòu)造的網(wǎng)絡(luò)拓?fù)?/p>

請(qǐng)回答下列問題：

I）本題中的網(wǎng)絡(luò)可抽象為數(shù)據(jù)結(jié)構(gòu)中的哪種邏輯結(jié)構(gòu)？

2）針對(duì)題42表中的內(nèi)容，設(shè)計(jì)合理的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以保存題42表中的鏈路狀態(tài)

信息（LSI）。要求給出鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的數(shù)據(jù)類型定義，并畫出對(duì)應(yīng)題42表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

示意圖（示意圖中可僅以ID標(biāo)識(shí)結(jié)點(diǎn)）。

43.19分）請(qǐng)根據(jù)題42描述的網(wǎng)絡(luò)，繼續(xù)回答下列問題。1）假設(shè)路由表結(jié)構(gòu)如下

表所示，請(qǐng)給出題42圖中R1的路由表，要求包括到達(dá)題42

2）若R1增加一條Metric為10的鏈路連接Internet,則題42表中R1的LSI需要增加

哪些信息？

44.（12分）某程序中有如下循環(huán)代碼段p：:“for（inti=0;ivN;i++）sum+=A[i];"。假設(shè)編

譯時(shí)變量sum和i分別分配在寄存器R1和R2中。常量N在寄存器R6中，數(shù)組A的首地

址在寄存器R3中。程序段P起始地址為08048100H,對(duì)應(yīng)的匯編代碼和機(jī)器代碼如下表

所示。

OP為操作碼;；Rs和Rd為寄存器編號(hào)；OFFSET為偏移量，用補(bǔ)碼表示。請(qǐng)回答下

列問題，并說明理由。

1）M的存儲(chǔ)器編址單位是什么？

2）己知sll指令實(shí)現(xiàn)左移功能，數(shù)組A中每個(gè)元素占多少位？

3）題44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相對(duì)尋址方式，

當(dāng)前PC內(nèi)容為bne指令地址，通過分析題44表中指令地址和bne指令內(nèi)容，推斷出bne

指令的轉(zhuǎn)移目標(biāo)地址計(jì)算公式。

4）若M采用如下“按序發(fā)射、按序完成”的5級(jí)指令流水線：IF（取值）、ID（譯碼

及取數(shù)）、EXE（執(zhí)行）、MEM（訪存）、WB（寫回寄存器），且硬件不采取任何轉(zhuǎn)發(fā)

措施，分支指令的執(zhí)行均引起3個(gè)時(shí)鐘周期的阻塞，則P中哪些指令的執(zhí)行會(huì)由于數(shù)據(jù)相

關(guān)而發(fā)生流水線阻塞？哪條指令的執(zhí)行會(huì)發(fā)生控制冒險(xiǎn)？為什么指令1的執(zhí)行不會(huì)囚為與

指令5的數(shù)據(jù)相關(guān)而發(fā)生阻塞？

45.假設(shè)對(duì)于44題中的計(jì)算機(jī)M和程序P的機(jī)器代碼，M采用頁式虛擬存儲(chǔ)管理；

P開始執(zhí)行時(shí)，(Rl)=(R2)=0,(R6)=1000,其機(jī)器代碼已調(diào)入主存但不在Cache中；數(shù)組A

未調(diào)入主存，且所有數(shù)組元素在同一頁，并存儲(chǔ)在磁盤同一個(gè)扇區(qū)。請(qǐng)回答下列問題并說

明理由。1)P執(zhí)行結(jié)束時(shí)，R2的內(nèi)容是多少？

2)M的指令Cache和數(shù)據(jù)Cache分離。若指令Cache共有16行，Cache和主存交換

的塊大小為32字節(jié)，則其數(shù)據(jù)區(qū)的容量是多少？若僅考慮程序段P的執(zhí)行，則指令Cache

的命中率為多少？

3)P在執(zhí)行過程中，哪條指令的執(zhí)行可能發(fā)生溢出異常？哪條指令的執(zhí)行可能產(chǎn)生缺

頁異常？對(duì)于數(shù)組A的訪問，需要讀磁盤和TLB至少各多少次？

46.文件F由200條記錄組成，記錄從1開始編號(hào)。用戶打開文件后，欲將內(nèi)存中的

一條記錄插入到文件F中，作為其第30條記錄。請(qǐng)回答下列問題，并說明理由。

I)若文件系統(tǒng)采用連續(xù)分配方式，每個(gè)磁盤塊存放一條記錄，文件F存儲(chǔ)區(qū)域前后

均有足夠的空閑磁盤空間，則完成上述插入操作最少需要訪問多少次磁盤塊？F的文件控

制塊內(nèi)容會(huì)發(fā)生哪些改變？

2)若文件系統(tǒng)采用鏈接分配方式，每個(gè)磁盤塊存放一條記錄和一個(gè)鏈接指針，則完

成上述插入操作需要訪問多少次磁盤塊？若每個(gè)存儲(chǔ)塊大小為1KB,其中4個(gè)字節(jié)存放鏈

接指針，則該文件系統(tǒng)支持的文件最大長(zhǎng)度是多少？

47.系統(tǒng)中有多個(gè)生產(chǎn)者進(jìn)程和多個(gè)消費(fèi)者進(jìn)程，共享一個(gè)能存放1000件產(chǎn)品的環(huán)形

緩沖區(qū)(初始為空)。當(dāng)緩沖區(qū)未滿時(shí)，生產(chǎn)者進(jìn)程可以放入其生產(chǎn)的一件產(chǎn)品，否則等

待；當(dāng)緩沖區(qū)未空時(shí)，消費(fèi)者進(jìn)程可以從緩沖區(qū)取走一件產(chǎn)品，否則等待。要求一個(gè)消費(fèi)

者進(jìn)程從緩沖區(qū)連續(xù)取出10件產(chǎn)品后，其他消費(fèi)者進(jìn)程才可以取產(chǎn)品。請(qǐng)使用信號(hào)量P，

V(wait(),signal。)操作實(shí)現(xiàn)進(jìn)程間的互斥與同步，要求寫出完整的過程，并說明所用信號(hào)

量的含義和初值。

2014年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案

一、單項(xiàng)選擇題

(一)單選題答案

1.C2.B3.A4.D5.C6.D7.D8.D9.DIO.B

11.C12.D13.C14.A15.A16.D17.A18.C19.C20.C

21.D22.B23.A24.B25.D26.A27.A28.C29.B30.A

31.C32.D33.C34.B35.D36.C37.B38.A39.B40.D

(二)單選題答案解析

1.內(nèi)層循環(huán)條件j<=n與外層循環(huán)的變量無關(guān)，每次循環(huán)j自增1,每次內(nèi)層循環(huán)都執(zhí)

行n次。外層循環(huán)條件為kun,增量定義為k*=2,可知循環(huán)次數(shù)為2k<=n,即kv=log2n。

所以內(nèi)層循環(huán)的時(shí)間復(fù)雜度是O(n),外層循環(huán)的時(shí)間復(fù)雜度是O(log2n)。對(duì)于嵌套循環(huán)，

根據(jù)乘法規(guī)則可知，該段程序的時(shí)間復(fù)雜度T(n尸Tl(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。

2.將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法思想如下：

從左向右開始掃描中綴表達(dá)式；

遇到數(shù)字時(shí)，加入后綴表達(dá)式；

遇到運(yùn)算符時(shí)：

a.若為'('，入棧;

b.若為)，則依次把棧中的的運(yùn)算符加入后綴表達(dá)式中，直到出現(xiàn)C從棧中刪除C

c.若為除括號(hào)外的其他運(yùn)算符，當(dāng)其優(yōu)先級(jí)高于除'('以外的棧頂運(yùn)算符時(shí)，直接入棧。

否則從棧頂開始，依次彈出比當(dāng)前處理的運(yùn)算符優(yōu)先級(jí)高和優(yōu)先級(jí)相等的運(yùn)算符，直到一

個(gè)比它優(yōu)先級(jí)低的或者遇到了一個(gè)左括號(hào)為止。

當(dāng)掃描的中綴表達(dá)式結(jié)束時(shí)，棧中的所有運(yùn)算符依次出棧加入后綴表達(dá)式。

由此可知，當(dāng)掃描到f的時(shí)候，棧中的元素依次是十(-*,選B。

在此，再給出中綴表達(dá)式轉(zhuǎn)換為前綴或后綴表達(dá)式的一種手工做法，以上面給出的中

綴表達(dá)式為例：

第一步：按照運(yùn)算符的優(yōu)先級(jí)對(duì)所有的運(yùn)算單位加括號(hào)。式子變成了：

((a^)+(((c*d)-(e*f))/g))

第二步：轉(zhuǎn)換為前綴或后綴表達(dá)式。

前綴：把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)前而，則變成了：+(/(ab)/(-(*(cd)*(ef))g))把括號(hào)

去掉：+/ab/-*cd*efg前綴式子出現(xiàn)。

后綴：把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)后面，則變成了：((ab)/(((cd)*(ct)*)-g)/)+把括號(hào)

去掉：ab/cd*ef*-g/+后綴式子出現(xiàn)。

當(dāng)題目要求直接求前綴或后綴表達(dá)式時(shí)，這種方法會(huì)比上一種快捷得多。

3.endl指向隊(duì)頭元素,那么可知出隊(duì)的操作是先從A[endl]讀數(shù)，然后endl再加1。

end2指向隊(duì)尾元素的后一個(gè)位置，那么可知入隊(duì)操作是先存數(shù)到A[end2],然后end2再加

lo若把A[()]儲(chǔ)存第一個(gè)元素，當(dāng)隊(duì)列初始時(shí)，入隊(duì)操作是先把數(shù)據(jù)放到A[()],然后end2

自增，即可知end2初值為0；而endl指向的是隊(duì)頭元素，隊(duì)頭元素的在數(shù)組A中的下標(biāo)

為0,所以得知endl初值也為0,可知隊(duì)空條件為endl==end2；然后考慮隊(duì)列滿時(shí),因?yàn)?/p>

隊(duì)列最多能容納M-1個(gè)元素，假設(shè)隊(duì)列存儲(chǔ)在下標(biāo)為0到下標(biāo)為M-2的M-1個(gè)區(qū)域，隊(duì)

頭為A[0],隊(duì)尾為A[M-2],此時(shí)隊(duì)列滿，考慮在這種情況下endl和cnd2的狀態(tài)，endl

指向隊(duì)頭元素，可知endl=O,end2指向隊(duì)尾元素的后一個(gè)位置，可知end2=M-2+l=M-l,

所以可知隊(duì)滿的條件為end1=(end2+1)modM,選A。

注意：考慮這類具體問題時(shí)，用一些特殊情況判斷往往比直接思考問題能更快的得到

答案，并可以畫出簡(jiǎn)單的草圖以方便解題。

4.線索二叉樹的線索實(shí)際上指向的是相應(yīng)遍歷序列特定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)

點(diǎn)，所以先寫出二叉樹的中序遍歷序列：edbxac,中序遍歷中在x左邊和右邊的字符，就

是它在中序線索化的左、右線索，即b、a,選D。

5.將森林轉(zhuǎn)化為二叉樹即相當(dāng)于用孩子兄弟表示法表示森林。在變化過程中，原森

林某結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)作為它的左子樹，它的兄弟作為它的右子樹。那么森林中的葉

結(jié)點(diǎn)由于沒有孩子結(jié)點(diǎn)，那么轉(zhuǎn)化為二叉樹時(shí)，該結(jié)點(diǎn)就沒有左結(jié)點(diǎn)，所以F中葉結(jié)點(diǎn)的

個(gè)數(shù)就等于T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)，選C。

此題還可以通過一些特例來排除A、B、D選項(xiàng)。

6.前綴編碼的定義是在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼

的前綴。D中編碼110是編碼1100的前綴，違反了前綴編碼的規(guī)則，所以D不是前綴編

碼。

7.按照拓?fù)渑判虻乃惴?，每次都選擇入度為0的結(jié)點(diǎn)從圖中刪去，此圖中一開始只

有結(jié)點(diǎn)3的入度為()：刪掉3結(jié)點(diǎn)后，只有結(jié)點(diǎn)1的入度為0；刪掉結(jié)點(diǎn)1后，只有結(jié)點(diǎn)4

的入度為0;刪掉4結(jié)點(diǎn)后，結(jié)點(diǎn)2和結(jié)點(diǎn)6的入度都為0,此時(shí)選擇刪去不同的結(jié)點(diǎn)，

會(huì)得出不同的拓?fù)湫蛄校謩e處理完畢后可知可能的拓?fù)湫蛄袨?14265和314625,選D。

8.產(chǎn)生堆積現(xiàn)象，即產(chǎn)生了沖突，它對(duì)存儲(chǔ)效率、散列函數(shù)和裝填因子均不會(huì)有影

響，而平均查找長(zhǎng)度會(huì)因?yàn)槎逊e現(xiàn)象而增大，選D。

9.關(guān)鍵字?jǐn)?shù)量不變，要求結(jié)點(diǎn)數(shù)量最多，那么即每個(gè)結(jié)點(diǎn)中含關(guān)鍵字的數(shù)量最少。

根據(jù)4階B樹的定義，根垢點(diǎn)最少含1個(gè)關(guān)鍵字，非根結(jié)點(diǎn)中最少含?4/2?-1=1個(gè)關(guān)鍵字,

所以每個(gè)結(jié)點(diǎn)中，關(guān)鍵字?jǐn)?shù)量最少都為1個(gè)，即每個(gè)結(jié)點(diǎn)都有2個(gè)分支，類似與排序二叉

樹，而15個(gè)結(jié)點(diǎn)正好可以構(gòu)造一個(gè)4層的4階B樹，使得葉子結(jié)點(diǎn)全在第四層，符合B

樹定義，因此選D。

10.首先，第二個(gè)元素為1,是整個(gè)序列中的最小元素，所以可知該希爾排序?yàn)閺男?/p>

到大排序。然后考慮增量問題，若增量為2,第1+2人元素4明顯比第1個(gè)元素9要大，

A排除；若增量為3,笫i、i+3、i+6個(gè)元素都為有序序列(i=1,2,3),符合希爾排序的定義;

若增量為4,第1個(gè)元素9比第1+4個(gè)元素7要大，C排除；若增量為5,第1個(gè)元素9

比第1+5個(gè)元素8要大，D排除，選B。

11.快排的階段性排序結(jié)果的特點(diǎn)是，第i趟完成時(shí)，會(huì)有i個(gè)以上的數(shù)出現(xiàn)在它最

終將要出現(xiàn)的位置，即它左邊的數(shù)都比它小，它右邊的數(shù)都比它大。題目問第二趟排序的

結(jié)果，即要找不存在2個(gè)這樣的數(shù)的選項(xiàng)。A選項(xiàng)中2、3、6、7、9均符合，所以A排除;

B選項(xiàng)中，2、9均符合，所以B排除；D選項(xiàng)中5、9均符合，所以D選項(xiàng)排除；最后看

C選項(xiàng)，只有9一個(gè)數(shù)符合，所以C不可能是快速排序第二趟的結(jié)果。

12.不妨設(shè)原來指令條數(shù)為x,那么原CPI就為20/x,經(jīng)過編譯優(yōu)化后，指令條數(shù)減

少到原來的70%,即指令條數(shù)為0.7x,而CPI增加到原來的1.2倍,即24/x,那么現(xiàn)在P

在M上的執(zhí)行時(shí)間就為指令條數(shù)*CPI=0.7x*24/x=24*0.7=16.8秒，選D。

13.8位定點(diǎn)補(bǔ)碼表示的數(shù)據(jù)范圍為-128727,若運(yùn)算結(jié)果超出這個(gè)范圍則會(huì)溢出，A

選項(xiàng)x+y=103-25=78,符合范圍,A排除;B選項(xiàng)?x+尸103-25=128,符合范圍,B排除；

D選項(xiàng)-x-y=-103+25=78,符合范圍,D排除;C選項(xiàng)x-y=103+25=128,超過了127,選C。

該題也可按照二進(jìn)制寫出兩個(gè)數(shù)進(jìn)行運(yùn)算觀察運(yùn)算的進(jìn)位信息得到結(jié)果，不過這種方

法更為麻煩和耗時(shí)，在實(shí)際考試中并不推薦。

此題還有更為簡(jiǎn)便的算法，⑴)與(⑵的前4位為1100與1011,可以看出兩數(shù)均為負(fù)數(shù),

而階碼用移碼表示，兩數(shù)的階碼頭三位分別為100和011,可知⑴)的階碼大于(f2)的階碼,

又因?yàn)槭荌EEE754規(guī)格化的數(shù)，尾數(shù)部分均為l.xxx,則階碼大的數(shù)，真值的絕對(duì)值必然

大，可知(")真值的絕對(duì)值大于(⑵真值的絕對(duì)值，因?yàn)槎紴樨?fù)數(shù)，則⑴)<(⑵，即xvy。

15.4Mx8位的芯片數(shù)據(jù)線應(yīng)為8根，地址線應(yīng)為log24M=22根，而DRAM采用地址

復(fù)用技術(shù)，地址線是原來的1/2,且地址信號(hào)分行、列兩次傳送。地址線數(shù)為22/2=11根，

所以地址引腳與數(shù)據(jù)引腳的總數(shù)為11+8=19根，選A。

此題需要注意的是DRAM是采用傳兩次地址的策略的，所以地址線為正常的一半，

這是很多考生容易忽略的地方。

16.把指令Cache與數(shù)據(jù)Cache分離后，取指和取數(shù)分別到不同的Cache中尋找，那

么指令流水線中取指部分和取數(shù)部分就可以很好的避免沖突，即減少了指令流水線的沖

突。

17.采用32位定長(zhǎng)指令字，其中操作碼為8位，兩個(gè)地址碼一共占用32-8=24位，而

Store指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址，機(jī)器中共有16

個(gè)通用寄存器，則尋址一個(gè)寄存器需要log216=4位，源操作數(shù)中的寄存器直接尋址用掉4

位，而目的操作數(shù)采用基址尋址也要指定一個(gè)寄存器，同樣用掉4位，則留給偏移址的位

數(shù)為24-4-4=16位，而偏移址用補(bǔ)碼表示，16位補(bǔ)碼的表示范圍為-32768?+32767,選A。

18.計(jì)算機(jī)共有32條指令，各個(gè)指令對(duì)應(yīng)的微程序平均為4條，則指令對(duì)應(yīng)的微指

令為32*4=128條，而公共微指令還有2條，整個(gè)系統(tǒng)中微指令的條數(shù)一共為128+2=13()

條，所以需要?log2130?=8位才能尋址到130條微指令，答案選C。

19.數(shù)據(jù)線有32根也就是一次可以傳送32bit/8=4B的數(shù)據(jù)，66MHz意味著有66M個(gè)

時(shí)鐘周期，而每個(gè)時(shí)許周期傳送兩次數(shù)據(jù)，可知總線每秒傳送的最大數(shù)據(jù)量為

66MX2X4B=528MB,所以總線的最大數(shù)據(jù)傳輸率為528MB/S,選C。

20.猝發(fā)(突發(fā))傳輸是在一個(gè)總線周期中，可以傳輸多個(gè)存儲(chǔ)地址連續(xù)的數(shù)據(jù)，即一

次傳輸一個(gè)地址和一批地址連續(xù)的數(shù)據(jù)，并行傳輸是在傳輸中有多個(gè)數(shù)據(jù)位同時(shí)在設(shè)備之

間進(jìn)行的傳輸，串行傳輸是指數(shù)據(jù)的二進(jìn)制代碼在一條物理信道上以位為單位按時(shí)間順序

逐位傳輸?shù)姆绞剑絺鬏斒侵競(jìng)鬏斶^程由統(tǒng)一的時(shí)鐘控制，選C。

21.采用統(tǒng)一編址時(shí)，CPU訪存和訪問I/O端口用的是一樣的指令，所以訪存指令可

以訪問I/O端口，D選項(xiàng)錯(cuò)誤，其他三個(gè)選項(xiàng)均為正確陳述，選D。

22.每400ns發(fā)出一次中斷請(qǐng)求,而響應(yīng)和處理時(shí)間為100ns,其中容許的延遲為干

擾信息，囚為在50ns內(nèi)，無論怎么延遲，每400ns還是要花費(fèi)100ns處理中斷的，所以該

設(shè)備的I/O時(shí)間占整個(gè)CPU時(shí)間的百分比為100ns/400ns=25%，選B。

23.采用靜態(tài)優(yōu)先級(jí)調(diào)度時(shí)，當(dāng)系統(tǒng)總是出現(xiàn)優(yōu)先級(jí)高的任務(wù)時(shí)，優(yōu)先級(jí)低的任務(wù)會(huì)

總是得不到處理機(jī)而產(chǎn)生饑餓現(xiàn)象；而短作業(yè)優(yōu)先調(diào)度不管是搶占式或是非搶占的，當(dāng)系

統(tǒng)總是出現(xiàn)新來的短任務(wù)時(shí)，長(zhǎng)任務(wù)會(huì)總是得不到處理機(jī)，產(chǎn)生饑餓現(xiàn)象，因此B、C、D

都錯(cuò)誤，選A。

24.三個(gè)并發(fā)進(jìn)程分別需要3、4、5臺(tái)設(shè)備，當(dāng)系統(tǒng)只有(3-1)+(4?1)+(5-1)=9臺(tái)設(shè)備時(shí),

第一個(gè)進(jìn)程分配2臺(tái)，第二個(gè)進(jìn)程分配3臺(tái)，第三個(gè)進(jìn)程分配4臺(tái)。這種情況下，三個(gè)進(jìn)

程均無法繼續(xù)執(zhí)行下去，發(fā)生死鎖。當(dāng)系統(tǒng)中再增加1臺(tái)設(shè)備，也就是總共10臺(tái)設(shè)備時(shí),

這最后1臺(tái)設(shè)備分配給任意一個(gè)進(jìn)程都可以順利執(zhí)行完成，因此保證系統(tǒng)不發(fā)生死鎖的最

小設(shè)備數(shù)為10o

25.irap指令、跳轉(zhuǎn)指令和壓棧指令均可以在用戶態(tài)執(zhí)行，其中tr叩指令負(fù)責(zé)由用戶

態(tài)轉(zhuǎn)換成為內(nèi)核態(tài)。而關(guān)中斷指令為特權(quán)指令，必須在核心態(tài)才能執(zhí)行，選D。

26.進(jìn)程申請(qǐng)讀磁盤操作的時(shí)候，因?yàn)橐却齀/O操作完成，會(huì)把自身阻塞，此時(shí)進(jìn)

程就變?yōu)榱俗枞麪顟B(tài)，當(dāng)I/O操作完成后，進(jìn)程得到了想要的資源，就會(huì)從阻塞態(tài)轉(zhuǎn)換到

就緒態(tài)(這是操作系統(tǒng)的行為)。而降低進(jìn)程優(yōu)先級(jí)、分配用戶內(nèi)存空間和增加進(jìn)程的時(shí)

間片大小都不一定會(huì)發(fā)生，選A。

27.簇的總數(shù)為10GB；4KB=2.5M,用一位標(biāo)識(shí)一簇是否被分配，則整個(gè)磁盤共需要

2.5M位，即需要2.5M/8=320KB,則共需要320KB/4KB=80個(gè)簇，選A。

28.虛實(shí)地址轉(zhuǎn)換是指邏輯地址和物理地址的轉(zhuǎn)換。增大快表容量能把更多的表項(xiàng)裝

入快表中，會(huì)加快虛實(shí)地址轉(zhuǎn)換的平均速率；讓頁表常駐內(nèi)存可以省去一些不在內(nèi)存中的

頁表從磁盤上調(diào)入的過程，也能加快虛實(shí)地址變換；增大交換區(qū)對(duì)虛實(shí)地址變換速度無影

響，因此I、II正確，選C。

29.一個(gè)文件被用戶進(jìn)程首次打開即被執(zhí)行了Open操作，會(huì)把文件的FCB調(diào)入內(nèi)存,

而不會(huì)把文件內(nèi)容讀到內(nèi)存中，只有進(jìn)程希望獲取文件內(nèi)容的時(shí)候才會(huì)讀入文件內(nèi)容；C、

D明顯錯(cuò)誤，選B。

30.只有FIFO算法會(huì)導(dǎo)致Belady異常，選A。

31.管道實(shí)際上是一種固定大小的緩沖區(qū)，管道對(duì)于管道兩端的進(jìn)程而言，就是一個(gè)

文件，但它不是普通的文件，它不屬于某種文件系統(tǒng)，而是自立門戶，單獨(dú)構(gòu)成一種文件

系統(tǒng)，并且只存在于內(nèi)存中。它類似于通信中半雙工信道的進(jìn)程通信機(jī)制，一個(gè)管道可以

實(shí)現(xiàn)雙向的數(shù)據(jù)傳輸，而同一個(gè)時(shí)刻只能最多有一個(gè)方向的傳輸，不能兩個(gè)方向同時(shí)進(jìn)行。

管道的容量大小通常為內(nèi)存上的一頁，它的大小并不是受磁盤容量大小的限制。當(dāng)管道滿

時(shí)，進(jìn)程在寫管道會(huì)被阻塞，而當(dāng)管道空時(shí)，進(jìn)程讀管道會(huì)被阻塞，因此選C。

32.多級(jí)頁表不僅不會(huì)加快地址的變換速度，還因?yàn)樵黾痈嗟牟楸磉^程，會(huì)使地址

變換速度減慢；也不會(huì)減少缺頁中斷的次數(shù)，反而如果訪問過程中多級(jí)的頁表都不在內(nèi)存

中，會(huì)大大增加缺頁的次數(shù)，也并不會(huì)減少頁表項(xiàng)所占的字節(jié)數(shù)(詳細(xì)解析參考二段)，而

多級(jí)頁表能夠減少頁表所占的連續(xù)內(nèi)存空間，即當(dāng)頁表太大時(shí)，將頁表再分級(jí)，可以把每

張頁表控制在一頁之內(nèi)，減少頁表所占的連續(xù)內(nèi)存空間，因此選D。補(bǔ)充：頁式管理中每

個(gè)頁表項(xiàng)的大小的下限如何決定？頁表項(xiàng)的作用是找到該頁在內(nèi)存的位置，以32位邏輯

地址空間，字節(jié)為編址單位，一頁4KB為例，地址空間內(nèi)一共含有232B/4KB=1M頁，則

需要log21M=20位才能保證表示范圍能容納所有頁面，乂因?yàn)橐宰止?jié)作為編址單位，即頁

表項(xiàng)的大小2?20/8?=3B。所以在這個(gè)條件下，為了保證頁表項(xiàng)能夠指向所有頁面，那么頁

表項(xiàng)的大小應(yīng)該大于3B,當(dāng)然，也可以選擇更大的頁表項(xiàng)大小以至于讓一個(gè)頁面能夠正好

容下整數(shù)個(gè)頁表項(xiàng)以方便存儲(chǔ)(例如取成4B,那么一頁正好可以裝下1K個(gè)頁表項(xiàng))，或

者增加一些其他信息。

33.直接為會(huì)話層提供服務(wù)的即會(huì)話層的下一層，是傳輸層，選C。

34.主機(jī)()O-el-d5-OO-23-al向00-el-d5-00-23-cl發(fā)送數(shù)據(jù)幀時(shí),交換機(jī)轉(zhuǎn)發(fā)表中沒有

00-el-d5-00-23-cl這項(xiàng)，所以向除1接口外的所有接匚廣播這幀,即2、3端口會(huì)轉(zhuǎn)發(fā)這幀,

同時(shí)因?yàn)檗D(zhuǎn)發(fā)表中并沒有00-el-d5-00-23-al這項(xiàng)，所以轉(zhuǎn)發(fā)表會(huì)把(目的地址

00-el-d5-00-23-al,端口1)這項(xiàng)加入轉(zhuǎn)發(fā)表。而當(dāng)00-el-d5-00-23-cl向00-el-d5-00-23-al

發(fā)送確認(rèn)幀時(shí)，由于轉(zhuǎn)發(fā)表已經(jīng)有00-el-d5-00-23-al這項(xiàng)，所以交換機(jī)只向1端口轉(zhuǎn)發(fā)，

選Bo

35.由香農(nóng)定理可知，信噪比和頻率帶寬都可以限制信道的極限傳輸速率，所以信噪

比和頻率帶寬對(duì)信道的數(shù)據(jù)傳輸速率是有影響的，A、B錯(cuò)誤；信道的傳輸速率實(shí)際上就

是信號(hào)的發(fā)送速率，而調(diào)制速度也會(huì)直接限制數(shù)據(jù)的傳輸速率，C錯(cuò)誤；信號(hào)的傳播速度

是信號(hào)在信道上傳播的速度，與信道的發(fā)送速率無關(guān)，選D。

36.考慮制約甲的數(shù)捱傳輸速率的因素，首先，信道帶寬能直接制約數(shù)據(jù)的傳輸速率,

傳輸速率一定是小于等于信道帶寬的；其次，主機(jī)甲乙之間采用后退N幀協(xié)議，那么因?yàn)?/p>

甲乙主機(jī)之間采用后退N幀協(xié)議傳輸數(shù)據(jù)?，要考慮發(fā)送一個(gè)數(shù)據(jù)到接收到它的確認(rèn)之前，

最多能發(fā)送多少數(shù)據(jù)，甲的最大傳輸速率受這兩個(gè)條件的約束，所以甲的最大傳輸速率是

這兩個(gè)值中小的那一個(gè)。甲的發(fā)送窗口的尺寸為1000,即收到第一個(gè)數(shù)據(jù)的確認(rèn)之前，最

多能發(fā)送1000個(gè)數(shù)據(jù)幀,也就是發(fā)送1000*1000B=lMB的內(nèi)容，而從發(fā)送第一個(gè)幀到接

收到它的確認(rèn)的時(shí)間是一個(gè)往返時(shí)延，也就是50+50=100ms=0.1s,即在100ms中，最多能

傳輸1MB的數(shù)據(jù)，因此此時(shí)的最大傳輸速率為lMB/0.1s=10MB/s=80Mbps。信道帶寬為

100Mbps,所以答案為min{80Mbps,100Mbps}=80Mbps,選C。

37.把收到的序列分成每4個(gè)數(shù)字一組，即為(2,0,2,0)、(0,-2,0,-2)、(0,2,0,2),因?yàn)轭}

目求的是A發(fā)送的數(shù)據(jù)，因此把這三組數(shù)據(jù)與A站的碼片序列(1』』」)做內(nèi)積運(yùn)算，結(jié)果

分別是(2,020)?(1,11,1)/4=1、(0,-2A-2Ml,LU)/4=-k(0,2A2)-(l,l,1,1)/4=1,所以C接收

到的A發(fā)送的數(shù)據(jù)是101,選B。

38.當(dāng)t時(shí)刻發(fā)生超時(shí)時(shí)，把sslhresh設(shè)為8的一半，即為4,且擁塞窗口設(shè)為1KB。

然后經(jīng)歷10個(gè)RTT后，擁塞窗口的大小依次為2、4、5、6、7、8、9、10、11、12,而

發(fā)送窗口取當(dāng)時(shí)的擁塞窗口和接收窗口的最小值，而接收窗口始終為10KB,所以此時(shí)的

發(fā)送窗口為10KB,選A。實(shí)際上該題接收窗口一直為10KB,可知不管何時(shí)，發(fā)送窗口一

定小于等于10KB,選項(xiàng)中只有A選項(xiàng)滿足條件，可直接得出選A。

39.UDP提供的是無連接的服務(wù)，I正確；同時(shí)UDP也提供復(fù)用/分用服務(wù)，II正確;

UDP雖然有差錯(cuò)校驗(yàn)機(jī)制，但是UDP的差錯(cuò)校驗(yàn)只是檢查數(shù)據(jù)在傳輸?shù)倪^程中有沒有出

錯(cuò)，出錯(cuò)的數(shù)據(jù)直接丟棄，并沒有重傳等機(jī)制，不能保證可靠傳輸，使用UDP協(xié)議時(shí)，

可靠傳輸必須由應(yīng)用層實(shí)現(xiàn)，III錯(cuò)誤；答案選B。

40.當(dāng)接入網(wǎng)絡(luò)時(shí)可能會(huì)用到PPP協(xié)議，A可能用到；而當(dāng)計(jì)算機(jī)不知道某主機(jī)的

MAC地址時(shí)二用IP地址查詢相應(yīng)的MAC地址時(shí)會(huì)用到ARP協(xié)議，B可能用到；而當(dāng)訪

問Web網(wǎng)站時(shí)，若DNS緩沖沒有存儲(chǔ)相應(yīng)域名的IP地址，用域名查詢相應(yīng)的IP地址時(shí)

要使用DNS協(xié)議，而DNS是基于UDP協(xié)議的，所以C可能用到，SMTP只有使用郵件

客戶端發(fā)送郵件，或是郵件服務(wù)器向別的郵件服務(wù)器發(fā)送郵件時(shí)才會(huì)用到，單純的訪問

Web網(wǎng)頁不可能用到。

二、綜合應(yīng)用題

41.解答；考查二叉樹的帶權(quán)路徑長(zhǎng)度，二叉樹的帶權(quán)路徑長(zhǎng)度為每個(gè)葉子結(jié)點(diǎn)的深

度與權(quán)值之積的總利，可以使用先序遍歷或?qū)哟伪闅v解決問題。

1)算法的基本設(shè)計(jì)思想：

①基于先序遞歸遍歷的算法思想是用一個(gè)static變量記錄wpl,把每個(gè)結(jié)點(diǎn)的深度作為

遞歸函數(shù)的一個(gè)參數(shù)傳遞，算法步驟如下：

若該結(jié)點(diǎn)是葉子結(jié)點(diǎn)，那么變量wpl加上該結(jié)點(diǎn)的深度與權(quán)值之積；

若該結(jié)點(diǎn)非葉子結(jié)點(diǎn)，那么若左子樹不為空，對(duì)左子樹調(diào)用遞歸算法，若右子樹不為

空，對(duì)右子樹調(diào)用遞歸算法，深度參數(shù)均為本結(jié)點(diǎn)的深度參數(shù)加一；

最后返回計(jì)算出的wpl即可。

②基于層次遍歷的算法思想是使用隊(duì)列進(jìn)行層次遍歷，并記錄當(dāng)前的層數(shù)，

當(dāng)遍歷到葉子結(jié)點(diǎn)時(shí)，累計(jì)wpl；

當(dāng)遍歷到非葉子結(jié)點(diǎn)時(shí)對(duì)該結(jié)點(diǎn)的把該結(jié)點(diǎn)的子樹加入隊(duì)列；

當(dāng)某結(jié)點(diǎn)為該層的最后一個(gè)結(jié)點(diǎn)時(shí)，層數(shù)自增1;

隊(duì)列空時(shí)遍歷結(jié)束，返回wpl

2）二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：

3）算法代碼如下：

①基于先序遍歷的算法：

②基于層次遍歷的算法：

【評(píng)分說明】①若考生給出能夠滿足題目要求的其他算法，且正確，可同樣給分。

②考生答案無論使用C或者C++語言，只要正確同樣給分。

③若對(duì)算法的基本設(shè)計(jì)思想和主要數(shù)據(jù)結(jié)構(gòu)描述不十分準(zhǔn)確，但在算法實(shí)現(xiàn)中能夠清

晰反映出算法思想且正確，參照①的標(biāo)準(zhǔn)給分。

④若考生給出的二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義和算法實(shí)現(xiàn)中，使用的是除整型之外的其

他數(shù)值，可視同使用整型類型。

⑤若考生給出的答案中算法主要設(shè)計(jì)思想或算法中部分正確，可酌情給分。

注意：上述兩個(gè)算法一個(gè)為遞歸的先序遍歷，一個(gè)為非遞歸的層次遍歷，讀者應(yīng)當(dāng)選

取自己最擅長(zhǎng)的書寫方式。直觀看去，先序遍歷代碼行數(shù)少，不用運(yùn)用其他工具，書寫也

更容易，希望讀者能掌握。

在先序遍歷的算法中，static是一個(gè)靜態(tài)變量，只在首次調(diào)用函數(shù)時(shí)聲明wpl并賦值為

0,以后的遞歸調(diào)用并不會(huì)使得wpl為0,具體用法請(qǐng)參考相關(guān)資料中的sialic關(guān)鍵字說明，

也可以在函數(shù)之外預(yù)先設(shè)置一個(gè)全局變量，并初始化C不過考慮到歷年真題算法答案通常

郤直接僅僅由一個(gè)函數(shù)構(gòu)成，所以參考答案使用static。若對(duì)sialic不熟悉的同學(xué)可以使用

以下形式的遞歸：

C/C++語言基礎(chǔ)好的同學(xué)可以使用更簡(jiǎn)便的以下形式：

這個(gè)形式只是上面方法的簡(jiǎn)化而已，本質(zhì)是一樣的，而這個(gè)形式代碼更短，在時(shí)間有

限的情況下更具優(yōu)勢(shì)，能比寫層次遍歷的考生節(jié)約很多時(shí)間，所以讀者應(yīng)當(dāng)在保證代碼正

確的情況下，盡量寫一些較短的算法，為其他題目贏得更多的時(shí)間。但是，對(duì)于基礎(chǔ)不扎

實(shí)的考生，還是建議使用寫對(duì)把握更大的方法，否則可能會(huì)得不償失。例如在上面的代碼

中，考生容易忘記三元式（x?y:z）兩端的括號(hào)，若不加括號(hào)，則答案就會(huì)是錯(cuò)誤的。

在層次遍歷的算法中，讀者要理解lastNode和newlastNodc的區(qū)別，lastNode指的是

當(dāng)前遍歷層的最后一個(gè)結(jié)點(diǎn)，而newlaslNode指的是下一層的最后一個(gè)結(jié)點(diǎn)，是動(dòng)態(tài)變化

的，直到遍歷到本層的最后一個(gè)結(jié)點(diǎn)，才能確認(rèn)下層真正的最后一個(gè)結(jié)點(diǎn)是哪個(gè)結(jié)點(diǎn)，而

函數(shù)中入隊(duì)操作并沒有判斷隊(duì)滿，若考試時(shí)用到，讀者最好加上隊(duì)滿條件，這里隊(duì)列的隊(duì)

滿條件為endl==（end2+l）%M,采用的是2014年真題選擇題中第三題的隊(duì)列形式。同時(shí)，

考生也可以嘗試使用記錄每層的第一個(gè)結(jié)點(diǎn)來進(jìn)行層次遍歷的算法，這里不再給出代碼，

請(qǐng)考生自行練習(xí)。

42.解答：

考察在給出具體模型時(shí)，數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。該題很多考生乍看之下以為是網(wǎng)絹的題目，

其實(shí)題本身并沒有涉及太多的網(wǎng)絡(luò)知識(shí)點(diǎn)，只是應(yīng)用了網(wǎng)絡(luò)的模型，實(shí)際上考察的還是數(shù)

據(jù)結(jié)構(gòu)的內(nèi)容。

（。圖（1分）

題中給出的是一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)拓?fù)鋱D，可以抽象為無向圖。

【評(píng)分說明】

只要考生的答案中給出與圖含義相似的描述，例如“網(wǎng)狀結(jié)構(gòu)”、“非線性結(jié)構(gòu)”等，同

樣給分。

（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的如下圖所

其數(shù)據(jù)類型定義如下：（3分）

【評(píng)分說明】

①若考生給出的答案是將鏈表中的表頭結(jié)點(diǎn)保存在一個(gè)一維數(shù)組中（即采用鄰接表形

式），同樣給分。

②若考生給出的答案中，弧結(jié)點(diǎn)沒有使用union定義，而是采用兩種不同的結(jié)構(gòu)分別

表示Link和Net,同時(shí)在表頭結(jié)點(diǎn)中定義了兩個(gè)指針，分別指向由這兩種類型的結(jié)點(diǎn)構(gòu)成

的兩個(gè)鏈表，同樣給分。

③考生所給答案的弧結(jié)點(diǎn)中，可以在單獨(dú)定義的域中保存各直連網(wǎng)絡(luò)IP地址的前綴長(zhǎng)

度，也可以與網(wǎng)絡(luò)地址保存在同一個(gè)域中。

④數(shù)據(jù)類型定義中，只要采用了可行的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并保存了題目中所給的LSI信

息，例如將網(wǎng)絡(luò)抽象為一類結(jié)點(diǎn)，寫出含8個(gè)表頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，均可參照①?③

的標(biāo)準(zhǔn)給分。

⑤若考生給出的答案中，圖示部分應(yīng)與其數(shù)據(jù)類型定義部分一致，圖示只要能夠體現(xiàn)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及題42圖中的網(wǎng)絡(luò)連接關(guān)系（可以不給出結(jié)點(diǎn)內(nèi)細(xì)節(jié)信息），即可給分。

⑥若解答不完全正確，酌情給分。

（3）計(jì)算結(jié)果如下表所示。（4分）

【評(píng)分說明】

①若考生給出的各條最短路徑的結(jié)果部分正確，可酌情給分。

43.解答：

【評(píng)分說明】

①每正確解答一個(gè)路由項(xiàng)，給2分，共6分。

②路由項(xiàng)解答不完全正確，或路由項(xiàng)多于3條，可酌情給分。

（2）Metric為10。（1分）

【評(píng)分說明】

44.解答：

該題為計(jì)算機(jī)組成原理科目的綜合題型，涉及到指令系統(tǒng)、存儲(chǔ)管理以及CPU三個(gè)部

分內(nèi)容，考生因注意各章節(jié)內(nèi)容之間的聯(lián)系，才能更好的把握當(dāng)前考試的趨勢(shì)。

（1）已知計(jì)算機(jī)M采用32位定長(zhǎng)指令字，即一條指令占4B,觀察表中各指令的地址可

知，每條指令的地址差為4個(gè)地址單位，即4個(gè)地址單位代表4B,一個(gè)地址單位就代表了

1B,所以該計(jì)算機(jī)是按字節(jié)編址的。（2分）

（2）在二進(jìn)制中某數(shù)左移二位相當(dāng)于以乘四，由該條件可知，數(shù)組間的數(shù)據(jù)口隔為4個(gè)

地址單位，而計(jì)算機(jī)按字節(jié)編址，所以數(shù)組A中每個(gè)元素占4B。（2分）

（3）由表可知，bne指令的機(jī)器代碼為1446FFFAH,根據(jù)題目給出的指令格式，后2B

的內(nèi)容為OFFSET字段，廳以該指令的OFFSET字段為FFFAH,用補(bǔ)碼表示，值為-6。（I

分）當(dāng)系統(tǒng)執(zhí)行到bne指令時(shí)，PC自動(dòng)加4,PC的內(nèi)容就為08048118H,而跳轉(zhuǎn)的目標(biāo)是

（）8（）4810（）H,兩者相差了18H,即24個(gè)單位的地址間隔，所以偏移址的一位即是真實(shí)跳轉(zhuǎn)

地址的-24/?6=4位。（1分）可知bne指令的轉(zhuǎn)移目標(biāo)地址計(jì)算公式為（PC）+4+OFFSET*4。（1

分）

（4）由于數(shù)據(jù)相關(guān)而發(fā)生阻塞的指令為第2、3、4、6條,因?yàn)榈?、3、4、6條指令都

與各自前一條指令發(fā)生數(shù)捱相關(guān)。（3分）

第6條指令會(huì)發(fā)生控制冒險(xiǎn)。（1分）

第7條當(dāng)前循環(huán)的第五條指令與下次循環(huán)的第一條指令雖然有數(shù)據(jù)相關(guān)，但由于第6

條指令后有3個(gè)時(shí)鐘周期的阻塞，因而消除了該數(shù)據(jù)相關(guān)。（1分）

【評(píng)分說明】

對(duì)于第1問，若考生回答：因?yàn)橹噶?和2、2和3、3和4、5和6發(fā)生數(shù)據(jù)相關(guān)，

因而發(fā)生阻塞的指令為第2、3、4、6條，同樣給3分。答對(duì)3個(gè)以上給3分，部分正確

酌情給分。

45.解答：

該題繼承了上題中的相關(guān)信息，統(tǒng)考中首次引入此種設(shè)置，具體考察到程序的運(yùn)行結(jié)

果、Cache的大小和命中率的計(jì)算以及磁盤和TLB的相關(guān)計(jì)算，是一題比較綜合的題型。

（1）R2里裝的是i的值，循環(huán)條件是i<N（1000）,即當(dāng)i自增到不滿足這個(gè)條件時(shí)跳出

循環(huán)，程序結(jié)束，所以此時(shí)i的值為lOOOo（1分）

（2）Cache共有16行，每塊32字節(jié)，所以Cache數(shù)據(jù)區(qū)的容量為16*32B=512B。（1分）

P共有6條指令,占24字節(jié)，小于主存塊大?。?2B）,其起始地址為08048100H,對(duì)

應(yīng)一塊的開始位置，由此可知所有指令都在一個(gè)主存塊內(nèi)。讀取第一條指令時(shí)會(huì)發(fā)生Cac