2018年計(jì)算機(jī)考研真題（含答案）

2018年計(jì)算機(jī)考研真題及參考答案

2018年全國碩士研究生入學(xué)統(tǒng)一考試

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題

一、單項(xiàng)選擇題：第1?40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，

只有一個(gè)選項(xiàng)最符合試題要求。

1.若棧Si中保存整數(shù)，棧S2中保存運(yùn)算符，函數(shù)F（）依次執(zhí)行下述各步操作：

（1）從Si中依次彈出兩個(gè)操作數(shù)a和b；

（2）從S2中彈出一個(gè)運(yùn)算符op；

（3）執(zhí)行相應(yīng)的運(yùn)算bopa；

（4）將運(yùn)算結(jié)果壓人&中。

假定Si中的操作數(shù)依次是5,8,3,2（2在棧頂），S2中的運(yùn)算符依次是*,-,+（+在棧頂）。調(diào)

用3次F（）后，S,棧頂保存的值是?

A.-15B.15C.-20D.20

2.現(xiàn)有隊(duì)列Q與棧S,初始時(shí)Q中的元素依次是1,2,3,4,5,6（1在隊(duì)頭），S為空。若僅允

許下列3種操作：①出隊(duì)并輸出出隊(duì)元素；②出隊(duì)并將出隊(duì)元素人棧；③出棧并輸出出棧元素，

則不能得到的輸出序列是。

A.1,2,5,6,4,3B.2,3,4,5,6,1

C.3,4,5,6,1,2D.6,5,4,3,2,1

3.設(shè)有一個(gè)12X12的對稱矩陣M,將其上三角部分的元素mi.i（1WiWj實(shí)控行優(yōu)先存人C

語言的一維數(shù)組N中，元素mm在N中的下標(biāo)是。

A.50B.51C.55D.66

4.設(shè)?棵非空完全二叉樹T的所有葉結(jié)點(diǎn)均位于同一層，且每個(gè)非葉結(jié)點(diǎn)都有2個(gè)子結(jié)點(diǎn)。

若丁有k個(gè)葉結(jié)點(diǎn)，則T的結(jié)點(diǎn)總數(shù)是.

A.2k-1B.2kC.k2D.2k-1

5.已知字符集｛a,b,c,d,e,f｝，若各字符出現(xiàn)的次數(shù)分別為6,3,8,2,10,4,則對應(yīng)字符集中

各字符的哈夫曼編碼可能是。

A.00,1011,01,1010,11,100B.00,100,110,000,0010,01

C.10,1011,11,0011,00,010D.0011,10,11,0010,01,000

6.已知二叉排序樹如下圖所示，元素之間應(yīng)滿足的大小關(guān)系是。

第1頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

C.5,1,2,3,6,4D.5,2,1,6,3,4

8.高度為5的3階B樹含有的關(guān)鍵字個(gè)數(shù)至少是=

A.15B.31C.62D.242

9.現(xiàn)有長度為7、初始為空的散列表HT,散列函數(shù)H(k)=k%7,用線性探測再散列法解決

沖突。將關(guān)鍵字22,43,15依次插人到HT后，查找成功的平均查找長度是?

A.1.5B.1.6C.2D.3

10.對初始數(shù)據(jù)序列(8,3,9,11,2,1,4,7,5,10,6)進(jìn)行希爾排序。若第一趟排序結(jié)果為(1,

3,7,5,2,6,4,9,11,10,8),第二趟排序結(jié)果為(1,2,6,4,3,7,5,8,11,10,9),則兩趟排序采用的

增量(間隔)依次是。

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

11.在將數(shù)據(jù)序列(6,1,5,9,8,4,7)建成大根堆時(shí)，正確的序列變化過程是

A.6,1,7,9,8,4,5~6,9,7,1,8,4,5~9,67,1,8,4,5~9,87,1,6,4,5

B.6,9,5,1,8,47一6,97,1,8,4,5一9,67,1,8,4,5一9,8,7,1,6,4,5

C.6,9,5,1,8,47-9,6,5,1,8,47-9,67,1,8,4,5—9,87,1,6,4,5

