計算機專業（基礎綜合）模擬試卷28

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

1、若一個棧的輸入序列為1,2,3…n,輸出序列的第一個元素是i,則第j個輸

出元素是（）。

A、i—j—]

B、i—j

C、j—i+1

D、不確定

標準答案：D

知識點解析：一串數據依次通過一個棧，并不能保證出棧數據的次序總是倒置，可

以產生多種出棧序列。一串數據通過一個棧后的次序由每個數據之間的進棧、出棧

操作序列決定，只有當所有數據“全部進棧后再全部出棧”才能使數據倒置事實

上，存在一種操作序列—“進棧、出棧、進棧、出棧……”—可以使數據通過棧

后仍然保持次序不變。題目中輸出序列的第一個元素是i,則第j個輸出元素是不

確定的。

2、若循環隊列以數組Q[0..m—1]作為其存儲結構，變量rear表示循環隊列中

的隊尾元素的實際位置，其移動按rear=（rear+l）MODm進行，變量length表示

當前循環隊列中的元素個數，則循環隊列的隊首元素的實際位置是（）。

A^rear-length

B、(rear—lengh+m)MODm

C、(1+rear+m—length)MODm

D、m一length

標準答案：C

知識點解析：按照循環隊列的定義，因為元素移動按照rear=（rear+l）MODm進

行，則當數組Q[m=l]存放了元素之后，下一個入隊的元素將存放到Q[0]中，因

此隊列的首元素的實際位置是（rear—length+1+m）MODm。

3、已知有一維數組A[0..m*n—1],若要對應為m行、n列的矩陣，將元素

A[k]（0<k

A、i=k/n,j=k%m

B、i=k/in*i—k%m

C、i=k/n,j=k%n

D、i=k/m,j=k%n

標準答案：C

知識點解析：本題是求一維數組向二維數組轉化的問題。最簡單的方法是把數組A

的第。?n—1共n個元素放到數組B的第一行，數組A的第n?2n—1共n個元素

放到數組B的第二行中，依次類推，數組A的最后n個元素放到數組B的最后一

行中。求A［k］在數組B中的位置，應先確定A［k］處在哪一行，顯然應該是k/n

行；然后再確定處在k/n行的哪一列，顯然是k%n。

4、由元素序列（27,16,75,38,51）構造平衡二叉樹,，則首次出現的最小不平衡

子樹的根（即離插入結點最近且平衡因子的絕對值為2的結點）是（）。

A、27

B、38

C、51

D、75

標準答案：D

知識點解析：二叉排序樹的構造方法如下：每讀入一個數據，建立一個新結點，若

二叉排序樹為空，則新結點為二叉排序樹的根結點；若二叉排序樹非空，則新結點

的值和根結點比較，若小于根結點，則插入左子樹；否則插入右子樹。結點的平衡

因子是指結點的左子樹的深度減去它的右子樹的深度。由數據（27,16,75,38,

51）構造平衡二義樹，插入51后首次出現不平衡子樹，易知最小不平衡子樹的結點

為75。

5、設結點x和y是二叉樹中任意的兩個結點，在該二叉樹的先序遍歷序列中x在

y之前，而在其后序遍歷序列中x在y之后，則x和y的關系是（）。

A、x是y的左兄弟

B、x是y的右兄弟

C、x是y的祖先

D、x是y的后裔

標準答案：C

知識點解析：由于先序遍歷是“根…左子樹一一右子樹”，而后序遍歷是“左子樹——

-右子樹——根”，題目中二叉樹的先序遍歷序列中x在y之前，而在其后序遍歷

序列中x在y之后，則x一定是y的祖先。［歸納總結］假設M、N分別是一棵二叉

樹中的兩個結點，關于各個結點的關系如下：

先序i!歷時、?M*，中用■歷內、A

M的左力11I

NA000

、扯M齡機先10

Nftf#00表中力”、“0”或“（P”分

別表示肯定、恰恰相反或者不一定。注：如果⑴離a和b最近的共同祖先p存

在，且（2）a在p的左子樹中，b在p的右子樹中，則稱a在b的左方（即b在a的右

方）。

6、在一棵完全二叉樹中，其根的序號為1,下列可判定序號為p和q的兩個結點

是否在同一層的正確選預是（）。

A、[log2p]=[logaq]

B、log2p=log2q

C>[log2p]+I=[log2q]

[log2p]=[logaq]+1

標準答案：A

知識點解析：由完全二叉樹的性質可知，在一棵完全二叉樹第h（l侖1）層上的結點p

和q,它們序號范圍應是2l「kp,因此有[log2p]=[log2]成立。

7、若G是一個具有36條邊的非連通無向圖（不含自回路和多重邊），則圖G的結點

數至少是（）。

A、II

B、10

C、9

D、8

標準答案：B

知識點解析：n個結點的無向圖中，邊數egn（n—1）/2,將e=36代入，有位9,

現已知無向圖非連通,則n=10。

8、有一個長度為12的有序表，按折半查找法對該表進行查找，在表內各元素等概

率情況下，查找成功所需的平均比較次數是（）。

A、37/12

B、35/12

C、39/12

D、43/12

標準答案：A

知識點解析：長度為12的折半查找判定樹如下圖所示，判定樹中有12個內結點。

ASL=gP.?C

I

一(1X20+2X2,+…+kX2'')/n

平均查找長度為:=(IX14-2X2+3X4+4X5)/12-37/12

9、設有一個含200個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找

到一個表項的平均探查次數不超過1.5,則散列表項應能夠至少容納的表項的數

目是（）。

A、400

B、526

C、624

D、676

標準答案：A

