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

2016年全國碩士研究生入學(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.已知表頭元素為c的單鏈表在內(nèi)存中的存儲(chǔ)狀態(tài)如下表所示。

地址元案鏈接地址

1000Ha1010H

1004Hb100CH

1008Hc1000H

100CHdNULL

1010He1004H

1014H

現(xiàn)將f存放于1014H處并插入到單鏈表中，若f在邏輯上位于a和e之間，則a,e,f的“鏈

接地址”依次是。

A.1010H,1014H,1004HB.1010H,1004H,1014H

C.1014H,I010H,1004HD.1014H,1004H,1010H

2.已知一個(gè)帶有表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L,結(jié)點(diǎn)結(jié)構(gòu)為：P￡e上［datajne,，其中，prev和

next分別是指向其直接前驅(qū)和直接后繼結(jié)點(diǎn)的指針。現(xiàn)要?jiǎng)h除指針p所指的結(jié)點(diǎn)，正確的語句序

列是。

A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);

B.p->next->prev=p->next;p->prev->next=p->next;free(p);

C.p->next->prev=p->next;p->prev->next=p->prev;free(p);

D.p->next->prev=p->prev;p->prev->nexl=p->next;free(p);

3.設(shè)有下圖所示的火車車軌，入口到出口之間有n條軌道，列車的行進(jìn)方向均為從左至右，

列車可駛?cè)肴我庖粭l軌道?，F(xiàn)有編號為1?9的9列列車，駛?cè)氲拇涡蛞来问?,425,3,9,1,6,7。若

期望駛出的次序依次為1?9,則n至少是.

761935248987654321

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

4.有一個(gè)100階的三對角矩陣M,其元素m”(IWiWIOO,iWjWlOO)按行優(yōu)先依次壓縮存

入下標(biāo)從0開始的一維數(shù)組N中。元素m3o,3。在N中的下標(biāo)是。

A.86B.87C.88D.89

5.若森林F有15條邊、25個(gè)結(jié)點(diǎn)，則F包含樹的個(gè)數(shù)是。

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

6.下列選項(xiàng)中，不是下圖深度優(yōu)先搜索序列的是。

A.VbV5,V4,V3,V2B.VhV3,V2,V5,V4

C.VbV2,V5,V4,V3D.VbV2,V3,V4,V5

7.若將n個(gè)頂點(diǎn)e條弧的有向圖采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是。

A.O(n)B.O(n+e)C.O(n2)D.O(n*e)

8.使用迪杰斯特拉(Dijkstra)算法求下圖中從頂點(diǎn)1到其他各頂點(diǎn)的最短路徑，依次得到

的各最短路徑的目標(biāo)頂點(diǎn)是o

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

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

9.在有n(n>1000)個(gè)元素的升序數(shù)組A中查找關(guān)鍵字x。查找算法的偽代碼如下所示。

k=0;

while(k<n且A[k]<x)k=k+3;

if(k<n且A[k]==x)查找成功；

elseif(k-l<n且A[k-1]==x)查找成功；

elseif(k-2<n且A[k-2]==x)查找成功；

else查找失敗；

本算法與折半查找算法相比，有可能具有更少比較次數(shù)的情形是。

A.當(dāng)x不在數(shù)組中B.當(dāng)x接近數(shù)組開頭處

C.當(dāng)x接近數(shù)組結(jié)尾處D.當(dāng)x位于數(shù)組中間位置

10.B+樹不同于B樹的特點(diǎn)之一是

A.能支持順序查找B.結(jié)點(diǎn)中含有關(guān)鍵字

C.根結(jié)點(diǎn)至少有兩個(gè)分支D.所有葉結(jié)點(diǎn)都在同一層上

II.對10TB的數(shù)據(jù)文件進(jìn)行排序，應(yīng)使用的方法是。

A.希爾排序B.堆排序C.快速排序D.歸并排序

12.將高級語言源程序轉(zhuǎn)換為機(jī)器級目標(biāo)代碼文件的程序是

A.匯編程序B.鏈接程序C.編譯程序D.解釋程序

13.有如下C語言程序段

shortsi=-32767;

unsignedshortusi=si;

執(zhí)行上述兩條語句后，usi的值為

A.-32767B.32767C.32768D.32769

14.某計(jì)算機(jī)字長為32位，按字節(jié)編址，采用小端(LittleEndian)方式存放數(shù)據(jù)。假定有

