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

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

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

1、若已知一個(gè)棧的入棧序列是1,2,3……n,其輸出序列為pl,p2,

p3....pn,若pl=n,則pi是（）。

A、i

B、n-i

C、n-i+1

D^不確定

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

知識(shí)點(diǎn)。析：本題中所敘述的情況，棧的輸出序列一定是輸入序列的逆序。

2、將一個(gè)A[1……100,I……100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組

R[l.-29用中，A中元素A66.65（即該元素下標(biāo)i=66,j=65）,在R數(shù)組中的位置k

為（）。

A、198

B、195

C、197

D、196

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

知識(shí)點(diǎn)解析：根據(jù)三對(duì)角對(duì)陣壓縮方法，將A[l..n][l..n]壓縮至B[0..3n

一3]時(shí)，aij與bk的對(duì)應(yīng)關(guān)系為:k=2i+j-3；將A[L.n][l..n]壓縮至

B[1..3n一2]時(shí)，叼與bk的對(duì)應(yīng)關(guān)系為：k-2i+j—2；根據(jù)題目，A中元素

A66,65，在B數(shù)組中的位置k為：k=2i+j--2=2x66+65—2=195

3、查找效率最高的二叉排序樹是（）。

A、所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹

B、所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹

C、平衡二叉樹

D、沒(méi)有左子樹的二叉排序樹

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

知識(shí)點(diǎn)解析：二叉排序樹的查找效率取決于二叉排序樹的深度，對(duì)于結(jié)點(diǎn)個(gè)數(shù)相同

的二叉排序樹，平衡二叉樹的深度最小。

4、一棵深度為k的平衡二叉樹，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為0,則該樹的

結(jié)點(diǎn)數(shù)是（）。

A、2k-1-l

B、2kl

C、2k-,+l

D、2卜一1

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

知識(shí)點(diǎn)解析：一棵深度為k的平衡二叉樹，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為0,

也就是說(shuō)每個(gè)非終端結(jié)點(diǎn)都有左子樹和右子樹且高度相等。因此，這樣的平衡二叉

樹即為滿二叉樹，而高度為k的滿二叉樹的結(jié)點(diǎn)數(shù)是2k—1。

5、以下敘述正確的是（LI.對(duì)有向圖G,如果以任一頂點(diǎn)出發(fā)講行一次深度優(yōu)先

或廣度優(yōu)先搜索能訪問(wèn)到每個(gè)頂點(diǎn)，則該圖一定是完全圖U.連通圖的廣度優(yōu)先

搜索中一般要采用隊(duì)列來(lái)暫存訪問(wèn)過(guò)的頂點(diǎn)m.圖的深度優(yōu)先搜索中一般要采用

棧來(lái)暫存訪問(wèn)過(guò)的頂點(diǎn)

A、I、n

B、口、m

c、I、m

D、I、n、m

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

知識(shí)點(diǎn)解析：i敘述是錯(cuò)誤的，因?yàn)槿绻邢驁D構(gòu)成雙向有向環(huán)時(shí)，則從任一頂點(diǎn)

出發(fā)均能訪問(wèn)到每個(gè)頂點(diǎn)，但該圖卻非完全圖?？?、ni敘述顯然是正確的。

6、一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡(jiǎn)單無(wú)向圖，在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中零元素的

個(gè)數(shù)是（）。

A、e

B、2e

C>n2—e

D、n2—2e-

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

知識(shí)點(diǎn)解析：由鄰接矩陣的定義可知，無(wú)向圖的鄰接矩陣是對(duì)稱的，即圖中的一條

邊對(duì)應(yīng)鄰接矩陣的兩個(gè)非零元素。因此一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡(jiǎn)單無(wú)向圖的

鄰接矩陣中共有產(chǎn)一2e個(gè)零元素。

7、從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上，所經(jīng)過(guò)的結(jié)點(diǎn)序列必按其關(guān)鍵字降序

排列的是（）。

A、二叉排序樹

B、大頂堆

C、小頂堆

D、平衡二叉樹

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

知識(shí)之解析：對(duì)于一個(gè)堆，若堆頂為最小元素，則稱為小頂堆；若堆頂為最大元

素，則稱為大頂堆。二叉排序樹和平衡二叉樹不符合。

8、順序存儲(chǔ)的某線性表共有123個(gè)元素，按分塊查找的要求等分為3塊。若對(duì)索

引表采用順序查找方法來(lái)確定子塊，且在確定的子塊中也采用順序查找方法，則在

等概率的情況下，分塊查找成功的平均查找長(zhǎng)度為()。

A、21

B、23

C、41

D、62

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

知識(shí)點(diǎn)解析：分塊查找成功的平均查找長(zhǎng)度為ASL=(s2+s+n)/2s。在本題中，

n=123,s=123/3=41,故平均查找長(zhǎng)度為23。

9、在下列存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射

關(guān)系的是()。

A、樹形存儲(chǔ)結(jié)構(gòu)

B、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C、索引存儲(chǔ)結(jié)構(gòu)

D、散列存儲(chǔ)結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：散列存儲(chǔ)結(jié)構(gòu)將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表中。

10、若對(duì)27個(gè)元素只進(jìn)行三趟多路歸并排序，則選取的歸并路數(shù)是()。

A、2

B、3

C、4

D、5

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

知識(shí)點(diǎn)解析：歸并就是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。設(shè)三趟

歸并中每次歸并x個(gè)有序表，則有27/X3=1,X=3C所以選取的歸并路數(shù)為3。

11、下列序列中，執(zhí)行第一趟快速排序的結(jié)果是()，

A、[da,ax,eb,de,bb]ff[ha,gc]

B、[cd,eb,ax,da]ff[ha,gc,bb]

C、[gc?ax,eb,cd,bb]ff[da?ha]

D、[ax,bb,cd,da]ff[eb,gc,ha]

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

知識(shí)點(diǎn)解析：本題要按字典順序進(jìn)行排序，前半?yún)^(qū)間中的所有元素都應(yīng)小于ff,后

半?yún)^(qū)間中的所有元素都應(yīng)大于ffo

12、某工作站采用時(shí)鐘頻率f為15MHz,處理速率為10MIPS的處理機(jī)來(lái)執(zhí)行一個(gè)

已知混合程序。假定每次存儲(chǔ)器存取為1周期延遲，試問(wèn)此計(jì)算機(jī)的有效CPI是

()。

A、2.5

B、2

C、1.5

D、1

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

知識(shí)點(diǎn)解析：CPI=15MHZ/(10X106)=1.5O

13、5位二進(jìn)制定點(diǎn)小數(shù)，用補(bǔ)碼表示時(shí)，最小負(fù)數(shù)是()。

A>0.II11

B、1.0001

C、1.1111

D、1

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

知識(shí)點(diǎn)解析：5位二進(jìn)制定點(diǎn)小數(shù)，用補(bǔ)碼表示時(shí)，最小負(fù)數(shù)表示為I.0000。

14、浮點(diǎn)加減中的對(duì)階是()。

A、將較小的一個(gè)階碼調(diào)整到與較大的一個(gè)階碼相同

