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

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

1、在雙鏈表中p所指的結(jié)點之前插入一個結(jié)點q的操作為（）。

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

BNq—>prior=p—>prior；p—>prior—>ncxt=q；q—>ncxt=p；p—>prior=q—>ncxt；

C、q一nexl=p；p一nexl=q；q—prior一next=q；q—nexl=p；

D^p—>prior—>next=q：q—?next=p：q—*prior=p—>prior：p—>prior=q：

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

知識點解析：這種題目其實大部分考生都見過，解題步驟都是固定的。先畫圖，將

選項給出的代碼逐個進行檢查，看是否存在斷鏈或者賦值錯誤的情況。但是有一種

萬能的解法可以應(yīng)對算法題。如果此題是算法題，考生可將此題的答案按照下面所

給的解題技巧輕松地寫出，完全不必擔(dān)心步驟是否會發(fā)生錯誤。解題技巧：這種

題目的目的僅僅是需要狙一個結(jié)點插入兩個結(jié)點之間即可，答案肯定不唯一.但是

我們應(yīng)該從一些正確答案中挑選出一個萬能的插入公式，這樣，遇到這種題目，就

能迎刃而解了。例題：假設(shè)在雙鏈表中p所指的結(jié)點之后插入一個結(jié)點s,其操作

語句描述為s->next=p一〉next：s—*>prior=p；p->next=s,s一>next—*>prior=s：

指針變化過程如圖8-5所示。

d)s>ncMt

用a雙諼衣氈點的拓入過程說明：不知道大家有沒有

注意到，在插入時，如果按照上面的順序來插入，可以看成是一個萬能的插入方

式。不管怎樣，先將要插入的結(jié)點兩邊鏈接好，這樣可以保證不會發(fā)生鏈斷之后找

不到結(jié)點的情況。所以考生們一定要記住這種萬能的插入結(jié)點的方式。

2、下列關(guān)于鏈?zhǔn)綏５臄⑹鲋?，錯誤的是（）。I.鏈?zhǔn)綏Ｖ荒茼樞蛟L問，而順序棧

不但能順序訪問，還能直接存取U.因為鏈?zhǔn)綏]有棧滿問題，所以進行進棧操

作，不需要判斷任何條件DI.在鏈?zhǔn)疥犃械某鲫牪僮髦?，需要修改尾指針的情況

發(fā)生在空隊列的情況下

A、僅I

B、僅I、n

C、僅口

D^i、n、m

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

知識點解析：I：棧要求只能在表的一端（棧頂）訪問、插入和刪除，這決定了淺無

論采用何種存儲方法表示，只能順序訪問，不能直接存取，故I錯誤。n：每創(chuàng)

建新的棧結(jié)點時還要判斷是否動態(tài)分配成功，若不成功，則進棧操作失敗。

StaekNOde*s=newStaekNode；if（s=NULL）{prinlf（“結(jié)點存儲分配失?。n"）；}

故n錯誤。m：首先要清楚鏈?zhǔn)疥犃行枰獌蓚€指針，即頭指針和尾指針。當(dāng)鏈隊

列需要插入元素時，在鏈?zhǔn)疥犃形膊坎迦胍粋€新的結(jié)點，并且修改尾指針；當(dāng)鏈隊

列需要刪除元素時，在鏈?zhǔn)疥犃蓄^部刪除一個結(jié)點，并且修改頭指針。所以當(dāng)鏈?zhǔn)?/p>

隊列需要進行入隊操作時，應(yīng)該只需修改尾指針即可。但是有一種特殊情況（考生

務(wù)必記住，因為不少考生在寫鏈?zhǔn)疥犃谐鲫牭乃惴〞r，并沒有考慮到去判斷這種情

況），就是當(dāng)此時只有一個元素時，不妨設(shè)此時鏈?zhǔn)疥犃杏蓄^結(jié)點，那么當(dāng)唯一個

元素出隊時，應(yīng)該將頭指針指向頭結(jié)點，并且此時尾指針也是指向該唯一的元素，

所以此時需要修改尾指針，并且使尾指針指向頭結(jié)點，故in錯誤。

3、設(shè)有一個二維數(shù)組在存儲中按行優(yōu)先存放（數(shù)組的每一個元素占一個窄

間），假設(shè)A[0]⑼存放位置在78O（io）,A[4]⑹存放位置在1146（io）,則A[6][20]存

放在（）位置（其中（10）、表明用十進制數(shù)表示）。

A^1342（io）

1336（io）

C、1338（io）

D、I34O（IO）

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

知識點解析：由Loc（4,6）=Loc（0,0）+（4xn+6）xl=780+（4xn+6）=l146,可得

n=（H46—780—6）/4=90,則可計算出Loc（6,20）=Loc（0,

0）+（6x90+20）x1=780+560=1340。

4、一棵二叉樹的前序遍歷序列為1234567,則它的中序遍歷序列不可能為（）。

I.3124567D.1234567IE.4135627IV.1436572

A僅

、I、n

B僅

、□、n

c僅

、i、n

D僅

、i、m、w

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

知識點解析：由二叉樹的前序遍歷為1234567可知，該二叉樹的根為結(jié)點1,并且

2為1的孩子結(jié)點。I：假如3124567是該二叉樹的中序遍歷，那么3必然是1的

左孩子，前序遍歷的序列一定是13,而前序遍歷并沒有以13開頭，所以I不可能

是中序序列。n：首先需要來證明一個知識點：什么情況下，前序遍歷和中序遍

歷是一樣的。前序遍歷是山（根左右），中序遍歷是Itr（左根右），下面就從Ur和Itr

著手。（1）當(dāng)沒有左子樹時，前序遍歷變成了tr,中序遍歷也變成了tr,故此種情

況F前序遍歷和中序遍歷一樣。（2）當(dāng)沒有右子樹時，前序遍歷變成U,中序遍歷

卻變成了It,故此種情況下前序遍歷和中序遍歷不一樣。綜上分析，只要該二叉

樹沒有左子樹，則都能夠滿足前序遍歷和中序遍歷是一樣的，故口是可能的。

m：和I的情況一樣的分析，前序應(yīng)該是以14開頭，所以不可能是中序序列。

IV：構(gòu)造的二叉樹如圖8-6所示。圖例因此，I、皿不可能?？偨Y(jié)：

以下3種情況可以唯一確定一棵二叉樹。①先序序列和中序序列。②后序序列和

中序序列。③層次序列和中序序列（重點，注意出題。）

5、寬度為27,高度為4的滿N叉樹總共有（）個結(jié)點。

A、27

B、40

C、85

D、97

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

知識點解析：寬度是指樹中每一層結(jié)點個數(shù)的最大值。滿N叉樹的寬度為27,即

最底層的葉子結(jié)點有27個，該層結(jié)點最多。高度為4,根據(jù)N叉樹的性質(zhì)，第4

層有結(jié)點N4J=27,N=3O該滿3叉樹的結(jié)點個數(shù)為。4一1）/（3一1尸（81?1）/

2=40o

