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

一、單選題(本題共40題，每題1.0分，共40分。)

1、設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是()。void

fun(intn){inti>k；for(i=1；i<=n；i++)for(j=l；j<=n；j++){k=l：while(k<

=n)k=5*k；})

A、O(n2log2n)

B、O(n-log5n)

C>O(n2log5n)

D、O(n3)

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

知識點(diǎn)解析：基本運(yùn)算語句是k=5*k，設(shè)其執(zhí)行時(shí)間為T(n)。對于j每循環(huán)一次，

該語句的執(zhí)行次數(shù)為m,有：5m<n,即mSlog5n。所以：

■■■■

22

T(n)=22析=桁22]=mn?=nlogsn=()(nlog5n)

wIJ1

2、利用棧求表達(dá)式的值時(shí)，設(shè)立運(yùn)算數(shù)棧OPND。假設(shè)OPND只有兩個存儲單

元，在下列表達(dá)式中，不發(fā)生溢出的是()。

A、A-B*(C-D)

B、(A-B)*C-D

C、(A-B*C)-D

D、(A-B)*(C-D)

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

知識點(diǎn)解析?：利用棧求表達(dá)式的值時(shí)，將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式以及進(jìn)行后

綴表達(dá)式求值這兩步操作可以一起進(jìn)行，需要設(shè)立運(yùn)算符棧OPTR和運(yùn)算數(shù)棧

oPND兩個棧。例如求選項(xiàng)A的表達(dá)式A—B*(C—D)的過程如表6—5所列：

?6-5求A-B?(C-D)裊達(dá)式值的過程

當(dāng)前字符運(yùn)一符棧OPTR運(yùn)算敷檢OPNDift明

AA

—一A

B一AB

■—■AB

