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

一、單項選擇題：1-40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是符合題目要求的。

1、下列對順序存儲的有序表（長度為n）實現(xiàn)給定操作的算法中平均時間復(fù)雜度為O（1）的是（  ）。

A.查找包含指定值元素的值

B.插入包含指定值元素的算法

C.刪除第i個元素的算法

D.獲取第i個值的算法

2、現(xiàn)有非空雙向鏈表L，其結(jié)點結(jié)構(gòu)為

prer是指向直接前驅(qū)結(jié)點的指針，next是指向直接后繼結(jié)點的指針。若要在L中指針p所指向的結(jié)點（非尾結(jié)點）之后插入指針s指向的新結(jié)點，則在執(zhí)行了語句序列：“s->next=p->next;p->next=s;”，后，還要執(zhí)行（  ）。

A.s->next->prer=p;s->prer=p;

B.p->next->prer=s;s->prer=p;

C.s->prer=s->next->prer;s->next->prer=s;

D.p->next->prer=s->prer;s->next->prer=p;

3、若采用三元組表存儲結(jié)構(gòu)存儲稀疏矩陣M，則除三元組外，下列數(shù)據(jù)中還需要保存的是（  ）。

I.M的行數(shù)

II.M中包含非零元素的行數(shù)

III.M的列數(shù)

IV.M中包含非零元素的列數(shù)

A.僅I、III

B.僅I、II

C.僅III、IV

D.I、II、III、IV

4、在有6個字符組成的字符集S中，各個字符出現(xiàn)的頻次分別為3，4，5，6，8，10，為S構(gòu)造的哈夫曼樹的加權(quán)平均長度為（  ）。

A.2.4

B.2.5

C.2.67

D.2.75

5、已知一棵二叉樹的樹形如圖，若其后序遍歷為f，d，b，e，c，a，則其先序列為（  ）。

A.aedfbc

B.acebdf

C.cabefd

D.dfebac

6、已知無向連通圖G中各邊的權(quán)值均為1，下列算法中一定能夠求出圖G中從某頂點到其余各個頂點最短路徑的是（  ）。

I.普利姆算法

II.克魯斯卡爾算法

III.圖的廣度優(yōu)先搜索

A.僅III

B.僅I、II

C.僅I、III

D.I、II、III

7、下列關(guān)于非空B樹的敘述中，正確的是（  ）。

I.插入操作可能增加樹的高度

II.刪除操作一定會導(dǎo)致葉結(jié)點的變化

III.查找某關(guān)鍵字一定是要查找到葉結(jié)點

IV.插入的新關(guān)鍵字最終位于葉結(jié)點中

A.僅I

B.僅I、II

C.僅III、IV

D.僅I、II、IV

8、對含有600個元素的有序順序表進行折半查找，關(guān)鍵字之間的比較次數(shù)最多是（  ）。

A.9

B.10

C.30

D.300

9、現(xiàn)有長度為5，初始為空的散列表HT，散列表函數(shù)H（K）=（k+4）%5，用線性探查再散列法解決沖突。若將關(guān)鍵字序列2022，12，25依次插入HT中，然后刪除關(guān)鍵字25，則HT中查找失敗的平均查找長度（  ）。

A.1

B.1.6

C.1.8

D.2.2

10、下列排序算法中，不穩(wěn)定的是（  ）。

I.希爾排序

II.歸并排序

III.快速排序

IV.堆排序

V.基數(shù)排序

A.僅I和II

B.僅II和V

C.僅I，III，IV

D.II，IV，V

11、使用快速排序算法對數(shù)據(jù)進行升序排序，若經(jīng)過一次劃分后得到的數(shù)據(jù)序列是68，11，70，23，80，77，48，81，93，88，則該次劃分的軸樞（  ）。

A.11

B.70

C.80

D.81

12、運算型指令中有一個地址碼是通用存儲器編號，其對應(yīng)的通用寄存器中存放的是操作數(shù)或操作數(shù)地址，CPU區(qū)分他們的依據(jù)是（  ）。

A.操作數(shù)的尋址方式

B.操作數(shù)的編碼方式

C.通用寄存器編號

D.通用寄存器的內(nèi)容

13、若short型變量x=-8190，則x的機器數(shù)為（  ）。

A.E002H

B.E001H

C.9FFFH

D.9FFEH