6、對于一棵具有n個結(jié)點、度為4的樹來說（樹的層數(shù)從1開始），以下說法正確

的是（）。I.樹的高度至多為n—3口.至少在某一層上正好有4個結(jié)點III.第i

層上至多有4。一1）個結(jié)點

A僅

、I

B僅

、I、n

c僅

、n

D僅

、i、m

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

知識點解析：I：樹中各結(jié)點的度的最大值稱為樹的度，所以對于度為4的樹，必

須存在某個結(jié)點有4個分支結(jié)點的情況。那么，樹最高的情況應(yīng)該類似于圖8-

f>-4

7,故I正確。n：這個不一定，如圖8-8所示的情況，故口

錯誤。圖8-8的的另外料情況n：就拿樹的第三層來說，可以有16個結(jié)點，正確

的答案應(yīng)該是第i層上至多有4用個結(jié)點，故in錯誤。

7、以下有關(guān)拓撲排序的說法中，錯誤的是（）。I.如果某有向圖存在環(huán)路，則該

有向圖一定不存在拓撲排序口.在拓撲排序算法中，既可以使用棧，也可以使用

隊列m.若有向圖的拓撲有序序列唯一，則圖中每個頂點的入度和出度最多為1

A、僅I、m

B、僅口、m

c、僅n

D、僅m

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

知識點解析：I：如果一個有向圖存在環(huán)路，則該有向圖肯定不會存在拓撲排序，

這是因為該環(huán)路找不到入度為o的結(jié)點，拓撲排序自然也就進行不下去了，故I正

確。n：使用棧來表示拓撲排序的序列，最后的出棧序列是逆拓撲排序，只需逆

轉(zhuǎn)過來即可，只是效率比較低；使用隊列時，出隊序列就是拓撲排序序列，故使用

棧和隊列都是可以的，只是效率不等而已，故n正確。m：一個反例如圖8—9所

示。該有向圖的拓撲有序序列是唯一的，但各個頂點的入度和出度可以超出1,故

坦錯誤。圖89反制

8、無向圖G有23條邊，度為4的頂點有5個，度為3的頂點有4個，其余都是度

為2的頂點，則圖G最多有（）個頂點。

A、II

B、12

C、15

D、16

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

知識點解析：頂點的度是指與此頂點相關(guān)聯(lián)的邊數(shù)，而每條邊與兩個頂點相關(guān)聯(lián)。

23條邊最多有46個頂點（不排除多條邊共享一個頂點），設(shè)圖G中有n個頂點，則

有4x5+3x4+（n—57）x2323x2,解得悵16。

9、圖8—1是一棵（）。圖8」應(yīng)9陽

A、4階B一樹

B、4階B+樹

C、3階B一樹

D、3階B+樹

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

知識點解析：首先很明顯不是B+樹，因為B+樹的葉子結(jié)點本身依關(guān)鍵字的大小自

小而大順序鏈接，故排除B、D選項。另外，B一樹有一個性質(zhì)為：m階B一樹的

結(jié)點關(guān)鍵字?jǐn)?shù)量最多為m—l個，但是圖8—1中有個結(jié)點有3個關(guān)鍵字，也就是

說此B一樹不可能是3階，故選A選項。

10、如果一臺計算機具有多個可并行運行的CPU,就可以同時執(zhí)行相互獨立的任

務(wù)。歸并排序的各個歸并段的歸并也可并行執(zhí)行，因此稱歸并排序是可并行執(zhí)行

的。那么以下的排序方法不可以并行執(zhí)行的有（）。I.基數(shù)排序D.快速排序

m.起泡排序w.堆排序

A、僅I、m

B、僅I、n

C、僅I、皿、W

D、僅n、w

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

知識點解析：此題解題的關(guān)鍵是要知道哪種內(nèi)部排序算法在執(zhí)行的過程中，不能劃

分出子序列來進行并行的排序，快速排序在一趟劃分了兩個子序列后，各子序列又

可并行執(zhí)行排序。而其他3種排序不能劃分成子序列來并行執(zhí)行排序，故4個選項

中，只有快速排序可以并行執(zhí)行，故選c選項。

11、假設(shè)有5個初始歸并段，每個歸并段有20個記錄，采用5路平衡歸并排序,

若采用敗者樹的方法，總的排序碼比較次數(shù)不超過（）。

A、20

R、300

C、396

D、500

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

知識點解析：假設(shè)采用k路平衡歸并排序算法，則敗者樹的高度為[10g2k|+l。且在

每次調(diào)整后，找下一個具有最小排序碼記錄時，最多做[10g2k]次排序碼比較。由題

意可知，總共有100個記錄，所以總的比較次數(shù)不超過100x[log25]=300。注意：

采用敗者樹進行k路平衡歸并的外部排序算法，其總的歸并效率與k無關(guān)。

12、已知定點整數(shù)X的原碼為lXn/Xn-2Xn-3…X0，且X>-2”"，則必有（）。

A、xn-i=0

B、Xn-]~1

C、xn.i=0,且xo~x『2不全為0

D、xn-l=l，且xo?Xn-2不全為0

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

知識點解析：由于X的符號位為1,可知X為負數(shù)。又因為X>-2n1可以得到X

的絕對值必須小于2nL所以Xn-I必須為0。

13、在原碼一位乘中，當(dāng)乘數(shù)Yi為1時，（）。

A、被乘數(shù)連同符號位與原部分積相加后，右移一位

B、被乘數(shù)絕對值與原部分積相加后，右移一位

C、被乘數(shù)連同符號位右移一位后，再與原部分積相加

D、被乘數(shù)絕對值右移一位后，再與原部分積相加

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

知識點解析：具體請參看表8—2o

表8”原碼、補碼的乘法與除法

符號口處即

桑散Y,為1時.被篥數(shù)葩對值，好部分積州加分首付

罩科重法符號付好或

聚也乂為0H.真接方格付

<1）倭喉?x符鄉(xiāng)仆意.集tty為,Et同Ki列位乘

（2）X桑Ky為優(yōu)：先構(gòu)[y]?去N符號位.遇打%孫位來憚作.得到的結(jié)

果越打+卜X].牧止

樸回泰法不單獨處用

（3）B<xKh"法：垂數(shù)連同符號付可加入運?T乂H堵加付附加付y..”4初蛤價為。.用

