2019年計算機408統(tǒng)考真題

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

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

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

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

1.設(shè)N是描述問題規(guī)模的非負整數(shù)，下列程序段的時間復(fù)雜度是。

x=0;

while(n>=(x+l)*(x+1))

x=x+l;

A.O(log〃)B.。(〃叼C.0(")D.。(/)

2.若將一棵樹T轉(zhuǎn)化為對應(yīng)的二叉樹BT,則下列對BT的遍歷中，其遍歷序列與T的后

根遍歷序列相同的是.

A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷

3.對〃個互不相同的符號進行哈夫曼編碼。若生成的哈夫曼樹共有115個結(jié)點，則〃的值

是。

A.56B.57C.58D.60

4.在任意一棵非空平衡二叉樹(AVL樹)「中，刪除某結(jié)點v之后形成平衡二叉樹Tz,

再將v插入T2形成平衡二叉樹T3。下列關(guān)于Ti與T3的敘述中，正確的是。

I.若v是Ti的葉結(jié)點，則Ti與T3可能不相同

II.若v不是Ti的葉結(jié)點，則Ti與T3一定不相同

III.若v不是Ti的葉結(jié)點，則Ti與T3一定相同

A.僅IB.僅IIC.僅kIID.僅I、III

5.下圖所示的AOE網(wǎng)表示一項包含8個活動的工程?；顒觗的最早開始時間和最遲開始

時間分別是。

A.3和7B.12和12C.12和14D.15和15

6.用有向無環(huán)圖描述表達式(x+y)((x+y)/x),需要的頂點個數(shù)至少是。

A.5B.6C.8D.9

7.選擇一個排序算法時，除算法的時空效率，下列因素中，還需要考慮的是。

I.數(shù)據(jù)的規(guī)模II.數(shù)據(jù)的存儲方式IIL算法的穩(wěn)定性IV.數(shù)據(jù)的初始狀態(tài)

A.僅IIIB.僅I、II

C.僅n、IILIVD.I、ILIlkIV

2019年計算機408統(tǒng)考真題第1頁，共7頁

8.現(xiàn)有長度為11且初始為空的散列表HT,散列函數(shù)是“（key）=key%7,采用線性探查

（線性探測再散列）法解決沖突。將關(guān)鍵字序列87,40,30,6,11,22,98,20依次插入HT后，HT

查找失敗的平均查找長度是。

A.4B.5.25C.6D.6.29

9.設(shè)主串T="abaabaabcabaabc",模式串S="abaabc",采用KMP算法進行模式匹配，到

匹配成功時為止，在匹配過程中進行的單個字符間的比較次數(shù)是。

A.9B.10C.12D.15

10.排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一“趟”。下列序列

中，不可能是快速排序第二趟結(jié)果的是o

A.5,2,16,12,28,60,32,72B.2,16,5,28,12,60,32,72

C.2,12,16,5,28,32,72,60D.5,2,12,28,16,32,72,60

11.設(shè)外存上有120個初始歸并段，進行12路歸并時，為實現(xiàn)最佳歸并，需要補充的虛段

個數(shù)是。

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

12.下列關(guān)于馮?諾依曼結(jié)構(gòu)計算機基本思想的敘述中，錯誤的是。

A.程序的功能都通過中央處理器執(zhí)行指令實現(xiàn)

B.指令和數(shù)據(jù)都用二進制數(shù)表示，形式上無差別

C.指令按地址訪問，數(shù)據(jù)都在指令中直接給出

D.程序執(zhí)行前，指令和數(shù)據(jù)需預(yù)先存放在存儲器中

13.考慮以下C語言代碼：

unsignedshortusi=65535;

shortsi=usi;

執(zhí)行上述程序段后，si的值是。

A.-1B.-32767C.-32768D.-65535

14.下列關(guān)于缺頁處理的敘述中，錯誤的是。

A.缺頁是在地址轉(zhuǎn)換時CPU檢測到的一種異常

B.缺頁處理由操作系統(tǒng)提供的缺頁處理程序來完成

C.缺頁處理程序根據(jù)頁故障地址從外存讀入所缺失的頁

D.缺頁處理完成后回到發(fā)生缺頁的指令的下一條指令執(zhí)行

15.某計算機采用大端方式，按字節(jié)編址。某指令中操作數(shù)的機器數(shù)為1234FF00H,該操

作數(shù)采用基址尋址方式，形式地址（用補碼表示）為FF12H,基址寄存器的內(nèi)容為F0000000H,

則該操作數(shù)的LSB（最低有效字節(jié)）所在的地址是。

A.F000FF12HB.F000FF15HC.EFFFFF12HD.EFFFFF15H

16.下列有關(guān)處理器時鐘脈沖信號的敘述中，錯誤的是o

A.時鐘脈沖信號由機器脈沖源發(fā)出的脈沖信號經(jīng)整形和分頻后形成

B.時鐘脈沖信號的寬度稱為時鐘周期，時鐘周期的倒數(shù)為機器主頻

C.時鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準確定

D.處理器總是在每來一個時鐘脈沖信號時就開始執(zhí)行一條新的指令

17.某指令功能為R[r2]-R[rl]+M[R[rO]],其兩個源操作數(shù)分別采用寄存器、寄存器間接

尋址方式。對于下列給定部件，該指令在取數(shù)及執(zhí)行過程中需要用到的是o

I.通用寄存器組（GPRs）II.算術(shù)邏輯單元（ALU）

2019年計算機408統(tǒng)考真題第2頁，共7頁

III.存儲器(Memory)IV.指令譯碼器(ID)

A.僅I、IIB.僅I、IkIIIC.僅II、IILIVD.僅I、III、IV

18.在采用“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫回”5段流水線的處理器中，執(zhí)行如下指

令序列，其中sO、si、s2、S3和t2表示寄存器編號。

II：adds2,sl,s0//R[s2]<-R[sl]+R[sO]

12：loads3,0(t2)//R(s3]<-M[R[t2]+0]

13：adds2,s2,s3//R[s2]<-R[s2]+R[s3]

14：stores2,0(t2)//M[R[t2]+0]<-R[s2]

下列指令對中，不存在數(shù)據(jù)冒險的是.

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

19.假定一臺計算機采用3通道存儲器總線，配套的內(nèi)存條型號為DDR3-1333,即內(nèi)存條

所接插的存儲器總線的工作頻率為1333MHz，總線寬度為64位，則存儲器總線的總帶寬大約

是O

A.10.66GB/sB.32GB/sC.64GB/sD.96GB/s

20.下列關(guān)于磁盤存儲器的敘述中，錯誤的是。

A.磁盤的格式化容量比非格式化容量小

B.扇區(qū)中包含數(shù)據(jù)、地址和校驗等信息

C.磁盤存儲器的最小讀寫單位為一字節(jié)

D.磁盤存儲器由磁盤控制器、磁盤驅(qū)動器和盤片組成

21.某設(shè)備以中斷方式與CPU進行數(shù)據(jù)交換，CPU主頻為1GHz,設(shè)備接口中的數(shù)據(jù)緩沖

寄存器為32位，設(shè)備的數(shù)據(jù)傳輸率為50kB/s。若每次中斷開銷(包括中斷響應(yīng)和中斷處理)為

1000個時鐘周期，則CPU用于該設(shè)備輸入/輸出的時間占整個CPU時間的百分比最多是。

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

22.下列關(guān)于DMA方式的敘述中，正確的是。

I.DMA傳送前由設(shè)備驅(qū)動程序設(shè)置傳送參數(shù)

II.數(shù)據(jù)傳送前由DMA控制器請求總線使用權(quán)

III.數(shù)據(jù)傳送由DMA控制器直接控制總線完成

IV.DMA傳送結(jié)束后的處理由中斷服務(wù)程序完成

A.僅I、IIB.僅I、IILIV

C.僅H、HI、IVD.I、II、III、IV

23.下列關(guān)于線程的描述中，錯誤的是。

A.內(nèi)核級線程的調(diào)度由操作系統(tǒng)完成

B.操作系統(tǒng)為每個用戶級線程建立一個線程控制塊

C.用戶級線程間的切換比內(nèi)核級線程間的切換效率高

D.用戶級線程可以在不支持內(nèi)核級線程的操作系統(tǒng)上實現(xiàn)

24.下列選項中，可能會將進程喚醒的事件是。

I.I/O結(jié)束II.某進程退出臨界區(qū)III.當前進程的時間片用完

A.僅IB.僅inC.僅I、IID.I、II、III

25.下列關(guān)于系統(tǒng)調(diào)用的敘述中，正確的是。

I.在執(zhí)行系統(tǒng)調(diào)用服務(wù)程序的過程中，CPU處于內(nèi)核態(tài)

H.操作系統(tǒng)通過提供系統(tǒng)調(diào)用避免用戶程序直接訪問外設(shè)

III.不同的操作系統(tǒng)為應(yīng)用程序提供了統(tǒng)一的系統(tǒng)調(diào)用接口

IV.系統(tǒng)調(diào)用是操作系統(tǒng)內(nèi)核為應(yīng)用程序提供服務(wù)的接口

A.僅I、IVB.僅H、IIIC.僅I、ILIVD.僅I、111、IV

26.下列選項中，可用于文件系統(tǒng)管理空閑磁盤塊的數(shù)據(jù)結(jié)構(gòu)是?

I.位圖II.索引結(jié)點in.空閑磁盤塊鏈IV.文件分配表（FAT）

A.僅I、IIB.僅I、III、IVC.僅I、IIID.僅II、IILIV

27.系統(tǒng)采用二級反饋隊列調(diào)度算法進行進程調(diào)度。就緒隊列Qi采用時間片輪轉(zhuǎn)調(diào)度算法,

時間片為10ms；就緒隊列Q?采用短進程優(yōu)先調(diào)度算法；系統(tǒng)優(yōu)先調(diào)度Qi隊列中的進程，當

Qi為空時系統(tǒng)才會調(diào)度Q2中的進程；新創(chuàng)建的進程首先進入Qi;QI中的進程執(zhí)行一個時間片

后，若未結(jié)束，則轉(zhuǎn)入Q2。若當前Qi、Q2為空，系統(tǒng)依次創(chuàng)建進程Pi、P2后即開始進程調(diào)度，

Pi、P2需要的CPU時間分別為30ms和20ms,則進程Pi>P2在系統(tǒng)中的平均等待時間為。

A.25msB.20msC.15msD.10ms

28.在分段存儲管理系統(tǒng)中，用共享段表描述所有被共享的段。若進程Pi和P2共享段S,

下列敘述中，錯誤的是。

A.在物理內(nèi)存中僅保存一份段S的內(nèi)容

B.段S在Pi和P2中應(yīng)該具有相同的段號

C.Pi和P2共享段S在共享段表中的段表項

D.Pi和P2都不再使用段S時才回收段S所占的內(nèi)存空間

29.某系統(tǒng)采用LRU頁置換算法和局部置換策略，若系統(tǒng)為進程P預(yù)分配了4個頁框，

進程P訪問頁號的序列為0,1,2,7,0,5,3,5,0,2,7,6,則進程訪問上述頁的過程中,產(chǎn)生頁置

換的總次數(shù)是。

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

30.下列關(guān)于死鎖的敘述中，正確的是。

I.可以通過剝奪進程資源解除死鎖

II.死鎖的預(yù)防方法能確保系統(tǒng)不發(fā)生死鎖

III.銀行家算法可以判斷系統(tǒng)是否處于死鎖狀態(tài)

IV.當系統(tǒng)出現(xiàn)死鎖時一，必然有兩個或兩個以上的進程處于阻塞態(tài)

A.僅n、IIIB.僅I、II、IVC.僅I、n、inD.僅I、HI、IV

31.某計算機主存按字節(jié)編址，采用二級分頁存儲管理，地址結(jié)構(gòu)如下所示：

頁目錄號（10位）頁號（10位）頁內(nèi)偏移（12位）

虛擬地址20501225H對應(yīng)的頁目錄號、頁號分別是。

A.081H、101HB.081H、401HC.201H、101HD.201H、401H

32.在下列動態(tài)分區(qū)分配算法中，最容易產(chǎn)生內(nèi)存碎片的是。

A.首次適應(yīng)算法B.最壞適應(yīng)算法

C.最佳適應(yīng)算法D.循環(huán)首次適應(yīng)算法

33.OSI參考模型的第5層（自下而上）完成的主要功能是，

A.差錯控制B.路由選擇C.會話管理D.數(shù)據(jù)表示轉(zhuǎn)換

34.1OOBaseT快速以太網(wǎng)使用的導(dǎo)向傳輸介質(zhì)是。

A.雙絞線B.單模光纖C.多模光纖D.同軸電纜

35.對于滑動窗口協(xié)議，若分組序號采用3比特編號，發(fā)送窗口大小為5,則接收窗口最

大是?

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

36.假設(shè)一個采用CSMA/CD協(xié)議的10Mb/s局域網(wǎng)，最小幀長是128B,則在一個沖突域

內(nèi)兩個站點之間的單向傳播延時最多是。

A.2.56psB.5.12nsC.10.24gsD.20.48ps

37.若將101.200.16.0/20劃分為5個子網(wǎng)，則可能的最小子網(wǎng)的可分配IP地址數(shù)是。

A.126B.254C.510D.1022

38.某客戶通過一個TCP連接向服務(wù)器發(fā)送數(shù)據(jù)的部分過程如題38圖所示?？蛻粼跉v時

刻第一次收到確認序列號ack_seq=100的段，并發(fā)送序列號seq=100的段，但發(fā)生丟失。若

TCP支持快速重傳，則客戶重新發(fā)送seq=100段的時刻是。

A.ZiB.t2C.tiD./4

時間

題38圖

39.若主機甲主動發(fā)起一個與主機乙的TCP連接，甲、乙選擇的初始序列號分別為2018

和2046,則第三次握手TCP段的確認序列號是.

A.2018B.2019C.2046D.2047

40.下列關(guān)于網(wǎng)絡(luò)應(yīng)用模型的敘述中，錯誤的是o

A.在P2P模型中，結(jié)點之間具有對等關(guān)系

B.在客戶/服務(wù)器（CIS）模型中，客戶與客戶之間可以直接通信

C.在C/S模型中，主動發(fā)起通信的是客戶，被動通信的是服務(wù)器

D.在向多用戶分發(fā)一個文件時，P2P模型通常比C/S模型所需的時間短

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

41.（13分）設(shè)線性表￡=-2，a,T，％）采用帶頭結(jié)點的單鏈表保存，鏈表中的

結(jié)點定義如下：

typedefstructnode

{intdata;

structnode*next;

}NODE;

請設(shè)計一個空間復(fù)雜度為0(1)且時間上盡可能高效的算法，重新排列心中的各結(jié)點，得到

線性表￡'=(4,%,。2，勺_|,。3,冊-2,…)。要求：

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

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

(3)說明你所設(shè)計的算法的時間復(fù)雜度。

42.(10分)請設(shè)計一個隊列，要求滿足：①初始時隊列為空；②入隊時，允許增加隊列

占用空間；③出隊后，出隊元素所占用的空間可重復(fù)使用，即整個隊列所占用的空間只增不減；

④入隊操作和出隊操作的時間復(fù)雜度始終保持為0(1)。請回答下列問題：

(1)該隊列是應(yīng)選擇鏈式存儲結(jié)構(gòu)，還是應(yīng)選擇順序存儲結(jié)構(gòu)？

(2)畫出隊列的初始狀態(tài)，并給出判斷隊空和隊滿的條件。

(3)畫出第一個元素入隊后的隊列狀態(tài)。

(4)給出入隊操作和出隊操作的基本過程。

43.(8分)有"(”?3)位哲學(xué)家圍坐在一張圓桌邊，每位哲學(xué)家交替地就餐和思考。在

圓桌中心有機(機》1)個碗，每兩位哲學(xué)家之間有一根筷子。每位哲學(xué)家必須取到一個碗和兩

側(cè)的筷子后，才能就餐，進餐完畢，將碗和筷子放回原位，并繼續(xù)思考。為使盡可能多的哲學(xué)

家同時就餐，且防止出現(xiàn)死鎖現(xiàn)象，請使用信號量的P、V操作［wait。、signal。操作］描述上

述過程中的互斥與同步，并說明所用信號量及初值的含義。

44.(7分)某計算機系統(tǒng)中的磁盤有300個柱面，每個柱面有10個磁道，每個磁道有200

個扇區(qū)，扇區(qū)大小為512B。文件系統(tǒng)的每個簇包含2個扇區(qū)。請回答下列問題：

(1)磁盤的容量是多少？

(2)假設(shè)磁頭在85號柱面上，此時有4個磁盤訪問請求，簇號分別為100260、60005、

101660和110560。若采用最短尋道時間優(yōu)先(SSTF)調(diào)度算法，則系統(tǒng)訪問簇的先后次序是

什么？

(3)第100530簇在磁盤上的物理地址是什么？將簇號轉(zhuǎn)換成磁盤物理地址的過程是由I/O

系統(tǒng)的什么程序完成的？

45.(16分)己知/(〃)=〃!=〃x("-l)x(”_2)xix2xl,計算/(〃)的C語言函數(shù)fl的源程

序(陰影部分)及其在32位計算機M上的部分機器級代碼如下：

intfl(intn){

10040100055pushebp

if(n>l)

1100401018837D0801cmpdwordptr[ebp+8],1

120040101C7E17jlefl+35h(00401035)

returnn*f1(n-1);

130040101E8B4508moveax,dwordptr[ebp+8]

140040102183E801subeax,1

150040102450pusheax

1600401025E8D6FFFFFFcallfl(00401000)

1900401030OFAFClimuleax,ecx

2000401033EB05jmpfl+3Ah(0040103a)

elsereturri1；

2100401035B801000000moveax,1

}

26004010403BECcmpebp,esp

300040104AC3ret

其中，機器級代碼行包括行號、虛擬地址、機器指令和匯編指令，計算機M按字節(jié)編址，int

型數(shù)據(jù)占32位。請回答下列問題：

（1）計算110）需要調(diào)用函數(shù)fl多少次？執(zhí)行哪條指令會遞歸調(diào)用fl?

（2）上述代碼中，哪條指令是條件轉(zhuǎn)移指令？哪幾條指令一定會使程序跳轉(zhuǎn)執(zhí)行？

（3）根據(jù)第16行的call指令，第17