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

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

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

1、在一個(gè)雙向鏈表中，在*p結(jié)點(diǎn)之后插入結(jié)點(diǎn)*q的操作是（）。

A^q->prior=p；p->next=q；p->next—*>prior=q；q->next=p->next；

B、q->ncxt=p->ncxt；p->ncxt->prior=q；p->ncxt=q；q->prior=p；

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

D^p->next->prior=q；q->next=p->next；q->prior=p：p->next=q：

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

知識(shí)點(diǎn)解析：在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背

線性表的邏輯特征。本題主要考查雙向鏈表的插入算法中的指針的變化過(guò)程。雖

然4個(gè)選項(xiàng)中的語(yǔ)句相同，但順序不同，根據(jù)雙向鏈表的結(jié)構(gòu)特點(diǎn)可知選項(xiàng)B的

操作順序是正確的，其他3個(gè)選項(xiàng)的指針修改順序不能完成在*p結(jié)點(diǎn)之后插入結(jié)

點(diǎn)*q的操作”

2、設(shè)線性表中有2n個(gè)元素，以下操作中，在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效

率更高的是（）。

A、刪除指定元素

B、在最后一個(gè)元素的后面插入一個(gè)新元素

C、順序輸出前k個(gè)元素

D^交換第i個(gè)元素和2n—i—1個(gè)元素的值（i=0,1….，n—1）

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

知識(shí)點(diǎn)解析：在順序表中刪除元素需要移動(dòng)較多元素，而在單鏈表上執(zhí)行同樣的操

作不需要移動(dòng)元素。

3、設(shè)數(shù)組S［n］作為兩個(gè)棧S］和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S［n］全滿(mǎn)時(shí)

才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是（）。

A^Si的棧底位置為O,S2的棧底位置為n—1

B、Si的棧底位置為O,S2的棧底位置為n/2

C、Si的棧底位置為O,S2的棧底位置為n

D、Si的棧底位置為0,S2的棧底位置為1

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

知識(shí)點(diǎn)解析：利用棧底位置不變的特性，可讓兩個(gè)順序棧共享一個(gè)一維數(shù)據(jù)空間，

以互補(bǔ)余缺，實(shí)現(xiàn)方法是：將兩個(gè)棧的棧底位置分別設(shè)在存儲(chǔ)空間的兩端，讓它們

的棧頂各自向中間延伸。這樣，兩個(gè)棧的空間就可以相互調(diào)節(jié)，只有在整個(gè)存儲(chǔ)空

間被占滿(mǎn)時(shí)才發(fā)生上溢，這樣一來(lái)產(chǎn)生上溢的概率要小得多。

4、若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和f.ront的值分別為0

和3,當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和Iront的值分別是()。

A1和

、5

B2和

、4

c4和

、

D5和

、

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

知識(shí)點(diǎn)解析：出隊(duì)1個(gè)元素后，front=(front+1)%MAXQSIZE,front的值是4；入

隊(duì)兩個(gè)元素后，rcar=(rcar+2)%MAXQSIZE,rear的值是2。

5、利用逐點(diǎn)插入建立序列(50,72,43,85,75,20,35,45,65,30)對(duì)應(yīng)的二

叉排序樹(shù)以后，要查找元素30要進(jìn)行元素間的比較次數(shù)是()。

A、4

B、5

C、6

D、7

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

知識(shí)點(diǎn)露析：利用逐點(diǎn)而入法建立二叉排序樹(shù)是從空樹(shù)開(kāi)始，通過(guò)查找，將每個(gè)結(jié)

點(diǎn)作為一個(gè)同子插入。項(xiàng)題目中數(shù)據(jù)的輸入次序建立的二叉排序樹(shù)如下圖所示，查

找元素30的比較次數(shù)為5次。

6、將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度

是()。

A、4

B、5

C、6

D、7

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

知識(shí)點(diǎn)解析：將二叉樹(shù)的性質(zhì)4推廣到完全三叉樹(shù)即可得出正確答案。

7、在一個(gè)具有n(n>0)個(gè)頂點(diǎn)的連通無(wú)向圖中，至少需要的邊數(shù)是()。

A、n

B、n+1

C、n—1

D、n/2

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

知識(shí)點(diǎn)解析：在無(wú)向圖中，如果從一個(gè)頂點(diǎn)喝到另一個(gè)頂點(diǎn)Vj(由)有路徑，則稱(chēng)頂

點(diǎn)%和Vj是連通的。如果圖中任意兩頂點(diǎn)都是連通的，則稱(chēng)該圖是連通圖。所以

具有n個(gè)頂點(diǎn)的連通無(wú)向圖至少有n—1條邊。

8、已知一個(gè)線性表(38,25,74,63,52,48),假定采用散列函數(shù)h(key)=key%7

計(jì)算散列地址，并散列存儲(chǔ)在散列表A[0.?6]中，若采用線性探測(cè)方法解決沖

突，則在該散列表上進(jìn)行等概率成功查找的平均查找長(zhǎng)度為()。

A、1.5

B、1.7

C、2

D、2.3

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

