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

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

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

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

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

5、1希爾排序的組內(nèi)排序采用的是（）A 直接插入排序B折半插入排序12計算機(jī)硬件能夠直接執(zhí)行的是（） 機(jī)器語言程序 匯編語言程序 A 僅B僅 C基數(shù)排序D快速排序16，12，刪除關(guān)鍵字 8 之后需重建堆，在此過C3D 4C 快速排序D 歸并排序硬件描述語言程序C僅 D 13由 3個“1”和 5 個“ 0”組成的 8位二進(jìn)制補(bǔ)碼，能表示的最小整數(shù)是（）A -126B -125C-32D -314下列有關(guān)浮點(diǎn)數(shù)加減運(yùn)算的敘述中，正確的是（）. 對階操作不會引起階碼上溢或下溢. 右規(guī)和尾數(shù)舍入都可能引起階碼上溢. 左規(guī)時可能引起階碼下溢 . 尾數(shù)溢出時結(jié)果不一定溢出A 僅 B僅C僅 D 15假定主存地址

6、為 32 位，按字節(jié)編址，主存和 Cache 之間采用直接映射方式，主存 塊大小為 4 個字，每字 32 位，采用回寫( Write Back )方式，則能存放 4K 字?jǐn)?shù)據(jù)的 Cache 的總?cè)萘康奈粩?shù)至少是()A 146kB 147KC148KD 158K16假定編譯器將賦值語句 “ x=x+3;轉(zhuǎn)”換為指令 ”add xaddt, 3，其”中 xaddt是 x 對應(yīng)的 存儲單元地址，若執(zhí)行該指令的計算機(jī)采用頁式虛擬存儲管理方式，并配有相應(yīng)的 TLB ， 且 Cache 使用直寫 ( Write Through )方式，則完成該指令功能需要訪問主存的次數(shù)至少是()A 0B 1C2D 317

7、下列存儲器中，在工作期間需要周期性刷新的是()A SRAMB SDRAMCROMD FLASH18某計算機(jī)使用 4 體交叉存儲器， 假定在存儲器總線上出現(xiàn)的主存地址(十進(jìn)制)序 列為 8005，8006，8007， 8008，8001，8002，8003，8004，8000，則可能發(fā)生發(fā)生緩存沖 突的地址對是()A8004、8008B8002、8007 C8001、 8008 D8000、800419下列有關(guān)總線定時的敘述中，錯誤的是()A異步通信方式中，全互鎖協(xié)議最慢 B異步通信方式中，非互鎖協(xié)議的可靠性最差 C同步通信方式中，同步時鐘信號可由多設(shè)備提供 D半同步通信方式中，握手信號的采樣由

8、同步時鐘控制 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) 、陷阱 (trap)和終止 (abort)三類。下列有關(guān)內(nèi)部 異常的敘述中，錯誤的 ( )A 內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)B內(nèi)部異常的檢測由 CPU 內(nèi)部邏輯實(shí)

9、現(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)容B 通用寄存器的內(nèi)容C塊表 (TLB) 的內(nèi)容D Cache 中的內(nèi)容24假定下列指令已裝入指令寄存器。 則執(zhí)行時不可能導(dǎo)致 CPU 從用戶態(tài)變?yōu)閮?nèi)核態(tài) ( 系 統(tǒng)態(tài) )的是 ( )ADIV R0 ，R1;(R0)/(R1) R0B INT n ；產(chǎn)生軟中斷CNOT R0 ；寄存器 R0 的內(nèi)容取非DMOV R0,addr ；把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中25下列選項(xiàng)中會導(dǎo)致進(jìn)程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是() A執(zhí)行 P(wait)

10、 操作B申請內(nèi)存失敗C啟動 I/O 設(shè)備D 被高優(yōu)先級進(jìn)程搶占26若系統(tǒng) S1 采用死鎖避免方法， S2 采用死鎖檢測方法，下列敘述中正確的是() S1會限制用戶申請資源的順序 S1需要進(jìn)行所需資源總量信息，而S2不需要 S1不會給可能導(dǎo)致死鎖的進(jìn)程分配資源，S2會A 僅 B僅 C僅 D 27系統(tǒng)為某進(jìn)程分配了 4 個頁框，該進(jìn)程已訪問的頁號序列為 2,0,2,9,3,4,2,8,2,3,8,4,5 ， 若進(jìn)程要訪問的下一頁的頁號為 7，依據(jù) LRU 算法，應(yīng)淘汰頁的頁號是()A 2B 3C 4D828在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是()A 減少磁盤 I/O 次數(shù)B減少平均尋道時間C提高

