2015計算機專業(yè)基礎(chǔ)綜合真題與答案解析

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

2、S(0)->main()2 .先序序列為a,b,c,d的不同二叉樹的個數(shù)是A. 13B. 14C. 15D. 163 .下列選項給出的是從根分別到達兩個葉節(jié)點路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是A. 24, 10, 5 和 24, 10, 7C. 24, 10, 10 和 24, 14, 114 .現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二 叉樹序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A. 根節(jié)點的度一定為2B. 24, 10, 5 和 24, 12, 7D. 24, 10, 5 和 24, 14, 6(AVL樹)，對其進行中序遍歷可得到一個降B. 樹中最小元素一定是葉節(jié)點C. 最后插入

3、的元素一定是葉節(jié)點D. 樹中最大元素一定是無左子樹5 .設(shè)有向圖 G=(V,E)，頂點集 V=V0,V1,V2,V3，邊集 E=vv0,v1>,vv0,v2>,vv0,v3>, <v1,v3>,若從頂點V)開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是A. 2B. 3C. 4D. 56 .求下面帶權(quán)圖的最小(代價)生成樹時，可能是克魯斯卡(kruskal )算法第二次選中但不是普里姆(Prim )算法(從7 4開始)第 2次選中的邊是A. (V1,V3)B. (V1,V4)C. (V2,V3)D. (V3,V4)7 .下列選項中，不能構(gòu)成折半查找中關(guān)鍵字

4、比較序列的是A. 500， 200， 450， 180B. 500， 450， 200， 180C. 180, 500, 200, 450D. 180, 200, 500, 4508 .已知字符串 S為“ abaabaabacacaabaabcc模式”串.t為“ abaabc”采用，KMP算法進行匹配，第一次出現(xiàn)“失配” （si!=ti）時,i=j=5,則下次開始匹配時,i和j的值分別是A. i=1 , j=0B. i=5 , j=0C. i=5 , j=2D. i=6 , j=29 .下列排序算法中兀素的移動次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是A.直接插入排序B.起泡排序C.基數(shù)排序D.快速排

5、序10 .已知小根堆為8, 15, 10, 21, 34,16, 12,刪除關(guān)鍵字8之后需重建堆，在此過專業(yè)資料整理程中，關(guān)鍵字之間的比較數(shù)是A. 1B. 2C. 3D. 411.希爾排序的組內(nèi)排序采用的是（）A.直接插入排序B.折半插入排 序12.計算機硬件能夠直接執(zhí)行的是（）I .機器語言程 序A.僅IU.匯編語言程序B.僅IHC.快速排序D.歸并排序川.硬件描述語言程序c.僅I 川 D.in 川13.由3個“1”和5個“0”組成的8位二進制補碼，能表示的最小整數(shù)是（）A. -126B. -125C. -32D. -314.下列有關(guān)浮點數(shù)加減運算的敘述中，正確的是（）I .對階操作不會引起

6、階碼上溢或下溢n.右規(guī)和尾數(shù)舍入都可能引起階碼上溢川.左規(guī)時可能引起階碼下溢IV .尾數(shù)溢出時結(jié)果不一定溢出A.僅n川B.僅 invc.僅I川 VD.in mv15.為假定主存地址32位，按字節(jié)編址，主存 和Cache之間采用直接映射方式，主存塊大小4個字，每32位，采用回寫WriteBack）方式，則能存4K字?jǐn)?shù)據(jù)Cache為字(放的的總?cè)萘康奈粩?shù)至少是（）A. 146kB. 147KC. 148KD. 158K16 .假定編譯器將賦值語“x=x+3;轉(zhuǎn)”換為指令” addxaddt,3，其” xadd是x對應(yīng)的句中t存儲單元地址，若執(zhí)行該指令的計算機采用頁式虛擬存儲管理方式，并配有相應(yīng)的T

7、LB,且Cache使用直寫（WriteThrough ）方式，則完成該指令功能需要訪問主存的次數(shù)至少（）是A. 0B.1C.2D.317 .下列存儲器中，在工作期間需要周期性刷新的是（）A. SRAMB.SDRAMC.ROMD.FLASH18 .某計算機使用4體交叉存儲器，假定在存儲器總線上出現(xiàn)的主存地址（十進制）序列為 8005, 8006, 8007, 8008, 8001 , 8002, 8003, 8004, 8000，則可能發(fā)生發(fā)生緩存沖突的地址對是（）A. 8004、8008B. 8002、8007C. 8001、8008D. 8000、800419.下列有關(guān)總線定時的敘述中，錯誤

