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

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

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

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

()oI.訪(fǎng)問(wèn)第i個(gè)結(jié)點(diǎn)(iWiWn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2Wign)口.在最后一個(gè)

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

(l<i<n)

A僅

、I

B僅

、u、m

c僅

、i、n

D僅

、i、口、in

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

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

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

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

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

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

2、中綴表達(dá)式腔(b+c)-d的后綴表達(dá)式是()。

A、abcd*+-

B、abc+*d—

C^abc*+d-

D、-+*abcd

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

[j

知識(shí)點(diǎn)解析：本題轉(zhuǎn)化過(guò)程如圖4-4所示。圖I鑄化過(guò)和示息圖由圖爾4可以寫(xiě)出以

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

第二步：y—d-vd-將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)?/p>

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

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

括號(hào)的對(duì)應(yīng)關(guān)系如圖4-5所示，將右括號(hào)用對(duì)應(yīng)的運(yùn)算符替換，變?yōu)?/p>

“((5(2(16+*+(82/一”，最后除掉所有左括號(hào)得到的后綴表達(dá)式為“5216+*+82/

九圖3運(yùn)算符和右括號(hào)的對(duì)應(yīng)關(guān)系注：本方法需要人工判斷表達(dá)式的執(zhí)行順序(即加]

括號(hào))，所以無(wú)法用程序?qū)崿F(xiàn)。按照以上方式可以很輕松地解題，不妨試著將中綴

表達(dá)式a*(b+c)—d轉(zhuǎn)換成后綴表達(dá)式。第一步：進(jìn)行乘法運(yùn)算，加括號(hào)變?yōu)?/p>

(a*(b+c))-do第二步：進(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)/c的后綴式。后綴式和前綴式都只有唯一的一種運(yùn)算次序，而中綴式卻

不一定，后綴式和前綴式是由中綴式按某一種運(yùn)算次序而生成的，因此對(duì)于一個(gè)中

綴式可能有多種后綴式或者前綴式。例如，a+b+c可以先算a+b,也可以先算

b+c,這樣就有兩種后綴式與其對(duì)應(yīng)，分別是ab+c+和abc++。

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

高。

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

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

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

D、輸出與給定值x相等的元素在線(xiàn)性表中的序號(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ù)雜度均為0(n),因此C不對(duì)。輸出與給定值x相等的元素在線(xiàn)性

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

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

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

鏈表要執(zhí)行5次：p=head->next；q=head->next->next；temp=p->data；

p->data=q->data；q->data=lemp,但本題是單選題的時(shí)候，考生需要選擇更準(zhǔn)確的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

線(xiàn)索化后E結(jié)點(diǎn)的右線(xiàn)索的接連情況。解決這類(lèi)題的方法為，先寫(xiě)出題目所要求

的遍歷方式下的結(jié)點(diǎn)訪(fǎng)問(wèn)序列，根據(jù)此序列找出題目要求中結(jié)點(diǎn)的前驅(qū)和后繼，然

后連接線(xiàn)索。圖4—6中二叉樹(shù)的中序遍歷序列為D,B,E,A,Co結(jié)點(diǎn)E的前

驅(qū)為B,后繼為A,因比其右線(xiàn)索應(yīng)該指向A,結(jié)果如圖4—7所示。

圖4.6二叉可圖a右線(xiàn)索指向A結(jié)點(diǎn)總結(jié)：⑴引入二叉線(xiàn)索樹(shù)的目的:

加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度。（2）二又樹(shù)在線(xiàn)索化后，仍不能解決的問(wèn)題：

后序線(xiàn)索二叉樹(shù)中求后序后繼。（3）n個(gè)結(jié)點(diǎn)的線(xiàn)索二叉樹(shù)上含有的線(xiàn)索樹(shù)為n-1o

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

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

為（）。

A、1

B、3

C、4

D、5

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

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

示。W4.8平衡一義樹(shù)可以看出度為2的結(jié)點(diǎn)有4個(gè)。

6、某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)可能是（）。I.空或只

有一個(gè)結(jié)點(diǎn)U.任意一個(gè)結(jié)點(diǎn)無(wú)右孩子m.任意一個(gè)結(jié)點(diǎn)無(wú)左孩子

A、只可能為I

B、只可能為U

c、只可能為in

D、口、DI都有可能

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

知識(shí)點(diǎn)解析：考生一定需要知道做這種題目的正確思路，而不是在草稿紙上隨意畫(huà)

一棵二又樹(shù)去套答案，因?yàn)橛行╊}目是不可能通過(guò)舉反例來(lái)驗(yàn)證的。解題思路：

