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

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

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

1、下列說(shuō)法中，正確的是（）。I.假設(shè)某有序表的長(zhǎng)度為n,則可以在1?（n+1）

的位置上插入元素H.在單鏈表中，無(wú)論是插入還是刪除操作，都必須找到其前

驅(qū)結(jié)點(diǎn)m.刪除雙鏈表的中間某個(gè)結(jié)點(diǎn)時(shí).，只需修改兩個(gè)指針域W.將兩個(gè)各有

n和m個(gè)元素的有序表（遞增）歸并成一個(gè)有序表，仍保持其遞增有序，則最少的

比較次數(shù)是m+n一lo

A、僅i、n、in

B、i、□、m、w

c、僅n、m

D、僅i、m、w

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

知識(shí)點(diǎn)解析：i：有序表插入的時(shí)候是不能指定位置的，因?yàn)檫@樣可能使得插入后

的表不再是有序表。正確的插入思想是：先通過(guò)元素比較找到插入的位置，再在該

位置上插入，故I錯(cuò)誤?？冢簭膯捂湵聿迦牒蛣h除的語(yǔ)句描述中可以看出，無(wú)論是

插入還是刪除操作，都必須找到其前驅(qū)結(jié)點(diǎn)，故口正確。m：刪除雙鏈表中間某個(gè)

結(jié)點(diǎn)時(shí)，需要修改前后兩個(gè)結(jié)點(diǎn)的各一個(gè)指針域，共計(jì)兩個(gè)指針域，故in正確。

IV：當(dāng)一個(gè)較短的有序表中所有元素均小于另一個(gè)較長(zhǎng)的有序表中所有的元素，所

需比較次數(shù)最少。假如一個(gè)有序表為1、3、4,另一個(gè)有序表為5、6、7、8、12,

這樣只需比較3次即可，故答案應(yīng)該是n和m中較小者，即min（n,m）,故W錯(cuò)

誤。

2、下列關(guān)于棧的說(shuō)法中，正確的是（）。I.若進(jìn)棧順序?yàn)閍、b、c,則通過(guò)出棧

操作可能得到5個(gè)a、b、c的不同排列H.鏈?zhǔn)綏５臈ｍ斨羔樢欢ㄖ赶驐５逆溛?/p>

n.兩個(gè)棧共享一個(gè)向量空間的好處是減少了存取時(shí)間

A、僅I

B、僅I、n

c、僅口

D、僅u、m

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

知識(shí)點(diǎn)解析：I：該選項(xiàng)旨在讓考生知道一個(gè)公式。對(duì)于n個(gè)不同元素進(jìn)棧，出棧

1U

序列的個(gè)數(shù)為n2。可以馬上得出，當(dāng)n=3時(shí)、出棧序列個(gè)數(shù)為

7=6x5x4=5

44x3x2xI故I正確?？冢烘?zhǔn)綏Ｒ话悴捎脝捂湵?，棧頂指針即為鏈頭

指針。進(jìn)棧和出棧均在鏈頭進(jìn)行，每次都要修改棧頂指針，鏈空即棧空

(top==NULL),故口錯(cuò)誤。m:由于棧中數(shù)據(jù)的操作只有入棧和出棧，且時(shí)間復(fù)雜

度均為0(1),因此并沒(méi)有減少存取時(shí)間，故ID錯(cuò)誤。補(bǔ)充知識(shí)點(diǎn)：共享?xiàng)＝馕觯?/p>

兩個(gè)棧共享一個(gè)數(shù)組A［0...MaxSize—1］的空間，從而構(gòu)成共享?xiàng)?。?shù)組A的兩端

是固定的，而棧底也是固定的，為此將下標(biāo)為0的一端作為棧1的棧底，其棧頂指

針為topi,將下標(biāo)為MaxSize—1的一端作為棧2的棧底，其棧頂指針為top2,如

圖7—4所示。

0I…I…MaxSize-1

11???與*?*b.

棧I底<opltop>檄底

圖7-4共享?xiàng)＃?/p>

的四要素如下：①棧空條件：topl=—lo②棧滿(mǎn)條件：topi==top2—Io③元素

x進(jìn)棧：topl++；將元素x插入A［topl］處。④出棧元素：播出A［topl］元素；topl-

-o棧2的四要素如下：①棧空條/：top2==MaxSize。②棧滿(mǎn)條南top2==top

l+lo③元素x進(jìn)棧：top2-；將元素x插入A［top2］處。④出棧元素：麻出

A［lop2］元素：top2++。注：以上都默認(rèn)指針指向當(dāng)前元素的下一個(gè)位置。

3、若將n階上三角矩陣A按照列優(yōu)先順序存放在一維數(shù)組B［0,1,…，

{nx(n+l)/2}—1］中,第一個(gè)非零元素a(l,1)存于B⑼中,則存放到B［k］中的非零

元素a(i,j)(l$i&i,閆gn)的下標(biāo)i、j與k的對(duì)應(yīng)關(guān)系是()。

A、k=ix(i+l)/2+j

B、k=jx(i—l)/2+j—1

C、k=jx(j+l)/2+i

D^k=jx(j-1)/2+i一1

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

知識(shí)點(diǎn)解析：對(duì)于元素a(i,j)而言，前面有j—1歹IJ,第1列到第j—1列的元素個(gè)

數(shù)分別為1?j—1個(gè)，由等差數(shù)列求和公式可算得一共有jx(j—1)/2個(gè)元素，故

k=jx(j—l)/2+i—I(注意B數(shù)組是從0開(kāi)始存元素，因此要減去1)。

4、知一棵二叉樹(shù)的先序、中序、后序的部分序列如下，其中有些位置沒(méi)有給出其

值，則原二叉樹(shù)的中序遍歷序列為()。先序：A_CDEF_H_J中序：C_EDA_GFI_

后序：C_BHGJI_

A、CBEDAHGFIJ

B、CHEDABGFIJ

C、CBEDAJGnil

D、CJEDAHGFIB

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

知識(shí)點(diǎn)解析：對(duì)于一棵二叉樹(shù)(包括子樹(shù))，它的遍歷序列對(duì)應(yīng)的結(jié)構(gòu)應(yīng)該是：先

序遍歷：|根|左子樹(shù)|右子樹(shù)|,中序遍歷：|左子樹(shù)|根|右子樹(shù)后序遍歷：|左子樹(shù)|

右子樹(shù)根I，由題目中給出的先序序列的第一個(gè)結(jié)點(diǎn)我們找到樹(shù)的根A,然后在中

序序列中找到A,并以A為分界將中序序列劃分為|C_ED|A|_GFI」，所以C_ED為

左子樹(shù)，GFI為右子樹(shù)，再對(duì)應(yīng)到后序遍歷序列上，這里左子樹(shù)結(jié)點(diǎn)的個(gè)數(shù)等于中

序遍歷序列中左子樹(shù)結(jié)點(diǎn)的個(gè)數(shù)，因此C_B為左子樹(shù)，HGJI_為右子樹(shù)，這樣把

中序序列和后續(xù)序列中的左右子樹(shù)一對(duì)比，則C8ED為左子樹(shù)，F(xiàn)GHIJ為右子

樹(shù)。答案選A?？偨Y(jié)：根據(jù)樹(shù)的遍歷結(jié)果來(lái)還原二又樹(shù)，或者根底其中的兩個(gè)遍

歷序列來(lái)求第三個(gè)遍歷序列這是歷年考試的熱點(diǎn)，考生需要記住的是無(wú)論怎樣的序

列，要想構(gòu)建二叉樹(shù)必須有中序序列。這是很顯然的，這里說(shuō)明一下原因：我們知

道二叉樹(shù)的定義是遞歸的，那么我們?cè)跇?gòu)建二叉樹(shù)的時(shí)候勢(shì)必也會(huì)用到遞歸這種方

法，而這種形式的遞歸我們把它稱(chēng)之為分治（從中間分開(kāi)來(lái)治理）法，而在三種遍

歷序列中只有中序遍歷的結(jié)構(gòu)才體現(xiàn)了這種思想。

5、設(shè)某赫夫曼樹(shù)的高度為5,若已對(duì)兩個(gè)字符編碼為1和01,則最多還可以對(duì)（）

個(gè)字符編碼。

A、3

B、4

C、5

D、6

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

知識(shí)點(diǎn)解析：首先，赫夫曼編碼遵循的原則為：一個(gè)編碼不能是任何其他編碼的前

綴。比如1和10就不行，因?yàn)?是10的前綴。既然1和01已經(jīng)使用了，所以1

和01開(kāi)頭的碼字不能再使用。又由于赫夫曼樹(shù)的高度為5,故赫夫蛙編碼的長(zhǎng)度