知識點解析：設線性探測法查找成功的平均查找長度為SN={1+1/(I—a)}/2,

其中a為裝填因子。因比算得a=0.5,最小表項數為200/0.5=400。

10、對于序列(49,38,65,97,76,13,27,50)按由小到大進行排序，初始步長

d=4的希爾排序法第一趟的結果的是()。

A、49,76,65,13,27,50,97,38

B、13,27,38,49,50,65,76,97

C、97,76,65,50,49,38,27,13

D、49,13,27,50,76,38,65,97

標準答案：D

知識點解析：本題根據希爾排序法的算法思想進行手工排序，可得答案為D。

11、堆排序分為兩個階段，其中第一階段將給定的序列建成一個堆，第二階段逐次

輸出堆頂元素。設給定序列{48,62,35,77,55,14,35,98},若在堆排序的第

一階段將該序列建成一個堆(大根堆)，那么交換元素的次數為()。

A、5

B、6

C、7

D、8

標準答案：B

知識點解析：序列{48,62,35,77,55,14,35.98}建立初始堆的過程如下圖所

(d)調整結點48,交換3次。所以上述序列建初始堆，共交換元素6次。

12、若存儲周期100納秒，每次讀出一個字節，則該存儲：器的數據傳輸率為()。

A、32x1()6位/秒

B、8xl()6位/秒

C、80Mb/秒

D、80xl（）6位/秒

標準答案：D

知識點解析：由于存儲周期100ns,每次讀出一個字節，則數據傳輸率=8/

（100*1。—9）=80*］（）6位/秒。選項c的錯誤在于存在誤差，1M=1O24*1O24。［歸

納總結］主存的數據傳輸率表示每秒從主存進出信息的最大數量，單位為字/秒或

字節/秒。

13、馮?諾依曼機工作方式的基本特點是（）。

A、存儲器內容選擇地址

B、采用多指令流單數據流

C、堆棧操作

D、按地址訪問并按順序執行指令

標準答案：D

知識點解析：馮.諾依曼機工作方式的基本特點就是程序事先存放在存儲器中，存

儲器按地址訪問，逐條地取出指令來執行。［歸納總結］存儲程序概念的基本含義是

將編好的程序和原始數據事先存入存儲器中，然后再啟動計算機工作。

14、字長相同的兩種浮點數，第一種階碼位數多，尾數位數少，第二種階碼位數

少，尾數位數多，階的底數都是2,則有（）。

A、它們表示的數的范圍與精度相同

B、第一種數的范圍大，但精度低

C、第二種數的范圍大，精度高

D、第一種數的范圍大，精度高

標準答案：B

知識點解析：字長相同的兩種浮點數，階碼位數較多表示的數范圍越大，尾數越多

表示的精度越高。［歸綱總結|所謂精度是指一個數所含有效數值位的位數，機器字

長越長精度就越高。對于字長相1可的浮點數來說，階碼位數多，就意味著尾數位數

少，數的表示范圍增大正是以降低精度為代價的。

15、以下關于校驗碼的敘述中，正確的是（）。I.校驗碼的碼距必須大于2口.校

驗碼的碼距越大檢錯糾錯能力越強n.增加奇偶校驗位的位數可以提高奇偶校驗

的正確性W.采用奇偶校驗可檢測出一位數據錯誤的位置并加以糾正V.采用海

明校驗可檢測出一位數據錯誤的位置并加以糾正VI.循環冗余校驗碼是通過除法

運算來建立數據和校驗位之間的約定關系的

A、I、m、v

R、II、TV.VI

C、I、V、VI

D、口、V、VI

標準答案：D

知識點解析：碼距22的數據校驗碼，開始具有檢錯的能力。碼距越大，檢、糾錯

能力就越強；奇偶校驗碼的碼距等于2,可以檢測出一位錯誤(：或奇數位錯誤)，

但不能確定出錯的位置，也不能檢測出偶數位錯誤；海明碼的碼距大于2,不僅可

以發現錯誤，還能指出錯誤的位置，為自動糾錯提供了依據；循環冗余校驗碼則通

過除法運算來建立數據和校驗位之間的約定關系。［歸納總結］數據校驗碼是指那些

能夠發現錯誤或能夠自動糾正錯誤的數據編碼，又稱之為“檢錯糾錯編碼任何一

種編碼都由許多碼字構成，任意兩個碼字之間最少變化的二進制位數，被稱為數據

校驗碼的碼距。具有檢、糾錯能力的數據校驗碼的實現原理是：在編碼中，除去

合法的碼字外，再加進一些非法的碼字，當某個合法碼字出現錯誤時，就變成為非

法碼字。合理地安排非法碼字的數量和編碼規則，就能達到糾錯的目的。

16、若內存地址區間為4000H?43FFH,每個存貯單元可存儲16位二進制數，該

內存區域用4片存儲器芯片構成，則構成該內存所用的存儲器芯片的容量是()。

A、5l2xl6bit

B、256x8bit

C、256x16bit

D、1024x8bit

標準答案：C

知識點解析：43FF-4000+1-400,即內存區域為1K個單元，總容量為1KX16。

現有4片存儲芯片構成，則芯片容量為256xl6bil。［歸納總結］根據總容量和芯片

總容量

數，由于總片數=而再所以可以計算出芯片容量。［解題技巧］已知總容量和選

定存儲芯片的容量，可以計算出總芯片數；現在已知總容量和總片數，也可以計算

出芯片的容量。

17、數據尋址和指令尋址的不同點在于()。

A、前者決定操作數地址，后者決定程序轉移地址

B、前者決定程序轉移地址，后者決定操作數地址

C、前者是短指令，后者是長指令

