一、1.單項選擇題

單項選擇題
1-40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。

0.圖的鄰接表存儲表示，數據元素之間的關系是(  )。

A.線性結構
B.樹形結構
C.網狀結構
D.無結構

1.1、2、3、4順序入棧(起始為空棧)，只要棧不空即可出棧，不可能的序列是(  )。

A.4、3、2、1
B.2、1、3、4
C.1、2、3、4
D.4，3，1，2

2.一棵N個結點的非空二叉樹，其葉子結點個數的最小值和最大值分別是(  )。

A.1，N-1
B.N／2，N／2
C.1，(N+1)／2
D.(N-1)／2，(N+1)／2

3.一棵結點個數為63的滿二叉樹轉換為森林，則森林中樹的個數是(  )。

A.7
B.6
C.5
D.4

4.

A.1 2 4 3
B.4 3 1 2
C.2 1 3 4
D.3 2 1 4

5.一棵：BS'r樹共7個結點，值分別為1、2、3、4、5、6、7，形態為滿二叉樹，(  )不是插入序列。

A.4 2 6 1 3 5 7
B.4 2 3 1 6 7 5
C.4 2 1 3 5 6 7
D.4 6 5 7 2 1 3

6.將N個關鍵字映射到一個Hash表中，用鏈地址法解決沖突。在這個Hash表中查找一個關鍵字所需的操作為( )。

A.Hash映射N次，鏈結點比較最多1次
B.Hash映射1次，鏈結點比較最多N次
C.Hash映射N／2次，鏈結點比較最多N／2次
D.Hash映射N-1次，鏈結點比較最多1次

7.高度為4的4階B樹最多可容納(  )個關鍵字(根是第1層)。

A.254
B.255
C.340
D.383

8.已知待排數據基本有序，則以下四種排序方法中比較合適的選擇應為(  )。

A.快速排序
B.選擇排序
C.插入排序
D.堆排序

9.對已知范圍矩形中的坐標排序，數據量較大，要求先排橫坐標，再排縱坐標，則應選(  )。

A.歸并排序
B.快速排序
C.堆排序
D.基數排序

10.一個8位的二進制整數，若采用補碼表示，且由3個“1”和5個“0”組成，則最小值為(  )。

A.-127
B.-32
C.-125
D.-3

11.以下(  )尋址方式用來支持浮動程序設計。

A.相對尋址
B.變址尋址
C.寄存器間接尋址
D.基址尋址

12.Cache用組相聯映射，一塊大小為128字節，Cache共64塊，4塊分一組。主存有4 096塊，主存地址供需( )位。

A.19
B.18
C.17
D.16

13.下列說法中不正確的是(  )。

A.變址尋址時，有效數據存放在主存中。
B.堆棧是先進后出的隨機存儲器。
C.堆棧指針SP的內容表示當前堆棧內所存儲的數據的個數。
D.內存中指令的尋址和數據的尋址是交替進行的。

14.下列各部件中不屬于控制器的部件是(  )。

A.指令寄存器
B.操作控制器
C.程序計數器
D.狀態條件寄存器

15.下列各種情況中，應采用異步通信方式的是(  )。

A.I／O接口與打印機交換信息
B.CPU與存儲器交換信息
C.CPU與I／O接口交換信息
D.CPU與PCI總線交換信息

16.在浮點數機制中，判斷補碼規格化形式的原則是(  )。

A.尾數的第一位為1，數符位任意
B.尾數的符號為與第一數位相同
C.尾數的符號位與第一數位不同
D.階符與數符不同

17.下列各術語中，用于表征計算機系統性能指標的是(  )。

A.RISC
B.PSW
C.PC
D.MFLOPS

18.IEEE 754標準規定的32位浮點數格式中，符號位為1位，階碼為8位，尾數為23位。則它所能表示的最大規格化正數為(  )。

A.+(2-2²³)×2⁺¹²⁷ 
B.+(1-2²³)×2⁺¹²⁷ 
C.+(2-2²³)×2⁺²⁵⁵ 
D.2⁺¹²⁷-2²³ 

19.在集中式總線仲裁中，(  )方式響應時間最快。

A.鏈式查詢
B.獨立請求
C.無條件傳送
D.計數器定時查詢

20.CPU在每個(  )周期后響應DMA請求。

A.時鐘
B.總線
C.存儲 DI指令

21.“守護進程”在系統中一般不需要使用(  )。

A.輔助存儲設備
B.中斷機制提供的功能
C.終端
D.物理內存

22.既允許在操作系統內核態執行叉可以在用戶態執行的指令是(  )。

A.禁止所有中斷
B.讀系統時鐘
C.寫系統時鐘
D.改變存儲映射

23.“程序與進程”的類比最接近(  )。

A.演員與演出
B.《雷雨》劇本與該劇本的一次演出
C.四個運動員和．4×100米接力比賽
D.Windows lE與MS Windows操作系統

24.Spooling技術一般不為(  )提供虛擬化支持。

A.鍵盤
B.打印機
C.磁盤
D.鼠標

25.把某設備mount到一個非空目錄dir，則(  )。

A.dir中僅可見原來的文件
B.dir中不僅可見原來的文件，還同時可見設備中的文件
C.dir中的文件被刪除，僅可見設備中的文件
D.dir中的文件未被刪除，僅可見設備中的文件

26.不需要搶占的進程調度算法是(  )。

A.最早截至時間優先
B.時間片輪轉
C.最短時間優先
D.最短剩余時間優先

27.

A.可能死鎖，p1或p2或p3都有可能饑餓
B.不可能死鎖，但p1或p2或p3都有可能饑餓
C.不可能死鎖，但只有p1或p2有可能饑餓
D.不可能死鎖，但只有p2或p3有可能饑餓

