2017計(jì)算機(jī)考研真題

1、2017 計(jì)算機(jī)考研真題一、單項(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()c. main()->s(0)->s(1)d.s(1)->s(0)->main()2. 先序序列為 a,b,c,d 的不同二叉樹的個(gè)數(shù)是a.13b.14c.15d.163. 下列選項(xiàng)給

2、出的是從根分別到達(dá)兩個(gè)葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是a.24 ，10 ，5 和 24 ，10， 7b.24 ，10 ，5 和 24，12 ，7 c.24 ，10 ，10 和 24， 14，11d.24 ， 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)集 v=v0,v1,v2,v3，邊集 e=, ，,若從頂點(diǎn)

3、v0開始對(duì)圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個(gè)數(shù)是a.2b.3c.4d.56. 求下面帶權(quán)圖的最小 (代價(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)鍵字比較序列的是a.500 ，200 ， 450 ，180 b.500 ，450 ， 200 ，180 c.180 ，500 ， 200 ，450 d.180 ，200 ， 500 ，4508. 已知字符串 s 為“ abaabaabacaca

4、abaabcc ”模. 式串 t 為“ abaabc ”采, 用 kmp算法進(jìn)行匹配，第一次出現(xiàn)“失配”(si != ti) 時(shí)， i=j=5, 則下次開始匹配時(shí)， i 和j 的值分別是a.i=1 ， j=0b.i=5 ， j=0c.i=5 ，j=2d.i=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ù)是a.1b.2c.3d.411. 希爾排序的組內(nèi)排序采用的是()a. 直接插入

5、排序b.折半插入排序c . 快速排序d.歸并排序12. 計(jì)算機(jī)硬件能夠直接執(zhí)行的是().機(jī)器語言程序.匯編語言程序.硬件描述語言程序a. 僅b.僅 c.僅 d. 13. 由 3 個(gè)“ 1和”5 個(gè)“ 0組”成的 8 位二進(jìn)制補(bǔ)碼，能表示的最小整數(shù)是() a.-126b.-125c.-32d.-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 之間采用直接映射方式， 主存塊大

6、小為 4 個(gè)字，每字 32 位，采用回寫 (write back) 方式，則能存放 4k 字?jǐn)?shù)據(jù)的 cache 的總?cè)萘康奈粩?shù)至少是 ()a.146kb.147kc.148kd.158k16. 假定編譯器將賦值語句 “ x=x+3;轉(zhuǎn)”換為指令 ” add xaddt, 3，其”中 xaddt 是x 對(duì)應(yīng)的存儲(chǔ)單元地址， 若執(zhí)行該指令的計(jì)算機(jī)采用頁(yè)式虛擬存儲(chǔ)管理方式，并配有相應(yīng)的 tlb，且 cache 使用直寫 (write through) 方式，則完成該指令功能需要訪問主存的次數(shù)至少是 ()a.0b.1c.2d.317. 下列存儲(chǔ)器中，在工作期間需要周期性刷新的是()a.sramb.sd

7、ramc.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 、8008b.8002 、8007c.8001 、8008 d.8000 、800419. 下列有關(guān)總線定時(shí)的敘述中，錯(cuò)誤的是()a. 異步通信方式中，全互鎖協(xié)議最慢b. 異步通信方式中，非互鎖協(xié)議的可靠性最差c. 同步通信方式中，同步時(shí)鐘信號(hào)可由多設(shè)備提供d. 半同步通信方式中，握手信號(hào)的采樣由同步時(shí)鐘控制20.

8、 若磁盤轉(zhuǎn)速為 7200 轉(zhuǎn)/分，平均尋道時(shí)間為 8ms, 每個(gè)磁道包含 1000 個(gè)扇區(qū)， 則訪問一個(gè)扇區(qū)的平均存取時(shí)間大約是( )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)部異常的敘述中，錯(cuò)誤的( )a. 內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)b. 內(nèi)部異常的檢測(cè)由cpu 內(nèi)部邏輯實(shí)現(xiàn)c. 內(nèi)部

9、異常的響應(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))的是( )a.div r0 ，r1;(r0)/(r1) r0b.int n; 產(chǎn)生軟中斷c.not r0; 寄存器 r0 的內(nèi)容取非d.mov 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

10、(wait) 操作b.申請(qǐng)內(nèi)存失敗c. 啟動(dòng) i/o 設(shè)備d.被高優(yōu)先級(jí)進(jìn)程搶占26. 若系統(tǒng) s1采用死鎖避免方法， s2 采用死鎖檢測(cè)方法，下列敘述中正確的是().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è)頁(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)是 ()a.2b.3c.4d.828. 在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是()a.

11、減少磁盤 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ù)分別是()a.1 ， 2b.1 ， 3c.2 ，3d.2 ， 430. 在請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)面分配策略與頁(yè)面置換策略不能組合使用的是()a. 可變分配，全局置換b.可變分配，局部置換c. 固定分配，全局置換d. 固定分配，局部置換二、綜合應(yīng)用題

12、： 4147 小題，共 70 分。41. 用單鏈表保存 m 個(gè)整數(shù)，節(jié)點(diǎn)的結(jié)構(gòu)為(data,link) ，且|data|例如若給定的單鏈表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 如下圖所示請(qǐng)回答下列問題：(1) 寫出圖 g 的鄰接矩陣 a(行、列下標(biāo)從0 開始)(2) 求 a2 ，矩陣 a2 中位于 0 行 3 列元素值的含義是什么 ?(3) 若

13、已知具有 n(n>=2) 個(gè)頂點(diǎn)的鄰接矩陣為b，則 bm(2<=m<=n) 非零元素的含義是什么 ?43. (13 分)某 16 位計(jì)算機(jī)主存按字節(jié)編碼。 存取單位為 16 位;采用 16 位定長(zhǎng)指令格式;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)直送a(mova) 、a 加 b(add) 、a 減 b(sub) 、a 與 b(and) 、a 或 b(or)

14、、非 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?45.有 a、b 兩人通過信箱進(jìn)行辯論，每人都從自己的信箱中取得對(duì)方的問題。將答案和向?qū)Ψ教岢龅男聠栴}組成一個(gè)郵件放入對(duì)方的郵箱中，設(shè)a 的信箱最多放 m 個(gè)郵件， b 的信箱最多放n 個(gè)郵件。初始時(shí) a 的信箱中有 x 個(gè)郵件 (0 a、b 兩人操作過程：code begin awhile(true)從