B、將較大的一個(gè)階碼調(diào)整到與較小的一個(gè)階碼相同

C、將被加數(shù)的階碼調(diào)整到與加數(shù)的階碼相同

D、將加數(shù)的階碼調(diào)整到與被加數(shù)的階碼相同

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

知識(shí)點(diǎn)解析：對(duì)階的原則是小階向大階看齊。

15、若內(nèi)存按字節(jié)編址，用存儲(chǔ)容量為32Kx8比特的存儲(chǔ)器芯片構(gòu)成地址編號(hào)

A0000H至DFFFFH的內(nèi)存空間，則至少需要的片數(shù)是()。

A、4

B、6

C、8

D、10

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

知識(shí)點(diǎn)解析：DFFFF—A0000+1=40000,即256KB,需用32Kx8的芯片數(shù)

=(256Kx8)/(32Kx8)=8o

16、某計(jì)算機(jī)的存儲(chǔ)系統(tǒng)由Cache一主存系統(tǒng)構(gòu)成，Cache的存取周期為10ns,主

存的存取周期為50ns。在CPU執(zhí)行一段程序時(shí)，Cache完成存取的次數(shù)為4800

次，主存完成的存取次數(shù)為200次，該Cache一主存系統(tǒng)的效率是()。

A、0.856

B、0.862

C、0.958

D、0.96

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

知識(shí)點(diǎn)解析：命中率=4800/(4800+200)=0.96,平均訪問(wèn)時(shí)間=0.96x10+(1—

0.96)x50=11.6ns,效率=10/II.6=0.862。

17、對(duì)于RISC機(jī)和CISC機(jī)，以下說(shuō)法錯(cuò)誤的是（）。

A、RISC機(jī)的指令條數(shù)比CISC機(jī)少

B、RISC機(jī)指令的平均字長(zhǎng)比CISC機(jī)指令的平均字長(zhǎng)短

C、對(duì)大多數(shù)計(jì)算任務(wù)來(lái)說(shuō)，RISC機(jī)程序所用的指令條數(shù)比CISC機(jī)少

D、RISC機(jī)和CISC機(jī)都在發(fā)展

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

知識(shí)點(diǎn)解析：對(duì)于大多數(shù)計(jì)算任務(wù)來(lái)說(shuō)，RISC機(jī)編寫的程序會(huì)比CISC機(jī)編寫的

程序更長(zhǎng)，這是因?yàn)镽ISC的指令都比較簡(jiǎn)單，CSIC中的一條復(fù)雜指令所完成的

功能在RISC中可能要用幾條指令才能實(shí)現(xiàn)，對(duì)于同一個(gè)源程序，顯然RISC的指

令條數(shù)要比CISC的多。

18、微程序在計(jì)算機(jī)中存放的位置是（）。

A、主存儲(chǔ)器

B、控制存儲(chǔ)器

C、通用寄存器

D、指令寄存器

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

知識(shí)點(diǎn)解析：微程序存放在只讀的控制存儲(chǔ)器中。

19、下列各敘述中正確的命題是（）。I.在取指周期中也可能從內(nèi)存取到操作數(shù)

n.CPU的訪存時(shí)間是由存儲(chǔ)器的容量決定的，存儲(chǔ)容量越大，訪存時(shí)間就越長(zhǎng)

m.在主存與Cache之間的直接映射方式下，不采用替換策略也可以實(shí)現(xiàn)正確的塊

替換IV.動(dòng)態(tài)存儲(chǔ)器的讀操作也具有刷新的功能

A、I、n、in

B、I、n、w

c、u、m、w

D、I、山、IV

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

知識(shí)點(diǎn)解析：立即尋址方式就可以在取指周期從內(nèi)存取到操作數(shù)；在直接映射方式

下，一旦發(fā)生塊沖突是不需要替換策略的；動(dòng)態(tài)存儲(chǔ)器的刷新是與讀寫操作沒(méi)有關(guān)

系的。

20、在菊花鏈方式中，靠近控制器的設(shè)備與遠(yuǎn)處設(shè)備的（）。

A、優(yōu)先級(jí)高

B、優(yōu)先級(jí)相等

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

D、不一定

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

知識(shí)點(diǎn)解析：常見的集中仲裁方式有鏈?zhǔn)讲樵儯ň栈ㄦ湥?、?jì)數(shù)器定時(shí)查詢和獨(dú)立請(qǐng)

求等3種。鏈?zhǔn)讲樵兎绞降膬?yōu)先次序是由串接部件的先后位置來(lái)確定的，在查詢鏈

中離總線控制器最近的設(shè)備具有最高優(yōu)先權(quán)。計(jì)數(shù)器定時(shí)查詢和獨(dú)立請(qǐng)求方式的優(yōu)

先級(jí)可以是固定的也可以是不固定的。鏈?zhǔn)讲樵兎绞叫枰?條控制線、計(jì)數(shù)器定

時(shí)查詢方式需要［*］條控制線，而獨(dú)立請(qǐng)求方式需要2n+l條控制線。

21、RAID利用冗余技術(shù)實(shí)現(xiàn)高可靠性，其中RAID1的磁盤利用率是()。

A、25%

B、50%

C、75%

D、100%

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

知識(shí)點(diǎn)解析：RA1D1稱為鏡象磁盤陣列，數(shù)據(jù)盤和檢測(cè)盤的數(shù)量是1:1的關(guān)系，所

以磁盤利用率為50%。

22、設(shè)存儲(chǔ)器容量為32字，字長(zhǎng)64位，模塊數(shù)m=4,存儲(chǔ)周期T=200ns,數(shù)據(jù)總

線寬度為64位，總線傳送周期i=50ns。用交叉方式進(jìn)行組織，交叉存儲(chǔ)器的帶寬

是()。

