計算機(jī)綜合2020年真題

更新時間2022-06-2617:58:37

2020年真題

408計算機(jī)學(xué)科專業(yè)基礎(chǔ)

研PDF:YanPDF.COM

注：【】內(nèi)為本題同類知識點(diǎn)歷年考頻信息

一、選擇題本大題共40小題，共80分。

1.[4】將一個10x10對稱矩陣M的上三角部分的元素按列優(yōu)先存入C語言

的一維數(shù)組N中，元素加加7,2在N中的下標(biāo)是一。

A.15B.16C.22D.23

2.【9】對空棧S進(jìn)行Push和Pop操作，入棧序列為a,b,c,d,e,經(jīng)過Push,Push,Pop,

Push,Pop,Push,Push,Pop操作后，得到的出棧序列是一。

A.b,a,cB.b,a,eC.b,c,aD.b,c,e

3.對于任意一棵高度為5且有10個結(jié)點(diǎn)的二叉樹，若采用順序存儲結(jié)構(gòu)保存，每個結(jié)點(diǎn)占1個存

儲單元（僅存放結(jié)點(diǎn)的數(shù)據(jù)信息）,則存放該二叉樹需要的存儲單元數(shù)量至少是—o

A.31B.16C.15D.10

4.[8]已知森林F及與之對應(yīng)的二叉樹T,若F的先根遍歷序列是a,b,c,d,e,f中根遍歷

序列是b,a,d,f,e,c,則T的后根遍歷序列是

A.b,a,d,f,e,cB.b,d,f,e,c,a

C.b,f,e,d,c,aD.f,e,d,c,b,a

5.[4]下列給定的關(guān)鍵字輸入序列中，不能生成如下二叉排序樹的是―。

A.4,5,2,1,3B.4,5,1,2,3C.4,2,5,3,1D.4,2,1,3,5

6.【3】修改遞歸方式實現(xiàn)的圖的深度優(yōu)先搜索（DFS）算法，將輸出（訪問）頂點(diǎn)信息的語句移到

退出遞歸前（即執(zhí)行輸出語句后立刻退出遞歸）。采用修改后的算法遍歷有向無環(huán)圖G,若輸出結(jié)果

中包含G中的全部頂點(diǎn)，則輸出的頂點(diǎn)序列是G的—。

A.拓?fù)溆行蛐蛄蠦.逆拓?fù)溆行蛐蛄?/p>

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

7.[3]已知無向圖G如下所示，使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹，加到最小

生成樹中的邊依次是一。

第1頁共10頁

更新時間2022-06-2617:58:37

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.[6]若使用AOE網(wǎng)估算工程進(jìn)度，則下列敘述中正確的是一。

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

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

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

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

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

I.可以將堆視為一棵完全二叉樹

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

ni,可以將堆視為一棵二叉排序樹

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

A.僅I、nB.僅n、inc.僅1、11和ivD.I、in和iv

10.[8]依次將關(guān)鍵字5,6,9,13,8,2,12,15插入初始為空的4階B樹后，根結(jié)點(diǎn)中包含

的關(guān)鍵字是―。

A.8B.6、9C.8、13D.9、12

11.[9]對大部分元素已有序的數(shù)組進(jìn)行排序時，直接插入排序比簡單選擇排序效率更高，其原

因是一o

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

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

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

A.僅IB.僅inc.僅I、iiD.I、n和in

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

I.ALUII.指令寄存器in,通用寄存器IV,浮點(diǎn)寄存器

A.僅I、IIB.僅I、inc.僅n、iiiD.僅n、ni、iv

13.[7]已知帶符號整數(shù)用補(bǔ)碼表示，float型數(shù)據(jù)用IEEE754標(biāo)準(zhǔn)表示，假定變量x的類型只可

能是int或float,當(dāng)x的機(jī)器數(shù)為C8000000H時，x的值可能是一。

A.-7x227B.-216C.217D.25x227

14.[9]在按字節(jié)編址，采用小端方式的32位計算機(jī)中，按邊界對齊方式為以下C語言結(jié)構(gòu)型變

量a分配存儲空間：

第2頁共10頁

更新時間2022-06-2617:58:37

structrecord{

shortxl;

intx2;

}a；

若a的首地址為2020FE00H,a的成員變量x2的機(jī)器數(shù)為12340000H,則其中34H所在存儲單

元的地址是一。

A.2020FE03HB.2020FE04HC.2020FE05HD.2020FE06H

15.[6]下列關(guān)于TLB和Cache的敘述中，錯誤的是一。

A.命中率都與程序局部性有關(guān)B,缺失后都需要去訪問主存

