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

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

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

3、識點】樹的中序遍歷和AVL樹的基本概念。 5設(shè)有向圖G=(V,E)，頂點集V=V,V,V,V，邊集E=,，,301201123300若從頂點V開始對圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是 0 A2 B3 C4 D5 【參考答案】D 【考查知識點】圖的深度優(yōu)先遍歷。 6求下面帶權(quán)圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V開始）第2次選中的邊是 4A(V1,V3) B(V1,V4) C(V2,V3) D(V3,V4) 【參考答案】A 【考查知識點】最小生成樹算法的Prim算法和Kruskal算法。 7下列選項中，不能構(gòu)成折

4、半查找中關(guān)鍵字比較序列的是 A500，200，450，180 B500，450，200，180 C180，500，200，450 D180，200，500，450 【參考答案】A 【考查知識點】二分查找算法。 8已知字符串S為“abaabaabacacaabaabcc”. 模式串t為“abaabc”, 采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”(si != ti) 時，i=j=5,則下次開始匹配時，i和j的值分別是 Ai=1，j=0 j=2 ，i=6D j=2 ，i=5C j=0 ，i=5B C 【參考答案】 】模式匹配（【考查知識點KMP）算法。 9下列排序算法中元素的移動次數(shù)和關(guān)鍵字的初始

5、排列次序無關(guān)的是 快速排序D 基數(shù)排序C 起泡排序B 直接插入排序A【參考答案】B 【考查知識點】幾種排序算法的比較。 10已知小根堆為8，15，10，21，34，16，12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的比較數(shù)是 A1 B2 C3 D4 【參考答案】B 【考查知識點】最小堆的概念和最小堆的重建。 11希爾排序的組內(nèi)排序采用的是（） A直接插入排序 B折半插入排序 C快速排序 D歸并排序 A 【參考答案】 （由【考查知識點】希爾排序基本思想是：先將整個待排元素序列分割成若干個子序列然后依次縮減增量再進(jìn)行排序，待分別進(jìn)行直接插入排序，相隔某個“增量”的元素組成的） 整個序列中

6、的元素基本有序（增量足夠小）時，再對全體元素進(jìn)行一次直接插入排序。 計算機(jī)硬件能夠直接執(zhí)行的是（）12 匯編語言程序 硬件描述語言程序機(jī)器語言程序C僅 D A僅 B僅 【參考答案】A 【考查知識點】用匯編語言等非機(jī)器語言書寫好的符號程序稱源程序,運(yùn)行時匯編程序要 將源程序翻譯成目標(biāo)程序，目標(biāo)程序是機(jī)器語言程序。 13由3個“1”和5個“0”組成的8位二進(jìn)制補(bǔ)碼，能表示的最小整數(shù)是（） A-126 -3 D -32 C -125 B B 【參考答案】 【考查知識點】二進(jìn)制的補(bǔ)碼表示。 14下列有關(guān)浮點數(shù)加減運(yùn)算的敘述中，正確的是（） . 對階操作不會引起階碼上溢或下溢 右規(guī)和尾數(shù)舍入都可能引起階

7、碼上溢. 左規(guī)時可能引起階碼下溢. . 尾數(shù)溢出時結(jié)果不一定溢出 A僅 D 僅C 僅B B 【參考答案】【考查知識點】浮點數(shù)的加減運(yùn)算。 15假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每字32位，采用回寫（Write Back）方式，則能存放4K字?jǐn)?shù)據(jù)的Cache的總?cè)萘康奈粩?shù)至少是（） A146k B147K C148K D158K B 【參考答案】主存儲器中 【考查知識點】Cache 和主存的映射方式。直接映射方式地址映象規(guī)則：(2) 的一個特定的塊中。Cache(1) 主存與緩存分成相同大小的數(shù)據(jù)塊。一塊只能映象到主存容量應(yīng)是緩存容量的整

8、數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的數(shù)與緩存的總塊數(shù)相等。(3) 位置。對應(yīng)的x xaddt16假定編譯器將賦值語句“x=x+3;”轉(zhuǎn)換為指令”add xaddt, 3”，其中是，TLB存儲單元地址，若執(zhí)行該指令的計算機(jī)采用頁式虛擬存儲管理方式，并配有相應(yīng)的 Cache且使用直寫（Write Through）方式，則完成該指令功能需要訪問主存的次數(shù)至少是（）3 D 1 C2 A0 B【參考答案】 C 【考查知識點】 考察了頁式虛擬存儲器及TLB快表。 17下列存儲器中，在工作期間需要周期性刷新的是（） ASRAM FLASH D

