計(jì)算機(jī)綜合2021年真題

更新時(shí)間2022-06-2516:30:12

2021年真題

408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)

研PDF:YanPDF.COM

注：【】內(nèi)為本題同類知識(shí)點(diǎn)歷年考頻信息

一、選擇題本大題共40小題，共80分。

1.[1J已知頭指針h指向一個(gè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表，結(jié)點(diǎn)結(jié)構(gòu)為如下圖，其中next是指

向直接后繼結(jié)點(diǎn)的指針，P是尾指針，q是臨時(shí)指針。現(xiàn)耍刪除該鏈表的第一個(gè)元素，正確的語句

序列是---O

datanext

A.h->next=h->next->next;q=h->next;free(q);

B.q=h->next；h->next=h->next->next；free(q)；

C.q=h->next；h->next=q->next；if(p!=q)p=h；free(q)；

D.q=h->next;h->next=q->next;if(p==q)p=h;free(q);

2.[2]已知初始為空的隊(duì)列Q的一端僅能進(jìn)行入隊(duì)操作，另外一端既能進(jìn)行入隊(duì)操作又能進(jìn)行

出隊(duì)操作。若Q的入隊(duì)序列是1、2、3、4、5,則不能得到的出隊(duì)序列是一o

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

3.[4]已知二維數(shù)組A按行優(yōu)先方式存儲(chǔ)，每個(gè)元素占用1個(gè)存儲(chǔ)單元。若元素A[0][0]的存儲(chǔ)

地址是100,A[3][3]的存儲(chǔ)地址是220,則元素A[5][5]的存儲(chǔ)地址是一。

A.295B.300C.301D.306

4.[3]某森林F對(duì)應(yīng)的二叉樹為T,若T的先序遍歷序列是a,b,d,c,e,g,f,中序遍歷序

列是b,d,a,e,g,c,f,則F中樹的棵數(shù)是一。

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

5.[9]若某二叉樹有5個(gè)葉結(jié)點(diǎn)，其權(quán)值分別為10,12,16,21,30則其最小的帶權(quán)路徑長度

(WPL)是一。

A.89B.200C.208D.289

6.[7]給定平衡二叉樹如下圖所示，插入關(guān)鍵字23后，根中的關(guān)鍵字是

A.16B.20C.23D.25

7.[7]給定如下有向圖，該圖的拓?fù)溆行蛐蛄械膫€(gè)數(shù)是―。

第1頁共10頁

更新時(shí)間2022-06-2516:30:12

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

8.[5]使用Dijkstra算法求下圖中從頂點(diǎn)1到其余各頂點(diǎn)的最短路徑，將當(dāng)前找到的從頂點(diǎn)1

到頂點(diǎn)2,3,4,5的最短路徑長度保存在數(shù)組dist中，求出第二條最短路徑后，dist中的內(nèi)容更

新為一。

A.26,3,14,6B,25,3,14,6C,21,3,14,6D,15,3,14,6

9.[8]在一棵高度為3的3階B樹中，根為第1層，若第2層中有4個(gè)關(guān)鍵字，則該樹的結(jié)點(diǎn)

個(gè)數(shù)最多是―。

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

10.[4]設(shè)數(shù)組S[]={93,946,372,9,146,151,301,485,236,327,43,

892）,采用最低位優(yōu)先（LSD）基數(shù)排序?qū)排列成升序序列。第1趟分配、收集后，元素372之

前、之后緊鄰的元素分別是―。

A.43,892B,236,301C,301,892D,485,301

11.19]將關(guān)鍵字6,9,1,5,8,4,7依次插入到初始為空的大根堆H中，得到的H是—。

A.9,8,7,6,5,4,1B.9,8,7,5,6,1,4

C.9,8,7,5,6,4,1D.9,6,7,5,8,4,1

12.[3]2017年公布的全球超級(jí)計(jì)算機(jī)TOP500排名中，我國“神威?太湖之光”超級(jí)計(jì)算機(jī)蟬

