2020全國碩士研究生招生考試

計算機學(xué)科專業(yè)基礎(chǔ)試題參考答案

一、單項選擇題

01.C02.D03.A04.C05.B06.B07.A08.B

09.C10.B11.A12.B13.A14.D15.D16.A

17.B18.A19.C20.C21.B22.C23.B24.A

25.D26.D27.B28.D29.B30.D31.B32.C

33.C34.B35.C36.D37.A38.D39.C40.D

01.【解析】

上三角矩陣按列優(yōu)先存儲，先存儲僅1個元素的第一列，再存儲有2個元素的第二列，以

此類推。2位于左下角，對應(yīng)右上角的元素為“2.7,在小2,7之前存有

第1列：1

第2歹（I：2

第6列:6

第7列：1

前面共存有1+2+3+4+5+6+1=22個元素（數(shù)組下標(biāo)范圍為。?21）,注意數(shù)組下標(biāo)

從0開始，故m2,7在數(shù)組N中的下標(biāo)為22,即用久2在數(shù)組N中的下標(biāo)為22。

02.【解析】

按題意，出入棧操作的過程如下:

操作棧內(nèi)元素出棧元素

Pusha

Pushab

Popab

Pushac

Popac

Pushad

Pushade

Popade

故出棧序列為6,c,e。

03.【解析】

二叉樹采用順序存儲時，用數(shù)組下標(biāo)來表示結(jié)點之間的父子關(guān)系。對于一棵高度為5的二

叉樹，為了滿足任意性，其1?5層的所有結(jié)點都要被存儲起來，即考慮為一棵高度為5

的滿二叉樹，總共需要存儲單元的數(shù)量為1+2+4+8+16=31。

04.【解析】

森林尸的先根遍歷序列對應(yīng)其二叉樹T的先序遍歷序列，森林戶的中根遍歷序列對應(yīng)其二

叉樹7的中序遍歷序列。即T的先序遍歷序列為a,b,c,d,e,f,中序遍歷序列為b,a,d,f,e,

根據(jù)二叉樹T的先序序列和中序序列可以唯一確定它的結(jié)構(gòu)，構(gòu)造過程如下：

05?【解析】

顯然選項B錯誤。

06?【解析】

DFS是一個遞歸算法，在遍歷過程中，先訪問的頂點被壓入棧底。設(shè)在圖中有頂點匕，它

有后繼頂點為，即存在邊根據(jù)DFS的規(guī)則，匕入棧后，必先遍歷完其后繼頂點后

”才會出棧，也就是說片會在多之后出棧，在如題所指的過程中，片在年后打印。由于環(huán)

和學(xué)具有任意性，從上面的規(guī)律可以看出，輸出頂點的序列是逆拓撲有序序列。

07.【解析】

Kruskal算法：按權(quán)值遞增順序依次選取〃-1條邊，并保證這”-1條邊不構(gòu)成回路。初始

構(gòu)造一個僅含〃個頂點的森林；第一步，選取權(quán)值最小的邊(瓦/)加入最小生成樹；第二步,

