全國碩士研究生入學統(tǒng)一考試計算機專業(yè)基礎綜合真題及答案解析.doc

《全國碩士研究生入學統(tǒng)一考試計算機專業(yè)基礎綜合真題及答案解析.doc》由會員分享，可在線閱讀，更多相關《全國碩士研究生入學統(tǒng)一考試計算機專業(yè)基礎綜合真題及答案解析.doc（24頁珍藏版）》請在裝配圖網上搜索。

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

2、ain() C． main()->S(0)->S(1) D．S(1)->S(0)->main() 2． 先序序列為a,b,c,d的不同二叉樹的個數是 A．13 B．14 C．15 D．16 3．下列選項給出的是從根分別到達兩個葉節(jié)點路徑上的權值序列，能屬于同一棵哈夫 曼樹的是 A．24，10，5和 24，10，7 B．24，10，5和24，12，7 C．24，10，10和 24，14，11 D．24，10，5和 24，14，6 4．現(xiàn)在有一顆無重復關鍵字的平衡二叉樹（AVL樹）,對其進行中序遍歷可得到一個降序序列。下

3、列關于該平衡二叉樹的敘述中，正確的是 A．根節(jié)點的度一定為2 B．樹中最小元素一定是葉節(jié)點 C．最后插入的元素一定是葉節(jié)點 D．樹中最大元素一定是無左子樹 5．設有向圖G=(V,E)，頂點集V={V0,V1,V2,V3}，邊集E={,,，},若從頂點V0 開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數是 A．2 B．3 C．4 D．5 6．求下面帶權圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是 A．(V1

4、,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4) 7．下列選項中，不能構成折半查找中關鍵字比較序列的是 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8．已知字符串S為“abaabaabacacaabaabcc”. 模式串t為“abaabc”, 采用KMP算法進行匹配，第一次出現(xiàn)“失配”(s[i] != t[i]) 時，i=j=5,則下次開始匹配時，i和j的值分別是 A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．

5、i=6，j=2 9．下列排序算法中元素的移動次數和關鍵字的初始排列次序無關的是 A．直接插入排序 B．起泡排序 C．基數排序 D．快速排序 10．已知小根堆為8，15，10，21，34，16，12，刪除關鍵字8之后需重建堆，在此過程中，關鍵字之間的比較數是 A．1 B．2 C．3 D．4 11．希爾排序的組內排序采用的是（） A．直接插入排序 B．折半插入排序 C．快速排序 D．歸并排序 12．計算機硬件能夠直接執(zhí)行的是（） Ⅰ．機器語言程序 Ⅱ．匯編語言程序 Ⅲ．硬件描述語言程序 A．僅Ⅰ B．僅Ⅰ Ⅱ C．僅Ⅰ Ⅲ

6、 D．ⅠⅡ Ⅲ 13．由3個“1”和5個“0”組成的8位二進制補碼，能表示的最小整數是（） A．-126 B．-125 C．-32 D．-3 14．下列有關浮點數加減運算的敘述中，正確的是（） Ⅰ. 對階操作不會引起階碼上溢或下溢 Ⅱ. 右規(guī)和尾數舍入都可能引起階碼上溢 Ⅲ. 左規(guī)時可能引起階碼下溢 Ⅳ. 尾數溢出時結果不一定溢出 A．僅Ⅱ Ⅲ B．僅ⅠⅡⅣ C．僅ⅠⅢ Ⅳ D．ⅠⅡ Ⅲ Ⅳ 15．假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每字32位，采用回寫（Write Back

7、）方式，則能存放4K字數據的Cache的總容量的位數至少是（） A．146k B．147K C．148K D．158K 16．假定編譯器將賦值語句“x=x+3;”轉換為指令”add xaddt, 3”，其中xaddt是x 對應的存儲單元地址，若執(zhí)行該指令的計算機采用頁式虛擬存儲管理方式，并配有相應的TLB，且Cache使用直寫（Write Through）方式，則完成該指令功能需要訪問主存的次數至少是（） A．0 B．1 C．2 D．3 17．下列存儲器中，在工作期間需要周期性刷新的是（） A．SRAM B．