D、前者是長指令，后者是短指令

標準答案：A

知識點解析：數據尋址尋找的是操作數的地址，指令尋址尋找的是下條指令的地

址，它決定于程序轉移地址。［歸納總結］尋址可以分為指令尋址和數據尋址。尋找

下一條將要執行的指令地址稱為指令尋址，尋找操作數的地址稱為數據尋址。指令

尋址比較簡單，它又可以細分為順序尋址和跳躍尋址。而數據尋址方式種類較多，

其最終目的都是尋找所需要的操作數。［解題技巧］數據尋址和指令尋址只與尋找的

地址類型有關，而與指令的長度無關。

18、流水計算機中，下列語句發生的數據相關類型是()。ADDRI,R2,R3；(R2)

+(R3)-R1ADDR4,RI,R5；(R1)+(R5)->R4

A、寫后讀

B、讀后寫

C、寫后寫

D、讀后讀

標準答案：A

知識點解析：|歸納總結］流水線中的相關是指相鄰或相近的兩條指令因存在某種關

聯，后一條指令不能按照原指定的時鐘周期運行，使流水線斷流。指令流水線的相

關性包括結構相關、數據相關、控制相關。結構相關也稱資源相關，是指由于多條

指令在同一時刻爭用同一資源而形成的沖突。數據相關是指后續指令要使用前面指

令的操作結果，而這一結果尚未產生或者未送到指定的位置，從而造成后續指令無

法運行的局面。控制相關又稱為指令相關，主要是由轉移指令引起的，在遇到條件

轉移指令時，存在著是順序執行還是轉移執行兩種可能，需要依據條件的判斷結果

來選擇其一。數據相關又可分為RWW（寫后讀）、WAR（讀后寫）和WAW（寫后寫）3

種類型。例如有i和j兩條指令，i指令在前，j指令在后，則3種不同類型的數據

相關的含義為：？RAW：指令j試圖在指令i寫入寄存器前就讀出該寄存器內容，

這樣指令j就會錯誤地讀出該寄存器舊的內容。?WAR：指令j試圖在指令i讀出

該寄存器前就寫入該寄存器，這樣指令i就會錯誤地讀出該寄存器的新內

容。？WAW：指令j試圖在指令i寫入寄存器前就寫入該寄存器，這樣兩次寫的先

后次序被顛倒，就會錯誤地使由指令i寫入的值成為該寄存器的內容。寫后讀相關

（RAW）、寫后寫相關（WAW）、讀后寫相關（WAR）。在這兩條指令中，都對RI進行

操作，其中前面對R1寫操作，后面對R1讀操作，因此發生寫后讀相關。

19、下列有關控制器的說法正確的是（）。

A、無論是組合邏輯控制器和時序邏輯控制器，都需要有程序計數器

B、微程序控制器不需耍程序計數器，只要有微程序計數器

C、都可以不需要程序計數器

D、以上都不對

標準答案：A

知識點解析?：無論控制器的硬件實現方法有何不同，都有需要程序計數器。對于微

程序控制器可能同時還有微程序計數器，這兩者并不矛盾。［歸納總結］程序計數器

PC用來存放當前正在執行指令的地址或下一條將要執行指令的地址，它是CPU的

專用寄存器之一。

20、下面是關于目前流行的PC機主板的敘述：I.主板上通常包含微處理器插座

（或插槽）和芯片組口.主板上通常包含ROMBIOS和存儲器（內存條）插座ID.主

板上通常包含PCI和AGP總線插槽IV.主板上通常包含IDE連接將其中正確的

是（）。

A、僅I

B、僅I和口

c、僅I、n和m

D、I、口、in和w

標準答案：D

知識點解析：關于PC機主板的四個描述都是正確的。［歸納總結］PC機主板上應

包含微處理器插座和芯片組、ROMBIOS芯片和內存條插座、PCI和AGP總線插

槽和IDE連接器等。

21、當圖像分辨率為800X600,屏幕分辨率為640X480時，正確的是（）。

A、屏幕上顯示一幅圖像的64%左右

B、圖像正好占滿屏幕

C、屏幕上顯示一幅完整的圖像

D、圖像只占屏幕的一部分

標準答案：A

知識點解析：屏幕分辨率的行、列像素數分別是圖像分辨率的80%,所以屏幕上

只能顯示這幅圖像的64%。［歸納總結］當圖像分辨率大于屏幕分辨率時，屏幕上

只能顯示圖像的部分內容。［解題技巧］由于圖像分辨率與屏幕分辨率不同，所以可

以排除掉選項B和C,而選項D是圖像分辨率小于屏幕分辨率情況。

22、外部設備打印機適合于連接的通道是（）。

A、數組多路通道

B、字節多路通道

C,選擇通道

D、任意一種通道

標準答案：B

知識點解析：打印設備屬于低速設備，它適合于連接到字節多路通道上，一個字節

多路通道上運行連接多臺相同或不相同的低速設備，當通道為一個設備傳送完一個

字節后，就轉去為另一個設備服務。［歸納總結］通道有3種類型：字節多路通道、

選擇通道和數組多路通道。字節多路通道是一種簡單的共享通道，用于連接與管理

多臺低速沒備，以字節交叉方式傳送信息。選擇通道又稱高速通道，在物理上它也

可以連接多個設備，但這些設備不能同時工作，在一段時間內通道只能選擇一臺設

備進行數據傳送.此時該設備可以獨占整個通道°數組多路通道是把字節多路通道

和選擇通道的特點結合起來的一種通道結構。它的基本思想是：當某設備進行數據

傳送時，通道只為該設備服務；當設備在執行輔助操作時，通道暫時斷開與這個設

