2015年考研計算機專業(yè)(基礎(chǔ)綜合)真題試卷

1、2015年考研計算機專業(yè)(基礎(chǔ)綜合)真題試卷(總分：130.00，做題時間：90分鐘)一、單項選擇題(總題數(shù)：41，分?jǐn)?shù)：82.00)單項選擇題1-40小題。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。TOC o 1-5 h z已知程序如下:intS(intn)return(n=0)?0：S(nT)+n,voidmain()coutS(l)；程序運行時使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息依次對應(yīng)的是。main()S(l)S(0)-JS(0)S(1)main()main()S(0)S(1)S(1)S(0)main()先序序列為a,b,c,d的不同二叉樹的個數(shù)是。131

2、4J1516下列選項給出的是從根分別到達兩個葉結(jié)點路徑上的權(quán)值序列,能屬于同一棵哈夫曼樹的是。24,10,5和2,4,10,724,10,5和24,12,724,10,10和24,14,1124,10,5和24,14,6J5現(xiàn)有一棵無重復(fù)關(guān)鍵字的平衡二叉樹(AVL樹)，對其進行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中,正確的是。根結(jié)點的度一定為2樹中最小元素一定是葉結(jié)點最后插入的元素一定是葉結(jié)點樹中最大元素一定是無左子樹J6設(shè)有向圖G=(V,E),頂點集V=V,V,V,V，邊集E=,。若從頂點V開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個03130數(shù)是。234D.5J7

3、.求下面帶權(quán)圖的最小(代價)生成樹時，可能是克魯斯卡(Kruskal)算法第2D.5J7.求下面帶權(quán)圖的最小(代價)生成樹時，可能是克魯斯卡(Kruskal)算法第2次選中但不是普里姆(Prim)13B.41(V(V(V，V，V，VC.D.8.下列選項中)J)不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A.500，200，450，180JB.500，450，200，180C.180，500，200，450D.180，200，500，450已知字符串S為abaabaabacacaabaabcc，模式串t為abaabc。采用KMP算法進行匹配，第一次出現(xiàn)失配”(siMtj)時，i=j=5，則下次開始匹配時

4、，i和j的值分別是。i=1，j=0i=5，j=0i=5,j=2丿i=6，j=2下列排序算法中，元素的移動次數(shù)與關(guān)鍵字的初始排列次序無關(guān)的是。直接插入排序起泡排序基數(shù)排序丿快速排序已知小根堆為8，15，10，21，34，16，12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的TOC o 1-5 h z比較次數(shù)是。-123丿4希爾排序的組內(nèi)排序采用的是。直接插入排序丿折半插入排序快速排序歸并排序計算機硬件能夠直接執(zhí)行的是。1機器語言程序II.匯編語言程序III硬件描述語言程序僅I丿僅1、11僅I、IIII、II、IIITOC o 1-5 h z由3個“1”和5個“0”組成的8位二進制補碼，能

5、表示的最小整數(shù)是。-126-125丿-32-315下列有關(guān)浮點數(shù)加減運算的敘述中，正確的是。1對階操作不會引起階碼上溢或下溢II右規(guī)和尾數(shù)舍入都可能引起階碼上溢III左規(guī)時可能引起階碼下溢IV.尾數(shù)溢出時結(jié)果不一定溢出僅II、III僅I、II、IV僅I、III、IVI、II、III、IV丿假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每TOC o 1-5 h z字32位，采用回寫(WriteBack)方式，則能存放4K字?jǐn)?shù)據(jù)的Cache的總?cè)萘康奈粩?shù)至少是。146k147K148K丿158K假定編譯器將賦值語句x=x+3；轉(zhuǎn)換為指令addxaddr

6、，3，其中xaddr是x對應(yīng)的存儲單元地址。若執(zhí)行該指令的計算機采用頁式虛擬存儲管理方式，并配有相應(yīng)的TLB,且Cache使用直寫(WriteThrough)方式，則完成該指令功能需要訪問主存的次數(shù)至少是。01丿23TOC o 1-5 h z下列存儲器中，在工作期間需要周期性刷新的是。SRAMSDRAM丿ROMFLASH某計算機使用4體交叉編址存儲器，假定在存儲器總線上出現(xiàn)的主存地址(十進制)序列為8005，8006，8007，8008，8001，8002，8003，8004，8000，則可能發(fā)生訪存沖突的地址對是。8004和80088002和80078001和80088000和8004丿下列

