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

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

1、若線性表最常用的運(yùn)算是查找第i個(gè)元素及其前驅(qū)的值，則下列存儲方式最節(jié)

省時(shí)間的是（）。

A、單鏈表

B、雙鏈表

C、單循環(huán)鏈表

D、順序表

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

知識點(diǎn)解析：線性表中常用的操作是取第i個(gè)元素，所以應(yīng)選擇隨機(jī)存取結(jié)構(gòu)，即

順序表，同時(shí)在順序表中查找第i個(gè)元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既

不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前驅(qū)也不方便，雙鏈表雖然能快速查找第i

個(gè)元素的前驅(qū)，但不能實(shí)現(xiàn)隨機(jī)存取。

2、在非空雙循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指結(jié)點(diǎn)的過程依次為：p

—>next=q；P->prior=q->prior；q—>prior=p；下一條語句是（）。

A、q—>next=p；

B、q—>prior—>next=p；

C、p->prior->next=p；

D^p—>next—>prior=p；

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

知識點(diǎn)解析：本題主要考查雙鏈表插入時(shí)指針的變化，由于兩個(gè)方向共需要修改4

個(gè)指針，指針操作的順序不是唯一的，但也不是任意的。只要把每條指針操作的涵

義搞清楚，就不難理解了。設(shè)q指向雙向鏈表中某結(jié)點(diǎn)，p指向待插入的新結(jié)點(diǎn)，

將*p插入到的的前面，插入過程如下圖所示：操作如下：

①p->next=q；@p->prior=q—>prior；（3）q—>prior=p；（4）p—>prior—>next

=p；顯然，題目中需要補(bǔ)充的語句為第④條語句，答案為C。

3、在一個(gè)長度為n的順序存儲線性表中，刪除第i個(gè)元素（1S&+1）時(shí)，需要從前

向后依次前移的元素個(gè)數(shù)是（）。

A、n-i

BNn—i+1

C、n-i—I

D、i

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

知識點(diǎn)解析：順序表的刪除運(yùn)算的時(shí)間主要消耗在了移動表中元素上，刪除第i個(gè)

元素時(shí)，其后面的元素句+]?an都要向上移動一個(gè)位置，共移動了n—i個(gè)元素。

4、將兩個(gè)長度為n的遞增有序表歸并成一個(gè)長度為2n的遞增有序表，最少需要進(jìn)

行關(guān)鍵字比較次數(shù)是（），

A、1

B、n—1

C、n

D、2n

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

知識點(diǎn)解析：假設(shè)有兩個(gè)有序表A和B都遞增有序，當(dāng)有序表A所有元素均小于

B的元素時(shí)，只需將A的所有元素與B的第一個(gè)元素比較即可，其比較n次。

5、已知一算術(shù)表達(dá)式的中綴形式為A+B*C—D/E,后綴形式為ABC+DE/

一，其前綴形式為（）。

A、一A+B*CD/E

B、-A+B*CD/E

C、-4-*ABC/DE

D、一+A*BC/DE

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

知識點(diǎn)解析：將算術(shù)表達(dá)式的中綴形式作為一棵二叉樹的中序遍歷序列，將后綴形

式作為這棵二叉樹的后序遍歷序列，再由二又樹的中序遍歷序列和后序遍歷序列唯

一的確定這棵二叉樹，在對其進(jìn)行先序遍歷，就可得出算術(shù)表達(dá)式的前綴形式。

6、一個(gè)循環(huán)隊(duì)列Q最多可存儲m個(gè)元素，已知其頭尾指針分別是from和rear,

則判定該循環(huán)隊(duì)列為滿的條件是（）。

A、Q.rear—Q.front==m

B、Q.rear!=Q.front

C^Q.front==（Q.rear+l）%m

D、Q.front==Q.rear%m+l

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

知識點(diǎn)解析：少用一個(gè)元素空間，每次入隊(duì)前測試入隊(duì)后頭尾指針是否會重合，如

果會重合就認(rèn)為隊(duì)列已滿，這種情況下隊(duì)滿的條件是：（Q.rcar+l）%MAXsIZE=

=Q.front,能和空隊(duì)區(qū)別開。

7、某二叉樹的先序和后序序列正好相反，則該二叉樹一定是（）。

A、空或只有一個(gè)結(jié)點(diǎn)

B、高度等于其結(jié)點(diǎn)數(shù)

C^任一結(jié)點(diǎn)無左孩子

D、任一結(jié)點(diǎn)無右孩子

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

知識點(diǎn)解析?：由于先序遍歷是“根——左子樹——右子樹”，而后序遍歷是“左子樹

-右子樹一根”，若某二叉樹的先序和后序序列正好相反，則該二叉樹每層

左、右子樹只能有1個(gè)，即則該二叉樹一定是高度等于其結(jié)點(diǎn)數(shù)。

8、對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左、右孩

子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，為實(shí)現(xiàn)

編號可米用的遍歷是（）c

A、先序

B、中序

C、后序

D、從根開始按層次遍歷

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

知識點(diǎn)解析：根據(jù)題意和先序、中序、后序遍歷規(guī)則，可簡單地判斷出正確答案。

9、一棵哈夫變樹共有9個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)為（）。

A、4

B,5

C、6

D、7

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

知識點(diǎn)解析：哈夫夏樹中沒有度為1的結(jié)點(diǎn)，用n個(gè)權(quán)值（對應(yīng)，z個(gè)葉子結(jié)點(diǎn)）構(gòu)

造哈夫曼樹，共需要n-l次合并，即哈夫曼樹中非葉子結(jié)點(diǎn)的總數(shù)為n-l,總結(jié)

點(diǎn)個(gè)數(shù)為2n—K

10、下列有關(guān)散列查找的敘述正確的是（）。

A、散列存儲法只能存儲數(shù)據(jù)元素的值，不能存儲數(shù)據(jù)元素之間的關(guān)系

B、散列沖突是指同一個(gè)關(guān)鍵字對應(yīng)多個(gè)不同的散列地址

C、用線性探測法解決沖突的散列表中，散列函數(shù)值相同的關(guān)鍵字總是存放在一片

連續(xù)的存儲單元中

D、若散列表的裝填因子a《I,則可避免沖突的產(chǎn)生

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

知識點(diǎn)解析：在散列表中，每個(gè)元素的存儲位置通過散列函數(shù)和解決沖突的方法得

