2025 年 408 真題及答案

2025 年 408 真題

歷年408真題及答案下載直通車

1、以下 C 代碼的時間復雜度是多少？（）

int count = 0;
for (int i=0; i*i<n; i++)for (int j=0; j<i; j++)count++;

A O(log2n)
B O(n)
C O(nlogn)
D O(n2)

2、對于括號匹配問題，符號棧初始為空，容量為 3，哪個表達式不能實現？（）

A. (a+[b+(c+d)e]+f)+g-h
B. [a*((b+c)/(d-e)+f/g)]-h
C. [a*(b-(c-d)*e/(f+g))-h]
D. [a-(b+[c*(d+e)-f]+g+h)]

3、以下數組不能作為完全二叉樹的是？（）

A. 8, 10, 15, 20, 25, 30, 35
B. 5, 9, 11, 14, 20, -1, -1
C. 1, 3, 6, 9, 12, 15, 18
D. 17, 20, 35, -1, 18, 45, -1, -1, 29, 2

4、下列關于二叉樹及森林的敘述中，正確的是？（）

A 完全二叉樹不存在度為 1 的結點
B 任意一個森林可以轉換為一棵二叉樹
C 二叉樹的分支結點個數比葉結點個數少
D 鏈式樹的根中保存的是最先計算的運算符

5、設字符集 S 包含 7 個字符，各字符出現的頻次分別是 2, 3, 4, 6, 10, 11。為 S 中的各字符構造哈夫曼編碼，編碼長度不小于 3 的字符個數是（）

6、下列關于圖的敘述中，正確的是（）

A 有向圖必定存在入度為 0 的頂點
B 有向無環圖的拓撲排序有序序列存在且唯一
C 各頂點的度均大于等于 2 的無向圖必有回路
D 可用 BFS 算法求出帶權圖中的每一對頂點的最短路徑

7、已知查找表中有 400 個元素，查找元素概率相同。采用分塊查找法且均勻分塊。若采用順序查找法確定元素所在塊，且塊內也采用順序查找法，為效率最高，每塊包含元素應為（）

A 8
B 10
C 20
D 25

8、給 7 個不同的關鍵字，能夠構成不同 4 階 B 樹的個數為（）

A 7
B 8
C9
D 10

9、下列關于散列法處理沖突的敘述中，正確的是（）

A 只要散列表不滿，線性探查再散列一定能找到一個空閑位置
B 只要散列表不滿，二次探查再散列一定能找到一個空閑位置
C 線性探查再散列處理的沖突，一定是發生在同義詞之間
D 二次探查再散列處理的沖突，一定是發生在非同義詞之間

10、下列排序算法中，最壞情況下元素移動最少的是（）

A 冒泡排序
B 直接插入排序
C 快速排序
D 簡單選擇排序

11、對含 9 個關鍵字的初始序列進行排序，若序列的變化情況如下表所示，則下列排序算法中，采用的是（）


初始序列	5, 25, 40, 30, 10, 20, 45, 15, 35
第 1 趟排序后的序列	5, 10, 20, 30, 15, 35, 45, 25, 40
第 2 趟排序后的序列	5, 10, 15, 25, 20, 30, 40, 35, 45

A 希爾排序
B 數排序
C 歸并排序
D 折半插入排序

12、在 32 位計算機上執行下列 C 語言代碼：

short si = -32767
unsigned int ui = si;

則 ui 的真值為（）

A 2¹⁵?1
B 2¹⁵+1
C 2³²?2¹⁵?1
D 2³²?2¹⁵+1

13、已知 float 型變量用 IEEE754 單精度浮點數格式表示。若 float 型變量 x 的機器數為 4730 0000H；則 x 的值為（）

A 0.375×2¹⁴
B 1.375×2¹⁴
C 0.375×2¹⁵
D 1.375×2¹⁵

14、假設 8 位字長的計算機中，兩個帶符號整數 x 和 y 的補碼表示分別為 $x\_{補} = A3H$ ， $y\_{補} = 75H$ ，則通過補碼加減運算器得到的 x-y 的值及 OF 標志分別為（）

A 24, 0
B 24, 1
C 46, 0
D 46, 1

15、某 32 計算機按字節編址，采用小端方式存放數據，編譯器按邊界對齊方式為下列 C 語言結構型數組變量 employce 分配儲存空間。

struct record {int id;char name[10];int salary;
} employee[200];

數組 employee 的起始地址為 0000A0B0H，employee[1].id 的機器數為 12345678H，問 56H 的地址是多少？（）

A 0000 A0C3H
B 0000 A0C4H
C 0000 A0C5H
D 0000 A0C6H

16、下列選項中，由指令體系結構（ISA）規定的是（）

