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

一、單項選擇題（第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是對應(yīng)in的出棧序列，則in與out一定不同。

D.若in是ST的入棧序列，out是對應(yīng)in的出棧序列，則in與out可能互為倒序。

3、若結(jié)點p與q在二叉樹T的中序遍歷序列中相鄰，且p在q之前，則下列p與q的關(guān)系中，不可能的是（  ）。

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個結(jié)點（葉結(jié)點的高度為1），則T的高度至少是（  ）。

A.8

B.7

C.6

D.5

5、對任意給定的含n(n>2)個字符的有限集S，用二叉樹表示S的哈夫曼編碼集和定長編碼集，分別得到二叉樹T1和T2。下列敘述中，正確的是（  ）。

A.T1與T2的結(jié)點數(shù)相同

B.T1的高度大于T2的高度

C.出現(xiàn)頻次不同的字符在T1中處于不同的層

D.出現(xiàn)頻次不同的字符在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網(wǎng)，時間余量最大的活動是（  ）。

A.c

B.g

C.h

D.j

8、在下圖所示的5階B樹T中，刪除關(guān)鍵字260之后需要進行必要的調(diào)整，得到新的B樹T1。下列選項中，不可能是T1根結(jié)點中關(guān)鍵字序列的是（  ）。

A.60，90，280

B.60，90，350

C.60，85，110，350

D.60，90，110，350

9、下列因素中，影響散列（哈希）方法平均查找長度是（  ）。

I裝填因子

II散列函數(shù)

III沖突解決策略

A.僅I、II

B.僅I、III

C.僅II、III

D.I、II、III

10、使用二路歸并排序?qū)琻個元素的數(shù)組M進行排序時，二路歸并操作的功能是（  ）。

A.將兩個有序表合并為一個新的有序表

B.將M劃分為兩部分，兩部分的元素個數(shù)大致相等

C.將M劃分為n個部分，每個部分中僅含有一個元素

D.將M劃分為兩部分，一部分元素的值均小于另一部分元素的值

11、對數(shù)據(jù)進行排序時，若采用直接插入排序而不采用快速排序，則可能的原因是（  ）。

I.大部分元素已有序

II.待排序元素數(shù)量很少

III.要求空間復雜度為O(1)

IV.要求排序算法是穩(wěn)定的

A.僅I、II

B.僅III、IV

C.僅I、II、IV

D.I、II、III、IV

12、某計算機主頻為1GHz，程序P運行過程中，共執(zhí)行了10000條指令，其中，80%的指令執(zhí)行平均需1個時鐘周期，20%的指令執(zhí)行平均需10個時鐘周期。程序P的平均CPI和CPU執(zhí)行時間分別是（  ）。

A.2.8，28us

B.28，28us

C.2.8，28ms

D.28，28ms

13、32位補碼所能表示的整數(shù)范圍是（  ）。

A.-232~231-1

B.-231~231-1

C.-232~232-1

D.-231~232-1

14、-0.4375的IEEE754單精度浮點數(shù)表示為（  ）。

A.BEE0 0000H

B.BF60 0000H

C.BF70 0000H

D.C0E0 0000H

15、某計算機主存地址為24位，采用分頁虛擬存儲管理方式，虛擬地址空間大小為4GB，頁大小為4KB，按字節(jié)編址。某進程的頁表部分內(nèi)容如下表所示。當CPU訪問虛擬地址00082840H，虛-實地址轉(zhuǎn)換的結(jié)果是（  ）。

A.得到主存地址02 4840H

B.得到主存地址18 0840H

C.得到主存地址01 8840H

D.檢測到缺頁異常

16、某計算機主存地址為32位，按字節(jié)變化，某Cache的數(shù)據(jù)區(qū)容量為32KB，主存塊大小為64B，采用8路組相聯(lián)映射方式，該Cache中比較器的個數(shù)和位數(shù)分別為（  ）。

A.8，20

B.8，23

C.64，20

D.64，23