7、有關(guān)總線定時的敘述中，錯誤的是。異步通信方式中，全互鎖協(xié)議最慢異步通信方式中，非互鎖協(xié)議的可靠性最差同步通信方式中，同步時鐘信號可由各設(shè)備提供丿半同步通信方式中，握手信號的采樣由同步時鐘控制21若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時間為8ms,每個磁道包含1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是。81ms12.2msV163ms205ms在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口之間交換的信息不可能是。打印字符主存地址V設(shè)備狀態(tài)控制命令內(nèi)部異常(內(nèi)中斷)可分為故障(fault)、陷阱(trap)和終止(abort)三類。下列有關(guān)內(nèi)部異常的敘述中，錯誤

8、的是。內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)內(nèi)部異常的檢測由CPU內(nèi)部邏輯實現(xiàn)內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中內(nèi)部異常處理后返回到發(fā)生異常的指令繼續(xù)執(zhí)行V處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是。程序計數(shù)器(PC)的內(nèi)容通用寄存器的內(nèi)容V塊表(TLB)中的內(nèi)容Cache中的內(nèi)容25假定下列指令已裝入指令寄存器。則執(zhí)行時不可能導(dǎo)致CPU從用戶態(tài)變?yōu)閮?nèi)核態(tài)(系統(tǒng)態(tài))的是。DIVR0，R1；(R0)/(RI)R0INTn產(chǎn)生軟中斷NOTR0寄存器R0的內(nèi)容取非VMOVR0，addr；把地址addr處的內(nèi)存數(shù)據(jù)放入寄存器R0中下列選項中，會導(dǎo)致進程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是執(zhí)行P(wait)操作申請內(nèi)存失敗

9、啟動I/O設(shè)備被高優(yōu)先級進程搶占V若系統(tǒng)S1采用死鎖避免方法，S2采用死鎖檢測方法。下列敘述中，正確的是。1.S1會限制用戶申請資源的順序，而S2不會II.S1需要進程運行所需資源總量信息，而S2不需要III.S1不會給可能導(dǎo)致死鎖的進程分配資源，而S2會僅1、11僅II、IIIV僅I、IIII、II、III系統(tǒng)為某進程分配了4個頁框，該進程己訪問的頁號序列為2，0，2，9，3，4，2，8，2，4，8，4，5。TOC o 1-5 h z若進程要訪問的下一頁的頁號為7,依據(jù)LRU算法，應(yīng)淘汰頁的頁號是。2V348在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是。減少磁盤I/O次數(shù)V減少平均尋道時間提高磁盤

10、數(shù)據(jù)可靠性實現(xiàn)設(shè)備無關(guān)性在文件的索引結(jié)點中存放直接索引指針10個，一級和二級索引指針各1個。磁盤塊大小為1KB，每個TOC o 1-5 h z索引指針占4個字節(jié)。若某文件的索引結(jié)點已在內(nèi)存中，則把該文件偏移量（按字節(jié)編址）為1234和307400處所在的磁盤塊讀入內(nèi)存，需訪問的磁盤塊個數(shù)分別是。1，21，3V2，32，4在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是?？勺兎峙洌种脫Q可變分配，局部置換固定分配，全局置換V固定分配，局部置換TOC o 1-5 h z32文件系統(tǒng)用位圖法表示磁盤空間的分配情況，位圖存于磁盤的32127號塊中，每個盤塊占1024個字節(jié)，盤塊和塊內(nèi)字節(jié)

11、均從0開始編號。假設(shè)要釋放的盤塊號為409612，則位圖中要修改的位所在的盤塊號和塊內(nèi)字節(jié)序號分別是。81、181、282、1V82、2某硬盤有200個磁道（最外側(cè)磁道號為0），磁道訪問請求序列為：130，42，180，15，199，當(dāng)前磁頭位于第58號磁道并從外側(cè)向內(nèi)側(cè)移動。按照SCAN調(diào)度方法處理完上述請求后，磁頭移過的磁道數(shù)是208287325V382通過POP3協(xié)議接收郵件時，使用的傳輸層服務(wù)類型是。無連接不可靠的數(shù)據(jù)傳輸服務(wù)無連接可靠的數(shù)據(jù)傳輸服務(wù)有連接不可靠的數(shù)據(jù)傳輸服務(wù)D.有鏈接可靠的數(shù)據(jù)傳輸服務(wù)D.有鏈接可靠的數(shù)據(jù)傳輸服務(wù)丿NRZ和差分曼徹斯特編碼NRZI和曼徹斯特編碼NRZI