不能超過(guò)4,只剩下0000、000K0010、0011等4種編碼（這種編碼方式可得到

最多），故選B選項(xiàng)。注意：木題選的是最多還可以對(duì)多少個(gè)字符編碼，所以不

能選取001、000等編伍。例如選取001,就意味著0010和0011不能使用，這樣

可編碼的字符就少了1個(gè)?？偨Y(jié)：（1）有n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為

2n—K（2）高度為h的赫夫曼樹(shù)中，至少有2h—1個(gè)結(jié)點(diǎn)，至多有2卜一1個(gè)結(jié)點(diǎn)。

（3）赫夫蛀樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)。（4）赫夫曼樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是

兄弟結(jié)點(diǎn)。（5）樹(shù)中任一非葉子結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。補(bǔ)

充例題：一棵赫夫曼樹(shù)共有215個(gè)結(jié)點(diǎn)，對(duì)其進(jìn)行赫夫曼編碼，共能得到多少個(gè)碼

字？解析：求多少個(gè)碼字就是求有多少個(gè)葉結(jié)點(diǎn)，從（1）可以得到，葉結(jié)點(diǎn)的個(gè)數(shù)

為108個(gè)，故可以得到108個(gè)碼字。

6、下列說(shuō)法中，正確的是（）。I.在含有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩陣

中，零元素的個(gè)數(shù)為J—2e口.若鄰接表中有奇數(shù)個(gè)邊表結(jié)點(diǎn)，則該圖一定是有

向圖HI.對(duì)于采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的中序遍

歷W.使用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先遍歷算法，則每個(gè)頂點(diǎn)進(jìn)隊(duì)列的次數(shù)可能大于1

A、僅I、m

B、僅口、皿、IV

C、僅I、U、W

D、僅i、n

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

知識(shí)點(diǎn)解析：I：總結(jié)如下：①對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩

陣表示，則該矩陣大小是if。②在含有n個(gè)頂點(diǎn)。條邊的無(wú)向圖的鄰接矩陣中，

非零元素的個(gè)數(shù)為2e。③在含有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩陣中，零元素

的個(gè)數(shù)為仔―2e,④在含有n個(gè)頂點(diǎn)e條邊的有向圖的鄰接矩陣中，非零元素的

個(gè)數(shù)為e。⑤在含有n個(gè)頂點(diǎn)e條邊的有向圖的鄰接矩陣中，零元素的個(gè)數(shù)為

2

n-eo根據(jù)③，故I正確。H:無(wú)向圖采用鄰接表表示時(shí)，每條邊存儲(chǔ)兩次，所

以其邊表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，故邊表結(jié)點(diǎn)為奇數(shù)只能是有向圖，故口正確。m：深度

優(yōu)先遍歷算法是先訪(fǎng)問(wèn)一個(gè)頂點(diǎn)V,然后是離開(kāi)頂點(diǎn)越遠(yuǎn)越優(yōu)先訪(fǎng)問(wèn)，即相當(dāng)于二

叉樹(shù)的先序遍歷，故皿錯(cuò)誤。iv：采用廣度優(yōu)先遍歷算法遍歷一個(gè)圖時(shí)，每個(gè)頂

點(diǎn)僅遍歷一次，所以最多只能進(jìn)隊(duì)1次，故w錯(cuò)誤。

7、下列關(guān)于生成樹(shù)的說(shuō)法中，正確的是()。

A、最小生成樹(shù)是指權(quán)值之和為最小的生成樹(shù)，且唯一

B、某圖的廣度優(yōu)先生成樹(shù)的高度一定大于等于深度優(yōu)先生成樹(shù)的高度

C、Prime算法和Kruskual算法構(gòu)造的最小生成樹(shù)一定一樣

D、Prime算法適用于求邊稠密的圖的最小生成樹(shù)

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

知識(shí)"解云：A:最小生成樹(shù)是指權(quán)值之和為最小的生成樹(shù)，但是不唯一，故A選

項(xiàng)錯(cuò)誤。B:由廣度優(yōu)先遍歷和深度優(yōu)先遍歷算法可知，深度優(yōu)先算法構(gòu)造的生成

樹(shù)的樹(shù)高大于等于廣度優(yōu)先算法構(gòu)造的生成樹(shù)的樹(shù)高，故B選項(xiàng)錯(cuò)誤。C:當(dāng)最小

生成樹(shù)不唯一時(shí)，這兩種算法構(gòu)造的最小生成樹(shù)可能相同，也可能不同，故C選

項(xiàng)錯(cuò)誤。D：Prime算法的時(shí)間復(fù)雜度為0(1?),適合稠密圖；Kruskual算法的時(shí)間

復(fù)雜度為O(ek)g2e),適合稀疏圖，故D選項(xiàng)正確。

8、下列關(guān)于m階B+樹(shù)的說(shuō)法中，正確的是()。I.具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)至少

含有n+1棵子樹(shù)D.所有葉子結(jié)點(diǎn)包含全部關(guān)鍵字HI.B+樹(shù)支持隨機(jī)索引

IV.B+樹(shù)可用于文件的索引結(jié)構(gòu)

A、僅m、W

B、僅口、IV

C、僅I、m、IV

D、僅I、n、w

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

知識(shí)點(diǎn)解析：一棵m階B+樹(shù)滿(mǎn)足下列條件：①每個(gè)分支結(jié)點(diǎn)至多有m棵子樹(shù)。

②根結(jié)點(diǎn)或者沒(méi)有子樹(shù)，或者至少有兩棵子樹(shù)。③除根結(jié)點(diǎn)外，其他每個(gè)分支結(jié)

點(diǎn)至少有［m/2］棵子樹(shù)。④具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有n棵子樹(shù)。⑤所有葉子結(jié)

點(diǎn)包含全部關(guān)鍵字及指向相應(yīng)記錄的指針，而且葉子結(jié)點(diǎn)按關(guān)鍵字的大小順序鏈

接。⑥所有分支結(jié)點(diǎn)中僅包含它的各個(gè)子結(jié)點(diǎn)中最大關(guān)鍵字及指向子結(jié)點(diǎn)的指

針。⑦B+樹(shù)中，所有非終端結(jié)點(diǎn)可以看成是索引部分，故可用于文件的索引結(jié)

構(gòu)。注意：由于B+樹(shù)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，所以不支持隨機(jī)檢索。綜上所述，可知

n、W正確，I、in錯(cuò)誤，故選B選項(xiàng)。補(bǔ)充知識(shí)點(diǎn)：很多考生被B+樹(shù)和B—樹(shù)

的基本概念弄混，下面做一個(gè)小結(jié)。解析：m階B+樹(shù)和m階B—樹(shù)的主要差異如

下：①在B+樹(shù)中，具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有n裸子樹(shù)；而在B—樹(shù)中，具有n

個(gè)關(guān)鍵字的結(jié)點(diǎn)至少含有（n+1）棵子樹(shù)。②在B+樹(shù)中，每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)外）

中的關(guān)鍵字個(gè)數(shù)n的取值范圍是［m/2Engm,根結(jié)點(diǎn)n的取值范圍是2slsm；而在

B—樹(shù)中，除根結(jié)點(diǎn)外，其他所有非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n的取值范圍是［m⑵-

l<n<m—1,根結(jié)點(diǎn)n的取值范圍是ISnSm—1。記憶方式：“B—”中有個(gè)“一”號(hào)，

自然關(guān)鍵字個(gè)數(shù)相對(duì)于B+減掉了1。③在B+樹(shù)中，所有葉子結(jié)點(diǎn)包含了全部關(guān)

鍵字，即其他非葉子結(jié)點(diǎn)中的關(guān)鍵字包含在葉子結(jié)點(diǎn)中；而在B—樹(shù)中，關(guān)鍵字是

不重復(fù)的。④在B+樹(shù)中，所有非葉子結(jié)點(diǎn)僅僅是起到了索引的作用，即結(jié)點(diǎn)中的

每個(gè)索引項(xiàng)只含有對(duì)應(yīng)子樹(shù)的最大關(guān)鍵字和指向子樹(shù)的指針，不含有該關(guān)鍵字對(duì)應(yīng)

記錄的存儲(chǔ)地址。而在B—樹(shù)中，每個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)記錄的存儲(chǔ)地址。⑤在B+

樹(shù)上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)，所有葉

子結(jié)點(diǎn)鏈接成一個(gè)鏈表；而在B—樹(shù)中，葉子結(jié)點(diǎn)并不會(huì)有指針相連。

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

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

A、4

B、5

C、6

D、7

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

知識(shí)點(diǎn)解析：由題可以建立出如圖7-5所示的一棵二叉排序樹(shù)。

查找元素30—次經(jīng)過(guò)比較的元素為50,43,20,35,

