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

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

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

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

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

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

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

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

A.-15

B.15

C.-20

D.20

2、現(xiàn)有隊列Q與棧S，初始時Q中的元素依次是1，2，3，4，5，6(1在隊頭)，S為空。若僅允許下列3種操作：① 出隊并輸出出隊元素；② 出隊并將出隊元素入棧；③ 出棧并輸出出棧元素，則不能得到的輸出序列是（  ）。

A.1，2，5，6，4，3

B.2，3，4，5，6，1

C.3，4，5，6，1，2

D.6，5，4，3，2，1

3、設(shè)有一個12×12的對稱矩陣M，將其上三角部分的元素mi,j(1<=i<=j<=12)按行優(yōu)先存入C語言的一維數(shù)組N中，元素m6,6在N中的下標(biāo)是（  ）。

A.50

B.51

C.55

D.66

4、設(shè)一棵非空完全二叉樹T的所有葉結(jié)點(diǎn)均位于同一層，且每個非葉結(jié)點(diǎn)都有2個子結(jié)點(diǎn)。若T有k個葉結(jié)點(diǎn)，則T的結(jié)點(diǎn)總數(shù)是（  ）。

A.2k-1

B.2k

C.k2

D.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，100

B.00，100，110，000，0010，01

C.10，1011，11，0011，00，010

D.0011，10，11，0010，01，000

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

A.x1<x2<x5

B.x1<x4<x5

C.x3<x5<x4

D.x4<x3<x5

7、下列選項(xiàng)中，不是如下有向圖的拓?fù)湫蛄械氖牵? ）。

A.1，5，2，3，6，4

B.5，1，2，6，3，4

C.5，1，2，3，6，4

D.5，2，1，6，3，4

8、高度為5的3階B樹含有的關(guān)鍵字個數(shù)至少是（  ）。

A.15

B.31

C.62

D.242

9、現(xiàn)有長度為7、初始為空的散列表HT，散列函數(shù)H(k)=k%7，用線性探測再散列法解決沖突。將關(guān)鍵字22，43，15依次插入到HT后，查找成功的平均查找長度是（  ）。

A.1、5

B.1、6

C.2

D.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，1

B.3，2

C.5，2

D.5，3

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

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ī)中數(shù)據(jù)采用二進(jìn)制編碼表示，其主要原因是（  ）。

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

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

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

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅲ

C.僅Ⅱ、Ⅲ

D.Ⅰ、Ⅱ和Ⅲ

13、假定帶符號整數(shù)采用補(bǔ)碼表示，若int型變量x和y的機(jī)器數(shù)分別是FFFF FFDFH和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-126

B.1.0X2-127

C.1.0X2-128

D.1.0X2-149

15、某32位計算機(jī)按字節(jié)編址，采用小端（Little Endian）方式。若語令“int i=0”對應(yīng)指令的機(jī)器代碼為“C745FC00000000”，則語句“int i=-64”對應(yīng)指令的機(jī)器代碼是（  ）。

A.C7 45 FC C0 FF FF FF

B.C7 45 FC 0C FF FF FF

C.C7 45 FC FF FF FF C0

D.C7 45 FC FF FF FF 0C

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

A.1110 1100、1110 1100

B.0110 1100、1110 1100

C.1110 1100、0110 1100

D.0110 1100、0110 1100

17、假定DRAM芯片中存儲陣列的行數(shù)為r、列數(shù)為c，對于一個2K×1位的DRAM芯片，為保證其地址引腳數(shù)最少，并盡量減少刷新開銷，則r、c的取值分別是（  ）。

A.2048、1

B.64、32

C.32、64

D.1、2048

18、按字節(jié)編址的計算機(jī)中，某double型數(shù)組A的首地址為2000H，使用變址尋址和循環(huán)結(jié)構(gòu)訪問數(shù)組A，保存數(shù)組下標(biāo)的變址寄存器初值為0，每次循環(huán)取一個數(shù)組元素，其偏移地址為變址值乘以sizeof(double)，取完后變址寄存器內(nèi)容自動加1。若某次循環(huán)所取元素的地址為2100H，則進(jìn)入該次循環(huán)時變址寄存器的內(nèi)容是（  ）。

A.25

B.32

C.64

D.100

19、減法指令“sub R1,R2,R3”的功能為“(R1)-(R2)→R3"，該指令執(zhí)行后將生成進(jìn)位/借位標(biāo)志CF和溢出標(biāo)志OF。若(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，則該減法指令執(zhí)行后，CF與OF分別為（  ）。

A.CF=0，OF=0

B.CF=1，OF=0

C.CF=0，0F=1

D.CF=1，OF=1

20、若某計算機(jī)最復(fù)雜指令的執(zhí)行需要完成5個子功能，分別由功能部件A~E實(shí)現(xiàn)，各功能部件所需時間分別為80ps、50ps、50ps、70ps和50ps，采用流水線方式執(zhí)行指令，流水段寄存器延時為20ps，則CPU時鐘周期至少為（  ）。

A.60ps

B.70ps

C.80ps

D.100ps

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

Ⅰ.增加總線寬度

