計算機專業(基礎綜合)模擬試卷56

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

1、若某線性表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一

個結點，則下面最合適的存儲方式是()。

A、單鏈表

B、循環雙鏈表

C、單循環鏈表

D、帶有尾指針的單循環鏈表

標準答案：B

知識點解析：在鏈表中的最后一個結點之后插入一個結點要知道終端結點的地址，

所以，單鏈表、單循環鏈表都不合適，刪除最后一個結點要知道終端結點的前驅結

點的地址，所以，帶有尾指針的單循環鏈表不合適，而循環雙鏈表滿足條件。

2、表長為n的順序存儲的線性表，當在任何位置上刪除一個元素的概率相等時，

刪除一個元素所需移動元素的平均個數為()。

A、n

B、n/2

C、(n-l)/2

D、(n+l)/2

標準答案：C

知識點解析：順序表的刪除運算的時間主要消耗在了移動表中元素上，刪除第i個

元素時，其后面的元素5+]?an都要向上移動一個位置，共移動了n?i個元素。在

等概率情況下,即pi=l/n,則:

E&==Zp.(n-i)=~(n—i)=n?

Gn仁2這說明順序表上作刪除運算時大

約需要移動表中一半的元素，顯然該算法的時間復雜度為O(n)。

3、在下面的應用中，通常使用棧的是()。I遞歸調用II括號匹配m表達式求

值

A、I、口

R、n、m

c、i、皿

D、i>n>HI

標準答案：D

知識點解析：這類問題一般都先分析題目中的數據是具有“先進后出''還是"先進先

出''特性，再判斷其邏輯結構為棧或者隊列。

4、用鏈表方式存儲的隊列，在進行刪除運算時，下面正確的是（）。

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

D、頭、尾指針可能都要修改

標準答案：D

知識點解析：鏈隊列中刪除元素一般僅修改隊頭指針，但只有一個元素時，出隊后

隊空，此時還要修改隊尾指針。

5、在含有15個結點的平衡二叉樹上，查找關鍵字為28（存在該結點）的結點，則依

次比較的關鍵字有可能是（）。

A、30,36

B、38,48,28

C、48,18,38,28

D、60,30,50,40,38,36

標準答案：C

知識點解析：設Nh表示深度為h的平衡二叉樹中含有的最少結點數，有No=O

N）=lN2=2...Nh=Nh-i+Nh-2+lNh=4,N4=7,N5=I2,N6=20>15o也就是說，高

度為6的平衡二叉樹的最少有20個結點，因此15個結點的平衡二叉樹的高度為

5,而最小葉子結點的層數為3,所以選項D錯誤。而A和B的查找過程不能構成

二叉排序樹，因而A、B錯誤。

6、設樹T的度為4,其中度為1,2,3和4的結點個數分別為4,2,1,1,則T

中的葉子數是（）。

A、5

B、6

C、7

D、8

標準答案：D

知識點解析：由二叉樹性質的推廣，度為4的樹應該有l+n2+2n3+3n4個葉結點g

表示度為i的結點數目），與度為1的結點的個數無關。因此，如果用no表示葉結

點的個數，則應該有no=l+2+2xl+3xl=8。

7、簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲\若無向圖G有n個

結點，其鄰接矩陣為A[l..n,1.?n],且壓縮存儲在B[l..n（n-l）/2]o若按

行壓縮存儲對稱矩陣的上三角元素，則當n等于10時，邊（v6,v3）的信息存儲在

（）。

A、B[18]

B、B|19]

C、B[20]

D、B[21]

標準答案：C

知識點解析：邊(v6,v3)與邊(v3,v3)是同一條邊。原第i行第j列元素在矩陣

B(上三角形式)中的下標為：(n-l)+(n-2)+…+(n-(i-l))+(j-i)。本題中將數值代入，

(10-l)+(10-2)+(6-3)-20o所以邊(v6,v3)的信息存儲在B[20]中。

8、以下關于圖的說法正確的是()。I在一個有向圖的拓撲序列中，若頂點a在

頂點b之前，則圖中必有一條弧<a,若一個有向圖的鄰接矩陣中對角線以下

元素均為0,則該圖的拓撲序列必定存在m在AOE網中一定只有一條關鍵路徑

A、I、n

B、口、DI

C、I、皿

D、僅有n

標準答案：D

知識點解析：說法工是錯誤的，在一個有向圖的拓撲序列中，若頂點a在頂點b之

