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

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

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

1、一個棧的入棧序列是1,2,3,4,5,則棧的不可能的輸出序列是（）。

A、5,4,3,2,1

B、4,5,3,2,1

C、4,3,5,1,2

D、1,2,3,4,5

標準答案：C

知識點解析：此類問題是常見題型。解答的基本原理是：一串數(shù)據(jù)依次通過一個

棧，并不能保證出棧數(shù)據(jù)的次序總是倒置，可以產(chǎn)生多種出棧序列。一串數(shù)據(jù)通過

一個棧后的次序由每個數(shù)據(jù)之間的進棧、出棧操作序列決定，只有當所有數(shù)據(jù)“全

部進棧后再全部出?！辈拍苁箶?shù)據(jù)倒置…事實上，存在一種操作序列——“進棧、出

棧、進棧、出?！薄梢允箶?shù)據(jù)通過棧后仍然保持次序不變.［解題技巧］將

一組數(shù)據(jù)入棧后，判斷題目備選項中的不可能的出棧順序，上述這類題目有一個解

題技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素

的序號）的兩個元素。

2、設有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a［，］為第

一元素，其存儲地址為1,每個元素占一個地址空間，則a8,5的地址是（）。

A、13

B、33

C、18

D、40

標準答案：B

知識點解析：這里數(shù)組下標從1開始，只存儲其下三角形元素，在5的前面有7

行，第1行有1個元素，第2行有2個元素，…，第7行有7個元素，這7行共有

（1+7）x7/2=28個元素，在第8行中，ag.5的前面有4個元素，所以，a8,5前有

28+4=32個元素，其地址為33。

3、在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（）。

A、n

B、n—1

C、n+1

D、2n

標準答案：C

知識點解析：在一棵具有n個結(jié)點的二叉樹中，每個結(jié)點可有兩棵子樹，共有2n

個子樹。其中二叉樹的總分支數(shù)等于總結(jié)點數(shù)減1,即有n—1棵不空的子樹。所

以在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于n+lo

4、在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點是（）。

A、左指針一定為空

B、右指針一定為空

C、左右指針均為空

D、左右指針均不為空

標準答案：B

知識點解析：在二叉排序樹的存儲結(jié)構(gòu)中，每個結(jié)點由三部分構(gòu)成，其中左（或右）

指針指向比結(jié)點的關(guān)鍵值?。ɑ虼螅┑慕Y(jié)點。關(guān)鍵字值最大的結(jié)點位于二叉排序礴的

最右位置上，因此它的右指針一定為空。

5、由權(quán)值為9、2、5、7的四個葉子構(gòu)造一棵哈夫蛙樹，該樹的帶權(quán)路徑長度為

（）。

A、23

B、37

C、44

D、46

標準答案：C

知識點解析：由權(quán)值為9、2、5、7的四個葉子構(gòu)造的哈夫曼樹可如下圖所示。

?⑤該樹的帶權(quán)路徑長度=9x1+7x2+2x3+5x3=44。［歸納總結(jié)］對哈

夫曼樹特征的總結(jié)：（1）用n個權(quán)值（對應n個葉子結(jié)點）構(gòu)造哈夫曼樹，共需要n-

1次合并，即哈夫曼樹中非葉子結(jié)點的總數(shù)為n—L總結(jié)點個數(shù)為2n—l。（2）哈

夫變樹中沒有度為1的結(jié)點，因為非葉子結(jié)點都是通過兩個結(jié)點合并而來。但是，

沒有度為1的二叉樹并不一定是哈夫曼樹。（3）用n個權(quán)值（對應n個葉子結(jié)點）構(gòu)造

的哈夫曼樹，形態(tài)并不是唯一的。建立哈夫曼樹的過程中有以下三種常見的錯

誤：（1）在合并中不是選取根結(jié)點權(quán)值最小的兩棵二叉樹（包括已合并的和未合并

的），而是選取未合并的根結(jié)點權(quán)值最小的一棵二叉樹與己經(jīng)合并的二叉樹合并。

⑵每次都是在未合并的二叉樹中選取根結(jié)點的權(quán)值最小的兩棵子樹。（3）有時沒有

嚴格按照哈夫曼算法也兩造出帶權(quán)路徑長度與哈夫曼樹相同的二叉樹，但那只是巧

合，沒有規(guī)律性，而沒有規(guī)律性的解法不利于用計算機進行處埋。

6、若一個具有n個結(jié)點、k條邊的非連通無向圖是一個森林（n>k）,則該森林中必

有樹的數(shù)目是（）。

A、k

B、n

C、n—k

D、n+k

標準答案：C

知識點解析：因為一棵具有n個頂點的樹有n-l條邊，因此設題目中的森林有m

棵樹，每棵樹具有頂點數(shù)為Vi(lgiWm),則V1+V2+…Vm=N&(V|-1)+"2—1)

+...(Vm—1)=K,所以，2=m+ko

7、采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于樹的()。

A、中根遍歷

B、先根遍歷

C、后根遍歷

D、按層次遍歷

標準答案：D

知識點解析：深度優(yōu)先嗖索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。廣

度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程?；蛘哒f，樹的先根遍歷是一種深度

優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略。

8、在有向圖G的拓撲產(chǎn)列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)

的是()。

A、G中有弧i,Vj>

B、G中有一條從Vi到Vj的路徑

C、G中沒有弧i,Vj>

D、G中有一條從Vi到Vj的路徑

標準答案：D

知識點解析：選項A、B、C都是有可能出現(xiàn)的，但是選項D是不可能出現(xiàn)的，因

為若是G中有一條從V到Vi的路杼，則在圖的拓撲序列中頂點Vi應該在頂點Vi

之前。

9、假設有k個關(guān)鍵字互為同義詞，若用線性探查法把這k個關(guān)鍵字存入，至少要

進行的探查次數(shù)是()。

A、k-1

B、k

C、k+1

D、k(k+l)/2