備的連接，掛起該設備的通道程序，去為其他設備服務。

23、在不同類型的操作系統中，批處理操作系統的主要缺點是（）。

A、CPU利用率低

B、不能并發執行

C、缺少交互性

D、周轉時間太長

標準答案：C

知識點解析：操作系統主要分為三種類型，批處理系統、交互式系統和實時系統。

批處理系統的設計其目標是加大吞吐量，減少周轉時間。為達到此目的，系統一般

要盡可能地提高CPU利用率，并采用多道并發程序設計，而與用戶的交互不在其

考慮范圍之內，此問題交由交互式操作系統來解決。

24、下列所示不是信號量能實現的功能是()。

A、進程同步

B、進程互斥

C、執行的前趨關系

D、進程的并發執行

標準答案：D

知識點解析：本題考查信號量的功能，在多道程序技術系統中，信號量機制是一種

有效的實現進程同步與互斥的工具。信號量可以實現的功能有：進程的同步與互

斥，進程執行的前趨關系，進程執行的前趨關系實質上是指進程的同步關系。除此

以外，只有進程的并發執行不需要信號量來控制，因此正確答案為D。

25、下面是一個并發進程的程序代碼，正確的說法是()。semaphorexl=x2=y=

i；intcl=c2=0：cobeginprocedurePlprocedureP2P(xl)；P(x2)；if(++cl=

l)P(y)；if(++c2=l)P(y)；V(xl)；V(x2)；computer(A)；computer(B)；P(xl)；

P(x2)；if(-----cl=0)V(v)；if(-----c2=0)V(y)；V(xl)；V(x2)；endendcoend

A、進程不會死鎖，也未會饑餓

B、進程不會死鎖，但是會饑餓

C、進程會死鎖，但是不會饑餓

D、進程會死鎖，也會饑餓

標準答案：B

知識點解析?：本題考查PV操作與死鎖以及饑餓的關系。仔細考察程序代碼，我們

似曾相識，可以看出是一個擴展的單行線的問題。也就是說，某單行線只允許單方

向的車輛通過，在單行線的入口設置信號量y,在告示牌上顯示某一時刻各方向來

車的數量cl和c2,要修改告示牌上的車輛數量必須互斥進行，為此設置信號量xl

和x2。若某方向的車輛需要通過時，首先要將該方向來車數量cl或c2增加1,并

查看自己是否是第一個進入單行線的車輛，若是，則獲取單行線的信號量y,進入

單行線。通過此路段以后出單行線時，將該方向的車輛數cl或c2減1(當然是利用

xl或x2來互斥修改)，并察看自己是否是最后一輛車，若是，則釋放單行線的互斥

量y,否則，保留信號置y,讓后繼車輛繼續通過。雙方的操作如出一轍。考慮出

現一個極端情況，即當某方向的車輛首先占據單行線并后來者絡繹不絕時，另一個

方向的車輛就再沒有機會通過該單行線了。從而造成饑餓。由于有信號量的控制，

死鎖的可能性沒有了(即雙方同時進入單行線，在中間相遇，造成雙方均無法通過

的情景)。

26、在操作系統中，要對并發進程進行同步的原因是()。

A、進程的有限時間性

B、進程具有動態性

C、并發進程推進的不確定性

D、進程具有結構性

標準答案：C

知識點解析：進程同步是指多個相關進程在執行次序上的協調。這些進程會互相競

爭以及相互合作，在一些關鍵點上可能需要前后順序操作。由于并發造成系統的不

確定性，運行中不知誰先誰后，因此當二個進程需要協調時必須互相等待或者互通

消息。由于不確定性，造成并發執行的進程在執行次序上本身無規律可循，因此需

要系統對這些相關進程進行同步。由此，正確答案應為C。

27、操作系統中為實現多道程序并發，對內存管理可以有多種方式，其中代價最小

的是（）。

A、分區管理

B、分頁管理

C、分段管理

D、段頁式管理

標準答案：A

知識點解析：本題考查實現各種存儲管理的方法。為實現多道出現并發，系統必須

將多個程序調入內存，讓多個進程競爭CPU和外設，使得計算機能高效地運轉。

多個程序調入內存會存在越界，溢出等多種問題。為解決這些問題，存儲管理采用

了分區法，分頁法，分段法和段頁式等多種技術，而實現分頁、分段和段頁式存儲

管理都需要特殊的硬件支持（例如帶地址加法器的CPU等），因而代價較高。分區

存儲是實現多道程序并發的最簡單易行而又代價最低的方法，這種方法特別適合嵌

入式系統或移動設備的操作系統中實現多道并發。

28、在一個請求頁式的虛擬存儲系統中，每個頁面的大小分為4096字節。如下某

個程序需要將數組賦值，假設，執行代碼已經駐留內存，而數據頁面尚未分配，數

組按先行后列存放。請計算，其缺頁中斷次數是（），inta[1024][1024]：inti,j；i

=0：for（j=0；j<=1023；j++）a[i][j]=j；

A、2

B、1

C、1024

D、512

標準答案：D

知識點解析：本題考查對C語言程序在使用內存時的分配機制。采用請求頁式虛

擬存儲管理的基本點的是按需分配內存，僅當使用到該頁時才通過缺頁中斷分配內

存。C語言對數組的存放是先行后列的，整型數組每個占用2個字節，據此，我們

可以計算，4096字節可以存放2行數組，由于程序中并非按行賦值，而是按列賦

值，所以一頁只賦值2個數組（是跳躍地賦值），若每申請一頁產生1次缺頁中斷，

那么總共要產生1024/2=512次缺頁中斷。