8、的是（）A .異步通信方式中，全互鎖協(xié)議最慢B. 異步通信方式中，非互鎖協(xié)議的可靠性最差C. 同步通信方式中，同步時鐘信號可由多設(shè)備提供D. 半同步通信方式中，握手信號的采樣由同步時鐘控制20 .若磁盤轉(zhuǎn)速為 7200轉(zhuǎn)/分，平均尋道時間為8ms,每個磁道包含 1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是（）A. 8.1msB. 12.2msC. 16.3msD. 20.5ms21.在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口之間交換的信息不可能是 （）A.打印字符B.主存地址C.設(shè)備狀態(tài)D.控制命令22 .內(nèi)部異常（內(nèi)中斷）可分為故障（fault）、陷阱

9、（trap）和終止（abort）三類。下列有關(guān)內(nèi)部異常的敘述中，錯誤的（）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í)行23 .處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是（）A.程序計數(shù) （PC）的內(nèi)容 器C.塊表（TLB）的內(nèi)容B.通用寄存器的內(nèi)容24 .假定下列指令已裝入指令寄存則執(zhí)行時不可能導(dǎo)CPU從用戶態(tài)變?yōu)閮?nèi)核（系致態(tài)D. Cache中的內(nèi)容統(tǒng)態(tài)）的是（）A. DIVR0 ,R1;(RO)/(R1)B. INTn ;產(chǎn)生軟中斷R0C. NOTR0寄存器R0的內(nèi)容取非D.

10、MOVRO,addr；把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中25 .下列選項中會導(dǎo)致進程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是（）A.執(zhí)行P（wait）操作B.申請內(nèi)存失敗C.啟動I/O設(shè)備D.被咼優(yōu)先級進程搶占26 .若系統(tǒng)S1采用死鎖避免方法，S2采用死鎖檢測方法，下列敘述中正確的是（）I. S1會限制用戶申請資源的順序需要進行所需資源總量信息，n. S1而S2不需要不會給可能導(dǎo)致死鎖的進程分配資川.S1源，S2會A.僅inB.僅nmc.僅I川27.系統(tǒng)為某進程分配了4個頁框，該進程已訪問的頁號序列為D.inm2,0,2,934,2,8,2,3,8,4,5 ,若進程要訪問的下一頁的頁號為7,依據(jù)LRU算法

11、，應(yīng)淘汰頁的頁號是（）A. 2B. 3C. 4D. 828 .在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是（）A. 減少磁盤 I/O次數(shù)B. 減少平均尋道時間C. 提高磁盤數(shù)據(jù)可靠性D. 實現(xiàn)設(shè)備無關(guān)性29 .在文件的索引節(jié)點中存放直接索引指針10個，一級二級索引指針各1個，磁盤塊大小為1KB。每個索引指針占4個字節(jié)。若某個文件的索引節(jié)點已在內(nèi)存中，到把該文件的偏移量（按字節(jié)編址）為 1234和307400處所在的磁盤塊讀入內(nèi)存。需訪問的磁盤塊個數(shù) 分別是（）A. 1 , 2B. 1, 3C. 2, 3D. 2, 430 .在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是()A.可變分配

12、，全局置換B.可變分配，局部置換C.固定分配，全局置換D.固定分配，局部置換二、綜合應(yīng)用題：4147小題，共 70分。41. 用單鏈表保存 m個整數(shù)，節(jié)點的結(jié)構(gòu)為(data,link)，且|data|vn(n為正整數(shù))?，F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次出現(xiàn)的節(jié) 點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表head如下HEAD* 2115 15刪除節(jié)點后的head為HEAD1繪1.-J亠-i n要求(1) 給出算法的基本思想(2) 使用c或C+語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義。(3) 根據(jù)設(shè)計思想，采用 c或C+語言描述算法，關(guān)鍵之處給出注