30,共有5次元素間的比較，因此本題選B選項(xiàng)。

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

A、1,4,7,10,15,24

B、2,5,3,20,15,18

C、4,5,7,13,10,9

D、4,7,8,5,19,16

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

知識(shí)點(diǎn)解析：首先需要知道快速排序的一個(gè)特性，即元素越無(wú)序，快速排序越快；

元素越有序，快速排序越慢。但是一般情況下，有序的元素序列比較少，大部分情

況都是雜亂無(wú)章的一堆數(shù)，所以說(shuō)快速排序是所有排序中性能最好的排序方法。有

些同學(xué)可能會(huì)有疑問(wèn)，快速排序最差的時(shí)間復(fù)雜度是O(r>2),而有不少排序算法最

壞的時(shí)間復(fù)雜度是O(nlog2n),比如堆排序。為什么快速排序的性能是最好的阻？

因?yàn)榭焖倥判虺霈F(xiàn)最壞性能的情況實(shí)在是太少發(fā)生了，所以要看綜合的性能，不能

只看最壞的(記住就好，在此不舉例子了)。本題A選項(xiàng)是一個(gè)有序序列，所以

速度肯定最慢。總結(jié)：如果元素基本有序，使用直接插入排序效果最好：如果元

素完全沒(méi)序，使用快速排序效果最好。

II、在外部排序算法中，最佳歸并樹(shù)主要的作用是()。

A、產(chǎn)生初始?xì)w并段

B、完成歸并排序

C、對(duì)歸并排序進(jìn)行優(yōu)化

D、增大歸并路樹(shù)

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

知識(shí)點(diǎn)解析：A:產(chǎn)生初始?xì)w并段的工作應(yīng)該由置換一選擇排序完成，故A選項(xiàng)錯(cuò)

誤。設(shè)輸入的關(guān)鍵字滿(mǎn)足k|>k2>—>km，緩沖區(qū)大小為m,用置換.選擇排序

方法可產(chǎn)生［n/n］個(gè)初始?xì)w并段。氏因?yàn)樽罴褮w并樹(shù)是針對(duì)排序之后的初始?xì)w并段

操作，所以歸并排序不可能由最佳歸并樹(shù)完成，故B選項(xiàng)錯(cuò)誤。C：最佳歸并樹(shù)

仿造赫夫曼樹(shù)的構(gòu)造過(guò)程，以初始?xì)w并段的長(zhǎng)度為權(quán)值，構(gòu)造具有最小帶權(quán)路徑長(zhǎng)

度的赫夫曼樹(shù)，可以有效地減少歸并過(guò)程中的讀寫(xiě)記錄數(shù)，以加快外部排序的速

度，故C選項(xiàng)正確。D:增大歸并路數(shù)應(yīng)該是由敗老樹(shù)來(lái)完成的，故D選項(xiàng)錯(cuò)誤。

12、下列說(shuō)法中，錯(cuò)誤的是()。I.時(shí)鐘頻率和CPI成反比關(guān)系U.數(shù)據(jù)字長(zhǎng)等

于MDR的位數(shù)HI.A主機(jī)的CPU主頻高于B主機(jī)的CPU主頻，則前者運(yùn)算能力

將會(huì)高于后者

A僅

、I、n

B僅

、口、皿

c僅

、I、m

DI

、、n、五

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

知識(shí)點(diǎn)解析：I：時(shí)鐘頻率和CPI并無(wú)關(guān)系。時(shí)鐘頻率的提高僅僅是將時(shí)鐘周期

縮短，并沒(méi)有改變執(zhí)行一條指令所需要的時(shí)鐘周期數(shù)，故I錯(cuò)誤。n：一般來(lái)講，

MDR的位數(shù)和存儲(chǔ)字長(zhǎng)相等，而數(shù)據(jù)字長(zhǎng)是一次存取數(shù)據(jù)的長(zhǎng)度，可以和MDR

不相等，故n錯(cuò)誤。川：CPU的主頻是表示在CPU內(nèi)數(shù)字脈沖信號(hào)震蕩的次數(shù)，

是衡量CPU運(yùn)算速度的重要參數(shù)，但不是唯一的參數(shù)。故不能直接根據(jù)主頻來(lái)比

較運(yùn)算能力，故HI錯(cuò)誤。

13、假定米用IEFF754單精度浮點(diǎn)數(shù)格式表示一個(gè)數(shù)為45100000H.則該數(shù)的值

是()。

A、(+1.125)x21°

B、(+1.125)x2"

C、(+0.125)x2,1

D、（+0.I25）x210

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

知識(shí)點(diǎn)解析：45100000H的二進(jìn)制數(shù)為01000101000100000000000000000000,

第1位為符號(hào)位，表示正數(shù)，隨后8位10001010為用移碼表示的階碼，減去127

得到十進(jìn)制數(shù)11，而IEEE754中單精度數(shù)在階碼不為0時(shí)隱含1,所以尾數(shù)為

（1.0010）2=1.125o

14、—個(gè)8位的二進(jìn)制整數(shù)，若采用補(bǔ)碼表示，且由3個(gè)力”和5個(gè)“0”組成，則最

小值為（）。

A、—127

B、—32

C、—125

D、一3

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

知識(shí)點(diǎn)解析：8位補(bǔ)碼最小時(shí)必為負(fù)數(shù)，所以第一位（符號(hào)位）必須為1。而負(fù)數(shù)

的數(shù)值位絕對(duì)值越大，則此負(fù)數(shù)越小。又負(fù)數(shù)的補(bǔ)碼表示的高位0相當(dāng)于原碼表示

的1,故當(dāng)剩下的2個(gè)力”在最低位，5個(gè)“0”在數(shù)值位的最高位時(shí)此負(fù)數(shù)最小。該

負(fù)數(shù)的補(bǔ)碼為10000011,則原碼為11111101.轉(zhuǎn)換成十進(jìn)制為一125。

15、一臺(tái)8位微機(jī)的地址總線(xiàn)為16條，其RAM存儲(chǔ)器容量為32KB,首地址為

4000H,且地址是連續(xù)的，可用的最高地址為（）。

A、BFFFH

B、CFFFH

C、DFFFH

D、EFFFH

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

知識(shí)點(diǎn)解析：32KB存儲(chǔ)空間共占用15條地址線(xiàn)，若32KB的存儲(chǔ)地址起始單元為

OOOOII,其范圍應(yīng)為OOOOi7FFni,但現(xiàn)在的首地址為400011,即首地址后移

了，因此最高地址也應(yīng)該相應(yīng)后移。故最高地力E為4000H+7FFFH=BFFFH。歸納

總結(jié)：32KB的存儲(chǔ)空間是連續(xù)的，由于首地址發(fā)生變化，末地址也會(huì)跟著發(fā)生變

化。

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

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

A、1234H

B、2468H

C、048DH

D、12345H

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

知識(shí)點(diǎn)解析：因?yàn)閴K的大小為16B,所以塊內(nèi)地址字段為4位；又因?yàn)镃ache容量

為128KB,8路組相聯(lián),所以可以分為1024組（128KB/（8xl6B）=l024）,對(duì)應(yīng)的組

號(hào)字段10位；剩下為標(biāo)記字段。1234567H=0001001000110100010101100111,標(biāo)

記字段為高14位,00010010001101=048DH,故選C選項(xiàng)。歸納總結(jié):組相聯(lián)映

像對(duì)應(yīng)的主存地址應(yīng)包帝3個(gè)部分，即標(biāo)記（Tag）、組號(hào)（Index）和塊內(nèi)地址

（Offset）o解題技巧：首先將主存地址由十六進(jìn)制變成二進(jìn)制，其中塊內(nèi)地址字段

為最后4位，組號(hào)字段為中間10位，剩下的就是標(biāo)記字段，將標(biāo)記字段二進(jìn)制轉(zhuǎn)

換為十六進(jìn)制，即可得出結(jié)果。

17、在單發(fā)射、按序流動(dòng)的普通流水線(xiàn)中，可能出現(xiàn)下列（）數(shù)據(jù)相關(guān)問(wèn)題。

I.寫(xiě)后讀相關(guān)RAW口.讀后寫(xiě)相關(guān)WAR皿.寫(xiě)后寫(xiě)相關(guān)WAW

A僅

、I

B僅

、

c僅

、

D僅

、、H

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

知識(shí)點(diǎn)解析：指令取操作數(shù)的動(dòng)作一定在寫(xiě)回結(jié)果之前，故在按序流動(dòng)的單發(fā)射

（普通標(biāo)量）普通流水線(xiàn)中，先進(jìn)入流水線(xiàn)的指令的取操作數(shù)和寫(xiě)回結(jié)果的動(dòng)作一

