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

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

1、在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組表示中，以下算法的時(shí)間復(fù)雜度是0(1)的操作是

()oI.訪問(wèn)第i個(gè)結(jié)點(diǎn)(1V=iV=n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2V=iV=n)

n.在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)in.刪除第一個(gè)結(jié)點(diǎn)w.在第i個(gè)結(jié)點(diǎn)

后插入一個(gè)結(jié)點(diǎn)(1<=i<=n)

A僅

、I

B僅

、口、①

c僅

、I、n

D僅

、I、n、m

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

知識(shí)點(diǎn)解析：I：由于線性表是用數(shù)組表示，即順序存儲(chǔ)，可以直接通過(guò)結(jié)點(diǎn)編號(hào)

訪問(wèn)，所以I的時(shí)間復(fù)雜度一定是o(i)“n：由于是在最后一個(gè)結(jié)點(diǎn)處插入一個(gè)

結(jié)點(diǎn)，所以不需要移動(dòng)元素，故時(shí)間復(fù)雜度為o(i)。n：刪除第一個(gè)結(jié)點(diǎn)之后，

需要將后續(xù)所有結(jié)點(diǎn)往前移動(dòng)，所以時(shí)間復(fù)雜度為08)。IV：由于i是不固定

的，所以后續(xù)結(jié)點(diǎn)i+l,1+2,…，n—1,都需要向后移動(dòng)，所以時(shí)間復(fù)雜度為

O(n)o

2、中綴表達(dá)式a*(b+c)—d的后綴表達(dá)式是()。

A^abed+一

B、abc+d—

C、abc+d—

D^一+abed

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

|abc：?d-1

知識(shí)點(diǎn)解析：本題轉(zhuǎn)化過(guò)程如圖J5所示。圖45轉(zhuǎn)化過(guò)程示意圖由圖4-5可

以寫出以下轉(zhuǎn)化過(guò)程：第一步：b+c-bc+(假設(shè)x="bc+”)第二步：a*x-ax*(假

設(shè)丫=一**”)第三步：y-d->yd一將xy還原后得到：abc+*d一。補(bǔ)充知識(shí)點(diǎn)(1):

中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的另?種方式。解析：可以通過(guò)手工加上、除掉括

號(hào)來(lái)將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，其過(guò)程如下：先根據(jù)中綴表達(dá)式的求值次序

加上括號(hào)，將右括號(hào)用相應(yīng)的運(yùn)算符替換，再除掉所有的左括號(hào)。例如，中綴表

達(dá)式“5+2*(1+6)—8/2”轉(zhuǎn)換成后綴表達(dá)式的過(guò)程如不：手工判斷該表達(dá)式的計(jì)算過(guò)

程。首先肯定是先計(jì)算2*(1+6),加上括號(hào)變?yōu)椤?+(2*(1+6))—8/2”，再計(jì)算除法

8/2,加上括號(hào)變?yōu)椤?+(2*(1+6))—(8/2)”，接著進(jìn)行加法運(yùn)算，加上括號(hào)變?yōu)?/p>

“(5+(2*(1+6)))—(8/2)”,最后再進(jìn)行減法運(yùn)算，加上括號(hào)變?yōu)椤?(5+(2*(1+6)))一

(8/2))”。運(yùn)算符和右括號(hào)的對(duì)應(yīng)關(guān)系如圖4.6所示，將右括號(hào)用對(duì)應(yīng)的運(yùn)算符替

換，變?yōu)椤?(5(2(16+*+(82/—"，最后除掉所有左括號(hào)得到的后綴表達(dá)式為

“5216+*+82/—"。圖4石運(yùn)算符和右括號(hào)的對(duì)應(yīng)關(guān)系注：本方法需要人工判斷表達(dá)

式的執(zhí)行順序(即加括號(hào))，所以無(wú)法用程序?qū)崿F(xiàn)。一此方法引自李春葆老師的

書籍按照以上方式可以很輕松地解題，不妨試著將中綴表達(dá)式；(b+c)—d轉(zhuǎn)換成

后綴表達(dá)式。第一步：進(jìn)行乘法運(yùn)算，加括號(hào)變?yōu)椋?a*(b+c))—d0第二步：進(jìn)行

減法運(yùn)算，加括號(hào)變?yōu)椋?(a*(b+c))—d)。第三步：找出運(yùn)算符和右括號(hào)的對(duì)應(yīng)

關(guān)系，將右括號(hào)用對(duì)應(yīng)的運(yùn)算符替換，變?yōu)?(a[bc+*d—。第四步：最后除掉

所有左括號(hào)得到的后綴表達(dá)式為：abc+*d—。補(bǔ)充知識(shí)點(diǎn)(2):怎么將后綴表達(dá)式轉(zhuǎn)

換成中綴表達(dá)式？解析：當(dāng)遇到數(shù)值的時(shí)候入棧，當(dāng)遇到運(yùn)算符的時(shí)候，連續(xù)兩

次出棧，將兩個(gè)出棧元素結(jié)合運(yùn)算符進(jìn)行運(yùn)算，將結(jié)果當(dāng)成新遇到的數(shù)值入棧。如

此往復(fù)，直到掃描到終止符“\0”，此時(shí)棧底元素值即為表達(dá)式的值。例：將后綴

表達(dá)式xy+z+轉(zhuǎn)換為中綴表達(dá)式。先將x、y入棧，遇到了然后彈出棧頂?shù)?

個(gè)元素，即x、y,然后對(duì)x、y做加法，現(xiàn)在將(x+y)的值入棧，然后Z入棧，遇到

了操作符所以最后的中綴表達(dá)式為：(x+y)+z。注意：中綴表達(dá)式轉(zhuǎn)化成后綴

或者是前綴，結(jié)果并不一定唯一。比如ab+cd*+e/同樣是(a+b+c*d)/e的后綴式。后

綴式和前綴式都只有唯一的一種運(yùn)算次序，而中綴式卻不--定，后綴式和前綴式是

由中綴式按某一種運(yùn)算次序而生成的，因此對(duì)于一個(gè)中綴式可能有多種后綴式或者

前綴式。比如a+b+c可以先算a+b也可以先算b+c,這樣就有兩種后綴式與其對(duì)

應(yīng)，分別是ab+c+和abc++。例：下列關(guān)于后綴表達(dá)式的比較中，結(jié)果為“假”的是

()oI.xy+z+==xyz++H.xy+z—==xyz—+HI.xy—z+==xyz+—IV.xy—z—

==xyz-A.IB.I.HC.HI、WD.II、WC,本題考查后綴表達(dá)式。I：

xy+z+==xyz++轉(zhuǎn)換成中綴表達(dá)式為(x+y)+z==x+(y+z),比較結(jié)果為“真”。H：

xy+z—=xyz—+轉(zhuǎn)換成中綴表達(dá)式為(x+y)—z==x+(y—z),比較結(jié)果為“真

n；乂丫-2+==乂丫2+—轉(zhuǎn)換成中綴表達(dá)式為田一丫)+2==乂一“十2),比較結(jié)果為“假。

IV：xy—z—=—xyz-轉(zhuǎn)換成中綴表達(dá)式為(X—y)—z==x一(y—z),比較結(jié)果為

“假綜上所述，HI、W為假。

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

氤

A、輸出第i(隆iSn)個(gè)元素值

B、交換第I個(gè)元素與第2個(gè)元素的值

C、順序輸出這n個(gè)元素的值

D、輸出與給定值x相等的元素在線性表中的序號(hào)

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

知識(shí)點(diǎn)解析：順序表支持隨機(jī)存儲(chǔ)，鏈表不支持，因此順序表輸出第i個(gè)元素的值

的時(shí)間復(fù)雜度為0(1),鏈表則為0(n),因此A正確。交換第1個(gè)與第2個(gè)元素的

值，對(duì)于順序表和鏈表，時(shí)間復(fù)雜度均為0(1),因此B不對(duì)。輸出n個(gè)元素的

值，兩者時(shí)間復(fù)雜度均為O(n),因此C不對(duì).輸出與給定值x相等的元素在線性

表中的序號(hào)，對(duì)于順序表和鏈表，count需要搜索整個(gè)表，因此時(shí)間復(fù)雜度為

