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

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

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

1、假設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度為()。void

fun(intn){inti,j?k；for(i=l;i<=n;i++)for(j=l;j<=n;j++){k=l；while(k<=n

k=5*k;}}

A、O(n2Iog2n)

O(nlog5n)

C、O(n-log5n)

D、O(n3)

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

知識(shí)點(diǎn)解析：首先抓基本運(yùn)算語(yǔ)句，即k=5*k：設(shè)其執(zhí)行時(shí)間為T(mén)(n)。對(duì)于j每循

環(huán)一次，該語(yǔ)句的執(zhí)行次數(shù)為m,有5msn,即mSbg5n。所以，

T(n)=^ni=?Xnj=1m=m￡ni=i^nj=i=mn2=n2log5n=0(n2log5n)

2、己知一個(gè)棧的進(jìn)棧序列是1、2、3、…、n,其輸出序列為pi、p2、P3、…、

Pn，若pi=3,則P2為()。

A、2或4、5、…、n都有可能

B、可能是1

C、一定是2

D、只可能是2或4

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

知識(shí)點(diǎn)解析：考查出入棧操作的性質(zhì)。當(dāng)P]=3,表示3最先出棧，前面1、2應(yīng)在

棧中，此時(shí)若出棧操作，則P2應(yīng)為2；此時(shí)若進(jìn)棧操作(進(jìn)棧1次或多次)，則P2為

4、5、…、n都有可能，故選A。

3、在具有n個(gè)頂點(diǎn)的圖G中，若最小生成樹(shù)不唯一，則()。I.G的邊數(shù)一定大

寸

一n.G的權(quán)值最小的邊一定有多條in.G的最小生成樹(shù)代價(jià)不一定相等

An-僅1

、I

B僅

、、

僅Im

c

、

僅、

DIn

、ni

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

知識(shí)點(diǎn)解析：最小生成棚邊的權(quán)值之和最小，若兩棵樹(shù)同時(shí)為最小生成樹(shù)，那么它

們的邊的權(quán)值之和一定相等，故山錯(cuò)誤；既然最小生成樹(shù)不唯一，并且最小生成樹(shù)

的邊都為n-1條，說(shuō)明圖G的邊數(shù)一定會(huì)大于n?l,故I正確；最小生成樹(shù)不唯

一，和G的權(quán)值最小的邊的條數(shù)沒(méi)有任何關(guān)系，故II錯(cuò)誤。

4、某機(jī)器采用16位單字長(zhǎng)指令，采用定長(zhǎng)操作碼，地址碼為5位，現(xiàn)已定義60

條二地址指令，那么單地址指令最多有（）條。

A、4

B、32

C、128

D、256

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

知識(shí)點(diǎn)解析：首先可以計(jì)算出操作碼字段的長(zhǎng)度為16-5?5=6。所以一共可以定義

26=64條指令，既然二地址指令占了60條，且是定長(zhǎng)操作碼，故單地址指令最多

可以有64-60=4條，所以選A。

5、某進(jìn)程代碼頁(yè)在頁(yè)框中固定不換出，數(shù)據(jù)頁(yè)在缺頁(yè)時(shí)換頁(yè)，每頁(yè)大小為4KB。

當(dāng)前正在執(zhí)行一條指令，其語(yǔ)義為：從數(shù)據(jù)頁(yè)讀四個(gè)字節(jié)并以此為地址從數(shù)據(jù)頁(yè)讀

另外4個(gè)字節(jié)到寄存器中，則缺頁(yè)次數(shù)最多是（）次。

A、1

B、2

C、3

D、4

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

知識(shí)點(diǎn)解析：每次讀取的4個(gè)字節(jié)可能不在同一頁(yè)中。

6、若子網(wǎng)掩碼為255.255.0.0,則下列（）IP與其他地址不在同一網(wǎng)絡(luò)中？

A、172.25.15.200

B、172.25.16.15

C、172.25.25.200

D、172.35.16.15

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

知識(shí)點(diǎn)解析：將子網(wǎng)掩碼與IP地址按位與，得A、B、C各IP地址所在的網(wǎng)絡(luò)號(hào)

為172.25.0.0；D中IP地址所在網(wǎng)絡(luò)號(hào)為172.35.0.0,故D中的IP地址與其

他地址不在同一個(gè)網(wǎng)絡(luò)中。一般對(duì)于這種求分別網(wǎng)絡(luò)號(hào)是否一樣的題目，只要抓住

IP地址從第幾個(gè)字段開(kāi)始不一樣，然后開(kāi)始將此字段按二進(jìn)制展開(kāi)，逐位與運(yùn)

算，這種方法幾乎在分析IP地址時(shí)都會(huì)用到。

7、下列關(guān)于TCP和UDP的描述正確的是（）.。

A、TCP和UDP都是無(wú)連接的

B、TCP是無(wú)連接的，UDP面向連接

C、TCP適用于可靠性較差的廣域網(wǎng)，UDP適用于可靠性較高的局域網(wǎng)

D、TCP適用于可靠性較高的局域網(wǎng)，UDP適用于可靠性較差的廣域網(wǎng)

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

知識(shí)點(diǎn)解析：TCP是面向連接的，UDP是無(wú)連接的，所以A、B均錯(cuò)。由于TCP

面向連接，所以可用于可靠性較差的廣域網(wǎng)，而UDP是無(wú)連接的，適用于可靠性

較高的局域網(wǎng)。故D錯(cuò)，選C。

8、DNS服務(wù)器在名稱解析過(guò)程中正確的查詢順序是（）。