知識(shí)點(diǎn)解析：按照散列函數(shù)h(kcy尸key%7和線性探測(cè)方法解決沖突，將線性表

(38,25,74,63,52,48)散列存儲(chǔ)在散列表A[0..6]中，如下圖所示。

位置01234s6

[63|48][38]25I74|521

比較次數(shù)I31124

那么，ASL3=《(1+3+1+1+2+4)=2.0

0

9、有一個(gè)長(zhǎng)度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概

率情況下，查找失敗時(shí)所需的平均比較次數(shù)是()。

A、37/12

B、62/13

C、39/12

D、49/13

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

知識(shí)點(diǎn)解析：這是一個(gè)負(fù)數(shù)，x>—8,意味著0>x>—8。X=—8的補(bǔ)碼表示為

11000,應(yīng)將一8排除在外。

14、在規(guī)格化浮點(diǎn)運(yùn)算中，若某浮點(diǎn)數(shù)為25x1.10101,其中尾數(shù)為補(bǔ)碼表示，則

該數(shù)是（）。

A、不需規(guī)格化

B、需右移規(guī)格化

C、需將尾數(shù)左移一位規(guī)格化

D、需將尾數(shù)左移兩位規(guī)格化

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

知識(shí)點(diǎn)解析：浮點(diǎn)數(shù)25*1.10101的尾數(shù)不是規(guī)格化數(shù)，需要進(jìn)行左規(guī)。

15、漢字“啊”的十進(jìn)制區(qū)位碼為“16-01”，它的十六進(jìn)制機(jī)內(nèi)碼是（）。

A、1601H

B、9081H

C、BOA1H

D、B081H

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

知識(shí)點(diǎn)解析：區(qū)位碼16—01（十進(jìn)制）=1001H,國(guó)標(biāo)碼=1001H+2020H=3021H,機(jī)

內(nèi)碼=3021H+8080H=BOA1H。

16、在一個(gè)按字節(jié)編址的計(jì)算機(jī)中，若數(shù)據(jù)在存儲(chǔ)器中以小端方案存放。假定血

型變量i的地址為08000000H,i的機(jī)器數(shù)為0234567H,地址:08000000H單元

的內(nèi)容是（）。

A、01H

B、23H

C、45H

D、67H

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

知識(shí)點(diǎn)解析：小端方案是將最低有效字節(jié)存儲(chǔ)在最小地址位置。在數(shù)01234567H

中，最低有效字節(jié)為67H。

17、在CPU的狀態(tài)寄存器中，若符號(hào)標(biāo)志為“1”，表示運(yùn)算結(jié)果是（）。

A、正

B、負(fù)

C、零

D、不一定

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

知識(shí)點(diǎn)解析：符號(hào)標(biāo)志位SF=O,表示為正數(shù)，符號(hào)標(biāo)志位SF=1,表示為負(fù)數(shù)。

18、在微程序控制器設(shè)計(jì)中，假設(shè)微命令采用最短編碼法，需產(chǎn)生N種微操作。

A.“ogJN+DIB.N

G.Tlog,N1D.Flog,N1+1

A、

B、

C、

D、

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

知識(shí)點(diǎn)解析：由于微命令控制字段必須是一個(gè)整數(shù)，所以在最短編碼法中為巴

位。

19、下列是有關(guān)馮.諾依曼結(jié)構(gòu)計(jì)算機(jī)中指令和數(shù)據(jù)存放位置的敘述，其中正確的

是（）。

A、指令存放在內(nèi)存中，數(shù)據(jù)存放在外存中

B、指令和數(shù)據(jù)任何時(shí)候都存放在內(nèi)存中

C、指令和數(shù)據(jù)任何時(shí)候都存放在外存中

D、程序被啟動(dòng)前指令和數(shù)據(jù)都存放在外存中，而啟動(dòng)后指令和數(shù)據(jù)被裝入內(nèi)存

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

知識(shí)點(diǎn)解析：計(jì)算機(jī)關(guān)機(jī)狀態(tài)時(shí)、計(jì)算機(jī)中指令和數(shù)據(jù)存放在外存中，但是CPU

不能直接和外存交互信息，因此啟動(dòng)后的指令和數(shù)據(jù)被裝入內(nèi)存。

20、在讀寫(xiě)硬盤(pán)的一個(gè)物理記錄塊時(shí)，不需要的參數(shù)是（）。

A、柱面（磁道）號(hào)

B、盤(pán)片（磁頭）

C、簇號(hào)

D、扇區(qū)號(hào)

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

知識(shí)點(diǎn).析：在讀寫(xiě)硬盤(pán)的一個(gè)物理記錄塊時(shí)，需要的參數(shù)是磁道號(hào)、磁頭號(hào)和扇

區(qū)號(hào)。

21、有效容量為128KB的Cache,每塊16字節(jié)，8路組相聯(lián)。字節(jié)地址為I2345

67H的單元調(diào)入該Cache,其Tag應(yīng)是（）。

A、1234H

B、2468H

C、048DH

D、12345H；

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

知識(shí)點(diǎn)解析：因?yàn)閴K的大小為16字節(jié)，所以塊內(nèi)地址字段為4位；乂因?yàn)镃ache

容量為128KB,八路組相聯(lián)，所以可以分為1024紀(jì)，128KB;（16x8）=1024,對(duì)應(yīng)

的組號(hào)字段10位；剩下為標(biāo)記字段。

1234567H=000l001000110100010101100111,標(biāo)記字段為其中高14位,

0001001000110l=048DH

22、中斷的概念是（）。

A、暫停正在運(yùn)行的程序

B、暫停對(duì)內(nèi)存的訪問(wèn)

C、暫停CPU運(yùn)行

D、I/O設(shè)備的輸入或輸出

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

知識(shí)點(diǎn)解析：程序中斷的實(shí)質(zhì)是程序切換，由現(xiàn)行程序切換到中斷服務(wù)程序，再由

中斷服務(wù)程序返回到現(xiàn)行程序。所以中斷只是暫停正在運(yùn)行的程序，而不會(huì)暫停

CPU的運(yùn)行，也不會(huì)暫停對(duì)內(nèi)存的訪問(wèn)。

23、在操作系統(tǒng)的以下功能中，不需要硬件支持的是（）。

A、中斷系統(tǒng)

B、時(shí)鐘管

C、地址映射

D、頁(yè)面調(diào)度

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

知識(shí)點(diǎn)解析：中斷系統(tǒng)需要硬件的支持是顯而易見(jiàn)的，在中斷過(guò)程中保存和恢復(fù)寄

存器值都需要硬件支持；時(shí)鐘管理需要硬件計(jì)數(shù)器保持時(shí)鐘的運(yùn)行；地址映射中需

要基地址（或頁(yè)表）寄存器和地址加法器的支持；頁(yè)面調(diào)度由相關(guān)調(diào)度算法完成，不

需要硬件支持；注意，頁(yè)面調(diào)度算法僅計(jì)算需要調(diào)入或置換的目標(biāo)頁(yè)面，調(diào)入過(guò)程

（例如缺頁(yè)中斷處理過(guò)程）才是與硬件相關(guān)的。

24、在單處理機(jī)的多進(jìn)程系統(tǒng)中，進(jìn)程什么時(shí)候占用處理機(jī)以及決定占用時(shí)間的長(zhǎng)

短是（）。

A、進(jìn)程相應(yīng)的代碼長(zhǎng)度

B、進(jìn)程總共需要運(yùn)行的時(shí)間

C、進(jìn)程特點(diǎn)和進(jìn)程調(diào)度策略

D、進(jìn)程完成什么功能

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

知識(shí)點(diǎn)解析：本題考查進(jìn)程調(diào)度的時(shí)機(jī)和進(jìn)程調(diào)度的策略。進(jìn)程調(diào)度的時(shí)機(jī)與進(jìn)程

特點(diǎn)有關(guān)，例如進(jìn)程是否是CPU繁忙型還是10繁忙型，自身的優(yōu)先級(jí)等。但是僅

有這些特點(diǎn)是不夠的，能否得到調(diào)度還取決于進(jìn)程調(diào)度策略，若采用優(yōu)先級(jí)調(diào)度算

法，則進(jìn)程的優(yōu)先級(jí)才起作用。至于占用處理機(jī)運(yùn)行時(shí)間的長(zhǎng)短，則要看進(jìn)程自

身，若進(jìn)程是10繁忙型，運(yùn)行過(guò)程中要頻繁訪問(wèn)10,也就是說(shuō)，可能會(huì)頻繁主動(dòng)

放棄CPU,所以，占用CPU的時(shí)間就不會(huì)長(zhǎng)，一旦放棄CPU,則必須等待卜次

調(diào)度。若進(jìn)程是CPU繁忙型，則一旦占有CPU就可能會(huì)運(yùn)行很長(zhǎng)時(shí)間，但是，運(yùn)

行時(shí)間還取決于進(jìn)程調(diào)度策略，大部分情況下，交互式系統(tǒng)為改善用戶(hù)的響應(yīng)時(shí)

間，大多采用時(shí)間片輪轉(zhuǎn)的算法，這種算法在進(jìn)程長(zhǎng)期占用CPU到一定時(shí)間后，

會(huì)強(qiáng)制將其換卜，以保證其它進(jìn)程的CPU使用權(quán)。所以，本題的正確答案應(yīng)為選

項(xiàng)C,其它都不是。

25、系統(tǒng)產(chǎn)生死鎖的可能原因是（）。

A、共享資源分配不當(dāng)

B、系統(tǒng)資源不足

C、進(jìn)程運(yùn)行太快

D、CPU內(nèi)核太多

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

知識(shí)點(diǎn)解析：系統(tǒng)死鎖的可能原因主要是時(shí)間上和空間上的。時(shí)間上由于進(jìn)程運(yùn)行