8、SDRAM C．ROM D．FLASH 18．某計算機使用4體交叉存儲器，假定在存儲器總線上出現(xiàn)的主存地址（十進制）序列為8005，8006，8007，8008，8001，8002，8003，8004，8000，則可能發(fā)生發(fā)生緩存沖突的地址對是（） A．8004、8008 B．8002、8007 C．8001、8008 D．8000、8004 19．下列有關總線定時的敘述中，錯誤的是（） A．異步通信方式中，全互鎖協(xié)議最慢 B．異步通信方式中，非互鎖協(xié)議的可靠性最差 C．同步通信方式中，同步時鐘信號可由多設備提供 D．半同步通信方式中，握手信號的采樣由同步

9、時鐘控制 20．若磁盤轉速為7200轉/分，平均尋道時間為8ms,每個磁道包含1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是( ) A．8.1ms B．12.2ms C．16.3ms D．20.5ms 21．在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口之間交換的信息不可能是( ) A．打印字符 B．主存地址 C．設備狀態(tài) D．控制命令 22．內部異常(內中斷)可分為故障(fault)、陷阱(trap)和終止(abort)三類。下列有關內部異常的敘述中，錯誤的( ) A．內部異常的產生與當前執(zhí)行指令相關 B．內部異常

10、的檢測由CPU內部邏輯實現(xiàn) C．內部異常的響應發(fā)生在指令執(zhí)行過程中 D．內部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行 23．處理外部中斷時，應該由操作系統(tǒng)保存的是( ) A．程序計數器(PC)的內容 B．通用寄存器的內容 C．塊表(TLB)的內容 D．Cache中的內容 24．假定下列指令已裝入指令寄存器。則執(zhí)行時不可能導致CPU從用戶態(tài)變?yōu)閮群藨B(tài)(系統(tǒng)態(tài))的是( ) A．DIV R0，R1;(R0)/(R1)→R0 B．INT n；產生軟中斷 C．NOT R0；寄存器R0的內容取非 D．MOV R0,addr；把地址處的內存數據放入寄存器R0中

11、 25．下列選項中會導致進程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是（） A．執(zhí)行P(wait)操作 B．申請內存失敗 C．啟動I/O設備 D．被高優(yōu)先級進程搶占 26．若系統(tǒng)S1 采用死鎖避免方法，S2采用死鎖檢測方法，下列敘述中正確的是（） Ⅰ．S1會限制用戶申請資源的順序 Ⅱ．S1需要進行所需資源總量信息，而S2不需要 Ⅲ．S1不會給可能導致死鎖的進程分配資源，S2會 A．僅Ⅰ Ⅱ B．僅Ⅱ Ⅲ C．僅Ⅰ Ⅲ D．Ⅰ Ⅱ Ⅲ 27．系統(tǒng)為某進程分配了4個頁框，該進程已訪問的頁號序列為2,0,2,9,3,4,2,8,2,3,8,4

12、,5，若進程要訪問的下一頁的頁號為7，依據LRU算法，應淘汰頁的頁號是（） A．2 B．3 C．4 D．8 28．在系統(tǒng)內存中設置磁盤緩沖區(qū)的主要目的是（） A．減少磁盤I/O次數 B．減少平均尋道時間 C．提高磁盤數據可靠性 D．實現(xiàn)設備無關性 29．在文件的索引節(jié)點中存放直接索引指針10個，一級二級索引指針各1個，磁盤塊大小為1KB。每個索引指針占4個字節(jié)。若某個文件的索引節(jié)點已在內存中，到把該文件的偏移量（按字節(jié)編址）為1234和307400處所在的磁盤塊讀入內存。需訪問的磁盤塊個數分別是（） A．1，2 B．1，3 C．

13、2，3 D．2，4 30．在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是（） A．可變分配，全局置換 B．可變分配，局部置換 C．固定分配，全局置換 D．固定分配，局部置換 二、綜合應用題：41~47小題，共70分。 41. 用單鏈表保存m個整數，節(jié)點的結構為(data,link)，且|data|