A、本地緩存記錄一區(qū)域記錄-轉(zhuǎn)發(fā)域名服務(wù)器一根域名服務(wù)器

B、區(qū)域記錄一本地緩存記錄一＞轉(zhuǎn)發(fā)域名服務(wù)器一＞根域名服務(wù)器

C、本地緩存記錄一區(qū)域記錄一根域名服務(wù)器一轉(zhuǎn)發(fā)域名服務(wù)器

D、區(qū)域記錄一本地緩存記錄一＞根域名服務(wù)器一轉(zhuǎn)發(fā)域名服務(wù)器

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

知識(shí)點(diǎn)解析：本題考查DNS域名解析的工作過(guò)程，具體步驟如下：（1）客戶機(jī)提交

域名解析請(qǐng)求，并將該請(qǐng)求發(fā)送給本地的域名服務(wù)器；（2）當(dāng)本地的域名服務(wù)器收

到請(qǐng)求后，就先查詢本地的緩存。如果有查詢的DNS信息記錄，則直接返回查詢

的結(jié)果。如果沒(méi)有該記錄，本地域名服務(wù)器就把請(qǐng)求發(fā)給根域名服務(wù)器；（3）根域

名服務(wù)器再返回給本地域名服務(wù)器一個(gè)所查詢域的頂級(jí)域名服務(wù)器的地址；（4）本

地服務(wù)器再向返回的域名服務(wù)器發(fā)送請(qǐng)求；（5）接收到該查詢請(qǐng)求的域名服務(wù)器查

詢其緩存和記錄，如果有相關(guān)信息則返回本地域名服務(wù)器查詢結(jié)果，否則通知本地

域名服務(wù)器下級(jí)的域名服務(wù)器的地址；（6）本地域名服務(wù)器將查詢請(qǐng)求發(fā)送給下級(jí)

的域名服務(wù)器的地址，直到獲取查詢結(jié)果；（7）本地域名服務(wù)器將返回的結(jié)果保存

到緩存，并且將結(jié)果返回給客戶機(jī)，完成解析過(guò)程。因此本題答案是C。

9、進(jìn)程創(chuàng)建的時(shí)候，不需要做的是（）。

A、填寫(xiě)一個(gè)該進(jìn)程的進(jìn)程表項(xiàng)

B、分配該進(jìn)程適當(dāng)?shù)膬?nèi)存

C、將該進(jìn)程插入就緒隊(duì)列

D、為該進(jìn)程分配CPU

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

知識(shí)點(diǎn)解析：本題考查的是進(jìn)程創(chuàng)建的過(guò)程「進(jìn)程創(chuàng)建最主要的T.作是為該進(jìn)程申

請(qǐng)并填寫(xiě)一張進(jìn)程表。進(jìn)程表內(nèi)包含有多個(gè)與進(jìn)程有關(guān)的數(shù)據(jù)結(jié)構(gòu)，例如進(jìn)程號(hào)、

進(jìn)程組、進(jìn)程的優(yōu)先級(jí)、進(jìn)程所分配的內(nèi)存、進(jìn)程需耍的10設(shè)備、進(jìn)程要打開(kāi)的

文件等。當(dāng)填寫(xiě)好了進(jìn)程表以后，進(jìn)程創(chuàng)建模塊就將進(jìn)程表按照該系統(tǒng)規(guī)定的法

則，將進(jìn)程表插入到就緒隊(duì)列的適當(dāng)位置，等待進(jìn)程調(diào)度模塊進(jìn)行下一步的調(diào)度。

所以進(jìn)程創(chuàng)建的過(guò)程中不會(huì)包含分配CPU的過(guò)程，這不是進(jìn)程創(chuàng)建者的工作。

10、考慮一個(gè)由4個(gè)進(jìn)程和1個(gè)單獨(dú)資源組成的系統(tǒng)，當(dāng)前的最大需求矩陣和分配

矩陣如下:對(duì)于安全狀態(tài)，需要的最小資源數(shù)目是（）。

A、1

B、2

C、3

D、5

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

知識(shí)點(diǎn)解析：依次用Pl?P4來(lái)表示4個(gè)進(jìn)程。從矩陣可以看出，4個(gè)進(jìn)程還需要

的資源數(shù)目為（2,1,6,5）,按所需資源數(shù)目從小到大排列，即P2、Pl、P4、

P3o這就是所需最小資源數(shù)目的執(zhí)行順序。設(shè)有x個(gè)可用資源。當(dāng)x多時(shí)，P2可

以執(zhí)行完成，并釋放占用資源，此時(shí)資源數(shù)為x+1。當(dāng)X+1N2時(shí)，P1可以執(zhí)行完

成，并釋放占用資源，此時(shí)資源數(shù)為x+2。當(dāng)x+225時(shí)，P4可以執(zhí)行完成，并釋

放占用資源，此時(shí)資源數(shù)為x+4。當(dāng)x+4次時(shí)，P3可以執(zhí)行完成，并釋放占月資

源，此時(shí)資源數(shù)為（忽略）。剩下的，就是解這個(gè)簡(jiǎn)單的方程組，得出e3。按這種

方法做題，可以比較有壬握不算錯(cuò)，也利于檢查。

11、在線索化二叉樹(shù)中，t所指結(jié)點(diǎn)沒(méi)有左子樹(shù)的充要條件是（）。

A、t->left=NULL

B、t—>ltag=l

C、t—>llag=l且l—>left=NULL

D、以上都不對(duì)

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

