2013年考研計算機統(tǒng)考真題及答案解析

1、2013年全國碩士研究生入學統(tǒng)一考試計算機基礎真題一、單項選擇題：140 小題，每小題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、，2，3，4，5，6，7 依次插入到初始為空的平衡二叉樹T 中，則T 中平衡因子為0 的分支結點的個數是A. 0 B. 1 C. 2 D. 34. 已知三叉樹T 中6 個葉結點的權分別是2，3，4，5，6，7，T 的帶權(外部)路徑長度最小是A. 27 B. 46 C. 54 D. 565. 若X 是后序線索二叉樹中的葉結點，且X 存在左兄弟結點Y，則X 的右線索指向的是A. X 的父結點 B. 以Y 為根的子樹的最左下結點C. X 的左兄弟結點Y D. 以Y 為根的子樹的最右下結點6. 在任意一棵非空二叉排序樹T1 中，刪除某結點v 之后形成二叉排序樹T2，再將v 插入T2 形成二叉排序樹T

3、3。下列關于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、IV7. 設圖的鄰接矩陣A 如下所示。各頂點的度依次是A. 1，2，1，2 B. 2，2，1，1 C. 3，4，2，3 D. 4，4，2，28. 若對如下無向圖進行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是A. h，c，a，b，d，e，g，f B. e，a，f，g，b

4、，h，c，dC. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g9. 下列 AOE 網表示一項包含 8個活動的工程。通過同時加快若干進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是A.c 和 e B. d 和 e C. f和 d D. f 和 h10. 在一株高度為2的5階B樹中，所含關鍵字的個數最少是A.5 B.7 C.8 D.1411.對給定的關鍵字序列 110，119 ，007 ，911，114 ，120 ，122進行基數排序，則第2趟分配收集后得到的關鍵字序列是A. 007，110，119，114，911，120 ，122 B. 007，1

5、10，119，114，911，122，120C. 007，110，911，114，119，120，122 D. 110，120，911，122，114，007，11912. 某計算機主頻為 1.2 GHz 1.2 GHz 1.2 GHz，其指令分為 4類，它們在基準程序中所占比例及 CPICPICPI如下表所示。該機的 MIPSMIPSMIPSMIPS數是A. 100 B. 200 C. 400 D. 60013. 某數采用 IEEE 754IEEE 754IEEE 754 單精度浮點數格式表示為 C640 C640 0000 H，則該數的值是A. -1.5 ×213 B. B. -

6、1.5 ×212 C. C. -0.5x ×213 D. -0.5 ×21214. 某字長為 8位的計算機中，已知整型變量 x、y的機器數分別為x補=1 1110100，y補=1 0110000。若整型變量 z=2*x+y/2，則 z的機器數為A. 1 1000000 B. 0 0100100 C. 1 0101010 D. 溢出15 . 用海明碼對長度為 8位的數據進行檢 /糾錯時，若能糾正一位錯，則校驗位數至少為A. 2 B. 3 C. 4 D. 516. 某計算機主存地址空間大小為256 MB，按字節(jié)編址。虛擬地空間大小為4 GB，采用頁式存儲管理，頁面大小

7、為4KB，TLB(快表)采用全相聯(lián)映射，有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. 4000H18. 某CPU主頻為1.03 GHz，采用4級指令流水線，每個段的執(zhí)行需要1個時鐘周期。假定CPU執(zhí)行了1

8、00條指令，在其執(zhí)行過程中沒有發(fā)生任何流水線阻塞，此時流水線的吞吐率為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-Express20. 下列選項中，用于提高RAID可靠性的措施有I. 磁盤鏡像 II.條帶化 III. 奇偶校驗 IV. 增加 Cache機制A. 僅 I、II B. 僅 I、III C. 僅I、III和IV D

