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

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

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

1、此程序的復雜度為（）。for（inti=0；i0；j-）A[i][j]=i+j；

A、O（m7）

B、0（n2）

C、O（m*n2）

D、O（m+n）

標準答案：C

知識點解析：內(nèi)層循環(huán)語句最多執(zhí)行次數(shù)為

2、一個具有1025個結(jié)點的二叉樹的高h為（）。

A、11

B、10

C、11至1025之間

D、10至1024之間

標準答案：c

知識點解析：一棵二叉樹每層只有1個結(jié)點，則具有1025個結(jié)點的二叉樹的最大

高度為1025。一個具有1025個結(jié)點的完全二叉樹的高度為11。這一個具有1025

個結(jié)點的二叉樹的高h為11至1025之間。

3、構造操作系統(tǒng)的主要結(jié)構模式是（）。I整體式垢構II層次式結(jié)構ID微內(nèi)核（客

戶/服務器）結(jié)構W對稱式結(jié)構

A^I和m

B、II和W

c、I、II和in

D、□、HI和IV

標準答案：C

知識點解析：操作系統(tǒng)是一種大型的、復雜的系統(tǒng)軟件，為了合理地使用操作系

統(tǒng)，必須分析、了解并掌握其結(jié)構。在操作系統(tǒng)的發(fā)展過程中，出現(xiàn)了多種操作系

統(tǒng)結(jié)構，整體式結(jié)構是早期操作系統(tǒng)設計中所采用的方法，即首先確定操作系統(tǒng)的

總體功能，然后將總功能分解為若干個子功能，實現(xiàn)每個子功能的程序稱為模塊。

層次式結(jié)構力求使模塊向調(diào)用的無序性變?yōu)橛行蛐?。因此層次式結(jié)構最內(nèi)層是裸

機，裸機的外層是操作系統(tǒng)的第一層，以后每增加一層軟件就是在原虛擬機上的又

一次擴充，又成為一個新的虛擬機。微內(nèi)核（客戶/服務器）結(jié)構的操作系統(tǒng)適宜于

應用在網(wǎng)絡環(huán)境下分布式處理的計算環(huán)境中。內(nèi)核只提供了一個很小的功能集合。

除內(nèi)核部分外，操作系統(tǒng)所有的其他部分被分成若干個相對獨立的進程，每一個進

程實現(xiàn)一組服務，稱為服務進程。這些服務進程可以提供各種系統(tǒng)功能、文件系統(tǒng)

服務以及網(wǎng)絡服務等。對稱式結(jié)構在操作系統(tǒng)結(jié)構設計中是不存在的。

4、在基址尋址方式中，若基址寄存器BR的內(nèi)容為2D3CH,形式地址A的內(nèi)容

為53H則有效地址EA為（）。

A、53H

B、2D3CH

C、2D8FH

D、803CH

標準答案：C

知識點解析：基址尋址方式下，EA=（BR）+A,結(jié)合題中條件，

EA=（BR）+A=2D3Ci6+53i6=2D8Fi6，選Co

5、假設棧的容量為3,入棧的序列為1、2、3、4、5,則出棧的序列可能為（）。

I.5、4、3、2、1H.1、5、4、3、2HI.3、2、1、5、41V.4、3、2、1、5

A、I、m

B、只有HI

c、口、in

D、只有IV

標準答案：B

知識點解析：此題有一個陷阱，因為沒有按照常規(guī)的思路出題。這種題型在2009

年的真題第2題中反著考過一次，是給出一個入棧和出棧的序列（通過出隊序列可

以知道出棧的序列），要求考生算出棧的容量。首先，由于棧的容量只有3,很明

顯4和5不能第一個出來，所以先排除I和W；再看口，1入棧，I出棧，然后只有

2、3、4、5同時入棧，5才能第二個出棧，所以要實現(xiàn)這種出棧序列，棧的容量至

少要為4,與題意矛盾，故只有IH才是可能的出棧序列。

6、設CPU與I/O設備以中斷方式進行數(shù)據(jù)傳送。當CPU響應中斷時，該I/O

設備接口控制器送給CPU的中斷向量表（中斷向量表存放中斷向量）的指針是

0800H,0800H單元中的值為1200H,則該I/O設備的中斷服務程序在主存中的