一個(gè)double型變量，其機(jī)器數(shù)表示為1122334455667788H,存放在00008040H開始的連續(xù)存儲(chǔ)

單元中，則存儲(chǔ)單元00008046H中存放的是。

A.22HB.33HC.77HD.66H

15.有如下C語言程序段：

for(k=0;k<1000;k++)

a[k]=a[k]+32;

若數(shù)組a及變量k均為int型，int型數(shù)據(jù)占4B,數(shù)據(jù)Cache采用直接映射方式，數(shù)據(jù)區(qū)大小

為1KB、塊大小為16B,該程序段執(zhí)行前Cache為空，則該程序段執(zhí)行過程中訪問數(shù)組a的Cache

缺失率約為。

A.1.25%B.2.5%C.12.5%D.25%

16.某存儲(chǔ)器容量為64KB,按字節(jié)編址，地址4000H~5FFFH位ROM區(qū)，其余為RAM區(qū)。

若采用8KX4位的SRAM芯片進(jìn)行設(shè)計(jì)，則需要該芯片的數(shù)量是。

A.7B.8C.14D.16

17.某指令格式如下所示。

OPMID

其中M為尋址方式，I為變址寄存器編號，D為形式地址。若采用先變址后間址的尋址方式,

則操作數(shù)的有效地址是?

A.I+DB.(1)+DC.((I)+D)D.((I))+D

18.某計(jì)算機(jī)主存空間為4GB,字長為32位，按字節(jié)編址，采用32位字長指令字格式。若

指令按字邊界對齊存放，則程序計(jì)數(shù)器(PC)和指令寄存器(IR)的位數(shù)至少分別是。

A.30、30B.30、32C.32、30D.32、32

19.在無轉(zhuǎn)發(fā)機(jī)制的五段基本流水線(取指、譯碼/讀寄存器、運(yùn)算、訪寫回寄存器)中，下

列指令序列存在數(shù)據(jù)冒險(xiǎn)的指令對是

II：addRI,R2,R3；(R2)+(R3)-R1

12：addR5,R2,R4；(R2)+(R4)-R5

13：addR4,R5,R3；(R5)+(R3)-R4

14：addR5,R2,R6；(R2)+(R6)-R5

A.II和12B.12和13C.12和14D.13和14

20.單周期處理器中所有指令的指令周期為一個(gè)時(shí)鐘周期。下列關(guān)于單周期處理器的敘述中,

錯(cuò)誤的是。

A.可以采用單總線結(jié)構(gòu)數(shù)據(jù)通路B.處理器時(shí)鐘頻率較低

C.在指令執(zhí)行過程中控制信號不變D.每條指令的CPI為1

21.下列關(guān)于總線設(shè)計(jì)的敘述中，錯(cuò)誤的是。

A.并行總線傳輸比串行總線傳輸速度快

B.采用信號線復(fù)用技術(shù)可減少信號線數(shù)量

C.采用突發(fā)傳輸方式可提高總線數(shù)據(jù)傳輸率

D.采用分離事務(wù)通信方式可提高總線利用率

22.異常是指令執(zhí)行過程中在處理器內(nèi)部發(fā)生的特殊事件，中斷是來自處理器外部的請求事

件。下列關(guān)于中斷或異常情況的敘述中，錯(cuò)誤的是.

A.“訪存時(shí)缺頁”屬于中斷B.“整數(shù)除以0”屬于異常

C.“DMA傳送結(jié)束”屬于中斷D.“存儲(chǔ)保護(hù)錯(cuò)”屬于異常

23.下列關(guān)于批處理系統(tǒng)的敘述中，正確的是。

I.批處理系統(tǒng)允許多個(gè)用戶與計(jì)算機(jī)直接交互

II.批處理系統(tǒng)分為單道批處理系統(tǒng)和多道批處理系統(tǒng)

III.中斷技術(shù)使得多道批處理系統(tǒng)和I/O設(shè)備可與CPU并行工作

A.僅H、inB.僅nC.僅I、IID.僅I、III

24.某單CPU系統(tǒng)中有輸入和輸出設(shè)備各1臺，現(xiàn)有3個(gè)并發(fā)執(zhí)行的作業(yè)，每個(gè)作業(yè)的輸

入、計(jì)算和輸出時(shí)間均分別為2ms、3ms和4ms,且都按輸入、計(jì)算和輸出的順序執(zhí)行，則執(zhí)行