12、和差分曼徹斯特編碼36主機甲通過128kbps星鏈路，采用滑動窗口協(xié)議向主機乙發(fā)送數(shù)據(jù)，鏈路單向傳播延遲為250ms，幀長TOC o 1-5 h z為1000字節(jié)。不考慮確認(rèn)幀的開銷，為使鏈路利用率不小于80，幀序號的比特數(shù)至少是。34丿78下列關(guān)CSMA/CD協(xié)議的敘述中，錯誤的是邊發(fā)送數(shù)據(jù)幀，邊檢測是否發(fā)生沖突適用于無線網(wǎng)絡(luò)，以實現(xiàn)無線鏈路共享丿需要根據(jù)網(wǎng)絡(luò)跨距和數(shù)據(jù)傳輸速率限定最小幀長當(dāng)信號傳播延遲趨近0時，信道利用率趨近100下列關(guān)于交換機的敘述中，正確的是。以太網(wǎng)交換機本質(zhì)上是一種多端口網(wǎng)橋丿通過交換機互連的一組工作站構(gòu)成一個沖突域交換機每個端口所連網(wǎng)絡(luò)構(gòu)成一個獨立的廣播域D.以太網(wǎng)

13、交換機可實現(xiàn)采用不同網(wǎng)絡(luò)層協(xié)議的網(wǎng)絡(luò)互聯(lián)39.某路由器的路由表如下表所示：路由器收到一個目的地址為D.以太網(wǎng)交換機可實現(xiàn)采用不同網(wǎng)絡(luò)層協(xié)議的網(wǎng)絡(luò)互聯(lián)39.某路由器的路由表如下表所示：路由器收到一個目的地址為169，96.40.5的IP分組，則轉(zhuǎn)發(fā)該口分組的接口是S1TOC o 1-5 h zS2S3丿S440.主機甲和主機乙新建一個TCP連接，甲的擁塞控制初始閾值為32KB，甲向乙始終以MSS=1KB大小的段發(fā)送數(shù)據(jù)，并一直有數(shù)據(jù)發(fā)送；乙為該連接分配16KB接收緩存，并對每個數(shù)據(jù)段進行確認(rèn)，忽略段傳輸延遲。若乙到的數(shù)據(jù)全部存入緩存，不被取走，則甲從連接建立成功時刻起，未發(fā)送超時的情況下，經(jīng)過4

14、個RTT后，甲的發(fā)送窗口是。1KB丿8KB16KBIndex.html存放在上該瀏覽器請求使用持續(xù)連接丿該瀏覽器曾經(jīng)瀏覽過、綜合應(yīng)用題（總題數(shù)：8，分?jǐn)?shù)：48.00）42.綜合應(yīng)用題41-47小題。用單鏈表保存m個整數(shù)，結(jié)點的結(jié)構(gòu)為：dlatalink，且丨data|Wn(n為正整數(shù))?，F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效的算法，對于鏈表中data的絕對值相等的結(jié)點，僅保留第一次出現(xiàn)的結(jié)點而刪除其余絕對值相等的結(jié)點。例如，若給定的單鏈表head如下數(shù)：8.00)用單鏈表保存m個整數(shù)，結(jié)點的結(jié)構(gòu)為：dlatalink，且丨data|Wn(n為正整數(shù))?，F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效的算法，對于