Ⅱ.提高總線工作頻率

Ⅲ.支持突發(fā)傳輸

Ⅳ.采用地址/數(shù)據(jù)線復(fù)用

A.僅Ⅰ、Ⅱ

B.僅Ⅰ、Ⅱ、Ⅲ

C.僅Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

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

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

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

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

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

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

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

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

Ⅲ、需要運(yùn)行在多CPU的硬件平臺上

A.僅Ⅰ

B.僅Ⅱ

C.僅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

24、某系統(tǒng)采用基于優(yōu)先權(quán)的非搶占式進(jìn)程調(diào)度策略，完成一次進(jìn)程調(diào)度和進(jìn)程切換的系統(tǒng)時間開銷為1μs。在T時刻就緒隊列中有3個進(jìn)程P1、P2和P3，其在就緒隊列中的等待時間、需要的CPU時間和優(yōu)先權(quán)如下表所示。

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

A.54μs

B.73μs

C.74μs

D.75μs

25、屬于同一進(jìn)程的兩個線程thread1和thread2并發(fā)執(zhí)行，共享初值為0的全局變量x。thread1和thread2實(shí)現(xiàn)對全局變量x加1的機(jī)器級代碼描述如下。

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

A.1

B.2

C.3

D.4

26、假設(shè)系統(tǒng)中有4個同類資源，進(jìn)程P1、P2和P3需要的資源數(shù)分別為4、3和1，P1、P2和P3已申請到的資源數(shù)分別為2、1和0，則執(zhí)行安全性檢測算法的結(jié)果是（  ）。

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

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

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

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

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

Ⅰ、進(jìn)程P申請臨界資源

Ⅱ、進(jìn)程P從磁盤讀取數(shù)據(jù)

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

A.僅Ⅰ

B.僅Ⅱ

C.僅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

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

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

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

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

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

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

Ⅰ、內(nèi)核中時鐘變量的值

Ⅱ、當(dāng)前進(jìn)程占用CPU的值

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

A.僅Ⅰ、Ⅱ

B.僅Ⅱ、Ⅲ

C.僅Ⅰ、Ⅲ

D.Ⅰ、Ⅱ、Ⅲ 

30、系統(tǒng)總是訪問磁盤的某個磁道而不響應(yīng)對其他磁道的訪問請求，這種現(xiàn)象稱為磁臂黏著。下列磁盤調(diào)度算法中，不會導(dǎo)致磁臂粘著的是（  ）。

A.先來先服務(wù)（FCFS）

B.最短尋道時間優(yōu)先（SSTF）

C.掃描算法（SCAN）

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

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

Ⅰ、提前讀

Ⅱ、為文件分配連續(xù)的簇

Ⅲ、延遲寫

Ⅳ、采用磁盤高速緩存

A.僅Ⅰ、Ⅱ

B.僅Ⅱ、Ⅲ

C.僅Ⅰ、Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ、Ⅳ

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

A.Peterson方法

B.swap指令

C.信號量方法

D.TestAndSet指令

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

A.FTP

B.DNS

C.SMTP

D.HTTP

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

A.接口形狀

B.引腳功能

C.物理地址

D.信號電平

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

A.發(fā)送確認(rèn)幀

B.采用二進(jìn)制指數(shù)退避

C.使用多個MAC地址

D.交換RTS與CTS幀

36、主機(jī)甲采用停-等協(xié)議向主機(jī)乙發(fā)送數(shù)據(jù)，數(shù)據(jù)傳輸速率是3kbps，單向傳播延時是200ms，忽略確認(rèn)幀的傳輸延時。當(dāng)信道利用率等于40%時，數(shù)據(jù)幀的長度為（  ）。

A.240比特

B.400比特

C.480比特

D.800比特

37、路由器R通過以太網(wǎng)交換機(jī)S1和S2連接兩個網(wǎng)絡(luò)，R的接口、主機(jī)H1和H2的IP地址與MAC地址如下圖所示。若H1向H2發(fā)送1個IP分組P，則H1發(fā)出的封裝P的以太網(wǎng)幀的目的MAC地址、H2收到的封裝P的以太網(wǎng)幀的源MAC地址分別是（  ）。

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

B.00-a1-b2-c3-d4-62，00-a1-b2-c3-d4-61

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

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

38、某路由表中有轉(zhuǎn)發(fā)接口相同的4條路由表項(xiàng)，其目的網(wǎng)絡(luò)地址分別為35.230.32.0/21，35.230.40.0/21，35.230.48.0/21和35.230.56.0/21，將該4條路由聚合后的目的網(wǎng)絡(luò)地址為（  ）。

A.35.230.0.0/19

B.35.230.0.0/20

C.35.230.32.0/19

D.35.230.32.0/20

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

A.源端口號

B.目的端口號

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分）給定一個含n（n>=1）個整數(shù)的數(shù)組，請設(shè)計一個在時間上盡可能高效的算法，找出數(shù)組中未出現(xiàn)的最小正整數(shù)。例如，數(shù)組{-5，3，2，3}中未出現(xiàn)的最小正整數(shù)是1；數(shù)組{1，2，3}中未出現(xiàn)的最小正整數(shù)是4。要求：

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

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

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