D.6,1,7,9,8,4,5-7,1,6,9,8,4,5-7,9,6,1,8,4,5—9,7,6,1,8,4,5-9,8,6,17,4,5

12.馮第?依曼結(jié)構(gòu)計(jì)算機(jī)中數(shù)據(jù)采用二進(jìn)制編碼表示，其主要原因是

I.二進(jìn)制的運(yùn)算規(guī)則簡唯

II.制造兩個(gè)穩(wěn)態(tài)的物理器件較容易

III.便于用邏輯門電路實(shí)現(xiàn)算術(shù)運(yùn)算

A.僅I、IIB.僅I、IHC.僅II、IIID.I、II和山

13.假定帶符號(hào)整數(shù)采用補(bǔ)碼表示，若int型變量x和y的機(jī)器數(shù)分別是FFFFFFDFH和0000

0041H,則x,y的值以及x-y的機(jī)器數(shù)分別是一

A.x=-65,y=41,x-y的機(jī)器數(shù)溢出

B.x=-33,y=65,x-y的機(jī)器數(shù)為FFFFFF9DH

C.x=-33,y=65,x-y的機(jī)器數(shù)為FFFFFF9EH

第2頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

D.x=-65,y=41,x-y的機(jī)器數(shù)為FFFFFF96H

14.IEEE754單精度浮點(diǎn)格式表示的數(shù)中，最小的規(guī)格化正數(shù)是=

A.1.02丈26B.1.0米27C.1.0農(nóng)28D.1.0米49

15.某32位計(jì)算機(jī)按字節(jié)編址，采用小端(LittleEndian)方式。若語令"inti=0;對應(yīng)指令的

機(jī)器代碼為“C745FC00000000,”則語句“inti=-64;'對應(yīng)指令的機(jī)器代碼是。

A.C745FCCOFFFFFFB.C745FCOCFFFFFF

C.C745FCFFFFFFCOD.C745FCFFFFFFOC

16.整數(shù)x的機(jī)器數(shù)為11011000,分別對x進(jìn)行邏輯右移1位和算術(shù)右移1位操作，得到的

機(jī)器數(shù)各是。

A.11101100,11101100B.01101100、11101100

C.11101100.01101100D.01101100.01101100

17.假定DRAM芯片中存儲(chǔ)陣列的行數(shù)為r、列數(shù)為c,對于一個(gè)2Kxi位的DRAM芯片，

為保證其地址引腳數(shù)最少，并盡量減少刷新開銷，則r、c的取值分別是o

A.2048,1B.64、32C.32、64D.1、2048

18.按字節(jié)編址的計(jì)算機(jī)中，某double型數(shù)組A的首地址為2000H,使用變址尋址和循環(huán)結(jié)

構(gòu)訪問數(shù)組A,保存數(shù)組下標(biāo)的變址寄存器初值為0,每次循環(huán)取一個(gè)數(shù)組元素，其偏移地址為

變址值乘以sizeof(double),取完后變址寄存器內(nèi)容自動(dòng)加1。若某次循環(huán)所取元素的地址為2100H,

則進(jìn)入該次循環(huán)時(shí)變址寄存器的內(nèi)容是。

A.25B.32C.64D.100

19.減法指令“subR1,R2,R3的功能為“(R1)-(R2)-R3'；該指令執(zhí)行后將生成進(jìn)位/借

位標(biāo)志CF和溢出標(biāo)志OF。若(R1)=FFFFFFFFH,(R2)=FFFFFFFOH,則該減法指令執(zhí)行

后，CF與OF分別為。

A.CF=0,OF=0B.CF=1,OF=0

C.CF=0,0F=1D.CF=1,OF=1

20.若某計(jì)算機(jī)最復(fù)雜指令的執(zhí)行需要完成5個(gè)子功能，分別由功能部件A-E實(shí)現(xiàn)，各功能

部件所需時(shí)間分別為80ps、50ps、50ps、70Ps和50ps,采用流水線方式執(zhí)行指令，流水段寄存器

延時(shí)為20ps,貝ijCPU時(shí)鐘周期至少為。

A.60psB.70psC.80psD.100ps

