2022年408計算機學科專業基礎真題
摘要：在研究生考試的備考過程中，部分同學可能會存在這樣的問題，比如：往年的真題是怎樣的？別擔心，為了幫大家解決疑這些問題，小編收集資料并整理了相關的內容，一起來了解下吧~
一、單項選擇題（第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求）
1、下列程序段的時間復雜度是（ ）。
int sum=0;
for(int i=1;i<n;i*=2)
for(int j=0;j<i;j++)
sum++;
A.O(logn)
B.O(n）
C.O(nlogn)
D.O(n2)
2、給定有限符號集S、in和out均為S中所有元素的任意排列，對于初始為空的棧ST，下列敘述中，正確的是（ ）。
A.若in是ST的入棧序列，則不能判斷out是否為其可能的出棧序列。
B.若out是ST的出棧序列，則不能判斷in是否為其可能的入棧序列。
C.若in是ST的入棧序列，out是對應in的出棧序列，則in與out一定不同。
D.若in是ST的入棧序列，out是對應in的出棧序列，則in與out可能互為倒序。
3、若結點p與q在二叉樹T的中序遍歷序列中相鄰，且p在q之前，則下列p與q的關系中，不可能的是（ ）。
I.q是p的雙親
II.q是p的右孩子
III.q是p的右兄弟
IV.q是p的雙親的雙親
A.僅I
B.僅III
C.僅II、III
D.僅II、IV
4、若三叉樹T中有244個結點（葉結點的高度為1），則T的高度至少是（ ）。
A.8
B.7
C.6
D.5
5、對任意給定的含n(n>2)個字符的有限集S，用二叉樹表示S的哈夫曼編碼集和定長編碼集，分別得到二叉樹T1和T2。下列敘述中，正確的是（ ）。
A.T1與T2的結點數相同
B.T1的高度大于T2的高度
C.出現頻次不同的字符在T1中處于不同的層
D.出現頻次不同的字符在T2中處于相同的層
6、對于無向圖G=(V，E)，下列選項中，正確的是（ ）。
A.當|V|>|E|時，G一定是連通的
B.當|V|<|E|時，G一定是連通的
C.當|V|=|E|-1時，G一定是不連通的
D.當|V|>|E|+1時，G一定是不連通的
7、下圖是一個有10個活動的AOE網，時間余量最大的活動是（ ）。
A.c
B.g
C.h
D.j
8、在下圖所示的5階B樹T中，刪除關鍵字260之后需要進行必要的調整，得到新的B樹T1。下列選項中，不可能是T1根結點中關鍵字序列的是（ ）。
A.60，90，280
B.60，90，350
C.60，85，110，350
D.60，90，110，350
9、下列因素中，影響散列（哈希）方法平均查找長度是（ ）。
I裝填因子
II散列函數
III沖突解決策略
A.僅I、II
B.僅I、III
C.僅II、III
D.I、II、III
10、使用二路歸并排序對含n個元素的數組M進行排序時，二路歸并操作的功能是（ ）。
A.將兩個有序表合并為一個新的有序表
B.將M劃分為兩部分，兩部分的元素個數大致相等
C.將M劃分為n個部分，每個部分中僅含有一個元素
D.將M劃分為兩部分，一部分元素的值均小于另一部分元素的值
11、對數據進行排序時，若采用直接插入排序而不采用快速排序，則可能的原因是（ ）。
I.大部分元素已有序
II.待排序元素數量很少
III.要求空間復雜度為O(1)
IV.要求排序算法是穩定的
A.僅I、II
B.僅III、IV
C.僅I、II、IV
D.I、II、III、IV
12、某計算機主頻為1GHz，程序P運行過程中，共執行了10000條指令，其中，80%的指令執行平均需1個時鐘周期，20%的指令執行平均需10個時鐘周期。程序P的平均CPI和CPU執行時間分別是（ ）。
A.2.8，28us
B.28，28us
C.2.8，28ms
D.28，28ms
13、32位補碼所能表示的整數范圍是（ ）。
A.-232~231-1
B.-231~231-1
C.-232~232-1
D.-231~232-1
14、-0.4375的IEEE754單精度浮點數表示為（ ）。
A.BEE0 0000H
B.BF60 0000H
C.BF70 0000H
D.C0E0 0000H
15、某計算機主存地址為24位，采用分頁虛擬存儲管理方式，虛擬地址空間大小為4GB，頁大小為4KB，按字節編址。某進程的頁表部分內容如下表所示。當CPU訪問虛擬地址00082840H，虛-實地址轉換的結果是（ ）。
虛頁號 | 實頁號（頁框號） | 存放位 |
82 | 024H | 0 |
... | ... | ... |
129 | 180H | 1 |
130 | 018H | 1 |
A.得到主存地址02 4840H
B.得到主存地址18 0840H
C.得到主存地址01 8840H
D.檢測到缺頁異常
16、某計算機主存地址為32位，按字節變化，某Cache的數據區容量為32KB，主存塊大小為64B，采用8路組相聯映射方式，該Cache中比較器的個數和位數分別為（ ）。
A.8，20
B.8，23
C.64，20
D.64，23
17、某內存條包含8個8192×8192×8位的DRAM芯片，按字節編址，支持突發傳送方式，對應存儲器總線寬度為64位，每個DRAM芯片內有一個行緩沖區。下列關于該內存條的敘述中，不正確的是（ ）。
A.內存條的容量為512MB
B.采用多模塊交叉編址方式
C.芯片的地址引腳為26位
D.芯片內行緩沖有8192×8位
18、下列選項中，屬于指令集體系結構（ISA）規定的內容是（ ）。
Ⅰ.指令字格式和指令類型
Ⅱ.CPU的時鐘周期
Ⅲ.通用寄存器個數和位數
Ⅳ.加法器的進位方式
A.僅Ⅰ、Ⅱ
B.僅Ⅰ、Ⅲ
C.僅Ⅱ、Ⅳ
D.僅Ⅰ、Ⅲ、Ⅳ
19、設計某指令系統時，假設采用16位定長指令字格式，操作碼使用擴展編碼方式，地址碼為6位，包含零地址、一地址和二地址3種格式的指令。若二地址指令有12條，一地址指令有254條，則零地址指令的條數最多為（ ）。
A.0
B.2
C.64
D.128
20、將高級語言源程序轉換為可執行目標文件的主要過程是（ ）。
A.預處理→編譯→匯編→鏈接
B.預處理→匯編→編譯→鏈接
C.預處理→編譯→鏈接→匯編
D.預處理→匯編→鏈接→編譯
21、下列關于中斷I/O方式的敘述中，不正確的是（ ）。
A.適用于鍵盤、針式打印機等字符型設備
B.外設和主機之間的數據傳送通過軟件完成
C.外設準備數據的時間應小于中斷處理時間
D.外設為某進程準備數據時CPU可運行其他進程
22、下列關于并行處理技術的敘述中，不正確的是（ ）。
A.多核處理器屬于MIMD結構
B.向量處理器屬于SIMD結構
C.硬件多線程技術只可用于多核處理器
D.SMP中所有處理器共享單一物理地址空間
23、下列關于多道程序系統的敘述中，不正確的是（ ）。
A.支持進程的并發執行
B.不必支持虛擬存儲管理
C.需要實現對共享資源的管理
D.進程數越多CPU利用率越高
24、下列選項中，需要在操作系統進行初始化過程中創建的是（ ）。
A.中斷向量表
B.文件系統的根目錄
C.硬盤分區表
D.文件系統的索引節點表
25、進程P0、P1、P2和P3進入就緒隊列的時刻、優先級（值越小優先權越高）及CPU執行時間如下表所示。
進程 | 進入就緒隊列的時刻 | 優先級 | CPU執行時間 |
P0 | 0ms | 15 | 100ms |
P1 | 10ms | 20 | 60ms |
P2 | 10ms | 10 | 20ms |
P3 | 15ms | 6 | 10ms |
若系統采用基于優先權的搶占式進程調度算法，則從0ms時刻開始調度，到4個進程都運行結束為止，發生進程調度的總次數為（ ）。
A.4
B.5
C.6
D.7
26、系統中有三個進程P0、P1、P2及三類資源A、B、C。若某時刻系統分配資源的情況如下表所示，則此時系統中存在的安全序列的個數為（ ）。
進程 | 已分配資源數 | 尚需資源數 | 可用資源數 | ||||||
A | B | C | A | B | C | A | B | C | |
P0 | 2 | 0 | 1 | 0 | 2 | 1 | 1 | 3 | 2 |
P1 | 0 | 2 | 0 | 1 | 2 | 3 | |||
P2 | 1 | 0 | 1 | 0 | 1 | 3 | |||
A.1
B.2
C.3
D.4
27、下列關于CPU模式的敘述中，正確的是（ ）。
A.CPU處于用戶態時只能執行特權指令
B.CPU處于內核態時只能執行特權指令
C.CPU處于用戶態時只能執行非特權指令
D.CPU處于內核態時只能執行非特權指令
28、下列事件或操作中，可能導致進程P由執行態變為阻塞態的是（ ）。
Ⅰ.進程P讀文件
Ⅱ.進程P的時間片用完
Ⅲ.進程P申請外設
Ⅳ.進程P執行信號量的wait()操作
A.僅Ⅰ、Ⅳ
B.僅Ⅱ、Ⅲ
C.僅Ⅲ、Ⅳ
D.僅Ⅰ、Ⅲ、Ⅳ
29、某進程訪問的頁b不在內存中，導致產生缺頁異常，該缺頁異常處理過程中不一定包含的操作是（ ）。
A.淘汰內存中的頁
B.建立頁號與頁框號的對應關系
C.將頁b從外存讀入內存
D.修改頁表中頁b對應的存在位
30、下列選項中，不會影響系統缺頁率的是（ ）。
A.頁面置換算法
B.工作集的大小
C.進程的數量
D.頁緩沖隊列的長度
31、執行系統調用的過程涉及下列操作，其中由操作系統完成的是（ ）。
Ⅰ.保存斷點和程序狀態字
Ⅱ.保存通用寄存器的內容
Ⅲ.執行系統調用服務程序
Ⅳ.將CPU模式改為內核態
A.僅Ⅰ、Ⅲ
B.僅Ⅱ、Ⅲ
C.僅Ⅱ、Ⅳ
D.僅Ⅱ、Ⅲ、Ⅳ
32、下列關于驅動程序的敘述中，不正確的是（ ）。
A.驅動程序與I/O控制方式無關
B.初始化設備是由驅動程序控制完成的
C.進程在執行驅動程序時可能進入阻塞態
D.讀/寫設備的操作是由驅動程序控制完成的
33、在ISO/OS參考模型中，實現兩個相鄰結點間流量控制功能的是（ ）。
A.物理層
B.數據鏈路層
C.網絡層
D.傳輸層
34、在一條帶寬為200kHz的無噪音信道上，若采用4個幅值的ASK調制，則該信道的最大數據傳輸速率是（ ）。
A.200kh/s
B.400kh/s
C.800kb/s
D.1600kb/s
35、若某主機的IP地址是183.80.72.48，子網掩碼是255.255.192.0，則該主機所在網絡的網絡地址是（ ）。
A.183.80.0.0
B.183.80.64.0
C.183.80.72.0
D.183.80.192.0
36、下圖所示網絡中的主機H的子網掩碼與默認網關分別是（ ）。
A.255.255.255.192，192.168.1.1
B.255.255.255.192，192.168.1.62
C.255.255.255.224，192.168.1.1
D.255.255.255.224，192.168.1.62
37、在SDN網絡體系結構中，SDN控制器向數據平面的SDN交換機下發流表時所使用的接口是（ ）。
A.東向接口
B.南向接口
C.西向接口
D.北向接口
38、假設主機甲和主機乙已建立一個TCP連接，最大段長MSS=1KB，甲一直有數據向乙發送，當甲的擁塞窗口為16KB時，計時器發生了超時，則甲的擁塞窗口再次增長到16KB所需要的時間至少是（ ）。
A.4RTT
B.5RTT
C.11RTT
D.16RTT
39、假設客戶C和服務器S已建立一個TCP連接、通信往返時間RTT=50ms，最長報文段壽命MSL=800ms，數據傳輸結束后，C主動諸求斷開連接。若從C主動向S發出FIN段時刻算起，則C和S進入CLOSED狀態所需的時間至少分別是（ ）。
A.850ms，50ms
C.850rns，75ms
B.1650ms，50ms
D.1650ms，75ms
40、根設主機H通過HTTP/1.1請求瀏覽某Web服務器S上的Web頁news408.html，news408.html引用了同目錄下1個圖像，news408.html文件大小為1MSS（最大段長），圖像文件大小為3MSS，H訪問S的往返時間RTT=10ms，忽略HTTP響應報文的首部開銷和TCP段傳輸時延。若H已完成域名解析，則從H請求與S建立TCP連接時刻起，到接收到全部內容止，所需的時間至少是（ ）。
A.30ms
B.40ms
C.50ms
D.60ms
二、綜合應用題（第41~47小題，共70分）
41、（13分）已知非空二叉樹T的結點值均為正整數，采用順序存儲方式保存，數據結構定義如下：typedef struct{//MAX_SIZE為已定義常量
int SqBiTNode[MAX_SIZE];//保存二叉樹節點值的數值
int ElemNum;//實際占用的數組元素個數
}SqBiTree;
T中不存在的結點在數組SqBiNode中用-1表示。例如，對于下圖所示的兩棵非空二叉樹T1和T2，
T1的存儲結果如下：
40 | 25 | 60 | -1 | 30 | -1 | 80 | -1 | -1 | 27 |
T1.SqBiTNode
T1.ElemNum=10
T2的存儲結果如下：
T2.SqBiTNode
40 | 50 | 60 | -1 | 30 | -1 | -1 | -1 | -1 | -1 | 35 |
T2.ElemNum=11
請設計一個盡可能高效的算法，判定一棵采用這種方式存儲的二叉樹是否為二叉搜索樹，若是，則返回true，否則，返回false。要求：
（1）給出算法的基本設計思想。
（2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。
42、（10分）現有n(n>100000)個數保存在一維數組M中，需要在找M中最小的10個數。請回答下列問題。
（1）設計一個完成上述查找任務的算法，要求平均情況下的比較次數盡可能少，簡述其算法思想（不要程序實現）。
（2）說明你所設計的算法平均情況下的時間復雜度和空間復雜度。
43、（15分）某CPU中部分數據通路如圖所示，其中，GPRs為通用寄存器組；FR為標志寄存器，用于存放ALU產生的標志信息；帶箭頭虛線表示控制信號，如控制信號Read、Write分別表示主存讀、主存寫，MDRin表示內部總線上數據寫入MDR，MDRout表示MDR的內容送內部總線。
（1）ALU的輸入端A、B及輸出端F的最高位分別為A15、B15及F15，FR中的符號標志和溢出標志分別為SF和OF，則SF的邏輯表達式是什么？A加B、A減B時OF的邏輯表達式分別是什么？要求邏輯表達式的輸入變量為A15、B15及F15。
（2）為什么要設置暫存器Y和Z？
（3）若GPRs的輸入端rs、rd分別為所讀、寫的通用寄存器的編號，則GPRs中最多有多少個通用寄存器？rs和rd來自圖中的哪個寄存器？已知GPRs內部有一個地址譯碼器和一個多路選擇器，rd應該連接地址譯碼器還是多路選擇器？
（4）取指令階段（不考慮PC增量操作）的控制信號序列是什么？若從發出主存讀命令到主存讀出數據并傳送到MDR共需5個時鐘周期，則取指令階段至少需要幾個時鐘周期？
（5）圖中控制信號由什么部件產生？圖中哪些寄存器的輸出信號會連到該部件的輸入端？
44、假設某磁盤驅動器中有4個雙面盤片，每個盤面有20000個磁道，每個磁道有500個扇區，每個扇區可記錄512字節的數據，盤片轉速為7200r/m(轉/分)，平均尋道時間為5ms，請回答下列問題。
（1）每個扇區包含數據及地址信息，地址信息分為3個字段，這3個字段的名稱格式什么？對于該磁盤，各字段至少占多少位？
（2）一個扇區的平均訪問時間約為多少？
（3）若采用周期挪用DMA方式進行磁盤與主機之間的數據傳送，磁盤控制器中的數據緩沖區大小為64位，則在一個扇區讀寫過程中，DMA控制器向CPU發送了多少次總線請求？若CPU檢測到DMA控制器的總線請求信號時也需要訪問主存，則DMA控制器是否可以獲得總線使用權？為什么？
45、（7分）某文件系統的磁盤大小為4KB，目錄項由文件名和索引節點號構成，每個索引節點占256字節，其中包含直接地址項10個，一級、二級和三級間接地址項各1個，每個地址項占4字節。該文件系統中子目錄stu的結構如題45(a)圖所示，stu包含子目錄course和文件doc，course子目錄包含文件course1和course2。各文件的文件名、索引節點號、占用磁盤塊的塊號如題45(b)圖所示。
請回答下列問題。
（1）目錄文件stu中每個目錄項的內容是什么？
（2）文件doc占用的磁盤塊的塊號x的值是多少？
（3）若目錄文件course的內容已在內存，則打開文件course1并將其讀入內存，需要讀幾個磁盤塊？說明理由。
（4）若文件course2的大小增長到6MB，為了存取course2需要使用該文件索引節點的哪幾級間接地址項？說明理由。
46、（8分）某進程的兩個線程T1和T2并發執行A、B、C、D、E和F共6個操作，其中T1執行A、E和F，T2執行B、C和D。題46圖表示上述6個操作的執行順序所必須滿足的約束：C在A和B完成后執行，D和E在C完成后執行，F在E完成后執行。請使用信號量的wait()、signal()操作描述T1和T2之間的同步關系，并說明所用信號量的作用及其初值。
47、(9分）某網絡拓撲如題47圖所示，R為路由器，S為以太網交換機，AP是802.11接入點，路由器的EO接口和DHCP服務器的IP地址配置如圖中所示：H1與H2屬于同一個廣播域，但不屬于同一個沖突域：12和H3屬于同一個沖突域：H4和H5已經接入網絡，并通過DHCP動態獲取了IP地址?，F有路由器、100BaseT以太網交換機和100BaseT集線器(Hub）三類設備各若干臺。
請回答下列問題。
（1）設備1和設備2應該分別選擇哪類設備？
（2）若信號傳播速度為2×108m/s，以太網最小幀長為64B。信號通過設備2時會產生額外的1.51μs的時間延遲，則H2與H3之間可以相距的最遠距離是多少？
（3）在H4通DHCP動態獲取IP地址過程中，H4首先發送了DHCP報文M，M是哪種DHCP報文？路由器EO接口能否收到封裝M的以太網幀？s向DHCP服務器轉發的封裝M的以太網幀的目的MAC地址是什么？
（4）若H4向HS發送一個IP分組P，則HS收到的封裝P的802.11幀的地址1、地址2和地址3分別是什么？
相關推薦：
| 課程名稱 | 課程價格 | 課程鏈接 |
2026寫作備考攻略 | 免費 | 點擊試聽 |
| 2010-2025數學16套真題講解 | 免費 | 點擊試聽 |
| 考研【公共課】自學視頻教程 | 98元 | 點擊試聽 |
| 408計算機】考研自學視頻教程（真題+習題+考點） | 98元 | 點擊查看 |
| 管理類聯考數學基本功視頻教程 | 398元 | 點擊查看 |
掃碼直達>>>考研課程咨詢
| ||
溫馨提示：因考試政策、內容不斷變化與調整，本網站提供的以上信息僅供參考，如有異議，請考生以權威部門公布的內容為準！
延伸閱讀
- ?工科三大王牌專業是什么？就業方向有哪些？
- 湖北考研最容易的學校有哪些？熱門專業易考院校匯總
- 女孩專業選電子信息工程、計算機、機器人、還是自動化？
- 電氣工程學碩考研難度排名？易上岸院校有哪些？
- 歷年考研國家分數線匯總（更新至2025年）
- 2025考研國家分數線正式發布
更多精彩內容請關注
考研微信公眾號
考研微信公眾號
考研備考資料免費領取
去領取
距離考試還有
天
- 1
- 0
- 8
專注在線職業教育24年
APP 
微信群 
掃描二維碼
掃描二維碼