聯(lián)第一，其浮點(diǎn)運(yùn)算速度為93.0146PFLOPS,說明該計(jì)算機(jī)每秒鐘內(nèi)完成的浮點(diǎn)操作次數(shù)約為—

A.9.3x1013次B.9.3x1015次C.9.3千萬億次D.9.3億億次

13.已知帶符號(hào)整數(shù)用補(bǔ)碼表示，變量x,y,z的機(jī)器數(shù)分別為FFFDH,FFDFH,7FFCH下列結(jié)論中,

正確的是一。

A.若x,y和z為無符號(hào)整數(shù)，則

B.若x,y和z為無符號(hào)整數(shù)，則

C.若x,y和z為帶符號(hào)整數(shù)，則/

D.若x,y和z為帶符號(hào)整數(shù)，則g<2<z

14.[7]下列數(shù)值中，不能用IEEE754浮點(diǎn)格式精確表示的是一。

A.1.2B,1.25C,2.0D.2.5

第2頁共10頁

更新時(shí)間2022-06-2516:30:12

15.[5]某計(jì)算機(jī)的存儲(chǔ)器總線中有24位地址線和32位數(shù)據(jù)線，按字編址，字長為32位。如果

000000H~3FFFFFH為RAM區(qū)，那么需要512Kx8位的RAM芯片數(shù)為一。

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

16.[8]若計(jì)算機(jī)主存地址為32位，按字節(jié)編址，Cache數(shù)據(jù)區(qū)大小為32KB,主存塊大小為32B,

采用直接映射方式和回寫（WriteBack）策略，則Cache行的位數(shù)至少是一。

A.275B.274C.258D.257

1714]下列寄存器中，匯編語言程序員可見的―。

I.指令寄存器IL微指令寄存器W.基址寄存器IV,標(biāo)志/狀態(tài)寄存器

A.僅I、nB.僅I、ivc.僅II、ivD.僅in、iv

18.[3]下列關(guān)于數(shù)據(jù)通路的敘述中，錯(cuò)誤的是—。

A.數(shù)據(jù)通路包含ALU等組合邏輯（操作）元件

B.數(shù)據(jù)通路包含寄存器等時(shí)序邏輯（狀態(tài)）元件

C.數(shù)據(jù)通路不包含用于異常事件檢測(cè)及響應(yīng)的電路

D.數(shù)據(jù)通路中的數(shù)據(jù)流動(dòng)路徑由控制信號(hào)進(jìn)行控制

19.[15]下列關(guān)于總線的敘述中，錯(cuò)誤的是_。

A.總線是在兩個(gè)或多個(gè)部件之間進(jìn)行數(shù)據(jù)交換的傳輸介質(zhì)

B.同步總線由時(shí)鐘信號(hào)定時(shí)，時(shí)鐘頻率不一定等于工作頻率

C.異步總線由握手信號(hào)定時(shí)，一握手過程完成一位數(shù)據(jù)交換

D.突發(fā)（Burst）傳送總線事務(wù)可以在總線上連續(xù)傳送多個(gè)數(shù)據(jù)

20.下列選項(xiàng)中，不屬于I/O接口的是―。

A.磁盤驅(qū)動(dòng)器B,打印機(jī)適配器

C.網(wǎng)絡(luò)控制器D.可編程中斷控制器

211111異常事件在當(dāng)前指令執(zhí)行過程中進(jìn)行檢測(cè)，中斷請(qǐng)求則在當(dāng)前指令執(zhí)行后進(jìn)行檢測(cè)。下

列事件中，相應(yīng)處理程序執(zhí)行后，必須回到當(dāng)前指令重新執(zhí)行的是―。

A.系統(tǒng)調(diào)用B.頁缺失C.DMA傳送結(jié)束D.打印機(jī)缺紙

22.下列是關(guān)于多重中斷系統(tǒng)中CPU響應(yīng)中斷的敘述，其中錯(cuò)誤的是

