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

一、單項選擇題（第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求）

1、將一個10×10對稱矩陣M的上三角部分的元素mi，j(1≤i≤j≤10)按列優(yōu)先存入C語言的一維數(shù)組N中，元素m7，2在N中的下標是（  ）。

A.15

B.16

C.22

D.23

2、對空棧S進行Push和Pop操作，入棧序列為a，b，c，d，e，經(jīng)過Push，Push，Pop，Push，Pop，Push，Push，Pop操作后得到的出棧序列是（  ）。

A.b，a，c

B.b，a，e

C.b，c，a

D.b，c，e

3、對于任意一棵高度為5且有10個結(jié)點的二叉樹，若采用順序存儲結(jié)構(gòu)保存，每個結(jié)點占1個存儲單元（僅存放結(jié)點的數(shù)據(jù)信息），則存放該二叉樹需要的存儲單元數(shù)量至少是（  ）。

A.31

B.16

C.15

D.10

4、已知森林F及與之對應的二叉樹T，若F的先根遍歷序列是a，b，c，d，e，f，中根遍歷序列是b，a，d，f，e，c，則T的后根遍歷序列是（  ）。

A.b，a，d，f，e，c

B.b，d，f，e，c，a

C.b，f，e，d，c，a

D.f，e，d，c，b，a

5、下列給定的關(guān)鍵字輸入序列中，不能生成如下二叉排序樹的是（  ）。

A.4，5，2，1，3

B.4，5，1，2，3

C.4，2，5，3，1

D.4，2，1，3，5

6、修改遞歸方式實現(xiàn)的圖的深度優(yōu)先搜索（DFS）算法，將輸出（訪問）頂點信息的語句移到退出遞歸前（即執(zhí)行輸出語句后立刻退出遞歸）。采用修改后的算法遍歷有向無環(huán)圖G，若輸出結(jié)果中包含G中的全部頂點，則輸出的頂點序列是G的（  ）。

A.拓撲有序序列

B.逆拓撲有序序列

C.廣度優(yōu)先搜索序列

D.深度優(yōu)先搜索序列

7、已知無向圖G如下所示，使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹，加到最小生成樹中的邊依次是（  ）。

A.（b，f），（b，d），（a，e），（c，e），（b，e）

B.（b，f），（b，d），（b，e），（a，e），（c，e）

C.（a，e），（b，e），（c，e），（b，d），（b，f）

D.（a，e），（c，e），（b，e），（b，f），（b，d）

8、若使用AOE網(wǎng)估算工程進度，則下列敘述中正確的是（  ）。

A.關(guān)鍵路徑是從原點到匯點邊數(shù)最多的一條路徑

B.關(guān)鍵路徑是從原點到匯點路徑長度最長的路徑

C.增加任一關(guān)鍵活動的時間不會延長工程的工期

D.縮短任一關(guān)鍵活動的時間將會縮短工程的工期

9、下列關(guān)于大根堆（至少含2個元素）的敘述中，正確的是（  ）。

I.可以將堆看成一棵完全二叉樹

II.可以采用順序存儲方式保存堆

III.可以將堆看成一棵二叉排序樹

IV.堆中的次大值一定在根的下一層

A.僅I、II

B.僅II、III

C.僅I、II和IV

D.I、III和IV

10、依次將關(guān)鍵字5，6，9，13，8，2，12，15插入初始為空的4階B樹后，根結(jié)點中包含的關(guān)鍵字是（  ）。

A.8

B.6，9

C.8，13

D.9，12

11、對大部分元素已有序的數(shù)組進行排序時，直接插入排序比簡單選擇排序效率更高，其原因是（  ）。

I.直接插入排序過程中元素之間的比較次數(shù)更少

II.直接插入排序過程中所需要的輔助空間更少

III.直接插入排序過程中元素的移動次數(shù)更少

A.僅I

B.僅III

C.僅I、II

D.I、II和III

12、下列給出的部件中，其位數(shù)（寬度）一定與機器字長相同的是（  ）。

Ⅰ.ALU

Ⅱ.指令寄存器

Ⅲ.通用寄存器

IV.浮點寄存器

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅲ

D.僅Ⅱ、Ⅲ、IV

13、已知帶符號整數(shù)用補碼表示，float型數(shù)據(jù)用IEEE754標準表示，假定變量x的類型只可能是int或float，當x的機器數(shù)為C8000000H時，x的值可能是（  ）。