標準答案：D

知識點解析：假設有k個關(guān)鍵字互為同義詞，若用線性探查法把這k個關(guān)鍵字存

入，探查次數(shù)最少的情況是第1個關(guān)鍵字通過1次比較后插入，第2個關(guān)鍵字通過

2次比較后插入，……，第k個關(guān)鍵字通過k次比較后插入。總的比較次數(shù)=1+2

+......+k=k(k+l)/2。

10、下列序列中，滿足堆定義的是（）。

A、（100,86,48,73,35,39,42,57,66,21）

B、（12,70,33,65,24,56,48,92,86,33）

C、（103,97,56,38,66,23,42,12,30,52,6,26）

D、（5,56,20,23,40,38,29,61,36,76,28,100）

標準答案：A

知識點解析：依據(jù)堆的定義，將選項中的每個數(shù)列分別看成是一棵完全二叉樹，則

堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當左/

右子樹不空時，根結(jié)點的值小于（或大于）左/右子樹根結(jié)點的值。

11、對于一個長度為n的任意表進行排序，至少需要進行的比較次數(shù)是（）。

A、O（n）

B、O（n2）

C^0（log

D、O（nlogn）

標準答案：D

知識點解析：在排序過程中，每次比較會有兩種情況出現(xiàn)，若整個排序過程中至少

需要t次比較，則顯然會有21種情況，由于n個記錄總共有出種不同的排列，因而

必須有n!種不同的比較路徑，于是有：2（＞n!,即Glog2（n!）。因為

Iog2（n!）-nlog2n,所以Gnlog2n。

12、哈佛（Harvard）結(jié)構(gòu)的基本特點是（）。

A、采用多指令流單數(shù)據(jù)流

B、程序和數(shù)據(jù)在不同的存儲空間

C、堆棧操作

D、存儲器按內(nèi)容選擇地址

標準答案：B

知識點解析：哈佛結(jié)構(gòu)的指令和數(shù)據(jù)是完全分開的，存儲器分為兩部分，一個是程

序存儲器，用來存放指令，另一個是數(shù)據(jù)存儲器，用來存放數(shù)據(jù)。［歸納總結(jié)］根據(jù)

程序（指令序列）和數(shù)據(jù)的存放形式，存儲器設計思想又可以分為馮?諾依曼結(jié)構(gòu)和哈

佛結(jié)構(gòu)。馮?諾依曼結(jié)構(gòu)的存儲器設計是指令和數(shù)據(jù)是不加區(qū)別混合存儲在同一個

存儲器中，共享數(shù)據(jù)總線；哈佛結(jié)構(gòu)的存儲器設計是指令和數(shù)據(jù)是完全分開的，存

儲器分為兩部分，一個是程序存儲器，用來存放指令，另一個是數(shù)據(jù)存儲器，用來

存放數(shù)據(jù)。在馮.諾依曼結(jié)構(gòu)中不能同時取指令和取操作數(shù)，而哈佛結(jié)構(gòu)允許同時

獲取指令字（來自程序存儲器）和操作數(shù)（來自數(shù)據(jù)存儲器）。

13、若二進制定點小數(shù)真值是一0.1101,機器中表示為1.0010,則該數(shù)采用的

編碼方法是（）。

A、原碼

B、補碼

C、反碼

D、移碼

標準答案：C

知識點解析：真值一0.1101,對應的原碼表示為1.1101,補碼表示為1.0011,

反碼表示為1.0010c移碼通常用于表示階碼，不用來表示定點小數(shù)。［歸納總結(jié)］

對于負數(shù)，原碼、補碼和反碼各有不同的表示形式。［解題技巧］由于真值是定點小

數(shù)，不能用移碼表示，所以可立即排除掉選項D。接下來寫出真值對應的原碼、補

碼和反碼，即可得出答案。

14、描述流水線CPU基本概念中，正確表述的句子是（）。

A、流水線CPU是以空間并行性為原理構(gòu)造的處理

B、流水線CPU一定是RISC機器

C、流水線CPU一定是多媒體CPU

D、流水線CPU是一種非常經(jīng)濟而實用的時間并行技術(shù)

標準答案：D

知識點解析：在4個選項中唯有選項D是正確的。選項A是指超標量處理機。

Rise機器一定采用流水線技術(shù)，而流水線CPU不一定就是RIsC機器。流水線

CPU也不一定是多媒體CPU。［歸納總結(jié)］超標量處理機采用的是空間并行性，流

水線處理機采用的是時間并行性。

15、原碼乘法時，符號位單獨處理，乘積的符號是（）。

A、兩個操作數(shù)符號相“與”

B、兩個操作數(shù)符號相“或”

C、兩個操作數(shù)符號相“異或”

D、兩個操作數(shù)中絕對值較大數(shù)的符號

標準答案：C

知識點解析：原碼的符號位為“1”表示負數(shù)，為“0”表示正數(shù)。原碼乘法時，符號位

單獨處理，乘積的符號是兩個操作數(shù)符號相“異或”，同號為正，異號為負。［歸納

總結(jié)］凡是原碼運算.不論加減乘除,符號位都單獨處理?其中乘除運算的結(jié)果符

號由參加運算的兩個操作數(shù)符號“異或”得到。

16、頁式存儲系統(tǒng)的邏輯地址是由頁號和頁內(nèi)地址兩部分組成，地址變換過程如下

圖所示。假定頁面的大小為8K,圖中所示的十進制邏輯地址9612經(jīng)過地址變換

校—■一■*―

――［/-觸］［蝴21

J5母筋奔於另

j13~\*理**

后,形成的物理地址a（十進制）是（）。IT?

A、42380

B、25996

C、9612

D、8192

標準答案：B

知識點解析：由于頁面大小為8K,則十進制邏輯地址9612處于第1虛頁中，頁內(nèi)

地址一1420,其對應的實頁為第3頁，故a=3x8192+1420=25996。［歸納總結(jié)］

