2014年全國碩士研究生入學統一考試

計算機科學與技術學科聯考計算機學科專業基礎綜合試題

一、單項選擇題：

第1?40小題，每小題2分，共80分。

下列每題給出的四個選項中，只有一個選項最符合試題要求。？

1.下列程序段的時間復雜度是。

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.假設棧初始為空，將中綴表達式a/b+(c%-e*f)/g轉換為等價的后綴表達式的過程中，

當掃描到f時，棧中的元素依次是?。？

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

3.循環隊列放在一維數組A0..M-1］中，endl指向隊頭元素，end2指向隊尾元素的

后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M-1個元素。初

始時為空。下列判斷隊空和隊滿的條件中，正確的是?。

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

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

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

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

4.若對如下的二叉樹進行中序線索化，則結點x的左、右線索指向的結點分別是。？

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

5.將森林F轉換為對應的二叉樹T,F中葉結點的個數等于。？

A.T中葉結點的個數”?B.T中度為1的結點個數？

C.T中左孩子指針為空的結點個數?D.T中右孩子指針為空的結點個數

?6.5個字符有如下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.對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是。？

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.用哈希(散列)方法處理沖突(碰撞)時可能出現堆積(聚集)現象，下列選項

中，會受堆積現象直接影響的是。

A.存儲效率B.散列函數C.裝填(裝載)因子D.平均查找長度

9.在一棵具有15個關鍵字的4階B樹中，含關鍵字的結點個數最多是。

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

10.用希爾排序方法對一個數據序列進行排序時，若第1趟排序結果為

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

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

11.下列選項中，不可能是快速排序第2趟排序結果的是。

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在機器M上的執行時間是2()秒，編譯優化后，P執行的指令數減少到原

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

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

13.若x=103,y=25,則下列表達式采用8位定點補碼運算實現時，會發生溢出的是。

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

14.float型數據據常用IEEE754單精度浮點格式表示。假設兩個float型變量x和y

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

的關系為。

A.x<y且符號相同B.x<y且符號不同C.x>y且符號相同D.x>y且符號不同

15.某容量為256MB的存儲器由若干4Mx8位的DRAM芯片構成，該DRAM芯片

的地址引腳和數據引腳總數是。

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

16.采用指令Cache與數據Cache分離的主要目的是。

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

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