A.僅在用戶態(tài)（執(zhí)行用戶程序）下，CPU才能檢測(cè)和響應(yīng)中斷

B.CPU只有在檢測(cè)到中斷請(qǐng)求信號(hào)后，才會(huì)進(jìn)入中斷響應(yīng)周期

C.進(jìn)入中斷響應(yīng)周期時(shí)，CPU一定處于中斷允許（開中斷）狀態(tài)

D.若CPU檢測(cè)到中斷請(qǐng)求信號(hào)，則一定存在未被屏蔽的中斷源請(qǐng)求信號(hào)

23.下列指令中，只能在內(nèi)核態(tài)執(zhí)行的是一。

A.trap指令B.I/O指令C.數(shù)據(jù)傳送指令D.設(shè)置斷點(diǎn)指令

24.[1I下列操作中，操作系統(tǒng)在創(chuàng)建新進(jìn)程時(shí)，必須完成的是―。

I.申請(qǐng)空白的進(jìn)程控制塊

H.初始化進(jìn)程控制塊

III,設(shè)置進(jìn)程狀態(tài)為執(zhí)行態(tài)

A.僅IB.僅I、nc.僅I、niD.僅n、in

25.[5]下列內(nèi)核的數(shù)據(jù)結(jié)構(gòu)或程序中，分時(shí)系統(tǒng)實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度需要使用的是―。

第3頁共10頁

更新時(shí)間2022-06-2516:30:12

I.進(jìn)程控制塊

H.時(shí)鐘中斷處理程序

W.進(jìn)程就緒隊(duì)列

IV.進(jìn)程阻塞隊(duì)列

A.僅II、inB.僅I、IVc.僅I、II、inD.僅I、n、iv

26.［12］某系統(tǒng)中磁盤的磁道數(shù)為200(0—199),磁頭當(dāng)前在184號(hào)磁道上。用戶進(jìn)程提出的磁

盤訪問請(qǐng)求對(duì)應(yīng)的磁道號(hào)依次為184,187,176,182,199。若采用最短尋道時(shí)間優(yōu)先調(diào)度算法

(SSTF)完成磁盤訪問，則磁頭移動(dòng)的距離(磁道數(shù))是—。

A.37B.38C.41D.42

27.［10］下列事件中,可能引起進(jìn)程調(diào)度程序執(zhí)行的是—。

I.中斷處理結(jié)束H.進(jìn)程阻塞III.進(jìn)程執(zhí)行結(jié)束IV.進(jìn)程的時(shí)間片用完

A.僅I、HIB.僅H、IVC.III,IVD.I、n、in和IV

28.［19］某請(qǐng)求分頁存儲(chǔ)系統(tǒng)的頁大小為4KB,按字節(jié)編址。系統(tǒng)給進(jìn)程P分配2個(gè)固定的頁框,

并采用改進(jìn)型Clock置換算法，進(jìn)程P頁表的部分內(nèi)容如下表所示。若P訪問虛擬地址為02A01H

的存儲(chǔ)單元，則經(jīng)地址變換后得到的物理地址是—。

存在位訪問位修改位

頁號(hào)頁框號(hào)

I：存在，0：不存在1：訪問，0未訪問1：修改，0：未修改

220H000

360H110

480H111

A.00A01HB.20A01HC.60A01HD.80A01H

29.［20］在采用二級(jí)頁表的分頁系統(tǒng)中，CPU頁表基址寄存器中的內(nèi)容是

A.當(dāng)前進(jìn)程的一級(jí)頁表的起始虛擬地址

B.當(dāng)前進(jìn)程的一級(jí)頁表的起始物理地址

C.當(dāng)前進(jìn)程的二級(jí)頁表的起始虛擬地址

D.當(dāng)前進(jìn)程的二級(jí)頁表的起始物理地址

30.14］若目錄dir下有文件filel,則為刪除該文件內(nèi)核不必完成的工作是一。

A.刪除filel的快捷方式

B.釋放filel的文件控制塊

C.釋放filel占用的磁盤空間

D.刪除目錄dir中與filel對(duì)應(yīng)的目錄項(xiàng)

31.［4］若系統(tǒng)中有n(n，2)個(gè)進(jìn)程，每個(gè)進(jìn)程均需要使用某類臨界資源2個(gè)，則系統(tǒng)不會(huì)發(fā)生死

鎖所需的該類資源總數(shù)至少是—。

A.2B.nC.n+1D.2n

32.［4］下列選項(xiàng)中，通過系統(tǒng)調(diào)用完成的操作是―。

A.頁置換B.進(jìn)程調(diào)度C,創(chuàng)建新進(jìn)程D.生成隨機(jī)整數(shù)

第4頁共10頁

更新時(shí)間2022-06-2516:30:12

33.[3]在TCP/IP參考模型中，由傳輸層相鄰的下一層實(shí)現(xiàn)的主要功能是一。

A,對(duì)話管理B.路由選擇

C.端到端報(bào)文段傳輸D.結(jié)點(diǎn)到結(jié)點(diǎn)流量控制

34.[3]若下圖為一段差分曼徹斯特編碼信號(hào)波形，則其編碼的二進(jìn)制位串是―。

A.10111001B.11010001C.00101110D.10110110

35.[6]現(xiàn)將一個(gè)IP網(wǎng)絡(luò)劃分為3個(gè)子網(wǎng)，若其中一個(gè)子網(wǎng)是28/26,則下列網(wǎng)絡(luò)中,

不可能是另外兩個(gè)子網(wǎng)之一的是一。

A./25B,/26

C.92/26D.92/27

36.[2]若路由器向MTU=800B的鏈路轉(zhuǎn)發(fā)一總長度為1580B的1P數(shù)據(jù)報(bào)（首部長度為20B）時(shí),

進(jìn)行了分片，且每個(gè)分片盡可能大，則第2個(gè)分片的總長度字段和MF標(biāo)志位的值分別是

A.796,0B,796,1C,800,0D.800,1

37,[3]某網(wǎng)絡(luò)中的所有路由器均采用距離向量路由算法計(jì)算路由。若路由器E與鄰居路由器A,

B,C和D之間的直接鏈路距離分別是8,10,12和6,且E收到鄰居路由器的距離向量如下表所

示，則路由器E更新后的到達(dá)目的網(wǎng)絡(luò)Netl?Net4的距離分別是—。

目的網(wǎng)絡(luò)A的距離向量B的距離向量c的距離向量D的距離向量

Netl1232022

Net212353028

Net324181636

Net43630824

A.9,10,12,6B.9,10,28,20

C.9,20,12,20D.9,20,28,20

38.[3]若客戶首先向服務(wù)器發(fā)送FIN段請(qǐng)求斷開TCP連接，則當(dāng)客戶收到服務(wù)器發(fā)送的FIN段

并向服務(wù)器發(fā)送了ACK段后，客戶的TCP狀態(tài)轉(zhuǎn)換為―。

A.CLOSE.WAITB.TIME.WAITC.FIN_WAIT_1D.FIN_WAIT_2

39.【5】若大小為12B的應(yīng)用層數(shù)據(jù)分別通過1個(gè)UDP數(shù)據(jù)報(bào)和1個(gè)TCP段傳輸，則該UDP數(shù)

據(jù)報(bào)和TCP段實(shí)現(xiàn)的有效載荷（應(yīng)用層數(shù)據(jù)）最大傳輸效率分別是—。

A.37.5%,16.7%B.37.5%,37.5%C.60.0%,16.7%D.60.0%,37.5%

40.設(shè)主機(jī)甲通過TCP向主機(jī)乙發(fā)送數(shù)據(jù)，部分過程如下圖所示甲在b時(shí)刻發(fā)送一個(gè)序號(hào)seq=501,

封裝200B數(shù)據(jù)的段，在同時(shí)刻收到乙發(fā)送的序號(hào)seq=601、確認(rèn)序號(hào)ack.seq=501。接收窗口

rcvwnd=500B的段，則甲在未收到新的確認(rèn)段之前，可以繼續(xù)向乙發(fā)送的數(shù)據(jù)序號(hào)范圍是一。

第5頁共10頁

更新時(shí)間2022-06-2516:30:12

A.501?1000B.601-1100C.701-1000D.801~1100

二、簡答題本大題共7小題，共70分。

41.[6](15分)已知無向連通圖G由頂點(diǎn)集V和邊集E組成，|E|>0,當(dāng)G中度為奇數(shù)的頂點(diǎn)

個(gè)數(shù)為不大于2的偶數(shù)時(shí)，G存在包含所有邊且長度為|E|的路徑(稱為EL路徑)。設(shè)圖G采用鄰

接矩陣存儲(chǔ)，類型定義如下：

typedefstruct{//圖的定義

intnumvertices,numEdges；//圖中實(shí)際的項(xiàng)點(diǎn)數(shù)和邊數(shù)

charVerticesList[MAXV];//頂點(diǎn)表。MAXV為已定義常量

intEdge[MAXV][MAXV];//鄰接矩陣

}MGraph；

請(qǐng)?jiān)O(shè)計(jì)算法intlsExistEL(MGraphG),判斷G是否存在EL路徑，若存在，則返回1,否則返回