29、在頁式存儲管理系統中選擇頁面的大小，需要考慮的因素是（）。I.頁面大的

好處是頁表較小n.頁面小的好處是可以減少由內碎片引起的內存浪費in.通

常，影響磁盤訪問時間的主要因素不在于頁面的大小，所以使用時可優先考慮較大

的頁面

A、I和m

B、n和m

c、i和n

D、i和n和！ii

標準答案：c

知識點解析?：在確定地址結構時，若選擇的頁面較小，一方面可使內碎片減小，從

而減少了內碎片的總空間、有利于提高內存利用。但另一方面，也會使每個進程要

求較多的頁面，從而導致頁表過長，占用大量內存。此外，還會降低頁面換進換出

的效率。若選擇的頁面較大，雖然可減少頁表長度，提高換進換出效率，但卻又會

使內碎片增大。因此。頁面的大小應選得適中，通常頁面的大小是2的累，即在

512B?4096B之間。頁面大小與磁盤調度的關系不大，磁盤調度與扇區有關。故

正確答案為C。

30、磁臂驅動調度算法中，能夠隨時改變磁頭運動方向的算法是（）。

A、電梯調度算法

B、掃描算法

C、循環察看算法

D、最短尋道距離優先算法

標準答案：D

知識點解析：本題考查磁臂調度算法。了解每一種磁臂調度算法后對該題就應該有

比較清晰的認識，例如，最短尋道時間優先算法是找離得最近的磁道去服務，那么

它隨時會改變方向；而電梯調度算法在一次單向運動過程中服務所有經過的磁道的

請求，直到該方向沒有夠道需要訪問了才改變方向，到達另一個方向的最遠的需要

服務的磁道后再返回；掃描調度算法非常類似電梯調度算法，區別是掃描算法不管

有沒有用戶請求訪問磁道，均會移到磁道兩端的終點。循環察看是電梯調度算法的

改進，它只進行單向服務，到最遠端的服務磁道結束后立即返回另一端的第一個需

要服務的磁道，返程途中不尋道，以保證對不同分相磁道的訪問具有公平性。

31、有一個文件含有10000個文件塊，若將其順序結構存放，則對文件塊順序查找

的平均時間為5000個單位。若按索引順序文件的結構存放，每個索引為100個文

件塊,則順序查找次數是（）。

A、500

B、100

C、50

D、10

標準答案：B

知識點解析：木題考查的是文件的邏輯結構。順序文件在按順序查找文件內容時，

必須按順序一個一個去讀取，最快在第一個就讀取到，最慢一直讀到最后一個文件

塊，所以平均為一半，計算結果是10000:2=5000。（若采用二分法不會有這么多

次）。當采用索引順序文件時，文件的內容已經按照索引的關鍵詞排好了序（例如按

字母順序等）。并建立了索引表，索引表一般將一定數量的文件塊組織成一組，本

題中以100個一組，所以分成10000700=100組，按順序查找法，查找這100組

平均需要100：2=50次，找到以后在組內繼續查找，平均需要100:2=50次，所以

共需要50+50=100次。

32、計算機系統中，不屬于DMA控制器的是（）。

A、命令/狀態寄存器

B、內存地址寄存器

C、數據寄存器

D、堆棧指針寄存器

標準答案：D

知識點解析：本題考查10設備中DMA設備的組成。DMA設備與CPU有三類信

號線：數據線、地址線和控制線。一般要DMA設備工作，必須有命令/狀態寄存

器，這個寄存器控制DMA的工作模式并反映給CPU它當前的狀態，地址寄存器

存放DMA作業時的源地址和目標地址，數據寄存器存放要DMA轉移的數據，只

有堆棧指針寄存器不需要在DMA控制器中存放。堆棧一般在計算機內存中開辟有

統一的區域。

33、在協議數據單元中，控制信息所不包括的內容是（）。

A、地址

B、查錯碼

C、數據

D、協議控制

標準答案：C

知識點解析：本題考查協議的基本概念，為保證網絡中的計算機之間有條不紊的進

行數據交換，合理的共享資源，各獨立的計算機系統必須嚴格的遵循事先約定好的

一套套的通信規程，包括嚴格規定要交換的數據形式。控制信息的格式和控制功

能，以及通信過程中事件執行的次序等，這里地址、查錯碼和協議控制都是控制信

息必須包括的，但具體的數據是由上層協議所決定，因此答案是C。

34、通過改變載波信號的相位值來表示數字信號1、。的方法是（）。

A、ASK

R、FSK

C、PSK

D、PPP

標準答案：C

知識點解析：本題考查數字調制的基本概念，使用某個頻率的正弦載波，使其的振

幅、頻率或相位隨著數字信號的變化而變化，稱為調制；相反的過程稱為解調；數

字調制具有三種基木形式即移幅鍵控法ASK、移頻鍵控法FSK和移相鍵控法

PSK。在ASK方式下，用載波的兩種不同幅度來表示二進制的兩種狀態。在FSK

方式下，用載波頻率附近的兩種不同頻率來表示二進制的兩種狀態。在PSK方式

下，用載波信號相位移動來表示數據。因此答案為C。

35、假設一個NAT服務器其公網地址為205.56.79.35,并且有如下的表項，

皿"當一小TP1Q91___________……--------------入公網的時候，轉換后

?IPMMV4II

M56192.Ue.32,S421

M5?192.IM.32,M20

1892192.IM.48.M

nss192.IM.55.1Mao

的端口號和源IP地址是()。

A、205.56.79.35：2056

B、192.168.32.56：2056

C、205.56.79.35：1892

D、205.56.79.35：2256

標準答案：A