14、已知float型變量用IEEE754單精度浮點數(shù)格式表示。若float型變量x的機器數(shù)為8020000H，則x的值（  ）。

A.-2-128

B.-1.01×2-127

C. -1.01×2-128

D.非數(shù)NaN

15、某計算機的CPU有30根地址線，按字節(jié)編址，CPU和主存芯片連接時，要求主存芯片占滿所有可能存儲地址空間，并且RAM區(qū)和ROM區(qū)所分配的容量大小比為3：1，若RAM在連續(xù)低地址區(qū)，ROM在連續(xù)高地址區(qū)，則ROM的地址范圍（  ）。

A.0000 0000H~0FFF FFFFH

B.1000 0000H~2FFF FFFFH

C.3000 0000H~3FFF FFFFH

D.4000 0000H~4FFF FFFFH

16、若機器M的主頻為1.5GHz，在M上執(zhí)行程序p的指令條數(shù)為5×105，p的平均CPI為1.2，則p在M上的指令執(zhí)行速度和用戶CPU時間分別為（  ）。

A.0.8GIPS、0.4ms

B.0.8GIPS、0.4μs

C.1.25GIPS、0.4ms

D.1.25GIPS、0.4μs

17、已知x、y為int類型，當x=100，y=200時，執(zhí)行x-y指令的溢出標志OF和借位標志CF分別為0，1，那么當x=10，y=-20時，執(zhí)行該指令得到的OF和CF分別是（  ）。

A.OF=0，CF=0

B.OF=0，CF=1

C.OF=1，CF=0

D.OF=1，CF=1

18、元件分為兩類，組合邏輯元件（也稱操作元件）和時序邏輯元件（也稱狀態(tài)元件）。以下是組合邏輯元件的是（  ）。

Ⅰ.算術(shù)邏輯部件

Ⅱ.程序計數(shù)器

Ⅲ.通用寄存器組

Ⅳ.多路選擇題

A.僅Ⅰ、Ⅱ

B.僅Ⅱ、Ⅳ

C.僅Ⅱ、Ⅲ

D.僅Ⅰ、Ⅳ

19、采用取指、解碼、執(zhí)行、存儲、寫入5段流水線，RISC處理器，S0，S1，S2，S3，t2為寄存器編號，

I1: add S2 S1 S0 //[R[S2]]= R[S1]+R[S0]

I2: add load(S3)0(S2) //[R[S3]] =R[S1]+R[S2]

I3: beq t2 S3 L1 //if R[t2]==R[S3] jump to L1

I4: add t2 S3 10 //[R[t2]] = R[S3]+10

如采用旁路技術(shù)處理數(shù)據(jù)相關(guān)，即采用專用數(shù)據(jù)通路技術(shù)處理器，則在I1~I4執(zhí)行過程中，發(fā)生流水線阻塞的有（  ）。

A.僅I3

B.僅I2和I4

C.僅I2和I3

D.僅I3和I4

20、若有存儲總線寬度為64位，總線時鐘頻率為1GHZ，在總線上傳輸一個數(shù)據(jù)的地址需要一個的時鐘周期，不支持突發(fā)傳送，若該總線連接CPU和主存，主存每次準備一個64位數(shù)據(jù)需要6ns，主存塊大小為32B，則讀取一個主存塊時間為（  ）。

A.8ns

B.11ns

C.26ns

D.32ns

21、下列關(guān)于硬件和異常/中斷關(guān)系的敘述中，錯誤的是（  ）。

A.指令執(zhí)行過程中會檢測是否有異常

B.指令執(zhí)行結(jié)束會檢測是否有中斷

C.開中斷時CPU檢測到中斷請求后就進行中斷響應(yīng)

D.由中斷控制器向CPU報告中斷結(jié)束

22、以下關(guān)于IO控制方法的說法錯誤的是（  ）。

A.程序查詢方式是由CPU控制查詢

B.中斷方式是由CPU控制中斷

C.DMA方式中CPU執(zhí)行DMA程序控制數(shù)據(jù)傳輸

D.DMA方式常用于SSD和網(wǎng)絡(luò)適配器

23、與宏內(nèi)核操作系統(tǒng)相比，下列特征中微內(nèi)核操作系統(tǒng)的優(yōu)點是（  ）？

I.較好的性能

II.較高的可靠性

III.較高的安全性

IV.較強的可擴展性

A.僅II、IV

B.僅I、II、IV

