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

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

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

1、假設n是描述問題規(guī)模的非負整數，下面程序片段的時間復雜度為()。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)

標準答案：C

知識點解析：首先抓基本運算語句，即k=5*k：設其執(zhí)行時間為T(n)。對于j每循

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

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

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

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

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

B、可能是1

C、一定是2

D、只可能是2或4

標準答案：A

知識點解析：考查出入棧操作的性質。當P]=3,表示3最先出棧，前面1、2應在

棧中，此時若出棧操作，則P2應為2；此時若進棧操作(進棧1次或多次)，則P2為

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

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

寸

一n.G的權值最小的邊一定有多條in.G的最小生成樹代價不一定相等

An-僅1

、I

B僅

、、

僅Im

c

、

僅、

DIn

、ni

標準答案：A

知識點解析：最小生成棚邊的權值之和最小，若兩棵樹同時為最小生成樹，那么它

們的邊的權值之和一定相等，故山錯誤；既然最小生成樹不唯一，并且最小生成樹

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

一，和G的權值最小的邊的條數沒有任何關系，故II錯誤。

4、某機器采用16位單字長指令，采用定長操作碼，地址碼為5位，現已定義60

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

A、4

B、32

C、128

D、256

標準答案：A

知識點解析：首先可以計算出操作碼字段的長度為16-5?5=6。所以一共可以定義

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

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

5、某進程代碼頁在頁框中固定不換出，數據頁在缺頁時換頁，每頁大小為4KB。

當前正在執(zhí)行一條指令，其語義為：從數據頁讀四個字節(jié)并以此為地址從數據頁讀

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

A、1

B、2

C、3

D、4

標準答案：D

知識點解析：每次讀取的4個字節(jié)可能不在同一頁中。

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

A、172.25.15.200

B、172.25.16.15

C、172.25.25.200

D、172.35.16.15

標準答案：D

知識點解析：將子網掩碼與IP地址按位與，得A、B、C各IP地址所在的網絡號

為172.25.0.0；D中IP地址所在網絡號為172.35.0.0,故D中的IP地址與其

他地址不在同一個網絡中。一般對于這種求分別網絡號是否一樣的題目，只要抓住

IP地址從第幾個字段開始不一樣，然后開始將此字段按二進制展開，逐位與運

算，這種方法幾乎在分析IP地址時都會用到。

7、下列關于TCP和UDP的描述正確的是（）.。

A、TCP和UDP都是無連接的

B、TCP是無連接的，UDP面向連接

C、TCP適用于可靠性較差的廣域網，UDP適用于可靠性較高的局域網

D、TCP適用于可靠性較高的局域網，UDP適用于可靠性較差的廣域網

標準答案：C

知識點解析：TCP是面向連接的，UDP是無連接的，所以A、B均錯。由于TCP

面向連接，所以可用于可靠性較差的廣域網，而UDP是無連接的，適用于可靠性

較高的局域網。故D錯，選C。

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

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

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

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

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

標準答案：C

知識點解析：本題考查DNS域名解析的工作過程，具體步驟如下：（1）客戶機提交

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

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

的結果。如果沒有該記錄，本地域名服務器就把請求發(fā)給根域名服務器；（3）根域

名服務器再返回給本地域名服務器一個所查詢域的頂級域名服務器的地址；（4）本

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

詢其緩存和記錄，如果有相關信息則返回本地域名服務器查詢結果，否則通知本地

域名服務器下級的域名服務器的地址；（6）本地域名服務器將查詢請求發(fā)送給下級

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

到緩存，并且將結果返回給客戶機，完成解析過程。因此本題答案是C。

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

A、填寫一個該進程的進程表項

B、分配該進程適當的內存

C、將該進程插入就緒隊列

D、為該進程分配CPU

標準答案：D

知識點解析：本題考查的是進程創(chuàng)建的過程「進程創(chuàng)建最主要的T.作是為該進程申

請并填寫一張進程表。進程表內包含有多個與進程有關的數據結構，例如進程號、