13、釋。(4) 說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。42. 已知有5個頂點的圖G如下圖所示(1)寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始) 求A2,矩陣A中位于0行3列元素值的含義是什么?若已知具 n(n>=2)個頂點的鄰接矩陣B，則Bm(2v=m<=n非零元素的含義是什有為么？43. ( 13分)16位計算機主存按字節(jié)編碼。某CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖 中為移位寄存器，可實現(xiàn)直(mov)、左移一送位存取單位16位；采16位定長指令格式；為用R0R3為通用寄存器；T為暫存器；SR(left)、右移一位(right)3種操作，控制信號為Srop,SR的輸出信號 Sr

14、out控制；ALU可實現(xiàn)直送 A(mova)、A加B(add)、A減B(sub)、A與B(_種操作，控制信號為_ALUop電位雪存黑 |SR”1 5 Rod”口=11"3*£DHL1R1lJ|I1iI i f MUX i1 -f-M1 IT T I! 1 !I I llICPU(中央魅理器PCIRdMDR t主存總線請回答下列問題。(1)圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T？ 控制信號ALUop和SRop的位數(shù)至少各是多少？(3) 控制信號Srout所控制郵件的名稱或作用是什么？(4) 端點中，哪些端點須連接到控制部件的輸出端？(5) 為完善單總線數(shù)據(jù)通路，需要

15、在端點中相應(yīng)的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。(6) 為什么二路選擇器MUX的個輸入端是2？(10分)題43中描述的計算機，其部分指令執(zhí)行過程的控制信號如如題44圖a所示mac題44圖a部分指令控制信號該機指令格式如題 44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址 方式位分別為0和1,通用寄存器 R0R3的編號分別為0、1、2和3。OPvRdSULRd. Rs打1勘豔占蘭號電1'J J ' .fP>e PvV 1 耳 F伸h HPjlPflt MHto一便u.!_請回答下列問題。題44圖b指令格式(1) 該機的指令系統(tǒng)

16、最多可定義多少條指令? 假定inc、shl和sub指令的操作碼分別為01H、02H和03H,則以下指令對應(yīng)的機器代碼各是什么? incRIR1+1 R1 shlR2,R1；(R1)v<1 R2subR3,(R1),R2； (R1) - (R2) R3(3Xin和Xout，其值為1表示有效，為)假定寄存器X的輸入和輸出控制信號分別為0表示無效(例如，PCout=1 表示PC內(nèi)容送總線)；存儲器控制信號為 MEMop用于控制 存儲器的讀(read )和寫(write)操作。寫出題44圖a中標(biāo)號處的控制信號或控制信號的 取值。(4) 指令“ subR1,R3,(R2) ”和“ incRI ”的

17、執(zhí)行階段至少各需要多少個時鐘周期？45.有A、B兩人通過信箱進行辯論，每人都從自己的信箱中取得對方的問題。將答案和向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的郵箱中，設(shè)A的信箱最多放 M個郵件，B的信箱最多放N個郵件。初始時 A的信箱中有x個郵件(0<x<M) .B中有y個(OvyvN)。辯論者每取出一個郵件，郵件數(shù)減1.A、B兩人操作過程：CodeBeginAWhile(TRUE)從A的信箱中取出一個郵件；回答問題并提出一個新問題；將新郵件放入B的信箱；BWhile(TRUE)從B的信箱中取出一個郵件; 回答問題并提出一個新問題；將新郵件放入A的信箱；CodeEnd當(dāng)信箱不為空時，辯

18、論者才能從信箱中取郵件，否則等待。當(dāng)信箱不滿時，辯論者才能將新郵件放入信箱，否則等待。請?zhí)砑颖匾男盘柫亢蚉、V (或wait,signed )操作，以實現(xiàn)上述過程的同步，要求寫出完整過程，并說明信號量的含義和初值2015年全國碩士研究生入學(xué)統(tǒng)一考試計算機學(xué)科專業(yè)基礎(chǔ)綜合試題答案解析、單項選擇題：140小題，每小題 2分，共80分。下列每題給出的四個選項中，1 只有一個選項符合題目要求。請在答題卡上將所選項的字母涂黑。1.已知程序如下：ints(intn)return(nv=0)?0:s(n-1)+n;voidmain() cout«s(1);程序運行時使用棧來保存調(diào)用過程的信息，自

19、棧底到棧頂保存的信息一次對應(yīng)的是A. main()->S(1)->S(0)D.main()->S(0)->S(1)【參考答案】DB. S(0)->S(1)->main()D. S(1)->S(0)->main()【考查知識點3 .先序序列為A. 13【參考答案】【考查知識點3.曼樹的是A. 24, 10, 5 和 24, 10, 7C. 24, 10, 10 和 24, 14, 11【參考答案】C【考查知識點】哈夫曼樹的原理。4 .現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉 樹】棧的基本概念和函數(shù)調(diào)用的原理。a,b,c,d 的不同二叉樹的個數(shù)是B. 14C

20、. 15D. 16C】二叉樹的基本概念。F列選項給出的是從根分別到達兩個葉節(jié)點路徑上的權(quán)值序列，能屬于同一棵哈夫序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A.根節(jié)點的度一定為2C. 最后插入的元素一定是葉節(jié)點B. 24, 10, 5 和 24, 12, 7D. 24, 10, 5 和 24, 14, 6AVL樹)，對其進行中序遍歷可得到一個 降B. 樹中最小元素一定是葉節(jié)點D.樹中最大元素一定是無左子樹【參考答案】B【考查知識點】樹的中序遍歷和AVL樹的基本概念。5 .設(shè)有向圖 G=(V,E)，頂點集 V=V0,V1,V2,V3，邊集 E=<v0,v1>,<v0,v2&g

