一、單項選擇題：1~40 小題，每小題2 分，共80 分。下列每題給出的四個選項中，只有一個選項符合試題要求。

1. 已知兩個長度分別為m 和n 的升序鏈表，若將它們合并為一個長度為m+n 的降序鏈表，則最壞情況下的時間復(fù)雜度是

A. O(n) B. O(m.n) C. O(min(m,n)) D. O(max(m,n))

2. 一個棧的入棧序列為1, 2,3, ,n ，其出棧序列是1 2 3 , , , , n p p p p 。若2 p . 3，則3 p 可能取值的個數(shù)是

A. n .3 B. n . 2 C. n .1 D. 無法確定

3. 若將關(guān)鍵字1，2，3，4，5，6，7 依次插入到初始為空的平衡二叉樹T 中，則T 中平衡因子為0 的分支結(jié)點的個數(shù)是

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

4. 已知三叉樹T 中6 個葉結(jié)點的權(quán)分別是2，3，4，5，6，7，T 的帶權(quán)(外部)路徑長度最小是

A. 27 B. 46 C. 54 D. 56

5. 若X 是后序線索二叉樹中的葉結(jié)點，且X 存在左兄弟結(jié)點Y，則X 的右線索指向的是

A. X 的父結(jié)點 B. 以Y 為根的子樹的最左下結(jié)點

C. X 的左兄弟結(jié)點Y D. 以Y 為根的子樹的最右下結(jié)點

6. 在任意一棵非空二叉排序樹T1 中，刪除某結(jié)點v 之后形成二叉排序樹T2，再將v 插入T2 形成二叉排序樹T3。下列關(guān)于T1 與T3 的敘述中，正確的是

I. 若v 是T1 的葉結(jié)點，則T1 與T3 不同

II. 若v 是T1 的葉結(jié)點，則T1 與T3 相同

III. 若v 不是T1 的葉結(jié)點，則T1 與T3 不同

IV. 若v 不是T1 的葉結(jié)點，則T1 與T3 相同

A. 僅I、III B. 僅I、IV C. 僅II、III D. 僅II、IV

7. 設(shè)圖的鄰接矩陣A 如下所示。各頂點的度依次是

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

8. 若對如下無向圖進行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是

A. h，c，a，b，d，e，g，f B. e，a，f，g，b，h，c，d

C. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g

9. 下列 AOE 網(wǎng)表示一項包含 8個活動的工程。經(jīng)過同時加快若干進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是

A.c 和 e B. d 和 e C. f和 d D. f 和 h

10. 在一株高度為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是

A.5 B.7 C.8 D.14

11.對給定的關(guān)鍵字序列 110，119 ，007 ，911，114 ，120 ，122進行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是

A. 007，110，119，114，911，120 ，122 B. 007，110，119，114，911，122，120

C. 007，110，911，114，119，120，122 D. 110，120，911，122，114，007，119

12. 某計算機主頻為 1.2 GHz 1.2 GHz 1.2 GHz，其指令分為 4類，它們在基準(zhǔn)程序中所占比例及 CPICPICPI如下表所示。

該機的 MIPSMIPSMIPSMIPS數(shù)是

A. 100 B. 200 C. 400 D. 600

13. 某數(shù)采用 IEEE 754IEEE 754IEEE 754 單精度浮點數(shù)格式表示為 C640 C640 0000 H，則該數(shù)的值是

A. -1.5 ×213 B. B. -1.5 ×212 C. C. -0.5x ×213 D. -0.5 ×212

14. 某字長為 8位的計算機中，已知整型變量 x、y的機器數(shù)分別為[x]補=1 1110100，[y]補=1 0110000。若整型變量 z=2x+y/2，則 z的機器數(shù)為

A. 1 1000000 B. 0 0100100 C. 1 0101010 D. 溢出

15 . 用海明碼對長度為 8位的數(shù)據(jù)進行檢 /糾錯時，若能糾正一位錯，則校驗位數(shù)至少為

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

