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

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

1、下列敘述中，正確的是()。I.非空循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足

p—*next-headII.帶頭結(jié)點(diǎn)的循環(huán)單鏈表的頭指針為head.如果

hcad—>ncxt—>ncxt—>ncxt=hcad成立，則該單鏈表的長(zhǎng)度為3HI.靜態(tài)鏈表中的指針

表示的是下一個(gè)元素在數(shù)組中的位置IV.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的

單鏈表之后的算法時(shí)間復(fù)雜度為0(1)

A、僅I、n、in

B、i、□、m、w

c、僅i、m

D、僅i、m、w

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

知識(shí)點(diǎn)解析：i：非空循環(huán)單鏈表的尾結(jié)點(diǎn)指針應(yīng)該指向鏈表頭，即

p—>next=hcad,故I正確?！?head指向頭結(jié)點(diǎn)，head-next就指向第一個(gè)結(jié)點(diǎn)。

既然head^-next—>next->next=head,說明此循環(huán)鏈表共有3個(gè)結(jié)點(diǎn)(包含頭結(jié)

點(diǎn))，而單鏈表中增加頭結(jié)點(diǎn)僅僅是為了更方便地進(jìn)行插入和刪除操作，它并不存

儲(chǔ)線性表的元素，故不能算為單鏈表結(jié)點(diǎn)，故此單鏈表的長(zhǎng)度為2,故II錯(cuò)誤，

n：靜態(tài)鏈表中的指針?biāo)鎯?chǔ)的不再是鏈表中的指針域，而是其下一個(gè)結(jié)點(diǎn)在數(shù)組

中的位置，即數(shù)組下標(biāo)，故in正確。IV：將鏈表連接起來只需0(1)的操作，但找

到具有m個(gè)結(jié)點(diǎn)鏈表的尾結(jié)點(diǎn)需遍歷該鏈表，所以時(shí)間復(fù)雜度應(yīng)該為O(m),故W

錯(cuò)誤。

2、利用棧求表達(dá)式的值時(shí)，設(shè)立運(yùn)算數(shù)棧S。假設(shè)棧S只有兩個(gè)存儲(chǔ)單元，在下

列表達(dá)式中，不發(fā)生溢出的是()。

A、A—B*(C—D)

B、(A—B)*C—D

C、(A—B*C)—D

D、(A—B)*(C—D)

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

知識(shí)點(diǎn)解析：利用棧求表達(dá)式的值時(shí)，需要設(shè)立運(yùn)算符棧和運(yùn)算數(shù)棧，下面僅舉一

例。例如，求2x(5—3)+6/2的過程如表6—2所示。

衰6-2

當(dāng)前字符運(yùn)算符棧運(yùn)算數(shù)枝說明

22

X2