(-?<AB

C—?(ABC

一-?(―ABC

D-?(-ABCD

)ABT,執(zhí)行C-D運(yùn)算.令Ti—C-D

一AT,執(zhí)行B?T1運(yùn)算?令TLB?T,

T,執(zhí)行A-Tz運(yùn)算?令T,=A-Tz

按照上述過程可知，選項(xiàng)A求值時(shí)，運(yùn)算數(shù)棧OPND的大小至少為4。例如求選

項(xiàng)B的表達(dá)式(A—B)*C—D的過程如表6—6所列：

衰6?6求(A-B)-C-D寰達(dá)式值的過程

當(dāng)前字符運(yùn)K符棧OPTR運(yùn)算熟棧OPND說明

((

A(A

一(-A

B(-AB

)T.AHT.-AB

■.T,

CT,C

一—Ti執(zhí)行Ti?Cifi尊?令TLL?C

D一T,D

T,執(zhí)行七一口運(yùn)算?令丁,二3一1)

按照上述過程可知，選項(xiàng)B求值時(shí)，運(yùn)算數(shù)棧OPND的大小至少為2。類似地,

選項(xiàng)C、D求值時(shí)，運(yùn)算數(shù)棧OPND的大小分別至少為3、3.因此本題答案為

Bo

3、輸入受限的雙端隊(duì)列是指元素只能從隊(duì)列的一端輸入，但可從隊(duì)列的兩端輸

出。若有8,1,4,2依次進(jìn)入輸入受限的雙端隊(duì)列，則得不到的輸出序列是()。

A、2814

B、1482

C、4218

D、2148

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

知識點(diǎn)解析：設(shè)el端可輸人可輸出，e2端僅能輸出；且設(shè)某元素x從el端進(jìn)隊(duì)為

Xe］進(jìn)進(jìn)，從el端出隊(duì)為Xel出，從e2端出隊(duì)為Xe2H；，則各選項(xiàng)出隊(duì)情況如下表

6—7所列。

寰6-78,1,4,2進(jìn)隊(duì)/出隊(duì)情況分析

發(fā)期，出進(jìn)隊(duì)/出隊(duì)過周實(shí)際■出

28148,s*1*22?Lilt2814

1482H82

42188.逢?Uie?2f.a*trim4218

2148將使4先于1輸出進(jìn)7格使8先于4?出不可能

4、一個具有1025個結(jié)點(diǎn)的二叉樹的高度為（）。

A、11

B、10

C、11至1025之間

D、D至1024之間

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

知識點(diǎn)解析：一棵二叉對每層只有1個結(jié)點(diǎn)，則具有1025個結(jié)點(diǎn)的二叉樹的最大

高度為1025o一個具有1025個結(jié)點(diǎn)的完全二叉樹的高度為11。這一個具有1025

個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為11至1025之間。

5、以下關(guān)于二叉排序樹的說法正確的是（）。I在二叉排序樹中，每個結(jié)點(diǎn)的關(guān)

鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小口每個結(jié)點(diǎn)的關(guān)鍵字都比左孩子

關(guān)鍵字大，比右孩子關(guān)健字小，這樣的二叉樹都是二叉排序樹m在二叉排序樹

中，新插入的關(guān)鍵字總是處于最底層W在二叉摔序樹中，新結(jié)點(diǎn)總是作為葉子

結(jié)點(diǎn)來插入的V二叉排序樹的查找效率和二叉排序樹的高度有關(guān)

A、I、n、W、v

B、□、III、IV

c、I、m、v

D、I、W、V

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

知識點(diǎn)解析：對于二叉排序樹，左子樹上所有記錄的關(guān)鍵字均小于根記錄的關(guān)鍵

字，右子樹上所有記錄的關(guān)鍵字均大于根記錄的關(guān)鍵字。而不是僅僅與左、右孩子

的關(guān)鍵字進(jìn)行比較。在二叉排序樹中，新插入的關(guān)鍵字總是作為葉子結(jié)點(diǎn)來插入

的，但是葉子結(jié)點(diǎn)不一定總是處于最底層。對于每一棵特定的二叉排序樹，均可按

照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關(guān)鍵字，構(gòu)迨所

得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。最

好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2n

成正比。

6、簡單無向圖的鄰接矩陣是對稱的，可以時(shí)其進(jìn)行壓縮存儲。若無向圖G有n個

結(jié)點(diǎn)，其鄰接矩陣為A[l..n,1..n],且壓縮存儲在B[l..k],則k的值至

少為()。

A、n(n+l)/2

B、n2/2

C、(n-l)(n+l)/2

D、n(n-l)/2

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

知識點(diǎn)解析：簡單無向圖的鄰接矩陣是對稱的，且對角線元素均是0,故壓縮存儲

只需存儲下三角或是上三角(均不包括對角線)即可。故有(上三角形式)：

k=(n-l)+(n-2)+...+l+0=n2-(1+2+...+n)=n(n-l)/2。

7、若無向圖G=(V,E)中含8個頂點(diǎn)，為保證圖G在任何情況下都是連通的，則

需要的邊數(shù)最少是()。

A、7

B、21

C、22

D、28

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

知識點(diǎn)解析：本題考查圖的基本概念。要保證無向圖G在任何情況下都是連通

的，即任意變動圖G中的邊，G始終保持連通。首先需要圖G的任意7個結(jié)點(diǎn)構(gòu)

成完全連通子圖Gi，需n(n-l)/2=7x(7-l)/2=21條邊，然后再添加一條邊將第8

個結(jié)點(diǎn)與G]連接起來，共需22條邊。本題非常容易錯誤地選擇選項(xiàng)A,主要原

因是對“保證圖G在任何情況下都是連通的”的理解，分析選項(xiàng)A,在圖G中，具

有8個頂點(diǎn)7條邊并不能保證其一定是連通圖，即有n-1條邊的圖不一定是連通

圖。分析選項(xiàng)D,圖G有8個頂點(diǎn)28條邊，那么圖G一定是無向完全圖，無向完

全圖能保證其在任何情況下都是連通的，但是這不符合題目中所需邊數(shù)最少的要

求。

8、用遞歸算法實(shí)現(xiàn)n個不同元素的有序序列的折半查找，采用一個遞歸工作棧

時(shí)，該棧的最小容量應(yīng)為()。

A、n

B>[n/21

C、[log2n]

D>[log2n]+l

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

知識點(diǎn)解析：根據(jù)折半查找的過程，由于需要棧結(jié)構(gòu)實(shí)現(xiàn)遞歸算法，棧的容量應(yīng)該

保證能存放查找失敗時(shí)所有未完成運(yùn)行的算法的活動記錄。第一次調(diào)用該算法

時(shí)，棧中加入了一條查找記錄，表示待查有序表中元素的個數(shù)為I】；第二次調(diào)用

時(shí)，無論是在前半?yún)^(qū)還是后半?yún)^(qū)查找，棧中又加入了一條查找記錄，所確定的查找

區(qū)間中的元素最多為n/2：第三次調(diào)用時(shí)，棧中又加入了一條查找記錄，所確定

的查找區(qū)間中的元素最多為n/4；依次類推，當(dāng)所確定的查找區(qū)間中的元素為0

時(shí)，遞歸調(diào)用該算法的次數(shù)為|log2n]+l次，查找結(jié)束。折半查找法在查找成功時(shí)

和給定值進(jìn)行比較的關(guān)鍵字個數(shù)至多是[log2n]+l:在查找不成功時(shí)和給定值進(jìn)行比

較的關(guān)鍵字個數(shù)最多也不超過[log2n]+l。

9、在采用線性探測法處理沖突所構(gòu)成的散列表上進(jìn)行查找，可能要探測多個位

置，在查找成功的情況下，所探測的這些位置的鍵值()。

A、一定都是同義詞

B、一定都不是同義詞

C、不一定都是同義詞

D、都相同

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

知識點(diǎn)解析：采用線性探測法處理沖突會產(chǎn)生堆積，即非同義詞爭奪同一個后繼地

址。

10、如果將中國人按照生日(不考慮年份，只考慮后、E1)來排序，那么使用下列排

序算法中最快的是()。

A、歸并排序

B、希爾排序

C、快速排序

D、基數(shù)排序

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

知識點(diǎn)解析：按照所有中國人的生日(月、日)排序，一方面待排序記錄個數(shù)n是非

常大的，另一方面關(guān)鍵字所含的排序碼為2,且一個排序碼基數(shù)為12,另一個為

31,都是較小的常數(shù)值，采用基數(shù)排序可以在O(n)內(nèi)完成排序過程。

11、用某種排序方法對線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序

時(shí),元素序列的變化情況如下：(1)25,84,21,47,15,27,68,35,20(2)20,

15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47,68,84

(4)15,20,21,25,27,35,47,68,84則采用的排序方法是()。

A、選擇排序

R、希爾排序

C、二路歸并排序

D、快速排序

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

知識點(diǎn)解析：本題主要考查各種排序的手工排序過程。選擇排序在每趟結(jié)束后可

以確定一個元素的最終位置，而題中第一趟結(jié)束后最小關(guān)鍵字并未出現(xiàn)在第一個位

置；歸并排序會在第一趟結(jié)束后，形成若干個部分有序的子序列，并且長度遞增，

直到最后的一個有序的完整序列；希爾排序也是形成部分有序的序列；快速排序以

某個元素為界將大于它和小于它的關(guān)鍵字劃分為兩個子序列，再將該元素放在中

間。觀察題中的元素排序過程，可知是快速排序。

12、若存儲周期100ns,每次讀出一個字節(jié)，則該存儲器的數(shù)據(jù)傳輸率為()。

A、32xl06b/s

B、8x10%/s

C、80Mb/s

D、80xl06b/s

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

知識點(diǎn)解析：由于存儲周期100ns,每次讀出一個字節(jié)，則數(shù)據(jù)傳輸率=8/

(100x10-9)=80x1()6位/秒。選項(xiàng)C的錯誤在于存在誤差，1M=1024xl024。

13、假定采用正EE754單精度浮點(diǎn)數(shù)格式表示一個數(shù)為45100000H,則該數(shù)的值

是()。

A、(+1.125)iox2,0

B、(+1.125)10x211

C、(+0.125)10X211

D、(+0.125)iox210

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

知識點(diǎn)解析：451OOOOOH=O1000101000100000000000000000000,符號位=0,

階碼=10001010,尾數(shù)=00100000000000000000000。階碼真值二10001010-

lllllll=10llB=llo因?yàn)殡[含了尾數(shù)最高數(shù)位，尾數(shù)為1.001,所以其真值為

(+1.125)10X2”。

14、字長相同的兩種浮點(diǎn)數(shù)，第一種階碼位數(shù)多，尾數(shù)位數(shù)少，第二種階碼位數(shù)

少，尾數(shù)位數(shù)多，階的底數(shù)都是2,則有()。

A、它們表示的數(shù)的范圍與精度相同

B、第一種數(shù)的范圍大，精度低

C、第二種數(shù)的范圍大，精度高

D、第一種數(shù)的范圍大，精度高

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

知識點(diǎn)解析：字長相同的兩種浮點(diǎn)數(shù)，階碼位數(shù)較多表示的數(shù)范圍越大，尾數(shù)越多

表示的精度越高。

15、以下關(guān)于校驗(yàn)碼的敘述中，正確的是()。I校驗(yàn)碼的碼距必須大于2II校驗(yàn)

碼的碼距越大檢錯糾錯能力越強(qiáng)HI增加奇偶校驗(yàn)位的位數(shù)可以提高奇偶校驗(yàn)的正

確性W采用奇偶校驗(yàn)可檢測出一位數(shù)據(jù)錯誤的位置并加以糾正V采用海明校驗(yàn)可

檢測出一位數(shù)據(jù)錯誤的位置并加以糾正VI循環(huán)冗余校驗(yàn)碼是通過除法運(yùn)算來建立

數(shù)據(jù)和校驗(yàn)位之間的約定關(guān)系的

A、I、m、v

B、口、W、VI

C、I、V、VI

D、n、v、vi

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

知識點(diǎn)解析：碼距大于等于2的數(shù)據(jù)校驗(yàn)碼，開始具有檢錯的能力。碼距越大，

檢、糾錯能力就越強(qiáng)；奇偶校驗(yàn)碼的碼距等于2,可以檢測出一位錯誤(或奇數(shù)位

錯誤)，但不能確定出錯的位置，也不能檢測出偶數(shù)位錯誤；海明碼的碼距大于

2,不僅可以發(fā)現(xiàn)錯誤，還能指出錯誤的位置，為自動糾錯提供了依據(jù)；循環(huán)冗余

校驗(yàn)碼則通過除法運(yùn)算來建立數(shù)據(jù)和校驗(yàn)位之間的約定關(guān)系。

16、若內(nèi)存地址區(qū)間為4000H?43FFH,每個存貯單元可存儲16位二進(jìn)制數(shù)，該

內(nèi)存區(qū)域用4片存儲器芯片構(gòu)成，則構(gòu)成該內(nèi)存所用的存儲器芯片的容量是()。

A、512xl6bit

B、256x8bit

C、256x16bit

D、1024x8bit

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

知識點(diǎn)解析：43FF-4000+1=400,即內(nèi)存區(qū)域?yàn)镮K個單元，總?cè)萘繛镮Kxl6。現(xiàn)

有4片存儲芯片構(gòu)成，則芯片容量為256xl6bit。

17、數(shù)據(jù)尋址和指令尋址的不同點(diǎn)在于()。

A、前者決定操作數(shù)地址，后者決定程序轉(zhuǎn)移地址

B、前者決定程序轉(zhuǎn)移地址，后者決定操作數(shù)地址

C、前者是短指令，后者是長指令

D、前者是長指令，后者是短指令

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

知識點(diǎn)解析：數(shù)據(jù)尋址尋找的是操作數(shù)的地址，指令尋址尋找的是下條指令的地

址，它決定于程序轉(zhuǎn)移地址。

18、流水計(jì)算機(jī)中，下列語句發(fā)生的數(shù)據(jù)相關(guān)類型是()。ADDRI,R2,R3；

(R2)+(R3)->R1ADDR4,RI,R5；(R1)+(R5)->R4

A、寫后讀

B、讀后寫

C>寫后寫

D、讀后讀

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

知識點(diǎn)解析：數(shù)據(jù)相關(guān)包括寫后讀相關(guān)(RAW)、寫后寫相關(guān)(WAW)、讀后寫相關(guān)

(WAR)o在這兩條指令中，都對R1進(jìn)行操作，其中前面對R1寫操作，后面對R1

讀操作，因此發(fā)生寫后讀相關(guān)。

19、卜列有關(guān)控制器的說法正確的是（）。

A、無論是組合邏輯控制器和時(shí)序邏輯控制器，都需要有程序計(jì)數(shù)器

B、微程序控制器不需要程序計(jì)數(shù)器，只要有微程序計(jì)數(shù)器

C、都可以不需要程序計(jì)數(shù)器

D、以上都不對

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

知識點(diǎn)解析：無論控制器的硬件實(shí)現(xiàn)方法有何不同，都需要程序計(jì)數(shù)器。對于微程

序控制器可能同時(shí)還有微程序計(jì)數(shù)器，這兩者并不矛盾。

2。、下面是關(guān)于目前流行的HJ機(jī)主板的敘述：I主板上通常包含微處理器插座

（或插槽）和芯片組口主板上通常包含ROMBIOS和存儲器（內(nèi)存條）插座HI主板上

通常包含PCI和AGP總線插槽W主板上通常包含IDE連接器其中正確的是（）。

A、僅I

B、僅I和口

c、僅I、n和m

D、I、n、in和w

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

知識點(diǎn)露析：關(guān)于PC機(jī)主板的四個描述都是正確的。

21、采用頁式內(nèi)存管理某虛擬存儲器，使用LRU頁面替換算法，假定內(nèi)存容量為

4個頁面，且開始時(shí)是空的，考慮下面的頁面訪問地址流（每次訪問在一個時(shí)間單

位內(nèi)完成）為1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7,

則頁面命中次數(shù)是（）。

A、24

B、14

C、16

D、6

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

知識點(diǎn)解析：LRU算法是堆棧型算法，按照頁面訪問地址流可以容易地得到命中

次數(shù)，如表6-8所列。

?6-8

地址流18178272183821317137

18178272183321317137

1811827218382131713

內(nèi)存

87188721138223371

711872213882222

命中HHHHHHHHHHHHHH

共命中14次。

22、外部設(shè)備打印機(jī)適合于連接的通道是（）。

A、數(shù)組多路通道

B、字節(jié)多路通道

C、選擇通道

D、任意一種通道

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

知識點(diǎn)解析：打印設(shè)備屬于低速設(shè)備，它適合于連接到字節(jié)多路通道上，一個字節(jié)

多路通道上連接多臺相同或不相同的低速設(shè)備，當(dāng)通道為一個設(shè)備傳送完一個字節(jié)

后，就轉(zhuǎn)去為另一個設(shè)備服務(wù)。

23、用戶程序在用戶態(tài)下使用陷入指令而引起的中斷是()。

A、故障中斷

B、外部中斷

C、不可屏蔽中斷

D、訪管中斷

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

知識點(diǎn)解析：本題考查用戶態(tài)和內(nèi)核態(tài)及其轉(zhuǎn)換的概念。在操作系統(tǒng)管理下的計(jì)算

機(jī)中，為保護(hù)系統(tǒng)的安全，對一部分處理機(jī)的指令限定使用對象，即只有操作系統(tǒng)

才可以執(zhí)行。而當(dāng)用戶需要使用這些特權(quán)指令時(shí)，必須調(diào)用特定的訪管指令，也稱

陷入指令，顧名思義由用戶態(tài)陷入到內(nèi)核態(tài)，從而從用戶態(tài)轉(zhuǎn)入內(nèi)核態(tài)，繼而可以

執(zhí)行特權(quán)指令；訪管指令引起的中斷稱為訪管中斷，它是用戶使用特權(quán)指令的唯一

人口。

24、下列所示關(guān)系中，不是信號量能實(shí)現(xiàn)的功能是()。

A、進(jìn)程同步

B、進(jìn)程互斥

C、執(zhí)行的前趨關(guān)系

D、進(jìn)程的并發(fā)執(zhí)行

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

知識點(diǎn)解析：本題考查信號量的功能.在多道程序技術(shù)系統(tǒng)中.信號量機(jī)制是一種

有效的實(shí)現(xiàn)進(jìn)程同步與互斥的工具。信號量可以實(shí)現(xiàn)的功能有：進(jìn)程的同步與互

斥，進(jìn)程執(zhí)行的前趨關(guān)系，進(jìn)程執(zhí)行的前趨關(guān)系實(shí)質(zhì)上是指進(jìn)程的同步關(guān)系。除此

以外，只有進(jìn)程的并發(fā)執(zhí)行不需要信號量來控制，因此正確答案為D。

25、下面是一個并發(fā)進(jìn)程的程序代碼，正確的說法是()。semaphorex1=x2=y=I；

intcl=c2=0：cobeginprocedurePlprocedureP2P(xl)；P(x2)if(++cl=l)P(y)；

if(++c2=l)P(y)；V(xl)；V(x2)；computer(A)；computer(B)；P(xl)；P(x2)；if(—

cl=0)V(y)；if(-c2=0)V(y)；V(xl)；V(x2)；endendcoend

A、進(jìn)程不會死鎖，也不會饑餓

B、進(jìn)程不會死鎖，但是會饑餓

C、進(jìn)程會死鎖，但是不會饑餓

D、進(jìn)程會死鎖，也會饑餓

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

知識點(diǎn)解析：本題考查PV操作與死鎖以及饑餓的關(guān)系。仔細(xì)考察程序代碼，我們

似曾相識，可以看出是一個擴(kuò)展的“單行線”的問題，也就是說，某單行線只允許單

方向的車輛通過，在單行線的人口設(shè)置信號量y,在告示牌上顯示某一時(shí)刻各方向

來車的數(shù)量cl和c2,要修改告示牌上的車輛數(shù)量必須互斥進(jìn)行，為此設(shè)置信號量

xl和x2。若某方向的車輛需耍通過時(shí)，首先要將該方向來車數(shù)量cl或c2增加1,

并查看自己是否是第一個進(jìn)入單行線的車輛，若是，則獲取單行線的信號量y，進(jìn)

入單行線。通過此路段以后出單行線時(shí)，將該方向的車輛數(shù)cl或c2減1（當(dāng)然是利

用xl或x2來互斥修改），并察看自己是否是最后一輛車，若是，則釋放單行線的

互斥量y,否則，保留信號量y,讓后繼車輛繼續(xù)通過。雙方的操作如出一轍。考

慮出現(xiàn)一個極端情況，即當(dāng)某方向的車輛首先占據(jù)單行線并后來者絡(luò)繹不絕時(shí)，另

一個方向的車輛就再沒有機(jī)會通過該單行線了。從而造成饑餓。由于有信號量的控

制，死鎖的可能性沒有了（即雙方同時(shí)進(jìn)入單行線，在中間相遇，造成雙方均無法

通過的情景）。

26、在操作系統(tǒng)中，進(jìn)程A與進(jìn)程B共享變量S1,進(jìn)程A與進(jìn)程C共享變量

S2,則進(jìn)程B和進(jìn)程C之間是（）。

A、必須互斥

B、必須同步

C、同步或互斥

D、無關(guān)系

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

知識點(diǎn)解析：進(jìn)程同步和進(jìn)程互斥是指多個相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，保證對

共享變量操作的正確性。這些進(jìn)程會互相競爭以及相互合作，在一些關(guān)鍵時(shí)刻點(diǎn)上

可能需要前后順序操作。這種順序操作必須有一個共同的操作對象，例如共享變量

等，當(dāng)不同的進(jìn)程對該共享變量進(jìn)行讀寫時(shí)，則必須互斥；只要雙方任何一方是只

讀的，則不存在互斥關(guān)系。若二個進(jìn)程互相之間無任何共享變量的話，就不存在同

步或互斥關(guān)系，本題中，進(jìn)程A與進(jìn)程B有關(guān)系，進(jìn)程A與進(jìn)程C有關(guān)系，進(jìn)程

B與進(jìn)程C并不存在遞延關(guān)系。

27、操作系統(tǒng)中為實(shí)現(xiàn)多道程序并發(fā)，對內(nèi)存管理可以有多種方式，其中內(nèi)存利用

率最高的是（）。

A、靜態(tài)分區(qū)管理

B、動態(tài)分區(qū)管理

C、分頁管理

D、分段管理

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

知識點(diǎn)解析：本題考查實(shí)現(xiàn)各種多道程序的存儲管理的方法。為實(shí)現(xiàn)多道程序并

發(fā)，系統(tǒng)必須將多個程序調(diào)入內(nèi)存，讓多個進(jìn)程競爭CPU和外設(shè)，使得計(jì)算機(jī)能

高效地運(yùn)轉(zhuǎn)。多個程序調(diào)人內(nèi)存會存在越界，溢出等多種問題。為解決這些問題，

存儲管理采用了分區(qū)法、分頁法、分段法和段頁式等多種技術(shù)。靜態(tài)分區(qū)方法平均

對內(nèi)存的利用率是分區(qū)大小的50%,利用率較低。動態(tài)分區(qū)在經(jīng)過多次分配和回

收以后會出現(xiàn)大量的外碎片（外零頭），這些外碎片很難利用，需要經(jīng)過內(nèi)存緊縮來

合并，綜合起來能比靜杰分區(qū)的利用率稍高。分段技術(shù)與動態(tài)分區(qū)技術(shù)類似，內(nèi)存

利用率較動態(tài)分區(qū)低，因?yàn)槠溥M(jìn)程分段數(shù)量大于單個進(jìn)程的數(shù)量，外碎片會增加。