具體的計算公式有：虛頁號=|虛地址/頁面大小|頁內(nèi)地址=虛地址一虛頁號x頁

面大小主存實地址=實頁號x頁面大小+頁內(nèi)位移量頁式虛擬存儲器中的頁表的

每一行記錄了與某個虛頁對應的若干信息，包括虛頁號、裝入位和實頁號等。頁表

基址寄存器和虛頁號拼接成頁表索引地址。根據(jù)這個索引地址可讀到一個頁表信息

字，然后檢測頁表信息字中裝入位的狀態(tài)。若裝入位為“1”，表示該頁面已在主存

中，將對應的實頁號與虛地址中的頁內(nèi)地址相拼接就得到了完整的實地址；若裝入

位為“0”,表示該頁面不在主存中，于是要啟動I/O系統(tǒng)，把該頁從輔存中調(diào)入主

存后再供CPU使用。［解題技巧］首先，根據(jù)題目那給出的虛地址可以計算出虛頁

號和頁內(nèi)地址，然后根據(jù)所求出的虛頁號查頁表找出實頁號，最后將實頁號拼上頁

內(nèi)地址得到相應的主存地址。

17、在指令系統(tǒng)的各種尋址方式中，獲取操作數(shù)最快的方式是()。

A、直接尋址

B、立即尋址

C、寄存器尋址

D、間接尋址

標準答案：B

知識點露析：立即尋址是一種特殊的尋址方式，指令中在操作碼字段后面的部分不

是通常意義上的地址碼，而是操作數(shù)本身，也就是說數(shù)據(jù)就包含在指令中，只要取

出指令，也就取出了可以立即使用的操作數(shù)，不必再次訪問存儲器，從而提高了指

令的執(zhí)行速度。［歸納總結(jié)］所謂尋址，指的是尋找操作數(shù)的地址或下一條將要執(zhí)行

的指令地址。各種不同的尋址方式獲取操作數(shù)的速度是不相同的，在這四種尋址方

式中，獲取操作數(shù)的速度由快至慢依次為立即尋址、寄存器尋址、直接尋址、間接

尋址。

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

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

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

()o

A、100—R0

B、IOOTMDR

C、PC一MAR

D、PCTIR

標準答案：c

知識點解析：無論運行什么類型的指令，CPU首先需要取指令，取指令階段的第

一個操作就是將指令地址(程序計數(shù)器PC中的內(nèi)容)送往存儲器地址寄存器。［歸納

總結(jié)］取指周期完成的微操作序列是公共的操作，與具體指令無關(guān)，取指公操價如

下：(1)將程序計數(shù)器PC中的內(nèi)容送至存儲器地址寄存器MAR,記作

(PC)TMAR；(2)向主存發(fā)讀命令，記作Read：(3)從主存中取出的指令送到存儲

器數(shù)據(jù)寄存：器MDR,記作M（MAR）-MDR；（4）將MDR的內(nèi)容送至指令寄存

器IR中，記作（MDR）TIR；（5）將PC的內(nèi)容遞增，為取下一條指令做好準備，記

作（PC）+1-PC。［解題技巧］題干中雖然給出了一條具體的指令“MOVRO,

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

19、在微指令的編碼方式中，若微命令數(shù)相同，下列敘述中正確的是（）。I.直接

控制方式與編碼控制方式的微指令長度相等D.最短編碼控制和直接控制方式不

影響微指令字長m.編碼控制方式的微指令比直接控制方式的微指令短w.直接

控制的微指令比字段編碼的微指令長V.字段直接編碼的微指令與字段間接編碼的

微指令長度相等VI.字段間接編碼的微指令比字段直接編碼的微指令長

A、in和w

B、I和m

c、口和川

D、m、w和VI

標準答案：A

知識點解析：微指令的操作控制字段可分為直接控制法、最短編碼法和字段編碼

法，字段編碼法中又可以進一步分為字段直接編碼法和字段間接編碼法。若微命令

數(shù)相同，微指令操作控制字段的長度由短至長依次為：最短編碼T字段間接編碼T

字段直接編碼一直接控制。操作控制字段短則相應的微指令字長就短。［歸納總結(jié)］

直接控制法即每個獨立的二進制位代表一個微命令，該位為“1”表示這個微命令有

效，為“0”則表示這個微命令無效。最短編碼法將所有的微命令統(tǒng)一編碼，每條微

指令只定義一個微命令。字段編碼法是前述兩種編碼法的一個折中的方法，將操作

控制字段分為若干組，組內(nèi)采用最短編碼法，組與組之間采用直接控制法。在字

段編碼法中，操作控制字段的分組并非是任意的，必須要遵循如下的原則：（1）應

把互斥性的微命令分在同一組內(nèi)，兼容性的微命令分在不同組內(nèi)。這樣不僅有助于

提高信息的利用率，縮短微指令字長，而且有助于充分利用硬件所具有的并行性，

加快執(zhí)行的速度。（2）應與數(shù)據(jù)通路結(jié)構(gòu)相適應。（3）每個小組中包含的信息位不能

太多，否則將增加譯碼線路的復雜性和譯碼時間。（4）一般每個小組還要留出一個

狀態(tài)，表示本組不發(fā)出任何微命令。因此當某組的長度為3位時，最多只能表示7

個互斥的微命令，通常用000表示不操作。

20、下列計算機總線屬于串行總線的是（）。

A、PCI

B、1394

C、EISA

D、ISA

標準答案：B

知識點解析：1394是高性能的串行總線。［歸納總結(jié)IIEEE—1394是由IEEE標準

委員會發(fā)布的，它的最初版本傳輸速率為200.Mbps,高版本有望支持1600Mbps

的傳輸速率，甚至可達到3200Mbps。IEEE—1394構(gòu)建在菊花鏈或樹狀的拓撲結(jié)

構(gòu)上的，它支持63個節(jié)點，每個節(jié)點可以支持多達16臺設備的菊花鏈。最新的

