2012年考研計算機統(tǒng)考真題及答案解析

1、絕密啟用前2012年全國碩士研究生入學統(tǒng)一考試計算機科學與技術(shù)學科聯(lián)考計算機學科專業(yè)基礎(chǔ)綜合（科目代碼：408）考生注意事項答題前，考生須在答題卡指定位置上填寫報考單位、考生姓名、科目名 稱和考生編號，并涂寫考試科目和考生編號的信息點；在答題紙指定位 置上填寫報考單位、考生姓名和考生編號。選擇題的答案必須涂寫在答題卡相應題號的選項上，非選擇題的答案必 須書寫在答題紙指定位置的邊框區(qū)域內(nèi)。寫在其他地方無效。填（書）寫部分必須使用藍（黑）色字跡鋼筆、圓珠筆或簽字筆，涂寫 部分必須使用2B鉛筆?？荚嚱Y(jié)束，將答題卡、答題紙和試題一并裝入試題袋中交回。一、單項選擇題：140小題，每小題2分，共80分。下

2、列每題給出的四個選項中，只 有一個選項是最符合題目要求的。請在等題卡上將所選項的字母涂黑。求整數(shù)階乘的算法如下，其時間復雜度是int fact( int n) if (nRd算術(shù)/邏輯左移SHL Rd2*(Rd)-Rd算術(shù)右移SHR Rd(Rd)/2Rd取數(shù)指令LOAD Rd, mem(mem)-* Rd存數(shù)指令STORE Rs, mem(Rs) f mem該計算機采用5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器 （ID）、執(zhí)行/計算有效地址（EX）、訪問存儲器（M）和結(jié)果寫回寄存器（WB）, 流水線采用“按序發(fā)射，按序完成”方式，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且 同一個

3、寄存器的讀寫操作不能在同一個時鐘周期內(nèi)進行。請回答下列問題。（1）若int型變量x的值為-513,存放在寄存器R1中，則執(zhí)行指令“SHRR1”后， R1的內(nèi)容是多少？（用十六進制表示）（2）若某個時間段中，有連續(xù)的4條指令進入流水線，在其執(zhí)行過程中沒有發(fā)生 任何阻塞，則執(zhí)行這4條指令所需的時鐘周期數(shù)為多少？（3）若高級語言程序中某賦值語句為x = a+b, x、a和b均為int型變量，它們的 存儲單元地址分別表示為x、a和b。該語句對應的指令序列及其在指令流 水線中的執(zhí)行過程如題44圖所示。IiLOADRl,aI2LOADR2, bI3ADDR1,R2I4STORER2, x時間單元指令123

4、4567891011121314IiIFIDEXMWBI2IFIDEXMWBI3IFIDEXMWBI4IFIDEXMWB題44圖指令序列及其執(zhí)行過程示意圖則這4條指令執(zhí)行過程中，13的ID段和I4的IF段被阻塞的原因各是什么？（4）若高級語言程序中某賦值語句為x = 2*x+a, x和a均為unsigned int類型變量, 它們的存儲單元地址分別表示為x、a,則執(zhí)行這條語句至少需要多少個時 鐘周期？要求模仿題44圖畫出這條語句對應的指令序列及其在流水線中的執(zhí) 行過程示意圖。計算機學科專業(yè)基礎(chǔ)綜合試題 第8頁（共10頁）（7分）某請求分頁系統(tǒng)的局部頁面置換策略如下:系統(tǒng)從0時刻開始掃描，每隔5

5、個時間單位掃描一輪駐留集（掃描時間忽略不計），本輪沒有被訪問過的頁框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容 在下一次被分配之前不被清空。當發(fā)生缺頁時，如果該頁曾被使用過且還在空閑頁 框鏈表中，則重新放回進程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。假設(shè)不考慮其它進程的影響和系統(tǒng)開銷，初始時進程駐留集為空。目前系統(tǒng)空閑頁 框鏈表中頁框號依次為32、15、21、41o進程P依次訪問的v虛擬頁號，訪問時刻 是：vl, 1、3,2、0, 4 0, 6 1,11 0,13、2, 14。請回答下列問題?！玖V（1）訪問04時，對應的頁框號是什么？（2）訪問vl,ll時，對應的頁框號是什么？

6、說明理由。（3）訪問2, 14時，對應的頁框號是什么？說明理由。（4）該策略是否適合于時間局部性好的程序？說明理由。（8分）某文件系統(tǒng)空間的最大容量為4 TB （1T= 240）,以磁盤塊為基本分配單位, 磁盤塊大小為1 KBo文件控制塊（FCB）包含一個512B的索引表區(qū)。請回答下列 問題。（1）假設(shè)索引表區(qū)僅釆用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤塊號。索 引表項中塊號最少占多少字節(jié)？可支持的單個文件最大長度是多少字節(jié)？（2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第07字節(jié)釆用v起始塊號，塊數(shù)格式表示 文件創(chuàng)建時預分配的連續(xù)存儲空間，其中起始塊號占6B,塊數(shù)占2B；剩余 504字節(jié)采用直接索引結(jié)構(gòu)

7、，一個索引項占6B,則可支持的單個文件最大長 度是多少字節(jié)？為了使單個文件的長度達到最大，請指出起始塊號和塊數(shù)分 別所占字節(jié)數(shù)的合理值并說明理由。(9分)主機H通過快速以太網(wǎng)連接Internet, IP地址為192.168.0.8,服務(wù)器S的IP 地址為211.68.71.80。H與S使用TCP通信時，在H上捕獲的其中5個IP分組如 題47-a表所示。題47-a表編號IP分組的前40字節(jié)內(nèi)容(十六進制)145 00 00 3001 9b 40 00 80 06 lde8 c0 a8 00 08d3 44 47 50Ob d9 13 8884 6b 41 c5 00 00 00 00 70 02

8、 43 805d bO 00 00245 00 00 30 00 00 40 0031 06 6e 83 d3 44 47 50cO a8 00 0813 88 Ob d9 eO 59 9fef84 6b 41 c6 70 12 16 dO37 el 00 00345 00 00 28 01 9c 40 0080 06 ldefcO a8 00 08d3 44 47 500b d9 13 88 84 6b 41 c6eO 59 9ff050 10 43 80 2b 32 00 00445 00 00 3801 9d40 00 80 06 Id de cO a8 00 08d3 44 47 50

9、0b d9 13 8884 6b 41 c6 eO 59 9ffl)50 18 43 80c6 55 00 00545 00 00 2868 11 40 00 31 06 06 7ad3 44 47 50 cO a8 00 0813 88 0b d9eO 59 9ff084 6b 41 d650 10 16 dO 57 d2 00 00請回答下列問題。題47a表中的IP分組中，哪幾個是由H發(fā)送的？哪幾個完成了 TCP連接建 立過程？哪幾個在通過快速以太網(wǎng)傳輸時進行了填充？根據(jù)題47a表中的IP分組，分析S已經(jīng)收到的應用層數(shù)據(jù)字節(jié)數(shù)是多少？若題47a表中的某個IP分組在S發(fā)出時的前40字節(jié)如題4