完3個(gè)作業(yè)需要的時(shí)間最少是o

A.15msB.17msC.22msD.27ms

25.系統(tǒng)中有3個(gè)不同的臨界資源RI、R2和R3,被4個(gè)進(jìn)程pl、p2、p3及p4共享。各進(jìn)

程對資源的需求為：pl申請R1和R2,p2申請R2和R3,p3申請R1和R3,p4申請R2。若系

統(tǒng)出現(xiàn)死鎖，則處于死鎖狀態(tài)的進(jìn)程數(shù)至少是O

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

26.某系統(tǒng)采用改進(jìn)型CLOCK置換算法，頁表項(xiàng)中字段A為訪問位，M為修改位。A=0

表示頁最近沒有被訪問，A=1表示頁最近被訪問過。M=0表示頁沒有被修改過，M=1表示頁被修

改過。按(A,M)所有可能的取值，將頁分為四類：(0,0)、(I,0)、(0,1)和(1,1),則

該算法淘汰頁的次序?yàn)?/p>

A.(0,0),(0,1),(1,0),(1,1)

B.(0,0),(1,0),(0,1),(1,1)

C.(0,0),(0,1),(1,1),(1,0)

D.(0,0),(1,1)，(0,1),(1,0)

27,使用TSL(TestandSetLock)指令實(shí)現(xiàn)進(jìn)程互斥的偽代碼如下所示。

do{

while(TSL(&lock));

criticalsection;

lock=FALSE;

}while(TRUE);

下列與該實(shí)現(xiàn)機(jī)制相關(guān)的敘述中，正確的是。

A.退出臨界區(qū)的進(jìn)程負(fù)責(zé)喚醒阻塞態(tài)進(jìn)程

B.等待進(jìn)入臨界區(qū)的進(jìn)程不會(huì)主動(dòng)放棄CPU

C.上述偽代碼滿足“讓權(quán)等待”的同步準(zhǔn)則

D.while(TSL(&lock))語句應(yīng)在關(guān)中斷狀態(tài)下執(zhí)行

28.某進(jìn)程的段表內(nèi)容如下所示。

段長內(nèi)存起始地址權(quán)限狀態(tài)

1006000只讀在內(nèi)存

200—讀寫不在內(nèi)存

3004000讀寫在內(nèi)存

當(dāng)訪問段號為2、段內(nèi)地址為400的邏輯地址時(shí)，進(jìn)行地址轉(zhuǎn)換的結(jié)果是

A.段缺失異常B.得到內(nèi)存地址4400

C.越權(quán)異常D.越界異常

29.某進(jìn)程訪問頁面的序列如下所示。

…,1,3,4.5,6,0,3,2,3,0,4,0,3,2,9,2,1,….

t時(shí)間

若工作集的窗口大小為6,則在t時(shí)刻的工作集為。

