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

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

2、(1)->S(0)->main()2 先序序列為a,b,c,d的不同二叉樹的個(gè)數(shù)是A13B14C15D163下列選項(xiàng)給出的是從根分別到達(dá)兩個(gè)葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是A24，10，5和 24，10，7B24，10，5和24，12，7C24，10，10和 24，14，11 D24，10，5和 24，14，64現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉樹（AVL樹）,對(duì)其進(jìn)行中序遍歷可得到一個(gè)降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A根節(jié)點(diǎn)的度一定為2B樹中最小元素一定是葉節(jié)點(diǎn)C最后插入的元素一定是葉節(jié)點(diǎn) D樹中最大元素一定是無左子樹5設(shè)有向圖G=(V,E)，頂點(diǎn)集

3、V=V0,V1,V2,V3，邊集E=<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>,若從頂點(diǎn)V0 開始對(duì)圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個(gè)數(shù)是A2B3C4D56求下面帶權(quán)圖的最?。ù鷥r(jià)）生成樹時(shí)，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是A(V1,V3)B(V1,V4)C(V2,V3)D(V3,V4)7下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A500，200，450，180B500，450，200，180C180，500，200，450 D180，2

4、00，500，4508已知字符串S為“abaabaabacacaabaabcc”. 模式串t為“abaabc”, 采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”(si != ti) 時(shí)，i=j=5,則下次開始匹配時(shí)，i和j的值分別是Ai=1，j=0Bi=5，j=0Ci=5，j=2Di=6，j=29下列排序算法中元素的移動(dòng)次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是A直接插入排序 B起泡排序C基數(shù)排序 D快速排序10已知小根堆為8，15，10，21，34，16，12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的比較數(shù)是A1 B2C3 D4 11希爾排序的組內(nèi)排序采用的是（）A直接插入排序 B折半插入排序

5、C快速排序 D歸并排序12計(jì)算機(jī)硬件能夠直接執(zhí)行的是（）機(jī)器語言程序匯編語言程序硬件描述語言程序A僅B僅 C僅 D 13由3個(gè)“1”和5個(gè)“0”組成的8位二進(jìn)制補(bǔ)碼，能表示的最小整數(shù)是（）A-126 B-125 C-32 D-314下列有關(guān)浮點(diǎn)數(shù)加減運(yùn)算的敘述中，正確的是（）. 對(duì)階操作不會(huì)引起階碼上溢或下溢. 右規(guī)和尾數(shù)舍入都可能引起階碼上溢. 左規(guī)時(shí)可能引起階碼下溢. 尾數(shù)溢出時(shí)結(jié)果不一定溢出A僅 B僅 C僅 D 15假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個(gè)字，每字32位，采用回寫（Write Back）方式，則能存放4K字?jǐn)?shù)據(jù)的Cache的

6、總?cè)萘康奈粩?shù)至少是（）A146k B147K C148K D158K16假定編譯器將賦值語句“x=x+3;”轉(zhuǎn)換為指令”add xaddt, 3”，其中xaddt是x 對(duì)應(yīng)的存儲(chǔ)單元地址，若執(zhí)行該指令的計(jì)算機(jī)采用頁式虛擬存儲(chǔ)管理方式，并配有相應(yīng)的TLB，且Cache使用直寫（Write Through）方式，則完成該指令功能需要訪問主存的次數(shù)至少是（）A0 B1 C2 D317下列存儲(chǔ)器中，在工作期間需要周期性刷新的是（）ASRAM BSDRAM CROM DFLASH18某計(jì)算機(jī)使用4體交叉存儲(chǔ)器，假定在存儲(chǔ)器總線上出現(xiàn)的主存地址（十進(jìn)制）序列為8005，8006，8007，8008，800

7、1，8002，8003，8004，8000，則可能發(fā)生發(fā)生緩存沖突的地址對(duì)是（）A8004、8008 B8002、8007 C8001、8008D8000、800419下列有關(guān)總線定時(shí)的敘述中，錯(cuò)誤的是（）A異步通信方式中，全互鎖協(xié)議最慢B異步通信方式中，非互鎖協(xié)議的可靠性最差C同步通信方式中，同步時(shí)鐘信號(hào)可由多設(shè)備提供D半同步通信方式中，握手信號(hào)的采樣由同步時(shí)鐘控制20若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時(shí)間為8ms,每個(gè)磁道包含1000個(gè)扇區(qū)，則訪問一個(gè)扇區(qū)的平均存取時(shí)間大約是( )A8.1ms B12.2ms C16.3msD20.5ms21在采用中斷I/O方式控制打印輸出的情況下，CP