17.某計算機有16個通用寄存器，采用32位定長指令字，操作碼字段(含尋址方式

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

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

值范圍是。

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

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

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

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

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

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

19.某同步總線采用數據線和地址線復用方式，其中地址/數據線有32根，總線時鐘

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

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

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

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

連續單元讀出或寫入多個數據。這種總線事務方式稱為。

A.并行傳輸B.串行傳輸C.突發傳輸D.同步傳輸

21.下列有關I/O接口的敘述中，錯誤.?的是。

A.狀態端口和控制端口可以合用同一個寄存器

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

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

D.采用統一編址方式時，CPU不能用訪存指令訪問I/O端口

22.若某設備中斷請求的響應和處理時間為l()()ns,每4()0ns發出一次中斷請求，中

斷響應所允許的最長延遲時間為50ns,則在該設備持續工作過程中，CPU用于該設備的I/O

時間占整個CPU時間的百分比至少是。

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

23.下列調度算法中，不可能導致饑餓現象的是c

A.時間片輪轉B.靜態優先數調度

C.非搶占式短作業優先D.搶占式短作業優先

24.某系統有n臺互斥使用的同類設備，三個并發進程分別需要3、4、5臺設備，可

確保系統不.發生.?死鎖的設備數n最小為。

A.9B.IOC.11D.12

25.下列指令中，不能..在用戶態執行的是。

A.trap指令B.跳轉指令C.壓棧指令D.關中斷指令

26.一個進程的讀磁盤操作完成后，操作系統針對該進程必做的是。

A.修改進程狀態為就緒態B.降低進程優先級

C.給進程分配用戶內存空間D.增加進程時間片大小

27.現有一個容量為10GB的磁盤分區，磁盤空間以簇(Cluster)為單位進行分配，簇的

大小為4KB,若采用位圖法管理該分區的空閑空間，即用一位(bil)標識一個簇是否被分配,

則存放該位圖所需簇的個數為。

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

28.下列措施中，能加快虛實地址轉換的是。

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

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

29.在一個文件被用戶進程首次打開的過程中，操作系統需做的是。

A.將文件內容讀到內存中B.將文件控制塊讀至J內存中

C.修改文件控制塊中的讀寫權限D.將文件的數據緩沖區首指針返回給用戶進程

30.在頁式虛擬存儲管理系統中，采用某些頁面置換算法，會出現Belady異?，F象，

即進程的缺頁次數會隨著分配給該進程的頁框個數的增加而增加。下列算法中，可能出現

Belady異常現象的是。

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

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

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

A.一個管道可實現雙向數據傳輸

B.管道的容量僅受磁盤容最大小限制

C.進程對管道進行讀操作和寫操作都可能被阻塞

D.一個管道只能有一個讀進程或一個寫進程對其操作

32.下列選項中，屬于多級頁表優點的是。

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

C.減少頁表項所占字節數D.減少頁表所占的連續內存空間

33.在OSI參考模型中，直接為會話層提供服務的是。

A.應用層B.表示層C.傳輸層D.網絡層

34.某以太網拓撲及交換機當前轉發表如下圖所示，主機00-el-d5-()0-23-al向主機

00-el-d5-00-23-cl發送1個數據幀，主機00-el-d5-00-23-cl收到該幀后,向主機

00-el-d5-00-23-al發送1個確認幀,交換機對這兩個幀的轉發端口分別是()。

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

35.下列因素中，不會影響信道數據傳輸速率的是。

A.信噪比B.頻率寬帶C.調制速率D.信號傳播速度

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

1(X)(),數據幀長為1()0()字節，信道帶寬為100Mbps,乙每收到一個數據幀立即利用一個

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

大平均數據傳輸速率約為。

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

37.站點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發送的數據是。

A.OOOB.1O1C.HOD.Ill

38.主機甲和主機乙已建立了TCP連接，甲始終以MSS=1KB大小的段發送數據，并

一直有數據發送；乙每收到一個數據段都會發出一個接收窗口為10KB的確認段。若甲在

t時刻發生超時時擁塞窗口為8KB,則從t時刻起，不再發生超時的情況下，經過1（）個RTT

后，甲的發送窗口是。

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

39.下列關于UDP協議的敘述中，正確..的是。

I.提供無連接服務II.提供復用/分用服務HI.通過差錯校驗，保障可靠數據傳輸

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

40.使用瀏覽器訪問某大學Web網站主頁時，不可能使用到的協議是。

A.PPPB.ARPC.UDPD.SMTP

二、綜合應用題：41-47小題，共70分。

41.（13分）二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結點的帶權路徑長度之和。

給定一棵二叉樹T,采用二叉鏈表存儲，結點結構為：

其中葉結點的weight城保存該結點的非負權值。設root為指向T的根結點的指針，請

設計求T的WPL的算法，要求：

1）給出算法的基本設計思想；

2）使用C或C++語言，給出二叉樹結點的數據類型定義；

3）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。

42.（1（）分）某網絡中的路由器運行OSPF路由協議，題42表是路由器R1維護的主要

鏈路狀態信息（LSI）,題42組是根據題42表及R1的接口名構造出來的網絡拓撲。

題42圖R1構造的網絡拓撲

請回答下列問題：

I）本題中的網絡可抽象為數據結構中的哪種邏輯結構？

2）針對題42表中的內容，設計合理的鏈式存儲結構，以保存題42表中的鏈路狀態

信息（LSI）。要求給出鏈式存儲結構的數據類型定義，并畫出對應題42表的鏈式存儲結構

示意圖（示意圖中可僅以ID標識結點）。

43.19分）請根據題42描述的網絡，繼續回答下列問題。1）假設路由表結構如下

表所示，請給出題42圖中R1的路由表，要求包括到達題42

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

哪些信息？

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

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

址在寄存器R3中。程序段P起始地址為08048100H,對應的匯編代碼和機器代碼如下表

所示。

OP為操作碼;；Rs和Rd為寄存器編號；OFFSET為偏移量，用補碼表示。請回答下

列問題，并說明理由。

1）M的存儲器編址單位是什么？

2）己知sll指令實現左移功能，數組A中每個元素占多少位？

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

當前PC內容為bne指令地址，通過分析題44表中指令地址和bne指令內容，推斷出bne

指令的轉移目標地址計算公式。

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

及取數）、EXE（執行）、MEM（訪存）、WB（寫回寄存器），且硬件不采取任何轉發

措施，分支指令的執行均引起3個時鐘周期的阻塞，則P中哪些指令的執行會由于數據相

關而發生流水線阻塞？哪條指令的執行會發生控制冒險？為什么指令1的執行不會囚為與

指令5的數據相關而發生阻塞？

45.假設對于44題中的計算機M和程序P的機器代碼，M采用頁式虛擬存儲管理；

P開始執行時，(Rl)=(R2)=0,(R6)=1000,其機器代碼已調入主存但不在Cache中；數組A

未調入主存，且所有數組元素在同一頁，并存儲在磁盤同一個扇區。請回答下列問題并說

明理由。1)P執行結束時，R2的內容是多少？

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