9、. 僅II、III和IV21. 某磁盤的轉速為10,000轉/分，平均尋道時間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個4KB的扇區(qū)所需平均時間約為A. 9ms B. 9.4ms C. 12ms D. 12.4ms22. 下列關于中斷 I/ O方式和 DMA 方式比較的敘述中，錯誤的是A. 中斷 I/ O方式請求的是方式請求的是 CPUCPUCPU處理時間，DMA 方式請求的是總線使用權B. 中斷響應發(fā)生在一條指令執(zhí)行結束后，中斷響應發(fā)生在一條指令執(zhí)行結束后，DMA響應發(fā)生在一個總線事務完成后C. 中斷 I/ O方式下數據傳送通過軟件完成，方式下數據傳送通過軟件

10、完成，DMA方式下數據傳送由硬件完成D. 中斷 I/ O方式適用于所有外部設備，方式適用于所有外部設備，DMA方式僅適用于快速外部設備23 . 用戶在刪除某文件的過程中，操作系統(tǒng)不可能執(zhí)行是A. 刪除此文件所在的目錄 B. 刪除與此文件關聯(lián)的目錄項C. 刪除與此文件對應的控制塊 D. 釋放與此文件關聯(lián)的內存級沖區(qū)24. 為支持CD-ROM中視頻文件的快速隨機播放，播放性能最好的文件數據塊組織方式是A. 連續(xù)結構 B. 鏈式結構 C. 直接索引結構 D. 多級索引結鉤25. 用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的處理系統(tǒng)的處理流程是：用戶程序系統(tǒng)調用處理程序設備駱動程序中斷處理程序。其中，計算數據

11、所在磁盤的柱面號、磁頭號、扇區(qū)號的程序是A. 用戶程序 B. 系統(tǒng)調用處理程序C. 設備驅動程序 D. 中斷處理程序26. 若某文件系統(tǒng)索引結點(inode)中有直接地址項和間接地址項，則下列選項中，與單個文件長度無關的因素是A. 索引結點的總數 B. 間接地址索引的級數C. 地址項的個數 D. 文件塊大小27 . 設系統(tǒng)緩沖區(qū)和用戶工作均采單，從外讀入1個數據塊到系統(tǒng)緩沖區(qū)的時間為100，從系統(tǒng)緩沖區(qū)讀入 1個數據塊到用戶工作區(qū)的時間為5，對用戶工作區(qū)中的1個數據塊進行分析的時間為90(如下圖所示)。進程從外設讀入并分析2個數據塊的最短時間是A. 200 B. 295 C. 300 D .3

12、9028. 下列選項中，會導致用戶進程從態(tài)切換到內核的操作是I. 整數除以零 II. sin( )函數調用 III. read系統(tǒng)調用A. 僅 I、II B. 僅 I、III C. 僅 II 、III D. I、II和III29. 計算機開后，操作系統(tǒng)最終被加載到A. BIOS B. ROM C. EPROM D. RAM30. 若用戶進程訪問內存時產生缺頁，則下列選項中，操作系統(tǒng)可能執(zhí)行的是I. 處理越界錯 II. 置換頁 III. 分配內存A. 僅 I、II B. 僅 II 、III C. 僅 I、III D. I、II 和 III31. 某系統(tǒng)正在執(zhí)行三個進程P1、P2和P3，各進程的計

13、算(CPUCPUCPU)時間和I/OI/O時間比例如下表所示。34. 若下圖為10BaseT網卡接收到的信號波形，則該比特串是A. 0011 0110 B. 1010 1101 C. 0101 0010 D. 1100 010135. 主機甲通過1個路由器個路由器(存儲轉發(fā)方式)與主機乙互聯(lián)，兩段鏈路的數據傳輸速率均為10Mbps,主機甲分別采用報文交換和組大小為10kb的分組交換向主機乙發(fā)送1個大小為8Mb(1M=10 6)的報文。若忽略鏈路傳播延遲、分組頭開銷和拆裝時間，則兩種交換方式完成該報文傳輸所需的總時間分別為A. 800ms 、1600ms B. 801ms、1600msC. 16

14、00ms、800ms D. 1600ms 、801ms36. 下列介質訪問控制方法中，可能發(fā)生沖突的是A. CDMA B. CSMA C. TDMAC D. FDMA37. HDLC 37. HDLC37. HDLC協(xié)議對01111100 01111110組幀后對應的比特串為A. 01111100 00111110 10 B. 01111100 01111101 01111110C. 01111100 01111101 0 D. 01111100 01111110 0111110138. 對于100Mbps的以太網交換機，當輸出端口無排隊直通(cut-through switching)方式轉