前，只能說明頂點a到頂點b有一條路徑。說法ID是錯誤的，AOE網中可能有不

止一條關鍵路徑，它們的路徑長度相同。說法II是正確的。任意n個頂點的有向

無環圖都可以得到一個拓撲序列。設拓撲序列為vc，vi，Vn-l，證明此時的鄰

接矩陣A為上三角矩陣，可用反證法證明。假設此時的鄰接矩陣不是上三角矩

陣，那么，存在下標i和j(i>j),使得A[U[j]不等于0,即圖中存在從增到黨的一

條有向邊。由拓撲序列的定義可知，在任意拓撲序列中，號的位置一定在Vj之

前，而上述拓撲序列vo,vi，…，vn.l中，由于i>j，即％的位置在Vj之后，導致

矛盾。因此說法II是正確的。

9、設無向圖G=(V,E)和G=(V=E)如果G，是G的生成樹，則下面說法中錯

誤的是()。

A、G，是G的子圖

B、G，是G的連通分量

C、G，是G的極小連通子圖且V=V'

D、G，是G的一個無環子圖

標準答案：B

知識點解析：選項B錯誤，因為連通分量是無向圖的極大連通子圖，其中極大的

含義是將依附于連通分量中頂點的所有邊都加上，所以，連通分量中可能存在回

路。

10、下列排序算法中，時間復雜度為O(nlogn)且與用額外空間最少的是()。

A、堆排序

B、起泡排序

C、快速排序

知識點解析：浮點數26*1.10101的尾數不是規格化數，需要進行左規。

15、“春”字的機內碼為B4BAH,由此可以推算它在GB2312--80國家標準中所在的

區號是（）。

A、19區

B、20區

C、3區

D、35

標準答案：B

知識點解析：漢字國標碼一漢字機內碼-080H=B4BAH-8080H=343AH,漢字區位

碼二漢字國標碼?2020H=141AH,前兩數14H轉換為十進制數為20,對應區號，后

兩數1AH轉換為十進制數位26,對應位號。

16、在一個按字節編址的計算機中，若數據在存儲器中以小端方案存放。假定int

型變量i的地址為08000000H,i的機器數為01234567H,地址08000000H單元的

內容是（）。

A、OIH

B、23H

C、45II

D、67H

標準答案：D

知識點解析?：小端方案是將最低有效字節存儲在最小地址位置。在數01234567H

中，最低有效字節為67H。

17、在CPU的狀態寄存器中，若符號標志為“1”，表示運算結果是（）。

A、正

B、負

C、零

D、不一定

標準答案：B

知識點解析：符號標志位SF=0,表示為正數，符號標志位SF=1,表示為負數。

18、在微程序控制器設計中，假設微命令采用最短編碼法，需產生N種微操作。

則微命令控制字段要設置的位數是（）。

A、riog2（N+l）］

B、N

C、［log2N］

D、［log2N］+l

標準答案：C

知識點解析：由于微命令控制字段必須是一個整數，所以在最短編碼法中為

［10g2N］位。L>10g2N

19、下列是有關馮.諾依曼結構計算機中指令和數據存放位置的敘述，其中正確的

是()。

A、指令存放在內存中，數據存放在外存中

B、指令和數據任何時候都存放在內存中

C、指令和數據任何時候都存放在外存中

D、程序被啟動前指令和數據都存放在外存中，而啟動后指令和數據被裝入內存

標準答案：D

知識點解析：計算機關機狀態時，計算機中指令和數據存放在外存中，但是CPU

不能直接和外存交互信息，因此啟動后的指令和數據被裝入內存。

20、一個磁盤的轉速為7200r/min,每個磁道有160個扇區，每個扇區有

512B,那么在理想情況下，其數據傳輸率為()。

A、7200x160KB/s

B、7200KB/s

C、9600KB/s

D、19200KB/s

標準答案：C

知識點解析：磁盤的轉速為7200r/min=120r/s,轉一圈經過160個扇區,每個

扇區有512B所以數據傳輸率為120x160x512/1024=9600KB/So

21、有效容量為128KB的Cache,每塊16字節，8路組相聯。字節地址為

1234567H的單元調入該Cache,其Tag應是()。

A、1234H

B、2468H

C、04DH

D、12345H

標準答案：C

知識點解析：因為塊的大小16字節.所以塊內地址字段為4位：又因為Cache容

量為128KB,八路組相聯，所以可以分為1024組，128KB+(16x8)=l024,對應的

組號字段10位；剩下為標記字段。1234567H=0001001000110100010101100111,

標記字段為其中高14位，00010010001101=048DH

22＞中斷的概念是()。

A、暫停正在運行的程序

B、暫停對內存的訪問

C、暫停CPU運行

D、I/O設備的輸入或輸出

標準答案：A

知識點解析：程序中斷的實質是程序切換，由現行程序切換到中斷服務程序，再由

中斷服務程序返回到現行程序。所以中斷只是暫停正在運行的程序，而不會暫停

CPU的運行，也不會暫停對內存的訪問。

23、當發生鍵盤中斷時，進入中斷處理程序的起始是（）。

A、發起中斷的用戶程序

B、操作系統系統程序

C、固化的硬件代碼程序

D、既非用戶亦非系統程序

標準答案：B

知識點解析：中斷處理程序是操作系統所提供的系統程序。鍵盤中斷也不例外，當

用戶程序發起鍵盤中斷時，需要保護現場，陷入內核，調用操作系統的代碼去完成

鍵盤輸入碼的讀取，并將結果在中斷返回時帶回到用戶程序中去?，F代操作系統不

允許用戶直接對硬件設備進行操作（早期匯編程序除外），用戶需要使用，必須采用

系統調用或陷入的方式。硬件固化的代碼程序可能有用戶代碼，也可能有系統代

碼，所以不正確。

24、在單處理機的多進程系統中，進程什么時候占用處理機以及決定占用時間的長

短是（）。

A、進程相應的代碼長度

B、進程總共需要運行的時間

C、進程特點和進程調度策略

D、進程完成引么功能

標準答案：C

知識點解析：本題考查進程調度的時機和進程調度的策略。進程調度的時機與進程

特點有關，例如進程是CPU繁忙型還是I/O繁忙型，自身的優先級等。但是僅有

這些特點是不夠的，能否得到調度還取決于進程調度策略，若采用優先級調度算

法，則進程的優先級才起作用。至于占用處理機運行時間的長短，則要看進程自

身，若進程是I/O繁忙型，運行過程中要頻繁訪問I/O,也就是說，可能會頻繁

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

次調度。若進程是CPU繁忙型，則一旦占有CPU就可能會運行很長時間，但是，

運行時間還取次于進程調度策略，大部分情況下，交互式系統為改善用戶的響應時

間，大多采用時間片輪轉的算法，這種算法在進程長期占用CPU到一定時間后，

會強制將其換下，以保證其他進程的CPU使用權。所以，本題的正確答案應為選

項C,其他都不是。

25、下列方式中，不是死鎖預防策略的是（）。

A、一次分配所有資源

B、銀行家算法

C、建立SPOOLing系統

D、按序分配資源

標準答案：B

知識點解析：死鎖發生的四個必要條件是互斥、部分分配、非剝奪和循環等待。死

鎖預防就是打破死鎖的這四個條件，建立SPOOLing系統可以部分解決互斥條件，

一次分配所有資源是打破部分分配條件，按序分配資源是打破循環等待條件，而銀

行家算法是死鎖避免的算法，不是死鎖預防的算法。

26、操作系統中的三級調度是()。

A、處理機調度、資源調度和網絡調度

B、處理機調度、內外存調度和作業調度

C、處理機調度、內外存調度和負載均衡調度

D、處理機調度、設備調度和作業調度

標準答案：B

知識點解析：本題考查進程調度的層次問題。在操作系統中存在著三級調度，作業

調度是決定外存上的作業何時可以創建到內存成為進程；成為進程以后位于就緒隊

列，等待處理機調度,一旦被調度就占用處理機運行；著并發進程較多，將有些不

具備運行條件的進程掛起，將其調出到外存，空出內存給更需要的進程使用，調節

負載均衡。這三級調度方式中，作業調度和進程調度比較類似，內外存交換調度因

為與存儲有關，所以算法上與前兩種差異較大。作業調度有先來先服務、短作業優

先、高優先級優先、高響應比優先等調度算法，進程調度有先來先服務、時間片輪

轉、高優先級優先、多級反饋隊列等調度算法；在采用虛擬頁式存儲管理的系統

中，內外存調度被請求頁式的分配方式所替代。

27、在某計算機中采用了多級存儲體系，設計有cache,主存和磁盤。假設訪問

cache一個字需要花費10ns,若該字不在cache中但是存在在主存中，那么需要

100ns載入cache,然后重新開始定位。若該字既不在cache中，也不在主存中，

那么需要10ms的時間裝入主存，再用100ns復制到cache,再開始定位。設cahe

的命中率為0.90,主存的命中率為0.75,那么，該系統訪問一個字的平均時間

是()。

A、25000ns

B、250023ns

C、250017ns

D、250020ns

標準答案：D

知識點解析；本題考查多級存儲層次下的平均訪問時間。多級存儲是現代計算機為

了獲得比較優異的存儲器訪問性能又比較廉價的一種實現方法。正確的計算需要搞

清楚CPU訪問一個字的流程。通常，若需要執行的指令字己經載入到cache中，

那么，僅需要從cache中取出放到指令隊列上即可，所花費的時間即是cache的訪

問時間。當cache中缺席時，產生中斷，調用cache更新程序，將所需的指令字載

入cache,然后返回到中斷點繼續定位，所需的時間是訪問cache的時間和中斷服

務程序所花費的時間之和。同理，可以推斷出訪問不在主存中的指令字所需花費的

時間是磁盤裝入時間與內存中斷服務程序時間以及cache訪問時間的和。根據各自

命中率的不同,可以計算出總時間為：10x0.9+(104-110)x(1-

0.9)x0.75+(10+100+10000000)x(1-0.9)x(1-0.75)=250020ns

28、在一個采用請求調頁的虛擬存儲系統中，存放在外存上的程序代碼調入內存的

時機是()。

A、在進程創建填寫進程表時

B、在進程創建分配內存時

C、在進程被調度占用處理機執行時

D、在每次產生缺頁中斷時

標準答案：D

知識點解析：本題考查虛擬存儲系統中程序調入內存的時刻。在一個采用請求式調

頁的虛擬存儲系統中，當一個程序需要執行時，首先由進程創建模塊為新進程找到

一張空白的進程表，將該進程的基本信息填入這張表，例如進程號、父進程、進程

組、優先級、狀態字等，然后分配該進程虛擬內存空間(此時不做任何實際的分

配)，打開文件獲得句柄，鏈接到用戶活動文件數據表中，分配設備等。做完這些

工作，進程表將被放入就緒隊列(假設所有資源均可用，只等CPU調度)，等待操

作系統的調度模塊調度。調度模塊按照規定的調度算法，從就緒隊列中選擇一個進

程(對于單核處理機)，將運行狀態賦予該進程，然后切換CPU,使得CPU的程序

計數器指向該進程起首執行處，開始運行。通常，新創建的進程是僅有虛擬地址空

間的，所以，當第一次執行該進程時，代碼不在物理內存，于是產生一次缺頁中

斷。缺頁中斷機構把對應的頁面從外存調入內存，返回到中斷點繼續運行。對于請

求式調頁，每次產生缺頁中斷一般僅調入相關的一頁，若運行過程中所需的頁面不

在內存，那么隨時可以產生缺頁中斷，調入內存。若在進程運行過程中，所需的頁

面己經在內存了，那么就不需要再將代碼調入內存。因此，真正將程序代碼和數據

調入內存的是缺頁中斷處理過程，其他過程不會對內外存的活動進行操作。

29、有四個用戶Li,Zhang,Sun和Wang,對應的用戶組分別為system,staff,

student,stuationo下列五個文件的訪問控制列表和訪問控制權限如下：

FilcO：(Li,*,rwx),(*,staff,rw-)Filel：(*,system,rwx)File2：

(Li,*,rw-),(Wang,staff,rw-),(Sun,*,rw-)File3：(*,student,rw-)

File4：(Zhang,*,-x),(*,stuation,rwx)那么,只能夠讀寫其中兩個文件

的用戶是()。

A、Li

Zhang

C、Sun

D、Wang

標準答案：C

知識點解析：本題考查考生對文件保護中訪問控制權限的理解。操作系統在對文件

的保護中，可以采取用戶口令認證、域保護和訪問控制列表及訪問控制權限表等方

式。將訪問矩陣按列進行劃分，每一列建立一個控制表，即可得到各個對象的訪問

控制表。將矩陣按行進行劃分，每一行建立一個訪問權限表，即可得到各個域的訪

問權限表，域在不同操作系統中可以按不同方式出現，例如可以是進程，也可以是

用戶等。當某個進程或用戶需要訪問某個文件時，先檢查對象的訪問控制表，檢查

是否有訪問權限。若有，則為其建立訪問權限表，并鏈接到該進程或用戶，以后，

該進程或用戶可以直接利用該用戶權限表進行訪問。本題中，Li可以讀寫的文件

有三個File。、1和2；Zhang可以訪問的文件有兩個File。和4,但是其中FilM只

能運行不能讀寫；Sun可以讀寫的文件為File2和3；Wang可以讀寫文件File4,但

是Wang不是staff組員，所以不能讀寫File2。因此，滿足條件的答案只有C。

30、已知某磁盤的平均轉速為轉/秒，平均尋道時間為T秒，每個磁道可以存儲

的字節數為N,現向該磁盤讀寫b字節的數據，采用隨機尋道的方法，每道的所有

扇區組成一個簇，請問：平均訪問時間是（）。

A、b/N*（r+T）

B、b/N*T

C>（b/N+T）*r

D、b*T/N+r

標準答案：A

知識點解析：本題考查磁盤結構和磁盤讀寫的概念。磁盤是旋轉盤式存儲設備，每

個盤面劃分有若干存儲信息的同心圓稱為磁道，每個磁道又劃分成多個扇區。本題

中，將每道的所有扇區組成一個簇，意味著可以將一個磁道的所有存儲空間組織成

一個數據塊組，這樣有利于提高存儲速度。讀寫磁盤時，磁頭首先要找到磁道，稱

為尋道，然后才可以將信息從磁道里讀出來或寫進去。讀寫完一個磁道以后磁頭會

繼續尋找下一個磁道，完成剩余的工作，所以，在隨機尋道的情況下，讀寫一個磁

道的時間要包含尋道時間和讀寫磁道時間，即T+r秒。由于總的數據量是b字節，

它要占用的磁道數為b/N個，所以總的平均讀寫時間為b/N*（T+r）秒。如果不采

用隨機尋道，而是采用連續讀寫的方式，那么磁盤的存儲方式是這樣的，首先也是

尋道，找到一組連續的磁道（用于連續讀或寫，寫入的話磁道總容量必定大于要寫

入的信息總數），花費時間T秒，然后再花費r秒將N個字節的信息寫入（或讀

出），然后磁頭移動到下一道（此時，這個磁道與上一個磁道是緊緊挨著的，幾乎可

以不花費時間），繼續寫入（或讀出）N字節，循環往復，直到全部信息寫入（或讀出）

完成。這樣的話，總時間可以縮短為b/N*r+T。因為其不需要每次都去尋道，只

需一次尋道即可。所以，考生要注意題目的條件，找出符合題意的正確答案。

31、文件系統中，當調用open。去打開一個文件時，其主要目的是（）。

A、把文件內容從外存調入內存

B、把文件的控制信息從外存調入內存

C、把文件系統的文件分配表調入內存

D、把文件系統的控制信息調入內存

標準答案：B

知識點解析：本題考查對文件控制塊（FCB）的理解。文件控制塊是控制一個文件讀

寫和管理文件的基本數據結構，當進程需要使用某個文件時，就會調用。pen（）來打

開文件，該調用將文件的文件控制塊從外存調入內存，存放在進程表中的用戶活動

文件表中，并在系統活動文件表中記錄該文件的打開次數，若是共享文件，還需要

將其鏈接的用戶數加一。由于在進程表中存放有該文件的控制塊，用戶進程才能在

調用read。時找到該文件的位置并對文件的內容進行存取。而文件系統的信息，例

如文件系統的控制信息,，文件系統的文件分配表等是在掛載一個文件系統時就讀入

內存的，掛載文件系統可以是一個磁盤分區，也可以是一個文件目錄。

32、在UNIX操作系統中，為塊設備提供了一種特殊的讀取方式，它是（）。

A、提前讀取

B、串行讀取

C、并發讀取

D、延遲讀取

標準答案：A

知識點解析：本題考查UNIX設備的讀寫概念。對于塊設備，UNIX操作系統為保

證設備讀寫的性能，除了提供一般的讀寫操作以外，還提供了提前讀取和延遲寫入

的特殊方式。在一個進程順利讀取塊設備的數據后，系統會預見到下一步可能讀取

的數據，并將其放入內存緩沖區，稱為預先讀取，它縮短了讀取數據的時間，可以

改善系統的性能。同理，延遲寫入并不真正將數據寫入塊設備，而是放在緩沖區

內，當需要再次讀取時，可以不必從塊設備讀取，縮短了讀取時間，只有當緩沖區

滿了，才將整個緩沖區數據寫入塊設備，減少了設備啟動的次數，改善了性能。

33、OSI模型中完成路徑選擇功能的層次是（）。

A、物理層

B、數據鏈路層

C、網絡層

D、傳輸層

標準答案：c

知識點露析：本題考查OSI模型中各個層次功能，完成路徑選擇，也就是路由功

能的是網絡層，答案是C。

34、現采用調相與調幅相結合的調制方式，載波有四種相位變化和兩種振幅變化，

調制速率是600波特，那么數據速率是（）。

A、1200bps

B、1800bps

C^2400bps

D、3600bps

標準答案：B

知識點解析：本題考查奈奎斯特定理的應用,這里載波有四種相位變化和兩種振幅

變化，也就是離散值為8,注意這里所提供的波特，由公式可得到600xlog28=l

800bps,因此答案是B,

35、數據鏈路層采用后退N幀協議，如果發送窗口的大小是30,那么為了保證協

議不會出錯，序列號至少需要的位數是（）。

A、4

B、5

C、6

D、7

標準答案：B

知識點解析：本題考查后退N幀協議的原理。數據鏈路層的停止一等待協議、后

退N幀協議、選擇重傳協議，以及TCP協議對發送窗口和接收窗口的要求，是理

解協議工作原理精髓所在。后退N幀協議的最大發送窗口為211（其中n為幀號的

位數），題目中已經說明發送窗口的大小為30,也就是說如果要使得協議不出錯，

必須滿足30W2L1,所以n至少要等于5,因此答案是B。

36、CSMA/CD以太網中，發生沖突后，重發前的退避時間最大是（）。

A、65536個時間片

B、65535個時間片

C、1024個時間片

D、1023個時間片

標準答案：D

知識點解析：考查CSMA/CD的退避算法，這里的時間片就是基本退避時間，確

定基本退避時間，一般是取為爭用期2禽定義重傳次數k,k<10,即k=Min［重傳

次數，10］從整數集合［0,1,…，（2七1）］中隨機地取出一個數，記為重傳所需

的時延就是r倍的基本退避時間。當重傳達16次仍不能成功時即丟棄該幀，并向

高層報告。本題中重傳次數的最大值為10,退避時間最大就是291=1023個時間

片，因此答案是D。

37、IEEE802.11采用了CSMA/CA協議，下面關于這個協議的描述中錯誤的是

（）o

A、各個發送站在兩次幀間隔（IFS）之間進行競爭發送

B、每一個發送站維持一個后退計數器并監聽網絡上的通信

C、各個發送站按業務的優先級獲得不同的發送機會

D、CSMA/CA協議適用于突發性業務

標準答案：C

知識點解析：本題考查CSMA/CA協議的工作原理，IEEE802.11標準定義了兩

種操作模式，第一種模式是DCF（分布式協調功能），該模式沒有中心控制設備，所

有站點都在競爭信道；另一種模式是PCF（點協調功能），該模式有基站，作為中心

控制設備通過輪詢機制控制決定各個站點的傳輸順序。根據IEEE802.11標準，

DCF是必須的而PCF是可選的。CSMA/CA協議應用于DCF下，目的在于解決

在允許競爭的情況下信道如何分配的問題。它支持的操作方式有兩種：第一種操作

方式采用延時算法進行訪問控制。當一個要發送數據的站點檢測到信道空閑時，站

點需繼續監聽與IFS（interframespace,幀間間隔）相等的一段時間，若此時信道依然

空閑，站點就可以發送噴；如果檢測到信道正忙，則發送站點推遲到信道空閑時再

發送數據。若沖突發生，則發生沖突的站點按照截斷二進制指數退避算法延遲一段

時間后，再試著重新發送數據。另一種操作方式類似于發收雙方的握手過程。它是

基于MACAW（MultipleAccesswithCollisionAvoidanceforWireless,帶沖突避免的

無線多路訪問），采用虛擬信道監聽的方法。CSMA/CA協議利用IFS機制讓PCF

和DCF共存在同一個通信單元內。因此答案是C。

38、局域網交換機首先完整地接收數據幀，并進行差錯檢測。如果正確，則根據幀

目的地址確定輸出端口號再轉發出去。這種交換方式是（）。

A、直接交換

B、改進直接交換

C、存儲轉發交換

D、查詢交換

標準答案：C

知識點解析：本題考查交換機的三種交換方式，直接交換在輸入端口檢測到數據幀

時，檢查幀頭地址，把數據幀直通到相應的端口，實現交換功能。存儲轉發交換把

輸入端口的數據幀先存儲起來，然后進行CRC（循環冗余碼校驗）檢查，在對錯誤包

處理后才取出數據幀的目的地址，通過查找表轉換成輸出端口送出幀。碎片隔離交

換檢查數據包的長度是否夠64個字節，如果小于64字節，說明是假包，則丟棄該

包；如果大于64字節，則發送該包。因此答案是C。

39、主機甲向主機乙發送一個（FIN=1,seq=12220）的TCP段，期望與主機乙斷開

TCP連接，若主機乙同意該連接請求，則主機乙向主機甲發送的正確的TCP段可

能是（）。

A、(SYN=O,ACK=1,seq=l1221,ack=l1221)

B、(SYN=1,ACK=1,seq=11220,ack=l1220)

C、(SYN=1,ACK=1,seq=l1221,ack=1122l)

D、(SYN=O,ACK=1,seq=l1220,ack=11220)

標準答案：A

知識點解析：本題考查TCP協議的連接管理中斷開連接過程，主機甲的應用進程

先向其TCP發出連接釋放請求，并且不再發送數據。TCP通知對方要釋放從甲到

乙這個方向的連接，將發往主機乙的TCP報文段首部的終止比特FIN置1,其序

號x等于前面已傳過的數據的最后一個字節的序號加1。主機乙的TCP收到釋放連

接通知后即發出確認，確認比特ACK置1,其序號為y,確認號為x+1,同時通知

高層應用進程，這樣，從甲到乙的連接就釋放了，連接處于半關閉（half-close）狀

態，相當于主機甲向主機乙說：“我已經沒有數據耍發送了。但你如果還發送數

據，我仍接收?！币虼吮绢}中主機乙返回的TCP段應該是SYN=0,ACK=1,seq是