一次il0時.富亡令圻y陰…oof?11IH.部分加行移由oiH.懸分枳加[小.西公杵tir.t

I0H.后分機自:卜7-.內(nèi)乙樣位.（汴息1Booth"法4收行也是小移口的.即切梟出觀00

和”mil儀站柬1方附現(xiàn)io或。1.惻篇分枳加梢聲位后紿束iim

（1）恢收余數(shù)溫|首光將祓除數(shù)葩對ffl”,?）.?公氽數(shù)為止.l-.ifii-r.AJtM總第緡堆

進法撮件：若余畋為豉.1曲懾圮余數(shù)?[y?b.5此也M

修用除法符號位用或

（2）加M殳瞥法t行先將被除數(shù)綸時值+[y?k若余數(shù)為匕8）T.A1W-W,*（）?1??

齊爾數(shù)為負.hft-0".左陟付.，??]?

甫先判瞭⑶和[“足否網(wǎng)1；,弓.tt*|yksTFW4.則WV；.6百余數(shù)|R卜,和?]”

料碼除法不單獨處方足古問號.6問號.IM1?-1-.古林?,冠用Tyjxr.?y.左林付.如北

fU

注：1.只要是原碼運算。符號位一定是單獨處理，不參與運算。2.此表只是列

出大體的運算規(guī)則，具體的操作還需要讀者進行一些針對的練習(xí)，雖然作為大題考

到的概率幾乎為0,但是也應(yīng)該從練習(xí)中多總結(jié)一些規(guī)律，以應(yīng)對選擇題。

14、在下列Cache替換算法中，一般情況下，（）性能最優(yōu)。

A、隨機法

先進先出法

C、后進先出法

D、近期最少使用法

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

知識點解析：隨機法：隨機地確定替換的存儲單元，肯定沒有遵循程序訪存局部性

原理。先進先出法：替換最早調(diào)入的存儲單元，也沒有遵循程序訪存局部性原

理，命中率較低。后進先出法：不是Cache所使用的替換算法，此法在堆棧存儲

結(jié)構(gòu)中使用。近期最少使用法：比較正確地利用了程序訪存局部性原理，替換出

近期用得最少的存儲塊，命中率較高，是一種比較好的替換算法。綜上分析，近

期最少使用法性能最優(yōu)。

15、如圖8-2所示，若低位地址(A0?All)接在主存芯片地址引腳上，高位地址

(A12?A19)進行片選譯碼(其中A14和AI6沒有參加譯碼)，且片選信號低電平有

效，則對圖8—2所示的譯碼器，不屬于其譯碼空間的地址為()。

圖8-2題IS圖

A、ABOOOH?ABFFFH

B、BBOOOH?BBFFFH

C、EFOOOH?EFFFFH

D、FEOOOH?FEFFFH

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

知識點解析：這是一個部分譯碼的片選信號(因為高8位地址中有兩位沒有參與譯

碼)，根據(jù)譯碼器電路，譯碼輸出的邏輯表達式應(yīng)為古

=A19(A18+A17)A15A13Al2注意：表示只要有一個為1即可，所以形成

A17+A18。而譯碼器中間有一個&,所以A19、A17+A18、A15、A13、A12都必

須為1。換句話說，AI9、A15、A13>A12必須為1,而A17、A18必須至少有I

個為1。由于D選項的A12為0,因此不屬于此譯碼空間。

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

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

MOVX#IOO(即將數(shù)值100傳送到寄存器X中)，則CPU首先要完成的操作是()。

A、100—R0

B、100—MDR

C、PC-MAR

D、PC—IR

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

知識點解析：取指周期完成的微操作序列是公共的操作，與具體指令無關(guān)。CPU

首先需要取指令，取指令階段的第一個操作就是將指令地址（程序計數(shù)器中的內(nèi)容）

送往存儲器地址寄存器。題干中雖然給出了一條具體的指令“MOVR0,#1001但

實際上CPU首先要完成的操作是取指令，與具體指令是沒有關(guān)系的。

17、條件轉(zhuǎn)移指令所依據(jù)的條件來自（）。

A、通用寄存器

B、數(shù)據(jù)寄存器

C、狀態(tài)寄存器

D、累加器

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

知識點解析：條件轉(zhuǎn)移指令所依據(jù)的條件來自狀態(tài)寄存器。對于此題，有些輔導(dǎo)書

給出的答案可能是標(biāo)志寄存器（狀態(tài)寄存器的組成之一）。狀態(tài)寄存器：狀態(tài)寄存器

又名條件碼寄存器，它是計算機系統(tǒng)的核心部件，屬于運算器的一部分。狀態(tài)寄存

器用來存放如下兩類信息。一類是體現(xiàn)當(dāng)前指令執(zhí)行結(jié)果的各種狀態(tài)信息（條件

碼），如有無進位（CY位）、有無溢出（OV位）、結(jié)果正負（SF位）、結(jié)果是否為零（ZF

位）、奇偶標(biāo)志位（P位）等。另一類是存放控制信息（PSW程序狀態(tài)字寄存器），如允

許中斷（IF位）、跟蹤標(biāo)志（TF位）等。有些機器中將PSW稱為標(biāo)志寄存器FR（Flag

Register）o

18、流水線中有3類數(shù)據(jù)相關(guān)沖突：寫后讀相關(guān)、讀后寫相關(guān)和寫后寫相關(guān)。那么

下列3組指令中存在讀后寫相關(guān)的是（）。I：IlSUBRI,R2,R3；（R2）一

（R3）->R112ADDR4,R5,RI；（R5）+（R1）->R4D：IlSTAM,R2；（R2）—M,

M為主存單元12ADDR2,R4,R5；（R4）+（R5）—R22：IlMULR3,R2,RI；

（R2）x（Rl）->R312SUBR3,R4,R5；（R4）—（R5）TR3

A、僅i、n

B、僅口

c、僅口、in

D、i>n>in

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

知識點解析：I：Il指令運算結(jié)果應(yīng)先寫入RI,然后在指令12中讀出R1的內(nèi)

容。由于12指令進入流水線，使得12指令在II指令寫入R1前就讀出R1的內(nèi)

容，發(fā)生“寫后讀相關(guān)，口：II指令應(yīng)先讀出R2的內(nèi)容并存入存儲單元M中，

然后12指令將運算結(jié)果寫入R2中。但由于12指令進入流水線，使得12指令在II

指令讀出R2之前就寫入R2,發(fā)生“讀后寫相關(guān)“。迎：12指令應(yīng)該在II指令寫入

R3之后，再寫入R3?，F(xiàn)由于12指令進入流水線，如果12指令減法運算在II指令

的乘法運算之前完成，使得12指令在II指令寫入R3之前就寫入R3,導(dǎo)致R3內(nèi)

容錯誤，發(fā)生“寫后寫相關(guān)

19、在單級中斷系統(tǒng)中，CPU一旦響應(yīng)中斷，則立即關(guān)閉（）觸發(fā)器，以防本次中

斷服務(wù)結(jié)束前同級的其地中斷源產(chǎn)生另一次中斷，導(dǎo)致中斷服務(wù)程序被干擾。

A、中斷允許

B、中斷請求

C、中斷屏蔽

D、中斷保護

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

知識點解析：單級中斷系統(tǒng)中，CPU響應(yīng)中斷將會關(guān)閉中斷允許觸發(fā)器。中斷系

統(tǒng)包含3個重要觸發(fā)器。中斷請求觸發(fā)器：為判斷是哪個中斷源提出請求，在中

斷系統(tǒng)中必須設(shè)置中斷請求標(biāo)記觸發(fā)器，簡稱中斷請求觸發(fā)器。當(dāng)其狀態(tài)為“1”

時，表示中斷源有請求。這種觸發(fā)器可集中設(shè)在CPU內(nèi)，組成一個中斷請求標(biāo)記

寄存器。中斷屏蔽觸發(fā)器：其功能是決定中斷請求觸發(fā)器的輸出信號是否可以作

為中斷請求信號向CPU發(fā)送。通常CPU可以對中斷屏蔽觸發(fā)器進行操作，從而達

到對中斷源的控制。例如：CPU不準(zhǔn)備響應(yīng)某個外設(shè)中斷，可將中斷屏蔽觸發(fā)器

復(fù)位，不讓該外設(shè)的中斷請求觸發(fā)器的輸出信號通過與門，此操作稱為中斷屏蔽。

CPU將中斷屏蔽觸發(fā)器置“1”，則準(zhǔn)備響應(yīng)該外設(shè)中斷。中斷允許觸發(fā)器：在CPU

內(nèi)部設(shè)置一個中斷允許觸發(fā)器（功能類似于中斷屏蔽觸發(fā)器），只有該觸發(fā)器置

“1”,才允許中斷；置“0”,則不允許中斷。指令系統(tǒng)中，開中斷指令，使中斷觸發(fā)

器置“1”，關(guān)中斷指令，使中斷觸發(fā)器置“0”。中斷保護觸發(fā)器是干擾項，沒有此

類觸發(fā)器。補充：中斷條件。提示：中斷請求要獲得CPU響應(yīng)，必須滿足3個條

件。①中斷屏蔽觸發(fā)器處于非屏蔽狀態(tài)，使外設(shè)的中斷請求信號能發(fā)給CPU。

②中斷允許觸發(fā)器處于開中斷狀態(tài)，使CPU允許響應(yīng)中斷。③一條指令執(zhí)行結(jié)

束。

20、下列屬于微指令結(jié)溝設(shè)計的目標(biāo)是（）。I.提高微程序的執(zhí)行速度U.縮短

微指令的長度m.增大控制存儲器的容量

A僅

、I、W

B僅

、I、口

c僅

、口、n

DI

、、口、山

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

知識點解析：設(shè)計微指令結(jié)構(gòu)時，所追求的目標(biāo)如下。①微指令結(jié)構(gòu)要有利于縮

短微指令的長度。②有利于減小控制存儲器的容量。③有利于提高微程序的執(zhí)行

速度。④有利于微指令的修改。⑤有利于微程序設(shè)計的靈活性。

21、下列說法中，正確的是（）。

A、CPU通過控制單元CU來識別信息是地址還是數(shù)據(jù)

B、間接尋址第一次訪問內(nèi)存所得到的信息經(jīng)過系統(tǒng)總線的地址總線傳送到CPU

C、單總線結(jié)構(gòu)中，可以不使用I/O指令

D、在異步總線中，傳送操作由設(shè)備控制器控制

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

知識點解析：A：CPU通過總線的類型來識別信息是地址還是數(shù)據(jù)，故A選項錯

誤。B：間接尋址第一次訪問內(nèi)存所得到的信息是操作數(shù)的有效地址，該地址通過

數(shù)據(jù)線傳送至CPU,而不是地址線，故B選項錯誤。C：在單總線結(jié)構(gòu)中，

CPU、主存和I/O設(shè)備（通過I/O接口）都掛在一組總線上，若I/O設(shè)備和主存

統(tǒng)一編址，則可以很方便地使用訪存指令訪問I/O設(shè)備，故C選項正確。D：異

步總線即采用異步通信方式的總線。在異步方式下，沒有公共的時鐘，完傘依靠傳

送雙方相互制約的“握手”信號來實現(xiàn)定時控制，故D選項錯誤。

22、下列關(guān)于程序中斷方式和DMA方式的敘述中，錯誤的是（）。I.DMA的優(yōu)

先級比程序中斷的優(yōu)先級要高D.程序中斷方式需要保護現(xiàn)場，DMA方式不需要

保護現(xiàn)場m.程序中斷方式的中斷請求是為了報告CPU數(shù)據(jù)的傳輸結(jié)束，而

DMA方式的中斷請求完全是為了傳送信息

A、僅U

B、僅口、皿

C、僅山

D、僅I、出

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

知識點解析：I：DMA方式不需CPU干預(yù)傳送操作，僅僅是開始和結(jié)尾借用

CPU一點時間，其余不占用CPU任何資源；中斷方式是程序切換，每次操作需要

保護和恢復(fù)現(xiàn)場，所以DMA優(yōu)先級高于中斷請求，這樣可以加快處理效率，故I

正確。D：從I的分析可知，程序中斷方式需要中斷現(xiàn)行程序，故需保護現(xiàn)場，

以便中斷執(zhí)行完之后還能同到原來的點去繼續(xù)沒有完成的工作；DMA方式不需要

中斷現(xiàn)行程序，無須保尹現(xiàn)場，故n正確。皿：DMA方式中的中斷請求不是為了

傳送信息（信息是通過主存和I/O間的直接數(shù)據(jù)通路傳送的），只是為了報告CPU

一組數(shù)據(jù)傳送結(jié)束，有待CPU做一些后處理工作，如測試傳送過程中是否出錯，

決定是否繼續(xù)使用DMA方式傳送等。而程序中斷方式的中斷請求是為了傳送數(shù)

據(jù)，I/O和主機交換信息完全靠CPU響應(yīng)中斷后，轉(zhuǎn)至中斷服務(wù)程序完成的，故

m錯誤。

23、下列關(guān)于系統(tǒng)調(diào)用的說法中，正確的是（）。I.當(dāng)操作系統(tǒng)完成用戶請求的

“系統(tǒng)調(diào)用”功能后，應(yīng)使CPU從內(nèi)核態(tài)轉(zhuǎn)到用戶態(tài)工作n.用戶程序設(shè)計時，使

用系統(tǒng)調(diào)用命令，該命令經(jīng)過編譯后，形成若干參數(shù)和屏蔽中斷指令HI.用戶在

編寫程序時計劃讀取某個數(shù)據(jù)文件中的20個數(shù)據(jù)塊記錄，需使用操作系統(tǒng)提供的

系統(tǒng)調(diào)用接口IV.用戶程序創(chuàng)建一個新進程，需使用操作系統(tǒng)提供的系統(tǒng)調(diào)用接

口

A僅

、I、m

B僅

、口、IV

c僅

、I、皿、w

D僅

、n、m、w

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

知識點解析：I正確，程序執(zhí)行系統(tǒng)調(diào)用是通過中斷機構(gòu)來實現(xiàn)的，需要從用戶態(tài)

轉(zhuǎn)到內(nèi)核態(tài)，當(dāng)系統(tǒng)調(diào)用返回后，繼續(xù)執(zhí)行用戶程序，同時CPU狀態(tài)也從內(nèi)核態(tài)

切換到用戶態(tài)。n錯誤，用戶程序無法形成屏蔽中斷指令。這里應(yīng)該是形成若干

參數(shù)和陷入（trap）指令。系統(tǒng)調(diào)用需要觸發(fā)trap指令，如基于x86的Linux系統(tǒng)，

該指令為皿0*80或5}^1116]。DI正確，編寫程序所使用的是系統(tǒng)調(diào)用，例如

read（）o系統(tǒng)調(diào)用會給用戶提供一個簡單的使用計算機的接口，而將復(fù)雜的對硬件

（例如磁盤）和文件操作（例如查找和訪問）的細節(jié)屏蔽起來，為用戶提供一種高效使

用計算機的途徑。W正確，用戶程序通過程序接口（即系統(tǒng)調(diào)用接口）進行進程控

制。操作系統(tǒng)實現(xiàn)的所有系統(tǒng)調(diào)用所構(gòu)成的集合，即程序接口或應(yīng)用編程接口

（ApplicationprogrammingInterface,API）,是應(yīng)用程序同系統(tǒng)之間的接口。它包括

進程控制、文件系統(tǒng)控制、系統(tǒng)控制、內(nèi)存管理、網(wǎng)絡(luò)管理、用戶管理、進程間通

信等，所以幾乎各個功能都需要用到系統(tǒng)調(diào)用。系統(tǒng)調(diào)用是操作系統(tǒng)提供給應(yīng)用程

序的唯一接口。綜上分析，本題選C選項。

24、同一進程中，多個線程之間（）是共享的。I.代碼區(qū)n.數(shù)據(jù)區(qū)in.執(zhí)行棧

IV.線程控制塊v.動態(tài)堆空間VI.運行時動態(tài)分配的寄存器

A、I、m、VI

B、口、ui、w

C、I、□、v

D、口、IV、V

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

知識點解析：在引入線程的系統(tǒng)中，進程仍然是資源分配的單位，所以，代碼區(qū)、

數(shù)據(jù)區(qū)和動態(tài)堆空間都是共享的，但線程乂是調(diào)度的基本單位，所以，線程擁有自

己的PCB。線程的私有成分包括：⑴線程控制塊；⑵一個執(zhí)行棧；⑶運行時動

態(tài)分配給線程的寄存器。

25、假定一個處理器正在執(zhí)行3道作業(yè)，I作、也以計算為主，n作業(yè)以輸入/輸出

為主，in作業(yè)以計算與輸入/輸出為主。應(yīng)該如何賦予它們占有處理器的優(yōu)先級，

使得系統(tǒng)效率較高？

A、I作業(yè)優(yōu)先級最高.DI次之.II最低

B、II作業(yè)優(yōu)先級最高，I次之，in最低

c、HI作業(yè)在優(yōu)先級最高，n次之，I最低

D、II作業(yè)優(yōu)先級最高，in次之，I最低

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

知識點解析：處理器調(diào)度算法會考慮作業(yè)響應(yīng)時間要求，讓CPU盡量和外圍設(shè)備

并行工作，防止一個計算進程長時間霸占處理器。因而，輸入/輸出為主作業(yè)（U

作業(yè)）優(yōu)先級最高，計算與輸入/輸出均勻的作業(yè)（HI作業(yè)）其次，計算為主作業(yè)（I

作業(yè)）的優(yōu)先級最低。

26、設(shè)有10個進程共享n個資源，每次允許3個連程同時使用該資源。試問：信

號量的變化范圍是（）。

A、[3n—10,3n]

B、[n-10,n]

C、|n—10/3,n]

