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

一、單項(xiàng)選擇題（第1～40小題，每小題2分，共80分。下列每題給出的四個選項(xiàng)中，只有一個選項(xiàng)最符合試題要求）

1、已知頭指針h指向一個帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表，結(jié)點(diǎn)結(jié)構(gòu)為：

其中next是指向直接后繼結(jié)點(diǎn)的指針，p是尾指針，q是臨時指針?，F(xiàn)要刪除該鏈表的第一個元素，正確的語句序列是（  ）。

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、已知初始為空的隊列Q的一端僅能進(jìn)行入隊操作，另外一端既能進(jìn)行入隊操作又能進(jìn)行出隊操作。若Q的入隊序列是1，2，3，4，5，則不能得到的出隊序列是（  ）。

A.5，4，3，1，2

B.5，3，1，2，4

C.4，2，1，3，5

D.4，1，3，2，5

3、已知二維數(shù)組A按行優(yōu)先方法存儲，每個元素占用1個存儲單元。若元素A[0][0]的存儲地址是100，A[3][3]的存儲地址是220，則元素A[5][5]的存儲地址是（  ）。

A.295

B.300

C.301

D.306

4、某森林F對應(yīng)的二叉樹為T，若T的先序遍歷序列是a，b，d，c，e，g，f，中序遍歷序列是b，d，a，e，g，c，f，則F中樹的棵數(shù)是（  ）。

A.1

B.2

C.3

D.4

5、若某二叉樹有5個葉結(jié)點(diǎn)，其權(quán)值分別為10，12，16，21，30，則其最小的帶權(quán)路徑長度（WPL）是（  ）。

A.89

B.200

C.208

D.289

6、給定平衡二叉樹如下圖所示，放入關(guān)鍵字23后，根中的關(guān)鍵字是（  ）。

A.16

B.20

C.23

D.25

7、給定如下有向圖，該圖的拓?fù)溆行蛐蛄械膫€數(shù)是（  ）。

A.1

B.2

C.3

D.4

8、使用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，6

B.25，3，14，6

C.21，3，14，6

D.15，3，14，6

9、在一棵高度為3的3階B樹中，根為第1層，若第2層中有4個關(guān)鍵字，則該樹的結(jié)點(diǎn)個數(shù)最多是（  ）。

A.11

B.10

C.9

D.8

10、設(shè)數(shù)組S[]={93，946，372，9，146，151，301，485，236，327，43，892}，采用最低位優(yōu)先（LSD）基數(shù)排序?qū)排列成升序序列。第1趟分配、收集后，元素372之前、之后緊鄰的元素分別是（  ）。

A.43，892

B.236，301

C.301，892

D.485，301

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

A.9，8，7，6，5，4，1

B.9，8，7，5，6，1，4

C.9，8，7，5，6，4，1

D.9，6，7，5，8，4，1

12、2017年公布的全球超級計算機(jī)TOP500排名中，我國“神威·湖之光”超級計算機(jī)蟬聯(lián)第一，其浮點(diǎn)運(yùn)算速度為93.0146PFLOPS，說明該計算機(jī)每秒鐘完成的浮點(diǎn)操作次數(shù)為（  ）。

A.9.3×1013次

B.9.3×1015次

C.9.3千萬億次

D.9.3億億次

13、已知帶符號整數(shù)用補(bǔ)碼表示，變量x，y，z的機(jī)器數(shù)分別為FFFDH，F(xiàn)FDFH，7FFCH，下列結(jié)論中，正確的是（  ）。

A.若x、y和z為無符號整數(shù)，則z<x<y

B.若x、y和z為無符號整數(shù)，則x<y<z

C.若x、y和z為帶符號整數(shù)，則x<y<z

D.若x、y和z為帶符號整數(shù)，則y<x<z

14、下列數(shù)值中，不能用IEEE754浮點(diǎn)格式精確表示的（  ）。

A.1.2

B.1.25

C.2.0

D.2.5

15、某計算機(jī)的存儲器總線中有24位地址線和32位數(shù)據(jù)線，按字節(jié)編址，字長為32位。若000000H~3FFFFFH為RAM區(qū)，則需要512K×8位的RAM芯片數(shù)為（  ）。

A.8

B.16

C.32

D.64

16、若計算機(jī)主存地址為32位，按字節(jié)編址，Cache數(shù)據(jù)區(qū)大小為32KB，主存塊大小為32B，采用直接映射方式和回寫（Write Back）策略，則cache行的位數(shù)至少是（  ）。

A.275

B.274

C.258

D.257

