2015年計算機考研真題解析..

1、2015 年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)基礎綜合試題一、單項選擇題：140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中，只 有一個選項符合題目要求。請在答題卡上將所選項的字母涂黑。1.已知程序如下：int s(i nt n)return (n=0) ? 0 : s(n-1) +n;void mai n() coutS(1)-S(0)B. S(0)-S(1)-main()C. main()-S(0)-SD . S(1)-S(0)-main()【參考答案】D【考查知識點】棧的基本概念和函數(shù)調用的原理。2.先序序列為 a,b,c,d 的不同二叉樹的個數(shù)是A . 13B.

2、 14C. 15D . 16【參考答案】C【考查知識點】二叉樹的基本概念。3.下列選項給出的是從根分別到達兩個葉節(jié)點路徑上的權值序列，能屬于同一棵哈夫序序列。下列關于該平衡二叉樹的敘述中，正確的是曼樹的是A . 24, 10, 5 和 24, 10, 7C . 24, 10, 10 和 24, 14, 11【參考答案】C【考查知識點】哈夫曼樹的原理。4.現(xiàn)在有一顆無重復關鍵字的平衡二叉B.24, 10, 5 和 24, 12, 7D. 24, 10, 5 和 24, 14, 6(AVL 樹)，對其進行中序遍歷可得到一個降A .根節(jié)點的度一定為 2B .樹中最小元素一定是葉節(jié)點C.最后插入的元素

3、一定是葉節(jié)點D .樹中最大元素一定是無左子樹【參考答案】B【考查知識點】樹的中序遍歷和 AVL 樹的基本概念。5.設有向圖 G=（V,E），頂點集 V=Vo,Vi,V2,V3，邊集 E=, ,若從頂點 V。開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是【參考答案】D【考查知識點】圖的深度優(yōu)先遍歷。6求下面帶權圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（【參考答案】A【考查知識點】二分查找算法。& 已知字符串 S 為“ abaabaabacacaabaabcc 模式串 t 為“ abaabc 采用 KMP 算法進行【參考答案】9.下列排序算法中元素的移動次數(shù)和關鍵字的初始排列次序

4、無關的是kruskal）算法第二次選中但不是普里姆（Prim）算法（從 V4開始）第2 次選中的邊是A.(V1,V3)B.(V1,V4)C. (V2,V3)D.(V3,V4)【參考答【考查】最小生成樹算法的Prim 算法和 Kruskal 算法。7.下列選項中，不能構成折半查找中關鍵字比較序列的是A.500, 200, 450, 180B.500, 450, 200, 180C.180, 500, 200, 450D. 180, 200, 500, 450匹配，第一次出現(xiàn)失配（si != ti）時，i=j=5,則下次開始匹配時,i 和 j 的值分別是A . i=1 , j=0B . i=5 ,

5、 j=0C . i=5 , j=2i=6 , j=2【考查】模式匹配（KMP ）算法。A.直接插入排序B.起泡排序C.基數(shù)排序快速排序1088118【參考答案】B【考查知識點】幾種排序算法的比較。10.已知小根堆為 8, 15, 10, 21, 34, 16, 12,刪除關鍵字 8 之后需重建堆，在此過 程中，關鍵字之間的比較數(shù)是A . 1B. 2C. 3D. 4【參考答案】B【考查知識點】最小堆的概念和最小堆的重建。11. 希爾排序的組內排序采用的是（）A .直接插入排序B .折半插入排序 C .快速排序D .歸并排序【參考答案】A【考查知識點】希爾排序基本思想是：先將整個待排元素序列分割成

6、若干個子序列（由相隔某個 增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。12.計算機硬件能夠直接執(zhí)行的是（）I.機器語言程序n.匯編語言程序川.硬件描述語言程序A .僅IB .僅I nc.僅I川D.in川【參考答案】A【考查知識點】用匯編語言等非機器語言書寫好的符號程序稱源程序，運行時匯編程序要將源程序翻譯成目標程序，目標程序是機器語言程序。13.由 3 個“1 和 5 個“ 0 組成的 8 位二進制補碼，能表示的最小整數(shù)是（）A . -126B. -125C. -32D. -3【參考答案】B

7、【考查知識點】 二進制的補碼表示。14 .下列有關浮點數(shù)加減運算的敘述中，正確的是（）I.對階操作不會引起階碼上溢或下溢n.右規(guī)和尾數(shù)舍入都可能引起階碼上溢川.左規(guī)時可能引起階碼下溢w.尾數(shù)溢出時結果不一定溢出A.僅n川B.僅Inwc.僅IMwD. In m w【參考答案】B【考查知識點】浮點數(shù)的加減運算。15.假定主存地址為 32 位，按字節(jié)編址，主存和Cache 之間采用直接映射方式，主存塊大小為 4 個字，每字 32 位，采用回寫（Write Back ）方式，則能存放 4K 字數(shù)據(jù)的 Cache 的總容量的位數(shù)至少是（）A . 146kB. 147KC. 148KD. 158K【參考答