中推進(jìn)順序不當(dāng)，即調(diào)度時(shí)機(jī)不合適，不該切換進(jìn)程時(shí)進(jìn)行了切換，可能會(huì)造成死

鎖；空間上的原因是對(duì)共享資源分配不當(dāng)，互斥資源部分分配乂不可剝奪，極易造

成死鎖。那么，為什么系統(tǒng)資源不足不是造成死鎖的原因呢?系統(tǒng)資源不足只會(huì)對(duì)

進(jìn)程造成饑餓，例如，某系統(tǒng)只有3臺(tái)打印機(jī)，若進(jìn)程運(yùn)行中要申請(qǐng)4臺(tái)，顯然不

能滿(mǎn)足，該進(jìn)程會(huì)永遠(yuǎn)等待下去。如果該進(jìn)程在創(chuàng)建時(shí)便聲明需要4臺(tái)打印機(jī)，

那么操作系統(tǒng)立即就會(huì)小絕，不會(huì)創(chuàng)建該進(jìn)程的。一般，系統(tǒng)由于部分分配，剩余

資源不足時(shí)，可能會(huì)造成死鎖，這實(shí)際上是資源分配不當(dāng)?shù)囊环N表現(xiàn)。不能以系統(tǒng)

資源不足來(lái)描述剩余資源不足的情形。

26、下列選項(xiàng)中，降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是（），

A、進(jìn)程時(shí)間片用完

B、進(jìn)程剛完成I/O,進(jìn)入就緒隊(duì)列

C、進(jìn)程長(zhǎng)期處于就緒隊(duì)列

D、進(jìn)程從就緒狀態(tài)轉(zhuǎn)換為運(yùn)行狀態(tài)

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

知識(shí)點(diǎn)解析：進(jìn)程時(shí)間片用完可以降低其優(yōu)先級(jí)，完成I/0的進(jìn)程應(yīng)該提升其優(yōu)

先級(jí)，處于就緒隊(duì)列等待調(diào)度的進(jìn)程一般不會(huì)改變其優(yōu)先級(jí)。這類(lèi)題目一般在采

用多級(jí)反饋隊(duì)列調(diào)度算法的系統(tǒng)中應(yīng)用”其具體算法為：設(shè)置多個(gè)就緒隊(duì)列,并為

各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二隊(duì)次之，其余隊(duì)列優(yōu)

先級(jí)依次降低。賦予各個(gè)隊(duì)列中進(jìn)程運(yùn)行時(shí)間片的大小也各不相同。在優(yōu)先級(jí)越高

的隊(duì)列中，每個(gè)進(jìn)程的運(yùn)行時(shí)間片就越小。當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放

入第一隊(duì)列的末尾，也就是優(yōu)先級(jí)最高，按先來(lái)先服務(wù)的原則排隊(duì)等待調(diào)度。當(dāng)輪

到該進(jìn)程運(yùn)行時(shí)，如能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)。如果它在一個(gè)時(shí)間

片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，此時(shí)其優(yōu)先級(jí)降低

了一級(jí)，再同樣地按先來(lái)先服務(wù)原則等待調(diào)度運(yùn)行。如果它在第二隊(duì)列中運(yùn)行一個(gè)

時(shí)間片后仍未完成，再以同樣方法，將它轉(zhuǎn)入第三隊(duì)列。它的優(yōu)先級(jí)又降低了一

級(jí)。如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)從第一隊(duì)列降到最后一個(gè)隊(duì)列后，在最后一個(gè)隊(duì)列

中，使用時(shí)間片輪轉(zhuǎn)方式運(yùn)行。此時(shí)優(yōu)先級(jí)也就再也無(wú)法降低了。僅當(dāng)?shù)谝魂?duì)列空

閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行。僅當(dāng)?shù)谝恢罭隊(duì)列均為空時(shí)，才

會(huì)調(diào)度第N+1隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第J隊(duì)列中為某進(jìn)程服務(wù)時(shí)，

又有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列，那么要考慮是否是可搶先式調(diào)度算法，若是，

則新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，而由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第

J隊(duì)列，將處理機(jī)分配給新進(jìn)程。若不是，則需要等待直到當(dāng)前的進(jìn)程完成它的時(shí)

間片再調(diào)度，此時(shí)會(huì)產(chǎn)生優(yōu)先級(jí)翻轉(zhuǎn)的情形，亦即在處理機(jī)上運(yùn)行的進(jìn)程其優(yōu)先級(jí)

低于就緒隊(duì)列中的某個(gè)進(jìn)程。這種情形非常糟糕，極易引起死鎖。一般應(yīng)該避免。

27、在某計(jì)算機(jī)中采用了多級(jí)存儲(chǔ)體系，設(shè)計(jì)有cache,主存和磁盤(pán)，假設(shè)訪問(wèn)

cache一個(gè)字需要花費(fèi)10ns,若該字不在cachep但是存在在主存中，那么需要

100ns載2kcache,然后重新開(kāi)始定位。若該字既不在cache中，也不在主存中，

那么需要10ms的時(shí)間裝入主存，再化100ns復(fù)制到cache,再開(kāi)始定位。設(shè)cache

的命中率為0.90,主存的命中率為0.75,那么，該系統(tǒng)訪問(wèn)一個(gè)字的平均時(shí)間

是()。

A、25000ns

B、250023ns

C、250017ns

D、250020ns

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

知識(shí)點(diǎn)解析：本題考查多級(jí)存儲(chǔ)層次下的平均訪問(wèn)時(shí)間。多級(jí)存儲(chǔ)是現(xiàn)代計(jì)算機(jī)為

了獲得比較優(yōu)異的存儲(chǔ)器訪問(wèn)性能又比較廉價(jià)的一種實(shí)現(xiàn)方法。正確的計(jì)算需要搞

清楚CPU訪問(wèn)一個(gè)字的流程。通常，若需要執(zhí)行的指令字已經(jīng)載入到cache中，

那么，僅需要從cache中取出放到指令隊(duì)列上即可，所花費(fèi)的時(shí)間即是cache的訪

問(wèn)時(shí)間。當(dāng)cache中缺席時(shí)，產(chǎn)生中斷，調(diào)用cache更新程序，將所需的指令字載

入cache,然后返回到中斷點(diǎn)繼續(xù)定位，所需的時(shí)間是訪問(wèn)cache的時(shí)間和中斷服

務(wù)程序所花費(fèi)的時(shí)間之和。同理，可以推斷出訪問(wèn)不在主存中的指令字所需花費(fèi)的

時(shí)間是磁盤(pán)裝入時(shí)間與內(nèi)存中斷服務(wù)程序時(shí)間以及cache訪問(wèn)時(shí)間的和。根據(jù)各自

命中率的不同，可以計(jì)算出總時(shí)間為：10x0.9+(104-110)x(1-0.9)X0.75+

(10+100+10000000)x(1-0.9)x(1-0.75)=250020ns

28、在一個(gè)采用請(qǐng)求式調(diào)頁(yè)的虛擬存儲(chǔ)系統(tǒng)中，存放在外存上的程序代碼調(diào)入內(nèi)存

的時(shí)機(jī)是()。

A、在進(jìn)程創(chuàng)建填寫(xiě)進(jìn)程表時(shí)

B、在進(jìn)程創(chuàng)建分配內(nèi)存時(shí)

C、在進(jìn)程被調(diào)度占用處理機(jī)執(zhí)行時(shí)