到，散列存儲法只存儲數(shù)據(jù)元素的值，不能存儲數(shù)據(jù)元素之間的關(guān)系，所以選項(xiàng)A

正確；散列沖突是指多個(gè)不同關(guān)鍵字對應(yīng)相同的散列地址，選項(xiàng)B錯(cuò)誤；用線性

探測法解決沖突的散列表中，散列函數(shù)值相同的關(guān)鍵字不一定總是存放在一片連續(xù)

的存儲單元中，選項(xiàng)C錯(cuò)誤；裝填因子a越小，發(fā)生沖突的概率越小，但仍有可

能發(fā)生沖突。

11、以下排序方法中，不需要進(jìn)行關(guān)鍵字的比較的是（）。

A、快速排序

B、歸并排序

C、基數(shù)排序

D、堆排序

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

知識點(diǎn)蓊析：基數(shù)排序是采用分配和收集實(shí)現(xiàn)的，不需要進(jìn)行關(guān)鍵字的比較，而其

他幾種排序方法都是通過關(guān)鍵字的比較實(shí)現(xiàn)的。

12、“容量為640KB的存儲器”是指（）。

A、640x1（）4字節(jié)的存儲器

B、640x1（）3位的存儲器

C、640x210位的存儲器

D、640x21°字節(jié)的存儲器

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

知識點(diǎn)解析：通常，以字節(jié)數(shù)來表示存儲容量，這樣的計(jì)算機(jī)稱為字節(jié)編址的計(jì)算

,0

機(jī)?！叭萘?40KB”是指640x1KB,W640x2Bo［歸納總結(jié)］在表示存儲器容量大

小時(shí)，經(jīng)常用到K,M,G,T,P之類的字符，它們與通常意義下的K,M,G,

w

wMS5N

WLT0nniA24

TCTcrO

KPrt1)LTgEK43U4

T,P有些差異，見下表。每1024個(gè)字節(jié)稱

為1K字節(jié)，每1024K字節(jié)稱為1M字節(jié),每1024M字節(jié)稱為1G字節(jié)...計(jì)算機(jī)

的主存容量越大，存放的信息就越多，處理問題的能力就越強(qiáng)。［解題技巧］選項(xiàng)

B、C的單位是位而不是字節(jié)，選項(xiàng)A與實(shí)際的存儲單元數(shù)有誤差。

13、在微程序控制的計(jì)算機(jī)中，若要修改指令系統(tǒng)，只要（）。

A、改變時(shí)序控制方式

B、改變微指令格式

C、增加微命令個(gè)數(shù)

D、改變控制存儲器的內(nèi)容

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

知識點(diǎn)解析：在微程序控制的計(jì)算機(jī)中，若要修改指令系統(tǒng)，只需修改相應(yīng)指令的

微程序即可。這些微程序都存放在控制存儲器中，所以只需改變控制存儲器的內(nèi)

容。［歸納總結(jié)］微程序控制器的設(shè)計(jì)思想和組合邏輯控制器的設(shè)計(jì)思想截然不同。

它具有設(shè)計(jì)規(guī)整、調(diào)試、維修以及更改、擴(kuò)充指令方便的優(yōu)點(diǎn)，易于實(shí)現(xiàn)自動化設(shè)

計(jì)，已成為當(dāng)前控制器的主流C但是，由于它增加了一級控制存儲器，所以指令執(zhí)

行速度比組合邏輯控制器慢。

14、生成多項(xiàng)式為x3+x+l,則數(shù)據(jù)信息10101的CRC編碼是（）。

A、1.00101e+007

B、1.00001e+007

C、1.010lle+007

D、11101001

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

知識點(diǎn)解析：CRC編碼由數(shù)據(jù)信息和校驗(yàn)位共同組成，前5位為數(shù)據(jù)位，后3位

為檢驗(yàn)位。10101000^1011,余數(shù)為101,將余數(shù)101(檢驗(yàn)位)拼接在數(shù)據(jù)位的后

面，就得到CRC碼。［歸納總結(jié)］循環(huán)冗余校驗(yàn)碼是通過除法運(yùn)算來建立有效信息

位和校驗(yàn)位之問的約定關(guān)系的。假設(shè)，待編碼的有效信息以多項(xiàng)式M(X)表示，將

它左移若干位后，用另一個(gè)約定的多項(xiàng)式G(x)去除，所產(chǎn)生的余數(shù)R(X)就是檢驗(yàn)

位。有效信息和檢驗(yàn)位相拼接就構(gòu)成了CRC碼。當(dāng)整個(gè)CRC碼被接收后，仍用約

定的多項(xiàng)式G(X)去除，若余數(shù)為0表明該代碼是正確的；若余數(shù)不為0表明某一

位出錯(cuò)，再進(jìn)一步由余數(shù)值確定出錯(cuò)的位置，以便進(jìn)行糾正?，F(xiàn)生成多項(xiàng)式為x3

+x+l,表示除數(shù)為1011。［解題技巧］在四個(gè)選項(xiàng)中，只有選項(xiàng)C的前5位與數(shù)

據(jù)位相同，所以實(shí)際上并不需要真得做除法運(yùn)算，就可以立即得出正確答案。

15、判斷加減法溢出時(shí)，可采用判斷進(jìn)位的方式，如果符號位的進(jìn)位為CO,最高

數(shù)值位為ci,產(chǎn)生溢出的條件是()。I.co產(chǎn)生進(jìn)位；n.ci產(chǎn)生進(jìn)位；

m.co、ci都產(chǎn)生進(jìn)位；iv.co、ci都不產(chǎn)生進(jìn)位；v.co產(chǎn)生進(jìn)位，ci不

產(chǎn)生進(jìn)位；VI.CO不產(chǎn)生進(jìn)位，C1產(chǎn)生進(jìn)位

A、1和n

B、n

C、IV

D、V和VI

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

知識點(diǎn)解析：采用進(jìn)位位來判斷溢出時(shí)，當(dāng)最高有效位和符號位的值不相同時(shí)才會

產(chǎn)生溢出。［歸納總結(jié)］兩正數(shù)相加I,當(dāng)最高有效位產(chǎn)生進(jìn)位(Ci=l)而符號位不產(chǎn)