知識(shí)點(diǎn)解析：線索二叉樹(shù)中某結(jié)點(diǎn)是否有左孩子，不能通過(guò)左指制域是否為空來(lái)判

斷，而要判斷左標(biāo)志是否為1。

12、分頁(yè)管理方式中的頁(yè)面是為（）。

A、用戶所感知的

B、操作系統(tǒng)所感知的

C、編譯系統(tǒng)所感知的

D、連接裝配系統(tǒng)程序所感知的

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

知識(shí)點(diǎn)解析：頁(yè)面信息是由操作系統(tǒng)管理的C

13、虛擬頁(yè)式存儲(chǔ)管理中，CPU必須具備必要的物理硬件的支持，而不是必需的

單元是（）。

A、缺頁(yè)中斷機(jī)構(gòu)

B、地址加法器

C、cache

D、地址寄存器

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

知識(shí)點(diǎn)。析：在虛擬頁(yè)式存儲(chǔ)管理中，除了有主存和輔存以外，為滿足虛擬技術(shù)，

CPU還需要有缺頁(yè)中斷機(jī)制；為滿足頁(yè)式存儲(chǔ)管理，CPU中需要有地址加法器和

地址寄存器來(lái)計(jì)算頁(yè)表到頁(yè)框的映射，而cache并不是必需的，因?yàn)閏ache的存在

只是提高了CPU尋址的效率，并不是虛擬頁(yè)式存儲(chǔ)技術(shù)的重要單元，缺少cache,

CPU每次執(zhí)行一個(gè)雙字的指令（以32位為例）或取一個(gè)數(shù)據(jù)均需要二次訪問(wèn)內(nèi)存，

當(dāng)然這是很不利的，可能會(huì)實(shí)際上造成虛擬頁(yè)式的使用障礙。增加了cache,使得

虛擬頁(yè)式存儲(chǔ)技術(shù)的實(shí)際使用提供了方便。

14、TCP的滑動(dòng)窗口協(xié)漢中規(guī)定重傳分組的數(shù)量最多可以是（）。

A、任意的

B、1個(gè)

C、大于滑動(dòng)窗口的大小

D、等于滑動(dòng)窗口的大小

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

知識(shí)點(diǎn)解析：TCP滑動(dòng)窗口協(xié)議中發(fā)送方滑動(dòng)窗口的大小規(guī)定了發(fā)送方最多能夠

傳送的分組的數(shù)目，只有窗口滑動(dòng)了，才能往后繼續(xù)發(fā)送。分組的重傳也是發(fā)送方

數(shù)據(jù)的發(fā)送，因而重傳分組的數(shù)量最多也不超過(guò)滑動(dòng)窗口的大小，答案是D。

15、散列表的地址范圍為0—17,散列函數(shù)為:H（k）=kmod17.采用線性探測(cè)法處

理沖突，將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到散列表中。元素59存放在

散列表中的地址是（）。

A、8

B、9

C,10

D、11

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

知識(shí)點(diǎn)解析：考查散列表的構(gòu)造過(guò)程。任何散列函數(shù)都不可能絕對(duì)的避免沖突，因

此采用合理的沖突處理方法，為沖突的關(guān)鍵字尋找下一個(gè)“空”位置。將前面各元素

分別放入散列表中，其中8、9、10的位置分別存放25、26、8o元素59經(jīng)過(guò)哈希

函數(shù)計(jì)算應(yīng)該存入位置59mod17=8,發(fā)生沖突，采用線性探測(cè)再散列，一依次比

較9、10、11,發(fā)現(xiàn)II為空，所以將其放入地址11中。各關(guān)鍵字對(duì)應(yīng)的散列地址

見(jiàn)下表。

關(guān)?字2625723881859

散列地址9844818

16、設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，ai,］為

第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，則as,5的地址是（）。

A、13

B、33

C、18

D、40

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

知識(shí)點(diǎn)解析：這里數(shù)組下標(biāo)從1開(kāi)始，只存儲(chǔ)其下三角形元素，在ag.5的前面有7

行，第1行有1個(gè)元素，第2行有2個(gè)元素，…，第7行有7個(gè)元素，這7行共有

(1+7)x7/2=28個(gè)元素，在第8行中，as，5的前面有4個(gè)元素，所以，a8,5前有

28+4=32個(gè)元素，其地址為33。

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

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

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

()0

A、100—R0

B、100—MDR

C、PJMAR

D、PC—IR

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

知識(shí)點(diǎn)解析：無(wú)論運(yùn)行葉么類型的指令，CPU首先需要取指令，取指令階段的第

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

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

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

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

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

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

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

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

18、某計(jì)算機(jī)采用微程序控制，微指令中操作控制字段共12位，若采用直接控

制，則此時(shí)一條微指令最多可同時(shí)啟動(dòng)()個(gè)操作。若采用字段直接編碼控制，并要

求一條微指令需要同時(shí)啟動(dòng)3個(gè)微操作，則指令中的操作控制字段應(yīng)分()段，若每

個(gè)字段的微指令數(shù)相同，這樣的微指令格式最多可包含()個(gè)微操作指令。

A、12；6；24

B、12；6；18

C、12；4；24

D、12；4；18

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

知識(shí)點(diǎn)解析：直接控制中每一位對(duì)應(yīng)一個(gè)微操作，故能最多同時(shí)啟動(dòng)12個(gè)微操

作；在字段直接編碼控制中，每段的長(zhǎng)度為N,則可表示的微操作的個(gè)數(shù)為