分頁技術(shù)的內(nèi)存利用率最高，每個進(jìn)程只在最后一頁有50%概率的浪費(fèi)，頁面大

小比分區(qū)大小要小得多，因此，被浪費(fèi)的內(nèi)存數(shù)量最少，從而內(nèi)存的利用率最高。

當(dāng)然，分頁需要額外增加頁表，分段需要增加段表，會增加系統(tǒng)開銷，但是對內(nèi)存

的利用率來講卻是最高的。

28、在一個請求頁式的虛擬存儲系統(tǒng)中，每個頁面的大小分為4096字節(jié)。如下某

個程序需要將數(shù)組賦值，假設(shè)，執(zhí)行代碼已經(jīng)駐留內(nèi)存，而數(shù)據(jù)頁面尚未分配，數(shù)

組按先行后列存放。請計(jì)算，其缺頁中斷次數(shù)是（），intaL1024J[1024J；inti,j；

i=0：fbr（j=0；j<1023；j++）a[i][j]=j；

A、2

B、1

C、1024

D、512

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

知識點(diǎn)解析：本題考查C語言程序在使用內(nèi)存時(shí)的分配機(jī)制。采用請求頁式虛擬

存儲管理的基本點(diǎn)是按需分配內(nèi)存，僅當(dāng)使用到該頁時(shí)才通過缺頁中斷分配內(nèi)存。

C語言對數(shù)組的存放是先行后列的，整型數(shù)組每個占用2個字節(jié)，據(jù)此，我們可以

計(jì)算，4096字節(jié)可以存放2行數(shù)組，由于程序中并非按行賦值，而是按列賦值，

所以一頁只賦值2個數(shù)組（是跳躍地賦值），若每申請一頁產(chǎn)生1次缺頁中斷，那么

總共要產(chǎn)生1024/2=512次缺頁中斷。

29、在頁式存儲管理系統(tǒng)中選擇頁面的大小，需要考慮的因素是（）。I頁面大的

好處是頁表較小n頁面小的好處是可以減少由內(nèi)碎片引起的內(nèi)存浪費(fèi)m通常，影

響磁盤訪問時(shí)間的主要因素不在于頁面的大小，所以使用時(shí)可優(yōu)先考慮較大的頁面

A、I和m

R、II和m

c、I和口

D、I和II和m

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

知識點(diǎn)解析：在確定地址結(jié)構(gòu)時(shí)，若選擇的頁面較小，一方面可使內(nèi)碎片減小，從

而減少了內(nèi)碎片的總空間、有利于提高內(nèi)存利用。但另一方面，也會使每個進(jìn)程要

求較多的頁面，從而導(dǎo)致頁表過長，占用大量內(nèi)存。此外，還會降低頁面換進(jìn)換出

的效率。若選擇的頁面較大，雖然可減少頁表長度，提高換進(jìn)換出效率，但卻又會

使內(nèi)碎片增大。因此。頁面的大小應(yīng)選得適中，通常頁面的大小是2的暴，即在

512B?4096B之間。頁面大小與磁盤調(diào)度的關(guān)系不大，磁盤調(diào)度與扇區(qū)有關(guān)。故

正確答案為C。

30、操作系統(tǒng)中，采用了多種技術(shù)改善磁盤輸入輸出的訪問速度，下列不能提高磁

盤訪問速度的是（）。

A、加快盤片轉(zhuǎn)速

B、運(yùn)用磁臂調(diào)度算法

C、采用通道技術(shù)

D、添加磁盤緩沖

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

知識點(diǎn)解析：本題考查對磁盤電氣結(jié)構(gòu)的理解。磁盤訪問時(shí)間是由磁盤片旋轉(zhuǎn)延

時(shí)、尋道延時(shí)、處理延時(shí)和數(shù)據(jù)內(nèi)部傳輸延時(shí)組成。加快盤片轉(zhuǎn)速可以減少旋轉(zhuǎn)延

時(shí)，運(yùn)用磁臂調(diào)度算法可以降低尋道時(shí)間，添加緩沖區(qū)可以降低內(nèi)部傳輸延時(shí)（例

如串并轉(zhuǎn)換，預(yù)讀寫等），而通道技術(shù)是與計(jì)算機(jī)接口總線和內(nèi)存速度有關(guān)，與磁

盤的性能無關(guān)。

31、有一個文件含有10000個文件塊，若將其順序結(jié)構(gòu)存放，則對文件塊順序查找

的平均時(shí)間為5000個。若按索引順序文件的結(jié)構(gòu)存放，每個索引為100個文件

塊，則順序查找次數(shù)是（）。

A、500

B、100

C、50

D、10

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

知識點(diǎn)解析：本題考查H勺是文件的邏輯結(jié)構(gòu)。順序文件在按順序查找文件內(nèi)容時(shí)，

必須按順序一個一個去讀取，最快在第一個就讀取到，最慢一直讀到最后一個文件

塊，所以平均為一半，計(jì)算結(jié)果是10000:2=5000。（若采用二分法不會有這么多

次）。當(dāng)采用索引順序文件時(shí)，文件的內(nèi)容已經(jīng)按照索引的關(guān)鍵詞排好了序（例如按

字母順序等）。并建立了索引表，索引表一般將一定數(shù)量的文件塊組織成一組，本

題中以100個一組，所以分成10000:100=100組，按順序查找法，查找這10。組

平均需要100:2=50次，找到以后在組內(nèi)繼續(xù)查找，平均需要100:2=50次，用以

共需要50+50=100次。

32、計(jì)算機(jī)系統(tǒng)中,不需要處理機(jī)干預(yù),能夠在內(nèi)存中（包括映射的內(nèi)存）快速搬運(yùn)

數(shù)據(jù)的控制器是（）。

A、通道控制器

B、DMA控制器

C、中斷控制器

D、時(shí)鐘控制器

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

知識點(diǎn)解析：本題考查10設(shè)備中各種控制器的特點(diǎn)。通道控制器主要用于外設(shè)與

內(nèi)存的數(shù)據(jù)搬運(yùn)，不需要處理機(jī)干預(yù)；DMA控制器用于內(nèi)存到內(nèi)存（包括將外設(shè)的

存儲器映射到內(nèi)存空間的部分，例如顯存空間）的快速數(shù)據(jù)搬運(yùn)，且不需要處理機(jī)

干預(yù)；中斷控制器用于接收中斷信號，對中斷信號進(jìn)行優(yōu)先級別排列并產(chǎn)生中斷碼

（中斷號）等工作，時(shí)鐘控制器管理計(jì)算機(jī)系統(tǒng)的所有時(shí)序和定時(shí)器，與數(shù)據(jù)搬運(yùn)無

關(guān)。

33、在協(xié)議數(shù)據(jù)單元中，控制信息所不包括的內(nèi)容是（）。

A、地劃

B、查錯碼

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

D、協(xié)議控制

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

知識點(diǎn)解析：本題考查協(xié)議的基本概念，為保證網(wǎng)絡(luò)中的計(jì)算機(jī)之間有條不紊的進(jìn)

行數(shù)據(jù)交換，合理的共享資源，各獨(dú)立的計(jì)算機(jī)系統(tǒng)必須嚴(yán)格的遵循事先約定好的

一套套的通信規(guī)程，包不嚴(yán)格規(guī)定要交換的數(shù)據(jù)形式。控制信息的格式和控制功

能，以及通信過程中事件執(zhí)行的次序等，這里地址、查錯碼和協(xié)議控制都是控制信

息必須包括的，但具體的數(shù)據(jù)是由上層協(xié)議所決定，因此答案是C。

34、通過改變載波信號的相位值來表示數(shù)字信號1、0的方法是（）。

A、ASK

B、FSK

C、PSK

D、PPP

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

知識點(diǎn)露析：本題考查數(shù)字調(diào)制的基本概念，使用某個頻率的正弦載波，使其的振

幅、頻率或相位隨著數(shù)字信號的變化而變化，稱為調(diào)制；相反的過程稱為解調(diào)；數(shù)

字調(diào)制具有三種基本形式即移幅鍵控法ASK、移頻鍵控法FSK和移相鍵控

法.PSKo在ASK方式下，用載波的兩種不同幅度來表示二進(jìn)制的兩種狀態(tài)。在

FSK方式下，用載波頻率附近的兩種不同頻率來表示二進(jìn)制的兩種狀態(tài)。在PSK

方式下，用載波信號相位移動來表示數(shù)據(jù)。因此答案為C。

35、假設(shè)一個NAT服務(wù)器其公網(wǎng)地址為205.56.79.35,并且有如表6-1的表

項(xiàng)，那么當(dāng)一個IP地址為192.168.32.56端口為21分組進(jìn)入公網(wǎng)的時(shí)候，轉(zhuǎn)

換后的端口號和源IP地址是（）。

?6-1

轉(zhuǎn)換端口原IP地址原端口

2056192.168.32.5621

2057192.168.32.5620

1892192.168.48.2680

2256192.168.55.10680

A、205.56.79.35：2056

B、192.168.32.56：2056

C、205.56.79.35：1892

D、205.56.79.35：2256

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

知識點(diǎn)解析：本題考查地址轉(zhuǎn)換技術(shù)NAT的工作原理，NAT協(xié)議利用端口域來解

決內(nèi)網(wǎng)到外網(wǎng)的地址映射問題。任何時(shí)候當(dāng)一個向外發(fā)送的分組進(jìn)入到NAT服務(wù)

器的時(shí)候，源地址被真實(shí)的公網(wǎng)地址所取代，而端口域被轉(zhuǎn)換為一個索引值⑵被

轉(zhuǎn)換成2056)。因此答案是A。