14、想 (2) 使用c或c++語言，給出單鏈表節(jié)點的數據類型定義。 (3) 根據設計思想，采用c或c++語言描述算法，關鍵之處給出注釋。 (4) 說明所涉及算法的時間復雜度和空間復雜度。 42. 已知有5個頂點的圖G如下圖所示 請回答下列問題 (1) 寫出圖G的鄰接矩陣A(行、列下標從0開始) (2) 求A2，矩陣A2中位于0行3列元素值的含義是什么？ (3) 若已知具有n(n>=2)個頂點的鄰接矩陣為B，則Bm(2<=m<=n)非零元素的含義是什么？ 43. （13分）某16位計算機主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式；CPU采用單總線結構，主要

15、部分如下圖所示。圖中R0~R3為通用寄存器；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？ (2) 控制信號ALUop和SRop的位數至少各是多少？ (3) 控制信號Srout所控制郵件的名稱或作用是什么？ (4) 端點①~⑨中，哪

16、些端點須連接到控制部件的輸出端？ (5) 為完善單總線數據通路，需要在端點①~⑨中相應的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數據的流動方向。 (6) 為什么二路選擇器MUX的一個輸入端是2？ 44. （10分）題43中描述的計算機，其部分指令執(zhí)行過程的控制信號如如題44圖a所示。 題44圖a 部分指令控制信號 該機指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0~R3的編號分別為0、1、2和3。 題44圖b 指令格式 請回答下列問題。 (1) 該機的指令系統(tǒng)最多可定義多少條指令？ (2)

17、假定inc、shl和sub指令的操作碼分別為01H、02H和03H，則以下指令對應的機 器代碼各是什么？ ① inc R1 ; R1 + 1→R1 ② shl R2,R1 ; (R1) << 1→R2 ③ sub R3, (R1),R2 ; ((R1)) – (R2) → R3 (3) 假定寄存器X的輸入和輸出控制信號分別為Xin和Xout，其值為1表示有效，為0表示無效（例如，PCout=1 表示PC內容送總線）；存儲器控制信號為MEMop，用于控制存儲器的讀(read）和寫(write)操作。寫出題44圖a中標號①⑧處的控制信號或控制信

18、號的取值。 (4) 指令“sub R1,R3,(R2)”和“inc R1”的執(zhí)行階段至少各需要多少個時鐘周期？ 45. 有A、B兩人通過信箱進行辯論，每人都從自己的信箱中取得對方的問題。將答案和向對方提出的新問題組成一個郵件放入對方的郵箱中，設A的信箱最多放M個郵件，B的信箱最多放 N個郵件。初始時A的信箱中有x個郵件（0

19、 While(TRUE){ 從B的信箱中取出一個郵件； 回答問題并提出一個新問題； 將新郵件放入A的信箱； } } Code End 當信箱不為空時，辯論者才能從信箱中取郵件，否則等待。 當信箱不滿時，辯論者才能將新郵件放入信箱，否則等待。 請?zhí)砑颖匾男盘柫亢蚉、V（或wait, signed）操作，以實現(xiàn)上述過程的同步，要求寫出完整過程，并說明信號量的含義和初值。 2015年全國碩士研究生入學統(tǒng)一考試 計算機學科專業(yè)基礎綜合試題答案解析 一、單項選擇題：1~40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項符合題目要求。請在答題卡上將所選項的

20、字母涂黑。 1．已知程序如下： int s(int n) { return (n<=0) ? 0 : s(n-1) +n; } void main() { cout<< s(1); } 程序運行時使用棧來保存調用過程的信息，自棧底到棧頂保存的信息一次對應的是 A．main()->S(1)->S(0) B．S(0)->S(1)->main() D． main()->S(0)->S(1) D．S(1)->S(0)->main() 【參考答案】D 【考查知識點】棧的基本概念和函數調用的原理。 3．

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