入口地址為（）。

A、0800H

B、0801H

C、1200H

D、1201H

標準答案：C

知識點解析：首先需耍明白中斷向量就是中斷服務程序的入口地址，所以需要找到

指定的中斷向量。中斷向量是保存在中斷向量表中的，而0800H是中斷向量表的

地址，所以0800H的內(nèi)容即是中斷向量。

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

數(shù)至少是（）。

A、11

B、10

C、9

D、8

標準答案：B

知識點解析：n個結(jié)點的無向圖中,邊數(shù)e0n(n-l)/2,將e=36代入，有定9,現(xiàn)

已知無向圖非連通,WJn=10o

8、下面的地址中，屬于單播地址的是()。

A、10.3.2.255/24

B、172.31.129.255./18

C、192.168.24.59/30

D、224.100.57.211

標準答案：B

知識點解析：A選項：10.3.2.255/24所表示的子網(wǎng)掩碼是1111111111111111

1111111100000000,即后8位為主機號，很明顯主機號全為1,所以10.3.2.255/24

是子網(wǎng)10.3.2.0的一個廣播地址。B選項：與A選項類似，可以得到主機號為

000001111111Ho由此可知，172.31.129.255/18是一個單播IP地址。C選項：與

A選項類似，可以得到主機號為11。由此可知，192.168.24.59/30屬于子網(wǎng)

192.168.24.56的一個廣播地址。D選項：224.100.57.211為D類IP地址，即組播

地址。

9、進程從運行狀態(tài)轉(zhuǎn)換為就緒狀態(tài)的可能原因是()。

A、被調(diào)度程序選中占用處理機

B、等待某一事件

C、等待的事件已經(jīng)發(fā)生

D、時間片用完

標準答案：D

知識點解析：就緒狀態(tài)是指一個進程獲得了除處理機以外的一切資源，當?shù)玫秸{(diào)度

時，就由就緒狀態(tài)轉(zhuǎn)換為運行狀態(tài)；運行狀態(tài)就是一個進程在處理機上正在運行。

當處于運行狀態(tài)的進程在運行過程中所分配的時間片用完，則會被強制撤離處理

機，以便調(diào)度其它進程運行。由于原先運行的進程是非自愿地離開運行狀態(tài)，所以

沒有其它的事件相關，只有繼續(xù)在就緒隊列中等候下一次的調(diào)度，所以D是正確

的。A的情形是由就緒狀態(tài)轉(zhuǎn)換為運行狀態(tài)；B的情形是由運行狀態(tài)轉(zhuǎn)換為阻塞狀

態(tài)；C的情形是由阻塞狀態(tài)轉(zhuǎn)換為就緒狀態(tài)，均不正確，正確答案應選D。本題主

要考察學生對進程狀態(tài)以及相互轉(zhuǎn)換的關系，難度也并不高，改變一下問題的問

法，ABC三個答案均會有可能。

10、已知10個數(shù)據(jù)元素為(54,28,16,34,73,62,95,60,23,43),按照依

次插入結(jié)點的方法生成一棵二叉排序樹后，查找值為62的結(jié)點所需比較的次數(shù)為

()o

A、2

B、3

C、4

D、5

標準答案：B

知識點解析：參考一.叉徘序樹的建立。將這10個元素按照依次插入結(jié)點的方法生

成一棵二又排序樹后，62位于這棵二又排序樹的第三層，查找值為62的結(jié)點所需

要的次數(shù)恰好是從二叉徘序樹的根到被查結(jié)點的樹的深度。

11、設有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，ai」為

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

A、13

B、33

C、18

D、40

標準答案：B

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

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

(I+7)x7/2=28個元素，在第8行中,的前面有4個元素,所以，ax.s前有

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

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

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

A、k

B、n

C>n-k

D、n+k

標準答案：C

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

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

1)+…(Vm-1)=K,所以n=m+k。

13、一臺裝有Linux系統(tǒng)的主機，只有兩個賬號root和guest,下面關于“Linux是

一個多用戶、多任務的操作系統(tǒng)”的理解中，正確的有()。I.該主機允許root和

guesl同時登錄，因為LinUX系統(tǒng)支持多用戶口.咳主機不允許root和guest同時