定位于后續(xù)指令寫(xiě)回結(jié)果的動(dòng)作之前，故不可能出現(xiàn)WAR和WAW。唯一可能出

現(xiàn)的數(shù)據(jù)相關(guān)問(wèn)題是后續(xù)指令在前一指令寫(xiě)回結(jié)果之前讀相關(guān)的操作數(shù)，即

RAW。注：而在非按序流動(dòng)的流水線(xiàn)中，允許后進(jìn)入流水線(xiàn)的指令超過(guò)先進(jìn)入流

水線(xiàn)的指令先流出流水線(xiàn)，故3種數(shù)據(jù)相關(guān)都可能出現(xiàn)。提醒：直接按照中文翻

譯的比如“讀后寫(xiě)”容易理解為“先讀后寫(xiě)”，事實(shí)上根據(jù)英文的意思，應(yīng)該是“先寫(xiě)

后讀“，容易繞暈，注意理順?biāo)悸?，要反著讀。

18、在按字節(jié)編址的計(jì)算機(jī)中，一條指令長(zhǎng)16位，當(dāng)前分支轉(zhuǎn)移指令（采用相對(duì)

尋址）地址為3000,指令地址的偏移量為一5,當(dāng)執(zhí)行完此轉(zhuǎn)移指令后，PC的值

為（）。

A、2996

B、2997

C、3001

D、3002

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

知識(shí)點(diǎn)解析：首先給出解答步驟，當(dāng)前指令地址為3000,取完這條指令后，PC的

值增加一個(gè)指令字長(zhǎng)度，即3002,加上偏移量一5,所以執(zhí)行完這條指令后，目標(biāo)

地址為2997,然后將這個(gè)值覆蓋到PC當(dāng)中。總結(jié)：這里面存在兩個(gè)問(wèn)題：1）PC

值到底如何計(jì)算？2）得出的目標(biāo)地址到底放哪里？這是一個(gè)當(dāng)年困擾筆者和很多

考生的一個(gè)很典型的問(wèn)題，PC到底是多少呢？“然后PC=PC+1”，老師經(jīng)常這么

說(shuō)。可是這里的、“到底怎么理解？一個(gè)字節(jié)？一個(gè)指令字？你先別急著回答，筆

者翻閱了很多書(shū)籍，也參考了各大院校的自主命題以及408統(tǒng)考真題，發(fā)現(xiàn)理解各

不一樣，拿北京理工大學(xué)2005年的一個(gè)選擇題為例（在按字節(jié)編址的計(jì)算機(jī)中，

一條指令長(zhǎng)16位……，然后取完指令后，PC的值是多少？），這里參考答案把加

1理解成了1個(gè)字節(jié)。在2009年408真題當(dāng)中同樣類(lèi)型的題目（指令字長(zhǎng)16位，

按字節(jié)編址），題于給出的卻是每取出一個(gè)字節(jié)，PC+1,那么取完這條指令時(shí)，

PC的值便自增了2,也就是說(shuō)在我們熟悉的那句話(huà)“當(dāng)取出一條指令后，PC的值

就+1”中，這里的1便是1個(gè)指令字的長(zhǎng)度。在考試當(dāng)中我們?cè)趺蠢斫?？?dāng)然是按

真題的講解，一切以得分為目標(biāo)，也就是說(shuō)以后遇到這樣的題，就把這里的1理解

為一個(gè)指令字。得到的目標(biāo)地址后不要以為就拿這個(gè)地址去尋址去了，記住，所

有的取指令的地址都是從PC傳到MAR中然后去尋址的，也就是說(shuō)得到目標(biāo)地址

后還要把這個(gè)地址覆蓋到PC當(dāng)中。終于講解完畢了，對(duì)于考試來(lái)說(shuō)也就夠了，可

是你真的覺(jué)得這就算完了嗎？遠(yuǎn)不是這樣，以上的理解都是片面的。（1）PC自增1

的情況指出現(xiàn)在無(wú)流水（non—pipeline）的情況下，這個(gè)時(shí)候取指，譯碼，執(zhí)指都是

順序執(zhí)行的。而在有流水的情況下就比較復(fù)雜了，這里用arm7的三級(jí)流水線(xiàn)為

例。流水線(xiàn)使用三個(gè)階段，因此指令分為三個(gè)階段執(zhí)行：1）取指（從存儲(chǔ)器裝載

一條指令）；2）譯碼（識(shí)別將要被執(zhí)行的指令）；3）執(zhí)行（處理指令并將結(jié)果寫(xiě)

回寄存器）。而R15（PC）總是指向“正在取指”的指令，而不是指向“正在執(zhí)行”的

指令或正在“譯碼”的指令。一般來(lái)說(shuō)，人們習(xí)慣性約定將“正在執(zhí)行的指令作為參

考點(diǎn)”，稱(chēng)之為當(dāng)前第一條指令，因此PC總是指向第三條指令。當(dāng)ARM狀態(tài)時(shí)，

每條指令為4字節(jié)長(zhǎng)，所以PC始終指向該指令地址加8字節(jié)的地址，即：PC值=

當(dāng)前程序執(zhí)行位置+8。（2）程序計(jì)數(shù)器值的修改分兩種情況：一是順序執(zhí)行指令的

情況，二是分支轉(zhuǎn)移指令的執(zhí)行情況。當(dāng)順序執(zhí)行指令時(shí)，程序計(jì)數(shù)器值的修改較

為簡(jiǎn)單。若當(dāng)前取得的有令是單字節(jié)指令，即將程序計(jì)數(shù)器的值加1（PC+1TPC）；

若當(dāng)前取得的指令是雙字節(jié)指令，即將程序計(jì)數(shù)器的值加12（相當(dāng)于加了一個(gè)指令

字長(zhǎng)度）……；在執(zhí)行分支轉(zhuǎn)移指令時(shí)，由分支轉(zhuǎn)移指令的尋址方式確定下一條指

令在主存中的地址。若分支轉(zhuǎn)移指令的尋址方式是相對(duì)尋址，那么程序計(jì)數(shù)器的值

修改為當(dāng)前地址加上相對(duì)偏移量；若分支轉(zhuǎn)移指令的尋址方式是絕對(duì)尋址，即將轉(zhuǎn)

移指令中絕對(duì)轉(zhuǎn)移地址送給程序計(jì)數(shù)器；當(dāng)是間接尋址方式的分支轉(zhuǎn)移指令時(shí)，程

序計(jì)數(shù)器的值從指令指定的寄存器或主存存儲(chǔ)單元中提取。

19、以下給出的事件中，無(wú)須異常處理程序進(jìn)行中斷處理的是（）。

缺頁(yè)故障

B、訪(fǎng)問(wèn)Cache缺失

C、地址越界

D、除數(shù)為0

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

知識(shí)點(diǎn)解析：缺頁(yè)會(huì)導(dǎo)致缺頁(yè)中斷，缺頁(yè)中斷就是要訪(fǎng)問(wèn)的頁(yè)不在主存，現(xiàn)行程序

無(wú)法往下走，需要操作系統(tǒng)采用缺頁(yè)處理程序?qū)⑵湔{(diào)入主存后再進(jìn)行訪(fǎng)問(wèn)；地址越

界就是在采取地址訪(fǎng)問(wèn)時(shí)，由于不注意，你訪(fǎng)問(wèn)的地址超過(guò)了所允許訪(fǎng)問(wèn)的地址空

間，這種操作肯定會(huì)導(dǎo)致結(jié)果錯(cuò)誤，所以是非法操作，產(chǎn)生異常；除數(shù)為0這是不

合法的，因此要終止現(xiàn)行程序，產(chǎn)生異常；而訪(fǎng)問(wèn)Cache缺失僅僅是說(shuō)要訪(fǎng)問(wèn)的內(nèi)

容不在Cache而已，但程序至少還可以繼續(xù)進(jìn)行下去（比如程序可以到主存中去找

需要的內(nèi)容）。所以答案為B?？偨Y(jié)：需不需要異?；蛑袛嗵幚沓绦蜻M(jìn)行處理你

就看現(xiàn)行程序當(dāng)前能不能繼續(xù)往下走，若能，則不需要，反之，則需要。

20、假定一臺(tái)計(jì)算機(jī)的顯示存儲(chǔ)器用DRAM芯片實(shí)現(xiàn)，若要求顯示分辨率為

1600x12（）0,顏色深度為24位，幀頻為85Hz,顯存總帶寬的50%用來(lái)刷新屏幕，

則需要的顯存總帶寬至少約為（）。

A、245MbiUs

B、979Mbit/s

C、1958Mbit/s

D、7834Mbit/s

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

知識(shí)點(diǎn)解析：首先一幀畫(huà)面的大小為1600xl200x24bit,又因?yàn)閹l為85Hz,即每

