2017年全國(guó)碩士研究生招生考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題

2017年全國(guó)碩士研究生招生考試

計(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.下列函數(shù)的時(shí)間復(fù)雜度是

intfunc(intii)

|inii=0,sum=0；

while(sum<n)sum+=++i；

returni；

1

j

A.O(logn)B.0(腦/2)c.O(n)D.O(nlogn)

2.下列關(guān)于棧的敘述中，歲年的是

I采用小遞歸方式或后盤歸程序時(shí)必須使用棧

n.函數(shù)調(diào)用時(shí)，系統(tǒng)要用棧保存必要的信息

in.只要確定了人棧次序，即可確定出棧次序

w.棧是一種受限的線性表，允許在其兩端進(jìn)行操作

A.僅IB.僅I、口、1D

c.僅i、m、ivD.僅n、in、］v

3,適用于壓縮存儲(chǔ)稀疏矩陣的兩種存儲(chǔ)結(jié)構(gòu)是

A.三元組表和十字鏈表B.三元組裊和鄰接矩陣

C.十字鏈表和二叉鏈表D.鄰接矩陣和十字鏈表

4.要使-棵非空二叉樹的先序序列與中jrjr列相同，其所有非葉結(jié)點(diǎn)

須滿足的條件是

A.只有左子樹B.只行右子樹

C.結(jié)點(diǎn)的度均為1D.結(jié)點(diǎn)的度均為2

5.已知一棵二叉樹的樹形如下圖所示，其后序序列為e,a,c,b,d,g,f,

樹中與結(jié)點(diǎn)a同層的結(jié)點(diǎn)是

6.已知字符集|a,b,c,d,e,f,g,h|,若各字符的哈夫曼編碼依次是

0100,10,0000,0101,001,011,11,0001,則編碼序列

0100011001001011110101的譯碼結(jié)果是

A.acgabfhB.adbagbb

C.afbeagdD.afeefgd

7.已知無(wú)向圖G含有16條邊，其中度為4的頂點(diǎn)個(gè)數(shù)為3,度為3的

頂點(diǎn)個(gè)數(shù)為4,其他頂點(diǎn)的度均小于3。圖G所含的頂點(diǎn)個(gè)數(shù)至

少是

A.10B.11C.13D.15

8.下列二叉樹中，可能成為折半杳找判定樹（不含外部結(jié)點(diǎn)）的是

9.下列應(yīng)用中，適合使用B,樹的是

A.編譯器中的詞法分析B.關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中的索引

c.網(wǎng)絡(luò)中的路由表快速杳找D.操作系統(tǒng)的磁盤空閑塊管理

10.在內(nèi)部排序時(shí)，若選擇了歸并排I乎而沒有選擇插入排序,則可能的

理由是

I.歸并排序的程序代碼更短

口.歸并排序的占用空間更少

m.歸并排序的運(yùn)行效率更高

A.僅口B.僅mc.僅I、nD.僅I、田

11.T列排序方法中,若將順JY存儲(chǔ)更換為鏈?zhǔn)酱鎯?chǔ),則算法的時(shí)間效

率會(huì)降低的是

I插入排序u.選擇排序III.起泡排序

IV.希爾排序v.堆排序

A.僅1、11氏僅口、田C.僅］H、IVD.僅W、V

12.假定計(jì)算機(jī)Ml和M2具有相同的指令集體系結(jié)構(gòu)（ISA）,主頻分

別為1.5GHz和1.2GHz。在Ml和M2上運(yùn)行某基準(zhǔn)程序P,平均

CPI分別為2和I,則程序P在Ml和M2上運(yùn)行時(shí)間的比值是

A.0.4B.0.625C.1.6D.2.5

13.某計(jì)算機(jī)主存按字節(jié)編址，由4個(gè)64Mx8位的DRAM芯片采用交

叉編址方式構(gòu)成，并與寬度為32位的存儲(chǔ)器總線和連，主存每次

最多讀寫32位數(shù)據(jù)若double型變M：%的主存地址為

804001AH,則讀取x需要的存儲(chǔ)周期數(shù)是

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

14.某C語(yǔ)肅程序段如下:

for(i=0；i<=9；i++)

lemp=1；

