2021年408計算機學科專業(yè)基礎真題

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

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

其中next是指向直接后繼結點的指針，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的一端僅能進行入隊操作，另外一端既能進行入隊操作又能進行出隊操作。若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對應的二叉樹為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個葉結點，其權值分別為10，12，16，21，30，則其最小的帶權路徑長度（WPL）是（  ）。

A.89

B.200

C.208

D.289

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

A.16

B.20

C.23

D.25

7、給定如下有向圖，該圖的拓撲有序序列的個數(shù)是（  ）。

A.1

B.2

C.3

D.4

8、使用Dijkstra算法求下圖中從頂點1到其余各頂點的最短路徑，將當前找到的從頂點1到頂點2,3,4,5的最短路徑長度保存在數(shù)組dist中，求出第二條最短路徑后，dist中的內容更新為（  ）。

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個關鍵字，則該樹的結點個數(shù)最多是（  ）。

A.11

B.10

C.9

D.8

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

A.43，892

B.236，301

C.301，892

D.485，301

11、將關鍵字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年公布的全球超級計算機TOP500排名中，我國“神威·湖之光”超級計算機蟬聯(lián)第一，其浮點運算速度為93.0146PFLOPS，說明該計算機每秒鐘完成的浮點操作次數(shù)為（  ）。

A.9.3×1013次

B.9.3×1015次

C.9.3千萬億次

D.9.3億億次

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

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浮點格式精確表示的（  ）。

A.1.2

B.1.25

C.2.0

D.2.5

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

A.8

B.16

C.32

D.64

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

A.275

B.274

C.258

D.257

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

Ⅰ.指令寄存器

Ⅱ.微指令寄存器

Ⅲ.基址寄存器

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

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、IV

C.僅Ⅱ、Ⅳ

D.僅Ⅲ、Ⅳ

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

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

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

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

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

19、下列關于總線的敘述中，錯誤的是（  ）。

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

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

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

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

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

A.磁盤驅動器

B.打印機適配器

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

D.可編程中斷控制器

21、異常事件在當前指令執(zhí)行過程中進行檢測，中斷請求則在當前指令執(zhí)行后進行檢測。下列事件中。下列事件中，相應處理程序執(zhí)行后，必須回到當前指令重新執(zhí)行的是（  ）。

A.系統(tǒng)調用

B.頁缺失

C.DMA傳送結束

D.打印機缺紙

22、下列是關于多重中斷系統(tǒng)中CPU響應中斷的敘述，其中錯誤的是（  ）。

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

B.CPU只有在檢測到中斷請求信號后，才會進入中斷響應周期

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

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

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

A.trap指令

B.I/O指令

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

D.設置斷點指令

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

Ⅰ.申請空白的進程控制塊

Ⅱ.初始化進程控制塊

Ⅲ.設置進程狀態(tài)為執(zhí)行態(tài)

A.僅Ⅰ

B.僅Ⅰ、Ⅱ

C.僅Ⅰ、Ⅲ

D.僅Ⅱ、Ⅲ

25、下列內核的數(shù)據(jù)結構或程序中，分時系統(tǒng)實現(xiàn)時間片輪轉調度需要使用的是（  ）。

Ⅰ.進程控制塊

Ⅱ.時鐘中斷處理程序

Ⅲ.進程就緒隊列

Ⅳ.進程阻塞隊列

A.僅Ⅱ、Ⅲ

B.僅Ⅰ、Ⅳ

C.僅Ⅰ、Ⅱ、Ⅲ

D.僅Ⅰ、Ⅱ、Ⅳ

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

A.37

B.38

C.41

D.42

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

Ⅰ.中斷處理結束

Ⅱ.進程阻塞

Ⅲ.進程執(zhí)行結束

Ⅳ.進程的時間片用完

A.僅Ⅰ、Ⅲ

B.僅Ⅱ、Ⅳ

C.僅Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

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

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

A.00A01H

B.20A01H

C.60A01H

D.80A01H

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

A.當前進程的一級頁表的起始虛擬地址

B.當前進程的一級頁表的起始物理地址

C.當前進程的二級頁表的起始虛擬地址

D.當前進程的二級頁表的起始物理地址

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

A.刪除file1的快捷方式

B.釋放file1的文件控制塊

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

D.刪除目錄dir中與file1對應的目錄項

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

A.2

B.n

C.n+1

D.2n

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

A.頁置換

B.進程調度

C.建新進程

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

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

A.對話管理

B.路由選擇

C.端到端報文段傳輸

D.結點到結點流量控制

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

A.10111001

B.11010001

C.00101110

D.10110110

35、現(xiàn)將一個IP網(wǎng)絡劃分為3個子網(wǎng)，若其中一個子網(wǎng)是192.168.9.128/26，則下列網(wǎng)絡中，不可能是另外兩個子網(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的鏈路轉發(fā)一個總長度為1580B的IP數(shù)據(jù)報（首部長度為20B)時，進行了分片，且每個分片盡可能大，則第2個分片的總長度字段和MF標志位的值分別是（  ）。

A.796，0

B.796，1

C.800，0

D.800，1

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

A.9，10，12，6

B.9，10，28，20

C.9，20，12，20

D.9，20，28，20

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

A.CLOSE_WAIT

B.TIME_WAIT

C.FIN_WAIT_1

D.FIN_WAIT_2

39、若大小為12B的應用層數(shù)據(jù)分別通過1個UDP數(shù)據(jù)報和1個TCP段傳輸，則該UDP數(shù)據(jù)報和TCP段實現(xiàn)的有效載荷（應用層數(shù)據(jù)）最大傳輸效率分別是（  ）。

A.37.5%，16.7%

B.37.5%，37.5%

C.60.0%，16.7%

D.60.0%，37.5%

40、假設主機甲通過TCP向主機乙發(fā)送數(shù)據(jù)，部分過程如下圖所示。甲在???0時刻發(fā)送了一個號seq=501、封裝200B數(shù)據(jù)的段，在t1時刻收到乙發(fā)送的序號seq=601、確認序號ack_seq=501、接收窗口rcvwnd=500B的段，則甲在未收到新的確認段之前可以繼續(xù)向乙發(fā)送的數(shù)據(jù)序號范圍是（  ）。

A.501~1000

B.601~1000

C.701~1000

D.801~1100

二、綜合應用題（第41~47小題，共70分）

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

Typedef struct{ //圖的定義

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

Char VertticesList[MAXV]; //頂點表。MAXV為已定義常量

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

};MGraph;

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

（1）給出算法的基本設計思想。

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

（3）說明你所設計算法的時間復雜度和空間復雜度。

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]，則調用cmpCountSort(a，b，6)后數(shù)組b中的內容是什么？

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

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

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

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

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

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

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

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

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

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

（1）虛擬地址中哪幾位表示虛頁號？哪幾位表示頁內地址？

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

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

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

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

請回答下列問題。

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

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

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

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

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

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

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

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

請回答下列問題。

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

（2）若S的交換表結構為：<MAC地址，端口>，則t1時刻S交換表的內容是什么？

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