8、U和打印控制接口中的I/O端口之間交換的信息不可能是( )A打印字符 B主存地址 C設(shè)備狀態(tài) D控制命令22內(nèi)部異常(內(nèi)中斷)可分為故障(fault)、陷阱(trap)和終止(abort)三類。下列有關(guān)內(nèi)部異常的敘述中，錯(cuò)誤的( )A內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)B內(nèi)部異常的檢測由CPU內(nèi)部邏輯實(shí)現(xiàn)C內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中D內(nèi)部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行23處理外部中斷時(shí)，應(yīng)該由操作系統(tǒng)保存的是( )A程序計(jì)數(shù)器(PC)的內(nèi)容 B通用寄存器的內(nèi)容C塊表(TLB)的內(nèi)容 DCache中的內(nèi)容24假定下列指令已裝入指令寄存器。則執(zhí)行時(shí)不可能導(dǎo)致CPU從用戶態(tài)變?yōu)閮?nèi)核態(tài)(系

9、統(tǒng)態(tài))的是( )ADIV R0，R1;(R0)/(R1)R0BINT n；產(chǎn)生軟中斷CNOT R0；寄存器R0的內(nèi)容取非DMOV R0,addr；把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中25下列選項(xiàng)中會(huì)導(dǎo)致進(jìn)程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是（）A執(zhí)行P(wait)操作 B申請(qǐng)內(nèi)存失敗 C啟動(dòng)I/O設(shè)備 D被高優(yōu)先級(jí)進(jìn)程搶占26若系統(tǒng)S1 采用死鎖避免方法，S2采用死鎖檢測方法，下列敘述中正確的是（）S1會(huì)限制用戶申請(qǐng)資源的順序S1需要進(jìn)行所需資源總量信息，而S2不需要S1不會(huì)給可能導(dǎo)致死鎖的進(jìn)程分配資源，S2會(huì)A僅 B僅 C僅 D 27系統(tǒng)為某進(jìn)程分配了4個(gè)頁框，該進(jìn)程已訪問的頁號(hào)序列為2,0,2,9,

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

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

12、42.已知有5個(gè)頂點(diǎn)的圖G如下圖所示請(qǐng)回答下列問題(1)寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始) (2)求A2，矩陣A2中位于0行3列元素值的含義是什么？(3)若已知具有n(n>=2)個(gè)頂點(diǎn)的鄰接矩陣為B，則Bm(2<=m<=n)非零元素的含義是什么？43.（13分）某16位計(jì)算機(jī)主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式；CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0R3為通用寄存器；T為暫存器；SR為移位寄存器，可實(shí)現(xiàn)直送(mov)、左移一位(left)、右移一位(right)3種操作，控制信號(hào)為Srop,SR的輸出信號(hào)Srout控制；ALU可實(shí)現(xiàn)直送

13、A(mova)、A加B(add)、A減B(sub)、A與B(and)、A或B(or)、非A(not)、A加1(inc)7種操作，控制信號(hào)為ALUop。請(qǐng)回答下列問題。(1)圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T？(2)控制信號(hào)ALUop和SRop的位數(shù)至少各是多少？(3)控制信號(hào)Srout所控制郵件的名稱或作用是什么？(4)端點(diǎn)中，哪些端點(diǎn)須連接到控制部件的輸出端？(5)為完善單總線數(shù)據(jù)通路，需要在端點(diǎn)中相應(yīng)的端點(diǎn)之間添加必要的連線。寫出連線的起點(diǎn)和終點(diǎn)，以正確表示數(shù)據(jù)的流動(dòng)方向。(6)為什么二路選擇器MUX的一個(gè)輸入端是2？44.（10分）題43中描述的計(jì)算機(jī)，其部分指令執(zhí)行過程的

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

15、，其值為1表示有效，為0表示無效（例如，PCout=1 表示PC內(nèi)容送總線）；存儲(chǔ)器控制信號(hào)為MEMop，用于控制存儲(chǔ)器的讀(read）和寫(write)操作。寫出題44圖a中標(biāo)號(hào)處的控制信號(hào)或控制信號(hào)的取值。(4)指令“sub R1,R3,(R2)”和“inc R1”的執(zhí)行階段至少各需要多少個(gè)時(shí)鐘周期？45. 有A、B兩人通過信箱進(jìn)行辯論，每人都從自己的信箱中取得對(duì)方的問題。將答案和向?qū)Ψ教岢龅男聠栴}組成一個(gè)郵件放入對(duì)方的郵箱中，設(shè)A的信箱最多放M個(gè)郵件，B的信箱最多放 N個(gè)郵件。初始時(shí)A的信箱中有x個(gè)郵件（0<x<M）. B 中有y個(gè)（0<y<N）。辯論者每取出一個(gè)