知識點解析：本題考查地址轉換技術NAT的工作原理，NAT協議利用端口域來解

決內網到外網的地址映射問題。任何時候當一個向外發送的分組進入到NAT服務

器的時候，源地址被真實的公網地址所取代，而端口域被轉換為一個索引值(21被

轉換成2056)。因此答案是A。

36、ICMP協議不具備的功能是()。

A、向源主機發送網絡不可達報文

B、向路由器發送回送請求報文

C、進行時間戳請求

D、獲取主機IP地址

標準答案：B

知識點解析：IPv6首部的固定部分被簡稱為IPv6首部，其大小是40字節，而

IPv4首部中的必要部分為20字節。IPv6已經定義了以下擴展首部：逐跳選項首部

(Hop—by-HopOptionsheader)：定義需要逐跳處理的特殊選項；路由首部(Rouling

header)：提供獷展路由，類似于IPv4的源路由：片段首部(Fragmentheader)：包

含分片和重組信息：認證首部(Authenticationheader)：提供數據完整性和認證；

封裝安全負載首部(EncapsulationSecurityPayloadheader)：提供秘密性；目標選項

首部(DestinationOptionsheader)：包含要在目標節點檢查的可選信息。因此答案是

Bo

37、現有一個長度為3000B的IP數據報，其IP頭部的長度為20B,該IP數據報

如在最大幀長度為1518B的以太網中進行傳輸，那么為了正確傳輸，需要將其拆

分的數據報個數是()。

A、2

B、3

C、4

D、不必拆分

標準答案：B

知識點解析：本題考查1P分片的原理和應用，這里以太網幀頭為18B,IP頭為

20B,因此最大數據載荷是1480B,3000B的數據必須進行分片，3000=1480+

1480+40共3片，因此答案是B。［歸納總結］分片目的：當到來的數據報長度超過

其輸出線路所屬網絡的MTU時，路由器將數據報分成許多較小的片段。每個片段

被封裝成數據報，獨立，專輸。封裝片段使用的報頭取自原始數據報的報頭。分片

原理：路由器利用MTU和報頭長度計算每一報片允許包含的最大數據字節數（必

須是8字節的整倍數），并對原始數據報的數據部分進行分片。在每個報片前僅用

原始報頭的拷貝，修改原始頭部中的某些字段，如總長度、標志位、片偏移（以字

節為單位的偏移量除以8）等，重新計算頭校驗，然后發送。當一個片段到達一個

具有更小MTU的網絡時，需要進一步分片，所有分片都在目的主機重組，中間路

由器不做重組的工作。分片重組：將到來的報片重新組裝一個完整數據報的過程

稱為重組，重組是在目的主機中進行的。目的主機使用源地址和分組標識來確定屬

于同一個數據報的片段，根據MF標志判斷是否最后一個報片己經到達。當MF=

0的報片到達時，根據該報片的片偏移字段和總長度字段可以計算出原始數據報的

總長度。當所有報片都已到達時，按照各報片在原始數據報中的偏移量進行組裝。

38、傳輸層用于標識不同的應用的是（）。

A、物理地址

B、端口號

C、IP地址

D、邏輯地址

標準答案：B

知識點解析：本題考查端口號的作用，端口號是傳輸層的服務訪問點，讓應用層的

應用進程通過端口來交討數據給傳輸層，是標志應用層的進程，因此答案是B。

［歸納總結］傳輸地址，也就是端口號是傳輸層通信的端點，網絡地址（網絡服務訪問

點）是網絡層通信的端點，注意每個端口號上綁定一個應用進程，應用進程通過各

自的端口號調用傳輸層服務。傳輸實體（傳輸層服務的提供者）通過本地的網絡服務

訪問點，也就是網絡地址調用網絡層服務，與遠程的對等傳輸實體進行通信。

39、有關路由器的描述F確的是（）.

A、單獨的廣播域，分開的沖突域

B、分開的廣播域，單獨的沖突域

C、分開的廣播域，分開的沖突域

D、單獨的廣播域，單獨的沖突域

標準答案：c

知識點解析：木題考查路由將的作用，路由器工作在網絡層，因此能夠隔斷廣播域

和沖突域，注意單獨的廣播域是指路由器本身是一個單獨的廣播域，因此答案是

Co

40、DNS作為一種分布式系統，所基于的模式是（）。

A、C/S模式

B、B/S模式

C、P2P模式

D、以上均不正確

標準答案：A

知識點解析：本題考查網絡應用模型，DNs作為分布式應用，是一種典型的C/S

模式，13/5模式又稱8/5結構，隨著Internet技術的興起，對C,/S模式應用

的擴展。因此答案為A。［歸納總結］現代網絡應用有3種主流的體系結構：客戶/

服務器體系結構，P2P體系結構，以及客戶/服務器和P2P混合的體系結構。（1）

在客戶/服務器體系結溝中，有一個總是打開的主機稱為服務器，它在固定的、眾

所周知的地址上為其它稱為客戶機的主機提供服務，客戶機之間不直接通信。經典

的網絡應用，如電子郵件、文件傳輸、遠程訪問、萬維網等，都采用了這種體系結

構。（2）在純P2P體系結構中，沒有一個總是打開的服務器，任意一對主機（稱為對

等方peer）之間直接通信。對等文件共享采用了這種體系結構，任何主機都能向其

它主機請求文件，也能向其它主機發送文件。每個主機的作用都像一臺服務器，向

它所在的共享文件社區貢獻資源。在今天的因特網中，P2P文件共享流量在所有流

量中占了很大一部分。（3）混合體系結構同時使用客戶/服務器結構和P2P結構，