11、磁盤數(shù)據(jù)可靠性D實(shí)現(xiàn)設(shè)備無關(guān)性29在文件的索引節(jié)點(diǎn)中存放直接索引指針10 個，一級二級索引指針各 1 個，磁盤塊大小為 1KB 。每個索引指針占 4 個字節(jié)。若某個文件的索引節(jié)點(diǎn)已在內(nèi)存中，到把該文件 的偏移量 (按字節(jié)編址) 為 1234 和 307400 處所在的磁盤塊讀入內(nèi)存。 需訪問的磁盤塊個數(shù) 分別是()30在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是()A 可變分配，全局置換B 可變分配，局部置換C固定分配，全局置換D 固定分配，局部置換二、綜合應(yīng)用題： 4147 小題，共 70 分。41. 用單鏈表保存 m 個整數(shù)， 節(jié)點(diǎn)的結(jié)構(gòu)為 (data,link) ，且|d

12、ata|<n(n 為正整數(shù) )。現(xiàn)要求設(shè)計 一個時間復(fù)雜度盡可能高效地算法， 對于鏈表中絕對值相等的節(jié)點(diǎn)， 僅保留第一次出現(xiàn)的節(jié) 點(diǎn)而刪除其余絕對值相等的節(jié)點(diǎn)。例如若給定的單鏈表 head 如下刪除節(jié)點(diǎn)后的 head 為要求(1) 給出算法的基本思想(2) 使用 c 或 c+語言，給出單鏈表節(jié)點(diǎn)的數(shù)據(jù)類型定義。(3) 根據(jù)設(shè)計思想，采用 c 或 c+ 語言描述算法，關(guān)鍵之處給出注釋。(4) 說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。42. 已知有 5 個頂點(diǎn)的圖 G 如下圖所示請回答下列問題(1) 寫出圖 G的鄰接矩陣 A(行、列下標(biāo)從 0 開始)(2) 求 A2，矩陣 A2中位于 0行

13、3 列元素值的含義是什么？(3) 若已知具有 n(n>=2) 個頂點(diǎn)的鄰接矩陣為 B ，則 Bm(2<=m<=n) 非零元素的含義是什 么？43. ( 13分)某 16位計算機(jī)主存按字節(jié)編碼。 存取單位為 16 位；采用 16位定長指令格式； CPU 采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中 R0R3 為通用寄存器； T 為暫存器； SR 為移位寄存器，可實(shí)現(xiàn)直送 (mov) 、左移一位 (left) 、右移一位 (right)3 種操作，控制信號為 Srop,SR 的輸出信號 Srout 控制； ALU 可實(shí)現(xiàn)直送 A(mova) 、 A 加 B(add)、 A 減 B(s

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

15、3 中描述的計算機(jī)，其部分指令執(zhí)行過程的控制信號如如題題 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ī) 器代碼各是什么？R1 + 1 R1(R1) << 1 R2(R1) (R2) R3 inc R1 shl R2,R1 sub R3, (R1),R

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