16、郵件，郵件數(shù)減1.A、B兩人操作過程：Code BeginAWhile(TRUE)從A的信箱中取出一個(gè)郵件；回答問題并提出一個(gè)新問題；將新郵件放入B的信箱；BWhile(TRUE)從B的信箱中取出一個(gè)郵件；回答問題并提出一個(gè)新問題；將新郵件放入A的信箱；Code End當(dāng)信箱不為空時(shí)，辯論者才能從信箱中取郵件，否則等待。當(dāng)信箱不滿時(shí)，辯論者才能將新郵件放入信箱，否則等待。請(qǐng)?zhí)砑颖匾男盘?hào)量和P、V（或wait, signed）操作，以實(shí)現(xiàn)上述過程的同步，要求寫出完整過程，并說明信號(hào)量的含義和初值。2015年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題答案解析一、單項(xiàng)選擇題：140小題，

17、每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)符合題目要求。請(qǐng)?jiān)诖痤}卡上將所選項(xiàng)的字母涂黑。1已知程序如下：int s(int n) return (n<=0) ? 0 : s(n-1) +n; void main() cout<< s(1); 程序運(yùn)行時(shí)使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息一次對(duì)應(yīng)的是Amain()->S(1)->S(0) BS(0)->S(1)->main()D main()->S(0)->S(1) DS(1)->S(0)->main()【參考答案】D【考查知識(shí)點(diǎn)】棧的基本概念和函

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

19、樹中最大元素一定是無左子樹【參考答案】B【考查知識(shí)點(diǎn)】樹的中序遍歷和AVL樹的基本概念。5設(shè)有向圖G=(V,E)，頂點(diǎn)集V=V0,V1,V2,V3，邊集E=<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>,若從頂點(diǎn)V0 開始對(duì)圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個(gè)數(shù)是A2B3C4D5【參考答案】D【考查知識(shí)點(diǎn)】圖的深度優(yōu)先遍歷。6求下面帶權(quán)圖的最小（代價(jià)）生成樹時(shí)，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是A(V1,V3)B(V1,V4)C(V2,V3)D(V3,

20、V4)【參考答案】A【考查知識(shí)點(diǎn)】最小生成樹算法的Prim算法和Kruskal算法。7下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A500，200，450，180B500，450，200，180C180，500，200，450 D180，200，500，450【參考答案】A【考查知識(shí)點(diǎn)】二分查找算法。8已知字符串S為“abaabaabacacaabaabcc”. 模式串t為“abaabc”, 采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”(si != ti) 時(shí)，i=j=5,則下次開始匹配時(shí)，i和j的值分別是Ai=1，j=0Bi=5，j=0Ci=5，j=2Di=6，j=2【參考答案】C【考查知

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

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

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

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

25、DFLASH【參考答案】B【考查知識(shí)點(diǎn)】DRAM使用電容存儲(chǔ)，所以必須隔一段時(shí)間刷新（refresh）一次，如果存儲(chǔ)單元沒有被刷新，存儲(chǔ)的信息就會(huì)丟失。18某計(jì)算機(jī)使用4體交叉存儲(chǔ)器，假定在存儲(chǔ)器總線上出現(xiàn)的主存地址（十進(jìn)制）序列為8005，8006，8007，8008，8001，8002，8003，8004，8000，則可能發(fā)生發(fā)生緩存沖突的地址對(duì)是（）A8004、8008 B8002、8007 C8001、8008D8000、8004【參考答案】 C【考查知識(shí)點(diǎn)】 考察了存儲(chǔ)器中的多模塊存儲(chǔ)器，多體并行系統(tǒng)。19下列有關(guān)總線定時(shí)的敘述中，錯(cuò)誤的是（）A異步通信方式中，全互鎖協(xié)議最慢B異步通

26、信方式中，非互鎖協(xié)議的可靠性最差C同步通信方式中，同步時(shí)鐘信號(hào)可由多設(shè)備提供D半同步通信方式中，握手信號(hào)的采樣由同步時(shí)鐘控制【參考答案】 B【考查知識(shí)點(diǎn)】考察了總線操作和定時(shí)，主要是同步定時(shí)與異步定時(shí)的定義及其特點(diǎn)。20若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時(shí)間為8ms,每個(gè)磁道包含1000個(gè)扇區(qū)，則訪問一個(gè)扇區(qū)的平均存取時(shí)間大約是( )A8.1ms B12.2ms C16.3msD20.5ms【參考答案】B【考查知識(shí)點(diǎn)】磁盤訪問時(shí)間計(jì)算。21在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口之間交換的信息不可能是( )A打印字符 B主存地址 C設(shè)備狀態(tài) D控制命令【參