A、32x1(/位/秒

B、8xl()7位/秒

C、73xl()7位/秒

D、18xl()7位/秒

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

知識(shí)點(diǎn)解析：順序存儲(chǔ)存儲(chǔ)器連續(xù)讀出4個(gè)字需要4個(gè)存儲(chǔ)周期，而交叉存儲(chǔ)存儲(chǔ)

器連續(xù)讀出4個(gè)字，由于采用分時(shí)啟動(dòng)的方法，只需要一個(gè)存儲(chǔ)周期加上三個(gè)總線

傳輸周期的時(shí)間?，F(xiàn)字長(zhǎng)為64位，交叉存儲(chǔ)器連續(xù)讀出4個(gè)字的信息總量q=64位

x4=256位，交叉存儲(chǔ)器連續(xù)讀出4個(gè)字所需的時(shí)間t=T+(4—

l)T=200ns+3x50ns=350ns=3.5xl0-7s,所以交叉存儲(chǔ)器的帶寬W=q/

t=256-(3.5xl0-7)=73xl()7(位/秒)。

23、操作系統(tǒng)為用戶提供了多種接口，它們是()。I.計(jì)算機(jī)高級(jí)指令；11.終端

命令：m.圖標(biāo)菜單；IV.匯編語(yǔ)言；V.C語(yǔ)言；VI.系統(tǒng)調(diào)用；

A、I；n；v

B、n；皿；vi

c、m；iv：v

D、口；w；w

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

知識(shí)點(diǎn)解析：本題考查操作系統(tǒng)的接口，操作系統(tǒng)有二種接口，命令輸入和系統(tǒng)調(diào)

用，而命令輸入又可以分為命令行和圖形用戶界面。命令行是在終端或命令輸入窗

口中輸入操作和控制計(jì)算機(jī)的規(guī)定的命令，既可以一條一條輸入，也可以組織成一

批命令，逐條自動(dòng)執(zhí)行，稱為批處理命令。圖形用戶接口是我們熟知的圖標(biāo)和菜單

形式。系統(tǒng)調(diào)用是我們編寫程序過(guò)程中，需要計(jì)算機(jī)所做的操作，一般要按固定格

式來(lái)調(diào)用。

24、若一個(gè)信號(hào)量的初值為3,經(jīng)過(guò)多次PV操作以后當(dāng)前值為一1,此表示等待

進(jìn)入臨界區(qū)的進(jìn)程數(shù)是()。

A、1

B、2

C、3

D、4

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

知識(shí)點(diǎn)3析：本題考查信號(hào)量的意義。信號(hào)量是一個(gè)整型的特殊變量，只有初始化

和PV操作才能改變其值。通常，信號(hào)量分為互斥量和資源量，互斥量的初值一般

為1,表示臨界區(qū)只運(yùn)許一個(gè)進(jìn)程進(jìn)入，從而實(shí)現(xiàn)互斥?；コ饬靠梢詾?,表示臨

界區(qū)己經(jīng)有1個(gè)進(jìn)程進(jìn)入，臨界區(qū)外尚無(wú)進(jìn)程等待；當(dāng)互斥量小于0時(shí)，表示臨界

區(qū)中有1個(gè)進(jìn)程，互斥量的絕對(duì)值表示在臨界區(qū)外等待進(jìn)入的進(jìn)程數(shù)。同樣的道

理，資源信號(hào)量初值可以是任意整數(shù)，表示可用的資源數(shù)，當(dāng)資源量為0時(shí)，表示

所有資源已經(jīng)用光，但是也沒(méi)有其它進(jìn)程等待使用該資源。當(dāng)資源量小于0時(shí)，表

示當(dāng)前貨源已經(jīng)全部用完，而目.還有進(jìn)程正在等待使用該資源，等待的進(jìn)程數(shù)就是

資源量的絕對(duì)值。

25、利用銀行家算法進(jìn)行安全序列檢查時(shí)，不需要的參數(shù)是()。

A、系統(tǒng)資源總數(shù)

B、滿足系統(tǒng)安全的最少資源數(shù)

C、用戶最大需求數(shù)

D、用戶已占有的資源數(shù)

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

知識(shí)點(diǎn)露析：安全性檢查一般要用到進(jìn)程所需的最大資源數(shù)，減去進(jìn)程占用的資源

數(shù)，得到進(jìn)程為滿足進(jìn)程運(yùn)行尚需要的可能最大資源數(shù)，而系統(tǒng)擁有的最大資源數(shù)

減去已經(jīng)分配掉的資源數(shù)得到剩余的資源數(shù)，比較剩余的資源數(shù)是否滿足進(jìn)程運(yùn)行

尚需要的可能最大資源數(shù)可以得到當(dāng)前狀態(tài)是否安全的結(jié)論。而滿足系統(tǒng)安全的最

少資源數(shù)并沒(méi)有這么一個(gè)說(shuō)法。

26、若有一進(jìn)程擁有100個(gè)線程，這些線程都屬于用戶級(jí)線程，則在系統(tǒng)調(diào)度執(zhí)行

時(shí)間上占用的時(shí)間片是()。

A、1

B、100

C、1/100

D、0

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

知識(shí)點(diǎn)解析：本題主要考查關(guān)于進(jìn)程和線程之間資源共享的知識(shí)點(diǎn)。在引入線程的

操作系統(tǒng)中，線程是進(jìn)程中的一個(gè)實(shí)體，是系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。但是

線程自己基本上不擁有系統(tǒng)資源，所以它不是資源分配的基本單位，它只擁有一部

分在運(yùn)行中必不可少的與處理機(jī)相關(guān)的資源，如線程狀態(tài)、寄存器上下文和棧等，

它同樣有就緒、阻塞和執(zhí)行三種基本狀態(tài)。它可與同屬一個(gè)進(jìn)程的其他線程共享進(jìn)

程所擁有的全部資源。一個(gè)線程可以創(chuàng)建和撤銷另一個(gè)線程；同一個(gè)進(jìn)程中的多個(gè)

線程之間可以并發(fā)執(zhí)行。由于用戶線程不依賴于操作系統(tǒng)內(nèi)核，因此，操作系統(tǒng)內(nèi)

核是不知道用戶線程的存在的，用戶線程是由用戶來(lái)管理和調(diào)度的，用戶利用線程

庫(kù)提供的API來(lái)創(chuàng)建、司步、調(diào)度和管理線程。所以，用戶線程的調(diào)度在用戶程

序內(nèi)部進(jìn)行，通常采用非搶先式和更簡(jiǎn)單的規(guī)則，也無(wú)須用戶態(tài)和核心態(tài)切換，所

以速度很快。由于操作系統(tǒng)不知道用戶線程的存在，所以，操作系統(tǒng)把CPU的時(shí)

間片分配給用戶進(jìn)程，再由用戶進(jìn)程的管理器將時(shí)間分配給用戶線程。那么，用戶

進(jìn)程能得到的時(shí)間片即為所有用戶線程共享。因此，正確答案應(yīng)為A。

27、某計(jì)算機(jī)采用頁(yè)式存儲(chǔ)管理，內(nèi)存中現(xiàn)有1000個(gè)頁(yè)表項(xiàng)，CPU的cache中可

以存放N個(gè)頁(yè)表項(xiàng)，該系統(tǒng)中，CPU內(nèi)存訪問(wèn)的時(shí)間為KJOns,對(duì)cache訪問(wèn)的時(shí)

間是5ns,如果希望頁(yè)表映射的平均時(shí)間降到20ns以下，那么cache中的N必須高

于()。

A、850

B、858

C、923

D、842

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

知識(shí)點(diǎn)露析：本題考查cache與頁(yè)式存儲(chǔ)管理結(jié)合下的時(shí)間計(jì)算。根據(jù)題意，頁(yè)式

尋址方式的過(guò)程是這樣的：當(dāng)執(zhí)行到一個(gè)邏輯地址時(shí)，MMU首先將頁(yè)號(hào)分離，將

得到的頁(yè)號(hào)與cache中的多個(gè)頁(yè)表項(xiàng)比較(同時(shí)進(jìn)行)，若頁(yè)表項(xiàng)命中，則取出頁(yè)表

項(xiàng)與頁(yè)內(nèi)地址相加，形成指令或數(shù)據(jù)的物理地址，花費(fèi)5ns,據(jù)此地址，然后到內(nèi)

存中取得對(duì)應(yīng)的指令或數(shù)據(jù)，送到CPU中執(zhí)行或計(jì)算。若不能在cache命中，那

么CPU會(huì)啟動(dòng)cache更新程序，將新的頁(yè)表項(xiàng)從內(nèi)存復(fù)制到cache,花費(fèi)100ns,

然后，重復(fù)上述地址轉(zhuǎn)段過(guò)程，又花去5ns,得到物理地址，再去內(nèi)存取指令或數(shù)

據(jù)。根據(jù)題意，要求得到頁(yè)框號(hào)，也就是物理地址的過(guò)程小于20ns,那么設(shè)，

cache的命中率為x,列關(guān)系式：5*x+(l—x)*(5+100)=20解得x為85%。因此，

裝入cache的頁(yè)表項(xiàng)應(yīng)大于1000*85%=850項(xiàng)，這樣可以保證獲得頁(yè)框號(hào)的時(shí)間小

于20ns。本題若問(wèn)，一個(gè)指令雙字的執(zhí)行時(shí)間是多少時(shí)，需要考慮的事情就比較

復(fù)雜。例如系統(tǒng)的字長(zhǎng)是否是32位，32位的系統(tǒng)執(zhí)行一個(gè)雙字的時(shí)間是1次尋

址，16位系統(tǒng)就需要2次尋址。8位系統(tǒng)的就需要4次尋址。另外，采用什么內(nèi)存

管理機(jī)制，頁(yè)式和段式都是執(zhí)行1次指令尋址需要訪問(wèn)內(nèi)存2次，段頁(yè)式需要3

次。還要看cache的容量多大，指令是否在cache中等，所以，內(nèi)存管理中尋址時(shí)

間的計(jì)算與CPU結(jié)構(gòu)和cache的運(yùn)行模式息息相關(guān)，考生應(yīng)結(jié)合計(jì)算機(jī)組成原

理，妥善解決此類問(wèn)題。

28、分頁(yè)系統(tǒng)中的頁(yè)面是()。

A、用戶所能感知的

B、操作系統(tǒng)所能感知的

C、編譯程序所能感知的

D、鏈接裝配程序所能感知的

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

知識(shí)點(diǎn)解析：分頁(yè)系統(tǒng)中由邏輯地址向物理地址的轉(zhuǎn)換是系統(tǒng)借助硬件系統(tǒng)自動(dòng)實(shí)

現(xiàn)的，對(duì)用戶透明，對(duì)編譯程序和鏈接裝配程序透明(在相同的系統(tǒng)里)。只有操作

系統(tǒng)可以感知頁(yè)面的存在，在內(nèi)存管理過(guò)程中，操作系統(tǒng)要為用戶進(jìn)程分配內(nèi)存，

回收內(nèi)存。所以操作系統(tǒng)是頁(yè)面最直接的接觸者，它將頁(yè)面從計(jì)算機(jī)系統(tǒng)中到用戶

進(jìn)行了隔離。

29、某操作系統(tǒng)的文件管理采用直接索引和多級(jí)索引混合方式，文件索引表共有

10項(xiàng)，其中前8項(xiàng)是直接索引項(xiàng)，第9項(xiàng)是一次間接索引項(xiàng)，第10項(xiàng)是二次間接

索引項(xiàng)，假定物理塊的大小是1K,每個(gè)索引項(xiàng)占用4個(gè)字節(jié)，則該文件系統(tǒng)日最

大的文件可以達(dá)到()。

A、65800K

B、65792K

C、65536K

D、34000K

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

知識(shí)點(diǎn)解析：多級(jí)索引的邏輯并不復(fù)雜，本題中一級(jí)間接索引表有256張，二級(jí)間

接索引表最多有256張，計(jì)算時(shí)加以仔細(xì)小心，一般不會(huì)有太多變化，但是對(duì)多級(jí)

索引的方法一定要掌握。直接索引為8xlK=8K,一級(jí)間接索引為(1K/4B)X1

K=256K；二級(jí)間接索引為(1K/4B)x(lK/4B)x1K=65536K。共計(jì)

65536K+25K+8K=65800K

30、設(shè)磁盤的IO請(qǐng)求隊(duì)列中所要訪問(wèn)的磁道號(hào)為:96,184,25,120,12,

126,73,75,當(dāng)前磁頭在96,前一次在90。當(dāng)采用最短尋道時(shí)間優(yōu)先算法(SSTF)

和電梯算法所要移動(dòng)的距離是()。

A、618,418

B、306,260

C、306,418

D、618,260

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

知識(shí)點(diǎn)解析：本題考查考生對(duì)最短尋道時(shí)間優(yōu)先算法和電梯算法的理解。最短尋道

時(shí)間優(yōu)先算法(SSTF)：96—75—73—120—126—184—25—12共計(jì)306道。電梯算

法，前一次在90,當(dāng)前在96,表示移動(dòng)方向?yàn)榇诺涝龃蠓较颍剩?/p>