0o要求：

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

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

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

42.【8】(8分)已知某排序算法如下：

voidcmpCountSort(inta[],intb[],intn)

{inti,j,*count；

count=(int*)malloc(sizeof(int)*n);//C++語言：count=newint[n];

for(i=0;i<n;i++)count[i]=0;

for(i=0;i<n-l;i++)

for(j=i+l;j<n;j++)

if(a[i]<a[j])count[j]++；

elsecount[i]++;

for(i=0;i<n;i++)b[count[i]]-a[i];

free(count);//C++語言：deletecount;

}

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

⑴若有inta[]={25,-10,25,10,11,19),b[6]；則調(diào)用cmpCountSort(a,b,6)后數(shù)組

b中的內(nèi)容是外?么？

(2)若a中含有n個(gè)元素，則算法執(zhí)行過程中，元素之間的比較次數(shù)是多少？

(3)該算法是穩(wěn)定的嗎？若是，則闡述理由；否則，修改為穩(wěn)定排序算法。

43.[16](15分)假定計(jì)算機(jī)M字長為16位，按字節(jié)編址，連接CPU和主存的系統(tǒng)總線中地址線

為20位、數(shù)據(jù)線為8位，采用16位定長指令字，指令格式及其說明如下：

第6頁共10頁

更新時(shí)間2022-06-2516:30:12