的塊大小為32字節，則其數據區的容量是多少？若僅考慮程序段P的執行，則指令Cache

的命中率為多少？

3)P在執行過程中，哪條指令的執行可能發生溢出異常？哪條指令的執行可能產生缺

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

46.文件F由200條記錄組成，記錄從1開始編號。用戶打開文件后，欲將內存中的

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

I)若文件系統采用連續分配方式，每個磁盤塊存放一條記錄，文件F存儲區域前后

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

制塊內容會發生哪些改變？

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

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

接指針，則該文件系統支持的文件最大長度是多少？

47.系統中有多個生產者進程和多個消費者進程，共享一個能存放1000件產品的環形

緩沖區(初始為空)。當緩沖區未滿時，生產者進程可以放入其生產的一件產品，否則等

待；當緩沖區未空時，消費者進程可以從緩沖區取走一件產品，否則等待。要求一個消費

者進程從緩沖區連續取出10件產品后，其他消費者進程才可以取產品。請使用信號量P，

V(wait(),signal。)操作實現進程間的互斥與同步，要求寫出完整的過程，并說明所用信號

量的含義和初值。

2014年計算機學科專業基礎綜合試題參考答案

一、單項選擇題

(一)單選題答案

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.內層循環條件j<=n與外層循環的變量無關，每次循環j自增1,每次內層循環都執

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

所以內層循環的時間復雜度是O(n),外層循環的時間復雜度是O(log2n)。對于嵌套循環，

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

2.將中綴表達式轉換為后綴表達式的算法思想如下：

從左向右開始掃描中綴表達式；

遇到數字時，加入后綴表達式；

遇到運算符時：

a.若為'('，入棧;

b.若為)，則依次把棧中的的運算符加入后綴表達式中，直到出現C從棧中刪除C

c.若為除括號外的其他運算符，當其優先級高于除'('以外的棧頂運算符時，直接入棧。

否則從棧頂開始，依次彈出比當前處理的運算符優先級高和優先級相等的運算符，直到一

個比它優先級低的或者遇到了一個左括號為止。

當掃描的中綴表達式結束時，棧中的所有運算符依次出棧加入后綴表達式。

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

在此，再給出中綴表達式轉換為前綴或后綴表達式的一種手工做法，以上面給出的中

綴表達式為例：

第一步：按照運算符的優先級對所有的運算單位加括號。式子變成了：

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

第二步：轉換為前綴或后綴表達式。

前綴：把運算符號移動到對應的括號前而，則變成了：+(/(ab)/(-(*(cd)*(ef))g))把括號

去掉：+/ab/-*cd*efg前綴式子出現。

后綴：把運算符號移動到對應的括號后面，則變成了：((ab)/(((cd)*(ct)*)-g)/)+把括號

去掉：ab/cd*ef*-g/+后綴式子出現。

當題目要求直接求前綴或后綴表達式時，這種方法會比上一種快捷得多。

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

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

lo若把A[()]儲存第一個元素，當隊列初始時，入隊操作是先把數據放到A[()],然后end2

自增，即可知end2初值為0；而endl指向的是隊頭元素，隊頭元素的在數組A中的下標

為0,所以得知endl初值也為0,可知隊空條件為endl==end2；然后考慮隊列滿時,因為

隊列最多能容納M-1個元素，假設隊列存儲在下標為0到下標為M-2的M-1個區域，隊

頭為A[0],隊尾為A[M-2],此時隊列滿，考慮在這種情況下endl和cnd2的狀態，endl

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

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

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

答案，并可以畫出簡單的草圖以方便解題。

4.線索二叉樹的線索實際上指向的是相應遍歷序列特定結點的前驅結點和后繼結

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

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