17、 B 的信箱最多放 N 個郵件。 初始時 A 的信箱中有 x 個郵件(0<x<M ). B 中有 y 個(0<y<N )。 辯論者每取出一個郵件，郵件數(shù)減 1.A、 B 兩人操作過程：Code BeginAWhile(TRUE)從 A 的信箱中取出一個郵件；回答問題并提出一個新問題；將新郵件放入 B 的信箱；BWhile(TRUE)從 B 的信箱中取出一個郵件；回答問題并提出一個新問題；將新郵件放入 A 的信箱；Code End 當(dāng)信箱不為空時，辯論者才能從信箱中取郵件，否則等待。 當(dāng)信箱不滿時，辯論者才能將新郵件放入信箱，否則等待。 請?zhí)砑颖匾男盘柫亢?P、V(或

18、wait, signed)操作，以實(shí)現(xiàn)上述過程的同步，要求寫出完整過程，并說明信號量的含義和初值。2015年全國碩士研究生入學(xué)統(tǒng)一考試計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題答案解析、單項(xiàng)選擇題：1 40 小題，每小題 2 分，共 80 分。下列每題給出的四個選項(xiàng)中，只有一個選項(xiàng)符合題目要求。請在答題卡上將所選項(xiàng)的字母涂黑。1已知程序如下：int s(int n)return (n<=0) ? 0 : s(n-1) +n;void main() cout<< s(1); 程序運(yùn)行時使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息一次對應(yīng)的是A main()->S(1)->S(

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

20、叉樹B24， 10，5 和 24， 12，7D24，10， 5 和 24， 14，6(AVL 樹) ,對其進(jìn)行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A 根節(jié)點(diǎn)的度一定為 2B樹中最小元素一定是葉節(jié)點(diǎn)C最后插入的元素一定是葉節(jié)點(diǎn)D樹中最大元素一定是無左子樹【參考答案】 B【考查知識點(diǎn) 】樹的中序遍歷和 AVL 樹的基本概念。5設(shè)有向圖 G=（V,E），頂點(diǎn)集 V=V 0,V1,V 2,V3 ，邊集 E=<v 0,v1>,<v0,v2>,<v0,v3>，<v1,v3>, 若從頂點(diǎn) V0 開始對圖進(jìn)行深度優(yōu)先遍歷，則可能得到

21、的不同遍歷序列個數(shù)是A 2B3C 4D 5【參考答案】 D【考查知識點(diǎn) 】圖的深度優(yōu)先遍歷。kruskal ）算法第二次選中但不是普里姆（6求下面帶權(quán)圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（Prim）算法（從 V4開始）第 2 次選中的邊是A (V1,V3)B (V1,V4)C(V2,V3)D(V3,V4)參考答案】考查知識點(diǎn)】最小生成樹算法的 Prim 算法和 Kruskal 算法。7下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A500，200，450，180B 500，450，200，180C180，500，200，450D 180， 200， 500， 450參考答案】 A考查知識

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

23、 8 之后需重建堆，在此過 程中，關(guān)鍵字之間的比較數(shù)是A 1B 2C3D 4【參考答案】 B【考查知識點(diǎn) 】最小堆的概念和最小堆的重建。11希爾排序的組內(nèi)排序采用的是（）A 直接插入排序B折半插入排序 C快速排序D歸并排序【參考答案】 A【考查知識點(diǎn) 】希爾排序基本思想是： 先將整個待排元素序列分割成若干個子序列 （由 相隔某個 “增量 ”的元素組成的） 分別進(jìn)行直接插入排序， 然后依次縮減增量再進(jìn)行排序，待 整個序列中的元素基本有序（增量足夠小）時，再對全體元素進(jìn)行一次直接插入排序。12計算機(jī)硬件能夠直接執(zhí)行的是（）機(jī)器語言程序 匯編語言程序 硬件描述語言程序A 僅B僅 C僅 D 【參考答案

24、】 A【考查知識點(diǎn)】 用匯編語言等非機(jī)器語言書寫好的符號程序稱源程序,運(yùn)行時匯編程序要將源程序翻譯成目標(biāo)程序，目標(biāo)程序是機(jī)器語言程序。13由 3個“1和”5 個“ 0組”成的 8位二進(jìn)制補(bǔ)碼，能表示的最小整數(shù)是（）A -126B -125C-32D -3【參考答案】 B【考查知識點(diǎn)】 二進(jìn)制的補(bǔ)碼表示。14下列有關(guān)浮點(diǎn)數(shù)加減運(yùn)算的敘述中，正確的是（）. 對階操作不會引起階碼上溢或下溢. 右規(guī)和尾數(shù)舍入都可能引起階碼上溢. 左規(guī)時可能引起階碼下溢 . 尾數(shù)溢出時結(jié)果不一定溢出A 僅 B僅C僅 D 【參考答案】 B考查知識點(diǎn)】 浮點(diǎn)數(shù)的加減運(yùn)算。15假定主存地址為 32 位，按字節(jié)編址，主存和 C

25、ache 之間采用直接映射方式，主存 塊大小為 4 個字，每字 32 位，采用回寫（ Write Back ）方式，則能存放 4K 字?jǐn)?shù)據(jù)的 Cache 的總?cè)萘康奈粩?shù)至少是（）A 146kB 147KC148KD 158K【參考答案】 B【考查知識點(diǎn)】 Cache 和主存的映射方式。直接映射方式地址映象規(guī)則： 主存儲器中 一塊只能映象到 Cache 的一個特定的塊中。 （1） 主存與緩存分成相同大小的數(shù)據(jù)塊。 （2） 主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊 數(shù)與緩存的總塊數(shù)相等。 （3） 主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的16假定編譯器將