96-120—126T184—75—73-25T12共計(jì)260道。計(jì)算時(shí)注意磁頭的當(dāng)前位置和

運(yùn)行方向。

31、UNIX操作系統(tǒng)中，文件的索引結(jié)構(gòu)存放在()。

A、超級(jí)塊

B、索引節(jié)點(diǎn)

C、目錄項(xiàng)

D、空閑塊

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

知識(shí)點(diǎn)解析：在UNIX的文件系統(tǒng)中文件系統(tǒng)是其核心，其功能強(qiáng)大，可擴(kuò)展性

強(qiáng)。UNIX采用的是樹形目錄結(jié)構(gòu)，文件的信息存放在索引節(jié)點(diǎn)中，索引節(jié)點(diǎn)是一

個(gè)64字節(jié)長(zhǎng)的表，含有一個(gè)文件的重要信息，包括文件大小，文件所有者，文件

存取許可方式，文件類型(普通文件、目錄文件、特殊文件)等信息，但是不包含文

件名，文件名存放在目錄中。除了上述信息以外，索引節(jié)點(diǎn)在表格的最后設(shè)計(jì)有

13項(xiàng)文件在外存存放的混合索引表，前10項(xiàng)存放的是直接指針，指向文件存放的

數(shù)據(jù)塊的直接地址，UNIX系統(tǒng)中文件塊的大小一般是1024字節(jié)。所以文件的大

小不能超過(guò)10*1024=10240字節(jié)，超過(guò)上述大小的文件將在第11項(xiàng)一級(jí)間接索引

表中指出，該表項(xiàng)指針指向的一個(gè)數(shù)據(jù)塊中，存放了256個(gè)索引指針(假設(shè)一個(gè)指

針為4字節(jié)，1024字節(jié)的一個(gè)存儲(chǔ)塊可以存放1024/4=256個(gè)指針)，可以最多容

納256*1024=262144字節(jié)。再大的文件在第12項(xiàng)的二級(jí)間接索引表中指明,二級(jí)

索引指針指向的數(shù)據(jù)塊中可以容納256個(gè)指針，這些指針指向的數(shù)據(jù)塊中還是索引

指針，故稱為二級(jí)間接索引，它可以容納的文件大小是256*256*1024=67108864

字節(jié)。第13項(xiàng)是三級(jí)間接索引，可以容納的文件大小更大，為

256*256*256*1024節(jié)。所以文件總的大小是上述各級(jí)索引文仁溶