for(j=0；j<=i;j++)temp*=a[j_;

sum+=temp；

下列關(guān)廠數(shù)組a的訪問局部性的描述中.lE確的是

A.時(shí)間局部性和空間局部性皆有

B.B時(shí)間局部性，有空間局部性

C.有時(shí)間局部性，無(wú)空間局部性

D.時(shí)間局部性和空間局部性皆無(wú)

15.1列尋址方式中，最適合按下標(biāo)順序訪問一維數(shù)組元素的是

A.相對(duì)尋址B.寄存器尋址C.直接尋址D.變址尋址

16.某計(jì)算機(jī)按字節(jié)編址，指令字長(zhǎng)固定且只有兩種指令格式，其中三

地址指令29條，二地址指令107條，每個(gè)地址字段為6位，則指令

字長(zhǎng)至少應(yīng)該是

A.24位B.26位C.28位D.32位

17.下列關(guān)于超標(biāo)垃流水線特性的敘述中，正確的是

I能縮短流水線功能段的處理時(shí)間

D.能在一個(gè)時(shí)鐘周期內(nèi)同時(shí)發(fā)射多條指令

DI-能結(jié)合動(dòng)態(tài)調(diào)度技術(shù)提高指令執(zhí)行并行性

A.僅nB.僅i、inc.僅口、出口.1、11和1]1

錯(cuò)的是

18.下列關(guān)于主存儲(chǔ)器（MM）和控制存儲(chǔ)器（CS）的敘述中，??誤

A.MM在CPI夕卜，CS在:CPI內(nèi)

B.MM按地址訪問，CS按內(nèi)容訪問

C.存儲(chǔ)指令和數(shù)據(jù)，CS存儲(chǔ)微指令

D.MM用RAM和ROM實(shí)現(xiàn)，CSJ|jROM實(shí)現(xiàn)

19.卜一列關(guān)于指令流水線數(shù)據(jù)通路的敘述中，審啰的是

A.包含生成控制信號(hào)的控制部件..

B.包含算術(shù)邏輯運(yùn)算部件（ALU）

C.包含通用寄存糊組和取指部件

D.由組合邏輯電路和時(shí)序邏輯電路組合而成

20.下列關(guān)于多總線結(jié)構(gòu)的敘述中，饞墀的是

A.靠近CPU的總線速度較快

B.存儲(chǔ)器總線可支持突發(fā)傳送方式

C.總線之間須通過(guò)橋接器相連

D.PCI-Expressxl6采用并行傳輸方式

21.I/O指令實(shí)現(xiàn)的數(shù)據(jù)傳送通常發(fā)生在

A.I/O設(shè)備和I/O端口之間B.通用寄存器和I/O設(shè)備之間

4

C.I/O端口和I/O端口之間D.通用寄存器和I/O端口之間

22.下列關(guān)于多重中斷系統(tǒng)的敘述中，帶誤的是

A.在一條指令執(zhí)行結(jié)束時(shí)響應(yīng)中面

B.中斷處理期間CPU處于關(guān)中斷狀態(tài)

C.中斷請(qǐng)求的產(chǎn)生與當(dāng)前指令的執(zhí)行無(wú)關(guān)

D.CPU通過(guò)采樣中斷請(qǐng)求信號(hào)檢測(cè)中斷請(qǐng)求

23.假設(shè)4個(gè)作業(yè)到達(dá)系統(tǒng)的時(shí)刻和運(yùn)行時(shí)間如下表所示。

作業(yè)到達(dá)時(shí)刻1運(yùn)行時(shí)間

J103

J213

J312

J431

系統(tǒng)在「=2時(shí)開始作業(yè)調(diào)度若分別采用先來(lái)先服務(wù)和短作業(yè)優(yōu)

先調(diào)度算法，則選中的作業(yè)分別是

A.J2、J3B.J1、J4C.J2J4D.J1J3

24.執(zhí)行系統(tǒng)調(diào)用的過(guò)程包括如下主要操作:

①返回用戶態(tài)②執(zhí)行陷入（trap）指令

③傳遞系統(tǒng)調(diào)用參數(shù)④執(zhí)行相應(yīng)的服務(wù)程序

正確的執(zhí)行順序是

A.②—③一①—*④B.②一④T③T①

C.③一一?1④一?①D.③一?④一?②