A.[6,0,3,2}B.{2,3,0,41

C.{0,4,3,2,9}D.{4,5,6,0,3,2)

30.進(jìn)程P1和P2均包含并發(fā)執(zhí)行的線程，部分偽代碼描述如下所示。

〃進(jìn)程P1〃進(jìn)程P2

intx=0；intx=0；

Thread1()Thread3()

|inta；|inta；

a=1；x+=1；a=x；x+=3；

11

Thread!()Thread4()

|inta；|intb；

a=2；x+=2；b=x；x+=4；

11

下列選項(xiàng)中，需要互斥執(zhí)行的操作是。

A.a=l與a=2B.a=x與b=x

C.x+=l與x+=2D.x+=l與x+=3

31.下列關(guān)于SPOOLing技術(shù)的敘述中，錯(cuò)誤的是。

A.需要外存的支持

B.需要多道程序設(shè)計(jì)技術(shù)的支持

C.可以讓多個(gè)作業(yè)共享一臺獨(dú)占設(shè)備

D.由用戶作業(yè)控制設(shè)備與輸入/輸出井之間的數(shù)據(jù)傳送

32.下列關(guān)于管程的敘述中，錯(cuò)誤的是。

A.管程只能用于實(shí)現(xiàn)進(jìn)程的互斥

B.管程是由編程語言支持的進(jìn)程同步機(jī)制

C.任何時(shí)候只能有一個(gè)進(jìn)程在管程中執(zhí)行

D.管程中定義的變量只能被管程內(nèi)的過程訪問

題33?41均依據(jù)題33?41圖回答。

圖中：

R1?R3為路由器：

Switch為100Base?T交換機(jī)；

Hub為100Base-T集線器：

主機(jī)H1~H4的默認(rèn)域名服務(wù)

器均配置為201』.1.1。

S33-41圖

33.在OS1參考模型中，RI、Switch.Hub實(shí)現(xiàn)的最高功能層分別是。

A.2、2、1B.2、2、2

C.3、2、1D,3、2、2

34.若連接R2和R3鏈路的頻率帶寬為8kHz,信噪比為30dB,該鏈路實(shí)際數(shù)據(jù)傳輸速率約

為理論最大數(shù)據(jù)傳輸速率的50%,則該鏈路的實(shí)際數(shù)據(jù)傳輸速率約是0

A.8kbpsB.20kbps

C.40kbpsD.80kbps

35.若主機(jī)H2向主機(jī)H4發(fā)送1個(gè)數(shù)據(jù)幀，主機(jī)H4向主機(jī)H2立即發(fā)送一個(gè)確認(rèn)幀，則除

H4外，從物理層上能夠收到該確認(rèn)幀的主機(jī)還有。

A.僅H2B,僅H3

C.僅Hl、H2D.僅H2、H3

36.若Hub再生比特流過程中，會(huì)產(chǎn)生1.535US延時(shí)，信號傳播速度為200m/us,不考慮以

太網(wǎng)幀的前導(dǎo)碼，則H3與H4之間理論上可以相距的最遠(yuǎn)距離是。

A.200mB.205m

C.359mD.512m

37.假設(shè)RI、R2、R3采用RIP協(xié)議交換路由信息，且均已收斂。若R3檢測到網(wǎng)絡(luò)201.120/25

不可達(dá)，并向R2通告一次新的距離向量，則R2更新后，其到達(dá)該網(wǎng)絡(luò)的距離是。

A.2B.3

C.16D.17

38.假設(shè)連接RI、R2和R3之間的點(diǎn)對點(diǎn)鏈路使用201.1.3.X/30地址，當(dāng)H3訪問Web服務(wù)

器S時(shí)，R2轉(zhuǎn)發(fā)出去的封裝HTTP請求報(bào)文的IP分組的源IP地址和目的IP地址分別是。

A.51,B.51,

C.,D.0,

39.假設(shè)H1與H2的默認(rèn)網(wǎng)關(guān)和子網(wǎng)掩碼均分別配置為和28,H3

和H4的默認(rèn)網(wǎng)關(guān)和子網(wǎng)掩碼均分別配置為54和28,則下列現(xiàn)象中可能

發(fā)生的是.

A.H1不能與H2進(jìn)行正常IP通信B.H2與H4均不能訪問Internet

C.Hl不能與H3進(jìn)行正常IP通信D.H3不能與H4進(jìn)行正常1P通信

40.假設(shè)所有域名服務(wù)器均采用迭代查詢方式進(jìn)行域名解析。當(dāng)H4訪問規(guī)范域名為

的網(wǎng)站時(shí)，域名服務(wù)器在完成該域名解析過程中，可能發(fā)出DNS查詢

的最少和最多次數(shù)分別是。

A.0,3B.1,3C.0,4D.1,4

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

41.假設(shè)題33~41圖中的H3訪問Web服務(wù)器S時(shí),S為新建的TCP連接分配了20KB(K=1024)

的接收緩存，最大段長MSS=1KB,平均往返時(shí)間RTT=200ms.,H3建立連接時(shí)的初始序號為100,

且持續(xù)以MSS大小的段向S發(fā)送數(shù)據(jù)，擁塞窗口初始閾值為32KB；S對收到的每個(gè)段進(jìn)行確認(rèn)，

并通告新的接收窗口。假定TCP連接建立完成后，S端的TCP接收緩存僅有數(shù)據(jù)存入而無數(shù)據(jù)

取出。請回答下列問題。

(1)在TCP連接建立過程中，H3收到的S發(fā)送過來的第二次握手TCP段的SYN和ACK標(biāo)

志位的值分別是多少？確認(rèn)序號是多少？

(2)H3收到的第8個(gè)確認(rèn)段所通告的接收窗口是多少？此時(shí)H3的擁塞窗口變?yōu)槎嗌?？H3

的發(fā)送窗口變?yōu)槎嗌伲?/p>