A.-7×227

B.-216

C.217

D.25x227

14、在按字節(jié)編址采用小端方式的32位計算機中，按邊界對齊方式為以下C語言結(jié)構(gòu)型變量a分配存儲空間。

struct record{

short x1;

int x2;

}a;

若a的首地址為2020FE00H，a的成員變量x2的機器數(shù)為12340000H，則其中34H所在的存儲單元的地址是（  ）。

A.2020FE03H

B.2020FE04H

C.2020FE05H

D.2020FE06H

15、下列關(guān)于TLB和Cache的敘述中，錯誤的是（  ）。

A.命中率都與程序局部性有關(guān)

B.缺失后都需要去訪問主存

C.缺失處理都可以由硬件實現(xiàn)

D.都由DRAM存儲器組成

16、某計算機采用16位定長指令字格式，操作碼位數(shù)和尋址方式位數(shù)固定，指令系統(tǒng)有48條指令，支持直接、間接、立即、相對4種尋址方式。單地址指令中，直接尋址方式的可尋址范圍是（  ）。

A.0~225

B.0~1023

C.-128~127

D.-512~511

17、下列給出的處理器類型中，理想情況下，CPI為1的是（  ）。

Ⅰ.單周期CPU

Ⅱ.多周期CPU

Ⅲ.基本流水線CPU

Ⅳ.超標量流水線CPU

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅳ

D.僅Ⅲ、Ⅳ

18、下列關(guān)于“自陷”（Trap，也稱陷阱）的敘述中，錯誤的是（  ）。

A.自陷是通過陷阱指令預先設定的一類外部中斷事件

B.自陷可用于實現(xiàn)程序調(diào)試時的斷點設置和單步跟蹤

C.自陷發(fā)生后CPU將轉(zhuǎn)去執(zhí)行操作系統(tǒng)內(nèi)核相應程序

D.自陷處理完成后返回到陷阱指令的下一條指令執(zhí)行

19、QPI總線是一種點對點全I同步串行總線，總線上的設備可同時接收和發(fā)送信息，每個方向可同時傳輸20位信息（16位數(shù)據(jù)+4位校驗位），每個QPI數(shù)據(jù)包有80位信息，分2個時鐘周期傳送，每個時鐘周期傳遞2次。因此，QPI總線帶寬為：每秒傳送次數(shù)×2B×2。若QPI時鐘頻率為2.4GHz，則總線帶寬為（  ）。

A.4.8GB/s

B.9.6GB/s

C.19.2GB/s

D.38.4GB/s

20、下列事件中，屬于外部中斷事件的是（  ）。

Ⅰ.訪存時缺頁

Ⅱ.定時器到時

Ⅲ.網(wǎng)絡數(shù)據(jù)包到達

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅲ

D.Ⅰ、Ⅱ和Ⅲ

21、外部中斷包括不可屏蔽中斷（NMI）和可屏蔽中斷，下列關(guān)于外部中斷的敘述中，錯誤的是（  ）。

A.CPU處于關(guān)中斷狀態(tài)時，也能響應NMI請求

B.一旦可屏蔽中斷請求信號有效，CPU將立即響應

C.不可屏蔽中斷的優(yōu)先級比可屏蔽中斷的優(yōu)先級高

D.可通過中斷屏蔽字改變可屏蔽中斷的處理優(yōu)先級

22、若設備采用周期挪用DMA方式進行輸入和輸出，每次DMA傳送的數(shù)據(jù)塊大小為512字節(jié)，相應的I/O接口中有一個32位數(shù)數(shù)據(jù)緩沖寄存器。對于數(shù)據(jù)輸入過程，下列敘述中，錯誤的是（  ）。

A.每準備好32位數(shù)據(jù)，DMA控制器就發(fā)出一次總線請求

B.相對于CPU，DMA控制器的總線使用權(quán)的優(yōu)先級更高

C.在整個數(shù)據(jù)塊的傳送過程中，CPU不可以訪問主存儲器

D.數(shù)據(jù)塊傳送結(jié)束時，會產(chǎn)生“DMA傳送結(jié)束”中斷請求

23、若多個進程共享同一個文件F，則下列敘述中，正確的是（  ）。

A.各進程只能用“讀”方式打開文件F