15、發(fā)一個以太網幀(不包括前導碼)時，引入的轉發(fā)延遲至少是A. 0 s B. 0.48 s C. 5.12 s D. 121.44 s39. 主機甲與乙之間已建立一個TCP連接，雙方持續(xù)有數據傳輸,且無差錯與丟失。若甲收到1個來自乙的TCP段，該段的序號為1913、確認序號為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的 TCP 段的序號和確認分別是A. 2046 、2012 B. 2046、2013 C. 2047 、2012 D. 2047 201240. 下列關于SMTP 協(xié)議的敘述中，正確的是I. 只支持傳輸7比特ASCII碼內容II. 支持在郵件服務器之間發(fā)送郵件III. 支持從用戶

16、代理向郵件服務器發(fā)送郵件IV. 支持從郵件服務器向用戶代理發(fā)送郵件A. 僅I、II 和III B. 僅I、II 和IVC. 僅I、III 和IV D. 僅II、III 和IV二、綜合應用題：4147 小題，共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)說明你所設計算

17、法的時間復雜度和空間復雜度。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，且要求平均查找長度更短，則元素應如

18、何排列?應使用何種查找方法?查找成功時的平均查找長度是多少?43.(9 分)某32 位計算機，CPU 主頻為800MHz，Cache 命中時的CPI 為4，Cache 塊大小為32 字節(jié);主存采用8 體交叉存儲方式，每個體的存儲字長為32 位、存儲周期為40 ns;存儲器總線寬度為32 位，總線時鐘頻率為200 MHz，支持突發(fā)傳送總線事務。每次讀突發(fā)傳送總線事務的過程包括：送首地址和命令、存儲器準備數據、傳送數據。每次突發(fā)傳送32 字節(jié)，傳送地址或32 位數據均需要一個總線時鐘周期。請回答下列問題，要求給出理由或計算過程。(1)CPU 和總線的時鐘周期各為多少?總線的帶寬(即最大數據傳輸率)

19、為多少?(2)Cache 缺失時，需要用幾個讀突發(fā)傳送總線事務來完成一個主存塊的讀取?(3)存儲器總線完成一次讀突發(fā)傳送總線事務所需的時間是多少?(4)若程序BP 執(zhí)行過程中，共執(zhí)行了100 條指令，平均每條指令需進行1.2 次訪存，Cache 缺失率為5%，不考慮替換等開銷，則BP 的CPU 執(zhí)行時間是多少?44.(14 分)某計算機采用16 位定長指令字格式，其CPU 中有一個標志寄存器，其中包含進位/借位標志CF、零標志ZF 和符號標志NF。假定為該機設計了條件轉移指令，其格式如下：其中，00000為操作碼OP;C、Z和 N分別為CF、ZF和NF的對應檢測位，某測位為1時表示需檢測對應標

20、志，需檢測的標志位中只要有一個為1就轉移，否則就不轉移，例如，若C=1，Z=0，N=1，則需檢測CF和NF的值，當 CF=1或NF=1時發(fā)生轉移;OFFSET是相對偏移量，用補碼表示。轉移執(zhí)行時，轉移目標地址為(PC)+2+2×OFFSET;順序執(zhí)行時，下條指令地址為(PC)+2。請回答下列問題。(1)該計算機存儲器按字節(jié)編址，還是按字編址?該條件轉移指令向后(反向)最多可跳轉最多少條指令?(2)某條件轉移指令的地址為200CH，指令內容如下圖所示，若該執(zhí)行時CF=0，ZF=0，NF=1，則該指令執(zhí)行后PC的值是多少?若該指令執(zhí)行時CF=1，ZF=0 Z，NF=0，則該指令執(zhí)行后PC