(3)當(dāng)H3的發(fā)送窗口等于0時(shí)，下一個(gè)待發(fā)送的數(shù)據(jù)段序號是多少？H3從發(fā)送第1個(gè)數(shù)據(jù)

段到發(fā)送窗口等于0時(shí)刻為止，平均數(shù)據(jù)傳輸速率是多少(忽略段的傳輸延時(shí))？

(4)若H3與S之間通信己經(jīng)結(jié)束，在t時(shí)刻H3請求斷開該連接，則從t時(shí)刻起，S釋放該

連接的最短時(shí)間是多少？

42.如果一棵非空k(k>2)叉樹T中每個(gè)非葉結(jié)點(diǎn)都有k個(gè)孩子，則稱T為正則k叉樹。

請回答下列問題并給出推導(dǎo)過程。

(1)若T有m個(gè)非葉結(jié)點(diǎn)，則T中的葉結(jié)點(diǎn)有多少個(gè)？

(2)若T的高度為h(單結(jié)點(diǎn)的樹h=l),則T的結(jié)點(diǎn)數(shù)最多為多少個(gè)？最少為多少個(gè)？

43.已知由n(n02)個(gè)正整數(shù)構(gòu)成的集合A={ak|0Wk<n},將其劃分為兩個(gè)不相交的子集

A,和A2,元素個(gè)數(shù)分別是小和Q,A,和A2中元素之和分別為S,和S2,設(shè)計(jì)一個(gè)盡可能高效的

劃分算法，滿足|川-間最小且|S「S?|最大。要求：

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

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

(3)說明你所設(shè)計(jì)算法的平均時(shí)間復(fù)雜度和空間復(fù)雜度。

44.假定CPU主頻為50MHz,CPI為4。設(shè)備D采用異步串行通信方式向主機(jī)傳送7位ASCII

字符，通信規(guī)程中有1位奇校驗(yàn)位和1位停止位，從D接收啟動(dòng)命令到字符送入I/O端口需要

0.5mso請回答下列問題，要求說明理由。

(1)每傳送一個(gè)字符，在異步串行通信線上共需傳輸多少位？在設(shè)備D持續(xù)工作過程中，每

秒鐘最多可向I/O端口送入多少個(gè)字符？

(2)設(shè)備D采用中斷方式進(jìn)行輸入/輸出，示意圖如下：

工作年工作完工作完

外設(shè)D<1成1-—1成1—1成

111111

11Q111

11拿啟；1▲啟；葉:

CPU11111

▼1▼1動(dòng)T______工

切春動(dòng)返

啟請響請響請響

動(dòng)求應(yīng)求應(yīng)回求應(yīng)

I/O端口每收到一個(gè)字符申請一次中斷，中斷響應(yīng)需10個(gè)時(shí)鐘周期，中斷服務(wù)程序共有20

條指令，其中第15條指令啟動(dòng)D工作。若CPU需從D讀取1000個(gè)字符，則完成這一任務(wù)所需

時(shí)間大約是多少個(gè)時(shí)鐘周期？CPU用于完成這一任務(wù)的時(shí)間大約是多少個(gè)時(shí)鐘周期？在中斷響

應(yīng)階段CPU進(jìn)行了哪些操作？

45.某計(jì)算機(jī)采用頁式虛擬存儲(chǔ)管理方式，按字節(jié)編址，虛擬地址為32位，物理地址為24

位，頁大小為8KB；TLB采用全相聯(lián)映射；Cache數(shù)據(jù)區(qū)大小為64KB,按2路組相聯(lián)方式組織，

主存塊大小為64B。存儲(chǔ)訪問過程的示意圖如下。

請回答下列問題。

(1)圖中字段A-G的位數(shù)各是多少？TLB標(biāo)記字段B中存放的是什么信息？

(2)將塊號為4099的主存塊裝入到Cache中時(shí)，，所映射的Cache組號是多少？對應(yīng)的H字

段內(nèi)容是什么？

(3)Cache缺失處理的時(shí)間開銷大還是缺頁處理的時(shí)間開銷大？為什么？

(4)為什么Cache可以采用直寫(WriteThrough)策略，而修改頁面內(nèi)容時(shí)總是采用回寫(Write

Back)策略。

46.某進(jìn)程調(diào)度程序采用基于優(yōu)先數(shù)(priority)的調(diào)度策略，即選擇優(yōu)先數(shù)最小的進(jìn)程運(yùn)行，