27、考答案】A【考查知識(shí)點(diǎn)】程序中斷I/O方式。22內(nèi)部異常(內(nèi)中斷)可分為故障(fault)、陷阱(trap)和終止(abort)三類。下列有關(guān)內(nèi)部異常的敘述中，錯(cuò)誤的( )A內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)B內(nèi)部異常的檢測由CPU內(nèi)部邏輯實(shí)現(xiàn)C內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中D內(nèi)部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行【參考答案】A【考查知識(shí)點(diǎn)】內(nèi)部異常概念。23處理外部中斷時(shí)，應(yīng)該由操作系統(tǒng)保存的是( )A程序計(jì)數(shù)器(PC)的內(nèi)容 B通用寄存器的內(nèi)容C塊表(TLB)的內(nèi)容 DCache中的內(nèi)容【參考答案】A【考查知識(shí)點(diǎn)】外部中斷處理過程。24假定下列指令已裝入指令寄存器。則執(zhí)行時(shí)不可能導(dǎo)致

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

29、給可能導(dǎo)致死鎖的進(jìn)程分配資源，S2會(huì)A僅 B僅 C僅 D 【參考答案】C【考查知識(shí)點(diǎn)】死鎖相關(guān)概念。27系統(tǒng)為某進(jìn)程分配了4個(gè)頁框，該進(jìn)程已訪問的頁號(hào)序列為2,0,2,9,3,4,2,8,2,3,8,4,5，若進(jìn)程要訪問的下一頁的頁號(hào)為7，依據(jù)LRU算法，應(yīng)淘汰頁的頁號(hào)是（）A2 B3 C4 D8 【參考答案】C【考查知識(shí)點(diǎn)】LRU算法。28在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是（）A減少磁盤I/O次數(shù)B減少平均尋道時(shí)間C提高磁盤數(shù)據(jù)可靠性D實(shí)現(xiàn)設(shè)備無關(guān)性【參考答案】A【考查知識(shí)點(diǎn)】磁盤和內(nèi)存速度的差異。29在文件的索引節(jié)點(diǎn)中存放直接索引指針10個(gè)，一級(jí)二級(jí)索引指針各1個(gè)，磁盤塊大小為1KB。

30、每個(gè)索引指針占4個(gè)字節(jié)。若某個(gè)文件的索引節(jié)點(diǎn)已在內(nèi)存中，到把該文件的偏移量（按字節(jié)編址）為1234和307400處所在的磁盤塊讀入內(nèi)存。需訪問的磁盤塊個(gè)數(shù)分別是（）A1，2 B1，3 C2，3 D2，4【參考答案】D【考查知識(shí)點(diǎn)】文件索引相關(guān)概念。30在請(qǐng)求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是（）A可變分配，全局置換 B可變分配，局部置換C固定分配，全局置換 D固定分配，局部置換【參考答案】D【考查知識(shí)點(diǎn)】頁面分配策略和頁面置換策略的概念和相應(yīng)的方法。二、綜合應(yīng)用題：4147小題，共70分。41.用單鏈表保存m個(gè)整數(shù)，節(jié)點(diǎn)的結(jié)構(gòu)為(data,link)，且|data|<

31、n(n為正整數(shù))?，F(xiàn)要求設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度盡可能高效地算法，對(duì)于鏈表中絕對(duì)值相等的節(jié)點(diǎn)，僅保留第一次出現(xiàn)的節(jié)點(diǎn)而刪除其余絕對(duì)值相等的節(jié)點(diǎn)。例如若給定的單鏈表head如下刪除節(jié)點(diǎn)后的head為要求(1)給出算法的基本思想(2)使用c或c+語言，給出單鏈表節(jié)點(diǎn)的數(shù)據(jù)類型定義。(3)根據(jù)設(shè)計(jì)思想，采用c或c+語言描述算法，關(guān)鍵之處給出注釋。(4)說明所涉及算法的時(shí)間復(fù)雜度和空間復(fù)雜度。【參考答案】(1) 算法思想：定義一個(gè)大小為N的數(shù)組，初始化為0.在遍歷鏈表的同時(shí)將數(shù)組中索引值為節(jié)點(diǎn)的值的絕對(duì)值的元素置1.如果此元素已經(jīng)為1，說明此節(jié)點(diǎn)之前已經(jīng)有與此節(jié)點(diǎn)的值的絕對(duì)值相等的節(jié)點(diǎn)，需將此節(jié)點(diǎn)刪除。(2

32、) 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct Node Int data; Struct Node * next;Node;(3) int an; / 全局?jǐn)?shù)組 標(biāo)志節(jié)點(diǎn)的絕對(duì)值的值是否出現(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) /如果此絕對(duì)值已經(jīng)在節(jié)點(diǎn)值的絕對(duì)值中出現(xiàn)過 /則刪除當(dāng)前節(jié)點(diǎn)r->