21、t;,vv0,v3>, <v1,v3>,若從頂點V)開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是A. 2B. 3C. 4D. 5【參考答案】 D【考查知識點 】圖的深度優(yōu)先遍歷。6 .求下面帶權(quán)圖的最小(代價)生成樹時，可能是克魯斯卡( 中但不是普里姆(Prim )算法(從V4開始)第 2次選中的邊是A. (V1,V3)B. (V1,V4)C. (V2,V3)(v?)3 58 11-Jit -/yakruskal )算法第二次選D. (V3,V4)【參考答案】 A【考查知識點】最小生成樹算法的Prim算法和Kruskal算法7 .下列選項中，不能構(gòu)成折半查找中關(guān)鍵

22、字比較序列的是A. 500, 200, 450, 180C. 180, 500, 200, 450【參考答案】A【考查知識點】二分查找算法B. 500, 450, 200, 180D. 180, 200, 500, 4508 .已知字符串 S為“ abaabaabacacaabaabcc模式”串.t為“ abaabc”采用，KMP算法進行匹配，第一次出 “失時，則下次開始匹配時，i j的值分別是現(xiàn)配 ”(si!=ti)i=j=5,和A. i=1 , j=0B. i=5 , j=0C. i=5 , j=2D. i=6 , j=2【參考答案】C【考查知識點 】模式匹配 KMP算法。(9 .下列排序

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

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

25、中，正確的是（）I .對階操作不會引起階碼上溢或下溢n.右規(guī)和尾數(shù)舍入都可能引起階碼上溢m .左規(guī)時可能引起階碼下溢IV .尾數(shù)溢出時結(jié)果不一定溢出A.僅n mB.僅 Invc.僅Im v D.In mv【參考答案】b【考查知識點】 浮點數(shù)的加減運算15 .假定主存地址32位，按字節(jié)編址，主存Cache之間采用直接映射方式，主存為和塊大小4個字，每為字32位，采用回寫（WriteBack ）方式， 放則能存4K字?jǐn)?shù)據(jù)Cache的的總谷量的位數(shù)至少是（）A. 146kB.147KC. 148KD. 158K【參考答案】B【考查知識點】Cache和主存的映射方式。直接映射方式地址映象規(guī)則：主存儲器

26、中一塊只能映象 Cache的一個特定的塊中。（1）主存與緩存分成相同大小的數(shù)據(jù)塊。（2）到主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。（3）主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。16 .假定編譯器將賦值語句“ x=x+3;轉(zhuǎn)”換為指令” addxaddt,3，其”中xaddt是x對應(yīng)的存儲單元地址，若執(zhí)行該指令的計算機采用頁式虛擬存儲管理方式，并配有相應(yīng)的TLB ,且Cache使用直寫（WriteThrough ）方式，則完成該指令功能需要訪問主存的次數(shù)至（）少是A. 0B. 1C. 2D. 3【參考答案】C【考查知識點】

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