22、確的是 A．根節(jié)點的度一定為2 B．樹中最小元素一定是葉節(jié)點 C．最后插入的元素一定是葉節(jié)點 D．樹中最大元素一定是無左子樹 【參考答案】B 【考查知識點】樹的中序遍歷和AVL樹的基本概念。 5．設有向圖G=(V,E)，頂點集V={V0,V1,V2,V3}，邊集E={,,，},若從頂點V0 開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數是 A．2 B．3 C．4 D．5 【參考答案】D 【考查知識點】圖的深度優(yōu)先遍歷。 6．求下面帶權圖的最小（代價）生成樹時，可能是克魯斯卡（krus

23、kal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是 A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4) 【參考答案】A 【考查知識點】最小生成樹算法的Prim算法和Kruskal算法。 7．下列選項中，不能構成折半查找中關鍵字比較序列的是 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 【參考答案】A 【考查知識點】二分查找算法。 8．已知字符串S為“abaabaabacacaabaabcc”.

24、 模式串t為“abaabc”, 采用KMP算法進行匹配，第一次出現(xiàn)“失配”(s[i] != t[i]) 時，i=j=5,則下次開始匹配時，i和j的值分別是 A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=2 【參考答案】C 【考查知識點】模式匹配（KMP）算法。 9．下列排序算法中元素的移動次數和關鍵字的初始排列次序無關的是 A．直接插入排序 B．起泡排序 C．基數排序 D．快速排序 【參考答案】B 【考查知識點】幾種排序算法的比較。 10．已知小根堆為8，15，10，21，34，16，12，刪除關鍵字8之后需重建堆，在此過程中，關鍵字

25、之間的比較數是 A．1 B．2 C．3 D．4 【參考答案】B 【考查知識點】最小堆的概念和最小堆的重建。 11．希爾排序的組內排序采用的是（） A．直接插入排序 B．折半插入排序 C．快速排序 D．歸并排序 【參考答案】A 【考查知識點】希爾排序基本思想是：先將整個待排元素序列分割成若干個子序列（由 相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。 12．計算機硬件能夠直接執(zhí)行的是（） Ⅰ．機器語言程序 Ⅱ．匯編語言程序

26、Ⅲ．硬件描述語言程序 A．僅Ⅰ B．僅Ⅰ Ⅱ C．僅Ⅰ Ⅲ D．ⅠⅡ Ⅲ 【參考答案】A 【考查知識點】用匯編語言等非機器語言書寫好的符號程序稱源程序,運行時匯編程序要 將源程序翻譯成目標程序，目標程序是機器語言程序。 13．由3個“1”和5個“0”組成的8位二進制補碼，能表示的最小整數是（） A．-126 B．-125 C．-32 D．-3 【參考答案】B 【考查知識點】二進制的補碼表示。 14．下列有關浮點數加減運算的敘述中，正確的是（） Ⅰ. 對階操作不會引起階碼上溢或下溢 Ⅱ. 右規(guī)和尾數舍入都可能引起階碼上溢 Ⅲ. 左

27、規(guī)時可能引起階碼下溢 Ⅳ. 尾數溢出時結果不一定溢出 A．僅Ⅱ Ⅲ B．僅ⅠⅡⅣ C．僅ⅠⅢ Ⅳ D．ⅠⅡ Ⅲ Ⅳ 【參考答案】B 【考查知識點】浮點數的加減運算。 15．假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每字32位，采用回寫（Write Back）方式，則能存放4K字數據的Cache的總容量的位數至少是（） A．146k B．147K C．148K D．158K 【參考答案】 B 【考查知識點】Cache 和主存的映射方式。直接映射方式地址映象規(guī)則： 主存儲器中一塊只能映象

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

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

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

31、個扇區(qū)的平均存取時間大約是( ) A．8.1ms B．12.2ms C．16.3ms D．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．內

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

33、斷 C．NOT R0；寄存器R0的內容取非 D．MOV R0,addr；把地址處的內存數據放入寄存器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采用死鎖檢測方法，下列敘述中正確的是（） Ⅰ．S1會限制用戶申請資源的順序 Ⅱ．S1需要進行所需資源總量信息，而S2不需要 Ⅲ．S1不

