2015年計算機(jī)考研真題解析..

1、2015年全國碩士研究生入學(xué)統(tǒng)一考試計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題：140小題，每小題2分，共80分。下列每題給出的四個選項中，只 有一個選項符合題目要求。請在答題卡上將所選項的字母涂黑。1. 已知程序如下:int s(i nt n) return (n<=0) ? 0 : s(n-1) +n;void main() cout<< s(1);程序運行時使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息一次對應(yīng)的是A . main()->S(1)->S(0)B. S(0)->S(1)->main()C. main()->S(0)->

2、S(1)D. S(1)->S(0)->main()【參考答案】D【考查知識點】棧的基本概念和函數(shù)調(diào)用的原理。2. 先序序列為a,b,c,d的不同二叉樹的個數(shù)是A. 13B . 14C. 15D . 16【參考答案】C【考查知識點】二叉樹的基本概念。3. 下列選項給出的是從根分別到達(dá)兩個葉節(jié)點路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是A. 24, 10,5 和 24, 10, 7B. 24, 10, 5 和 24, 12, 7C . 24, 10,10 和 24, 14, 11D. 24, 10, 5 和 24, 14, 6【參考答案】【考查知識點】哈夫曼樹的原理。4. 現(xiàn)在有一顆無

3、重復(fù)關(guān)鍵字的平衡二叉樹（AVL樹），對其進(jìn)行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A. 根節(jié)點的度一定為 2B .樹中最小元素一定是葉節(jié)點C.最后插入的兀素一定是葉節(jié)點D .樹中最大兀素一定是無左子樹【參考答案】B【考查知識點】樹的中序遍歷和 AVL樹的基本概念。5.設(shè)有向圖 G=(V,E)，頂點集 V=V 0,Vi,V2,V3，邊集 E=<v 0,V1><V0,V2>,<V0,V3> ,<vi,V3>,若從頂點Vo開始對圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是【參考答案】D【考查知識點】圖的深度優(yōu)先遍歷。k

4、ruskal）算法第二次選6求下面帶權(quán)圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（中但不是普里姆（Prim）算法（從V4開始）第A. (V1,V3)2次選中的邊是B .D. (V3,V4)【參考答案】【考查知識點】最小生成樹算法的Prim算法和Kruskal算法。7.下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A. 500, 200, 450, 180B. 500, 450, 200, 180C. 180, 500, 200, 450D. 180, 200, 500, 450【參考答案】A【考查知識點】二分查找算法。&已知字符串 S為"abaabaabacacaabaabc

5、c模式串 t 為 “ abaabc 采用 KMP 算法進(jìn)行匹配，第一次出現(xiàn)失配”（si != ti）時，i=j=5,則下次開始匹配時,i和j的值分別是A . i=1 , j=0B . i=5 , j=0C . i=5 , j=2i=6 , j=2【參考答案】【考查知識點】模式匹配（KMP ）算法。9. 下列排序算法中元素的移動次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是A.直接插入排序B.起泡排序C.基數(shù)排序快速排序【參考答案】B【考查知識點】幾種排序算法的比較。10. 已知小根堆為8, 15, 10, 21, 34 , 16, 12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的比較數(shù)是C. 3【

6、參考答案】B【考查知識點】最小堆的概念和最小堆的重建。11. 希爾排序的組內(nèi)排序采用的是（）A 直接插入排序B .折半插入排序 C .快速排序D .歸并排序【參考答案】A（由【考查知識點】希爾排序基本思想是：先將整個待排元素序列分割成若干個子序列相隔某個 增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待 整個序列中的元素基本有序（增量足夠?。r，再對全體元素進(jìn)行一次直接插入排序。12. 計算機(jī)硬件能夠直接執(zhí)行的是（）I.機(jī)器語言程序 n.匯編語言程序川硬件描述語言程序A .僅I【參考答案】A【考查知識點】用匯編語言等非機(jī)器語言書寫好的符號程序稱源程序,運行時匯編程序要將