D、［3n—10,n|

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

知識點解析?：本題的關(guān)健在于，“每次允許3個進程同時使用一個資源”這個條件，

即可以把該資源看成是3個獨立的臨界資源。那么臨界資源的總個數(shù)為3n,很顯

然，A選項是正確答案＜：

27、如果對經(jīng)典的分頁式存儲管理策略的頁表做細微改造，允許不同頁表的頁表項

指向同一物理頁幀，可能的結(jié)果有（）。I.實現(xiàn)對可重入代碼的共享H.只需要

修改頁表項，就能實現(xiàn)內(nèi)存“復(fù)制”操作m.容易發(fā)生越界訪問W.實現(xiàn)進程間通

信

A、僅I、n、w

B、僅u、m

c、僅I、n、m

D、僅I

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

知識之解析A：地址在頁式分配系統(tǒng)上是一個邏輯頁號和一個偏移量。在邏輯頁號的

基礎(chǔ)上產(chǎn)生一個物理頁號，物理頁通過搜索表被找到。因為操作系統(tǒng)控制這張表的

內(nèi)容，只有在這些物理頁被分配到進程中時，它才可以限制一個進程的進入。一個

進程想要分配一個它所不搦有的頁是不可能的，因為這一頁在頁表中不存在。為了

允許這樣的進入，操作系統(tǒng)只簡單地將屬于其他進程的頁信息加到該進程頁表中。