A 是否采用陣列乘法器
B 是否采用定長指令字格式
C 是否采用微程序控制器
D 是否采用單總線數據通路

17、下列關于 RISC 的敘述中，錯誤的是（）

A 多采用硬連線方式實現控制器
B 通常采用 Load/Store 型指令設計風格
C 難以采用流水線數據通路實現微架構
D 多采用寄存器傳遞過程調用時的參數

18、下列關于 CPI 和 CPU 時鐘周期的敘述中，錯誤的是（）

A 不同類型指令的 CPI 可能不一樣
B 程序的 CPI 與 Cache 缺失率無關
C 單周期 CPU 的時鐘周期以最耗時指令所用的時間為準
D 流水線 CPU 的時鐘周期以最長流水段所用時間為準

19、下列關于 CPU 中的數據通路和控制器的敘述中，錯誤的是（）

A 通用寄存器組中應該包含程序計數器
B 控制器中一定包含指令操作碼的譯碼電路
C 單周期 CPU 中的控制器比多周期 CPU 中的更簡單
D 流水線 CPU 需解決數據相關和控制相關等冒險問題

20、某處理器總線采用同步，并行傳輸方式，每個總線時鐘周期傳送 4 次數據（quadpumped 技術），若該總線的工作頻率為 1333MHz（實際單位是 MT/s，表示每秒傳送 1333M/次），總線寬度為 64 位，則總線帶寬約為（）

A 10.66 GB/s
B 42.66 GB/s
C 85.31 GB/s
D 341.25 GB/s

21、下列設備中，適合采用 DMA 輸入輸出的設備是（）

I. 鍵盤

II. 網卡

III. 固態硬盤

IV. 針十式打印機

A I、II
B II、III
C II、IV
D III、IV

22、下列選項中，會觸發外部中斷請求的事件是（）

A DMA 傳送結束
B 總線事務結束
C 頁故障處理結束
D 執行斷點指令

23、在采用頁式虛擬存儲管理方式的系統中，當發生上下文切換時，下列寄存器中操作系統不需要更新的是（）

A 通用寄存器
B 頁表基址寄存器
C 程序計數器
D 內核中斷向量表基址寄存器

24、關于虛擬化技術，下列說法錯誤的是（）

A 操作系統可以在虛擬機上運行
B 一臺主機可以支持多個虛擬機
C VMM 與操作系統特權級相同
D 通過虛擬機技術，可以用一臺主機上模擬多種 ISA

25、優先權調度，采用單鏈表保存進程就緒隊列，高優先級進程在隊頭。就緒隊列長度為 n，則插入進程、選出進程的時間復雜度（）

A O(1),O(1)
B O(1),O(n)
C O(n),O(1)
D O(n),O(n)

26、現有一 LRU 算法，固定分配局部置換，已為進程分配 3 個頁框，頁面訪問序列為{0,1,2,0,5,1,4,3,0,2,3,2,0}，其中 0,1,2 已調入內存。則缺頁次數是（）

27、確定進程運行所需的最少頁框數時，要考慮的指標是（）

A 代碼段長
B 虛擬地址空間大小
C 物理地址空間大小
D 指令系統支持的尋址方式

28、關于虛擬文件系統，下列說法正確的是（）

A 虛擬文件系統是運行在虛擬內存的文件系統
B VFS 可以加快文件系統的訪問速度
C VFS 定義了可訪問不同文件系統的統一接口
D VFS 只能訪問本地文件系統，不能訪問網絡文件系統

29、某文件系統采用索引節點方式。用戶在目錄中新建文件 F 時，文件系統不會做的是（）

A 初始化文件 F 的索引節點
B 在目錄文件中寫入 F 的索引節點號
C 在目錄文件中寫入 F 的訪問權限信息
D 在目錄文件中增加一條文件 F 對應的目錄項

30、關于內存映射文件，下列說法正確的是（）

I. 可實現進程間通信

II. 實現了頁面到磁盤塊的映射

III. 將文件映射到進程的虛擬地址空間

IV. 將文件映射到系統的物理地址空間

A I、III
B I、IV
C II、III
D I、II、III

31、下列選項中，文件系統能知道外存空閑空間使用情況的是（）

A 目錄
B 系統打開文件表
C 文件分配表（FAT）
D 進程控制塊（FCB）

32、下列選項中，文件系統能為溫徹斯特硬盤和固態硬盤提供的功能是（）

A 劃分扇區
B 確定盤塊大小
C 降低尋道時間
D 降低尋道時間

33、如下圖所示，主機 H1 向 H2 發送一個 2MB（1MB = $10^6$ B）文件有三種方式：① 電路交換，建立時間為 32us，速度為 10Mbps；② 分組交換，分組長度為 400B，忽略首部；③ 報文交換。電路交換的時間為 $T\_{cs}$ ，報文交換的時間為 $T\_{ms}$ ，分組交換的時間為 $T\_{ps}$ ，則三者的大小關系是（）