C.缺失處理都可以由硬件實現(xiàn)D.都由DRAM存儲器組成

16.[14]某計算機(jī)采用16位定長指令字格式，操作碼位數(shù)和尋址方式位數(shù)固定，指令系統(tǒng)有48

條指令，支持直接、間接、立即、相對4種尋址方式。單地址指令中，直接尋址方式的可尋址范圍

是-O

A.0—255B,0?1023C.-128?127D.-512?511

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

I.單周期CPUn,多周期CPUn.基本流水線CPUiv.超標(biāo)量流水線CPU

A.僅I、nB.僅I、inc.僅n、ivD.僅in、iv

18.[11]下列關(guān)于“自陷”（Trap,也稱陷阱）的敘述中,錯誤的是一。

A.自陷是通過陷阱指令預(yù)先設(shè)定的一類外部中斷事件

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

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

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

19.[14]QPI總線是一種點(diǎn)對點(diǎn)全工同步串行總線，總線上的設(shè)備可同時接收和發(fā)送信息，每個方

向可同時傳輸20位信息（16位數(shù)據(jù)+4位校驗位），每個QPI數(shù)據(jù)包有80位信息，分2個時鐘周

期傳送，每個時鐘周期傳遞2次。因此，QPI總線帶寬為：每秒傳送次數(shù)x28x2。若QPI時鐘頻

率為2.4GHz,則總線帶寬為一。

A.4.8GBpsB.9.6GBpsC.19.2GBpsD.38.4GBps

2O.[11]下列事件中，屬于外部中斷事件的是一。

I.訪存時缺頁n.定時器到時in.網(wǎng)絡(luò)數(shù)據(jù)包到達(dá)

A.僅I、nB.僅I、IIIC.僅n、IIID.LII和HI

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

是——O

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

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

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

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

22.16]若設(shè)備采用周期挪用DMA方式進(jìn)行輸入和輸出，每次DMA傳送的數(shù)據(jù)塊大小為512字

節(jié)，相應(yīng)的I/O接口中有一個32位數(shù)數(shù)據(jù)緩沖寄存器。對于數(shù)據(jù)輸入過程，下列敘述中錯誤的是.

第3頁共10頁

更新時間2022-06-2617:58:37

A.每準(zhǔn)備好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.[2]若多個進(jìn)程共享同一個文件F,則下列敘述中，正確的是一。

A.各進(jìn)程只能用“讀”方式打開文件F

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

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

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

24.[20]下列選項中，支持文件長度可變、隨機(jī)訪問的磁盤存儲空間分配方式是―。

A.索引分配B,鏈接分配C.連續(xù)分配D.動態(tài)分區(qū)分配