I正確，讓同一頁表的兩個頁表項指向同一物理頁幀，用戶可以利用此特點共享該

頁幀的代碼或數(shù)據(jù)。如果代碼是可重入的，如編輯軟件、編譯軟件、數(shù)據(jù)庫管理系

統(tǒng)等，這種方法可節(jié)省大量的內(nèi)存空間。n正確，實現(xiàn)內(nèi)存“復(fù)制”操作時，不需

要將頁面的內(nèi)存逐字節(jié)復(fù)制，而只要在頁表里將指向該頁面的指針復(fù)制到代表目的

地址的頁表項中。in錯誤，是干擾項。w正確，當(dāng)兩個或多個進程需要交換數(shù)據(jù)

時，這是十分有用的。它們只是讀和寫相同的物理地址（可能在多樣的物理地址

中），在進程問通信時，這是十分高效的。

28、作業(yè)在執(zhí)行中發(fā)生缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行的指令是（）。

A、被中斷的前一條

B、被中斷的那一條

C、被中斷的后一條

D、啟動時的第一條

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

知識點解析：因為中斷是由執(zhí)行指令自己產(chǎn)生的，而且還沒有執(zhí)行完，故中斷返回

時，應(yīng)重新執(zhí)行被中斷的那一條指令。知識點回顧：在請求分頁系統(tǒng)中，每當(dāng)要

訪。問的頁面不在內(nèi)存時，便產(chǎn)生一個缺頁中斷，請求操作系統(tǒng)將所缺頁調(diào)入內(nèi)

存。此時應(yīng)將缺頁的進程阻塞（調(diào)頁完成后喚醒），如果內(nèi)存中有空閑塊，則分配一

個塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)的頁表項，若此時內(nèi)存中沒有空

閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回內(nèi)存）。缺頁

中斷與一般中斷的相同點是：缺頁中斷作為中斷，同樣需要經(jīng)歷諸如保護CPU環(huán)

境、分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進行處理、恢復(fù)CPU環(huán)境等幾個歲

驟。但缺頁中斷是一種特殊的中斷，與一般中斷有明顯區(qū)別：缺頁中斷是在指令

執(zhí)行期間產(chǎn)生和處理中斷信號，另外，一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中

斷。

29、在一個請求分頁系統(tǒng)中，采用LRU頁面置換算法時，假如一個作業(yè)的頁面走

向為：1、3、2、1、1、3、5、1、3、2、1、5。當(dāng)分配給該作業(yè)的物理塊數(shù)分別為