36、IPv6協(xié)議數(shù)據(jù)單元由一個固定頭部和若干個擴(kuò)展頭部以及上層協(xié)議提供的負(fù)

我組成，其中用于標(biāo)識松散源路由功能的擴(kuò)展頭是()。

A、目標(biāo)頭部

B、路由選擇頭部

C、分段頭部

D、安全封裝負(fù)荷頭部

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

知識點(diǎn)解析：本題考查IPv6地址的基本概念，IPv6首部的固定部分被簡稱為IPv6

首部，其大小是40字節(jié)，而IPv4首部中的必要部分為20字節(jié)。IPv6已經(jīng)定義了

以下擴(kuò)展首部：逐跳選項(xiàng)首部(H0p-by-HopOptionsheader)：定義需要逐跳處理的

特殊選項(xiàng)；路由首部(Routingheader)：提供擴(kuò)展路由，類似于IPv4的源路由；片

段首部(Fragmentheade門：包含分片和重組信息：認(rèn)證首部(Authentication

header)：提供數(shù)據(jù)完整性和認(rèn)證；封裝安全負(fù)載首部(EncapsulationSecurity

Payloadheader)：提供秘密性；目標(biāo)選項(xiàng)首部(DeslinationOplionsheader)：包含要

在目標(biāo)節(jié)點(diǎn)檢查的可選信息。因此答案是B。

37、現(xiàn)有一個長度為3000B的IP數(shù)據(jù)報(bào)，其IP頭部的長度為20B,該IP數(shù)據(jù)報(bào)

如在最大幀長度為1518B的以太網(wǎng)中進(jìn)行傳輸，那么為了正確傳輸，最后一個IP

數(shù)據(jù)分片的數(shù)據(jù)大小是()。

A、20B

B、30B

C、40B

D、50B

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

知識點(diǎn)解析：分片目的：當(dāng)?shù)絹淼臄?shù)據(jù)報(bào)長度超過其輸出線路所屬網(wǎng)絡(luò)的MTU

