計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷16

計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷16

一、單選題（本題共40題，每題1.0分，共40分。）

1、一個(gè)棧的入棧序列是1,2,3,4,5,則棧的不可能的輸出序列是（）。

A、5,4,3,2,1

B、4,5,3,2,：1

C、4,3,5,1,2

D、1,2,3,4,5

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：此類問(wèn)題是常見(jiàn)題型。解答的基本原理是：一串?dāng)?shù)據(jù)依次通過(guò)一個(gè)

棧，并不能保證出棧數(shù)據(jù)的次序總是倒置，可以產(chǎn)生多種出棧序列。一串?dāng)?shù)據(jù)通過(guò)

一個(gè)棧后的次序由每個(gè)數(shù)據(jù)之間的進(jìn)棧、出棧操作序列決定，只有當(dāng)所有數(shù)據(jù)“全

部進(jìn)棧后再全部出?！辈拍苁箶?shù)據(jù)倒置…事實(shí)上，存在一種操作序列—“進(jìn)棧、出

棧、進(jìn)棧、出?！薄梢允箶?shù)據(jù)通過(guò)棧后仍然保持次序不變.

2、設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1」為第

一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，則a8,5的地址是（）。

A、13

B、33

C、18

D、40

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：這里數(shù)組下標(biāo)從1開(kāi)始，只存儲(chǔ)其下三角形元素，在28、5的前面有7

行，第1行有1個(gè)元素，第2行有2個(gè)元素，…，第7行有7個(gè)元素，這7行共有

（l+7）x7/2=28個(gè)元素，在第8行中，a&5的前面有4個(gè)元素，所以，ag,5前有

28+4=32個(gè)元素，其地址為33。

3、在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于（）。

A、n

B、n-1

C、n+1

D、2n

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，每個(gè)結(jié)點(diǎn)可有兩棵子樹(shù)，共有2n

個(gè)子樹(shù)。其中二叉樹(shù)的總分支數(shù)等于總結(jié)點(diǎn)數(shù)減1,即有n-1棵不空的子樹(shù)。所

以在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于n+lo

4、在常用的描述二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)是()。

A、左指針一定為空

B、右指針一定為空

C、左右指針均為空

D、左右指針均不為空

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：在二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)由三部分構(gòu)成，其中左(或右)

指針指向比結(jié)點(diǎn)的關(guān)鍵值小(或大)的結(jié)點(diǎn)。關(guān)鍵字值最大的結(jié)點(diǎn)位于二叉排序樹(shù)的

最右位置上，因此它的右指針一定為空。

5、由權(quán)值為9、2、5、7的四個(gè)葉子構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為

()。

A、23

B、37

C、44

D、46

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：由權(quán)值為9、2、5、7的四個(gè)葉子構(gòu)迨的哈夫曼樹(shù)可如下圖所示。

該對(duì)的帶權(quán)路徑長(zhǎng)度=9x1+7x2+2x3+5x3=44。

6、若一個(gè)具有n個(gè)結(jié)點(diǎn)、k條邊的非連通無(wú)向圖是一個(gè)森林(n>k),則該森林中必

有樹(shù)的數(shù)目是().

A、k

B、n

C、n-k

D、n+k

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：因?yàn)橐豢镁哂衝個(gè)頂點(diǎn)的樹(shù)有n—l條邊，因此設(shè)題目中的森林有m

棵樹(shù)，每棵樹(shù)具有頂點(diǎn)數(shù)為Vi(lSiSm),貝ijV1+V2+…Vm=N及(Vi—1)+(V2—

l)+...(Vm-1)=K,所以n=m+k。

7、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于樹(shù)的()。

A、中根遍歷

B、先根遍歷

C、后根遍歷

D、按層次遍歷

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：深度優(yōu)先嗖索遍歷類似于樹(shù)的先根遍歷，是樹(shù)的先根遍歷的推廣。廣

度優(yōu)先搜索遍歷類似于樹(shù)的按層次遍歷的過(guò)程?；蛘哒f(shuō)，樹(shù)的先根遍歷是一種深度

優(yōu)先搜索策略，樹(shù)的層次遍歷是一種廣度優(yōu)先搜索策略。

8、在有向圖G的拓?fù)洚a(chǎn)列中，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)

的是()。

A、G中有弧i,Vj>

B、G中有一條從Vi到Vj的路徑

C、G中沒(méi)有弧i,Vj>

D、G中有一條從Vj到Vi的路徑

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：選項(xiàng)A、B、C都是有可能出現(xiàn)的，但是選項(xiàng)D是不可能出現(xiàn)的：因

為若是G中有一條從V到M的路徑，則在圖的拓?fù)湫蛄兄许旤c(diǎn)Vj應(yīng)該在頂點(diǎn)Vi

之前。

9、假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這k個(gè)關(guān)鍵字存入，至少要

進(jìn)行的探查次數(shù)是()。

A、k-I

B、k

C、k+1

D、k(k+l)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這k個(gè)關(guān)鍵字存

入，探查次數(shù)最少的情況是第1個(gè)關(guān)鍵字通過(guò)1次比較后插入，第2個(gè)關(guān)鍵字通過(guò)

2次比較后插入，……，第k個(gè)關(guān)鍵字通過(guò)k次比較后插入?？偟谋容^次數(shù)

=1+2+.......+k=k(k+l)/2o

10、下列序列中，滿足堆定義的是()。

A、(100,86,48,73,35,39,42,57,66,21)

B、(12,70,33,65,24,56,48,92,86,33)

C、(103,97,56,38,66,23,42,12,30,52,6,26)

D、(5,56,20,23,40,38,29,61,36,76,28,100)

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：依據(jù)堆的定義，將選項(xiàng)中的每個(gè)數(shù)列分別看成是一棵完全二叉樹(shù)，則

堆或是空樹(shù)或是滿足下列特性的完全二叉樹(shù)：其左、右子樹(shù)分別是堆，并且當(dāng)左/

右子樹(shù)不空時(shí)，根結(jié)點(diǎn)的值小于(或大于)左/右子樹(shù)根結(jié)點(diǎn)的值。

II、對(duì)于一個(gè)長(zhǎng)度為n的任意表進(jìn)行排序，至少需要進(jìn)行的比較次數(shù)是()。

A、O(n)

B、0(n2)

C>O(logn)

D、O(nlogn)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：在排序過(guò)程中，每次比較會(huì)有兩種情況出現(xiàn)，若整個(gè)排序過(guò)程中至少