D、在每次產(chǎn)生缺頁(yè)中斷時(shí)

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

知識(shí)點(diǎn)解析：本題考查虛擬存儲(chǔ)系統(tǒng)中程序調(diào)入內(nèi)存的時(shí)刻。在一個(gè)采用請(qǐng)求式調(diào)

頁(yè)的虛擬存儲(chǔ)系統(tǒng)中，當(dāng)一個(gè)程序需要執(zhí)行時(shí)，首先由進(jìn)程創(chuàng)建模塊為新進(jìn)程找到

一張空白的進(jìn)程表，將咳進(jìn)程的基本信息填入這張表，例如進(jìn)程號(hào)，父進(jìn)程，進(jìn)程

組，優(yōu)先級(jí)，狀態(tài)字等，然后分配該進(jìn)程虛擬內(nèi)存空間(此時(shí)不做任何實(shí)際的分

配)，打開(kāi)文件獲得句柄，鏈接到用戶(hù)活動(dòng)文件數(shù)據(jù)表中，分配設(shè)備等，做完這些

工作，進(jìn)程表將被放入就緒隊(duì)列(假設(shè)所有資源均匕用，只等CPU調(diào)度)，等待操

作系統(tǒng)的調(diào)度模塊調(diào)度。調(diào)度模塊按照規(guī)定的調(diào)度算法，從就緒隊(duì)列中選擇一個(gè)進(jìn)

程(對(duì)于單核處理機(jī))，將運(yùn)行狀態(tài)賦予該進(jìn)程，然后切換CPU,使得CPU的程序

計(jì)數(shù)器指向該進(jìn)程起首執(zhí)行處，開(kāi)始運(yùn)行。通常，新創(chuàng)建的進(jìn)程是僅有虛擬地址空

間的，所以，當(dāng)?shù)谝淮螆?zhí)行該進(jìn)程時(shí)，代碼不在物理內(nèi)存，于是產(chǎn)生一次缺頁(yè)中

斷。缺頁(yè)中斷機(jī)構(gòu)把對(duì)應(yīng)的頁(yè)面從外存調(diào)入內(nèi)存，返回到中斷點(diǎn)繼續(xù)運(yùn)行。對(duì)于請(qǐng)

求式調(diào)頁(yè)，每次產(chǎn)生缺頁(yè)中斷一般僅調(diào)入相關(guān)的一頁(yè)，若運(yùn)行過(guò)程中所需的頁(yè)面不

在內(nèi)存，那么隨時(shí)可以產(chǎn)生缺頁(yè)中斷，調(diào)入內(nèi)存。若在進(jìn)程運(yùn)行過(guò)程中，所需的頁(yè)

面己經(jīng)在內(nèi)存了，那么就不需要再將代碼調(diào)入內(nèi)存。因此，真正將程序代碼和數(shù)據(jù)

調(diào)入內(nèi)存的是缺頁(yè)中斷處理過(guò)程，其它過(guò)程不會(huì)對(duì)內(nèi)外存的活動(dòng)進(jìn)行操作。

29、為了防止各種意外可能破壞文件，文件系統(tǒng)保護(hù)文件的方法可以是()。

A、為文件加密

B、對(duì)每個(gè)文件規(guī)定使用權(quán)限

C、建立副本和定時(shí)轉(zhuǎn)儲(chǔ)

D、為文件設(shè)置口令

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

知識(shí)點(diǎn)解析：本題主要考查文件保護(hù)、防止系統(tǒng)故障或人為誤操作造成的破壞。文

件的保護(hù)是防止文件被破壞，造成文件可能被破壞的原因有時(shí)是硬件故隙、軟件失

誤引起的，有時(shí)是由于共享文件時(shí)引起的錯(cuò)誤，應(yīng)根據(jù)不同的情況，采用不用的保

護(hù)措施。為了防止各種意外可能破壞文件，文件系統(tǒng)可以采用建立副本和定時(shí)轉(zhuǎn)儲(chǔ)

的方法，來(lái)保護(hù)文件。建立副本是指把同一個(gè)文件存放到多個(gè)存儲(chǔ)介質(zhì)上，當(dāng)某個(gè)

存儲(chǔ)介質(zhì)上的文件被破壞時(shí)，可用其他存儲(chǔ)介質(zhì)U勺備用副本來(lái)替換。這種方法簡(jiǎn)

單，但系統(tǒng)開(kāi)銷(xiāo)增大，且當(dāng)文件更新時(shí)必須改動(dòng)所有的副本，也增加了系統(tǒng)的負(fù)

擔(dān)。因此，這種方法適用于容量較小且極為重要的文件。另一種保護(hù)方法是定時(shí)轉(zhuǎn)

儲(chǔ)，即定時(shí)地把文件轉(zhuǎn)儲(chǔ)到其他的存儲(chǔ)介質(zhì)上。當(dāng)文件發(fā)生故障時(shí)，就用轉(zhuǎn)儲(chǔ)的文

件來(lái)復(fù)原，把有故障的文件恢復(fù)到某一時(shí)刻的狀態(tài)，僅丟失了自上次轉(zhuǎn)儲(chǔ)以來(lái)新修

改或增加的信息。UNIX系統(tǒng)就采用定時(shí)轉(zhuǎn)儲(chǔ)來(lái)保護(hù)文件，提高文件的可靠性。正

確答案為C。

30、已知某磁盤(pán)的平均轉(zhuǎn)速為r秒/轉(zhuǎn)，平均尋道時(shí)間為T(mén)秒，每個(gè)磁道可以存儲(chǔ)

的字節(jié)數(shù)為N.現(xiàn)向該磁盤(pán)讀寫(xiě)h字節(jié)的數(shù)據(jù).采用隨機(jī)尋道的方法.每道的所有

扇區(qū)組成一個(gè)簇，請(qǐng)問(wèn)；平均訪問(wèn)時(shí)間是()。

A、b/N*(r+T)

B、b/N*T

C、(b/Nq+T)*r

D、b*T/N+r

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

知識(shí)點(diǎn)解析：本題考查磁盤(pán)結(jié)構(gòu)和磁盤(pán)讀寫(xiě)的概念。磁盤(pán)是旋轉(zhuǎn)盤(pán)式存儲(chǔ)設(shè)備，每

個(gè)盤(pán)面劃分有若干存儲(chǔ)信息的同心圓稱(chēng)為磁道，每個(gè)磁道又劃分成多個(gè)扇區(qū)。本題

中，將每道的所有扇區(qū)組成一個(gè)簇，意味著可以將一個(gè)磁道的所有存儲(chǔ)空間組織成

一個(gè)數(shù)據(jù)塊組，這樣有利于提高存儲(chǔ)速度。讀寫(xiě)磁盤(pán)時(shí)，磁頭首先要找到磁道，稱(chēng)

為尋道，然后才可以將信息從磁道里讀出來(lái)或?qū)戇M(jìn)去。讀寫(xiě)完一個(gè)磁道以后磁頭會(huì)

繼續(xù)尋找下一個(gè)磁道，完成剩余的工作，所以，在隨機(jī)尋道的情況下，讀寫(xiě)一個(gè)磁

道的時(shí)間要包含尋道時(shí)間和讀寫(xiě)磁道時(shí)間，即T+r秒。由于總的數(shù)據(jù)量是b字節(jié)，

它要占用的磁道數(shù)為b/N個(gè)，所以總的平均讀寫(xiě)時(shí)間為b/N*(T+r)秒。如果不采