16. 某計算機主存地址空間大小為256 MB，按字節(jié)編址。虛擬地空間大小為4 GB，采用頁式存儲管理，頁面大小為4KB，TLB(快表)采用全相聯(lián)映射，有4個頁表項，內(nèi)容如下表所示。

則對虛擬地址03FF F180H進行虛實地址變換的結(jié)果是

A. 015 3180H B. 003 5180H C. TLB缺失 D. 缺頁

17. 假設(shè)變址寄存器R的內(nèi)容為1000 H，指令中的形式地址為2000H地址1000H中的內(nèi)容為2000H，地址2000H中的內(nèi)容為3000H，地址3000H中的內(nèi)容為4000H ，則變址尋方式下訪問到的操作數(shù)是

A. 1000H B. 2000H C. 3000H D. 4000H

18. 某CPU主頻為1.03 GHz，采用4級指令流水線，每個段的執(zhí)行需要1個時鐘周期。假定CPU執(zhí)行了100條指令，在其執(zhí)行過程中沒有發(fā)生任何流水線阻塞，此時流水線的吞吐率為

A. 0.25×10 9條指令/秒 B. 0.97 ×10 9條指令 /秒

C. 1.0 ×10 9條指令/秒 D. 1.03 ×10 9條指令 /秒

19. 下列選項中，用于設(shè)備和控制器 (I/O接口 )之間互連的接口標(biāo)準(zhǔn)是

A. PCI B. USB C. AGP D. PCI-Express

20. 下列選項中，用于提高RAID可靠性的措施有

I. 磁盤鏡像 II.條帶化 III. 奇偶校驗 IV. 增加 Cache機制

A. 僅 I、II B. 僅 I、III C. 僅I、III和IV D. 僅II、III和IV

21. 某磁盤的轉(zhuǎn)速為10,000轉(zhuǎn)/分，平均尋道時間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個4KB的扇區(qū)所需平均時間約為

A. 9ms B. 9.4ms C. 12ms D. 12.4ms

22. 下列關(guān)于中斷 I/ O方式和 DMA 方式比較的敘述中，錯誤的是

A. 中斷 I/ O方式請求的是方式請求的是 CPUCPUCPU處理時間，DMA 方式請求的是總線使用權(quán)

B. 中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，DMA響應(yīng)發(fā)生在一個總線事務(wù)完成后

C. 中斷 I/ O方式下數(shù)據(jù)傳送經(jīng)過軟件完成，方式下數(shù)據(jù)傳送經(jīng)過軟件完成，DMA方式下數(shù)據(jù)傳送由硬件完成

D. 中斷 I/ O方式適用于所有外部設(shè)備，方式適用于所有外部設(shè)備，DMA方式僅適用于快速外部設(shè)備

23 . 用戶在刪除某文件的過程中，操作系統(tǒng)不可能執(zhí)行是

A. 刪除此文件所在的目錄 B. 刪除與此文件關(guān)聯(lián)的目錄項

C. 刪除與此文件對應(yīng)的控制塊 D. 釋放與此文件關(guān)聯(lián)的內(nèi)存級沖區(qū)

24. 為支持CD-ROM中視頻文件的快速隨機播放，播放性能最好的文件數(shù)據(jù)塊組織方式是

A. 連續(xù)結(jié)構(gòu) B. 鏈?zhǔn)浇Y(jié)構(gòu) C. 直接索引結(jié)構(gòu) D. 多級索引結(jié)鉤

25. 用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的處理系統(tǒng)的處理流程是：用戶程序&rarr系統(tǒng)調(diào)用處理程序&rarr設(shè)備駱動程序&rarr中斷處理程序。其中，計算數(shù)據(jù)所在磁盤的柱面號、磁頭號、扇區(qū)號的程序是

A. 用戶程序 B. 系統(tǒng)調(diào)用處理程序

C. 設(shè)備驅(qū)動程序 D. 中斷處理程序

26. 若某文件系統(tǒng)索引結(jié)點(inode)中有直接地址項和間接地址項，則下列選項中，與單個文件長度無關(guān)的因素是

A. 索引結(jié)點的總數(shù) B. 間接地址索引的級數(shù)