25.某計(jì)算機(jī)按字節(jié)編址，其動(dòng)態(tài)分區(qū)內(nèi)存管理采用最佳適應(yīng)算法，每

次分配和回收內(nèi)存后都對(duì)空閑分區(qū)鏈而新排序.當(dāng)前空閑分區(qū)信

息如下表所示,

分區(qū)起始地址20K500K1000K200K

分區(qū)大小40KB80KB100KB200KB

5

回收起始地址為60K、大小為140KB的分區(qū)后，系統(tǒng)中空閑分區(qū)

的數(shù)收、空閑分區(qū)鏈第一個(gè)分區(qū)的起始地址和大小分別是

A.3、20K.380KBB.3.500K、80KB

C.4.20KJ80KBD.4s500K、80KB

26.某文件系統(tǒng)的簇和磁盤場(chǎng)區(qū)大小分別為1KB和512Bo若一個(gè)文

件的大小為1026B,則系統(tǒng)分配給該文件的磁盤空間大小是

A.1026BB.1536BC.1538BD.2048B

27.下列有關(guān)基于時(shí)間片的進(jìn)程調(diào)度的敘述中，埼識(shí)的是

A.時(shí)間片越短，進(jìn)程切換的次數(shù)越多，系統(tǒng)"若也越大

B.當(dāng)前進(jìn)程的時(shí)間片用完后，該進(jìn)程狀態(tài)由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)

C.時(shí)鐘中斷發(fā)生后，系統(tǒng)會(huì)修改當(dāng)前進(jìn)程在時(shí)間片內(nèi)的剩余時(shí)間

D.影響時(shí)間片大小的主要因素包括響應(yīng)時(shí)間、系統(tǒng)開銷和進(jìn)程數(shù)

量等

28.與單道程序系統(tǒng)相比，多道程序系統(tǒng)的優(yōu)點(diǎn)是

I.CPU利用率高n.系統(tǒng)開銷小

in.系統(tǒng)吞吐量大w.I/O設(shè)備利用率高

A.僅I、川B.僅I、W

c.僅n、inD.僅i、m、iv

29.下列選項(xiàng)中，磁盤邏輯格式化程序所做的工作是

I.對(duì)磁盤進(jìn)行分區(qū)

n.建立文件系統(tǒng)的根目錄

山.確定磁盤扇區(qū)校驗(yàn)碼所占位數(shù)

w.對(duì)保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化

A.僅n氏僅n、w

c.僅D1、IVD.僅I、n、iv

30.某文件系統(tǒng)中，針時(shí)每個(gè)文件，川戶類別分為4類：安全管理員、文

件主、文件書的伙伴、其他用戶；訪問權(quán)限分為5和I：完全控制、執(zhí)

行、修改、讀取、寫入。若文件控制塊中用二進(jìn)制位中表示文件權(quán)

限，為表示不同類別用戶對(duì)一個(gè)文件的訪問權(quán)限，則描述文件權(quán)限

的位數(shù)至少應(yīng)為6

A.5B.9C.12D.20

31.若文件fl的硬鏈接為f2,兩個(gè)進(jìn)程分別打開fl和f2,獲得對(duì)應(yīng)的文

件描述符為fdl和fd2,則下列敘述中，正確的是

I”和f2的讀寫指針位置保持相同

口.fl和f2共享同一個(gè)內(nèi)存索引結(jié)點(diǎn)

n.fdi和fd2分別指向各自的用戶打開文件表中的一項(xiàng)

A.僅皿B.僅口、mC.僅I、D口.1、!1和111

32.系統(tǒng)將數(shù)據(jù)從磁盤讀到內(nèi)存的過(guò)程包括以下操作：

①DMA控制器發(fā)出中斷請(qǐng)求

②初始化DMA控制器并啟動(dòng)磁盤

③從磁盤傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū)

④執(zhí)行“DMA結(jié)束”中斷服務(wù)程序

正確的執(zhí)行順序是

A.③一?①一?②一?④B.②一?③一?①—>④

C.②一①T③一④D.①T②T④一③

33.假設(shè)OSI參考模型的應(yīng)用層欲發(fā)送400B的數(shù)據(jù)（無(wú)拆分），除物