隨機選擇的序號，ack必須是主機甲的序號加1,也就是11221,答案是A。

40、在下列協議中，客戶端和服務器之間采用面向無連接的協議進行通信的是（）。

A、FTP

B、SMTP

C、POP3

D、DHCP

標準答案：D

知識點解析：本題考查協議的下一層服務類型，FTP,POP3,SMTP都是基于TCP

協議，而TCP協議是面向連接的。DHCP建立在BOOTP的基礎上，它擴展了

BOOTP的功能，向主機投遞配置信息，它根據主機所提出的具體請求可以提供IP

地址和子網掩碼等信息，并使用BOOTP眾所周知的UDP端口67號作為服務器端

口，是基于UDP協議，而UDP協議是面向無連接的，因此答案是D。

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

41、已知加權有向圖如圖3—2所示，回答下列問題:

圖3-2（1）畫出該有向圖的鄰接矩陣；（2）試利用Dijkstra算

法求圖3-2中從頂點a到其他各頂點間的最短路徑，并給出求解過程。

,oo15212COOOOO'

00880c6oooo

QOOOOOOC848

oooooooeoooo3

OOCOOOOOOOOO9

8885OOOO10

OO4OOOOOOOOOO

標準答案：（I）有向圖G的鄰接矩陣a（2）頂點a到其