C. 地址項的個數(shù) D. 文件塊大小

27 . 設(shè)系統(tǒng)緩沖區(qū)和用戶工作均采單，從外讀入1個數(shù)據(jù)塊到系統(tǒng)緩沖區(qū)的時間為100，從系統(tǒng)緩沖區(qū)讀入 1個數(shù)據(jù)塊到用戶工作區(qū)的時間為5，對用戶工作區(qū)中的1個數(shù)據(jù)塊進行分析的時間為90(如下圖所示)。進程從外設(shè)讀入并分析2個數(shù)據(jù)塊的最短時間是

A. 200 B. 295 C. 300 D .390

28. 下列選項中，會導(dǎo)致用戶進程從態(tài)切換到內(nèi)核的操作是

I. 整數(shù)除以零 II. sin( )函數(shù)調(diào)用 III. read系統(tǒng)調(diào)用

A. 僅 I、II B. 僅 I、III C. 僅 II 、III D. I、II和III

29. 計算機開后，操作系統(tǒng)最終被加載到

A. BIOS B. ROM C. EPROM D. RAM

30. 若用戶進程訪問內(nèi)存時產(chǎn)生缺頁，則下列選項中，操作系統(tǒng)可能執(zhí)行的是

I. 處理越界錯 II. 置換頁 III. 分配內(nèi)存

A. 僅 I、II B. 僅 II 、III C. 僅 I、III D. I、II 和 III

31. 某系統(tǒng)正在執(zhí)行三個進程P1、P2和P3，各進程的計算(CPUCPUCPU)時間和I/OI/O時間比例如下表所示。

34. 若下圖為10BaseT網(wǎng)卡接收到的信號波形，則該比特串是

A. 0011 0110 B. 1010 1101 C. 0101 0010 D. 1100 0101

35. 主機甲經(jīng)過1個路由器個路由器(存儲轉(zhuǎn)發(fā)方式)與主機乙互聯(lián)，兩段鏈路的數(shù)據(jù)傳輸速率均為10Mbps,主機甲分別采用報文交換和組大小為10kb的分組交換向主機乙發(fā)送1個大小為8Mb(1M=10 6)的報文。若忽略鏈路傳播延遲、分組頭開銷和拆裝時間，則兩種交換方式完成該報文傳輸所需的總時間分別為

A. 800ms 、1600ms B. 801ms、1600ms

C. 1600ms、800ms D. 1600ms 、801ms

36. 下列介質(zhì)訪問控制方法中，可能發(fā)生沖突的是

A. CDMA B. CSMA C. TDMAC D. FDMA

37. HDLC 37. HDLC37. HDLC協(xié)議對01111100 01111110組幀后對應(yīng)的比特串為

A. 01111100 00111110 10 B. 01111100 01111101 01111110

C. 01111100 01111101 0 D. 01111100 01111110 01111101

38. 對于100Mbps的以太網(wǎng)交換機，當(dāng)輸出端口無排隊直通(cut-through switching)方式轉(zhuǎn)發(fā)一個以太網(wǎng)幀(不包括前導(dǎo)碼)時，引入的轉(zhuǎn)發(fā)延遲至少是

A. 0 &mus B. 0.48 &mus C. 5.12 &mus D. 121.44 &mus

39. 主機甲與乙之間已建立一個TCP連接，雙方持續(xù)有數(shù)據(jù)傳輸,且無差錯與丟失。若甲收到1個來自乙的TCP段，該段的序號為1913、確認(rèn)序號為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的 TCP 段的序號和確認(rèn)分別是

A. 2046 、2012 B. 2046、2013 C. 2047 、2012 D. 2047 2012

40. 下列關(guān)于SMTP 協(xié)議的敘述中，正確的是

I. 只支持傳輸7比特ASCII碼內(nèi)容

II. 支持在郵件服務(wù)器之間發(fā)送郵件

III. 支持從用戶代理向郵件服務(wù)器發(fā)送郵件

IV. 支持從郵件服務(wù)器向用戶代理發(fā)送郵件

