一、單項(xiàng)選擇題：1~40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是符合題目要求的。

1. 下列程常段的時(shí)間復(fù)雜度是

count=0;

for(k=1;k<=n;k^*=2)

for(j=1;j<=n;j+1)

count++;

A.O(log₂n)          B.O(n)              C.O(nlog₂n)           D.O(n²)

2. 假設(shè)棧初始為空，將中綴表達(dá)式轉(zhuǎn)換為等價(jià)后綴表達(dá)式的過(guò)程中，當(dāng)掃描到f時(shí)，棧中的元素依次是

A．         B.             C.         D.

3. 循環(huán)兩列放在一維數(shù)組A[0…M-1]中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空，下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是

A.隊(duì)空：end1==end2；  隊(duì)滿：end1==(end2+1)modM

B.隊(duì)空：end1==end2;   隊(duì)滿：end2==(end1+1)mod(M-1)

C.隊(duì)空：end2==(end1+1)modM ;       隊(duì)滿：end1==（end2+1）modM

D.隊(duì)空：end1==（end2+1）modM;     隊(duì)滿：end2==(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(xiàn)中葉結(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.000,001,010,011,100

7. 對(duì)如下所示的有向圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)湫蛄锌赡苁?/span>

A.3,1,2,4,5,6              B.3,1,2,4,6,5         

C.3,1,4,2,5,6              D.3,1,4,2,6,5

8. 用哈希（散列）方法處理沖突（碰撞）時(shí)可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項(xiàng)中，會(huì)受堆積現(xiàn)象直接影響的是

A.存儲(chǔ)效率            B.數(shù)列函數(shù)          

C.裝填（裝載）因子    D.平均查找長(zhǎng)度

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

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

10. 用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是

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

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

A.2,3,5,4,6,7,9              B.2,7,5,6,4,3,9         

C.3,2,5,4,7,6,9              D.4,2,3,5,7,6,9

12. 程序P在機(jī)器M上的執(zhí)行時(shí)間是20秒，編譯優(yōu)化后，P執(zhí)行的指令數(shù)減少到原來(lái)的70%，而CPI增加到原來(lái)的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+y     B  -x+y      C  x-y       D   -x-y

14. float型整數(shù)據(jù)常用IEEE754單精度浮點(diǎn)格式表示，假設(shè)兩個(gè)float型變量x和y分別在32為寄存器f₁和f₂中，若（f₁）=CC900000H, （f₂）=B0C00000H,則x和y之間的關(guān)系為：

A  x<y且符號(hào)相同  B  x

15. 某容量為256M的存儲(chǔ)器，由若干4M*8位的DRAM芯片構(gòu)成，該DRAM芯片的地址引腳和數(shù)據(jù)引腳總數(shù)是：    

A  19       B  22     C  30    D  36

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

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

C  減低CPU平均訪問(wèn)時(shí)間                     D  減少指令流水線資源沖突

17. 某計(jì)算機(jī)有16個(gè)通用寄存器，采用32位定長(zhǎng)指令字操作碼字段（含尋址方式位）為8位，Store指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址方式，若基址寄存器可使用任一通用寄存器，且偏移量用補(bǔ)碼表示，則Store指令中偏移量的取值范圍是

A  -32768~+32768  B  -32767~+32768   C  -65536~+65535   D  -65535~+65536

18. 某計(jì)算機(jī)采用微程序控制器，共有32條指令，公共的取指令微程序包含2條微程序，各指令對(duì)應(yīng)的微程序平均由4條微指令組成，采用斷定法（下址字段法）確定下條微指令的地址，則微指令中下址字段的位數(shù)至少是：

A  5    B  6     C  8    D  9

19. 某同步總線采用數(shù)據(jù)線和地址伐復(fù)用方式。其中之地?cái)?shù)據(jù)伐有紅根，總伐時(shí)鐘頻率為66MHZ，每個(gè)時(shí)鐘同期傳送兩次數(shù)據(jù)。（上升沿和下降沿各傳送一次數(shù)據(jù)）該總線的最大數(shù)據(jù)傳輸率是（總線帶寬）：（）

A. 132MB/S    B. 264     C.528   D. 1056

    20.一次總線事物中，主設(shè)備只需給出一個(gè)首地址，從設(shè)備就能從首地址開始的若干連續(xù)單元格讀出或?qū)懭氲膫€(gè)數(shù)，這種總伐事務(wù)方式稱為（）

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

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

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

    B. I/O接口中CPU可訪問(wèn)寄存器，稱為I/O端口 

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

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

22. 某設(shè)備中斷請(qǐng)求的相應(yīng)和處理時(shí)間為100ns，每400ns發(fā)出一次中斷請(qǐng)求，中斷相應(yīng)所容許的最長(zhǎng)延遲時(shí)間為50ns，則在該設(shè)備持續(xù)工作過(guò)程中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)象的是

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

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

24. 某系統(tǒng)有n臺(tái)互斥使用的同類設(shè)備，3個(gè)并發(fā)進(jìn)程需要3,4,5臺(tái)設(shè)備，可確保系統(tǒng)發(fā)生死鎖的設(shè)備數(shù)n最小為

A.9           B.10            C.11           D.12

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

A.trap指令           B.跳轉(zhuǎn)指令

C.后棧指令           D.關(guān)斷指令

26. 一個(gè)進(jìn)程的讀磁區(qū)操作完成后，操作系統(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)有容量為10GB的磁盤分區(qū)，磁盤空間以簇（cluster）為單位進(jìn)行分配，簇的大小為4KB，若采用位圖法管理該分區(qū)的空閑空間，即用一位（bit）標(biāo)識(shí)一個(gè)簇是否被分配，則存放該位圖所需簇的個(gè)數(shù)為