17、某內(nèi)存條包含8個8192×8192×8位的DRAM芯片，按字節(jié)編址，支持突發(fā)傳送方式，對應(yīng)存儲器總線寬度為64位，每個DRAM芯片內(nèi)有一個行緩沖區(qū)。下列關(guān)于該內(nèi)存條的敘述中，不正確的是（  ）。

A.內(nèi)存條的容量為512MB

B.采用多模塊交叉編址方式

C.芯片的地址引腳為26位

D.芯片內(nèi)行緩沖有8192×8位

18、下列選項中，屬于指令集體系結(jié)構(gòu)（ISA）規(guī)定的內(nèi)容是（  ）。

Ⅰ.指令字格式和指令類型

Ⅱ.CPU的時鐘周期

Ⅲ.通用寄存器個數(shù)和位數(shù)

Ⅳ.加法器的進位方式

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅳ

D.僅Ⅰ、Ⅲ、Ⅳ

19、設(shè)計某指令系統(tǒng)時，假設(shè)采用16位定長指令字格式，操作碼使用擴展編碼方式，地址碼為6位，包含零地址、一地址和二地址3種格式的指令。若二地址指令有12條，一地址指令有254條，則零地址指令的條數(shù)最多為（  ）。

A.0

B.2

C.64

D.128

20、將高級語言源程序轉(zhuǎn)換為可執(zhí)行目標文件的主要過程是（  ）。

A.預處理→編譯→匯編→鏈接

B.預處理→匯編→編譯→鏈接

C.預處理→編譯→鏈接→匯編

D.預處理→匯編→鏈接→編譯

21、下列關(guān)于中斷I/O方式的敘述中，不正確的是（  ）。

A.適用于鍵盤、針式打印機等字符型設(shè)備

B.外設(shè)和主機之間的數(shù)據(jù)傳送通過軟件完成

C.外設(shè)準備數(shù)據(jù)的時間應(yīng)小于中斷處理時間

D.外設(shè)為某進程準備數(shù)據(jù)時CPU可運行其他進程

22、下列關(guān)于并行處理技術(shù)的敘述中，不正確的是（  ）。

A.多核處理器屬于MIMD結(jié)構(gòu)

B.向量處理器屬于SIMD結(jié)構(gòu)

C.硬件多線程技術(shù)只可用于多核處理器

D.SMP中所有處理器共享單一物理地址空間

23、下列關(guān)于多道程序系統(tǒng)的敘述中，不正確的是（  ）。

A.支持進程的并發(fā)執(zhí)行

B.不必支持虛擬存儲管理

C.需要實現(xiàn)對共享資源的管理

D.進程數(shù)越多CPU利用率越高

24、下列選項中，需要在操作系統(tǒng)進行初始化過程中創(chuàng)建的是（  ）。

A.中斷向量表

B.文件系統(tǒng)的根目錄

C.硬盤分區(qū)表

D.文件系統(tǒng)的索引節(jié)點表

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

若系統(tǒng)采用基于優(yōu)先權(quán)的搶占式進程調(diào)度算法，則從0ms時刻開始調(diào)度，到4個進程都運行結(jié)束為止，發(fā)生進程調(diào)度的總次數(shù)為（  ）。

A.4

B.5

C.6

D.7 

26、系統(tǒng)中有三個進程P0、P1、P2及三類資源A、B、C。若某時刻系統(tǒng)分配資源的情況如下表所示，則此時系統(tǒng)中存在的安全序列的個數(shù)為（  ）。

A.1

B.2

C.3

D.4

27、下列關(guān)于CPU模式的敘述中，正確的是（  ）。

A.CPU處于用戶態(tài)時只能執(zhí)行特權(quán)指令

B.CPU處于內(nèi)核態(tài)時只能執(zhí)行特權(quán)指令

C.CPU處于用戶態(tài)時只能執(zhí)行非特權(quán)指令

D.CPU處于內(nèi)核態(tài)時只能執(zhí)行非特權(quán)指令