他各頂點間的最短路徑的求解過程如表3—3所歹h

?3-3

弊點

b€dErts

Disl、、

IS212

k-1(a.c)

(a.b)(a?c>(?.d>

1

1512106

k-2(a.c.O

(a.b)(a.d)(a?c?e)(1?€?()

IS111011

k-3

(a.b)(a.c?f.d)(a9c?e)(fteCeftg)

IS11IC

k?4

(?.b)(a.e.(.g)

15u

k-S{a?c.f.c.d.g>

(a.b)

IS

k=6

(a.b)

知識點解析：暫無解析

42、己知數組A[l..n]的元素類型為整型int,設計一個時間和空間上盡可能高效

的算法，將其調整為左右兩部分，左邊所有元素為負整數，右邊所有元素為正整

數。不要求對這些元素排序。（1）給出算法的基本設計思想；（2）根據設計思想，采

用C或C++或Java語言表述算法，關鍵之處給出注釋；（3）說明你所設計算法的時

間復雜度和空間復雜度。

標準答案：用C語言算法描述如下：voildAdjust（intA[]）｛//調整數組A,使得

A的左邊為負整數,右邊為正整數inti=l,j=n,temp：while（i<j）（while（A[i]<

0&&i<j）i++；//A|_iJ為負整數時，i增1while（A[jl>O&&i<j）j-；//A|jJ為正

整數時，j減1if（iVVj）｛Letup：A[i]；A[i]：A[j]；A[j]：temp；//A[i]為正整

數、A[j]為負整數時，交換i++：j-；｝｝｝（3）算法的時間復雜度為0（n）；算法的

空間復雜度為0（1）。

知識點解析：暫無解析

43、設主存容量1MB,有16KB直接相聯映像的Cache,假定該Cache的塊為8

個32位的字。解答下列問題：（1）寫出Cache的地址格式；（2）寫出主存的地址格

式；（3）塊表的容量有多大；（4）主存地址為DE8F8H的單元在Cache中的什么位

置”

標準答案：（l）Cache地址14位，其中Cache塊號9位，塊內地址5位。（2）主存地

址20位，包括主存塊號（標記字段6位+塊號9位）和塊內地址5位。（3）Cache的塊

號為9位，所以塊表的單元數為22塊表中存放的是塊標記，由于塊標記為6

位，所以塊表的字長為6位。故塊表的容量為29字x6位。（4）Cache有16x1024/

32=512個塊。因為主存地址DE8F8=11011110100011111000,主存地址中前6位

是塊標記，標記字段的值是110111,中間9位為塊號=101000111,最后5位為塊

內地址=11000。在直接映像方式下，Cache地址即為塊號十塊內地址

=10100011111000,所以主存地址DE8F8H轉換成Cache地址為28F8H。

知識點解析；暫無解析

44、一臺模型機共有7條指令，主頻25MHz，各指令的使用頻度與CPI如表3—1

所列，該機有8位和16位兩種指令字長，采用2-4擴展操作碼。8位字長指令為

寄存器一寄存器（R—R）二地址類型，16位字長指令為寄存器一存儲器（R—M）二地

址變址類型（地址碼范圍在-128?127之間）。

表3-1

指令字長使用頻率執行一條指令的周期敷CP1

IM8位）35%1

12(8tt)25%2

13《8位）20%2

14(16ft)10%2

15(16位)5%1

16(16位)3%2

17(16位)2%2

（1）計算該

機的MIPS速率；（2）計算操作碼的平均碼長；（3）設計該機的兩種指令格式，標出

各字段位數并給出操作碼編碼；（4）該機允許使用多少個可編址的通用寄存器，多

少個變址寄存器；（5）如何計算存儲器有效地址。

標準答案：（1）根據各條指令的CPI,求出平均CPL平均

CPI=O.35x1+0.25x2+0.20x2+0.10x2+0.05x1+0.03x2+0.01x2=1.6速率二

主頻/平均CPI=25MHz/1.6=15.6MIPS（2）操作碼的平均長度

=2x(0.35+0.25+0.2)+4x(0.10+0.05+0.03+0.02)=2.4位(3)該機的指令格

233

R.R型IOPIRi[RjI

式如下圖3—6所示。圖3-67條指令

的操作碼分別為11：0012：0113：1014：110015：110116：111017：1111（4）

根據指令格式，8位R—R型指令，操作碼占2位，兩個通用寄存器編號字段各占

3位，允許8個通用寄存器。16位R—M型指令，操作碼占4位，地址碼字段占8

位，一個通用寄存器編號字段占3位，變址寄存器編號僅1位，允許2個變址寄存

器。（5）存儲器有效地址EA=（X）+A,有效地址的位數取決于變址寄存器的長度。

知識點解析：暫無解析

45、假設有8個記錄A、B,C、D、E、F、G、H存放在磁盤里，每個磁道有8個

扇區，正好可以存放8個記錄。假設磁盤旋轉速度為20ms/r,處理程序每讀出一

個記錄后，用2ms的時間進行處理，請問：（1）當記錄A、B、C、D、E、F、G、

H按順序放在磁道上時，順序處理這5個記錄花費的總時間是多少?（假設啟動時的

位置正好在A扇區的起點。）（2）如何采取優化方法，使處理這些記