用隨機(jī)尋道，而是采用連續(xù)讀寫(xiě)的方式，那么磁盤(pán)的存儲(chǔ)方式是這樣的，首先也是

尋道，找到一組連續(xù)的磁道（用于連續(xù)讀或?qū)?，?xiě)入的話磁道總?cè)萘勘囟ù笥谝獙?xiě)

入的信息總數(shù)），花費(fèi)時(shí)間T秒，然后再花費(fèi)r秒將N個(gè)字節(jié)的信息寫(xiě)入（或讀

出），然后磁頭移動(dòng)到下一道（此時(shí)，這個(gè)磁道與上一個(gè)磁道是緊緊挨著的，幾乎可

以不花費(fèi)時(shí)間），繼續(xù)寫(xiě)入（或讀出）N字節(jié)，循環(huán)往復(fù)，直到全部信息寫(xiě)入（或讀出）

完成。這樣的話，總時(shí)間可以縮短為b/N*r+T。因?yàn)槠洳恍枰看味既さ?，?/p>

需一次尋道即可。所以，考生要注意題目的條件，找出符合題意的正確答案。

31、文件系統(tǒng)中，當(dāng)調(diào)用open。去打開(kāi)一個(gè)文件時(shí)，其主要目的是（）。

A、把文件內(nèi)容從外存調(diào)入內(nèi)存

B、把文件的控制信息從外存調(diào)入內(nèi)存

C、把文件系統(tǒng)的文件分配表調(diào)入內(nèi)存

D、把文件系統(tǒng)的目錄調(diào)入內(nèi)存

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

知識(shí)點(diǎn)解析：本題考查對(duì)文件控制塊（FCB）的理解。文件控制塊是控制一個(gè)文件讀

寫(xiě)和管理文件的基本數(shù)據(jù)結(jié)構(gòu)，當(dāng)進(jìn)程需要使用某個(gè)文件時(shí)，就會(huì)調(diào)用。pen（）來(lái)打

開(kāi)文件，該調(diào)用將文件的文件控制塊從外存調(diào)入內(nèi)存，存放在進(jìn)程表中的用戶(hù)活動(dòng)

文件表中，并在系統(tǒng)活動(dòng)文件表中記錄該文件的打開(kāi)次數(shù)，若是共享文件，還需要

將其鏈接的用戶(hù)數(shù)加一。由于在進(jìn)程表中存放有該文件的控制塊，用戶(hù)進(jìn)程才能在

調(diào)用read（）時(shí)找到該文件的位置并對(duì)文件的內(nèi)容進(jìn)行存取。而文件系統(tǒng)的信息，例

如文件系統(tǒng)的控制信息，文件系統(tǒng)的文件分配表等是在掛載一個(gè)文件系統(tǒng)時(shí)就讀入

內(nèi)存的，掛載文件系統(tǒng)可以是一個(gè)磁盤(pán)分區(qū)，也可以是一個(gè)文件目錄。

32、在下列事件中，哪個(gè)不是設(shè)備分配中應(yīng)該考慮的問(wèn)題（）。

A、及時(shí)性

B、設(shè)備的固有屬性

C、設(shè)備的無(wú)關(guān)性

D、安全性

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

知識(shí)點(diǎn)解析：本題考查設(shè)備分配的概念。設(shè)備分配的原則是：根據(jù)設(shè)備的固有屬性

（獨(dú)占、共享還是虛擬）、用戶(hù)的需求和系統(tǒng)的配置、使用情況，考慮既要充分發(fā)揮

設(shè)備的使用效率，又應(yīng)咳避免由于不合理的分配方式造成進(jìn)程死鎖（即設(shè)備必須處

于安全狀態(tài)）；同時(shí)，要將用戶(hù)程序所申請(qǐng)使用的設(shè)備與具體的物理設(shè)備映射起來(lái)

（即讓用戶(hù)使用邏輯設(shè)備，分配程序?qū)⑦壿嬙O(shè)備映射到物理設(shè)備后，再根據(jù)要求的

物理設(shè)備號(hào)進(jìn)行分配），保證設(shè)備分配和使用。因此及時(shí)性在設(shè)備分配中并沒(méi)有考

慮。

33、OSI模型中完成路徑選擇功能的層次是（）。

A、物理層

B、數(shù)據(jù)鏈路層

C、網(wǎng)絡(luò)層

D、傳輸層

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

知識(shí)點(diǎn)露析：本題考查OSI模型中各個(gè)層次功能，完成路徑選擇，也就是路由功

能的是網(wǎng)絡(luò)層，答案是C。

34、現(xiàn)采用調(diào)相與調(diào)幅相結(jié)合的調(diào)制方式，載波有四種相位變化和兩種振幅變化，

調(diào)制速率是600波特，那么數(shù)據(jù)速率是()。

A、1200bps

B、1800bps

C、2400bps

D、3600bps

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

知識(shí)點(diǎn)。析：本題考查奈奎斯特定理的應(yīng)用，這里載波有四種相位變化和兩種振幅

變化，也就是離散值為8,有公式可得到2x600xk)g28=3600bps,因此答案是D。

35、在CSMA/CD協(xié)議中，下列指標(biāo)與沖突時(shí)間沒(méi)有關(guān)系的是()。

A、檢測(cè)一次沖突所需的最長(zhǎng)時(shí)間

B、最小幀長(zhǎng)度

C、最大幀長(zhǎng)度

D、最大幀碎片長(zhǎng)度

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

知識(shí)點(diǎn)解析：本題考查CSMA/CD協(xié)議中沖突時(shí)間，CSMA/CD屬于競(jìng)爭(zhēng)型協(xié)

議，某站點(diǎn)發(fā)送的MAC幀可能會(huì)沖突。問(wèn)題是一旦發(fā)生沖突，該站點(diǎn)必須知道是

自己發(fā)送的幀造成的沖突，以便重發(fā)該幀；即在本幀未發(fā)送完畢之前檢測(cè)到?jīng)_突信

號(hào)。因此每幀的服務(wù)時(shí)間必須不小于信號(hào)的往返傳播延遲Ts>2l,如果設(shè)MAC幀

為L(zhǎng),信道的速率為C(bps),總線長(zhǎng)度為S,信號(hào)傳播速度為V,中繼器產(chǎn)生的延

遲為M則L/C>2(s/v+tr)。沖突時(shí)間就是能夠進(jìn)行沖突檢測(cè)的最長(zhǎng)時(shí)間，其決

定了最小幀的長(zhǎng)度和最大幀碎片的長(zhǎng)度，對(duì)最大幀的長(zhǎng)度沒(méi)有影響，因此答案是

Co

36、CSMA/CD以太網(wǎng)中，發(fā)生沖突后，重發(fā)前的退避時(shí)間最大是()。

A、65536個(gè)時(shí)間片

B、65535個(gè)時(shí)間片

C、1024個(gè)時(shí)間片

D、1023個(gè)時(shí)間片

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

知識(shí)點(diǎn)解析：考查CSMA/CD的退避算法，這里的時(shí)間片就是基本退避時(shí)間，確

定基本退避時(shí)間，一般是取為爭(zhēng)用期2r。定義重傳次數(shù)k,k<10,即1<=1^11［重傳