28、8000、8004【參考答案】 C【考查知識點】考察了存儲器中的多模塊存儲器，多體并行系統(tǒng)。19 .下列有關(guān)總線定時的敘述中，錯誤的是（）A .異步通信方式中，全互鎖協(xié)議最慢B. 異步通信方式中，非互鎖協(xié)議的可靠性最差C. 同步通信方式中，同步時鐘信號可由多設(shè)備提供D. 半同步通信方式中，握手信號的采樣由同步時鐘控制【參考答案】B【考查知識點 】考察了總線操作和定時，主要是同步定時與異步定時的定義及其特點。20 .若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時間為8ms,每個磁道包含 1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是（）A. 8.1msB. 12.2msC. 16.3msD. 20.

29、5ms【參考答案】B【考查知識點 】磁盤訪問時間計算。21.在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的 I/O端口之間交換的信息不可能是 （）A.打印字符B.主存地址C.設(shè)備狀態(tài)D.控制命令【參考答案】A【考查知識點 】程序中斷I/O方式。22 .內(nèi)部異常（內(nèi)中斷）可分為故障（fault）、陷阱（trap）和終止（abort）三類。下列有關(guān)內(nèi)部 異常的敘述中，錯誤的（）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)部異常

30、概念。23 .處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是（）B.通用寄存器的內(nèi)容D. Cache中的內(nèi)容A.程序計數(shù) （PC）的內(nèi)容 器C. 塊表（TLB）的內(nèi)容【參考答案】A 【考查知識點 】外部中斷處理過程24 .假定下列指令已裝入指令寄存則執(zhí)行時不可能導(dǎo)CPU從用戶態(tài)變?yōu)閮?nèi)核 態(tài)統(tǒng)態(tài)）的是（）A. DIVR0, R1;（RO）/（R1） R0B. INTn ;產(chǎn)生軟中斷C. NOTR0寄存器 R0的內(nèi)容取非D. MOVRO,addr；把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中【參考答案】 C【考查知識點 】CPU用戶態(tài)和內(nèi)核態(tài)概念。25 .下列選項中會導(dǎo)致進程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是（）A.執(zhí)行

31、P（wait）操作C.啟動I/ 設(shè)備O【參考答案】DB. 申請內(nèi)存失敗D. 被高優(yōu)先級進程搶占【考查知識點】進程間各狀態(tài)的轉(zhuǎn)化26.若系統(tǒng) S1采用死鎖避免方法，S2采用死鎖檢測方法，下列敘述中正確的是（）I. S1會限制用戶申請資源的順序n. si需要進行所需資源總量信息，S2不需要而川.S1不會給可能導(dǎo)致死鎖的進程分配資源，S2會A.僅I nB.僅nc.僅I【參考答案】cd.i nm【考查知識點】死鎖相關(guān)概念27 .系統(tǒng)為某進程分配了 4個頁框，該進程已訪問的頁號序列為2,029,3,4,2,8,2,3,8,4,5 ,若進程要訪問的下一頁的頁號為7,依據(jù)LRU算法，應(yīng)淘汰頁的頁號是（）A.

32、 2B. 3【參考答案】 C【考查知識點】LRU算法。C. 4D. 828 .在系統(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和307400處所在的磁盤塊讀入內(nèi)存。需訪問的磁盤塊個數(shù)分別是()A. 1 , 2B. 1, 3C. 2, 3D. 2, 4【參考答案】D【考

33、查知識點 】文件索引相關(guān)概念。30 .在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是()A.可變分配，全局置換B.可變分配，局部置換C. 固定分配，全局置換D.固定分配，局部置換【參考答案】D【考查知識點】頁面分配策略和頁面置換策略的概念和相應(yīng)的方法。、綜合應(yīng)用題：4147小題，共 70分,且|data|vn(n 為正整數(shù))。現(xiàn)要求設(shè)計41.用單鏈表保存m個整數(shù)，節(jié)點的結(jié)構(gòu)為(data,link)一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次出現(xiàn)的節(jié) 點而刪除其余絕對值相等的節(jié)點例如若給定的單鏈表head如下HEAD刪除節(jié)點后的head為HEAD要求(1

34、) 給出算法的基本思想(2) 使用c或C+語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義。(3) 根據(jù)設(shè)計思想，采用 c或C+語言描述算法，關(guān)鍵之處給出注釋。(4) 說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。【參考答案】(1) 算法思想：定義一個大小為N的數(shù)組，初始化為 0.在遍歷鏈表的同時將數(shù)組中索引值為節(jié)點的值的絕對值的元素置 1.如果此元素已經(jīng)為1，說明此節(jié)點之前已經(jīng)有與此節(jié)點的值的絕對值相 等的節(jié)點，需將此節(jié)點刪除。(2) 節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstructNodeIntdata;StructNode*next;Node;(3) intan;全局?jǐn)?shù)組標(biāo)志節(jié)點的絕對值的值是否出現(xiàn)過vo

