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

1、WORD格式2015 年全國(guó)碩士研究生入學(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)的是A main()->S(1)->S(0)B S(0)->S(1)->main()Cmain()->S(0)-

2、>S(1)D S(1)->S(0)->main()2先序序列為 a,b,c,d 的不同二叉樹的個(gè)數(shù)是A13B14C15D16專業(yè)資料整理3A 24 ， 10 ， 5 和 24 ，10， 7B 24 ， 10 ， 5 和 24 ， 12 ， 7C24， 10 ， 10 和 24 ， 14 ， 11D 24 ， 10， 5 和 24 ， 14 ， 64現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二 叉樹序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是AVL 樹） , 對(duì)其進(jìn)行中序遍歷可得到一個(gè)降A(chǔ) 根節(jié)點(diǎn)的度一定為 2B樹中最小元素一定是葉節(jié)點(diǎn)C最后插入的元素一定是葉節(jié)點(diǎn)D 樹中最大元素一定是無左

3、子樹5設(shè)有向圖 G=(V,E) ，頂點(diǎn)集 V=V 0,V 1,V 2,V 3 <v 1,v3>,，邊集 E=<v 0,v1>,<v 0,v2>,<v 0,v3>若從頂點(diǎn) V 0 開始對(duì)圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個(gè)數(shù)是A2B3C4D5列選項(xiàng)給出的是從根分別到達(dá)兩個(gè)葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是kruskal ）算法第二次選6求下面帶權(quán)圖的最小（代價(jià)）生成樹時(shí)，可能是克魯斯卡（中但不是普里姆（ Prim ）算法（從 V 4 開始）第 2 次選中的邊是A (V1,V3)B (V1,V4)C (V2,V3)D (V3,

4、V4)B 500 ， 450，200 ， 1807下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A 500 ， 200 ， 450 ，180C180， 500 ， 200 ，450D 180， 200 ，500 ， 4508已知字符串 S 為 行abaabaabacacaabaabcc模式”串 . t為 “ abaabc ”采用 , KMP 算法進(jìn)匹配，第一次出現(xiàn) “失配i 和 j”(si != ti) 的值分別是時(shí)， i=j=5, 則下次開始匹配時(shí)，A i=1 ， j=0B i=5j=0C i=5j=2Di=6 ， j=29下列排序算法中元素的移動(dòng)次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是A 直接

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

6、引起階碼下溢 . 尾數(shù)溢出時(shí)結(jié)果不一定溢出A 僅 B僅C僅 D 15假定主存地址為32 位，按字節(jié)編址，主存 和Cache 之間采用直接映射方式，主存塊大小為4 個(gè)字，每 字32 位，采用回寫 Write( Back)方式，則能存 放4K 字?jǐn)?shù)據(jù) 的Cache的總?cè)萘康奈粩?shù)至少是()A 146kB147KC 148KD 158K16句假定編譯器將賦值語“ x=x+3;3，其”中轉(zhuǎn)”換為指令” add xaddt, xadd 是 x 對(duì)應(yīng)的 t存儲(chǔ)單元地址，若執(zhí)行該指令的計(jì)算機(jī)采用頁(yè)式虛擬存儲(chǔ)管理方式，并配有相應(yīng)的 TLB ， 且 Cache 使用直寫( Write Through )方式，則完

7、成該指令功能需要訪問主存的次數(shù) ()至少是A 0B 1C2D 317下列存儲(chǔ)器中，在工作期間需要周期性刷新的是()A SRAMB SDRAMC ROMD FLASH18某計(jì)算機(jī)使用 4 體交叉存儲(chǔ)器， 假定在存儲(chǔ)器總線上出現(xiàn)的主存地址(十進(jìn)制)序 列為 8005 ， 8006 ， 8007 ， 8008 ， 8001 ， 8002 ， 8003 ， 8004 ， 8000 ，則可能發(fā)生發(fā) 生緩存沖突的地址對(duì)是()A 8004 、 8008 B 8002 、 8007 C 8001 、 8008 D 8000 、 800419下列有關(guān)總線定時(shí)的敘述中，錯(cuò)誤的是()A 異步通信方式中，全互鎖協(xié)議最

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