10、7-b表所示，則該 IP分組到達H時經(jīng)過了多少個路由器？題47-b表S發(fā)出的45 00 00 2868 11 40 0040 06 ec add3 44 47 50ca 76 01 06IP分組13 88 al 08eO 59 9ff084 6b 41 d650 10 16 dOb7 d6 00 00注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題47圖、題47b圖所示。比特 081624311 1 1 1 1 1 1 11 1 1 ! 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1-X-頭部 I 版本長度服務(wù)類型總長度標識標志片偏移生存時間(TTL)協(xié)議頭部校驗和源地址目的地址題

11、47a圖IP分組頭結(jié)構(gòu)比特 08162431源端口Illi11111目的端口序號(seq)確認號(ack)頭部W爻度保留劭 p Rs J:S S；Y IC HT|N h1窗口校驗和緊急指針題47-b圖TCP段頭結(jié)構(gòu)絕密啟用前2012年全國碩士研究生入學統(tǒng)一考試計算機科學與技術(shù)學科聯(lián)考計算機學科專業(yè)基礎(chǔ)綜合試題答案及評分參考、單項選擇題:每小題2分，共80分。1B2. A3. A4. B5. C6. C7C8. A9. D10. A11. D12 . D13. B14. D15. D16 . A17. C18. C19. C20. D21. D22. B23. C24. B25. B26. A2