因?yàn)橐粭l微指令需啟動(dòng)3個(gè)微操作，故至少需要兩位，所以操作控制字段應(yīng)分為

12/2=6段；現(xiàn)在每個(gè)字段占2位，則最多能表示3條微指令(根據(jù)字段直接編碼的

要求要留出一位表示空操作)，則最多可以包含18個(gè)微操作指令。

19、若用100個(gè)雙字(字長(zhǎng)32位)組成的位示圖管理內(nèi)存，假定用戶歸還一個(gè)塊號(hào)

為240的內(nèi)存塊時(shí)，它對(duì)應(yīng)的位示圖的位置是()。

A、字號(hào)為6,位號(hào)為16

B、字號(hào)為7,位號(hào)為16

C、字號(hào)為6,位號(hào)為14

D、字號(hào)為7,位號(hào)為14

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

知識(shí)點(diǎn)解析：位示圖也禰為示位圖，是利用二進(jìn)制的一位來(lái)表示內(nèi)存或磁盤(pán)中一個(gè)

存儲(chǔ)塊的使用情況。當(dāng)其值為“0”時(shí)，表示對(duì)應(yīng)的塊空閑；為力”時(shí)，表示己分配。

反之亦然。內(nèi)存或磁盤(pán)上的所有塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)，這樣，由所有塊所

對(duì)應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。計(jì)算方法：字號(hào)i=INT(240/32)=7字內(nèi)位

置上=\10口(240/32)=16

2。、在平均往返時(shí)間Rfl為20ms的快速以太網(wǎng)上運(yùn)行TCP/IP協(xié)議，假設(shè)1CP的

最大窗口尺寸為64KB,問(wèn)此時(shí)TCP協(xié)議所能支持的最大數(shù)據(jù)傳輸率是()。

A、3.2Mbit/s

B、12.8Mbit7s

C、25.6Mbit/s

D、51.2Mbit/s

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

知識(shí)點(diǎn)解析：因?yàn)門(mén)CP；IP的最大窗口尺寸/數(shù)據(jù)傳輸率之往返時(shí)間RTT,即

64x8xl03/C>20xl0—3,所以C<(64x8x103)/(20x10—3)=25.6Mbit/S.補(bǔ)充：在運(yùn)行

CSMA/CD的以太網(wǎng)，，發(fā)送的時(shí)延必須要大于等于平均往返時(shí)延RTT,這樣才能

及時(shí)監(jiān)測(cè)到是否與其他站點(diǎn)發(fā)生沖突，這樣就能及時(shí)停止發(fā)送保證所傳輸?shù)臄?shù)據(jù)的

完整性和正確性。

21、如果主機(jī)A要向處于同一子網(wǎng)段的主機(jī)B(IP地址為172.16.204.89/16)

發(fā)送一個(gè)分組，那么主孔A使用的“這個(gè)網(wǎng)絡(luò)上的特定主機(jī)”的地址為()。

A、172.16.255.255

B、172.16.204.255

C、0.0.255.255

D、0.0.204.89

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

知識(shí)點(diǎn)解析：當(dāng)一臺(tái)主機(jī)或一臺(tái)路由器向本網(wǎng)絡(luò)的某臺(tái)特定的主機(jī)發(fā)送一個(gè)分組

時(shí)，它需要使用“這個(gè)網(wǎng)絡(luò)上的特定主機(jī)”地址。該分組被限制在本網(wǎng)內(nèi)部，由主機(jī)

號(hào)對(duì)應(yīng)的主機(jī)接收。例如，主機(jī)A要向處于同一子網(wǎng)段的主機(jī)B(IP地址為

172.16.204.89/16)發(fā)送一個(gè)分組，由于172.16.204.89/16是一個(gè)B類IP地址，

“/16”是子網(wǎng)掩碼255.255.0.0的簡(jiǎn)寫(xiě)形式，該B類IP地址的網(wǎng)絡(luò)號(hào)為“172.16”、主

機(jī)號(hào)為“204.89”，所以主機(jī)A使用的“這個(gè)網(wǎng)絡(luò)上的特定主機(jī)”的地址為

0.0.204.89。補(bǔ)充知識(shí)點(diǎn)：這個(gè)網(wǎng)絡(luò)上的特定主機(jī)。具有全。的網(wǎng)絡(luò)號(hào)的IP地址表

示在這個(gè)網(wǎng)絡(luò)上的特定主機(jī)，用于當(dāng)某個(gè)主機(jī)向同一網(wǎng)絡(luò)上的其他主機(jī)發(fā)送報(bào)文。

因?yàn)榉纸M被路由器擋住了，所以這是把分組限制在本地網(wǎng)絡(luò)上的一種方法。還應(yīng)注

意到，實(shí)際上這是一個(gè)A類地址而不管是什么網(wǎng)絡(luò)類型，如圖3—15所示。

個(gè)網(wǎng)絡(luò)上的特定上機(jī)發(fā)送報(bào)文

圖3?15這個(gè)網(wǎng)絡(luò)上的特定主機(jī)

22、假設(shè)某硬盤(pán)由5個(gè)盤(pán)片構(gòu)成（共有8個(gè)記錄面），盤(pán)面有效記錄區(qū)域的外直徑為

30厘米，內(nèi)直徑為10厘米，記錄位密度為250位/毫米，磁道密度為16道/毫

米，每磁道分16個(gè)扇區(qū)，每扇區(qū)512字節(jié)，則該硬盤(pán)的格式化容量約是（）。

A8x<3Q-1（DX1OX25OX】6MRr8X（30-10）X10Xl$X］6乂5】2m打