需要t次比較，則顯然會(huì)有2t種情況，由于n個(gè)記錄總共有n!種不同的排列，因而

必須有n!種不同的比較路徑，于是有:2l>n!,即Glog2(n!)。因?yàn)?/p>

Iog2(n!)~nlog2n,所以Gnlogzn。

12、哈佛(Harvard)結(jié)構(gòu)的基本特點(diǎn)是()。

A、采用多指令流單數(shù)據(jù)流

B、程序和數(shù)據(jù)在不同的存儲(chǔ)空間

C、堆棧操作

D、存儲(chǔ)器按內(nèi)容選擇地址

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：哈佛結(jié)構(gòu)的指令和數(shù)據(jù)是完全分開(kāi)的，存儲(chǔ)器分為兩部分，一個(gè)是程

序存儲(chǔ)器，用來(lái)存放指令，另一個(gè)是數(shù)據(jù)存儲(chǔ)器，用來(lái)存放數(shù)據(jù)。

13、若二進(jìn)制定點(diǎn)小數(shù)真值是一0.1101,機(jī)器中表示為1.0010,則該數(shù)采用的

編碼方法是()0

A、原碼

B、補(bǔ)碼

C、反碼

D、移碼

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：真值一0.1101,對(duì)應(yīng)的原碼表示為1.1101,補(bǔ)碼表示為

1.0011,反碼表示為1.0010o移碼通常用于表示階碼，不用來(lái)表示定點(diǎn)小數(shù)。

14、描述流水線CPU基本概念中，正確表述的句子是()。

A、流水線CPU是以空間并行性為原理構(gòu)造的處理

B、流水線CPU一定是RISC機(jī)器

C、流水線CPU一定是多媒體CPU

D、流水線CPU是一種非常經(jīng)濟(jì)而實(shí)用的時(shí)間并行技術(shù)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：在4個(gè)選項(xiàng)中唯有選項(xiàng)D是正確的。選項(xiàng)A是指超標(biāo)量處理機(jī)。

RISC機(jī)器一定采用流水線技術(shù)，而流水線CPU不一定就是RISC機(jī)器。流水線

CPU也不一定是多媒體CPU.

15、原碼乘法時(shí)，符號(hào)位單獨(dú)處理，乘積的符號(hào)是()。

A、兩個(gè)操作數(shù)符號(hào)相“與”

B、兩個(gè)操作數(shù)符號(hào)相“或”

C、兩個(gè)操作數(shù)符號(hào)相“異或”

D、兩個(gè)操作數(shù)中絕對(duì)值較大數(shù)的符號(hào)

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析?：原碼的符號(hào)位為“1”表示負(fù)數(shù)，為“0”表示正數(shù)。原碼乘法時(shí)，符號(hào)位

單獨(dú)處理，乘積的符號(hào)是兩個(gè)操作數(shù)符號(hào)相“異或”，同號(hào)為正，異號(hào)為負(fù)。

16、頁(yè)式存儲(chǔ)系統(tǒng)的邏輯地址是由頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分組成，地址變換過(guò)程如下

圖所示。假定頁(yè)面的大小為8K,圖中所示的十進(jìn)制邏輯地址9612經(jīng)過(guò)地址變換

后，形成的物理地址a（十進(jìn)制）是（）。

控制寄存器遂灣地址

A、42380

B、25996

C、9612

D、8192

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：由于頁(yè)面大小為8K,則十進(jìn)制邏輯地址9612處于第1虛頁(yè)中，頁(yè)內(nèi)

地址一1420,其對(duì)應(yīng)的實(shí)頁(yè)為第3頁(yè)，故a=3x8192+1420=25996。

17、在指令系統(tǒng)的各種尋址方式中，獲取操作數(shù)最快的方式是（）。

A、直接尋址

B、立即尋址

C、寄存器尋址

D、間接尋址

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：立即尋址是一種特殊的尋址方式，指令中在操作碼字段后面的部分不

是通常意義上的地址碼，而是操作數(shù)本身，也就是說(shuō)數(shù)據(jù)就包含在指令中，只要取

出指令，也就取出了可以立即使用的操作數(shù)，不必再次訪問(wèn)存儲(chǔ)器，從而提高了指

令的執(zhí)行速度。

18、在計(jì)算機(jī)體系結(jié)構(gòu)中，CPU內(nèi)部包括程序計(jì)數(shù)器PC、存儲(chǔ)器數(shù)據(jù)寄存器

MDR、指令寄存器IR和存儲(chǔ)器地址寄存器MAR等。若CPU要執(zhí)行的指令為：

MOVR0,#100（即將數(shù)值100傳送到寄存器R0中），則CPU首先要完成的操作是

（）。

A、100—R0

B、100—MDR

C、PC一MAR

D、PC—IR

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：無(wú)論運(yùn)行什么類型的指令，CPU首先需要取指令，取指令階段的第

一個(gè)操作就是將指令地址（程序計(jì)數(shù)器PC中的內(nèi)容）送往存儲(chǔ)器地址寄存器。

19、在微指令的編碼方式中，若微命令數(shù)相同，下列敘述中正確的是（）。I.直接

控制方式與編碼控制方式的微指令長(zhǎng)度相等n.最短編碼控制和直接控制方式不

影響微指令字長(zhǎng)皿.編碼控制方式的微指令比直接控制方式的微指令短w.宜接

控制的微指令比字段編碼的微指令長(zhǎng)v.字段直接編碼的微指令與字段間接編碼的

微指令長(zhǎng)度相等VI.字段間接編碼的微指令比字段直接編碼的微指令長(zhǎng)

A、in和PC

B、I和111

C、口和皿

D、川、IV和VI

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：微指令的操作控制字段可分為直接控制法、最短編碼法和字段編碼

法，字段編碼法中乂可以進(jìn)一步分為字段直接編碼法和字段間接編碼法。若微命令

數(shù)相同，微指令操作控制字段的長(zhǎng)度由短至長(zhǎng)依次為：最短編碼一字段間接編碼一

字段直接編碼一直接控制。操作控制字段短則相應(yīng)的微指令字長(zhǎng)就短。

20、下列計(jì)算機(jī)總線屬于串行總線的是（）。

A、PCI

B、1394

C、EISA

D、ISA

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：1394是高性能的串行總線.

21、某數(shù)碼相機(jī)內(nèi)近128MB的存儲(chǔ)空間，拍攝分辨率設(shè)定為1600x1200像素，