21.下列選項(xiàng)中，可提高同步總線數(shù)據(jù)傳輸率的是。

I.增加總線寬度II.提高總線工作頻率

III.支持突發(fā)傳輸IV.采用地址/數(shù)據(jù)線復(fù)用

A.僅I、nB.僅I、n、m

c.僅in、ivD.i、n、ni和N

22.下列關(guān)于外部i/o中斷的敘述中，正確的是.

A.中斷控制器按所接收中斷請求的先后次序進(jìn)行中斷優(yōu)先級排隊(duì)

B.CPU響應(yīng)中斷時(shí)，通過執(zhí)行中斷隱指令完成通用寄存器的保護(hù)

C.CPU只有在處于中斷允許狀態(tài)時(shí)，才能響應(yīng)外部設(shè)備的中斷請求

D.有中斷請求時(shí)，CPU立即暫停當(dāng)前指令執(zhí)行，轉(zhuǎn)去執(zhí)行中斷服務(wù)程序

23.下列關(guān)于多任務(wù)操作系統(tǒng)的敘述中，正確的是。

I.具有并發(fā)和并行的特點(diǎn)

II.需要實(shí)現(xiàn)對共享資源的保護(hù)

第3頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

III.需要運(yùn)行在多CPU的硬件平臺(tái)上

A.僅IB.僅nC.僅I、IID.I、II.III

24.某系統(tǒng)采用基于優(yōu)先權(quán)的非搶占式進(jìn)程調(diào)度策略，完成一次進(jìn)程調(diào)度和進(jìn)程切換的系統(tǒng)

時(shí)間開銷為1us。在T時(shí)刻就緒隊(duì)列中有3個(gè)進(jìn)程R、2和p3,其在就緒隊(duì)列中的等待時(shí)間、需

要的CPU時(shí)間和優(yōu)先權(quán)如卜表所示。

進(jìn)程等待時(shí)間需要的CPU時(shí)間優(yōu)先權(quán)

P130MS12us10

P215MS24us30

P318ys36us20

若優(yōu)先權(quán)值大的進(jìn)程優(yōu)先獲得CPU,從T時(shí)刻起系統(tǒng)開始進(jìn)程調(diào)度，則系統(tǒng)的平均周轉(zhuǎn)時(shí)間

為

A.54B.73BC.74sD.758

25.屬于同進(jìn)程的兩個(gè)線程threadl和thread2并發(fā)執(zhí)行，共享初值為0的全局變量x°thread1

和thread2實(shí)現(xiàn)對全局變量x加1的機(jī)器級代碼描述如下。

threadlthread2

movR1,x//(x)-R1movR2,x//(x)-*R2

incR1//(RD+1-R1incR2//(R2)+1fR2

movx,R1//(R1)-xmovx,R2//(R2)-x

在所有可能的指令執(zhí)行序列中，使x的值為2的序列個(gè)數(shù)是

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

26.假設(shè)系統(tǒng)中有4個(gè)同類資源，進(jìn)程R、P2和P3需要的資源數(shù)分別為4、3和1,Pi、P2

和P3已申請到的資源數(shù)分別為2、1和0,則執(zhí)行安全性檢測算法的結(jié)果是.

A.不存在安全序列，系統(tǒng)處于不安全狀態(tài)

B.存在多個(gè)安全序列，系統(tǒng)處于安全狀態(tài)

C.存在唯一安全序列P3、Pi、P2,系統(tǒng)處于安全狀態(tài)

D.存在唯一安全序列P3、丹、R,系統(tǒng)處于安全狀態(tài)

27.下列選項(xiàng)中，可能導(dǎo)致當(dāng)前進(jìn)程P阻塞的事件是。

I.進(jìn)程P申請臨界資源

H.進(jìn)程P從磁盤讀數(shù)據(jù)

III.系統(tǒng)將CPU分配給高優(yōu)先權(quán)的進(jìn)程

A.僅1B.僅HC.僅I、IlD.I,II>III

28.若x是管程內(nèi)的條件變量，則當(dāng)進(jìn)程執(zhí)行x.waW）時(shí)所做的工作是。