登錄，因為Linux系統(tǒng)最多只能有一個活躍用戶HI.該主機允許多個客戶端通過

root賬號登錄，因為Linux系統(tǒng)支持多任務W.該主機不允許多個客戶端通過同一

賬號登錄，因為Linux用戶只能有一個活躍客戶端

A、I和川

B、I和W

c、II和m

D、II和IV

標準答案：A

知識點解析：這里的“賬號”等價于“用戶”。I正確很容易理解，支持多用戶，肯

定就是支持同時登錄。in正確，多個客戶端通過同一賬號登錄，這些個客戶端其

實運行的只是一個進程。Linux支持多任務的系統(tǒng)，所以肯定是可以的。知識點擴

展：Linux是一個多用戶、多任務的操作系統(tǒng)，考生應該了解單用戶多任務和多用

戶多任務的概念。（l）Linux的單用戶、多任務。例如,以bcinan登錄系統(tǒng)，進入

系統(tǒng)后，要打開gedil來寫文檔，但在寫文檔的過程中，感覺少點音樂，所以又打

開xmms來點音樂；當然聽點音樂還不行，MSN還得打開，想知道幾個朋友現(xiàn)在

正在做什么。這樣，在用bcinan用戶登錄時，執(zhí)行了gcdit>xmms以及msn等，

還有輸入法fcilx。這樣說來就有點簡單了，一個beinan用戶，為了完成工作，執(zhí)

行了幾個任務；當然beinan這個用戶，其他的人還能以遠程登錄過來，也能做其

他的工作。（2）Linux的多用戶、多任務。有時可能是很多用戶同時用同一個系

統(tǒng)，但并非所有的用戶都一定要做同一件事，所以這就有多用戶、多任務。例

如，LinuxSir.org服務器，上面有FTP用戶、系統(tǒng)管理員、Web用戶、常規(guī)普通

用戶等，在同一時刻，可能有人正在訪問論壇；有人可能在上傳軟件包管理子站，

如luma或Yuking在管理他們的主頁系統(tǒng)和FTP；與此同時，可能還會有系統(tǒng)管理

員在維護系統(tǒng)；瀏覽主頁用的是nobodv用戶，大家都用同一個，而上傳軟件包用

的是FTP用戶；管理員對系統(tǒng)的維護或查看，可能用的是普通賬號或超級權限

rool賬號；不同用戶所具有的權限也不同，要完成不同的任務就需要不同的用戶，

也可以說不同的用戶，可能完成的工作也不一樣。值得注意的是，多用戶、多任

務并不是大家同時擠到一起在一臺機器的鍵盤和顯示器前來操作機器，多用戶可能

通過遠程登錄來進行，比如對服務器的遠程控制，只要有用戶權限任何人都是可以

上去操作或訪問的。

14、磁盤和磁帶是兩種存儲介質(zhì)，他們的特點是（），

A、二者都是順序執(zhí)行的

B、二者都是隨機存取的

C、磁盤是順序存取的，磁帶是隨機存取的

D、磁帶是順序存取的，磁盤是隨機存取的

標準答案：D

知識點解析：本題主要考查磁盤和磁帶的工作方式的區(qū)別。

15、關于ICMP協(xié)議的說法正確的是（）。I.ICMP消息的傳輸是可靠的

D.ICMP被封裝在IP數(shù)據(jù)報的數(shù)據(jù)部分皿.ICMP可用來進行擁塞控制

A、僅I

B、I和n

c>ii和in

D、i和in

標準答案：c

知識點解析：I：由于IP層提供的是無連接不可靠的服務，所以ICMP消息的傳

輸是不可靠的，故I錯誤?？冢篒CMP報文整個被作為【P分組的數(shù)據(jù)部分，所以

II正確。m：主機在發(fā)送數(shù)據(jù)報時，經(jīng)常會由于各種原因發(fā)送錯誤，比如路由器

擁塞丟棄了或者傳輸過程中出現(xiàn)錯誤丟棄了，如果檢測出錯誤的路由器或主機都能

把這些錯誤報告通過一些控制消息告訴發(fā)送數(shù)據(jù)的主機那就好了，那么發(fā)送數(shù)據(jù)的

主機就可根據(jù)ICMP報文確定發(fā)生錯誤的類型，并確定如何才能更好地重發(fā)失敗的