次數(shù)，10］從整數(shù)集合［0,1,……，(2k(l)］中隨機(jī)地取出一個(gè)數(shù)，記為r。重傳所

需的時(shí)延就是r倍的基本退避時(shí)間。當(dāng)重傳達(dá)16次仍不能成功時(shí)即丟棄該幀，并

向高層報(bào)告。本題中重芍次數(shù)的最大值為10,退避時(shí)間最大就是21°一1=1023個(gè)

時(shí)間片，因此答案是D。

37、IEEE802.11采用了CSMA/CA協(xié)議，下面關(guān)于這個(gè)協(xié)議的描述中錯(cuò)誤的是

（）。

A、各個(gè)發(fā)送站在兩次幀間隔（IFS）之間進(jìn)行競(jìng)爭(zhēng)發(fā)送

B、每一個(gè)發(fā)送站維持一個(gè)后退計(jì)數(shù)器并監(jiān)聽(tīng)網(wǎng)絡(luò)上的通信

C、各個(gè)發(fā)送站按業(yè)務(wù)的優(yōu)先級(jí)獲得不同的發(fā)送機(jī)會(huì)

D、CSMA/CA協(xié)議適用于突發(fā)性業(yè)務(wù)

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

知識(shí)點(diǎn)解析：本題考查CSMA/CA協(xié)議的工作原理，IEEE802.11標(biāo)準(zhǔn)定義了兩

種操作模式，第一種模式是DCF（分布式協(xié)調(diào)功能），該模式?jīng)]有中心控制設(shè)備，所

有站點(diǎn)都在競(jìng)爭(zhēng)信道；另一種模式是PCF（點(diǎn)協(xié)調(diào)功能），該模式有基站，作為中心

控制設(shè)備通過(guò)輪詢(xún)機(jī)制控制決定各個(gè)站點(diǎn)的傳輸順序。根據(jù)IEEE802.11標(biāo)準(zhǔn)，

DCF、是必須的而PCF是可選的。CSMA/CA協(xié)灰應(yīng)用于DCF、下，目的在于

解決在允許競(jìng)爭(zhēng)的情況下信道如何分配的問(wèn)題。它支持的操作方式有兩種：第一種

操作方式采用延時(shí)算法進(jìn)行訪問(wèn)控制。當(dāng)一個(gè)要發(fā)送數(shù)據(jù)的站點(diǎn)檢測(cè)到信道空閑

時(shí)，站點(diǎn)需繼續(xù)監(jiān)聽(tīng)與IFS（interframcspace,幀間間隔）相等的一段時(shí)間，若此時(shí)信

道依然空閑，站點(diǎn)就可以發(fā)送幀；如果檢測(cè)到信道正忙，則發(fā)送站點(diǎn)推遲到信道空

閑時(shí)再發(fā)送數(shù)據(jù)。若沖突發(fā)生，則發(fā)生沖突的站點(diǎn)按照截?cái)喽M(jìn)制指數(shù)退避算法延

遲一段時(shí)間后，再試著重新發(fā)送數(shù)據(jù)。另一種操作方式類(lèi)似于發(fā)收雙方的握手過(guò)

程。它是基于MACAW（MultipieAccesswithCollisionAvoidanceforWireless,帶沖

突避免的無(wú)線多路訪問(wèn)），采用虛擬信道監(jiān)聽(tīng)的方法。CSMA/CA協(xié)議利用IFS機(jī)

制讓PCF和DCF共存在同一個(gè)通信單元內(nèi)。因此答案是Co

38、局域網(wǎng)交換機(jī)首先完整地接收數(shù)據(jù)幀，并進(jìn)行差錯(cuò)檢測(cè)。如果正確，則根據(jù)幀

目的，則根據(jù)目的地址確定輸出端口號(hào)再轉(zhuǎn)發(fā)出去。這種交換方式是（）。

A、直接交換

B、改進(jìn)直接交換

C、存儲(chǔ)轉(zhuǎn)發(fā)交換

D、查詢(xún)交換

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

知識(shí)點(diǎn)解析：本題考查交換機(jī)的三種交換方式，直接交換在輸入端口檢測(cè)到數(shù)據(jù)幀

時(shí)，檢查幀頭地址，把數(shù)據(jù)幀直通到相應(yīng)的端口，實(shí)現(xiàn)交換功能。存儲(chǔ)轉(zhuǎn)發(fā)交換把

輸入端口的數(shù)據(jù)幀先存儲(chǔ)起來(lái)，然后進(jìn)行CRC（循環(huán)冗余碼校驗(yàn)）檢查，在對(duì)錯(cuò)誤包

處理后才取出數(shù)據(jù)幀的目的地址，通過(guò)查找表轉(zhuǎn)換成輸出端口送出幀。碎片隔離交

換檢查數(shù)據(jù)包的長(zhǎng)度是否夠64個(gè)字節(jié)，如果小于64字節(jié)，說(shuō)明是假包，則丟棄該

包；如果大于64字節(jié)，則發(fā)送該包。因此答案是C。

39、在TCP協(xié)議中，建立連接時(shí)被置為1的標(biāo)志位和所處的字段是（）。

A、保留，ACK

B、保留，SYN

C、偏移，ACK

D、控制，SYN

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

知識(shí)點(diǎn)解析：本題考查T(mén)CP連接的過(guò)程，首先服務(wù)器方（接收方）始終監(jiān)聽(tīng)特定的端

口，被動(dòng)的等待客戶(hù)方發(fā)來(lái)的連接請(qǐng)求。客戶(hù)方發(fā)出連接請(qǐng)求數(shù)據(jù)段，即

SYN=1,ACK=O的數(shù)據(jù)段，其中指明想要連接的IP地址和端口號(hào)，設(shè)置TCP數(shù)

據(jù)段最大值等。該數(shù)據(jù)段到達(dá)目的端后，服務(wù)器方的TCP實(shí)體檢查是否又有進(jìn)程

在監(jiān)聽(tīng)目的端口字段指定的端口，如果沒(méi)有，則返回一個(gè)RST=1的數(shù)據(jù)段作為應(yīng)

答，拒絕該連接請(qǐng)求。如果某進(jìn)程正在對(duì)該端口進(jìn)行監(jiān)聽(tīng)，于是將到達(dá)的TCP數(shù)

據(jù)段交給該進(jìn)程。它可以接受或拒絕建立連接。如果接受，則返回一個(gè)確認(rèn)數(shù)據(jù)

段（SYN=1和ACK=1）?？蛻?hù)方發(fā)送（SYN=1,ACK=1）TCP數(shù)據(jù)段。此時(shí)，連接建

立完畢。因此在建立連接的時(shí)候，必須把控制字段中的SYN位設(shè)置為1,答案為

Do

40、下列協(xié)議中，用于解決電子郵件中傳輸多語(yǔ)言文字和附件問(wèn)題的協(xié)議是（）。

A、MIME

B、SMTP

C、SNMP

D、POP3

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

知識(shí)點(diǎn)解析：本題考查郵件協(xié)議中MIME的作用，MIME設(shè)計(jì)的最初目的就是為

了在發(fā)送電子郵件時(shí)附加多媒體數(shù)據(jù)，LL郵件客戶(hù)程序能根據(jù)其類(lèi)型進(jìn)行處理，囚

此定義了5個(gè)新的郵件首部字段，它們可包含在［RFC822|首部中。這些字段提供

了有關(guān)郵件主體的信息。定義了許多郵件內(nèi)容的格式，對(duì)多媒體電子郵件的表示方

法進(jìn)行了標(biāo)準(zhǔn)化。定義了傳送編碼，可對(duì)任何內(nèi)容格式進(jìn)行轉(zhuǎn)換，而不會(huì)被郵件系