A Tcs > Tms > Tps
B Tms >Tps > Tcs
C Tms > Tcs > Tps
D Tps > Tws >Tcs

34、某差錯編碼的編碼集為{ 10011010，01011100，11110000，00001111 }，其檢錯和糾錯能力是（）

A 可以檢測不超過 2 位錯，檢錯率 100%；可糾正不超過 1 位錯
B 可以檢測不超過 2 位錯，檢錯率 100%；可糾正不超過 2 位錯
C 可以檢測不超過 3 位錯，檢錯率 100%；可糾正不超過 1 位錯
D 可以檢測不超過 3 位錯，檢錯率 100%；可糾正不超過 2 位錯

35、現有一 10BaseT 以太網，甲乙處于同一個沖突域，連續發生 11 次沖突，甲再次發送的最大時間間隔為（）

A 0.512ms
B 0.5632ms
C 52.3776ms
D 104.8064ms

36、一臺新接入網絡的主機 H 通過 DHCP 服務器動態請求 IP 地址過程中，與 DHCP 服務器交換 DHCP 報文過程如下圖所示。封裝 DHCP 的 REQUEST 報文的 P 數據報的目的 IP 地址和源 IP 地址分別是（）

在這里插入圖片描述

A 192.168.5.1，0.0.0.0
B 192.168.5.1，192.168.5.9
C 255.255.255.255，0.0.0.0
D 255.255.255.255，192.168.5.9

37、假設路由器實現 NAT 功能，內網中主機 H 的 IP 地址為 192.168.1.5/24。若 H 運行某應用向 internet 發送一個 UDP 報文段，則路由器在轉發封裝該 UDP 報文段的 IP 數據報的過程中，UDP 報文的首部字段會被修改的是（）

I 源端口號

II 目的端口號

III 總長度

IV 校驗和

A 僅 I、III
B 僅 I、IV
C 僅 lI、III
D 僅 II、IV

38、主機甲通過 TCP 向主機乙發送數據的部分過程如下圖，seq 為序號，ack-seq 為確認序號，rcwnd 為接收窗口。甲在 $t\_0$ 時刻的擁塞窗口和發送窗口均為 2000B，擁塞控制閾值為 8000B，MSS=1000B。甲始終以 MSS 發送 TCP 段。若甲在 $t\_1$ 時刻收到如圖所示的確認段，則甲在未收到新的確認段之前，還可以繼續向乙發送的 TCP 段數是（）

在這里插入圖片描述
rcwnd=4000B

39、Time 是一個提供時間查詢服務的 C/S 架構網絡應用，支持客戶通過 UDP 和 TCP 向 Time 服務器請求時間。若某客戶與 Time 服務器通信往返時間為 8ms，則該客戶分別通過 UDP 和 TCP 向該服務器請求服務，所需的最少時間分別是（）

A 8ms，8ms
B 8ms，16ms
C 16ms，8ms
D 16ms，16ms

40、關于 POP3，正確的是（）

I 支持用戶代理從郵件服務器讀取郵件

II 支持用戶代理向郵件服務器發送郵件

III 支持郵件服務器之間發送與接收郵件

IV 支持一條 TCP 連接收取多封郵件

A I、IV
B II、III
C I、II、III
D I、III、IV

41

設有兩個長度均為 n 的一維整型數組 A 和 res，對數組 A 中的每個元素 A[i]，計算 A[i] 與 A[j](0 ≤ i ≤ j ≤ n-1)乘積的最大值，并將其保存到 res[i]中。

例如，若 A[i] = {1, 4, -9, 6}，則得到 res[i] = {6, 24, 81, 36}。

現給定數組 A，請設計一個時間和空間上盡可能高效的算法 calMulMax，求 res 中各元素的值。

函數原型為：void calMulMax(int A[], int res[], int n)，要求：

(1) 給出算法的基本設計思想：（4 分）

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

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

42

AOE 網，描述 12 個工程活動及持續時間。

在這里插入圖片描述

(1) 完成該工程的最短時間是多少？哪些是關鍵活動？

(2) 若以最短時間完成工程，則與活動 e 同時進行的活動可能有哪些？

(3) 時間余量最大的活動是哪個？其時間余量是多少？

(4) 假設工程從時刻 0 啟動，因某種原因，活動 b 在時刻 6 開始，為保證工程不延期，在其它活動持續時間保持不變的情況下， b 的持續時間最多是多少？若不改變 b 的持續時間，則壓縮哪個活動的持續時間也能保證工程不延期？

43