C.僅I、III、IV

D.僅II、III、IV

24、中斷向量表適合采用什么數(shù)據(jù)結(jié)構(gòu)（  ）？

A.數(shù)組

B.隊列

C.單向鏈表

D.雙向鏈表

25、某系統(tǒng)采頁式存儲管理，用位圖管理空閑頁框。若頁大小為4KB，物理內(nèi)存大小為16GB，則位圖所占空間大小是（  ）？

A.128B

B.128KB

C.512KB

D.4MB

26、下列操作完成時，導(dǎo)致CPU從內(nèi)核態(tài)轉(zhuǎn)為用戶態(tài)的是（  ）？

A.阻塞進程

B.執(zhí)行CPU調(diào)度

C.喚醒進程

D.執(zhí)行系統(tǒng)調(diào)用

27、下列由當前線程引起的事件或執(zhí)行的操作中，可能導(dǎo)致該線程由執(zhí)行態(tài)變?yōu)榫途w態(tài)的是（  ）？

A.鍵盤輸入

B.缺頁異常

C.主動出讓CPU

D.執(zhí)行信號量的wait()操作

28、進程P1，P2和P3進入就緒隊列的時刻，優(yōu)先值（越大優(yōu)先權(quán)越高）以及CPU的執(zhí)行時間如下表所示：

系統(tǒng)采用基于優(yōu)先權(quán)的搶占式CPU調(diào)度算法，從0ms時刻開始進行調(diào)度，則P1，P2，P3的平均周轉(zhuǎn)時間為（  ）？

A.60ms

B.61ms

C.80ms

D.81ms

29、進程R和S共享數(shù)據(jù)data，若date在R和S中所在頁的頁號分別為p1和p2，兩個頁所對應(yīng)的頁框號分別為f1和f2，則下列敘述中正確的是（  ）。

A.p1和p2不一定相同，f1和f2不一定相同  

B.p1和p2一定相同，f1和f2不一定相同  

C.p1和p2不一定相同，f1和f2一定相同  

D.p1和p2一定相同，f1和f2一定相同

30、文件F僅有一個進程打開，當該進程關(guān)團時，必須的操作是（  ）。

A.刪除目錄項  

B.刪除內(nèi)存的文件索引結(jié)點  

C.刪除外存的文件索引結(jié)點  

D.文件磁盤索引節(jié)點鏈接計數(shù)器減一

31、對于采用虛擬內(nèi)存管理方式的系統(tǒng)，下列關(guān)于進程虛擬地址空間的敘述中錯誤的是（  ）？

A.每個進程有自己獨立的虛擬地址空間  

B.C語言中malloc()函數(shù)返回的是虛擬地址  

C.進程的數(shù)據(jù)段和代碼段可以有不同的訪問權(quán)限  

D.進程的虛擬地址空間由內(nèi)存和外存的容量決定 

32、設(shè)備分配需要關(guān)注的是（  ）？

I.設(shè)備類型
II.設(shè)備使用狀態(tài)

III.邏輯設(shè)備和物理設(shè)備的映射

IV.進程對設(shè)備的訪問權(quán)限

A.I和II

B.I和III

C.I、III和IV

D.I、II、III和IV