5.將森林轉化為二叉樹即相當于用孩子兄弟表示法表示森林。在變化過程中，原森

林某結點的第一個孩子結點作為它的左子樹，它的兄弟作為它的右子樹。那么森林中的葉

結點由于沒有孩子結點，那么轉化為二叉樹時，該結點就沒有左結點，所以F中葉結點的

個數就等于T中左孩子指針為空的結點個數，選C。

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

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

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

碼。

7.按照拓撲排序的算法，每次都選擇入度為0的結點從圖中刪去，此圖中一開始只

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

的入度為0;刪掉4結點后，結點2和結點6的入度都為0,此時選擇刪去不同的結點，

會得出不同的拓撲序列，分別處理完畢后可知可能的拓撲序列為314265和314625,選D。

8.產生堆積現象，即產生了沖突，它對存儲效率、散列函數和裝填因子均不會有影

響，而平均查找長度會因為堆積現象而增大，選D。

9.關鍵字數量不變，要求結點數量最多，那么即每個結點中含關鍵字的數量最少。

根據4階B樹的定義，根垢點最少含1個關鍵字，非根結點中最少含?4/2?-1=1個關鍵字,

所以每個結點中，關鍵字數量最少都為1個，即每個結點都有2個分支，類似與排序二叉

樹，而15個結點正好可以構造一個4層的4階B樹，使得葉子結點全在第四層，符合B

樹定義，因此選D。

10.首先，第二個元素為1,是整個序列中的最小元素，所以可知該希爾排序為從小

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

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

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

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

11.快排的階段性排序結果的特點是，第i趟完成時，會有i個以上的數出現在它最

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

結果，即要找不存在2個這樣的數的選項。A選項中2、3、6、7、9均符合，所以A排除;

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

C選項，只有9一個數符合，所以C不可能是快速排序第二趟的結果。

12.不妨設原來指令條數為x,那么原CPI就為20/x,經過編譯優化后，指令條數減

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

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

13.8位定點補碼表示的數據范圍為-128727,若運算結果超出這個范圍則會溢出，A

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

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

該題也可按照二進制寫出兩個數進行運算觀察運算的進位信息得到結果，不過這種方

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

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

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

又因為是IEEE754規格化的數，尾數部分均為l.xxx,則階碼大的數，真值的絕對值必然