量的總和。即文件最大可以達(dá)節(jié)的大小。當(dāng)然，UNIX文件系統(tǒng)

對(duì)文件的大小是有限制的，不會(huì)讓其用完整個(gè)三級(jí)索引。文件的物理結(jié)構(gòu)中，主

要使用的是順序結(jié)構(gòu)、鏈接結(jié)構(gòu)和索引結(jié)構(gòu)(Hash結(jié)構(gòu)實(shí)際上與索引結(jié)構(gòu)類似)。在

索引結(jié)構(gòu)的文件中，必須要用專門的存儲(chǔ)空問(wèn)來(lái)存放索引指針，表示文件的內(nèi)容存

放的地址。所以，當(dāng)訪問(wèn)該文件時(shí)，必須首先去讀取該文件的索引表，才能知道相

應(yīng)的邏輯文件塊在外存上的存放地址。邏輯文件塊與物理文件塊是一一對(duì)應(yīng)關(guān)系，

不能在一個(gè)記錄中存放多個(gè)地址，而索引表中只存放地址指針，不存放文件內(nèi)容由

于有額外的索引表，所以它并不節(jié)省存儲(chǔ)空間。

32、在設(shè)備管理中，用來(lái)實(shí)現(xiàn)設(shè)備分配的四個(gè)數(shù)據(jù)結(jié)構(gòu)中，每個(gè)設(shè)備一張，描述設(shè)

備的特性和狀態(tài)，反映設(shè)備的特性、設(shè)備和控制器的連接情況的數(shù)據(jù)結(jié)構(gòu)是()。

A、設(shè)備控制表(DCT)

B、系統(tǒng)設(shè)備表(SDT)

C、控制器控制表(COCT)

D、通道控制表(CHCT)

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

知識(shí)點(diǎn)解析：設(shè)備控制的數(shù)據(jù)結(jié)構(gòu)中，系統(tǒng)設(shè)備表(SDT)在整個(gè)操作系統(tǒng)中只有一

張，記錄了系統(tǒng)中所有的外部設(shè)備。經(jīng)系統(tǒng)設(shè)備表找到需使用的外部設(shè)備，則數(shù)據(jù)

結(jié)構(gòu)指針指向設(shè)備控制表(DCT),這個(gè)數(shù)據(jù)表每個(gè)設(shè)備一張，記錄了設(shè)備的特性和

狀態(tài)。每個(gè)設(shè)備有可能有不止一個(gè)控制器，所以從設(shè)備控制表會(huì)指向多張(至少一

張)控制器控制表(COCT),里面存放了控制器的控制參數(shù)，如果該設(shè)備是通道的

話，則會(huì)指向多張通道控制表(CHCT)。

33、在OSI參考模型中，第N層和其上的第N+1層的關(guān)系是()。

A、第N層為第N+1層提供服務(wù)

B、第N+1層將從第N層接收的信息增加了一個(gè)頭

C、第N層利用第N+1層提供的服務(wù)

D、第N層對(duì)N+l層沒(méi)有任何作用

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

知識(shí)點(diǎn)解析：本題考查OSI模型的層次關(guān)系，在協(xié)嘆的控制下，兩個(gè)對(duì)等實(shí)體問(wèn)的

通信使得本層能夠向上一層提供服務(wù)，同時(shí)要實(shí)現(xiàn)本層協(xié)議，還需要使用下層所提

供的服務(wù)。本層的服務(wù)用戶只能看見服務(wù)而無(wú)法看見下面的協(xié)議。下層的協(xié)議對(duì)上

層的服務(wù)用戶是透明的。也就是下一層要為上一層提供服務(wù)，并為上一層數(shù)據(jù)進(jìn)行

封裝，因此答案為A,這里選項(xiàng)B和C的說(shuō)法正好相反，應(yīng)該是第N層將從第

N+1層接收的信息增加了一個(gè)頭，第N+1層利用第N層提供的服務(wù)。

34、設(shè)待傳送數(shù)據(jù)總長(zhǎng)度為L(zhǎng)位，分組長(zhǎng)度為P位，其中頭部開銷長(zhǎng)度為H位，

源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間.的鏈路數(shù)為h,每個(gè)鏈路上的延遲時(shí)間為D秒，數(shù)據(jù)傳輸

率為Bbps,電路交換建立連接的時(shí)間為S秒，則傳送所有數(shù)據(jù)，電路交換需時(shí)間

是（）。

A、hD+L/B秒

B、S+hD+L/P秒

C、S+hD+L/B秒

D、S+L/B秒

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

知識(shí)點(diǎn)解析：本題考查電路交換的原理，電路交換包括三個(gè)階段：建立電路。在傳

送數(shù)據(jù)之前，由發(fā)送方發(fā)出建立電路請(qǐng)求，交換機(jī)根據(jù)該請(qǐng)求，設(shè)法選擇一條空閑

的信道連接到接收方。諼收方收到該呼叫后，返回一應(yīng)答信號(hào)確認(rèn)本次電路連成，

則本次連接成功。傳送數(shù)據(jù)。建立電路連接后，發(fā)送方通過(guò)已建立的電路向接收方

發(fā)送數(shù)據(jù)。拆除電路。數(shù)據(jù)傳輸完畢，發(fā)送方或接收方任一方發(fā)出拆線信號(hào)，終止

電路連接，釋放所占用的信道資源。因此傳送所有數(shù)據(jù)所需的時(shí)間是連接建立時(shí)

間，鏈路延遲，發(fā)送時(shí)間的和，因此是S+hD+L/B,答案是C。

35、若數(shù)據(jù)鏈路的發(fā)送窗口尺寸WT=4,在發(fā)送3號(hào)幀、并接到2號(hào)幀的確認(rèn)幀

后,發(fā)送方還可連續(xù)發(fā)送的幀數(shù)是（）“

A、2幀

B、3幀

C、4幀

D、1幀

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

知識(shí)點(diǎn)解析：本題考查滑動(dòng)窗口的機(jī)制，發(fā)送方可連續(xù)發(fā)送K幀而無(wú)需對(duì)方應(yīng)

答，但需要將已發(fā)出但尚未收到確認(rèn)的幀保存在發(fā)送窗口中，以備由于出錯(cuò)或丟失

而準(zhǔn)備重發(fā)。接收方按正確的次序接受和遞交數(shù)據(jù)幀，并返回確認(rèn)信息。接收方可

能因?yàn)橐粠鲥e(cuò)，不能正確接受并遞交主機(jī)，對(duì)后面連續(xù)發(fā)送來(lái)的n幀均丟失，這

就是累積確認(rèn)的概念。本題收到了2號(hào)幀的確認(rèn)后，即0,1,2號(hào)幀已經(jīng)正確接

收，因此窗口向右移動(dòng)3個(gè)幀，目前已經(jīng)發(fā)送了3號(hào)幀，因此可連續(xù)發(fā)送的幀數(shù)是

窗口大小一已經(jīng)發(fā)送的項(xiàng)數(shù)，即4—1=3,答案是B。

36、TCP/IP網(wǎng)絡(luò)中，某主機(jī)的IP地址為130.25.3.135,子網(wǎng)掩碼為