35、idDeleteABSEqualNode(Node*head)memset(a,0,n); / 初始化為 0if(head=NULL)returnNULL;Node*p=head;Node*r=head;while(p!=NULL)if(aabs(p->data)=1) /如果此絕對值已經(jīng)在節(jié)點值的絕對值中出現(xiàn)過/則刪除當(dāng)前節(jié)點r->next=p->next;deletep;p=r- >n ext;else/否則，將數(shù)組中對應(yīng)的元素置1,并將指針指向下一個兀素aabs(p->data)=1;r=p；p=p->n ext;returnhead;(4)只遍歷一次

36、鏈表，所以時間復(fù)雜度為O(n),因為申請大小為n的數(shù)組，所以空間復(fù)雜度為O(n) ,( n為節(jié)點絕對值的最大值)【考查知識點】 鏈表的操作。42.已知有5個頂點的圖G如下圖所示J/ 1 U r k JjfJr11/ zVjpJF忸(2> ./(4)請回答下列問題(1) 寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始)(2) 求A2,矩陣A2中位于0行3列元素值的含義是什么？ 若已知具有n(n>=2)個頂點的鄰接矩陣為B,則Bm(2<=m<=n)非零元素的含義是什么？【參考答案】(1) 鄰接矩陣為A2=220行3列的元素的含義是頂0到頂點點(3)Bm中非零元素的含義是：假設(shè)此頂

37、點位于3的最短距離2.為i行j列，如果i=j，則表示i頂點到自己的距離為0 ;如果i工j，則表示頂點i到達不了頂點 j?！究疾橹R點】 鄰接矩陣的概念，最短路徑。43.( 13分)某16位計算機主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式;CPU采用單總線結(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與BALUopF-十LrIiIIiJI廠T:

38、i I I I I I I I ICPUCPU內(nèi)總魏MAR1" (R*|控制牛i*主畫線主存請回答下列問題。(1) 圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T?(2) 控制信號ALUop和SRop的位數(shù)至少各是多少？(3) 控制信號Srout所控制郵件的名稱或作用是什么？(4) 端點中，哪些端點須連接到控制部件的輸出端？(5) 為完善單總線數(shù)據(jù)通路，需要在端點中相應(yīng)的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。(6) 為什么二路選擇器MUX的個輸入端是2？【參考答案】(1) 圖中程序員可見的寄存器有通用寄存器R0R3和程序計數(shù)器PC;設(shè)置暫存器T用于

39、暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。(2) ALUop和SRop的位數(shù)分別為3,2。(3) Srout所控制的部件作用是控制計算機運算結(jié)果的輸出。(4) 須連接到控制部件的輸出端端點有。(5) -，-。(6) 使PC自增2以獲取下一條指令地址?！究疾橹R點】寄存器相關(guān)概念及寄存器的操作，單總線結(jié)構(gòu)44. (10分)題43中描述的計算機，其部分指令執(zhí)行過程的控制信號如如題44圖a所示Rlout-1. MAP.in-1. MEMop 宜由IDRodf迪書呼虬j盞XJD產(chǎn) 詢a 其 鼻a bhLfKb F -IL 3'觀遒求扣斑bWfl昵腳SRorut=i；鋤書聽悄播存器輸?shù)漭敵隹刂菩盘栂x扇值狗任意的直他控*血號均未衣圈中標(biāo)出Ii jig | i i i r Iwn | I-*1 V upaq pi| “ | w|iii | PWB|f-i imB*" |m* 1 FWW題44圖a部分指令控制信號該機指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1,通用寄存器 R0R3的編號分別為0、1、2和3題44圖b指令格式請回答下