首先前序序列和后序序列的遍歷順序分別為T(mén)LR（根左右）和LRT（左右根），然后分

以下幾種情況：（1）假設(shè)該二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)，此時(shí)前序序列和后序序列乜算

是相反，所以滿(mǎn)足題意。但是空樹(shù)比較特殊，不存在遍歷的概念，無(wú)法給出解釋?zhuān)?/p>

記住就行，所以I錯(cuò)誤。（2）假設(shè)任意一個(gè)結(jié)點(diǎn)無(wú)左孩子，則前序的遍歷變成TR,

后序的遍歷變成RT,恰好相反，所以該假設(shè)的二叉樹(shù)成立。（3）假設(shè)任意一個(gè)結(jié)點(diǎn)

無(wú)右孩子，則前序的遍歷變成TL,后序的遍歷變成LT,恰好相反，所以該假設(shè)的

二叉樹(shù)成立。綜上所述，n和HI都有可能。提醒：如果此題為單項(xiàng)選擇題，假設(shè)

出現(xiàn)選項(xiàng)二叉樹(shù)的高度等于結(jié)點(diǎn)的個(gè)數(shù)也是正確答案，因?yàn)檫@個(gè)答案把n和HI的情

況都包括了。

7、對(duì)圖4—1進(jìn)行拓?fù)渑判颍梢缘玫讲煌耐負(fù)湫蛄械膫€(gè)數(shù)是（）。

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,d0

8、如果從無(wú)向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪(fǎng)問(wèn)所有頂點(diǎn)，

則該圖一定是（）。

A、完全圖

B、連通圖

C、有回路

D、一棵樹(shù)

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

知識(shí)點(diǎn)解析：圖的一次深度優(yōu)先搜索遍歷，可以遍歷完圖中一個(gè)連通分量中所有的

頂點(diǎn)。如果圖是連通的，則圖只含有一個(gè)連通分量，即圖本身，這樣一次深度優(yōu)先

搜索遍歷即可遍歷完圖中所有頂點(diǎn)。因此本題選B,完全圖相當(dāng)于在連通圖上加上

了更嚴(yán)格的條件，即任意兩個(gè)頂點(diǎn)間都存在邊，對(duì)于滿(mǎn)足本題的要求不需要完全

圖，條件達(dá)到連通圖的強(qiáng)度就足夠了?？赡芤蓡?wèn)點(diǎn),：有些考生可能認(rèn)為D也正

確，樹(shù)難道不是連通圖嗎？提示：樹(shù)的類(lèi)型有很多，相信選D的同學(xué)必定是思維定

式，總是想著普通的無(wú)向樹(shù)，這些樹(shù)當(dāng)然是連通圖。但是，是否想過(guò)有向樹(shù)?想必

提到這個(gè)概念誤選D的考生就會(huì)恍然大悟了，不再多做解釋。補(bǔ)充：用深度優(yōu)先

算法遍歷一個(gè)無(wú)環(huán)有向圖，并在深度優(yōu)先退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂

點(diǎn)序列是逆拓?fù)溆行颉?/p>

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

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

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

A、僅I、H

B、僅口、m

C、僅M、IV

D、僅I、□、W

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

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

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

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

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

m—1個(gè)關(guān)鍵字，所以D正確。HI中：B一樹(shù)是平衡的多路查找樹(shù)，葉子結(jié)點(diǎn)均在

同一層上，所以HI正確。W中：發(fā)生結(jié)點(diǎn)分裂的時(shí)候不一定會(huì)使樹(shù)長(zhǎng)高。比如向

圖4-9中的B—樹(shù)插入一個(gè)關(guān)鍵字10變成圖4—10中的B—樹(shù)，使得第二層右端

的一個(gè)結(jié)點(diǎn)分裂成兩個(gè)，但是樹(shù)并沒(méi)有長(zhǎng)高，所以w錯(cuò)誤。綜上所述，n、ni正

確。4-9W4-I0%人一個(gè)美孤字石的BH

10、在下列排序方法中，平均時(shí)間復(fù)雜度為O（nlogn）的排序算法是（）。I.快速

排序n.冒泡排序m.希爾排序IV.選擇排序

A、僅I、n

B、僅I、m

c、僅I、m、w

D、僅m、iv

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

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