數(shù)據(jù)報。比如ICMP報文發(fā)過來的是改變路由，那么主機就不能繼續(xù)按照這個路由

線路發(fā)送了，需要用另外一條路由線路發(fā)送數(shù)據(jù)，所以m正確。注I：ICMP很文

包含的不僅是出錯類型，而且還要包含出錯IP數(shù)據(jù)報的數(shù)據(jù)部分的前8個字節(jié)。

因為前8個字節(jié)包含了TCP和UDP報文首部巾的TCP或UDP端口號，這樣源主

機可更好地和用戶進程(用戶進程需要IP地址和端口號才能唯一確定)聯(lián)系起來，

因為發(fā)送數(shù)據(jù)的是某個主機中的某個進程向不足主機本身，這樣才算是真正找到了

發(fā)送數(shù)據(jù)源。注2：常用的ping命令使用了回送請求報文，以探測目標主機是否

可達；如果在IP數(shù)據(jù)報傳送過程中，發(fā)現(xiàn)生命周期字段為零，則路由器發(fā)出超時

報文。

16、若線性表最常用的運算是查找第i個元素及其前驅(qū)的值，則下列存儲方式最節(jié)

省時間的是()。

A、單鏈表

B、雙鏈表

C、單循環(huán)鏈表

D、順序表

標準答案：D

知識點解析：線性表中常用的操作是取第i個元素，所以應選擇隨機存取結(jié)構，即

順序表，同時在順序表中查找第i個元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既

不能實現(xiàn)隨機存取，查找第i個元素的前驅(qū)也不方便，雙鏈表雖然能快速杳找第i

個元素的前驅(qū)，但不能實現(xiàn)隨機存取。

17、下列程序段的時間復雜度是()。inti,j；for(i=m+l；i<=m+n；

i++){A[O]=A[i]；for(j=i-l;A[j]>A[i]；j-){A[j+l]=A[j]；)}

A、O(m2)

B、0(n2)

C、O(m*n)

D、O(m+n)

標準答案：C

知識點解析：時間復雜度由m,n共同決定，最壞情況F的時間復雜度為O(mn)。

18、將兩個長度為n的遞增有序表歸并成一個長度為2n的遞增有序表，最少需要

進行關鍵字比較次數(shù)是()。

A、1

B、n-1

C、n

D、2n

標準答案：C

知識點解析：假設有兩個有序表A和B都遞增有序，當有序表A所有元素均小于

B的元素時，只需將A的所有元素與B的第一個元素比較即可，其比較n次。

19、“總線忙”信號由（）建立。

A、獲得總線控制權的設備

B、發(fā)出“總線請求”的設備

C、總線控制器

D、CPU

標準答案：A

知識點解析：在總線控制機制中，準備使用總線的設備向總線控制器發(fā)出,、總線清

求”由總線控制器進行裁決。如果經(jīng)裁決允許該設備使用總線，就由總線控制器向

該設備發(fā)出一個“總線允許”信號。該設備接收到此信號后，發(fā)出一個“總線忙”信號

用來通知其他設備總線已被占用。當該設備使用完總線時，將“總線忙:''信號撤銷，

釋放總線。因此“總線忙”信號是由獲得總線控制權的設備建立的。

20、在UNIX系統(tǒng)中，將一個文件卷復制到另一個磁盤上。只復制文件數(shù)據(jù)，包括

目錄之后（）。

A、文件數(shù)據(jù)能夠被訪問

B、文件目錄能夠被訪問

C、文件數(shù)據(jù)和目錄都能被訪問

D、文件數(shù)據(jù)和目錄都不能訪問

標準答案：D

知識點解析：UNIX系統(tǒng)中每個文件卷需要經(jīng)過安裝后才能使用。所以只復制文件

數(shù)據(jù)，包括目錄后，是都不能訪問的。即使物理介質(zhì)本身在工作，但若其上的文件

卷沒有安裝好，系統(tǒng)也無法存取其中的信息。uNIx需要安裝文件卷后才可以被訪

問。

21、某計算機采用微程序控制，微指令字中操作控制字段共12位，下列說法正確

的是（）。I.若采用直接控制，則此時一條微指令最多可同時啟動12個微操作