15、鏈表中data的絕對值相等的結(jié)點，僅保留第一次出現(xiàn)的結(jié)點而刪除其余絕對值相等的結(jié)點。例如，若給定的單鏈表head如下數(shù)：8.00)(1).給出算法的基本設(shè)計思想。head為：要求：(分正確答案：(正確答案：算法的基本設(shè)計思想算法的核心思想是用空間換時間。使用輔助數(shù)組記錄鏈表中已出現(xiàn)的數(shù)值，從而只需對鏈表進行一趟掃描。因為丨data|Wn,故輔助數(shù)組q的大小為n+1,各元素的初值均為0。依次掃描鏈表中的各結(jié)點，同時檢查qIdata門的值，如果為0,則保留該結(jié)點，并令q丨dataI=1；否則，將該結(jié)點從鏈表中刪除。)(2).使用C或C+語言，給出單鏈表結(jié)點的數(shù)據(jù)類型定義。正確答案：(正確答案：使用

16、C語言描述的單鏈表結(jié)點的數(shù)據(jù)類型定義typedefstructnodeintdatastructnode*link；NODE；TypedefNODE*PNODE。)(3).根據(jù)設(shè)計思想，采用C或C+語言描述算法，關(guān)鍵之處給出注釋。正確答案：(正確答案：算法實現(xiàn)voidfunc(PNODEh，intn)PNODEp=h，r，int*q，m；q=(int*)malloc(sizeof(int)*(n十1)；/申請n+1個位置的輔助空間for(inti=0,ilink-data0?p-link-data：-p-link-data；if(*(q+m)=0)/判斷該結(jié)點的data是否己出現(xiàn)過*(q+m)

17、=1，/首次出現(xiàn)p=p-link；/保留else/重復(fù)出現(xiàn)r=p-link；/刪除P-link=r-finkfree(r)；)(4).說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。正確答案：(正確答案：算法的時間復(fù)雜度為0(m)，空間復(fù)雜度為0(n)。)已知含有5個頂點的圖G如下圖所示。(1).寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始)。：(分?jǐn)?shù)：6.00)正確答案：(正確答案：圖G的鄰接矩陣A如下：(2).求A2，矩陣A2中位于0行3列元素值的含義是什么？(3).若己知具有n(n2)個頂點的圖的鄰接矩陣為B則Bm(2WmWn)中非零元素的含義是什么？正確答案：(正確答案：Bm(2WmWn)中位于

18、i行j列(0Wj，jWn-1)的非零元素的含義是：圖中從頂點i到頂點j長度為m的路徑條數(shù)。)某16位計算機的主存按字節(jié)編碼，存取單位為16位；采用16位定長指令字格式；CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0R3為通用寄存器；T為暫存器；SR為移位寄存器，可實現(xiàn)直送(mov)、左移一位(left)和右移一位(right)3種操作，控制信號為SRop，SR的輸出由信號SRout控制；ALU可實現(xiàn)直請回答下列問題：(分?jǐn)?shù)：12.00)送A(mova)、A加B(add)、A減B(sub)、A與B(and)、A或B(or)、非A(not)、A加1(inc)7種操作，控制信號為ALUop請回答