進(jìn)程創(chuàng)建時(shí)由用戶指定一個(gè)nice作為靜態(tài)優(yōu)先數(shù)。為了動(dòng)態(tài)調(diào)整優(yōu)先數(shù)，引入運(yùn)行時(shí)間cpuTime

和等待時(shí)間waitTime,初值均為0。進(jìn)程處于執(zhí)行態(tài)時(shí)，cpuTime定時(shí)加1,且waitTime置0；進(jìn)

程處于就緒態(tài)時(shí)，cpuTime置0,waitTime定時(shí)加1。請回答下列問題。

(1)若調(diào)度程序只將nice的值作為進(jìn)程的優(yōu)先數(shù)，即priority=nice,則可能會(huì)出現(xiàn)饑餓現(xiàn)

象，為什么？

(2)使用nice、cpuTime和waitTime設(shè)計(jì)一種動(dòng)態(tài)優(yōu)先數(shù)計(jì)算方法，以避免產(chǎn)生饑餓現(xiàn)象，

并說明waitTime的作用。

47.某磁盤文件系統(tǒng)使用鏈接分配方式組織文件，簇大小為4KB。目錄文件的每個(gè)目錄項(xiàng)包

括文件名和文件的第一個(gè)簇號，其他簇號存放在文件分配表FAT中。

(1)假定目錄樹如下圖所示，各文件占用的簇號及順序如下表所示，其中dir、dirl是目錄，

filel、file2是用戶文件。請給出所有目錄文件的內(nèi)容。

（2）若FAT的每個(gè)表項(xiàng)僅存放簇號，占2個(gè)字節(jié)，則FAT的最大長度為多少字節(jié)？該文件

系統(tǒng)支持的文件長度最大是多少？

（3）系統(tǒng)通過目錄文件和FAT實(shí)現(xiàn)對文件的按名存取，說明filel的106、108兩個(gè)簇號分別

存放在FAT的哪個(gè)表項(xiàng)中。

（4）假設(shè)僅FAT和dir目錄文件已讀入內(nèi)存，若需將文件dir/dirl/filel的第5000個(gè)字節(jié)讀入

內(nèi)存，則要訪問哪幾個(gè)簇？

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

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

1.D2.D3.C4.B5.C6.D7.B8.B

9.B10.A11.D12.C13.D14.A15.C16.C

17.C18.B19.B20.A21.A22.A23.A24.B

25.C26.A27.B28.D29.A30.C31.D32.A

33.C34.C35.D36.B37.B38.D39.C40.C

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

41.解答：

（1）TCP連接的建立分以下三個(gè)階段。首先，H3向Web服務(wù)器S發(fā)出連接請求報(bào)文段，這

時(shí)首部中的同步位SYN=1,ACK=0,同時(shí)選擇一個(gè)初始序號seq=100。TCP規(guī)定，SYN報(bào)文段

（即SYN=1的報(bào)文段）不能攜帶數(shù)據(jù)，但是要消耗一個(gè)序號。接著，S收到連接請求報(bào)文段，為

自己選擇一個(gè)初始序號seq=y,向A發(fā)送確認(rèn)。這個(gè)報(bào)文段SYN=1,ACK=1,seq=y,確認(rèn)號ack

是100+1=101。它不能攜帶數(shù)據(jù)，但是也要消耗一個(gè)序號。最后，H3收到S的確認(rèn)報(bào)文段后，還

要向S給出確認(rèn)。這份確認(rèn)報(bào)文段SYN=0,ACK=1,確認(rèn)號ack=y+l,自己的序號seq=101。因

此，第二次握手TCP段的SYN=1,（1分）ACK=1；（1分）確認(rèn)序號是101。（1分）

（2）題目規(guī)定S對收到的每個(gè)段（MSS大小的段）進(jìn)行確認(rèn)，并通告新的接收窗口，而且

TCP接收緩存僅有數(shù)據(jù)存入而無數(shù)據(jù)取出。H3收到的第8個(gè)確認(rèn)段所通告的接收窗口是

20-8=12KB；（1分）在慢開始算法里，發(fā)送方H3先設(shè)置擁塞窗口cwnd=lKB,接下來每收到一

個(gè)對新報(bào)文段的確認(rèn)就使發(fā)送方的擁塞窗口加IKBoH3共收到8個(gè)確認(rèn)段，所以此時(shí)H3的擁塞