0(n),因此D不對(duì)?！咀ⅰ坑械耐瑢W(xué)認(rèn)為B也是正確的，其實(shí)嚴(yán)格來(lái)說(shuō)B確實(shí)是

對(duì)的，因?yàn)榫€性表交換要執(zhí)行3次操作：temp=a[l]；a[2]=temD；而鏈表要執(zhí)行

5次：p=head—>next；q=hcad—>next—>next；tcmp=p—>data；p->data=q—

>data；q—>data=temp；但本題是單選題的時(shí)候，考生需要選擇更準(zhǔn)確的一項(xiàng)，

顯然與B項(xiàng)相比，A項(xiàng)更準(zhǔn)確。

4、設(shè)k是中序線索二叉樹中一個(gè)有左子女的結(jié)點(diǎn)，旦k不是根結(jié)點(diǎn)，則k在中序

序列下的直接前驅(qū)結(jié)點(diǎn)是()。

A、k的左線索(指示中序前驅(qū))所指示的結(jié)點(diǎn)

B、從k父結(jié)點(diǎn)的左子女開始沿右子女鏈走到底的結(jié)點(diǎn)

C、從k的左子女開始沿右子女鏈走到底的結(jié)點(diǎn)

D、從k的左子女開始沿左子女鏈走到底的結(jié)點(diǎn)

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

知識(shí)點(diǎn)解析：如果k沒(méi)有左子女，則k的左指針即為指向k的中序前驅(qū)的線索；當(dāng)

k有左子女時(shí)，k的中序直接前驅(qū)結(jié)點(diǎn)是k的左子樹中中序的最后一個(gè)結(jié)點(diǎn)，即從

k的左子女開始沿右鏈走到右指針不再是右子女的結(jié)點(diǎn)為止，該結(jié)點(diǎn)即為k的中序

前驅(qū)結(jié)點(diǎn)。說(shuō)明：上述二叉樹的線索化算法其實(shí)考試中涉及的不多，本節(jié)在考試

中涉及最多的是，在選擇題中給你一棵二叉樹，讓你指出其中一個(gè)結(jié)點(diǎn)的線索按照

某種線索化方法所應(yīng)該指向的結(jié)點(diǎn)。例如：請(qǐng)畫出圖4-7中按照中序線索化方法

A

線索化后E結(jié)點(diǎn)的右線索的接連情況。圖4-8右線索指向A結(jié)點(diǎn)解決這類題

的方法為，先寫出題目所要求的遍歷方式下的結(jié)點(diǎn)訪問(wèn)序列，根據(jù)此序列找出題目

要求中結(jié)點(diǎn)的前驅(qū)和后繼，然后連接線索。圖4—7中二叉樹的中序遍歷序列為

D,B,E,A,Co結(jié)點(diǎn)E的前驅(qū)為B,后繼為A,因此其右線索應(yīng)該指向A,結(jié)

果如圖4—8所示?？偨Y(jié)：（1）引入二叉線索樹的目的：加快查找結(jié)點(diǎn)的前驅(qū)或后

繼的速度。（2）二叉樹在線索化后，仍不能解決的問(wèn)題：后序線索二叉樹中求后序

后繼。（3）n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索樹為：n+1。

5、假定一組元素序列為｛38,42,55,15,23,44,34,74,45,26）,按次序插

入每個(gè)元素生成一棵平衡二叉樹，那么最后得到的平衡二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)

為（）。

A、1

B、3

C、4

D、5

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

知識(shí)點(diǎn)解析：根據(jù)題目所給的元素序列，可以得到以下的平衡二叉樹，如圖14—9

6、由23、12、45、36構(gòu)成的二叉排序樹有（）個(gè)，其中AVL樹有（）個(gè)。

A、13；4

B、13；5

C、14；5

D、14；4

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

知識(shí)點(diǎn)解析：該題的結(jié)點(diǎn)不多，可以采用枚舉法。但枚舉法比較容易造成遺漏，所

以在枚舉時(shí)要按照一定的規(guī)律，而且在枚舉完之后看是否有重合的樹并將其去掉，

為避免重復(fù)可以采用根結(jié)點(diǎn)來(lái)枚舉，枚舉得二義排序樹共有14個(gè)，其中5個(gè)為

AVL樹。

7、對(duì)圖4-1進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是()。

圖4J

A、4

B、3

C、2

D、1

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

知識(shí)點(diǎn)解析：尋找拓?fù)渑判虻牟襟E：(1)在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)并且輸

出。(2)從圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均

已輸出。由于沒(méi)有前驅(qū)的頂點(diǎn)可能不唯一，所以拓?fù)渑判虻慕Y(jié)果也不唯一。題中

所給圖有3個(gè)不同的拓?fù)渑判蛐蛄?，分別為：l)a,b,c,e,do2)a,b,e,

c,do3)a,e?b,c?do

8、無(wú)向圖G有*16條邊，有3個(gè)度為4的頂點(diǎn)，4個(gè)度為3的頂點(diǎn)，其余頂點(diǎn)的度

均小于3,則G至少有()個(gè)頂點(diǎn)。

A、10

B、11

C、12

D、13

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

知識(shí)點(diǎn)解析：度的定義指的是進(jìn)入一個(gè)頂點(diǎn)的邊數(shù)和從該頂點(diǎn)出去的邊數(shù)之和。我

們可以根據(jù)這個(gè)關(guān)系來(lái)求解此題。由于題目已經(jīng)告訴度為4的頂點(diǎn)有3個(gè)，度為3

的頂點(diǎn)有4個(gè),其余的頂點(diǎn)的度均小于3?而已知有16條邊,則總的度數(shù)應(yīng)為

16x2=32。所以要求最小的頂點(diǎn)個(gè)數(shù)，我們應(yīng)當(dāng)盡量增加每個(gè)頂點(diǎn)的度數(shù)，這里將

剩下的結(jié)點(diǎn)的度數(shù)全部看成2,設(shè)結(jié)點(diǎn)數(shù)為x,貝I」3x4+4x3+(x—3-4)x2232,解得

x至少為11。補(bǔ)充：解這題的過(guò)程中，我們是從假設(shè)剩下的結(jié)點(diǎn)的度數(shù)為2來(lái)考

慮的，這樣才能最大程度地減小結(jié)點(diǎn)的個(gè)數(shù)。這其實(shí)用到了一種稱為貪心的思想，

這是一種很重要的思想，每次決策的時(shí)候都是按照最有利的情況去考慮。這種思想

在其他幾門課程當(dāng)中也會(huì)有體現(xiàn)，讀者應(yīng)自己去發(fā)現(xiàn)和總結(jié)。

9、以下有關(guān)m階B—樹的說(shuō)法中正確的有（）。I.每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹

n.樹中每個(gè)結(jié)點(diǎn)至多有m—1個(gè)關(guān)鍵字in.所有葉子在同一層上w.當(dāng)插入一

個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)—樹結(jié)點(diǎn)分裂后，樹長(zhǎng)高一層

A、僅I、n

B、僅口、m

C＞僅川、IV

D、僅I、口、IV

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

知識(shí)點(diǎn)3析：I中：m階B—樹根結(jié)點(diǎn)至少有兩棵子樹，并且這兩顆子樹可以是空

樹，其余結(jié)點(diǎn)至少有［m⑵個(gè)分支，即［m/2］個(gè)子樹，所以I錯(cuò)誤。補(bǔ)充：B—樹中

每個(gè)結(jié)點(diǎn)至多有m棵子樹，m—1個(gè)關(guān)鍵字值。II中：每個(gè)結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)比

分支數(shù)少1,m階B—樹的一個(gè)結(jié)點(diǎn)中至多有m個(gè)分支，因此至多有m—1個(gè)關(guān)鍵

字，所以D正確。HI中：B—樹是平衡的多路查找樹，葉子結(jié)點(diǎn)均在同一層上，所

以in正確。w中：發(fā)生結(jié)點(diǎn)分裂的時(shí)候不一定會(huì)使樹長(zhǎng)高。比如向圖4—10中的

B—樹插入一個(gè)關(guān)鍵字10變成圖4-11中的B—樹，使得第二層右端的一個(gè)結(jié)點(diǎn)分

圖4-10B-樹