高性能外部總線設計的趨勢是使用串行結(jié)構(gòu)，這樣可以通過一根導線一次發(fā)送一位

數(shù)據(jù)，而無須擔心數(shù)據(jù)的到達時間，如IEEE—1394端口（使用高速串行技術(shù)）支持

的傳輸速率高達400Mbps（約50MB/s）,USB2.0支持的傳輸速率可以為

480Mbps（約60MB/s）。［解題技巧］選項A、C、D均屬于并行總線。

21、某數(shù)碼相機內(nèi)置128MB的存儲空間，拍攝分辨率設定為1600x1200像素，顏

色深度為24位，若不采用壓縮存儲技術(shù)，使用內(nèi)部存儲器最多可以存儲的照片數(shù)

是（）。

A、12

B、25

C、13

D、23

標準答案：D

知識點解析：顏色深度為24位（3個字節(jié)），每張照片的存儲量為

1600x1200x3即5.5MB,128MB/5.5MB=23.3,所以內(nèi)置的存儲空間最多可

存儲23張照片。［歸納總結(jié)］數(shù)碼相機內(nèi)部存儲器存放照片數(shù)的多少與照片的分辨

率和顏色數(shù)有關(guān)。

22、中斷向量表中保存的是（）。

A、被中斷程序的返回地址

B、中斷服務程序入口地址

C、中斷優(yōu)先級

D、中斷源編碼

標準答案：B

知識點解析：中斷向量表是用來存放中斷服務程序的人口地址的。［歸納總結(jié)］許多

計算機中在主存的特定位置設置有中斷向量表，在中斷向量表的相關(guān)單元中存放著

各級中斷服務程序的入口地址。中斷源給出的向量地址是中斷向量表的指針，也就

是中斷服務程序入口地址的地址。由向量地址指向一個中斷向量表，從中斷向量表

的相應單元中再取出中斷服務程序的入口地址C

23、對于設計實時操作系統(tǒng)，不是其設計目標的是（）。

A、安全可靠

B、處理機效率

C、及時響應輸入

D、快速處理請求

標準答案：B

知識點解析：本題考查實時操作系統(tǒng)的設計目標。實時操作系統(tǒng)要求能對用戶的請

求在規(guī)定的時間內(nèi)完成，同時需要保證進程運行的安全性和高可靠性。而處理機的

效率不是實時操作系統(tǒng)沒計所關(guān)心的。

24、并發(fā)進程在運行時，其推進的相對速度是（）。

A、由進程的程序結(jié)構(gòu)決定

B、由進程自己的代碼控制

C、與進程調(diào)度策略有關(guān)

D、在進程創(chuàng)建時確定的

標準答案：C

知識點解析：在進程的一次運行過程中，其代碼的執(zhí)行序列是確定的，即使有循環(huán)

或轉(zhuǎn)移，對于進程來講，其運行的軌跡也是確定的，所以對于這樣一個確定的運行

軌跡，進程自身是可以控制自身前進或停止的，例如可以休眠10秒再喚醒等，但

是，當這樣的進程存在于一個并發(fā)系統(tǒng)中時，這種確定性就被打破了。由于系統(tǒng)中

存在有大量的可運行的進程，操作系統(tǒng)為了提高計算機的效率，會根據(jù)用戶的需求

和系統(tǒng)資源的數(shù)量來自動地進行調(diào)度和切換，以保證系統(tǒng)高效地運行。此時，進程

由于被調(diào)度，打破了原來的固有執(zhí)行速度，走走停停，因此，進程的相對速度就不

受進程自己的控制，而是取決于進程調(diào)度的策略。不確定性也是并發(fā)系統(tǒng)的一個特

征。

25、兩個旅行社甲和已為旅客到某航空公司訂飛機票，形成互斥資源的是（）。

A、旅行社

B、航空公司

C、飛機票

D、旅行社與航空公司

標準答案：C

知識點解析：本題考查互斥資源的問題，一張飛機票不能售給不同的旅客，因此飛

機票是互斥資源，其它因素只是為完成飛機票訂票的中間過程，與互斥資源無關(guān)。

26、在進程通信中，消息的一般形式為四個部分組成。是（）。

A、發(fā)送進程名、接收進程名、消息標示符、消息正文

B、發(fā)送進程名、消息標示符、消息長度、消息正文

C、發(fā)送進程名、接收進程名、消息長度、消息當前狀態(tài)

D、發(fā)送進程名、接收進程名、消息長度、消息正文

標準答案：D

知識點解析：在消息傳遞系統(tǒng)中，進程間的數(shù)據(jù)交換是以消息（在計算機網(wǎng)絡中又

稱為報文）為單位的。消息的一般結(jié)構(gòu)形式有發(fā)送進程名、接收進程名、消息長

度、消息正文。故正確答案為選項D。

27、某計算機系統(tǒng)中內(nèi)存保護采用基址、限長寄存器的療法來實現(xiàn)，那么，判斷是

否越界的判別式是（）。

A、0W被訪問的邏輯地讓（限長寄存器的內(nèi)容

B、0S被訪問的邏輯地址S限長寄存器的內(nèi)容

C、0W被訪問的物理地址＜限長寄存器的內(nèi)容

D、0W被訪問的物理地址W限長寄存器的內(nèi)容

標準答案：A

知識點解析：本題考查存儲保護的方法?？疾榛?、限長寄存器方式下是如何進行

越界判斷的。在基址、限長寄存器的保護方式下，系統(tǒng)為每個并發(fā)進程設置一個基

址寄存器和一個限長寄存器，限長寄存器保存的是進程的長度，所以有關(guān)系式：邏

輯地址〈進程長度。在此注意，地址一般是從0開始，故需要包含。一般，對于長

度為100的區(qū)域，地址為從0?99。因此選A。

28、在某個計算機系統(tǒng)中，內(nèi)存的分配采用按需調(diào)頁的方式，測得當前CPU的利