進程組、進程的優(yōu)先級、進程所分配的內存、進程需耍的10設備、進程要打開的

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

則，將進程表插入到就緒隊列的適當位置，等待進程調度模塊進行下一步的調度。

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

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

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

A、1

B、2

C、3

D、5

標準答案：C

知識點解析：依次用Pl?P4來表示4個進程。從矩陣可以看出，4個進程還需要

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

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

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

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

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

源，此時資源數為（忽略）。剩下的，就是解這個簡單的方程組，得出e3。按這種

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

11、在線索化二叉樹中，t所指結點沒有左子樹的充要條件是（）。

A、t->left=NULL

B、t—>ltag=l

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

D、以上都不對

標準答案：B

知識點解析：線索二叉樹中某結點是否有左孩子，不能通過左指制域是否為空來判

斷，而要判斷左標志是否為1。

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

A、用戶所感知的

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

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

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

標準答案：B

知識點解析：頁面信息是由操作系統(tǒng)管理的C

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

單元是（）。

A、缺頁中斷機構

B、地址加法器

C、cache

D、地址寄存器

標準答案：c

知識點。析：在虛擬頁式存儲管理中，除了有主存和輔存以外，為滿足虛擬技術，

CPU還需要有缺頁中斷機制；為滿足頁式存儲管理，CPU中需要有地址加法器和

地址寄存器來計算頁表到頁框的映射，而cache并不是必需的，因為cache的存在

只是提高了CPU尋址的效率，并不是虛擬頁式存儲技術的重要單元，缺少cache,

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

當然這是很不利的，可能會實際上造成虛擬頁式的使用障礙。增加了cache,使得

虛擬頁式存儲技術的實際使用提供了方便。

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

A、任意的

B、1個

C、大于滑動窗口的大小

D、等于滑動窗口的大小

標準答案：D

知識點解析：TCP滑動窗口協議中發(fā)送方滑動窗口的大小規(guī)定了發(fā)送方最多能夠

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

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

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

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

散列表中的地址是（）。

A、8

B、9

C,10

D、11

標準答案：D

知識點解析：考查散列表的構造過程。任何散列函數都不可能絕對的避免沖突，因

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

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

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

較9、10、11,發(fā)現II為空，所以將其放入地址11中。各關鍵字對應的散列地址

見下表。

關?字2625723881859

散列地址9844818

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

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

A、13

B、33

C、18

D、40

標準答案：B

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

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

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

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

17、在計算機體系結構中，cPU內部包括程序計數器PC、存儲器數據寄存器

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

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

()0

A、100—R0

B、100—MDR

C、PJMAR

D、PC—IR

標準答案：c

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

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

總結］取指周期完成的微操作序列是公共的操作，與具體指令無關，取指公操伶如

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

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

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

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

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

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

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

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

求一條微指令需要同時啟動3個微操作，則指令中的操作控制字段應分()段，若每

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

A、12；6；24

B、12；6；18

C、12；4；24

D、12；4；18

標準答案：B

知識點解析：直接控制中每一位對應一個微操作，故能最多同時啟動12個微操

作；在字段直接編碼控制中，每段的長度為N,則可表示的微操作的個數為

因為一條微指令需啟動3個微操作，故至少需要兩位，所以操作控制字段應分為

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

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

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

為240的內存塊時，它對應的位示圖的位置是()。

A、字號為6,位號為16

B、字號為7,位號為16

C、字號為6,位號為14

D、字號為7,位號為14

標準答案：B

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

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

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

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

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

2。、在平均往返時間Rfl為20ms的快速以太網上運行TCP/IP協議，假設1CP的

最大窗口尺寸為64KB,問此時TCP協議所能支持的最大數據傳輸率是()。

A、3.2Mbit/s

B、12.8Mbit7s

C、25.6Mbit/s

D、51.2Mbit/s

標準答案：D

知識點解析：因為TCP；IP的最大窗口尺寸/數據傳輸率之往返時間RTT,即

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

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

及時監(jiān)測到是否與其他站點發(fā)生沖突，這樣就能及時停止發(fā)送保證所傳輸的數據的