(?(2

5?(25

-?(-25

3253

)22---出棧

,+4出枝

6+46

146

2462

+43*/*出棧

7出棧

從上述的計(jì)算過程中，考生可以自行對(duì)

A、B、C、D選項(xiàng)進(jìn)行練習(xí)，運(yùn)算數(shù)棧S的大小分別至少為4、2、3、3,只有B

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

3、設(shè)有一個(gè)n階三對(duì)角線矩陣A[n][n],現(xiàn)把它的三條對(duì)角線上的非零元素按行存

放到一個(gè)一維數(shù)組B口中，存放到B5中(假定不用0下標(biāo))，那么B[k]

存放的元素的行號(hào)是()c

A、|(k+l)/3]

B、[(k+l)/3]

C、[(k+2)/3]

D、[(k+2)/3]

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

知識(shí)點(diǎn)解析：這種題目最好采用特殊值法，推導(dǎo)過程可能比較繁瑣，見表6—3。

?6-3特殊值推導(dǎo)過程

k123456789

A(i)UlA[l](2]A[2][l]AR][2]A(2][3JA[3][2]A[3][3]A[3)(4]A(4J|3]

r(k+iy311i2223334

4、已知一棵5階B—樹有53個(gè)關(guān)鍵字.并旦每個(gè)結(jié)點(diǎn)的關(guān)鍵字都達(dá)到最少狀態(tài),

則它的深度是()。

A、3

B、4

C、5

D、6

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

知識(shí)點(diǎn)解析：根據(jù)B—樹定義，m階B—樹除根結(jié)點(diǎn)之外，所有非終端結(jié)點(diǎn)至少有

[m⑵=3個(gè)子樹，即至少有2個(gè)關(guān)鍵字。那么在每個(gè)結(jié)點(diǎn)的關(guān)鍵字最少的情況二，

根結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)為1,其他的結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)都為2。又第一層有1個(gè)結(jié)點(diǎn)，第

二層有2個(gè)結(jié)點(diǎn)，第三層有2x3個(gè)結(jié)點(diǎn)，第四層有2x3x3個(gè)結(jié)點(diǎn)。即：

1x1+2x2+2x3x2+2x3x3x2=53,根結(jié)點(diǎn)加非終端剛好四層，葉子結(jié)點(diǎn)那一層不算，

故樹的深度為4。

5、下列說法中，正確的是（）。I.具有10個(gè)葉子結(jié)點(diǎn)的二義樹中有9個(gè)度為2

的結(jié)點(diǎn)E.設(shè)高度為5的二叉樹上只有度為。和度為2的結(jié)點(diǎn)，則該二叉樹中所

包含的結(jié)點(diǎn)數(shù)至少為9HL一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，則可知葉子結(jié)點(diǎn)的

個(gè)數(shù)為501個(gè)IV.高度為h的完全二叉樹最少有211個(gè)結(jié)點(diǎn)

A、僅I、n

B、僅口、m、IV

C、僅I、UI、IV

D、僅I、口、m

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

知識(shí)點(diǎn)解析：I：二叉對(duì)葉子結(jié)點(diǎn)的個(gè)數(shù)比度為2的結(jié)點(diǎn)的個(gè)數(shù)多1,故I正的。

總結(jié)：這個(gè)性質(zhì)在選擇題中常有體現(xiàn)（見下面的補(bǔ)充例題），并且需要靈活運(yùn)用。

比如題目可能問，二叉樹中總的結(jié)點(diǎn)數(shù)為n,則樹中空指針的個(gè)數(shù)是多少？我們可

以將所有的空指針看作葉子結(jié)點(diǎn)，則圖中原有的所有結(jié)點(diǎn)都成了雙分支結(jié)點(diǎn)。因此

可得空指針域的個(gè)數(shù)為附中所有結(jié)點(diǎn)個(gè)數(shù)加1,即n+1個(gè)。這個(gè)性質(zhì)還可以擴(kuò)

展，即在一棵度為m的樹中，度為1的結(jié)點(diǎn)數(shù)為川，度為2的結(jié)點(diǎn)數(shù)為n2……度

為m的結(jié)點(diǎn)數(shù)為nm，則葉子結(jié)點(diǎn)數(shù)no=l+n2+2n3+...+（m—l）nmo推導(dǎo)過程如人：

總結(jié)點(diǎn)=n（）+n]+n2+n3+..+nm...........，①總分支數(shù)=lxni+2xn2+3+mxnm

（度為m的結(jié)點(diǎn)引出m條分支）...........②總分支數(shù)二總結(jié)點(diǎn)數(shù)一

1...........③將式①）和式②代入式③并化簡(jiǎn)得no=l+n2+2n3+...+（m—l）nnl補(bǔ)

充例題：在一棵二叉樹中度為0的結(jié)點(diǎn)個(gè)數(shù)為匕度為1的結(jié)點(diǎn)個(gè)數(shù)為m,則咳二

叉樹采用二叉鏈存儲(chǔ)結(jié)溝時(shí)，有（）個(gè)指針指向孩子結(jié)點(diǎn)。A.kB.mC.2k+m—2

D.2k+mC.本題考查樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。首先，由二叉樹的性質(zhì)可知，no=n2+l

（多次用到，考生一定要記?。。玫絥2=k—l。其次，二叉樹的結(jié)點(diǎn)總數(shù)

n=no+ni+n2=2k+m—1。求指向孩子結(jié)點(diǎn)的指針個(gè)數(shù)其實(shí)就是求該二叉樹的分支

數(shù)，而分支數(shù)就是等于總結(jié)數(shù)一1,所以答案為2k+m—2,故選C選項(xiàng)。H：最

少結(jié)點(diǎn)的情況應(yīng)該是除根結(jié)點(diǎn)層只有1個(gè)結(jié)點(diǎn)外，其余4層都有2個(gè)結(jié)點(diǎn)，因此結(jié)

點(diǎn)總數(shù)為2x(5—1)+1=9。如圖6~4所示，故II正確。圖6y最少結(jié)點(diǎn)的情況總

結(jié)：設(shè)高度為h的二叉樹只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)

點(diǎn)數(shù)至少為2h—l。m:由二叉樹的性質(zhì)可知：no=n2+l,且完全二叉樹度為1的結(jié)

點(diǎn)個(gè)數(shù)要么為0,要么為I。又因?yàn)槎鏄涞目偨Y(jié)點(diǎn)個(gè)數(shù)n=no+n]+n2。n0=n2+l

代入，可得n=2no+ni—1：由于n=1001,得到2no=1002+ni。①當(dāng)ni=l時(shí)，無

解。②當(dāng)n]=0時(shí)，可解得no=5Ol故HI正確。IV：高度為h的完全二叉樹中，第

1層?第h—1層構(gòu)成一個(gè)高度為h—1的滿二叉樹，結(jié)點(diǎn)個(gè)數(shù)為2h1—1。第h層

至少有一個(gè)結(jié)點(diǎn)，所以最少的結(jié)點(diǎn)個(gè)數(shù)二(2卜—1—1)+1=2心1故W錯(cuò)誤。

6、在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)就造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并

已知A的左孩子的平衡因子為一1,右孩子的平衡因子為O,則為使其平衡，應(yīng)做

()型調(diào)整。

A、LL

B、RR

C、RL

D、LR

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

知識(shí)點(diǎn)露析：既然最低不平衡結(jié)點(diǎn)是A,則以A為根的子樹不平衡的情況有4

種，如圖6—5所示。

圖65最小不平衡子樹又因?yàn)锳的左孩

子的平衡因子為一1,右孩子的平衡因子是0,只有第2個(gè)符合，所以應(yīng)當(dāng)做LR

型調(diào)整?！究偨Y(jié)】為了不至于混淆調(diào)整不平衡狀態(tài)時(shí)做出的是什么類型的調(diào)整，

以下介紹一種簡(jiǎn)便的方法：找出最低的不平衡結(jié)點(diǎn)到剛剛插入之后(導(dǎo)致不平衡)

的結(jié)點(diǎn)的路徑，這種路徑的序列也就標(biāo)識(shí)了應(yīng)該做出什么類型的調(diào)整，如圖6—5

的2所示，最低不平衡結(jié)點(diǎn)到插入結(jié)點(diǎn)的路徑序列是LR,那么就應(yīng)該做LR調(diào)

整。

7、下列關(guān)于無向圖的說法中，正確的是（）。I.無向圖中某個(gè)頂點(diǎn)的度是指圖中

與該頂點(diǎn)連通的頂點(diǎn)數(shù)U.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至

少需要n—1條邊ID.無向圖的鄰接矩陣是對(duì)稱矩陣W.具有n個(gè)頂點(diǎn)的無向圖，

最多有"個(gè)連通分量

A、僅I、n、m

B、僅口、nI、w

c、僅m

D、i、n、m、w

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

知識(shí)點(diǎn)解析：i：無向圖頂點(diǎn)的度即為一個(gè)頂點(diǎn)所引出邊的條數(shù)，等價(jià)于一個(gè)頂點(diǎn)

所含有的鄰接頂點(diǎn)的個(gè)數(shù)，而不是與該頂點(diǎn)連通的頂點(diǎn)數(shù)（這樣就會(huì)擴(kuò)大范圍，如

圖6E干向圖

圖―6所示），故I錯(cuò)誤。頂點(diǎn)V2的度應(yīng)該是1,而如果

度是按照?qǐng)D6-6中與該頂點(diǎn)連通的頂點(diǎn)數(shù)來定義，頂點(diǎn)V2的度應(yīng)該是3,明顯錯(cuò)

誤。H:n個(gè)頂點(diǎn)的無向圖要連通的話只需每個(gè)頂點(diǎn)做一個(gè)結(jié)點(diǎn)，構(gòu)成一棵樹即可

（解題關(guān)鍵），并且此時(shí)是邊最少的情況。對(duì)于樹來說，頂點(diǎn)的個(gè)數(shù)比邊要多1,

故n正確。m：顯然，在無向圖中，每條邊（沒有方向）對(duì)應(yīng)于矩陣中與主對(duì)角線

對(duì)稱的兩個(gè)“I”，因此無向圖對(duì)應(yīng)的鄰接矩陣是對(duì)稱的，故in正確。IV：無向圖的

連通分量最少只有一個(gè)，即其自身；最多有n個(gè)，即該圖沒有邊，則每個(gè)頂點(diǎn)構(gòu)成

一個(gè)連通分量，故W正確。

8、下列關(guān)于強(qiáng)連通圖的說法中，正確的是（）。I.n個(gè)頂點(diǎn)構(gòu)成的強(qiáng)連通圖至少

有n條邊口.強(qiáng)連通圖是任何頂點(diǎn)到其他所有頂點(diǎn)都有邊HI.完全有向圖一定是強(qiáng)

連通圖

A、僅I、口

B、僅口、m

c、僅I、m

D、I、nin

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

知識(shí)點(diǎn)解析：I：強(qiáng)連通圖是相對(duì)于有向圖而言的，即在有向圖G中，任何兩個(gè)

頂點(diǎn)都存在路徑。所以最少的情況應(yīng)該是n個(gè)頂點(diǎn)構(gòu)成一個(gè)首尾相連的環(huán)，共有n

條邊，故I正確。n：這個(gè)選項(xiàng)不細(xì)心的話很容易誤選。在有向圖中，邊和路徑是

不同的概念。有向圖中頂點(diǎn)A和B之間存在邊，不能說明A和B是互相連通的，

所以說正確的表述應(yīng)該是強(qiáng)連通圖是任何頂點(diǎn)到其他所有頂點(diǎn)都有路徑，故n錯(cuò)

誤。n：完全有向圖肯定是任何頂點(diǎn)到其他所有頂點(diǎn)都有路徑，故in正確。

9、假設(shè)初始為空的散列表的地址空間為（0-10）,散列函數(shù)為H（key）=keymod

11,采用線性探測(cè)再散列法處理沖突，若依次插入關(guān)鍵字37、95、27、14、48,

則最后一個(gè)關(guān)鍵字值48的插入位置是（）。

A、4

B、5

C、6

D、8

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

知識(shí)點(diǎn)解析：首先通過散列函數(shù)H(key)=keymod11的計(jì)算得知，37、95、27、14

分別插入到散列表中的4、7、5、3的位置。而48mod11=4,但是此時(shí)4已經(jīng)有元

素了，根據(jù)線性探測(cè)再散列法處理沖突的原則，依次探測(cè)位置4的下一個(gè)地址，直

到此地址為空，發(fā)現(xiàn)6為空則插入，故選C選項(xiàng)。補(bǔ)充：如果此題改為使用平方

探測(cè)法，則又應(yīng)該選擇哪一個(gè)選項(xiàng)？解析：平方探測(cè)法的原理是設(shè)發(fā)生沖突的地

址為d,則平方探測(cè)法的探測(cè)序列為d+12,d_12,d+22,d_22,…。位置4不空

時(shí)，下一個(gè)探測(cè)的位置應(yīng)該為5,發(fā)現(xiàn)又不空，則下一個(gè)探測(cè)的位置應(yīng)該是3,發(fā)

現(xiàn)又不空。接著再探測(cè)位汽8,發(fā)現(xiàn)為空，將元素插入，故選D選項(xiàng)。平方探測(cè)

法是一種較好的處理沖突的方法，可以避免出現(xiàn)堆積問題。它的缺點(diǎn)是不能探測(cè)到

散列表上的所有單元，但至少能探測(cè)到一半單元。

10、設(shè)待排序元素序列所有元素的排序碼都相等，則下列排序方法中排序速度最慢

的是()。

A、直接插入排序

B、起泡排序

C、簡(jiǎn)單選擇排序

D、基數(shù)排序

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

知識(shí)點(diǎn)解析?：當(dāng)所有待排序元素的排序碼都相等時(shí)，直接插入排序的排序碼比較次

數(shù)為n—1,元素移動(dòng)次數(shù)為0；起泡排序的排序碼比較次數(shù)為n—1,元素移動(dòng)個(gè)

數(shù)為0;簡(jiǎn)單選擇排序的排序碼比較次數(shù)為n(n—1)/2,元素移動(dòng)次數(shù)為0；基數(shù)排

序采用靜態(tài)鏈表存儲(chǔ)待排序元素，用于分配的桶亦采用鏈?zhǔn)疥?duì)列，排序碼比較次數(shù)

為nxd(d是排序碼位數(shù))，元素移動(dòng)次數(shù)為0,故排序速度最慢的是簡(jiǎn)單選攔排

序。

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

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

A、20

B、300

C、396

D、500

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

知識(shí)點(diǎn)解析：假設(shè)采用k路平衡歸并排序算法，則敗者樹的高度為［log2k|+l。在每

次調(diào)整后，找下一個(gè)具有最小排序碼記錄時(shí)，最多做［log2］次排序碼比較。由題意

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

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

12、下列說法中，錯(cuò)誤的是（）。I.設(shè)浮點(diǎn)數(shù)的基數(shù)為4,尾數(shù)用原碼表示，則

0.000010為規(guī)格化數(shù)U.浮點(diǎn)數(shù)運(yùn)算中，運(yùn)算結(jié)果超出尾數(shù)表示范圍則表示溢出

川.任何情況下，浮點(diǎn)數(shù)的右規(guī)操作最多只會(huì)進(jìn)行一次

A、僅I、m

B、僅口、皿

c、僅I、n

D、I、II和HI

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

知識(shí)點(diǎn)解析：I：對(duì)于原碼表示的基值為4的小數(shù)，規(guī)格化的形式是小數(shù)點(diǎn)后2位

不全為0,故【錯(cuò)誤。最笨的解題思路：基數(shù)『4,由于1/E|M|W,即尾數(shù)的十進(jìn)

制絕對(duì)值在0.25?1之間。而（0.000010）2=0.03125,故不是規(guī)格化數(shù)。D：浮點(diǎn)

數(shù)的溢出并不是由尾數(shù)來判斷的，而是規(guī)格化后階碼超出所能表示的范圍時(shí)，才表

示溢出，故n錯(cuò)誤。皿在浮點(diǎn)數(shù)的運(yùn)算過程中，尾數(shù)如果出現(xiàn)01.XXX…X和

10.XXX...X,則需要進(jìn)行右規(guī)，并且只需進(jìn)行一次右規(guī)尾數(shù)就會(huì)變成規(guī)格化數(shù)，

但是左規(guī)操作可能不止一次，故in正確。

13、下列關(guān)于定點(diǎn)數(shù)原碼一位乘法的描述中，錯(cuò)誤的是（）。I.符號(hào)位不參加運(yùn)

算，根據(jù)數(shù)值位的乘法運(yùn)算結(jié)果確定結(jié)果的符號(hào)位n.在原碼一位乘算法過程

中，所有的移位均是算術(shù)移位操作皿.假設(shè)兩個(gè)n位數(shù)進(jìn)行原碼一位乘，部分積

至少需要使用n位寄存器

A、僅I、n

B、僅口、皿

c、僅I、m

D、I>n>in

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

知識(shí)點(diǎn)解析：I：在原碼一位乘算法過程中，符號(hào)位是不參加運(yùn)算的，結(jié)果的符號(hào)

位是被乘數(shù)的符號(hào)位和乘數(shù)的符號(hào)位異或的結(jié)果，故I錯(cuò)誤。n：在原碼一位乘算

法過程中，由于參與操年的數(shù)是真值的絕對(duì)值，所以沒有正負(fù)可言，故在原碼一位

乘法中運(yùn)算過程中所有的移位均是邏輯移位操作，即在高位添加o,故口錯(cuò)誤，

n：由于在部分積相加中，可能導(dǎo)致兩個(gè)小數(shù)相加大于1,所以部分積至少需要使

用n+l位寄存器，故皿錯(cuò)誤。

14、某容量為256MB的存儲(chǔ)器由若干16Mx8bitDRAM芯片構(gòu)成，該DRAM芯片

的地址引腳和數(shù)據(jù)引腳總數(shù)是（）。

A、20

B、24

「、32

D、36

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

知識(shí)點(diǎn)解析：很多不了解DRAM引腳結(jié)構(gòu)的同學(xué)很可能會(huì)得出24+8=32的結(jié)果，

其實(shí)這是不正確的，在《高分筆記》當(dāng)中講過半導(dǎo)體存儲(chǔ)芯片的譯碼驅(qū)動(dòng)方式，其

中介紹了重合法，將存儲(chǔ)單元分成行和列，然后分別通過行地址線和列地址線來確

定行列地址從而確定一個(gè)單元，這里DRAM采用引腳復(fù)用，將行地址線和列地址

線合用作一組，只不過在譯碼時(shí)，需要發(fā)送兩次地址信號(hào)（相當(dāng)于一次行地址，

次列地址），從而減少了DRAM的引腳總數(shù)，便于設(shè)計(jì)DRAM；因此這里地址空

間是16M,需要24個(gè)地址位來標(biāo)識(shí)，分為兩次發(fā)送，則地址引腳數(shù)為12,故地址

引腳和數(shù)據(jù)引腳總數(shù)為12+8=20。【總結(jié)】DRAM芯片采用引腳復(fù)用，且行列地

址位數(shù)一致。

15、現(xiàn)有一64Kx2bit的存儲(chǔ)器芯片，欲設(shè)計(jì)具有同樣存儲(chǔ)容量的存儲(chǔ)器，有（）種方

法可以合理地安排地址線和數(shù)據(jù)線引腳的數(shù)目，且使兩者之和最小。

A、2

B、3

C、4

D、5

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

知識(shí)點(diǎn)解析：不妨設(shè)地址線和數(shù)據(jù)線的數(shù)目分別為x和y。只需要滿足

2xxy=64Kx2,所以就有如下方案：當(dāng)產(chǎn)1時(shí)，x=17；當(dāng)y=2時(shí)，x=16；當(dāng)y=4

時(shí)，x=15；當(dāng)y=8時(shí)，x=14；后面的就不要計(jì)算了，肯定比前面的引腳數(shù)目多。

從以上分析可以出看，當(dāng)數(shù)據(jù)線分別為1或2時(shí)，地址線和數(shù)據(jù)線引腳的數(shù)目之和

為18,達(dá)到最小，并且有兩種解答。

16、某計(jì)算機(jī)有30個(gè)通用寄存器，采用32位定長(zhǎng)指令字，操作碼字段（不含尋址

方式）為8位，Add指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址

尋址方式。若基址寄存器可使用任一通用寄存器，且偏移量用補(bǔ)碼表示，則Add

指令中偏移量的取值范圍是（）。

A、一4096?4095

B、一2048?2047

C、-1023—1024

D、—3071~3072

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

知識(shí)點(diǎn)解析：首先可以直接排出C、D選項(xiàng)，因?yàn)闊o論偏移量是多少位，由于偏移

量是采用補(bǔ)碼表示的，艱據(jù)補(bǔ)碼的特性，它比源碼表示的數(shù)多一位，而且多出來的

就是補(bǔ)碼的最小值。因此偏移量的最小值一定是一個(gè)偶數(shù)。操作碼占8位，兩個(gè)操

作數(shù)具有兩種不同的尋址方式，則需要2位尋址特征位，另外一共有30個(gè)寄存

器，故需要5位來標(biāo)識(shí)選擇哪個(gè)寄存器，所以偏移量的位數(shù)=32—8—2—5-

5=12,而12位的帶符號(hào)的補(bǔ)碼所能表示的數(shù)的范圍為一2048?2047。【提示】在

考場(chǎng)卜有時(shí)候即便我們不能一步就算出結(jié)果，或者題目復(fù)雜的時(shí)候,可以抓住問題

的一些細(xì)節(jié)來排除某些選項(xiàng)，這對(duì)我們分析余下的選項(xiàng)也是很有幫助的。

17、與本指令的地址有關(guān)的尋址方式是（）。

A、寄存器尋址

B、直接尋址

C、相對(duì)尋址

D、間接尋址

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

知識(shí)點(diǎn)解析：相對(duì)尋址本身就是相對(duì)于本指令地址進(jìn)行上下浮動(dòng)，所以相對(duì)尋址的

區(qū)間范圍和本指令的地址密切相關(guān)，其他3個(gè)選項(xiàng)都與本指令的地址無關(guān)。

18、假定執(zhí)行最復(fù)雜的指令需要完成6個(gè)子功能，分別由對(duì)應(yīng)的功能部件A?F來

完成，每個(gè)功能部件所花的時(shí)間分別為80ns、40ns、50ns、70ns>20ns、30ns,流

水線寄存器延時(shí)為20ns,現(xiàn)把最后兩個(gè)功能部件E和F合并，以產(chǎn)生一個(gè)五段流

水線。該五段流水線的時(shí)鐘周期至少是（）。

A^70ns

B、80ns

C、90ns

D、100ns

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

知識(shí)點(diǎn)解析：指令的各個(gè)子功能在不同的部件中是并行執(zhí)行的，因此執(zhí)行這條指令

的時(shí)間一定是各個(gè)子功能中所花的最長(zhǎng)時(shí)間，當(dāng)前最長(zhǎng)時(shí)間為80ns,當(dāng)合并E和

F這兩個(gè)功能部件之后，合并子功能執(zhí)行時(shí)間為50ns,因此最長(zhǎng)的時(shí)間還是

80ns,再加上20ns的寄存器延遲，所以五段流水線的時(shí)鐘周期至少是100ns。

19、在微程序控制器中，執(zhí)行指令微程序的首條微指令地址是由（）得到的。

A、程序計(jì)數(shù)器PC

B、前條微指令

C、uPC+1

D、指令操作碼映射

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

知識(shí)點(diǎn)解析：本題問的是微程序中首條微指令的地址，稍不注意就可能誤選B,微

程序是用來解釋指令的,通過指令操作碼的內(nèi)容來區(qū)別指令,然后根據(jù)指令操作碼

映射找到對(duì)應(yīng)解釋這個(gè)指令的微程序段。因此首條微指令的地址是由指令操作碼映

射而來的。

20、指令流水線中出現(xiàn)數(shù)據(jù)相關(guān)時(shí)流水線將受阻，（）可解決數(shù)據(jù)相關(guān)問題。

A、增加硬件資源

B、采用旁路電路技術(shù)

C、采用分支預(yù)測(cè)技術(shù)

D、A?C都可以

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

知識(shí)點(diǎn)解析：在流水線處理器中處理數(shù)據(jù)相關(guān)問題有兩種方法：一種是暫停相關(guān)指

令的執(zhí)行，即暫停流水線，直到能夠正確讀出寄存器操作數(shù)為止；另一種是采用旁

路電路技術(shù)，即采用專門的數(shù)據(jù)通路，直接把結(jié)果送到ALU的輸入端，也就是把

內(nèi)部數(shù)據(jù)前推，即不必等待某條指令的執(zhí)行結(jié)果寫回到寄存器后，再從寄存器取出

結(jié)果，而是直接將執(zhí)行結(jié)果通過專用通路送至需要該結(jié)果的地方。

21、在計(jì)數(shù)器定時(shí)查詢方式下，若每次計(jì)數(shù)從|n/2］開始，則（）。

A、設(shè)備號(hào)小的優(yōu)先級(jí)高

B、每個(gè)設(shè)備使用總線的機(jī)會(huì)相等

C、設(shè)備號(hào)大的優(yōu)先級(jí)高

D、以上說法都不正確

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

知識(shí)點(diǎn)解析：當(dāng)每次計(jì)數(shù)從［n/2］開始時(shí)，所有設(shè)備被分為兩部分，設(shè)備號(hào)為［H2］到

n的設(shè)備優(yōu)先級(jí)高于設(shè)備號(hào)為0到［n⑵-1的設(shè)備：且在這兩部分內(nèi)，卻是設(shè)備小

的優(yōu)先級(jí)高，故A、B、C選項(xiàng)都是錯(cuò)誤的。

22、以下4個(gè)步驟在通道過程中的正確順序是（）。I.組織I/O操作D.向CPU

發(fā)出中斷請(qǐng)求HI.編制通道程序W.啟動(dòng)I/O通道

A、I—>n—?川―iv

B、U—III—I—W

c、I

D、m—w-i->n

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

知識(shí)點(diǎn)解析?：通道的工作過程如下：（1）用戶程序中使用訪管指令進(jìn)入操作系統(tǒng)的

管理程序，由CPU通過管理程序組織一個(gè)通道程序，并使用I/O指令啟動(dòng)通道

（此后CPU就可以并行運(yùn)行應(yīng)用程序了）。（2）通道并行執(zhí)行CPU為它組織的通

道程序（通道程序在主存中），完成指定的數(shù)據(jù)輸入輸出工作。（3）通道程序結(jié)束

后向CPU發(fā)出中斷請(qǐng)求。CPU響應(yīng)這個(gè)中斷請(qǐng)求后，第二次調(diào)用管理程序?qū)斎?/p>

輸出中斷請(qǐng)求進(jìn)行處理。這樣，每完成一次輸入輸出工作，CPU只需要兩次調(diào)用

管理程序，大大減少了對(duì)用戶程序的打擾。補(bǔ)充：在采用通道結(jié)構(gòu)的系統(tǒng)中，也

需要使用I/O指令，但這種I/O指令比較簡(jiǎn)單，它并不直接控制具體1/0操作，只

是負(fù)責(zé)通道的啟動(dòng)和停止、查詢通道或設(shè)備的狀態(tài)，從而控制通道去完成I/O操

作。

23、下列關(guān)于批處理技術(shù)和多道程序設(shè)計(jì)技術(shù)說法中，正確的是（）。I.批處理系

統(tǒng)的最主要缺點(diǎn)是不能并發(fā)執(zhí)行H,所謂多道程序設(shè)計(jì)，是指每一個(gè)時(shí)刻有若干個(gè)

進(jìn)程在執(zhí)行in.引入多道程序設(shè)計(jì)的前提條件之一是系統(tǒng)具有中斷功能w,采用多

道程序設(shè)計(jì)的系統(tǒng)中，系統(tǒng)的程序道數(shù)越多，系統(tǒng)的效率越高

A、僅I、口

B、僅口、m

c、僅m

D、僅I、w

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

知識(shí)點(diǎn)解析：I錯(cuò)誤，讓處理系統(tǒng)的最主要缺點(diǎn)是缺乏交互性。I的表述肯定是錯(cuò)

的，多道批處理系統(tǒng)就可以并發(fā)執(zhí)行多個(gè)程序。這里多道是指允許多個(gè)進(jìn)程同時(shí)駐

留在主存中，按照某種原則分派處理機(jī)，逐個(gè)執(zhí)行這些程序。這里其實(shí)還考查了

并發(fā)的概念。并行性是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生；而并發(fā)性是指兩個(gè)或

多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。n錯(cuò)誤，多道程序設(shè)計(jì)是指把多個(gè)程序同時(shí)存

放在內(nèi)存中，使它們同時(shí)處于運(yùn)行狀態(tài)。但是，在單處理機(jī)環(huán)境中，同一時(shí)刻只有

一個(gè)進(jìn)程在執(zhí)行。知識(shí)點(diǎn)回顧：多道程序設(shè)計(jì)技術(shù)的主要特點(diǎn)是多道、宏觀上并

行、微觀上串行。多道是指計(jì)算機(jī)內(nèi)存中同時(shí)存放多個(gè)相互獨(dú)立的程序。宏觀上

并行是指同時(shí)進(jìn)入系統(tǒng)中的多道程序都處于運(yùn)行過程中（即同時(shí)存放在內(nèi)存中）。

微觀上串行是指在單處理機(jī)環(huán)境中，內(nèi)存中的多道程序輪流占有CPU,交替執(zhí)

行。HI正確，有了中斷后才能實(shí)現(xiàn)進(jìn)程間并發(fā)，進(jìn)程間并發(fā)才有可能把多個(gè)進(jìn)程

裝入到內(nèi)存實(shí)現(xiàn)多道程序技術(shù)。w錯(cuò)誤，程序道數(shù)如果過多的話，會(huì)導(dǎo)致每個(gè)程

序分配到的內(nèi)存不夠，很多程序所需的程序和代碼需要臨時(shí)從磁盤調(diào)入到內(nèi)存，系

統(tǒng)會(huì)頻繁地處于I/O狀態(tài)中，導(dǎo)致系統(tǒng)效率降低。

24、假設(shè)系統(tǒng)中所有進(jìn)程是同時(shí)到達(dá)，則最不利于短作業(yè)的進(jìn)程調(diào)度算法是（）。

A、FCFS

B、SPF

C、RR

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

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

知識(shí)點(diǎn)解析：本題可用排除法。首先排除B選項(xiàng)。因?yàn)樗嵌套鳂I(yè)優(yōu)先算法，肯

定是有利于短作業(yè)的。然后繼續(xù)排除C選項(xiàng)。RR兼顧長(zhǎng)短作業(yè)，一般來說在時(shí)間

片不是的太長(zhǎng)的情況下，對(duì)于短作業(yè)還是比較公平的。（時(shí)間片設(shè)的無限長(zhǎng)，即變

成了FCFS算法。）最后排除D選項(xiàng)。響應(yīng)比二作業(yè)響應(yīng)時(shí)間/作業(yè)執(zhí)行時(shí)間二

（作業(yè)執(zhí)行時(shí)間+作業(yè)等待時(shí)間）/作業(yè)執(zhí)行時(shí)間=1+作'也等待時(shí)間/作業(yè)執(zhí)行時(shí)間

在作業(yè)等待時(shí)間相同的情況下，短作業(yè)的響應(yīng)比是更高的，所以高響應(yīng)比優(yōu)先有利

于短作業(yè)。綜上分析，本題選A選項(xiàng)。知識(shí)點(diǎn)回顧：表6—4給出幾種常見的進(jìn)

程調(diào)度算法特點(diǎn)的總結(jié)，讀者要在理解的基礎(chǔ)上識(shí)記。

袤J常見的進(jìn)程調(diào)度算法特點(diǎn)

先來先服務(wù)短作業(yè)優(yōu)先高響應(yīng)比優(yōu)先時(shí)間片輪轉(zhuǎn)多級(jí)反饋隊(duì)列

能否是可搶占否能能能隊(duì)列內(nèi)算法不一定

能否是不可搶占能能能否隊(duì)列內(nèi)算法不一定

平均等椅時(shí)間?兼或長(zhǎng)煙作業(yè)，4.較好

優(yōu)點(diǎn)公平,實(shí)現(xiàn)簡(jiǎn)單兼顧長(zhǎng)短作業(yè)兼顧長(zhǎng)短作業(yè)

少.效率?高的響應(yīng)時(shí)間,可行等強(qiáng)

長(zhǎng)作業(yè)公饑計(jì)翼響應(yīng)比的平均等待時(shí)間較長(zhǎng).

殿點(diǎn)不利于短作業(yè)無

估計(jì)時(shí)間不易?定開銷大t卜文切換浪費(fèi)時(shí)間

作業(yè)調(diào)度，批處

如用于無無分時(shí)系統(tǒng)相當(dāng)遢用

理系統(tǒng)

決策模式非搶占等搶占再搶占搶占搶占

25、Pi（）｛Lock（m_mutex）；//含義為獲取互斥信號(hào)量a=newint[100]；〃開辟一

個(gè)大小為100的整星數(shù)組空間，〃并用全局指針變量a保存空間地址UnLock

（m_mutex）；free（a）；//釋放數(shù)組空間，且a的值不改變｝有多個(gè)優(yōu)先級(jí)相同的進(jìn)

程Pi。試問下列同時(shí)運(yùn)行多個(gè)進(jìn)程Pi,可能會(huì)出現(xiàn)的錯(cuò)誤是（）。

A、內(nèi)存泄露

B、內(nèi)存越界訪問

C、內(nèi)存泄露和內(nèi)存越界訪問

D^無

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

知識(shí)點(diǎn)解析：由于a為全局指針變量，即屬于臨界資源，訪問a的代碼都屬于臨界

區(qū)，臨界區(qū)應(yīng)該在Lock(m_mulex)和UnLock(m_mutex)之間，使各個(gè)進(jìn)程互斥訪問

a。但由于本題free(a)在Lock(m_mutex)和UnLock(m_mutex)之外，所以是會(huì)出現(xiàn)

錯(cuò)誤的。舉例：假設(shè)有進(jìn)程P1示口P2,PI進(jìn)程申請(qǐng)的數(shù)組空間地址賦給a之后，還

沒有free掉。P2進(jìn)程又申請(qǐng)了新的數(shù)組空間又把地址賦給a,導(dǎo)致Pl進(jìn)程申請(qǐng)的

空間地址丟失(即內(nèi)存泄露)。然后P1進(jìn)程繼續(xù)執(zhí)行，P1進(jìn)程執(zhí)行free操作，將

P2進(jìn)程申請(qǐng)的空間釋放掉了，P2進(jìn)程繼續(xù)執(zhí)行，P2進(jìn)程執(zhí)行free操作，free操作

訪問了不屬于P2進(jìn)程的空間(之前已經(jīng)被P1釋放掉了)，會(huì)發(fā)生內(nèi)存越界訪

問。知識(shí)點(diǎn)擴(kuò)展：內(nèi)存泄露：當(dāng)以前分配的一片內(nèi)存不再需要使用或無法訪問

時(shí)，但是并沒有釋放它，那么對(duì)于該進(jìn)程來說，會(huì)因此導(dǎo)致總可用內(nèi)存的減少，這

時(shí)就出現(xiàn)了內(nèi)存泄漏。內(nèi)存越界訪問：簡(jiǎn)單地說，進(jìn)程訪問了不屬于該進(jìn)程的內(nèi)

存空間。

26、生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程代碼如下。生產(chǎn)者進(jìn)程有一個(gè)局部變量

nextProduced,以存儲(chǔ)新產(chǎn)生的新項(xiàng)：while(1){/*produceaniteminnextProduced*/

while({in+l)%BUFFERSIZE==out)；/?donothing*/buffer|in］=nextProduced；

in=(in+l)%BUFFERSIZE；.}消費(fèi)者進(jìn)程有一個(gè)局部變量nextConsumed,以存儲(chǔ)

所要使用的項(xiàng)：while(1)(while(in==out)；/*donothing*/

nextConsumed=buffer［out］；out=(out+1)%BUFFERSIZE；/*consumetheitemin

nextConsumed*/}當(dāng)in==outfll(in+l)%BUFFER_SIZE==out條件成立的時(shí)候，緩沖

區(qū)中item數(shù)目各是()o

A、0,BUFFER.SIZE

B、0,BUFFER.SIZE—1

C、BUFFER_SIZE_1,0

D、BUFFER_S1ZE,0

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

知識(shí)點(diǎn)解析?：通過閱讀代碼可知，變量in指向緩沖區(qū)中下一個(gè)空位，變量。ut指向

緩沖區(qū)中的第一個(gè)非空位。BUFFERSIZE是緩沖區(qū)最大能容納的ilem數(shù)目。

buffer中，非空的位置范圍是［oul,由一1］或者［out,BUFFER_SIZE—1］U［0,in—

1］，即有如圖6—7所示的兩種情況。

out——in—

??in~~i

in--out—1

口II

圖67出現(xiàn)的兩種情況當(dāng)in=out時(shí)，前一個(gè)操

作肯定是運(yùn)行了消費(fèi)者進(jìn)程(oul追上了in),因?yàn)樯a(chǎn)者進(jìn)程中，當(dāng)遇到(in-1)%

BUFFER_SIZE==out時(shí)就忙等，即生產(chǎn)進(jìn)程無法使in=out,所以此時(shí)緩沖區(qū)白

ilem數(shù)目應(yīng)該是0。當(dāng)(in+l)%BUFFER_SIZE==oul時(shí)，即in差一個(gè)空位就追上

out了，此時(shí)緩沖區(qū)中ilem數(shù)目應(yīng)該是BUFFER_SIZE—1。所以本題正確答案是

B選項(xiàng)。

27、某操作系統(tǒng)采用可變分區(qū)分配存儲(chǔ)管理方法，操作系統(tǒng)占用低地址部分的

126KBo用戶區(qū)大小為386KB,且用戶區(qū)始址為126KB,用空閑分區(qū)表管理空閑

分區(qū)。若分配時(shí)采用分配空閑區(qū)高地址的方案，且初始時(shí)用戶區(qū)的386KB空間空

閑，對(duì)下述申請(qǐng)序列：作業(yè)1中請(qǐng)80KB,作業(yè)2申請(qǐng)56KB,作業(yè)3申請(qǐng)

120KB,作業(yè)1完成并釋放空間，作業(yè)3完成并釋放空間，作業(yè)4申請(qǐng)156KB，作

業(yè)5申請(qǐng)80KB。如果用首次適應(yīng)算法處理上述序列，最后的空閑分區(qū)的首地址為

()。

A、126

B、432

C、256

D、220

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

知識(shí)點(diǎn)解析：本題需要注意的有，一般首次適應(yīng)算法是要求空閑分區(qū)鏈以地址遞增

的次序鏈接，本題相反，是以地址遞減的順序鏈接的。為描述方便，本題用“(分

區(qū)首址，分區(qū)長(zhǎng)度)',的形式描述系統(tǒng)中的分區(qū)。由題中所給條件可知，最初系統(tǒng)

中只有一個(gè)空閑區(qū),大小為386KB,始址為126KB,即(126KB,386KB)。采用首

次適應(yīng)算法的操作流程如表J5所示。

衰&5首次適應(yīng)輯法的操作流程

掾作已分配區(qū)空閑區(qū)

初始無(126KB.386KB)

作業(yè)1申請(qǐng)80KB(432KB.80KB)(126KB.306KB)

作業(yè)2申請(qǐng)56KB(432KB.80KB>(126KB.250KB)

(376KB.56KB)

作業(yè)3申請(qǐng)120KB(432KB.80KB)(126KB.130KB)

(376KB.56KB)

(256KB.120KB)

作業(yè)1R放80KB(376KB.56KB)(126KB.130KB》

(256KB.120KB)(432KB.80KB)

作業(yè)3科放120KB(376KB.S6KB)(126KB.2S0KB)

(432KB.80KB)

作業(yè)4申謙156KB(376KB.56KB)(126KB.94KB)

(220KB.156KB)(432KB.80KB)

作業(yè)5申清80KB(376KB.56KB)(126KB.94KB)

(220KB,IS6KB)

(432KB.80KB)

28、在分頁式系統(tǒng)中，分頁由()實(shí)現(xiàn)。

A、程序員

B、編譯器

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

D、系統(tǒng)

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

知識(shí)點(diǎn)解析：分頁由操作系統(tǒng)自動(dòng)實(shí)現(xiàn)，對(duì)用戶透明?！究偨Y(jié)】關(guān)于“透明問

題”：（1）覆蓋對(duì)程序員是可見的；（2）交換對(duì)程序員是透明的；（3）在分頁系統(tǒng)環(huán)境

下，分頁對(duì)程序員是透明的；（4）聯(lián)想寄存器的地址變換對(duì)操作系統(tǒng)是透明的。

29、在頁式虛擬管理系統(tǒng)中，假定駐留集為m個(gè)頁幀（初始所有頁幀均為空），

在長(zhǎng)為p的引用串中具有n個(gè)不同頁號(hào)（n>m）,對(duì)于FIFO、LRU兩種頁面替換算

法，其缺頁中斷的次數(shù)的范圍分別為（）。

A、|m,p|和［n,p|

B、［m,n］和［n,p］

CN［n,p］和［m,n］

D、［n,p］和［n,p］

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

知識(shí)點(diǎn)解析：缺頁中斷的原因是當(dāng)前訪問的頁不在內(nèi)存，需將該頁調(diào)入主存。此時(shí)

不管主存是否已滿（已滿則先調(diào)出一頁），都要發(fā)生一次缺頁中斷。即無論怎么安

排，n個(gè)不同的頁號(hào)在首次進(jìn)入主存時(shí)必須要發(fā)生一次缺頁中斷，總共發(fā)生n次，

這就是缺頁中斷的下限。雖然不同頁號(hào)數(shù)位n,小于或等于總長(zhǎng)度p（訪問率可能

會(huì)有一些頁重復(fù)出現(xiàn)），但駐留集mVn,所以可能會(huì)有某些頁進(jìn)入主存后又被調(diào)

出主存，當(dāng)再次訪問時(shí)乂發(fā)生一次缺頁中斷的現(xiàn)象，即有些頁可能會(huì)出現(xiàn)多次缺頁

中斷。極端情況是每訪問一個(gè)頁號(hào)時(shí)，該頁都不在主存，這樣共發(fā)生了p次故障。

所以無論對(duì)于FIFO或者LRU替換算法，其缺頁中斷的上限均為p,下限均為n。

例如：當(dāng)m=3,p=12,n=4時(shí)，有如下訪問串：111223334444則缺頁中斷

數(shù)為4,恰好是不同頁號(hào)數(shù)，即缺頁中斷下限。又如：訪問串為2341234123

4則缺頁中斷為12,恰好是引用串長(zhǎng)度值，即缺頁中斷上限。

30、設(shè)有一個(gè)記錄式文'牛.采用鏈接分配方式，邏輯記錄的固定長(zhǎng)度為I00R.記

錄類型是英文文本（例如：WelcOmEtoTiaNqin!）,在磁盤上存儲(chǔ)時(shí)采用成組分

解技術(shù)。盤塊長(zhǎng)度為512B。如果該文件的目錄項(xiàng)已經(jīng)讀入內(nèi)存，用戶現(xiàn)在需要規(guī)

范第22個(gè)邏輯記錄中的大小寫格式，該操作共需啟動(dòng)硬盤的次數(shù)為（）。

A、1

B、2

C、5

D、6

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

知識(shí)點(diǎn)解析:第22個(gè)邏輯記錄對(duì)應(yīng)第4（22x100/512—4余152）個(gè)物理塊，即讀

入第5個(gè)物理塊的數(shù)據(jù)，由于文件采用的物理結(jié)構(gòu)是鏈接文件，因此需要從目錄項(xiàng)

所指的第一個(gè)物理塊開始讀取，依次讀到第4塊才得到第5塊的物理地址，然后讀

入第5塊的內(nèi)容到內(nèi)存（啟動(dòng)了5次），處理完后，寫回磁盤（啟動(dòng)了6次）。

參數(shù)值

旋W速率7200r/min

Tyl9ms

每條磁道的平均扇區(qū)數(shù)400

估計(jì)訪問一個(gè)磁盤扇區(qū)的平均時(shí)間Taccess約為()。

A、4ms

B、8ms

C、13ms

D、17ms

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

知識(shí)點(diǎn)解析：對(duì)于這個(gè)磁盤，平均旋轉(zhuǎn)延遲(以ms為單位)為Tavg

rotational/2xTmaxrotation=l/2x(60/7200r/min)x1OOOms/sMms平均傳送時(shí)間為Tavg

roiaiion=60/7200i7minx1/400扇區(qū)/磁道xlOOOms/s-0.02ms綜上所述，整個(gè)估計(jì)的訪

=++=

問時(shí)間為TaccessTavgseekTavgrotationTavgtransfer9nis+4ms+0.02ms=13.02ms注

意：磁盤以扇區(qū)大小的塊來讀寫數(shù)據(jù)。對(duì)扇區(qū)的訪問時(shí)間(accesstime)有3個(gè)主要

的部分：尋道時(shí)間(seektime)、旋轉(zhuǎn)時(shí)間(rotationallatency)和傳送時(shí)間(transfer

time)。尋道時(shí)間：為了讀取某個(gè)目標(biāo)扇區(qū)的內(nèi)容，傳動(dòng)臂首先將讀/寫頭定位到包

含目標(biāo)扇區(qū)的磁道上。移動(dòng)傳動(dòng)臂所需的時(shí)間稱為尋道時(shí)間。尋道時(shí)問Tseek依賴

于讀/寫頭以前的位置和傳動(dòng)臂在盤面上移動(dòng)的速度?，F(xiàn)代驅(qū)動(dòng)器中平均尋道時(shí)間

Tavgseek是通過對(duì)幾千次對(duì)隨機(jī)扇區(qū)的尋道求平均值來測(cè)量的，通常為3?9ms。一

次尋道的最大時(shí)間Tmaxseek可以高達(dá)20ms。旋轉(zhuǎn)時(shí)間：一旦讀/寫頭定位到了期望

的磁道，驅(qū)動(dòng)器等待目標(biāo)扇區(qū)的第一個(gè)位旋轉(zhuǎn)到讀，寫頭下。這個(gè)步驟的性能依賴

于當(dāng)讀/寫頭到達(dá)目標(biāo)扇區(qū)盤面時(shí)的位置和磁盤的旋轉(zhuǎn)速度。在最壞的情況下，讀/

寫頭剛剛錯(cuò)過了目標(biāo)扇區(qū)，必須等待磁盤轉(zhuǎn)一整圈。因此，最大旋轉(zhuǎn)延遲(以秒(S)

,160s

1maxrotation"；-~

為單位)為F/min，m，n平均旋轉(zhuǎn)時(shí)間Tavgregion是Tmaxro儂ion的一

半。傳送時(shí)間：當(dāng)目標(biāo)扇區(qū)的第一個(gè)位位于讀/寫頭下時(shí)，驅(qū)動(dòng)器就可以開始讀或

者寫該扇區(qū)的內(nèi)容了。一個(gè)扇區(qū)的傳送時(shí)間依賴于旋轉(zhuǎn)速度和每條磁道的扇區(qū)數(shù)

目。因此，我們可以粗略地估計(jì)一個(gè)扇區(qū)以秒⑸為單位的平均傳送時(shí)間如下：

1160s

T*vgrcx?tion=_____x__________________x_____

r/min（平均扇區(qū)數(shù)/磁道）Imin

32、下列關(guān)于設(shè)備驅(qū)動(dòng)程序的敘述中，正確的是()，I.與設(shè)備相關(guān)的中斷處理

過程是由設(shè)備驅(qū)動(dòng)程序完成的n.由于驅(qū)動(dòng)程序與I/O設(shè)備(硬件)緊密相關(guān)，

故必須全部用匯編語言書寫in.磁盤的調(diào)度程序是在設(shè)備驅(qū)動(dòng)程序中運(yùn)行的

IV.一個(gè)計(jì)算機(jī)系統(tǒng)配置了2臺(tái)同類繪圖機(jī)和3臺(tái)司類打印機(jī)，為了正確驅(qū)動(dòng)這些

設(shè)備，系統(tǒng)應(yīng)該提供5個(gè)設(shè)備驅(qū)動(dòng)程序

A、僅I、m

B、僅口、皿

c、僅I、m、w

D、I、n、山、w

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

知識(shí)點(diǎn)解析：子網(wǎng)掩碼為255.255.255.192,則表示用原C類網(wǎng)的8位主機(jī)號(hào)的前

兩位表示子網(wǎng)號(hào)，剩下的6位表示子網(wǎng)中的主機(jī)號(hào)，所以每個(gè)子網(wǎng)最多有62臺(tái)主

機(jī)（26—2=62）。C正確。知識(shí)點(diǎn)回顧：不同類型的設(shè)備應(yīng)有不同的設(shè)備驅(qū)動(dòng)程序

（相同類型設(shè)備的設(shè)備驅(qū)動(dòng)程序只需有一種），但大體上都可以分為3部分，如圖

I所示。圖設(shè)備更動(dòng)程序低層部分：它由處理程序組成，當(dāng)發(fā)生中斷時(shí)調(diào)

用，即為設(shè)備的中斷處理程序。高層部分：它由一些函數(shù)組成，在應(yīng)用程序請(qǐng)求

I/O操作時(shí)調(diào)用。一組共享變量：保存協(xié)調(diào)高層部分和低層部分所需要的狀態(tài)信

息。

33、透明網(wǎng)橋的MAC地址表要記錄的信息有（）。I.目的站MAC地址H.源站

MAC地址DI.端口號(hào)IV.幀到達(dá)時(shí)間V.幀轉(zhuǎn)發(fā)標(biāo)記

A僅

、I、口、皿

B僅

、I、口、V

c僅

、口、、

僅miv

D

、口、m、v

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

知識(shí)點(diǎn)解析：網(wǎng)橋轉(zhuǎn)發(fā)數(shù)據(jù)的依據(jù)是MAC地址表，透明網(wǎng)橋的MAC地址表要記

錄3類信息，即源站MAC地址、端口號(hào)和幀到達(dá)時(shí)間。透明網(wǎng)橋剛接入局域網(wǎng)

時(shí)，其MAC地址表是空的。當(dāng)透明網(wǎng)橋接收到一個(gè)幀時(shí)，它將記錄所接收幀的源

MAC地址、幀進(jìn)入該網(wǎng)橋的端口號(hào)以及該幀進(jìn)入網(wǎng)橋的時(shí)間，然后將該幀向所有

具他端口轉(zhuǎn)發(fā)。網(wǎng)橋在轉(zhuǎn)發(fā)過程中逐漸建立起MAC地址表。之所以要記錄幀到達(dá)

網(wǎng)絡(luò)的時(shí)間，是因?yàn)榫钟蚓W(wǎng)的拓?fù)浣?jīng)常會(huì)發(fā)生變化。為了使MAC地址表能反映整