用率為8%,硬盤交換空間的利用率為55%,硬盤的繁忙率為97%,其它設備的

利用率可以忽略不計，由此斷定系統(tǒng)發(fā)生異常，此異?？赡軙牵ǎ?，解決辦法是

（）oI.Bclady現(xiàn)象；H.抖動；IH.死鎖；W.饑餓；V.加大交換空間容

量；VI.增加內(nèi)存容量；VD.增加CPU數(shù)量；VID.增加并發(fā)進程數(shù)；

A、I和V

B、II和VI

C、HI和皿

D、W和皿

標準答案：B

知識點解析：本題考查按需調(diào)頁下提高系統(tǒng)效率的措施。首先判斷系統(tǒng)異常是屬于

什么異常，從測試數(shù)據(jù)看，CPU不忙，交換空問也不滿，就是硬盤的10非常繁

忙，所以不是交換空間不夠，系統(tǒng)也沒有死鎖，主要瓶頸在內(nèi)外存交換上，因此可

能的最大情況就是抖動，即由于內(nèi)存緊缺，并發(fā)進程數(shù)多，采用按需調(diào)頁而引起的

頻繁的換入換出作業(yè)。對于抖動問題的解決，最好的辦法是增加內(nèi)存，或減少并發(fā)

進程數(shù)，單純地增大交於分區(qū)的大小或增加CPU數(shù)量或提高CPU處理能力都沒有

解決根本問題。

29、若用100個雙字（字長32位）組成的位示圖管理內(nèi)存，假定用戶歸還一個塊號

為240的內(nèi)存塊時，它對應的位示圖的位置是（）。

A、字號為6,位號為16

B、字號為7,位號為16

C、字號為6,位號為14

D、字號為7,位號為14

標準答案：B

知識點解析：位示圖也禰為示位圖，是利用二進制的一位來表示內(nèi)存或磁盤中一個

存儲塊的使用情況。當其值為“0”時，表示對應的塊空閑；為“1”時，表示己分配。

反之亦然。內(nèi)存或磁盤上的所有塊都有一個二進制位與之對應，這樣，由所有塊所

對應的位構(gòu)成一個集合，稱為位示圖。計算方法：字號i=INT（240/32）=7字內(nèi)

位置j=MOD（240/32）=16

30、通常對文件系統(tǒng)來說，文件名和文件屬性可以找到的地方是（）。

A、目錄

B、索引

C、字典

D、作業(yè)控制塊

標準答案：A

知識點解析：在文件系統(tǒng)中，為每個文件建立一個目錄（或稱文件目錄或目錄項），

文件目錄記錄文件的名字，文件長度和文件存放的外存地址以及文件屬性、文件創(chuàng)

建時間日期等信息。文件目錄在大部分文件系統(tǒng)中乂成為文件控制塊，即FCB。

31、為保證文件的安全，操作系統(tǒng)一般采用多種方式來保護文件。為防止未經(jīng)授權(quán)

對文件的訪問而造成的篡改或破壞，所采取的方法是（）。

A、訪問控制列表

B、轉(zhuǎn)儲備份

C、加密數(shù)據(jù)

D、口令保護

標準答案：A

知識點露析：本題考查的是文件的保護。系統(tǒng)中的文件有些是只能由文件擁有者使

用，有些是可以共享的，獨享的文件需要采取保護措施，防止非法用戶存取文件。

保護文件的方法可以有多種，定時轉(zhuǎn)儲備份可以防止設備故障造成的文件損壞，U

令保護和加密數(shù)據(jù)可以保護文件被非法竊取時不會泄密，而對于授權(quán)用戶的使用，

一般采用訪問控制列表來對文件的權(quán)限進行分配，從而保證文件的安全。

32、CPU輸出數(shù)據(jù)的速度遠遠高于打印機的打印速度，為解決這一矛盾，可采用

的技術(shù)是（）.

A、并行技術(shù)

B、通道技術(shù)

C、緩沖技術(shù)

D、虛存技術(shù)

標準答案：C

知識點解析：緩沖技術(shù)的引入主要解決cPu速度和外設速度不匹配的問題，它同時

減少了通道數(shù)量上的占用，提高了CPU、10和通道的并發(fā)性，減少了中斷的次

數(shù)，放寬了CPU對中斷響應的時間要求，例如打印、文件訪問，網(wǎng)絡收發(fā)等場

合.均要用到緩沖技術(shù).

33、在不同網(wǎng)絡節(jié)點的對等層之間通信需要的是（），

A、模塊接口

B、對等層協(xié)議

C、電信號

D、傳輸介質(zhì)

標準答案：B

知識點解析：本題考查計算機網(wǎng)絡體系結(jié)構(gòu)，注意對等層是指在計算機網(wǎng)絡協(xié)議層

次中，將數(shù)據(jù)直接傳遞給對方的任何兩個同樣的層次，因此對等層之間通信必須需

要對等層之間的協(xié)議，這里選項A是相鄰層之問通信所必需的，選項C和D屬于

物理層，答案是B。

34、關(guān)于數(shù)據(jù)交換，下列敘述不正確的是（）。

A、線路交換面向連接

B、分組交換比報文交換具有更好的網(wǎng)絡響應速度

C、報文交換無存儲轉(zhuǎn)發(fā)過程

D、分組交換有存儲轉(zhuǎn)發(fā)過程

標準答案：C

知識點解析：該題考查數(shù)據(jù)交換的原理，要明確報文是一份完整的信息，而分組是

報文分組的簡稱，乂叫信息包，將報文劃分為若干格式化信息單位作為網(wǎng)絡層的數(shù)

據(jù)傳輸單元。分組交換方式：將一份完整的報文劃分為若干組，每個分組獨立的從

源節(jié)點發(fā)送到目的節(jié)點，目的節(jié)點收到這些分組后，再組裝成源報文。其特點是化