25.[9】下列與中斷相關(guān)的操作中，由操作系統(tǒng)完成的是―。

I.保存被中斷程序的中斷點(diǎn).

II提供中斷服務(wù)

n.初始化中斷向量表

iv.保存中斷屏蔽字

A.僅I、nB.僅I、n、ivc.僅in、ivD.僅11、ni、iv

26.【2】下列與進(jìn)程調(diào)度有關(guān)的因素中，在設(shè)計多級反饋隊列調(diào)度算法時需要考慮的是―。

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

n,就緒隊列的優(yōu)先級

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

IV.進(jìn)程在就緒隊列間的遷移條件

A.僅I、IIB.僅in、IVc.僅n、III、IVD.LII、IIIIV

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

進(jìn)程A已分配數(shù)量B已分配數(shù)量A需求總量B需求總量

P12344

P22131

P31234

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

A.存在安全序列Pl、P2、P3B,存在安全序列P2、Pl、P3

C.存在安全序列P2、P3、PlD.不存在安全序列

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

L缺頁率.

n.磁盤讀寫時間

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

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

A,僅II、IIIB.僅I、IVC,僅I、III、IVD.I、II、III和IV

第4頁共10頁

更新時間2022-06-2617:58:37

29.下列關(guān)于父進(jìn)程與子進(jìn)程的敘述中，錯誤的是—。

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

B.父進(jìn)程與子進(jìn)程共享虛擬地址空間

C.父進(jìn)程與子進(jìn)程有不同的進(jìn)程控制塊

D.父進(jìn)程與子進(jìn)程不能同時使用同一臨界資源

30.對于具備設(shè)備獨(dú)立性的系統(tǒng)，下列敘述中，錯誤的是—。

A,可以使用文件名訪問物理設(shè)備

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

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

D.更換物理設(shè)備后必須修改訪問該設(shè)備的應(yīng)用程序

31.L2］某文件系統(tǒng)的目錄項由文件名和索引結(jié)點(diǎn)號構(gòu)成。若每個目錄項長度為64字節(jié)，其中4

字節(jié)存放索引結(jié)點(diǎn)號，60字節(jié)存放文件名。文件名由小寫英文字母構(gòu)成，則該文件系統(tǒng)能創(chuàng)建的

文件數(shù)量的上限為―。

A.226B.232C.260D.264

32.下列準(zhǔn)則中，實現(xiàn)臨界區(qū)互斥機(jī)制必須遵循的是一。

I.兩個進(jìn)程不能同時進(jìn)入臨界區(qū)

II.允許進(jìn)程訪問空閑的臨界資源

II.進(jìn)程等待進(jìn)入臨界區(qū)的時間是有限的

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

A.僅I、ivB.僅n、inc.僅I、n、inD.僅I、III、IV

33.［i］下圖描述的協(xié)議要素是一。

D.I、n和川

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

B.需要為每條虛電路預(yù)分配帶寬

C.建立虛電路時需要進(jìn)行路由選擇

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

35.［18］在下圖所示的網(wǎng)絡(luò)中，沖突域和廣播域的個數(shù)分別是―。

第5頁共10頁

更新時間2022-06-2617:58:37

以太網(wǎng)交換機(jī)路由靜

A.2,2B.2,4C,4,2D,4,4

36.[2]假設(shè)主機(jī)甲采用停-等協(xié)議向主機(jī)乙發(fā)送數(shù)據(jù)幀，數(shù)據(jù)幀長與確認(rèn)幀長均為1000B,數(shù)據(jù)

傳輸速率是10kbps,單項傳播延時是200ms。則甲的最大信道利用率為一。

A.80%B,66.7%C.44.4%D.40%

37.[3]某IEEE802.11無線局域網(wǎng)中，主機(jī)H與AP之間發(fā)送或接收CSMA/CA幀的過程如下圖

所示。在H或AP發(fā)送幀前所等待的幀間間隔時間（IFS）中，最長的是—。

A.IFS1B.IFS2C.IFS3D.IFS4

38.【5I若主機(jī)甲與主機(jī)乙已建立一條TCP連接，最大段長（MSS）為1KB,往返時間（RTT）為

2ms,則在不出現(xiàn)擁塞的前提下，擁塞窗口從8KB增長到32KB所需的最長時間是

A.4msB.8msC.24msD.48ms

39.[7]若主機(jī)甲與主機(jī)乙建立TCP連接時，發(fā)送的SYN段中的序號為1000,在斷開連接時，甲

發(fā)送給乙的FIN段中的序號為5001,則在無任何重傳的情況下，甲向乙已經(jīng)發(fā)送的應(yīng)用層數(shù)據(jù)的

字節(jié)數(shù)為_。

A.4002B.4001C.4000D.3999

40.[9]假設(shè)下圖所示網(wǎng)絡(luò)中的本地域名服務(wù)器只提供遞歸查詢服務(wù)，其他域名服務(wù)器均只提供

迭代查詢服務(wù)：局域網(wǎng)內(nèi)主機(jī)訪問Internet。上各服務(wù)器的往返時間（RTT）均為10ms,忽略其他各

種時延。若主機(jī)H通過超鏈接/index.html請求瀏覽純文本W(wǎng)eb頁index.html,

則從點(diǎn)擊超鏈接開始到瀏覽器接收到index.html頁面為止，所需的最短時間與最長時間分別是—。

本地域名

服務(wù)器路由器

局域網(wǎng)

H

第6頁共10頁

更新時間2022-06-2617:58:37

A.10ms,40msB.10ms,50msC.20ms,40msD.20ms,50ms

二、簡答題本大題共7小題，共70分。

41.(13分)定義三元組(a,b,c)(其中a,b,c均為正數(shù))的距離D=|a—b|+|b-c|+|c—給定3

個非空整數(shù)集合S2和S3,按升序分別存儲在3個數(shù)組中。設(shè)計一個盡可能高效的算法，計算

并輸出所有可能的三元組(a,b,c)(ae&,beS2,c€S3)中的最小距離。例如0,9},

S2={-25,-10,10,11},S3={2,9,17,30,41),則最小距離為2,相應(yīng)的三元組為(9,10,9)。

要求:

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

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