顏色深度為24位，若不采用壓縮存儲(chǔ)技術(shù)，使用內(nèi)部存儲(chǔ)器最多可以存儲(chǔ)的照片

數(shù)是（）。

A、12

B、25

C、13

D、23

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：顏色深度為24位（3個(gè)字節(jié)），每張照片的存儲(chǔ)量為

1600xl200x3B^5.5MB,128MB/5.5MB—23.3,所以內(nèi)置的存儲(chǔ)空間最多

可存儲(chǔ)23張照片。

22、中斷向量表中保存的是（）。

A、被中斷程序的返回地址

B、中斷服務(wù)程序入口地址

C、中斷優(yōu)先級(jí)

D、中斷源編碼

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：中斷向量表是用來(lái)存放中斷服務(wù)程序的入口地址的。

23、對(duì)于設(shè)計(jì)實(shí)時(shí)操作系統(tǒng)，不是其設(shè)計(jì)目標(biāo)的是（）。

A、安全可靠

B、處理機(jī)效率

C、及時(shí)響應(yīng)輸入

D、快速處理請(qǐng)求

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：本題考查實(shí)時(shí)操作系統(tǒng)的設(shè)計(jì)目標(biāo)。實(shí)時(shí)操作系統(tǒng)要求能對(duì)用戶的請(qǐng)

求在規(guī)定的時(shí)間內(nèi)完成，同時(shí)需要保證進(jìn)程運(yùn)行的安全性和高可靠性。而處理機(jī)的

效率不是實(shí)時(shí)操作系統(tǒng)沒(méi)計(jì)所關(guān)心的。

24、并發(fā)進(jìn)程在運(yùn)行時(shí)，其推進(jìn)的相對(duì)速度是（）。

A,由進(jìn)程的程序結(jié)構(gòu)決定

B、由進(jìn)程自己的代碼控制

C、與進(jìn)程調(diào)度策略有關(guān)

D、在進(jìn)程創(chuàng)建時(shí)確定的

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：在進(jìn)程的一次運(yùn)行過(guò)程中，其代碼的執(zhí)行序列是確定的，即使有循環(huán)

或轉(zhuǎn)移，對(duì)于進(jìn)程來(lái)講，其運(yùn)行的軌跡也是確定的，所以對(duì)于這樣一個(gè)確定的運(yùn)行

軌跡，進(jìn)程自身是可以控制自身前進(jìn)或停止的，例如可以休眠10秒再喚醒等，但

是，當(dāng)這樣的進(jìn)程存在于一個(gè)并發(fā)系統(tǒng)中時(shí)，這種確定性就被打破了。由于系統(tǒng)中

存在有大量的可運(yùn)行的進(jìn)程,操作系統(tǒng)為了提高計(jì)算機(jī)的效率,會(huì)根據(jù)用戶的需求

和系統(tǒng)資源的數(shù)量來(lái)自動(dòng)地進(jìn)行調(diào)度和切換，以保證系統(tǒng)高效地運(yùn)行。此時(shí)，進(jìn)程

由于被調(diào)度，打破了原來(lái)的固有執(zhí)行速度，走走停停，因此，進(jìn)程的相對(duì)速度就不

受進(jìn)程自己的控制，而是取決于進(jìn)程調(diào)度的策略。不確定性也是并發(fā)系統(tǒng)的一個(gè)特

征。

25、兩個(gè)旅行社甲和已為旅客到某航空公司訂飛機(jī)票，形成互斥資源的是（）。

A、旅行社

B、航空公司

C、飛機(jī)票

D、旅行社與航空公司

標(biāo)準(zhǔn)答案：c

知識(shí)點(diǎn)》析：本題考查互斥資源的問(wèn)題，一張飛機(jī)票不能售給不同的旅客，因此飛

機(jī)票是互斥資源，其它因素只是為完成飛機(jī)票訂票的中間過(guò)程，與互斥資源無(wú)關(guān)。

26、在進(jìn)程通信中，消息的一般形式為四個(gè)部分組成。是（）。

A、發(fā)送進(jìn)程名、接收進(jìn)程名、消息標(biāo)示符、消息正文

B、發(fā)送進(jìn)程名、消息標(biāo)示符、消息長(zhǎng)度、消息正文

C、發(fā)送進(jìn)程名、接收進(jìn)程名、消息長(zhǎng)度、消息當(dāng)前狀態(tài)

D、發(fā)送進(jìn)程名、接收進(jìn)程名、消息長(zhǎng)度、消息正文

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：在消息傳潴系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換是以消息（在計(jì)算機(jī)網(wǎng)絡(luò)中又

稱為報(bào)文）為單位的。消息的一般結(jié)構(gòu)形式有發(fā)送進(jìn)程名、接收進(jìn)程名、消息長(zhǎng)

度、消息正文。故正確答案為選項(xiàng)D。

27、某計(jì)算機(jī)系統(tǒng)中內(nèi)存保護(hù)采用基址、限長(zhǎng)寄存器的方法來(lái)實(shí)現(xiàn)，那么，判斷是

否越界的判別式是（）。

A、OS被訪問(wèn)的邏輯地址〈限長(zhǎng)寄存器的內(nèi)容

B、0W被訪問(wèn)的邏輯地址不艮長(zhǎng)寄存器的內(nèi)容

C、OW被訪問(wèn)的物理地址〈限長(zhǎng)寄存器的內(nèi)容

D、0W被訪問(wèn)的物理地址W限長(zhǎng)寄存器的內(nèi)容

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析?：本題考查存儲(chǔ)保護(hù)的方法?？疾榛?、限長(zhǎng)寄存器方式下是如何進(jìn)行

越界判斷的。在基址、限長(zhǎng)寄存器的保護(hù)方式下，系統(tǒng)為每個(gè)并發(fā)進(jìn)程設(shè)置一個(gè)基

址寄存器和一個(gè)限長(zhǎng)寄存器，限長(zhǎng)寄存器保存的是進(jìn)程的長(zhǎng)度，所以有關(guān)系式：邏

輯地址〈進(jìn)程長(zhǎng)度。在此注意，地址一般是從0開(kāi)始，故需要包含。一般，對(duì)于長(zhǎng)

度為100的區(qū)域，地址為從。?99。因此選A。

28、在某個(gè)計(jì)算機(jī)系統(tǒng)中，內(nèi)存的分配采用按需調(diào)頁(yè)的方式，測(cè)得當(dāng)前CPU的利