17、下列存儲器中，匯編語言程序員可見的是（  ）。

Ⅰ.指令寄存器

Ⅱ.微指令寄存器

Ⅲ.基址寄存器

Ⅳ.標(biāo)志狀態(tài)寄存器

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、IV

C.僅Ⅱ、Ⅳ

D.僅Ⅲ、Ⅳ

18、下列關(guān)于數(shù)據(jù)通路的敘述中，錯誤的是（  ）。

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

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

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

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

19、下列關(guān)于總線的敘述中，錯誤的是（  ）。

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

B.同步總線由時鐘信號定時，時鐘頻率不一定等于工作頻率

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

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

20、下列選項(xiàng)中不屬于I/O接口的是（  ）。

A.磁盤驅(qū)動器

B.打印機(jī)適配器

C.網(wǎng)絡(luò)控制器

D.可編程中斷控制器

21、異常事件在當(dāng)前指令執(zhí)行過程中進(jìn)行檢測，中斷請求則在當(dāng)前指令執(zhí)行后進(jìn)行檢測。下列事件中。下列事件中，相應(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)中斷的敘述，其中錯誤的是（  ）。

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

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

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

D.若CPU檢測到中斷請求信號，則一定存在未被屏蔽的中斷源請求信號 

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

A.trap指令

B.I/O指令

C.數(shù)據(jù)傳送指令

D.設(shè)置斷點(diǎn)指令

24、下列操作中，操作系統(tǒng)在創(chuàng)建新進(jìn)程時，必須完成的是（  ）。

Ⅰ.申請空白的進(jìn)程控制塊

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

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

A.僅Ⅰ

B.僅Ⅰ、Ⅱ

C.僅Ⅰ、Ⅲ

D.僅Ⅱ、Ⅲ

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

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

Ⅱ.時鐘中斷處理程序

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

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

A.僅Ⅱ、Ⅲ

B.僅Ⅰ、Ⅳ

C.僅Ⅰ、Ⅱ、Ⅲ

D.僅Ⅰ、Ⅱ、Ⅳ

26、某系統(tǒng)中磁盤的磁道數(shù)為200(0~199)，磁頭當(dāng)前在184號磁道上。用戶進(jìn)程提出的磁盤訪問請求對應(yīng)的磁道號依次為184、187、176、182、199。若采用最短尋道時間優(yōu)先調(diào)度算法（SSTF）完成磁盤訪問，則磁頭移動的距離（磁道數(shù)）是（  ）。

A.37

B.38

C.41

D.42

27、下列事件中，可能引起進(jìn)程調(diào)度程序執(zhí)行的是（  ）。

Ⅰ.中斷處理結(jié)束

Ⅱ.進(jìn)程阻塞

Ⅲ.進(jìn)程執(zhí)行結(jié)束

Ⅳ.進(jìn)程的時間片用完

A.僅Ⅰ、Ⅲ

B.僅Ⅱ、Ⅳ

C.僅Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

28、某請求分頁存儲系統(tǒng)的頁大小為4KB，按字節(jié)編址。系統(tǒng)給進(jìn)程P分配2個固定的頁框，并采用改進(jìn)型Clock置換算法，進(jìn)程P頁表的部分內(nèi)容如下表所示。

若P訪問虛擬地址為02A01H的存儲單元，則經(jīng)地址變換后得到的物理地址是（  ）。

A.00A01H

B.20A01H

C.60A01H

D.80A01H

29、在采用二級頁表的分頁系統(tǒng)中，CPU頁表基址寄存器中的內(nèi)容是（  ）。

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

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

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

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

30、若目錄dir下有文件file1，則為刪除該文件內(nèi)核不必完成的工作是（  ）。

A.刪除file1的快捷方式

B.釋放file1的文件控制塊

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

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

31、若系統(tǒng)中有n(n≥2)個進(jìn)程，每個進(jìn)程均需要使用某類臨界資源2個，則系統(tǒng)不會發(fā)生死鎖所需的該類資源總數(shù)至少是（  ）。

A.2

B.n

C.n+1

D.2n

32、下列選項(xiàng)中，通過系統(tǒng)調(diào)用完成的操作是（  ）。

A.頁置換

B.進(jìn)程調(diào)度

C.建新進(jìn)程

D.生成隨機(jī)整數(shù)

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

A.對話管理

B.路由選擇

C.端到端報文段傳輸

D.結(jié)點(diǎn)到結(jié)點(diǎn)流量控制

34、若下圖為一段差分曼徹斯特編碼信號波形，則其編碼的二進(jìn)制位串是（  ）。