A.實(shí)現(xiàn)對變量x的互斥訪問

B.喚醒一個(gè)在x上阻塞的進(jìn)程

C.根據(jù)x的值判斷該進(jìn)程是否進(jìn)人阻塞狀態(tài)

D.阻塞該進(jìn)程，并將之插入x的阻塞隊(duì)列中

29.當(dāng)定時(shí)器產(chǎn)生時(shí)鐘中斷后，由時(shí)鐘中斷服務(wù)程序更新的部分內(nèi)容是。

I.內(nèi)核中時(shí)鐘變量的值

II.當(dāng)前進(jìn)程占用CPU的時(shí)間

HI.當(dāng)前進(jìn)程在時(shí)間片內(nèi)的剩余執(zhí)行時(shí)間

A.僅I、IIB.僅II、IHC.僅I、IIID.I、II>III

第4頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

30.系統(tǒng)總是訪問磁盤的某個(gè)磁道而不響應(yīng)對其他磁道的訪問請求,這種現(xiàn)象稱為磁臂黏著。

卜列磁盤調(diào)度算法中，不會(huì)導(dǎo)致磁臂粘著的是.

A.先來先服務(wù)（FCFS）B.最短尋道時(shí)間優(yōu)先（SSTF）

C.掃描算法（SCAN）D.循環(huán)掃描算法（CSCAN）

31.下列優(yōu)化方法中，可以提高文件訪問速度的是。

I.提前讀II.為文件分配連續(xù)的簇

III.延遲寫IV.采用磁盤高速緩存

A.僅I、nB.僅n、in

c.僅i、山、ivD.I、n、in、iv

32.在下列同步機(jī)制中，可以實(shí)現(xiàn)讓權(quán)等待的是.

A.Peterson方法B.swap指令

C.信號(hào)量方法D.TestAndSet指令

33.下列TCP/IP應(yīng)用層協(xié)議中，可以使用傳輸層無連接服務(wù)的是o

A.FTPB.DNSC.SMTPD.HTTP

34.下列選項(xiàng)中，不屬于物理層接口規(guī)范定義范疇的是o

A.接口形狀B.引腳功能C.物理地址D.信號(hào)電平

35.IEEE802.11無線局域網(wǎng)的MAC協(xié)議CSMA/CA進(jìn)行信道預(yù)約的方法是。

A.發(fā)送確認(rèn)幀B.采用二進(jìn)制指數(shù)退避

C.使用多個(gè)MAC地址D.交換RTS與CTS幀

36.主機(jī)甲采用停-等協(xié)議向主機(jī)乙發(fā)送數(shù)據(jù)，數(shù)據(jù)傳輸速率是3kbps,單向傳播延時(shí)是200

ms,忽略確認(rèn)幀的傳輸延時(shí)。當(dāng)信道利用率等于40%時(shí)，數(shù)據(jù)幀的長度為。

A.240比特B.400比特C.480比特D.800比特

37.路由器R通過以太網(wǎng)交換機(jī)S1和S2連接兩個(gè)網(wǎng)絡(luò)，R的接口、主機(jī)H1和H2的IP地

址與MAC地址如下圖所示。若H1向H2發(fā)送1個(gè)IP分組P,則H1發(fā)出的封裝P的以太網(wǎng)幀的

目的MAC地址、H2收到的封裝P的以太網(wǎng)幀的源MAC地址分別是

00-la-2b-3c-4d-5200-a1-b2-c3-d4-62

00-la-2b-3c-4d-5200-aI-b2-c3-d4-62

A.00-a1-b2-c3-d4-6200-1a-2b-3c-4d?52

B.00-a1-b2-c3-d4-6200-a1-b2-c3-d4-61

C.00-1a-2b-3c-4d-5100-1a-2b-3c-4d-52

第5頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

D.00-1a-2b-3c-4d-51.00-a1-b2-c3-d4-61

38.某路由表中有轉(zhuǎn)發(fā)接口相同的4條路由表項(xiàng)，其目的網(wǎng)絡(luò)地址分別為/21、

/21,/21和/21,將該4條路由聚合后的目的網(wǎng)絡(luò)地址為.

A./19B./20