12、7. D28. A29. B30. C31. A32. B33. B34. C35. A36. B37. C38. A39. D40. D二、綜合應用題：4147小題，共70分?！敬鸢敢c】（1）6個表的合并順序如下圖所示。對應于合并過程的哈夫曼樹根據(jù)上圖中的哈夫曼樹，6個序列的合并過程為：第1次合并：表A與表B合并，生成含45個元素的表AB；第2次合并：表AB與表C合并，生成含85個元素的表ABC；第3次合并：表D與表E合并，生成含110個元素的表DE；教育部考試屮心第4次合并：表ABC與表DE合并，生成含195個元素的表ABCDE；第5次合并：表ABCDE與表F合并，生成含395個元素的最

13、終表；（5分）由于合并兩個長度分別為m和n的有序表，最壞情況下需要比較m+nl次，故最 壞情況下比較的總次數(shù)計算如下：第1次合并：最多比較次數(shù)=10+35-1 =44第2次合并：最多比較次數(shù)=45+40-1 = 84第3次合并：最多比較次數(shù)-50+60-1 = 109第4次合并：最多比較次數(shù)=85+110-1 = 194第5次合并：最多比較次數(shù)=195+200-1 =394比較的總次數(shù)最多為：44+84+109+194+394 = 825 （2分）（2）各表的合并策略是：在對多個有序表進行兩兩合并時，若表長不同，則最壞 情況下總的比較次數(shù)依賴于表的合并次序?？梢越栌霉蚵鼧涞臉?gòu)造思想，依次選擇

14、最 短的兩個表進行合并，可以獲得最壞情況下最佳的合并效率。（3分）（1） （2）評分說明】對于用類似哈夫曼樹（或最佳歸并樹）思想進行合并，過程描述正確，給5分。 按其他策略進行合并，過程描述正確，給3分。正確算出與合并過程一致的總比較次數(shù)，給2分。若計算過程正確，但結(jié)果錯誤， 可給1分?？忌灰f明采用的是類似哈夫曼樹（或最佳歸并樹）的構(gòu)造方法作為合并策略. 即可給3分。如果采用其他策略，只要能夠完成合并，給2分。【答案要點】（1）給岀算法的基本設(shè)計思想：（4分）分別求出strl和str2所指的兩個鏈表的長度m和n；將兩個鏈表以表尾對齊：令指針p、g分別指向strl strl的頭結(jié)點，若加 =

15、小 則使p指向鏈表中的第m-n+ 1個結(jié)點；若m n ; m-) p = p-next;for ( q=str2; m next;while( p-next != NULL & p-next != qnext) /* 查找共同后綴起始點 */ p = p-next;/*兩個指針同步向后移動*/q = q-next;return p-next;int listlen( SNODE * head )/*返回共同后綴的起始點*/*求鏈表長度*/int len=O;while ( head-next != NULL )len -H-;head = head-next;return len;(1) (2

16、)的評分說明】若考生所給算法實現(xiàn)正確，且時間復雜度為O(加+力，可給12分；若算法正確， 但時間復雜度超過0(加+刃)，則最高可給9分。若在算法的基本設(shè)計思想描述中因文字表達沒有非常清晰反映岀算法思路，但在 算法實現(xiàn)中能夠清晰看出算法思想且正確的，可參照的標準給分。若算法的基本設(shè)計思想描述或算法實現(xiàn)中部分正確，可參照中各種情況的相應 給分標準酌情給分。參考答案中只給岀了使用C語言的版本，使用C+/Java語言的答案視同使用C 語言。敎育部芍試中心（3）說明算法的時間復雜度：（1分）參考答案的時間復雜度為：0伽+力或伽,刃）。其中加、n分別為兩個鏈 表的長度。（3）的評分說明】若考生所估計的時間

17、復雜度與考生所實現(xiàn)的算法一致，可給1分。【答案要點】（1）平均每秒CPU執(zhí)行的指令數(shù)為：80 M/4 = 20M,故MIPS數(shù)為20； （1分）平均每秒 Cache 缺失的次數(shù)為：20 MX 1.5 X （1 -99%）=300 000=300 k； （1 分）當Cache缺失時，CPU訪問主存，主存與Cache之間以塊為單位傳送數(shù)據(jù)，此時， 主存帶寬為：16BX300 k/s = 4.8MB/s。在不考慮DMA傳輸?shù)那闆r下，主存帶寬至少 達到4.8 MB/s才能滿足CPU的訪存要求。（2分）（2）平均每秒鐘“缺頁”異常次數(shù)為：300 000X0.0005%= 1.5次；（1分）因為存儲器總線

18、寬度為32位，所以，每傳送32位數(shù)據(jù)，磁盤控制器發(fā)岀一次DMA 請求，故平均每秒磁盤DMA請求的次數(shù)至少為：1.5X4 KB/4B= 1.5 K= 1536。（2分）（3）CPU和DMA控制器同時要求使用存儲器總線時，DMA請求優(yōu)先級更高；（1分） 因為，若DMA請求得不到及時響應，I/O傳輸數(shù)據(jù)可能會丟失。（1分）（4）4體交叉存儲模式能提供的最大帶寬為：4X4 B/50 ns = 320 MB/S。（2分）【答案要點】（1）x的機器碼為x補=1111 1101 1111 1111B,即指令執(zhí)行前（R1） = FDFFH,右移 1 位后為 1111 1110 1111 1111B,即指令執(zhí)行

19、后（R1） = FEFFHO （2 分）【評分說明】僅正確寫出指令執(zhí)行前的（R1）可給1分。（2）至少需要4+（5T）=亙個時鐘周期數(shù)。（2分）（3）h的ID段被阻塞的原因：因為13與h和【2都存在數(shù)據(jù)相關(guān)，需等到h和12將結(jié)果寫回寄存器后，【3才能讀寄存器內(nèi)容，所以【3的ID段被阻塞。（1分）【4的IF段被阻塞的原因：因為【4的前一條指令【3在ID 段被阻塞，所以1的IF段 一一、被阻塞。（1分）（4）因2*x操作有左移和加法兩種實現(xiàn)方法，故x = 2*x+a對應的指令序列為1) LOADRl,xI2 LOADR2, aI3 SHLR1或者 ADD R1,R1I4 ADDR1,R215 ST