21、的值又是多少?請給出計算過程。(3)實現“無符號數比較小于等時轉移”功能的指令中， C、Z和 N應各是什么?(4)以下是該指令對應的數據通路示意圖，要求給出中部件的名稱或功能說明。為提高系統(tǒng)資源利用率，合理的進程優(yōu)先級設置應A. P1 >P2 >P3 B. P3>P2 >P1 C. P2>P1 =P3 D. P1>P2=P332 . 下列關于銀行家算法的敘述中，正確的是A. 銀行家算法可以預防死鎖B. 當系統(tǒng)處于安全狀態(tài)時，系統(tǒng)中一定無死鎖進程C. 當系統(tǒng)處于不安全狀態(tài)時，系統(tǒng)中一定會出現死鎖進程D. 銀行家算法破壞了死鎖必要條件中的“請求和保持”條件33.

22、 在 OSI 參考摸型中，下列功能需由應用層的相鄰層實現的是A. 對話管理 B. 數據格式轉換 C. 路由選擇 D. 可靠數據傳輸45. (7分)某博物館最多可容納500人同時參觀，有一個出入口，該出入口一次僅允許個通過。參觀者的活動描述如下：cobegin參觀者進程i：進門;參觀;出門;coend請?zhí)砑颖匾男盘柫亢蚉、V(或wait()、signal( )操作，以實現上述操作過程中的互斥與同步。要求寫出完整的過程，說明信號量含義并賦初值。46. (8分)某計算機主存按字節(jié)編址，邏輯地址和物理地址都是32位，頁表項大小為4字節(jié)。請回答下列問題。(1)若使用一級頁表的分存儲管理方式，邏輯地址結

23、構為：則頁的大小是多少字節(jié)?頁表最大占用多少字節(jié)?(2)若使用二級頁表的分存儲管理方式，邏輯地址結構為：設邏輯地址為 LA ，請分別給出其對應的頁目錄號和表索引達式。(3)采用(1)中的分頁存儲管理方式，一個代碼段起始邏輯地址為0000 8000H，其長度為8KB，被裝載到從物理地址0090 0000H開始的連續(xù)主存空間中。頁表從主存0020 0000H 0020 0000H開始的物理地址處連續(xù)存放，如下圖所示(地址大小自下向上遞增)。請計算出該代碼段對應的兩個頁表項物理地址、這中框號以及計算出該代碼段對應的兩個頁表項物理地址、這中框號以及計算出該代碼段對應的兩個頁表項物理地址、這兩個頁表項中

24、的框號以及代碼頁面2的起始物理地址。47. (9分)假設Internet的兩個自治系統(tǒng)構成網絡如題 47 圖所示，自治系統(tǒng)ASI由路由器R1連接兩個子網構成;自治系統(tǒng)AS2由路由器R2、R3互聯(lián)并連接3個子網構成。各子網地址、R2的接口名、R1與R3的部分接口IP地址如題47圖所示。題47圖網絡拓撲結構請回答下列問題。(1)假設路由表結構如下所示。請利用路由聚合技術，給出R2的路由表，要求包括到達題47圖中所有子網的路由，且路由表中的路由項盡可能少。(2)若R2收到一個目的IP地址為194.17.20.200的IP分組，R2會通過哪個接口轉發(fā)該IP分組?(3)R1與R2之間利用哪個路由協(xié)議交換

25、信息?該路由協(xié)議的報文被封裝到哪個議的分組中進行傳輸? 計算機學科專業(yè)基礎綜合試題參考答案及解析（2013 年）一、單項選擇題1. D 解析：m、n 是兩個升序鏈表，長度分別為 m 和 n。在合并過程中，最壞的情況是兩個鏈表 中的元素依次進行比較，比較的次數最少是 m 和 n 中的最小值。2. C 解析：除了 3 本身以外，其他的值均可以取到，因此可能取值的個數為 n - 1 。3. D解析：利用 7 個關鍵字構建平衡二叉樹 T，平衡因子為 0 的分支結點個數為 3，構建的平衡二叉樹如下圖所示。52613474. B解析：利用三叉樹的 6 個葉子結點的權構建最小帶權生成樹，最小的帶權

26、路徑長度為(2 + 3) ´ 3 + (4 + 5) ´ 2 + (6 + 7) ´1 = 46 。5. A 解析：根據后續(xù)線索二叉樹的定義，X 結點為葉子結點且有左兄弟，那么這個結點為右孩子 結點，利用后續(xù)遍歷的方式可知 X 結點的后繼是其父結點，即其右線索指向的是父結點。6. C 解析：在一棵二叉排序樹中刪除一個結點后再將此結點插入到二叉排序樹中，如果刪除的結 點是葉子結點，那么在插入結點后，后來的二叉排序樹與刪除結點之前相同。如果刪除的結 點不是葉子結點，那么再插入這個結點后，后來的二叉樹可能發(fā)生變化，不完全相同。7. C 解析：各頂點的度是矩陣中此結點對應

27、的橫行和縱列非零元素之和。8. D 解析：D 選項是深度優(yōu)先遍歷不是廣度優(yōu)先遍歷的順序。9. C 解析：根據 AOE 網的定義可知，關鍵路徑上的活動時間同時減少，可以縮短工期。10. A 解析：一棵高度為 2 的 5 階 B 樹，根結點只有到達 5 個關鍵字的時候才能產生分裂，成為 高度為 2 的 B 樹。11. C 解析：基數排序的第 1 趟排序是按照個位數字來排序的，第 2 趟排序是按然十位數字的大 小進行排序的，答案是 C 選項。12. C解析：基準程序的 CPI = 2 ´ 0.5 + 3´ 0.2 + 4 ´ 0.1 + 5 ´ 0.2 = 3

28、 ，計算機的主頻為 1.2GHa，為 1 200MHz，該機器的是 MIPS 為 1 200/3=400。13. A解析：IEEE 754 單精度浮點數格式為 C640 0000H，二進制格式為 1100 0110 0100 00000000 0000 0000 0000，轉換為標準的格式為： 因此，浮點數的值為 -1.5 ´ 213 。14. A 解析：將 x 左移一位，y 右移一位，兩個數的補碼相加的機器數為 1 1000000，答案選擇 A。15. C解析：設校驗位的位數為 k，數據位的位數為 n，應滿足下述關系： 2k ³ n + k + 1 。 n = 8 ，當

29、k = 4 時， 24 (= 16) > 8 + 4 + 1(= 13) 符合要求，校驗位至少是 4 位。16. A解析：虛擬地址為 03FF F180H，其中頁號為 03FFFH，頁內地址為 180H，根據題目中給出的頁表項可知頁標記為 03FFFH 所對應的頁框號為 0153H，頁框號與頁內地址之和即為物 理地址 015 3180 H。17. D解析：根據變址尋址的主要方法，變址寄存器的內容與形式地址的內容相加之后，得到操作數的實際地址，根據實際地址訪問內存，獲取操作數 4000H。18. CS階碼尾數11000 1100100 0000 0000 0000 0000 0000解析：

30、采用 4 級流水執(zhí)行 100 條指令，在執(zhí)行過程中共用 4 + (100 -1) = 103 個時鐘周期。CPU 的主頻是 1.03 GHz，也就是說每秒鐘有 1.03 G 個時鐘周期。流水線的吞吐率為 1.03G´ 100 /103 1.0 10= ´ 9 條指令/秒。19. B 解析：設備和設備控制器之間的接口是 USB 接口，其余選項不符合，答案為 B。20. B 解析：能夠提高 RAID 可靠性的措施主要是對磁盤進行鏡像處理和進行奇偶校驗。其余選 項不符合條件。21. B 解析：磁盤轉速是 10 000 轉/分鐘，平均轉一轉的時間是 6 ms，因此平均查詢扇區(qū)的時間

31、 是 3 ms，平均尋道時間是 6 ms，讀取 4 KB 扇區(qū)信息的時間為 0.2 ms，信息延遲的時間為 0.2 ms，總時間為 3+6+0.2+0.2=9.4 ms。22. D解析：中斷處理方式：在 I/O 設備輸入每個數據的過程中，由于無需 CPU 干預，因而可使CPU 與 I/O 設備并行工作。僅當輸完一個數據時，才需 CPU 花費極短的時間去做些中斷處理。因此中斷申請使用的是 CPU 處理時間，發(fā)生的時間是在一條指令執(zhí)行結束之后，數據是在軟件的控制下完成傳送。而 DMA 方式與之不同。DMA 方式：數據傳輸的基本單位是 數據塊，即在 CPU 與 I/O 設備之間，每次傳送至少一個數據

32、塊；DMA 方式每次申請的是 總線的使用權，所傳送的數據是從設備直接送入內存的，或者相反；僅在傳送一個或多個 數據塊的開始和結束時，才需 CPU 干預，整塊數據的傳送是在控制器的控制下完成的。答 案 D 的說法不正確。23. A 解析：刪除文件不需要刪除文件所在的目錄，而文件的關聯(lián)目錄項和文件控制塊需要隨著 文件一同刪除，同時釋放文件的關聯(lián)緩沖區(qū)。24. A解析：為了實現快速隨機播放，要保證最短的查詢時間，即不能選取鏈表和索引結構，因 此連續(xù)結構最優(yōu)。25. C 解析：計算磁盤號、磁頭號和扇區(qū)號的工作是由設備驅動程序完成的，答案選 C。26. A 解析：四個選項中，只有 A 選項是與單個文件長

33、度無關的。27. C解析：數據塊 1 從外設到用戶工作區(qū)的總時間為 105，在這段時間中，數據塊 2 沒有進行操作。在數據塊 1 進行分析處理時，數據塊 2 從外設到用戶工作區(qū)的總時間為 105，這段 時間是并行的。再加上數據塊 2 進行處理的時間 90，總共是 300，答案為 C。28. B 解析：需要在系統(tǒng)內核態(tài)執(zhí)行的操作是整數除零操作和 read 系統(tǒng)調用函數，答案選 B。29. D 解析：系統(tǒng)開機后，操作系統(tǒng)的程序會被自動加載到內存中的系統(tǒng)區(qū)，這段區(qū)城是 RAM， 答案選 D。30. B 解析：用戶進程訪問內存時缺頁會發(fā)生缺頁中斷。發(fā)生缺頁中斷，系統(tǒng)地執(zhí)行的操作可能 是置換頁面或分配內

34、存。系統(tǒng)內沒有越界的錯誤，不會進行越界出錯處理。31. B 解析：為了合理地設置進程優(yōu)先級，應該將進程的 CPU 利用時間和 I/O 時間做綜合考慮， 答案選 B。32. B 解析：銀行家算法是避免死鎖的方法。利用銀行家算法，系統(tǒng)處于安全狀態(tài)時沒有死鎖進 程，答案選 B。33. B解析：OSI 參考模型中，應用層的相鄰層是表示層。表示層是 OSI 七層協(xié)議的第六層。表示層的目的是表示出用戶看得懂的數據格式，實現與數據表示有關的功能。主要完成數據 字符集的轉換、數據格式化和文本壓縮、數據加密、解密等工作。因此答案選 B。34. A 解析：根據信號編碼的基本規(guī)則可知，網卡收到的比特串為 0011

35、0110，答案選 A。35. D 解析：不進行分組時，發(fā)送一個報文的時延是 8 Mb/10 Mb/s=800 ms，在接收端接收此報文 件 的 時 延 也 是 800 ms ， 共 計 1 600 ms 。 進 行 分 組 后 ， 發(fā) 送 一 個 報 文 的 時 延 是 10 kb/10Mb/s=1 ms，接收一個報文的時延也是 1 ms，但是在發(fā)送第二個報文時，第一個報文 已經開始接收。共計有 800 個分組，總時間為 801 ms。36. B 解析：介質訪向控制協(xié)議中能夠發(fā)生沖突的是 CSMA 協(xié)議，答案為 B。37. A解析：HDLC 協(xié)議對比特串進行組幀時，HDLC 數據幀以位模式 0

36、111 1110 標識每一個幀的 開始和結束，因此在幀數據中凡是出現了 5 個連續(xù)的位“1”的時候，就會在輸出的位流中 填充一個“0”。所以答案為 A。38. B 解析：直通交換方式是指以太網交換機可以在各端口間交換數據。它在輸入端口檢測到一 個數據包時，檢查該包的包頭，獲取包的目的地址，啟動內部的動態(tài)查找表轉換成相應的 輸出端口，在輸入與輸出交叉處接通，把數據包直通到相應的端口，實現交換功能。通常 情況下，直通交換方式只檢查數據包的包頭即前 14 個字節(jié)，由于不需要考慮前導碼，只需 要檢測目的地址的 6 B，所以最短的傳輸延遲是 0.48s。39. B解析：若甲收到 1 個來自乙的 TCP

37、段，該段的序號 seq=1913、確認序號 ack = 2046、有效載 荷 為 100 字 節(jié) ， 則 甲 立 即 發(fā) 送 給 乙 的 TCP 段 的 序 號 seq1=ack=2046 和 確 認 序 號ack1=seq+100=2013，答案為 B。二、綜合應用題41.【答案要點】 （1）給出算法的基本設計思想： 分）（4 算法的策略是從前向后掃描數組元素，標記出一個可能成為主元素的元素 Num。然 后重新計數，確認 Num 是否是主元素。算法可分為以下兩步： 選取候選的主元素：依次掃描所給數組中的每個整數，將第一個遇到的整數 Num 保存 到 c 中，記錄 Num 的出現次數為 1；若

38、遇到的下一個整數仍等于 Num，則計數加 1， 否則計數減 1；當計數減到 0 時，將遇到的下一個整數保存到 c 中，計數重新記為 1， 開始新一輪計數，即從當前位置開始重復上述過程，直到掃描完全部數組元素。 判斷 c 中元素是否是真正的主元素：再次掃描該數組，統(tǒng)計 c 中元素出現的次數，若 大于 n/2，則為主元素；否則，序列中不存在主元素。（2）算法實現： 分）（7int Majority ( int A , int n )int i, c, count=1;c = A0;for ( i=1; i<n; i+ ) if ( Ai = = c ) count+;elseif ( cou

39、nt > 0) count-;else c = Ai;/ / c 用來保存候選主元素，count 用來計數/ / 設置 A0為候選主元素 / / 查找候選主元素/ / 對 A 中的候選主元素計數/ / 處理不是候選主元素的情況/ / 更換候選主元素，重新計數count = 1; if ( count>0 )for ( i=count=0; i<n; i+ ) if ( Ai = = c ) count+;if ( count> n/2 ) return c;else return -1;【（1）（2）的評分說明】、 若考生設計的算法滿足題目的功能要求且正確，則（1） （

40、2）根據所實現算法的效率、 給分，細則見下表：時間復雜度O(n)O(n)O ( nlog2n )O ( n2 )空間復雜度O(1)O(n)其他其他（1）得分4433（2）得分7665如采用計數排序思想，見表后 Majority1 程序如采用其他排序的思想其他方法說明/ / 統(tǒng)計候選主元素的實際出現次數/ / 確認候選主元素/ / 不存在主元素int Majority1 ( int A , int n) / / 采用計數排序思想，時間：O ( n ), 空間：O ( n )int k, * p, max;p = ( int * ) malloc ( sizeof ( int ) * n );fo

41、r ( k=0; k < n ; k+ ) p k =0;max = 0 ;for ( k=0; k<n; k+ ) p Ak +;if (pAk >p max ) max = Ak;if ( p max > n/2 ) return max;else return -1;/ / 計數器+1/ / 記錄出現次數最多的元素/ / 申請輔助計數數組/ / 計數數組清 0 若在算法的基本設計思想描述中因文字表達沒有非常清晰反映出算法思路，但在算法 實現中能夠清晰看出算法思想且正確的，可參照的標準給分。 若算法的基本設計思想描述或算法實現中部分正確，可參照中各種情況的相應給分

42、標準酌情給分。 參考答案中只給出了使用 C 語言的版本，使用 C+或 Java 語言的答案視同使用 C 語 言。（3）說明算法復雜性： 分）（2 參考答案中實現的程序的時間復雜度為 O（n），空間復雜度為 O（1）。 【評分說明】若考生所估計的時間復雜度與空間復雜度與考生所實現的算法一致，可各給 1 分。42.【答案要點】 （1）采用順序存儲結構，數據元素按其查找概率降序排列。 分）（2 采用順序查找方法。 分）（1 查找成功時的平均查找長度= 0.35×1+0.35×2+0.15×3+0.15×4=2.1。 分）（2 （2）【答案一】采用鏈式存儲結構，

43、數據元素按其查找概率降序排列，構成單鏈表。 分）（2采用順序查找方法。 分）（1查找成功時的平均查找長度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。 分）（2【答案二】采用二叉鏈表存儲結構，構造二叉排序樹，元素存儲方式見下圖。 分）（2采用二叉排序樹的查找方法。 分）（1查找成功時的平均查找長度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。 分）（2【（1）（2）的評分說明】、 若考生以實際元素表示“降序排列”，同樣給分。 若考生正確求出與其查找方法對應的查找成功時的平均查

44、找長度，給 2 分；若計算過 程正確，但結果錯誤，給 1 分。 若考生給出其他更高效的查找方法且正確，可參照評分標準給分。43.【答案要點】 （1）CPU 的時鐘周期為：1/800 MHz = 1.25 ns。 分）（1 總線的時鐘周期為：1/200 MHz = 5 ns。 分）（1總線帶寬為：4 B×200 MHz = 800 MB/s 或 4 B/5 ns = 800 MB/s。 分）（1（2）Cache 塊大小是 32 B，因此 Cache 缺失時需要一個讀突發(fā)傳送總線事務讀取一個主存 塊。 分）（1（3）一次讀突發(fā)傳送總線事務包括一次地址傳送和 32 B 數據傳送：用 1 個

45、總線時鐘周期傳輸地址；每隔 40 ns/8 = 5 ns 啟動一個體工作（各進行 1 次存?。?，第一個體讀數據 花費 40 ns，之后數據存取與數據傳輸重疊；用 8 個總線時鐘周期傳輸數據。讀突發(fā) 傳送總線事務時間：5 ns + 40 ns + 8×5 ns = 85 ns。 分）（2（4）BP 的 CPU 執(zhí)行時間包括 Cache 命中時的指令執(zhí)行時間和 Cache 缺失時帶來的額外開 銷。命中時的指令執(zhí)行時間：100×4×1.25 ns = 500 ns。（1 分）指令執(zhí)行過程中 Cache 缺失時的額外開銷：1.2×100×5%×

46、;85 ns = 510 ns。BP 的 CPU 執(zhí)行時間： 500 ns+510 ns=1 010 ns。 分）（2【評分說明】 執(zhí)行時間采用如下公式計算時，可酌情給分。 執(zhí)行時間=指令條數×CPI×時鐘周期×命中率+訪存次數×缺失率×缺失損失 計算公式正確但運算結果不正確時，可酌情給分。44.【答案要點】 （1）因為指令長度為 16 位，且下條指令地址為（PC）+2，故編址單位是字節(jié)。 分）（1 偏移 OFFSET 為 8 位補碼，范圍為-128127，故相對于當前條件轉移指令，向后最多可跳轉 127 條指令。 分）（2【評分說明】若正確給

47、出 OFFSET 的取值范圍，則酌情給分。（2）指令中 C = 0，Z = 1，N = 1，故應根據 ZF 和 NF 的值來判斷是否轉移。當 CF=0，ZF=0，NF=1 時，需轉移。 分）已知指令中偏移量為 1110 0011B=E3H，符號擴展（1 后為 FFE3 H，左移一位（乘 2）后為 FFC6 H，故 PC 的值（即轉移目標地址）為 200CH+2+FFC6H=1FD4H。 分）當 CF = 1，ZF = 0，NF = 0 時不轉移。 分）PC（2（1 的值為：200CH+2=200EH。 分）（1 （3）指令中的 C、Z 和 N 應分別設置為 C=Z=1，N=0。 分）（3 （4）部件：指令寄存器（用于存放當前指令）；部件：移位寄存器（用于左移一位）； 部件：