28、下列事件或操作中，可能導致進程P由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)的是（  ）。

Ⅰ.進程P讀文件

Ⅱ.進程P的時間片用完

Ⅲ.進程P申請外設(shè)

Ⅳ.進程P執(zhí)行信號量的wait()操作

A.僅Ⅰ、Ⅳ

B.僅Ⅱ、Ⅲ

C.僅Ⅲ、Ⅳ

D.僅Ⅰ、Ⅲ、Ⅳ

29、某進程訪問的頁b不在內(nèi)存中，導致產(chǎn)生缺頁異常，該缺頁異常處理過程中不一定包含的操作是（  ）。

A.淘汰內(nèi)存中的頁

B.建立頁號與頁框號的對應(yīng)關(guān)系

C.將頁b從外存讀入內(nèi)存

D.修改頁表中頁b對應(yīng)的存在位

30、下列選項中，不會影響系統(tǒng)缺頁率的是（  ）。

A.頁面置換算法

B.工作集的大小

C.進程的數(shù)量

D.頁緩沖隊列的長度

31、執(zhí)行系統(tǒng)調(diào)用的過程涉及下列操作，其中由操作系統(tǒng)完成的是（  ）。

Ⅰ.保存斷點和程序狀態(tài)字

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

Ⅲ.執(zhí)行系統(tǒng)調(diào)用服務(wù)程序

Ⅳ.將CPU模式改為內(nèi)核態(tài)

A.僅Ⅰ、Ⅲ

B.僅Ⅱ、Ⅲ

C.僅Ⅱ、Ⅳ

D.僅Ⅱ、Ⅲ、Ⅳ

32、下列關(guān)于驅(qū)動程序的敘述中，不正確的是（  ）。

A.驅(qū)動程序與I/O控制方式無關(guān)

B.初始化設(shè)備是由驅(qū)動程序控制完成的

C.進程在執(zhí)行驅(qū)動程序時可能進入阻塞態(tài)

D.讀/寫設(shè)備的操作是由驅(qū)動程序控制完成的

33、在ISO/OS參考模型中，實現(xiàn)兩個相鄰結(jié)點間流量控制功能的是（  ）。

A.物理層

B.數(shù)據(jù)鏈路層

C.網(wǎng)絡(luò)層

D.傳輸層

34、在一條帶寬為200kHz的無噪音信道上，若采用4個幅值的ASK調(diào)制，則該信道的最大數(shù)據(jù)傳輸速率是（  ）。

A.200kh/s

B.400kh/s

C.800kb/s

D.1600kb/s

35、若某主機的IP地址是183.80.72.48，子網(wǎng)掩碼是255.255.192.0，則該主機所在網(wǎng)絡(luò)的網(wǎng)絡(luò)地址是（  ）。

A.183.80.0.0

B.183.80.64.0

C.183.80.72.0

D.183.80.192.0

36、下圖所示網(wǎng)絡(luò)中的主機H的子網(wǎng)掩碼與默認網(wǎng)關(guān)分別是（  ）。

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網(wǎng)絡(luò)體系結(jié)構(gòu)中，SDN控制器向數(shù)據(jù)平面的SDN交換機下發(fā)流表時所使用的接口是（  ）。

A.東向接口

B.南向接口

C.西向接口

D.北向接口

38、假設(shè)主機甲和主機乙已建立一個TCP連接，最大段長MSS=1KB，甲一直有數(shù)據(jù)向乙發(fā)送，當甲的擁塞窗口為16KB時，計時器發(fā)生了超時，則甲的擁塞窗口再次增長到16KB所需要的時間至少是（  ）。

A.4RTT

B.5RTT

C.11RTT

D.16RTT

39、假設(shè)客戶C和服務(wù)器S已建立一個TCP連接、通信往返時間RTT=50ms，最長報文段壽命MSL=800ms，數(shù)據(jù)傳輸結(jié)束后，C主動諸求斷開連接。若從C主動向S發(fā)出FIN段時刻算起，則C和S進入CLOSED狀態(tài)所需的時間至少分別是（  ）。