格式6位2位2位2位4位指令功能或指令類型說明

R型000000rsrtrdoplR[rd]-R[rs]oplR[rt]

I型含ALU運(yùn)算、條件轉(zhuǎn)移和

op2rsrtimm

訪存操作3類指令

J型op3targetPC的低10位Jtarget

其中，opl?op3為操作碼，rs,rt和rd為通用寄存器編號(hào)，R[r]表示寄存器r的內(nèi)容，imm為

立即數(shù)，target為轉(zhuǎn)移目標(biāo)的形式地址。請(qǐng)回答下列問題。

(l)ALU的寬度是多少位？可尋址主存空間大小為多少字節(jié)？指令寄存器、主存地址寄存器(MAR)

和主存數(shù)據(jù)寄存器(MDR)分別應(yīng)有多少位？

(2)R型格式最多可定義多少種操作？I型和J型格式總共最多可定義多少種操作？通用寄存器最多

有多少個(gè)？

(3)假定。pl為0010和0011時(shí)，分別表示帶符號(hào)整數(shù)減法和帶符號(hào)整數(shù)乘法指令，則指令01B2H

的功能是什么(參考上述指令功能說明的格式進(jìn)行描述)？若1,2,3號(hào)通用寄存器當(dāng)前內(nèi)容

分別為B052H,0008H,0020H,則分別執(zhí)行指令01B2H和01B3H后，3號(hào)通用寄存器內(nèi)容