時(shí)，路由器將數(shù)據(jù)報(bào)分成許多較小的片段。每個片段被封裝成數(shù)據(jù)報(bào)，獨(dú)立傳輸。

封裝片段使用的報(bào)頭取自原始數(shù)據(jù)報(bào)的報(bào)頭。分片原理：路由器利用MTU和報(bào)頭

長度計(jì)算每一報(bào)片允許包含的最大數(shù)據(jù)字節(jié)數(shù)(必須是8字節(jié)的整倍數(shù))，并對原始

數(shù)據(jù)報(bào)的數(shù)據(jù)部分進(jìn)行分片。在每個報(bào)片前使用原始報(bào)頭的拷貝，修改原始頭部中

的某些字段，如總長度、標(biāo)志位、片偏移(以字節(jié)為單位的偏移量除以8)等，直新

計(jì)算頭校驗(yàn)，然后發(fā)送。當(dāng)一個片段到達(dá)一個具有更小MTU的網(wǎng)絡(luò)時(shí)，需要進(jìn)一

步分片，所有分片都在目的主機(jī)重組，中間路由器不做重組的工作。分片重組：將

到來的報(bào)片重新組裝一個完整數(shù)據(jù)報(bào)的過程稱為重組，重組是在目的主機(jī)中進(jìn)行