生進(jìn)位(Cs=O)時(shí)，發(fā)生正溢；兩負(fù)數(shù)相加，當(dāng)最高有效位不產(chǎn)生進(jìn)位(Ci=0)而符

號位產(chǎn)生進(jìn)位(Cs=l)時(shí)，發(fā)生負(fù)溢。故溢出條件為：溢出?仁6+(；(\?(；?0,。

16、內(nèi)存按字節(jié)編址，地力匕從90000H至UCFFFFH,若用存儲容量為16Kx8bit芯片

構(gòu)成該內(nèi)存，至少需要的芯片數(shù)是()。

A、2

B、4

C、8

D、16

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

知識點(diǎn)解析：CFFFF-90000+I=40000,即256KB,若用存儲容量為16Kx8bil芯

片則需芯片數(shù)=(256KxB)/(16Kx8)=16(片)。［歸納總結(jié)］采用字?jǐn)U展的方法，用若

干存儲芯片構(gòu)成一個(gè)存儲器。［解題技巧］用地址范圍的末地址減去首地址再加1,

就可以方便的計(jì)算出存儲空間的大小。

17、某計(jì)算機(jī)指令字長為16位，指令有雙操作數(shù)、單操作數(shù)和無操作數(shù)3種格

式，每個(gè)操作數(shù)字段均有6位二進(jìn)制表示，該指令系統(tǒng)共有m條(m<16)雙操作數(shù)

指令，并存在無操作數(shù)有令。若采用擴(kuò)展操作碼技術(shù)，那么最多還可設(shè)計(jì)出單操作

數(shù)指令的條數(shù)是()。

A、26

B、(24-m)x26-l

C、(24-m)x26

D、(24-m)x(26-l)

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

知識點(diǎn)解析：雙操作數(shù)指令操作碼字段占4位，單操作數(shù)指令操作碼字段占10

位，無操作數(shù)指令操作碼字段占16位?，F(xiàn)指令系統(tǒng)中有m條雙操作數(shù)指令，則給

單操作數(shù)和無操作數(shù)指令留下了Q4—m)個(gè)擴(kuò)展窗口。因?yàn)榇嬖谥鵁o操作數(shù)指令，

所以單操作數(shù)指令必須要給無操作數(shù)指令留下一個(gè)擴(kuò)展窗口，最終最多可以設(shè)計(jì)出

單操作數(shù)指令的數(shù)目為(24—m)x26-l。［歸納總結(jié)］因?yàn)槿绻噶铋L度一定，則地

址碼與操作碼字段的長度是相互制約的。采用擴(kuò)展操作碼法是讓操作數(shù)地址個(gè)數(shù)多

的指令(三地址指令)的操作碼字段短些，操作數(shù)地址個(gè)數(shù)少的指令(一或零地址指

令)的操作碼字段長些，這樣既能充分地利用指令的各個(gè)字段，又能在不增加指令

K度的情況下擴(kuò)展操作碼的位數(shù)，使它能表示更多的指令。［解題技巧］選項(xiàng)C沒

有給無操作數(shù)指令留下才展窗口，不完全符合題意。

18、指令流水線將一條指令的執(zhí)行過程分為四步，其中第1、2和4步的經(jīng)過時(shí)間

為人如下圖所示。若該流水線順序執(zhí)行，50條指令共用153與，并且不考慮相關(guān)

問題，則該流水線的瓶頸第3步的時(shí)間是()。丁丁~

A、2At

B、3At

C、4At

D、5At

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

知識點(diǎn)解析：在第18題圖中，第3個(gè)流水段的執(zhí)行時(shí)間沒有給出，顯然這是一個(gè)

瓶頸段，設(shè)它的執(zhí)行時(shí)間為X。通過列方程(3+X)At+49XAt=1532U,可以求得

X=3o［歸納總結(jié)］對于包含瓶頸段的指令流水線，完成n個(gè)任務(wù)的解釋共需時(shí)間T

=2*'+(n-1)maxlAti，),其中k為流水線段數(shù)。［解題技巧］首先要列方程，

然后才能求出瓶頸段的執(zhí)行時(shí)間。

19、以下關(guān)于CPU的敘述中，錯(cuò)誤的是()。

A、CPU產(chǎn)生每條指令的操作信號并將操作信號送往相應(yīng)的部件進(jìn)行控制

B、程序計(jì)數(shù)器PC除了存放指令地址，也可以臨時(shí)存儲算術(shù)/邏輯運(yùn)算結(jié)果

C、CPU中的控制器決定計(jì)算機(jī)運(yùn)行過程的自動化

D、指令譯碼器是CPU控制器中的部件

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

知識點(diǎn)解析：程序計(jì)數(shù)器PC又稱指令計(jì)數(shù)器，用來存放正在執(zhí)行的指令地址或接

著要執(zhí)行的下一條指令地址，不能用于臨時(shí)存儲算術(shù)/邏輯運(yùn)算結(jié)果。［歸納總結(jié)］

控制器中應(yīng)包括指令部件、時(shí)序部件、微操作信號發(fā)生器（控制單元）、中斷控制邏

輯等。指令部件中包括程序計(jì)數(shù)器、指令寄存器和指令譯碼器。［解題技巧］程序計(jì)

數(shù)器歸屬于控制器，而與運(yùn)算器沒有關(guān)系。

20、在系統(tǒng)總線中，地址總線的位數(shù)（）。

A、與機(jī)器字長有關(guān)

B、與存儲單元個(gè)數(shù)有關(guān)

C、與存儲字長有關(guān)

D、與存儲器帶寬有關(guān)

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

知識點(diǎn)解析：地址總線的位數(shù)與存儲單元個(gè)數(shù)有關(guān)，地址總線的位數(shù)越長，可訪問

的存儲單元個(gè)數(shù)就越多。［歸納總結(jié)］系統(tǒng)總線按傳送信息的不同可以細(xì)分為：地址

總線、數(shù)據(jù)總線和控制總線。地址總線由單方向的多根信號線組成，用于CPU向

主存、外設(shè)傳輸?shù)刂沸畔?；?shù)據(jù)總線由雙方向的多根信號線組成，CPU可以沿這

些線從主存或外設(shè)讀入數(shù)據(jù)，也可以沿這些線向主存或外設(shè)送出數(shù)據(jù)：控制總線上

傳輸?shù)氖强刂菩畔ⅲ–PU送山的控制命令和主存（或外設(shè)）返回CPU的反饋信