A.80              B.320             C.80K       D.320K  

28. 下列措施中，能加快虛實(shí)地址轉(zhuǎn)換的是1增大快表（TLB）2讓頁(yè)表常駐內(nèi)存3增大交換區(qū)

A.僅1           B.僅2           C.僅1,2             D.僅2,3

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

A.將文件內(nèi)容讀到內(nèi)存中

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

C.修改文件控制塊中的讀寫權(quán)限

D.將文件的數(shù)據(jù)緩沖區(qū)首指針?lè)祷亟o用戶進(jìn)程       

30．在頁(yè)式存儲(chǔ)管理系統(tǒng)中，采用某些頁(yè)面置換算法，會(huì)出現(xiàn)Belady異?，F(xiàn)象，即進(jìn)程的缺頁(yè)次數(shù)會(huì)隨著分配給該進(jìn)程的頁(yè)框個(gè)數(shù)的增加而增加。下列算法中，可能出現(xiàn)Belady異?，F(xiàn)象的是

Ⅰ.LRU算法                      Ⅱ.FIFO算法               Ⅲ.OPT算法

A．僅Ⅱ

B．僅ⅠⅡ

C．僅ⅠⅢ

D．僅Ⅱ Ⅲ

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è)表優(yōu)點(diǎn)的是

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

C.減少頁(yè)表項(xiàng)所占字節(jié)數(shù)               D.減少頁(yè)表所占的連續(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-e1-d5-00-23-a1向主機(jī)00-e1-d5-00-23-c1發(fā)送1個(gè)數(shù)據(jù)幀，主機(jī)00-e1-d5-00-23-c1收到該幀后，向主機(jī)00-e1-d5-00-23-a1發(fā)送一個(gè)確認(rèn)幀，交換機(jī)對(duì)這兩個(gè)幀的轉(zhuǎn)發(fā)端口分別是

A. 和                    B. 和

C. 和                D. 和

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

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

36.主機(jī)甲與主機(jī)乙之間使用后退N幀協(xié)議（GBN）傳輸數(shù)據(jù)，甲的發(fā)送窗口尺寸為1000，數(shù)據(jù)幀長(zhǎng)為1000字節(jié)，信道寬帶為100Mbps，乙每收到一個(gè)數(shù)據(jù)幀立即利用一個(gè)短幀（忽略其傳輸延遲）進(jìn)行確認(rèn)，若甲乙之間的單向傳播延遲是50ms，則甲可以達(dá)到的最大平均數(shù)據(jù)傳輸速率約為

A．10 Mbps    B.20 Mbps    C.80 Mbps    D.100 Mbps

37.站點(diǎn)A、B、C通過(guò)CDMA共享鏈路，A、B、C的碼片序列（chipping  sequence）分別是（1,1,1,1）、（1，-1,1，-1）和（1，1,-1，-1），若C從鏈路上收到的序列是（2,0,2,0,0，-2,0，-2,0,2,0,2），則C收到A發(fā)送的數(shù)據(jù)是

A．000    B.101    C.110    D.111

38.主機(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)過(guò)10個(gè)RTT后，甲的發(fā)送窗口是

A．10KB   B. 12KB    C. 14KB    D. 15KB

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

Ⅰ 提供無(wú)連接服務(wù)

Ⅱ 提供復(fù)用/分用服務(wù)

Ⅲ 通過(guò)差錯(cuò)校驗(yàn)，保障可靠數(shù)據(jù)傳輸

A．僅Ⅰ   B. 僅Ⅰ、Ⅱ    C. 僅Ⅱ、Ⅲ     D. Ⅰ、Ⅱ、Ⅲ

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

A．PPP   B. ARP    C. UDP     D. SMTP

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

left

weight

right

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)的指針，設(shè)計(jì)求T的WPL的算法。要求：

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

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

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

42. （10分）某網(wǎng)絡(luò)中的路由器運(yùn)行OSPF路由協(xié)議，題42表是路由器R1維護(hù)的主要鏈路狀態(tài)信息（LSI），題42圖是根據(jù)題42表及R1的接口名構(gòu)造出來(lái)的網(wǎng)絡(luò)拓?fù)洹?/span>

題42表R1所維護(hù)的LSI

		R1的LSI	R2的LSI	R3的LSI	R4的LSI	備注
Router ID		10.1.1.1	10.1.1.2	10.1.1.5	10.1.1.6	標(biāo)識(shí)路由器的IP地址
Link1	ID	10.1.1.2	10.1.1.1	10.1.1.6	10.1.1.5	所連路由器的RounterID
	IP	10.1.1.1	10.1.1.2	10.1.1.5	10.1.1.6	Link1的基本IP地址
	Metric	3	3	6	6	Link1的費(fèi)用
Link2	ID	10.1.1.5	10.1.1.6	10.1.1.1	10.1.1.12	所連路由器的RounterID
	IP	10.1.1.9	10.1.1.13	10.1.1.10	10.1.1.14	Link2基本IP地址
	Metic	2	4	2	4	Link2費(fèi)用
Net1	Prefix	192.1.1.0/24	192.1.6.0/24	192.1.7.0/24	192.1.7.0/24	直接網(wǎng)絡(luò)Net1的網(wǎng)絡(luò)前綴
	Metric	1	1	1	1	到達(dá)直連網(wǎng)絡(luò)Net1的費(fèi)用

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

請(qǐng)回答下列問(wèn)題。

（1）

以上是關(guān)于“2014年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合”的相關(guān)資訊，想要更詳細(xì)了解更多考研培訓(xùn)機(jī)構(gòu)的相關(guān)情況，可以咨詢?cè)蹅冊(cè)诰€客服老師！