A.10111001

B.11010001

C.00101110

D.10110110

35、現(xiàn)將一個IP網(wǎng)絡(luò)劃分為3個子網(wǎng)，若其中一個子網(wǎng)是192.168.9.128/26，則下列網(wǎng)絡(luò)中，不可能是另外兩個子網(wǎng)之一的是（  ）。

A.192.168.9.0/25

B.192.168.9.0/26

C.192.168.9.192/26

D.192.168.9.192/27

36、若路由器向MTU=800B的鏈路轉(zhuǎn)發(fā)一個總長度為1580B的IP數(shù)據(jù)報（首部長度為20B)時，進(jìn)行了分片，且每個分片盡可能大，則第2個分片的總長度字段和MF標(biāo)志位的值分別是（  ）。

A.796，0

B.796，1

C.800，0

D.800，1

37、某網(wǎng)絡(luò)中的所有路由器均采用距離向量路由算法計算路由。若路由器E與鄰居路由器A、B、C和D之間的直接鏈路距離分別是8、10、12和6，且E收到鄰居路由器的距離向量如下表所示，則路由器E更新后的到達(dá)目的網(wǎng)絡(luò)Net1~Net4的距離分別是（  ）。

A.9，10，12，6

B.9，10，28，20

C.9，20，12，20

D.9，20，28，20

38、若客戶首先向服務(wù)器發(fā)送FIN段請求斷開TCP連接，則當(dāng)客戶收到服務(wù)器發(fā)送的FIN段并向服務(wù)器發(fā)送了ACK段后，客戶的TCP狀態(tài)轉(zhuǎn)換為（  ）。

A.CLOSE_WAIT

B.TIME_WAIT

C.FIN_WAIT_1

D.FIN_WAIT_2

39、若大小為12B的應(yīng)用層數(shù)據(jù)分別通過1個UDP數(shù)據(jù)報和1個TCP段傳輸，則該UDP數(shù)據(jù)報和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ù)，部分過程如下圖所示。甲在???0時刻發(fā)送了一個號seq=501、封裝200B數(shù)據(jù)的段，在t1時刻收到乙發(fā)送的序號seq=601、確認(rèn)序號ack_seq=501、接收窗口rcvwnd=500B的段，則甲在未收到新的確認(rèn)段之前可以繼續(xù)向乙發(fā)送的數(shù)據(jù)序號范圍是（  ）。

A.501~1000

B.601~1000

C.701~1000

D.801~1100

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

41、（15分）已知無向連通圖G由頂點(diǎn)集V和邊集E組成|E|>0，當(dāng)G中度為奇數(shù)的頂點(diǎn)個數(shù)為不大于2的偶數(shù)時，G存在包含所有邊且長度為|E|的路徑（稱為EL路徑），設(shè)圖G采用鄰接矩陣存儲，類型定義下：

Typedef struct{ //圖的定義

int numVertices，numEdges; //圖中實(shí)際的頂點(diǎn)數(shù)和邊數(shù)

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

 Int Edge[MAXV][MAXV]; //鄰接矩陣

};MGraph;

請設(shè)計算法：int IsExistEL(MGraph G)，判斷G是否存在EL路徑，若存在，則返回1，否則，返回0，要求：

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

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

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

42、（8分）已知某排序算法：

void cmpCountSort(int a[],int b[], int n){

int i,j, *count;

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

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

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

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

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

else count[i]++;

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

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

}

請回答下列問題。

（1）若有int a[]={25，-10，25，10，11，19}，b[6]，則調(diào)用cmpCountSort(a，b，6)后數(shù)組b中的內(nèi)容是什么？

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

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

43、（15分）假定計算機(jī)M字長為16位，按字節(jié)編址，連接CPU和主存的系統(tǒng)總線中地址線為20位、數(shù)據(jù)線為8位，采用16位定長指令字，指令格式及其說明如下：

其中，op1~op3為操作碼，rs、rt和rd為通用寄存器編號，R[r]表示寄存器r的內(nèi)容，imm為立即數(shù)，target為轉(zhuǎn)移目標(biāo)的形式地址。請回答下列問題。

（1）ALU的寬度是多少位？可尋址主存空間大小為多少字節(jié)？指令寄存器、主存地址寄存器（MAR）和主存數(shù)據(jù)寄存器（MDR）分別應(yīng)有多少位？

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