統(tǒng)改變。因此答案為A。

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

41、對(duì)于下圖G,按下列條件試分別寫(xiě)出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的

頂點(diǎn)序列和按廣度優(yōu)先嗖索遍歷得到的頂點(diǎn)序列。（1）假定它們均采用鄰接矩陣表

示；（2）假定它們均采年鄰接表表示，并且假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)

序號(hào)從大到小的次序鏈接的。

標(biāo)準(zhǔn)答案：（1）采用鄰接矩陣表示得到的頂點(diǎn)序列如下表所示:

圖S?度優(yōu)先序列廣度優(yōu)先序網(wǎng)

01283456790142738659

⑵采用鄰接表表示

得到的頂點(diǎn)序列如下表所示:

圖深度優(yōu)先序列廣度優(yōu)先序列

G04389567120413728695

知識(shí)點(diǎn)解析：導(dǎo)致對(duì)一個(gè)圖進(jìn)行遍歷而得到的遍歷序列不唯一的因素有許多。首

先，遍歷的出發(fā)頂點(diǎn)的選擇不唯一，而得到的遍歷序列顯然也不是唯一的。即使遍

歷的出發(fā)頂點(diǎn)相同，采用的遍歷方法若不相同，得到的結(jié)果也是不相同的。另外，

即使遍歷的出發(fā)頂點(diǎn)相同，并且采用同一種遍歷方法，若圖的存儲(chǔ)結(jié)構(gòu)不相同，則

得到的結(jié)果也可能是不相同的。例如，對(duì)于鄰接表結(jié)構(gòu)而言，建立鄰接表時(shí)提供邊

的信息的先后次序不同，邊結(jié)點(diǎn)的鏈接次序也不同，從而會(huì)建立不同的鄰接表；同

一個(gè)圖的不同鄰接表結(jié)溝會(huì)導(dǎo)致不同的遍歷結(jié)果。本題中導(dǎo)致對(duì)一個(gè)圖進(jìn)行遍歷

而得到的遍歷序列不唯一的因素都確定下來(lái)，那么遍歷序列就唯一確定下來(lái)。本

題需要先建立圖G的鄰接矩陣和按頂點(diǎn)序號(hào)從大到小的次序鏈接的鄰接表，然后

再進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷。

42、一棵二叉樹(shù)的繁茂度定義為R層結(jié)點(diǎn)數(shù)的最大值與樹(shù)的高度的乘積。編寫(xiě)一

個(gè)算法求二叉樹(shù)的繁茂度。

標(biāo)準(zhǔn)答案：lypedefstructBiTNode{TElemTypedata：structBiTNode*lchiId；

*rchild；//左、右孩子指針}BiTNode,*Bifree；typedetstruct)Bil'Node

node；intlayer；[BTNRecord；//包含結(jié)點(diǎn)所在層次的記錄類(lèi)型int

FanMao(BitreeT){intcount|MAX]；//count數(shù)組存放每一層的結(jié)點(diǎn)數(shù)

InitQueue(Q)；//Q的元素為BTNRecord類(lèi)型EnQueue(Q,{T,0()；

while(!QueueEmpty(Q)){//利用層序遍歷來(lái)統(tǒng)計(jì)各層的結(jié)點(diǎn)數(shù)DcQucuc(Q,r)；

count[r.Iayer]++：if(r.node一>ichild)EnQueue(Q,{r.node一>ichild,

r.layer+1))；if(r.node一>rchild)EnQueue(Q,{r.node->rchild,

r.layer+1))；)h=r.layer；//最后一個(gè)隊(duì)列元素所在層就是樹(shù)的高度

for(maxn=counl[0],i=l：count[i]；i++)if(count[i]>maxn)maxn=count[i]；//求層

最大結(jié)點(diǎn)數(shù)returnh>:,maxn；)

知識(shí)點(diǎn)解析：要用層次遍歷以及隊(duì)列來(lái)處理，可增設(shè)一個(gè)寬度計(jì)數(shù)器，在統(tǒng)計(jì)完每

一層的結(jié)點(diǎn)個(gè)數(shù)之后，再?gòu)挠?jì)數(shù)器中挑出最大值。

43、(11分)某圖形顯示器的分辨率為640x480,刷新頻率為50Hz,且假定水平回

掃期和垂直回掃期各占水平掃描周期和垂直掃描周期的20%,試計(jì)算圖形顯示器

的行頻、水平掃描周期、每個(gè)像素的讀出時(shí)間和視頻帶寬。若分辨率提高到

1024x768,刷新頻率提高到60Hz,再次計(jì)算圖形顯示器的行頻、水平掃描周期、

每個(gè)像素的讀出時(shí)間和視頻帶寬。

標(biāo)準(zhǔn)答案：對(duì)于640x480分辨率，行頻為：4S0X50H7：X0%=30kH7,水平掃描周

期為：l+30kHzN33ps,每一像素的讀出時(shí)間為：3311sx80%+640%2ns,視頻帶寬

為：640x30kHz-80%=24MHz<>對(duì)于1024x768分辨率，行頻為：

768x60Hz^80%=57.6kHz,水平掃描周期為：L57.6kHz=17.4ps,每一像素的

讀出時(shí)間為：17.4gx80%+1024句3.6ns,視頻帶寬為：1024x57.6kHz：80%

=73.73MHzo

知識(shí)點(diǎn)解析：要考慮回掃時(shí)間對(duì)掃描周期的影響。視頻帶寬也可以由每一像素的讀

出時(shí)間的倒數(shù)求得，稍有一些誤差。

44、一臺(tái)模型機(jī)共有7條指令，主頻25MHz,各指令的使用頻率與CPI如下表所

示，該機(jī)有8位和16位兩種指令字長(zhǎng)，采用2一擴(kuò)展操作碼。8位字長(zhǎng)指令為寄

存器一寄存器（R—R）二地址類(lèi)型，I6位字長(zhǎng)指令為寄存器?存儲(chǔ)器（R—M）二地址

變址類(lèi)型（地址碼范圍在一128?127之間）。（1）計(jì)算該機(jī)的MIPS速率。（2）計(jì)算操

作碼的平均碼長(zhǎng)。（3）設(shè)計(jì)該機(jī)的兩種指令格式，標(biāo)出各字段位數(shù)并給出操作碼編

碼。（4）該機(jī)允許使用多少個(gè)可編址的通用寄存器，多少個(gè)變址寄存器？（5）如何計(jì)

指令字長(zhǎng)使用■率執(zhí)行一條瘠。的nwietcpi

11(8位)33%1

12(8ft)2SK2