很少有考生在做這種選擇題的時(shí)候能夠分析其算法來(lái)選擇答案。下面與大家分享一

個(gè)記憶總結(jié)，該總結(jié)可以將內(nèi)部排序所有的記憶性題目輕輕松松地拿下。由以下總

結(jié)可以很輕松地得到答案B。穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜度總結(jié)：（1）穩(wěn)定性

總結(jié)：一句話(huà)解決：本人考研無(wú)聊中，那么就快（快速排序）些（些和希爾諧音，希爾

排序）選（選擇排序）堆（堆排序）來(lái)聊!這里面都是不穩(wěn)定的，其他的就自然都是穩(wěn)定的

了。（2）時(shí)間復(fù)雜度總結(jié)：1）在軍訓(xùn)的時(shí)候，教官說(shuō)了一句話(huà)：快（快速排序）些（希

爾排序）以nlogn的速度與（歸并排序）隊(duì)（堆排序）!在這句話(huà)里面包含的排序，時(shí)間復(fù)

雜度都是O（nk）gn）l2）屋泡冒得好就是。（n）,冒泡冒得不好就是3）直接插

插得好就是O（n）,插得不好就是0（/）,其中插得好、冒得好分別對(duì)應(yīng)最好的時(shí)間

復(fù)雜度，插得不好、冒得不好分別對(duì)應(yīng)最壞時(shí)間復(fù)雜度，而平均時(shí)間復(fù)雜度對(duì)應(yīng)最

壞的時(shí)間復(fù)雜度。（3）輔助空間總結(jié)：只需記住幾個(gè)特殊的就好，歸并O（n）、快速

O（log2n）,基數(shù)排序O（r+d）,其他的就自然全部是0⑴了。

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=Ilogi480I=2o

12、考慮以下C語(yǔ)言代碼：shortsi=-8196；unsignedshortusi=si：執(zhí)行上述程序

段后，usi的值為（）。

A、8196

B、34572

C、57339

D、57340

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

知識(shí)點(diǎn)解析：此種題型已經(jīng)在2012年真題中考查過(guò)。首先，求得-8196的補(bǔ)碼表

示為1101111111111100,賦值給usi后，由于usi為無(wú)符號(hào)數(shù)，所以將二進(jìn)制

1101111111111100轉(zhuǎn)換為十進(jìn)制為57340。技巧:FFFFHMz：iS$iJ^65535,

應(yīng)該記住。然后減去3個(gè)0對(duì)應(yīng)的權(quán)值，分別為8192、2、1,即最后的結(jié)果為65

535—8192—2—1=57340。

13、32位字長(zhǎng)的浮點(diǎn)數(shù)，其中階碼8位（含1位階符），尾數(shù)24位（含1位數(shù)符），機(jī)

器數(shù)采用補(bǔ)碼表示，且尾數(shù)為規(guī)格化形式，則對(duì)應(yīng)的最小正數(shù)為（）。

A、2RMS）

B、2-⑵

C、2'128X2-23

D、2'I27X2-23

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

知識(shí)點(diǎn)解析：最大數(shù)、最小數(shù)及規(guī)格化浮點(diǎn)數(shù)的二進(jìn)制表示如表4-5所示。

*4-5最大賬.■小跤及JR格化浮點(diǎn)敷的二進(jìn)制袤示

■大長(zhǎng)的.!!!；《&尿01IIIIHoinniiiiiiiiiuiiiiiii2f,x(!-2°)

■小數(shù)的二遺M表示0IIIIIII100000000000000000000000/X-l)

OI1IIIII01HIIIIIIIIIIIIIIUUII

r1

畿格化■小■?)0(XK)O(M)0100000000000000008000(12x2

rH

規(guī)格化?大允依11)000000lOlllltlllllllllllllllil-2x(2-'+2>

盛格化■小0R0IIIIIII10000000000000000000000()4M叫

__________________________ZkfcC.

（1）最大數(shù)的二進(jìn)制表示：首先要使得數(shù)最大，很明顯前面2的xx次方必須是最大

的，自然就想到01111111,后面的尾數(shù)也盡量離1最近，自然想到

Olllllllllllllllllllllllo（2）最小數(shù)的二進(jìn)制表示：首先要使得數(shù)最小，很明

顯前面2的xx次方必須是最大的，自然就想到01111111,后面的尾數(shù)也盡量離-I

最近，因?yàn)樵浇颓懊娴闹笖?shù)乘起來(lái)就會(huì)越遠(yuǎn)離①而補(bǔ)碼又恰好可以取到-1,那

