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

2012年考研計(jì)算機(jī)統(tǒng)考408真題單項(xiàng)選擇題求整數(shù)n(n>=0)階乘的算法如下，其時(shí)間復(fù)雜度是 1 。Intfact(intn){ If(n<=1)return1; Returnn*fact(n-1);O(log2n)O(n)O(nlog2n)O(n2)已知操作符包括’+’、’-‘、’*’、’/’、’(‘和’)’。將中綴表達(dá)式a+b-a*((c+d/e-f)+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符，若棧初始為空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是 2 。57811若一棵二叉樹的前序遍歷序列為a,e,b,d,c，后序遍歷序列為b,c,d,e,a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn) 3 。只有e有e,b有e,c無法確定若平衡二叉的高度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為 4 。10203233對有n個(gè)結(jié)點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是 5 。O(n)O(e)O(n+e)O(n*e)若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是 6 。存在，且唯一存在，且不唯一存在，可能不唯一無法確定是否存在對如下有向圖帶權(quán)圖，若采用迪杰斯特位（Dijkstra）算法求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是c，后續(xù)得到的其余最短路徑的目標(biāo)頂點(diǎn)依次是 7 。d,e,fe,d,ff,d,ef,e,d下列關(guān)于最小生成樹的敘述中，正確的是 8 。I.最小生成樹的代價(jià)唯一。II.所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中。III.使用普里姆(Prim)算法從不同頂點(diǎn)開始得到的最小生成樹一定相同。IV.使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不同。僅I僅II僅I、III僅II、IV已知一顆3階B-樹，如下圖所示。刪除關(guān)鍵字78得到一顆新B-樹，其最右葉結(jié)點(diǎn)中的關(guān)鍵字是 3 。6060,6262,6565在內(nèi)部排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束都至少能夠確定一個(gè)元素最終位置的方法是 10 。I.簡單選擇排序II.希爾排序III.快速排序IV.堆排序V.二路歸并排序僅I、III、IV僅I、III、V僅II、III、IV僅III、IV、V對一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是 11 。排序的總趟數(shù)元素的移動(dòng)次數(shù)使用輔助空間的數(shù)量元素之間的比較次數(shù)假定基準(zhǔn)程序A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為100秒，其中90秒為CPU時(shí)間，其余為I/O時(shí)間。若CPU速度提高50%，I/O速度不變，則運(yùn)行基準(zhǔn)程序A所超耗費(fèi)的時(shí)間是 12 。55秒60秒65秒70秒假定編譯器規(guī)定int和short型長度分別為32位和16位，執(zhí)行下列C語言語句：unsignedshortx=65530;unsignedinty=x;得到y(tǒng)的機(jī)器數(shù)為 13 。00007FFAH0000FFFAHFFFF7FFAHFFFFFFFAHfloat類型（即IEEE754單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù)是 14 。2126-21032127-21042127-21032128-2104某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int型和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存儲(chǔ)。某C語言程序段如下：struct{ inta; charb; shortc; }record; record.a=273;若record變量的首地址為0xC008，則地址0xC008中內(nèi)容及record.c的地址分別為 15 。0x00、0xC00D0x00、0xC00E0x11、0xC00D0x11、0xC00E下列關(guān)于內(nèi)存(flashmemory)的敘述中，錯(cuò)誤的是 16 。信息可讀可寫，并且讀、寫速度一樣快存儲(chǔ)元由MOS管組成，是一種半導(dǎo)體存儲(chǔ)器掉電后信息不丟失，是一種易失性存儲(chǔ)器采用隨機(jī)訪問方式，可替代計(jì)算機(jī)外部存儲(chǔ)器假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交換的塊大小為1個(gè)字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方式和LRU替換策略。訪問的主存地址依次為0,4,8,2,0,6,8,6,4,8時(shí)，命中Cache的次數(shù)是 17 。1234某計(jì)算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有33個(gè)微命令，構(gòu)成5個(gè)互斥類，分別包含7、3、12、5和6個(gè)微命令，則操作控制字段至少有 18 。5位6位15位33位某同步總線的時(shí)鐘頻率為100MHz，寬度為32位，地址/數(shù)據(jù)線復(fù)用，每傳輸一個(gè)地址或數(shù)據(jù)占用一個(gè)時(shí)鐘周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫”總線事務(wù)傳輸128位數(shù)據(jù)所需要的時(shí)間至少是 19 。20ns40ns50ns80ns下列關(guān)于USB總線特性的描述中，錯(cuò)誤的是 20 ?？蓪?shí)現(xiàn)外設(shè)的即插即用和熱拔插可通過級聯(lián)方式連接多臺(tái)是一種通信總線，連接不同外設(shè)同時(shí)傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高下列選項(xiàng)中，在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔?21 。I.I/O接口中的命令字II.I/O接口中的狀態(tài)字III.中斷類型號僅I、II僅I、III僅II、III僅I、II、III響應(yīng)外部中斷的過程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)外，還包括 22 。I.關(guān)中斷II.保存通用寄存器的內(nèi)存III.形成中斷服務(wù)程序入口地址并送PC僅I、II僅I、III僅II、IIII、II、III下列選項(xiàng)中，不可能在用戶態(tài)發(fā)生的事件是 23 。系統(tǒng)調(diào)用外部中斷進(jìn)程切換缺頁中斷處理和子程序調(diào)用都需要壓棧以保護(hù)現(xiàn)場，中斷處理一定會(huì)保存而子程序調(diào)用不需要保存其內(nèi)容的是 24 。程序計(jì)數(shù)器程序狀態(tài)字寄存器通用數(shù)據(jù)寄存器通用地址寄存器下列關(guān)于虛擬存儲(chǔ)器的敘述中，正確的是 24 。虛擬存儲(chǔ)只能基于連續(xù)分配技術(shù)虛擬儲(chǔ)存只能基于非連續(xù)分配技術(shù)虛擬存儲(chǔ)容量只受外在容量的限制虛擬存儲(chǔ)容量只受內(nèi)存容量的限制操作系統(tǒng)的I/O子系統(tǒng)通常由四個(gè)層次組成，每一層明確定義了與鄰近層次的接口。其合理的層次組織排列順序是 25 。用戶級I/O軟件、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序用戶級I/O軟件、設(shè)備無關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動(dòng)程序用戶級I/O軟件、設(shè)備驅(qū)動(dòng)程序、設(shè)備無關(guān)軟件、中斷處理程序用戶級I/O軟件、中斷處理程序、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動(dòng)程序假設(shè)5個(gè)進(jìn)程P0、P1、P2、P3、P4共享三類資源R1、R2、R3，這些資源總數(shù)分別為18、6、22。T0時(shí)刻的資源分配情況如下表所示，此時(shí)存在的一個(gè)安全序列是 26 。P0,P2,P4,P1,P3P1,P0,P3,P4,P2P2,P1,P0,P3,P4P3,P4,P2,P1,P0若一個(gè)用戶進(jìn)程通過read系統(tǒng)調(diào)用讀取一個(gè)磁盤文件中數(shù)據(jù)，則下列關(guān)于此過程的敘述中，正確的 28 。I.若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)II.請求read系統(tǒng)調(diào)用會(huì)導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)III.read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱僅I、II僅I、III僅II、IIII、II和III一個(gè)多道批處理系統(tǒng)中僅有P1和P2兩個(gè)作業(yè)，P2比P1晚5ms到達(dá)，它們的計(jì)算和I/O操作順序如下：P1：計(jì)算60ms，I/O80ms，計(jì)算20msP2：計(jì)算120ms，I/O40ms，計(jì)算40ms若不考慮調(diào)度和切換時(shí)間，則完成兩個(gè)作業(yè)需要的時(shí)間最少是 29 。240ms260ms340ms360ms若某單處理器多進(jìn)程系統(tǒng)中有多個(gè)就緒態(tài)進(jìn)程，則下列關(guān)于處理機(jī)調(diào)度的敘述中，錯(cuò)誤的是 30 。在進(jìn)程結(jié)束時(shí)能進(jìn)行處理機(jī)調(diào)度創(chuàng)建新進(jìn)程后能進(jìn)行處理機(jī)調(diào)度在進(jìn)程處于臨界區(qū)時(shí)不能進(jìn)行處理機(jī)調(diào)度在系統(tǒng)調(diào)用完成并返回用戶態(tài)時(shí)能進(jìn)行處理機(jī)調(diào)度下列關(guān)于進(jìn)程和線程的敘述中，正確的是 31 。不管系統(tǒng)是否支持線程，進(jìn)程都是資源分配的基本單位線程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位系統(tǒng)級線程和用戶及緩和的切換都需要內(nèi)核的支持同一進(jìn)程中的各個(gè)線程擁有各自不同的地址空間下列選項(xiàng)中，不能改善磁盤設(shè)備I/O性能的是 32 。重排I/O請求次序在一個(gè)磁盤上設(shè)置多個(gè)分區(qū)預(yù)讀和滯后寫優(yōu)化文件物理塊的分布在TCP/IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是 33 。PPPIPUDPTCP在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序是 34 。機(jī)械特性功能特性過程特性電氣特性以太網(wǎng)的MAC協(xié)議提供的是 35 。無連接不可靠服務(wù)無連接可靠服務(wù)有連接不可靠服務(wù)有連接可靠服務(wù)兩臺(tái)主機(jī)之間的數(shù)據(jù)鏈路層采用后退N幀協(xié)議（GBN）傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為16kbps，單向傳播時(shí)延為270ms，數(shù)據(jù)幀長度范圍是128~512字節(jié)，接收方總是以與數(shù)據(jù)幀等長的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號的比特?cái)?shù)至少為 36 。5432下列關(guān)于IP路由器功能的描述中，正確的是 37 。I.運(yùn)行路由協(xié)議，設(shè)置路由表II.監(jiān)測到擁塞時(shí)，合理丟棄IP分組III.對收到的IP分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)腎P分組不丟失IV.根據(jù)收到的IP分組的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出路線上僅III、IV僅I、II、III僅I、II、IVI、II、III、IVARP協(xié)議的功能是 38 。根據(jù)IP地址查詢MAC地址根據(jù)MAC地址查詢IP地址根據(jù)域名查詢IP地址根據(jù)IP地址查詢域名某主機(jī)的IP地址為180.80.77.55，子網(wǎng)掩碼為255.255.252.0。若該主機(jī)向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是 39 。180.80.76.0180.80.76.255180.80.77.255180.80.79.255若用戶1與用戶2之間發(fā)送和接收電子郵件的過程如下圖所示，則目的地址可以是 40 。SMTP、SMTP、SMTPPOP3、SMTP、POP3POP3、SMTP、SMTPSMTP、SMTP、POP3綜合應(yīng)用題設(shè)有6個(gè)有序表A、B、C、D、E，分別含有10、35、40、50、60和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個(gè)表最終合并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請回答下列問題。給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。根據(jù)你的合并過程，描述N（N>=2）個(gè)不等長升序表的合并策略，并說明理由。假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)空間，例如，’loading’和’being’的存儲(chǔ)映像如下圖所示。設(shè)str1和str2分別指向兩個(gè)單詞所在單鏈表的頭結(jié)點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為，請?jiān)O(shè)計(jì)一個(gè)時(shí)間上盡可能高效的算法，找出由str1和str2所指向兩個(gè)鏈表共同后綴的起始位置（如圖中字符i所在的結(jié)點(diǎn)位置p）。要求：給出算法的基本設(shè)計(jì)思想。根據(jù)設(shè)計(jì)思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。假定某計(jì)算機(jī)的CPU主頻為80MHz，CPI為4，平均每條指令訪存1.5次，主存與Cache之間交換的塊大小為16B，Cache的命中率為99%。存儲(chǔ)器總線寬度為32位。請回答下列問題。該計(jì)算機(jī)的MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA傳送的情況下，主存帶寬至少到多少才能滿足CPU的訪存要求？假定在Cache丟失的情況下訪問主存時(shí)，存儲(chǔ)0.0005%的缺頁率，則CPU平均每秒產(chǎn)生多少次缺頁異常？若頁面大小為4KB，每次缺頁都需要訪問磁盤，訪問磁盤時(shí)DMA傳送采用周期挪用方式，磁盤I/O接口的數(shù)據(jù)緩沖寄存器為32位，則磁盤I/O接口平均每秒發(fā)出的DMA請求次數(shù)至少是多少？CPU和DMA控制器同時(shí)要求使用存儲(chǔ)器總線時(shí)，哪個(gè)優(yōu)先級更高？為什么？為了提高性能，主存采用4體低位交叉存儲(chǔ)模式，工作時(shí)每1/4個(gè)存儲(chǔ)周期啟動(dòng)一個(gè)體。若每個(gè)體的存儲(chǔ)周期為50ns，則該主存能提供的最大帶寬是多少？某16位計(jì)算機(jī)中，帶符號整數(shù)用補(bǔ)碼表示，數(shù)據(jù)Cache和指令Cache分離。題44表給出了指令系統(tǒng)中部分指令格式，其中Rs和Rd表示寄存器，mem表示存儲(chǔ)單地址，(x)表示寄存器x或存儲(chǔ)單元x的內(nèi)容。該計(jì)算機(jī)采用5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器（D）、執(zhí)行/計(jì)算有效地址（EX）、訪問存儲(chǔ)器（M）和結(jié)果寫回寄存器（WB），流水線采用“按序發(fā)射，按序完成”方式，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一個(gè)寄存器的讀和寫不能在同一個(gè)時(shí)鐘周期內(nèi)進(jìn)行。請回答下列問題：若int型變量x的值為-513，存放在寄存器R1中，則執(zhí)行指令“SHLR1”后，R1的內(nèi)容是多少？（用十六進(jìn)制表示）。若某個(gè)時(shí)間段中，有連續(xù)的4條指令進(jìn)入流水線，在其執(zhí)行過程中沒有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時(shí)鐘周期數(shù)為多少？若高級語言程序中某賦值語句為x=a+b,x,b和b均為int型變量，它們的存儲(chǔ)單元地址分別表示為[x],[a]和[b]。該語句對應(yīng)的指令序列及其在指令流水線中的執(zhí)行過程如下圖所示。則這4條指令執(zhí)行過程中，I3的ID段和I4的IF段被阻塞的原因各是什么？若高級語言程序中某賦值語句為x=x*2+a,x和a均為unsignedint類型變量，它們的存儲(chǔ)單元地址分別表示為[x],[a]，則執(zhí)行這條語句至少需要多少個(gè)時(shí)鐘周期？要求模仿題44圖畫出這條語句對應(yīng)的指令序列及其在流水線中的執(zhí)行過程示意圖。某請求分頁系統(tǒng)的局部頁面轉(zhuǎn)換策略如下：系統(tǒng)從0時(shí)刻開始掃描，每隔5個(gè)時(shí)間單位掃描下一輪駐留集（掃描時(shí)間忽略不計(jì)），本輪沒有被訪問過的頁框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次分配之前不被清空。當(dāng)發(fā)生缺頁時(shí)，如果該頁曾被使用過且不在空閑頁鏈表中，則重新放回進(jìn)程的駐留集中；否則，從空閑頁框鏈表善取出一個(gè)頁框。假設(shè)不考慮其他進(jìn)程的影響和系統(tǒng)開銷。初始時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁框鏈表中頁框號依次為32、15、21、41。進(jìn)程P依次訪問的<虛擬頁號，訪問時(shí)刻>是：<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>。請回答下列問題。訪問<0,4>時(shí)，對應(yīng)的頁框號是什么？說明理由。