剩余邊中權(quán)值最小的邊為(瓦田，加入最小生成樹，第二步操作后權(quán)值最小的邊(4/)不能選,

因為會與之前已選取的邊形成回路；接下來依次選取權(quán)值9,10,11對應(yīng)的邊加入最小生成

樹，此時6個頂點形成了一棵樹，最小生成樹構(gòu)造完成。按照上述過程，加到最小生成樹

的邊依次為(b,/),(b,d),(a,e),(c,e),(b,e)?其生成過程如下所示。

?031?

第二步第三步

選取邊<qe>

第四步

選取邊<C,e>選取邊<b,e>

08.【解析】

關(guān)鍵路徑是指權(quán)值之和最大而非邊數(shù)最多的路徑，故選項A錯誤。選項B正確，是關(guān)鍵路

徑的概念。無論是存在一條還是存在多條關(guān)鍵路徑，增加任一關(guān)鍵活動的時間都會延長工

程的工期，因為關(guān)鍵路徑始終是權(quán)值之和最大的那條路徑，選項C錯誤。僅有一條關(guān)鍵路

徑時，減少關(guān)鍵活動的時間會縮短工程的工期；存在多條關(guān)鍵路徑時，縮短一條關(guān)鍵活動

的時間不一定會縮短工程的工期，縮短了路徑長度的那條關(guān)鍵路徑不一定還是關(guān)鍵路徑，

選項D錯誤。

09.【解析】

這是一道簡單的概念題。堆是一棵完全樹，采用一維數(shù)組存儲，故I正確，II正確。大根

堆只要求根結(jié)點值大于左右孩子值，并不要求左右孩子值有序，HI錯誤。堆的定義是遞歸

的，所以其左右子樹也是大根堆，所以堆的次大值一定是其左孩子或右孩子，IV正確。

10.【解析】

一個4階B樹的任意非葉結(jié)點至多含有m-1=3個關(guān)鍵字，在關(guān)鍵字依次插入的過程中,

會導(dǎo)致結(jié)點的不斷分裂，插入過程如下所示。

69

插入12

■|2彳1315

得到根結(jié)點包含的關(guān)鍵字為6,9。

H.【解析】

考慮較極端的情況，對于有序數(shù)組，直接插入排序的比較次數(shù)為簡單選擇排序的比

較次數(shù)始終為1+2+…+=I正確。兩種排序方法的輔助空間都是0(1),無

差別，H錯誤。初始有序時，移動次數(shù)均為0；對于通常情況，直接插入排序每趟插入都

?032?

需要依次向后挪位，而簡單選擇排序只需與找到的最小元素交換位置，后者的移動次數(shù)少

很多，in錯誤。

12.【解析】

機器字長是指CPU內(nèi)部用于整數(shù)運算的數(shù)據(jù)通路的寬度。CPU內(nèi)部數(shù)據(jù)通路是指CPU內(nèi)

部的數(shù)據(jù)流經(jīng)的路徑及路徑上的部件，主要是CPU內(nèi)部進行數(shù)據(jù)運算、存儲和傳送的部件,

這些部件的寬度基本上要一致才能相互匹配。因此，機器字長等于CPU內(nèi)部用于整數(shù)運算

的運算器位數(shù)和通用寄存器寬度。

13?【解析】

C8000000H=11001000000000000000000000000000.

將其轉(zhuǎn)換為對應(yīng)的float型或int型：

1)為float型時，尾數(shù)隱藏最高位1,數(shù)符為1表示負數(shù)，階碼10010000=27+24=128+16,

再減去偏置值127得到17,算出x值為-2%

2)為int型時，帶符號補碼，為負數(shù)，數(shù)值部分取反加1,得01110000000000000000000

00000000,算出x值為-7x2”。

14.【解析】

在32位計算機中，按字節(jié)編址，根據(jù)小端方式和按邊界對齊的定義，給出變量a的存放方

式如下：

地址2020FE00H2020FE01H2020FE02H2020FE03H

未知未知E11

說明xl(LSB)xl(MSB)

地址2020FE04H2020FE05H2020FE06H2020FE07H

00HOOH34H12H

說明x2(LSB)x2(MSB)

于是，34H所在存儲單元的地址為2020FE06H,

15.【解析】

Cache由SRAM組成：TLB通常由相聯(lián)存儲器組成，也可由SRAM組成。DRAM需要不

斷刷新，性能偏低，不適合組成TLB和Cache.選項A、B和C都是TLB和Cache的特點。

16.【解析】

48條指令需要6位操作碼字段(2$<48<26),4種尋址方式需要2位尋址特征位(4=22),

還剩16-6-2=8位作為地址碼，故直接尋址范圍為0?255。注意，主存地址不能為負。

17.【解析】

CPI表示執(zhí)行指令所需的時鐘周期數(shù)。對于一個程序或一臺機器來說，其CP1指執(zhí)行該程

序或機器指令集中的所有指令所需的平均時鐘周期數(shù)。對于單周期CPU,令指令周期=時

鐘周期，CPI=1,I正確。對于多周期CPU,CPU的執(zhí)行過程分成幾個階段，每個階段用

一個時鐘去完成，每種指令所用的時鐘數(shù)可以不同，CPI>I,n錯誤。對于基本流水線CPU,