用率為8%,硬盤交換空間的利用率為55%,硬盤的繁忙率為97%,其它設(shè)備的利

用率可以忽略不計(jì)，由此斷定系統(tǒng)發(fā)生異常，此異常可能會(huì)是（），解決辦法是（）。

I.Belady現(xiàn)象；D.抖動(dòng)；HI.死鎖；IV.饑餓；V.加大交換空間容量；

VI.增加內(nèi)存容量：W.增加CPU數(shù)量：皿.增加并發(fā)進(jìn)程數(shù)：

A、I和V

B、□和VI

C、C和皿

D、W和血

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：本題考查校需調(diào)頁(yè)下提高系統(tǒng)效率的措施。首先判斷系統(tǒng)異常是屬于

什么異常，從測(cè)試數(shù)據(jù)看，CPU不忙，交換空間也不滿，就是硬盤的10非常繁

忙，所以不是交換空間不夠，系統(tǒng)也沒(méi)有死鎖，主要瓶頸在內(nèi)外存交換上，因此可

能的最大情況就是抖動(dòng)，即由于內(nèi)存緊缺，并發(fā)進(jìn)程數(shù)多，采用按需調(diào)頁(yè)而引起的

頻繁的換入換出作業(yè)。對(duì)于抖動(dòng)問(wèn)題的解決，最好的辦法是增加內(nèi)存，或減少并發(fā)

進(jìn)程數(shù)，單純地增大交爽分區(qū)的大小或增加CPU數(shù)量或提高CPU處理能力都沒(méi)有

解決根本問(wèn)題。

29、若用100個(gè)雙字（字長(zhǎng)32位）組成的位示圖管理內(nèi)存，假定用戶歸還一個(gè)塊號(hào)

為240的內(nèi)存塊時(shí)，它對(duì)應(yīng)的位示圖的位置是（）。

A、字號(hào)為6,位號(hào)為16

B、字號(hào)為7,位號(hào)為16

C、字號(hào)為6,位號(hào)為14

D、字號(hào)為7,位號(hào)為14

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：位示圖也禰為示位圖，是利用二進(jìn)制的一位來(lái)表示內(nèi)存或磁盤中一個(gè)

存儲(chǔ)塊的使用情況。當(dāng)其值為"0”時(shí)，表示對(duì)應(yīng)的塊空閑；為力”時(shí)，表示已分配。

反之亦然。內(nèi)存或磁盤上的所有塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)，這樣，由所有塊所

對(duì)應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。計(jì)算方法：字號(hào)i=INT（240/32）=7字內(nèi)位

置產(chǎn)MOD（240/32）=16

30、通常對(duì)文件系統(tǒng)來(lái)說(shuō)，文件名和文件屬性可以找到的地方是（）。

A、目錄

B、索引

C、字典

D、作業(yè)控制塊

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：在文件系統(tǒng)中，為每個(gè)文件建立一個(gè)目錄（或稱文件目錄或目錄項(xiàng)），

文件目錄記錄文件的名字，文件長(zhǎng)度和文件存放的外存地址以及文件屬性、文件創(chuàng)

建時(shí)間日期等信息。文件目錄在大部分文件系統(tǒng)中又成為文件控制塊，即FCB。

31、為保證文件的安全，操作系統(tǒng)一般采用多種方式來(lái)保護(hù)文件。為防止未經(jīng)授權(quán)

對(duì)文件的訪問(wèn)而造成的篡改或破壞，所采取的方法是（）。

A、訪問(wèn)控制列表

B、轉(zhuǎn)儲(chǔ)備份

C、加密數(shù)據(jù)

D、口令保護(hù)

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：本題考查的是文件的保護(hù)。系統(tǒng)中的文件有些是只能由文件擁有者使

用，有些是可以共享的，獨(dú)享的文件需要采取保護(hù)措施，防止非法用戶存取文件。

保護(hù)文件的方法可以有多種，定時(shí)轉(zhuǎn)儲(chǔ)備份可以防止設(shè)備故障造成的文件損壞，口

令保護(hù)和加密數(shù)據(jù)可以保護(hù)文件被非法竊取時(shí)不會(huì)泄密，而對(duì)于授權(quán)用戶的使用，

一般采用訪問(wèn)控制列表來(lái)對(duì)文件的權(quán)限進(jìn)行分配，從而保證文件的安全。

32、CPU輸出數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)高于打印機(jī)的打印速度，為解決這一矛盾，可采用

的技術(shù)是（）。

A、并行技術(shù)

B、通道技術(shù)

C、緩沖技術(shù)

D、虛存技術(shù)

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：緩沖技術(shù)的引入主要解決CPU速度和外設(shè)速度不匹配的問(wèn)題，它同

時(shí)減少了通道數(shù)量上的與用，提高了CPU、10和通道的并發(fā)性，減少了中斷的次

數(shù)，放寬了CPU對(duì)中斷響應(yīng)的時(shí)間要求，例如打印、文件訪問(wèn)，網(wǎng)絡(luò)收發(fā)等場(chǎng)

合，均要用到緩沖技術(shù)。

33、在不同網(wǎng)絡(luò)節(jié)點(diǎn)的對(duì)等層之間通信需要的是()，

A、模塊接E1

B、對(duì)等層協(xié)議

C、電信號(hào)

D、傳輸介質(zhì)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：本題考查計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)，注意對(duì)等層是指在計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議層

次中，將數(shù)據(jù)直接傳遞給對(duì)方的任何兩個(gè)同樣的層次，因此對(duì)等層之間通信必須需

要對(duì)等層之間的協(xié)議，這里選項(xiàng)A是相鄰層之間通信所必需的，選項(xiàng)C和D屬于

物理層，答案是B。

34、關(guān)于數(shù)據(jù)交換，下列敘述不正確的是()。

A,線路交換面向連接

B、分組交換比報(bào)文交換具有更好的網(wǎng)絡(luò)響應(yīng)速度

C、報(bào)文交換無(wú)存儲(chǔ)轉(zhuǎn)發(fā)過(guò)程

D、分組交換有存儲(chǔ)轉(zhuǎn)發(fā)過(guò)程

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：該題考查數(shù)據(jù)交換的原理，要明確報(bào)文是一份完整的信息，而分組是

報(bào)文分組的簡(jiǎn)稱，乂叫信息包，將報(bào)文劃分為若干格式化信息單位作為網(wǎng)絡(luò)層的數(shù)