就肯定是選擇-1了，自然就想到100000000000000000000000。（3）規(guī)格化形式范圍

其實(shí)和（1）（2）的情況類(lèi)似，這里只講一個(gè)比較難理解的，即規(guī)格化最大負(fù)數(shù)。首先

不考慮規(guī)格化的事情，要使得一個(gè)數(shù)是最大的負(fù)數(shù)，也就是離0越近越好，所以自

然想到2的指數(shù)越小越好，既然是補(bǔ)碼，自然就想到最小的數(shù)-128,所以階碼應(yīng)該

是10000000,尾數(shù)也應(yīng)該離1最近，現(xiàn)在的離1最近就不能隨便選了，因?yàn)槭且?/p>

選擇滿(mǎn)足規(guī)格化的前提下離1最近的數(shù)字。而規(guī)格化要求1/2WIsIVI,所以s

應(yīng)當(dāng)取得-1/2才是最理想的，但是-1/2不是規(guī)格化數(shù)，所以退一步，加一個(gè)最

小的數(shù)，也就是723,得到所要的結(jié)論。考生看完此總結(jié)以后，應(yīng)當(dāng)能馬上寫(xiě)出

任何位數(shù)以補(bǔ)碼形式表示的規(guī)格化浮點(diǎn)數(shù)的范圍，不是補(bǔ)碼也沒(méi)有關(guān)系，只要知道

此X碼能夠表示數(shù)的范圍就好了，思路都是一致的。

14、硬盤(pán)平均尋道時(shí)間為12ms,傳輸速率為lOME/s,磁盤(pán)控制器延時(shí)為2ms,

則一個(gè)轉(zhuǎn)速為7200r/min的硬盤(pán)寫(xiě)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è)磁道上。

I

7200r/min=120r/s；因?yàn)閭鬏斔俾蕿?0MB/s,故每轉(zhuǎn)容量為：而W*,所以

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

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

的時(shí)間，即（60/7200）x1/2=4.17ms；數(shù)據(jù)傳輸時(shí)間等于1KB/10MB/

s=0.1ms,所以寫(xiě)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ì)真題的解釋?zhuān)纯此麄內(nèi)≈刀嗌伲罩〖纯伞?/p>

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

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

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

A僅

、I、n

B僅

、口、IV

c僅

、、、

僅Ium

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)部有行列式的熔絲，視需要利用電流將其燒

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

戶(hù)可以根據(jù)需要將其中的某些單元寫(xiě)入數(shù)據(jù)0（部分的PROM在出廠(chǎng)時(shí)數(shù)據(jù)全為

0,則用戶(hù)可以將其中的部分單元寫(xiě)入1）,以實(shí)現(xiàn)對(duì)其“編程”的目的，所以口正

確。m：EPROM是可改寫(xiě)的，但它不屬于隨機(jī)存儲(chǔ)器，所以in錯(cuò)誤。w：（電可

擦可編程只讀存儲(chǔ)器，ElectricallyErasableProgrammableRead-Only?Memory,

EEPROM）屬于一種掉電后數(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è)字4B。假設(shè)

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

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

字，3個(gè)周期恢復(fù)和寫(xiě)入糾錯(cuò)碼，當(dāng)系統(tǒng)以35%為讀操作、65%為寫(xiě)操作的訪(fǎng)問(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í)鐘周期、速率以

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

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

寫(xiě)操作的時(shí)間為T(mén)w=（l-2+8+3）x20ns=280ns則綜合加權(quán)的時(shí)間為

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

輸32B）Bn=32B/（266x10"V120.3MB/s

17、在二地址指令中，操作數(shù)的物理位置可安排在（）。I.兩個(gè)主存單元D.兩

個(gè)寄存器HI.一個(gè)主存單元和一個(gè)寄存器IV.棧頂和次棧頂

A、僅I、m、w

B、僅I、u、m

c、僅i、n、iv

D、僅i、口、m、w

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

知識(shí)點(diǎn)解析：這里I、口、in應(yīng)該沒(méi)有什么疑問(wèn)，在一般指令中都可以見(jiàn)到（對(duì)應(yīng)

RR、RS、SS指令），主要解釋一下首先，采用棧項(xiàng)和次棧頂?shù)奈锢砦恢迷趫?zhí)

行上是可行的，但是這徉的指令容易受到不確定性的影響。舉例來(lái)說(shuō)明：一個(gè)這樣