33、如圖，2段鏈路的數(shù)據(jù)傳輸速率為100Mbps，時延帶寬積(即單向傳播時延*帶寬）均為1000bit。若H1向H2發(fā)送1個大小為1MB 的文件，分組長度為 1000B，則從H1開始發(fā)送時刻起到H2收到文件全部數(shù)據(jù)時刻止，所需的時間至少是(注:M=10⁶)?

A.80.02ms

B.80.08ms

C.80.09ms

D.80.10ms

34、某無噪聲理想信道帶寬為4MHz，采用QAM調(diào)制，若該信道的最大數(shù)據(jù)傳輸率是48Mbps，則該信道采用的QAM調(diào)制方案是（  ）。

A.QAM-16

B.QAM-32

C.QAM-64

D.QAM-128

35、假設(shè)通過同一信道，數(shù)據(jù)鏈路層分別采用停-等協(xié)議、GBN 協(xié)議和 SR 協(xié)議(發(fā)送窗口和接收窗口相等）傳輸數(shù)據(jù)，三個協(xié)議數(shù)據(jù)幀長相同，忽略確認幀長度，幀序號位數(shù)為3比特。若對應(yīng)三個協(xié)議的發(fā)送方最大信道利用率分別是U1、U2 和 U3，則 U1、U2 和 U3 滿足的關(guān)系是（  ）。

A.U1≤U2<U3

B.U1<U3<U2

C.U2≤U3<U1

D.U3<U2<U

36、已知10BaseT以太網(wǎng)的爭用時間片為51.2μs。若網(wǎng)卡在發(fā)送某幀時發(fā)生了連續(xù)4次沖突，則基于二進制指數(shù)退避算法確定的再次嘗試重發(fā)該幀前等待的最長時間是（ ）。

A.51.2μs

B.204.8μs

C.768μs

D.819.2μs

37、若甲向乙發(fā)送數(shù)據(jù)時采用CRC校驗，生成多項式為G(x)=x4+x+1（即G=10011），則乙接收到下列比特串時，可以斷定其在傳輸過程中未發(fā)生錯誤的是（  ）。

A.101110000

B.101110100

C.101111000

D.101111100

38、某網(wǎng)絡(luò)拓撲如下圖所示，其中路由器R2實現(xiàn)NAT功能。若主機H向Internet發(fā)送一個IP分組，則經(jīng)過R2轉(zhuǎn)發(fā)后，該IP分組的源IP地址是（  ）。

A.192.168.0.33

B.192.168.0.35

C.192.168.0.1

D.192.168.0.3

39、主機168.16.84.24/20所在子網(wǎng)的最小可分配地址和最大可分配地址分別是（  ）。

A.168.16.80.1，168.16.84.254

B.168.16.80.1，168.16.95.254

C.168.16.84.1，168.16.84.254

D.168.16.84.1，168.16.95.254

40、下列關(guān)于ipv6和ipv4的敘述中，正確的是（  ）。

I.ipv6地址空間是ipv4地址空間的96倍

II.ipv4和ipv6的基本首部的長度均可變

III.ipv4向ipv6過渡可以采用雙協(xié)議棧和隧道技術(shù)

IV.ipv6首部的Hop-Limit等價于ipv4首部的TTL字段

A.僅I、Ⅱ

B.僅I、IV

C.僅Ⅱ、Ⅲ

D.僅Ⅲ、IV

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

41、（13分）對于有向圖，如果一個頂點的出度大于入度，則這個頂點稱為K頂點。有向圖用鄰接矩陣存儲，數(shù)據(jù)結(jié)構(gòu)定義如下：

Typedef struct{//圖的定義

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

char VerticesList[MAXV];//頂點表，MAXV為已定義常量

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

}MGraph;

設(shè)計算法int printVertices(MGraph G)對給定任意非空有向圖G，輸出G中所有K頂點的算法，并返回K頂點的個數(shù)。

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

（2）根據(jù)算法思想，寫出C/C++描述，并注釋。 

42、（10分）對含有n（n>0）個記錄的文件進行外部排序，采用置換-選擇排序生成初始歸并段時需要使用一個工作，工作區(qū)中能保存m個記錄，請回答下列問題。

（1）如果文件有19個記錄，其關(guān)鍵字是51，94，37，92，14，63，15，99，48，56，23，60，31，17，42，8，90，166，100。當m=4時，可生成幾個初始歸并段，各是什么？

（2）對任意m（n>>m>0），生成的第一個初始歸并段最大可能長度，最小可能長度分別是？

43、(14分) 某機器字長為32位的計算機M，采用請求調(diào)頁存儲管理。虛擬地址32位，頁面大小4KB。Cache采用4路組相聯(lián)映射，內(nèi)存塊大小為32B，Cache數(shù)據(jù)區(qū)大小為8KB。 二維數(shù)組int a[24][64]按行優(yōu)先存儲，數(shù)組的起始虛擬地址為0042 2000H。數(shù)組a的數(shù)據(jù)初始時未調(diào)入內(nèi)存，按如下方式訪問數(shù)組a：

for(int i=0;i<24;i++)

for(int j=0;j<64;j++)

a[i][j]=10;

（1）數(shù)組a分為幾個頁面存儲？訪問數(shù)組a缺頁幾次？頁故障地址各是什么？

（2）考慮對變量i，j的訪問，訪問數(shù)組a的過程是否具有時間局部性？為什么？

（3）在計算機M的32位地址中，塊內(nèi)地址是哪幾位？Cache組號是哪幾位？數(shù)組元素a[1][0]的虛擬地址是什么？對應(yīng)的Cache組號是什么？

（4）數(shù)組a總共占多少塊？訪問a的Cache命中率是多少？若采用如下方式訪問數(shù)組a，則命中率又是多少？

for(int j=0;j<64;j++)

    for(int i=0;i<24;i++)

a[i][j]=10;

44、（9分）題43中C程序段在計算機M上的部分機器級代碼如下，每個機器級代碼行中依次包含指令序號，虛擬地址，機器指令和匯編指令，請回答問題。

（1）第20條指令的虛擬地址是多少？

（2）已知第2條jmp和第7條jge都是跳轉(zhuǎn)指令，其操作碼分別是EBH和7DH，跳轉(zhuǎn)地址分別為0040 1084、0040 10BC，這兩條指令都采用什么尋址方式？給出第2條指令jmp的跳轉(zhuǎn)目標地址計算過程。

（3）已知第19條mov指令的功能是“a[i][j]←10”，其中ecx和edx為寄存器名，00422000H是數(shù)組a 的首地址，指令中源操作數(shù)采用什么尋址方式？己知edx中存放的是變量j，ecx 中存放的是？根據(jù)該指令的機器碼判斷計算機M采用的是大端還是小端方式。

（4）第1次執(zhí)行第19條指令時，取指令過程中是否會發(fā)生缺頁異常？為什么？

45、（7分）現(xiàn)要求學(xué)生使用swap指令和布爾型變量lock，實現(xiàn)臨界區(qū)互斥。lock為線程間共存的變量。lock的值為true時線程不能進入臨界區(qū)，為false時線程能進入臨界區(qū)。某同學(xué)編寫的實現(xiàn)臨界區(qū)互斥的偽代碼如下所示：

（1）請修改代碼，正確實現(xiàn)互斥（不增加語句條數(shù)）。

（2）請問是否可以用函數(shù)newSwap (&a, &b) 代替swap指令以實現(xiàn)臨界區(qū)的互斥？為什么？

46、（8分）進程P通過系統(tǒng)調(diào)用請求從鍵盤讀入一個字符。題目亂序給出6個處理步驟：

① 將進程P插入就緒隊列；

② 將進程P插入阻塞隊列；

③ 將字符從鍵盤控制器讀入系統(tǒng)緩沖區(qū)；

④ 啟動中斷處理程序；

⑤ 系統(tǒng)調(diào)用返回；

⑥ 用戶通過鍵盤輸入字符。

（1）①的前、后分別是哪個步驟？⑥的后面是什么步驟？

（2）哪個步驟一定會使CPU從P進程切換到其他進程？哪個步驟之后調(diào)度器可以調(diào)度進程P？

（3）哪個步驟是由鍵盤驅(qū)動程序完成的？

（4）中斷處理時，進程P是什么狀態(tài)？CPU處于內(nèi)核態(tài)還是用戶態(tài)？

47、(9分）如圖，主機H登錄FTP服務(wù)器后自服務(wù)器上估一個大小為18000B的文件F，假設(shè)H傳輸F建立數(shù)據(jù)連接時，選擇的初始序號為100，MTU=1000B，擁塞控制初始閾值為4MSS，RTT=10ms，忽略TCP的傳輸時延，在F的傳輸過程中，H以MSS段向服務(wù)器發(fā)送數(shù)據(jù)，且未發(fā)生差錯。丟包和亂序。

（1）FTP的控制連接是持久的還是非持久的？FTP的數(shù)據(jù)連接是持久的還是非持久的？H登錄FTP服務(wù)器時，建立的TCP 連接是控制連接還是數(shù)據(jù)連接？

（2）H通過數(shù)據(jù)連接發(fā)送F時，F(xiàn)的第一個字節(jié)序號是多少？在斷開數(shù)據(jù)連接的過程中，F(xiàn)TP發(fā)送的第二次揮手的ACK序號是？

（3）F發(fā)送過程中，當H收到確認序號為2101的確認段時，H的擁塞窗口調(diào)整為多少？收到確認序號為7101的確認段時，H的擁塞窗調(diào)整為多少？（4）H從請求建立數(shù)據(jù)連接開始，到確認F已被服務(wù)器全部接收為止，至少需要多長時間，期間應(yīng)用層數(shù)據(jù)平均發(fā)送速率是多少？