9、bort) 三類 列有關(guān)內(nèi)部異常的敘述中，錯(cuò)誤的 ( )A 內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)B內(nèi)部異常的檢測(cè)由 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)容D Cache 中的內(nèi)容24假定下列指令已裝入指令寄存 器。則執(zhí)行時(shí)不可能導(dǎo)致CPU 從用戶態(tài)變?yōu)閮?nèi)核 態(tài)(系統(tǒng)態(tài) ) 的是 ()ADIV R0BINT n ；R1;(R0)/(R1) 產(chǎn)生軟中斷 R0CNOT R0；寄存器 R0 的內(nèi)容取非DMOV R0,addr

10、 ；把地址處的內(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 采用死鎖避免方法， 111S2 采用死鎖檢測(cè)方法，下列敘述中正確的是()會(huì)限制用戶申請(qǐng)資源的順序 需要進(jìn)行所需資源總量信息， 而 不會(huì)給可能導(dǎo)致死鎖的進(jìn)程分配資 源，S2 不需要S2 會(huì)A僅27系統(tǒng)為某進(jìn)程分配4 個(gè)頁(yè)框，該進(jìn)程已訪問的頁(yè)號(hào)序列了為B僅 C僅 D2,0,2,9,3,4,2,8,2,3,8,4 ,5 ，若進(jìn)程要訪問的下一頁(yè)的頁(yè)號(hào)為7，依據(jù) LRU算法，應(yīng)淘汰頁(yè)的頁(yè)號(hào)是()A2B3C

11、4D28在系統(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ù)分別是()1，2B1， 3C 2， 3D2，430在請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)面分配策略與頁(yè)面置換策略不能組合使用的是()A 可變分配，全局置換 B 可變分配，局部置換C固定分配，全局置換D 固定分配，局部置換二、

12、綜合應(yīng)用題： 4147 小題，共 70 分。為正整數(shù) ) 。僅保留第一41. 用單鏈表保存 m 個(gè)整數(shù)， 節(jié)點(diǎn)的結(jié)構(gòu)為 (data,link) ，且 |data|<n(n 現(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ù)雜度。42. 已知有 5 個(gè)頂點(diǎn)的圖 G

13、如下圖所示請(qǐng)回答下列問題(1)(2)3.(有3)若已知具 n(n>=2) 個(gè)頂點(diǎn)的鄰接矩 陣為13分) 16 位計(jì)算機(jī)主存按字節(jié)編碼。CPU 采用單總線結(jié)構(gòu)，主 中為移位寄存器送部分如下圖所示。圖，可實(shí)現(xiàn)直(位mov) 、左移一B，則 Bm(2<=m<=n)存取單位為16 位；采 用R0R3(left)非零元素的含義是什16 位定長(zhǎng)指令格式；為通用寄存器；、右移 (right 一位 )3T 為 暫 存 器 ；SR種操作，控制信號(hào)為rop,SR 的輸出信號(hào) Srout 控制； A 與 B(and) 、 A 或 B(or)A(mova) 、 A 加 或 B(or) 、非 A(no

14、t) 、 A 加 1(inc)7ALU 可實(shí)現(xiàn)直送B(add) 、 A 減 B(sub) 、 種操作，控制信號(hào)為 ALUop寫出圖 G 的鄰接矩陣 A( 行、列下標(biāo)從 0 開始 )求 A 2，矩陣 A 2 中位于 0 行 3 列元素值的含義是什么？請(qǐng)回答下列問題。(1)圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T？(2)控制信號(hào) ALUop 和 SRop 的位數(shù)至少各是多少？(3)控制信號(hào) Srout 所控制郵件的名稱或作用是什么？(4)端點(diǎn) 中，哪些端點(diǎn)須連接到控制部件的輸出端？(5) 寫出連線的起點(diǎn)和終點(diǎn)，以正確表示數(shù)據(jù)的流動(dòng)方向。為完善單總線數(shù)據(jù)通路，需要在端點(diǎn) 中相應(yīng)的端點(diǎn)之間添加