的指令在執(zhí)行完畢之后，得到的結(jié)果必然還是要存入到棧頂（二地址指令存數(shù)地址

也由其中一個(gè)地址指定），在這個(gè)結(jié)果被使用之前，如果有其他的指令又進(jìn)行了棧

操作（仍比如存數(shù)吧），這樣就導(dǎo)致棧頂操作數(shù)變化，于是就造成了后續(xù)指令執(zhí)行的

錯(cuò)誤。這種情況當(dāng)然可以避免，但是會(huì)對(duì)編制程序造成很大的限制，囚此在實(shí)際中

不予采用。但是，一般來(lái)說(shuō)零地址指令的操作數(shù)是來(lái)自堆棧和次堆棧，記住就好。

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

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

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

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

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

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

A僅

、I、n

B僅

、I、n

c僅

、n、in

DI

、、n和in

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

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

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

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

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

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

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

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

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

1-SP,后存入數(shù)據(jù)。則CALL指令執(zhí)行后，SP及棧項(xiàng)的內(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）,棧項(xiàng)內(nèi)容為1002H。

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

為At,如圖4-2所示。若該流水線(xiàn)順序執(zhí)行50條指令共用了203回（無(wú)需考慮相關(guān)

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

T1，H~7^一

圖42條指令的執(zhí)行過(guò)程

A、3At

B、4At

C、5At

D、6At

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

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

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

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

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

5；i=ikAtt+（n—l）max{Ati，△12，…，△&}根據(jù)上述公式，假定流水線(xiàn)中第3步的執(zhí)

行時(shí)間為S,該指令流水線(xiàn)順序執(zhí)行50條指令所用的時(shí)間為厚+厚+5+&+（50-

l）max{At,At,S,At}=203At,解得S=4zu,即第3步的執(zhí)行時(shí)間為4回。

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

線(xiàn)為36根，總線(xiàn)的工作頻率為66MHz,則總線(xiàn)寬度為（），傳輸速率為（）。

A、32bit264MB/s

B、20bit264MB/s

C>32bit254MB/s

D、20bit264MB/s

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

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

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

率為總線(xiàn)的工作頻率乘以總線(xiàn)寬度，即66MHzx32bit=66MHzx4B=264MB/s。

22、設(shè)置中斷排隊(duì)判優(yōu)邏輯的目的是（）。

A、產(chǎn)生中斷源編碼

B、使同時(shí)提出的請(qǐng)求中的優(yōu)先級(jí)別最高者得到及時(shí)響應(yīng)

C、使CPU能方便地轉(zhuǎn)入中斷服務(wù)子程序

D、提高中斷響應(yīng)速度

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

知識(shí)點(diǎn)解析：當(dāng)有多個(gè)中斷請(qǐng)求同時(shí)出現(xiàn)時(shí)，中斷服務(wù)系統(tǒng)必須能從中選出當(dāng)前最

需要給予響應(yīng)的最重要的中斷請(qǐng)求，這就需要預(yù)先對(duì)所有的中斷進(jìn)行優(yōu)先級(jí)排隊(duì)，

這個(gè)工作可由中斷優(yōu)先級(jí)判斷邏輯來(lái)完成，排隊(duì)的規(guī)則可由軟件通過(guò)對(duì)中斷屏蔽寄

存器進(jìn)行設(shè)置來(lái)確定。

23、實(shí)時(shí)系統(tǒng)中，通常采用（）算法進(jìn)行進(jìn)程調(diào)度。

A、先來(lái)先服務(wù)

B、時(shí)間片輪換

C、搶占式的優(yōu)先數(shù)高者優(yōu)先

D、響應(yīng)比高者優(yōu)先

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

知識(shí)點(diǎn)解析：實(shí)時(shí)系統(tǒng)中，由于對(duì)響應(yīng)時(shí)間要求非常高，所以通常采用響應(yīng)比高者

優(yōu)先的調(diào)度算法c

24、考慮下面的基于動(dòng)態(tài)改變優(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)以B速率改變。所有的進(jìn)程在進(jìn)入就緒隊(duì)列被給定

優(yōu)先權(quán)數(shù)為0。參數(shù)a和?？梢栽O(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ù)。在。>a>0設(shè)定下，在就緒隊(duì)列中，PM>PN,原因是a>0,則越

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

>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,原因跟B>a>0一樣。但由于a邛，所以在M運(yùn)行時(shí)，無(wú)法保證PM

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

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

Service)o又因?yàn)樗栽贜運(yùn)行時(shí)，PN下降速度大于PM的下降速度，有

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