號。地址總線寬度決定了CPU可以訪問的最大的物理地址空間，簡單地說就是

CPU到底能夠使用多大容量的主存。例如，32位地址線，可尋址的最大容量為232

=4096MB（4GB）o［解題技巧］地址總線的位數(shù)與選項(xiàng)A、C、D均無：關(guān)，采用排

除法。

21、假設(shè)某硬盤由5個(gè)盤片構(gòu)成（共有8個(gè)記錄面），盤面有效記錄區(qū)域的外直徑為

30厘米，內(nèi)直徑為10厘米，記錄位密度為250位/亳米，磁道密度為16道/亳

米，每磁道分16個(gè)扇區(qū)，每扇區(qū)512字節(jié)，則該硬盤的格式化容量約是（）。

A8X（3O-1Q）X10X250X16."n8』（30—I0X16X16X5】2.4n

8X1024X10240以2X1024X1024”

8X（30-10）X10X250X16X16“n8」（30-10）X16X16X512

rJ8X1024X1024°nj2X1024X1024wt0>

A、

B、

c、

D、

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

知識點(diǎn)解析：格式化容量計(jì)算中根據(jù)扇區(qū)數(shù)和扇區(qū)容量計(jì)算出每條磁道上的信息

量，然后再乘以總磁道數(shù)。而總磁道數(shù)計(jì)算時(shí)，首先求出每面磁道數(shù)（柱面數(shù)），再

乘以記錄面數(shù)。［歸納總結(jié)］磁盤的容量有格式化容量與非格式化容量之分，磁盤上

標(biāo)稱的容量為格式化容量。計(jì)算磁盤容量公式中的總磁道數(shù)是指記錄面數(shù)與圓柱面

數(shù)的乘積。其中柱面數(shù)的計(jì)算公式為：柱面數(shù)=（外半徑一內(nèi)半徑）x道密度格式化

容量是磁盤實(shí)際可以使用的容量。新的磁盤在使用之前需要先進(jìn)行格式化，格式化

實(shí)際上就是在磁盤上劃分記錄區(qū)，寫入各種標(biāo)志信息和地址信息。這些信息占用了

磁盤的存儲空間，故格式化之后的有效存儲容量要小于非格式化容量。它的計(jì)算公

式為：格式化容量=每道扇區(qū)數(shù)X扇區(qū)容量X總磁道數(shù)［解題技巧］計(jì)算格式化容量

時(shí)只與道密度有關(guān)，而與位密度沒有關(guān)系，所以選項(xiàng)A和C都是錯(cuò)誤的，而選項(xiàng)

B擴(kuò)大了一個(gè)10倍。

22、下列情況下，可能不發(fā)生中斷請求的是（）。

A、13MA操作結(jié)束

B、一條指令執(zhí)行完畢

C、機(jī)器出現(xiàn)故障

D、執(zhí)行、'軟中斷”指令

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

知識點(diǎn)解析：在4個(gè)選項(xiàng)中，唯有選項(xiàng)B為正確答案，因?yàn)椴⒎敲織l指令執(zhí)行完

畢都會產(chǎn)生中斷請求。［歸納總結(jié)］DMA操作結(jié)束必須產(chǎn)生中斷請求以進(jìn)行后處

理；機(jī)器出現(xiàn)故障將產(chǎn)生故障中斷請求對故障進(jìn)行處理；當(dāng)執(zhí)行“軟中斷”（INT）指

令時(shí)也將產(chǎn)生中斷請求進(jìn)行相應(yīng)的處理。

23、用戶在編寫程序時(shí)計(jì)劃讀取某個(gè)數(shù)據(jù)文件中的50個(gè)數(shù)據(jù)塊記錄，他使用操作

系統(tǒng)提供的接口是（）。

A、系統(tǒng)調(diào)用

B、圖形用戶接口

C、原語

D、命令行輸入控制

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

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

編寫程序所使用的是系統(tǒng)調(diào)用，例如read。。系統(tǒng)調(diào)用會給用戶提供一個(gè)簡單的使

用計(jì)算機(jī)的接口，而將復(fù)雜的對硬件（例如磁盤），和文件操作（例如查找和訪問）的

細(xì)節(jié)屏蔽起來，為用戶提供一種高效使用計(jì)算機(jī)的途徑。

24、計(jì)算機(jī)系統(tǒng)中2個(gè)協(xié)作進(jìn)程之間不能用來進(jìn)行進(jìn)程間通信的是（）。

A、數(shù)據(jù)庫

B、共享內(nèi)存

C、消息傳遞機(jī)制

D、管道

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

知識點(diǎn)解析：本題考查進(jìn)程間的通信，進(jìn)程間的通信主要有管道，命名管道，消息

傳遞，共享內(nèi)存，文件映射和套接字等。數(shù)據(jù)庫不能用于進(jìn)程間的通信。

25、時(shí)間片輪轉(zhuǎn)調(diào)度算法是為了（）。

A、多個(gè)終端能得到系統(tǒng)的及時(shí)響應(yīng)

B、使系統(tǒng)變得高效

C、優(yōu)先級較高的進(jìn)程得到及時(shí)響應(yīng)

D、需要CPU時(shí)間最少的進(jìn)程最先做

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

知識點(diǎn)解析：本題考查進(jìn)程的時(shí)間片輪轉(zhuǎn)調(diào)度算法。時(shí)間片輪轉(zhuǎn)的主要目的是使得

多個(gè)交互的用戶能夠及時(shí)得到響應(yīng)，使得用戶以為“獨(dú)占”計(jì)算機(jī)在使用。因此它并

沒有偏好，也不會對特殊進(jìn)程特殊服務(wù)。時(shí)間片輪轉(zhuǎn)增加了系統(tǒng)開銷，所以不會使

得系統(tǒng)高效運(yùn)轉(zhuǎn)，吞吐量和周轉(zhuǎn)時(shí)間均不如批處理優(yōu)。但是其較快速的響應(yīng)時(shí)間使

得用戶能夠與計(jì)算機(jī)進(jìn)行交互，改善了人機(jī)環(huán)境，滿足用戶需求。

26、一次分配所有資源的方法可以預(yù)防死鎖的發(fā)生，它破壞的死鎖四個(gè)必要條件中

的()。