A.850ms，50ms

C.850rns，75ms

B.1650ms，50ms

D.1650ms，75ms

40、根設(shè)主機H通過HTTP/1.1請求瀏覽某Web服務(wù)器S上的Web頁news408.html，news408.html引用了同目錄下1個圖像，news408.html文件大小為1MSS（最大段長），圖像文件大小為3MSS，H訪問S的往返時間RTT=10ms，忽略HTTP響應(yīng)報文的首部開銷和TCP段傳輸時延。若H已完成域名解析，則從H請求與S建立TCP連接時刻起，到接收到全部內(nèi)容止，所需的時間至少是（  ）。

A.30ms

B.40ms

C.50ms

D.60ms

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

41、（13分）已知非空二叉樹T的結(jié)點值均為正整數(shù)，采用順序存儲方式保存，數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct{//MAX_SIZE為已定義常量

int SqBiTNode[MAX_SIZE];//保存二叉樹節(jié)點值的數(shù)值

int ElemNum;//實際占用的數(shù)組元素個數(shù)

}SqBiTree;

T中不存在的結(jié)點在數(shù)組SqBiNode中用-1表示。例如，對于下圖所示的兩棵非空二叉樹T1和T2， 

T1的存儲結(jié)果如下：

T1.SqBiTNode

T1.ElemNum=10

T2的存儲結(jié)果如下：

T2.SqBiTNode

T2.ElemNum=11

請設(shè)計一個盡可能高效的算法，判定一棵采用這種方式存儲的二叉樹是否為二叉搜索樹，若是，則返回true，否則，返回false。要求：

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

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

42、（10分）現(xiàn)有n(n>100000)個數(shù)保存在一維數(shù)組M中，需要在找M中最小的10個數(shù)。請回答下列問題。

（1）設(shè)計一個完成上述查找任務(wù)的算法，要求平均情況下的比較次數(shù)盡可能少，簡述其算法思想（不要程序?qū)崿F(xiàn)）。

（2）說明你所設(shè)計的算法平均情況下的時間復雜度和空間復雜度。

43、（15分）某CPU中部分數(shù)據(jù)通路如圖所示，其中，GPRs為通用寄存器組；FR為標志寄存器，用于存放ALU產(chǎn)生的標志信息；帶箭頭虛線表示控制信號，如控制信號Read、Write分別表示主存讀、主存寫，MDRin表示內(nèi)部總線上數(shù)據(jù)寫入MDR，MDRout表示MDR的內(nèi)容送內(nèi)部總線。

（1）ALU的輸入端A、B及輸出端F的最高位分別為A15、B15及F15，F(xiàn)R中的符號標志和溢出標志分別為SF和OF，則SF的邏輯表達式是什么？A加B、A減B時OF的邏輯表達式分別是什么？要求邏輯表達式的輸入變量為A15、B15及F15。

（2）為什么要設(shè)置暫存器Y和Z？

（3）若GPRs的輸入端rs、rd分別為所讀、寫的通用寄存器的編號，則GPRs中最多有多少個通用寄存器？rs和rd來自圖中的哪個寄存器？已知GPRs內(nèi)部有一個地址譯碼器和一個多路選擇器，rd應(yīng)該連接地址譯碼器還是多路選擇器？

（4）取指令階段（不考慮PC增量操作）的控制信號序列是什么？若從發(fā)出主存讀命令到主存讀出數(shù)據(jù)并傳送到MDR共需5個時鐘周期，則取指令階段至少需要幾個時鐘周期？

（5）圖中控制信號由什么部件產(chǎn)生？圖中哪些寄存器的輸出信號會連到該部件的輸入端？

44、假設(shè)某磁盤驅(qū)動器中有4個雙面盤片，每個盤面有20000個磁道，每個磁道有500個扇區(qū)，每個扇區(qū)可記錄512字節(jié)的數(shù)據(jù)，盤片轉(zhuǎn)速為7200r/m(轉(zhuǎn)/分)，平均尋道時間為5ms，請回答下列問題。