FirstOut)o在aVpV0設(shè)定下，還是LCFS,原因跟QVaVO一樣。但由于a<

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

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

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

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

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

表4」某時(shí)削進(jìn)展知資源狀態(tài)

AHooMiof)MaxAVIIIBWC

ABcABcABc

Pi212559233

P24025J6

n40S40II

IM204425

PS314424

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

B、該時(shí)刻，系統(tǒng)安全，安全序列為

C、該時(shí)刻，系統(tǒng)安全，安全序列為

D、該時(shí)刻，系統(tǒng)安全，安全序列為

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

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

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

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

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

26、某系統(tǒng)擁有一個(gè)CPU。I/O1和I/O2為兩個(gè)不同步的輸入/輸出裝置，它們

能夠同時(shí)工作。當(dāng)使用CPU之后控制轉(zhuǎn)向1/01、：1/02時(shí)，或者使用。1/

01、1/02之后控制轉(zhuǎn)向CPU時(shí)，由控制程序執(zhí)行中斷處理，但這段處理時(shí)間可

以忽略不計(jì)。有A、B兩個(gè)進(jìn)程同時(shí)被創(chuàng)建，進(jìn)程B的調(diào)度優(yōu)先權(quán)比進(jìn)程A高，

但是當(dāng)進(jìn)程A正在占用CPU時(shí)，即使進(jìn)程B需要占用CPU,也不能打斷進(jìn)程A

的執(zhí)行。若在同一體系中分別單獨(dú)執(zhí)行，則需要占用CPU、1/01、1/02的時(shí)間

CPUV01CPU1-02CPUVO\

25ms30ms20fm20ms20ms30tm

如下表所示。進(jìn)程A：進(jìn)程B：

CPU1X)1CFU102CPUVO2CPU

20m>20ms20nB10m*20m經(jīng)過(guò)計(jì)算可知：（）先結(jié)

束。

A、進(jìn)程A

B、進(jìn)程B

C、進(jìn)程A和進(jìn)程B同時(shí)結(jié)束

D、不一定

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

知識(shí)點(diǎn)解析：A、B兩進(jìn)程執(zhí)行的過(guò)程如圖4—11所示，可知進(jìn)程A先執(zhí)行完

2cMim25mm20mm20mm4、EE

EI-R~|——7—|I~~jT-

A.B兩進(jìn)程執(zhí)行的過(guò)"

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

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

A、I

B、n

c、I和n

D、都不可能

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

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

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

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

的空閑幀時(shí)，系統(tǒng)正確的處理順序?yàn)椋ǎ?/p>

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)程需要訪(fǎng)問(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)生Bclady現(xiàn)象D.最近最少使用（LRU）頁(yè)面置換算法會(huì)產(chǎn)生Belady

現(xiàn)象DI.為了保證進(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、川

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)題。HI錯(cuò)誤、W正確。若頁(yè)面在內(nèi)存中，不會(huì)產(chǎn)生缺頁(yè)中斷，即不會(huì)出

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

上所述，本題選B。

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

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

索引項(xiàng)，假定物理塊的大小是2KB,每個(gè)索引項(xiàng)占用4B,假定一個(gè)文件的實(shí)際大

小是128MB,該文件實(shí)際占用磁盤(pán)空間為（）（包括索引表所占空間）。

A、128MB

B、128MB+2KB

C、128MB+256KB

D、128MB+258KB

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

知識(shí)點(diǎn)解析：文件本身需要占用128M/2K=64K塊。直接索引塊有8塊，這B塊

不需要索引表。一級(jí)間接索引塊有2KB/4B=512塊，需要一個(gè)一級(jí)索引表。二

級(jí)間接索引塊有64K-8-512塊，需要一個(gè)一級(jí)索引表，需要[（64K—8—512）/

512]=127個(gè)二級(jí)索引表，每個(gè)索引表都占用一個(gè)物理塊，即索引表需要額外占用

129個(gè)物理塊，所占空間為129x2KB=258KB,加上文件的實(shí)際大小128MB,再加

上索引表所占空間，該文件實(shí)際占用磁盤(pán)空間為128MB+258KB。

31、信息在外存空間的徘列也會(huì)影響存取等待時(shí)間。考慮幾個(gè)邏據(jù)記錄A、B、

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

*4-2每個(gè)珀遍存觸10個(gè)記錄