n.若采用字段直接編碼控制，并要求一條微指令需同時啟動3個微操作，則微指

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

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

含45個微操作命令

A、僅I、口

B、僅I、m

c、僅u、m

D、I、II和m

標準答案：B

知識點解析：對于I選項：如果12個微操作都相容的話，最多可以同時啟動12個

微操作，故I正確。對于II選項：首先，如果要同時啟動3個微操作，那么這3個

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

誤。對于in選項：由口的分析可知，由于每段占4位，每個字段可表示15種狀態(tài)

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

22、無向圖G有16條邊，有3個度為4的頂點，4個度為3的頂點，其余頂點的

度均小于3,則G至少有（）個頂點。

A、10

B、11

C、12

D、13

標準答案：B

知識點解析：度的定義有的是進入一個頂點的邊數(shù)和從該頂點出去的邊數(shù)之和。我

們可以根據(jù)這個關系來求解此題。由于題目已經(jīng)告訴度為4的頂點有3個，度為3

的頂點有4個，其余的頂點的度均小于3,而已知有16條邊，則總的度數(shù)應為

16x2=32。所以要求最小的頂點個數(shù)，我們應當盡量增加每個頂點的度數(shù)，這里將

剩下的結(jié)點的度數(shù)全部看成2,設結(jié)點數(shù)為x,則3x4+4x3+（x-3-4）x2N32,解得x

至少為11。

23、若循環(huán)隊列以數(shù)組Q[0.?m—”作為其存儲結(jié)構，變量rear表示循環(huán)隊列中

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

當前循環(huán)隊列中的元素個數(shù)，則循環(huán)隊列的隊首元素的實際位置是（）。

A、rear一length

B、（rear-lengh+m）MODm

C>（1+rcar+m—lcngth）MODm

D、m—length

標準答案：C

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

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

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

24、TCP的通信雙方，有一方發(fā)送了帶有FIN標志的數(shù)據(jù)段后表示（）。

A、將斷開通信雙方的TCP連接

B、單方面釋放連接，表示本方已經(jīng)無數(shù)據(jù)發(fā)送，但是可以接收對方的數(shù)據(jù)

C、中止數(shù)據(jù)發(fā)送，雙方都不能發(fā)送數(shù)據(jù)

D、連接被重新建立

標準答案：B

知識點解析：FIN位用來釋放一個連接，它表示本方已經(jīng)沒有數(shù)據(jù)要傳輸了。然

而，在關閉一個連接之后，對方還可以繼續(xù)發(fā)送數(shù)據(jù)，所以還有可能接收到數(shù)據(jù)。

25、有n個葉子結(jié)點的哈夫曼樹的結(jié)點總數(shù)為（）。

A、不確定

B、2n

C、2n+l

D、2n-l

標準答案：D

知識點解析：在哈夫曼樹中，由計算公式可得，結(jié)點總數(shù)為2n—1,所以選D。

26、8086的堆棧采取向下生長的方式，在壓入時的操作是（）。

A、SP先減，再壓入數(shù)據(jù)

B、先壓入數(shù)據(jù)，SP再減

C、SP先加，再壓入數(shù)據(jù)

D、先壓入數(shù)據(jù)，SP再加

標準答案：A

知識點解析：8086微處理器中所謂的向下生長堆棧就是自底向上生成的堆棧（即棧

底地址大于棧頂?shù)刂罚?，棧指針始終指向棧頂?shù)臐M單元。

27、下列關于強連通圖的說法中，正確的是（）。I.n個頂點構成的強連通圖至少

有n條邊H.強連通圖是任何頂點到其他所有頂點都有邊HI.完全有向圖一定是

強連通圖

A、僅I、n

B、僅u、m

c、僅I、m

D、I、口、m

標準答案：C

知識點解析：I：強連通圖是相對于有向圖而言的，即在有向圖G中，任何兩個

頂點都存在路徑。所以最少的情況應該是n個頂點構成一個首尾相連的環(huán)，共有n

條邊，故I正確。H：這個選項不細心的話很容易誤選。在有向圖中，邊和路徑

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

的，所以說正確的表述應該是：強連通圖是任何頂點到其他所有頂點都有路徑，故

II錯誤。n：完全有向圖肯定是任何頂點到其他所有頂點都有路徑，故皿正確。

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

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