圖4-11插入一個(gè)關(guān)鍵字后的B-樹

裂成兩個(gè)，但是樹并沒(méi)有長(zhǎng)高，所以W錯(cuò)誤。綜

上所述，口、in正確。

10、對(duì)以下關(guān)鍵字序列用快速排序進(jìn)行排序，速度最慢的是（）。

A、{19,23,3,15,7,21,28}

B、{23,21,28,15,19,3,7}

C、{19,7,15,28,23,21,3）

D、{3,7,15,19,21,23,28）

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

知識(shí)點(diǎn)解析：這種題目其實(shí)就是考查考生的記憶能力，因?yàn)樵诳佳芯o張的氛圍下，

很少有考生在做這種選擇題的時(shí)候能夠分析其算法來(lái)選擇答案。這里就是變相地考

查快速排序算法的最壞情況?？焖倥判蚍ǖ淖顗那闆r為待排序列是有序或接近有序

的時(shí)候，由于D中元素已經(jīng)有序，所以選擇D。評(píng)注：本題是指定了使用某種排

序方法，當(dāng)題目中沒(méi)有指定具體的排序方法的時(shí)候，我們--定不要急于挨個(gè)用每個(gè)

算法去試，而應(yīng)該從所給的待排序列出發(fā)，觀察序列元素的信息，找出某種特殊的

性質(zhì)。

11、某個(gè)文件經(jīng)內(nèi)部排序得到80個(gè)初始?xì)w并段。如果操作系統(tǒng)要求一個(gè)程序同時(shí)

可用的輸入/輸出文件的總數(shù)不超過(guò)15個(gè)，則按多路歸并至少需要（）趟可以完成排

序。

A、2

B、3

C、4

D、5

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

知識(shí)點(diǎn)露析：不妨設(shè)采用m路歸并，則至少需要m個(gè)輸入緩沖區(qū)和1個(gè)輸出緩沖

區(qū)。因?yàn)橐粋€(gè)緩沖區(qū)對(duì)應(yīng)一個(gè)文件，所以m+l=15,解得m=14,所以可做14路歸

并。假設(shè)需要s趟可以完成排序，則s=[logi480]=2。

12、考慮以下C語(yǔ)言代碼：vcshortsi=一8196；unsingnedshortusi=si；執(zhí)行上述

程序段后，usi的值為（）。

A、8196

B、34572

C、57339

D、57340

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

知識(shí)點(diǎn)解析：首先，求得一8196的補(bǔ)碼表示為1】01II1111111100,賦值給

usi后，由于usi為無(wú)符號(hào)數(shù)，所以將二進(jìn)制1101111111111100轉(zhuǎn)換為十進(jìn)制為

57340o技巧：FFFFH的二進(jìn)制應(yīng)該記住，為65535。然后減去3個(gè)0對(duì)應(yīng)的權(quán)

值，分別為8192、2、1,即最后的結(jié)果為65535—8192—2—1=57340。

13、設(shè)浮點(diǎn)數(shù)的階碼用移碼表示，尾數(shù)用補(bǔ)碼表示，階碼的底數(shù)為2,階碼用3位

表示（包含一位符號(hào)位），尾數(shù)用5位表示（包含1位符號(hào)位），則它能表示的最

小負(fù)數(shù)為（）。

A、—8

B、—7.5

C、—128

D、—256

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

知識(shí)點(diǎn)解析：要求最小負(fù)數(shù)，按照浮點(diǎn)數(shù)的格式來(lái)看，我們要盡量使尾數(shù)最小，達(dá)

到補(bǔ)碼所能表示的最小的負(fù)數(shù)，另外還要使階碼最大，達(dá)到移碼所能表示的最大整

數(shù)，而由補(bǔ)碼的性質(zhì)可知，無(wú)論對(duì)于尾數(shù)多少位來(lái)說(shuō)，尾數(shù)的最小值永遠(yuǎn)是一1,

階碼最大為3。故最小的負(fù)數(shù)為一8。

14、硬盤平均尋道時(shí)間為12ms,傳輸速率為10MB/S,磁盤控制器延時(shí)為2ms,則

一個(gè)轉(zhuǎn)速為7200r/min的硬盤寫1KB數(shù)據(jù)的時(shí)間為[）。

A、13.11ms

B、14.13ms

C>15.15ms

D、18.27ms

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

知識(shí)點(diǎn)解析：首先，需要判斷1KB數(shù)據(jù)是否需要存儲(chǔ)到多個(gè)磁道上。

lOMB/s1…

----------=—MB；s

7200r/min=120r/s；因?yàn)閭鬏斔俾蕿閘OMB/s,故每轉(zhuǎn)容量為：120r/s12,

所以1KB的數(shù)據(jù)只要在一個(gè)磁道上就能存儲(chǔ)下了，無(wú)須換道。其次，寫數(shù)據(jù)時(shí)間:

磁盤啟動(dòng)時(shí)間+磁盤尋道時(shí)間+旋轉(zhuǎn)等待時(shí)間+數(shù)據(jù)傳輸時(shí)間。旋轉(zhuǎn)等待時(shí)間為：旋

轉(zhuǎn)半圈的時(shí)間，及（60/7200）x1/2=4.17ms；數(shù)據(jù)傳輸時(shí)間等于lKB/10MB/s=0.1ms,

所以寫1KB數(shù)據(jù)的時(shí)間為：2ms+12ms+4.17ms+0.1ms=18.27ms?？赡芤蓡?wèn)點(diǎn)：

《計(jì)算機(jī)網(wǎng)絡(luò)高分筆記》不是說(shuō)在通信領(lǐng)域K取1000,在計(jì)算機(jī)領(lǐng)域K取1024

嗎？此道題目中1KB應(yīng)該是屬于計(jì)算機(jī)領(lǐng)域，為什么取值1000?解析：《計(jì)算機(jī)

網(wǎng)絡(luò)高分筆記》給出的是最一般的理解的方式，不是絕對(duì)的。至于K到底取多

少，至今沒(méi)有統(tǒng)一標(biāo)準(zhǔn)。筆者根據(jù)經(jīng)驗(yàn)總結(jié)出兩點(diǎn)：（1）如果在考試中遇到，K取

多少，就看約分，考研的答案一定是最簡(jiǎn)化的，肯定可以約分，哪個(gè)好約分取哪

個(gè)。如果分子和分母都有K那就最好了。（2）如果實(shí)在不放心，可以參考教育部針

對(duì)真題的解釋，看看他們?nèi)≈刀嗌伲罩〖纯伞?/p>

15、下面關(guān)于各種存儲(chǔ)器的說(shuō)法中，正確的有（）。I.靜態(tài)RAM不是易失性存儲(chǔ)

器，而動(dòng)態(tài)RAM是易矢性存儲(chǔ)器D.PROM只能寫錄一次HI.EPROM是可改寫

的，并且也是隨機(jī)存儲(chǔ)器的一種W.EEPROM存儲(chǔ)器是可寫存儲(chǔ)器

A、僅I、D

B、僅口、W

c、僅I、u、m

D、僅口、m、w

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

知識(shí)點(diǎn)解析：I：靜態(tài)RAM和動(dòng)態(tài)RAM都是易失性存儲(chǔ)器，斷電后信息都會(huì)遺

失，所以I錯(cuò)誤。n：PROM的內(nèi)部有行列式的熔絲，視需要利用電流將其燒斷，

寫入所需的資料，但僅能寫錄一次。PROM在出廠時(shí)，存儲(chǔ)的內(nèi)容全為1,用戶可

以根據(jù)需要將其中的某些單元寫入數(shù)據(jù)0（部分的PROM在出廠時(shí)數(shù)據(jù)全為0,則

用戶可以將其中的部分單元寫入1）,以實(shí)現(xiàn)對(duì)其“編程''的目的，所以II正確。

n：EPROM是可改寫的，但它不屬于隨機(jī)存儲(chǔ)器，所以HI錯(cuò)誤。IV：EEPROM

（ElectricallyErasableProgrammableRead-OnlyMemory）,電可擦可編程只讀存

儲(chǔ)器，屬于一種掉電后數(shù)據(jù)不丟失的存儲(chǔ)芯片。EEPROM可以在計(jì)算機(jī)上或?qū)Ｓ?/p>