理層和應(yīng)用層之外，其他各層在封裝PDU時(shí)均引入20B的額外開

銷，則應(yīng)用層數(shù)據(jù)傳輸效率約為

A.80%B.83%C.87%D.91%

34.若信道在無(wú)噪聲情況下的極限數(shù)據(jù)傳輸速率不小卜信噪比為

30dB條件下的極限數(shù)據(jù)傳輸速率，則信號(hào)狀態(tài)數(shù)至少是

A.4B.8C.16D.32

35.在下圖所示的網(wǎng)絡(luò)中，若主機(jī)H發(fā)送一個(gè)封裝訪問Internet的IP分組

的IEEE802.11數(shù)據(jù)幀F(xiàn),則幀F(xiàn)的地址1、地址2和地址3分別是

00-12-34-56-78-9a00-I2-34-56-78-9b

A.00-12-34-56-78-9a,00-12-34-56-78-%,00-12-34-56-78-9c

B.00-12-34-56-78-9b,00-12-34-56-78-9a,00-12-34-56-78-9c

C.00-12-34-56-78~9b,00-12-34-56-78-9c,00-12-34-56-78-9a

D.00-12-34-56-78-9a,00-12-34-56-78-9c,00-12-34-56-78-9B

36.下列IP地址中，只能作為IP分組的源IP地址但不能作為目的IP

地址的是

A.B.

C.D.55

37.在接封裝RIP、（）SPF、BGP報(bào)文的協(xié)議分別是

A.TCP、UDP、IPB.TCPJP、UDP

C.UDP、TCPJPD.LDPJP.TCP

38.若將網(wǎng)絡(luò)/16劃分為128個(gè)規(guī)模相同的子網(wǎng)，則每個(gè)子網(wǎng)

可分配的最大IP地址個(gè)數(shù)是

A.254B.256

C.510D.512

39.若干間乙發(fā)起一個(gè)TCP連接，最大段長(zhǎng)MSS=1KB,RTT=5ms,乙

開辟的接收緩存為64KB,則甲從連接建立成功至發(fā)送的口達(dá)到

32KB,需經(jīng)過(guò)的時(shí)間至少是

A.25msB.30ms

C.160msD.165ms

40.下列關(guān)fFTP協(xié)議的敘述中，笛誤的是

A.數(shù)據(jù)連接在每次數(shù)據(jù)傳輸4電后就關(guān)閉

B.控制連接在整個(gè)會(huì)話期間保持打開狀態(tài)

C.服務(wù)器與客戶端的TCP20端口建立數(shù)據(jù)連接

D.客戶端與服務(wù)器的TCP21端口建立控制連接

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

41.（15分）i點(diǎn)設(shè)計(jì)一個(gè)算法，將給定的表達(dá)式樹（二叉樹）轉(zhuǎn)換為等價(jià)

的中綴去達(dá)式（通過(guò)括號(hào)反映操作符的計(jì)算次序）并輸出。例如,

當(dāng)下列兩棵表達(dá)式樹作為莫法的輸入時(shí)：

8

輸出的等價(jià)中綴去達(dá)式分別為(a+b)*(c*(-d))和(a*b)+

(-(c-d))o

二叉樹結(jié)點(diǎn)定義如下：

typedefstructnode

chardata[10]；//存儲(chǔ)操作數(shù)或操作符

structnode*left,*right；

BTree；

要求：

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

(2)根據(jù)設(shè)計(jì)思想，采川C或C++語(yǔ)；:描述克法，關(guān)鍵之處給出

注祥。

42.(8分)使用Prim(普里姆)算法求帶權(quán)連通圖的最小(代價(jià))生成樹

(MST)o請(qǐng)回答下列問題。

(1)對(duì)下列圖C,從頂點(diǎn)A開始求G的MST,依次給出按算法選出

的邊。

(2)圖G的MST是唯一的嗎？

9

(3)對(duì)任意的帶權(quán)連通圖，滿足什么條件時(shí)，其MST是唯一的？

?“+I位

43.(13分)已知/(幾)=工2'=2"-1=TTTIB,計(jì)算/")的C語(yǔ)”.函

i=0

數(shù)fl如下：

1intfl(unsignedn)

2|intsum=1,power=1；

3for(unsignedi=0；i<=n-1；i++)