個(gè)網(wǎng)絡(luò)的最新拓?fù)洌枰涗浢總€(gè)幀到達(dá)網(wǎng)橋的時(shí)間，以便在MAC地址表中保留

網(wǎng)絡(luò)拓?fù)涞淖钚聽顟B(tài)信息。網(wǎng)橋中的端口管理軟件周期性地掃描MAC地址表，只

要是在一定時(shí)間（例如幾分鐘）以前登記的都要?jiǎng)h除，從而使得MAC地址表能反

映當(dāng)前網(wǎng)絡(luò)的拓?fù)錉顟B(tài)。

34、下列說法中，錯(cuò)誤的是（）。I.假設(shè)幀序號(hào)有3位，采用連續(xù)ARQ協(xié)議，發(fā)

送窗口的最大值為4n.對(duì)于窗口大小為n的滑動(dòng)窗口，最多可以有n幀已發(fā)送但

沒有確認(rèn)皿.在后退N幀協(xié)議中，如果發(fā)送窗口的大小是16,那么至少需要4位

的序列號(hào)才能保證協(xié)議不出錯(cuò)

A、僅I、n

B、僅HI

C、僅口、m

D^I□、皿

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

知識(shí)點(diǎn)解析：I:連續(xù)ARQ協(xié)議包括后退N幀協(xié)議和選擇重傳協(xié)議。如果幀序號(hào)

