2013年考研計算機統(tǒng)考408真題一、單項選擇題1.已知兩個長度分別為m和n的升序鏈表，若將它們合并為長度為m+n的降序鏈表，則最壞下的時間復雜度是1。A.O(n)B.O(m*n)C.O(min(m,n))D.O(max(m,n))2.一個棧的入棧序列為1,2,3,…,n，其出棧序列是p1,p2,p3,…,pn，若p2=3，則p3可能取值的個數(shù)是2。A.n-3B.n-2C.n-1D.無法確定3.若將關(guān)鍵字1,2,3,4,5,6,7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點的個數(shù)是3。A.0B.1C.2D.34.已知二叉樹T中6個葉結(jié)點的權(quán)分別是2,3,4,5,6,7，T的帶權(quán)（外部）路徑長度最小是4。A.27B.46C.54D.565.若X是后序線索二叉樹中的葉結(jié)點，且X存在左兄弟結(jié)點Y。則X的右線索指的是5。A.X的父結(jié)點B.以Y為根的子樹的最左下結(jié)點C.X的左兄弟結(jié)點YD.以Y為根的子樹的最右下結(jié)點6.在任意一棵非空二叉排序樹T1中，刪除某結(jié)點v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3.下列關(guān)于T1與T3的敘述中，正確的是6。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、IIIB.僅I、IVC.僅II、IIID.僅II、IV7.設圖的鄰接矩陣A如下所示。各頂點的度依次是7。精選文庫A.1,2,1,2B.2,2,1,1,C.3,4,2,3D.4,4,2,28.若對如下無向圖進行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是8。A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,dC.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g9.下列AOE網(wǎng)表示一項包含8個活動的工程，通過同時加快若干活動的進度可以縮短項中，加快其進度就可以縮短工程工期的是9。整個工程的工期。下列選A.c和eB.d和cC.f和dD.f和h10.在一顆高度為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是10。A.5B.7C.8D.1411.對給定的關(guān)鍵字序列110,119,007,911,114,120,122進行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是11。A.007,110,119,114,911,120,122B.007,110,119,114,911,122,120C.007,110,911,114,119,120,122D.110,120,911,122,114,007,11912.某計算機主頻為1.2GHz，其指令分為4類，它們在基準程序中所占比例及CPI如下表所示。該機的MIPS數(shù)是A.10012。B.200C.400D.6002—精選文庫13.某數(shù)采用IEEE754單精度浮點數(shù)格式表示為C6400000H，則該數(shù)的值是13。A.-1.5*213B.-1.5*212C.-0.5*213D.-0.5*21214.某字長為8位的計算機中，已知整型變量x,y的機器數(shù)分別為[x]=11110100，[y]補14。補=1011000。若整型變量z=2*x+y/2，則z的機器數(shù)為A.11000000B.00100100C.10101010D.溢出15.用海明碼對長度為8位的數(shù)據(jù)進行檢/糾錯時，若能糾正一位錯，則校驗位數(shù)至少為15。A.2B.3C.4D.516.某計算機主存地址空間大小為256MB，按字節(jié)編址。虛擬地址空間大小為4GB，采用頁式存儲管理，頁面大小為4KB，TLB（快表）采用全相聯(lián)映射，有4個頁表項，內(nèi)容如下表所示。則對虛擬地址03FFF180H進行虛實地址變換的結(jié)果是16。A.0153180HB.0335180HC.TLB缺失D.缺頁17.假設變址寄存器R的內(nèi)容為1000H，指令中的形式地址為2000H；地址1000H中的內(nèi)容為2000H，地址2000H中的內(nèi)容為3000H，地址3000H中的內(nèi)容為4000H，則變址尋址方式下訪問到的操作數(shù)是17。A.1000HB.2000HC.3000HD.4000H18.某CPU主頻為1.03GHz，采用4級指令流水線，每個流水段的執(zhí)行需要1個時鐘周期。假定CPU執(zhí)行了100條指令，在其執(zhí)行過程中，沒有發(fā)生任何流水線阻塞，此時流水線的吞吐率為18。A.0.25*109條指令/秒B.0.97*109條指令/秒C.1.0*109條指令/秒3—精選文庫D.1.03*109條指令/秒19.下列選項中，用于設備和設備控制器（I/O接口）之間互連的接口標準是19。A.PCIB.USBC.AGPD.CPI-Express20.下列選項中，用于提高RAID可靠性的措施有20。I.磁盤鏡像II.條帶化III.奇偶校驗IV.增加Cache機制A.僅I、IIB.僅I、IIIC.僅I、III和IVD.僅II、III和IV21.某磁盤的轉(zhuǎn)速為10000轉(zhuǎn)/分，平均尋道時間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個4KB的扇區(qū)所需的平均時間約為21。A.9msB.9.4msC.12nsD.12.4ns22.下列關(guān)于中斷I/O方式和DMA方式比較的敘述中，錯誤的是22。A.中斷I/O方式請求的是CPU處理時間，DMA方式請求的是總線使用權(quán)B.中斷響應發(fā)生在一條指令執(zhí)行結(jié)束后，DMA響應發(fā)生在一個總線事務完成后C.中斷I/O方式下數(shù)據(jù)傳送通過軟件完成，DMA方式下數(shù)據(jù)傳送由硬件完成D.中斷I/O方式適用于所有外部設備，DMA方式僅適用于快速外部設備23.用戶在刪除某文件的過程中，操作系統(tǒng)不可能執(zhí)行的操作是A.刪除此文件所在的目錄23。B.刪除與此文件關(guān)聯(lián)的目錄項C.刪除與此文件對應的文件控制塊D.刪除與此文件關(guān)聯(lián)的內(nèi)存緩沖區(qū)24.為支持CD-ROM中視頻文件的快速隨機播放，播放性能最好的文件數(shù)據(jù)塊組織方式是24。A.連續(xù)結(jié)構(gòu)B.鏈式結(jié)構(gòu)C.直接索引結(jié)構(gòu)D.多級索引結(jié)構(gòu)25.用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的處理流程是：用戶程序系統(tǒng)調(diào)用處理程序設備驅(qū)動程序中斷處理程序。其中，計算數(shù)據(jù)所在磁盤的柱面號、磁頭號、扇區(qū)號的程序是A.用戶程序25。B.系統(tǒng)調(diào)用處理程序C.設備驅(qū)動程序D.中斷處理程序4—精選文庫26.若某文件系統(tǒng)索引結(jié)點（inode）中有直接地址項和間接地址項，則下列選項中，與26。單個文件長度無關(guān)的因素是A.索引結(jié)點的總數(shù)B.間接地址索引的級數(shù)C.地址項的個數(shù)D.文件塊大小27.設系統(tǒng)緩沖區(qū)和用戶工作區(qū)均采用單緩沖，從外設讀入1個數(shù)據(jù)塊到系統(tǒng)緩沖區(qū)的時間為100，從系統(tǒng)緩沖區(qū)讀入1個數(shù)據(jù)塊到用戶工作區(qū)的時間為5，對用戶工作區(qū)的1個數(shù)據(jù)塊進行分析的時間為90（如下圖所示）。進程從外設讀入并分析2個數(shù)據(jù)塊的最短時間為27。A.200B.295C.300D.39028.下列選項中，會導致用戶進程從用戶態(tài)切換到內(nèi)核態(tài)的操作是28。I.整數(shù)除以零II.sin()函數(shù)調(diào)用III.read系統(tǒng)調(diào)用A.僅I、IIB.僅I、IIIC.僅II、IIID.I、II和III29.計算機開機后，操作系統(tǒng)最終被加載到29。A.BIOSB.ROMC.EPROMD.RAM30.若用戶進程訪問內(nèi)存時產(chǎn)生缺頁，則下列選項中，操作系統(tǒng)可能執(zhí)行的操作是30。I.處理越界錯II.置換頁III.分配內(nèi)存A.僅I、IIB.僅II、IIIC.僅I、IIID.I、II、和III31.某系統(tǒng)正在執(zhí)行三個進程P1、P2和P3，各進程的計算（CPU）時間和I/O時間比例如下表所示。5—精選文庫為提高系統(tǒng)資源利用率，合理的進程優(yōu)化級設置應為31。A.P1>P2>P3B.P3>P2>P1C.P2>P1=P3D.P1>P2=P332.下列關(guān)于銀行家算法的敘述中，正確的是A.銀行家算法可以預防死鎖32。B.當系統(tǒng)處于安全狀態(tài)時，系統(tǒng)中一定無死鎖進程C.當系統(tǒng)處于不安全狀態(tài)時，系統(tǒng)中一定會出現(xiàn)死鎖進程D.銀行家算法破壞了死鎖必要條件中的“請求和保持”條件33.在OSI參考模型中，下列功能需由應用層和相鄰層實現(xiàn)的是A.對話管理33。B.數(shù)據(jù)格式轉(zhuǎn)換C.路由選D.可靠數(shù)據(jù)傳輸擇34.若下圖為10BaseT網(wǎng)卡接收到的信號波形，則該網(wǎng)卡收到的比特串是34。A.00110110B.10101101C.01010010D.1100010135.主機甲通過1個路由器（存儲轉(zhuǎn)發(fā)方式）與主機乙互聯(lián)，兩段鏈路的數(shù)據(jù)傳輸速率均為10Mbps，主機甲分別采用報文交換和分組大小為10kb的分組交換向主機乙發(fā)送1個大小為8Mb（1M=106kb）的報文。若忽略鏈路傳播延遲、分組頭開銷和分組折裝時間，則兩種交換方式完成該報文傳輸所需的總時間分別為35。A.800ms、1600msB.801ms、1600msC.1600ms、800msD.1600ms、801ms36.下列介質(zhì)訪問控制方法中，可能發(fā)生沖突的是36。A.CDMAB.CSMAC.TDMAD.FDMA37.HDLC協(xié)議對0111110001111110組幀后對應的比特串為A.01111100001111101037。B.0111110001111101011111106—精選文庫C.01111100011111010D.01111100011111100111110138.對于100Mbps的以太網(wǎng)交換機，當輸出端口無排隊，以直通交換（cut-throughswitching）方式轉(zhuǎn)發(fā)一個以太網(wǎng)幀（不包括前導碼）時，引入的轉(zhuǎn)發(fā)延遲至少是38。A.0μsB.0.48μsC.5.12μsD.121.44μs39.主機甲與主機乙之間已建立一個TCP連接，雙方持續(xù)有數(shù)據(jù)傳輸，且數(shù)據(jù)無差錯與丟失。若甲收到1個來自乙的TCP段，該段的序號為1913、確認序號為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的TCP段的序號和確認序號分別是39。A.2046、2012B.2046、2013C.2047、2012D.2047、201340.下列關(guān)于SMTP協(xié)議的敘述中，正確的是I.只支持傳輸7比特的ASCII碼內(nèi)容II.支持在郵件服務器之間發(fā)送郵件III.支持從用戶代理向郵件服務器發(fā)送郵件IV.支持從郵件服務器向用戶代理發(fā)送郵件A.僅I、II和III40。B.僅I、II和IVC.僅I、III和IVD.僅II、III和IV二、用應題41.已知一個整數(shù)序列A=(a0,a1,…,an+1)，其中0<=ai<n(0<=i<n)。若存在ap1=ap2=…=apm=x且m>n/2(0<=pk<n,1<=k<=m)，則稱x為A的主元素。例如A=(0,5,5,3,5,7,5,5)，則5為主元素；又如A=(0,5,5,3,5,1,5,7)，則A中沒有主元素。假設A中的n個元素保存在一個一維數(shù)組中，請設計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：(1)給出算法的基本設計思想。(2)根據(jù)設計思想，采用C、C++或Java語文描述算法，關(guān)鍵之處給出注釋。(3)說明你所設計算法的時間復雜度和空間復雜度。42.設包含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，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？(2)若采用鏈式存儲結(jié)構(gòu)保存S，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？43.某32位計算機，CPU主頻為800MHz，Cache命中時的CPI為4，Cache塊大小為32字節(jié)；主存采用8體交叉存儲方式，每個體的存儲字長為32位、存儲周期為40ns；7—精選文庫存儲器總線寬度為32位，總線時鐘頻率為200MHz，支持突發(fā)傳送總線事務。每次讀突發(fā)傳送總線事務的過程包括：送首地址和命令、存儲器準備數(shù)據(jù)、傳送數(shù)據(jù)。每次突發(fā)傳送32字節(jié)，傳送地址或32位數(shù)據(jù)均需要一個總線時鐘周期。請回答下列問題，要求給出理由或計算過程。(1)CPU和總線的時鐘周期各為多少？總線的帶寬（即最大數(shù)據(jù)傳輸率）為多少？(2)Cache缺失時，需要用幾個讀突發(fā)傳送總線事務來完成一個主存塊的讀??？(3)存儲器總線完成一次讀突發(fā)傳送總線事務所需的時間是多少？(4)若程序BP執(zhí)行過程中，共執(zhí)行了100條指令，平均每條指令需進行1.2次訪存，Cache缺失率為5%，不考慮替換等開銷，則BP的CPU執(zhí)行時間是多少？44.某計算機采用16位定長指令字格式，其CPU中有一個標志存寄器，其中包含進位/錯位標志CF、零如下：ZF和符號NF。假定為該機設計了條件轉(zhuǎn)移指令，其格式其中，00000為操作碼OP；C、Z和N分別為CF、ZF和NF的對應檢測位，某檢測位為1時表示需檢測對應檢測的標志位中只要有一個為1就轉(zhuǎn)移，否則不轉(zhuǎn)移；OFFSET是相對偏移量，用補碼表示。轉(zhuǎn)移執(zhí)行時，轉(zhuǎn)移目標地址為(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，NF=0，則該指令執(zhí)行后PC的值又是多少？請給出計算過程。(3)實現(xiàn)“無符號數(shù)比較小于等于時轉(zhuǎn)移”功能的指令中，C、Z和N應各是什么？(4)以下是該指令對應的數(shù)據(jù)通路示意圖，要求給出圖中部件1)~3)的名稱或功能說明。45.某博物館最多容納500人同時參觀，有一個出入口，該出入口一次僅允許一個