計算機 M 字長為 32 位，按字節編址，數據 cache 的數據區大小為 32KB，采 8 路組相聯，主存塊大小為 64B，cache 命中時間為 2 個時鐘周期，缺失損失為 200 個時鐘周期，采用頁式虛擬存儲，頁大小為 4KB。數組 d 的起始地址為 0180 0020H(VA31~VA0)

(1) 主存地址中的 Cache 組號，塊內地址分別占幾位？VA 中哪些位可以作為 Cache 索引。

(2) d[100] 的 VA 是多少？d[100]所在主存塊中對應的 Cache 組號是多少？

(3) 設代碼已經在 cache 中，i,x 已裝入內存，但不在 cache，則 d[0]在其主存塊內的偏移量是多少？執行 for 的過程中，訪問 d 的 Cache 缺失率和數組元素的平均訪問時間分別是多少？（缺失率用百分比表示，保留兩位小數）

(4) d 分布在幾個頁中？若代碼已在主存，d 不在主存，則執行 for 的過程中，訪問 d 所引起的缺頁次數是？

int x, d[2048], i;
for (i = 0; i < 2048; i++)d[i] = d[i]/x;

44

接上題，R0~R4 為通用寄存器，SEXT 表示按符號擴展，M 中補碼除法器，邏輯結構圖如下：

在這里插入圖片描述

機器級代碼：

// x 在 R2 中，i 在 R4 中
// 數組 d 的首地址在 R3 中
mov R1,(R3+R4*4) // R1 ← d[i]
scov R1          // {R0,R1} ← SEXT(R1)
idiv R1          // R1<-({R0,R1}/R2)

(1) 若執行 idiv 指令時，d[i]=0x87654321，x=0xff，則補碼除法器中 R、Q、Y 的初始值分別為多少（用十六進制表示）？圖 b 中哪個部分包含計數器？在補碼除法器執行過程中，ALUop 所控制的 ALU 運算有哪幾種？

(2) 假設 idiv 執行過程中會檢測并觸發除法異常，則執行 idiv 指令時，哪些情況下會發生除法異常（要求給出此時 d[i] 和 x 的十六進制機器數）。發生除法異常時，在異常響應過程中，CPU 需要完成哪些操作？

45

三個人一起植樹，甲挖坑，乙放樹苗入坑并填土，丙負責為新種樹苗澆水。步驟依次為：挖樹坑，放樹苗，填土和澆水。現在有鐵鍬和水桶各一個，鐵鍬用于挖樹坑，填土。水桶用于澆水。當樹坑數量小于 3 時，甲才可以挖樹坑。設初始坑 = 0，鐵鍬水桶均可用，定義盡可能少的信號量，用 wait() 和 signal() 操作描述植樹過程中三人的同步互斥關系，并說明所用信號量的作用及其初值。

46

某進程的虛擬地址空間如圖，陰影部分為未占用區域，有 C 程序：

char * ptr;
void main() {int length;ptr=(char*) malloc(100);scanf("%s", ptr);length = strlen(ptr);printf("length=%d\n", length);free(ptr) ;
}

(1) 上述程序執行時，PCB 位于哪個區域，執行 scanf ()等待鍵盤輸入時，該進程處于什么狀態？

(2) main() 函數的代碼位于哪個區域？其直接調用的哪些函數的功能需要通過執行驅動程序實現？

(3) 變量 ptr 被分配在哪個區域？若變量 length 沒有被分配在寄存器中，則會被分配在哪個區域？ptr 指向的字符串位于哪個區域？

47

軌道高度 36000km，電磁波速度 300000 km/s

在這里插入圖片描述

TR1 和 TR2 為全雙工調制解調設備，

衛星鏈路為 R1, R2 之間提供對稱全雙工信號，每個方向數據傳輸率為 200kbps

(1) 忽略衛星信號中繼，TR1，TR2 調制解調開銷，則 R1 到 R2 之間的衛星鏈路單向傳播時延是多少？主機 H 向總部服務器傳輸數據時可達到的最大吞吐量是多少？若忽略各層協議首部開銷，以及以太網的傳播時延，則 H → server 上傳一個 4000B 的文件，至少需要多長時間？

(2) 基于 GBN 為衛星鏈路設計單向可靠的鏈路層協議 SLP，支持 R1 → R2 發送數據。SLP 數據幀長 1500B，忽略 ACK 幀長度，要求 SLP 單向信道利用率不低于 80%，則發送窗口至少為？SLP 幀序號至少為多少？

(3) 總部給工程部分配 IP 地址空間 10.10.10.0/24，再劃分為 3 個子網，生活區子網不少于 120 個，作業子網，管理區子網 IP 均不少于 60 個，H 已正確配置 IP。問作，管，生子網地址各是多少？