據(jù)傳輸單元。分組交換方式：將一份完整的報(bào)文劃分為若干組，每個(gè)分組獨(dú)立的

從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)，目的節(jié)點(diǎn)收到這些分組后，再組裝成源報(bào)文。其特點(diǎn)是

化整為零,即將完整的較長(zhǎng)的報(bào)文劃分為較小的分組,以分組單位傳輸數(shù)據(jù)C優(yōu)點(diǎn)

是減少節(jié)點(diǎn)緩沖區(qū)容量，并有利于差錯(cuò)控制。而存儲(chǔ)轉(zhuǎn)發(fā)是指每個(gè)節(jié)點(diǎn)均設(shè)有緩

沖區(qū)，分組到達(dá)某節(jié)點(diǎn)后，先存儲(chǔ)在緩沖區(qū)中，等待輸出鏈路空閑時(shí)在轉(zhuǎn)發(fā)到下一

個(gè)節(jié)點(diǎn)。本題中面向連接的只有線路交換，存儲(chǔ)轉(zhuǎn)發(fā)只有分組和報(bào)文，由于分組

交換的靈活性，使其具有更好的響應(yīng)速度，因此答案是C。

35、當(dāng)DHCP客戶計(jì)算機(jī)第一次啟動(dòng)或初始化IP時(shí)，廣播發(fā)送給本地子網(wǎng)的消息

是()。

A、DHCPDISCOVER

B、DHCPREQUEST

C、DHCPOFFER

D、DHCPACK

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：本題考查DHCP協(xié)議的工作原理，需要IP地址的主機(jī)在啟動(dòng)時(shí)就向

DHCP服務(wù)器廣播發(fā)送發(fā)現(xiàn)報(bào)文(DHCPDISCOVER),這時(shí)該主機(jī)就成為DHCP客

戶。本地網(wǎng)絡(luò)上所有主磯都能收到此廣播報(bào)文，但只有DHCP服務(wù)器才回答此廣

播報(bào)文。DHCP服務(wù)器先在其數(shù)據(jù)庫(kù)中查找該計(jì)算機(jī)的配置信息。若找到，則返回

找到的信息。若找不到，則從服務(wù)器的IP地址池(addresspOOl)中取一個(gè)地址分配

給該計(jì)算機(jī)。DHCP服務(wù)器的回答報(bào)文叫做提供報(bào)文(DHCPOFFER)?？蛻粲?jì)算機(jī)

初始化IP的時(shí)候，首先要查找DHCP服務(wù)器，因此要發(fā)送的消息是DHCP

DISCOVER,答案是A。

36、網(wǎng)絡(luò)由6個(gè)路由器互連而成，路由器之間的鏈路費(fèi)用如下圖所示，從PC機(jī)到

服務(wù)器的最短路徑和通路費(fèi)用是()。

A、1—>3->6,7

B、1-4->5-6,4

C、14—3——>6,6

D、1-2T4—5—6,7

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：本題考查鏈路狀態(tài)路由算法，將網(wǎng)絡(luò)看成連通圖。每條鏈路以其“費(fèi)

用”為權(quán)值。通過(guò)Dijkstra最短路徑算法求出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，本題

中，就是以PC機(jī)所連接的路由器1為根節(jié)點(diǎn)，計(jì)算到達(dá)其他網(wǎng)絡(luò)的最短路徑，也

就是費(fèi)用最小的路徑，這樣可以直接從選項(xiàng)中得出答案，是B。

37、一個(gè)B類網(wǎng)絡(luò)的子網(wǎng)掩碼為255.255.252.0,則該B類網(wǎng)絡(luò)的主機(jī)數(shù)目是

()o

A、2046

B、1022

C、510

D、128

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：本題考查IPv4字網(wǎng)劃分，首先明確B類網(wǎng)絡(luò)的掩碼是

255.255.0.0,而192的二進(jìn)制是11111100,由此可知可劃分26=64個(gè)子網(wǎng),

每個(gè)子網(wǎng)的主機(jī)數(shù)為2?—2=2,因此該B類網(wǎng)絡(luò)的主機(jī)數(shù)目是64x2=128,因此答

案是D。

38、在TCP報(bào)文段的報(bào)頭中，窗口字段的作用是()。

A、報(bào)頭中32bit字節(jié)的數(shù)量

B、說(shuō)明對(duì)方端口的數(shù)量

C、控制對(duì)方的發(fā)送流量

D、說(shuō)明網(wǎng)絡(luò)的負(fù)荷能力

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：本題考查TCP報(bào)文段的作用窗口大?。河糜诹髁靠刂?。表示在確認(rèn)

了的字節(jié)之后還可以發(fā)送多少字節(jié)。窗口大小也允許為0,表示它已經(jīng)收到了包括

確認(rèn)號(hào)減1在內(nèi)的所有數(shù)據(jù)段，但接收方急需暫停接受數(shù)據(jù)。對(duì)于窗口字段，占2

個(gè)字節(jié)，用來(lái)控制對(duì)方發(fā)送的數(shù)據(jù)量，并不能說(shuō)明網(wǎng)絡(luò)的負(fù)荷能力，因此答案是

Co

39、關(guān)于以太網(wǎng)交換機(jī)，下面的論述中不正確的是（）。

A、交換機(jī)工作在數(shù)據(jù)鏈路層

B、交換機(jī)的每個(gè)端口形成一個(gè)沖突域

C、交換機(jī)支持多端口同時(shí)收發(fā)數(shù)據(jù)

D、交換機(jī)是一種多端口中繼器

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：本題考查交換機(jī)的工作原理和特性，交換機(jī)是工作與數(shù)據(jù)鏈路層的網(wǎng)

絡(luò)設(shè)備，每個(gè)端口是獨(dú)立的沖突域，交換機(jī)的交換結(jié)構(gòu)保證了多端口同時(shí)進(jìn)行數(shù)據(jù)

交換，多端口的中繼器可以認(rèn)為是集線器，其所有端口處于同一個(gè)沖突域內(nèi)，囚此

答案為D。

40、一臺(tái)主機(jī)要解析www.abc.edu.cn的IP地址，如果這臺(tái)主機(jī)配置的域名服

務(wù)器為202.120.66.68,因特網(wǎng)頂級(jí)域名服務(wù)器為11.2.8.6,而存儲(chǔ)

www.abc.edu.cn其IP地址對(duì)應(yīng)關(guān)系的域名服務(wù)器為202.113.16.10,那么