15、必要的連線。(6) 為什么二路選擇器 MUX 的一個(gè)輸入端是 2 ？4.10 分)題 43 中描述的計(jì)算機(jī)，其部分指令執(zhí)行過程的控制信號(hào)如如題44 圖 a所示。部分指令控制信號(hào)存器直接和寄存器間接兩種尋址方式，尋的編號(hào)分別為 0 、址方式位分別為 01、 2 和 3 。題 44 圖 b 指令格式請(qǐng)回答下列問題。(1) 該機(jī)的指令系統(tǒng)最多可定義多少條指令？(2) 假定 inc、shl 和 sub 指令的操作碼分別為 01H、 02H 和 03H，則以下指令對(duì)應(yīng)的機(jī)器代碼各是什么？ sub R3,(R1),R2; (R1) (R2) R3(3 假定寄存器X 的輸入和輸出控制信號(hào)分別 Xin和 Xo

16、ut ，其值為 1 表示有) 為效，為inc R1R1+1 R1shl R2,R1；存儲(chǔ)器控制信號(hào)為表示 PC 內(nèi)容送總線) 控制0 表示無效PCout=1MEMop ，用于; (R1) << 1 R2存儲(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è)

17、郵件， B 的信箱最多放 N 個(gè)郵件。 初始時(shí) A 的信箱中有 x 個(gè)郵件( 0<x<M ) . B 中有 y 個(gè)( 0<y<N ) 辯論者每取出一個(gè)郵件，郵件數(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

18、 (或 wait, signed )操作，以實(shí)現(xiàn)上述過程的同步，要求寫出完整過程，并說明信號(hào)量的含義和初值。2015 年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題答案解析、單項(xiàng)選擇題：1 40小題，每小題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)的是A main()->S(1)->

19、S(0)B S(0)->S(1)->main()D main()->S(0)->S(1)【 參 考 答 案 】DDS(1)->S(0)->main()B 24 ， 10 ， 5 和 24 ， 12 ， 7D 24 ， 10， 5 和 24 ， 14 ， 6（ AVL 樹） , 對(duì)其進(jìn)行中序遍歷可得到一 個(gè)降B樹中最小元素一定是葉節(jié)點(diǎn)D 樹中最大元素一定是無左子樹【考查知識(shí)點(diǎn) 】棧的基本概念和函數(shù)調(diào)用的原理。3 先序序列為 a,b,c,d 的不同二叉樹的個(gè)數(shù)是A13B14C15D 16【參考答案】 C【考查知識(shí)點(diǎn) 】二叉樹的基本概念。 3下列選項(xiàng)給出的是從根分

20、別到達(dá)兩個(gè)葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫 曼樹的是A 24 ， 10 ， 5 和 24 ，10， 7C24， 10 ， 10 和 24 ， 14 ， 11【參考答案】 C【考查知識(shí)點(diǎn) 】哈夫曼樹的原理。 4現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉 樹序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A 根節(jié)點(diǎn)的度一定為 2C最后插入的元素一定是葉節(jié)點(diǎn)參考答案】考查知識(shí)點(diǎn)】樹的中序遍歷和AVL 樹的基本概念5設(shè)有向圖<v 1,v3>,G=（V,E） ，頂點(diǎn)集V=V 0,V 1,V 2,V 3，邊集 E=<v 0,v1>,<v 0,v2>,<v 0,v3&g

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

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

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