的。目的主機(jī)使用源地址和分組標(biāo)識來確定屬于同一個數(shù)據(jù)報(bào)的片段，根據(jù)MF標(biāo)

志判斷是否最后一個報(bào)片已經(jīng)到達(dá)。當(dāng)MF=0的報(bào)片到達(dá)時(shí)，根據(jù)該報(bào)片的片偏移

字段和總長度字段可以計(jì)算出原始數(shù)據(jù)報(bào)的總長度。當(dāng)所有報(bào)片都已到達(dá)時(shí)，按照

各報(bào)片在原始數(shù)據(jù)報(bào)中的偏移量進(jìn)行組裝。本題考查IP分片的原理和應(yīng)用，這里

以太網(wǎng)幀頭為18B,IP頭為20B,因此最大數(shù)據(jù)載荷是1480B,3020B的IP數(shù)據(jù)

的數(shù)據(jù)部分是3020-20=3000B,因此必須進(jìn)行分片，30001480+1480+40共3

片，最后一片的數(shù)據(jù)部分是40B,因此答案是C。

38、傳輸層用于標(biāo)識不同的應(yīng)用的是（）。

A、物理地址

B、端口號

C、IP地劃

D、邏輯地址

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

知識點(diǎn)解析：本題考查端口號的作用，端口號是傳輸層的服務(wù)訪問點(diǎn)，讓應(yīng)用層的