A. 僅I、II 和III B. 僅I、II 和IV

C. 僅I、III 和IV D. 僅II、III 和IV

二、綜合應(yīng)用題：41~47 小題，共70 分。

41.

(0， 5，5，3，5，7，5，5)，側(cè)5 為主元素又如A=(0，5，5，3，5，1，5，7)，則A中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中，請設(shè)計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素否則輸出-1。要求：

(1)給出算法的基本設(shè)計思想。

(2)根據(jù)設(shè)計思想，采用C 或C++或Java 語言描述算法，關(guān)鍵之處給出注釋。

(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。

42. (10 分)設(shè)包含4 個數(shù)據(jù)元素的集合S= "do"，"for"，" repeat"，" while"，各元素的查找概率依次為：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。將S 保存在一個長度為4的順序表中，采用折半查找法，查找成功時的平均查找長度為2.2。請回答：

(1)若采用順序存儲結(jié)構(gòu)保存S，且要求平均查找長度更短，則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時的平均查找長度是多少?

(2)若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)保存S，且要求平均查找長度更短，則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時的平均查找長度是多少?

43.(9 分)某32 位計算機，CPU 主頻為800MHz，Cache 時的CPI 為4，Cache 塊大小為32 字節(jié)主存采用8 體交叉存儲方式，每個體的存儲字長為32 位、存儲周期為40 ns存儲器總線寬度為32 位，總線時鐘頻率為200 MHz，支持突發(fā)傳送總線事務(wù)。每次讀突發(fā)傳送總線事務(wù)的過程包括：送首地址和命令、存儲器準(zhǔn)備數(shù)據(jù)、傳送數(shù)據(jù)。每次突發(fā)傳送32 字節(jié)，傳送地址或32 位數(shù)據(jù)均需要一個總線時鐘周期。請回答下列問題，要求給出理由或計算過程。

(1)CPU 和總線的時鐘周期各為多少?總線的帶寬(即最大數(shù)據(jù)傳輸率)為多少?

(2)Cache 缺失時，需要用幾個讀突發(fā)傳送總線事務(wù)來完成一個主存塊的讀取?

(3)存儲器總線完成一次讀突發(fā)傳送總線事務(wù)所需的時間是多少?

(4)若程序BP 執(zhí)行過程中，共執(zhí)行了100 條指令，平均每條指令需進行1.2 次訪存，Cache 缺失率為5%，不考慮替換等開銷，則BP 的CPU 執(zhí)行時間是多少?

44.(14 分)某計算機采用16 位定長指令字格式，其CPU 中有一個標(biāo)志寄存器，其中包含進位/借位標(biāo)志CF、零標(biāo)志ZF 和符號標(biāo)志NF。假定為該機設(shè)計了條件轉(zhuǎn)移指令，其格式如下：

其中，00000為操作碼OPC、Z和 N分別為CF、ZF和NF的對應(yīng)檢測位，某測位為1時表示需檢測對應(yīng)標(biāo)志，需檢測的標(biāo)志位中只要有一個為1就轉(zhuǎn)移，否則就不轉(zhuǎn)移，例如，若C=1，Z=0，N=1，則需檢測CF和NF的值，當(dāng) CF=1或NF=1時發(fā)生轉(zhuǎn)移OFFSET是相對偏移量，用補碼表示。轉(zhuǎn)移執(zhí)行時，轉(zhuǎn)移目標(biāo)地址為(PC)+2+2×OFFSET順序執(zhí)行時，下條指令地址為(PC)+2。請回答下列問題。

(1)該計算機存儲器按字節(jié)編址，還是按字編址?該條件轉(zhuǎn)移指令向后(反向)最多可跳轉(zhuǎn)最多少條指令?

(2)某條件轉(zhuǎn)移指令的地址為200CH，指令內(nèi)容如下圖所示，若該執(zhí)行時CF=0，ZF=0，NF=1，則該指令執(zhí)行后PC的值是多少?若該指令執(zhí)行時CF=1，ZF=0 Z，NF=0，則該指令執(zhí)行后PC的值又是多少?請給出計算過程。