這臺(tái)主機(jī)解析該域名通常首先查詢的服務(wù)器是（）。

A、202.120.66.68域名服務(wù)器

B、11.2.8.6域名服務(wù)器

C、202.113.16.10域名服務(wù)器

D、不能確定，可從這三個(gè)域名服務(wù)器中任選一個(gè)

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：本題考查域名解析的過(guò)程，一個(gè)主機(jī)發(fā)出DNS查詢報(bào)文時(shí)，這個(gè)查

詢報(bào)文首先被送往該主磯的本地域名服務(wù)器。當(dāng)本地域名服務(wù)器不能立即答某個(gè)

主機(jī)的查詢時(shí)，該本地域名服務(wù)器就以DNS客戶的身份向某一根域名服務(wù)器查

詢。若根域名服務(wù)器也沒(méi)有該主機(jī)的信息時(shí)（但此時(shí)根域名服務(wù)器一定知道該主機(jī)

的授權(quán)域名服務(wù)器的IP地址），有兩種做法：（1）遞歸查詢：根域名服務(wù)器向該主

機(jī)的授權(quán)域名服務(wù)器發(fā)送DNS查詢報(bào)文，查詢結(jié)果再逐級(jí)返回給原主機(jī)；（2）遞歸

與迭代相結(jié)合的方法：艱域名服務(wù)器把授權(quán)域名服務(wù)器的IP地址返回給本地域名

服務(wù)器，由本地域名服務(wù)器再去查詢。無(wú)論是遞歸方式，還是迭代方式，主機(jī)進(jìn)

行域名解析的第一步都是向自己的本地域名服務(wù)器發(fā)起請(qǐng)求，因此答案為Ao

二、綜合應(yīng)用題（本題共7題，每題7.0分，共7分。）

41、已知一組關(guān)鍵字為(26,36,41,38,44,15,68,12,6,51,25),用鏈地