26、賦值語句 “ x=x+3;轉(zhuǎn)”換為指令 ”add xaddt, 3，其”中 xaddt 是 x 對應(yīng)的 存儲單元地址，若執(zhí)行該指令的計算機(jī)采用頁式虛擬存儲管理方式，并配有相應(yīng)的 TLB ， 且 Cache 使用直寫 （ Write Through ）方式，則完成該指令功能需要訪問主存的次數(shù)至少是（）A 0B 1C2D 3【參考答案】 C【考查知識點(diǎn) 】 考察了頁式虛擬存儲器及 TLB 快表。17下列存儲器中，在工作期間需要周期性刷新的是（）A SRAMB SDRAMCROMD FLASH【參考答案】 B【考查知識點(diǎn) 】DRAM 使用電容存儲，所以必須隔一段時間刷新（refresh）一次，如果存

27、儲單元沒有被刷新，存儲的信息就會丟失。18某計算機(jī)使用 4 體交叉存儲器， 假定在存儲器總線上出現(xiàn)的主存地址（十進(jìn)制）序 列為 8005，8006，8007， 8008，8001，8002，8003，8004，8000，則可能發(fā)生發(fā)生緩存沖 突的地址對是（）A8004、8008B8002、8007 C8001、 8008 D8000、8004【參考答案】 C【考查知識點(diǎn) 】 考察了存儲器中的多模塊存儲器，多體并行系統(tǒng)。19下列有關(guān)總線定時的敘述中，錯誤的是（）A異步通信方式中，全互鎖協(xié)議最慢B異步通信方式中，非互鎖協(xié)議的可靠性最差C同步通信方式中，同步時鐘信號可由多設(shè)備提供 D半同步通信方式中

28、，握手信號的采樣由同步時鐘控制 【參考答案】 B【考查知識點(diǎn) 】考察了總線操作和定時，主要是同步定時與異步定時的定義及其特點(diǎn)。20若磁盤轉(zhuǎn)速為 7200 轉(zhuǎn) /分，平均尋道時間為 8ms,每個磁道包含 1000 個扇區(qū)，則訪 問一個扇區(qū)的平均存取時間大約是 ( )A 8.1msB 12.2msC 16.3msD 20.5ms【參考答案】 B【考查知識點(diǎn) 】磁盤訪問時間計算。21在采用中斷 I/O 方式控制打印輸出的情況下， CPU 和打印控制接口中的 I/O 端口之 間交換的信息不可能是 ( )A 打印字符B主存地址C設(shè)備狀態(tài)D 控制命令【參考答案】 A【考查知識點(diǎn) 】程序中斷 I/O 方式。

29、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)部邏輯實(shí)現(xiàn)C內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中D內(nèi)部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行【參考答案】 A【考查知識點(diǎn) 】內(nèi)部異常概念。23處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是A 程序計數(shù)器 (PC)的內(nèi)容C塊表 (TLB) 的內(nèi)容( )B通用寄存器的內(nèi)容【參考答案】 A【考查知識點(diǎn) 】外部中斷處理過程。24假定下列指令已裝入指令寄存器。 統(tǒng)態(tài) )的是 ( )D Cache 中的內(nèi)容則