*8X1024X1024,2X1024X1024

8X（30—10）X10X250X16X16、p8」（3。-10〉X16X16X512.”

rj8X1024X1024Dn2X1024X10240

A、

B、

c、

D、

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

知識(shí)點(diǎn)解析：格式化容量計(jì)算中根據(jù)扇區(qū)數(shù)和扇區(qū)容量計(jì)算出每條磁道上的信息

量，然后再乘以總磁道數(shù)。而總磁道數(shù)計(jì)算時(shí)，首先求出每面磁道數(shù)（柱面數(shù)）：再

乘以記錄面數(shù)。［歸納總結(jié)］磁盤(pán)的容量有格式化容量與非格式化容量之分，磁盤(pán)上

標(biāo)稱的容量為格式化容量。計(jì)算磁盤(pán)容量公式中的總磁道數(shù)是指記錄面數(shù)與圓柱面

數(shù)的乘積。其中柱面數(shù)的計(jì)算公式為：柱面數(shù)=（外半徑一內(nèi)半徑）x道密度格式化

容量是磁盤(pán)實(shí)際可以使用的容量。新的磁盤(pán)在使用之前需要先進(jìn)行格式化，格式化

實(shí)際上就是在磁盤(pán)上劃分記錄區(qū)，寫(xiě)入各種標(biāo)志信息和地址信息。這些信息占用了

磁盤(pán)的存儲(chǔ)空間，故格式化之后的有效存儲(chǔ)容量要小于非格式化容量。它的計(jì)算公

式為：格式化容量=每道扇區(qū)數(shù)x扇區(qū)容量x總磁道數(shù)［解題技巧1計(jì)算格式化容量

時(shí)只與道密度有關(guān)，而與位密度沒(méi)有關(guān)系，所以選項(xiàng)A和C都是錯(cuò)誤的，而選項(xiàng)

B擴(kuò)大了一個(gè)10倍。

23、下列情況下，可能不發(fā)生中斷請(qǐng)求的是（）。

A、DMA操作結(jié)束

B、一條指令執(zhí)行完畢

C、機(jī)器出現(xiàn)故障

D、執(zhí)行“軟中斷”指令

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

知識(shí)點(diǎn)解析：在4個(gè)選項(xiàng)中，唯有選項(xiàng)B為正確答案，因?yàn)椴⒎敲織l指令執(zhí)行完

畢都會(huì)產(chǎn)生中斷請(qǐng)求。

24、若存儲(chǔ)周期100內(nèi)秒，每次讀出一個(gè)字節(jié)，則該存儲(chǔ)器的數(shù)據(jù)傳輸率為()。

A、32xl()6位/秒

B、8xl()6位/秒

C、80Mb/秒

D、80xl()6位/秒

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

知識(shí)之解由于存儲(chǔ)周期100ns,每次讀出一個(gè)字節(jié)，則數(shù)據(jù)傳輸率=8/

(100*103=80*1()6位/秒。選項(xiàng)c的錯(cuò)誤在于存在誤差，1M=1O24*1O24。

25、當(dāng)圖像分辨率為800x600,屏幕分辨率為640x480時(shí)，正確的是()。

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

B、圖像正好占滿屏幕

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

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

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

知識(shí)點(diǎn)解析：屏幕分辨率的行、列像素?cái)?shù)分別是圖像分辨率的80%,所以屏幕上

只能顯示這幅圖像的64%。

26、有一個(gè)文件含有■10000個(gè)文件塊，若將其順序結(jié)構(gòu)存放，則對(duì)文件塊順序查找

的平均時(shí)間為5000個(gè)單位。若按索引順序文件的結(jié)構(gòu)存放，每個(gè)索引為100個(gè)文

件塊，則順序查找次數(shù)是()。

A、500

B、100

C、50

D^10

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

知識(shí)點(diǎn)解析：本題考查的是文件的邏輯結(jié)構(gòu)。順序文件在按順序查找文件內(nèi)容時(shí)，

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

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

次)。當(dāng)采用索引順序文件時(shí)，文件的內(nèi)容已經(jīng)按照索引的關(guān)鍵詞排好了序(例如按

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

題中以100個(gè)一組，所以分成10000:100=100組，按順序查找法，查找這100組

平均需要100：2=50次，找到以后在組內(nèi)繼續(xù)查找，平均需要100"=50次，所以

共需要50+50=100次,

27、設(shè)一棵二叉樹(shù)是由森林轉(zhuǎn)換而來(lái)的，若森林中有n個(gè)非終端結(jié)點(diǎn)，則二叉樹(shù)中

無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)為()。

ANn-I

n

C、n+l

D^n+2

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

知識(shí)點(diǎn)解析：首先，對(duì)于一棵樹(shù)來(lái)講，每個(gè)非終端結(jié)點(diǎn)（除了樹(shù)的根結(jié)點(diǎn)）轉(zhuǎn)換成

二叉樹(shù)后都對(duì)應(yīng)一個(gè)無(wú)右孩子的結(jié)點(diǎn)，因?yàn)橐粋€(gè)非終端結(jié)點(diǎn)至少有一個(gè)孩子結(jié)點(diǎn)，

其最右邊的孩子結(jié)點(diǎn)轉(zhuǎn)疾成二義樹(shù)后一定沒(méi)有右孩子。為什么要除去根結(jié)點(diǎn)？因?yàn)?/p>

根結(jié)點(diǎn)比較特殊，樹(shù)轉(zhuǎn)爽成二叉樹(shù)之后，根結(jié)點(diǎn)本身也將會(huì)沒(méi)有右孩子。所以對(duì)于