12J4$67S910

ABcDEFG>1IJ—假定要經(jīng)

常順序處理這些記錄，磁盤(pán)旋轉(zhuǎn)速度為20ms/r,處理程序讀出每個(gè)記錄后花4ms

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

優(yōu)化后的時(shí)間縮短了（）c

*4-3優(yōu)化后磁道存放的10個(gè)圮量

12456?s910

if融匕承AHEB1FcJGD

A、60ms

B、104ms

C>144ms

D、204ms

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

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

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

錄A需要6ms,則此時(shí)讀寫(xiě)磁頭己轉(zhuǎn)到記錄D的開(kāi)始處，因此為了讀出記錄B,

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

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

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

后，讀寫(xiě)磁頭剛好轉(zhuǎn)到紀(jì)錄B的開(kāi)始處，因此立即就可讀出并處理，后續(xù)記錄的

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

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

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

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

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

n.包含用戶(hù)文件的磁盤(pán)驅(qū)動(dòng)器W.使用存儲(chǔ)器映射i/o,直接和總線(xiàn)相連的圖

形卡

A、I、m

B、口、IV

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ù)。in正確。為了能使數(shù)據(jù)從用戶(hù)作業(yè)空間傳

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

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

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

33、電路交換的優(yōu)點(diǎn)有（）。I.傳輸時(shí)延小u.分組按序到達(dá)in.無(wú)需建立連接

IV.線(xiàn)路利用率高

A、I、n

B、II、in

c、i、m

D、口、w

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

知識(shí)點(diǎn)解析：首先電路交換是面向連接的，一旦連接建立，數(shù)據(jù)便可直接通過(guò)連接

好的物理通路到達(dá)接收端，因此傳輸?shù)臅r(shí)延小；其次由于電路交換中，通信雙方始

終占用帶寬，即使是不芍送數(shù)據(jù)（就像兩個(gè)人打電話(huà)都不說(shuō)話(huà)），所以電路交換的線(xiàn)

路利用率很低；由于電路交換是面向連接的，由面向連接的服務(wù)特性可知，傳送的

分組必定是按序達(dá)到的?？偨Y(jié)：關(guān)于電路交換和分組交換的總結(jié)，如表1所

豪44電路交換和分蜴交接的總結(jié)

比依林本電冷2晨分如爻寰

■求不要笊

6用物彳睇林HK

何個(gè)分批0氣收定的跆校咨

分研技中列站￡fi

中H跣由的30“整體"4肥府fi

可用俯塞動(dòng)而

可能加H的U月總建立4叫逢持的時(shí)俅修個(gè)分型件比的MM

可使行濃費(fèi)的希宛ft

使電“他將發(fā)ft星

&以數(shù)/啟寸梏式。的米舄林”一選

選明外明“傳歸.全改機(jī)?1用戶(hù)0片除價(jià)g不〃佃.

行分析.然娟“發(fā)到卜?個(gè)路由勃）

分析和處紂）

“分立,打電訊It性黑分仲訃”的.巾定峰個(gè)分蛾＜TM1RffftitHHffl.不

a或是核分鐘密的,從博外命慢也可以抱出國(guó)

?小打電人通電睇文晨）S黑使用的貶少《12樓》

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

續(xù)CSMAH.p-持續(xù)CSMAHI.非持續(xù)的CSMA

A、只有I

B、I、m

C、I、口

D、只有口

標(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)，所以HI正確。p-持續(xù)CSMA,當(dāng)一個(gè)站準(zhǔn)備好要

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

送數(shù)據(jù)。在概率1-p的情況下，它會(huì)選擇不發(fā)送數(shù)據(jù)，所以II錯(cuò)誤。注：CSMA/

CD協(xié)議類(lèi)似于1-持續(xù)的CSMA協(xié)議。

35、以下滑動(dòng)窗口協(xié)議收到的分組一定是按序接收的（）。I.停止一等待協(xié)議

D.后退N幀協(xié)議HL選擇重傳協(xié)議

A、I、in

B、I、口

c、n、皿

D、都有可能

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

知識(shí)點(diǎn)解析：要使分組一定是按序接收的，接收窗口的大小為1才能滿(mǎn)足，只有停

止■等待協(xié)議與后退N幀協(xié)議的接收窗口大小為1。

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

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

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

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

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

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

知識(shí)點(diǎn)解析：總結(jié)：IPv6首部總結(jié)，如圖4-12所示。版本(Version)——4bit,它