完整性和正確性。

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

發(fā)送一個分組，那么主孔A使用的“這個網絡上的特定主機”的地址為()。

A、172.16.255.255

B、172.16.204.255

C、0.0.255.255

D、0.0.204.89

標準答案：D

知識點解析：當一臺主機或一臺路由器向本網絡的某臺特定的主機發(fā)送一個分組

時，它需要使用“這個網絡上的特定主機”地址。該分組被限制在本網內部，由主機

號對應的主機接收。例如，主機A要向處于同一子網段的主機B(IP地址為

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

“/16”是子網掩碼255.255.0.0的簡寫形式，該B類IP地址的網絡號為“172.16”、主

機號為“204.89”，所以主機A使用的“這個網絡上的特定主機”的地址為

0.0.204.89。補充知識點：這個網絡上的特定主機。具有全。的網絡號的IP地址表

示在這個網絡上的特定主機，用于當某個主機向同一網絡上的其他主機發(fā)送報文。

因為分組被路由器擋住了，所以這是把分組限制在本地網絡上的一種方法。還應注

意到，實際上這是一個A類地址而不管是什么網絡類型，如圖3—15所示。

個網絡上的特定上機發(fā)送報文

圖3?15這個網絡上的特定主機

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

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

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

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、

標準答案：D

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

量，然后再乘以總磁道數。而總磁道數計算時，首先求出每面磁道數（柱面數）：再

乘以記錄面數。［歸納總結］磁盤的容量有格式化容量與非格式化容量之分，磁盤上

標稱的容量為格式化容量。計算磁盤容量公式中的總磁道數是指記錄面數與圓柱面

數的乘積。其中柱面數的計算公式為：柱面數=（外半徑一內半徑）x道密度格式化

容量是磁盤實際可以使用的容量。新的磁盤在使用之前需要先進行格式化，格式化

實際上就是在磁盤上劃分記錄區(qū)，寫入各種標志信息和地址信息。這些信息占用了

磁盤的存儲空間，故格式化之后的有效存儲容量要小于非格式化容量。它的計算公

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

時只與道密度有關，而與位密度沒有關系，所以選項A和C都是錯誤的，而選項

B擴大了一個10倍。

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

A、DMA操作結束

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

C、機器出現故障

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

標準答案：B

知識點解析：在4個選項中，唯有選項B為正確答案，因為并非每條指令執(zhí)行完

畢都會產生中斷請求。

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

A、32xl()6位/秒

B、8xl()6位/秒

C、80Mb/秒

D、80xl()6位/秒

標準答案：D

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

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

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

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

B、圖像正好占滿屏幕

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

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

標準答案：A

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

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

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

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

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

A、500

B、100

C、50

D^10

標準答案：B

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

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

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

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

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

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

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

共需要50+50=100次,

27、設一棵二叉樹是由森林轉換而來的，若森林中有n個非終端結點，則二叉樹中

無右孩子的結點個數為()。

ANn-I

n

C、n+l

D^n+2

標準答案：C

知識點解析：首先，對于一棵樹來講，每個非終端結點（除了樹的根結點）轉換成

二叉樹后都對應一個無右孩子的結點，因為一個非終端結點至少有一個孩子結點，

其最右邊的孩子結點轉疾成二義樹后一定沒有右孩子。為什么要除去根結點？因為

根結點比較特殊，樹轉爽成二叉樹之后，根結點本身也將會沒有右孩子。所以對于

一棵具有n個非終端結點的樹來講，將其轉換成二叉樹之后，二叉樹中無右孩子的

結點個數為n+l個。其實，此時已經可以選出答案了，因為一棵樹也可以算是一

個森林。如果一個森林有多棵樹（假設有x棵），我們先把所有樹的根結點拿出

來。除根結點之外的非終端結點（n—x個）轉換成二叉樹之后都是對應一個無右

孩子的結點，可得到n—x個無右孩子的結點。但是，x個根結點是不是就對應2x

個無右孩子的結點？顯然不是，因為下一棵數將會成為上一棵樹根結點的右孩子

（見圖5—3）,所以只有森林的最后一棵樹的根結點才會變成無右孩子的結點，

故x個根結點將會得到x+1個無右孩子的根結點，所以一共可以得到n-

x+（x+l）=n+l個無右孩子的根結點。

圖5.3森林轉換成二叉樹

從圖5—3可以看出，三棵樹的根結點A、E、G轉換成二叉樹之后，只有最后一棵

樹的根結點G是沒有右孩子的"綜上分析，二叉樹中無右孩子的結點個數為n+l

個，故選C選項。解題技巧：使用特殊值代入法，如圖5-4所示。

■）1個非終端結點bR個無右孩子結點

圖5Y示例圖

可以從圖5-4中很直觀地看出無右孩了結

點比非終端結點多1。補充例題：設森林F對應的二叉樹為B,它有m個結點，B

的根為p,p的右子樹結點個數為n,森林F中第一棵樹的結點個數是（）。A.m—

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

除了左子樹和根結點來源于原森林中第一棵樹，其余結點來源于森林中的其他樹,

其他樹的結點總數為n,則第一棵樹的結點個數為m—n,故選A選項。

28、計算機在進行浮點數的相加(減)運算之前先進行對階操作，若x的階碼大于y

的階碼，則應將()。

A、x的階碼縮小至與y的階碼相同，且使x的尾數部分進行算術左移

B、x的階碼縮小至與y的階碼相同，且使x的尾數部分進行算術右移

C、y的階碼擴大至與x的階碼相同，且使y的尾數部分進行算術左移

D、y的階碼擴大至與x的階碼相同，且使y的尾數部分進行算術右移

標準答案：D

知識點解析：在浮點數加減運算時，首先要進行對階，根據對階的規(guī)則，階碼和尾

數將進行相應的操作。［歸納總結］要對階，首先應求出兩數階碼Ex和之差，即

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

若△￡<(),表示ExVEy。當ExrEy時，要通過尾數的移位來改變Ex或Ey,使Ex=

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

位，階碼加1,直到兩數的階碼相等為止。如：EX=Ey,無需對階。Ex>Ey,則

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

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

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

A、只有根結點的二叉樹

B、根結點無左孩子的二叉樹

C、根結點無右孩子的二叉樹

D、所有結點只有左子樹的二叉樹

標準答案：A

知識點解析：使用特值法，排除B、C、D選項。

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

C、

o

D、D

標準答案：B

知識點解析：暫無解析

31、UDP協議和TCPI辦議報文首部的非共同字段有（）。

A、源端口

B、目的端口

C、序列號

D、校驗和

標準答案：C

知識點解析：本題考查UDP和TCP報文格式的區(qū)別。需要理解記憶。UDP和

TCP作為傳輸層協議，源/目的端口（復用和分用）和校驗和字段是必須有的。由于

UDP僅提供盡最大努力的交付服務，不保證數據按序到達，。因此不需要序列號

字段，而TCP的可靠傳輸機制需要設置序列號字段。UDP數據報首部包括偽首

部、源端II、目的端II、長度和校驗和；TCP首部包括源端II、目的端口、序

號、確認號、數據偏移、URG、ACK、PSH、RST、SYN、FIN、窗口、校驗和、

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

有序列號而UDP沒有，答案選C。

32、下列說法中，錯誤的是（）。I.假設幀序號有3位，采用連續(xù)ARQ協議，發(fā)

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

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

的序列號才能保證協議不出錯

A、僅I、n

B、僅皿

c、僅u、m

D、I、口、in

標準答案：D

知識點解析?：I:連續(xù)ARQ協議包括后退N幀協議和選擇重傳協議。如果幀序號

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

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

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

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

發(fā)出去時，接收方已經收到了，并且發(fā)出確認。但是發(fā)送方卻沒有收到確認，導致

0?7號幀超時重傳，而此時接收方就判斷不出這個是重傳的還是新一輪的幀，導

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

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

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

1（其中n為幀號的位數），題目中已經說明發(fā)送窗口的大小為16,也就是說如果

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

33、下列關于m階B+樹的說法中，正確的是（）。I.具有n個關鍵字的結點至少

含有n+1棵子樹D.所有葉子結點包含全部關鍵字HI.B+樹支持隨機索引

IV.B+樹可用于文件的索引結構

A、僅江、IV

B、僅U、IV

c、僅I、m、w

D、僅I、口、W

標準答案：B

知識點解析：一棵m階B+樹滿足下列條件。①每個分支結點至多有m棵子樹。

②根結點或者沒有子樹，或者至少有兩棵子樹。③除根結點外，其他每個分支結

點至少有［m/2］棵子樹。④具有n個關鍵字的結點含有n棵子樹。⑤所有葉子結

點包含傘部關鍵字及指向相應記錄的指針，而且葉子結點按關鍵字的大小順序鏈

接。⑥所有分支結點中僅包含它的各個子結點中最大關鍵字及指向子結點的指

針。⑦B+樹中，所有非終端結點可以看成是索引部分，故可用于文件的索引結

構。注意：由于B+樹為鏈式存儲結構，因此不支持隨機檢索。綜上所述，可知

口、IV正確，I、IE錯誤，故B選項正確。補充知識點：很多考生被B+樹和B-

樹的基本概念弄混，下面做一個小結。提示：m階B+樹和m階B-樹的主要差異

如下。①在B+樹中，具有n個關鍵字的結點含有n棵子樹；而在B-樹中，具有n

個關鍵字的結點至少含有（n+1）棵子樹。②在B+樹中，每個結點（除根結點外）中的

關鍵字個數n的取值范圍是［m/2］<n<m,根結點n的取值范圍是2<n<m；而在B

一樹中，除根結點外，其他所有非葉子結點的關鍵字個數n的取值范圍是［m/2］-

l<n<m—1,根結點n的取值范圍是l<n<m—1。記憶方式：“B一”中有個“一”

號，自然關鍵字個數相對于B+減掉了1。③在B+樹中，所有葉子結點包含了全

部關鍵字，即其他非葉子結點中的關鍵字包含在葉子結點中：而在B—樹中，關

鍵字是不重復的。④在B+樹中，所有非葉子結點僅僅是起到了索引的作用，即結

點中的每個索引項只含有對應子樹的最大關鍵字和指向子樹的指針，不含有該關鍵

字對應記錄的存儲地址。而在B一樹中，每個關鍵字對應一個記錄的存儲地址。

⑤在B+樹上有兩個頭指針，一個指向根結點，另一個指向關鍵字最小的葉子結

點，所有葉子結點鏈接成一個鏈表；而在B一樹中，葉子結點并不會有指針相

連。

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

、?.??一、??

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

標準答案：c

知識點.帚：當查找文件在磁盤上的存放地址時，先從目錄中找到文件的起始簇

號，然后再到FAT表的相應表1=1中找到文件存放的下一個簇號，依此類推，直至

遇到值為FFF的表項為止。文件A在磁盤上占用5簇，簇號依次為002、004、

009、005、007o文件B在磁盤上占用3簇，簇號依此為003、008、006。知識點

回顧：鏈接分配中每個文件對應一個盤塊的鏈表，盤塊分布在磁盤的任何地方。

鏈接方式可分為隱式鏈接和顯示鏈接兩種。隱式鏈接：在文件目錄的每個目錄項

中，都必須含有指向鏈援文件第一個盤塊和最后一個盤塊的指針。例如，目錄表中

有一個目錄項為（jeep,9,25）,表示jeep文件的第一個盤塊號是9,最后一個盤塊

號是25,而在每個盤塊中都含有一個指向下一個盤塊的指針，如

9->16->l->10->25o如果指針占用4B,對于盤塊大小為512B的磁盤，則每個盤

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

地存放在內存的一張鏈接表中。該表在整個磁盤僅設置一張。表的序號是物理盤塊

號，從0開始，直到N—1,其中N為盤塊總數。在每個表項中存放鏈接指針，

即下一個盤塊號。

35、下列說法中，錯誤的是（）。I.時鐘頻率和CPI成反比關系U.數據字長等

于MDR的位數HI.A主機的CPU主頻高于B主機的CPU主頻，則前者運算能力

將會高于后者

A、僅I、n

B、僅u、m

c、僅I、m

D、I、口、HI

標準答案：D

知識點解析：I：時鐘頻率和CPI并無關系。時鐘頻率的提高僅僅是將時鐘周期

縮短，并沒有改變執(zhí)行一條指令所需要的時鐘周期數，故I錯誤。n：—般來講，

MDR的位數和存儲字長相等，而數據字長是一次存取數據的長度，可以和MDR

不相等，故II錯誤。n：CPU的主頻是表示在CPU內數字脈沖信號震蕩的次數，

是衡量CPU運算速度的重要參數，但不是唯一的參數。故不能直接根據主頻來比

較運算能力，故in錯誤。

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

10項，其中前8項是直接索引項，第9項是一次間接索引項，第10項是二次間接

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

大的文件可以達到（）。

A、65800K

B、65792K

C、65536K

D、34000K

標準答案：A

知識點解析：多級索引的邏輯并不復雜，本題中一級間接索引表有256張，二級間

接索引表最多有256張，計算時加以仔細小心，一般不會有太多變化，但是對多級

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

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

65536K+25K+8K=65800K

37、一個C語言程序在一臺32位機器上運行。程序中定義了三個變量x、y和z,

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

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

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

B、x=0000007FH,產FFF9H,z=FFFF0076H

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

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

標準答案：D

知識點解析：結合題干及選項可知，int為32位，short為16位；又C語言的整型

數據在內存中為補碼形式，故x、y的機器數寫為十六進制為0000007FH、

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

為int,在機器中通過符號位擴展實現，由于y的符號位為1,故在y的前面添加

16個1,即可將y強制轉換為int型，其十六進制形式為FFFFFFF7H；然后執(zhí)行加

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

38、以卜有關拓撲排序的說法中，錯誤的是（）。I.如果某有向圖存在環(huán)路，則

該有向圖一定不存在拓撲排序口.在拓撲排序算法中，既可以使用棧，也可以使

用隊列HI.若有向圖的拓撲有序序列唯一，則圖中每個頂點的入度和出度最多為1

A、僅I、m

B、僅口、m

C、僅口

D、僅ni

標準答案：D

知識點解析：I:如果一個有向圖存在環(huán)路，則肯定不會存在拓撲排序，因為該環(huán)

路找不到入度為0的結點，拓撲排序自然也就進行不下去了，故I正確。n：使用

棧來表示拓撲排序的序列，最后的出棧序列是逆拓撲排序，只需逆轉過來即可，只

是效率比較低；使用隊列時，出隊序列就是拓撲排序序列，故使用棧和隊列都是可

以的，只是效率不等而已，故口正確。皿一個反例如圖8—9所示。該圖的拓撲

有序序列是唯一的，但各個頂點的入度和出度可以超出1,故HI錯誤。

圖8-9反例

39、已知一棵完全二叉礴的第6層（設根為第1層）有8個葉結點，則完全二叉樹的

結點個數最多是（）。

A、39

B、52

C、111

D、119

標準答案：C

知識點解析：暫無解析

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

A、先進先出算法FIFO

B、隨機算法RAND

C、先進后出算法FILO

D、最近最少使用算法LRU

標準答案：D

知識點解析：理想頁面置換算法是每次調換出的頁面是所有內存頁面中最遲將被使

用的，可惜的是這種算法是無法實現的。為了盡量減少與理想算法的差距產生了最

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

的頁面很可能在后面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面

很可能在未來較長的一段時間內不會被用到。這就是著名的局部性原理一一比內存

速度還要快的Cache,乜是基于同樣的原理運行的,

二、綜合應用題（本題共9題，每題1.0分，共9分0）

下圖所示為雙總線結構雙器的數據通路，IR為指令寄存器，PC為程序計數器（具有

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

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

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

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

A危線

i666A6iiAA