B.在系統(tǒng)打開文件表中僅有一個表項包含F(xiàn)的屬性

C.各進程的用戶打開文件表中關(guān)于F的表項內(nèi)容相同

D.進程關(guān)閉F時，系統(tǒng)刪除F在系統(tǒng)打開文件表中的表項

24、下列選項中，支持文件長度可變、隨機訪問的磁盤存儲空間分配方式是（  ）。

A.索引分配

B.鏈接分配

C.連續(xù)分配

D.動態(tài)分區(qū)分配

25、下列與中斷相關(guān)的操作中，由操作系統(tǒng)完成的是（  ）。

Ⅰ.保存被中斷程序的中斷點

Ⅱ.提供中斷服務

Ⅲ.初始化中斷向量表

Ⅳ.保存中斷屏蔽字

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅱ、Ⅳ

C.僅Ⅲ、Ⅳ

D.僅Ⅱ、Ⅲ、Ⅳ

26、下列與進程調(diào)度有關(guān)的因素中，在設計多級反饋隊列調(diào)度算法時需要考慮的是（  ）。

Ⅰ.就緒隊列的數(shù)量

Ⅱ.就緒隊列的優(yōu)先級

Ⅲ.各就緒隊列的調(diào)度算法

Ⅳ.進程在就緒隊列間的遷移條件

A.僅Ⅰ、Ⅱ

B.僅Ⅲ、Ⅳ

C.僅Ⅱ、Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

27、某系統(tǒng)中有A、B兩類資源各6個，t時刻資源分配及需求情況如下表所示。

t時刻安全性檢測結(jié)果是（  ）。

A.存在安全序列P1、P2、P3

B.存在安全序列P2、P1、P3

C.存在安全序列P2、P3、P1

D.不存在安全序列

28、下列因素中，影響請求分頁系統(tǒng)有效（平均）訪存時間的是（  ）。

Ⅰ.缺頁率

Ⅱ.磁盤讀寫時間

Ⅲ.內(nèi)存訪問時間

Ⅳ.執(zhí)行缺頁處理程序的CPU時間

A.僅Ⅱ、Ⅲ

B.僅Ⅰ、Ⅳ

C.僅Ⅰ、Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

29、下列關(guān)于父進程與子進程的敘述中，錯誤的是（  ）。

A.父進程與子進程可以并發(fā)執(zhí)行

B.父進程與子進程共享虛擬地址空間

C.父進程與子進程有不同的進程控制塊

D.父進程與子進程不能同時使用同一臨界資源

30、對于具備設備獨立性的系統(tǒng)，下列敘述中，錯誤的是（  ）。

A.可以使用文件名訪問物理設備

B.用戶程序使用邏輯設備名訪問物理設備

C.需要建立邏輯設備與物理設備之間的映射關(guān)系

D.更換物理設備后必須修改訪問該設備的應用程序 

31、某文件系統(tǒng)的目錄項由文件名和索引結(jié)點號構(gòu)成。若每個目錄項長度為64字節(jié)，其中4字節(jié)存放索引結(jié)點號，60字節(jié)存放文件名。文件名由小寫英文字母構(gòu)成，則該文件系統(tǒng)能創(chuàng)建的文件數(shù)量的上限為（  ）。

A.226

B.232

C.260

D.264

32、下列準則中，實現(xiàn)臨界區(qū)互斥機制必須遵循的是（  ）。

Ⅰ.兩個進程不能同時進入臨界區(qū)

Ⅱ.允許進程訪問空閑的臨界資源

Ⅲ.進程等待進入臨界區(qū)的時間是有限的

Ⅳ.不能進入臨界區(qū)的執(zhí)行態(tài)進程立即放棄CPU

A.僅Ⅰ、Ⅳ

B.僅Ⅱ、Ⅲ

C.僅Ⅰ、Ⅱ、Ⅲ

D.僅Ⅰ、Ⅲ、Ⅳ

33、下圖描述的協(xié)議要素是（  ）。

I.語法

II.語義

II.時序

A.僅I

B.僅II

C.僅III

D.I、II和III

34、下列關(guān)于虛電路網(wǎng)絡的敘述中，錯誤的是（  ）。

A.可以確保數(shù)據(jù)分組傳輸順序

B.需要為每條虛電路預分配帶寬

C.建立虛電路時需要進行路由選擇