C./19D./20

39.UDP協(xié)議實(shí)現(xiàn)分用(demultiplexing)時(shí)所依據(jù)的頭部字段是。

A.源端口號(hào)B.目的端口號(hào)C.長度D.校驗(yàn)和

40.無需轉(zhuǎn)換即可由SMTP協(xié)議直接傳輸?shù)膬?nèi)容是。

A.JPEG圖像B.MPEG視頻C.EXE文件D.ASCII文本

二、綜合應(yīng)用題：第41?47小題，共70分。

41.(13分)給定一個(gè)含n(n、件整數(shù)的數(shù)組，請?jiān)O(shè)計(jì)一個(gè)在時(shí)間上盡可能高效的算法，找出數(shù)

組中未出現(xiàn)的最小正整數(shù)。例如，數(shù)組｛-5,3,2,3｝中未出現(xiàn)的最小正整數(shù)是1；數(shù)組｛1,2,3｝中未出

現(xiàn)的最小正整數(shù)是4。要求：

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

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

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

42.(12分)擬建設(shè)一個(gè)光通信骨干網(wǎng)絡(luò)連通BJ,CS、XA、QD、JN、NJ、TL和WH等8個(gè)

城市，題42圖中無向邊上的權(quán)值表示兩個(gè)城市間備選光纜的鋪設(shè)費(fèi)用。

請回答下列問題。

(1)僅從鋪設(shè)費(fèi)用角度出發(fā)，給出所有可能的最經(jīng)濟(jì)的光纜鋪設(shè)方案(用帶權(quán)圖表示)，并

第6頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

計(jì)算相應(yīng)方案的總費(fèi)用。

(2)題42圖可采用圖的哪一種存儲(chǔ)結(jié)構(gòu)？給出求解問題(1)所使用的算法名稱。

(3)假設(shè)每個(gè)城市采用一個(gè)路由器按(1)中得到的最經(jīng)濟(jì)方案組網(wǎng)，主機(jī)H1直接連接在

TL的路由器上，主機(jī)H2直接連接在BJ的路由器上。若H1向H2發(fā)送一個(gè)TTL=5的IP分組，

則H2是否可以收到該IP分組？

43.(8分)假定計(jì)算機(jī)的主頻為500MHz,CPI為4?，F(xiàn)有設(shè)備A和B,其數(shù)據(jù)傳輸率分別為

2MB/S和40MB/S,對應(yīng)I/O接口中各有一個(gè)32位數(shù)據(jù)緩沖寄存器。請回答下列問題，要求給出

計(jì)算過程。

(1)若設(shè)備A采用定時(shí)查詢I/O方式，每次輸入/輸出都至少執(zhí)行10條指令。設(shè)備A最多

間隔多長時(shí)間查詢?次才能不丟失數(shù)據(jù)？CPU用于設(shè)備A輸入/輸出的時(shí)間占CPU總時(shí)間的百分

比至少是多少？

(2)在中斷I/O方式下，若每次中斷響應(yīng)和中斷處理的總時(shí)鐘周期數(shù)至少為400,則設(shè)備B

能否采用中斷I/O方式？為什么？

(3)若設(shè)備B采用DMA方式，每次DMA傳送的數(shù)據(jù)塊大小1000B,CPU用于DMA預(yù)處

理和后處理的總時(shí)鐘周期數(shù)為500,則CPU用于設(shè)備B輸人/輸出的時(shí)間占CPU總時(shí)間的百分比

最多是多少？

44.(15分)某計(jì)算機(jī)采用頁式虛擬存儲(chǔ)管理方式，按字節(jié)編址。CPU進(jìn)行存儲(chǔ)訪問的過程如

題44圖所示。

題44圖

根據(jù)題44圖回答下列問題。

(1)主存物理地址占多少位？

(2)TLB采用什么映射方式？TLB用SRAM還是DRAM實(shí)現(xiàn)？

(3)Cache采用什么映射方式？若Cache采用LRU替換算法和回寫(WriteBack)策略，

則Cache每行中除數(shù)據(jù)(Data)、Tag和有效位外，還應(yīng)有哪些附加位？Cache總?cè)萘渴嵌嗌?？Cache