址法解決沖突。假設(shè)裝填因子a=0.75,散列函數(shù)的形式為H(K尸KMODP,回

答下列問(wèn)題：(1)構(gòu)造散列函數(shù)；(2)畫(huà)出散列表；(3)計(jì)算出等概率情況下查找成

功的平均查找長(zhǎng)度；(4)計(jì)算出等概率情況下查找不成功的平均查找長(zhǎng)度。

標(biāo)準(zhǔn)答案：由a=0.75,得表長(zhǎng)75n5。(1)在一般情況下，H(K)=K

MODP中，P取質(zhì)數(shù)或者不包含小于20的質(zhì)因數(shù)的和數(shù)，因此選擇P=13。散列函

數(shù)H(K)=KMOD13。(2)散列表：

1361A

碗|T"HUJ"―書(shū)】ITH251Al

(3)等概率情況下查找

成功的平均查找長(zhǎng)度：ASL=(1x7+2x2+3x1+4x1)/11=18/11o(4)等概率情況下

查找不成功的平均查找長(zhǎng)度：ASL=(lx5+2x1+4x1)/13=11/13。

知識(shí)點(diǎn)解析：本題是對(duì)散列表的一種常見(jiàn)考杳方式，題目的難點(diǎn)是求查找成功和不

成功的平均查找長(zhǎng)度。用鏈地址法解決沖突構(gòu)造散列表，并對(duì)查找性能進(jìn)行分析，

具體解題步驟如下。

42、已知L為沒(méi)有頭結(jié)點(diǎn)的單鏈表中第一個(gè)結(jié)點(diǎn)的指針，每個(gè)結(jié)點(diǎn)數(shù)據(jù)域存放一

個(gè)字符，該字符可能是英文字母字符或數(shù)字字符或其它字符，編寫(xiě)算法構(gòu)造三個(gè)以

帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類字符。(要求用最少

的時(shí)間和最少的空間)。

標(biāo)準(zhǔn)答案：voidOneToThree(LinkList&L,&la,&ld,&lo){/*L是無(wú)頭結(jié)點(diǎn)的單

鏈表第一個(gè)結(jié)點(diǎn)的指針，鏈表中的數(shù)據(jù)域存放字符。本算法將鏈表L分解成含有

英文字母字符、數(shù)字字符和其它字符的帶頭結(jié)點(diǎn)的三個(gè)循環(huán)鏈表*/

la=(LinkLisl)inallou(sizeof(LN(j(Je))；//建立三個(gè)鏈表的頭結(jié)點(diǎn)

ld=(LinkList)malloc(sizeof(LNode))；lo=(LinkList)malloc(sizeof(LNode))；la

一>next=la；//置三個(gè)循環(huán)鏈表為空表Id一>next=ld；lo_*>rlext=lo；

while(L!=NULL){//分解原鏈表廠L；L=L->next；//L指向待處理結(jié)點(diǎn)的后

繼if(r->data>=ta,&&r一>data<=tz,||r一>data>=tA,&&r一>data<=tz,){r

一>next=la一〉nexl；//處理字母字符la—^>next=r；}elseif(r一>dala>='O'&&r

-,>data<=<9,){r一>next=ld->next；//處理數(shù)字字符Id—*>next=r；}else(r

->next=lo->next；//處理其它符號(hào)lo—>next=r；}}}

知識(shí)點(diǎn)解析：將一個(gè)結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽址膯捂湵?，分解成含有字母字符、?shù)字字符

和其它字符的三個(gè)循環(huán)鏈表，首先要構(gòu)造分別含有這三類字符的表頭結(jié)點(diǎn)。然后從

原鏈表第一個(gè)結(jié)點(diǎn)開(kāi)始，根據(jù)結(jié)點(diǎn)數(shù)據(jù)域是字母字符、數(shù)字字符和其它字符而分別

插入到三個(gè)鏈表之一的鏈表。注意：不要因結(jié)點(diǎn)插入新建鏈表而使原鏈表斷鏈。另

外，題目并未要求鏈表有序，插入采用“頭插法”，每次插入的結(jié)點(diǎn)均成為所插入鏈

表的第一元素的結(jié)點(diǎn)即可。

43、下圖所示的CPU邏輯框圖中，有兩條獨(dú)立的總線和兩個(gè)獨(dú)立的存儲(chǔ)器。已知

指令存儲(chǔ)器IM最大容量為16384字(字長(zhǎng)18位)，數(shù)據(jù)存儲(chǔ)器DM最大容量是

65536字(字長(zhǎng)I6位)。各寄存器均有“打入”(Rm)“送出”(RoM控制命令，但圖口未

BUS,

(1)指出下列寄存器的位數(shù):程序計(jì)數(shù)器PC,指令寄存器IR,累加器AC。、AC),

通用寄存器Ro?R3,指令存儲(chǔ)器地址寄存器IAR,指令存儲(chǔ)器數(shù)據(jù)存儲(chǔ)器IDR,

數(shù)據(jù)存儲(chǔ)器地址寄存器DAR,數(shù)據(jù)存儲(chǔ)器數(shù)據(jù)寄存器DDR。(2)設(shè)機(jī)器指令格式

1713120

|OP|X|

為1--------------------------加法指令可寫(xiě)為“ADDX(Ri)”，其功能是

(ACo)+((Ri)+X)-ACi，其中((Ri)+X)部分通過(guò)尋址方式指向數(shù)據(jù)存儲(chǔ)器DM?，F(xiàn)取

Ri為Ri。畫(huà)出ADD指令的指令周期流程圖，寫(xiě)明“數(shù)據(jù)通路”和相應(yīng)的微操作控制

信號(hào)。

標(biāo)準(zhǔn)答案：(1)PC=14位，IR=18位ACo=ACi=16位,Ro?R3=16位IAR=14位,

IDR=18位DAR=16位，DDR=16位(2)加法指令“ADDX(Ri)”是一條一地址指令，

其中一個(gè)操作數(shù)來(lái)自ACo,另一個(gè)操作數(shù)在DM中，其地址由通用寄存器的自容

（Ri）加上指令格式中的X量值決定。其指令周期流程圖如卜.圖所示，相應(yīng)的微程序

控制信號(hào)標(biāo)在框圖外面。

知識(shí)點(diǎn)解析：（1）由于指令存儲(chǔ)器IM的容量為16384*18,數(shù)據(jù)存儲(chǔ)器DM的容量

為65536*16,可以推出相應(yīng)寄存器的位數(shù)。（2）根據(jù)數(shù)據(jù)通路，可以寫(xiě)出加法指令

的微操作控制信號(hào)。

44、設(shè)某計(jì)算機(jī)有四級(jí)中斷A、B、C、D,其硬件排隊(duì)優(yōu)先級(jí)次序?yàn)锳>B>C>D。

中斷服務(wù)程序所需時(shí)間

ASpn

B

C

D12度

下表列出了執(zhí)行每級(jí)中斷服務(wù)程序所需的時(shí)間。如

果以執(zhí)行中斷服務(wù)程序的時(shí)間作為確定中斷優(yōu)先級(jí)的尺度：時(shí)間越短優(yōu)先級(jí)越高。

⑴請(qǐng)指出如何為各級(jí)中斷服務(wù)程序設(shè)置屏蔽碼？（2）如果A、B、C、D分別在62、

8w、10由、0四時(shí)刻發(fā)出中斷請(qǐng)求，請(qǐng)畫(huà)出CPU執(zhí)行中斷服務(wù)程序的序列。（3）基

于上題，請(qǐng)計(jì)算上述四個(gè)中斷服務(wù)程序的平均執(zhí)行時(shí)間。

標(biāo)準(zhǔn)答案：（1）如果以執(zhí)行中斷服務(wù)程序的時(shí)間長(zhǎng)短來(lái)確定中斷優(yōu)先級(jí)（時(shí)間越短優(yōu)

先級(jí)越高），可知中斷處理的次序?yàn)椋篊>A>D>Bo中斷服務(wù)程序屏蔽碼見(jiàn)下表。

中斷解喙碼

中斷海

ABC

A1101

B0100

C1111

D0101

(2)根據(jù)各級(jí)中斷源發(fā)出的中斷請(qǐng)求信號(hào)的時(shí)

刻，畫(huà)出CPU執(zhí)行中斷服務(wù)程序的序列，如下圖所示。

中斷服務(wù)

B請(qǐng)求中斷處理的優(yōu)先級(jí)

別是C>A>D>B。0四時(shí)，D請(qǐng)求來(lái)到，由于沒(méi)有其他的中斷請(qǐng)求，所以開(kāi)始執(zhí)行

中斷服務(wù)程序D。第6國(guó)時(shí)，A請(qǐng)求來(lái)到，A的優(yōu)先級(jí)高于D,轉(zhuǎn)去執(zhí)行中斷服務(wù)

程序A。第8四時(shí)，B請(qǐng)求來(lái)到，由于B的優(yōu)先級(jí)低于A,所以不響應(yīng)B請(qǐng)求，繼

續(xù)執(zhí)行中斷服務(wù)程序A。第10g時(shí)，C請(qǐng)求來(lái)到，C的優(yōu)先級(jí)最高，雖然此時(shí)中

斷服務(wù)程序A還沒(méi)有結(jié)束，也必須暫停轉(zhuǎn)去執(zhí)行中斷服務(wù)程序C。中斷服務(wù)程序

C所需時(shí)間為3弊，當(dāng)?shù)?3即時(shí)，中斷服務(wù)程序C執(zhí)行完畢，返回執(zhí)行中斷服務(wù)

程序A。第14g時(shí)，中斷服務(wù)程序A執(zhí)行完畢(總共執(zhí)行時(shí)間52)，返回執(zhí)行中斷

服務(wù)程序D。第20a時(shí)中斷服務(wù)程序D執(zhí)行完畢(總共執(zhí)行時(shí)間12g),返回現(xiàn)行

程序-因?yàn)镽請(qǐng)求還存在，所以此時(shí)開(kāi)始執(zhí)行中斷服務(wù)程序R,直至第35四時(shí)結(jié)

束(總共執(zhí)行時(shí)間35.)，(3)由于在35卬時(shí)間內(nèi)，完成了4級(jí)中斷的處理，所以平

均執(zhí)行時(shí)間=35+4=8.752。

知識(shí)點(diǎn)解析：硬件排隊(duì)電路次序又稱中斷響應(yīng)次序，它是不可以改變的，在不改變

硬件排隊(duì)電路的前提下，通過(guò)改變中斷屏蔽字可以改變中斷處理的優(yōu)先級(jí)，使原級(jí)

別較低的中斷源變成較高的級(jí)別，這便稱為中斷升級(jí)。實(shí)際上中斷升級(jí)是一種動(dòng)態(tài)

改變優(yōu)先級(jí)的方法。

45、某大學(xué)的閱覽室共有300個(gè)座位，同學(xué)進(jìn)入時(shí)必須先在管理處用學(xué)生證換取座

位牌，若座位滿了，同學(xué)就要在閱覽室外等候。當(dāng)有同學(xué)離開(kāi)時(shí)，要到管理處用座

位牌換回學(xué)生證。請(qǐng)畫(huà)出流程圖，試用一種類語(yǔ)言，利用信號(hào)量和P、V操作，描

述同學(xué)進(jìn)入和離開(kāi)閱覽室的過(guò)程。

標(biāo)準(zhǔn)答案：同學(xué)進(jìn)入閱覽室的同步算法如下流程圖所示。typcdcfintscm叩hore；

semaphoremutex=1；semaphoresit=300：voidstudent(){P(sit)；P(mutex)；

mark_sit()；V(mutex)；readingO；P(mutex)；release_sil()；V(mutex)；V(sit)；

leave()；}一

知識(shí)點(diǎn)解析：本題考查進(jìn)程間同步的問(wèn)題。用信號(hào)量是可以解決同步問(wèn)題的。假設(shè)

同學(xué)有很多，晚自習(xí)時(shí)都希望在圖書(shū)館的閱覽室占到一個(gè)座位，但是，閱覽室的座

位數(shù)是有限的，我們不妨設(shè)該數(shù)值為一個(gè)資源信號(hào)量，用它來(lái)控制進(jìn)入閱覽室的同

學(xué)的數(shù)量。另外設(shè)互斥量mutex,代表在管理處換取座位牌時(shí);管理處的臨界資

源，初始值為1,用來(lái)防止兩個(gè)及以上的同學(xué)同時(shí)換取座位牌而造成混亂。

46、某虛擬存儲(chǔ)系統(tǒng)中有一個(gè)進(jìn)程共有6頁(yè)(0?5),其中代碼占3頁(yè)(0?2),數(shù)據(jù)

占1頁(yè)(3),數(shù)據(jù)堆占1頁(yè)(4),用戶棧占1頁(yè)(5)。它們依次存放在外存的22,23,

25,26存儲(chǔ)塊。當(dāng)前，代碼頁(yè)已經(jīng)分配在物理內(nèi)存的66,67,87頁(yè)，數(shù)據(jù)頁(yè)為

31,并已經(jīng)進(jìn)行了修改。數(shù)據(jù)堆頁(yè)還沒(méi)有分配內(nèi)存，用戶棧分配在01頁(yè)。請(qǐng)問(wèn)：

⑴頁(yè)表中應(yīng)該包含哪些項(xiàng)目？請(qǐng)?zhí)顚?xiě)此頁(yè)表(見(jiàn)下表)。(2)若內(nèi)存堆申請(qǐng)內(nèi)存，因無(wú)