7、源程序翻譯成目標(biāo)程序，目標(biāo)程序是機(jī)器語言程序。13由3個“1和5個“ 0組成的8位二進(jìn)制補(bǔ)碼，能表示的最小整數(shù)是（）A. -126B. -125C. -32D. -3【參考答案】B【考查知識點】 二進(jìn)制的補(bǔ)碼表示。14 .下列有關(guān)浮點數(shù)加減運算的敘述中，正確的是（）I.對階操作不會引起階碼上溢或下溢n.右規(guī)和尾數(shù)舍入都可能引起階碼上溢川.左規(guī)時可能引起階碼下溢w.尾數(shù)溢出時結(jié)果不一定溢出B.僅inwC.僅im w【參考答案】B【考查知識點】浮點數(shù)的加減運算。15 .假定主存地址為 32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每字32位，采用回寫（Write B

8、ack ）方式，則能存放 4K字?jǐn)?shù)據(jù)的Cache的總?cè)萘康奈粩?shù)至少是（）A. 146kB. 147KC. 148KD. 158K【參考答案】【考查知識點】Cache和主存的映射方式。直接映射方式地址映象規(guī)則:主存儲器中一塊只能映象到Cache的一個特定的塊中。（1）主存與緩存分成相同大小的數(shù)據(jù)塊。（2）主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。（3）主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。16 .假定編譯器將賦值語句“x=x+3;轉(zhuǎn)換為指令” add xaddt, 3,其'中xaddt是x對應(yīng)的存儲單元地址，若執(zhí)行

9、該指令的計算機(jī)采用頁式虛擬存儲管理方式，并配有相應(yīng)的TLB ,且Cache使用直寫（Write Through ）方式，則完成該指令功能需要訪問主存的次數(shù)至少是()C. 2【參考答案】 C【考查知識點】考察了頁式虛擬存儲器及 TLB快表。17 .下列存儲器中，在工作期間需要周期性刷新的是（）A . SRAMB . SDRAMC . ROMD . FLASH【參考答案】B【考查知識點】DRAM使用電容存儲，所以必須隔一段時間刷新（ refresh） 一次，如果存儲單元沒有被刷新，存儲的信息就會丟失。18 .某計算機(jī)使用4體交叉存儲器，假定在存儲器總線上出現(xiàn)的主存地址（十進(jìn)制）序 列為 8005,

10、 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000,則可能發(fā)生發(fā)生緩存沖突的地址對是（）A. 8004、 8008B. 8002、 8007 C. 8001、 8008 D. 8000、 8004【參考答案】C【考查知識點】 考察了存儲器中的多模塊存儲器，多體并行系統(tǒng)。19 .下列有關(guān)總線定時的敘述中，錯誤的是（）A .異步通信方式中，全互鎖協(xié)議最慢B .異步通信方式中，非互鎖協(xié)議的可靠性最差C. 同步通信方式中，同步時鐘信號可由多設(shè)備提供D .半同步通信方式中，握手信號的采樣由同步時鐘控制【參考答案】 B【考查知識點】考察了總線操作和定時，主要是同

11、步定時與異步定時的定義及其特點。20.若磁盤轉(zhuǎn)速為 7200轉(zhuǎn)/分，平均尋道時間為 8ms,每個磁道包含1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是（）A. 8.1msB. 12.2msC. 16.3msD. 20.5ms【參考答案】B【考查知識點】磁盤訪問時間計算。21.在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口之間交換的信息不可能是（）A .打印字符B 主存地址C .設(shè)備狀態(tài)D .控制命令【參考答案】【考查知識點】程序中斷I/O方式。22內(nèi)部異常（內(nèi)中斷）可分為故障（fault）、陷阱（trap）和終止（abort）三類。下列有關(guān)內(nèi)部異常的敘述中，錯

12、誤的（）A .內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)B.內(nèi)部異常的檢測由 CPU內(nèi)部邏輯實現(xiàn)C.內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中D .內(nèi)部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行【參考答案】A【考查知識點】內(nèi)部異常概念。23.處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是（）A .程序計數(shù)器（PC）的內(nèi)容B .通用寄存器的內(nèi)容C.塊表（TLB）的內(nèi)容D . Cache中的內(nèi)容【參考答案】A【考查知識點】外部中斷處理過程。24.假定下列指令已裝入指令寄存器。則執(zhí)行時不可能導(dǎo)致 CPU從用戶態(tài)變?yōu)閮?nèi)核態(tài)（系統(tǒng)態(tài)）的是（）A.DIV R0 , R1;(R0)/(R1) T R0INT n ;產(chǎn)生軟中斷C.NOT