秒要刷新畫(huà)面85次，因此每秒需要更新的容量為46080000bitx85=391680000Gbit,

占顯存總帶寬的50%,顯存的帶寬至少約為3916.8Mbit/sx2=7834MbiMS。

21、總線(xiàn)寬度只與下列（）選項(xiàng)有關(guān)。I.控制線(xiàn)根數(shù)U.地址線(xiàn)根數(shù)m.數(shù)據(jù)線(xiàn)

根數(shù)

僅I

A、

僅nm

B、、

僅n

C、Inm

D、>、

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

知識(shí)點(diǎn)解析：總線(xiàn)寬度又稱(chēng)為總線(xiàn)位寬，它是總線(xiàn)上能夠同時(shí)傳輸?shù)臄?shù)據(jù)位數(shù)，通

常是指數(shù)據(jù)總線(xiàn)的根數(shù)。

22、在主機(jī)和外設(shè)的信息傳送中，（）沒(méi)有使用程序控制方式。

A、程序查詢(xún)方式

B、程序中斷方式

C、DMA方式

D、通道方式

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

知識(shí)點(diǎn)解析：程序查詢(xún)方式和程序中斷方式顯然是需要程序的干預(yù)，而通道方式也

是要編制通道程序來(lái)控制，只有DMA方式是靠硬件電路實(shí)現(xiàn)的。

23、下列關(guān)于操作系統(tǒng)結(jié)構(gòu)說(shuō)法中，正確的是（）。I.當(dāng)前廣泛使用的Windows

XP操作系統(tǒng)，采用的是分層式OS結(jié)構(gòu)H.模塊化的OS結(jié)構(gòu)設(shè)計(jì)的基本原則

是：每一層都僅使用其底層所提供的功能和服務(wù)，這樣使系統(tǒng)的調(diào)試和驗(yàn)證都變得

容易m.由于微內(nèi)核結(jié)構(gòu)能有效支持多處理機(jī)運(yùn)行，故非常合適于分布式系統(tǒng)環(huán)

境W.采用微內(nèi)核結(jié)構(gòu)設(shè)計(jì)和實(shí)現(xiàn)操作系統(tǒng)具有諸多好處，如添加系統(tǒng)服務(wù)時(shí)，

不必修改內(nèi)核、使系統(tǒng)更高效等

A、僅I、n

B、僅I、HI

c、僅in

D、僅田、IV

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

知識(shí)點(diǎn)解析：I錯(cuò)誤，當(dāng)前比較流行的、能支持多處理機(jī)運(yùn)行的OS,幾乎全部都

采用微內(nèi)核結(jié)構(gòu)，包括WindowsXP?？阱e(cuò)誤，模塊化OS結(jié)構(gòu)原則是：分解和模

塊化?？谥忻枋龅氖欠謱邮浇Y(jié)構(gòu)設(shè)計(jì)的基本原則。皿正確。W錯(cuò)誤，微內(nèi)核結(jié)構(gòu)

將操作系統(tǒng)的很多服務(wù)移動(dòng)到內(nèi)核以外(如文件系統(tǒng))。且服務(wù)之間使用進(jìn)程間通

信機(jī)制進(jìn)行信息交換，這種通過(guò)進(jìn)程間通信機(jī)制進(jìn)行信息交換影響了系統(tǒng)的效率，

所以微內(nèi)核結(jié)構(gòu)設(shè)計(jì)并不會(huì)使系統(tǒng)更高效。由于內(nèi)核的內(nèi)服務(wù)變少了，且一般來(lái)說(shuō)

內(nèi)核的服務(wù)越少肯定越穩(wěn)定。

24、在有一個(gè)CPU和兩臺(tái)外設(shè)D1和D2,且能夠?qū)崿F(xiàn)搶占式優(yōu)先級(jí)調(diào)度算法的多

道程序環(huán)境中，同時(shí)進(jìn)入優(yōu)先級(jí)由高到低的Pl,P2,P3的3個(gè)作業(yè)，每個(gè)作業(yè)

的處理程序和使用資源的時(shí)間如下：Pl:D2(30ms),CPU(10ms),DI(30ms),

CPU(10ms)P2:DI(20ms),CPU(20ms),D2(40ms)P3:CPU(30ms),DI(20ms)假

設(shè)對(duì)于其他輔助操作時(shí)間忽略不計(jì)，CPU的利用率是()。

A、47.8%

B、57.8%

C、67.8%

D、77.8%

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

知識(shí)點(diǎn)解析：搶占式優(yōu)先級(jí)調(diào)度算法，3個(gè)作業(yè)執(zhí)行的順序如圖7—6所示。(還

可以有一種畫(huà)法，即按照進(jìn)程來(lái)考慮，縱坐標(biāo)為P］、P2、P3。)

1

CPUP3P2PlP2P3PI

D1P2PlP3P3

D2PlP2

圖7.63個(gè)作業(yè)執(zhí)行的順序

每小格表示10ms,3個(gè)作業(yè)從進(jìn)入系統(tǒng)到全部運(yùn)行結(jié)束，時(shí)間為90ms。CPU與外

設(shè)都是獨(dú)占設(shè)備，運(yùn)行時(shí)間分別為各作業(yè)的使用時(shí)間之和：CPU運(yùn)行時(shí)間為

(10ms+10ms)+20ms+30ms=70mso故利用率為70/90=77.8%提示：對(duì)于本題中作

業(yè)執(zhí)行的順序可以這樣得到，由于采用的是可搶占的基于優(yōu)先級(jí)的調(diào)度算法，也就

是優(yōu)先級(jí)高的作業(yè)優(yōu)先調(diào)度，并且可以搶占任何資源使用，故我們?cè)诋?huà)設(shè)備利用情

況表時(shí)，可以讓優(yōu)先級(jí)高的作業(yè)一次性完成，再考慮低一級(jí)的作、也，最后再考慮級(jí)

別最低的作業(yè)。

25、設(shè)有如下兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2。信號(hào)量S1和S2的初值均為0,試

問(wèn)Pl、P2并發(fā)執(zhí)行結(jié)束后，z的值可能是()。

進(jìn)程Pl:進(jìn)程P2：

y=3：x?2；

z=2：P(S1);

V(Sl)tx?x+2；

z?y+l：V(S2):

P(S2)：z=x+z：

y=z+y；

A、4、8、11

B、4、6

C、6、8

D、4、8

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

知識(shí)點(diǎn)解析：這類(lèi)題目其實(shí)不難，但這種題卻很容易答錯(cuò)，原因就是很容易漏掉某

種情況。首先，將上述進(jìn)程分解成以下6個(gè)程序段：

PSI：y=3：PS2：z=y+l：PS3：y=z+y；

z=2；

PS4：x=2；PS5：x=x+2：PS6：z=x+z；

假設(shè)沒(méi)有PV操作的情況下。進(jìn)程并發(fā)執(zhí)行關(guān)系用前驅(qū)圖表示如圖7—7所示。加

入了PV操作后用前驅(qū)圖表示如圖7—8所示。由于x的值只有PS4、PS5決定，

且兩者順序關(guān)系確定，則易得x的值始終為4。乂P2和P1共享的變量只有z,則

PS6與PSI、PS2、PS3的關(guān)系決定了最終的y和z的值。又根據(jù)進(jìn)程前驅(qū)圖得，

PS6在PS1之后。所以可能的情況有（PS4、PS5嚴(yán)處的順序有多種情況，但都不

對(duì)最后結(jié)果產(chǎn)生影響，為了方便，我們統(tǒng)一把PS4、PS5放在PS1后面執(zhí)行）：

PSKPS4、PS5、PS6、PS2、PS3；PSUPS4、PS5、PS?.PS6>PS3：PS1.

PS4、PS5、PS2、PS3、PS6；這3種情況，計(jì)算過(guò)程如表7—2所示。

?7-2計(jì)輯過(guò)程

XyzXyzXyz

PSI32PSI32PSI32

PS42PS42PS42

PS54PS54PS54

PS?6PS24PS24

PS24PS68PS37

PS37PS311PS68

4744II8478

綜上所述，z的值可能是4、8o

26、系統(tǒng)的資源分配圖在下列情況中，無(wú)法判斷是否處于死鎖的情況是（）。

I.出現(xiàn)了環(huán)路U.沒(méi)有環(huán)路田.每種資源只有一個(gè)，并出現(xiàn)環(huán)路W.每個(gè)進(jìn)程

結(jié)點(diǎn)至少有一條請(qǐng)求邊

A、I、口、m、w

B、僅I、皿、W

C、僅I、w

D、都能判斷

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

知識(shí)點(diǎn)解析：首先要注意，本題的問(wèn)法比較拗口，是無(wú)法判斷的情況，不可理解錯(cuò)