D.依據(jù)虛電路號（VCID）進行數(shù)據(jù)分組轉(zhuǎn)發(fā)

35、在下圖所示的網(wǎng)絡中，沖突域和廣播域的個數(shù)分別是（  ）。

A.2，2

B.2，4

C.4，2

D.4，4

36、假設主機甲采用停-等協(xié)議向主機乙發(fā)送數(shù)據(jù)幀，數(shù)據(jù)幀長與確認幀長均為1000B，數(shù)據(jù)傳輸速率是10kbps，單向傳播延時是200ms。則甲的最大信道利用率為（  ）。

A.80%

B.66.7%

C.44.4%

D.40%

37、某IEEE802.11無線局域網(wǎng)中，主機H與AP之間發(fā)送或接收CSMA/CA幀的過程如下圖所示。在H或AP發(fā)送幀前所等待的幀間間隔時間（IFS）中，最長的是（  ）。

A.IFS1

B.IFS2

C.IFS3

D.IFS4

38、若主機甲與主機乙已建立一條TCP連接，最大段長（MSS）為1KB，往返時間（RTT）為2ms，則在不出現(xiàn)擁塞的前提下，擁塞窗口從8KB增長到32KB所需的最長時間是（  ）。

A.4ms

B.8ms

C.24ms

D.48ms

39、若主機甲與主機乙建立TCP連接時，發(fā)送的SYN段中的序號為1000，在斷開連接時，甲發(fā)送給乙的FIN段中的序號為5001，則在無任何重傳的情況下，甲向乙已經(jīng)發(fā)送的應用層數(shù)據(jù)的字節(jié)數(shù)為（  ）。

A.4002

B.4001

C.4000

D.3999

40、假設下圖所示網(wǎng)絡中的本地域名服務器只提供遞歸查詢服務，其他域名服務器均只提供迭代查詢服務；局域網(wǎng)內(nèi)主機訪問Internet上各服務器的往返時間（RTT）均為10ms,忽略其他各種時延。若主機H通過超鏈接http://www.abc.com/index.html請求瀏覽純文本W(wǎng)eb頁index.html,則從點擊超鏈接開始到瀏覽器接收到index.html頁面為止，所需的最短時間與最長時間分別是（  ）。

A.10ms，40ms

B.10ms，50ms

C.20ms，40ms

D.20ms，50ms

二、綜合應用題（第41~47小題，共70分）

41、（13分）定義三元組（a，b，c）（其中a，b，c均為正數(shù)）的距離D=|a-b|+|b-c|+|c-a|。給定3個非空整數(shù)集合S1、S2和S3，按升序分別存儲在3個數(shù)組中。設計一個盡可能高效的算法，計算并輸出所有可能的三元組（a，b，c）（a∈S1，b∈S2，c∈S3）中的最小距離。例如S1={-1，0，9}，S2={-25，-10，10，11}，S3={2，9，17，30，41}，則最小距離為2，相應的三元組為（9，10，9）。要求：

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

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

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

42、（10分）若任一個字符的編碼都不是其他字符編碼的前綴，則稱這種編碼具有前綴特性?，F(xiàn)有某字符集（字符個數(shù)≥2）的不等長編碼，每個字符的編碼均為二進制的0、1序列，最長為L位，且具有前綴特性。請回答下列問題：

（1）哪種數(shù)據(jù)結(jié)構(gòu)適宜保存上述具有前綴特性的不等長編碼？

（2）基于你所設計的數(shù)據(jù)結(jié)構(gòu)，簡述從0/1串到字符串的譯碼過程。

（3）簡述判定某字符集的不等長編碼是否具有前綴特性的過程。

43、（13分）有實現(xiàn)x×y的兩個C語言函數(shù)如下：

unsigned umul (unsigned x, unsigned y) { return x*y; }

int imul (int x, int y) {return x * y; }

假定某計算機M中ALU只能進行加減運算和邏輯運算。請回答下列句題。

（1）若M的指令系統(tǒng)中沒有乘法指令，但有加法、減法和位移等指令，則在M上也能實現(xiàn)上述兩個函數(shù)中的乘法運算，為什么？

（2）若M的指令系統(tǒng)中有乘法指令，則基于ALU、位移器、寄存器以及相應控制邏輯實現(xiàn)乘法指令時，控制邏輯的作用是什么？