28.某操作系統采用變長存儲分區機制，分區有兩類，一類是占用塊，一類是空閑塊。占用塊又可進一步分為(I)左右均為占用塊， (II)僅左邊為占用塊，(III)僅右邊為占用塊，(IV)左右均為空閑塊，用a記(I)類塊的個數，b記(II)類塊的個數，c記(III)類塊的個數，d記(IV)類塊的個數，則系統中的空閑塊數為(  )。

A.a+b+c+d
B.b+c+2d
C.2b+2d
D.b+d

29.某文件系統專用于影視多媒體應用，數據存放在光盤，則合理的文件物理存儲格式應為(  )。

A.順序存儲
B.鏈式存儲
C.索引式存儲
D.BST樹

30.某系統中n個相互獨立的生產者進程為一個消費者進程提供數據，假設每個生產者提供的數據寫入各不相同的緩沖區，且生產者寫緩沖區的速度比消費者讀緩沖區的速度快，則緩沖區個數的最優值應為( )。

A.n-1
B.n
C.n+1
D.2n

31.UNIX設備驅動程序分為上半區和下半區，上、下半區的工作方式為(  )。

A.同步、同步
B.異步、同步
C.同步、異步
D.異步、異步

32.TCP／IP網絡協議主要在OSI模型中進行操作的層次是(  )。

A.數據鏈路層、傳輸層、物理層
B.物理層、傳輸層、會話層
C.網絡層、傳輸層、應用層
D.網絡層、傳輸層、會話層

33.設待傳送數據總長度為L位，分組長度為P位，其中頭部開銷長度為H位，源節點到目的節點之間的鏈路數為h，每個鏈路上的延遲時間為D秒，數據傳輸率為B bps，虛電路建立連接的時間都為S秒，在分組交換方式下每個中間節點產生d位的延遲時間，則傳送所有數據，虛電路分組交換所需時間是([X]表示對X向上取整)(  )。

A.S+(hd／B+P／B)×[L／(P-H)]秒
B.S+(hD+P／B)×[L／(P-H)]秒
C.S+[(h-1)D+P／B]×[L／(P-H)]秒
D.S+[(h-1)d／B+hD+P／B]×[L／(P-H)]秒

34.在IP數據報報頭中有兩個有關長度的字段，一個為報頭長度(IHL)字段，一個為總長度 (total length)字段，下面說法正確的是( )。

A.報頭長度字段和總長度字段都以8比特為計數單位
B.報頭長度字段以8比特為計數單位，總長度字段以32比特為計數單位
C.報頭長度字段以32比特為計數單位，總長度字段以8比特為計數單位
D.報頭長度字段和總長度字段都以32比特為計數單位

35.如果一臺主機的IP地址為192．168．0．10，子網掩碼為255．255．255．224，那么主機所在網絡的網絡號占IP地址的位數是(  )。

A.24
B.25
C.27
D.28

36.關于DHCP的工作過程，下面說法錯誤的是(  )。

A.新入網的計算機一般可以從DHCP服務器取得IP地址，獲得租約
B.若新入網的計算機找不到DHCP服務器，則該計算機無法取得IP地址
C.在租期內計算機重新啟動，而且沒有改變與網絡的連接，允許該計算機維持原租約
D.當租約執行到50％時，允許該計算機申請續約

37.路由器中發現TTL值為0的分組將進行的處理是(  )。

A.返回發送方
B.丟棄
C.繼續轉發
D.本地提交

38.關于TCP和UDP端口，下列說法正確的是(  )。

A.TCP和UDP分別擁有自己的端口號，它們互不干擾，可以共存于同一臺主機
B.TCP和UDP分別擁有自己的端口號，但它們不能共享于同一臺主機
C.TCP和UDP的端口沒有本質區別，它們可以共存于同一臺主機
D.TCP和UDP的端口沒有本質區別，它們互不干擾，不能共存于同一臺主機

39.下列Internet應用中，基于C／S計算模式的是(  )。

A.FTP
B.BT
C.MSN
D.Skype

二、2.綜合應用題

綜合應用題
41-47小題，共70分。

0. 已知一組關鍵字為(26，36，41，38，44，15，68，12，6，51，25)，用鏈地址法解決沖突。假設裝填因子a=0．75，散列函數的形式為H(K)=K MOD P，回答下列問題：
  (1)構造散列函數。
  (2)畫出散列表。
  (3)計算出等概率情況下查找成功的平均查找長度。
  (4)計算出等概率情況下查找失敗的平均查找長度。

1. 設計一個算法，求無向圖G(采用鄰接表存儲)的連通分量個數。

2.

3. 已知x和y，用變形補碼計算結果，同時指出結果是否溢出。(要求寫出計算步驟)x=0．1011，y=-0．1001求x+y，x-y=?

4. 若干個等待訪問磁盤者依次要訪問的柱面為20，44，40，4，80，12，76，假設每移動一個柱面需要3毫秒時間，移動臂當前位于40號柱面，請按下列算法分別計算為完成上述各次訪問總共花費的尋找時間。
  (1)先來先服務算法；
  (2)最短尋找時間優先算法。

5. 在4×100米接力賽中，4個運動員之間存在如下關系：運動員1跑到終點把接力棒交給運動員2；運動員2一開始處于等待狀態，在接到運動員1傳來的接力棒后才能往前跑，他跑完100米后交棒給運動員3；運動員3也只有接到運動員2傳來的接力棒后才能往前跑，他跑完100米后交棒給運動員4；運動員4接棒后跑完全程。試用信號量機制進行描述。

6. 什么是域名解析?域名解析中采取了什么措施提高效率?對同一個域名向DNS服務器發出多次的DNS請求報文后，得到IP地址都不一樣，可能嗎?為什么?