指明了協(xié)議的版本，對(duì)于IPv6,該字段總是6。通信量類(lèi)(TrafficClass)一—8bit,

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

級(jí)，0的優(yōu)先級(jí)最低。0?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)。

圖412IPv6首落總結(jié)有效載荷長(zhǎng)度(PayloadLength)一

16bit,它指明IPv6數(shù)據(jù)報(bào)除基本首部以外的字節(jié)數(shù)(所有擴(kuò)展首部都算在有效載

荷之內(nèi))，其最大值是64KB。下一個(gè)首部(NextHeader)——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ù)限制字段中的值減I。當(dāng)跳數(shù)限制的值為

零時(shí)，就要將此數(shù)據(jù)報(bào)丟棄。源地址——128bit,數(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位一組合就可以了。11100110=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-E6。

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

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

A、僅I

B、僅I、n、w

c、僅口、m

D、僅江、IV

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

知識(shí)點(diǎn)常析：在IP首部中，標(biāo)識(shí)域的用途是讓目標(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)H.幀

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

A僅

、I、口、IV

B僅

、I、u、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、（）可以將其管轄的主機(jī)名轉(zhuǎn)換為該主機(jī)的IP地址。

A、本地域名服務(wù)器

B、根域名服務(wù)器

C、授權(quán)域名服務(wù)器

D、代理域名服務(wù)器

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

知識(shí)點(diǎn)解析：因特網(wǎng)的每一個(gè)主機(jī)都必須在授權(quán)域名服務(wù)器處登記，授權(quán)域名服

務(wù)器一定能夠?qū)⑵涔茌牭闹鳈C(jī)名轉(zhuǎn)換為該主機(jī)的IP地址。

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

分。）

設(shè)有3階B一樹(shù)，如圖1-4所示。

□□66a□□□□ui□

ffl1-4B網(wǎng)

41、在該B一樹(shù)上依次插入關(guān)鍵字33和97。試畫(huà)出兩次插入后的B-樹(shù)。

標(biāo)準(zhǔn)答案：插入33：第一步需要定位，33應(yīng)該被插入35和41的那個(gè)葉子結(jié)點(diǎn)。

由于該葉子結(jié)點(diǎn)沒(méi)有了空位置（怎么檢測(cè)是否有空位置?m階B-樹(shù)最多只能有m-1

個(gè)關(guān)鍵字），所以需要進(jìn)行分裂操作。插入后的情況應(yīng)該是35、41、33,那么怎么

分裂?首先需要取一個(gè)籽結(jié)點(diǎn)，把原結(jié)點(diǎn)上的關(guān)鍵字按照升序排列，即33、35、

4lo從中間位置（即［m/2］之處）把關(guān)鍵字（不包括中間位置的關(guān)鍵字）分成兩部分，

左部分所含的關(guān)鍵字放在舊結(jié)點(diǎn)中，右邊所含的關(guān)犍字放在新結(jié)點(diǎn)中，中間位置的

關(guān)鍵字連同新結(jié)點(diǎn)的存儲(chǔ)位置插入到雙親結(jié)點(diǎn)中，如圖1一II所示。

圖bn插入關(guān)健,沔新結(jié)點(diǎn)到雙親站點(diǎn)如果雙親結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過(guò)分支數(shù)

減1,則要再分裂，再往上插，直至這勺過(guò)程傳到根結(jié)點(diǎn)為止。從以上步驟可以得

出插入33之后的B—樹(shù)，如圖1?12所示。

圖“2捅入33后的B-樹(shù)可能疑問(wèn)點(diǎn)：

結(jié)點(diǎn)下面的小方塊都是什么？提示：小方塊就是葉子結(jié)點(diǎn)，因?yàn)槿~子結(jié)點(diǎn)本身不帶

有信息，所以有些教材都不畫(huà)出來(lái)，但是葉子結(jié)點(diǎn)這一層一定要計(jì)入樹(shù)的高度。另

外，葉子結(jié)點(diǎn)一般也被認(rèn)為外部結(jié)點(diǎn)（類(lèi)似于折半查找判定樹(shù)的外部結(jié)點(diǎn)）或是查找

失敗的結(jié)點(diǎn)。插入97：過(guò)程與上面的一樣，最終結(jié)果如圖1?13所示。

mI-B隨入33和97后的B例

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

42、從⑴得到的B-樹(shù)上刪除66。試畫(huà)出刪除后的后樹(shù)。

標(biāo)準(zhǔn)