一棵具有n個(gè)非終端結(jié)點(diǎn)的樹(shù)來(lái)講，將其轉(zhuǎn)換成二叉樹(shù)之后，二叉樹(shù)中無(wú)右孩子的

結(jié)點(diǎn)個(gè)數(shù)為n+l個(gè)。其實(shí)，此時(shí)已經(jīng)可以選出答案了，因?yàn)橐豢脴?shù)也可以算是一

個(gè)森林。如果一個(gè)森林有多棵樹(shù)（假設(shè)有x棵），我們先把所有樹(shù)的根結(jié)點(diǎn)拿出

來(lái)。除根結(jié)點(diǎn)之外的非終端結(jié)點(diǎn)（n—x個(gè)）轉(zhuǎn)換成二叉樹(shù)之后都是對(duì)應(yīng)一個(gè)無(wú)右

孩子的結(jié)點(diǎn)，可得到n—x個(gè)無(wú)右孩子的結(jié)點(diǎn)。但是，x個(gè)根結(jié)點(diǎn)是不是就對(duì)應(yīng)2x

個(gè)無(wú)右孩子的結(jié)點(diǎn)？顯然不是，因?yàn)橄乱豢脭?shù)將會(huì)成為上一棵樹(shù)根結(jié)點(diǎn)的右孩子

（見(jiàn)圖5—3）,所以只有森林的最后一棵樹(shù)的根結(jié)點(diǎn)才會(huì)變成無(wú)右孩子的結(jié)點(diǎn)，

故x個(gè)根結(jié)點(diǎn)將會(huì)得到x+1個(gè)無(wú)右孩子的根結(jié)點(diǎn)，所以一共可以得到n-

x+（x+l）=n+l個(gè)無(wú)右孩子的根結(jié)點(diǎn)。

圖5.3森林轉(zhuǎn)換成二叉樹(shù)

從圖5—3可以看出，三棵樹(shù)的根結(jié)點(diǎn)A、E、G轉(zhuǎn)換成二叉樹(shù)之后，只有最后一棵

樹(shù)的根結(jié)點(diǎn)G是沒(méi)有右孩子的"綜上分析，二叉樹(shù)中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)為n+l

個(gè)，故選C選項(xiàng)。解題技巧：使用特殊值代入法，如圖5-4所示。

■）1個(gè)非終端結(jié)點(diǎn)bR個(gè)無(wú)右孩子結(jié)點(diǎn)

圖5Y示例圖

可以從圖5-4中很直觀地看出無(wú)右孩了結(jié)

點(diǎn)比非終端結(jié)點(diǎn)多1。補(bǔ)充例題：設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B,它有m個(gè)結(jié)點(diǎn)，B

的根為p,p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（）。A.m—

nB.m—n—1C.n+lD.條件不足，無(wú)法確定解析：由轉(zhuǎn)換規(guī)則可知，二叉樹(shù)中

除了左子樹(shù)和根結(jié)點(diǎn)來(lái)源于原森林中第一棵樹(shù)，其余結(jié)點(diǎn)來(lái)源于森林中的其他樹(shù),

其他樹(shù)的結(jié)點(diǎn)總數(shù)為n,則第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為m—n,故選A選項(xiàng)。

28、計(jì)算機(jī)在進(jìn)行浮點(diǎn)數(shù)的相加(減)運(yùn)算之前先進(jìn)行對(duì)階操作，若x的階碼大于y

的階碼，則應(yīng)將()。

A、x的階碼縮小至與y的階碼相同，且使x的尾數(shù)部分進(jìn)行算術(shù)左移

B、x的階碼縮小至與y的階碼相同，且使x的尾數(shù)部分進(jìn)行算術(shù)右移

C、y的階碼擴(kuò)大至與x的階碼相同，且使y的尾數(shù)部分進(jìn)行算術(shù)左移

D、y的階碼擴(kuò)大至與x的階碼相同，且使y的尾數(shù)部分進(jìn)行算術(shù)右移

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

知識(shí)點(diǎn)解析：在浮點(diǎn)數(shù)加減運(yùn)算時(shí)，首先要進(jìn)行對(duì)階，根據(jù)對(duì)階的規(guī)則，階碼和尾

數(shù)將進(jìn)行相應(yīng)的操作。［歸納總結(jié)］要對(duì)階，首先應(yīng)求出兩數(shù)階碼Ex和之差，即

△E=Ex=Ey若△￡=(),表示兩數(shù)階碼相等，即Ex=Ey；若△￡>(),表示Ex>Ey；

若△￡<(),表示ExVEy。當(dāng)ExrEy時(shí)，要通過(guò)尾數(shù)的移位來(lái)改變Ex或Ey,使Ex=

Ey相等。對(duì)階的規(guī)則是：小階向大階看齊。即階碼小的數(shù)的尾數(shù)右移，每右移一

位，階碼加1,直到兩數(shù)的階碼相等為止。如：EX=Ey,無(wú)需對(duì)階。Ex>Ey,則

My右移。每右移一位，Ey+1-Ey,直至Ex=Ey為止。Exy,則M、右移。每右移

一位，Ex+l->Ex,直至Ex=Ey為止。

29、前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為()。

A、只有根結(jié)點(diǎn)的二叉樹(shù)

B、根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)

C、根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)

D、所有結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)

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

知識(shí)點(diǎn)解析：使用特值法，排除B、C、D選項(xiàng)。