設(shè)備上擦除已有信息，重新編程，所以W正確。

16、一個(gè)Cache—主存系統(tǒng)，采用50MHz的時(shí)鐘，存儲(chǔ)器以每一個(gè)時(shí)鐘周期傳輸

一個(gè)字的速率，連續(xù)傳輸8個(gè)字，以支持塊長(zhǎng)為8個(gè)字的Cache,每個(gè)字4個(gè)字

節(jié)。假設(shè)讀操作所花的時(shí)間是：1個(gè)周期接受地址，3個(gè)周期延遲，8個(gè)傳輸周期

傳輸8個(gè)字；寫操作所花的時(shí)間是：I個(gè)周期接受地址，2個(gè)周期延遲，8個(gè)周期

傳輸8個(gè)字，3個(gè)周期恢復(fù)和寫入糾錯(cuò)碼，則當(dāng)系統(tǒng)以35%為讀操作，65%為寫操

作的訪問(wèn)情況工作，則存儲(chǔ)器最大帶寬為()。

A、133.2MB/S

B、114.4MB/S

C、126MB/S

D、120.3MB/s

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

知識(shí)點(diǎn)解析：題目很長(zhǎng)，首先需要弄清題目的意思。題目告訴了時(shí)鐘周期、速率以

及讀和寫操作各自花的時(shí)鐘周期數(shù)，所要求的是存儲(chǔ)器的最大帶寬，也就是單位時(shí)

間內(nèi)傳輸?shù)挠行畔⒘?。?jì)算過(guò)程如下：讀操作的時(shí)間為TF(l+3+8)x20ns=240ns

寫操作的時(shí)間為Tw=(1+2+8+3)x20ns=280ns則綜合加權(quán)的時(shí)間為

240nsx0.35+280nsx0.65=266ns帶寬為(也就是266ns可以傳輸8個(gè)字，或者說(shuō)傳輸

32B)Bn=32B/(266x10-9S)-120.3MB/s

17、以下是一段指令序列：laddiRI,20(Rl)*-202lwR2,RO,12

(R2)<-M(12+(R0))3addR3,RI,R2(R3)—(R1)+(R2)以上指令序列中,假定采用

“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫回”這種五段流水線方式，那么在采用“轉(zhuǎn)發(fā)”

技術(shù)時(shí)，需要在第3條指令之前至少加入()條空操作(nop)指令，才能使這段程序

不發(fā)生數(shù)據(jù)冒險(xiǎn)。

A、0

B、1

C、2

D、3

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

知識(shí)點(diǎn)解析：通過(guò)觀察這三條指令發(fā)現(xiàn)，第一、二條指令與第三條指令存在寫后讀

的數(shù)據(jù)冒險(xiǎn)，也就是說(shuō)有可能在第一、二條指令執(zhí)行結(jié)束后還沒(méi)來(lái)得及將最終的結(jié)

果存入寄存器R1和R2中，第三條指令就開始直接讀取寄存器R1和R2中的內(nèi)

容。于是為了防止出現(xiàn)數(shù)據(jù)冒險(xiǎn)，在執(zhí)行第三條指令之前至少應(yīng)加入一條空操作來(lái)

保證取R1和R2中內(nèi)容的滯后性。

18、某計(jì)算機(jī)采用微程序控制，微指令字中操作控制字段共12位，下列說(shuō)法正確

的是()。I.若采用直接控制，則此時(shí)一條微指令最多可同時(shí)啟動(dòng)11個(gè)微操作

n.若采用字段直接編碼控制，并要求一條微指令需同時(shí)啟動(dòng)3個(gè)微操作，則微指

令字中的操作控制字段應(yīng)分6段in.若采用字段直接編碼控制，并要求一條微指

令需同時(shí)啟動(dòng)3個(gè)微操作，每個(gè)字段的微命令數(shù)相同，這樣的微指令格式最多可包

含45個(gè)微操作命令

A、僅I、n

B、僅I、m

c、僅口、也

D、I、II和m

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

知識(shí)點(diǎn)解析：對(duì)于I選項(xiàng)：如果12個(gè)微操作都是相容的話，可以最多同時(shí)啟動(dòng)12

個(gè)微操作，故I正確。對(duì)于n選項(xiàng)：首先，如果要同時(shí)啟動(dòng)3個(gè)微操作，那么這3

個(gè)微操作必須是相容的，所以要將控制字段分為3段，也就是每段占4位，故口錯(cuò)

誤。對(duì)于ID選項(xiàng)：由II的分析可知，由于每段占4位，每個(gè)字段可表示15種狀態(tài)

（保留一個(gè)狀態(tài)表示不發(fā)微命令），那么一共就可以表示45個(gè)狀態(tài)，故IE正確。

19、一條雙字長(zhǎng)直接尋址的子程序調(diào)用CALL指令，其第一個(gè)字為操作碼和尋址

特征，第二個(gè)字為地址碼5000H。假設(shè)PC（程序L數(shù)器）當(dāng)前值為1000H,SP的

內(nèi)容為0160H,棧頂內(nèi)容為1234H,存儲(chǔ)器按字編址，而且進(jìn)棧操作是先（SP）

1-SP,后存入數(shù)據(jù)。則CALL指令執(zhí)行后，SP及棧頂?shù)膬?nèi)容分別為（）。

A、OOFFH,1000H

B、0101H,1000H

C、OOFEH,1002H

D、OOFFH,1002H

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

知識(shí)點(diǎn)解析：當(dāng)子程序調(diào)用CALL指令時(shí)，首先需要將程序斷點(diǎn)（PC的值）保存

在堆棧中，然后將CALL指令的地址碼送入PC。因?yàn)橹噶顬殡p字長(zhǎng)，所以取出

CALL指令后，PC的值需要加2,即1002H。當(dāng)CALL指令執(zhí)行后，程序斷點(diǎn)

1002H進(jìn)棧，此時(shí)SP=OOFFH（因?yàn)檫M(jìn)棧操作需要將SP的值減1,即0100H—

0001H=00FFH）,棧頂內(nèi)容為1002H。

20、指令流水線將一條指令的執(zhí)行過(guò)程分為4步，其中第1、2和4步的執(zhí)行時(shí)間

為Z,如圖4—2所示。若該流水線順序執(zhí)行50條指令共用了203At（無(wú)需考慮相

關(guān)問(wèn)題），則該流水線的第3步的執(zhí)行時(shí)間是（）。

------1------2——3—4——

AtAtAt

圖4-2條指令的執(zhí)行過(guò)程

A、3At

B、4At

C、5At

D、6At

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

知識(shí)點(diǎn)解析：根據(jù)題意可以看到，在此流水線中順序執(zhí)行50條指令用了203%（正

常情況下如果第3步的執(zhí)行時(shí)間為人，則執(zhí)行50條指令只需要4+（50-

l）xAt=53Al）,所以流水線的瓶頸必定是第3步。補(bǔ)充：對(duì)于包含瓶頸段的指令流

水線，不妨設(shè)流水線共有k段，且需要執(zhí)行n條指令，則總的執(zhí)行時(shí)間為

￡i=ikAti+（n—l）max{Ati，At2，...?Atk}根據(jù)上述公式，假定流水線中第3步的

執(zhí)行時(shí)間為S,該指令流水線順序執(zhí)行50條指令所用的時(shí)間為：△"△1+S+ZU+

（50—1）max{At,At,S,At}=203At,解得S=4AI,即第3步的執(zhí)行時(shí)間為

4Ato

21、某總線總共有88根信號(hào)線，其中數(shù)據(jù)總線為32bil,地址總線為20bit,控制

總線為36根，總線的工作頻率為66MHz，則總線寬度為（），傳輸速率為（）。

A、32bit264MB/S

B、20bit264MB/S

C、32bit254MB/S

D、20bit264MB/S

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

知識(shí)點(diǎn)解析：需要清楚的是，總線的寬度不是地址總線的位數(shù)，也不是控制總線的

位數(shù)，而是數(shù)據(jù)總線的位數(shù)，所以此題總線的寬度應(yīng)該是32bit。而總線的傳輸速

率為總線的工作頻率乘以總線寬度，即66N4Hzx32bit=66MHzx4B=264MB/s.