為3位，當(dāng)采用后退N幀協(xié)議時(shí)，發(fā)送窗口的最大值為23—1=7；當(dāng)采用選擇重

傳協(xié)議時(shí)，發(fā)送窗口的最大值為23一匕4,故I錯(cuò)誤?？冢涸谶B續(xù)ARQ協(xié)議中，如

果總的窗口大小為n,發(fā)送窗口的大小最大為n-1（當(dāng)采用后退N幀協(xié)議時(shí)可以達(dá)

到）。例如：假設(shè)窗口大小為8（0?7）,如果發(fā)送窗口大小為8,則當(dāng)0?7號(hào)幀都

發(fā)出去時(shí)，接收方已經(jīng)收到了，并且發(fā)出確認(rèn)。但是發(fā)送方卻沒有收到確認(rèn)，導(dǎo)致

。?7號(hào)幀超時(shí)重傳，而此時(shí)接收方就判斷不出這個(gè)是重傳的還是新一輪的幀，導(dǎo)

致錯(cuò)誤，故D錯(cuò)誤。注意：有的考生認(rèn)為窗口就是發(fā)送窗口。其實(shí)窗口和發(fā)送窗

口是不一樣的。假設(shè)幀序號(hào)為n,則窗口大小為2,而發(fā)送窗口只能在［1,2n-l］