大，可知(")真值的絕對值大于(⑵真值的絕對值，因為都為負數，則⑴)<(⑵，即xvy。

15.4Mx8位的芯片數據線應為8根，地址線應為log24M=22根，而DRAM采用地址

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

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

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

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

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

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

突。

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

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

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

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

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

18.計算機共有32條指令，各個指令對應的微程序平均為4條，則指令對應的微指

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

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

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

時鐘周期，而每個時許周期傳送兩次數據，可知總線每秒傳送的最大數據量為

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

20.猝發(突發)傳輸是在一個總線周期中，可以傳輸多個存儲地址連續的數據，即一

次傳輸一個地址和一批地址連續的數據，并行傳輸是在傳輸中有多個數據位同時在設備之

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

逐位傳輸的方式，同步傳輸是指傳輸過程由統一的時鐘控制，選C。

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

以訪問I/O端口，D選項錯誤，其他三個選項均為正確陳述，選D。

22.每400ns發出一次中斷請求,而響應和處理時間為100ns,其中容許的延遲為干

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

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

23.采用靜態優先級調度時，當系統總是出現優先級高的任務時，優先級低的任務會

總是得不到處理機而產生饑餓現象；而短作業優先調度不管是搶占式或是非搶占的，當系

統總是出現新來的短任務時，長任務會總是得不到處理機，產生饑餓現象，因此B、C、D

都錯誤，選A。

24.三個并發進程分別需要3、4、5臺設備，當系統只有(3-1)+(4?1)+(5-1)=9臺設備時,

第一個進程分配2臺，第二個進程分配3臺，第三個進程分配4臺。這種情況下，三個進

程均無法繼續執行下去，發生死鎖。當系統中再增加1臺設備，也就是總共10臺設備時,

這最后1臺設備分配給任意一個進程都可以順利執行完成，因此保證系統不發生死鎖的最

小設備數為10o

25.irap指令、跳轉指令和壓棧指令均可以在用戶態執行，其中tr叩指令負責由用戶

態轉換成為內核態。而關中斷指令為特權指令，必須在核心態才能執行，選D。

26.進程申請讀磁盤操作的時候，因為要等待I/O操作完成，會把自身阻塞，此時進

程就變為了阻塞狀態，當I/O操作完成后，進程得到了想要的資源，就會從阻塞態轉換到

就緒態(這是操作系統的行為)。而降低進程優先級、分配用戶內存空間和增加進程的時

間片大小都不一定會發生，選A。

27.簇的總數為10GB；4KB=2.5M,用一位標識一簇是否被分配，則整個磁盤共需要

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

28.虛實地址轉換是指邏輯地址和物理地址的轉換。增大快表容量能把更多的表項裝

入快表中，會加快虛實地址轉換的平均速率；讓頁表常駐內存可以省去一些不在內存中的

頁表從磁盤上調入的過程，也能加快虛實地址變換；增大交換區對虛實地址變換速度無影

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

29.一個文件被用戶進程首次打開即被執行了Open操作，會把文件的FCB調入內存,

而不會把文件內容讀到內存中，只有進程希望獲取文件內容的時候才會讀入文件內容；C、

D明顯錯誤，選B。

30.只有FIFO算法會導致Belady異常，選A。

31.管道實際上是一種固定大小的緩沖區，管道對于管道兩端的進程而言，就是一個

文件，但它不是普通的文件，它不屬于某種文件系統，而是自立門戶，單獨構成一種文件

系統，并且只存在于內存中。它類似于通信中半雙工信道的進程通信機制，一個管道可以

實現雙向的數據傳輸，而同一個時刻只能最多有一個方向的傳輸，不能兩個方向同時進行。

管道的容量大小通常為內存上的一頁，它的大小并不是受磁盤容量大小的限制。當管道滿

時，進程在寫管道會被阻塞，而當管道空時，進程讀管道會被阻塞，因此選C。

32.多級頁表不僅不會加快地址的變換速度，還因為增加更多的查表過程，會使地址

變換速度減慢；也不會減少缺頁中斷的次數，反而如果訪問過程中多級的頁表都不在內存

中，會大大增加缺頁的次數，也并不會減少頁表項所占的字節數(詳細解析參考二段)，而

多級頁表能夠減少頁表所占的連續內存空間，即當頁表太大時，將頁表再分級，可以把每

張頁表控制在一頁之內，減少頁表所占的連續內存空間，因此選D。補充：頁式管理中每

個頁表項的大小的下限如何決定？頁表項的作用是找到該頁在內存的位置，以32位邏輯

地址空間，字節為編址單位，一頁4KB為例，地址空間內一共含有232B/4KB=1M頁，則

需要log21M=20位才能保證表示范圍能容納所有頁面，乂因為以字節作為編址單位，即頁

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

表項的大小應該大于3B,當然，也可以選擇更大的頁表項大小以至于讓一個頁面能夠正好

容下整數個頁表項以方便存儲(例如取成4B,那么一頁正好可以裝下1K個頁表項)，或

者增加一些其他信息。

33.直接為會話層提供服務的即會話層的下一層，是傳輸層，選C。

34.主機()O-el-d5-OO-23-al向00-el-d5-00-23-cl發送數據幀時,交換機轉發表中沒有

00-el-d5-00-23-cl這項，所以向除1接口外的所有接匚廣播這幀,即2、3端口會轉發這幀,

同時因為轉發表中并沒有00-el-d5-00-23-al這項，所以轉發表會把(目的地址

00-el-d5-00-23-al,端口1)這項加入轉發表。而當00-el-d5-00-23-cl向00-el-d5-00-23-al

發送確認幀時，由于轉發表已經有00-el-d5-00-23-al這項，所以交換機只向1端口轉發，

選Bo

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

比和頻率帶寬對信道的數據傳輸速率是有影響的，A、B錯誤；信道的傳輸速率實際上就

是信號的發送速率，而調制速度也會直接限制數據的傳輸速率，C錯誤；信號的傳播速度

是信號在信道上傳播的速度，與信道的發送速率無關，選D。

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

傳輸速率一定是小于等于信道帶寬的；其次，主機甲乙之間采用后退N幀協議，那么因為

甲乙主機之間采用后退N幀協議傳輸數據?，要考慮發送一個數據到接收到它的確認之前，

最多能發送多少數據，甲的最大傳輸速率受這兩個條件的約束，所以甲的最大傳輸速率是

這兩個值中小的那一個。甲的發送窗口的尺寸為1000,即收到第一個數據的確認之前，最

多能發送1000個數據幀,也就是發送1000*1000B=lMB的內容，而從發送第一個幀到接

收到它的確認的時間是一個往返時延，也就是50+50=100ms=0.1s,即在100ms中，最多能

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

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

37.把收到的序列分成每4個數字一組，即為(2,0,2,0)、(0,-2,0,-2)、(0,2,0,2),因為題

目求的是A發送的數據，因此把這三組數據與A站的碼片序列(1』』」)做內積運算，結果

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

到的A發送的數據是101,選B。

38.當t時刻發生超時時，把sslhresh設為8的一半，即為4,且擁塞窗口設為1KB。

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

發送窗口取當時的擁塞窗口和接收窗口的最小值，而接收窗口始終為10KB,所以此時的

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

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

39.UDP提供的是無連接的服務，I正確；同時UDP也提供復用/分用服務，II正確;

UDP雖然有差錯校驗機制，但是UDP的差錯校驗只是檢查數據在傳輸的過程中有沒有出

錯，出錯的數據直接丟棄，并沒有重傳等機制，不能保證可靠傳輸，使用UDP協議時，

可靠傳輸必須由應用層實現，III錯誤；答案選B。

40.當接入網絡時可能會用到PPP協議，A可能用到；而當計算機不知道某主機的

MAC地址時二用IP地址查詢相應的MAC地址時會用到ARP協議，B可能用到；而當訪

問Web網站時，若DNS緩沖沒有存儲相應域名的IP地址，用域名查詢相應的IP地址時

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

客戶端發送郵件，或是郵件服務器向別的郵件服務器發送郵件時才會用到，單純的訪問

Web網頁不可能用到。

二、綜合應用題

41.解答；考查二叉樹的帶權路徑長度，二叉樹的帶權路徑長度為每個葉子結點的深

度與權值之積的總利，可以使用先序遍歷或層次遍歷解決問題。

1)算法的基本設計思想：