4jpower*=2；

5sum+二power；

6!

7returnsum；

8I

將fl中的int都改為float,可得到計(jì)算/(到的另一個(gè)函數(shù)f2。假設(shè)

unsigned和int型數(shù)據(jù)都占32位，float采用IEEE754單精度標(biāo)準(zhǔn)。

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

(1)當(dāng)九二0時(shí)，口會(huì)出現(xiàn)死循環(huán)，為什么？若將門中的變讓，和〃

都定義為int型，則八是否還會(huì)出現(xiàn)死循環(huán)？為什么？

(2)11(23)和屹(23)的返回值是否相等？機(jī)器數(shù)各是什么(用十

六進(jìn)制表示)？

(3)fl(24)和他(24)的返回值分別為33554431和33554432.0,

為什么不相等？

(4)〃31)=232-1,而fl(31)的返回值卻為-1,為什么？若使

fl(幾)的返回值與/(八)相等，則最大的。是多少？

(5)Q(127)的機(jī)器數(shù)為7F800000H,對(duì)應(yīng)的值是什么？若使

f2(〃)的結(jié)果不溢出，則最大的n是多少？若使f2(n)的結(jié)果

精確(無(wú)舍入)，則最大的〃是多少？

44.(10分)在按字節(jié)編址的計(jì)算機(jī)M-上，題43中fl的部分源程序

(陰影部分)與對(duì)應(yīng)的機(jī)器級(jí)代碼(包括指令的虛擬地址)

如下：

10

intfl(unsignedn)

10040102055pushebp

for(unsignedi0；i<=n-1；i++)

200040105E3941)l'4cmpdwordptr[ebp-OCh,ecx

power*=2

23004010661)1l<2shledx,l

returnsum；

350040107FC3ret

其中，機(jī)器級(jí)代碼行包括"號(hào)、虛擬地址、機(jī)器指令和匯編指令。

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

(1)計(jì)算機(jī)M是RISC還是CISC?為什么？

(2)fl的機(jī)器指令代碼共占多少字節(jié)？要求給出計(jì)算過(guò)程。

(3)第20條指令cmp通過(guò)，減n-I實(shí)現(xiàn)對(duì)?和兀-1的比較。執(zhí)行

門(0)過(guò)程中，當(dāng)程0時(shí),cmp指令執(zhí)行后,進(jìn)/借位標(biāo)志CF的

內(nèi)容是什么？要求給出計(jì)算過(guò)程。

(4)第23條指令shl通過(guò)左移操作實(shí)現(xiàn)了power*2運(yùn)算，在12中

能否也用shl指令實(shí)現(xiàn)power*2?為什么？、

45.(7分)假定題44給出的計(jì)算機(jī)M采用二級(jí)分貝虛擬存儲(chǔ)管理方

式，虛擬地址格式如下：

頁(yè)―一號(hào)位).［貞表索引(10位)|頁(yè)內(nèi)偏移3(12位)

請(qǐng)針對(duì)題43的函數(shù)fl和題44中的機(jī)器指令代碼，回答卜列問題

(I)函數(shù)。的機(jī)器指令代碼占侈少頁(yè)？

（2）取第1條指令（pushebp）時(shí)，若在進(jìn)行地址變換的過(guò)程中需要

訪問內(nèi)存中的頁(yè)月錄和頁(yè)表，則會(huì)分別訪問它們各自的第幾

個(gè)表項(xiàng)（編號(hào)從0開始）？

（3）M的I/O采用中斷控制方式。若進(jìn)程P在調(diào)用fl之前通過(guò)

scanf（）獲取幾的值，則在執(zhí)行scanf（）的過(guò)程中，進(jìn)程P的狀

態(tài)會(huì)如何變化？CPU是否會(huì)進(jìn)入內(nèi)核態(tài)？

46.（8分）某進(jìn)程中有3個(gè)并發(fā)執(zhí)行的線程thread1,thread2和thread3,

其偽代碼如下所示。

//復(fù)數(shù)的結(jié)構(gòu)類型定義thread1thread3

typedefstruct11

1:cnumw；cnumw；

floata；w=add(x,y)；w.a=1；

floatb；....w.b=1；

]cnum；1z=add(z,w)；

cnumx,y,z；//全局變量