讓每個時鐘周期流出一條指令，CPI=1,HI正確。超標(biāo)量流水線CPU在每個時鐘周期內(nèi)

?033?

并發(fā)執(zhí)行多條獨立的指令，每個時鐘周期流出多條指令，CPI<LIV錯誤。

18.【解析】

自陷是一種內(nèi)部異常，A錯誤。在80x86中，用于程序調(diào)試的“斷點設(shè)置”功能是通過“自

陷”方式實現(xiàn)的，選項B正確。執(zhí)行到自陷指令時，無條件或有條件地自動調(diào)出操作系統(tǒng)

內(nèi)核程序進行執(zhí)行，選項C正確。CPU執(zhí)行“陷阱指令”后，會自動地根據(jù)不同“陷阱”

類型進行相應(yīng)的處理，然后返回到“陷阱指令”的下一條指令執(zhí)行，選項D正確。

19.【解析】

每個時鐘周期傳送2次，故每秒傳送的次數(shù)=時鐘頻率x2=2.4Gx2/s。

總線帶寬=每秒傳送次數(shù)'28'2=2.46、2*28、2/5=19.268/$。

題中已給出總線帶寬公式，降低了難度。公式中的“x2B”是因為每次傳輸16位數(shù)據(jù)，“x2”

是因為采用點對點全雙工總線，兩個方向可同時傳輸信息。

20.【解析】

訪存時缺頁屬于內(nèi)部異常，I錯誤；定時器到時描述的是時鐘中斷，屬于外部中斷，II正確；

網(wǎng)絡(luò)數(shù)據(jù)包到達描述的是CPU執(zhí)行指令以外的事件，屬于外部中斷，in正確。

21.【解析】

由CPU內(nèi)部產(chǎn)生的異常稱為內(nèi)中斷，內(nèi)中斷都是不可屏蔽中斷。通過中斷請求線INTR和

NMI,從CPU外部發(fā)出的中斷請求為外中斷，通過INTR信號線發(fā)出的外中斷是可屏蔽中

斷，而通過NMI信號線發(fā)出的是不可屏蔽中斷。不可屏蔽中斷不受中斷標(biāo)志位的影響，即

使在關(guān)中斷的情況下也會被響應(yīng)，選項A正確。不可屏蔽中斷的處理優(yōu)先級最高，任何時

候只要發(fā)生不可屏蔽中斷，都要中止現(xiàn)行程序的執(zhí)行，轉(zhuǎn)到不可屏蔽中斷處理程序執(zhí)行，

選項C正確。CPU響應(yīng)中斷需要滿足3個條件：①中斷源有中斷請求；②CPU允許中斷

及開中斷；③一條指令執(zhí)行完畢，且沒有更緊迫的任務(wù)。故選項B錯誤。

22.【解析】

周期挪用法由DMA控制器挪用一個或幾個主存周期來訪問主存，傳送完一個數(shù)據(jù)字后立

即釋放總線，是一種單字傳送方式，每個字傳送完后CPU可以訪問主存，選項C錯誤。

停止CPU訪存法則是指在整個數(shù)據(jù)塊的傳送過程中，使CPU脫離總線，停止訪問主存。

23.【解析】

多個進程可同時以“讀"或"寫”方式打開文件，操作系統(tǒng)并不保證寫操作的互斥性，進

程可通過系統(tǒng)調(diào)用對文件加鎖，保證互斥寫（讀者-寫者問題），選項A錯誤。整個系統(tǒng)只

有一個系統(tǒng)打開文件表，同一個文件打開多次只需改變引用計數(shù)，選項B正確。用戶進程

的打開文件表關(guān)于同一個文件不一定相同，例如讀寫指針位置不一定相同，選項C錯誤。

進程關(guān)閉文件時，文件的引用計數(shù)減1,引用計數(shù)變?yōu)?時才刪除系統(tǒng)打開文件表中的表

項，選項D錯誤。

24.【解析】

索引分配支持變長的文件，同時可以隨機訪問文件的指定數(shù)據(jù)塊，選項A正確。鏈接分配