(3)實現(xiàn)“無符號數(shù)比較小于等時轉(zhuǎn)移”功能的指令中， C、Z和 N應(yīng)各是什么?

(4)以下是該指令對應(yīng)的數(shù)據(jù)通路示意圖，要求給出中部件①~③的名稱或功能說明。

為提高系統(tǒng)資源利用率，合理的進程優(yōu)先級設(shè)置應(yīng)

A. P1 >P2 >P3 B. P3>P2 >P1 C. P2>P1 =P3 D. P1>P2=P3

32 . 下列關(guān)于銀行家算法的敘述中，正確的是

A. 銀行家算法可以預(yù)防死鎖

B. 當(dāng)系統(tǒng)處于安全狀態(tài)時，系統(tǒng)中一定無死鎖進程

C. 當(dāng)系統(tǒng)處于不安全狀態(tài)時，系統(tǒng)中一定會出現(xiàn)死鎖進程

D. 銀行家算法破壞了死鎖必要條件中的“請求和保持”條件

33. 在 OSI 參考摸型中，下列功能需由應(yīng)用層的相鄰層實現(xiàn)的是

A. 對話管理 B. 數(shù)據(jù)格式轉(zhuǎn)換 C. 路由選擇 D. 可靠數(shù)據(jù)傳輸

45. (7分)某博物館最多可容納500人同時參觀，有一個出入口，該出入口一次僅允許個經(jīng)過。參觀者的活動描述如下：

cobegin

參觀者進程i：

…

進門

…

參觀

…

出門

…

coend

請?zhí)砑颖匾男盘柫亢蚉、V(或wait()、signal( ))操作，以實現(xiàn)上述操作過程中的互斥與同步。

要求寫出完整的過程，說明信號量含義并賦初值。

46. (8分)某計算機主存按字節(jié)編址，邏輯地址和物理地址都是32位，頁表項大小為4字節(jié)。請回答下列問題。

(1)若使用一級頁表的分存儲管理方式，邏輯地址結(jié)構(gòu)為：

則頁的大小是多少字節(jié)?頁表最大占用多少字節(jié)?

(2)若使用二級頁表的分存儲管理方式，邏輯地址結(jié)構(gòu)為：

設(shè)邏輯地址為 LA ，請分別給出其對應(yīng)的頁目錄號和表索引達式。

(3)采用(1)中的分頁存儲管理方式，一個代碼段起始邏輯地址為0000 8000H，其長度為8KB，被裝載到從物理地址0090 0000H開始的連續(xù)主存空間中。頁表從主存0020 0000H 0020 0000H開始的物理地址處連續(xù)存放，如下圖所示(地址大小自下向上遞增)。請計算出該代碼段對應(yīng)的兩個頁表項物理地址、這中框號以及計算出該代碼段對應(yīng)的兩個頁表項物理地址、這中框號以及計算出該代碼段對應(yīng)的兩個頁表項物理地址、這兩個頁表項中的框號以及代碼頁面2的起始物理地址。

47. (9分)假設(shè)Internet的兩個自治系統(tǒng)構(gòu)成網(wǎng)絡(luò)如題 47 圖所示，自治系統(tǒng)ASI由路由器R1連接兩個子網(wǎng)構(gòu)成自治系統(tǒng)AS2由路由器R2、R3互聯(lián)并連接3個子網(wǎng)構(gòu)成。各子網(wǎng)地址、R2的接口名、R1與R3的部分接口IP地址如題47圖所示。

題47圖網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

請回答下列問題。

(1)假設(shè)路由表結(jié)構(gòu)如下所示。請利用路由聚合技術(shù)，給出R2的路由表，要求包括到達題47圖中所有子網(wǎng)的路由，且路由表中的路由項盡可能少。

(2)若R2收到一個目的IP地址為194.17.20.200的IP分組，R2會經(jīng)過哪個接口轉(zhuǎn)發(fā)該IP分組?

(3)R1與R2之間利用哪個路由協(xié)議交換信息?該路由協(xié)議的報文被封裝到哪個議的分組中進行傳輸?