（1）每個扇區(qū)包含數(shù)據(jù)及地址信息，地址信息分為3個字段，這3個字段的名稱格式什么？對于該磁盤，各字段至少占多少位？

（2）一個扇區(qū)的平均訪問時間約為多少？

（3）若采用周期挪用DMA方式進行磁盤與主機之間的數(shù)據(jù)傳送，磁盤控制器中的數(shù)據(jù)緩沖區(qū)大小為64位，則在一個扇區(qū)讀寫過程中，DMA控制器向CPU發(fā)送了多少次總線請求？若CPU檢測到DMA控制器的總線請求信號時也需要訪問主存，則DMA控制器是否可以獲得總線使用權(quán)？為什么？

45、（7分）某文件系統(tǒng)的磁盤大小為4KB，目錄項由文件名和索引節(jié)點號構(gòu)成，每個索引節(jié)點占256字節(jié)，其中包含直接地址項10個，一級、二級和三級間接地址項各1個，每個地址項占4字節(jié)。該文件系統(tǒng)中子目錄stu的結(jié)構(gòu)如題45(a)圖所示，stu包含子目錄course和文件doc，course子目錄包含文件course1和course2。各文件的文件名、索引節(jié)點號、占用磁盤塊的塊號如題45(b)圖所示。

請回答下列問題。

（1）目錄文件stu中每個目錄項的內(nèi)容是什么？

（2）文件doc占用的磁盤塊的塊號x的值是多少？

（3）若目錄文件course的內(nèi)容已在內(nèi)存，則打開文件course1并將其讀入內(nèi)存，需要讀幾個磁盤塊？說明理由。

（4）若文件course2的大小增長到6MB，為了存取course2需要使用該文件索引節(jié)點的哪幾級間接地址項？說明理由。

46、（8分）某進程的兩個線程T1和T2并發(fā)執(zhí)行A、B、C、D、E和F共6個操作，其中T1執(zhí)行A、E和F，T2執(zhí)行B、C和D。題46圖表示上述6個操作的執(zhí)行順序所必須滿足的約束：C在A和B完成后執(zhí)行，D和E在C完成后執(zhí)行，F(xiàn)在E完成后執(zhí)行。請使用信號量的wait()、signal()操作描述T1和T2之間的同步關(guān)系，并說明所用信號量的作用及其初值。

47、(9分）某網(wǎng)絡(luò)拓撲如題47圖所示，R為路由器，S為以太網(wǎng)交換機，AP是802.11接入點，路由器的EO接口和DHCP服務(wù)器的IP地址配置如圖中所示：H1與H2屬于同一個廣播域，但不屬于同一個沖突域：12和H3屬于同一個沖突域：H4和H5已經(jīng)接入網(wǎng)絡(luò)，并通過DHCP動態(tài)獲取了IP地址。現(xiàn)有路由器、100BaseT以太網(wǎng)交換機和100BaseT集線器(Hub）三類設(shè)備各若干臺。

請回答下列問題。

（1）設(shè)備1和設(shè)備2應(yīng)該分別選擇哪類設(shè)備？

（2）若信號傳播速度為2×108m/s，以太網(wǎng)最小幀長為64B。信號通過設(shè)備2時會產(chǎn)生額外的1.51μs的時間延遲，則H2與H3之間可以相距的最遠距離是多少？

（3）在H4通DHCP動態(tài)獲取IP地址過程中，H4首先發(fā)送了DHCP報文M，M是哪種DHCP報文？路由器EO接口能否收到封裝M的以太網(wǎng)幀？s向DHCP服務(wù)器轉(zhuǎn)發(fā)的封裝M的以太網(wǎng)幀的目的MAC地址是什么？

（4）若H4向HS發(fā)送一個IP分組P，則HS收到的封裝P的802.11幀的地址1、地址2和地址3分別是什么？