應(yīng)用進(jìn)程通過端口來交時(shí)數(shù)據(jù)給傳輸層，是標(biāo)志應(yīng)用層的進(jìn)程，因此答案是B。

39、如圖6-1所示一臺路由器連接3個以太網(wǎng)，假設(shè)主機(jī)C上要發(fā)送一個IP分

組，使得主機(jī)D和主機(jī)E都會接收它，而子網(wǎng)3和子網(wǎng)4上的主機(jī)都不會接收

它，那么該IP分組的目標(biāo)IP地址是（）。

A、255.255.255.255

B、130.130.20.255

C、127.0.0.1

D、130.130.19.255

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

知識點(diǎn)解析：本題考查路由器的功能和IPv4地址的特點(diǎn)，主機(jī)D屬于子網(wǎng)

130.130.19.0,主機(jī)E屬于130.130.20.0,分別屬于不同的網(wǎng)絡(luò)，可以同

時(shí)接收的IP分組必定是廣播報(bào)文，題目又要求該廣播報(bào)文不能轉(zhuǎn)發(fā)到子網(wǎng)3,和

子網(wǎng)4,則這個廣播報(bào)又必定是有限廣播地址255.255.255.255,路由器可以割

斷廣播報(bào)，因此答案是A。

40、DNS作為一種分布式系統(tǒng)，所基于的網(wǎng)絡(luò)應(yīng)用模式是（）。

A、C/S模式

B、B/S模式

C、P2P模式

D、以上均不正確

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

知識點(diǎn)解析：本題考查網(wǎng)絡(luò)應(yīng)用模型，DNS作為分布式應(yīng)用，是一種典型的C/S

模式。13/5模式又稱8/5結(jié)構(gòu)，是隨著Internet技術(shù)的興起，對C/S模式應(yīng)用

的擴(kuò)展。因此答案為A。

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

41、已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一

個結(jié)點(diǎn)的指針，是否可不用遞歸，且不用棧來完成?請簡述原因。