(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。

42.[9](10分)若任一個字符的編碼都不是其他字符編碼的前綴、則稱這種編碼具有前綴特性。

現(xiàn)有某字符集(字符個數(shù)>2)的不等長編碼，每個字符的編碼均為二進(jìn)制的0、1序列，最長為L

位，且具有前綴特性。請回答下列問題：

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

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

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

43.(13分)有實現(xiàn)xxy的兩個C語言函數(shù)如下：

unsignedumul(unsignedx,unsignedy){returnx*y；}

intimul(intx,inty){returnx*y；}

_____________________________________________________________________________________:

假定某計算機(jī)M中ALU只能進(jìn)行加減運(yùn)算和邏輯運(yùn)算。請回答下列問題。

(1)若M的指令系統(tǒng)中沒有乘法指令，但有加法、減法和位移等指令，則在M上也能實現(xiàn)上述兩

個函數(shù)中的乘法運(yùn)算，為什么？

(2)若M的指令系統(tǒng)中有乘法指令，則基于ALU、位移器、寄存器以及相應(yīng)控制邏輯實現(xiàn)乘法指令

時，控制邏輯的作用是什么？

(3)針對以下三種情況:①沒有乘法指令;②有使用ALU和位移器實現(xiàn)的乘法指令;③有使用陣列乘法

器實現(xiàn)的乘法指令，函數(shù)umul。在哪種情況下執(zhí)行時間最長？哪種情況下執(zhí)行的時間最短？說

明理由

(4)n位整數(shù)乘法指令可保存2n位乘積，當(dāng)僅取低n位作為乘積時，其結(jié)果可能會發(fā)生溢出。當(dāng)

n=32,x=231-l,y=2時，帶符號整數(shù)乘法指令和無符號整數(shù)乘法指令得到的xxy的2n位乘

積分別是什么(用十六進(jìn)制表示)？此時函數(shù)umul。和imul。的返回結(jié)果是否溢出？對于無符

號整數(shù)乘法運(yùn)算，當(dāng)僅取乘積的低n位作為乘法結(jié)果時"如何用2n位乘積進(jìn)行溢出判斷？

44.(10分)假定主存地址為32位，按字節(jié)編址，指令Cache和數(shù)據(jù)Cache與主存之間均采用8路組

相聯(lián)映射方式，直寫(WriteThrough)寫策略和LRU替換算法，主存塊大小為64B,數(shù)據(jù)區(qū)容量各為

32KB。開始時Cache均為空。請回答下列問題。

(IJCache每一行中標(biāo)記(Tag),LRU位各占幾位？是否有修改位？

(2)有如下C語言程序段：

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

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

第7頁共10頁

更新時間2022-06-2617:58:37

若數(shù)組s及其變量k均為int型，int型數(shù)據(jù)占4B,變量k分配在寄存器中，數(shù)組s在主存中的

起始地址為008000C0H,則該程序段執(zhí)行過程中，訪問數(shù)組s的數(shù)據(jù)Cache缺失次數(shù)為多少?

（3）若CPU最先開始的訪問操作是讀取主存單元00010003H中的指令，簡耍說明從Cache中訪問

該指令的過程，包括Cache缺失處理過程。

45.[9]（7分）現(xiàn)有5個操作A、B、C、D和E,操作C必須在A和B完成后執(zhí)行，操作E必須

在C和D完成后執(zhí)行，請使用信號量的wait。、signal。操作（P、V操作）描述上述操作之間的同步

關(guān)系，并說明所用信號量及其初值。

46.[15]（8分）某32位系統(tǒng)采用基于二級頁表的請求分頁存儲管理方式，按字節(jié)編址，頁目錄項

和頁表項長度均為4字節(jié)，虛擬地址結(jié)構(gòu)如下所示。

頁目錄號（10位）頁號（10位）頁內(nèi)偏移量（12位）

某C程序中數(shù)組a[1024][1024]的起始虛擬地址為10800000H,數(shù)組元素占4字節(jié)，該程序

運(yùn)行時，其進(jìn)程的頁目錄起始物理地址為00201000H,請回答下列問題。

（1）數(shù)組元素a[l][2]的虛擬地址是什么？對應(yīng)的頁目錄號和頁號分別是什么？對應(yīng)的頁目錄項的

物理地址是什么？若該目錄項中存放的頁框號為00301H,則所在頁對應(yīng)的頁表項的物

理地址是什么？

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

續(xù)？

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

性更好？

47.[2]（9分）某校園網(wǎng)有兩個局域網(wǎng)，通過路由器Rl、R2和R3互聯(lián)后接入Internet,S1和S2

為以太網(wǎng)交換機(jī)。局域網(wǎng)采用靜態(tài)IP地址配置，路由器部分接口以及各主機(jī)的1P地址如下圖所示。

、Internet------------1

203.1021/30203.1025/30

R1

/30?/30?

NATS