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

2018年全國(guó)碩士研究生入學(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)從與中依次彈出兩個(gè)操作數(shù)a和b；

(2)從S2中彈出一個(gè)運(yùn)算符。p；

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

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

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

用3次F()后，Si棧頂保存的值是。

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ì)元素人棧；③出棧并輸出出棧元素，

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

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的對(duì)稱矩陣M,將其上三角部分的元素mi.j(l<i<j<12)按行優(yōu)先存人C

語(yǔ)言的一維數(shù)組N中，元素儂,6在N中的下標(biāo)是o

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

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

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

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

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

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

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

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

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

A.X1<X2<X5

7.下列選項(xiàng)中，不是如下有向圖的拓?fù)湫蛄械氖?/p>

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

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)有長(zhǎng)度為7、初始為空的散列表HT,散列函數(shù)H(k)=k%7,用線性探測(cè)再散列法解決

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

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

10.對(duì)初始數(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),則兩趟排序采用的

增量(間隔)依次是o

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

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

A.6,1,7,9,8,4,5—6,9,7,1,8,4,5—9,6,7,1,8,4,5—9,8,7,1,6,4,5

B.6,9,5,1,8,4,7—6,9,7,1,8,4,5->9,6,7,1,8,4,5->9,8,7,1,6,4,5

C.6,9,5,1,8,4,7—9,6,5,1,8,4,7—9,6,7,1,8,4,5—9,8,7,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,1,7,4,5

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

1.二進(jìn)制的運(yùn)算規(guī)則簡(jiǎn)單

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

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

A.僅I、IIB.僅1、川c.僅n、niD.i、i［和in

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

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

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

A.1.0x2-126B.1.0x2-127C.1.0x2-128D.1.0x2-149

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

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

A.C745FCCOFFFFFFB.C745FCOCFFFFFF

C.C745FCFFFFFFCOD.C745FCFFFFFFOC

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

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

A.11101100^11101100B.01101100,11101100

C.11101100,01101100D.01101100s01101100

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

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

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.減法指令％此1<1,1<2,1<3”的功能為“61)-(R2)-R3"，該指令執(zhí)行后將生成進(jìn)位/借

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

后，CF與OF分別為。

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

C.CF=0,0F=lD.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,則CPU時(shí)鐘周期至少為,

A.60psB.70psC.80psD.lOOps

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

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

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

A.僅I、nB.僅I、n、ni

C.僅III、IVDJ、n、HI和IV

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

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

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

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

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

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

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

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

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

A.僅IB.僅IIC.僅I、IID.1、II、III

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

時(shí)間開銷為IJJS。在T時(shí)刻就緒隊(duì)列中有3個(gè)進(jìn)程Pi、P?和P3,其在就緒隊(duì)列中的等待時(shí)間、需

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

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

Pl30Ps12ps10

P215ps24ps30

P318ps36ps20

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

為。

A.54HsB.73psC.74psD.75Hs

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

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

threadlthread2

movRI,x//(x)-RImovR2,x//(x)—>R2

incRI//(RI)+1-?RIincR2〃(R2)+1TR2

movx,RI//(RI)—?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,P2

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

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

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

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

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

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

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

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

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

A.僅IB.僅nc.僅I、nD.I、ii、in

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

A.實(shí)現(xiàn)對(duì)變量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)容是

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

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

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

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

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

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

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

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

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

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

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

A.僅I、nB.僅n、m

c.僅i、ni、ivD.i、n、山、iv

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

A.Peterson方法B.swap指令

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

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

A.FTPB.DNSC.SMTPD.HTTP

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

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

35.IEEE802.11無(wú)線局域網(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ù)幀的長(zhǎng)度為o

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-1a-2b-3c-4d-5200-a1-b2-c3-d4-62

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

A.00-al-b2-c3-d4-62.00-la-2b-3c-4d-52

B.00-al-b2-c3-d4-62、00-al-b2-c3-d4-61

C.00-1a-2b-3c-4d-51>00-la-2b-3c-4d-52

D.00-1a-2b-3c-4d-51、00-al-b2-c3-d4-61

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

/2K/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.長(zhǎng)度D.校驗(yàn)和

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

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

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

41.(13分)給定一個(gè)含n(n*)個(gè)整數(shù)的數(shù)組，請(qǐng)?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++語(yǔ)言描述算法，關(guān)鍵之處給出注釋。

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

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

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

請(qǐng)回答下列問題。

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

計(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,對(duì)應(yīng)I/O接口中各有一個(gè)32位數(shù)據(jù)緩沖寄存器。請(qǐng)回答下列問題，要求給出

計(jì)算過程。

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

間隔多長(zhǎng)時(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ī)采用頁(yè)式虛擬存儲(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

中有效位的作用是什么？

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

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

號(hào)是多少？

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

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

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

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

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

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

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

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

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

個(gè)地址項(xiàng)長(zhǎng)度為4B。請(qǐng)回答下列問題。

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

(2)文件系統(tǒng)用IM(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地址空間192.168.1.0/24被均分給銷售部和技術(shù)部?jī)?/p>

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

子網(wǎng)的MTU=800Bo

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

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

(2)假設(shè)主機(jī)192.168.1.1向主機(jī)192.168.1.208發(fā)送一個(gè)總長(zhǎng)度為I500B的IP分組，IP分

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

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

移量是多少？

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.C23.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],用來(lái)記錄A中是否出現(xiàn)了l~n中的正整數(shù)，B[0]對(duì)應(yīng)正整數(shù)1,對(duì)應(yīng)正整數(shù)n,初

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

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

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

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

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

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

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

intfindMissMin(intA[]/intn)

intiz*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]的值介于則標(biāo)記數(shù)組B

B(A[i]-l]=l;

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)量級(jí)，因此時(shí)間復(fù)

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

42.解析：

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

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

方案的總費(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ù)至少是ls/2us=5xl（）5,每秒CPU

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

少是2xl07/500M=4%o

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í)間最多為

40000x500=2x107個(gè)時(shí)鐘周期，占CPU總時(shí)間的百分比最多為2X1（）7/5OOM=4%。

44.解析：

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

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

較器，沒有映射規(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行，每行有25=32B；故Cache總?cè)萘繛?x2x（20+1+1+1+32x8）=4464位=558

字節(jié)。

Cache中有效位用來(lái)指出所在Cache行中的信息是否有效。

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

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

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

為1,說(shuō)明存在），虛擬地址的后3位為頁(yè)內(nèi)地址040H,則對(duì)應(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相等，但對(duì)應(yīng)的有效位為0,而另一Cache

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

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

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

組號(hào)為3。

45.解析：

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

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

00000001100000000110000000001000B

\________JI_11________________