22、指令（）從主存中讀出。

A、總是根據(jù)程序計(jì)數(shù)器（PC）

B、有時(shí)根據(jù)PC,有時(shí)根據(jù)轉(zhuǎn)移指令

C、根據(jù)地址寄存器

D、有時(shí)根據(jù)PC,有時(shí)根據(jù)地址寄存器

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

知識(shí)點(diǎn)露析：指令總是艱據(jù)程序計(jì)數(shù)器（PC）從主存中讀出（這一點(diǎn)一定要記住）。

可能考生會(huì)想到無(wú)條件轉(zhuǎn)移指令的情況，認(rèn)為不一定總是根據(jù)PC讀出。實(shí)際_L,

正確的執(zhí)行順序是這樣的，當(dāng)前指令正在執(zhí)行時(shí)，其實(shí)PC已經(jīng)是下一條指令的地

址了，如果遇到了無(wú)條,牛轉(zhuǎn)移指令，則只需要簡(jiǎn)單地把跳轉(zhuǎn)的地址覆蓋PC的內(nèi)容

就可以了，最終的結(jié)果還是指令需要根據(jù)PC從主存讀出。

23、在操作系統(tǒng)中，用戶在使用I/O設(shè)備時(shí)，通常采用（）。

A、物理設(shè)備名

B、邏輯設(shè)備名

C、虛擬設(shè)備名

D、設(shè)備序號(hào)

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

知識(shí)點(diǎn)解析：設(shè)備管理通常將邏輯設(shè)備和物理設(shè)備分開，邏輯設(shè)備是用戶使用的。

系統(tǒng)設(shè)置了一張邏輯設(shè)備表，用于將應(yīng)用程序中所使用的邏輯設(shè)備名映射為物理設(shè)

備名。

24、考慮下面的基于動(dòng)杰改變優(yōu)先級(jí)的可搶占式優(yōu)先權(quán)調(diào)度算法。大的優(yōu)先權(quán)數(shù)代

表高優(yōu)先級(jí)。當(dāng)一個(gè)進(jìn)程在等待CPU時(shí)（在就緒隊(duì)列中，但未執(zhí)行），優(yōu)先權(quán)以

a速率改變；當(dāng)它運(yùn)行時(shí)，優(yōu)先權(quán)以p速率改變。所有的進(jìn)程在進(jìn)入就緒隊(duì)列被給

定優(yōu)先權(quán)數(shù)為0。參數(shù)a和p可以設(shè)定給許多不同的調(diào)度算法。下列（）設(shè)定可以實(shí)

現(xiàn)進(jìn)程FIFO（FirstInFirstOut）。

A、p>a>0

B、a>p>0

C、p<a<0

D、a<p<0

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

知識(shí)點(diǎn)解析：假設(shè)進(jìn)程M先于進(jìn)程N(yùn)進(jìn)入就緒隊(duì)列。PM和PN分別表示M和N

的優(yōu)先權(quán)數(shù)。在0>a>O設(shè)定下，在就緒隊(duì)列中，PM>PN,原因是a>0,貝］越

早進(jìn)入就緒隊(duì)列，優(yōu)先數(shù)就越大,所以是FCFS(FirstComeFirstService)。又因?yàn)?/p>

P>a,所以在M運(yùn)行時(shí)，PM增長(zhǎng)速度大于PN的增長(zhǎng)速度，則PM>PN,從而保

證了M進(jìn)程先于N進(jìn)程完成，即FIFO(FirstInFirstOut)?在a>p>0設(shè)定下，還

是FCFS,原因跟p>a>0—樣。但由于a>p,所以在M運(yùn)行時(shí)，無(wú)法保證PM

仍然大于PN,即無(wú)法保證FIFO。在pVaVO設(shè)定下，在就緒隊(duì)列中，PM<PN,

原因是aVO,則越早進(jìn)入就緒隊(duì)列，優(yōu)先數(shù)就越小，所以是LCFS(LastComeFirst

Service)o又因?yàn)?<a,,所以在N運(yùn)行時(shí)，PN下降速度大于PM的下降速度，

有可能出現(xiàn)PM>PN的情況，此時(shí)CPU就有可能被M搶占，無(wú)法保證LIFO(Last

InFirstOut)o在aV0VO設(shè)定下，還是LCFS,原因跟pVaVO一樣。但由于aV

P，在N運(yùn)行時(shí)，PN的下降速度變慢了，從而保證了PN始終大于PM,導(dǎo)致N進(jìn)

程先于M進(jìn)程完成，即LIFO。所以本題的答案選A。本題通過(guò)對(duì)a、［3的設(shè)置實(shí)

現(xiàn)更多的調(diào)度方式，有興趣的同學(xué)可以再思考下，比如aVaV|3的情況等。

25、假設(shè)系統(tǒng)有5個(gè)進(jìn)程，A、B、C三類資源。某時(shí)刻進(jìn)程和資源狀態(tài)如表4—1

所示。下面敘述正確的是()。

表4-1某時(shí)刻進(jìn)程和資源狀態(tài)

AllocationMaxAvailable

ABcABCABC

PI212559233

P24025-36

P340540!l

P4204425

P5314424

A^系統(tǒng)不安全

B、該時(shí)刻，系統(tǒng)安全，安全序列為VP1,P2,P3,P4,P5>

C、該時(shí)刻，系統(tǒng)安全，安全序列為VP2,P3,P4,P5,Pl>

D、該時(shí)刻，系統(tǒng)安全，安全序列為VP4,P5,Pl,P2,P3>

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

知識(shí)點(diǎn)解析：當(dāng)Available為(2,3,3)時(shí)，可以滿足P4、P5中任意一個(gè)進(jìn)程的需

求；這兩個(gè)進(jìn)程結(jié)束后釋放資源，Available為(7,4,11),此時(shí)可以滿足P1、

P2、P3中任意?個(gè)進(jìn)程的需求，所以該時(shí)刻系統(tǒng)處于安全狀態(tài)，安全序列中只有

D選項(xiàng)滿足條件。

26、設(shè)有一個(gè)發(fā)送者進(jìn)程和接收者進(jìn)程，其流程圖如圖4—3所示。S是用于實(shí)現(xiàn)

進(jìn)程同步的信號(hào)量，mutex是用于實(shí)現(xiàn)進(jìn)程互斥的信號(hào)量。試問(wèn)流程圖中的A、

B、C、D4個(gè)框中應(yīng)填寫什么？假定緩沖區(qū)有無(wú)限多個(gè)且初始為空，S和mutex的

初值應(yīng)該是什么？()

圖4-3發(fā)送者進(jìn)程和接收者進(jìn)程的流程圖

A、P(mutex)、V(mutex)、P(S)^P(mutex)S=緩沖區(qū)的個(gè)數(shù)mutex=l

B、P(S)、V(mutex)sP(S)、P(mutcx)S=0mutcx=l

C、P(mutex)、V(mutex)、P(S)、P(mutex)S=0mutex=l

D、P(S)、V(mulex)、P(S)、P(mutcx)S=緩沖區(qū)的個(gè)數(shù)mutex=O

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

知識(shí)點(diǎn)解析：流程圖中的A、B、C、D4個(gè)框中分別應(yīng)該填寫：P(mutex).

V(mutex)>P(S)、P(mutex)或者P(mutex)、V(mutexKP(mutex)、P(S)。首先應(yīng)該明

確這里的緩沖區(qū)是臨界資源，所以“把緩沖區(qū)放到信息鏈尾''和"從緩沖區(qū)中取出消

息”是互斥的。在操作前都要，P(mutex),成功的P操作后，進(jìn)入臨界區(qū)，退出時(shí)

V(mutex),又mutex作為互斥信號(hào)量，初值應(yīng)為1。S作為同步信號(hào)量，發(fā)送者進(jìn)

程發(fā)送完信息后進(jìn)行V(S),表示信號(hào)鏈中信息的個(gè)數(shù)增加1,作為接收者進(jìn)程必須

有相應(yīng)的表示取走信息的P(S)操作。S是資源信號(hào)量，是用來(lái)表示信號(hào)鏈中信息的

個(gè)數(shù)，其初值要根據(jù)進(jìn)程的初始狀態(tài)確定，這里初始為空，所以其初值應(yīng)設(shè)置為

Oo知識(shí)點(diǎn)回顧：解決進(jìn)程同步和互斥問(wèn)題的求解步驟：1)先要確定哪些操作是