19、下列問題：(分?jǐn)?shù)：12.00).圖中哪些寄存器是程序員可見的?為何要設(shè)置暫存器T?正確答案：(正確答案：程序員可見寄存器為通用寄存器(R0R3)和PC。因為采用了單總線結(jié)構(gòu)，因此,若無暫存器T,則ALU的A、B端口會同時獲得兩個相同的數(shù)據(jù)，使數(shù)據(jù)通路不能正常工作。).控制信號ALUop和SRop的位數(shù)至少各是多少?正確答案：(正確答案：ALU共有7種操作，故其操作控制信號ALUop至少需要3位；移位寄存器有3種操作，其操作控制信號SRop至少需要2位。).控制信號SRout所控制部件的名稱或作用是什么?正確答案：(正確答案：信號SRout所控制的部件是一個三態(tài)門，用于控制移位器與總線之間數(shù)據(jù)通

20、路的連接與斷開。).端點中，哪些端點須連接到控制部件的輸出端？正確答案：(正確答案：端口、須連接到控制部件輸出端。).為完善單總線數(shù)據(jù)通路，需要在端點中相應(yīng)的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。正確答案：(正確答案：連線1,一；連線2,一。).為什么二路選擇器MID(的一個輸入端是2?正確答案：(正確答案：因為每條指令的長度為16位，按字節(jié)編址，所以每條指令占用2個內(nèi)存單元，順序執(zhí)行時，下條指令地址為(PC)+2。MUX的一個輸入端為2,可便于執(zhí)行(PC)+2操作。)某16位計算機的主存按字節(jié)編碼，存取單位為16位；采用16位定長指令字格式；CPU采用單總線

21、結(jié)構(gòu),主要部分如下圖所示。圖中R0R3為通用寄存器；T為暫存器；SR為移位寄存器，可實現(xiàn)直送(mov)、左移一位(left)和右移一位(right)3種操作，控制信號為SRop,SR的輸出由信號SRout控制；ALU可實現(xiàn)直送A(mova)、A加B(add)、A減B(sub)、A與B(and)、A或B(or)、非A(not)、A加1(inc)7種操作，控制信號為ALUop。式如下圖所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0信號為ALUop。式如下圖所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1,通用寄存器R0以上描述的計算機，其部分指令執(zhí)行過程的控制

22、信號如下圖所示。該機指令格：(分?jǐn)?shù)：8.00)R3的編號分別為0、1、2和：(分?jǐn)?shù)：8.00).該機的指令系統(tǒng)最多可定義多少條指令?正確答案：(正確答案：指令操作碼有7位，因此最多可定義27=128條指令。).假定inc、shl和sub指令的操作碼分別為01H、02H和03H,則以下指令對應(yīng)的機器代碼各是什么？incR1；R1+1R1shlR1,R2；(R1)1R2subR3；(R1),R2；(R1)-(R2)R3正確答案：(正確答案：各條指令的機器代碼分別如下：“incR1”的機器碼為：0000001001000000,即0240H。“sblR2,R1”的機器碼為：0000010010001

23、000,即0488H?！皊ubR3,(R1),R2”的機器碼為：0000011011101010,即06EAH。).假設(shè)寄存器X的輸入和輸出控制信號分別為Xin和Xout，其值為1表示有效，為0表示無效(例如，PCout=1表示PC內(nèi)容送總線)；存儲器控制信號為MEMop,用于控制存儲器的讀(read)和寫(write)操作。寫出題圖a中標(biāo)號處的控制信號或控制信號的取值。正確答案：(正確答案：各標(biāo)號處的控制信號或控制信號取值如下：0;mov；mova；left；read；sub:mov:Srout。).指令“subR1,R3,(R2)”和“incR1”的執(zhí)行階段至少各需要多少個時鐘周期?正確答

24、案：(正確答案：指令“subR1,R3,(R2)”的執(zhí)行階段至少包含4個時鐘周期；指令“incR1”的執(zhí)行階段至少包含2個時鐘周期。)43有A、B兩人通過信箱進行辯論，每個人都從自己的信箱中取得對方的問題。將答案和向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的郵箱中。假設(shè)A的信箱最多放M個郵件，B的信箱最多放N個郵件。初始時A的信箱中有x個郵件(0 xM),B的信箱中有y個(0yN)。辯論者每取出一個郵件，郵件數(shù)減1。A和oEnd當(dāng)信箱不為空時，辯論者才能從信箱中取郵件，否則等B兩人的操作過程描述如下：oEnd當(dāng)信箱不為空時，辯論者才能從信箱中取郵件，否則等待。當(dāng)信箱不滿時，辯論者才能將新郵件放入信

25、箱，否則等待。請?zhí)砑颖匾男盘柫亢蚉、V(或wait,signal)操作，以實現(xiàn)上述過程的同步。要求寫出完整過程，并說明信號量的含義和初值。正確答案：(正確答案：semaphoreFull_A=x；/Full_A表示A的信箱中的郵件數(shù)量semaphoreEmpty_A=M-x；/Empty_A表示A的信箱中還可存放的郵件數(shù)量semaphoreFull_B；y；/Full_B表示B的信箱中的郵件數(shù)量semaphoreEmpty_B；N-y；/Empty_B表示B的信箱中還可存放的郵件數(shù)量semaphoremutex_A=1；-)/mutex_A用于A的信箱互斥semaphoremutex_B=1；/mutex_B用于B的信箱互斥Cobegin-)請回答下某計算機系統(tǒng)按字節(jié)編址，采用二級頁表的分頁存儲管理方式，虛擬地址格式如下所示請回答下列問題：(分?jǐn)?shù)：6.00).頁和頁框的大小各為多少字節(jié)?進程的虛擬地址空間大小為多少頁？正確答案：(正確答案：頁和頁框大小均為4KB。進程的虛擬地址空間大小為232/212=220頁。).假定頁目錄項和頁表項均占4個字節(jié)，則進程的頁目錄和頁表共占多少頁?要求寫出計算過程。正確答案：(正確答案：(210*4)212(頁目錄所占頁數(shù))+(220*4)212(頁表所占頁數(shù)