8、案】 B【考查知識點】Cache 和主存的映射方式。直接映射方式地址映象規(guī)則：主存儲器中一塊只能映象到 Cache 的一個特定的塊中。（1）主存與緩存分成相同大小的數(shù)據(jù)塊。（2）主存容量應是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊 數(shù)與緩存的總塊數(shù)相等。（3）主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的16.假定編譯器將賦值語句 “x=x+3;轉換為指令” add xaddt, 3,其中 xaddt 是 x 對應的 存儲單元地址，若執(zhí)行該指令的計算機采用頁式虛擬存儲管理方式，并配有相應的TLB ,且 Cache 使用直寫（Write Through ）方式，則完成

9、該指令功能需要訪問主存的次數(shù)至少是（）A . 0B. 1C. 2D. 3【參考答案】 C【考查知識點】考察了頁式虛擬存儲器及 TLB 快表。17 .下列存儲器中，在工作期間需要周期性刷新的是（）A . SRAMB . SDRAMC . ROMD . FLASH【參考答案】B【考查知識點】DRAM 使用電容存儲，所以必須隔一段時間刷新（ refresh） 一次，如果存儲單元沒有被刷新，存儲的信息就會丟失。18 .某計算機使用 4 體交叉存儲器，假定在存儲器總線上出現(xiàn)的主存地址（十進制）序列為 8005, 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000

10、,則可能發(fā)生發(fā)生緩存沖 突的地址對是（）A . 8004、8008B . 8002、8007 C . 8001、8008 D . 8000、8004【參考答案】 C【考查知識點】 考察了存儲器中的多模塊存儲器，多體并行系統(tǒng)。19 .下列有關總線定時的敘述中，錯誤的是（）A .異步通信方式中，全互鎖協(xié)議最慢B 異步通信方式中，非互鎖協(xié)議的可靠性最差C.同步通信方式中，同步時鐘信號可由多設備提供D 半同步通信方式中，握手信號的采樣由同步時鐘控制【參考答案】 B【考查知識點】考察了總線操作和定時，主要是同步定時與異步定時的定義及其特點。20.若磁盤轉速為 7200 轉/分，平均尋道時間為 8ms,每

11、個磁道包含1000 個扇區(qū)，則訪 問一個扇區(qū)的平均存取時間大約是（）A . 8.1msB . 12.2msC. 16.3msD . 20.5ms【參考答案】B【考查知識點】磁盤訪問時間計算。21.在采用中斷 I/O 方式控制打印輸出的情況下，CPU 和打印控制接口中的 I/O 端口之 間交換的信息不可能是（）A 打印字符B 主存地址C 設備狀態(tài)D 控制命令【參考答案】A【考查知識點】程序中斷 I/O 方式。22. 內部異常（內中斷）可分為故障（fault）、陷阱（trap）和終止（abort）三類。下列有關內部 異常的敘述中，錯誤的（）A 內部異常的產生與當前執(zhí)行指令相關B內部異常的檢測由 C

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

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

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

15、，到把該文件的偏移量(按字節(jié)編址)為 1234 和 307400 處所在的磁盤塊讀入內存。需訪問的磁盤塊個數(shù)分別是()A . 1，2B . 1，3C. 2，3D. 2，4【參考答案】D【考查知識點】文件索引相關概念。30.在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是()A .可變分配，全局置換B .可變分配，局部置換C 固定分配，全局置換D 固定分配，局部置換【參考答案】D【考查知識點】頁面分配策略和頁面置換策略的概念和相應的方法。、綜合應用題： 4147 小題，共 70 分。41.用單鏈表保存 m 個整數(shù)，節(jié)點的結構為(data,link),且|data|data) = 1)

16、如果此絕對值已經(jīng)在節(jié)點值的絕對值中出現(xiàn)過則刪除當前節(jié)點r-n ext = p-n ext;delete p;p = r-n ext;否則，將數(shù)組中對應的元素置1 并將指針指向下一個aabs(p-data) = 1;r = p；p = p_n ext;retur n head;(4)只遍歷一次鏈表，所以時間復雜度為O(n),因為申請大小為 n 的數(shù)組，所以空間復雜度為0(n)，(n 為節(jié)點絕對值的最大值)【考查知識點】鏈表的操作。42.已知有 5 個頂點的圖 G 如下圖所示請回答下列問題(1)寫出圖 G 的鄰接矩陣 A(行、列下標從 0 開始)求 A2,矩陣 A2中位于 0 行 3 列元素值的含