分配物理內(nèi)存而產(chǎn)生缺頁(yè)H」斷，此時(shí)內(nèi)存無(wú)空閑頁(yè)面，則采用LRU頁(yè)面淘汰算法

選中內(nèi)存的那個(gè)頁(yè)面?操作系統(tǒng)作何處理?頁(yè)表乂如何變化?設(shè)當(dāng)前時(shí)刻為虛擬時(shí)間

1256oo

渡撇頁(yè)號(hào)存在位修改位保護(hù)方式引用時(shí)間外存塊號(hào)內(nèi)〃近枇號(hào)

01203

11178

21225

31020

4—

51250

標(biāo)準(zhǔn)答案：(1)頁(yè)表填寫(xiě)見(jiàn)下:

魏就寅號(hào)存在位修改位引用位保妒方式引用時(shí)間外存塊號(hào)內(nèi)存頁(yè)常9

0101可球、可運(yùn)行12032266

1101可鼻、町運(yùn)行11782367

2101可饞、即運(yùn)行12252587

3111可讀、可寫(xiě)10202631

40—町派、可寫(xiě)**—

S101可京，可寫(xiě)1250—01

(2)當(dāng)內(nèi)存堆申請(qǐng)內(nèi)存，產(chǎn)生缺頁(yè)中斷，采用LRU頁(yè)面淘汰算法選中數(shù)據(jù)頁(yè)，操作

系統(tǒng)根據(jù)頁(yè)表的指示，咳頁(yè)已經(jīng)被改寫(xiě)了，所以首先要將該頁(yè)寫(xiě)回外存塊中，修改

該頁(yè)表，然后將該頁(yè)分配給數(shù)據(jù)堆頁(yè)，重新修改數(shù)據(jù)堆頁(yè)的頁(yè)表，返回到缺頁(yè)中斷

的那條指令，繼續(xù)執(zhí)行。修改的頁(yè)表如下：

存在位修就值引用位保「方式引用時(shí)阿外“埃號(hào)

0101彳?，彳■行12032266

1101可使,可運(yùn)行11782367

2101可讀?4運(yùn)行12252S87

31-*01——可博.可耳1020—2631—

40-1—0一］可博.可寫(xiě)—1256■-*31

S101可博,阿耳1250一01

邏輯4、5頁(yè)只要從來(lái)沒(méi)有被換出到交換區(qū)，就沒(méi)有外存塊號(hào)。

知識(shí)點(diǎn)解析：內(nèi)存計(jì)算的變化很多，本題主要考查考生對(duì)內(nèi)存管理的理解。根據(jù)題

意，本系統(tǒng)采用的是虛隊(duì)存儲(chǔ)系統(tǒng)，因此立即可以想到，進(jìn)程一定是部分調(diào)入。從

題目給出的條件中可知，進(jìn)程共有6頁(yè)(0?5),其中代碼占3頁(yè)(0-2)，數(shù)據(jù)占1

頁(yè)(3),數(shù)據(jù)堆占I頁(yè)(4),用戶棧占I頁(yè)(5)。這個(gè)條件顯然是虛擬存儲(chǔ)管理的實(shí)際

情況，進(jìn)程的邏輯頁(yè)有6頁(yè)，因此分配的虛擬空間也是6頁(yè)。按題意，頁(yè)面依次存

放在外存的22,23,25,26存儲(chǔ)塊。這個(gè)條件告訴我們，進(jìn)程對(duì)應(yīng)的外存是4

塊，顯然，有2頁(yè)是進(jìn)程運(yùn)行過(guò)程中產(chǎn)生的，一般數(shù)據(jù)堆和棧是在運(yùn)行過(guò)程中產(chǎn)生

的，在虛擬存儲(chǔ)管理中，數(shù)據(jù)堆和棧對(duì)應(yīng)的外存應(yīng)該在對(duì)換區(qū)上，而且，只有在換