即時訊息采用了這種結溝。在即時訊息中，兩個聊天的用戶之間通常是P2P,即這

兩個用戶之間發送的消息不通過總是打開的中間服務器。然而，一個用戶在開始他

的即時訊息應用前必須在某個中心服務器上注冊，當他要與聯系人列表中的某個人

聊天時，他的即時訊息客戶機要與中心服務器聯系，以找出可以聊天的在線聯系

人。

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

41、已知AOE網中頂點V”v2,v3,……V7分別表示7個時間，有向線段ai，

a2,a3,……aIOo分別表示10個活動，線段旁的數值表示每個活動花費的天數，

如下圖所示。請填寫下面兩個表格，并用頂點序列表示出關鍵路徑，給出關鍵活

動。

*1n“

0I2?1110

41晚宴4時IW0S3?1410

■:aa4Al一Aj<?

a單斤的時同0003322<7s

00134$3.?6

0010131001

標準答案:關鍵路徑：V|v2v5V7V1

V4V5V7關鍵“舌動：a1a2a4a8a9

知識點解析：AOE網中從源點到終點的最大路徑長度(這里的路徑長度是指該路徑

上的各個活動所需時間之和)的路徑稱為關鍵路徑。關鍵路徑長度是整個工程所需

的最短工期。關鍵路徑上的活動稱為關鍵活動。要縮短整個工期，必須加快關鍵活

動的進度。尋找關鍵活動時所用到的幾個參量的定義。假設第i條弧為，dut()為

弧上的權值。(1)事件的最早發生時間ve[k]=從源點到頂點k的最長路徑長度，

ve(源點)=0；ve(k)=Max{ve(j)+dul()}(2)事件的最遲發生時間vl[j]=從頂點j到

匯點的最短路徑長度。vl(匯點)=ve(匯點)；vl(j)=Min{vl(k)—dut()}(3)活動i的最

早開始時間e(i)=ve(j)o(4)活動i的最晚開始時間l(i)=vl(k)—dut()0e[i]=l川的

活動就是關鍵活動，關鍵活動所在的路徑就是關鍵路徑。

42、己知在二叉樹中，T為根結點，*p和*q為二叉樹中兩個結點，試編寫求距離

它們最近的共同祖先的算法。

標準答案：int.found=FALSEIBitree*Find_Near_Ancient(BitreeT,BitreeP,

Bitreeq){//求二叉樹T中結點P和q的最近共同祖先Bitreepathp[100],

pathq[iOO]；//設立漩個輔助數組暫行從根到P,q的路徑Findpath(T,P,

pathp>0)；found=FALSE；Findpath(T,q,pathq,0)；//求從根到p,q的路

徑放在pathp和pathq中for(i=Opathp[i]==pathq[i]&&pathp[i]；i++)；，//

查找兩條路徑上最后一個相同結點returnpathp[----i]；)voidFindpath(BitreeT,

BitreeP,Bitreepath|],inti){//求從T到P路徑的遞歸算法if(T==p){found=

TRUE：//找至ljreturn；)path[i]=T；//當前結點存入路徑if(T->ichild)

Findpath(T->ichiId,P,path,i+1)：//在左子樹中繼續尋找if(T

—>rchild&&!found)Findpath(T—>rchild,P,path,i+1)；//在右子樹中繼續尋

找if(!found)path[i]=NULL：//回溯

知識點解析：本題也可敘述為求，*十和*口兩個結點的最小子樹。遍歷訪問到十

時，將*p結點的祖先保存到數組palhp中，再遍歷訪問到*q時，將*q結點的祖先

保存到藪組palhq中，將數組palhp與數組pathq的結點依次(從0開始)比較，技到

最近的共同祖先。

43、試用74181和門電路實現?位余3碼加法器。

標準答案：用2片74181和1個非門即可實現余3碼加法器，其邏輯框圖如下圖所

知識點解析：首先寫出余3碼的校正函數：有進位，+3（+0011）校正；無進位，

-3（+1101）校正。根據余3碼的校正函數，設計加法器，下面一片74181完成一

位余3碼的加法，上面一片74181完成校正。［歸納總結］在計算機中，十進制數是

用BCD碼表示的，BcD碼由4位二進制數表示，按二進制加法規則進行加法。十

進制數的進位是10,而4位二進制數的進位是16,為此需要進行必要的十進制校

正，才能使該進位正確。不同的BCD碼對應的十進制校正規律是不一樣的，因此

硬件實現也是不同的。余3碼的加法規則：（1）兩個十進制數的余3碼相加，按

“逢二進一”的原則進行c（2）若具和沒有進位，則減3（即十11。1）校正。（3）若具和

有進位，則加3（即+0011）校正。余3碼的校正關系見下表。

*3W

1iKMft

C/&'&'g?

G&S,51sl

000011oo11a

10010000111

20C101o|ooa

3001100l00I

4001I10l01o

50100001011

i010010II00

-3?iE

010t001101

8oioii0111o

9Oil。。0t111

101001110000

IIIaioo10001

121cio110010

11i011010011

141011110100

151100010101

li1100110110

十$校iF

1711D1010111

IB110111I000

1911100I1001

根據校正關系，很容易得到校正函數;

C4=0,一3校正；CZ=1，+3校正。向上一位的進位C4=C，4。［解題技巧］對

于BCD碼加法器的設計來說，關鍵的問題是找出校正關系。

44、一個字節多路通道連接D］、D2、D3、D4、D5共5臺設備，這些設備分別每

10邯、30|is>30ps>50|JS和75|is向通道發出一次數據傳送的服務請求，請回答下

列問題：（1）計算這個字節多路通道的實際流量和工作周期。（2）如果設計字節多路