標(biāo)準(zhǔn)答案：可以。原因：后序遍歷的順序是“左子樹-右子樹-根結(jié)點(diǎn)因此，二叉

樹最左下的葉子結(jié)點(diǎn)是遍歷的第一個結(jié)點(diǎn)。下面的語句段說明了這一過程(設(shè)p是

二義樹根結(jié)點(diǎn)的指針)。if(p!=NULL){while(p->ichild!=NULLIIP->

rchild!=NULL){while(p->Ichild!=NULL)P：P->ichild；if(p->rchild!=NULL)P=P-

>rchild：)}return(p)；//返回后序序列第一個結(jié)點(diǎn)的指針

知識點(diǎn)解析：暫無解析

42、設(shè)有一個帶頭結(jié)點(diǎn)的循環(huán)單鏈表，其結(jié)點(diǎn)值均為正整數(shù)。試設(shè)計(jì)一個算法，反

復(fù)找出單鏈表中結(jié)點(diǎn)值最小的結(jié)點(diǎn)，并輸出之，然后將該結(jié)點(diǎn)從中刪除，直到單鏈

表空為止，最后再刪除表頭結(jié)點(diǎn)。(1)給出算法的基本設(shè)計(jì)思想；(2)根據(jù)設(shè)計(jì)思

想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋。

標(biāo)準(zhǔn)答案：用C語言算法描述如下：voiddelall(LinkList&L){LNode*p,*pre,

*minp,*minpre；while(L->next!=L){//循環(huán)單鏈表不空時(shí)循環(huán)p=L->next：

pre=L；minp=p；minpre=pre；while(p!=L){//從頭開始查找最小值的結(jié)點(diǎn)1￡8-

>data<minp->data){minp=p；minpre=pre；)pre=p；//p、pre同步后移p=p-

>next：|printf("%c",minp->data)；//輸由最小值結(jié)點(diǎn)minpre->next=minp-

>next；//刪除最小值結(jié)1free(minp)；)free(L)；)

知識點(diǎn)解析：暫無解析

43、圖2-2所示的CPU邏輯框圖中，有兩條獨(dú)立的總線和兩個獨(dú)立的存儲器。已

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

65536字(字長16位)。各寄存器均有“打入”(Rin)“送出”(Rout)控制命令，但圖中未

BUS,

標(biāo)出。圖2-2⑴指

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

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

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

1113120

??加法指令可寫為“ADDX(Ri)”，其功能是

(AC())+((Ri)+X)-ACi，其中((Ri)+X)部分通過尋址方式指向數(shù)據(jù)存儲器DM。現(xiàn)取

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

信號。

標(biāo)準(zhǔn)答案：(1)PC=14位，IR=18位ACO=AC1=16位,RO~R3=16位IAR=14位，

IDR=18位DAR=16位，DDR=16位⑵加法指令“ADDX(R。”是一條一地址指令，

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

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

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

PC-IAR

PC..IAR.

IMTDR或IM,IDRin

IDR-IRIDR^,.IR.

X-,+?AC.

AC._?DAR^

￡DM.DDRin

AJBUSJ,+,DDQ(BUSj).Cto

圖2-8

知識點(diǎn)解析：暫無解析

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

Do表2—1列出了執(zhí)行每級中斷服務(wù)程序所需的時(shí)間。

斷優(yōu)先級的尺度，時(shí)間越短優(yōu)先級越高。（1）指出如何為各級中斷服務(wù)程序設(shè)置屏

蔽碼；（2）如果A、B、C、D分別在6愀、8M、10四、0四時(shí)刻發(fā)出中斷請求，畫

出CPU執(zhí)行中斷服務(wù)程序的序列；（3）基于上題，請計(jì)算上述四個中斷服務(wù)程序的

平均執(zhí)行時(shí)間c

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

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

裊2-5

D-

現(xiàn)行程序"(J24681012141618202224262830323436

D請求A請求|C請求

B請求

圖2-9中斷處理的優(yōu)先級別

是C>A>D>B。0四時(shí)，D請求來到，由于沒有其他的中斷請求，所以開始執(zhí)行

中斷服務(wù)程序D。笫6卬時(shí)，A請求來到，A的優(yōu)先級高于D,轉(zhuǎn)去執(zhí)行中斷服務(wù)

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

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

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

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

程序A。第142時(shí)，中斷服務(wù)程序A執(zhí)行完畢（總共執(zhí)行時(shí)間5ps）,返回執(zhí)行中斷

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

程序。因?yàn)锽請求還存在，所以此時(shí)開始執(zhí)行中斷服務(wù)程序B,直至第35M時(shí)結(jié)

束（總共執(zhí)行時(shí)間15陛）。（3）由于在352時(shí)間內(nèi)，完成了4級中斷的處理，所以平

均執(zhí)行時(shí)間=35=4=8.75pso

知識點(diǎn)解析：暫無解析

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

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

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

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

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

學(xué)生進(jìn)程

國z-iotypcdefintsemaphore；semaphoremutcx=l：

semaphoresit=300；voidstudent(){P(sit)；P(mutex)；mark_sit()；V(mutex)；

readingO；P(mutex)：release_sit()；V(mutex)；V(sit)；leave()；)

知識點(diǎn)解析：暫無解析

46、一個32位的計(jì)算機(jī)系統(tǒng)中，虛擬存儲系統(tǒng)采用了物理地址擴(kuò)展的三級分頁方

式，第一級頁表占用地址的最高2位，第二、三級頁表依次占用9位地址，最低

12位用于頁內(nèi)偏移量，如圖2—3所示。

313029212012II

|0頁第|二級頁次1三級頁表]頁內(nèi)偏移?

網(wǎng)2-3

一個進(jìn)程的地址空間為4GB,每個頁表項(xiàng)占用8個字節(jié)，請問：(1)一個進(jìn)程最多

有多少個頁面？(2)一級、二級以及三級頁表各為多大?一共占用多少存儲空間？(3)

為提高效率，一級頁表和二級頁表全部裝入內(nèi)存，三級頁表只裝入一頁，若