內(nèi)取值，否則將會(huì)出錯(cuò)。n：首先需要清楚后退N幀協(xié)議的最大發(fā)送窗口為an-

il其中n為幀號(hào)的位數(shù)），題目中已經(jīng)說明發(fā)送窗口的大小為16,也就是說如果

要使得協(xié)議不出錯(cuò)，必須滿足16與2”—1,所以n至少要等于5,故HI錯(cuò)誤。

35、假設(shè)某網(wǎng)絡(luò)最遠(yuǎn)的兩個(gè)站點(diǎn)長(zhǎng)度為10km,數(shù)據(jù)傳輸率為10Mbit/s的

CSMA/CS以太網(wǎng)，信號(hào)傳播速度為200m4is。那么該網(wǎng)絡(luò)的最小幀長(zhǎng)為（）。

A、20bit

B、200bit

C、lOObit

D、lOOObit

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

知識(shí)點(diǎn)解析：要求最小項(xiàng)長(zhǎng)，首先得求出爭(zhēng)用期。來回往返的路程為20km,而信

號(hào)傳播速度為200m〃s（2x108m/s）,所以爭(zhēng)用期=2x10一40,故最小幀

長(zhǎng);數(shù)據(jù)傳輸率x爭(zhēng)用期二1（）7乂］（）一bit=lOOObit,故選D選項(xiàng)?？偨Y(jié)：最短幀長(zhǎng)與