①基于先序遞歸遍歷的算法思想是用一個static變量記錄wpl,把每個結點的深度作為

遞歸函數的一個參數傳遞，算法步驟如下：

若該結點是葉子結點，那么變量wpl加上該結點的深度與權值之積；

若該結點非葉子結點，那么若左子樹不為空，對左子樹調用遞歸算法，若右子樹不為

空，對右子樹調用遞歸算法，深度參數均為本結點的深度參數加一；

最后返回計算出的wpl即可。

②基于層次遍歷的算法思想是使用隊列進行層次遍歷，并記錄當前的層數，

當遍歷到葉子結點時，累計wpl；

當遍歷到非葉子結點時對該結點的把該結點的子樹加入隊列；

當某結點為該層的最后一個結點時，層數自增1;

隊列空時遍歷結束，返回wpl

2）二叉樹結點的數據類型定義如下：

3）算法代碼如下：

①基于先序遍歷的算法：

②基于層次遍歷的算法：

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

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

③若對算法的基本設計思想和主要數據結構描述不十分準確，但在算法實現中能夠清

晰反映出算法思想且正確，參照①的標準給分。

④若考生給出的二叉樹結點的數據類型定義和算法實現中，使用的是除整型之外的其

他數值，可視同使用整型類型。

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

注意：上述兩個算法一個為遞歸的先序遍歷，一個為非遞歸的層次遍歷，讀者應當選

取自己最擅長的書寫方式。直觀看去，先序遍歷代碼行數少，不用運用其他工具，書寫也

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

在先序遍歷的算法中，static是一個靜態變量，只在首次調用函數時聲明wpl并賦值為

0,以后的遞歸調用并不會使得wpl為0,具體用法請參考相關資料中的sialic關鍵字說明，

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

郤直接僅僅由一個函數構成，所以參考答案使用static。若對sialic不熟悉的同學可以使用

以下形式的遞歸：

C/C++語言基礎好的同學可以使用更簡便的以下形式：

這個形式只是上面方法的簡化而已，本質是一樣的，而這個形式代碼更短，在時間有

限的情況下更具優勢，能比寫層次遍歷的考生節約很多時間，所以讀者應當在保證代碼正

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

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

中，考生容易忘記三元式（x?y:z）兩端的括號，若不加括號，則答案就會是錯誤的。

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

