2017年全國碩士研究生招生考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題

2017年全國碩士研究生招生考試

計算機科學與技術學科聯(lián)考

計算機學科專業(yè)基礎綜合試題

一、單項選擇題：1~40小題，每小題2分，共80分。下列每題給出的

四個選項中，只有一個選項符合題目要求。

1.下列函數(shù)的時間復雜度是

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.下列關于棧的敘述中，歲年的是

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

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

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

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

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

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

3,適用于壓縮存儲稀疏矩陣的兩種存儲結構是

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

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

4.要使-棵非空二叉樹的先序序列與中jrjr列相同，其所有非葉結點

須滿足的條件是

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

C.結點的度均為1D.結點的度均為2

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

樹中與結點a同層的結點是

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

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

0100011001001011110101的譯碼結果是

A.acgabfhB.adbagbb

C.afbeagdD.afeefgd

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

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

少是

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

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

9.下列應用中，適合使用B,樹的是

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

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

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

理由是

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

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

m.歸并排序的運行效率更高

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

11.T列排序方法中,若將順JY存儲更換為鏈式存儲,則算法的時間效

率會降低的是

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

IV.希爾排序v.堆排序

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

12.假定計算機Ml和M2具有相同的指令集體系結構（ISA）,主頻分

別為1.5GHz和1.2GHz。在Ml和M2上運行某基準程序P,平均

CPI分別為2和I,則程序P在Ml和M2上運行時間的比值是

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

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

叉編址方式構成，并與寬度為32位的存儲器總線和連，主存每次

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

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

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

14.某C語肅程序段如下:

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

lemp=1；

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

sum+=temp；

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

A.時間局部性和空間局部性皆有

B.B時間局部性，有空間局部性

C.有時間局部性，無空間局部性

D.時間局部性和空間局部性皆無

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

A.相對尋址B.寄存器尋址C.直接尋址D.變址尋址

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

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

字長至少應該是

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

17.下列關于超標垃流水線特性的敘述中，正確的是

I能縮短流水線功能段的處理時間

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

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

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

錯的是

18.下列關于主存儲器（MM）和控制存儲器（CS）的敘述中，??誤

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

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

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

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

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

A.包含生成控制信號的控制部件..

B.包含算術邏輯運算部件（ALU）

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

D.由組合邏輯電路和時序邏輯電路組合而成

20.下列關于多總線結構的敘述中，饞墀的是

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

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

C.總線之間須通過橋接器相連

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

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

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

4

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

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

A.在一條指令執(zhí)行結束時響應中面

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

C.中斷請求的產(chǎn)生與當前指令的執(zhí)行無關

D.CPU通過采樣中斷請求信號檢測中斷請求

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

作業(yè)到達時刻1運行時間

J103

J213

J312

J431

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

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

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

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

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

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

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

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

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

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

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

息如下表所示,

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

分區(qū)大小40KB80KB100KB200KB

5

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

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

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

C.4.20KJ80KBD.4s500K、80KB

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

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

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

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

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

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

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

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

量等

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

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

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

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

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

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

I.對磁盤進行分區(qū)

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

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

w.對保存空閑磁盤塊信息的數(shù)據(jù)結構進行初始化

A.僅n氏僅n、w

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

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

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

行、修改、讀取、寫入。若文件控制塊中用二進制位中表示文件權

限，為表示不同類別用戶對一個文件的訪問權限，則描述文件權限

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

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

31.若文件fl的硬鏈接為f2,兩個進程分別打開fl和f2,獲得對應的文

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

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

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

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

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

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

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

②初始化DMA控制器并啟動磁盤

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

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

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

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

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

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

理層和應用層之外，其他各層在封裝PDU時均引入20B的額外開

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

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

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

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

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

35.在下圖所示的網(wǎng)絡中，若主機H發(fā)送一個封裝訪問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報文的協(xié)議分別是

A.TCP、UDP、IPB.TCPJP、UDP

C.UDP、TCPJPD.LDPJP.TCP

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

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

A.254B.256

C.510D.512

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

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

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

A.25msB.30ms

C.160msD.165ms

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

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

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

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

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

二、綜合應用題：41~47小題，共70分。

41.（15分）i點設計一個算法，將給定的表達式樹（二叉樹）轉(zhuǎn)換為等價

的中綴去達式（通過括號反映操作符的計算次序）并輸出。例如,

當下列兩棵表達式樹作為莫法的輸入時：

8

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

(-(c-d))o

二叉樹結點定義如下：

typedefstructnode

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

structnode*left,*right；

BTree；

要求：

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

(2)根據(jù)設計思想，采川C或C++語；:描述克法，關鍵之處給出

注祥。

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

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

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

的邊。

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

9

(3)對任意的帶權連通圖，滿足什么條件時，其MST是唯一的？

?“+I位

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

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,可得到計算/(到的另一個函數(shù)f2。假設

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

請回答下列問題。

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

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

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

六進制表示)？

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

為什么不相等？

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

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

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

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

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

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

(陰影部分)與對應的機器級代碼(包括指令的虛擬地址)

如下：

10

intfl(unsignedn)

10040102055pushebp

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

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

power*=2

23004010661)1l<2shledx,l

returnsum；

350040107FC3ret

其中，機器級代碼行包括"號、虛擬地址、機器指令和匯編指令。

請回答下列問題。

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

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

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

門(0)過程中，當程0時,cmp指令執(zhí)行后,進/借位標志CF的

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

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

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

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

式，虛擬地址格式如下：

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

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

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

（2）取第1條指令（pushebp）時，若在進行地址變換的過程中需要

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

個表項（編號從0開始）？

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

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

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

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

其偽代碼如下所示。

//復數(shù)的結構類型定義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；//全局變量