整為零，即將完整的較長的報文劃分為較小的分組，以分組單位傳輸數(shù)據(jù)。優(yōu)點是

減少節(jié)點緩沖區(qū)容量，并有利于差錯控制。而存儲轉(zhuǎn)發(fā)是指每個節(jié)點均設有緩沖

區(qū)，分組到達某節(jié)點后，先存儲在緩沖區(qū)中，等待輸出鏈路空閑時在轉(zhuǎn)發(fā)到下一個

節(jié)點。本題中面向連接的只有線路交換，存儲轉(zhuǎn)發(fā)只有分組和報文，由于分組交

換的靈活性，使其具有更好的響應速度，因此答案是C。

35、當DHCP客戶計算機第一次啟動或初始化1P時，廣播發(fā)送給本地子網(wǎng)的消息

是()。

A、DHCPDISCOVER

B、DHCPREQUEST

C、DHCPOFFER

D、DHCPACK

標準答案：A

知識點解析：本題考查DHCP協(xié)議的工作原理，需要IP地址的主機在啟動時就向

DHCP服務器廣播發(fā)送發(fā)現(xiàn)報文(DHCPDISCOVER),這時該主機就成為DHCP客

戶。本地網(wǎng)絡上所有主機都能收到此廣播報文，但只有DHCP服務器才回答此廣

播報文。DHCP服務器先在其數(shù)據(jù)庫中查找該計算機的配置信息。若找到，則返回

找到的信息。若找不到，則從服務器的IP地址池(addresspool)中取一個地址分配

給該計算機。DHCP服務器的回答報文叫做提供報文(DHCPOFFER)?？蛻粲嬎銠C

初始化IP的時候，首先要查找DHCP服務器，因此要發(fā)送的消息是DHCP

DISCOVER,答案是A。

36、網(wǎng)絡由6個路由器互連而成，路由器之間的鏈路費用如下圖所示，從PC機到

服務器的最短路徑和通路費用是()。

A、1—3—6,7

1—>4—>5—>6?4

C、1—4—3-6,6

D、12—4—5—6,7

標準答案：B

知識點解析：本題考查鏈路狀態(tài)路由算法，將網(wǎng)絡看成連通圖。每條鏈路以其“費

用''為權(quán)值。通過Dijkstra最短路徑算法求出任意兩個節(jié)點之間的最短距離，本題

中，就是以PC機所連接的路由器1為根節(jié)點，計算到達其他網(wǎng)絡的最短路徑，也

就是費用最小的路徑，這樣可以直接從選項中得出答案，是B。

37、一個B類網(wǎng)絡的子網(wǎng)掩碼為255.255.252.0,則該B類網(wǎng)絡的主機數(shù)目是

()o

A、2046

B、1022

C、510

D、128

標準答案：D

知識點解析：本題考查IPv4字網(wǎng)劃分，首先明確B類網(wǎng)絡的掩碼是

255.255.0.0,而192的二進制是11111100,由此可知可劃分？6=64個子網(wǎng)，

每個子網(wǎng)的主機數(shù)為22—2=2,因此該B類網(wǎng)絡的主機數(shù)目是64x2=128,因此

答案是D。

38、在TCP報文段的報頭中，窗口字段的作用是

A、報頭中32bit字節(jié)的數(shù)量

B、說明對■方端口的數(shù)量

C、控制對方的發(fā)送流量

D、說明網(wǎng)絡的負荷能力

標準答案：C

知識點》析：本題考查TCP報文段的作用窗口大?。河糜诹髁靠刂?。表示在確認

了的字節(jié)之后還可以發(fā)送多少字節(jié)。窗口大小也允許為0,表示它已經(jīng)收到了包括

確認號減1在內(nèi)的所有數(shù)據(jù)段，但接收方急需暫停接受數(shù)據(jù)。對于窗口字段，占2

個字節(jié)，用來控制對方發(fā)送的數(shù)據(jù)量，并不能說明網(wǎng)絡的負荷能力，因此答案是

Co

39、關(guān)于以太網(wǎng)交換機，下面的論述中不正確的是()。

A、交換機工作在數(shù)據(jù)鏈路層

B、交換機的每個端口形成一個沖突域

C、交換機支持多端口同時收發(fā)數(shù)據(jù)

D、交換機是一種多端口中繼器

標準答案：D

知識點解析：本題考查交換機的工作原理和特性，交換機是工作與數(shù)據(jù)鏈路層的網(wǎng)

絡設備，每個端口是獨立的沖突域，交換機的交換結(jié)構(gòu)保證了多端口同時進行數(shù)據(jù)

交換，多端口的中繼器可以認為是集線器，其所有端口處于同一個沖突域內(nèi)，因此

答案為D。

40、一臺主機要解析www.abc.edu.cn的IP地址，如果這臺主機配置的域名服

務器為202.120.66.68,因特網(wǎng)頂級域名服務器為11.2.8.6,而存儲

WWW.abc.edu.cn與其IP地址對應關(guān)系的域名服務器為20的113.16.10,那

么這臺主機解析該域名通常首先查詢的服務器是（），

A、202.120.66.68域名服務器

B>11.2.8.6域名服務器

C、202.113.16.10域名服務器

D、不能確定，可從這三個域名服務器中任選一個

標準答案：A

知識點解析：本題考查域名解析的過程，一個主機發(fā)出DNS查詢報文時，這個查

詢報文首先被送往該主機的本地域名服務器。當本地域名服務器不能立即回答某個

主機的查詢時，該本地域名服務器就以DNS客戶的身份向某一根域名服務器查

詢。若根域名服務器也沒有該主機的信息時（但此時根域名服務器一定知道該主機

的授權(quán)域名服務器的IP地址），有兩種做法：（1）遞歸查詢：根域名服務器向該主

機的授權(quán)域名服務器發(fā)送DNS查詢報文，查詢結(jié)果再逐級返回給原主機；（2）遞歸