誤。本題的難點(diǎn)主要在于區(qū)分資源分配圖中的環(huán)路和系統(tǒng)狀態(tài)的環(huán)路有什么關(guān)

系。資源分配圖中的環(huán)路通過(guò)分配資源，是可以消除的，即消邊。而系統(tǒng)狀態(tài)圖中

的環(huán)路其實(shí)就是死鎖。兩者的關(guān)系其實(shí)可以理解為資源分配圖通過(guò)簡(jiǎn)化（消邊）后

就是系統(tǒng)狀態(tài)圖。如果資源分配圖中不存在環(huán)路，則系統(tǒng)狀態(tài)圖無(wú)環(huán)路，則無(wú)死

鎖；故n確定不會(huì)發(fā)生死鎖。反之，如果資源分配圖中存在環(huán)路，經(jīng)過(guò)簡(jiǎn)化（消

邊）后，則系統(tǒng)狀態(tài)圖中可能存在環(huán)路；，也可能不存在環(huán)路。根據(jù)資源分配圖

算法，如果每一種資源類(lèi)型只有一個(gè)實(shí)例且出現(xiàn)環(huán)路，那么無(wú)法簡(jiǎn)化（消邊），死

鎖發(fā)生，故in可以確定死鎖發(fā)生。剩下I和w都不能確定，因?yàn)樗鼈兊馁Y源分配

圖中雖然存在環(huán)路，但是不能確定是否可以簡(jiǎn)化成無(wú)環(huán)路的系統(tǒng)狀態(tài)圖。所以本

題選c選項(xiàng)。

27、下列存儲(chǔ)管理方式中，會(huì)產(chǎn)生內(nèi)部碎片的是（”I.分段虛擬存儲(chǔ)管理

n.分頁(yè)虛擬存儲(chǔ)管理m.段頁(yè)式分區(qū)管理w.固定式區(qū)區(qū)管理

A、僅I、口、m

B、僅山、IV

c、僅口

D、僅口、m、w

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

知識(shí)點(diǎn)解析；只要是固定的分配就會(huì)產(chǎn)生內(nèi)部碎片，其余的都會(huì)產(chǎn)生外部碎片。如

果固定和不固定同時(shí)存在（例如段頁(yè)式），物理本質(zhì)還是固定的，解釋如下：分

段虛擬存儲(chǔ)管理：每一段的長(zhǎng)度都不一樣（對(duì)應(yīng)不固定），所以會(huì)產(chǎn)生外部碎片。

分頁(yè)虛擬存儲(chǔ)管理：每一頁(yè)的長(zhǎng)度都一樣（對(duì)應(yīng)固定），所以會(huì)產(chǎn)生內(nèi)部碎片。

段頁(yè)式分區(qū)管理：地址空間首先被分成若干個(gè)邏輯分段（這里的分段只是邏輯上

的，而我們所說(shuō)的碎片都是物理上的真實(shí)存在的，所以是否有碎片還是要看每個(gè)段

的存儲(chǔ)方式，所以頁(yè)才是物理單位），每段都有自己的段號(hào)，然后再將每個(gè)段分成

若干個(gè)固定的頁(yè)。所以其仍然是固定分配，會(huì)產(chǎn)生內(nèi)部碎片。固定式分區(qū)管理：

很明顯固定，會(huì)產(chǎn)生內(nèi)部碎片。綜上分析，本題選D選項(xiàng)。

28、下列程序設(shè)計(jì)技術(shù)和數(shù)據(jù)結(jié)構(gòu)中，適合虛擬頁(yè)式存儲(chǔ)系統(tǒng)的有（）。I.堆棧

n.Hash函數(shù)索引的符號(hào)表m.順序搜索W.二分法查找V.純代碼VI.矢量

操作vn.間接尋址vr矩陣操作

A、I、m、v、W、vn

B、I、nm>vn

c、口、v、vi、vni

D、田、v、vi、vn

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

知識(shí)點(diǎn)解析：虛擬分頁(yè)存儲(chǔ)系統(tǒng)中，頁(yè)內(nèi)地址是連續(xù)的，而頁(yè)間地址不連續(xù)。當(dāng)頁(yè)

面不在內(nèi)存時(shí)，會(huì)引起缺頁(yè)中斷，相對(duì)消耗很多的時(shí)間。這類(lèi)題解題思路起始都是

應(yīng)該從局部性出發(fā)。I適合。棧頂操作一般是在當(dāng)前頁(yè)中進(jìn)行，此前已駐留內(nèi)

存。只有當(dāng)棧頂跨頁(yè)面時(shí)，才會(huì)引起缺頁(yè)中斷?？诓贿m合。Hash函數(shù)產(chǎn)生的索引

地址是隨機(jī)的，可能會(huì)頻繁缺頁(yè)。in適合。搜索一般是在當(dāng)前頁(yè)中進(jìn)行，此前已

駐留內(nèi)存。只有當(dāng)跨頁(yè)面搜索時(shí)，才會(huì)引起缺頁(yè)中斷。W不適合。二分法查找是

跳躍式的，可能會(huì)頻繁缺頁(yè)。V適合。純代碼基本上是順序執(zhí)行的。其跳轉(zhuǎn)指令

全是相對(duì)跳轉(zhuǎn)的，范圍一般在一個(gè)頁(yè)面之內(nèi)。只有當(dāng)跨頁(yè)面跳轉(zhuǎn)時(shí)，才會(huì)引起缺頁(yè)

中斷。VI適合。一個(gè)矢量的各分量均順序排列，一般在同一頁(yè)面內(nèi)。血不適合。

存放間接地址的頁(yè)面，存放直接地址的頁(yè)面，以及存放內(nèi)容的頁(yè)面沒(méi)有規(guī)律，它們

可能不在同一個(gè)頁(yè)面。而適合。矩陣的各元素均順序排列，一般在同一頁(yè)面內(nèi)。

29、下面關(guān)于文件的敘述中，錯(cuò)誤的是（）。I.打開(kāi)文件的主要操作是把指定文

件復(fù)制到內(nèi)存指定的區(qū)域口.對(duì)一個(gè)文件的訪(fǎng)問(wèn)，常由用戶(hù)訪(fǎng)問(wèn)權(quán)限和用戶(hù)優(yōu)先

級(jí)共同限制in.文件系統(tǒng)采用樹(shù)形目錄結(jié)構(gòu)后，對(duì)于不同用戶(hù)的文件，其文件名

應(yīng)該不同W.為防止系統(tǒng)故障造成系統(tǒng)內(nèi)文件受損，常采用存取控制矩陣方法保

護(hù)文件

A、僅U

B、僅I、m

c、僅I、m、w

D、I、口、山、W

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

知識(shí)點(diǎn)解析：I錯(cuò)誤，系統(tǒng)調(diào)用open把文件的信息目錄放到打開(kāi)文件表中?？阱e(cuò)

誤，對(duì)一個(gè)文件的訪(fǎng)問(wèn)，常由用戶(hù)訪(fǎng)問(wèn)權(quán)限和文件屬性共同限制。ID錯(cuò)誤，文件

系統(tǒng)采用樹(shù)形目錄結(jié)構(gòu)后，對(duì)于不同用戶(hù)的文件，其文件名可以不同，也可以相

同。W錯(cuò)誤，常采用備份的方法保護(hù)文件。而存取控制矩陣的方法是用于多用戶(hù)

之間的存取權(quán)限保護(hù)。

30、在PC—DOS中，某磁盤(pán)文件A與B,它們所占用的磁盤(pán)空間如下所示。試問(wèn)

、?.（?一、?一《?

FDT（文件目錄表》FAT（文件配置表》

A、3,3

B、4,5

C、5,3

D、5,4

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

知識(shí)點(diǎn)解析：當(dāng)查找文件在磁盤(pán)上的存放地址時(shí)，首先從目錄中找到文件的起始簇

號(hào)，然后再到FAT表的相應(yīng)表目中找到文件存放的下一個(gè)簇號(hào)，依此類(lèi)推，直至

遇到值為FFF的表項(xiàng)為止。文件A在磁盤(pán)上占用5簇，簇號(hào)依次為002、004、

009、005、007o文件B在磁盤(pán)上占用3簇，簇號(hào)依此為003、008、006。知識(shí)點(diǎn)

回顧：鏈接分配中每個(gè)文件對(duì)應(yīng)一個(gè)盤(pán)塊的鏈表，盤(pán)塊分布在磁盤(pán)的任何地方。

鏈接方式可分為隱式鏈諼和顯示鏈接兩種。隱式鏈接：在文件目錄的每個(gè)目錄項(xiàng)