則最后一個關鍵字值48的插入位置是（）。

A、4

B、5

C、6

D、8

標準答案：C

知識點解析：首先通過散列函數(shù)H（key尸keymod11的計算得知，37、95、27、14

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

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

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

探測法，則又應該選擇哪一個選項？提示：平方探測法的原理是設發(fā)生沖突的地址

為d,則平方探測法的探測序列為d+產(chǎn)，d-I2,d+22,d—22,…位置4不空

時，下一個探測的位置應該為5,發(fā)現(xiàn)又不空，則下一個探測的位也應該是3,發(fā)

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

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

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

29、傳輸一幅分辨率為640x480,6.5萬色的照片（圖像），假設采用數(shù)據(jù)傳輸速度

為56kb/s,大約需要的時間是（）。

A、34.82s

B、42.86s

C、85.71s

D、87.77s

標準答案：c

知識點解析：照片（圖像）的顏色數(shù)為65536色，意味著顏色深度為16位，則一幅

圖占據(jù)的存儲空間為640x480x16=4915200Ro又因為用數(shù)據(jù)傳輸速度為56Kb/

s,則有傳輸時間=4915200/（56x1024.戶85.71s［歸納總結(jié)］圖片存儲的內(nèi)容就

是一幅像點信息，在單色顯示時，每個點只用一位二進制代碼來表示，在彩色顯示

時，每個點需要由若干位代碼來表示。顏色深度與顏色數(shù)的對應關系為：顏色深

度=10g2顏色數(shù)所以圖片的容量不僅與分辨率有關，還與顏色數(shù)有關。分辨率越

高，顏色數(shù)越多，圖片所占的容量就越大。|解題技巧］首先計算出每幅圖的存儲空

間，然后除以數(shù)據(jù)傳輸率，就可以得出傳輸一幅圖的時間。

30、下列說法中，正確的是（）。I.具有10個葉子結(jié)點的二叉樹中有9個度為2

的結(jié)點U.設高度為5的二叉樹上只有度為0和度為2的結(jié)點，則該二叉樹作所

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

個數(shù)為501個IV.高度為h的完全二義樹最少有2h個結(jié)點

A、僅I、n

B、僅口、m、iv

c、僅I、m、w

D、僅i、口、m

標準答案：D

知識點解析：I：二又樹葉子結(jié)點的個數(shù)比度為2的結(jié)點的個數(shù)多1,故I正確。

總結(jié)：這個性質(zhì)在選擇題中常有體現(xiàn)，并且需要靈活運用。比如題目可能問，二叉

樹中總的結(jié)點數(shù)為n,則樹中空指針的個數(shù)是多少?我們可以將所有的空指針看作

葉子結(jié)點，則圖中原有的所有結(jié)點都成了雙分支結(jié)點。因此可得空指針域的個數(shù)為

樹中所有結(jié)點個數(shù)加1，即n+1個。這個性質(zhì)還可以擴展，即在一棵度為m的樹

中，度為1的結(jié)點數(shù)為M，度為2的結(jié)點數(shù)為n2……度為m的結(jié)點數(shù)為nm，則葉

子結(jié)點數(shù)no=l+n2+2njI...I（m-l）nm。推導過程如下;總結(jié)點=-no+ni+n2+n3I...Inm

①總分支數(shù)=lxni+2xn2+_+mxnm（度為m的結(jié)點引出m條分支）②總分支數(shù)二總

結(jié)點數(shù)-1③將式①和式②代入式③并化簡得no=1+n2+2ns+...+（m-1）nm口：最少

結(jié)點的情況應該是除根結(jié)點層只有1個結(jié)點外，其余4層都有2個結(jié)點，因此結(jié)點

總數(shù)為2x(5-I)+l=9。如圖6-4所示，故II正確。圖64最少結(jié)點的情況皿：由

二叉樹的性質(zhì)可知：no=n2+l,且完全二叉樹度為1的結(jié)點個數(shù)要么為0,要么為

1o又因為二叉樹的總結(jié)點個數(shù)n=no+ni+H2。將no=r)2+l代入，可得n=2no+ni-l；

由于n=1001,得到2no=1002+n]。①當i]]二l時，無解。②當ii]=0時，可解得