第7頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

中有效位的作用是什么？

（4）若CPU給出的虛擬地址為0008C040H,則對應(yīng)的物理地址是多少？是否在Cache中命

中？說明理由，若CPU給出的虛擬地址為0007C260H,則該地址所在主存塊映射到的Cache組

號(hào)是多少？

45.（8分）請根據(jù)題44圖給出的虛擬儲(chǔ)管理方式，回答下列問題。

（1）某虛擬地址對應(yīng)的頁目錄號(hào)為6,在相應(yīng)的頁表中對應(yīng)的頁號(hào)為6,頁內(nèi)偏移量為8,

該虛擬地址的十六進(jìn)制表示是什么？

（2）寄存器PDBR用于保存當(dāng)前進(jìn)程的頁目錄起始地址，該地址是物理地址還是虛擬地址？

進(jìn)程切換時(shí)，PDBR的內(nèi)容是否會(huì)變化？說明理由。同一進(jìn)程的線程切換時(shí)，PDBR的內(nèi)容是否

會(huì)變化？說明理由。

（3）為了支持改進(jìn)型CLOCK置換算法，需要在頁表項(xiàng)中設(shè)置哪些字段？

46.（7分）某文件系統(tǒng)采用索引節(jié)點(diǎn)存放文件的屬性和地址信息，簇大小為4KB。每個(gè)文件索

引節(jié)點(diǎn)占64B,有11個(gè)地址項(xiàng)，其中直接地址項(xiàng)8個(gè)，-級、二級和三級間接地址項(xiàng)各1個(gè)，每

個(gè)地址項(xiàng)長度為4Bo請回答下列問題。

（1）該文件系統(tǒng)能支持的最大文件長度是多少？（給出計(jì)算表達(dá)式即可）

（2）文件系統(tǒng)用1M（1M=220）個(gè)簇存放文件索引節(jié)點(diǎn)，用512M個(gè)簇存放文件數(shù)據(jù)。若一

個(gè)圖像文件的大小為5600B,則該文件系統(tǒng)最多能存放多少個(gè)這樣的圖像文件？

（3）若文件F1的大小為6KB,文件F2的大小為40KB,則該文系統(tǒng)獲取F1和F2最后一

個(gè)簇的簇號(hào)需要的時(shí)間是否相同？為什么？

47.（7分）某公司網(wǎng)絡(luò)如題47圖所示。IP地址空間/24被均分給銷售部和技術(shù)部兩

個(gè)子網(wǎng)，并已分別為部分主機(jī)和路由器接口分配了IP地址，銷售部子網(wǎng)的MTU=1500B,技術(shù)部

子網(wǎng)的MTU=800B。

（1）銷售部子網(wǎng)的廣播地址是什么？技術(shù)部子網(wǎng)的子網(wǎng)地址是什么？若每個(gè)主機(jī)僅分配一

個(gè)IP地址，則技術(shù)部子網(wǎng)還可以連接多少臺(tái)主機(jī)？

（2）假設(shè)主機(jī)向主機(jī)08發(fā)送?個(gè)總長度為1500B的IP分組，IP分

組的頭部長度為20B,路由器在通過接口F1轉(zhuǎn)發(fā)該IP分組時(shí)進(jìn)行了分片。若分片時(shí)盡可能分為

最大片，則一個(gè)最大IP分片封裝數(shù)據(jù)的字節(jié)數(shù)是多少？至少需要分為幾個(gè)分片？每個(gè)分片的片偏

移量是多少？

第8頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

2018年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案

一、單項(xiàng)選擇題

1.B2.C3.A4.A5.A6.C7.D8.B

9.C10.D11.A12.D13.C14.A15.A16.B

17.C18.B19.A20.D21.B22.023.C24.D

25.B26.A27.C28.D29.D30.A31.D32.C

33.B34.C35.D36.D37.D38.C39.B40.D

二、綜合應(yīng)用題

41.解析：

1)題目要求算法時(shí)間上盡可能高效，因此采用空間換時(shí)間的辦法。分配一個(gè)用于標(biāo)記的數(shù)