255.255.255.192,那么該主機(jī)所在的子網(wǎng)的網(wǎng)絡(luò)地址是（）。

A、130.25.0.0

B、130.25.3.0

C、130.25.3.128

D、130.25.3.255

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

知識(shí)點(diǎn)解析：本題考查子網(wǎng)劃分的計(jì)算，從掩碼可以看出網(wǎng)絡(luò)地址僅和第四個(gè)字節(jié)

有關(guān)，因此130.25.3.135的二進(jìn)制為130.25.3.10000111,子網(wǎng)掩碼的二

進(jìn)制為255.255.255.11000000,兩者相與，因此網(wǎng)絡(luò)地址為

130.25.3.10000000,換算為十進(jìn)制是130.25.3.128,因此答案為C。

37、為了限制路由信息傳播的范圍，OSPF、協(xié)議把網(wǎng)絡(luò)劃分成4種區(qū)域（Area）,其

中連接各個(gè)區(qū)域的傳輸網(wǎng)絡(luò)是（）。

A、不完全存根區(qū)域

B、標(biāo)準(zhǔn)區(qū)域

C、主干區(qū)域

D、存根區(qū)域

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

知識(shí)點(diǎn)解析：本題考查層次路由與OSPF路由協(xié)議，如果將區(qū)域看成一個(gè)節(jié)點(diǎn)，則

OSPF是以主干區(qū)域（area。）為頂點(diǎn)，其他區(qū)域?yàn)榻K端的星形拓?fù)浣Y(jié)構(gòu)。標(biāo)準(zhǔn)區(qū)域可

以接收鏈路更新信息和路由總結(jié)。存根區(qū)域是不接受自治系統(tǒng)以外的路由信息的區(qū)

域。如果需要自治系統(tǒng)以外的路由，它使用默認(rèn)路由0.0.0.0。完全存根區(qū)域

不接受外部自治系統(tǒng)的路由以及自治系統(tǒng)內(nèi)其他區(qū)域的路由總結(jié)，需要發(fā)送到區(qū)域

外的報(bào)文則使用默認(rèn)路由0.0.0.0o不完全存根區(qū)域類似于存根區(qū)域，但是允

許接收以LSAType7發(fā)送的外部路由信息，并且要把LSAType7轉(zhuǎn)換成

LSAType5o因此答案是C。

38、一臺(tái)主機(jī)的IP地址為11.I.1.100,子網(wǎng)掩碼為255.0.0.0?，F(xiàn)在用戶

需要配置該主機(jī)的默認(rèn)路由。經(jīng)過(guò)觀察發(fā)現(xiàn)，與該主機(jī)直接相連的路由器具有如下

4個(gè)IP地址和子網(wǎng)掩碼：I.IP地址：11.1.1.1,子網(wǎng)掩碼：255.0.0.0

n.1P地址：II.1.2.1,子網(wǎng)掩碼：255.0.0.0山.IP地址：1

2.1.1.1,子網(wǎng)掩碼：255.0.0.0W.IP地址：13.1.2.1,子網(wǎng)掩碼：

255.0.0.。請(qǐng)問(wèn)IP地址和子網(wǎng)屏蔽碼可能是該主機(jī)的默認(rèn)路由的是（）。

A、I和口

B、I和m

C>CC和w

D、in和w

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

知識(shí)點(diǎn)解析：本題考查默認(rèn)路由的配置，路由器還可采用默認(rèn)路由以減少路由表所

占用的空間和搜索路由表所用的時(shí)間。這種轉(zhuǎn)發(fā)方式在一個(gè)網(wǎng)絡(luò)只有很少的對(duì)外連

接時(shí)是很有用的。本題中主機(jī)地址是一個(gè)標(biāo)準(zhǔn)的A類地址，其網(wǎng)絡(luò)地址為

II.0.0.Oo選項(xiàng)I的網(wǎng)絡(luò)地址為11.0.0.0,選項(xiàng)II的網(wǎng)絡(luò)地址為

11.0.0.0,選項(xiàng)HI的網(wǎng)絡(luò)地址為12.0.0.0,選項(xiàng)IV的網(wǎng)絡(luò)地址為

13.0.0.0,因此和主機(jī)在同一個(gè)網(wǎng)絡(luò)是選項(xiàng)I和n,因此答案為A。

39、以太網(wǎng)交換機(jī)中的端口/MAC地址映射表是()。

A、是由交換機(jī)的生產(chǎn)廠商建立的

B、是交換機(jī)在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中通過(guò)學(xué)習(xí)動(dòng)態(tài)建立的

C、是由網(wǎng)絡(luò)管理員建立的

D、是由網(wǎng)絡(luò)用戶利用特殊的命令建立的

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

知識(shí)點(diǎn)解析：本題考查交換機(jī)中地址映射表的原理，主要與路由器的路由表進(jìn)行區(qū)

分，路由表可以由人為配置靜態(tài)路由，也可以通過(guò)動(dòng)態(tài)協(xié)議建立，而對(duì)于交換機(jī)，

映射表只能在數(shù)據(jù)轉(zhuǎn)發(fā)中進(jìn)行動(dòng)態(tài)學(xué)習(xí)建立，并且每個(gè)表項(xiàng)都有定時(shí)器，具體是收

到一幀后先進(jìn)行自學(xué)習(xí)。查找轉(zhuǎn)發(fā)表中與收到幀的源地址有無(wú)相匹配的項(xiàng)目。如沒(méi)

有，就在轉(zhuǎn)發(fā)表中增加一個(gè)項(xiàng)目(源地址、進(jìn)入的接口和時(shí)間)。如有，則把原有的

項(xiàng)目進(jìn)行更新，因此答案為B。

40、下面關(guān)于電子郵件的說(shuō)法中，不正確的是()。

A、電子郵件只能發(fā)送文本文件

B、電子郵件可以發(fā)送圖形文件

C、電子郵件可以發(fā)送二進(jìn)制文件

D、電子郵件可以發(fā)送主頁(yè)形式的文件

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

知識(shí)點(diǎn)解析：本題考查電子郵件的主要功能，電子郵件不僅僅發(fā)送文本文件，注意

郵件統(tǒng)中SMTP不能傳送可執(zhí)行文件或其他的二進(jìn)制對(duì)象。SMTP限于傳送7位的

ASCII碼，也就是文本文件，因此引入MIME協(xié)議，在沒(méi)有改動(dòng)SMTP或取代

SMTP的前提下，增加了郵件主體的結(jié)構(gòu)，并定義了傳送非ASCII碼的編碼規(guī)

則.因此答案為A.

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

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

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

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

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