并發(fā)的，確定哪些操作是互斥的。并發(fā)操作可以用多個(gè)進(jìn)程實(shí)現(xiàn)，同步和互斥就發(fā)

生在這多個(gè)進(jìn)程之間。多個(gè)進(jìn)程操作同一臨界資源就是進(jìn)程間的互斥問(wèn)題。多個(gè)進(jìn)

程要按一定的順序操作就是進(jìn)程間的同步問(wèn)題。2)每道題都指定了互斥和同步的

規(guī)則，從中提煉出正確的操作條件，從而確定互斥和同步的操作流程。3)根掂互

斥和同步規(guī)則以及操作流程確定信號(hào)量的個(gè)數(shù)和每個(gè)信號(hào)量表示的含義，只有確切

地知道信號(hào)量所代表的含義，設(shè)置這個(gè)信號(hào)量才有意義。4)同步信號(hào)量的初值要

根據(jù)進(jìn)程的初始狀態(tài)確定，具體問(wèn)題具體分析，沒(méi)有統(tǒng)一的方法。互斥信號(hào)量的初

值通常是1。5)根據(jù)同步、互斥規(guī)則和每個(gè)進(jìn)程的操作流程可以確定P、V操作的

位置。需要說(shuō)明的是，無(wú)論是互斥問(wèn)題還是同步問(wèn)只要是需要進(jìn)程進(jìn)入阻塞狀

態(tài)，就必須想到在什么時(shí)候?qū)⑦M(jìn)程喚醒。提示：同步進(jìn)程之間具有某種合作關(guān)

系，如在執(zhí)行時(shí)間上必須按一定的順序協(xié)調(diào)運(yùn)行，或者共享某種資源?；コ膺M(jìn)程彼

此在邏輯上完全無(wú)關(guān)，它們的運(yùn)行不具有次序的特征。

27、考慮在一個(gè)虛擬頁(yè)式存儲(chǔ)管理的系統(tǒng)中，在地址變換過(guò)程中，進(jìn)程狀態(tài)可能發(fā)

生的變化有()。I.進(jìn)程被撤銷U.進(jìn)程變?yōu)樽枞?/p>

A、I

B、n

c＞i和n

D、都不可能

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

知識(shí)點(diǎn)。析：當(dāng)本次訪問(wèn)地址超越進(jìn)程的地址空間時(shí)，該進(jìn)程被撤銷，屬于異常結(jié)

束。在產(chǎn)生缺頁(yè)中斷及處理過(guò)程中，該進(jìn)程變?yōu)樽枞麪顟B(tài)，所以選C。

28、在虛擬分頁(yè)存儲(chǔ)管理系統(tǒng)中，若進(jìn)程訪問(wèn)的頁(yè)面不在主存，且主存中沒(méi)有可用

的空閑幀時(shí)，系統(tǒng)正確的處理順序?yàn)?)。

A、決定淘汰頁(yè)一＞頁(yè)面調(diào)出一缺頁(yè)中斷一＞頁(yè)面調(diào)入

B、決定淘汰頁(yè)—頁(yè)面調(diào)入一缺頁(yè)中斷一頁(yè)面調(diào)出

C、缺頁(yè)中斷一決定淘汰頁(yè)一頁(yè)面調(diào)出一頁(yè)面調(diào)入

D、缺頁(yè)中斷一＞決定淘汰頁(yè)一頁(yè)面調(diào)入一頁(yè)面調(diào)出

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

知識(shí)點(diǎn)解析：根據(jù)缺頁(yè)中斷的處理流程，產(chǎn)生缺頁(yè)中斷后，首先去內(nèi)存尋找空閑物

理塊，若內(nèi)存沒(méi)有空閑物理塊，則使用相應(yīng)的頁(yè)面置換算法決定淘汰頁(yè)面，然后調(diào)

出該淘汰頁(yè)面；最后在調(diào)入該進(jìn)程需要訪問(wèn)的頁(yè)面，所以整個(gè)流程可以歸結(jié)為：缺

頁(yè)中斷一決定淘汰頁(yè)一頁(yè)面調(diào)出一頁(yè)面調(diào)入。

29、下列關(guān)于Belady現(xiàn)象和工作集的說(shuō)法正確的是()。I.先進(jìn)先出(FIFO)頁(yè)面

置換算法會(huì)產(chǎn)生Belady現(xiàn)象D.最近最少使用(LRU)頁(yè)面置換算法會(huì)產(chǎn)生Belady

現(xiàn)象m.為了保證進(jìn)程高效的運(yùn)行，它的工作集頁(yè)面需要都在虛擬存儲(chǔ)器內(nèi)，否

則會(huì)出現(xiàn)頻繁的頁(yè)面調(diào)入/調(diào)出現(xiàn)象W.為了保證進(jìn)程高效的運(yùn)行，它的工作集頁(yè)

面需要都在主存儲(chǔ)器內(nèi)，否則會(huì)出現(xiàn)頻繁的頁(yè)面調(diào)入/調(diào)出現(xiàn)象

A、I、m

B、I、W

c、口、in

D、n、w

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

知識(shí)點(diǎn)解析：I正確。舉個(gè)例子：使用先進(jìn)先出(FIFO)頁(yè)面置換算法，頁(yè)面引用串

為1、2、3、4、1、2、5、1、2、3、4、5時(shí)，當(dāng)分配3幀時(shí)產(chǎn)生9次缺頁(yè)中斷，

分配4幀時(shí)產(chǎn)生10次缺頁(yè)中斷。II錯(cuò)誤。最近最少使用(LRU)頁(yè)面置換算法沒(méi)有

這樣的問(wèn)題。m錯(cuò)誤、W正確。若頁(yè)面在內(nèi)存中，不會(huì)產(chǎn)生缺頁(yè)中斷，即不會(huì)出

現(xiàn)頁(yè)面的調(diào)入/調(diào)出，而不是在虛擬存儲(chǔ)器(包括作為虛擬內(nèi)存那部分硬盤)中。

綜上所述，本題選B。

30、某文件系統(tǒng)物理結(jié)溝采用三級(jí)索引分配方法，如果每個(gè)磁盤塊的大小為

1024B,每個(gè)盤塊索引號(hào)占用4B,請(qǐng)問(wèn)在該文件系統(tǒng)中，最大的文件大小最接近

的是（）。

A、8GB

B、16GB

C>32GB

D、2TB

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

知識(shí)點(diǎn)解析：根據(jù)已知條件，每個(gè)盤塊為1024B,每個(gè)索引號(hào)為4B,因此，每個(gè)

索引塊可以存放256個(gè)索引號(hào)，三級(jí)索引塊可以管理文件的大小為

256x256x256xl024B-16GBo

31、信息在外存空間的排列也會(huì)影響存取等待時(shí)間?？紤]幾個(gè)邏輯記錄A、B、

C.........J,它們被存放于磁盤上，每個(gè)磁道存放10個(gè)記錄，安排如表4-2所示。

袤4-2每個(gè)磁道存放10個(gè)記錄

物理塊12345678910

遂輯記錄ABCDEFGH1J

假定要經(jīng)常順序處理這些記錄，磁盤旋轉(zhuǎn)速度為20ms/r,處理程序讀出每個(gè)記錄

后花4ms進(jìn)行處理?？紤]對(duì)信息的分布進(jìn)行優(yōu)化，如表4-3所示，相比之前的信

息分布，優(yōu)化后的時(shí)間縮短了（）。

表83優(yōu)化后磁道存放的10個(gè)記錄

的理塊12345678910

邏輯記玳AHEBIFCJGD

A、60ms

B、104ms

C>144ms

D、204ms

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

知識(shí)點(diǎn)解析：題中磁盤旋轉(zhuǎn)速度為20ms/r,每個(gè)磁道存放10個(gè)記錄，因此讀出一

個(gè)記錄的時(shí)間為20/10ms=2ms。（1）對(duì)于第一種記錄分布情況，讀出并處理記錄A