爭(zhēng)用期的關(guān)系是什么？解析：在數(shù)據(jù)傳輸率不變的條件下，若要使得最小幀長(zhǎng)減

小，爭(zhēng)用期就必須減小。而爭(zhēng)用期要減少不可能加大信號(hào)的傳播速度，所以只能減

小網(wǎng)絡(luò)中最遠(yuǎn)兩個(gè)站點(diǎn)之間的距離。注意：以太網(wǎng)最小傳送的幀長(zhǎng)為64B,如果

某幀小于這個(gè)長(zhǎng)度，則必須填充。

圖6-1

A、S=135.2.1.1,80D=202.0.1.1,5001

B、S=135.2.1.1,80D=192,168.1.1,3342

C、S=202.0.l.l,5001D=135.2.1.1,80

D、S=192.168.1.1,3342D=135.2.1.1,80

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

知識(shí)點(diǎn)解析：在圖6—1中，Web服務(wù)器給地址為192.168.1.1的源主機(jī)返回響應(yīng)結(jié)

果時(shí)，進(jìn)入NAT路由器之前的IP分組的源IP地址為13521.1,源端口號(hào)為80,

目的1P地址為202:0.1.1,目的端口號(hào)為5001,即在圖6—1中標(biāo)號(hào)為③的方格中