A、互斥條件

B、占有并請求

C、非剝奪條件

D、循環(huán)等待

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

知識點(diǎn)解析：發(fā)生死鎖的四個(gè)必要條件如下：互斥條件、占有并請求資源、非剝奪

條件和循環(huán)等待條件。一次分配所有資源的方法是當(dāng)進(jìn)程需要資源時(shí)，一次性提出

所有的請求，若請求的所有資源均滿足則分配，只要有一項(xiàng)不滿足，那么不分配任

何資源，該進(jìn)程阻塞，直到所有的資源空閑后，滿足了進(jìn)程的所有需求時(shí)再分配。

這種分配方法不會部分占有資源，所以就打破了死鎖的四個(gè)必要條件之一，實(shí)現(xiàn)了

對死鎖的預(yù)防。但是，這種分配方式需要湊齊所有資源，所以，當(dāng)一個(gè)進(jìn)程所需的

資源比較多時(shí)，資源的利用率會比較低，甚至?xí)斐蛇M(jìn)程的饑餓。正確答案為B。

27、有二個(gè)處理機(jī)PI和P2,它們各自有一個(gè)cache和主存，分別為Cl、C2和

CIMlC2M2

UKB128MB12KB】28MB

40vtlOOOfi*301M90O??

Ml、M2,其性能見下表:請4時(shí)就若兩個(gè)處理機(jī)的

指令系統(tǒng)相同，指令的執(zhí)行時(shí)間與存儲器的平均存取周期成正比，當(dāng)執(zhí)行某程序

時(shí)，cache的命中率為70%,則PI處理機(jī)的速度比P2處理機(jī)().

A、更快

B、更慢

C、相等

D、不能確定

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

知識點(diǎn)解析：本題考查多級存儲層次下的平均訪問時(shí)間的計(jì)算。根據(jù)題意，處理機(jī)

執(zhí)行指令的時(shí)間與存儲器的平均存取周期成正比，因此只要計(jì)算出存儲器的平均存

取周期，即可比較出兩者的優(yōu)劣。對于處理機(jī)P1,存儲器的平均存取周期為：

40x().7+(100()+40)x(1—0.7)=340ns對于處理機(jī)P2,存儲器的平均存取周期

為：50x0.7+(900+50)x(l—0.7)=320ns因此可以看出,處理機(jī)P1需要更多的

處理機(jī)時(shí)間，處理機(jī)P1比處理機(jī)P2更慢。

28、在頁式存儲管理中，每個(gè)頁表的表項(xiàng)實(shí)際上是用于實(shí)現(xiàn)()。

A、訪問內(nèi)存單元

B、靜態(tài)重定位

C、動態(tài)重定位

D、裝載程序

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

知識點(diǎn)編析：本題考查頁式存儲管理的基本概念。頁式存儲管理的基本點(diǎn)是解決程

序在內(nèi)存中離散存放的問題，其尋址方式是借鑒于動態(tài)重定位的技術(shù)，在動態(tài)重定

位技術(shù)中，通過設(shè)置基址寄存器，將程序的邏輯地址通過基址寄存器和地址加法

器，動態(tài)地實(shí)現(xiàn)了地址轉(zhuǎn)換（即每一條都是自動轉(zhuǎn)換的），操作系統(tǒng)在裝載程序時(shí)可

以不用像靜態(tài)重定位那樣計(jì)算程序代碼的地址定位，使得地址轉(zhuǎn)換快捷又簡單。頁

式存儲管理將動態(tài)重定位中的基址寄存器用一組頁表來替代，當(dāng)訪問不同的頁面

時(shí)，在基址寄存器中只要存放該頁面的頁框號便可以快速地實(shí)現(xiàn)地址轉(zhuǎn)換。所以

說，頁表項(xiàng)實(shí)際上是實(shí)現(xiàn)了動態(tài)重定位。

29、物理文件的組織方式的確定是（）。

A、應(yīng)用程序

B、索引文件

C、外存容量

D、操作系統(tǒng)

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

知識點(diǎn)解析：文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是從兩個(gè)：不同觀點(diǎn)組織文件的結(jié)構(gòu)而形

成的概念。用戶根據(jù)自己的需要確定文件的邏輯結(jié)構(gòu)，而文件物理結(jié)構(gòu)則是系統(tǒng)設(shè)

計(jì)者根據(jù)文件存儲器的特性和用戶對文件的使用情況來確定的，一旦確定，就由操

作系統(tǒng)管理。故正確答案為D。

30、假如一個(gè)FCB塊的大小是64字節(jié)。盤塊的大小為1KB,則在每個(gè)盤塊中能存

放的最大FCB數(shù)是（）。

A、64

R、1

C、1000

D、16

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

知識點(diǎn)解析：FCB的存放是不能分開的，所以1KB大小的盤塊能存放的FCB數(shù)

為：1024:64=16,要注意單位的統(tǒng)一，約定俗成的KB一般指1024B,kB指

lOOOBo

31、一個(gè)文件的絕對路經(jīng)名的出發(fā)點(diǎn)是（）。

A、當(dāng)前目錄

B、根目錄

C、磁盤盤符

D、公共目錄

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

知識點(diǎn)解析：本題考查文件路徑名的概念。文件的路徑名是從根目錄到目標(biāo)文件所

經(jīng)歷的路徑上各符號名的集合。路徑名有二種形式，第一種是絕對路徑名，它由根

目錄出發(fā)，沿著目錄的路徑直到文件，絕對路徑名總是從根目：錄出發(fā)，并且是唯

一的。第二種是相對路徑名，它與工作目錄（也稱當(dāng)前目錄）一起使用，用戶一般預(yù)

先指定一個(gè)目錄為當(dāng)前目錄，這時(shí)，所有的路徑名均從當(dāng)前目錄出發(fā)，這樣的路徑

名，只要不是從根目錄出發(fā)的，都稱為相對路徑名。

32、如果一個(gè)沒有內(nèi)存映射的10設(shè)備與主存之間交換數(shù)據(jù)，希望這種數(shù)據(jù)交換不

經(jīng)過CPU來完成，那么，可以采用的最佳方法是（）。

A、程序查詢方式

B、中斷技術(shù)

C、通道技術(shù)

D、DMA方式

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

知識點(diǎn)解析：本題考查對通道和DMA的理解。對于CPU干預(yù)的IO操作，程序查