通道的最大流量正好等于通道實際流量，并假設對數據傳輸率高的設備，通道響應

它的數據傳送請求的優先級也高。5臺設備在0時刻同時向通道發出第一次傳送數

據的請求，并在以后的時間里按照各自的數據傳輸率連續工作。畫出通道分時為每

臺設備服務的時間關系圖，并計算這個字節多路通道處理完各臺設備的第一次數據

傳送請求的時刻。（3）從時間關系圖上可以發現什么問題?如何解決這個問題？

標準答案：⑴這個字節多路通道的實際流量為'=（上+*

通道的工作周期為：丁=二"*包括設備選擇時間Ts和傳送一個字節的時間

TDO（2）5臺設備向通道請求傳送和通道為它們服務的時間關系下圖所示，向上的

箭頭表示設備的數據傳送請求，有陰影的長方形表示通道響應設備的請求并為設備

服務所用的工作周期。

時刻同時向字節多路通道發出第一次傳送時間的請求，通道處理完各設備第一次請

求的時間分別為：處理完設備Di的第一次請求的時刻為5gs；處理完設備D2的

第一次請求的時刻為10ps；處理完設備D3的第一次請求的時刻為202：處理完

設備D4的第一次請求的時刻為302；設備D5的第一次請求沒有得到通道的響

應，直到第85四通道才開始響應設備Ds的服務請求，這時，設備已經發出了兩個

傳送數據的服務請求，因此第一次傳送的數據有可能丟失。（3）當字節多路通道的

最大流量與連接在這個通道上的所有設備的數據流量之和非常接近時，雖然能夠保

證在宏觀上通道不丟失設備的信息，但不能保證在某個局部時刻不丟失信息。由于

高速設備在頻繁地發出要求傳送數據的請求時，總是被優先得到響應和處理，這就

可能使低速設備的信息一時得不到處理而丟失，如本題中的設備D5。為了保證本

題中的字節多路通道能正常工作，可以采取以下措施來解決：①增加通道的最大

流量，保證連接在通道上的所有設備的數據傳送請求能夠及時得到通道的響應。

②動態改變設備的優先級。例如，只要在302?70g之間臨時提高設備D5的優

先級，就可使設備D5的第一次傳送傳送請求及時得到通道的響應，其他設備的數

據傳送請求也能正常得到通道的響應。③增加一定數量的數據緩沖器，特別是對

優先級比較低的設備。例如，只要為設備D5增加一個數據緩沖器，它的第一次數

據傳送請求可在85Ps處得到通道的響應，第二次數據傳送請求可以在145聯史得

到通道的響應，所有設備的數據都不會丟失。

知識點解析：通道流量是指通道在數據傳送期內，單位時間里傳送的字節數。它能

達到的最大流量稱為通道極限流量。［歸納總結］假設通道選擇一次設備的時間為

Ts，每傳送一個字節的時間為TD，字節多路通道通道工作時的極限流量分別為：

中干部兩二由每選擇一臺設備只傳送一個字節。若通道上接P臺設

備，則通道要求的實際流量分別為：字節多路通道'=為使通道所接外部設

備在滿負荷工作時仍不丟失信息，應使通道的實際最大流量不能超過通道的極限流

量。如果在I/O系統中有多個通道，各個通道是并行工作的，貝IJI/O系統的極

限流量應當是各通道或各子通道工作時的極限流量之和。

45、設某多道程序系統中有用戶使用內存1000M,打印機1臺。系統采用可變分

區動態分配算法管理內存，而對打印機采用靜態分配。假設輸入輸出操作時間忽略

不計，采用最短剩余時間優先的進程調度算法，進程最短剩余時間相同時采用先來

先服務的算法，進程調度時機選擇在進程執行結束或新進程創建時，現有進程如

**供行時斛*就行卬花

001I

1<1100MI

1101eOOM0

1IIX）MOM1

下:<14IooM0假設系統優先分配內存低地址區

域,且不允許移動，那么，求：（1）給出進程調度算法選中進程的次序，并說明理

由O（2）全部進程執行結束所用的時間是多少？

標準答案：（1）進程運行的順序是，進程0,進程1,進程3,進程4,進程3,進程

2,原因見上述分析。（2）總共運行了47個時間片。原因見上述分析。

BBtotiiiiiiaiir-

幫例一運行

—后善

知識點解析：本題考查調度算法的理解和計算。最簡單的方法就是畫出其甘特圖。

下面分析：時刻0,進程0到達，投入運行，占用150M內存，并占用打印機；運

行到時刻4,進程1到達，占用內存300M,申請使用打印機，此時進程。和進程

1均剩余4,但是進程0先到，故繼續運行；運行到時刻8,進程0退出，釋放

150M內存，進程I運行，占用打印機；運行到時刻10,進程2到達，但是，剩余

內存不足，不可創建到內存，在外存后備；時刻11,進程3到達，占用200M內

存，申請打印機，其運行時間20大大大于此時進程1的1,故進程1保持運行；

運行到時刻12,進程1退出，進程3運行，運行到時刻16,進程4到達，內存空

間450M和350M均滿足使用，創建到內存，由于它不需要打印機，他的剩余時間

14小于進程3的16,故進程4搶奪進程3運行，進程3帶著打印機就緒等待；運

行到30,進程4退出，進程2還是不能參加到內存，進程3繼續運行；到時刻

46,進程3退出，內存足夠進程2創建了，進程2創建并運行，至U時亥U47退出,

運行結束。

46、假定某采用頁式虛網存儲管理的計算機系統中，主存儲器容量為IGB,被分

為262144塊物理塊，物理塊號為0,1,2,……,26