不支持隨機訪問，需要依靠指針依次訪問，選項B錯誤。連續(xù)分配的文件長度固定，不支持

?034?

可變文件長度(連續(xù)分配的文件長度雖然也可變，但是需大量移動數(shù)據(jù)，代價較大，相比之

下不太合適)，選項C錯誤。動態(tài)分區(qū)分配是內(nèi)存管理方式，不是磁盤空間的管理方式，選

項D錯誤。

25.【解析】

當(dāng)CPU檢測到中斷信號后，由硬件自動保存被中斷程序的斷點(即程序計數(shù)器PC),I錯

誤。之后，硬件找到該中斷信號對應(yīng)的中斷向量，中斷向量指明中斷服務(wù)程序入口地址(各

中斷向量統(tǒng)一存放在中斷向量表中，該表由操作系統(tǒng)初始化，IH正確)。接下來開始執(zhí)行

中斷服務(wù)程序，保存PSW、保存中斷屏蔽字、保存各通用寄存器的值，并提供與中斷信號

對應(yīng)的中斷服務(wù)，中斷服務(wù)程序?qū)儆诓僮飨到y(tǒng)內(nèi)核，II和IV正確。

26.【解析】

多級反饋隊列調(diào)度算法需要綜合考慮優(yōu)先級數(shù)量、優(yōu)先級之間的轉(zhuǎn)換規(guī)則等，就緒隊列的

數(shù)量會影響長進程的最終完成時間，I正確；就緒隊列的優(yōu)先級會影響進程執(zhí)行的順序，II

正確；各就緒隊列的調(diào)度算法會影響各隊列中進程的調(diào)度順序，HI正確；進程在就緒隊列

中的遷移條件會影響各進程在各隊列中的執(zhí)行時間，IV正確。

27.【解析】

首先求出需求矩陣:

ABABAB

442321

Need=Max-Allocation=-=

312110

341222

由Allocation得知當(dāng)前Available為(1,0).由需求矩陣可知，初始只能滿足P2的需求，選

項A錯誤。P2釋放資源后Available變?yōu)?3,1),此時僅能滿足P1的需求，選項C錯誤。

P1釋放資源后Available變?yōu)?5,4),可以滿足P3的需求，得到的安全序列為P2,Pl,P3,

選項B正確，選項D錯誤。

28.【解析】

I影響缺頁中斷的頻率，缺頁率越高，平均訪存時間越長；H和IV影響缺頁中斷的處理時

間，中斷處理時間越長，平均訪存時間越長；in影響訪問頁表和訪問目標(biāo)物理地址的時間，

故I、n、in和iv均正確。

29.【解析】

父進程與子進程當(dāng)然可以并發(fā)執(zhí)行，選項A正確。父進程可與子進程共享一部分資源，但

不能共享虛擬地址空間，在創(chuàng)建子進程時，會為子進程分配資源，如虛擬地址空間等，選

項B錯誤。臨界資源一次只能為一個進程所用，選項D正確。進程控制塊PCB是進程存

在的唯一標(biāo)志，每個進程都有自己的PCB,選項C正確。

30.【解析】

設(shè)備可視為特殊文件，選項A正確。用戶使用邏輯設(shè)備名來訪問物理文件，有利于設(shè)備獨

立性，選項B正確。通過邏輯設(shè)備名訪問物理設(shè)備時，需要建立邏輯設(shè)備和物理設(shè)備之間

的映射關(guān)系，選項C正確。應(yīng)用程序按邏輯設(shè)備名訪問設(shè)備，再經(jīng)驅(qū)動程序的處理來控制

,035,

物理設(shè)備，若更換物理設(shè)備，則只需更換驅(qū)動程序，而無須修改應(yīng)用程序，選項D錯誤。

31.【解析】

在總長為64字節(jié)的目錄項中，索引結(jié)點占4字節(jié)，即32位。不同目錄下的文件的文件名

可以相同，所以在考慮系統(tǒng)創(chuàng)建最多文件數(shù)量時，只需考慮索引結(jié)點的個數(shù)，即創(chuàng)建文件