no=5O1故HI正確。IV：高度為h的完全二叉樹中，第1層?第h-1層構成一個高

度為h-1的滿二叉樹，結(jié)點個數(shù)為2向-1。第h層至少有一個結(jié)點，所以最少的結(jié)

點個數(shù)=(2>1-1)+1=2k1故W錯誤。

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

存放到一個一維數(shù)組B口中，存放到B[l]中(假定不用O下標)，那么

B[k]存放的元素的行號是()。

A、|(k+l)/3|

B、[(k+l)/3]

C>[(k+2)/3]

D、[(k+2)/3|

標準答案：B

知識點解析：這種題1=1最好采用特殊值法，推導過程可能比較繁瑣，見表6—3。

?6-3特殊值推導過程

k1234S6789

A(i]U]A(1MUA(2](l]Al2H2]A|2](3]A[3J(2]A(3][3JA叫⑷7*3]

「(k+1)/311i2223334

32、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和f.ront的值分別為

0和3,當從隊列中刪除一個元素，再加入兩個元素后，rear和Irom的值分別是

()。

A、1和5

B、2和4

C、4和2

D、5和1

標準答案：B

知識點解析：出隊1個元素后，fronl=(fronl+l)%MAXQSIZE,fronl的值是4；入

隊兩個元素后，rear=(rear+2)%MAXQSIZE,rear的值是2。

33、若一個信號量的初值為3,經(jīng)過多次PV操作以后當前值為一I,此表示等待進

入臨界區(qū)的進程數(shù)是（）c

A、1

B、2

C、3

D、4

標準答案：A

知識點解析：暫無解析

34、某計算機采用頁式存儲管理，內(nèi)存中現(xiàn)有1。00個頁表項，CP1J的cache中可

以存放N個頁表項，該系統(tǒng)中，CP[J內(nèi)存訪問的時間為100ns,對cache訪問的時

間是5ns,如果希望頁表映射的平均時間降到20ns以下,那么cache中的N必須高

于（）。

A、850

B、858

C、923

D、842

標準答案：A

知識點解析：本題考查cache與頁式存儲管理結(jié)合下的時間”算。根據(jù)題意，頁式

尋址方式的過程是這樣的：當執(zhí)行到一個邏輯地址時，MMU首先將頁號分離,將

得到的頁號與cache中的多個頁表項比較（同時進行），若頁表項命中，則取出頁表

項與頁內(nèi)地址相加，形成指令或數(shù)據(jù)的物理地址，花費5ns,據(jù)此地址，然后到內(nèi)

存中取得對應的指令或數(shù)據(jù)，送到CPU中執(zhí)行或計算。若不能在cache命中，那

么cPu會啟動cache更新程序，將新的頁表項從內(nèi)存復制到cache,花費100ns,然

后，重復上述地址轉(zhuǎn)換過程，又花去5ns,得到物理地址，再去內(nèi)存取指令或數(shù)

據(jù)。根據(jù)題意，要求得到頁框號，也就是物理地址的過程小于20ns,那么設，

cache的命中率為x,列關系式：5*x+（l—x）*（5+100）=20解得x為85%。因

此，裝入cache的頁表項應大于1000*85%=850項，這樣可以保證獲得頁框號的

時間小于20ns。本題若問，一個指令雙字的執(zhí)行時間是多少時，需要考慮的事情

就比較復雜。例如系統(tǒng)的字長是否是32位，32位的系統(tǒng)執(zhí)行一個雙字的時間是1

次尋址，16位系統(tǒng)就需要2次尋址。8位系統(tǒng)的就需要4次尋址。另外，采用什么

內(nèi)存管理機制，頁式和段式都是執(zhí)行1次指令尋址需耍訪問內(nèi)存2次，段頁式需耍

3次。還要看cache的容量多大，指令是否在cache中等，所以，內(nèi)存管理中尋址

時間的計算與CPU結(jié)構和cache的運行模式息息相關，考生應結(jié)合計算機組成原

理，妥善解決此類問題。

35、下列關于操作系統(tǒng)結(jié)構說法中，正確的是（）。I.當前廣泛使用的Windows

XP操作系統(tǒng)，采用的是分層式OS結(jié)構口.模塊化的OS結(jié)構設計的基本原則

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

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

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

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

僅In

A、、

僅Im

B、、

僅n

、

C僅w

D、In、

標準答案：c

知識點解析：I錯誤，當前比較流行的、能支持多處理機運行的OS,幾乎全部都

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

塊化。口中描述的是分層式結(jié)構設計的基本原則。皿正確。W錯誤，微內(nèi)核結(jié)構

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

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

以微內(nèi)核結(jié)構設計并不會使系統(tǒng)更高效。由于內(nèi)核的內(nèi)服務變少了，且一般來說內(nèi)

核的服務越少肯定越穩(wěn)定。

36、循環(huán)隊列用數(shù)組A0..m—1］存放其元素值，頭尾指針分別為front和rear,

front指向隊頭元素，rear指向隊尾元素的下一個元素，其移動按數(shù)組下標增大的方

向進行(rear!=m—1時)，則當前隊列中的元素個數(shù)是()。

A^(rear-front+m)%m

B、(rear—front+1)%m

C、real—front-1

D、rear-front

標準答案：A

知識點解析：考查循環(huán)隊列的性質(zhì)。分rear>front和rear〈front兩種情況討論：

①當rear>from時，隊列中元素個數(shù)為rear—front=(rear-front+m)%m②當rear<

front時，隊列中元素個數(shù)為m-(front—rear)=(rear—front+m)%m綜合①、②可

知，選項A正確。

37、單處理機系統(tǒng)中，可并行的是()。I進程與進程n處理機與設備in處理機與

通道w設備與設備

A、I、n和山

B、I、II和w

C、I、ni和w

D、口、in和w

標準答案：D

知識點解析：進程和進程是不能并行的，因為只有一個CPU。

38、圖8—1是一棵()。

A、4階B一樹

B、4階B+樹

C、3階B一樹

D、3階B+樹

標準答案：A

知識點解析：首先很明顯不是B+樹，因為B+樹的葉子結(jié)點本身依關鍵字的大小自

小而大順序鏈接，故排除B、D選項。另外，B一樹有一個性質(zhì)為：m階B一樹的

結(jié)點關鍵字數(shù)量最多為m—1個，但是圖8—1中有個結(jié)點有3個關鍵字，也就是

說此B一樹不可能是3階，故選A選項。

39、設有一個二維數(shù)組在存儲中按行優(yōu)先存放(數(shù)組的每一個元素占一個

空間)，假設A[。]⑼存放位置在7X0C1O),A[4][6]存放位置在1146(1U),則

A[6][20]在()位置(其中(10)表明用十進制數(shù)表示)。

A、1342(10)

1336()o)