3和4時，試計算在訪問過程中所發(fā)生的缺頁率是（）。

A、35%,25%

B、35%,50%

C、50%,33%

D、50%,25%

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

知識點解析：①物理塊數(shù)為3時，缺頁情況如表8-3所示。

餓頁情況（物理塊勤為3》

8—3、表8一I那樣列出缺頁情況。

30、下面關(guān)于目錄檢索的敘述中，正確的是（）。

A、由于Hash法具有較快的檢索速度，因此現(xiàn)代操作系統(tǒng)中都用它來替代傳統(tǒng)的

順序檢索方法

B、在利用順序檢索法時，對樹形目錄應(yīng)采用文件的路徑名，且應(yīng)從根目錄開始逐

級檢索

C、在利用順序檢索法時，只要路徑名的一個分量名未找到，便應(yīng)停止查找

D、在順序檢索法時的查找完成后，即可得到文件的物理地址

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

知識點解析：A錯誤：目錄檢索的方式有兩種，即線性檢索法和Hash法，線性檢

索法即root/../filename,現(xiàn)代操作系統(tǒng)中，一般還是采用這種方式查找文件。B

錯誤：為了加快文件查找速度，可以設(shè)立當(dāng)前目錄，這樣，文件路徑可以從當(dāng)前目

錄進行查找。C正確：實現(xiàn)用戶對文件的按名存取，系統(tǒng)先利用用戶提供的文件

名形成檢索路徑，對目錄進行查詢。在順序檢索時，路徑名的一個分量名未找到，

說明路徑名中的某個目錄或文件不存在，就不需要再查找了。D錯誤：在順序檢

索法時的查找完成后，得到文件的邏輯地址。

31、假設(shè)磁頭的當(dāng)前位置是100磁道，磁頭正向磁道號增加的方向移動，磁道號從

最小的0號到最大的199號?，F(xiàn)有一個磁盤讀寫清求隊列：98、183、37、122、

10、124、65、67o若采用掃描算法，則平均尋道長度是（）。

A、29

B、32

C、36

D、40

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

知識點解析：這類題其實是有爭議的。問題其實就是SCAN算法和LOOK算法

（①LOOK不是CSCAN；②CSCAN跟SCAN的區(qū)別是CSCAN只有一個起點［的

區(qū)別。SCAN算法是要掃到頭的，而LOOK算法是移動到最內(nèi)/外磁道后，就改

變方向。但很多時候教材只提到SCAN算法，而算法描述其實是LOOK算法。考

生如果遇到這樣的問題，建議這樣處理：若沒有給出最內(nèi)/最外磁道號的，題目就

默認是考查LOOK算法；若給出最內(nèi)/最外磁道號的，而又無特殊說明的，就默

認是考查SCAN算法。2012年的大綱解析中，對SCAN算法的解釋是耍掃到底才

改變方向的。所以，本題解答如下：掃描算法的尋道順序為

100—122—124—183—199—98—67—65—37—10,由100至U199移動道數(shù)為99：

再由199到10移動道數(shù)為189,總共移動道數(shù)為288,平均尋道長度為288/

R=36,本題選C選項。知識點回顧：掃描算法（SCAN）或電梯調(diào)度算法優(yōu)缺點如

下。優(yōu)點：解決最短尋道時問優(yōu)先（SSTF）算法的饑餓問題，性能較好。缺點：存

在一個請求剛好被錯過而需要等待很長時間才會被處理的問題。

32、下列幾種類型的系統(tǒng)中，適合采用忙等待I/O方式的有（）0I.專門用來捽

制單I/O設(shè)備的系統(tǒng)u.運行一個多任務(wù)操作系統(tǒng)的個人計算機m.作為一個

負載很大的網(wǎng)絡(luò)服務(wù)器的工作站

A僅

、I

B僅

、I、n

c僅

、口、皿

D僅

、I、口、m

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

知識點解析：采用忙等待I/O方式，當(dāng)CPU等待I/O操作完成時，進程不能繼

續(xù)執(zhí)行。對于I和n這兩種系統(tǒng)而言，執(zhí)行I/O操作時，系統(tǒng)不需要處理其他事

務(wù)，因此忙等待I/O方式是合適的。而對于網(wǎng)絡(luò)服務(wù)器而言，它需要處理網(wǎng)頁的

并發(fā)請求，需要CPU有并行處理的能力，忙等待I/O方式不適合這種系統(tǒng)。

33、一個信道每1/8s采樣一次，傳輸信號共有8種變化狀態(tài)，則最大數(shù)據(jù)傳輸率

是（）。

A、16bit/s

B、24bit/s

C、32bit/s

D、48bit/s

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

知識點解析：由每1/8s采樣一次可知，采樣頻率為8Hz。由采樣定理可知，采樣

頻率要大于等于有效信號最高頻率的兩倍，故信號頻率小于等于4Hz。其次，傳輸

信號共有8種變化狀態(tài)，由奈奎斯特定理可得：最大數(shù)據(jù)傳輸速率

=2Hlog2V=2x4xlog28bit/s=24bit/s,故選B選項。

34、下列協(xié)議中，不會發(fā)生碰撞的是（）。I.TDMH：.ALOHADI.CSMA

IV.CDMA

A僅

、I

B僅

、I、W

c僅

、I、U、w

D都

、

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

知識點解析：TDM、CDMA等都是屬于靜態(tài)劃分信道的方式，分別是時分復(fù)用和

碼分復(fù)用，不會發(fā)生碰撞。而像ALOHA、CSMA、CSMA/CD都是屬于動態(tài)的

隨機訪問協(xié)議，都采用了相應(yīng)的檢測碰撞的策略來應(yīng)對碰撞。

35、在二進制指數(shù)后退算法中，在16次碰撞之后，那么站點會在。?（）選擇一個

隨機數(shù)。

A、1023

B、215-1

C、216—1

D、以上都錯誤

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

知識點解析：總結(jié)：存二進制指數(shù)后退算法中，在N次碰撞之后，那么站點會在

0?M之間選擇一個隨機數(shù)，分以下3種情況討論。①當(dāng)仁NV10時，M=2N-1O

②當(dāng)10WNV15時，M=210-l=1023o③當(dāng)N=16,直接丟棄，并給計算機發(fā)送一

個錯誤報告。注：二進制指數(shù)后退算法縮短了站點檢測到?jīng)_突后繼續(xù)等待的時

間。

36、一個主機有兩個IP地址，一個地址是192.168.11.25,另一個地址可能是

nnn6n625

（）192.11.2.8.m.192.13.

o168.198.

IV.92I.?16n814.25

僅

A、n

僅I

B、、

口

僅M

、

、口

C僅w

D、、

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

知識點解析：在Intemel中允許一臺主機有兩個或兩個以上的IP地址，如果一臺主

機有兩個或兩個以上IP地址，說明這個主機屬于兩個或兩個以上的網(wǎng)絡(luò)。需要注

意的是，在同一時刻，一個合法的IP地址只能分配給一臺主機，否則就會引起IP