30、下列二叉排序樹(shù)中，滿足平衡二叉樹(shù)定義的是()。

C、

o

D、D

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

知識(shí)點(diǎn)解析：暫無(wú)解析

31、UDP協(xié)議和TCPI辦議報(bào)文首部的非共同字段有（）。

A、源端口

B、目的端口

C、序列號(hào)

D、校驗(yàn)和

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

知識(shí)點(diǎn)解析：本題考查UDP和TCP報(bào)文格式的區(qū)別。需要理解記憶。UDP和

TCP作為傳輸層協(xié)議，源/目的端口（復(fù)用和分用）和校驗(yàn)和字段是必須有的。由于

UDP僅提供盡最大努力的交付服務(wù)，不保證數(shù)據(jù)按序到達(dá)，。因此不需要序列號(hào)

字段，而TCP的可靠傳輸機(jī)制需要設(shè)置序列號(hào)字段。UDP數(shù)據(jù)報(bào)首部包括偽首

部、源端II、目的端II、長(zhǎng)度和校驗(yàn)和；TCP首部包括源端II、目的端口、序

號(hào)、確認(rèn)號(hào)、數(shù)據(jù)偏移、URG、ACK、PSH、RST、SYN、FIN、窗口、校驗(yàn)和、

緊急指針。源端口、目的端口和校驗(yàn)和兩者都有，所以A、B、D錯(cuò)誤；TCP首部

有序列號(hào)而UDP沒(méi)有，答案選C。

32、下列說(shuō)法中，錯(cuò)誤的是（）。I.假設(shè)幀序號(hào)有3位，采用連續(xù)ARQ協(xié)議，發(fā)

送窗口的最大值為4n.對(duì)于窗口大小為n的滑動(dòng)窗口，最多可以有n幀已發(fā)送但

沒(méi)有確認(rèn)HI.在后退N幀協(xié)議中，如果發(fā)送窗口的大小是16,那么至少需要4位

的序列號(hào)才能保證協(xié)議不出錯(cuò)

A、僅I、n

B、僅皿

c、僅u、m

D、I、口、in

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

知識(shí)點(diǎn)解析?：I:連續(xù)ARQ協(xié)議包括后退N幀協(xié)議和選擇重傳協(xié)議。如果幀序號(hào)

為3位，當(dāng)采用后退N幀協(xié)議時(shí)，發(fā)送窗口的最大值為23—1=7；當(dāng)采用選擇重

傳協(xié)議時(shí)，發(fā)送窗口的最大值為23—匕4,故I錯(cuò)誤?？冢涸谶B續(xù)ARQ協(xié)議中，如

果總的窗口大小為n,發(fā)送窗口的大小最大為n—1（當(dāng)采用后退N幀協(xié)議時(shí)可以達(dá)

到）。例如：假設(shè)窗口大小為8（0?7）,如果發(fā)送窗口大小為8,則當(dāng)。?7號(hào)幀都

發(fā)出去時(shí)，接收方已經(jīng)收到了，并且發(fā)出確認(rèn)。但是發(fā)送方卻沒(méi)有收到確認(rèn)，導(dǎo)致

0?7號(hào)幀超時(shí)重傳，而此時(shí)接收方就判斷不出這個(gè)是重傳的還是新一輪的幀，導(dǎo)

致錯(cuò)誤，故D錯(cuò)誤。注意：有的考生認(rèn)為窗口就是發(fā)送窗口。其實(shí)窗口和發(fā)送窗

口是不一樣的。假設(shè)幀序號(hào)為n,則窗口大小為2＜而發(fā)送窗口只能在[1,2n-l]

內(nèi)取值，否則將會(huì)出錯(cuò)。m：首先需要清楚后退N幀協(xié)議的最大發(fā)送窗U為211-

1（其中n為幀號(hào)的位數(shù)），題目中已經(jīng)說(shuō)明發(fā)送窗口的大小為16,也就是說(shuō)如果

要使得協(xié)議不出錯(cuò)，必須滿足16s2門(mén)一1,所以n至少要等于5,故DI錯(cuò)誤。

33、下列關(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、僅江、IV

B、僅U、IV

c、僅I、m、w

D、僅I、口、W

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

知識(shí)點(diǎn)解析：一棵m階B+樹(shù)滿足下列條件。①每個(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ī)檢索。綜上所述，可知

口、IV正確，I、IE錯(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/2］<n<m,根結(jié)點(diǎn)n的取值范圍是2<n<m；而在B

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

l<n<m—1,根結(jié)點(diǎn)n的取值范圍是l<n<m—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ì)有指針相

連。

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

、?.??一、??

FDT（文竹IIM&iFAT（文處配置

…FATffl

A002000FFD

口003001FFF

002004

_________________

…???003OOH

004009

_________________

005007

006FFF

007FFF

0M006

009oos

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)表1=1中找到文件存放的下一個(gè)簇號(hào)，依此類推，直至

遇到值為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->l->10->25o如果指針占用4B,對(duì)于盤(pán)塊大小為512B的磁盤(pán)，則每個(gè)盤(pán)

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

地存放在內(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)。