詢和中斷技術(shù)都是必要的，而可以解放CPU且能控制數(shù)據(jù)交換的10操作只能是通

道技術(shù)和DMA方式。經(jīng)過分析這兩種方式，我們發(fā)現(xiàn)，DMA方式需要將10設(shè)備

的數(shù)據(jù)口地址映射到內(nèi)存中，通道是不需要的，所以采用通道控制方式來作此傳送

是最佳的。

33、下面對計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)中協(xié)議所做的描述，錯(cuò)誤的是（）。

A、網(wǎng)絡(luò)協(xié)議的三要素是語法、語義和同步

B、協(xié)議是控制兩個(gè)對等層實(shí)體之間通信的規(guī)則的集合

C、在OSI參考模型中，要實(shí)現(xiàn)第N層的協(xié)議，需要使用N+1層提供的服務(wù)

D、協(xié)議規(guī)定了對等層實(shí)體之間所交換的信息的格式和含義

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

知識點(diǎn)解析：協(xié)議是控制兩個(gè)對等層實(shí)體之間通信的規(guī)則的集合，網(wǎng)絡(luò)協(xié)議的三要

素是語法、語義和同步,其中語法和語義規(guī)定了對等層實(shí)體之間所交換的信息的格

式和含義，但第N層協(xié)議要為第N+I層提供服務(wù)，因此選項(xiàng)C的論述是錯(cuò)誤的，

答案是C。

34、對于帶寬為6MHz的信道，若用8種不同的狀態(tài)來表示數(shù)據(jù)，在不考慮熱噪聲

的情況下，該信道每秒最多能傳送的位數(shù)是（）。

A、36X106

B、18X106

C、48x106

D、96x106

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

知識點(diǎn)解析：本題考查奈奎斯特定理的直接應(yīng)用，注意這里采用8種不同的狀態(tài)，

因此離散個(gè)數(shù)為8,由C=2xHxlog2N=2x6x|og28=36Mbps,因此答案為A。

35、在MAC子層中，數(shù)據(jù)傳輸?shù)幕締卧牵ǎ?/p>

A、比特流

B、MAC幀

C、LLCPDU

D、數(shù)據(jù)報(bào)

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

知識點(diǎn)解析：本題考查局域網(wǎng)的體系結(jié)構(gòu)，局域網(wǎng)的數(shù)據(jù)鏈路層分為邏輯鏈路控制

即LLC和媒體接入控制，即MAC,因此MAC子層還是屬于鏈路層，數(shù)據(jù)傳輸單

元就是MAC幀，答案為B。［歸納總結(jié)］IEEE802標(biāo)準(zhǔn)將數(shù)據(jù)鏈路層劃分成兩個(gè)子

層：LLC和MAC子層。凡與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通信介質(zhì)，訪問方式無關(guān)的部分集

中在LLC子層，換句話說，無論是以太網(wǎng)，令牌環(huán)網(wǎng)或令牌總線網(wǎng)，它的LLC子

層都是相同的。LLC子層為上層用戶提供三種類型的服務(wù)可供選擇。它們是無確

認(rèn)連接，有確認(rèn)無連接和面相連接三種服務(wù)。一般提供三種可選功能。MAC子層

的任務(wù)：將LLC幀包裝成MAC幀，并將MAC幀從源站點(diǎn)傳輸?shù)侥康恼军c(diǎn)。

IEEE802標(biāo)準(zhǔn)分別規(guī)定了三種MAC協(xié)議，每種協(xié)議對應(yīng)一種特定的介質(zhì)訪問方

法，拓?fù)浣Y(jié)構(gòu)和物理層技術(shù)規(guī)范。這三種協(xié)議分別是：802.3、802.4和

802.5o

36、考慮在一條1000米長的電纜（無中繼器）,建立一個(gè)IGbps速率的CSMA/CD

網(wǎng)絡(luò)，假定信號在電纜中的速度為2x108米/秒。最小幀長是（）。

A、1250

B、1230

C、1280

D、1220

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

知識點(diǎn)解析：本題考查CSMA/CD協(xié)議的基本原理，這里a代表單程端到端的傳

播延時(shí)，因此2a=2x1000/2x108=10微秒。在IGbps速率下，每位的時(shí)間為1

納秒，所以最小幀長為10/1〃=100UU位=125。字節(jié)，因此答案為A。

37、將一條物理信道按時(shí)間分成若干時(shí)間片輪換地給多個(gè)信號使用，每一時(shí)間片由

復(fù)用的一個(gè)信號占用，這樣可以在一條物理信道上傳輸多個(gè)數(shù)字信號，這就是（）。

A、頻分多路復(fù)用

B、時(shí)分多路復(fù)用

C、空分多路復(fù)用

D、頻分與時(shí)分混合多路復(fù)用

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

知識點(diǎn)解析：木題考查信道復(fù)用的幾種方式，題意指明這種復(fù)用是通過劃分時(shí)間

片，因此是時(shí)分多路復(fù)用，答案為B。［歸納總結(jié)］頻分多路復(fù)用（FDM）將一條物理

線路的總帶寬分割成若干個(gè)較小帶寬的子信道，每個(gè)子信道傳輸一路信號。時(shí)分

多路復(fù)用（TDM）將一條高速物理線路的傳輸時(shí)間劃分成若干相等的時(shí)間片，輪流的

為多路信號使用。統(tǒng)計(jì)TDM：采用動態(tài)分配時(shí)間策略，即有數(shù)據(jù)要傳輸?shù)木€路才

分配時(shí)間片。

38、TCP使用的流量控制協(xié)議是（）。

A、固定大小的滑動窗LI協(xié)議

B、可變大小的滑動窗口協(xié)議

C、后退N幀ARQ協(xié)議

D、選擇重發(fā)ARQ協(xié)議

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

知識點(diǎn)解析：本題考查TCP流量控制，TCP采用滑動窗口機(jī)制來實(shí)現(xiàn)流量控制，

并通過接收端來控制發(fā)送端的窗口大小，因此這是一種大小可變的滑動窗口協(xié)議，

因此答案是B。

39、以下關(guān)于路由器的路由表說法正確的是（）。I.路由表包含目的網(wǎng)絡(luò)和到達(dá)該

