2013年計算機考研統(tǒng)考408真題

絕密★啟用前2013年全國碩士研究生招生考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合（科目代碼:408）考生注意事項1.答題前，考生在試題冊指定位置上填寫考生編號和考生姓名；在答題卡指定位置上填寫報考單位、考生姓名和考生編號，并涂寫考生編號信息點。2.考生須把試題冊上的“試卷條形碼”黏貼條取下，黏貼在答題卡的“試卷條形碼黏貼位置”框中，不按規(guī)定黏貼條形碼而影響評卷結(jié)果的，責(zé)任由考生自負(fù)。3.選擇題的答案必須涂寫在答題卡和相應(yīng)題號的選項上，非選擇題的答案必須書寫在答題卡指定位置的邊框區(qū)域內(nèi)，超出答題區(qū)域書寫的答案無效；在草稿紙、試題冊上答題無效。4.填（書）寫部分必須使用黑色字跡簽字筆書寫，字跡工整、筆跡清楚；涂寫部分必須使用2B鉛筆涂寫。5.考試結(jié)束，將答題卡和試題冊按規(guī)定交回。（以下信息考生必須認(rèn)真填寫）考生編號考生姓名一、單項選擇題：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，其出棧序列是p，p2，p3，…，pn。若p=3，則p3可能取值的個12數(shù)是（）。A.n-3B.n-2C.n-1D.無法確定3.若關(guān)鍵字1，2，3，4，5，6，7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點的個數(shù)是（）。A.0B.1C.2D.34.已知三叉樹T中6個葉結(jié)點的權(quán)分別是2，3，4，5，6，7，T的帶權(quán)（外部）路徑長度最小是（）。A.27B.46C.54D.565.若X是后序線索二叉樹中的葉結(jié)點，且X存在左兄弟結(jié)點Y，則X的右線索指向的是（）。A.X的父結(jié)點B.以Y為根的子樹的最左下結(jié)點C.X的左兄弟結(jié)點YD.以Y為根的子樹的最右下結(jié)點6.在任意一棵非空二叉排序樹T1中，刪除某結(jié)點之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關(guān)于T1與T3的敘述中，正確的是（）。Ⅰ.若v是T1的葉結(jié)點，則T1與T3不同Ⅱ.若v是T1的葉結(jié)點，則T1與T3相同Ⅲ.若v不是T1的葉結(jié)點，則T1與T3不同Ⅳ.若v不是T1的葉結(jié)點，則T1與T3相同A.僅Ⅰ、ⅢB.僅Ⅰ、ⅣC.僅Ⅱ、ⅢD.僅Ⅱ、Ⅳ7.設(shè)圖的鄰接矩陣A如下所示。各頂點的度依次是（）。é0101ùêA=êúú0011ê0100úê1000?ú?A.1，2，1，2B.2，2，1，1C.3，4，2，3D.4，4，2，28.若對如下無向圖進行遍歷，則下列選項中，不．是廣度優(yōu)先遍歷序列的是（）。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個活動的工程。通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（）。A.c和eB.d和cC.f和dD.f和h10.在一株高度為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是（）。A.5B.7C.8D.1411.對給定的關(guān)鍵字序列110，119，007，911，114，120，122進行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是（）。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類，它們在基準(zhǔn)程序中所占比例及CPI如下表所示。指令類型所占比例50%CPIAB234520%CD10%20%該機的MIPS數(shù)是（）。A.100B.200C.400D.60013.某數(shù)采用IEEE754單精度浮點數(shù)格式表示為C6400000H，則該數(shù)的值是（）。A.-1.5×132B.-1.5×122C.-0.5×132D.-0.5×12214.某字長為8位的計算機中，已知整型變量x、y的機器數(shù)分別為[x]=11110100，[y]=10110000。若整型補補變量z=2*x+y/2，則z的機器數(shù)為（）。A.11000000B.00100100C.10101010D.溢出15.用海明碼對長度為8位的數(shù)據(jù)進行檢/糾錯時，若能糾正一位錯，則校驗位數(shù)至少為（）。A.2B.3C.4D.516.某計算機主存地址空間大小為256MB，按字節(jié)編址。虛擬地址空間大小為4GB，采用頁式存儲管理，頁面大小為4KB，TLB（快表）采用全相聯(lián)映射，有4個頁表項，內(nèi)容如下表所示。有效位標(biāo)記頁框號0002H0035H0351H0153H……………0101FF180H3FFF1H02FF3H03FFFH則對虛擬地址03FFF180H進行虛實地址變換的結(jié)果是（）。A.0153180HB.0035180HC.TLB缺失D.缺頁17.假設(shè)變址寄存器R的內(nèi)容為1000H，指令中的形式地址為2000H；地址1000H中的內(nèi)容為2000H，地址2000H中的內(nèi)容為3000H，地址3000H中的內(nèi)容為4000H，則變址尋址方式下訪問到的操作數(shù)是（）。A.1000HB.2000HC.3000HD.4000H18.某CPU主頻為1.03GHz，采用4級指令流水線，每個流水段的執(zhí)行需要1個時鐘周期。假定CPU執(zhí)行了100條指令，在其執(zhí)行過程中，沒有發(fā)生任何流水線阻塞，此時流水線的吞吐率為（）。9條指令/秒B.0.97×109條指令/秒A.0.25×109條指令/秒D.1.03×109條指令/秒C.1.0×1019.下列選項中，用于設(shè)備和設(shè)備控制器（I/O接口）之間互連的接口標(biāo)準(zhǔn)是（）。A.PCIB.USBC.AGPD.PCI-Express20.下列選項中，用于提高RAID可靠性的措施有（）。Ⅰ.磁盤鏡像Ⅱ.條帶化Ⅲ.奇偶校驗Ⅳ.增加Cache機制A.僅Ⅰ、ⅡB.僅Ⅰ、ⅢC.僅Ⅰ、Ⅲ和ⅣD.僅Ⅱ、Ⅲ和Ⅳ21.某磁盤的轉(zhuǎn)速為10000轉(zhuǎn)/分，平均尋道時間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個4KB的扇區(qū)所需的平均時間約為（）。A.9msB.9.4msC.12msD.12.4ms22.下列關(guān)于中斷I/O方式和DMA方式比較的敘述中，錯誤．．的是（）。A.中斷I/O方式請求的是CPU處理時間，DMA方式請求的是總線使用權(quán)B.中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，DMA響應(yīng)發(fā)生在一個總線事務(wù)完成后C.中斷I/O方式下數(shù)據(jù)傳送通過軟件完成，DMA方式下數(shù)據(jù)傳送由硬件完成D.中斷I/O方式適用于所有外部設(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)調(diào)用處理程序→設(shè)備驅(qū)動程序→中斷處理程序。其中，計算數(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ū)和用戶工作區(qū)均采用單緩沖，從外設(shè)讀入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.200B.295C.300D.39028.下列選項中，會導(dǎo)致用戶進程從用戶態(tài)切換到內(nèi)核態(tài)的操作是（）。Ⅰ.整數(shù)除以零Ⅱ.sin（）函數(shù)調(diào)用Ⅲ.read系統(tǒng)調(diào)用A.僅Ⅰ、ⅡB.僅Ⅰ、ⅢC.僅Ⅱ、ⅢD.Ⅰ、Ⅱ和Ⅲ29.計算機開機后，操作系統(tǒng)最終被加載到（）。A.BIOSB.ROMC.EPROMD.RAM30.若用戶進程訪問內(nèi)存時產(chǎn)生缺頁，則下列選項中，操作系統(tǒng)可能執(zhí)行的操作是（）。Ⅰ.處理越界錯Ⅱ.置換頁Ⅲ.分配內(nèi)存A.僅Ⅰ、ⅡB.僅Ⅱ、ⅢC.僅Ⅰ、ⅢD.Ⅰ、Ⅱ和Ⅲ31.某系統(tǒng)正在執(zhí)行三個進程P1、P2和P3，各進程的計算（CPU）時間和I/O時間比例如下表所示。進程P1計算時間I/O時間90%50%15%10%50%85%P2P3為提高系統(tǒng)資源利用率，合理的進程優(yōu)先級設(shè)置應(yīng)為（）。A.P1>P2>P3B.P3>P2>P1C.P2>P1=P3D.P1>P2=P332.下列關(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ù)傳輸34.若下圖為10BaseT網(wǎng)卡接收到的信號波形，則該網(wǎng)卡收到的比特串是（）。A.00110110B.10101101C.01010010D.1100010135.主機甲通過1個路由器（存儲轉(zhuǎn)發(fā)方式）與主機乙互聯(lián)，兩段鏈路的數(shù)據(jù)傳輸速率均為10Mbps，主機甲分別采用報文交換和分組大小為10kb的分組交換向主機乙發(fā)送1個大小為8Mb（1M=106）的報文。若忽略鏈路傳播延遲、分組頭開銷和分組拆裝時間，則兩種交換方式完成該報文傳輸所需的總時間分別為（）。A.800ms、1600msB.801ms、1600msC.1600ms、800msD.1600ms、801ms36.下列介質(zhì)訪問控制方法中，可能發(fā)生沖突的是（）。A.CDMAB.CSMAC.TDMAD.FDMA37.HDLC協(xié)議對0111110001111110組幀后對應(yīng)的比特串為（）。A.011111000011111010B.011111000111110101111110C.01111100011111010D.01111100011111100111110138.對于100Mbps的以太網(wǎng)交換機，當(dāng)輸出端口無排隊，以直通交換（cut-throughswitching）方式轉(zhuǎn)發(fā)一個以太網(wǎng)幀（不包括前導(dǎo)碼）時，引入的轉(zhuǎn)發(fā)延遲至少是（）。A.0μsB.0.48μsC.5.12μsD.121.44μs39.主機甲與主機乙之間已建立一個TCP連接，雙方持續(xù)有數(shù)據(jù)傳輸，且數(shù)據(jù)無差錯與丟失。若甲收到1個來自乙的TCP段，該段的序號為1913、確認(rèn)序號為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的TCP段的序號和確認(rèn)序號分別是（）。A.2046、2012B.2046、2013C.2047、2012D.2047、201340.下列關(guān)于SMTP協(xié)議的敘述中，正確的是（）。Ⅰ.只支持傳輸7比特ASCII碼內(nèi)容Ⅱ.支持在郵件服務(wù)器之間發(fā)送郵件Ⅲ.支持從用戶代理向郵件服務(wù)器發(fā)送郵件Ⅳ.支持從郵件服務(wù)器向用戶代理發(fā)送郵件A.僅Ⅰ、Ⅱ和ⅢB.僅Ⅰ、Ⅱ和ⅣC.僅Ⅰ、Ⅲ和ⅣD.僅Ⅱ、Ⅲ和Ⅳ二、綜合應(yīng)用題：41～47小題，共70分。請將答案寫在答題紙指定位置上。41.（13分）已知一個整數(shù)序列A=(a，a，…，a)，其中0≤ai<n(0≤i<n)。若存在ap1=ap2=…=a01n-1pm=x且m>n/2（0≤pk<n，1≤k≤m），則稱x為A的主元素。例如A=（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"}，各元素的查找概率依次為：p=0.351，p=0.152，p3=0.15，p=0.354。將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位、存儲周期為40ns；存儲器總線寬度為32位，總線時鐘頻率為200MHz，支持突發(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)移指令，其格式如下：151110987N000000CZOFFSET其中，00000為操作碼OP；C、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，NF=0，則該指令執(zhí)行后PC的值又是多少？請給出計算過程。15111098700000011011100011（3）實現(xiàn)“無符號數(shù)比較小于等于時轉(zhuǎn)移”功能的指令中，C、Z和N應(yīng)各是什么？（4）以下是該指令對應(yīng)的數(shù)據(jù)通路示意圖，要求