窗口變?yōu)镮+8=9KB；（1分）發(fā)送窗口=min{擁塞窗口，接收窗口}，所以H3的發(fā)送窗口變?yōu)閙in{9,

12}=9KBo（1分）

（3）TCP是用字節(jié)作為窗口和序號的單位。當(dāng)H3的發(fā)送窗口等于0KB時(shí)，也就是接收窗口

等于0KB時(shí)，下一個(gè)待發(fā)送段的序號是20K+101=20X1024+101=20581；（1分）H3從發(fā)送第1

個(gè)段到發(fā)送窗口等于0KB時(shí)刻為止，經(jīng)過五個(gè)傳輸輪次，每個(gè)傳輸輪次的時(shí)間就是往返RTT,

因此平均數(shù)據(jù)傳輸速率是20KB/（5X200ms）=20KB/s=20.48kbps。（1分）

（4）通信結(jié)束后，H3向S發(fā)送連接釋放報(bào)文段。S收到H3的連接釋放報(bào)文段后，馬上發(fā)出

確認(rèn)報(bào)文段。此時(shí)S已經(jīng)沒有數(shù)據(jù)需要傳輸，于是它也馬上發(fā)出連接釋放報(bào)文段。H3在收到S

的連接釋放報(bào)文段后，發(fā)出確認(rèn)報(bào)文段。S在收到這份確認(rèn)后就釋放TCP連接。因此從t時(shí)刻起，

S釋放該連接的最短時(shí)間是：H3的連接釋放報(bào)文段傳送到S的時(shí)間+S的連接釋放報(bào)文段傳送到

H3的時(shí)間+H3的確認(rèn)報(bào)文段傳送到S的時(shí)間二L5X200ms=300ms。（1分）

42.解答：

（1）根據(jù)定義，正則k叉樹中僅含有兩類結(jié)點(diǎn)；葉結(jié)點(diǎn)（個(gè)數(shù)記為即）和度為k的分支結(jié)點(diǎn)

(個(gè)數(shù)記為n,)?樹T中的結(jié)點(diǎn)總數(shù)n=n0+nk=no+mo樹中所含的邊數(shù)e=n-1,這些邊均為m個(gè)度

為k的結(jié)點(diǎn)發(fā)出的，即e=mXk。整理得：n0+m=mXk+1,故n()=(k-l)Xm+1?(3分)

(2)高度為h的正則k叉樹T中，含最多結(jié)點(diǎn)的樹形為：除第h層外，第1到第h-1層的結(jié)

點(diǎn)都是度為k的分支結(jié)點(diǎn)；而第h層均為葉結(jié)點(diǎn)，即樹是“滿”樹。此時(shí)第j(IWjWh)層結(jié)點(diǎn)

數(shù)為kJ!結(jié)點(diǎn)總數(shù)M1為：

7丁(3分)

含最少結(jié)點(diǎn)的正則k叉樹的樹形為：第1層只有根結(jié)點(diǎn)，第2到第h-1層僅含1個(gè)分支

結(jié)點(diǎn)和k-1個(gè)葉結(jié)點(diǎn)，第h層有k個(gè)葉結(jié)點(diǎn)。即除根外第2到第h層中每層的結(jié)點(diǎn)數(shù)均為k,

故T中所含結(jié)點(diǎn)總數(shù)M2為：

M2=1+(/?-1)XJI(2分)

【評分說明】

①參考答案僅給出一種推導(dǎo)過程，若考生采用其他推導(dǎo)方法且正確，同樣給分。②若考生僅

給出結(jié)果，但沒有推導(dǎo)過程，則(1)、(2)的最高得分分別是2分和3分。若推導(dǎo)過程或答案不

完全正確，酌情給分。

43.解答：

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

由題意知，將最小的Ln/2)」個(gè)元素放在AI中，其余的元素放在A2中，分組結(jié)果即可滿足題目

要求。仿照快速排序的思想，基于樞軸將n個(gè)整數(shù)劃分為兩個(gè)子集。根據(jù)劃分后樞軸所處的位置

i分別處理：

①若i=Ln/2)」，則分組完成，算法結(jié)束；

②若i<Ln/2)」，則樞軸及之前的所有元素均屬于A”繼續(xù)對i之后的元素進(jìn)行劃分；

③若i>Ln/2)」，則樞軸及之后的所有元素均屬于A2,繼續(xù)對i之前的元素進(jìn)行劃分；