數(shù)量上限=索引結(jié)點數(shù)量上限。整個系統(tǒng)中最多存儲232個索引結(jié)點，因此整個系統(tǒng)最多

可以表示232個文件，選項B正確。

32.【解析】

實現(xiàn)臨界區(qū)互斥需滿足多個準則?！懊t等待”準則，即兩個進程不能同時訪問臨界區(qū)，I

正確?！翱臻e讓進”準則，若臨界區(qū)空閑，則允許其他進程訪問，II正確。“有限等待”

準則，即進程應(yīng)該在有限時間內(nèi)訪問臨界區(qū)，山正確。I、H和IH是互斥機制必須遵循的

原則。IV是“讓權(quán)等待”準則，不一定非得實現(xiàn)，如皮特森算法。

33.【解析】

協(xié)議由語法、語義和時序（又稱同步）三部分組成。語法規(guī)定了通信雙方彼此“如何講”,

即規(guī)定了傳輸數(shù)據(jù)的格式。語義規(guī)定了通信雙方彼此“講什么”，規(guī)定了所要完成的功能,

如通信雙方要發(fā)出什么控制信息、執(zhí)行的動作和返回的應(yīng)答。時序規(guī)定了信息交流的次序。

由圖可知發(fā)送方與接收方依次交換信息，體現(xiàn)了協(xié)議三要素中的時序要素。

34.【解析】

虛電路服務(wù)需要有建立連接過程，每個分組使用短的虛電路號，屬于同一條虛電路的分組

按照同一路由進行轉(zhuǎn)發(fā)，分組到達終點的順序與發(fā)送順序相同，可以保證有序傳輸，不需

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

35.【解析】

網(wǎng)絡(luò)層設(shè)備路由器可以隔離廣播域和沖突域；鏈路層設(shè)備普通交換機只能隔離沖突域；物

理層設(shè)備集線器、中繼器既不能隔離沖突域又不能隔離廣播域。因此，題中共有2個廣播

域、4個沖突域。

36?【解析】

發(fā)送數(shù)據(jù)幀和確認幀的時間均為/=1000x8b/10kbps=800ms（.

?036?

發(fā)送周期T=800ms+200ms+800ms+200ms=2000ms?

信道利用率=t/Txl00%=800/2000x100%=40%?

37.【解析】

為了盡量避免碰撞，802.11規(guī)定，所有站在完成發(fā)送后，必須等待一段很短的時間（繼續(xù)

監(jiān)聽）才能發(fā)送下一幀。這段時間稱為幀間間隔（InterFrameSpace,IFS）.幀間間隔的長

短取決于該站要發(fā)送的幀的類型。IEEE802.11使用3種幀間間隔：

DIFS（分布式協(xié)調(diào)IFS）：最長的IFS,優(yōu)先級最低，用于異步幀競爭訪問的時延。

PIFS（點協(xié)調(diào)IFS）：中等長度的IFS,優(yōu)先級居中，在PCF操作中使用。

SIFS（短IFS）：最短的IFS,優(yōu)先級最高，用于需要立即響應(yīng)的操作。

網(wǎng)絡(luò)中的控制幀及所接收數(shù)據(jù)的確認幀都采用SIFS作為發(fā)送之前的等待時延。當(dāng)結(jié)點要發(fā)

送數(shù)據(jù)幀時，載波監(jiān)聽到信道空閑時，需等待DIFS后發(fā)送RTS預(yù)約信道，圖中IFS1對應(yīng)

的是幀間間隔DIFS,時間最長，圖中IFS2、IFS3、IFS4對應(yīng)SIFS。

38?【解析】

由于慢開始門限ssthresh可以根據(jù)需求設(shè)置，為了求擁塞窗口從8KB增長到32KB所需的

最長時間，可以假定慢開始門限小于等于8KB,只要不出現(xiàn)擁塞，擁塞窗口就都是加法增

大,每經(jīng)歷一個傳輸輪次（RTT）,擁塞窗口逐次加1,所需最長時間為（32-8）x2ms=48ms?

39?【解析】

甲與乙建立TCP連接時發(fā)送的SYN段中的序號為1000,則在數(shù)據(jù)傳輸階段所用的起始序