13、RO ;寄存器 RO的內(nèi)容取非MOV R0,addr ;把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中【參考答案】C【考查知識點】CPU用戶態(tài)和內(nèi)核態(tài)概念。25.下列選項中會導(dǎo)致進(jìn)程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是（）A .執(zhí)行P（wait）操作B 申請內(nèi)存失敗C.啟動I/O設(shè)備D 被高優(yōu)先級進(jìn)程搶占【參考答案】D【考查知識點】進(jìn)程間各狀態(tài)的轉(zhuǎn)化。26.若系統(tǒng)S1采用死鎖避免方法,S2采用死鎖檢測方法，下列敘述中正確的是（）I. S1會限制用戶申請資源的順序n. S1需要進(jìn)行所需資源總量信息，而S2不需要川.S1不會給可能導(dǎo)致死鎖的進(jìn)程分配資源,S2會A .僅I n【參考答案】C【考查知識點】死鎖相關(guān)概念。2,

14、0,2,9,3,4,2,8,238,4,5 ,27.系統(tǒng)為某進(jìn)程分配了4個頁框，該進(jìn)程已訪問的頁號序列為若進(jìn)程要訪問的下一頁的頁號為7,依據(jù)LRU算法，應(yīng)淘汰頁的頁號是（）C. 4【參考答案】C【考查知識點】LRU算法。28.在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是（）A .減少磁盤I/O次數(shù)B .減少平均尋道時間C.提高磁盤數(shù)據(jù)可靠性D .實現(xiàn)設(shè)備無關(guān)性【參考答案】A【考查知識點】磁盤和內(nèi)存速度的差異。29.在文件的索引節(jié)點中存放直接索引指針10個，一級二級索引指針各 1個，磁盤塊大小為1KB。每個索引指針占 4個字節(jié)。若某個文件的索引節(jié)點已在內(nèi)存中，到把該文件的偏移量（按字節(jié)編址）為1234

15、和307400處所在的磁盤塊讀入內(nèi)存。需訪問的磁盤塊個數(shù)分別是（）A. 1, 2B. 1, 3【參考答案】【考查知識點】文件索引相關(guān)概念。30.在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是（）A .可變分配,全局置換B 可變分配，局部置換C.固定分配,全局置換D 固定分配，局部置換【參考答案】【考查知識點】頁面分配策略和頁面置換策略的概念和相應(yīng)的方法。二、綜合應(yīng)用題： 4147小題，共70分。41.用單鏈表保存 m個整數(shù)，節(jié)點的結(jié)構(gòu)為（data,link）,且|data|<n（n為正整數(shù)）?，F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次

16、出現(xiàn)的節(jié) 點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表 head如下HEAD-15-715 A刪除節(jié)點后的head為HEAD要求* -15給出算法的基本思想 使用C或C+語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義。根據(jù)設(shè)計思想，采用 c或C+語言描述算法，關(guān)鍵之處給出注釋。說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度?！緟⒖即鸢浮?1)算法思想:定義一個大小為 N的數(shù)組，初始化為 0.在遍歷鏈表的同時將數(shù)組中索引值為節(jié)點的值的絕對值的元素置 1.如果此元素已經(jīng)為1，說明此節(jié)點之前已經(jīng)有與此節(jié)點的值的絕對值相等的節(jié)點，需將此節(jié)點刪除。 節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義如下:typ edef struct NodeInt

17、 data;Struct Node * next;Node;int an; /全局?jǐn)?shù)組標(biāo)志節(jié)點的絕對值的值是否出現(xiàn)過void DeleteABSEqualNode(Node * head)memset(a,0,n);/ 初始化為 0 if (head = NULL)return NULL;Node * p = head;Node * r = head;while (p != NULL)if (aabs( p->data) = 1)如果此絕對值已經(jīng)在節(jié)點值的絕對值中出現(xiàn)過/則刪除當(dāng)前節(jié)點r->n ext = p->n ext;delete p;p = r->n ext;e

18、lse否則，將數(shù)組中對應(yīng)的元素置1,并將指針指向下一個元素aabs( p->data) = 1;r = p； p = p->n ext;retur n head;只遍歷一次鏈表，所以時間復(fù)雜度為0(n)，因為申請大小為n的數(shù)組，所以空間復(fù)雜度為O(n)，(n為節(jié)點絕對值的最大值)?！究疾橹R點】 鏈表的操作。42. 已知有5個頂點的圖G如下圖所示請回答下列問題(1)寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始)(2)求A2,矩陣A2中位于0行3列元素值的含義是什么? 若已知具有n(n>=2)個頂點的鄰接矩陣為B，則Bm(2<=m<=n)非零元素的含義是什么？【參考答案