30、執(zhí)行時不可能導(dǎo)致 CPU 從用戶態(tài)變?yōu)閮?nèi)核態(tài) ( 系A(chǔ)DIV R0 ，R1;(R0)/(R1) R0B INT n ；產(chǎn)生軟中斷CNOT R0 ；寄存器 R0 的內(nèi)容取非DMOV R0,addr ；把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中【參考答案】 C【考查知識點(diǎn) 】CPU 用戶態(tài)和內(nèi)核態(tài)概念。 25下列選項(xiàng)中會導(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【考查知識點(diǎn) 】進(jìn)程間各狀態(tài)的轉(zhuǎn)化。26若系統(tǒng) S1 采用死鎖避免方法， S2 采用死鎖檢測方法，下列敘述中正確的是（） S1會限制用戶申請資源的順序

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

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

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

34、想：定義一個大小為 N 的數(shù)組，初始化為 0.在遍歷鏈表的同時將數(shù)組中索引值為節(jié)點(diǎn)的值 的絕對值的元素置 1.如果此元素已經(jīng)為 1，說明此節(jié)點(diǎn)之前已經(jīng)有與此節(jié)點(diǎn)的值的絕對值相 等的節(jié)點(diǎn)，需將此節(jié)點(diǎn)刪除。(2) 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如下： typedef struct NodeInt data;Struct Node * next;Node;(3) int an; / 全局?jǐn)?shù)組 標(biāo)志節(jié)點(diǎn)的絕對值的值是否出現(xiàn)過void DeleteABSEqualNode(Node * head)memset(a,0,n); / 初始化為 0if (head = NULL)return NULL;Node * p

35、= head;Node * r = head;while (p != NULL)if (aabs(p->data) = 1) /如果此絕對值已經(jīng)在節(jié)點(diǎn)值的絕對值中出現(xiàn)過 / 則刪除當(dāng)前節(jié)點(diǎn)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) ，因?yàn)樯暾埓笮?n 的數(shù)組，所以空間復(fù)雜度為 O(n)，(n 為節(jié)點(diǎn)絕對值的最大值)【考查知

36、識點(diǎn)】 鏈表的操作。42. 已知有 5 個頂點(diǎn)的圖 G 如下圖所示請回答下列問題(1) 寫出圖 G的鄰接矩陣 A(行、列下標(biāo)從 0 開始)(2) 求 A2，矩陣 A2中位于 0行 3 列元素值的含義是什么？(3) 若已知具有 n(n>=2) 個頂點(diǎn)的鄰接矩陣為 B ，則 Bm(2<=m<=n) 非零元素的含義是什 么？參考答案】(1) 鄰接矩陣為0110010011100100110101030(2)01122102112A2 = 2 1 0 1 221101212100行 3列的元素的含義是頂點(diǎn) 0到頂點(diǎn) 3的最短距離為 2.(3)Bm中非零元素的含義是：假設(shè)此頂點(diǎn)位于i行

37、 j列，如果 i=j ，則表示 i頂點(diǎn)到自己的距離為 0；如果 i ，j則表示頂點(diǎn) i 到達(dá)不了頂點(diǎn) j?！究疾橹R點(diǎn)】 鄰接矩陣的概念，最短路徑。43. ( 13分)某 16位計算機(jī)主存按字節(jié)編碼。 存取單位為 16 位；采用 16位定長指令格式； CPU 采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中 R0R3 為通用寄存器； T 為暫存器； SR 為移位寄存器，可實(shí)現(xiàn)直送 (mov) 、左移一位 (left) 、右移一位 (right)3 種操作，控制信號為 Srop,SR 的輸出信號 Srout 控制； ALU 可實(shí)現(xiàn)直送 A(mova) 、 A 加 B(add)、 A 減 B(sub)、

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

39、0R3 和程序計數(shù)器 PC；設(shè)置暫存器 T 用 于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。(2) ALUop 和 SRop 的位數(shù)分別為 3,2。(3) Srout 所控制的部件作用是控制計算機(jī)運(yùn)算結(jié)果的輸出。(4) 須連接到控制部件的輸出端端點(diǎn)有。(5) ， 。(6) 使 PC 自增 2 以獲取下一條指令地址。【考查知識點(diǎn) 】寄存器相關(guān)概念及寄存器的操作，單總線結(jié)構(gòu)44. ( 10分)題 43中描述的計算機(jī)，其部分指令執(zhí)行過程的控制信號如如題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 + 1 R1 shl R2,R1; (R1) &