號為1001；斷開連接時，甲發(fā)送給乙的FIN段中的序號為5001,在無任何重傳的情況下，

甲向乙已經(jīng)發(fā)送的應(yīng)用層數(shù)據(jù)的字節(jié)數(shù)為5001-1001=4000?

40.【解析】

題中RTT均為局域網(wǎng)內(nèi)主機（主機H、本地域名服務(wù)器）訪問Internet上各服務(wù)器的往返

時間，且忽略其他時延，因此主機H向本地域名服務(wù)器的查詢時延忽略不計。最短時間：

本地主機中有該域名到IP地址對應(yīng)的記錄，因此不需要DNS查詢時延，直接和

服務(wù)器建立TCP連接再進行資源訪問，TCP連接建立需要1個RTT,接著發(fā)

送訪問請求并收到服務(wù)器資源響應(yīng)需要1個RTT,共計2個RTT,即20ms：最長時間：本

地主機遞歸查詢本地域名服務(wù)器（延時忽略），本地服務(wù)器依次迭代查詢根域名服務(wù)器、com

頂級域名服務(wù)器、域名服務(wù)器，共3個RTT,查詢到IP地址后，將該映射返回給

主機H,主機H和服務(wù)器建立TCP連接再進行資源訪問，共2個RTT,因

此最長時間需要3+2=5個RTT,即50ms。

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

41.【解析】

分析。由。=卜-同+他-<?|+卜-a》0得：

①當(dāng)。=6=c時，距離最小。

②其余情況。不失一般性，假設(shè)觀察下面的數(shù)軸:

?037?

A

bAc

Lj=|a—?Lj=—c|?L3=|c-a|>D=|a-Z>|+|Z>-c|+|c-a|=￡,+L2+L3=2L,

由。的表達式可知，事實上決定。大小的關(guān)鍵是。和c之間的距離，于是問題就可以簡化

為每次固定c找一個a使得右=|c-a|最小。

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

①使用。min記錄所有已處理過的三元組的最小距離，初值為一個足夠大的整數(shù)。

②集合S|、S2和&分別保存在數(shù)組A、B、C中。數(shù)組的下標(biāo)變量i=片％=0,當(dāng)i<同、

/<同且％<區(qū)|時(⑶表示集合s中的元素個數(shù))，循環(huán)執(zhí)行a)?c)。

a)計算(AU],B[/],C因)的距離。；(計算。)

b)若。<￡>min，貝(更新。)

c)將A國,因中的最小值的下標(biāo)+1；(對照分析：最小值為a,最大值為C,

這里c不變而更新a,試圖尋找更小距離。)

③輸出Dmin,結(jié)束。

2)算法實現(xiàn)：

#defineINT_MAX0x7fffffff

intabs_(inta){〃計算絕對值

if(a<0)return-a;

elsereturna;

)

boolxls_min(inta,intb,intc){//a是否是三個數(shù)中的最小值

if(a<=b&&a<=c)returntrue;

returnfalse;

)

intfindMinofTrip(intA[]zintn,intB[]zintm,intC[],intp){

//D_min用于記錄三元組的最小距離，初值賦為INT_MAX

inti=0,j=0,k=0,D_min=INT_MAX,D;

while(i<n&&j<m&&k<p&&D_min>0){

D=abs_(A[i]-B[j])+abs__(B[j]-C[k])+abs_(C[k]-A[i]);〃計算D

if(D<D_min)D__min=D;〃更新D

if(xls__min(A[i],B[j],C[k]))i++;〃更新a

elseif(xls_min(B[j]zC[k]rA[i]))j++;

elsek++;

)

returnD__min;

)

3)設(shè)〃=區(qū)|+河+網(wǎng),時間復(fù)雜度為。(〃)，空間復(fù)雜度為51)。

42.【解析】

1)使用一棵二叉樹保存字符集中各字符的編碼，每個編碼對應(yīng)于從根開始到達某葉結(jié)點的

一條路徑，路徑長度等于編碼位數(shù)，路徑到達的葉結(jié)點中保存該編碼對應(yīng)的字符。