13(8(ft)2OK2

14(1610%2

15(16值)ss1

16(16(2)3%2

17(1?位)2K2

算存儲(chǔ)器有效地址？

標(biāo)準(zhǔn)答案：（1）根據(jù)各條指令的CPL求出平均CPI。平均

CPI=0.35x1+0.25x2+0.20x2+0.10x2+0.05x1+0.03x2+0.01x2—1.6速率

二主頻/平均CPI=25MHz/1.6=15.6MIPS(2)操作碼的平均長(zhǎng)度

=2x(0.35+0.25+0.2)+4x(0.10+0.05+0.03+0.02)—2.4位(3)該機(jī)的指令

R-R型

格式如下圖所示。R-M?

的操作碼分別為11：0012：0113：1014：110015：110116：111017：1111（4）

根據(jù)指令格式，8位R—R型指令，操作碼占2位，兩個(gè)通用寄存器編號(hào)字段各占

3位，允許8個(gè)通用寄存器。16位R—M型指令，操作碼占4位，地址碼字段占8

位，一個(gè)通用寄存器編號(hào)字段占3位，變址寄存器編號(hào)僅1位，允許2個(gè)變址寄存

器。（5）存儲(chǔ)器有效地址EA=（X）+A,有效地址的位數(shù)取決于變址寄存器的長(zhǎng)度。

知識(shí)點(diǎn)解析：該模型機(jī)采用2—4擴(kuò)展操作碼，即操作碼分為2位和4位兩種，其

中8位字長(zhǎng)的R—R型指令采用短碼，16位字長(zhǎng)的R—M型指令采用長(zhǎng)碼。

45、假設(shè)有8個(gè)記錄A、B,C、D、E、F、G、H存放在磁盤(pán)里，每個(gè)磁道有8個(gè)

扇區(qū)，正好可以存放8個(gè)記錄。假設(shè)磁盤(pán)旋轉(zhuǎn)速度為20ms/r,處理程序每讀出一

個(gè)記錄后，用2ms的時(shí)間進(jìn)行處理，請(qǐng)問(wèn)：（1）當(dāng)記錄A、B、C、D、E、F、G、

H按順序放在磁道上時(shí)，順序處理這5個(gè)記錄花費(fèi)的總時(shí)間是多少?假設(shè)啟動(dòng)時(shí)的

位置正好在A扇區(qū)的起點(diǎn)。（2）如何采取優(yōu)化方法，使處理這些記錄所花費(fèi)的總時(shí)

間最短?求出該最短時(shí)間。

標(biāo)準(zhǔn)答案：（1）磁盤(pán)旋轉(zhuǎn)速度是20ms/r,共分成8個(gè)扇區(qū)，因此，每個(gè)扇區(qū)所花費(fèi)

的讀寫(xiě)時(shí)間為20ms/8=2.5ms。若按順序編號(hào)，每讀出一個(gè)扇區(qū)后用2ms的時(shí)間

進(jìn)行處理，此時(shí)，磁盤(pán)為在轉(zhuǎn)動(dòng)，處理完A扇區(qū)后，磁頭已經(jīng)過(guò)了大部分的B扇

區(qū)，即將到達(dá)C扇區(qū)，因此，要等磁盤(pán)再轉(zhuǎn)一圈后才可讀扇區(qū)B,見(jiàn)下左圖，依

此類(lèi)推，順序處理8個(gè)扇區(qū)的時(shí)間花費(fèi)是（其中H是最后一個(gè)，因此，處理有別于

其他扇區(qū)）：A~G扇區(qū)讀取時(shí)間：2.5ms；A?G扇區(qū)處理時(shí)間：2ms等待下一個(gè)

扇區(qū)到達(dá)時(shí)間:20ms—2ms=18msH扇區(qū)讀取時(shí)間:2.5ms；H扇區(qū)處理時(shí)間:

2ms總消耗時(shí)間為:（2.5ms+2ms+l8ms）x7+2.5ms+2ms=162ms

是扇區(qū)交替編號(hào)，使得A扇區(qū)在處理完以后可以在最短時(shí)間內(nèi)定位B扇區(qū)，排列

方式如上右圖?；ㄙM(fèi)時(shí)間是：A?D扇區(qū)讀取時(shí)間：2.5ms；A?D扇區(qū)處理時(shí)

間：2msA~C等待下一個(gè)扇區(qū)到達(dá)時(shí)間：2.5ms—2ms=0.5msD等待E扇區(qū)到

達(dá)時(shí)間：0.5ms+2.5ms=3msE?H扇區(qū)讀取時(shí)間：2.5ms；E~H扇區(qū)處理時(shí)

間：2msE?G等待下一個(gè)扇區(qū)到達(dá)時(shí)間：2.5ms—2ms=0.5ms總消耗時(shí)間為：

（2.5ms+2ms）x4+0.5msx3+3ms+（2.5ms+2ms）x4+0.5msx3=42ms

知識(shí)點(diǎn)解析：本題考的是如何減少讀寫(xiě)磁盤(pán)的時(shí)間、尋找時(shí)間、延遲時(shí)間和傳輸時(shí)

間。

46、在某個(gè)操作系統(tǒng)中，通過(guò)大量的實(shí)驗(yàn)，人們觀察到在兩次缺頁(yè)中斷之間執(zhí)行的

指令數(shù)與分配給程序的頁(yè)框數(shù)成正比，即可用內(nèi)存加倍，缺頁(yè)中斷的平均間隔也加

倍。整體缺頁(yè)次數(shù)減少約一半。假設(shè)一條普通指令需要100ns，但若發(fā)生了缺頁(yè)中

斷就需耍1ms。一個(gè)程序運(yùn)行了60s,期間發(fā)生了1500次缺頁(yè)中斷，如果該程序

的可用內(nèi)存增加到原來(lái)的2倍，那么，請(qǐng)計(jì)算，此」寸這個(gè)程序運(yùn)行需要多少時(shí)間？

標(biāo)準(zhǔn)答案：內(nèi)存增加以后，原來(lái)運(yùn)行60s的程序變?yōu)椋海?500/

2）x1ms4-585000000x100ns=59.25s

知識(shí)點(diǎn)解析：本題的形式較少見(jiàn)，計(jì)算的不是缺頁(yè)中斷的次數(shù)，而是根據(jù)缺頁(yè)中斷

的次數(shù)計(jì)算程序運(yùn)行時(shí)間。首先應(yīng)算出該程序一共運(yùn)行了多少條指令，一條普通

指令需要100ns,但發(fā)生缺頁(yè)中斷就要花費(fèi)1ms,也即處理頁(yè)故障時(shí)間是

1000000ns,由此可算出該程序一共有指令數(shù)為：（60s—

1500xlms）:100ns=5850（）0000（條）擴(kuò)容后，處理缺頁(yè)中斷的總時(shí)間為：（1500/

2）xlms=750ms（內(nèi)存是原來(lái)的兩倍，缺頁(yè)中斷數(shù)降低為原來(lái)的1/2）。那么，該程

序的運(yùn)行時(shí)間是：750ms+585000000條x100ns/條=59.25s。

47、下面是給出的一段IP數(shù)據(jù)包頭所包含的數(shù)據(jù)，0000305252400080062C

23C0A80101D803E215,請(qǐng)根據(jù)IPv4頭部格式回答如下問(wèn)題:（1）該IP包的發(fā)

送主機(jī)和接收主機(jī)的地址分別是什么？（2）該IP包的總長(zhǎng)度是多少?頭部長(zhǎng)度是多

少？（3）該IP分組有分片嗎?如果有分片它的分片偏移量是多少？（4）該IP包是由什么

傳輸層協(xié)議發(fā)出的？

比笛o31

版本買(mǎi)餐長(zhǎng)度服務(wù)類(lèi)型總長(zhǎng)度

固標(biāo)研標(biāo)志片集移

定

?生命期頭部檢■和

分

源地址

目的地址

可

盤(pán)選*填充

ff分

敬輯?分

■47圈IPv4融?幺加幡式

標(biāo)準(zhǔn)答案：（1）該IP包的發(fā)送主機(jī)和接收主機(jī)的地址分別是192.168.1.1和

216.3.226.21o（2）