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

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

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 可能取值的個數是

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 網表示一項包含 8個活動的工程。經過同時加快若干進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是

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

10. 在一株高度為2的5階B樹中，所含關鍵字的個數最少是

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

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

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類，它們在基準程序中所占比例及 CPICPICPI如下表所示。

該機的 MIPSMIPSMIPSMIPS數是

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. 下列選項中，用于設備和控制器 (I/O接口 )之間互連的接口標準是

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. 某磁盤的轉速為10,000轉/分，平均尋道時間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個4KB的扇區所需平均時間約為

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

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

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

B. 中斷響應發生在一條指令執行結束后，中斷響應發生在一條指令執行結束后，DMA響應發生在一個總線事務完成后

C. 中斷 I/ O方式下數據傳送經過軟件完成，方式下數據傳送經過軟件完成，DMA方式下數據傳送由硬件完成

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

23 . 用戶在刪除某文件的過程中，操作系統不可能執行是

A. 刪除此文件所在的目錄 B. 刪除與此文件關聯的目錄項

C. 刪除與此文件對應的控制塊 D. 釋放與此文件關聯的內存級沖區

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

A. 連續結構 B. 鏈式結構 C. 直接索引結構 D. 多級索引結鉤

25. 用戶程序發出磁盤I/O請求后，系統的處理系統的處理流程是：用戶程序&rarr系統調用處理程序&rarr設備駱動程序&rarr中斷處理程序。其中，計算數據所在磁盤的柱面號、磁頭號、扇區號的程序是

A. 用戶程序 B. 系統調用處理程序

C. 設備驅動程序 D. 中斷處理程序

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

A. 索引結點的總數 B. 間接地址索引的級數

C. 地址項的個數 D. 文件塊大小

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

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

28. 下列選項中，會導致用戶進程從態切換到內核的操作是

I. 整數除以零 II. sin( )函數調用 III. read系統調用

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

29. 計算機開后，操作系統最終被加載到

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

30. 若用戶進程訪問內存時產生缺頁，則下列選項中，操作系統可能執行的是

I. 處理越界錯 II. 置換頁 III. 分配內存

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

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

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

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

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

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

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

36. 下列介質訪問控制方法中，可能發生沖突的是

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

37. HDLC 37. HDLC37. HDLC協議對01111100 01111110組幀后對應的比特串為

A. 01111100 00111110 10 B. 01111100 01111101 01111110

C. 01111100 01111101 0 D. 01111100 01111110 01111101

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

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

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

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

40. 下列關于SMTP 協議的敘述中，正確的是

I. 只支持傳輸7比特ASCII碼內容

II. 支持在郵件服務器之間發送郵件

III. 支持從用戶代理向郵件服務器發送郵件

IV. 支持從郵件服務器向用戶代理發送郵件

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

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

二、綜合應用題：41~47 小題，共70 分。

41.

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

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

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

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

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

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

(2)若采用鏈式存儲結構保存S，且要求平均查找長度更短，則元素應如何排列?應使用何種查找方法?查找成功時的平均查找長度是多少?

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

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

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

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

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

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

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

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

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

(3)實現“無符號數比較小于等時轉移”功能的指令中， C、Z和 N應各是什么?

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

為提高系統資源利用率，合理的進程優先級設置應

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

32 . 下列關于銀行家算法的敘述中，正確的是

A. 銀行家算法可以預防死鎖

B. 當系統處于安全狀態時，系統中一定無死鎖進程

C. 當系統處于不安全狀態時，系統中一定會出現死鎖進程

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

33. 在 OSI 參考摸型中，下列功能需由應用層的相鄰層實現的是

A. 對話管理 B. 數據格式轉換 C. 路由選擇 D. 可靠數據傳輸

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

cobegin

參觀者進程i：

…

進門

…

參觀

…

出門

…

coend

請添加必要的信號量和P、V(或wait()、signal( ))操作，以實現上述操作過程中的互斥與同步。

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

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

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

則頁的大小是多少字節?頁表最大占用多少字節?

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

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

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

47. (9分)假設Internet的兩個自治系統構成網絡如題 47 圖所示，自治系統ASI由路由器R1連接兩個子網構成自治系統AS2由路由器R2、R3互聯并連接3個子網構成。各子網地址、R2的接口名、R1與R3的部分接口IP地址如題47圖所示。

題47圖網絡拓撲結構

請回答下列問題。

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

(2)若R2收到一個目的IP地址為194.17.20.200的IP分組，R2會經過哪個接口轉發該IP分組?

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