9、 ROM C SDRAM B B 【參考答案】）一次，如果refresh】DRAM使用電容存儲，所以必須隔一段時間刷新（【考查知識點 存儲單元沒有被刷新，存儲的信息就會丟失。假定在存儲器總線上出現(xiàn)的主存地址（十進(jìn)制）序4體交叉存儲器，18某計算機(jī)使用，則可能發(fā)生發(fā)生緩存沖8006列為8005，8007，80048003，800080028008，8001， 突的地址對是（）8004 、8000D8008 、 8008 8004A、 8001C 8007 、8002BC 【參考答案】 考察了存儲器中的多模塊存儲器，多體并行系統(tǒng)?！俊究疾橹R點 下列有關(guān)總線定時的敘述中，錯誤的是（）19 異步通信

10、方式中，全互鎖協(xié)議最慢AB異步通信方式中，非互鎖協(xié)議的可靠性最差 C同步通信方式中，同步時鐘信號可由多設(shè)備提供 D半同步通信方式中，握手信號的采樣由同步時鐘控制 【參考答案】 B 【考查知識點】考察了總線操作和定時，主要是同步定時與異步定時的定義及其特點。 20若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時間為8ms,每個磁道包含1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是( ) A8.1ms 20.5ms D 16.3ms C 12.2ms BB 【參考答案】 【考查知識點】磁盤訪問時間計算。端口之I/OCPU21在采用中斷I/O方式控制打印輸出的情況下，和打印控制接口中的( ) 間交換的信息

11、不可能是 A打印字符 B主存地址 C設(shè)備狀態(tài)D控制命令 A 【參考答案】 】程序中斷【考查知識點I/O方式。三類。下列有關(guān)內(nèi)部(abort)(trap)內(nèi)中斷可分為故障(fault)、陷阱和終止22內(nèi)部異常( ) 異常的敘述中，錯誤的 A內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān) B內(nèi)部異常的檢測由CPU內(nèi)部邏輯實現(xiàn) 內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中C D內(nèi)部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行A 【參考答案】 】內(nèi)部異常概念?！究疾橹R點( ) 23處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是 通用寄存器的內(nèi)容B (PC)A程序計數(shù)器的內(nèi)容 中的內(nèi)容Cache (TLB)C塊表的內(nèi)容 DA 【參考答案】

12、 【考查知識點】外部中斷處理過程。系則執(zhí)行時不可能導(dǎo)致24假定下列指令已裝入指令寄存器。(從用戶態(tài)變?yōu)閮?nèi)核態(tài)CPU( ) 的是)統(tǒng)態(tài)ADIV R0，R1;(R0)/(R1)R0 BINT n；產(chǎn)生軟中斷 CNOT R0；寄存器R0的內(nèi)容取非 DMOV 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)存失敗 D 被高優(yōu)先級進(jìn)程搶占C啟動I/O設(shè)備 D 【參考答案】 【考查知識點】進(jìn)程間各狀態(tài)的轉(zhuǎn)化。 采用死鎖檢測方法，下列敘述中正確的是（）若系統(tǒng)

13、26S1 采用死鎖避免方法，S2 會限制用戶申請資源的順序S1 不需要S1需要進(jìn)行所需資源總量信息，而S2 S1不會給可能導(dǎo)致死鎖的進(jìn)程分配資源，S2會 C僅 D A僅 B 僅 C 【參考答案】 】死鎖相關(guān)概念。【考查知識點，該進(jìn)程已訪問的頁號序列為2,0,2,9,3,4,2,8,2,3,8,4,5系統(tǒng)為某進(jìn)程分配了274個頁框， 若進(jìn)程要訪問的下一頁的頁號為7LRU算法，應(yīng)淘汰頁的頁號是（），依據(jù) 2 A B3 C4 8 D 【參考答案】C 【考查知識點】LRU算法。 28在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是（） A減少磁盤I/O次數(shù) B減少平均尋道時間 C提高磁盤數(shù)據(jù)可靠性 D實現(xiàn)設(shè)備無