的內(nèi)容應(yīng)為“S=135.2.1.1,80；D-202.0.1.1.5001%該IP分組經(jīng)過查詢路由器中

NAT轉(zhuǎn)換表可知，目的IP地址202.0.1.1應(yīng)轉(zhuǎn)換為192.168.1.1,目的端口號(hào)5001

應(yīng)轉(zhuǎn)換成3342,而源IP地址、源端口號(hào)不變?？梢姡趫D6—1中標(biāo)號(hào)為④的方

格中的內(nèi)容應(yīng)該為'5=135.2.1.1,80；D—192.168.1.1,3342”。

37、對(duì)于193.100.60.0網(wǎng)絡(luò)，若子網(wǎng)掩碼設(shè)置成255.255.255.192,則每

個(gè)子網(wǎng)最多可接入（）臺(tái)主機(jī)。

A、256

B、254

C、62

D、30

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

知識(shí)點(diǎn)解析：在一條點(diǎn)對(duì)點(diǎn)的鏈路上，存在兩臺(tái)主機(jī)，即只需要給這個(gè)網(wǎng)絡(luò)分配2

位主機(jī)位Q2—2=2）即可，所以說子網(wǎng)掩碼應(yīng)該為

11111111.11111111.11111111.11111100,即255.255.255.252o

.總

。I

是()