17、義是什么？若已知具有 n(n=2)個頂點的鄰接矩陣為B，則 Bm(2=m=n)非零元素的含義是什么？【參考答案】(1)鄰接矩陣為0 1 1 0 o110 0 11else0423100100 110 10 10 3 0 h.-I(2)0 112 210 2 11AJ- 2 1 0 1 22 110 12 12 100 行 3 列的元素的含義是頂點0 到頂點 3 的最短距離為 2.(3) Bm中非零元素的含義是：假設此頂點位于i 行 j 列，如果 i=j，則表示 i 頂點到自己的距離為 0;如果 iz,j則表示頂點 i 到達不了頂點 j?！究疾橹R點】鄰接矩陣的概念，最短路徑。43.(13 分)

18、某 16 位計算機主存按字節(jié)編碼。存取單位為 16 位；采用 16 位定長指令格式；CPU 采用單總線結構，主要部分如下圖所示。圖中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。請回答下列問題。(1)圖中哪些寄存器是程序員可見的？為何要設置暫存器 T

19、 ?(2)控制信號 ALUop 和 SRop 的位數(shù)至少各是多少？(3)控制信號 Srout 所控制郵件的名稱或作用是什么？(4)端點中，哪些端點須連接到控制部件的輸出端？(5)為完善單總線數(shù)據(jù)通路，需要在端點中相應的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。(6)為什么二路選擇器 MUX 的一個輸入端是 2？【參考答案】(1)圖中程序員可見的寄存器有通用寄存器R0R3 和程序計數(shù)器 PC;設置暫存器 T 用于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。(2)ALUop 和 SRop 的位數(shù)分別為 3,2。(3)Srout 所控制的部件作用是控制計算機運算結果的輸出。(4)須連接到控

20、制部件的輸出端端點有。(5)T，7。(6)使 PC 自增 2 以獲取下一條指令地址。CPU沖央強理勒R0一主存總線CPU內思絨| MAR 【考查知識點】寄存器相關概念及寄存器的操作，單總線結構題 44 圖 a 部分指令控制信號該機指令格式如題 44 圖 b 所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為 0 和 1,通用寄存器 R0R3 的編號分別為 0、1、2 和 3。指令換陀礙邑的負乍數(shù)捋薫乍益 1潭燥陀較”O(jiān)P*IERd*MsbRs 2Ms2慕二 Md. MsK為尋淪方弍吐 Rd、Rsl. Rs2 為粛存器澹號 *三地址&令：溥操作歎 1 OP 源操存數(shù) 2 -目

21、的擁悖地松二忑壬巻令末 3 色諂為 5OP遐拯咤鼠 1 ”巨訂摂詐取違址至匕二搖總|未&土均為 0OP巨門超亡戲一巨約竝亡戒陀也題 44 圖 b 指令格式請回答下列問題。(1)該機的指令系統(tǒng)最多可定義多少條指令？(2)假定 inc、shl 和 sub 指令的操作碼分別為01H、02H 和 03H，則以下指令對應的機44.(10 分)題 43 中描述的計算機，其部分指令執(zhí)行過程的控制信號如如題44 圖 a 所示。 shl R2,R1(R1) 1TR2器代碼各是什么？ inc R1; R1 + 1TR1 sub R3, (R1),R2 ; (R1) -(R2)R3(3)假定寄存器 X 的輸

22、入和輸出控制信號分別為Xin 和 Xout，其值為 1 表示有效，為0 表示無效(例如，PCout=1 表示 PC 內容送總線)；存儲器控制信號為 MEMop，用于控制 存儲器的讀(read)和寫(write)操作。寫出題 44 圖 a 中標號處的控制信號或控制信號的 取值。(4)指令“sub R1,R3,(R2)和“inc R1 的執(zhí)行階段至少各需要多少個時鐘周期？【參考答案】(1) 128(2)0280H，04A8H， 06EEH(3) 0， mov， mova， left， read, sub， mov， Srout。(4)至少各需要 8 和 7 個時鐘周期。【考查知識點】指令的格式與尋址方式，指令執(zhí)行過程45.有 A、B 兩人通過信箱進行辯論，每人都從自己的信箱中取得對方的問題。將答案和向對方提出的新問題組成一個郵件放入對方的郵箱中，設A 的信箱最多放 M 個郵件，B的信箱最多放 N 個郵件。初始時 A 的信箱中有 x 個郵件(0 xM). B 中有 y 個(0yN )。 辯論者每取出一個郵件，郵件數(shù)減 1.A、B 兩人操作過程：Code Beg