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

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

1、利用棧求表達(dá)式的值時，設(shè)立運(yùn)算數(shù)棧OPND。假設(shè)OPND只有兩個存儲單

元，在下列表達(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

知識點(diǎn)解析：利用棧求表達(dá)式的值時，將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式以及進(jìn)行后

綴表達(dá)式求值這兩步操祚可以和在一起進(jìn)行，需要設(shè)立運(yùn)算符棧OPTR和自算數(shù)

棧OPND兩個棧。例如求選項(xiàng)A的表達(dá)式A—B*(C—D)的過程如下表所示：

求A-B-(C-D)衰達(dá)式值的過程

當(dāng)前字符運(yùn)算符枝OPTR運(yùn)算數(shù)極。PND說明

AA

一—A

B一AB

.一?AB

(一?(AB

C?(ABC

-?(-ABC

D-?<-ABCD

)一■ABT!執(zhí)行C-D運(yùn)克?令Ti-C-D

一AT,執(zhí)行B?「運(yùn)算,令

T,執(zhí)行ATi運(yùn)算?令T嚴(yán)A-T,

按照上述過程可知，選項(xiàng)A求值時，運(yùn)算數(shù)棧OPND的大小至少為4。例如求選

項(xiàng)B的表達(dá)式(A—B)*C—D的過程如下表所示：

求（A-B）?C-D表達(dá)式值的過程

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

((

A(A

—(-A

B(-AB

)Ti執(zhí)行A-B運(yùn)算.令=

?■Ti

CT?C

—一

Tt執(zhí)行Ti-C運(yùn)d?令Ti-T,?C

D—T,D

T,執(zhí)行Tt-D運(yùn)算,令TJ-TLD

按照上述過程可知，選項(xiàng)B求值時，運(yùn)算數(shù)棧OPND的大小至少為2。類似地,

選項(xiàng)C、D求值時，運(yùn)算數(shù)棧OPND的大小至少為3、3o因此本題答案為B。

2、序列（8,9,10,4,5,6,20,1,2）,只能是以下哪種排序方法兩趟排序后的

結(jié)果是（）。

A、選擇排序

B、冒泡排序

C、插入排序

D、堆排序

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

知識點(diǎn)解析：本題主要考查各種排序的手工排序過程。執(zhí)行兩趟選擇排序后，結(jié)果

應(yīng)該是（1,2,……）。執(zhí)行兩趟冒泡排序后（假設(shè)掃描是從前向后），結(jié)果應(yīng)該是

（……,10,20）o執(zhí)行兩趟堆排序后，若采用大根堆，則結(jié)果應(yīng)該是（……，10，

20）：若采用小根堆，則結(jié)果應(yīng)該是（……，2,l）o執(zhí)行兩趟插入排序后，待排序序

列前3個關(guān)鍵碼有序。

3、頁式存儲系統(tǒng)的邏輯地址是由頁號和頁內(nèi)地址兩部分組成的。假定頁面的大小

為4KB,地址變換過程如圖1-3所示，圖中邏輯地址用十進(jìn)制數(shù)表示。邏輯地址經(jīng)

過變換后，十進(jìn)制數(shù)物理地址a應(yīng)為（）。

控制寄存器邏輯地址

圖1?3頁式存儲系統(tǒng)的邏輯地址變換過程

A、33220

B、8644

C、4548

D、2500

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

知識點(diǎn)解析：本題考查的是頁式存儲系統(tǒng)管理中的地址變換知識。在頁式存儲系統(tǒng)

管理中，邏輯地址除以頁的大小，然后向下取整為頁號，取余為頁內(nèi)地址。本題頁

面的大小為4KB,邏根地址8644除以4096,取整為2,取余為452。頁號為2,

查頁表得物理塊號為8。因此，a的有效地址為8x4096+452=33220。

4、下列關(guān)于Flash存儲器的說法正確的是（）。

A、Flash存儲器屬于易失性存儲器

B、Flash存儲器不具備寫功能

C、Flash存儲器是不可擦除的存儲器

D、Flash存儲器同時具有ROM和RAM的功能

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

知識點(diǎn)解析：Flash存儲器是一種具有較高存儲容量、較低價格、非易失性、可在

線擦除與編程的新一代讀寫存儲器。從基本工作原理上看，F(xiàn)lash存儲器屬于

ROM。型存儲器，但由于它又可以隨時改寫其中的信息，所以從功能上看，它又

相當(dāng)于隨機(jī)存儲器（RAM）。Flash存儲器與其他存儲器的區(qū)別總結(jié)，如表1-6所

衰1-6存儲3與其他存儲立的區(qū)別

內(nèi)存類盤tsxn高*度可與

FUsb〃健器是生ik

SRAM不是不是￡

DRAM不禁ftft

ROM&ft不JC

EPROM&是小型

EEPROMft不是

/J、O

5、臨界區(qū)是指并發(fā)進(jìn)程訪問共享變量段的（）。

A、管理信息

B、信息存儲

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

D、代碼程序

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

知識點(diǎn)解析：本題考查對臨界區(qū)的理解。所謂臨界區(qū)，并不是指臨界資源，臨界資

源是指共享的數(shù)據(jù)、代碼或硬件設(shè)備等，而臨界區(qū)是指訪問這些臨界資源的那段代

碼程序，例如PV操作，加減鎖等。操作系統(tǒng)中對臨界區(qū)的訪問關(guān)心的就是臨界區(qū)

的操作過程，具體對臨界資源作何操作是應(yīng)用程序的事，操作系統(tǒng)并不關(guān)心。

6、CRC校驗(yàn)是目前常用的檢錯方式。如果采用的多項(xiàng)式為G(X)=X4+-X?+X+1,那

么對于要傳的信息串1101011011的CRC校驗(yàn)碼是()。

A、1011

B、1101

C、1110

D、1100

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

知識點(diǎn)解析：本題考查CRC校驗(yàn)的計(jì)算方法。設(shè)信息位串為al2a3……則信

1m,2m2Jni3

息編碼多項(xiàng)式為M(x)=ax-+ax-+ax-+……+叫選擇一個r次多項(xiàng)式G[x)作

為生成多項(xiàng)式，再按下面步驟生成校驗(yàn)串：(1)在信息位串后補(bǔ)r個0,對應(yīng)的多項(xiàng)

式為X『M(x)；(2)用模2又不借位除法，計(jì)算X「M(K)/G(x)的余數(shù)R(x)。R(x)就是

校驗(yàn)位串對應(yīng)的多項(xiàng)式。設(shè)要發(fā)送的碼字多項(xiàng)式為T(x),則：T(x)=xrM(x)+R(x)

本題中該字符串為1010001,G(X)=X4+X2+X+1,因此M(X)=X6+X4+L

r=4xrM(x)=x1O+x8+x4->10100010000itR(x)=xrM(x)/G(x)的過程如下：

looini

loinyioioooioooo

loin

11010

10111

11010

loin

11010

ion】

11010

loin

1101R(x)為1101,因此R(x)=xrM(x)/G(X)=X3+X2+1,T(x)=xrM(x)/

G(x)+R(x)=x10+x8+x4+x3+x2+l,也就是1010001(信息位用)1101(校驗(yàn)位串)，因此

答案為B。

7、信道帶寬為IGbps,端到端時延為10ms,TCP的發(fā)送窗口為65535B,則可能

達(dá)到的最大吞吐量是()c

A、1Mbps

B、3.3Mbps

C、26.2Mbps

D、52.4Mbps

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

知識點(diǎn)解析：本題考查TCP傳輸?shù)男阅芊治觥０l(fā)送時延M=65535x8;(lxio9)s,往

返時延t2=2x0.01s,當(dāng)達(dá)到最大吞吐量時信道接收到確認(rèn)之后立刻發(fā)送下一報(bào)文

段，時間間隔日1+12。所以最大吞吐量為65535x以(tl+t2戶26.2Mbps。

8、對關(guān)鍵碼序列(23,17,72,60,25,8,68,71,52)進(jìn)行堆排序，輸出兩個最

小關(guān)鍵碼后的剩余堆是()。

A、(23,72,60,25,68,71,52)

B、(23,25,52,60,71,72,68)

C、(71,25,23,52,60,72,68)

D、(23,25,68,52,60,72,71)

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

知識點(diǎn)解析：本題主要考查堆排序過程。篩選法初始建堆為(8,17,23,52,25,

72,68,71,60),輸出8重建堆(17,25,23,52,60,72,68,71),輸出17重

建堆為(23,25,68,52,60,72,71)。

9、一個磁盤有N個磁道，尋道時每移過一個磁道耗時T秒，文件相鄰的數(shù)據(jù)塊在

磁盤上存放的位置平均相隔13個磁道，磁盤旋轉(zhuǎn)延時平均R秒，每個存儲塊的傳

輸時間為P秒，在這種情況下，傳輸100個數(shù)據(jù)塊需要的時間是()。

A、13T+l00(R+P)

B、100(13T+R+P)

C、13(T+100R+P)

D、100(l3T+P)+R

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

知識點(diǎn)解析：木題考查磁盤讀寫的時間計(jì)算.對于單磁頭的情況，一般計(jì)算時考慮

的時間花費(fèi)主要有尋道延時，旋轉(zhuǎn)延時.,讀寫延時和傳送延時，根據(jù)題意，對每一

個環(huán)節(jié)的時間做出計(jì)算，便可以求的整個時間的延時。解得本題的關(guān)鍵是要了解磁

盤的結(jié)構(gòu)以及磁盤讀寫的工作機(jī)制。因?yàn)槊總€塊的平均位置相隔13道，故每次訪

問一個塊均需要單獨(dú)尋道，尋道以后等待旋轉(zhuǎn)到位，再讀寫。

10、在下列文件的物理結(jié)構(gòu)中，()不利于文件長度的動態(tài)增長。

A、連續(xù)結(jié)構(gòu)

B、鏈接結(jié)構(gòu)

C、索引結(jié)構(gòu)

D、哈希結(jié)構(gòu)

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

知識點(diǎn)解析：連續(xù)結(jié)構(gòu)不適合刪除和插入操作，即不利于文件的動態(tài)增長。

11、一個棧的入棧序列是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

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

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

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

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

部進(jìn)棧后再全部出棧”才能使數(shù)據(jù)倒置。事實(shí)上，存在一種操作序列——“進(jìn)棧、出

棧、進(jìn)棧、出棧……”——可以使數(shù)據(jù)通過棧后仍然保持次序不變。［解題技巧］將

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

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

的序號）的兩個元素。

12、一組記錄的關(guān)鍵字為{45,78,55,37,39,83},利用堆排序初始時的堆為

()o

A、78,45,55,37,39,83

B、83,78,55,37,39,45

C、83,78,55,45,39,37

D、83,55,78,39,45,37

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

知識點(diǎn)解析：縱觀四個選項(xiàng)可知，顯然題目要求建立一個大頂堆。按照建堆的過

程，先將序列構(gòu)造成一棵完全二叉樹，然后由最后一個非葉子結(jié)點(diǎn)開始，由下至上

調(diào)整使得其滿足堆的性質(zhì)，構(gòu)建過程如圖3-9所示。

圖3-9構(gòu)建堆

即堆排序初始時的堆的序列是83,78,55,37,39,45。

13、下列關(guān)于文件控制次的錯誤說法的個數(shù)為（）。I.文件控制塊就是文件目錄

項(xiàng)口.文件控制塊是在執(zhí)行open（打開）系統(tǒng)調(diào)用時建立的HI.一個文件可以對應(yīng)

有多個文件控制塊W.文件控制塊通常含有3類信息：基本信息、存取控制信息

及使用信息

A、1

B、2

C、3

D、4

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

知識點(diǎn)解析：文件控制塊與文件一一對應(yīng)（HI錯誤），創(chuàng)建文件時（create）建立對應(yīng)的

FCB,而不是打開文件時創(chuàng)建的（n錯誤）。人們把文件控制塊的有序集合稱為文件

目錄，即一個文件控制塊就是一個文件目錄項(xiàng)（I正確）。在文件控制塊中，通常含

有3類信息，即基本信息、存取控制信息及使用信息（W正確）。所以I,W正確，

n,in錯誤。錯誤的個數(shù)為2,所以選B。

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

n.ICMP被封裝在IP數(shù)據(jù)報(bào)的數(shù)據(jù)部分m.ICMP可用來進(jìn)行擁塞控制

A、僅I

B、I和n

C、口和皿

D、I和田

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

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

輸是不可靠的，故I錯浜。口：ICMP報(bào)文整個被作為IP分組的數(shù)據(jù)部分，所以

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

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

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

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

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

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

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

因?yàn)榍?個字節(jié)包含了TCP和UDP報(bào)文首部巾的TCP或UDP端口號，這樣源主

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

因?yàn)榘l(fā)送數(shù)據(jù)的是某個主機(jī)中的某個進(jìn)程而不足主機(jī)本身，這樣才算是真正找到了

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

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

報(bào)文。

15＞活動頭磁盤的尋道時間是指（）。

A、最大尋道時間

B、最小尋道時間

C、A、B之和

D、A、B的平均值

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

知識點(diǎn)解析：尋道時間又叫平均尋道時間，是指磁盤最大尋道時間和最小尋道時間

的平均值。

16、以下有關(guān)m階B?樹的說法中正確的有（）。I.每個結(jié)點(diǎn)至少有兩棵非空子樹

n.樹中每個結(jié)點(diǎn)至多有m-1個關(guān)鍵字ID.所有葉子在同一層上W.當(dāng)插入一個

數(shù)據(jù)項(xiàng)引起B(yǎng)—樹結(jié)點(diǎn)分裂后，樹長高一層

A、僅I、n

B、僅口、皿

C、僅川、IV

D、僅I、n、w

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

知識點(diǎn)解析：I中：m階B—樹根結(jié)點(diǎn)至少有兩棵子樹，并且這兩顆子樹可以是

空樹，其余結(jié)點(diǎn)至少有［m/2］個分支，即［m/2］個子樹，所以I錯誤。補(bǔ)充：B

一樹中每個結(jié)點(diǎn)至多有m棵子樹，m—l個關(guān)鍵字值。II中：每個結(jié)點(diǎn)中關(guān)鍵字

的個數(shù)比分支數(shù)少1,m階B一樹的一個結(jié)點(diǎn)中至多有m個分支，因此至多有

m—1個關(guān)鍵字，所以II正確。HI中：B一樹是平衡的多路查找樹，葉子結(jié)點(diǎn)均在

同一層上，所以HI正確。W中：發(fā)生結(jié)點(diǎn)分裂的時候不一定會使樹長高。比如向

圖4-9中的B—樹插入一個關(guān)鍵字10變成圖4—10中的B—樹，使得第二層右端

的一個結(jié)點(diǎn)分裂成兩個，但是樹并沒有長高，所以w錯誤。綜上所述，n、HI正

物人一個美孤字石的B科

17、如果二叉樹T2是由有序樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點(diǎn)的先序就是

T2中結(jié)點(diǎn)的（）。

A、先序

B、中序

C、后序

D、層次序

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

知識點(diǎn)解析：一般樹中一個結(jié)點(diǎn)的孩子是無序的，所謂有序樹是指樹中任一結(jié)點(diǎn)的

孩子是有序的。由樹轉(zhuǎn)換成二叉樹的過程可知本題答案為A。

18、指令（）從主存中讀出。

A、總是根據(jù)程序計(jì)數(shù)器（PC）

B、有時根據(jù)PC,有時根據(jù)轉(zhuǎn)移指令

C、根據(jù)地址寄存器

D、有時根據(jù)PC,有時根據(jù)地址寄存器

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

知識點(diǎn)解析：指令總是艱據(jù)程序計(jì)數(shù)器（PC）從主存中讀出（這一點(diǎn)一定要記住）。

可能考生會想到無條件轉(zhuǎn)移指令的情況，認(rèn)為不一定總是根據(jù)PC讀出。實(shí)際上，

正確的執(zhí)行順序是這樣的，當(dāng)前指令正在執(zhí)行時，其實(shí)PC已經(jīng)是下一條指令的地

址了，如果遇到了無條件轉(zhuǎn)移指令，則只需要簡單地把跳轉(zhuǎn)的地址覆蓋PC的內(nèi)容

就可以了，最終的結(jié)果還是指令需要根據(jù)PC從主存讀出。

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

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

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

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

D、連接被重新建立

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

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

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

20、在整數(shù)定點(diǎn)機(jī)中，下述（）說法是錯誤的。I.原碼和反碼不能表示-1,但是補(bǔ)

碼可以表示-In.原碼、反碼、補(bǔ)碼均可表示-In.補(bǔ)碼可以比原碼和反碼多表

示一個正數(shù)

A、僅I、五

B、僅口、m

C、僅u

D、僅I、n

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

知識點(diǎn)解析：I：在定點(diǎn)小望中，這句話斗正確的，但是題干是在定點(diǎn)整數(shù)中，故

原碼、反碼、補(bǔ)碼均可以表示分別表示為10000001、11111110、IIII11

11（假設(shè)字長為8,首位為符號位），故I錯誤。n：由I的分析可知，口正確。

n：補(bǔ)碼應(yīng)該是比原碼和反碼多表示一個負(fù)數(shù)，假設(shè)字長為8,首位為符號位，則

原碼和反碼的表示范圍為一127?127,而補(bǔ)碼的表示范圍為一128?127,故DI錯

誤。

21、高度為5（除葉子層之外）的三階B一樹至少有（）個結(jié)點(diǎn)。

A、30

B、31

C、32

D、33

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

知識點(diǎn)解析：由m階R一樹忤質(zhì)可知.根結(jié)點(diǎn)至少有兩棵子樹，根結(jié)點(diǎn)之外的所

有非終端結(jié)點(diǎn)至少有m/2棵子樹：則三階B一樹的形狀至少類似于一棵滿二叉

樹，也即高度為5的三階B一樹至少有05—1二）31個結(jié)點(diǎn)。

22、對地址轉(zhuǎn)換協(xié)議（ARP）描述正確的是（）。

A、ARP封裝在IP數(shù)據(jù)報(bào)的數(shù)據(jù)部分

B、ARP是采用廣播方式發(fā)送的

C、ARP是用于IP地址到域名的轉(zhuǎn)換

D、發(fā)送ARP包需要知道對方的MAC地址

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

知識點(diǎn)解析：本題考查ARP協(xié)議的原理，當(dāng)主機(jī)A要向本局域網(wǎng)上的某個主機(jī)B

發(fā)送1P數(shù)據(jù)報(bào)時，如果在其ARP高速緩存中查詢不到主機(jī)B的物理地址，這時

候ARP進(jìn)程就需要在本局域網(wǎng)上廣播發(fā)送一個ARP請求分組，所以ARP協(xié)議的

請求報(bào)文是廣播的，不是單播的，此時應(yīng)該是本局域網(wǎng)上的所有主機(jī)都可以收到此

ARP的請求分組，而主機(jī)B見到ARP分組中的IP地址是自己的IP時，就向主機(jī)

A發(fā)送一個ARP響應(yīng)分組，所以ARP響應(yīng)分組是普通的單播，一定注意ARP是

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

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

完成。同時ARP位于區(qū)絡(luò)層，并沒有和ICMP一樣封裝在IP數(shù)據(jù)報(bào)中，主要實(shí)現(xiàn)

IP地址和物理地址的轉(zhuǎn)換，因此，ARP報(bào)文在發(fā)送的時候并不知道對方的MAC地

址，因此答案是B。

23、對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左、右孩

子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，為實(shí)現(xiàn)

編號可采用的遍歷是（）。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、從根開始按層次遍歷

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

知識點(diǎn)解析：根據(jù)題意和先序、中序、后序遍歷規(guī)則，可簡單地判斷出正確答案。

24、已知一棵5階B-樹有53個關(guān)鍵字，并且每個結(jié)點(diǎn)的關(guān)鍵字都達(dá)到最少狀杰，

則它的深度是（）.

A、3

B、4

C、5

D、6

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

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

/2]=3個子樹，即至少有2個關(guān)鍵字。那么在每個結(jié)點(diǎn)的關(guān)鍵字最少的情況下，

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

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

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

故樹的深度為4。

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

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

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

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

A、僅I、n

B、僅口、皿、IV

c、僅I、nI、w

D、僅I、n、n

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

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

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

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

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

可得空指針域的個數(shù)為磁中所有結(jié)點(diǎn)個數(shù)加1,即n+1個。這個性質(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）nino推導(dǎo)過程如不：

總結(jié)點(diǎn)=no+ni+n2+n3+..+nm...........，①總分支數(shù)=lxni+2+n2+…+mxnm

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

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

充例題；在一棵二叉樹中度為0的結(jié)點(diǎn)個數(shù)為k,度為1的結(jié)點(diǎn)個數(shù)為m,則詼二

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

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

（多次用到，考生一定要記住！），得到1124一1。其次，二叉樹的結(jié)點(diǎn)總數(shù)

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

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

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

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

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

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

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

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

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

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

至少有一個結(jié)點(diǎn)，所以最少的結(jié)點(diǎn)個數(shù)二（2八一一1）+1=2心1故W錯誤。

26、現(xiàn)采用調(diào)相與調(diào)幅相結(jié)合的調(diào)制方式，載波有四種相位變化和兩種振幅變化,

調(diào)制速率是600波特，那么數(shù)據(jù)速率是（）。

A、1200bps

B、1800bps

C、2400bps

D、3600bps

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

知識點(diǎn)解析：本題考查奈奎斯特定理的應(yīng)用。這里載波有四種相位變化和兩種振幅

變化，也就是離散值為8,由奈奎斯特定理公式可得：2x600xlog28=3600bps,因

此答案是Do

27、一條線路帶寬為1Mbps,往返時延為45ms,假設(shè)數(shù)據(jù)幀的大小為1000字

節(jié)。若采用停一等協(xié)議，實(shí)際的數(shù)據(jù)率是()。

A、15Kbps

B、1.5Kbps

C、151Kbps

D、1510Kbps

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

知識點(diǎn)解析：往返時延為45ms,發(fā)送一幀的時間是8x1000*000000s。實(shí)際的數(shù)

據(jù)率是8x1000-(8x1000-1000000+45x0.001)=150943(bps)^151(Kbps)o

28、假設(shè)初始為空的散列表的地址空間為@..10),散列函數(shù)為H(key)=keymod

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

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

A、4

B、5

C、6

D、8

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

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

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

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

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

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

址為d,則平方探測法的探測序列為d+12,d」2,d+22,d_22.........位置4不空

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

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

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

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

29、將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點(diǎn)的完全三叉樹的高度

是()。

A、4

B、5

C、6

D、7

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

知識點(diǎn)解析：將二義樹的性質(zhì)4推廣到完全三叉樹即可得出正確答案。

30、在單處理機(jī)的多進(jìn)程系統(tǒng)中，進(jìn)程什么時候占用處理機(jī)以及決定占用時間的長

短是（）。

A、進(jìn)程相應(yīng)的代碼長度

B、進(jìn)程總共需要運(yùn)行的時間

C、進(jìn)程特點(diǎn)和進(jìn)程調(diào)度策略

D、進(jìn)程完成什么功能

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

知識點(diǎn)解析：本題考查進(jìn)程調(diào)度的時機(jī)和進(jìn)程調(diào)度的策略。進(jìn)程調(diào)度的時機(jī)與進(jìn)程

特點(diǎn)有關(guān)，例如進(jìn)程是CPU繁忙型還是I/O繁忙型，自身的優(yōu)先級等。但是僅有

這些特點(diǎn)是不夠的，能否得到調(diào)度還取決于進(jìn)程調(diào)度策略，若采用優(yōu)先級調(diào)度算

法，則進(jìn)程的優(yōu)先級才起作用。至于占用處理機(jī)運(yùn)行時間的長短，則要看進(jìn)程自

身，若進(jìn)程是I/O繁忙型，運(yùn)行過程中要頻繁訪問I/O,也就是說，可能會頻繁

主動放棄CPU,所以，占用CPU的時間就不會長，一旦放棄CPU,則必須等待下

次調(diào)度。若進(jìn)程是CPU繁忙型，則一旦占有CPU就可能會運(yùn)行很長時間，但是，

運(yùn)行時間還取決于進(jìn)程調(diào)度策略，大部分情況下，交互式系統(tǒng)為改善用戶的響應(yīng)時

間，大多采用時間片輪轉(zhuǎn)的算法，這種算法在進(jìn)程長期占用CPU到一定時間后，

會強(qiáng)制將其換下，以保證其他進(jìn)程的CPU使用權(quán)。所以，本題的正確答案應(yīng)為選

項(xiàng)C,其他都不是。

31、以下有關(guān)二叉樹的描述中正確的是（）。（1）二叉樹按某種右岸序線索化后，任

一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索（2）二義樹的前序遍歷序列中，任意一個結(jié)點(diǎn)

均處在其子女結(jié)點(diǎn)的前面

A、只有（1）

B、只有（2）

C、⑴和⑵

D、以上全不對

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

知識點(diǎn)解析；暫無解析

32、分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是（）。

A、界地址保護(hù)

B、程序代碼保護(hù)

C、數(shù)據(jù)保護(hù)

D、棧保護(hù)

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

知識點(diǎn)解析：界地址寄存器來保護(hù)內(nèi)存管理方式的主要措施。

33、已知一棵二叉樹的光序、中序、后序的部分序列如下，其中有些位置沒有給出

其值，則原二叉樹的中序遍歷序列為（）。先序：A_CDEF_H」中序：

C_EDA_GFI_后序：C_BHGJI_

A、CBEDAHGFIJ

B、CHEDABGFIJ

C、CBEDAJGFIH

D、CJEDAHGFIB

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

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

遍歷：I根I左子樹I右子樹I,中序遍歷：I左子樹I根I右子樹I,后序遍

歷：I左子樹I右子樹I根I,由題目中給出的先序序列的第一個結(jié)點(diǎn)我們找到樹

的根A,然后在中序序列中找到A,并以A為分界將中序序列劃分為IC_EDI

AI_GFI_I,所以C_ED為左子樹，_GFI_為右子樹，再對應(yīng)到后序遍歷序列上，

這里左子樹結(jié)點(diǎn)的個數(shù)等于中序遍歷序列中左子樹結(jié)點(diǎn)的個數(shù)，因此C__B為左

子樹，HGJL為右子樹，這樣把中序序列和后續(xù)序列中的左右子樹一對比，則

CBED為左子樹，F(xiàn)GHIJ為右子樹。答案選A。

34、在進(jìn)行域名解析的過程中，由（）獲取的解析結(jié)果耗時最短。

A、主域名服務(wù)器

B、輔域名服務(wù)器

C、緩存域名服務(wù)器

D、轉(zhuǎn)發(fā)域名服務(wù)器

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

知識點(diǎn)解析：緩存域名服務(wù)器是一種很特殊的DNS服務(wù)器，它本身并不管理任何

區(qū)域，但是DNS客戶端仍然可以向它請求查詢。緩存域名服務(wù)器類似于代理服務(wù)

器，它沒有自己的域名數(shù)據(jù)庫，而是將所有查詢轉(zhuǎn)發(fā)到其他DNS服務(wù)器處理。當(dāng)

緩存域名服務(wù)器從其他DNS服務(wù)器收到查詢結(jié)果后，除了返回給客戶端外，還會

將結(jié)果保存在緩存中。當(dāng)下一個DNS客戶端再查詢相同的域名數(shù)據(jù)時，就可以從

高速緩存里得到結(jié)果，從而加快對DNS客戶端的響應(yīng)速度。

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

含的結(jié)點(diǎn)數(shù)最少為（）。

A、100

B、201

C、199

D、200

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

知識點(diǎn)解析：考查二叉樹的特點(diǎn)。結(jié)點(diǎn)最少時的情況如下圖所示。除根結(jié)點(diǎn)層只有

1個結(jié)點(diǎn)外,其他各層均有兩個結(jié)點(diǎn),結(jié)點(diǎn)總數(shù)=2*（1007）+1=199。

36、當(dāng)（）時，進(jìn)程從執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。

A、進(jìn)程被調(diào)度程序選中

B、時間片到

C、等待某一事件

D、等待的事件發(fā)生

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

知識點(diǎn)解析：A：從就緒態(tài)到執(zhí)行狀態(tài)；C：從執(zhí)行狀態(tài)到阻塞狀態(tài)；D：從隹塞

狀態(tài)到就緒狀態(tài)。

37、系統(tǒng)“抖動”現(xiàn)象的發(fā)生是由（）引起的。

A、置換算法選擇不當(dāng)

B、交換的信息量過大

C、內(nèi)存容量不足

D、請求頁式管理方案

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

知識點(diǎn)解析：在請求分頁存儲管理中，從主存中剛剛移走某一頁面后，根據(jù)請求馬

上又調(diào)進(jìn)該頁，這種反復(fù)調(diào)進(jìn)調(diào)出的現(xiàn)象，稱為系統(tǒng)抖動。原因是調(diào)度的算法不科

學(xué)。系統(tǒng)抖動大大降低系統(tǒng)效率。

38、啟動磁盤執(zhí)行一次輸入/輸出操作時，（）是硬件設(shè)計(jì)時就固定的。

A、尋找時間

B、傳送時間

C、延遲時間

D、一次I/O操作的總時間

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

知識點(diǎn)解析：暫無解析

39、下面關(guān)于設(shè)備獨(dú)立性的論述中正確的是（）。

A、設(shè)備獨(dú)立性是指I/O設(shè)備具有獨(dú)立執(zhí)行I/O功能的一種特性

B、設(shè)備獨(dú)立性是指用戶程序獨(dú)立于具體使用的物理設(shè)備的一種特性

C、設(shè)備獨(dú)立性是指能獨(dú)立實(shí)現(xiàn)設(shè)備共享的一種特性

D、設(shè)備獨(dú)立性是指設(shè)各驅(qū)動程序獨(dú)立于具體使用的物理設(shè)備的一種特性

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

知識點(diǎn)解析：設(shè)備獨(dú)立性是指用戶不指定特定的設(shè)備，而指定邏輯設(shè)備，使得用戶

作業(yè)和物理設(shè)備獨(dú)立開來，再通過其他途徑建立邏輯設(shè)備和物理設(shè)備之間的對應(yīng)關(guān)

系的特性；即用戶程序獨(dú)立于具體使用的物理設(shè)備的一種特性。

40、對已知范圍矩形中的坐標(biāo)排序，數(shù)據(jù)量較大，要求先排橫坐標(biāo)，再排縱坐標(biāo)，

則應(yīng)選（）。

A、歸并排序

B、快速排序

C、堆排序

D、基數(shù)排序

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

知識點(diǎn)解析：暫無解析

二、綜合應(yīng)用題（本題共9題，每題7.0分，共9分0）

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

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

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

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

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

41、“ADDR2,R0”指令完成（R0）+（R2）-R0的功能操作，畫出其指令周期流程圖,

假設(shè)該指令的地址已放入PC