地址的沖突。而只有I和192.168.11.地屬于同一網(wǎng)絡(luò)（因為192開頭屬于C類

網(wǎng)絡(luò)，所以默認子網(wǎng)掩碼為255.255.255.0,故網(wǎng)絡(luò)號為前24位，例如

192.168.11.25的網(wǎng)絡(luò)號就是192.168.11.0）,其他都和192.168.11.25

屬于不同網(wǎng)絡(luò)，故選A選項。

37、因特網(wǎng)的RIP、（JSPF協(xié)議、BGP分別使用了（）路由選擇算法。I.路徑-向

量路由選擇協(xié)議n.鏈路狀態(tài)協(xié)議HI.距離.向量路由選擇協(xié)議

A、I、n、m

B、n>in、i

C、口、I、HI

D、田、ni

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

知識點解析：RIP即路由信息協(xié)議，OSPF協(xié)議即開放最短路徑優(yōu)先協(xié)議，BGP

即邊界網(wǎng)關(guān)協(xié)議。RIP和OSPF協(xié)議屬于內(nèi)部網(wǎng)關(guān)怖議，主要處理自治系統(tǒng)內(nèi)部的

路由選擇問題，BGP屬于外部網(wǎng)關(guān)協(xié)議，主要處理自治系統(tǒng)之間的路由選擇問

題。RIP、OSPF協(xié)議和BGP的特點如表8—5所示。

表84RIP.OSPF誨議和BGP的特點

RIP(fSPfBGP

內(nèi)信內(nèi)部

冊由K內(nèi)容II的同熔.K箝.II?IIW河絡(luò).FM.II的網(wǎng)絡(luò)，尤◎鵑櫛

■優(yōu)通法依第疑數(shù)6用UH

Wil例第伏態(tài)檢議孤護.向u處議

傳出方式從9幅UDPIP@**tfTCPiiW

效率A.

同牛.斷小《4也.

：鯉博3*QM

卬用?傳何M

38、如果IPv4的分組太大，則會在傳輸中被分片，那么分片后的數(shù)據(jù)報在（）地方

被重組。

A、中間路由器

B、下一跳路由器

C、核心路由器

D、目的端主機

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

知識點解析：數(shù)據(jù)報被分片后，每個分片都將獨立地傳輸?shù)侥康牡?，期間有可能會

經(jīng)過不同的路徑，而最后在目的端主機分組被重組。

39、下列說法中，錯誤的是（）。I.網(wǎng)絡(luò)上唯，標(biāo)識一個進程，需要一個服務(wù)端口

號即可n.路由器必須實現(xiàn)TCP,才能保證傳輸?shù)恼_性m.面向連接的數(shù)據(jù)傳

輸比面向無連接的數(shù)據(jù)為輸更快

A、僅I、n

B、僅口、皿

c、僅I、出

D、I、口、m

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

知識點解析：I：傳輸層提供應(yīng)用進程間的邏輯通信（即端到端的通信）。在傳輸

層，進程是用端門號來標(biāo)識的，而在網(wǎng)絡(luò)中IP地址可唯一標(biāo)識一臺主機，所以網(wǎng)

絡(luò)上唯一標(biāo)識一個進程首先要標(biāo)識是哪一個主機上的進程，故I錯誤。n：路由

器工作在網(wǎng)絡(luò)層，TCP的報文段只是封裝在網(wǎng)絡(luò)層的IP數(shù)據(jù)報中，作為其數(shù)據(jù)部

分,對路由器是不可見的，所以路由器不需要實現(xiàn)TCP,故II錯誤。n：面向連

接由于建立了一個虛鏈路，因此，每個數(shù)據(jù)分組可以省略源地址，減小了數(shù)據(jù)冗

余，這是速度增加的因素；但是，建立虛鏈路也要花費一定的時間，這是速度降低

的因素。因此，很難說二者速度誰快，故m錯誤。

40、域名系統(tǒng)DNS的組成包括（）。I.域名空間u.分布式數(shù)據(jù)庫m.域名服

務(wù)器IV.從內(nèi)部IP地址到外部IP地址的翻譯程序

A、僅I、n

B、僅I、n、m

c、僅口、出

D、I、口、m、w

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

知識點解析：因特網(wǎng)采用了層次樹狀結(jié)構(gòu)的命名方法，任何一個連接在因特網(wǎng)上的

主機或路由器，都有一個唯一的層次結(jié)構(gòu)的名字，即域名（DomainName）,故需要

有一個域名空間。這里，域（domain）是名字空間中一個可被管理的劃分。域還可以

維續(xù)劃分為子域，如二級域、三級域等。因特網(wǎng)的域名系統(tǒng)DNS被設(shè)計成一個聯(lián)

機分布式數(shù)據(jù)庫系統(tǒng)，并采用客戶機/服務(wù)器方式。DNS讓大多數(shù)名字都在本地

解析，僅少量解析需要在因特網(wǎng)上通信，因此系統(tǒng)效率很高。由于DNS是分布式

系統(tǒng)，即使單個計算機出了故障，也不會妨礙整個系統(tǒng)的正常運行。域名的解析是

由若干個域名服務(wù)器程序完成的，人們也常把運行該程序的機器稱為域名服務(wù)器。

域名系統(tǒng)DNS的組成不包括從內(nèi)部1P地址到外部【P地址的翻譯程序（這個是具有

NAT協(xié)議的路由器來實現(xiàn)的，和DNS沒有關(guān)系）。

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

分。）

給定的有7個頂點vl,v2,v7的有向圖的鄰接矩陣如表5-1所示。

表5“鄰接矩陣

co253ooooO0

co82OD8Rao

coODan13sao

X3OCDcm0?588

oo88ooCO39

<30CDODCDB85

B889ao8OO

41、畫出該有向圖。

標(biāo)準(zhǔn)答案：該有向圖如圖5-7所示。圖2”向圖

知識點解析：暫無解析

42、畫出其鄰接表。

標(biāo)準(zhǔn)答案：鄰接表如圖5-8所不。

W5-S鋁接表

知識點解析：暫無解析

43、從vl出發(fā)到其余各頂點的最短路徑長度。

標(biāo)準(zhǔn)答案；可使用迪杰斯特拉算法，進行模擬，如表5-5所示。陰影的部分為己求

出的最短距離。

表迪杰斯特拉Jt法程

■2*3v6

dlM2S3■■

dui—E鄧耀4310?■>

。'型簿8io

dot蝌藏瑞嬲踩網(wǎng)79oo

dutaG『手『16

■■■

dist煤啰^^祥那瘞鴕累屣靂灌整14

dist

1因此最

后得出的從vl出發(fā)到其余各頂點的最短路徑長度如表5—6所示。

費口

vlv2v3v5v6v7

disc0243?914

知識點解析：暫無解析

44、若將圖看成AOE網(wǎng)，列出其關(guān)鍵活動及相應(yīng)的有向邊Vi,i,w>,i、i為頂

點，w為權(quán)值，試問其關(guān)鍵路徑的長度是多少？

標(biāo)準(zhǔn)答案：表5-7中的陰影部分為最早發(fā)生時間二最晚發(fā)生時間的活動。

