2017計算機考研真題

1、2017計算機考研真題一、單項選擇題1 已知程序如下：int s(i nt n)return (nS(1)-S(0) B.S(0)-S(1)-mai n()C. ma in ()-S(0)-S(1)D.S(1)-S(0)-mai n()2先序序列為a,b,c,d的不同二叉樹的個數(shù)是A. 133. 下列選項給出的是從根分別到達兩個葉節(jié)點路徑上的權(quán)值序列，能屬于同一棵 哈夫曼樹的是A. 24，10，5 和 24，10，7 B.24，10，5 和24，12，7C.24，10，10 和 24，14，11D.24，10，5 和 24，14，64. 現(xiàn)在有一顆無重復(fù)尖鍵字的平衡二叉樹(AVL樹),對其進行

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

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

4、4,16 ,12，刪除尖鍵字8之后需重建堆，在此 過程中，尖鍵字之間的比較數(shù)是A.1B.2C.3D.411希爾排序的組內(nèi)排序采用的是（）A.直接插入排序B.折半插入排序C 快速排序D.歸并排序12計算機硬件能夠直接執(zhí)行的是（）I 機器語言程序n 匯編語言程序川硬件描述語言程序A.僅 I B.僅 I n C.僅 I d. in m13由3個“和5個“組成的8位二進制補碼，能表示的最小整數(shù)是（）A.-126B.-125C.-32D.-314. 下列有尖浮點數(shù)加減運算的敘述中，正確的是（）1.對階操作不會引起階碼上溢或下溢n 右規(guī)和尾數(shù)舍入都可能引起階碼上溢m.左規(guī)時可能引起階碼下溢IV 尾數(shù)溢出時

5、結(jié)果不一定溢出A.僅 n mB.僅 InvC.僅 Im V d. In m V15. 假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主 存塊大小為4個字，每字32位，采用回寫（Write Back）方式，則能存放4K字數(shù) 據(jù)的Cache的總?cè)萘康奈粩?shù)至少是（）A.146kB.147KC.148KD.158K16. 假定編譯器將賦值語句“x=x+3轉(zhuǎn)換為指令” add xaddt, 3,其中xaddt是x對 應(yīng)的存儲單元地址，若執(zhí)行該指令的計算機采用頁式虛擬存儲管理方式， 并配有 相應(yīng)的TLB，且Cache使用直寫（Write Through）方式，則完成該指令功能需要

6、訪 問主存的次數(shù)至少是（）A.OB.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-下列有尖總線定時的敘述中，錯誤的是()A. 異步通信方式中，全互鎖協(xié)議最慢B. 異步通信方式中，非互鎖協(xié)議的可

7、靠性最差C. 同步通信方式中，同步時鐘信號可由多設(shè)備提供D. 半同步通信方式中，握手信號的采樣由同步時鐘控制20.若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時間為8ms,每個磁道包含1000個扇區(qū)， 則訪問一個扇區(qū)的平均存取時間大約是()21在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口 之間交換的信息不可能是()A.打印字符B.主存地址C.設(shè)備狀態(tài)D.控制命令22. 內(nèi)部異常(內(nèi)中斷)可分為故障(fault)、陷阱(trap)和終止(abort)三類。下列有尖內(nèi) 部異常的敘述中，錯誤的()A. 內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相尖B. 內(nèi)部異常的檢測由CPU內(nèi)部邏輯實現(xiàn)C

8、. 內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中D. 內(nèi)部異常處理的返回到發(fā)生異常的指令繼續(xù)執(zhí)行23. 處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是 0A.程序計數(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))的是()A. DIV RO ， R1;(R0)/(R1) - ROB. INTn;產(chǎn)生軟中斷C. NOT R0;寄存器R0的內(nèi)容取非D. MOV RO,addr;把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中25. 下列選項中會導(dǎo)致進程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是()A.執(zhí)行P(wait臊作B

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

10、. 減少平均尋道時間C. 提高磁盤數(shù)據(jù)可靠性D. 實現(xiàn)設(shè)備無尖性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.可變分配，全局置換B.可變分配，局部置換C.固定分配，全局置換D.固定分配，局部置換二、綜合應(yīng)用題：4147小題，共70分。41用單鏈表保存m個整數(shù)，節(jié)點的

11、結(jié)構(gòu)為（datajink），且|data|例如若給定的單鏈表head如下11KAI|1 7）刪除節(jié)點后的head為要求：（1）給出算法的基本思想（2）使用c或C+語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義（3）根據(jù)設(shè)計思想，采用c或C+語言描述算法，尖鍵之處給出注釋(4) 說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。42.已知有5個頂點的圖G如下圖所示請回答下列問題：(1)寫出圖G的鄰接矩陣A(行、列下標從0幵始)求A2，矩陣A2中位于0行3列元素值的含義是什么？若已知具有n(nx2)個頂點的鄰接矩陣為B,則Bm(2=m=n)非零元素的含 義是什 么？43. (13分)某16位計算機主存按字節(jié)編碼。存取單

12、位為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 與 B(and)、A 或 B(or)、非 A(not)、A加1(inc)7種操作，控制信號為ALUop(1)圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T? 控制信號ALUop和SRop的位數(shù)至少各是多少？(3)控制信號Srout所控制郵件的名稱或作用是什么？端點中，哪些端點須連接到控制部件的輸出端？(5) 為完善單總線數(shù)據(jù)通路，需要在端點中相應(yīng)的端點之間添加必要的連 線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。 為什么二路選擇器MUX的一個輸入端是2?45有A、B兩人通過信箱進行辯論，每人都從自己的信箱中取得對方的問題。將 答案和向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的郵箱中，設(shè) A的信箱最 多放M個郵件，B的信箱最多放N個郵件。初始時A的信箱中有x個郵件(0 A、B 兩人操作過程：Code Begi nAWhile(TRUE)從A的信箱中取出一個郵件