（3）針對以下三種情況：a）沒有乘法指令；b）有使用ALU和位移器實現(xiàn)的乘法指令；c）有使用陣列乘法器實現(xiàn)的乘法指令，函數(shù)umul()在哪種情況下執(zhí)行時間最長？哪種情況下執(zhí)行的時間最短？說明理由

（4）n位整數(shù)乘法指令可保存2n位乘積，當僅取低n位作為乘積時，其結(jié)果可能會發(fā)生溢出。當n=32、x=231-1、y=2時，帶符號整數(shù)乘法指令和無符號整數(shù)乘法指令得到的x×y的2n位乘積分別是什么（用十六進制表示）？此時函數(shù)umuI()和imuI()的返回結(jié)果是否溢出？對于無符號整數(shù)乘法運算，當僅取乘積的低位作為乘法結(jié)果時，如何用2n位乘積進行溢出判斷？

44、（10分）假定主存地址為32位，按字節(jié)編址，指令Cache和數(shù)據(jù)Cache與主存之間均采用8路組相聯(lián)映射方式，直寫（Write Through）寫策略和LRU替換算法，主存塊大小為64B，數(shù)據(jù)區(qū)容量各為32KB。開始時Cache均為空。請回答下列問題。

（1）Cache每一行中標記（Tag）、LRU位各占幾位？是否有修改位？

（2）有如下C語言程序段：

for(k=0;k<1024;k++)

s[k]=2*s[k];

若數(shù)組s及其變量k均為int型，int型數(shù)據(jù)占4B，變量k分配在寄存器中，數(shù)組s在主存中的起始地址為0080 00C0H，則該程序段執(zhí)行過程中，訪問數(shù)組s的數(shù)據(jù)Cache缺失次數(shù)為多少？

（3）若CPU最先開始的訪問操作是讀取主存單元0001 0003H中的指令，簡要說明從Cache中訪問該指令的過程，包括Cache缺失處理過程。

45、（7分）現(xiàn)有5個操作A、B、C、D和E，操作C必須在A和B完成后執(zhí)行，操作E必須在C和D完成后執(zhí)行，請使用信號量的wait()、signal()操作(P、V操作)描述上述操作之間的同步關(guān)系，并說明所用信號量及其初值。

46、（8分）某32位系統(tǒng)采用基于二級頁表的請求分頁存儲管理方式，按字節(jié)編址，頁目錄項和頁表項長度均為4字節(jié)，虛擬地址結(jié)構(gòu)如下所示。

某C程序中數(shù)組a[1024][1024]的起始虛擬地址為1080 000H，數(shù)組元素占4字節(jié)，該程序運行時，其進程的頁目錄起始物理地址為0020 1000H，請回答下列問題。

（1）數(shù)組元素a[1][2]的虛擬地址是什么?對應的頁目錄號和頁號分別是什么?對應的頁目錄項的物理地址是什么?若該目錄項中存放的頁框號為00301H,則a[1][2]所在頁對應的頁表項的物理地址是什么?

（2）數(shù)組a在虛擬地址空間中所占區(qū)域是否必須連續(xù)?在物理地址空間中所占區(qū)域是否必須連續(xù)?

（3）已知數(shù)組a按行優(yōu)先方式存放，若對數(shù)組a分別按行遍歷和按列遍歷，則哪一種遍歷方式的局部性更好?

47、（9分）某校園網(wǎng)有兩個局域網(wǎng)，通過路由器RI、R2和R3互聯(lián)后接入Internet,S1和S2為以太網(wǎng)交換機。局域網(wǎng)采用靜態(tài)IP地址配置，路由器部分接口以及各主機的IP地址如下圖所示。

假設NAT轉(zhuǎn)換表結(jié)構(gòu)為

請回答下列問題：

（1）為使H2和H3能夠訪問Web服務器（使用默認端口號），需要進行什么配置？

（2）若H2主動訪問Web服務器時，將HTTP請求報文封裝到IP數(shù)據(jù)報P中發(fā)送，則H2發(fā)送P的源IP地址和目的IP地址分別是什么？經(jīng)過R3轉(zhuǎn)發(fā)后，P的源IP地址和目的IP地址分別是什么？經(jīng)過R2轉(zhuǎn)發(fā)后，P的源IP地址和目的IP地址分別是什么？