35、下列說(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、僅u、m

c、僅I、m

D、I、口、HI

標(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

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

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

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

36、某操作系統(tǒng)的文件管理采用直接索引和多級(jí)索引混合方式，文件索引表共有

10項(xiàng)，其中前8項(xiàng)是直接索引項(xiàng)，第9項(xiàng)是一次間接索引項(xiàng)，第10項(xiàng)是二次間接

索引項(xiàng)，假定物理塊的大小是1K,每個(gè)索引項(xiàng)占用4個(gè)字節(jié)，則該文件系統(tǒng)口最

大的文件可以達(dá)到（）。

A、65800K

B、65792K

C、65536K

D、34000K

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

知識(shí)點(diǎn)解析：多級(jí)索引的邏輯并不復(fù)雜，本題中一級(jí)間接索引表有256張，二級(jí)間

接索引表最多有256張，計(jì)算時(shí)加以仔細(xì)小心，一般不會(huì)有太多變化，但是對(duì)多級(jí)

索引的方法一定要掌握。直接索引為8xlK=8K,一級(jí)間接索引為（1K/4B）X1

K=256K；二級(jí)間接索引為（1K/4B）X（1K/4B）X1K=65536K。共計(jì)

65536K+25K+8K=65800K

37、一個(gè)C語(yǔ)言程序在一臺(tái)32位機(jī)器上運(yùn)行。程序中定義了三個(gè)變量x、y和z,

其中x和z是int型，y為short型。當(dāng)x=127,y=-9時(shí)，執(zhí)行賦值語(yǔ)句z=x+y后，

x、y和z的值分別是（）。

A、x=0000007FH,y=FFF9H,z=00000076H

B、x=0000007FH,產(chǎn)FFF9H,z=FFFF0076H

C、x=0000007FH,y=FFF7H,z=FFFF0076H

D、x=0000007FH,y=FFF7H,z=00000076H

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

知識(shí)點(diǎn)解析：結(jié)合題干及選項(xiàng)可知，int為32位，short為16位；又C語(yǔ)言的整型

數(shù)據(jù)在內(nèi)存中為補(bǔ)碼形式，故x、y的機(jī)器數(shù)寫(xiě)為十六進(jìn)制為0000007FH、

FFF7H；執(zhí)行z=x+y時(shí)，由于x為ini型，y為short型，故需將y的類型強(qiáng)制轉(zhuǎn)換

為int,在機(jī)器中通過(guò)符號(hào)位擴(kuò)展實(shí)現(xiàn)，由于y的符號(hào)位為1,故在y的前面添加

16個(gè)1,即可將y強(qiáng)制轉(zhuǎn)換為int型，其十六進(jìn)制形式為FFFFFFF7H；然后執(zhí)行加

法，即0000007FH+FFFFFFF7H=00000076H（最高位的進(jìn)位1自然丟棄）。故選D。

38、以卜有關(guān)拓?fù)渑判虻恼f(shuō)法中，錯(cuò)誤的是（）。I.如果某有向圖存在環(huán)路，則

該有向圖一定不存在拓?fù)渑判蚩?在拓?fù)渑判蛩惴ㄖ?，既可以使用棧，也可以?/p>

用隊(duì)列HI.若有向圖的拓?fù)溆行蛐蛄形ㄒ?，則圖中每個(gè)頂點(diǎn)的入度和出度最多為1

A、僅I、m

B、僅口、m

C、僅口

D、僅ni

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

知識(shí)點(diǎn)解析：I:如果一個(gè)有向圖存在環(huán)路，則肯定不會(huì)存在拓?fù)渑判?，因?yàn)樵摥h(huán)

路找不到入度為0的結(jié)點(diǎn)，拓?fù)渑判蜃匀灰簿瓦M(jìn)行不下去了，故I正確。n：使用

棧來(lái)表示拓?fù)渑判虻男蛄?，最后的出棧序列是逆拓?fù)渑判?，只需逆轉(zhuǎn)過(guò)來(lái)即可，只

是效率比較低；使用隊(duì)列時(shí)，出隊(duì)序列就是拓?fù)渑判蛐蛄?，故使用棧和?duì)列都是可

以的，只是效率不等而已，故口正確。皿一個(gè)反例如圖8—9所示。該圖的拓?fù)?/p>

有序序列是唯一的，但各個(gè)頂點(diǎn)的入度和出度可以超出1,故HI錯(cuò)誤。

圖8-9反例

39、已知一棵完全二叉礴的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹(shù)的

結(jié)點(diǎn)個(gè)數(shù)最多是（）。

A、39

B、52

C、111

D、119

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

知識(shí)點(diǎn)解析：暫無(wú)解析

40、使Cache命中率最高的替換算法是（）。

A、先進(jìn)先出算法FIFO

B、隨機(jī)算法RAND

C、先進(jìn)后出算法FILO

D、最近最少使用算法LRU

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

知識(shí)點(diǎn)解析：理想頁(yè)面置換算法是每次調(diào)換出的頁(yè)面是所有內(nèi)存頁(yè)面中最遲將被使

用的，可惜的是這種算法是無(wú)法實(shí)現(xiàn)的。為了盡量減少與理想算法的差距產(chǎn)生了最

近最少未使用頁(yè)面置換算法，它是基于這樣一個(gè)事實(shí)：在前面幾條指令中使用頻繁

的頁(yè)面很可能在后面的幾條指令中頻繁使用。反過(guò)來(lái)說(shuō)，已經(jīng)很久沒(méi)有使用的頁(yè)面

很可能在未來(lái)較長(zhǎng)的一段時(shí)間內(nèi)不會(huì)被用到。這就是著名的局部性原理一一比內(nèi)存

速度還要快的Cache,乜是基于同樣的原理運(yùn)行的,

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

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

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

存器，ALU由加、減控制信號(hào)決定完成何種操作，控制信號(hào)G控制的是一個(gè)門(mén)電

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

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

A危線

i666A6iiAA