當前遍歷層的最后一個結點，而newlaslNode指的是下一層的最后一個結點，是動態變化

的，直到遍歷到本層的最后一個結點，才能確認下層真正的最后一個結點是哪個結點，而

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

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

考生也可以嘗試使用記錄每層的第一個結點來進行層次遍歷的算法，這里不再給出代碼，

請考生自行練習。

42.解答：

考察在給出具體模型時，數據結構的應用。該題很多考生乍看之下以為是網絹的題目，

其實題本身并沒有涉及太多的網絡知識點，只是應用了網絡的模型，實際上考察的還是數

據結構的內容。

（。圖（1分）

題中給出的是一個簡單的網絡拓撲圖，可以抽象為無向圖。

【評分說明】

只要考生的答案中給出與圖含義相似的描述，例如“網狀結構”、“非線性結構”等，同

樣給分。

（2）鏈式存儲結構的如下圖所

其數據類型定義如下：（3分）

【評分說明】

①若考生給出的答案是將鏈表中的表頭結點保存在一個一維數組中（即采用鄰接表形

式），同樣給分。

②若考生給出的答案中，弧結點沒有使用union定義，而是采用兩種不同的結構分別

表示Link和Net,同時在表頭結點中定義了兩個指針，分別指向由這兩種類型的結點構成

的兩個鏈表，同樣給分。

③考生所給答案的弧結點中，可以在單獨定義的域中保存各直連網絡IP地址的前綴長

度，也可以與網絡地址保存在同一個域中。

④數據類型定義中，只要采用了可行的鏈式存儲結構，并保存了題目中所給的LSI信

息，例如將網絡抽象為一類結點，寫出含8個表頭結點的鏈式存儲結構，均可參照①?③

的標準給分。

⑤若考生給出的答案中，圖示部分應與其數據類型定義部分一致，圖示只要能夠體現

鏈式存儲結構及題42圖中的網絡連接關系（可以不給出結點內細節信息），即可給分。

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

（3）計算結果如下表所示。（4分）

【評分說明】

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

43.解答：

【評分說明】

①每正確解答一個路由項，給2分，共6分。

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

（2）Metric為10。（1分）

【評分說明】

44.解答：

該題為計算機組成原理科目的綜合題型，涉及到指令系統、存儲管理以及CPU三個部

分內容，考生因注意各章節內容之間的聯系，才能更好的把握當前考試的趨勢。

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

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

1B,所以該計算機是按字節編址的。（2分）

（2）在二進制中某數左移二位相當于以乘四，由該條件可知，數組間的數據口隔為4個

地址單位，而計算機按字節編址，所以數組A中每個元素占4B。（2分）

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

的內容為OFFSET字段，廳以該指令的OFFSET字段為FFFAH,用補碼表示，值為-6。（I

分）當系統執行到bne指令時，PC自動加4,PC的內容就為08048118H,而跳轉的目標是

（）8（）4810（）H,兩者相差了18H,即24個單位的地址間隔，所以偏移址的一位即是真實跳轉

地址的-24/?6=4位。（1分）可知bne指令的轉移目標地址計算公式為（PC）+4+OFFSET*4。（1

分）

（4）由于數據相關而發生阻塞的指令為第2、3、4、6條,因為第2、3、4、6條指令都

與各自前一條指令發生數捱相關。（3分）

第6條指令會發生控制冒險。（1分）

第7條當前循環的第五條指令與下次循環的第一條指令雖然有數據相關，但由于第6

條指令后有3個時鐘周期的阻塞，因而消除了該數據相關。（1分）

【評分說明】

對于第1問，若考生回答：因為指令1和2、2和3、3和4、5和6發生數據相關，

因而發生阻塞的指令為第2、3、4、6條，同樣給3分。答對3個以上給3分，部分正確

酌情給分。

45.解答：

該題繼承了上題中的相關信息，統考中首次引入此種設置，具體考察到程序的運行結

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

（1）R2里裝的是i的值，循環條件是i<N（1000）,即當i自增到不滿足這個條件時跳出

循環，程序結束，所以此時i的值為lOOOo（1分）

（2）Cache共有16行，每塊32字節，所以Cache數據區的容量為16*32B=512B。（1分）

P共有6條指令,占24字節，小于主存塊大小（32B）,其起始地址為08048100H,對

應一塊的開始位置，由此可知所有指令都在一個主存塊內。讀取第一條指令時會發生Cac