33、;next = p->next;delete p;p = r->next;else /否則，將數(shù)組中對(duì)應(yīng)的元素置1，并將指針指向下一個(gè)元素aabs(p->data) = 1;r = p;p = p->next;return head;(4) 只遍歷一次鏈表，所以時(shí)間復(fù)雜度為O(n)，因?yàn)樯暾?qǐng)大小為n的數(shù)組，所以空間復(fù)雜度為O(n)，（n為節(jié)點(diǎn)絕對(duì)值的最大值）?！究疾橹R(shí)點(diǎn)】鏈表的操作。42.已知有5個(gè)頂點(diǎn)的圖G如下圖所示請(qǐng)回答下列問題(1)寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始) (2)求A2，矩陣A2中位于0行3列元素值的含義是什么？(3)若已知具有n(n>=

34、2)個(gè)頂點(diǎn)的鄰接矩陣為B，則Bm(2<=m<=n)非零元素的含義是什么？【參考答案】(1)鄰接矩陣為（2）0行3列的元素的含義是頂點(diǎn)0到頂點(diǎn)3的最短距離為2.（3）Bm中非零元素的含義是：假設(shè)此頂點(diǎn)位于i行j列，如果i=j，則表示i頂點(diǎn)到自己的距離為0；如果ij，則表示頂點(diǎn)i到達(dá)不了頂點(diǎn)j?！究疾橹R(shí)點(diǎn)】鄰接矩陣的概念，最短路徑。 43.（13分）某16位計(jì)算機(jī)主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式；CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0R3為通用寄存器；T為暫存器；SR為移位寄存器，可實(shí)現(xiàn)直送(mov)、左移一位(left)、右移一位(right)3

35、種操作，控制信號(hào)為Srop,SR的輸出信號(hào)Srout控制；ALU可實(shí)現(xiàn)直送A(mova)、A加B(add)、A減B(sub)、A與B(and)、A或B(or)、非A(not)、A加1(inc)7種操作，控制信號(hào)為ALUop。請(qǐng)回答下列問題。(1)圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T？(2)控制信號(hào)ALUop和SRop的位數(shù)至少各是多少？(3)控制信號(hào)Srout所控制郵件的名稱或作用是什么？(4)端點(diǎn)中，哪些端點(diǎn)須連接到控制部件的輸出端？(5)為完善單總線數(shù)據(jù)通路，需要在端點(diǎn)中相應(yīng)的端點(diǎn)之間添加必要的連線。寫出連線的起點(diǎn)和終點(diǎn)，以正確表示數(shù)據(jù)的流動(dòng)方向。(6)為什么二路選擇器MUX的

36、一個(gè)輸入端是2？【參考答案】(1) 圖中程序員可見的寄存器有通用寄存器R0R3和程序計(jì)數(shù)器PC；設(shè)置暫存器T用于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。(2) ALUop和SRop的位數(shù)分別為3,2。(3) Srout所控制的部件作用是控制計(jì)算機(jī)運(yùn)算結(jié)果的輸出。(4) 須連接到控制部件的輸出端端點(diǎn)有。(5) ，。(6) 使PC自增2以獲取下一條指令地址?！究疾橹R(shí)點(diǎn)】寄存器相關(guān)概念及寄存器的操作，單總線結(jié)構(gòu)44.（10分）題43中描述的計(jì)算機(jī)，其部分指令執(zhí)行過程的控制信號(hào)如如題44圖a所示。題44圖a 部分指令控制信號(hào)該機(jī)指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0R3的編號(hào)分別為0、1、2和3。題44圖b 指令格式請(qǐng)回答下列問題。(1)該機(jī)的指令系統(tǒng)最多可定義多少條指令？(2)假定inc、shl和sub指令的操作碼分別為01H、02H和03H，則以下指令對(duì)應(yīng)的機(jī)器代碼各是什么？ inc R1 ; R1 + 1R1 shl R2,R1 ; (R1) << 1R2 sub R3, (R1),R