組B[n],用來記錄A中是否出現(xiàn)了1~n中的正整數(shù)，B⑼對應(yīng)正整數(shù)1,對應(yīng)正整數(shù)n,初

始化B中全部為0.由于A中含有n個(gè)整數(shù)，因此可能返回的值是1~n+1,當(dāng)A中n個(gè)數(shù)恰好為

1~n時(shí)返回n+1。當(dāng)數(shù)組A中出現(xiàn)了小于等于0或者大于n的值時(shí)，會(huì)導(dǎo)致1~n中出現(xiàn)空余位置，

返回結(jié)果必然在1~門中，因此對于A中出現(xiàn)了小于等于。或者大于n的值可以不采取任何操作。

經(jīng)過以上分析可以得出算法流程：從A[0]開始遍歷A,若0<A[i]<=n,則令B[A[i]-1]=1；否

則不做操作。對A遍歷結(jié)束后，開始遍歷數(shù)組B,若能查找到第?個(gè)滿足B[i]==0的下標(biāo)i,返回

i+1即為結(jié)果，此時(shí)說明A中未出現(xiàn)的最小正整數(shù)在1~n之間。若B[i]全部不為0,返回i+1(跳

出循環(huán)時(shí)i=n,i+1等于n+1),此時(shí)說明A中未出現(xiàn)的最小正整數(shù)是n+1。

intfindMissMin(intA[],intn)

{

inti,*B;//標(biāo)記數(shù)組

B=(int*)malloc(sizeof(int)*n);//分配空間

memset(B,0,sizeof(int)*n);//賦初值為0

for(i=0;i<n;i++)

if(A[i]>0&&A[i]<=n)//若A[i]的值介于1~n，則標(biāo)記數(shù)組B

B[A[i]-1]=1;

for(i=0;i<n;i++)//掃描數(shù)組B,找到目標(biāo)值

if(B[i]==0)break;

returni+1;//返回結(jié)果

}

3)時(shí)間復(fù)雜度：遍歷A一次，遍歷B-次，兩次循環(huán)內(nèi)操作步驟為0(1)量級，因此時(shí)間復(fù)

雜度為O(n).空間復(fù)雜度：額外分配了B[n],空間復(fù)雜度為O(n)。

42.解析：

1)為了求解最經(jīng)濟(jì)的方案，可以把問題抽象為求無向帶權(quán)圖的最小生成樹?？梢圆捎檬謩?dòng)

prim算法或kruskal算法作圖。注意本題最小生成樹有兩種構(gòu)造，如下圖所示。

第9頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

方案的總費(fèi)用為16。

2）存儲(chǔ)題中的圖可以采用鄰接矩陣（或鄰接表）。構(gòu)造最小生成樹采用Prim算法（或kruskal

算法）.

3）TTL=5,即IP分組的生存時(shí)間（最大傳遞距離）為5,方案1中TL和BJ的距離過遠(yuǎn)，

TTL=5不足以讓IP分組從H1傳送到H2,因此H2不能收到IP分組。而方案2中TL和BJ鄰近，

H2可以收到IP分組。

43.解析：

1）程序定時(shí)向緩存端口查詢數(shù)據(jù)，由于緩存端口大小有限，必須在傳輸完端口大小的數(shù)據(jù)

時(shí)訪問端口，以防止部分?jǐn)?shù)據(jù)沒有被及時(shí)讀取而丟失。設(shè)備A準(zhǔn)備32位數(shù)據(jù)所用時(shí)間為

4B/2MB=2us,所以最多每隔2us必須查詢一次，每秒的查詢次數(shù)至少是1s/2us=5X）5）每秒CPU

用于設(shè)備A輸入/輸出的時(shí)間至少為5X105x1。沖=2XI。7個(gè)時(shí)鐘周期，占整個(gè)CPU時(shí)間的百分比至

少是2X107/500M=4%。

2）中斷響應(yīng)和中斷處理的時(shí)間為400X（1/500M）=0.8us,這時(shí)只需判斷設(shè)備B準(zhǔn)備32位數(shù)

