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

一、單項選擇題（第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的結點數(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中，刪除關鍵字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散列函數(shù)

III沖突解決策略

A.僅I、II

B.僅I、III

C.僅II、III

D.I、II、III

10、使用二路歸并排序對含n個元素的數(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é)編址。某進程的頁表部分內容如下表所示。當CPU訪問虛擬地址00082840H，虛-實地址轉換的結果是（  ）。

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

A.內存條的容量為512MB

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

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

D.芯片內行緩沖有8192×8位

18、下列選項中，屬于指令集體系結構（ISA）規(guī)定的內容是（  ）。

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

Ⅱ.CPU的時鐘周期

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

Ⅳ.加法器的進位方式

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅳ

D.僅Ⅰ、Ⅲ、Ⅳ

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

A.0

B.2

C.64

D.128

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

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

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

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

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

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

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

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

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

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

22、下列關于并行處理技術的敘述中，不正確的是（  ）。

A.多核處理器屬于MIMD結構

B.向量處理器屬于SIMD結構

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

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

23、下列關于多道程序系統(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)先權越高）及CPU執(zhí)行時間如下表所示。

若系統(tǒng)采用基于優(yōu)先權的搶占式進程調度算法，則從0ms時刻開始調度，到4個進程都運行結束為止，發(fā)生進程調度的總次數(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、下列關于CPU模式的敘述中，正確的是（  ）。

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

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

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

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

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

Ⅰ.進程P讀文件

Ⅱ.進程P的時間片用完

Ⅲ.進程P申請外設

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

A.僅Ⅰ、Ⅳ

B.僅Ⅱ、Ⅲ

C.僅Ⅲ、Ⅳ

D.僅Ⅰ、Ⅲ、Ⅳ

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

A.淘汰內存中的頁

B.建立頁號與頁框號的對應關系

C.將頁b從外存讀入內存

D.修改頁表中頁b對應的存在位

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

A.頁面置換算法

B.工作集的大小

C.進程的數(shù)量

D.頁緩沖隊列的長度

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

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

Ⅱ.保存通用寄存器的內容

Ⅲ.執(zhí)行系統(tǒng)調用服務程序

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

A.僅Ⅰ、Ⅲ

B.僅Ⅱ、Ⅲ

C.僅Ⅱ、Ⅳ

D.僅Ⅱ、Ⅲ、Ⅳ

32、下列關于驅動程序的敘述中，不正確的是（  ）。

A.驅動程序與I/O控制方式無關

B.初始化設備是由驅動程序控制完成的

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

D.讀/寫設備的操作是由驅動程序控制完成的

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

A.物理層

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

C.網(wǎng)絡層

D.傳輸層

34、在一條帶寬為200kHz的無噪音信道上，若采用4個幅值的ASK調制，則該信道的最大數(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)絡的網(wǎng)絡地址是（  ）。

A.183.80.0.0

B.183.80.64.0

C.183.80.72.0

D.183.80.192.0

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

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

A.東向接口

B.南向接口

C.西向接口

D.北向接口

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

A.4RTT

B.5RTT

C.11RTT

D.16RTT

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

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的結點值均為正整數(shù)，采用順序存儲方式保存，數(shù)據(jù)結構定義如下：typedef struct{//MAX_SIZE為已定義常量

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

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

}SqBiTree;

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

T1的存儲結果如下：

T1.SqBiTNode

T1.ElemNum=10

T2的存儲結果如下：

T2.SqBiTNode

T2.ElemNum=11

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

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

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

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

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

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

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

（1）ALU的輸入端A、B及輸出端F的最高位分別為A15、B15及F15，F(xiàn)R中的符號標志和溢出標志分別為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增量操作）的控制信號序列是什么？若從發(fā)出主存讀命令到主存讀出數(shù)據(jù)并傳送到MDR共需5個時鐘周期，則取指令階段至少需要幾個時鐘周期？

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

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

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

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

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

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

請回答下列問題。

（1）目錄文件stu中每個目錄項的內容是什么？

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

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

（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之間的同步關系，并說明所用信號量的作用及其初值。

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

請回答下列問題。

（1）設備1和設備2應該分別選擇哪類設備？

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

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

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