34、會給可能導致死鎖的進程分配資源，S2會 A．僅Ⅰ Ⅱ B．僅Ⅱ Ⅲ C．僅Ⅰ Ⅲ D．Ⅰ Ⅱ Ⅲ 【參考答案】C 【考查知識點】死鎖相關概念。 27．系統(tǒng)為某進程分配了4個頁框，該進程已訪問的頁號序列為2,0,2,9,3,4,2,8,2,3,8,4,5，若進程要訪問的下一頁的頁號為7，依據LRU算法，應淘汰頁的頁號是（） A．2 B．3 C．4 D．8 【參考答案】C 【考查知識點】LRU算法。 28．在系統(tǒng)內存中設置磁盤緩沖區(qū)的主要目的是（） A．減少磁盤I/O次數 B．減少平均尋道時間 C．提高磁盤數據可靠

35、性 D．實現(xiàn)設備無關性 【參考答案】A 【考查知識點】磁盤和內存速度的差異。 29．在文件的索引節(jié)點中存放直接索引指針10個，一級二級索引指針各1個，磁盤塊大小為1KB。每個索引指針占4個字節(jié)。若某個文件的索引節(jié)點已在內存中，到把該文件的偏移量（按字節(jié)編址）為1234和307400處所在的磁盤塊讀入內存。需訪問的磁盤塊個數分別是（） A．1，2 B．1，3 C．2，3 D．2，4 【參考答案】D 【考查知識點】文件索引相關概念。 30．在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是（） A．可變分配，全局置換 B．可變分配，局部置換

36、 C．固定分配，全局置換 D．固定分配，局部置換 【參考答案】D 【考查知識點】頁面分配策略和頁面置換策略的概念和相應的方法。 二、綜合應用題：41~47小題，共70分。 41. 用單鏈表保存m個整數，節(jié)點的結構為(data,link)，且|data|

37、根據設計思想，采用c或c++語言描述算法，關鍵之處給出注釋。 (4) 說明所涉及算法的時間復雜度和空間復雜度。 【參考答案】 (1) 算法思想： 定義一個大小為N的數組，初始化為0.在遍歷鏈表的同時將數組中索引值為節(jié)點的值的絕對值的元素置1.如果此元素已經為1，說明此節(jié)點之前已經有與此節(jié)點的值的絕對值相等的節(jié)點，需將此節(jié)點刪除。 (2) 節(jié)點的數據結構定義如下： typedef struct Node { Int data; Struct Node * next; }Node; (3) int a[n]; // 全局數組 標志節(jié)點的絕對值的值是否出現(xiàn)過

38、 void DeleteABSEqualNode(Node * head) { memset(a,0,n); // 初始化為0 if (head == NULL) { return NULL; } Node * p = head; Node * r = head; while (p != NULL) { if (a[abs(p->data)] == 1) //如果此絕對值已經在節(jié)點值的絕對值中出現(xiàn)過 { //則刪除當前節(jié)點 r->next = p->next; de

39、lete p; p = r->next; } else //否則，將數組中對應的元素置1，并將指針指向下一個元素 { a[abs(p->data)] = 1; r = p; p = p->next; } } return head; } (4) 只遍歷一次鏈表，所以時間復雜度為O(n)， 因為申請大小為n的數組，所以空間復雜度為O(n)，（n為節(jié)點絕對值的最大值）。 【考查知識點】鏈表的操作。 42. 已知有5個頂點的圖G如下圖所示 請回答下列問題 (1) 寫出圖G的鄰接矩陣A(行、列

40、下標從0開始) (2) 求A2，矩陣A2中位于0行3列元素值的含義是什么？ (3) 若已知具有n(n>=2)個頂點的鄰接矩陣為B，則Bm(2<=m<=n)非零元素的含義是什么？ 【參考答案】 (1)鄰接矩陣為 （2） 0行3列的元素的含義是頂點0到頂點3的最短距離為2. （3）Bm中非零元素的含義是：假設此頂點位于i行j列，如果i==j，則表示i頂點到自己的距離為0；如果i≠j，則表示頂點i到達不了頂點j。 【考查知識點】鄰接矩陣的概念，最短路徑。 43. （13分）某16位計算機主存按字節(jié)編碼。存取單位為16位；采用16位定長指令格式；CPU采用單總線結構，主要