C、1338(io)

D>134O(io)

標準答案：D

知識點解析：由Loc(4,6)=Loc(0,0)+(4xn+6)xl=780+(4xn+6)=l146,n=(1146—

780—6)/4=90,則可計算Loc(6,20)=Loc(0,0)+(6x90+20)x1=780+560=1340°

40、不需要搶占的進程調(diào)度算法是()。

A、最早截至時間優(yōu)先

B、時間片輪轉(zhuǎn)

C、最短時間優(yōu)先

D、最短剩余時間優(yōu)先

標準答案：C

知識點解析：最短時間優(yōu)先算法以進程本次所需CPU時間的長短作為調(diào)度的依據(jù)

來選擇進程投入運行，一旦進程獲得處理機后就不可被搶占直到本進程執(zhí)行完畢。

而其他3種進程調(diào)度算法都是基于搶占的調(diào)度算法，當前獲得處埋機的進程可能被

剛進來的進程搶占處理機。故選C。

二、綜合應用題(本題共9題，每題7.0分，共9分。)

下圖所示為雙總線結(jié)構機器的數(shù)據(jù)通路，IR為指令寄存器，PC為程序計數(shù)器(具有

自增功能)，M為主存(受R/W信號控制)，AR為地址寄存器，DR為數(shù)據(jù)緩沖寄

存器，ALU由加、減控制信號決定完成何種操作，控制信號G控制的是一個門電

路。另外，線上標注有小圈表示有控制信號，例中yi表示y寄存器的輸入控制信

號，R1。為寄存器R1的輸出控制信號，未標字符的線為直通線，不受控制。

Aq線

B總找

41、“ADDR2,R0”指令