24、入排序，再對(duì)全體元素進(jìn)行一次直接插入排序。硬件描述語言程序C僅D 【考查知識(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 -126B -125C -32D -3【參考答案】 B【考查知識(shí)點(diǎn)】 二進(jìn)制的補(bǔ)碼表示。 14下列有關(guān)浮點(diǎn)數(shù)加減運(yùn)算的敘述中，正確的是（） . 對(duì)階操作不會(huì)引起階碼上溢或下溢 . 右規(guī)和尾數(shù)舍入都可能引起階碼上溢 . 左規(guī)時(shí)可能引起階碼下溢 . 尾數(shù)溢出時(shí)結(jié)果不一定溢出A 僅 B僅C僅 D 【參考答案

25、】 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ù)至少是（）A 146kB147KC148KD 158K【參考答案】 B【考查知識(shí)點(diǎn)】 Cache 和主存的映射方式。直接映射方式地址映象規(guī)則： 主存儲(chǔ)器中 一塊只能映象 Cache 的一個(gè)特定的塊中。 （1） 主存與緩存分成相同大小的數(shù)據(jù) （2） 到 塊。主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等

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

27、 ）一次，如果考查知識(shí)點(diǎn) 】DRAM 使用電容存儲(chǔ)，所以必須隔一段時(shí)間刷新（存儲(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ì)是（）A 8004、8008D 8000、B 8002 、 8007 C 8001 、 8008 8004【參考答案】C【考查知識(shí)點(diǎn)】考察了存儲(chǔ)器中的多模塊存儲(chǔ)器，多體并行系統(tǒng)。19下列有關(guān)總線定時(shí)的敘述中，錯(cuò)誤的是（）A 異步通信方式中，全互鎖

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

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

30、容【 參 考 答 案 】A考查知識(shí)點(diǎn) 】外部中斷處理過程24假定下列指令已裝入指令寄存則執(zhí)行時(shí)不可能導(dǎo)致CPU 從用戶態(tài)變?yōu)閮?nèi)核 態(tài)(系統(tǒng)態(tài) ) 的是 ()A DIV R0 ， R1;（R0）/（R1） R0BINT n ；產(chǎn)生軟中斷CNOT R0 ；寄存器 R0 的內(nèi)容取非D MOV 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） 操作 行C啟動(dòng) I/ 設(shè)備O【參考答案】DB 申請(qǐng)內(nèi)存失敗D 被高優(yōu)先級(jí)進(jìn)程搶占26若系統(tǒng)S1 采用死鎖避免方法，

31、S2 采用死鎖檢測(cè)方法，下列敘述中正確的是（） S1會(huì)限制用戶申請(qǐng)資源的順序 S1 而需要進(jìn)行所需資源總量信息，S2 不需要 S1不會(huì)給可能導(dǎo)致死鎖的進(jìn)程分配資 S2 會(huì)源，A僅B僅C僅D 考查知識(shí)點(diǎn) 】進(jìn)程間各狀態(tài)的轉(zhuǎn)化參考答案】C考查知識(shí)點(diǎn) 】死鎖相關(guān)概念27系統(tǒng)為某進(jìn)程分配了4 個(gè)頁(yè)框，該進(jìn)程已訪問的頁(yè)號(hào)序列為2,0,2,9,3,4,2,8,2,3,8,4,5 ，若進(jìn)程要訪問的下一頁(yè)的頁(yè)號(hào)為7，依據(jù) LRU 算法，應(yīng)淘汰頁(yè)的頁(yè)號(hào)是（）A2B3【參考答案】 C【考查知識(shí)點(diǎn) 】 LRU 算法。C4D828在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是（）A 減少磁盤 I/O 次數(shù)B減少平均尋道時(shí)間C