是二叉樹根結(jié)點(diǎn)的指針)。if(p!=NULL){while(p—>lchild!=NULL||p—>rchild!

-NULL){while(p>lchild!-NULL)p-p>lchild；if(p>ichild!-NULL)p-p

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

知識(shí)點(diǎn)解析：本題主要考查后序遍歷過(guò)程及特點(diǎn)。

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

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

表空為止，最后再刪除表頭結(jié)點(diǎn)。

標(biāo)準(zhǔn)答案：voiddelall(LinkL5.st&L){LNode*p,*pre,*minp,*minpre；while(L

—*>next!=L){//循環(huán)單鏈表不空時(shí)循環(huán)p=Lnext：pre=L；minp=p；

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

—>datadata){minp=p；minpre=pre；)pre=p；//p>pre同步后移p=p

一〉next；}printf("％c"，minpdata)；//輸出最小值結(jié)點(diǎn)minpre

—>ncxt=minp—>ncxt；//刪除最小值結(jié)點(diǎn)frec(minp)；)free(L)；}

知識(shí)點(diǎn)解析：對(duì)于循環(huán)單鏈表L,在不空時(shí)循環(huán)：每循環(huán)一次查找一個(gè)最小結(jié)點(diǎn)

(由minp指向最小結(jié)點(diǎn)，minpre指向其前趨結(jié)點(diǎn))并刪除它。最后釋放頭結(jié)點(diǎn)。

43、什么是單重分組和雙重分組跳躍進(jìn)位鏈?一個(gè)按3,5,3,5分組的雙重分組跳

躍進(jìn)位鏈(最低位為第0位)，試問(wèn)大組中產(chǎn)生的是哪幾位進(jìn)位?與4,4,4,4分組

的雙重分組跳躍進(jìn)位鏈相比，試問(wèn)產(chǎn)生全部進(jìn)位的時(shí)間是否一致?為什么？

標(biāo)準(zhǔn)答案：?jiǎn)沃胤纸M即組內(nèi)并行、組間串行的進(jìn)位方式；雙重分組即組內(nèi)并行，組

間也并行。雙重分組跳躍進(jìn)位鏈中一個(gè)按3,5,3,5分組，大組中產(chǎn)生的進(jìn)位輸

出是C4、C7、。2和C5而一個(gè)按4,4,4,4分組，大組中產(chǎn)生的進(jìn)位輸出是

C3、C7、Cu和C|5雖然這兩種方式小組內(nèi)的位數(shù)不同，但產(chǎn)生全部進(jìn)位的時(shí)間是

一致的。因?yàn)閮煞N方式都被分成4個(gè)小組，假定一級(jí)“與門”、“或門”的延遲時(shí)間定

為ly,則每一級(jí)進(jìn)位的延遲時(shí)間為2ty。C]經(jīng)過(guò)2ty產(chǎn)生第1小組的進(jìn)位及所有組

進(jìn)位產(chǎn)生函數(shù)G「和組進(jìn)位傳遞函數(shù)Pi*；再經(jīng)過(guò)2ty,由大組產(chǎn)生相應(yīng)的進(jìn)位；再

經(jīng)過(guò)2ty后，才能產(chǎn)生第2、3、4小組內(nèi)的其余的進(jìn)位，所以最長(zhǎng)的進(jìn)位延遲時(shí)間

者B為6tyo

知識(shí)點(diǎn)解析?：假設(shè)最低位為第0位，16位并行加法器均分為4組，最低位的進(jìn)位

輸入為C-],最高位的進(jìn)位輸出為C]5。

44、某機(jī)的主要部件如下圖所示。

移位器1-1R.MDR

“L-￡^JR.

rm1凡Ld

DR,MAR

回函1--------1(1)請(qǐng)補(bǔ)充各部件間的主

要連接線，并注明數(shù)據(jù)流動(dòng)方向。(2)擬出指令SUB(Ri),一(R2)的執(zhí)行流程(含取

指過(guò)程與確定后繼指令地址)。該指令的含義是進(jìn)行減法操作，源操作數(shù)地址和日

的操作數(shù)地址分別在寄存器Ri和R2中，目的操作數(shù)尋址方式為自減型寄存器間接

尋址。其中：LA—A輸入選擇器，LB—B輸入選擇器，C、D一暫存器。

標(biāo)準(zhǔn)答案：(1)將各部件間的主要連接線補(bǔ)充完后，數(shù)據(jù)通路下圖所示。

CR~凡DR~旦

票機(jī)的敷據(jù)通路圖(2)指令

SUB(Ri),一(R2)的含義為(R2)-1-R2((RI))—(。2))一(R2)指令的執(zhí)行流程如

下：①(PC)—MAR；取指令②ReadG)M(MAR)-MDR-1R④(PC)+1-PC

⑤(RI)-MAR；取被減數(shù)⑥Read⑦M(jìn)(MAR)TMDR-C⑧(R2)一1-R2:修改

R的地址@(R2)->MAR:取減數(shù)⑩Read?M(MAR)-MDR->D?(C)一

(D)一MDR；求差并保存結(jié)果？Write?MDR—MM

知識(shí)點(diǎn)解析：第44題的圖中只給出了計(jì)算機(jī)的主要部件，但各部件之間的連接線

沒(méi)有給出，由于LA和LB分別為輸入選擇器，所以特將數(shù)據(jù)通路設(shè)計(jì)為簡(jiǎn)單的單

總線結(jié)構(gòu)形式。

45、實(shí)現(xiàn)一個(gè)經(jīng)典的“讀者一寫者”算法時(shí)，若當(dāng)前臨界區(qū)中有讀者訪問(wèn)，寫者再來(lái)

時(shí)必須在臨界區(qū)外面等候，如果其后讀者源源不斷地到達(dá)，按策略他們均可以進(jìn)入

臨界區(qū)，始終保持臨界區(qū)中有讀者訪問(wèn)，那么寫者可能長(zhǎng)時(shí)間不能進(jìn)入臨界區(qū)而形

成饑餓。為解決此類問(wèn)題，我們修改訪問(wèn)策略，要求當(dāng)寫者到達(dá)時(shí)，寫者具有優(yōu)先

權(quán)。具體說(shuō)，寫者到達(dá)后，已經(jīng)在臨界區(qū)內(nèi)的讀者繼續(xù)讀取直到結(jié)束，而后來(lái)的讀

者就不能進(jìn)入臨界區(qū)。等所有的讀者離開臨界區(qū)以后讓寫者先進(jìn)去訪問(wèn)，然后等寫

者離開后再允許讀者進(jìn)入臨界區(qū)。這所謂“寫者優(yōu)先讀者一寫者''問(wèn)題。請(qǐng)用信號(hào)

量和PV操作來(lái)描述這一組進(jìn)程的工作過(guò)程。

標(biāo)準(zhǔn)答案：第一部分：假設(shè)臨界區(qū)能容納的最大讀者數(shù)量為n。貝I：typedefint

semaphore；//定義信號(hào)量semaphoremutex=l；//讀寫的互斥量semaphore

rcadcrs=n；//讀者的資源量voidReaders(viod)//讀者進(jìn)程{while(TRUE){/

/調(diào)度P(mutex)；//讀寫互斥P(readers)；//讀者資源量減一，為負(fù)時(shí)等待

V(mutex)；//釋放讀寫互斥read_data(void)；//讀者讀取數(shù)據(jù)V(readers)；}

//離開時(shí)釋放讀者數(shù)量，加I一}VoidWriters(void)//寫者進(jìn)程