14、關(guān)性 【參考答案】A 】磁盤和內(nèi)存速度的差異?！究疾橹R點29在文件的索引節(jié)點中存放直接索引指針10個，一級二級索引指針各1個，磁盤塊大小為1KB。每個索引指針占4個字節(jié)。若某個文件的索引節(jié)點已在內(nèi)存中，到把該文件的偏移量（按字節(jié)編址）為1234和307400處所在的磁盤塊讀入內(nèi)存。需訪問的磁盤塊個數(shù)分別是（） A1，2 B1，3 C2，3 D2，4 【參考答案】D 【考查知識點】文件索引相關(guān)概念。 30在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是（） A可變分配，全局置換 B可變分配，局部置換 D 固定分配，局部置換 固定分配，全局置換CD 【參考答案】 】頁面分配策略和頁面

15、置換策略的概念和相應(yīng)的方法?！究疾橹R點 二、綜合應(yīng)用題：4147小題，共70分?，F(xiàn)要求設(shè)計。|data|data) = 1) / 則刪除當(dāng)前節(jié)點 /r-next = p-next; delete p; p = r-next; else /否則，將數(shù)組中對應(yīng)的元素置1，并將指針指向下一個元素 aabs(p-data) = 1; r = p; p = p-next; return head; (4) 只遍歷一次鏈表，所以時間復(fù)雜度為O(n)， 為節(jié)點絕對值的最大值）。n的數(shù)組，所以空間復(fù)雜度為因為申請大小為nO(n)，（ 鏈表的操作?！究疾橹R點】 已知有42. 5個頂點的圖G如下圖所示 請回答

16、下列問題 (1) 寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始) 22中位于0行3列元素值的含義是什么？求(2) AA，矩陣 m(2=m=2)(3) 若已知具有么？ 【參考答案】 鄰接矩陣為(1) （2） 0行3列的元素的含義是頂點0到頂點3的最短距離為2. m中非零元素的含義是：假設(shè)此頂點位于i行j列，如果Bi=j，則表示i頂點到（3） 。ji到達(dá)不了頂點自己的距離為0；如果ij，則表示頂點【考查知識點】鄰接矩陣的概念，最短路徑。 43. （13分）某16位計算機(jī)主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式；CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0R3為通用寄存器；T為暫存

17、器；SR為移位寄存器，可實現(xiàn)直送(mov)、左移一位(left)、右移一位(right)3種操作，控制信號為Srop,SR的輸出信號Srout控制；ALU可實現(xiàn)直送A(mova)、A加B(add)、A減B(sub)、A 。ALUop種操作，控制信號為1(inc)7加A、A(not)、非B(or)或A、B(and)與 請回答下列問題。 (1) 圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T？ (2) 控制信號ALUop和SRop的位數(shù)至少各是多少？ (3) 控制信號Srout所控制郵件的名稱或作用是什么？ (4) 端點中，哪些端點須連接到控制部件的輸出端？ (5) 為完善單總線數(shù)據(jù)通路，需要在

18、端點中相應(yīng)的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。 (6) 為什么二路選擇器MUX的一個輸入端是2？ 【參考答案】 (1) 圖中程序員可見的寄存器有通用寄存器R0R3和程序計數(shù)器PC；設(shè)置暫存器T用于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。 (2) ALUop和SRop的位數(shù)分別為3,2。 (3) Srout所控制的部件作用是控制計算機(jī)運(yùn)算結(jié)果的輸出。 (4) 須連接到控制部件的輸出端端點有。 (5) ，。 (6) 使PC自增2以獲取下一條指令地址。 】寄存器相關(guān)概念及寄存器的操作，單總線結(jié)構(gòu)【考查知識點44. （10分）題43中描述的計算機(jī)，其部分指令執(zhí)行過程的控制信號如如

19、題44圖a所示。 題44圖a 部分指令控制信號 該機(jī)指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0R3的編號分別為0、1、2和3。 題44圖b 指令格式 請回答下列問題。 (1) 該機(jī)的指令系統(tǒng)最多可定義多少條指令？ (2) 假定inc、shl和sub指令的操作碼分別為01H、02H和03H，則以下指令對應(yīng)的機(jī) 器代碼各是什么？ inc R1 ; R1 + 1R1 (R1) 1R2 ; shl R2,R1 sub R3, (R1),R2 ; (R1) (R2) R3 (3) 假定寄存器X的輸入和輸出控制信號分別為Xin和Xout，其值為

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