中，都必須含有指向鏈接文件第一個(gè)盤(pán)塊和最后一個(gè)盤(pán)塊的指針。例如，目錄表中

有一個(gè)目錄項(xiàng)為（jeep,9,25）,表示jeep文件的第一個(gè)盤(pán)塊號(hào)是9,最后一個(gè)盤(pán)塊

號(hào)是25,而在每個(gè)盤(pán)塊中都含有一個(gè)指向下一個(gè)盤(pán)塊的指針，如

9—16—一10—25。如果指針占用4B,對(duì)于盤(pán)塊大小為512B的磁盤(pán)，則每個(gè)盤(pán)

塊中只有508B可供用戶(hù)使用。顯示鏈接：把用于鏈接文件各物理塊的指針，顯示

地存放在內(nèi)存的一張鏈裝表中。該表在整個(gè)磁盤(pán)僅設(shè)置一張。表的序號(hào)是物理盤(pán)塊

號(hào)，從0開(kāi)始，直到N—1,其中N為盤(pán)塊總數(shù)。在每個(gè)表項(xiàng)中存放鏈接指針，即

下一個(gè)盤(pán)塊號(hào)。

31、某磁盤(pán)盤(pán)組共有10個(gè)盤(pán)面，每個(gè)盤(pán)面上有100個(gè)磁道，每個(gè)磁道有32個(gè)扇

區(qū)，假定物理塊的大小為2個(gè)扇區(qū)，分配以物理塊為單位。若使用位圖（bitmap）管

理磁盤(pán)空間，則位圖需要占用的空間大小是（）。

A、2000B

B、12000B

C、6000B

D、16000B

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

知識(shí)點(diǎn)解析：已知磁盤(pán)盤(pán)組共有10個(gè)盤(pán)面，每個(gè)盤(pán)面上有100個(gè)磁道，每個(gè)磁道

有32個(gè)扇區(qū)，則一共有10x100x32=32000個(gè)扇區(qū)。題目又假定物理塊的大小為2

個(gè)扇區(qū)，分配以物理塊為單位，即一共有16000個(gè)物理塊。因此，位圖所占的空

間為16000/8B=2000B,知識(shí)點(diǎn)回顧：磁盤(pán)可包括一個(gè)或多個(gè)物理盤(pán)片，每個(gè)盤(pán)

片分一個(gè)或兩個(gè)存儲(chǔ)面，每個(gè)存儲(chǔ)面組織成若干個(gè)同心環(huán)，即為磁道。每條磁道又

從邏輯上劃分成若干扇區(qū)（也稱(chēng)為盤(pán)塊）。位圖（位示圖）用二進(jìn)制位表示磁盤(pán)

中的一個(gè)盤(pán)塊的使用情況，0表示空閑，1表示已分配。磁盤(pán)上的所有盤(pán)塊都與一

個(gè)二進(jìn)制位相對(duì)應(yīng)，這樣，由所有盤(pán)塊所對(duì)應(yīng)的位構(gòu)成一個(gè)集合，稱(chēng)為位示圖。通

?？捎胢xn個(gè)位數(shù)構(gòu)成位示圖，并使mxn等于磁盤(pán)的總塊數(shù)。（考點(diǎn)所在）位圖

法的優(yōu)點(diǎn)就是很容易找到一個(gè)或一組相鄰的空閑盤(pán)塊。位示圖一般來(lái)說(shuō)非常小，可

以把它保存在內(nèi)存中，進(jìn)而使在每次進(jìn)行磁盤(pán)空間分配時(shí)，無(wú)須都要進(jìn)行位示圖讀

入內(nèi)存的操作，從而節(jié)省了磁盤(pán)的啟動(dòng)操作。

32、關(guān)于SPOOLing技術(shù)的說(shuō)法，以下正確的是（）。I.SPOOLing系統(tǒng)中不需要

獨(dú)占設(shè)備D.SPOOLing系統(tǒng)加快了作業(yè)完成的速度ID.當(dāng)輸入設(shè)備忙時(shí)，

SPOOLing系統(tǒng)中的用戶(hù)程序暫停執(zhí)行，待I/O空閑時(shí)再被喚醒執(zhí)行輸出操作

IV.在采用SPOOLing技術(shù)的系統(tǒng)中，用戶(hù)的打印結(jié)果首先被送到內(nèi)存固定區(qū)域

A、僅I、D

B、僅口

c、僅口、m

D、僅皿、IV

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

知識(shí)點(diǎn)解析：I錯(cuò)誤，SPOOLing技術(shù)是將獨(dú)占設(shè)備改為共享設(shè)備，所以肯定需要

獨(dú)占設(shè)備。II正確，SPOOLing技術(shù)通過(guò)在磁盤(pán)上開(kāi)辟存儲(chǔ)空間模擬脫機(jī)輸出，可

以減少作業(yè)輸出等待時(shí)間，加快作業(yè)完成的速度。DI錯(cuò)誤，引入SPOOLing技術(shù)

的目的就是在輸入設(shè)備忙時(shí)，進(jìn)程不必等待I/O操作的完成。W錯(cuò)誤，在

SPOOLing系統(tǒng)中，用戶(hù)的輸出數(shù)據(jù)先送入輸出井，即磁盤(pán)固定區(qū)域。綜上分析，

本題選B選項(xiàng)。知識(shí)點(diǎn)回顧：SPOOLing系統(tǒng)是對(duì)脫機(jī)輸入/輸出工作的模擬，它

必須有高速大容量且可隨機(jī)存取的外存（如磁盤(pán)、磁鼓等）支持。SPOOLing系統(tǒng)

組成如圖7—9所示，主要包括以下3個(gè)部分。

內(nèi)存

圖7-9SPOOLing系統(tǒng)組成

33、如圖7—1所示的是某IP網(wǎng)絡(luò)連接拓?fù)浣Y(jié)構(gòu)，共有（）。

圖7-1

A、5個(gè)沖突域，1個(gè)廣播域

B、3個(gè)沖突域，3個(gè)廣播域

C、4個(gè)沖突域.2個(gè)廣播域

D、6個(gè)沖突域，2個(gè)廣播域

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

知識(shí)點(diǎn)解析：通常普通的集線(xiàn)器是一種工作在物理層，具有“共享沖突域、共享廣

播域''特性的網(wǎng)絡(luò)互連設(shè)備。而將交換機(jī)和網(wǎng)橋稱(chēng)為二層設(shè)備，它是一種工作在數(shù)

據(jù)鏈路層，具有“隔離沖突域、共享廣播域''特性的網(wǎng)絡(luò)互連設(shè)備?？梢?jiàn)，交換機(jī)只

能縮小沖突域，而不能縮小廣播域。將路由器稱(chēng)為三層設(shè)備，它是一種工作在網(wǎng)絡(luò)

層,具有“隔離沖突域、隔離廣播域''功能的網(wǎng)絡(luò)互連設(shè)備。在Internet等主干網(wǎng)

上，路由器的主要作用是路由選擇。由以上分析可知，圖7—1所示的拓?fù)浣Y(jié)構(gòu)中

共有4個(gè)沖突域，2個(gè)廣播域，具體如圖7—10所示。其中，沖突域1和沖突域2

屬于同一個(gè)廣播域，沖突域3和沖突域4屬于另外一個(gè)廣播域?？偨Y(jié)(見(jiàn)表7—3):

表7-3各設(shè)備的沖突域與廣播域

設(shè)答名林隔離沖突域隔離廣播城

集線(xiàn)器XX

中繼蹲XX

交換機(jī)X

網(wǎng)橋VX

型用器VV

34、長(zhǎng)度為1km,數(shù)據(jù)傳輸率為10Mbit/s以太網(wǎng)，電信號(hào)在網(wǎng)上的傳播速度是

200m/gSo假設(shè)以太網(wǎng)數(shù)據(jù)幀的長(zhǎng)度為256bit,其中包括64bit幀頭、檢驗(yàn)和及其他

開(kāi)銷(xiāo)。數(shù)據(jù)幀發(fā)送成功后的第一個(gè)時(shí)間片保留給接收方，用于發(fā)送一個(gè)64bit的確

認(rèn)幀。假設(shè)網(wǎng)絡(luò)負(fù)載非常輕(即不考慮沖突的任何情形)，則該以太網(wǎng)的有效數(shù)據(jù)

傳輸速率為()。

A、4.21Mbit/s

B、11.7Mbit/s

C、6.09Mbit/s

D、5.19Mbit/s

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

知識(shí)點(diǎn)解析：⑴發(fā)送256bit數(shù)據(jù)幀所用的發(fā)送時(shí)間=256bit/10Mbit/s=25.6吟⑵數(shù)