{while(TRUE){P(mutex)；//獲取讀寫互斥量for(inli=l；iv=n；

i++)P(readers)；//將許可讀者進(jìn)入的資源量消耗光writedata(void)；//寫入

數(shù)據(jù)for(inti=l；iv=n；i++)V(readers)；//釋放讀者的資源量V(mutex)；}//

釋放讀寫互斥量}第二部分：若對(duì)讀者的數(shù)量不加以限制，那么應(yīng)該如下書寫程

序。lypedefintsemaphore；//定義信號(hào)量semaphorerwmulex=l；//讀寫的

互斥量semaphorercmutex=l；//訪問(wèn)讀者計(jì)數(shù)器的互斥量semaphore

nrmutex=1；//寫者等待讀者退出的互斥量intreaderscount=0；//讀者計(jì)數(shù)器

voidReaders(viod)//讀者進(jìn)程{while(TRUE){//調(diào)度P(rwmutex)；//讀寫

互斥P(rcmutex)；//進(jìn)入修改讀者計(jì)數(shù)器互斥readerscount++；//讀者數(shù)量加

-if(readerscount=1)P(nrmutex)；//若是第一個(gè)讀者，互斥寫者V(rcmutex)；/

/釋放讀者計(jì)數(shù)器互斥量V(rwmutex)；//及時(shí)移放讀寫互斥量，允許其它進(jìn)程

申請(qǐng)readdata(void)；//讀者讀取數(shù)據(jù)P(rcmutex)；//離開臨界區(qū)時(shí)讀者計(jì)數(shù)

器互斥rcadcrscount--；//讀者數(shù)量減一if(rcaderscount==0)V(nnnutex)；//所

有讀者退出臨界區(qū)V(rcmutex)；)//離開時(shí)釋放讀者計(jì)數(shù)器互斥量}Void

writers(void)//寫者進(jìn)程{while(TRUE){P(rwmutex)；//獲取讀寫互斥量

P(nrmutex)；//若臨界區(qū)有讀者，等待其退出writc_data(void)；//寫入數(shù)據(jù)

V(nrmutex)；//允許后續(xù)第一個(gè)讀者進(jìn)入臨界區(qū)V(rwmulex)；}//允許新的讀

者和寫者排隊(duì)}上述程序不能保證在等待隊(duì)列中寫者更優(yōu)一點(diǎn)，因?yàn)樯鲜黾s束條件

只能將讀者無(wú)限制地進(jìn)入臨界區(qū)的情況給扉蔽了，而在臨界區(qū)外，讀者和寫者還是

按照先來(lái)先服務(wù)的方式排隊(duì)。第三部分給出的方法使得訪問(wèn)隊(duì)列中只要有寫者出

現(xiàn)，它必然優(yōu)先進(jìn)入臨界區(qū)。typedefintsemaphore；//定義信號(hào)量semaphore

rwmutcx=l；//讀寫的互斥量semaphorercmutcx=l；//訪問(wèn)讀者計(jì)數(shù)器的互

斥量semaphorewcmutex=l；//訪問(wèn)排隊(duì)寫者計(jì)數(shù)器的互斥量semaphore

nrmutex=1；//寫者等待讀者退出的互斥量intreaderscount=0；//讀者計(jì)數(shù)器

intwriterscount=0；//寫者計(jì)數(shù)器voidReaders(viod)//讀者進(jìn)程

{while(TRUE){//調(diào)度P(rwmutex)；//讀寫互斥P(rcmutex)；//進(jìn)入修改

讀者計(jì)數(shù)器互斥readerscount++；//讀者數(shù)量加一

if(readerscount==l)P(nrmutex)；//若是第一個(gè)讀者，互斥寫者V(rcmutex)；//

釋放讀者計(jì)數(shù)器互斥量V(rwmulex)；//及時(shí)釋放讀寫互斥量，允許其它進(jìn)程申

請(qǐng)read_data(void)；//讀者讀取數(shù)據(jù)P(rcnnutex)://離開臨界區(qū)時(shí)讀者計(jì)數(shù)

器互斥readerscount-；//讀者數(shù)量減一if(readerscounl==0)V(nrmutex)；//所

有讀者退出臨界區(qū)V(rcmulex)；}//離開時(shí)釋放讀者計(jì)數(shù)器互斥量}Void

writers(void)//寫者進(jìn)程{while(TRUE){P(wcmutex)；//獲取寫者隊(duì)列互斥量

writerscount++；//寫者隊(duì)列加一if(writerscount==l)P(ru/mutex)；//第一寫者

使用讀寫互斥量V(wcmurex)；//釋放寫者計(jì)數(shù)互斥量P(nrmutex)；//若臨界

區(qū)有讀者，等待其退出write_data(void)；//寫入數(shù)據(jù)V(nimutex)；//釋放后

續(xù)第一個(gè)讀者P(wcmutex)；//獲取寫者隊(duì)列互斥量writerscount-；//寫者隊(duì)

列減一if(writerscount==0)V(rwmutex)；//最后一個(gè)寫者退出，釋放臨界區(qū)

V(wcmutex)；)//釋放寫者計(jì)數(shù)互斥量}每個(gè)讀者進(jìn)程最開始都要申請(qǐng)一下

rwmulex信號(hào)量，之后在真正做讀操作前即讓出(使得寫進(jìn)程可以隨時(shí)申請(qǐng)到

rwmulex)o而只有第一個(gè)寫進(jìn)程需要中請(qǐng)nnnulex,之后就一直占著不放了，直到

所有寫進(jìn)程都完成后才讓出。等于只要有寫進(jìn)程提出申請(qǐng)就禁止讀進(jìn)程排隊(duì)，從而

提高了寫進(jìn)程的優(yōu)先級(jí)。

知識(shí)點(diǎn)解析：“寫者優(yōu)先讀者一寫者''問(wèn)題也是考試的熱點(diǎn)，解決此類問(wèn)題也分兩方

面，一是讀者訪問(wèn)臨界區(qū)的最大數(shù)量是有限的，例如說(shuō)n,那么程序就比較簡(jiǎn)單，

看解答中第一部分。若是不限的，則必須設(shè)定一個(gè)排隊(duì)的信號(hào)量，所有到達(dá)臨界區(qū)

的所有讀者一寫者均需在此排隊(duì)，按先來(lái)先服務(wù)使用臨界區(qū)，一旦進(jìn)入臨界區(qū)以后

就釋放該信號(hào)量。見解答的第二部分。若需要徹底地讓后到的寫者跨越前面等待

的讀者，那么需要設(shè)定更多的限制，見解答的第三部分。

46、某32位計(jì)算機(jī)系統(tǒng)采用段頁(yè)式虛擬存儲(chǔ)管理，現(xiàn)有一個(gè)進(jìn)程被分成5段，其

段號(hào)和段長(zhǎng)見下表，段內(nèi)分頁(yè)，頁(yè)表見下，存放在內(nèi)存中，每頁(yè)的長(zhǎng)度為4096B。

進(jìn)程運(yùn)行到某一個(gè)指令，其地址為（2,3,010）,當(dāng)前CPU的寄存器和地址加法器

的狀態(tài)如圖所示，當(dāng)上述指令執(zhí)行時(shí)，操作系統(tǒng)如何工作?CPU