42、（12分）擬建設(shè)一個光通信骨干網(wǎng)絡(luò)連通BJ、CS、XA、QD、JN、NJ、TL和WH等8個城市，題42圖中無向邊上的權(quán)值表示兩個城市間備選光纜的鋪設(shè)費(fèi)用。

請回答下列問題。

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

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

（3）假設(shè)每個城市采用一個路由器按（1）中得到的最經(jīng)濟(jì)方案組網(wǎng)，主機(jī)H1直接連接在TL的路由器上，主機(jī)H2直接連接在BJ的路由器上。若H1向H2發(fā)送一個TTL=5的IP分組，則H2是否可以收到該IP分組？

43、（8分）假定計算機(jī)的主頻為500MHz，CPI為4?，F(xiàn)有設(shè)備A和B，其數(shù)據(jù)傳輸率分別為2MBps和40MBps，對應(yīng)I/O接口中各有一個32位數(shù)據(jù)緩沖寄存器。請回答下列問題，要求給出計算過程。

（1）若設(shè)備A采用定時查詢I/O方式，每次輸入/輸出都至少執(zhí)行10條指令。設(shè)備A最多間隔多長時間查詢一次才能不丟失數(shù)據(jù)？CPU用于設(shè)備A輸入輸出的時間占CPU總時間的百分比至少是多少？

（2）在中斷I/O方式下，若每次中斷響應(yīng)和中斷處理的總時鐘周期數(shù)至少為400，則設(shè)備B能否采用中斷I/O方式？為什么？

（3）若設(shè)備B采用DMA方式，每次DMA傳送的數(shù)據(jù)塊大小1000B，CPU用于DMA預(yù)處理和后處理的總時鐘周期數(shù)為500，則CPU用于設(shè)備B輸入/輸出的時間占CPU總時間的百分比最大是多少？

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

題44圖

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

（1）主存物理地址占多少位？

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

（3）Cache采用什么映射方式？若Cache采用LRU替換算法和回寫（Write Back）策略，則Cache每行中除數(shù)據(jù)（Data）、Tag和有效位外，還應(yīng)有哪些附加位？Cache總?cè)萘渴嵌嗌?？Cache中有效位的作用是什么？

（4）若CPU給出的虛擬地址為0008C040H，則對應(yīng)的物理地址是多少？是否在Cache中命中？說明理由，若CPU給出的虛擬地址為0007C260H，則該地址所在主存塊映射到的Cache組號是多少？

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

（1）某虛擬地址對應(yīng)的頁目錄號為6，在相應(yīng)的頁表中對應(yīng)的頁號為6，頁內(nèi)偏移量為8，該虛擬地址的十六進(jìn)制表示是什么？

（2）寄存器PDBR用于保存當(dāng)前進(jìn)程的頁目錄起始地址，該地址是物理地址還是虛擬地址？進(jìn)程切換時，PDBR的內(nèi)容是否會變化？說明理由。同一進(jìn)程的線程切換時，PDBR的內(nèi)容是否會變化？說明理由。

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

46、（7分）某文件系統(tǒng)采用索引節(jié)點(diǎn)存放文件的屬性和地址信息，簇大小為4KB。每個文件索引節(jié)點(diǎn)占64B，有11個地址項(xiàng)，其中直接地址項(xiàng)8個，一級、二級和三級間接地址項(xiàng)各1個，每個地址項(xiàng)長度為4B。請回答下列問題。

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

（2）文件系統(tǒng)用1M（1M=220）個簇存放文件索引節(jié)點(diǎn)，用512M個簇存放文件數(shù)據(jù)。若一個圖像文件的大小為5600B，則該文件系統(tǒng)最多能存放多少個這樣的圖像文件？

（3）若文件F1的大小為6KB，文件F2的大小為40KB，則該文件系統(tǒng)獲取F1和F2最后一個簇的簇號需要的時間是否相同？為什么？

47、（7分）某公司網(wǎng)絡(luò)如題47圖所示。IP地址空間192.168.1.0/24被均分給銷售部和技術(shù)部兩個子網(wǎng)，并已分別為部分主機(jī)和路由器接口分配了IP地址，銷售部子網(wǎng)的MTU=1500B，技術(shù)部子網(wǎng)的MTU=800B。

請回答下列問題。

（1）銷售部子網(wǎng)的廣播地址是什么？技術(shù)部子網(wǎng)的子網(wǎng)地址是什么？若每個主機(jī)僅分配一個IP地址，則技術(shù)部子網(wǎng)還可以連接多少臺主機(jī)？

（2）假設(shè)主機(jī)192.168.1.1向主機(jī)192.168.1.208發(fā)送一個總長度為1500B的IP分組，IP分組的頭部長度為20B，路由器在通過接口F1轉(zhuǎn)發(fā)該IP分組時進(jìn)行了分片。若分片時盡可能分為最大片，則一個最大IP分片封裝數(shù)據(jù)的字節(jié)數(shù)是多少？至少需要分為幾個分片？每個分片的片偏移量是多少？