20、ORER2, x【評分說明】指令正確給其他正確答案同樣給分；部分正確，酌情給分。 計算機學科專業(yè)基礎(chǔ)綜合試題答案及評分參考 第4頁（共&頁）這5條指令在流水線中的執(zhí)行過程如下圖所示。（3分）時!司單元指令I(lǐng)23456789101112131415161711IFIDEXMWB12IFIDEXMWBhIFIDEXMWBkIFIDEXMWBIsIFIDEXMWB故執(zhí)行x=2*x+a語句最少需要17個時鐘周期。（1分）【答案要點】（1）頁框號為21。（1分）因為起始駐留集為空，而0頁對應的頁框為空閑鏈表中的第三個空閑頁框（21）, 其左應的頁框號為21。（2）頁框號為32。（1分）理由：因1110故

21、發(fā)生第三輪掃描，頁號為1的頁框在第二輪已處于空閑頁框鏈表 中，此刻該頁又被重新訪問，因此應被重新放回到駐留集中。其頁框號為32。（1分）（3）頁框號為41。（1分）理由：因為第2頁從來沒有被訪問過，它不在駐留集中，因此從空閑頁框鏈表中取 出鏈表頭的頁框41,頁框號為41。（1分）（4）適合。（1分）理由池菓理序的時間局部性越好，從空閑頁框鏈表中重新取回的機會越大，該策 略的優(yōu)勢越明顯。（1分）【答案要點】（1）文件系統(tǒng)存儲空間共有塊數(shù)2* / 210二232o為表示2立個塊號，索引表項占 32/8=4 B。（2 分）512字節(jié)可存放，個索引表項，故最大文件長度：27x210=217 B=128

22、 KBo （2分） 【評分說明】過程描述正確，但計算結(jié)果不正確，可酌情給分。（2）塊號占6字節(jié)，塊數(shù)占2字節(jié)的情形下，最大文件長度：216x 2,0+（504/6）x 210 =64 MB+84 KB = 65620 KBo （2 分）合理的起始塊號和塊數(shù)所占字節(jié)數(shù)分別為4.4（或1、7或2,6或3,5）。（1分）理由： 塊數(shù)占4 B或以上，就可表示4 TB大小的文件長度，達到文件系統(tǒng)的空間上限。（1分）計算機學科專業(yè)基礎(chǔ)綜合試題答案及評分參考 第5頁（共6頁）教育部考試中心【評分說明】過程描述正確，但計算結(jié)果不正確，可酌情給分。只要答出起始塊號 和塊數(shù)所占字節(jié)數(shù)的任意合理值，均可得1分；理由說明正確得1分。【答案要點】由于題47a表中1、3、4號分組的源IP地址均為192.16