各是什么？各自結(jié)果是否溢出？

⑷若采用I型格式的訪存指令中imm(偏移量)為帶符號(hào)整數(shù)，則地址計(jì)算時(shí)應(yīng)對(duì)imm進(jìn)行零擴(kuò)

展還是符號(hào)擴(kuò)展？

(5)無條件轉(zhuǎn)移指令可以采用上述哪種指令格式？

44.[27](8分)假設(shè)計(jì)算機(jī)M的主存地址為24位，按字節(jié)編址；采用分頁存儲(chǔ)管理方式，虛擬地

址為30位，頁大小為4KB；TLB采用2路組相聯(lián)方式和LRU替換策略，共8組。請(qǐng)回答下列問題。

(1)虛擬地址中哪幾位表示虛頁號(hào)？哪幾位表示頁內(nèi)地址？

(2)已知訪問TLB時(shí)虛頁號(hào)高位部分用作TLB標(biāo)記，低位部分用作TLB組號(hào)，M的虛擬地址中哪

幾位是TLB標(biāo)記？哪幾位是TLB組號(hào)？

(3)假設(shè)TLB初始時(shí)為空，訪問的虛頁號(hào)依次為10,12,16,7,26,4,12和20,在此過程中,

哪一個(gè)虛頁號(hào)對(duì)應(yīng)的TLB表項(xiàng)被替換？說明理由。

(4)若將M中的虛擬地址位數(shù)增加到32位，則TLB表項(xiàng)的位數(shù)增加幾位？

45.[9](7分)下表給出了整型信號(hào)量S的wait。和signal。操作的功能描述，以及采用開/關(guān)中

斷指令實(shí)現(xiàn)信號(hào)量操作互斥的兩種方法。

第7頁共10頁

更新時(shí)間2022-06-2516:30:12

功能描述方法1方法2

semaphoreS;semaphoreS;semaphoreS;

wait(S){wait(S){wait(S){

while(S<=0);關(guān)中斷；關(guān)中斷；

S=S-1;while(S<=0);while(S<=0){

)S=S-1;開中斷；

開中斷；關(guān)中斷；

signal(S){))

S=S+1;S=S-1;

)signal(S){開中斷；

關(guān)中斷；)

S=S+1;signal(S){

開中斷；關(guān)中斷；

)S=S+1;

開中斷；

}

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

(1)為什么在waitQ和signalQ操作中對(duì)信號(hào)量S的訪問必須互斥執(zhí)行？

(2)分別說明方法1和方法2是否正確。若不正確，請(qǐng)說明理由。

(3〕用戶程序能否使用開/關(guān)中斷指令實(shí)現(xiàn)臨界區(qū)互斥？為什么？

46.(8分)某計(jì)算機(jī)用硬盤作為啟動(dòng)盤，硬盤第一個(gè)扇區(qū)存放主引導(dǎo)記錄，其中包含磁盤引導(dǎo)程序

和分區(qū)表。磁盤引導(dǎo)程序用于選擇要引導(dǎo)哪個(gè)分區(qū)的操作系統(tǒng)，分區(qū)表記錄硬盤上各分區(qū)的位置等

描述信息。硬盤被劃分成若干個(gè)分區(qū)，每個(gè)分區(qū)的第一個(gè)扇區(qū)存放分區(qū)引導(dǎo)程序，用于引導(dǎo)該分區(qū)

中的操作系統(tǒng)。系統(tǒng)采用多階段引導(dǎo)方式，除了執(zhí)行磁盤引導(dǎo)程序和分區(qū)引導(dǎo)程序外，還需要執(zhí)行