2016年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(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的“鏈

接地址”依次是o

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

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

2.已知一個(gè)帶有表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L,結(jié)點(diǎn)結(jié)構(gòu)為|prev|data|next其中，prev

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

句序列是o

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->next=p->next;free(p);

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

右，列車可駛?cè)肴我庖粭l軌道?，F(xiàn)有編號(hào)為1?9的9列列車，駛?cè)氲拇涡蛞来问?,4,2,5,3,9,

1,6,7。若期望駛出的次序依次為1?9,則〃至少是o

涼C川即||山叫％

761935248:迨1987654321

呷坤曙11ttmw川叩川1111Hlm螂旭川11中

冬5mIIwii時(shí)叩田笏才

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

4.有一個(gè)100階的三對(duì)角矩陣M,其元素(iWiWIOO,1W/W100)按行優(yōu)先依次壓縮

存入下標(biāo)從0開始的一維數(shù)組N中。元素^30,30在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)先搜索序列的是o

C.丫1,丫—3D.V,5V2,V3,V4,V5

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

A.O(〃)B.0(〃+e)C.O(n2)D.O(ne)

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>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)之一是o

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

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

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

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

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

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

13.有如下C語言程序段

shortsi=-32767;

unsignedshortusi=si;

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

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

14.某計(jì)算機(jī)字長(zhǎng)為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ù)量是o

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

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

OPMID

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

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

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

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

若指令按字邊界對(duì)齊存放，則程序計(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)的指令對(duì)是_O

II：addR1,R2,R3；(R2)+(R3)-*R1

12：addR5,R2,R4；(R2)+(R4)fR5

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

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

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

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

中，錯(cuò)誤的是O

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.僅n、inB.僅nc.僅i、nD.僅I、ni

24.某單CPU系統(tǒng)中有輸入和輸出設(shè)備各1臺(tái)，現(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è)不同的臨界資源R1,R2和R3,被4個(gè)進(jìn)程pi,p2,p3及P4共享。各進(jìn)程對(duì)

資源的需求為：pi申請(qǐng)R］和R2,pz申請(qǐng)R2和R3'P3申請(qǐng)Ri和R3,P4申請(qǐng)R2°若系統(tǒng)出現(xiàn)死

鎖，則處于死鎖狀態(tài)的進(jìn)程數(shù)至少是<

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),(1,0),(0,1)和(1,1),則該算法淘

汰頁的次序?yàn)閛

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)容如下所示。

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

1006000只讀在內(nèi)存

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

3004000讀寫在內(nèi)存

當(dāng)訪問段號(hào)為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,2,40,4,0,3,2,9,2,1,

/時(shí)間

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

A.{6,0,3,2}B.{2,3,0,4}

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

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

〃進(jìn)程Pl〃進(jìn)程p2

intx=0;intx=0；

Threadl()Thread3()

|inta;|inta；

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

i

11

Thread2()Thread4()

|inta;|intb;

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

11

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

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è)共享一臺(tái)獨(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圖回答。

33.在OSI參考模型中，Rl>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ù)傳輸速率約是一o

A.8kbpsB.20kbps

C.40kbpsD.80kbps

R1~R3為路由器；

Switch為lOOBase-T交換機(jī)；

Hub為lOOBase-T集線器；

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

器均配置為。

題33?41圖

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.535R延時(shí)，信號(hào)傳播速度為200向國，不考慮

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

A.200mB.205m

C.359mD.512m

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

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

A.2B.3

C.16D.17

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

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

是C

A.192.168.3,251,B.51,

C.,D.0,

39.若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ā)生的是o

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

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

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

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

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

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)的接收緩存，最大段長(zhǎng)MSS=1KB,平均往返時(shí)間RTT=200ms。H3建立連接時(shí)

的初始序號(hào)為100,且持續(xù)以MSS大小的段向S發(fā)送數(shù)據(jù)，擁塞窗口初始閾值為32KB；S對(duì)

收到的每個(gè)段進(jìn)行確認(rèn)，并通告新的接收窗口。假定TCP連接建立完成后，S端的TCP接收緩

存僅有數(shù)據(jù)存入而無數(shù)據(jù)取出。請(qǐng)回答下列問題。

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

標(biāo)志位的值分別是多少？確認(rèn)序號(hào)是多少？

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

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

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

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

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

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

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

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

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

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

43.已知由〃(〃22)個(gè)正整數(shù)構(gòu)成的集合4=｛而04k＜力｝,將其劃分為兩個(gè)不相交的子

集小和A2,元素個(gè)數(shù)分別是rn和〃2,4和4中元素之和分別為S］和S2o設(shè)計(jì)一個(gè)盡可能高效

的劃分算法，滿足最小且IS-Sd最大。要求：

(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.5ms。請(qǐng)回答下列問題，要求說明理由。

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

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

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

I?_____L,?_____?__________________t

CPU!啟jJ；啟j111

啟請(qǐng)響返請(qǐng)響返請(qǐng)響

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

I/O端口每收到一個(gè)字符申