41、部分如下圖所示。圖中R0~R3為通用寄存器；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？ (2) 控制信號ALUop和SRop的位數至少各是多少？ (3) 控制信號Srout所控制郵件的名稱或作用是什么？ (4) 端點①~⑨中，哪

42、些端點須連接到控制部件的輸出端？ (5) 為完善單總線數據通路，需要在端點①~⑨中相應的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數據的流動方向。 (6) 為什么二路選擇器MUX的一個輸入端是2？ 【參考答案】 (1) 圖中程序員可見的寄存器有通用寄存器R0~R3和程序計數器PC；設置暫存器T用于暫存數據總線發(fā)送的數據。 (2) ALUop和SRop的位數分別為3,2。 (3) Srout所控制的部件作用是控制計算機運算結果的輸出。 (4) 須連接到控制部件的輸出端端點有①②③⑤⑧。 (5) ⑥→⑨，⑦→④。 (6) 使PC自增2以獲取下一條指令地址。 【考查

43、知識點】寄存器相關概念及寄存器的操作，單總線結構 44. （10分）題43中描述的計算機，其部分指令執(zhí)行過程的控制信號如如題44圖a所示。 題44圖a 部分指令控制信號 該機指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0~R3的編號分別為0、1、2和3。 題44圖b 指令格式 請回答下列問題。 (1) 該機的指令系統(tǒng)最多可定義多少條指令？ (2) 假定inc、shl和sub指令的操作碼分別為01H、02H和03H，則以下指令對應的機 器代碼各是什么？ ③ inc R1 ; R1 + 1

44、→R1 ④ shl R2,R1 ; (R1) << 1→R2 ③ sub R3, (R1),R2 ; ((R1)) – (R2) → R3 (3) 假定寄存器X的輸入和輸出控制信號分別為Xin和Xout，其值為1表示有效，為0表示無效（例如，PCout=1 表示PC內容送總線）；存儲器控制信號為MEMop，用于控制存儲器的讀(read）和寫(write)操作。寫出題44圖a中標號①~⑧處的控制信號或控制信號的取值。 (4) 指令“sub R1,R3,(R2)”和“inc R1”的執(zhí)行階段至少各需要多少個時鐘周期？ 【參考答案】 (1) 128 (2) ① 0

45、280H，② 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

46、ile(TRUE){ 從A的信箱中取出一個郵件； 回答問題并提出一個新問題； 將新郵件放入B的信箱； } } B{ While(TRUE){ 從B的信箱中取出一個郵件； 回答問題并提出一個新問題； 將新郵件放入A的信箱； } } Code End 當信箱不為空時，辯論者才能從信箱中取郵件，否則等待。 當信箱不滿時，辯論者才能將新郵件放入信箱，否則等待。 請?zhí)砑颖匾男盘柫亢蚉、V（或wait, signed）操作，以實現(xiàn)上述過程的同步，要求寫出完整過程，并說明信號量的含義和初值。 【參考答案】 Semaphore mutexA=1; Semaphore

47、 mutexB=1; Semaphore emptyA=M; Semaphore emptyB=N; Semaphore fullA=0; Semaphore fullB=0; Code Begin A{ While(TRUE){ P(fullA); P(mutexA) Get a mail from A_mailbox； V(mutexA); V(fullA); Answer the question and raise a question; P(emptyB); P(mutexB) send the mail to B； V(mutexB); V(emptyB); } } B{ While(TRUE){ P(fullB); P(mutexB) Get a mail from B_mailbox； V(mutexB); V(fullB); Answer the question and raise a question; P(emptyA); P(mutexA)  send the mail to A； V(mutexA); V(emptyA); } } Code End 【考查知識點】 考察了利用信號量進程同步問題。