（3）假定op1為0010和0011時，分別表示帶符號整數(shù)減法和帶符號整數(shù)乘法指令，則指令01B2H的功能是什么（參考上述指令功能說明的格式進(jìn)行描述）？若1、2、3號通用寄存器當(dāng)前內(nèi)容分別為B052H、0008H、0020H，則分別執(zhí)行指令01B2H和01B3H后，3號通用寄存器內(nèi)容各是什么？各自結(jié)果是否溢出？

（4）若采用I型格式的訪存指令中imm（偏移量）為帶符號整數(shù)，則地址計算時應(yīng)對imm進(jìn)行零擴(kuò)展還是符號擴(kuò)展？

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

44、（8分）假設(shè)計算機(jī)M的主存地址為24位，按字節(jié)編址；采用分頁存儲管理方式，虛擬地址為30位，頁大小為4KB；TLB采用2路組相聯(lián)方式和LRU替換策略，共8組。請回答下列問題。

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

（2）已知訪問TLB時虛頁號高位部分用作TLB標(biāo)記，低位部分用作TLB組號，M的虛擬地址中哪幾位是TLB標(biāo)記？哪幾位是TLB組號？

（3）假設(shè)TLB初始時為空，訪問的虛頁號依次為10、12、16、7、26、4、12和20，在此過程中，哪一個虛頁號對應(yīng)的TLB表項(xiàng)被替換？說明理由。

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

45、（7分）下表給出了整型信號量S的wait()和signal()操作的功能描述，以及采用開/關(guān)中斷指令實(shí)現(xiàn)信號量操作互斥的兩種方法。

請回答下列問題。

（1）為什么在wait()和signal()操作中對信號量S的訪問必須互斥執(zhí)行？

（2）分別說明方法1和方法2是否正確。若不正確，請說明理由。

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

46、（8分）某計算機(jī)用硬盤作為啟動盤，硬盤第一個扇區(qū)存放主引導(dǎo)記錄，其中包含磁盤引導(dǎo)程序和分區(qū)表。磁盤引導(dǎo)程序用于選擇要引導(dǎo)哪個分區(qū)的操作系統(tǒng)，分區(qū)表記錄硬盤上各分區(qū)的位置等描述信息。硬盤被劃分成若干個分區(qū)，每個分區(qū)的第一個扇區(qū)存放分區(qū)引導(dǎo)程序，用于引導(dǎo)該分區(qū)中的操作系統(tǒng)。系統(tǒng)采用多階段引導(dǎo)方式，除了執(zhí)行磁盤引導(dǎo)程序和分區(qū)引導(dǎo)程序外，還需要執(zhí)行ROM中的引導(dǎo)程序。請回答下列問題。

（1）系統(tǒng)啟動過程中操作系統(tǒng)的初始化程序、分區(qū)引導(dǎo)程序、ROM中的引導(dǎo)程序、磁盤引導(dǎo)程序的執(zhí)行順序是什么？

（2）把硬盤制作為啟動盤時，需要完成操作系統(tǒng)的安裝、磁盤的物理格式化、邏輯格式化、對磁盤進(jìn)行分區(qū)，執(zhí)行這4個操作的正確順序是什么？

（3）磁盤扇區(qū)的劃分和文件系統(tǒng)根目錄的建立分別是在第（2）問的哪個操作中完成的？

47、（9分）某網(wǎng)絡(luò)拓?fù)淙珙}47圖所示，以太網(wǎng)交換機(jī)S通過路由器R與Internet互聯(lián)。路由器部分接口、本地域名服務(wù)器、H1、H2的IP地址和MAC地址如圖中所示。在t0時刻H1的ARP表和S的交換表均為空，H1在此刻利用瀏覽器通過域名www.abc.com請求訪問Web服務(wù)器，在t1時刻（t1＞t0）S第一次收到了封裝HTTP請求報文的以太網(wǎng)幀，假設(shè)從t0到t1期間網(wǎng)絡(luò)未發(fā)生任何與此次Web訪問無關(guān)的網(wǎng)絡(luò)通信。

請回答下列問題。

（1）從t0到t1期間，H1除了HTTP之外還運(yùn)行了哪個應(yīng)用層協(xié)議？從應(yīng)用層到數(shù)據(jù)鏈路層，該應(yīng)用層協(xié)議報文是通過哪些協(xié)議進(jìn)行逐層封裝的？

（2）若S的交換表結(jié)構(gòu)為：<MAC地址，端口>，則t1時刻S交換表的內(nèi)容是什么？

（3）從t0到t1期間，H2至少會接收到幾個與此次Web訪問相關(guān)的幀？接收到的是什么幀？幀的目的MAC地址是什么？