據(jù)要多久，如果準(zhǔn)備數(shù)據(jù)的時(shí)間小于中斷響應(yīng)和中斷處理的時(shí)間，那么數(shù)據(jù)就會(huì)被刷新、造成丟

失。經(jīng)過計(jì)算，設(shè)備B準(zhǔn)備32位數(shù)據(jù)所用時(shí)間為4B/40MB=0.1us,因此，設(shè)備B不適合采用中

斷I/O方式。

3）在DMA方式中，只有預(yù)處理和后處理需要CPU處理，數(shù)據(jù)的傳送過程是由DMA控制。

設(shè)備B每秒的DMA次數(shù)最多為40MB/1000B=40000,CPU用于設(shè)備B輸入/輸出的時(shí)間最多為

40000>500=2Xl（f個(gè)時(shí)鐘周期，占CPU總時(shí)間的百分比最多為2X107/500M=4%?

44.解析：

1）物理地址由實(shí)頁號(hào)和頁內(nèi)地址拼接，因此其位數(shù)為16+12=28；或直接可得20+3+5=28。

2）TLB采用全相聯(lián)映射，可以把頁表內(nèi)容調(diào)入任一塊空TLB項(xiàng)中，TLB中每項(xiàng)都有一個(gè)比

第10頁，共12頁

2018年計(jì)算機(jī)考研真題及參考答案

較器，沒有映射規(guī)則，只要空閑就行。TLB采用靜態(tài)存儲(chǔ)器SRAM,讀寫速度快，但成本高，多

用于容量較小的高速緩沖存儲(chǔ)器。

3）圖中可以看到，Cache中每組有兩行，故采用2路組相聯(lián)映射方式。

因?yàn)槭?路組相聯(lián)并采用LRU替換算法，所以每行（或每組）需耍1位LRU位；因?yàn)椴捎?/p>

回寫策略，所以每行有1位修改位（臟位），根據(jù)臟位判斷數(shù)據(jù)是否被更新，如果臟位為1則需

要寫回內(nèi)存。

28位物理地址中Tag字段占20位,組索引字段占3位，塊內(nèi)偏移地址占5位，故Cache共

有23=8組，每組2行，每行有2、32B：故Cache總?cè)萘繛?X2X（20+1+1+1+32鄧）=4464位=558

字節(jié)。

Cache中有效位用來指出所在Cache行中的信息是否有效。

4）虛擬地址分為兩部分：虛頁號(hào)、頁內(nèi)地址；物理地址分為兩部分：實(shí)頁號(hào)、頁內(nèi)地址。

利用虛擬地址的虛頁號(hào)部分去查找TLB表（缺失時(shí)從頁表調(diào)入），將實(shí)頁號(hào)取出后和虛擬地址的

頁內(nèi)地址拼接，就形成了物理地址。虛頁號(hào)008cH恰好在TLB表中對應(yīng)實(shí)頁號(hào)0040H（有效位

為1，說明存在），虛擬地址的后3位為頁內(nèi)地址040H,則對應(yīng)的物理地址是0040040H。

物理地址為0040040H,其中高20位00400H為標(biāo)志字段，低5位00000B為塊內(nèi)偏移量，

中間3位010B為組號(hào)2,因此將00400H與Cache中的第2組兩行中的標(biāo)志字段同時(shí)比較，可以

看出，雖然有一個(gè)Cache行中的標(biāo)志字段與00400H相等，但對應(yīng)的有效位為0,而另一Cache

行的標(biāo)志字段與00400H不相等，故訪問Cache不命中。

因?yàn)槲锢淼刂返牡?2位與虛擬地址低12位相同，即為001001100000B。根據(jù)物理地址的

結(jié)構(gòu)，物理地址的后八位01100000B的前三位011B是組號(hào)，因此該地址所在的主存映射到Cache

組號(hào)為3。

45.解析：

1）由圖可知，地址總長度為32位，高20位為虛頁號(hào)，低12位為頁內(nèi)地址。且虛頁號(hào)高10

位為頁目錄號(hào)，低10位為頁號(hào)。展開成二進(jìn)制則表示為：

00000001100000000110000000001000B

I_11_，I_____________I

III

頁目錄于