需要6ms,則此時(shí)讀寫磁頭已轉(zhuǎn)到記錄D的開始處，因此為了讀出記錄B,必須

再轉(zhuǎn)一圈少兩個(gè)記錄（從記錄D到記錄B）。后續(xù)8個(gè)記錄的讀取及處理與此相

同，但最后一個(gè)記錄的讀取與處理只需6ms。于是，處理10個(gè)記錄的總時(shí)間為

9x（2+4+16）ms+（2+4）ms=204mso（2）對(duì)于第二種記錄分布情況，讀出并處理記錄A

后.讀寫磁頭剛好轉(zhuǎn)到定錄B的開始處，因此立即就可讀出并處理.，后續(xù)記錄的

讀取與處理情況相同。一共旋轉(zhuǎn)2.7圈。最后一個(gè)記錄的讀取與處理只需6ms。于

是處理10個(gè)記錄的總時(shí)間為20x2.7ms+6ms=60ms。綜上所述，信息分布優(yōu)化后，

處理的時(shí)間縮減了204ms—60ms=144ms。

32、考慮單用戶計(jì)算機(jī)上的下列I/O操作，需要使用緩沖技術(shù)的是（）。I.圖形用

戶界面下使用鼠標(biāo)n.在多任務(wù)操作系統(tǒng)下的磁帶驅(qū)動(dòng)器（假設(shè)沒(méi)有設(shè)備預(yù)分

配）n.包含用戶文件的磁盤驅(qū)動(dòng)器w.使用存儲(chǔ)器映射I/O,直接和總線相連

的圖形卡

A、I、m

B、口、w

c、口、m、iv

D、全選

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

知識(shí)點(diǎn)解析：I正確。在鼠標(biāo)移動(dòng)時(shí)，如果有高優(yōu)先級(jí)的操作產(chǎn)生，為了記錄鼠標(biāo)

活動(dòng)的情況，必須使用緩沖技術(shù)。n正確。由于磁帶驅(qū)動(dòng)器和目標(biāo)或源I/O設(shè)備

間的吞吐量不同，必須采用緩沖技術(shù)。m正確。為了能使數(shù)據(jù)從用戶作業(yè)空間傳

送到磁盤或從磁盤傳送到用戶作業(yè)空間，必須采用緩沖技術(shù)。w正確。為了便于

多幅圖形的存取及提高性能，緩沖技術(shù)是可以采用的，特別是在顯示當(dāng)前一幅圖形

時(shí)又要得到下一幅圖形時(shí)，應(yīng)采用雙緩沖技術(shù)。綜上所述，本題選D。

33、假定運(yùn)行發(fā)送窗口大小為5和接收窗口大小為3的滑動(dòng)窗口算法，并且在傳輸

過(guò)程中不會(huì)發(fā)生分組失序的問(wèn)題，幀序號(hào)的編碼至少有（）位。

A、2

B、3

C、4

D、5

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

知識(shí)點(diǎn)解析：總結(jié)：停止一等待協(xié)議、后退N幀協(xié)議和選擇重傳協(xié)議都可以看成

是滑動(dòng)窗口協(xié)議?；瑒?dòng)窗口協(xié)議中發(fā)送、接收窗口大小必須滿足：發(fā)送窗口大小

W佗接收窗口大小WR,且WT+WRW2m（幀序號(hào)的位數(shù)為m）。所以

3

WT+WR=8<2,即幀序號(hào)的編碼至少有3位。

34、以下幾種CSMA協(xié)議中，什么協(xié)議在監(jiān)聽(tīng)到介質(zhì)是空閑時(shí)一定發(fā)送（）。

I.1—持續(xù)CSMAn.p一持續(xù)CSMA皿.非持續(xù)的CSMA

A、只有I

B、I、皿

C、I、U

D、只有n

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

知識(shí)點(diǎn)解析：1-持續(xù)的CSMA:當(dāng)檢測(cè)到信道為空的時(shí)候就會(huì)發(fā)送數(shù)據(jù)。當(dāng)它檢測(cè)

到信道為忙的時(shí)候，就一直為檢測(cè)信道的狀態(tài)，所以I正確。非持續(xù)的CSMA:也

是當(dāng)檢測(cè)到信道為空的時(shí)候就發(fā)送數(shù)據(jù)。但是，當(dāng)它檢測(cè)到信道正在被使用時(shí)，則

不會(huì)持續(xù)地對(duì)信道進(jìn)行監(jiān)聽(tīng)，所以DI正確。p-持續(xù)CSMA,當(dāng)一個(gè)站準(zhǔn)備好要發(fā)

送數(shù)據(jù)的時(shí)候，它會(huì)檢測(cè)信道。如果信道是空閑的，則它按照概率p的可能性發(fā)送

數(shù)據(jù)。在概率i—p的情況下，它會(huì)選擇不發(fā)送數(shù)據(jù)，所以n錯(cuò)誤，。注:

CSMA/CD協(xié)議類似于1.持續(xù)的CSMA協(xié)議。

35、10個(gè)站點(diǎn)連接到一個(gè)10Mbit/s的以太網(wǎng)交換機(jī)上，下面說(shuō)法正確的是()。

A、每個(gè)站點(diǎn)共享10Mbit/s

B、每個(gè)站點(diǎn)都獨(dú)享1Mbit/s

C、每個(gè)站點(diǎn)共享IMbil/s

D、每個(gè)站點(diǎn)都獨(dú)享IOMbit/s

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

知識(shí)點(diǎn)解析：交換機(jī)能同時(shí)連通許多對(duì)端口，使每一對(duì)相互通信的主機(jī)都能像獨(dú)占

通信介質(zhì)一樣，進(jìn)行無(wú)碰撞的數(shù)據(jù)傳輸?？偨Y(jié)：交換機(jī)所連主機(jī)能達(dá)到的帶寬是

每個(gè)端口能達(dá)到帶塊的最大值，而集線器所連接的主機(jī)所能達(dá)到的帶寬是端口能達(dá)

到的1/n到為所連的主機(jī)數(shù))。

36、一個(gè)IPv6包中“通信量類”字段的值為0,表明()。

A、該包優(yōu)先級(jí)最低，擁塞時(shí)可以被丟棄

B、該包優(yōu)先級(jí)最高，擁塞時(shí)不能被丟棄

C、該包中沒(méi)有用戶數(shù)據(jù)，只有首部

D、該包不可進(jìn)行路由器轉(zhuǎn)發(fā)

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

知識(shí)點(diǎn)解析：總結(jié)：IPv6首部總結(jié)，如圖4一12所示。

比特？3I?162431

'版本]通侑量類]1流懷號(hào)

有效/低長(zhǎng)一~下一個(gè)百部~跳數(shù)限制

IPV的6

源地址

察(128bit)

本

首

部

40B

目的堆址

(I28bit)

圖4?12IPv6苜部總結(jié)

版本(version)--

4bit,它指明了協(xié)議的版本，對(duì)于IPv6,該字段總是6。通信量類(irafficclass)-

8bit,這是為了區(qū)分不同的IPv6數(shù)據(jù)報(bào)的類別或優(yōu)先級(jí)。已經(jīng)定義了0?15共16

個(gè)優(yōu)先級(jí)，0的優(yōu)先級(jí)最低。。?7表示允許延遲，8?15表示高優(yōu)先級(jí)，需要固定

速率傳輸。流標(biāo)號(hào)(flowlabel)—20bit,“流”是互聯(lián)網(wǎng)上從特定源點(diǎn)到特定終點(diǎn)的

一系列數(shù)據(jù)報(bào)，“流''所經(jīng)過(guò)的路徑上的路由器都保證指明的服務(wù)質(zhì)量。所有屬于同

?個(gè)流的數(shù)據(jù)報(bào)都具有同樣的流標(biāo)號(hào)。有效載荷長(zhǎng)度(payloadlength)--16bit,它指

明IPv6數(shù)據(jù)報(bào)除基本首部以外的字節(jié)數(shù)(所有擴(kuò)展首部都算在有效載荷之內(nèi))，

其取大值是64KBo下一個(gè)首部（nexlheader）-8bit,它相當(dāng)于IPv4的協(xié)議字段或可

選字段。跳數(shù)限制（hoplimit）--8bit,源站在數(shù)據(jù)報(bào)發(fā)出時(shí)即設(shè)定跳數(shù)限制，路由器

在轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)時(shí)將跳數(shù)限制字段中的值減1。當(dāng)跳數(shù)限制的值為零時(shí)，就要將此數(shù)

據(jù)報(bào)丟棄。源地址--128bil,數(shù)據(jù)報(bào)的發(fā)送站'的IP地址。目的地址--128bit,數(shù)據(jù)

報(bào)的接收站的IP地址。

37、以太網(wǎng)組播IP地址224.215,145.230應(yīng)該映射到組播MAC地址（）。

A、01—00—5E—57—91—E6

B、01—00—5E—D7—91—E6

C、01—00—5E—5B—91—E6

D、01—00—5E—55—91—E6

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

知識(shí)點(diǎn)解析：先把IP地址換算成二進(jìn)制

224.215.145.230^11011111.11010111.10010001.11100110,若映射，則只映射IP地

址的后面23位，因?yàn)镸AC地址是用十六進(jìn)制表示的，所以只要把二進(jìn)制的IP地

址簡(jiǎn)單地4位一組合就可以了。11100U0=E6,10010001=91,0111=7,這個(gè)時(shí)候

已經(jīng)映射了20位，再取前3位即可：101第24位取0（這是規(guī)定，大家看看課本

就知道為什么FF:FF:FF變成了7F:FF:FF）,然后前24位用MAC地址的組播就可

以了，所以最后結(jié)果應(yīng)該是：01—00—5E—57—91—E6o

38、在IP首部的字段中，與分片和重組無(wú)關(guān)的字段是（）。I.總長(zhǎng)度口.標(biāo)識(shí)

m.標(biāo)志域W.片偏移

A、僅I

B、僅I、U、W

c、僅口、m

D、僅m、w

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

知識(shí)點(diǎn)解析：在【P首部中.標(biāo)識(shí)域的用途是讓1=1標(biāo)主機(jī)確定一個(gè)新到達(dá)的分段屬

于哪一個(gè)數(shù)據(jù)報(bào)，用于重新組合分片后的IP數(shù)據(jù)報(bào)；而標(biāo)志域中的DF（是否不能

分片）和MF（是否后面還有分片）位都與分片有關(guān)；片偏移則是標(biāo)志分片在IP

數(shù)據(jù)報(bào)中的位置，重新組合分組的時(shí)候要用到，所以只有總長(zhǎng)度字段用不上。

39、以下字段中，TCP首部和UDP首部都有的字段為（）。I.目標(biāo)端口號(hào)II.幀

序號(hào)m.源端口號(hào)W.校驗(yàn)號(hào)

A僅

、I、口、IV

B僅

、I、n、m

c僅

、口、

僅m

D

、I、巫、w

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

知識(shí)點(diǎn)解析：顯然TCP數(shù)據(jù)報(bào)和UDP數(shù)據(jù)報(bào)都包含目標(biāo)端口、源端口和校驗(yàn)號(hào)。

但是，由于UDP是不可靠的傳輸，故幀不需要編號(hào)，所以不會(huì)有序號(hào)字段，而

TCP是可靠的傳輸，故需要設(shè)置序號(hào)字段。

40、路由匯聚是把小的子網(wǎng)匯聚成大的網(wǎng)絡(luò)，下面4個(gè)子網(wǎng)：

172.16.193.0/24、172.16.194.0/24、172.16.196.0/24、

172.16.198.0/24,進(jìn)行路由匯聚后的網(wǎng)絡(luò)地址是（）。

A、172.16.192.0/21

B、172.16.192.0/22

C、172.16.200.0/22

D、172.16.224.0/20

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

知識(shí)點(diǎn)解析：根據(jù)前面講過(guò)的知識(shí)，只要將網(wǎng)絡(luò)地址中第一個(gè)不一樣的字段按二進(jìn)

制展開，然后找到它們最大限度的相同的位數(shù)，然后再轉(zhuǎn)化成十進(jìn)制即可，展開如

下：172.16.11000001/24172.16.11000010/24172.16.11000100/24

172.16.11000110/24很明顯，他們之間最大限度的相同的位數(shù)是21位，故聚合之后

的網(wǎng)絡(luò)地址為172.16.192.0/24o

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

分。）

表5—1給出了果_11程各，序之間的優(yōu)先關(guān)系和各序所需的時(shí)間（具中表示無(wú)

先驅(qū)工序），請(qǐng)完成以下各題：

*5-1工程工序的優(yōu)先關(guān)系和所需時(shí)間

工序代號(hào)ABCDEFGH

所需時(shí)間32234321

先奧1：序——AABAC、ED

41、畫出相應(yīng)的AOE網(wǎng)。

圖5-7AOE網(wǎng)

知識(shí)點(diǎn)解析：暫無(wú)解析

42、列出各事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間。

標(biāo)準(zhǔn)答案：所有事件的最早發(fā)生時(shí)間ve,如下所示：ve(vi)—Ove(V2)=3ve(V3)

=2ve（V4）=max{ve（V2）+2,ve（V3）+4}=6,ve(V5)=ve(V2)+3=6ve(V6)

=max{ve（V2）+3,ve（V4）+2,ve（V5）+1}=8所有事件的最遲發(fā)生時(shí)間vl,如下所

示：vl（V6）=8vl（V5）=vl（V6）一1=7vl（V4）=vl（V6）-2=6vl（V3）=vl（V4）―4=2vl

（V2）=Min{vl（V4）—2,vl（V5）—3,vl（V6）—3）=4vl（vi）=Min{vl（V2）—3,vl（V3）

—2）=0

知識(shí)點(diǎn)解析：暫無(wú)解析

43、求出關(guān)鍵路徑并指明完成該工程所需的最短時(shí)間。

標(biāo)準(zhǔn)答案：求所有活動(dòng)的最早發(fā)生時(shí)間e、坡遲發(fā)生時(shí)間1和時(shí)間余量1—e。e(A)

=ve(vi)=0；1(A)=vl(V2)-3=1；1(A)—e(A)=le(B)=ve(V6)=0；1(B)=vl(V3)一

2=0；1(B)―e(B)=0e(C)=ve(V2)=3；1(C)=vl(V4)-2=4：1(C)―e(C)=le(D)

=ve(V2)=3；1(D)=vl(V5)—3=4；1(D)―e(D)=le(E)=ve(V3)=2；1(E)=vl(V4)-

4=2；1(E)一e(E)=0e(F)=ve(V2)=3；1(F)=vl(V6)—3=5；1(F)―e(F)=2e(G)=ve

(V4)=6；1(G)=vl(ve)—2=6；1(G)―e(G)=0e(H)=ve(V5)=6；1(H)=vl(V6)—

1=7；1(H)—e(H)=l所以，關(guān)鍵路徑為B、E、G,旦完成該工程最少需要8天時(shí)

間。

知識(shí)點(diǎn)解析：暫無(wú)解析

輸入一個(gè)按升序排序過(guò)的整數(shù)數(shù)組(I、2、4、7、II、15}以及一個(gè)整數(shù)數(shù)字15,

我們可以從該數(shù)組中找到兩個(gè)數(shù)字，即4和11,使得4+11=15。請(qǐng)實(shí)現(xiàn)一個(gè)時(shí)間

上盡可能高效率的算法，當(dāng)輸入一個(gè)已經(jīng)按升序排序過(guò)的整數(shù)數(shù)組和一個(gè)整數(shù)數(shù)

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

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

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

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

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

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

便在數(shù)組中找到兩個(gè)數(shù),如果它們的和等于輸入的數(shù)字.那太好了，我們找到了要

找的兩個(gè)數(shù)字；如果小于輸入的數(shù)字呢？我們希望兩個(gè)數(shù)字的和再大一點(diǎn)。由于數(shù)

組己經(jīng)排好序了，我們是不是可以把較小的數(shù)字往后面移動(dòng)一個(gè)數(shù)字？因?yàn)榕旁诤?/p>

面的數(shù)字要大?些，那么兩個(gè)數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了；

同樣，當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字的時(shí)候，我們把較大的數(shù)字往前移動(dòng)，因?yàn)?/p>

排在數(shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。我們把前

面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字

的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng)；當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，