據(jù)幀在電纜線(xiàn)上的傳播時(shí)間=1000m/(200m/|xs)=5NS；(3)發(fā)送64bit的確認(rèn)幀所用的

發(fā)送時(shí)間=64bit/10Mbit/s=6.4g；(4)確認(rèn)幀在電纜上的傳播時(shí)間

=1000m/(200nvjis)=5|is；(5)為了保證沖突檢測(cè)機(jī)制能夠正常進(jìn)行，64位確認(rèn)幀要

進(jìn)行填充，使得其傳輸時(shí)延等于往返傳播時(shí)延10gs；有效數(shù)據(jù)傳輸率=發(fā)送的有效

數(shù)據(jù)/發(fā)送有效數(shù)據(jù)所用的總時(shí)間，而有效數(shù)據(jù)=(256—64)bil=192bit,發(fā)送192bit

的有效數(shù)據(jù)所古用的總時(shí)間=(25.6+5+6.4+5)2=45.62；則該以太網(wǎng)的有效數(shù)據(jù)傳

輸率為192bit/42Hs=4.21Mbit/s。

35、下面技術(shù)無(wú)法使10Mbit/s的以太網(wǎng)升級(jí)到100Mbit/s的是()。

A、幀長(zhǎng)保持不變，網(wǎng)絡(luò)跨距增加

B、采用幀擴(kuò)展技術(shù)

C、傳輸介質(zhì)使用高速光纖

D、使用以太網(wǎng)交換機(jī)，引入全雙工流量控制協(xié)議

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

知識(shí)點(diǎn)解析：CSMA/CD協(xié)議要求每幀的發(fā)送時(shí)間不小于信號(hào)的往返時(shí)延。如果電

纜線(xiàn)長(zhǎng)度增加，傳播時(shí)延增加，沖突檢測(cè)時(shí)間增加，幀長(zhǎng)保持不變，則發(fā)送速率應(yīng)

減少，A錯(cuò)。幀擴(kuò)展技術(shù)解決了網(wǎng)絡(luò)跨距問(wèn)題，但可能影響短幀的傳輸性能，在千

兆以太網(wǎng)標(biāo)準(zhǔn)中增加了噴突發(fā)技術(shù)，提高了網(wǎng)絡(luò)帶寬利用率，B對(duì)。高速光纖的使

用大大提高了網(wǎng)絡(luò)的傳瑜速率，使lOMbit/s升級(jí)到lOOMbit/s和IGbit/s成為nJ?能，

C對(duì)。全雙工的以太網(wǎng)交換機(jī)不執(zhí)行CSMA/CD協(xié)議，每幀的發(fā)送時(shí)間不受往返時(shí)

延影響，D對(duì)。

36、某端口的1P地址為172.16.7.131/26,則該IP地址所在網(wǎng)絡(luò)的廣播地址是

（）。

A、172.16.7.255

B、172.16.7.129

C、172.16.7.191

D、172.16.7.252

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

知識(shí)點(diǎn)解析：首先要清楚廣播地址就是將主機(jī)位全部置為1,/26表示前3個(gè)字節(jié)

都是網(wǎng)絡(luò)段，最后一個(gè)字節(jié)的頭兩位也是網(wǎng)絡(luò)段。前.3個(gè)字節(jié)忽略，只解釋最后一

個(gè)字節(jié)。將131以二進(jìn)制表示為10000011。根據(jù)廣播地址的定義，主機(jī)段全1即

為廣播地址，即10111111,轉(zhuǎn)換為十進(jìn)制為191,故廣播地址為172.16.7.191,

37、下列關(guān)于A(yíng)RP的說(shuō)法中，錯(cuò)誤的是（）。I.ARP的請(qǐng)求報(bào)文是單播的

H.ARP的響應(yīng)報(bào)文是單播的HI.如果局域網(wǎng)A的主機(jī)1想和局域網(wǎng)B的主機(jī)2

通信，但是主機(jī)1不知道主機(jī)2的物理地址，主機(jī)1通過(guò)發(fā)送ARP報(bào)文就可以解

決

A僅

、I

B僅

、

c僅

、I、m

D僅

、口、m

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

知識(shí)點(diǎn)解析：I：當(dāng)主磯A要向本局域網(wǎng)上的某個(gè)主機(jī)B發(fā)送IP數(shù)據(jù)報(bào)時(shí)，如果

在其ARP高速緩存中查詢(xún)不到主機(jī)B的物理地址，這時(shí)候ARP進(jìn)程就需要在本局

域網(wǎng)卜廣播發(fā)送一個(gè)ARP請(qǐng)求分組.所以ARP的請(qǐng)求報(bào)文是廣播的,不是單播

的，故I錯(cuò)誤?！?接著上面的論述，此時(shí)應(yīng)該是本局域網(wǎng)上的所有主機(jī)都可以收

到此ARP的請(qǐng)求分組，而主機(jī)B見(jiàn)到ARP分組中的IP地址是自己的IP時(shí)，就向

主機(jī)A發(fā)送一個(gè)ARP響應(yīng)分組，所以ARP響應(yīng)分組是普通的單播，故II正確。

n：這個(gè)一定要注意了，很多考生都誤認(rèn)為是正確的。記住一句話(huà)：ARP是解決

同一局域網(wǎng)上的主機(jī)或路，由器的1P地址和硬件地址的映射問(wèn)題，如果所要找的

主機(jī)和源主機(jī)不在同一個(gè)局域網(wǎng)上，剩下的所有工作都應(yīng)該由下一跳的路由器來(lái)完

成，故m錯(cuò)誤。注：ARP數(shù)據(jù)單元是被封裝在以太幀中。

38、—個(gè)網(wǎng)段的網(wǎng)絡(luò)號(hào)為198.90.10.0/27,子網(wǎng)掩碼固定為

255.255.255.224,最多可以分成（）個(gè)子塊，而每個(gè)子塊最多具有（）個(gè)有效的IP

地址。

A、8,30

B、6,30

C、16,14

D、32,6

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

知識(shí)點(diǎn)解析：/27是引入無(wú)類(lèi)別域間路由選擇（CIDR）后子網(wǎng)IP地址的表示方法，對(duì)

應(yīng)的子網(wǎng)掩碼表示是255.255.255.224。地址的最后I個(gè)字節(jié)中有3位屬于子網(wǎng)號(hào)部

分（物理網(wǎng)絡(luò)號(hào)共27位），主機(jī)號(hào)只有5位。198.90.10.0是C類(lèi)地址，網(wǎng)絡(luò)號(hào)24

位，最后1個(gè)字節(jié)中的子網(wǎng)號(hào)3位，最多可以分成8個(gè)子塊，主機(jī)號(hào)部分5位共

32個(gè)地址，除了全1和全O,有30個(gè)有效的IP地址。易混知識(shí)點(diǎn)：什么時(shí)候子

網(wǎng)號(hào)可以為全“0”或全“1”？解析：當(dāng)使用CIDR時(shí)，子網(wǎng)號(hào)可以使用全“0”或全

“1”，因?yàn)镃IDR子塊的劃分并不是真正意義上的子網(wǎng)劃分，只是劃分的形式很像

子網(wǎng)的劃分。那有的同學(xué)可能會(huì)問(wèn)，我怎么知道是不是CIDR?只要題目的網(wǎng)絡(luò)號(hào)

是以X.X.X.X/Y的形式給出，就認(rèn)為是CIDR。

39、A和B建立TCP連接，MSS為1KB。某時(shí)，慢開(kāi)始門(mén)限值為2KB,A的擁塞

窗口為4KB,在接下來(lái)的一個(gè)RTT內(nèi)，A向B發(fā)送了4KB的數(shù)據(jù)（TCP的數(shù)據(jù)部

分），并且得到了B的確認(rèn)，確認(rèn)報(bào)文中的窗口字段的值為2KB,那么，請(qǐng)問(wèn)在

下一個(gè)RTT中，A最多能向B發(fā)送（）數(shù)據(jù)。

A、2KB

B、4KB

C、SKB

D、8KB

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

知識(shí)點(diǎn)解析：首先，發(fā)送窗口應(yīng)該在擁塞窗口和接收窗口中取最小值，所以本題關(guān)

鍵點(diǎn)在于求本RTT內(nèi)擁塞窗口和接收窗口的大小。在接下來(lái)的一個(gè)RTT內(nèi)，A向

B發(fā)送了4KB的數(shù)據(jù)，且此時(shí)擁塞窗口為4KB,按照擁塞避免算法（因?yàn)榇藭r(shí)擁

塞窗口大于慢開(kāi)始門(mén)限值，所以采用擁塞避免算法），收到B的確認(rèn)報(bào)文后，擁

塞窗口增加到SKB。另外，B發(fā)給A的確認(rèn)報(bào)文中的窗口字段的值為2