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

1、2013年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)基礎(chǔ)真題一、單項(xiàng)選擇題：140 小題，每小題2 分，共80 分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)符合試題要求。1. 已知兩個(gè)長(zhǎng)度分別為m 和n 的升序鏈表，若將它們合并為一個(gè)長(zhǎng)度為m+n 的降序鏈表，則最壞情況下的時(shí)間復(fù)雜度是A. O(n) B. O(m.n) C. O(min(m,n) D. O(max(m,n)2. 一個(gè)棧的入棧序列為1, 2,3, ,n ，其出棧序列是1 2 3 , , , , n p p p p 。若2 p . 3，則3 p 可能取值的個(gè)數(shù)是A. n .3 B. n . 2 C. n .1 D. 無法確定3. 若將關(guān)鍵字1

2、，2，3，4，5，6，7 依次插入到初始為空的平衡二叉樹T 中，則T 中平衡因子為0 的分支結(jié)點(diǎn)的個(gè)數(shù)是A. 0 B. 1 C. 2 D. 34. 已知三叉樹T 中6 個(gè)葉結(jié)點(diǎn)的權(quán)分別是2，3，4，5，6，7，T 的帶權(quán)(外部)路徑長(zhǎng)度最小是A. 27 B. 46 C. 54 D. 565. 若X 是后序線索二叉樹中的葉結(jié)點(diǎn)，且X 存在左兄弟結(jié)點(diǎn)Y，則X 的右線索指向的是A. X 的父結(jié)點(diǎn) B. 以Y 為根的子樹的最左下結(jié)點(diǎn)C. X 的左兄弟結(jié)點(diǎn)Y D. 以Y 為根的子樹的最右下結(jié)點(diǎn)6. 在任意一棵非空二叉排序樹T1 中，刪除某結(jié)點(diǎn)v 之后形成二叉排序樹T2，再將v 插入T2 形成二叉排序樹T

3、3。下列關(guān)于T1 與T3 的敘述中，正確的是I. 若v 是T1 的葉結(jié)點(diǎn)，則T1 與T3 不同II. 若v 是T1 的葉結(jié)點(diǎn)，則T1 與T3 相同III. 若v 不是T1 的葉結(jié)點(diǎn)，則T1 與T3 不同IV. 若v 不是T1 的葉結(jié)點(diǎn)，則T1 與T3 相同A. 僅I、III B. 僅I、IV C. 僅II、III D. 僅II、IV7. 設(shè)圖的鄰接矩陣A 如下所示。各頂點(diǎn)的度依次是A. 1，2，1，2 B. 2，2，1，1 C. 3，4，2，3 D. 4，4，2，28. 若對(duì)如下無向圖進(jìn)行遍歷，則下列選項(xiàng)中，不是廣度優(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 網(wǎng)表示一項(xiàng)包含 8個(gè)活動(dòng)的工程。通過同時(shí)加快若干進(jìn)度可以縮短整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是A.c 和 e B. d 和 e C. f和 d D. f 和 h10. 在一株高度為2的5階B樹中，所含關(guān)鍵字的個(gè)數(shù)最少是A.5 B.7 C.8 D.1411.對(duì)給定的關(guān)鍵字序列 110，119 ，007 ，911，114 ，120 ，122進(jìn)行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是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. 某計(jì)算機(jī)主頻為 1.2 GHz 1.2 GHz 1.2 GHz，其指令分為 4類，它們?cè)诨鶞?zhǔn)程序中所占比例及 CPICPICPI如下表所示。該機(jī)的 MIPSMIPSMIPSMIPS數(shù)是A. 100 B. 200 C. 400 D. 60013. 某數(shù)采用 IEEE 754IEEE 754IEEE 754 單精度浮點(diǎn)數(shù)格式表示為 C640 C640 0000 H，則該數(shù)的值是A. -1.5 ×213 B. B. -

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

7、為4KB，TLB(快表)采用全相聯(lián)映射，有4個(gè)頁表項(xiàng)，內(nèi)容如下表所示。則對(duì)虛擬地址03FF F180H進(jìn)行虛實(shí)地址變換的結(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. 4000H18. 某CPU主頻為1.03 GHz，采用4級(jí)指令流水線，每個(gè)段的執(zhí)行需要1個(gè)時(shí)鐘周期。假定CPU執(zhí)行了1

8、00條指令，在其執(zhí)行過程中沒有發(fā)生任何流水線阻塞，此時(shí)流水線的吞吐率為A. 0.25×10 9條指令/秒 B. 0.97 ×10 9條指令 /秒C. 1.0 ×10 9條指令/秒 D. 1.03 ×10 9條指令 /秒19. 下列選項(xiàng)中，用于設(shè)備和控制器 (I/O接口 )之間互連的接口標(biāo)準(zhǔn)是A. PCI B. USB C. AGP D. PCI-Express20. 下列選項(xiàng)中，用于提高RAID可靠性的措施有I. 磁盤鏡像 II.條帶化 III. 奇偶校驗(yàn) IV. 增加 Cache機(jī)制A. 僅 I、II B. 僅 I、III C. 僅I、III和IV D

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

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

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

12、9028. 下列選項(xiàng)中，會(huì)導(dǎo)致用戶進(jìn)程從態(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和III29. 計(jì)算機(jī)開后，操作系統(tǒng)最終被加載到A. BIOS B. ROM C. EPROM D. RAM30. 若用戶進(jìn)程訪問內(nèi)存時(shí)產(chǎn)生缺頁，則下列選項(xiàng)中，操作系統(tǒng)可能執(zhí)行的是I. 處理越界錯(cuò) II. 置換頁 III. 分配內(nèi)存A. 僅 I、II B. 僅 II 、III C. 僅 I、III D. I、II 和 III31. 某系統(tǒng)正在執(zhí)行三個(gè)進(jìn)程P1、P2和P3，各進(jìn)程的計(jì)

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

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

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

16、代理向郵件服務(wù)器發(fā)送郵件IV. 支持從郵件服務(wù)器向用戶代理發(fā)送郵件A. 僅I、II 和III B. 僅I、II 和IVC. 僅I、III 和IV D. 僅II、III 和IV二、綜合應(yīng)用題：4147 小題，共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個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素;否則輸出-1。要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C 或C+或Java 語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算

17、法的時(shí)間復(fù)雜度和空間復(fù)雜度。42. (10 分)設(shè)包含4 個(gè)數(shù)據(jù)元素的集合S= "do"，"for"，" repeat"，" while"，各元素的查找概率依次為：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。將S 保存在一個(gè)長(zhǎng)度為4的順序表中，采用折半查找法，查找成功時(shí)的平均查找長(zhǎng)度為2.2。請(qǐng)回答：(1)若采用順序存儲(chǔ)結(jié)構(gòu)保存S，且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時(shí)的平均查找長(zhǎng)度是多少?(2)若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存S，且要求平均查找長(zhǎng)度更短，則元素應(yīng)如

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、遇到的下一個(gè)整數(shù)仍等于 Num，則計(jì)數(shù)加 1， 否則計(jì)數(shù)減 1；當(dāng)計(jì)數(shù)減到 0 時(shí)，將遇到的下一個(gè)整數(shù)保存到 c 中，計(jì)數(shù)重新記為 1， 開始新一輪計(jì)數(shù)，即從當(dāng)前位置開始重復(fù)上述過程，直到掃描完全部數(shù)組元素。 判斷 c 中元素是否是真正的主元素：再次掃描該數(shù)組，統(tǒng)計(jì) c 中元素出現(xiàn)的次數(shù)，若 大于 n/2，則為主元素；否則，序列中不存在主元素。（2）算法實(shí)現(xiàn)： 分）（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 用來計(jì)數(shù)/ / 設(shè)置 A0為候選主元素 / / 查找候選主元素/ / 對(duì) A 中的候選主元素計(jì)數(shù)/ / 處理不是候選主元素的情況/ / 更換候選主元素，重新計(jì)數(shù)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）的評(píng)分說明】、 若考生設(shè)計(jì)的算法滿足題目的功能要求且正確，則（1） （

40、2）根據(jù)所實(shí)現(xiàn)算法的效率、 給分，細(xì)則見下表：時(shí)間復(fù)雜度O(n)O(n)O ( nlog2n )O ( n2 )空間復(fù)雜度O(1)O(n)其他其他（1）得分4433（2）得分7665如采用計(jì)數(shù)排序思想，見表后 Majority1 程序如采用其他排序的思想其他方法說明/ / 統(tǒng)計(jì)候選主元素的實(shí)際出現(xiàn)次數(shù)/ / 確認(rèn)候選主元素/ / 不存在主元素int Majority1 ( int A , int n) / / 采用計(jì)數(shù)排序思想，時(shí)間：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;/ / 計(jì)數(shù)器+1/ / 記錄出現(xiàn)次數(shù)最多的元素/ / 申請(qǐng)輔助計(jì)數(shù)數(shù)組/ / 計(jì)數(shù)數(shù)組清 0 若在算法的基本設(shè)計(jì)思想描述中因文字表達(dá)沒有非常清晰反映出算法思路，但在算法 實(shí)現(xiàn)中能夠清晰看出算法思想且正確的，可參照的標(biāo)準(zhǔn)給分。 若算法的基本設(shè)計(jì)思想描述或算法實(shí)現(xiàn)中部分正確，可參照中各種情況的相應(yīng)給分

42、標(biāo)準(zhǔn)酌情給分。 參考答案中只給出了使用 C 語言的版本，使用 C+或 Java 語言的答案視同使用 C 語 言。（3）說明算法復(fù)雜性： 分）（2 參考答案中實(shí)現(xiàn)的程序的時(shí)間復(fù)雜度為 O（n），空間復(fù)雜度為 O（1）。 【評(píng)分說明】若考生所估計(jì)的時(shí)間復(fù)雜度與空間復(fù)雜度與考生所實(shí)現(xiàn)的算法一致，可各給 1 分。42.【答案要點(diǎn)】 （1）采用順序存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素按其查找概率降序排列。 分）（2 采用順序查找方法。 分）（1 查找成功時(shí)的平均查找長(zhǎng)度= 0.35×1+0.35×2+0.15×3+0.15×4=2.1。 分）（2 （2）【答案一】采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，

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

44、找長(zhǎng)度，給 2 分；若計(jì)算過 程正確，但結(jié)果錯(cuò)誤，給 1 分。 若考生給出其他更高效的查找方法且正確，可參照評(píng)分標(biāo)準(zhǔn)給分。43.【答案要點(diǎn)】 （1）CPU 的時(shí)鐘周期為：1/800 MHz = 1.25 ns。 分）（1 總線的時(shí)鐘周期為：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 缺失時(shí)需要一個(gè)讀突發(fā)傳送總線事務(wù)讀取一個(gè)主存 塊。 分）（1（3）一次讀突發(fā)傳送總線事務(wù)包括一次地址傳送和 32 B 數(shù)據(jù)傳送：用 1 個(gè)

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

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

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