目的網(wǎng)絡(luò)的完整路徑U.路由表必須包含子網(wǎng)掩碼山.目的網(wǎng)絡(luò)和到達(dá)該目的網(wǎng)

絡(luò)路徑上的下一個(gè)路由器的IP地址IV.目的網(wǎng)絡(luò)和到達(dá)該目的網(wǎng)絡(luò)路徑上的下一

個(gè)路由器的MAC地址

A、口、in

B、只有m

c、I、m

D、口、m、w

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

知識點(diǎn)解析：本題考查網(wǎng)絡(luò)設(shè)備中路由器的作用結(jié)構(gòu)和工作原理，路由器是網(wǎng)絡(luò)互

連的關(guān)鍵設(shè)備，其任務(wù)是轉(zhuǎn)發(fā)分組。每個(gè)路由器都維護(hù)著一個(gè)路由表以決定分組的

傳輸路徑。當(dāng)目的主機(jī)與源主機(jī)不在同一個(gè)網(wǎng)絡(luò)中，則應(yīng)將數(shù)據(jù)報(bào)發(fā)送給源主機(jī)所

在網(wǎng)絡(luò)上的某個(gè)路由器，由該路由器按照轉(zhuǎn)發(fā)表（由路由表構(gòu)造的）指出的路由將數(shù)

據(jù)報(bào)轉(zhuǎn)發(fā)給下一個(gè)路由器，這種交付方式稱為間接交付。I：為了提高路由器的查

詢效率和減少路由表的內(nèi)容,路由表只保留到達(dá)目的主機(jī)的下一個(gè)路由器的地址.

而不是保留通向目的主孔的傳輸路徑上的所有路由信息，故I錯(cuò)誤。n：路由表

并不一定包含子網(wǎng)掩碼，一般只在劃分了子網(wǎng)的網(wǎng)絡(luò)中，路由器的路由表才使用子

網(wǎng)掩碼，如果不使用就艱本不能得到網(wǎng)絡(luò)號。而沒有劃分子網(wǎng)的網(wǎng)絡(luò)，使用默認(rèn)的

就可以，不需要在路由表上顯示，故n錯(cuò)誤。in：路由器的路由表的表項(xiàng)通常包

含目的網(wǎng)絡(luò)和到達(dá)該目的網(wǎng)絡(luò)的下一個(gè)路由器的IP地址，因?yàn)槁酚善魇枪ぷ髟诰W(wǎng)

絡(luò)層，網(wǎng)絡(luò)層使用的是IP地址，故in正確，iv：路由器是工作在網(wǎng)絡(luò)層的設(shè)備，

對數(shù)據(jù)鏈路層是透明的，故iv錯(cuò)誤。綜上，只有田正確，因此答案是B。

40、FTP客戶和服務(wù)器之問一般需要建立的連接個(gè)數(shù)是（）。

A、1

B、2

C、3

D、4

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

知識點(diǎn)解析：本題考查FTP的基本原理，F(xiàn)TP客戶與服務(wù)器之間一般要建立法個(gè)

連接，一個(gè)是控制連接，一個(gè)是數(shù)據(jù)連接，控制連接在整個(gè)會話期間一直保持打

開，F(xiàn)TP客戶發(fā)出的傳送請求通過控制連接發(fā)送給服務(wù)器端的控制進(jìn)程，但控制連

接不用來傳送文件。實(shí)際用于傳輸文件的是“數(shù)據(jù)連接服務(wù)器端的控制進(jìn)程在接

收至IJFTP客戶發(fā)送來的文件傳輸請求后就創(chuàng)建“數(shù)據(jù)傳送進(jìn)程”和“數(shù)據(jù)連接”，用來

連接客戶端和服務(wù)器端的數(shù)據(jù)傳送進(jìn)程。數(shù)據(jù)傳送進(jìn)程實(shí)際完成文件的傳送，在傳

送完畢后關(guān)閉“數(shù)據(jù)傳送連接''并結(jié)束運(yùn)行。因此答案是B。

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

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

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

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

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