2)從左至右依次掃描0/1串中的各位。從根開始，根據(jù)串中當(dāng)前位沿當(dāng)前結(jié)點的左子指針

或右子指針下移，直到移動到葉結(jié)點時為止。輸出葉結(jié)點中保存的字符。然后從根開始

重復(fù)這個過程，直到掃描到0/1串結(jié)束，譯碼完成。

?038?

3）二叉樹既可用于保存各字符的編碼，又可用于檢測編碼是否具有前綴特性。判定編碼是

否具有前綴特性的過程，也是構(gòu)建二叉樹的過程。初始時，二叉樹中僅含有根結(jié)點，其

左子指針和右子指針均為空。

依次讀入每個編碼C,建立/尋找從根開始對應(yīng)于該編碼的一條路徑，過程如下：

對每個編碼，從左至右掃描C的各位，根據(jù)C的當(dāng)前位（0或1）沿結(jié)點的指針（左子指

針或右子指針）向下移動。當(dāng)遇到空指針時，創(chuàng)建新結(jié)點，讓空指針指向該新結(jié)點并繼續(xù)

移動。沿指針移動的過程中，可能遇到三種情況：

①若遇到了葉結(jié)點（非根），則表明不具有前綴特性，返回。

②若在處理C的所有位的過程中，均沒有創(chuàng)建新結(jié)點，則表明不具有前綴特性，返回。

③若在處理C的最后一個編碼位時創(chuàng)建了新結(jié)點，則繼續(xù)驗證下一個編碼。

若所有編碼均通過驗證，則編碼具有前綴特性。

43?【解析】

1）乘法運算可以通過加法和移位來實現(xiàn)。編譯器可以將乘法運算轉(zhuǎn)換為一個循環(huán)代碼段,

在循環(huán)代碼段中通過比較、加法和移位等指令實現(xiàn)乘法運算。

2）控制邏輯的作用是控制循環(huán)次數(shù)，控制加法和移位操作。

3）①最長，③最短。對于①，需要用循環(huán)代碼段（即軟件）實現(xiàn)乘法操作，因而需要反復(fù)

執(zhí)行很多條指令，而每條指令都需要取指令、譯碼、取數(shù)、執(zhí)行并保存結(jié)果，所以執(zhí)行

時間很長；對于②和③，都只需用一條乘法指令實現(xiàn)乘法操作，不過②中的乘法指令需

要多個時鐘周期才能完成，而③中的乘法指令可以在一個時鐘周期內(nèi)完成，所以③的執(zhí)

行時間最短。

4）當(dāng)〃=32,x=23i-lj=2時，帶符號整數(shù)和無符號整數(shù)乘法指令得到的64位乘積都是

00000000FFFFFFFEH,int型的表示范圍為[-23）-1],故函數(shù)imul（）的結(jié)果溢出：

unsignedint型的表示范圍為[0,232-1],故函數(shù)umul（）的結(jié)果不溢出。對于無符號整數(shù)

乘法，若乘積高〃位全為0,即使低〃位全為1也正好是232-1,不溢出，否則溢出。

44.【解析】

1）主存塊大小為64B=26字節(jié)，所以主存地址低6位為塊內(nèi)地址，Cache組數(shù)為

32KB/（64Bx8）=64=26,故主存地址中間6位為Cache組號，主存地址中高32-6-6

=20位為標(biāo)記，采用8路組相聯(lián)映射，故每行中的LRU位占3位，采用直寫方式，故

沒有修改位。

2）008000C0H=00000000100000000000000011000000B,主存地址的低6位為塊內(nèi)地

址，為全0,故s位于一個主存塊的開始處，占1024x4B/64B=64個主存塊；在執(zhí)行程

序段的過程中，每個主存塊中的64B/4B=16個數(shù)組元素依次讀、寫1次，因而對每個

主存塊，總是第一次訪問缺失，此時會將整個主存塊調(diào)入Cache,之后每次都命中。綜

上，數(shù)組s的數(shù)據(jù)Cache訪問缺失次數(shù)為64次。

3）00010003H=00000000000000010000000000000011B,根據(jù)主存地址劃分可知，組

索引為0,故該地址所在主存塊被映射到指令Cache的第0組；因為Cache初始為空，