32、提高磁盤數(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 。每個(gè)索引指針占 4 個(gè)字節(jié)。若某個(gè)文件的索引節(jié)點(diǎn)已在內(nèi)存中，到把該文件的偏移量 (按字節(jié)編址) 為 1234 和 307400 處所在的磁盤塊讀入內(nèi)存。 需訪問的磁盤塊個(gè)數(shù)分別是()A1，2B1， 3C2， 3D 2，4參考答案】考查知識(shí)點(diǎn)】文件索引相關(guān)概念。30C可變分配，全局置換固定分配，全局置換可變分配，局部置換固定分配，局部置換在請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)面分配策略與頁(yè)面置換策略不能組合使用的是參考答案】考查知識(shí)

33、點(diǎn)】頁(yè)面分配策略和頁(yè)面置換策略的概念和相應(yīng)的方法。二、綜合應(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) 說明所涉及算法

34、的時(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) 節(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)的絕對(duì)值的值是否出現(xiàn)過void DeleteABSEqualNode(Node * head)memset(a,0,n); / 初始化為 0if (head

35、= 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->next = p->next;delete p;p = r->next;else否則，將數(shù)組中對(duì)應(yīng)的元素置1，并將指針指向下一個(gè)元素aabs(p->data) = 1;r = p;return head;p = p->next;/(4) 只遍歷一次鏈表，所以時(shí)間復(fù)雜度為 O(n) ，因?yàn)樯暾?qǐng)大小為 n 的數(shù)組，所以

36、空間復(fù)雜度為O(n) ，( n 為節(jié)點(diǎn)絕對(duì)值的最大值)考查知識(shí)點(diǎn)】 鏈表的操作。42. 已知有 5 個(gè)頂點(diǎn)的圖 G 如下圖所示請(qǐng)回答下列問題(1) 寫出圖 G 的鄰接矩陣 A( 行、列下標(biāo)從 0 開始 )(2) 求 A 2，矩陣 A 2 中位于 0 行 3 列元素值的含義是什么？(3) 若已知具有 n(n>=2) 個(gè)頂點(diǎn)的鄰接矩陣為 B，則 B m(2<=m<=n) 非零元素的含義是什 么？【參考答案】(1) 鄰接矩陣為2)01 110 010 001 101 00 11 0A2= 212 12 10 01 11 00 13 01 2 22 1 10 1 21 0 12 1

37、00 3 列的元素的含義是頂0 到頂 3 的最短距離行 點(diǎn)點(diǎn)為( 3 ) B m 中非零元素的含義是：假設(shè)此頂點(diǎn)位于i 行 j頂點(diǎn)到2.列，如果i=j ，則表示 i自己的距離為 0；如果 i j ，則表示頂點(diǎn)i 到達(dá)不了頂點(diǎn) j【考查知識(shí)點(diǎn)】 鄰接矩陣的概念，最短路徑。存取單位為 16 位；采用 16 位定長(zhǎng)指令43. ( 13 分)某 16 位計(jì)算機(jī)主存按字節(jié)編碼。 格式；R0R3 為通用寄存器； T 為暫存器； SRCPU 采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中為移位寄存器，可實(shí)現(xiàn)直送為(mov) 、左移一位 (left) 、右移一位(right)3種操作，控制信號(hào)Srop,SR 的輸出

38、信號(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)須連接到控制部件的輸出端？為完善單總線數(shù)據(jù)通路，需要在端點(diǎn) 寫出連線的起點(diǎn)和終點(diǎn)，以正確表示數(shù)據(jù)的流動(dòng)方向(6) 為什么二路選擇器 MUX 的一個(gè)輸入端是(5

39、) 中相應(yīng)的端點(diǎn)之間添加必要的連線。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以獲取下一條指令地址。考查知識(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)分別為 01、 2 和 3題 44 圖 b 指令格式請(qǐng)回答下列問題。(1) 該機(jī)的指令系統(tǒng)最多可定義多少條指令？(2) 假定 inc、shl和 sub 指令的操作碼分別為01H 、 02H 和 03H，則以下指令對(duì)應(yīng)的機(jī)器代碼各是什么？ inc R1; R1+1 R1 shl R2,R1 sub R3,(R1)