一、1.單項選擇題

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

0.圖的鄰接表存儲表示，數(shù)據(jù)元素之間的關(guān)系是(  )。

A.線性結(jié)構(gòu)
B.樹形結(jié)構(gòu)
C.網(wǎng)狀結(jié)構(gòu)
D.無結(jié)構(gòu)

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個結(jié)點的非空二叉樹，其葉子結(jié)點個數(shù)的最小值和最大值分別是(  )。

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

3.一棵結(jié)點個數(shù)為63的滿二叉樹轉(zhuǎn)換為森林，則森林中樹的個數(shù)是(  )。

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個結(jié)點，值分別為1、2、3、4、5、6、7，形態(tài)為滿二叉樹，(  )不是插入序列。

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個關(guān)鍵字映射到一個Hash表中，用鏈地址法解決沖突。在這個Hash表中查找一個關(guān)鍵字所需的操作為( )。

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

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

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

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

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

9.對已知范圍矩形中的坐標(biāo)排序，數(shù)據(jù)量較大，要求先排橫坐標(biāo)，再排縱坐標(biāo)，則應(yīng)選(  )。

A.歸并排序
B.快速排序
C.堆排序
D.基數(shù)排序

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

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

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

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

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

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

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

A.變址尋址時，有效數(shù)據(jù)存放在主存中。
B.堆棧是先進(jìn)后出的隨機(jī)存儲器。
C.堆棧指針SP的內(nèi)容表示當(dāng)前堆棧內(nèi)所存儲的數(shù)據(jù)的個數(shù)。
D.內(nèi)存中指令的尋址和數(shù)據(jù)的尋址是交替進(jìn)行的。

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

A.指令寄存器
B.操作控制器
C.程序計數(shù)器
D.狀態(tài)條件寄存器

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

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

16.在浮點數(shù)機(jī)制中，判斷補(bǔ)碼規(guī)格化形式的原則是(  )。

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

17.下列各術(shù)語中，用于表征計算機(jī)系統(tǒng)性能指標(biāo)的是(  )。

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

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

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

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

A.鏈?zhǔn)讲樵?br/>B.獨立請求
C.無條件傳送
D.計數(shù)器定時查詢

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

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

21.“守護(hù)進(jìn)程”在系統(tǒng)中一般不需要使用(  )。

A.輔助存儲設(shè)備
B.中斷機(jī)制提供的功能
C.終端
D.物理內(nèi)存

22.既允許在操作系統(tǒng)內(nèi)核態(tài)執(zhí)行叉可以在用戶態(tài)執(zhí)行的指令是(  )。

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

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

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

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

A.鍵盤
B.打印機(jī)
C.磁盤
D.鼠標(biāo)

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

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

26.不需要搶占的進(jìn)程調(diào)度算法是(  )。

A.最早截至?xí)r間優(yōu)先
B.時間片輪轉(zhuǎn)
C.最短時間優(yōu)先
D.最短剩余時間優(yōu)先

27.

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

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

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

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

A.順序存儲
B.鏈?zhǔn)酱鎯?br/>C.索引式存儲
D.BST樹

30.某系統(tǒng)中n個相互獨立的生產(chǎn)者進(jìn)程為一個消費者進(jìn)程提供數(shù)據(jù)，假設(shè)每個生產(chǎn)者提供的數(shù)據(jù)寫入各不相同的緩沖區(qū)，且生產(chǎn)者寫緩沖區(qū)的速度比消費者讀緩沖區(qū)的速度快，則緩沖區(qū)個數(shù)的最優(yōu)值應(yīng)為( )。

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

31.UNIX設(shè)備驅(qū)動程序分為上半?yún)^(qū)和下半?yún)^(qū)，上、下半?yún)^(qū)的工作方式為(  )。

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

32.TCP／IP網(wǎng)絡(luò)協(xié)議主要在OSI模型中進(jìn)行操作的層次是(  )。

A.數(shù)據(jù)鏈路層、傳輸層、物理層
B.物理層、傳輸層、會話層
C.網(wǎng)絡(luò)層、傳輸層、應(yīng)用層
D.網(wǎng)絡(luò)層、傳輸層、會話層

33.設(shè)待傳送數(shù)據(jù)總長度為L位，分組長度為P位，其中頭部開銷長度為H位，源節(jié)點到目的節(jié)點之間的鏈路數(shù)為h，每個鏈路上的延遲時間為D秒，數(shù)據(jù)傳輸率為B bps，虛電路建立連接的時間都為S秒，在分組交換方式下每個中間節(jié)點產(chǎn)生d位的延遲時間，則傳送所有數(shù)據(jù)，虛電路分組交換所需時間是([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數(shù)據(jù)報報頭中有兩個有關(guān)長度的字段，一個為報頭長度(IHL)字段，一個為總長度 (total length)字段，下面說法正確的是( )。

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

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

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

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

A.新入網(wǎng)的計算機(jī)一般可以從DHCP服務(wù)器取得IP地址，獲得租約
B.若新入網(wǎng)的計算機(jī)找不到DHCP服務(wù)器，則該計算機(jī)無法取得IP地址
C.在租期內(nèi)計算機(jī)重新啟動，而且沒有改變與網(wǎng)絡(luò)的連接，允許該計算機(jī)維持原租約
D.當(dāng)租約執(zhí)行到50％時，允許該計算機(jī)申請續(xù)約

37.路由器中發(fā)現(xiàn)TTL值為0的分組將進(jìn)行的處理是(  )。

A.返回發(fā)送方
B.丟棄
C.繼續(xù)轉(zhuǎn)發(fā)
D.本地提交

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

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

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

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

二、2.綜合應(yīng)用題

綜合應(yīng)用題
41-47小題，共70分。

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

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

2.

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

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

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

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