與迭代相結(jié)合的方法：取域名服務器把授權(quán)域名服務器的IP地址返回給本地域名

服務器，由本地域名服務器再去查詢。無論是遞歸方式，還是迭代方式，主機進

行域名解析的第一步都是向自己的本地域名服務器發(fā)起請求，因此答案為Ao

二、綜合應用題（本題共7題，每題7.0分，共7分0）

41、采用散列函數(shù)H（k）=3xkMOD13并用線性探測開放地址法處理沖突，在數(shù)列

地址空間［0..12］中對關(guān)鍵字序列22,41,53,46,30,13,1,67,51；（1）構(gòu)

造散列表（畫示意圖）：（2）裝填因子：（3）等概率情況下查找成功的平均查找長度：

⑷等概率情況卜查找失敗的平均查找長度。

標準答案：（1）各關(guān)鍵字的散列函數(shù)值如下：

下標0it1iS67S101112

key224153llI6751關(guān)?7225314167uSI

H(key)163803610111212111

⑵裝填因子=關(guān)鍵字總數(shù)/表長=9/13=0.7。（3）設查找成功在每個關(guān)鍵字上是

等概率的，則查找每個關(guān)鍵字的概率為1/9,各關(guān)鍵字的探查次數(shù)分別為：

所以有，ASLwcc=(l+1+1+2+1+2+1

+l+l）/9=ll/9o（4）設不成功的查找在每個地址上發(fā)生的概率相同，平均概率

關(guān)鍵字為例，若該關(guān)鍵字不在散列表中，需要將它與從位置3開始向后直至位置5

的關(guān)鍵字相比較，由于關(guān)鍵字5的關(guān)鍵字為空，所以不再向后比較，共比較3次，

其他的類推得到。所以有，ASLunsucc=（3+2+1+3+2+1+4+3+2+1+2+1+

4）/13=29/13o

知識點解析：用線性探測法解決沖突構(gòu)造散列表，并對查找性能進行分析，具體解

題步驟如上。

42、假設二叉樹采用二叉鏈表存儲結(jié)構(gòu)存儲，試設計一個算法，求出該二叉樹中第

一條最長的路徑長度以及此路徑上各結(jié)點的值。

標準答案：voidLongpath（BiTrccb,TElcmTypcpath[],intpathlcn,TElcmTypc

longpath[],intlongpalhlen）{inti；if（b==NULL）（if（pathlen-longpathlen）{//若

當前路徑更長，將路徑保存在longpath中for（i=pa【hlen—1；i>=0：i-----）

iongpath[i]=path[i]；longpathlen=pathlen；}}else{path[：pathlen]=b—>data；

//將當前結(jié)點放入路徑中palhlen++；//路徑長度增ILongpath（b—>.Ichii

d.pat.h,pathlen,longpath,longpathlen）；//遞歸掃描左子樹Longpath（b

—>rchild.pat.h,pathlen,longpath,longpathlen）；//遞歸掃描右子樹path]en

一一；//環(huán)境恢復}}

知識點解析：采用path數(shù)組保存掃描到當前結(jié)點的路徑，pathlen保存掃描到當前

結(jié)點的路徑長度，longpath數(shù)組保存最長的路徑，longpathlen保存最長路徑長度。

當b為空時，表示當前掃描的一個分支已掃描完畢，將pathlen與longpalhlen進行

比較，將較長路徑及路徑長度分別保存在longpath和longpathlen中。

43、某微機的尋址范圍為64KB,其存儲器選擇器信號為M,接有8片8KB的存

儲器，試完成下列問題。（1）畫出選片譯碼邏輯圖。（2）寫出每片RAM的尋址范

圍。（3）如果運行時發(fā)現(xiàn)不論往哪片存儲器存放8KB數(shù)據(jù)，以4000H起始地址的存

儲芯片都有與之相同的數(shù)據(jù)，分析故障原因。（4）如果運行時發(fā)現(xiàn)以0000H為起始

地址的一片存儲芯片不能讀寫，分析故障原因。（5）若發(fā)現(xiàn)譯碼器中的地址線A”

與CPU斷線，并搭接到低電平的故障，問后果如何？（6）如果發(fā)現(xiàn)只能對第1-4片

RAM進行讀寫，試分析故障原因。

LAl

1?小低言爰：也nm舊疼粗刈「因"小。-———匕（2）8片RAM的尋址

范圍分別是：0000H?IFFFH、2000H?3FFFH、4000H?5FFFH、6000H?

7FFFH、8000H?9FFFH、A000H?BFFFH、C000H?DFfFH和E000H?FFFFH。

⑶說明譯碼器有誤，兇輸出始終為低。因該輸出接至第3片RAM的

端，該片對應的地址范圍是4000H?5FFFH,故不淪往哪片RAM存放8K數(shù)據(jù)，

該存儲芯片始終被選中，所以都有與之相同的數(shù)據(jù)。（4）說明yO輸出始終為高。因

RAM的片選信號時低比平有效，故用作片選信號的存儲芯片（對應0000H?1FFFH

地址范圍）不能讀寫，而其他芯片可以讀寫。（5）若發(fā)現(xiàn)A］3與CPU斷線，并搭接

到低電平的故障，則信號均不可能輸出0,故第2、4、6、8片RAM始終不被選

中。（6）說明譯碼器的C輸入端始終為低，可以檢查一下A］5是否搭接到低電平

上。

知識點解析：（3）?（6）中出現(xiàn)的問題都是由于譯碼器連接上的問題（短路或斷路）造成

的，使得某些片選信號始終被選中或始終不被選中。［歸納總結(jié)］全譯碼法將除片內(nèi)

尋址外的全部高位地址線都作為地址譯碼器的輸入，譯碼器的輸出作為各芯片的片

選信號，將它們分別接到存儲芯片的片選端，以實現(xiàn)對存儲芯片的選擇。全譯碼法

的優(yōu)點是每片（或組）芯片的地址范圍是唯一確定的，而日.是連續(xù)的，也便于擴展，

不會產(chǎn)生地址重疊的存儲區(qū)。［解題技巧］首先確定片選電路以及各個芯片的地址分

配，然后分析各種出錯情況，分別找出出錯的原因。

44、某模型機的通路結(jié)溝如下圖所示，用寄存器傳送語句（如PC-MAR）,擬出下

列指令從讀取到執(zhí)行的完整流程。（1）數(shù)據(jù)傳送指令MOVX（Ro）,Y（Ri）,源和目

的操作數(shù)地址均采用變址尋址，第1個參數(shù)X為源操作數(shù)的形式地址，第2個參

數(shù)為目的操作數(shù)的形式地址，分別位于指令的第2個和第3個存儲字。（2）數(shù)據(jù)求

反指令COM—（Ro）,采用自減型寄存器間接尋址，結(jié)果送回自減后的地由E單

告耳禽］f一"?~~I-->1~K"""MDR

CRTD具禺

標準答案：（l）MOVX（Ro）,Y（R。①PC—MAR,Read；取指令②M—MDR—IR

③PC+ITPC④PCTMAR,Read；取源操作數(shù)形式地址&M—MDR—C@PC

+1-PC⑦C+Ro—MAR,Read；形成源操作數(shù)有效地址，并取源操作數(shù)

⑧M—MDR—C；源操作數(shù)暫存C中⑨PC—MAR,Read；取目的操作數(shù)形式地

址⑩MTMDR—D⑩PC+1-PC⑩D+Ri-MAR；形成目的操作數(shù)有效地址

⑩C-MDR；將源操作數(shù)送存儲器數(shù)據(jù)寄存器⑩MDR-M,write；將源操作數(shù)

寫入目的有效地址中（2jCOM-（Ro）①PC—MAR,Read；取指令

②M—MDR—IR③PC+1-PC④Ro-l-Ro，RO-1->MAR,Read；修改Ro的

內(nèi)容（源和0的操作數(shù)地址）⑤M-MDR—D；取出源操作數(shù)⑥D(zhuǎn)—MDR；將源操

作數(shù)取反⑦MDR—M,write；寫入目的地址中

知識點解析：數(shù)據(jù)傳送指令占3個字，第1個字是操作碼和寄存器編號；第2個字

是參數(shù)X,為源操作數(shù)的形式地址；第3個字是參數(shù)Y,為目的操作數(shù)的形式地

址，源和目的操作數(shù)地址均采用變址尋址，指令的含義是：（（Ro）+X）一（RD+Y。

求反指令僅占1個字，自減型寄存器尋址是先修改寄存器的內(nèi)容（一1）,再取數(shù)。

［歸納總結(jié)］（l）MOVX（Ro）,Y（R］）指令執(zhí)行流程中的前3步是完成取指令的操作公

操作；接下來的5步是去主存中取源操作數(shù)，把取出的數(shù)放在暫存器C中；然后

的4步是形成目的操作數(shù)地址；最后2步完成傳送操作。(2)COM-(Ro)指令執(zhí)行

流程中的前3步是取指令公操作；接下來的2步是去主存中取源操作數(shù)，把取出的

數(shù)放在暫存器D中；然后將D的內(nèi)容取反，寫入目的地址中。［解題技巧］根據(jù)數(shù)

據(jù)通路，寫出指令執(zhí)行的微操作序列。使用寄存器傳送語句(如PC-MAR),比較

直觀。

45、某工廠有一個倉庫可以存放甲、乙兩種零部件，甲零件可以存放m件，乙零

件可以存放n件，車間A專門生產(chǎn)甲零件，每次1件，每生產(chǎn)1件存放進倉庫1

件；車間B專門生產(chǎn)零件乙，每次1件，每生產(chǎn)1件存放進倉庫1件?？傃b車間每

次從倉庫取出2件甲零件、1件乙零件組裝成成品，車間A、B和總裝車間必須互

斥進入倉庫。當倉庫內(nèi)甲、乙零件分別達到m、n件時，車間A、B分別停止生

產(chǎn)。而倉庫內(nèi)任何一種零件為。時，總裝車間停產(chǎn)。根據(jù)上述規(guī)則，請利用信號量

機制，沒計一個可以讓車間A、B和總裝車間協(xié)調(diào)運轉(zhuǎn)的程序，并說明各個信號量

的意義，用類c語言寫出整個過程。

標準答案：設信號量mutex用于車間的互斥,positionA>positionBpartA,partB

為資源信號量，分別表示倉庫中零件甲、乙的空位數(shù)和滿位數(shù)，positionA+partA

=m；positionB4-partB=n；編程如下：deftypeintsem叩hore；//定義信號量

semaphoremutex=l；//進入倉庫的互斥信號量semaphorepositionA=m,

positionB=n；//車間A、B生產(chǎn)的零件甲、乙存放的位置semaphorepartA=

0,partB=0；//零件甲、乙的信號量voidworkshopA()//車間A進程

｛while(TRUE)//并發(fā)調(diào)度｛intitem；//倉庫貨架指針item=produce(甲)：/

/生產(chǎn)零件甲P(positior.A)；//查有無零件甲的貨位P(mutex)；//倉庫可以進

入嗎？puton(item)；//放置零件甲V(mutex)；//釋放倉庫互斥量V(partA)；

//增加零件甲的資源信號量｝//離開｝voidworkshopB()//車間B進程

｛while(TRUE)//并發(fā)調(diào)度(intitem；//倉庫貨架指針item=produce(乙):/

/生產(chǎn)零件乙P(positionB)；//查有無零件乙的貨位P(mutex)；//倉庫可以進

入嗎？puton(itcm)；//放置零件乙V(mutex)；//釋放倉庫互斥量V(panB)；

//增加零件乙的資源信號量)//離開)voidassembleshop()//總裝車間進程

(while(TR