基于該設(shè)計(jì)思想實(shí)現(xiàn)的算法，毋須對全部元素進(jìn)行全排序，其平均時(shí)間復(fù)雜度是0(n),空間

復(fù)雜度是0(1)。

(2)算法實(shí)現(xiàn)(9分)

intsetPartition(inta[]zintn){

intpivotkey,low=0,low0=0,high=n-lzhighO=n-lzflag=lzk=n/2,i;

intsl=0,s2=0;

while(flag){

piovtkey=a[low];〃選擇樞軸

while(low<high){〃基于樞軸對數(shù)據(jù)進(jìn)行劃分

while(low<high&&a[high]>=pivotkey)-high;

if(low!=high)a[low]=a[high];

while(low<high&&a[low]<=pivotkey)++low;

if(low!=high)a[high]=a[low];

}//endofwhile(low<high)

a[low]=pivotkey;

if(low==k-l)〃如果樞軸是第n/2小元素，劃分成功

flag=O;

else{//是否繼續(xù)劃分

if(low<k-l){

lowO=++low;

high=highO;

）

else{

highO=-high;

low=lowO;

}

}

}

for（i=0;i<k;i++）sl+=a[i];

for（i=k;i<n;i++）s2+=a[i];

returns2-sl;

）

r（i）（2）的評分說明】

①本題目只需將最大的一半元素與最小的一半元素分組，不需要對所有元素進(jìn)行全部排序。

參考答案基于快速排序思想，采用非遞歸的方式實(shí)現(xiàn)。若考生設(shè)計(jì)的算法滿足題目的功能要求且

正確，則（1）、（2）根據(jù)所實(shí)現(xiàn)算法的平均時(shí)間復(fù)雜度給分，細(xì)則見下表。

時(shí)間復(fù)雜度分?jǐn)?shù)說明

0(n)13采用類似快速排序思想，沒有對元素進(jìn)行全排序。

O(nlog2n)11

O(n2)9

其他7時(shí)間復(fù)雜度高于0（，）的算法。

②若在算法的基本設(shè)計(jì)思想描述中因文字表達(dá)沒有清晰反映出算法思路，但在算法實(shí)現(xiàn)中能

夠表達(dá)出算法思想且正確的，可參照①的標(biāo)準(zhǔn)給分。

③若算法的基本設(shè)計(jì)思想描述或算法實(shí)現(xiàn)中部分正確，可參照①中各種情況的相應(yīng)給分標(biāo)準(zhǔn)

酌情給分。

④參考答案中只給出了使用C語言的版本，使用C++語言的答案視同使用C語言。

（3）算法的平均時(shí)間復(fù)雜度和空間復(fù)雜度

本參考答案給出的算法平均時(shí)間復(fù)雜度是0（n）,空間復(fù)雜度是0（1）。

【評分說明】

44.解答:

（1）每傳送一個(gè)ASCII字符，需要傳輸?shù)奈粩?shù)有1位起始位、7位數(shù)據(jù)位（ASCII字符占7

位）、1位奇校驗(yàn)位和1位停止位，故總位數(shù)為1+7+1+1=10。（2分）

I/O端口每秒鐘最多可接收1000/0.5=2000個(gè)字符。（1分）

【評分說明】對于第一問，若考生回答總位數(shù)為9,則給1分。

（2）一個(gè)字符傳送時(shí)間包括：設(shè)備D將字符送I/O端口的時(shí)間、中斷響應(yīng)時(shí)間和中斷服務(wù)程

序前15條指令的執(zhí)行時(shí)間。時(shí)鐘周期為l/（50MHz）=20ns,設(shè)備D將字符送1/0端口的時(shí)間為

0.5ms/20ns=2.5XIO4個(gè)時(shí)鐘周期。一個(gè)字符的傳送時(shí)間大約為2.5X1（）4+10+15X4=25070個(gè)時(shí)鐘

周期。完成1000個(gè)字符傳送所需時(shí)間大約為1000X25070=25070000個(gè)時(shí)鐘周期。（3分）

CPU用于該任務(wù)的時(shí)間大約為1000X（10+20X4）=9X10」個(gè)時(shí)鐘周期。（1分）

在中斷響應(yīng)階段，CPU主要進(jìn)行以下操作：關(guān)中斷、保護(hù)斷點(diǎn)和程序狀態(tài)、識別中斷源。

（2分）

【評分說明】

①位于第一問，若答案是25070020,則同樣