19、】(1)鄰接矩陣為01roA=0行3列的元素的含義是頂點0到頂點3的最短距離為2.(3)Bm中非零元素的含義是：假設(shè)此頂點位于i行j列，如果i=j，則表示i頂點到自己的距離為0;如果i M,則表示頂點i到達(dá)不了頂點j。【考查知識點】鄰接矩陣的概念，最短路徑。43. ( 13分)某16位計算機(jī)主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式;CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0R3為通用寄存器；T為暫存器；SR為移位寄存器，可實現(xiàn)直送(mov)、左移一位(left)、右移一位(right)3種操作，控制信號為Srop,SR的輸出信號 Srout控制；ALU 可實現(xiàn)直送 A(

20、mova)、A力口 B(add)、A減B(sub)、A與B(and)、A或B(or)、非A(not)、A加1(inc)7種操作，控制信號為 ALUop。主存總線主存請回答下列問題。圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器控制信號ALUop和SRop的位數(shù)至少各是多少?控制信號Srout所控制郵件的名稱或作用是什么?端點-中，哪些端點須連接到控制部件的輸出端?為完善單總線數(shù)據(jù)通路，需要在端點-中相應(yīng)的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。(6)為什么二路選擇器 MUX的一個輸入端是 2？【參考答案】(1)圖中程序員可見的寄存器有通用寄存器R0R3和程序計數(shù)

21、器PC;設(shè)置暫存器T用于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。ALUoP和SRoP的位數(shù)分別為 3,2。Srout所控制的部件作用是控制計算機(jī)運算結(jié)果的輸出。須連接到控制部件的輸出端端點有。使PC自增2以獲取下一條指令地址?！究疾橹R點】寄存器相關(guān)概念及寄存器的操作，單總線結(jié)構(gòu)144圖a所示。-r.44. (10分)題43中描述的計算機(jī)，其部分指令執(zhí)行過程的控制信號如如題 shl R2,R1;(R1) << 1 7 R2題44圖a部分指令控制信號該機(jī)指令格式如題 44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1,通用寄存器R0R3的編號分別為0、1、2和3。S為負(fù)卡S

22、憑至性或1OPMd*R<i<Msl-'RsbRs2-OP泡釦亡g； 1 一巨叮損選鼓遷出OP g巨揑陀荻-巨閃撿岸衣:出其土： Md. MsK MQU耳漁萬弍住* Rd> Rsl. Rs2為毎尋鯊潼號 三澤姻芒或1 OP溼撫電鑫】一g的S連鼓丸壬* 二匕壬擰4 "末3泣為兀0冷 壬芷壬指令I(lǐng)耒6 &士 Z；題44圖b指令格式請回答下列問題。(1)該機(jī)的指令系統(tǒng)最多可定乂多少條指令? 假定inc、shl和sub指令的操作碼分別為 01H、02H和03H，則以下指令對應(yīng)的機(jī) inc R1器代碼各是什么?R1 + 1 T R1 sub R3, (R1),R

23、2; (R1) -(R2)R3 假定寄存器X的輸入和輸出控制信號分別為 Xin和Xout，其值為1表示有效，為 0表示無效(例如，PCout=1表示PC內(nèi)容送總線)；存儲器控制信號為 MEMop，用于控制存儲器的讀(read)和寫(write)操作。寫出題44圖a中標(biāo)號處的控制信號或控制信號的 取值。 指令“sub R1,R3,(R2)和“inc R1的執(zhí)行階段至少各需要多少個時鐘周期?【參考答案】1280280H，04A8H， 06EEH0, mov， mova, left， read, sub， mov， Srout。至少各需要8和7個時鐘周期?！究疾橹R點】指令的格式與尋址方式，指令執(zhí)行過程45. 有A、B兩人通過信箱進(jìn)行辯論，每人都從自己的信箱中取得對方的問題。將答案A的信箱最多放M個郵件，B和向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的郵箱中，設(shè) 的信箱最多放 N個郵件。初始時A的信箱中有x個郵件(0<x<M). B中有y個(0<y<N )。辯論者每取出一個郵件，郵件數(shù)減