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

2013年考研計(jì)算機(jī)統(tǒng)考408真題一、單項(xiàng)選擇題己知兩個(gè)長(zhǎng)度分別為m和n的升序鏈表，若將它們合并為長(zhǎng)度為m+n的降序鏈表，則最壞F的時(shí)間復(fù)雜度是1QO(n)O(m*n)O(min(m,n))O(max(m,n))一個(gè)棧的入棧序列為1,2,3，…,n,其出棧序列是pi,P2,P3，…,Pn，若P2=3,則以可能取TOC\o"1-5"\h\z值的個(gè)數(shù)是2。n-3n-2n-1無法確定若將關(guān)鍵字123,4,5,6,7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點(diǎn)的個(gè)數(shù)是。0123己知二叉樹T中6個(gè)葉結(jié)點(diǎn)的權(quán)分別是234,5,6,7,T的帶權(quán)(外部)路徑長(zhǎng)度最小是4。27465456若X是后序線索二叉樹中的葉結(jié)點(diǎn)，且X存在左兄弟結(jié)點(diǎn)Y。則X的右線索指的是._5_oX的父結(jié)點(diǎn)以Y為根的子樹的最左下結(jié)點(diǎn)X的左兄弟結(jié)點(diǎn)Y以Y為根的子樹的最右下結(jié)點(diǎn)在任意一棵非空二叉排序樹T】中，刪除某結(jié)點(diǎn)v之后形成二叉排序樹T2,再將v插入T2形成二叉排序樹T,.下列關(guān)于Ti與T3的敘述中，正確的是o若v是Ti的葉結(jié)點(diǎn)，則Ti與Ta不同若v是L的葉結(jié)點(diǎn)，則L與「相同若v不是Ti的葉結(jié)點(diǎn)，則L與「不同若v不是Ti的葉結(jié)點(diǎn)，則Ti與T3相同僅I、III僅I、IV僅II、III僅II、IV設(shè)圖的鄰接矩陣A如下所示。各頂點(diǎn)的度依次是—。0101001101001000TOC\o"1-5"\h\z12L22,2,1,1,3,4234,4,2,2若對(duì)如下無向圖進(jìn)行遍歷，則下?列選項(xiàng)中，不是廣度優(yōu)先遍歷序列的是8。h,c,a,b,d,e,g,fe,a,f,g,b,h,c,dd,b,c,a,h,e,f,ga,b,c,d,h,e,f,g下列AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程，通過同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短TOC\o"1-5"\h\z整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是9。c和ed和cf和df和h在一顆高度為2的5階B樹中，所含關(guān)鍵字的個(gè)數(shù)最少是10357814對(duì)給定的關(guān)鍵字序列110,119,007,911,114,120,122進(jìn)行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是11Q007,110,119,114,911,120,122007,110,119,114,911,122,120007,110,911,114,119,120,122110,120,911,122,114,007,119某計(jì)算機(jī)主頻為1.2GHz,其指令分為4類，它們?cè)诨鶞?zhǔn)程序中所占比例及CPI如下表所示。指令綁所占比例CPIA50%2B20%C10%4D20%5該機(jī)的MIPS數(shù)是—12。TOC\o"1-5"\h\z100200400600某數(shù)采用IEEE754單精度浮點(diǎn)數(shù)格式表示為C6400000H,則該數(shù)的值是E3。-1.5*213-1.5*212-0.5*2】3-0.5*212某字長(zhǎng)為8位的計(jì)算機(jī)中，己知整型變量x,y的機(jī)器數(shù)分別為［x］補(bǔ)=11110100,［y］補(bǔ)=1011000。若整型變量z=2*x+y/2,則z的機(jī)器數(shù)為14°110000000010010010101010溢出用海明碼對(duì)長(zhǎng)度為8位的數(shù)據(jù)進(jìn)行檢/糾錯(cuò)時(shí)，若能糾正一位錯(cuò)，則校驗(yàn)位數(shù)至少為15。TOC\o"1-5"\h\z2345某計(jì)算機(jī)主存地址空間大小為256MB,按字節(jié)編址。虛擬地址空間大小為4GB,采用頁式存儲(chǔ)管理，頁面大小為4KB,TLB（快表）采用全相聯(lián)映射，有4個(gè)頁表項(xiàng)，容如下表所示。砌立梳己頁框號(hào)???nFF180H0002H???13FFF1HOO35H0O2FF3HO351H103HTHO153H???則對(duì)虛擬地址03FFF180H進(jìn)行虛實(shí)地址變換的結(jié)果是16o0153180H0335180HTLB缺失缺頁假設(shè)變址寄存器R的容為1000H,指令中的形式地址為2000H；地址1000H中的容為2000H,地址2000H中的容為3000H,地址3000H中的容為4000H,則變址尋址方式下訪問到的操作數(shù)是一17。TOC\o"1-5"\h\z1000H2000H3000H4000H某CPU主頻為1.03GHz,采用4級(jí)指令流水線，每個(gè)流水段的執(zhí)行需要1個(gè)時(shí)鐘周期。假定CPU執(zhí)行了100條指令，在其執(zhí)行過程中，沒有發(fā)生任何流水線阻塞，此時(shí)流水線的吞吐率為18。0.25*IO。條指令/秒0.97*109條指令/秒1.0*109條指令/秒1.03*109條指令/秒下列選項(xiàng)中，用于設(shè)備和設(shè)備控制器（I/O接II）之間互連的接II標(biāo)準(zhǔn)是19。PCIUSBAGPCPI-Express下列選項(xiàng)中，用于提高RAID可棠性的措施有20。磁盤鏡像條帶化奇偶校驗(yàn)增加Cache機(jī)制僅I、II僅I、III僅I、III和IV僅II、III和IV某磁盤的轉(zhuǎn)速為10000轉(zhuǎn)/分，平均尋道時(shí)間是6ms,磁盤傳輸速率是20MB/s,磁盤控制器延遲為0.2ms,讀取一個(gè)4KB的扇區(qū)所需的平均時(shí)間約為21°TOC\o"1-5"\h\z9ms9.4ms12ns12.4ns下列關(guān)于中斷I/O方式和DMA方式比較的敘述中，錯(cuò)誤的是22°中斷I/O方式請(qǐng)求的是CPU處理時(shí)間，DMA方式請(qǐng)求的是總線使用權(quán)中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，DMA響應(yīng)發(fā)生在一個(gè)總線事務(wù)完成后中斷I/O方式下數(shù)據(jù)傳送通過軟件完成，DMA方式下數(shù)據(jù)傳送由硬件完成中斷I/O方式適用于所有外部設(shè)備，DMA方式僅適用于快速外部設(shè)備用戶在刪除某文件的過程中，操作系統(tǒng)不可能執(zhí)行的操作是一23°刪除此文件所在的目錄刪除與此文件關(guān)聯(lián)的目錄項(xiàng)刪除與此文件對(duì)應(yīng)的文件控制塊刪除與此文件關(guān)聯(lián)的存緩沖區(qū)為支持CD-ROM中視頻文件的快速隨機(jī)播放，播放性能最好的文件數(shù)據(jù)塊組織方式是24O連續(xù)結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)直接索引結(jié)構(gòu)多級(jí)索引結(jié)構(gòu)用戶程序發(fā)出磁盤I/O請(qǐng)求后，系統(tǒng)的處理流程是：用戶程序今系統(tǒng)調(diào)用處理程序今設(shè)備驅(qū)動(dòng)程序今中斷處理程序。其中，計(jì)算數(shù)據(jù)所在磁盤的柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)的程序是25。用戶程序系統(tǒng)調(diào)用處理程序設(shè)備驅(qū)動(dòng)程序中斷處理程序若某文件系統(tǒng)索引結(jié)點(diǎn)(inode)中有直接地址項(xiàng)和間接地址項(xiàng)，則下列選項(xiàng)中，與單個(gè)文件長(zhǎng)度無關(guān)的因素是26。索引結(jié)點(diǎn)的總數(shù)間接地址索引的級(jí)數(shù)地址項(xiàng)的個(gè)數(shù)文件塊大小設(shè)系統(tǒng)緩沖區(qū)和用戶工作區(qū)均采用單緩沖，從外設(shè)讀入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í)間為27°用戶工作區(qū)系統(tǒng)緩神區(qū)「100外設(shè)TOC\o"1-5"\h\z200295300390F列選項(xiàng)中，會(huì)導(dǎo)致用戶進(jìn)程從用戶態(tài)切換到核態(tài)的操作是28,整數(shù)除以零sin()函數(shù)調(diào)用read系統(tǒng)調(diào)用僅I、II僅I、III僅II、IIII、II和III計(jì)算機(jī)開機(jī)后，操作系統(tǒng)最終被加載到29°BIOSROMEPROMRAM若用戶進(jìn)程訪問存時(shí)產(chǎn)生缺頁，則下列選項(xiàng)中，操作系統(tǒng)可能執(zhí)行的操作是—30OI?處理越界錯(cuò)置換頁分配存僅I、II僅II、III僅I、IIII、II、和III某系統(tǒng)正在執(zhí)行三個(gè)進(jìn)程PLP2和P3,各進(jìn)程的計(jì)算(CPU)時(shí)間和I/O時(shí)間比例如下表所示。進(jìn)程計(jì)f司I/O時(shí)間Pl90%10%P250%50%P315%85%為提高系統(tǒng)資源利用率，合理的進(jìn)程優(yōu)化級(jí)設(shè)置應(yīng)為3]°P1>P2>P3P3>P2>P1P2>P1=P3P1>P2=P3下列關(guān)于銀行家算法的敘述中，正確的是一32。銀行家算法可以預(yù)防死鎖當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)，系統(tǒng)中一定無死鎖進(jìn)程當(dāng)系統(tǒng)處于不安全狀態(tài)時(shí)，系統(tǒng)中一定會(huì)出現(xiàn)死鎖進(jìn)程銀行家算法破壞了死鎖必要條件中的“請(qǐng)求和保持”條件在OSI參考模型中，下列功能需由應(yīng)用層和相鄰層實(shí)現(xiàn)的是33°對(duì)話管理數(shù)據(jù)格式轉(zhuǎn)換路由選擇可靠數(shù)據(jù)傳輸TOC\o"1-5"\h\z若下圖為lOBaseT網(wǎng)卡接收到的信號(hào)波形，則該網(wǎng)卡收到的比特串是34。?????■,tinjTLnjJTLrarIIIIlliI00110110101011010101001011000101主機(jī)甲通過1個(gè)路由器(存儲(chǔ)轉(zhuǎn)發(fā)方式)與主機(jī)乙互聯(lián)，兩段鏈路的數(shù)據(jù)傳輸速率均為10Mbps,主機(jī)甲分別采用報(bào)文交換和分組大小為10kb的分組交換向主機(jī)乙發(fā)送1個(gè)大小為8Mb(lM=106kb)的報(bào)文。若忽略鏈路傳播延遲、分組頭開銷和分組折裝時(shí)間，則兩種交換方式完成該報(bào)文傳輸所需的總時(shí)間分別為主800ms、1600ms801ms、1600ms1600ms、800ms1600ms、801msTOC\o"1-5"\h\z下列介質(zhì)訪問控制方法中，可能發(fā)生沖突的是36。CDMACSMATDMAFDMAHDLC協(xié)議對(duì)0111110001111110組幀后對(duì)應(yīng)的比特串為37o01111100001111101001111100011111010111111001111100011111010011111000111111001111101對(duì)于100Mbps的以太網(wǎng)交換機(jī)，當(dāng)輸出端II無排隊(duì)，以直通交換(cut-throughswitching)方式轉(zhuǎn)發(fā)一個(gè)以太網(wǎng)幀(不包括前導(dǎo)碼)時(shí)，引入的轉(zhuǎn)發(fā)延遲至少是_38oOps0.48ps5.12f.ts121.44*主機(jī)甲與主機(jī)乙之間已建立一個(gè)TCP連接，雙方持續(xù)有數(shù)據(jù)傳輸，且數(shù)據(jù)無差錯(cuò)與丟失。若甲收到1個(gè)來自乙的TCP段，該段的序號(hào)為1913、確認(rèn)序號(hào)為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的TCP段的序號(hào)和確認(rèn)序號(hào)分別是39■A.2046、2012B.2046、2013C.2047、2012D.2047、2013下列關(guān)于SMTP協(xié)議的敘述中，正確的是一40°只支持傳輸7比特的ASCII碼容支持在服務(wù)器之間發(fā)送支持從用戶代理向服務(wù)器發(fā)送支持從服務(wù)器向用戶代理發(fā)送僅I、II和III僅I、II和IV僅I、III和IV僅II、III和IV二、綜合應(yīng)用題己知一個(gè)整數(shù)序列A=(a0,ai,...zan+i),其中0<=ai<n(0<=i<n)o若存在api=aP2=...=apm=x且m>n/2(0<=pk<n,l<=k<=m),則稱x為A的主元素。例如A=(0,5,5,3,5,7,5,5),則5為主元素：又如A=(0,5,5,3,5,l,5,7),則A中沒有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：給出算法的基本設(shè)計(jì)思想。根據(jù)設(shè)計(jì)思想，采用C、C++或Java語文描述算法，關(guān)鍵之處給出注釋。說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。設(shè)包含4個(gè)數(shù)據(jù)元素的集合S={“do",“for”,“repeat”,“while”},各元素的查找概率依次為：pl=0.35,p2=0.15/P3=0.15,p4=0.35o將S保存在一個(gè)長(zhǎng)度為4的順序列中，采用折半查找法，查找成功時(shí)的平均查找長(zhǎng)度為2.2。請(qǐng)回答：若采用順序存儲(chǔ)結(jié)構(gòu)保存S,且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時(shí)的平均查找長(zhǎng)度是多少？若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存S,且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時(shí)的平均查找長(zhǎng)度是多少？某32位計(jì)算機(jī)，CPU主頻為800MHz,Cache命中時(shí)的CPI為4,Cache塊大小為32字節(jié)；主存采用8體交叉存儲(chǔ)方式，每個(gè)體的存儲(chǔ)字長(zhǎng)為32位、存儲(chǔ)周期為40ns；存儲(chǔ)器總線寬度為32位，總線時(shí)鐘頻率為200MHz,支持突發(fā)傳送總線事務(wù)。每次讀突發(fā)傳送總線事務(wù)的過程包括：送首地址和命令、存儲(chǔ)器準(zhǔn)備數(shù)據(jù)、傳送數(shù)據(jù)。每次突發(fā)傳送32字節(jié)，傳送地址或32位數(shù)據(jù)均需要一個(gè)總線時(shí)鐘周期。請(qǐng)回答下列問題，要求給出理由或計(jì)算過程。CPU和總線的時(shí)鐘周期各為多少？總線的帶寬(即最大數(shù)據(jù)傳輸率)為多少？Cache缺失時(shí)，需要用幾個(gè)讀突發(fā)傳送總線事務(wù)來完成一個(gè)主存塊的讀取？存儲(chǔ)器總線完成一次讀突發(fā)傳送總線事務(wù)所需的時(shí)間是多少？若程序BP執(zhí)行過程中，共執(zhí)行了100條指令，平均每條指令需進(jìn)行1.2次訪存,Cache缺失率為5%,不考慮替換等開銷，則BP的CPU執(zhí)行時(shí)間是多少？某計(jì)算機(jī)采用16位定長(zhǎng)指令字格式，其CPU中有一個(gè)標(biāo)志寄存器，其中包含進(jìn)位/錯(cuò)位標(biāo)志CF、零標(biāo)志ZF和符號(hào)標(biāo)志NF。假定為該機(jī)設(shè)計(jì)了條件轉(zhuǎn)移指令，其格式如下：1511109S7000000CZNOFFSET其中，00000為操作碼OP：C、Z和N分別為CF、ZF和NF的對(duì)應(yīng)檢測(cè)位，某檢測(cè)位為1時(shí)表示需檢測(cè)對(duì)應(yīng)標(biāo)志位，需檢測(cè)的標(biāo)志位中只要有一個(gè)為1就轉(zhuǎn)移，否則不轉(zhuǎn)移：OFFSET是相對(duì)偏移量，用補(bǔ)碼表示。轉(zhuǎn)移執(zhí)行時(shí)，轉(zhuǎn)移目標(biāo)地址為(PC)+2+2*OFFSET：順序執(zhí)行時(shí)，下條指令地址為(PC)+2°請(qǐng)回答下列問題。該計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址還是按字編址？該條件轉(zhuǎn)移指令向后(反向)最多可跳轉(zhuǎn)多少條指令？某條件轉(zhuǎn)移指令的地址為200CH,指令容如下圖所示,若該指令執(zhí)行時(shí)CF=0,ZF=0,NF=1,則該指令執(zhí)行后PC的值是多少？若該指令執(zhí)行時(shí)CF=1,ZF=0,NF=0,則該指令執(zhí)行后PC的值又是多少？請(qǐng)給出計(jì)算過程。15111098700000001111100011⑶實(shí)現(xiàn)“無符號(hào)數(shù)比較小于等于時(shí)轉(zhuǎn)移”功能的指令中，c、Z和N應(yīng)各是什么？以下是該指令對(duì)應(yīng)的數(shù)據(jù)通路示意圖，要求給出圖中部件1)~3)的名稱或功能說明。某博物館最多容納500人同時(shí)參觀，有一個(gè)出入II,該出入口一次僅允許一個(gè)人通過。參觀者的活動(dòng)如下：cobegin參觀者進(jìn)程i；

進(jìn)門;參觀;出門;46.47.）coend請(qǐng)?zhí)砑颖匾男盘?hào)量和P、V（或wait。、signal。）操作，以實(shí)現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號(hào)量的信義并賦初值。46.47.（1）若使用一級(jí)頁表的分布存儲(chǔ)管理方式，邏輯地址結(jié)構(gòu)為：頁