所有Cache行的有效位均為0,所以Cache訪問缺失。此時，將該主存塊取出后存入指

令Cache的第0組的任意一行，并將主存地址高20位（00010H）填入該行標(biāo)記字段，

設(shè)置有效位，修改LRU位，最后根據(jù)塊內(nèi)地址000011B從該行中取出相應(yīng)的內(nèi)容。

?039?

45.【解析】

本題要求實現(xiàn)操作的先后順序，沒有互斥關(guān)系，是一個簡單的同步問題。

本題雖然有5個操作，但是只有4個同步關(guān)系，因此分別設(shè)置信號量SAC、SBC、SCE和

SDE對應(yīng)4個同步關(guān)系。

SemaphoreSAC0;//控制A和C的執(zhí)行順序

SemaphoreSBC0;//控制B和C的執(zhí)行順序

Semaphore0;//控制C和E的執(zhí)行順序

SemaphoreSDE=0;//控制D和E的執(zhí)行順序

5個操作可描述為如下。

CoBegin

A()(

完成動作A；

//實現(xiàn)A、C之間的同步關(guān)系

V(SAC)；

完成動作B;

V(SBC)；//實現(xiàn)B、C之間的同步關(guān)系

CO{

//C必須在A、B都完成后才能完成

P(SAC)；

P(SBC)；

完成動作C;

V(SCE)；//實現(xiàn)C、E之間的同步關(guān)系

完成動作D；

V(SDE)；〃實現(xiàn)D、E之間的同步關(guān)系

EO{

//E必須在完成C、D之后執(zhí)行

P(SCE)；

P(SDE)

完成動作E;

)

CoEnd

46.【解析】

1)①頁面大小=212B=4096B=4KBo每個數(shù)組元素4B,每個頁面可以存放4KB/4B=

1024個數(shù)組元素，正好是數(shù)組的一行，數(shù)組a按行優(yōu)先方式存放。10800000H的虛

頁號為10800H,因此a[0]行存放在虛頁號為10800H的頁面中，a[l]行存放在頁號

為10801H的頁面中。a[l]⑵的虛擬地址為10801000H+4x2=10801008H.

②轉(zhuǎn)換為二進制00010000100000000001000000001000，根據(jù)虛擬地址結(jié)構(gòu)可知，對

應(yīng)的頁目錄號為042H,頁號為001H。

③進程的頁目錄表起始地址為00201000H,每個頁目錄項長4B,因此042H號頁目錄

項的物理地址是00201000H+4x42H=00201108H?

④頁目錄項存放的頁框號為00301H,二級頁表的起始地址為00301000H,因此

所在頁的頁號為001H,每個頁表項4B,因此對應(yīng)的頁表項物理地址是00301000H+

001Hx4=00301004Ho

?040?

2）根據(jù)數(shù)組的隨機存取特點，數(shù)組a在虛擬地址空間中所占的區(qū)域必須連續(xù)，由于數(shù)組a

不止占用一頁，相鄰邏輯頁在物理上不一定相鄰，因此數(shù)組a在物理地址空間中所占的

區(qū)域可以不連續(xù)。

3）由1）可知每個頁面正好可以存放一整行的數(shù)組元素，“按行優(yōu)先方式存放”意味著數(shù)

組的同一行的所有元素都存放在同一個頁面中，同一列的各個元素都存放在不同的頁面

中，因此數(shù)組a按行遍歷的局部性較好。

47.【解析】

1）兩個子網(wǎng)使用了相同的網(wǎng)段，且路由器開啟了NAT功能，加上題干給出了NAT表的結(jié)

構(gòu)，因此需要配置NAT表。路由器R2開啟NAT服務(wù)，當(dāng)路由器R2從WAN口收到

H2或H3發(fā)來的數(shù)據(jù)時，根據(jù)NAT表發(fā)送給Web服務(wù)器的對應(yīng)端口。外網(wǎng)IP地址應(yīng)

該為路由器的外端IP地址，內(nèi)網(wǎng)IP地址應(yīng)該為Web服務(wù)器的地址，Web服務(wù)器的默

認端口為8