袤3

動：vl,v3,v4,v5,v7；相應(yīng)的有向邊：，，，：關(guān)鍵路徑的長度是20。補

充：求關(guān)鍵路徑的手動方法。求出每個事件的最早發(fā)生時間和最晚發(fā)生時間，求

解方法如下：①一個事件的最早發(fā)生時間為指向它的邊（設(shè)為a）的權(quán)值加上發(fā)出a

這條邊的事件的最早發(fā)生時間，若有多條，取最大值，把最大值的邊保留，其余邊

去除。②一個事件的最晚發(fā)生時間為由它發(fā)出的邊（設(shè)為b）所指向的事件的最遲發(fā)

生時間減去b這條邊的權(quán)值，若有多條，取最小者，把最小值的邊保留，其余邊去

除。然后找出最早發(fā)生時間和最遲發(fā)生時間相同的活動，即為關(guān)鍵活動；剩余的

邊都是組成關(guān)鍵路徑的邊。

知識點解析：暫無解析

輸入一個按升序排序過的整數(shù)數(shù)組｛1、2、4、7、11、15｝以及一個整數(shù)數(shù)字15,

可以從該數(shù)組中找到兩個數(shù)字，即4和11,使得4+11=15。請實現(xiàn)一個時間上盡

可能高效率的算法，輸入一個已經(jīng)按升序排序過的整數(shù)數(shù)組和一個整數(shù)數(shù)字，在數(shù)

組中查找兩個數(shù)，使得它們的和正好是輸入的那個整數(shù)數(shù)字。如果有多對數(shù)字的和

等于輸入的整數(shù)數(shù)字，輸出任意一對即可。要求：

45、給出算法的基本設(shè)計思想。

標(biāo)準(zhǔn)答案：基本設(shè)計思想：如果不考慮時間復(fù)雜度，最簡單的想法是先在數(shù)組中固

定一個數(shù)字，再依次判斷數(shù)組中剩下的n-1個數(shù)字與它的和是不是等于輸入的數(shù)

字?？上н@種思路需要的時間復(fù)雜度是0（/）,不滿足題意要求。假設(shè)現(xiàn)在隨便在

數(shù)組中找到兩個數(shù)，如果它們的和等于輸入的數(shù)字，則找到了要找的兩個數(shù)字；如

果小于輸入的數(shù)字呢，則希望兩個數(shù)字的和再大一點。當(dāng)兩個數(shù)字的和大于輸入的

數(shù)字的時候，把較大的數(shù)字往前移動，因為排在數(shù)組前面的數(shù)字要小一些，它們的

和就有可能等于輸入的數(shù)字了。把前面的思路整理一下：找到數(shù)組的第一個數(shù)字

和最后一個數(shù)字。當(dāng)兩個數(shù)字的和大于輸入的數(shù)字時，把較大的數(shù)字往前移動；當(dāng)

兩個數(shù)字的和小于數(shù)字時，把較小的數(shù)字往后移動；當(dāng)相等時，正合題意。

知識點解析：暫無解析

46、根據(jù)設(shè)計思想，采用C、C++或Java語言描述算法，關(guān)鍵之處給出注釋。

標(biāo)準(zhǔn)答案：算法實現(xiàn)如下：boolFind1'woNumbersWithSum(//以下都為

FindTwoNumberswithsuin函數(shù)的參數(shù)intdata|],//已排序的數(shù)組unsignedint

length,//己排序數(shù)經(jīng)的長度int&numl,//第一個數(shù)字int&num2,//第

二個數(shù)字intsum,//輸入的整數(shù)數(shù)字){boolfound=false；//空數(shù)組將會出

錯if(1ength<1)returnfound；intahead=length——1；intbehind=0；

while(ahead>behind){intcurSum=data[ahead]+data[behind]；//如果兩個數(shù)之和恰

好等于輸入的數(shù)字if(cu「Sum=sum){numl=data[bchind]；num2=data[ahcad]；

found=true；break；}//如果兩個數(shù)之和大于輸入的數(shù)字，將大的數(shù)字減小else

if(curSum>suin)ahead-；//如果兩個數(shù)之和小于輸入的數(shù)字，將小的數(shù)字加大

elsebehind十十；)returnfound；)

知識點解析：暫無解析

47、說明你所設(shè)計算法的時間復(fù)雜度。

標(biāo)準(zhǔn)答案：時間復(fù)雜度分析:在while的循環(huán)中,每次根據(jù)curSum和sum之間的

大小關(guān)系來決定是改變ahead還是改變behind。這個過程每次是0(1)的。在整個算

法流程中，因為ahead始終大于behind,如果一個數(shù)被ahead掃過了，那么它不會

被behind掃到，也不會被ahead再次掃到；同樣的，如果一個數(shù)被behind掃過

了，那么它將不會再被ahead或者behind掃到。所以循環(huán)最多執(zhí)行n—1次就會結(jié)

束.故整個算法的時間復(fù)雜度為O(n)c

知識點解析：暫無解析

在一個單總線結(jié)構(gòu)的計算機中，用一條總線連接了指令寄存器(IR)、程序計數(shù)器

(PC)、存儲器地址寄存器(MAR)、存儲器數(shù)據(jù)寄存器(MDR)、通用寄存器(rtk

r7),ALU輸入端寄存器(Y),ALU以及ALU輸出端寄存器(Z)。該計算機有以下指

令：ADDrl,r2,r3//(r2)+(r3)-rlJUMP#a//(pc)+Ha-^pcLOADrl,

1000m//mem[1000]->rlSTORErl,1000//(rl)->mem[1000]

48、畫出控制器執(zhí)行各指令的流程圖。

標(biāo)準(zhǔn)答案：注意：取指周期中的取指令過程所有指令都是一樣的。由題目所給的條

件可畫出控制器的流程圖，如圖5-9所示。

圖5-9控制需的流程()

知識點解析：暫無解析

49、為了處理出現(xiàn)無定義指令的異常情況，計算機中已增加了一個異常寄存器

(ER),連接在總線上。控制器在遇到未定義的指令操作碼時，將ER設(shè)置為1,然

后照常取下一條指令。減在控制器流程圖中增加這個異常處理的控制流程。

標(biāo)準(zhǔn)答案：增加異常處理的控制流程后，當(dāng)控制器在遇到未定義的指令操作碼時，

將ER設(shè)置為1,然后照常取下一條指令。因此可畫出控制器的流程圖如圖5-10所

示。圖務(wù)10控制器的流取《二》

知識點解析：暫無解析

50、上述情況卜，如何贊得無定義指令的異常情況得到操作系統(tǒng)的處理？

標(biāo)準(zhǔn)答案：為了使無定義指令的異常情況得到操作系統(tǒng)的處理，可以在硬件中使得

ER寄存器置1時產(chǎn)生一個內(nèi)部中斷?？刂破髟谧x取下一條指令之前先判斷中斷條

件，在有中斷請求發(fā)生時啟動中斷處理，即保存現(xiàn)場，根據(jù)中斷源