2016年全國碩士研究生入學統(tǒng)一考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題

2016年全國碩士研究生入學統(tǒng)一考試

計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題

一、單項選擇題(第1?40小題，每小題2分，共80分。下列每題給出的四個選項中,

只有一個選項最符合試題要求)

1.已知表頭元素為c的單鏈表在內存中的存儲狀態(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.已知一個帶有表頭結點的雙向循環(huán)鏈表L,結點結構為|prev|data|next其中，prev

和next分別是指向其直接前驅和直接后繼結點的指針?，F(xiàn)要刪除藉稈p所指的結點，正確的語

句序列是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.設有下圖所示的火車車軌，入口到出口之間有M條軌道，列車的行進方向均為從左至

右，列車可駛入任意一條軌道。現(xiàn)有編號為1?9的9列列車，駛入的次序依次是8,4,2,5,3,9,

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

涼C川即||山叫％

761935248:迨1987654321

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

冬5mIIwii時叩田笏才

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

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

存入下標從0開始的一維數(shù)組N中。元素^30,30在N中的下標是______.

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

5.若森林F有15條邊、25個結點，則F包含樹的個數(shù)是

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

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

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

7.若將〃個頂點e條弧的有向圖采用鄰接表存儲，則拓撲排序算法的時間復雜度是,

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

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

到的各最短路徑的目標頂點是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)個元素的升序數(shù)組A中查找關鍵字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查找失?。?/p>

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

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

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

10.B+樹不同于B樹的特點之一是o

A.能支持順序查找B.結點中含有關鍵字

C.根結點至少有兩個分支D.所有葉結點都在同一層上

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

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

12.將高級語言源程序轉換為機器級目標代碼文件的程序是o

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

13.有如下C語言程序段

shortsi=-32767;

unsignedshortusi=si;

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

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

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

有一個double型變量，其機器數(shù)表示為1122334455667788H,存放在00008040H開始的連續(xù)

存儲單元中，則存儲單元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.某存儲器容量為64KB,按字節(jié)編址，地址4000H?5FFFH位ROM區(qū)，其余為RAM

區(qū)。若采用8Kx4位的SRAM芯片進行設計，則需要該芯片的數(shù)量是o

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

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

OPMID

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

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

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

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

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

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

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

下列指令序列存在數(shù)據(jù)冒險的指令對是_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.單周期處理器中所有指令的指令周期為一個時鐘周期。下列關于單周期處理器的敘述

中，錯誤的是O

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

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

21.下列關于總線設計的敘述中，錯誤的是□

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

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

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

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

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

事件。下列關于中斷或異常情況的敘述中，錯誤的是?

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

C.“DMA傳送結束”屬于中斷D.“存儲保護錯”屬于異常

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

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

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

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

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

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

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

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

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

25.系統(tǒng)中有3個不同的臨界資源R1,R2和R3,被4個進程pi,p2,p3及P4共享。各進程對

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

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

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

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

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

頁被修改過。按(A,M)所有可能的取值，將頁分為四類：(0,0),(1,0),(0,1)和(1,1),則該算法淘

汰頁的次序為o

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)指令實現(xiàn)進程互斥的偽代碼如下所示。

do{

while(TSL(&lock))；

criticalsection;

lock=FALSE;

}while(TRUE);

下列與該實現(xiàn)機制相關的敘述中，正確的是.

A.退出臨界區(qū)的進程負責喚醒阻塞態(tài)進程

B.等待進入臨界區(qū)的進程不會主動放棄CPU

C.上述偽代碼滿足“讓權等待”的同步準則

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

28.某進程的段表內容如下所示。

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

1006000只讀在內存

200讀寫不在內存

3004000讀寫在內存

當訪問段號為2、段內地址為400的邏輯地址時，進行地址轉換的結果是

A.段缺失異常B.得到內存地址4400

C.越權異常D.越界異常

29.某進程訪問頁面的序列如下所示。

…,1,3,4,5,6,0,3,2,3,2,40,4,0,3,2,9,2,1,

/時間

若工作集的窗口大小為6,則在r時刻的工作集為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.進程R和P2均包含并發(fā)執(zhí)行的線程，部分偽代碼描述如下所示。

〃進程Pl〃進程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

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

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

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

31.下列關于SPOOLing技術的敘述中，錯誤的是。

A.需要外存的支持

B.需要多道程序設計技術的支持

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

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

32.下列關于管程的敘述中，錯誤的是。

A.管程只能用于實現(xiàn)進程的互斥，

B.管程是由編程語言支持的進程同步機制

C.任何時候只能有一個進程在管程中執(zhí)行

D.管程中定義的變量只能被管程內的過程訪問

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

33.在OSI參考模型中，Rl>Switch,Hub實現(xiàn)的最高功能層分別是

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

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

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

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

A.8kbpsB.20kbps

C.40kbpsD.80kbps

R1~R3為路由器；

Switch為lOOBase-T交換機；

Hub為lOOBase-T集線器；

主機H1~H4的默認域名服務

器均配置為。

題33?41圖

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

除H4夕卜，從物理層上能夠收到該確認幀的主機還有。

A.僅H2B.僅H3

C.僅Hl、H2D.僅H2、H3

36.若Hub再生比特流過程中，會產生1.535R延時，信號傳播速度為200向國，不考慮

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

A.200mB.205m

C.359mD.512m

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

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

A.2B.3

C.16D.17

38.假設連接RI、R2和R3之間的點對點鏈路使用201.1.3.X/30地址，當H3訪問Web服

務器S時，R2轉發(fā)出去的封裝HTTP請求報文的IP分組的源IP地址和目的IP地址分別

是C

A.192.168.3,251,B.51,

C.,D.0,

39.若H1與H2的默認網(wǎng)關和子網(wǎng)掩碼均分別配置為和28,H3

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

能發(fā)生的是o

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

C.Hl不能與H3進行正常IP通信D.H3不能與H4進行正常IP通信

40.假設所有域名服務器均采用迭代查詢方式進行域名解析。當H4訪問規(guī)范域名為

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

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

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

二、綜合應用題(第41?47小題，共70分)

41.假設題33-41圖中的H3訪問Web服務器S時，S為新建的TCP連接分配了20KB

(K=1024)的接收緩存，最大段長MSS=1KB,平均往返時間RTT=200ms。H3建立連接時

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

收到的每個段進行確認，并通告新的接收窗口。假定TCP連接建立完成后，S端的TCP接收緩

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

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

標志位的值分別是多少？確認序號是多少？

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

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

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

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

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

該連接的最短時間是多少？

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

請回答下列問題并給出推導過程。

(1)若T有加個非葉結點，則T中的葉結點有多少個？

(2)若T的高度為〃(單結點的樹〃=1),則T的結點數(shù)最多為多少個？最少為多少個？

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

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

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

(1)給出算法的基本設計思想。

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

(3)說明你所設計算法的平均時間復雜度和空間復雜度。

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

ASCII字符，通信規(guī)程中有1位奇校驗位和1位停止位，從D接收啟動命令到字符送入I/O端

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

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

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

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

I?_____L,?_____?__________________t

CPU!啟jJ；啟j111

啟請響返請響返請響

動求應回泉應回源應

I/O端口每收到一個字符申