是二義樹根結(jié)點(diǎn)的指針)。if(p!=NuLL){while(p->lchild!=NuLLIIp

->rchild!=NuLL){while(p->lchild!=NULL)p=p->lchild；if(p->rchiid!=

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

知識點(diǎn)解析：本題主要考查后序遍歷過程及特點(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)答案：voidde!alI(LinkList&L){LNode*p,樂pre,*minp,*minpre；while(L

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

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

adata){minp=p；minpre=pre；}pre=p；//p、pre同步后移p=p->next；}

prinlR''%c",minp—>data)；//輸出最小值結(jié)點(diǎn)minpre—>next=minp->next：

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

知識點(diǎn)解析：對于循環(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位)，試問大組中產(chǎn)生的是哪幾位進(jìn)位?與4,4,4,4分組

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

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

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

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

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

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

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

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

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

間都為6ty。

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

輸入為C7,最高位的進(jìn)位輸出為Ci5。［歸納總結(jié)］n位并行加法器按進(jìn)位信號的

傳遞方式，可分為串行進(jìn)位方式、并行進(jìn)位方式和分組并行進(jìn)位方式。串行進(jìn)位方

式的每一級進(jìn)位直接依賴于前一級的進(jìn)位，即進(jìn)位信號是逐級形成的；并行進(jìn)位方

式所有各位的進(jìn)位不依賴于其低位的進(jìn)位，而只依賴于最低位的進(jìn)位C—i，各位的

進(jìn)位是同時(shí)產(chǎn)生的，隨著加法器位數(shù)的增加，完全采用并行進(jìn)位是不現(xiàn)實(shí)的。真

正實(shí)用的進(jìn)位方式是分組先行進(jìn)位方式，分組先行進(jìn)位方式又有單級和多級之分。

單級先行進(jìn)位方式(單重分組)又稱為組內(nèi)并行、組間串行方式。多級先行進(jìn)位方式

(雙重或多重分組)又稱組內(nèi)并行、組間并行方式。［解題技巧］首先要搞清楚單重分

組和雙重分組跳躍進(jìn)位鏈的特點(diǎn)。然后利用雙重分組跳躍進(jìn)位鏈構(gòu)成兩種16位并

行加法器，兩種方式的區(qū)別在于其小組的位數(shù)不同。

［一位*1C30；MM]

1-1

1-1□

44、某機(jī)的主要部件如下圖所示?；鼗?3(1)請補(bǔ)充

各部件間的主要連接線，并注明數(shù)據(jù)流動方向。⑵擬出指令SUB(Ri),—(R2)的

執(zhí)行流程(含取指過程與確定后繼指令地址)。該指令的含義是進(jìn)行減法操作，源操

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

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

器。

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

(R2)-l一R2((R。)一((R2))T(R2)指令的執(zhí)行流程如下：①(Pc)-MAR；取指令

②Read③M(MAR)-MDR-IR④(PC)+1->PC⑤(Ri)-MAR；取被減數(shù)

⑥Read⑦M(jìn)(MAR)TMDR—C⑥住2)一】TR2；修改目的地址⑨(R2)一MAR；

取減數(shù)⑩Read⑩M(MAR)->MDR一D?(C)->(D)->MDR；求差并保存結(jié)果

?Write⑩MDR-MM

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

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

總線結(jié)構(gòu)形式。|歸納總結(jié)］指令執(zhí)行流程中的前4步是完成去主存中取指令的操

作，這是公操作，與具體指令無關(guān)；接下來的3步是去主存中取被減數(shù)，把取出的

被減數(shù)放在暫存器C中；然后的4步是去主存中取減數(shù)，并把取出的減數(shù)放在暫

存器D中，由于目的操作數(shù)尋址方式為自減型寄存器間接尋址，所以先要修改目

的地址；最后的3步是完成減法運(yùn)算，并將結(jié)果保存在主存中。自減尋址是先對

寄存器R。的內(nèi)容自動減量修改，修改之后的內(nèi)容才是操作數(shù)的有效地址，據(jù)此可

到主存中取出操作數(shù)。尋址操作的含義為：Ri—(R。-1,EA=(Ri),通常記作一

(Ri),減號在括號之前，形象地表示先修改后操作。而自增尋址時(shí)，寄存器Ri的內(nèi)

容是有效地址，按照這個(gè)有效地址從主存中取數(shù)以后，寄存器的內(nèi)容自動增量修

改。尋址操作的含義為：EA=(Ri),Ri—(Ri)+1,通常記作(&)+,加號在括號之

后，形象地表示先操作后修改。［解題技巧］根據(jù)數(shù)據(jù)通路，寫出指令執(zhí)行的微操作

序列。使用寄存器傳送語句(如PC—MAR),比較直觀。

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

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

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

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

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

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

者離開后再允許讀者進(jìn)入1臨界區(qū)。這所謂“寫者優(yōu)先讀者一寫者”問題。請用信號

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

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

semaphore；//定義信號量semaphoremutex=1；//讀寫的互斥量semaphore

readers=n；//讀者的資源最voidReaders(viod)//讀者進(jìn)程

{while(TRUE){//調(diào)度P(mutex)；//讀寫互斥P(readers)；//讀者資源量減

一，為負(fù)時(shí)等待V(mulex)；//釋放讀寫互斥read—dala(void)；//讀者讀我數(shù)

據(jù)V(readers)；}//離開時(shí)釋放讀者數(shù)量，加一}Voidwriters(void)//寫者進(jìn)程

(while(TRUE){P(mutex)；//獲取讀寫互斥量for(inti=1；i＜：n；i+

H-)P(readers)；//將許可讀者進(jìn)入的資源量消耗光wrile_dala(VOid)；//寫入

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

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

程序。lypedefintsemaphore；//定義信號量semaphorerwmutex=1；//讀寫

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

nrmutex=l；//寫者等待讀者退出的互斥最intrcaderscount=0；//瀆者i-數(shù)

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

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

數(shù)量加一if(readerscounl=l)P(nrmutex)；//若是第一個(gè)讀者，互斥寫者

V(rcmutex)；//釋放讀者計(jì)數(shù)器互斥量V(rwmutex)；//及時(shí)釋放讀寫互斥

量，允許其它進(jìn)程申請read—data(void)；//讀者讀取數(shù)據(jù)P(rcmutex)；//離

開臨界區(qū)時(shí)讀者計(jì)數(shù)器互斥readerscount-----；//讀者數(shù)量減一if(readerscount=

O)V(nrmutex)；//所有讀者退出臨界區(qū)V(rcmutex)；)//離開時(shí)釋放讀者計(jì)數(shù)

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

讀寫互斥量P(nmiutex)；//若臨界區(qū)有讀者，等待其退出write_data(void)；/

/寫入數(shù)據(jù)V(nrmutex)；//允許后續(xù)第一個(gè)讀者進(jìn)入臨界區(qū)V(rwmutex)；}/

/允許新的讀者和寫者排隊(duì)上述程序不能保證在等待隊(duì)列中寫者更優(yōu)一點(diǎn)，因?yàn)?/p>

上述約束條件只能將讀者無限制地進(jìn)入臨界區(qū)的情況給屏蔽了，而在臨界區(qū)外，讀

者和寫者還是按照先來先服務(wù)的方式排隊(duì)。第三部分給出的方法使得訪問隊(duì)列中

只要有寫者出現(xiàn)，它必然優(yōu)先進(jìn)入臨界區(qū)。typedefintsemaphore；//定義信號

量semaphorerwmutex=1；//讀寫的互斥量semaphoreremutex=1；//訪問讀

者計(jì)數(shù)器的互斥量semaphorewcmutex=h//訪問排隊(duì)寫者計(jì)數(shù)器的互斥量

semaphorenrmutex=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)程申請read

dat|a(void)；//讀者讀取數(shù)據(jù)P(rcmutex);//離開臨界區(qū)時(shí)讀者計(jì)數(shù)器互斥

readerscount-----；//讀者數(shù)量減一if(readerscount==O)V(nnnutex)；//所有

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

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

++;//寫者隊(duì)列加一if(writerscount==l)P(rwmutex)；//第一寫者使用讀

寫互斥量V(wcmutex)；//釋放寫者計(jì)數(shù)互斥量P(nrrout：ex)；//若臨界區(qū)有

讀者，等待其退出write—data(void)；//寫入數(shù)據(jù)v(nrmlatex)；//釋放后續(xù)第

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

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

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

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

rwmutex)o而只有第一個(gè)寫進(jìn)程需要申請nrmulex,之后就一直占著不放了，直到

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

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

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

面，一是讀者訪問臨界區(qū)的最大數(shù)量是有限的，例如說n,