(好)2010計(jì)算機(jī)考研真題及答案報(bào)告

1、12010 年全國研究生考試計(jì)算機(jī)統(tǒng)考試題及答案一、單選題1、若元素 a,b,c,d,e,f 依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次 進(jìn)行退棧工作，則不可能得到的出棧序列是（D ）A： dcebfa B： cbdaef C: dbcaef D： afedcb2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作， 但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是（C）A： bacde B： dbace C： dbcae D： ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是4、在下列所示的平衡二叉樹中插入關(guān)鍵字 48 后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字 37

2、所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ C）2A： 13，48 B： 24，48 C： 24，53 D： 24，9035、 在一棵度為 4 的樹 T 中，若有 20 個(gè)度為 4 的結(jié)點(diǎn)，10 個(gè)度為 3 的結(jié)點(diǎn)，1 個(gè)度 為 2的結(jié)點(diǎn)， 10 個(gè)度為 1 的結(jié)點(diǎn)，則樹 T 的葉節(jié)點(diǎn)個(gè)數(shù)是（ B）A：41B： 82C： 113D： 1226、 對(duì) n（n 大于等于 2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹， 關(guān)于該樹的敘述中， 錯(cuò)誤的是（ B）A:該樹一定是一棵完全二叉樹B:樹中一定沒有度為 1 的結(jié)點(diǎn)C:樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D :樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的

3、權(quán)值7、 若無向圖 G-（VE）中含 7 個(gè)頂點(diǎn)，則保證圖 G 在任何情況下都是連通的，則需 要的邊數(shù)最少是（ A）A : 6B： 15C： 16 D： 218、 對(duì)下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是（B ）A: 4B: 3C: 2 D: 19、 已知一個(gè)長度為 16 的順序表 L,其元素按關(guān)鍵字有序排列，若采用折半查找法 查找一個(gè)不存在的元素，則比較次數(shù)最多是（ A）A: 4B: 5C: 6 D: 710、采用遞歸方式對(duì)順序表進(jìn)行快速排序,下列關(guān)于遞歸次數(shù)的敘述中,正確的是（ D）A:遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B:每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C:每次劃分后

4、，先處理較短的分區(qū)可以減少遞歸次數(shù)D:遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)11、對(duì)一組數(shù)據(jù)（ 2， 12， 16， 88， 5， 10）進(jìn)行排序，若前三趟排序結(jié)果如下（ A） 第一趟: 2， 12， 16， 5， 10， 88第二趟: 2， 12， 5， 10， 16， 88 第三趟: 2， 5， 10， 12， 16， 88 則采用的排序方法可能是:A:起泡排序 B:希爾排序 C:歸并排序 D:基數(shù)排序12、 下列選項(xiàng)中，能縮短程序執(zhí)行時(shí)間的措施是( D)4I 提高 CPU 時(shí)鐘頻率， II 優(yōu)化數(shù)據(jù)通過結(jié)構(gòu)， III 對(duì)程序進(jìn)行編譯優(yōu)化A:僅 I 和 II B:僅 I 和 III C

5、:僅 II 和 III D: 1,11 , III13、 假定有 4 個(gè)整數(shù)用 8 位補(bǔ)碼分別表示 r1=FEH ,r2=F2H ,r3=90H,r4=F8H, 若將 運(yùn)算結(jié)果存放在一個(gè) 8 位的寄存器中,則下列運(yùn)算會(huì)發(fā)生溢出的是( C)A: r1*r2 B : r2*r3C: r1*r4 D: r2*r414、 假定變量 I,f,d 數(shù)據(jù)類型分別為 int,float 和 double(int 用補(bǔ)碼表示, float 和 double 分別用 IEEE754 單精度和雙精度浮點(diǎn)數(shù)據(jù)格式表示 ),已知 i=785,f=1.5678,d=1.5 若在 32 位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式,則結(jié)果為

6、真是( C)(I)f=(int)(float)I (II)f=(float)(int)f (III)f=(float)(double) (IV)=(d+f)-d=fA:僅 I 和 II B:僅 I 和 IIIC:僅 II 和 III D:僅 III 和 IV15、 假定用若干個(gè) 2k*4 位芯片組成一個(gè) 8*8 位存儲(chǔ)器,則地址 0B1FH 所在芯片的 最小地址是( D )A: 0000HB: 0600HC: 0700HD: 0800H16、 下列有關(guān) RAM 和 ROM 的敘述中，正確的是(A)I 、 RAM 是易失性存儲(chǔ)器, ROM 是非易失性存儲(chǔ)器II、 RAM 和 ROM 都是采用隨機(jī)

7、存取的方式進(jìn)行信息訪問III、 RAM 和 ROM 都可用作 CacheIV、 RAM 和 ROM 都需要進(jìn)行刷新A:僅 I 和 II B:僅 II 和 III C:僅 I,II，III D:僅 II，III，IV1 7 、下列命令組合情況中，一次訪存過程中，不可能發(fā)生的是( D)A： TLB 未命中，Cache 未命中，Page 未命中B： TLB 未命中，Cache 命中，Page 命中C: TLB 命中，Cache 未命中，Page 命中D: TLB 命中，Cache 命中，Page 未命中18、下列存儲(chǔ)器中,匯編語言程序員可見的是( B)5A:存儲(chǔ)器地址寄存器（MAR）B:程序計(jì)數(shù)器（

8、PC）C:存儲(chǔ)器數(shù)據(jù)寄存器（MDR）D:指令寄存器（IR）19、 下列不會(huì)引起指令流水阻塞的是（ A）A:數(shù)據(jù)旁路B:數(shù)據(jù)相關(guān)C:條件轉(zhuǎn)移D:資源沖突20、 下列選項(xiàng)中的英文縮寫均為總線標(biāo)準(zhǔn)的是（ D）A: PCI、CRT、USB、EISAB: ISA、CPI、VESA、EISAC: ISA、SCSI、RAM、MIPSD: ISA、EISA、PCI、PCI-Express21、 單級(jí)中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（ A）I、保護(hù)現(xiàn)場 II、開中斷 III、關(guān)中斷 IV、保存斷點(diǎn)V、中斷事件處理 VI、恢復(fù)現(xiàn)場 VII、中斷返回A: I 、 V、 VI、 II 、 VIIB: III 、 I

9、 、 V、 VIIC: III 、 IV、 V、 VI、 VIID: IV、 I 、 V、 VI、 VII22、 假定一臺(tái)計(jì)算機(jī)的顯示存儲(chǔ)器用 DRAM 芯片實(shí)現(xiàn)，若要求顯示分辨率為1600*1200，顏色深度為 24 位，幀頻為 85Hz，顯示總帶寬的 50%用來刷新屏幕, 則需要的顯存總帶寬至少約為（ D）A : 245 MbpsB: 979 MbpsC: 1958 MbpsD: 7834Mbps23、 下列選項(xiàng)中，操作 S 提供的給應(yīng)用程序的接口是（A）A:系統(tǒng)調(diào)用B:中斷C:庫函數(shù)D :原語24、 下列選項(xiàng)中，導(dǎo)致創(chuàng)進(jìn)新進(jìn)程的操作是（ C）I 用戶成功登陸 II 設(shè)備分配 III 啟動(dòng)

10、程序執(zhí)行A:僅 I 和 IIB:僅 II 和 IIIC:僅 I 和 IIID: I，II，III25、 設(shè)與某資源相關(guān)聯(lián)的信號(hào)量初值為 3，當(dāng)前值為 1 ，若 M 表示該資源的可用個(gè) 數(shù)，N 表示等待資源的進(jìn)程數(shù)，則 M,N 分別是（ B ）A: 0， 1B: 1 ， 0C: 1 ， 2 D: 2， 0626、下列選項(xiàng)中，降低進(jìn)程優(yōu)先權(quán)級(jí)的合理時(shí)機(jī)是（ A ）A:進(jìn)程的時(shí)間片用完B:進(jìn)程剛完成 Z/0，進(jìn)入就緒隊(duì)列C:進(jìn)程長期處于就緒隊(duì)列中D:就緒從就緒狀態(tài)轉(zhuǎn)為運(yùn)行態(tài)27、進(jìn)行 P0 和 P1 的共享變量定義及其初值為（A）boolean flag2 ；int turn=0 ；flag0=fa

11、ulse ；flag 1 =faulse ；若進(jìn)行 P0 和 P1 訪問臨界資源的類 C 代碼實(shí)現(xiàn)如下：Void p0() / 進(jìn)程 p0Void p1 () / 進(jìn)程 p1while ( TURE) while ( TURE) Flag0=TURE;ture=1Flag1=TURE; ture=1While ( flag1&( turn=1 )While ( flag0& ( turn=0 )臨界區(qū):Flag0=FALSE;Flag1=FALSE;則并發(fā)執(zhí)行進(jìn)程 P0 和 P1 時(shí)產(chǎn)生的情況是:A：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會(huì)出現(xiàn) 饑餓”現(xiàn)象B:不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，

12、不會(huì)出現(xiàn) 饑餓”現(xiàn)象C：能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會(huì)出現(xiàn) 饑餓”現(xiàn)象D:能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會(huì)出現(xiàn) 饑餓”現(xiàn)象28、某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存容量為55mb （初試為空間），采用最佳適配（Best fit）算法，分配和釋放的順序?yàn)椋悍峙?15mb，分配 30mb，釋放 15mb，分配 8mb，此時(shí)主存中最大空閑分區(qū)的大小是（B）A: 7mbB: 9mbC: 10mbD: 15mb29、某計(jì)算機(jī)采用二級(jí)頁表的分頁存儲(chǔ)管理方式， 按字節(jié)編制， 頁大小為 216 字節(jié)， 頁表項(xiàng)大小為 2 字節(jié)，邏輯地址結(jié)構(gòu)為頁目編號(hào)頁號(hào)頁內(nèi)偏移量7邏輯地址空間大小為 216 頁，則表示整個(gè)邏輯地

13、址空間的頁目錄表中包含表項(xiàng)的個(gè) 數(shù)至少是（B）A: 64B: 128C: 256D: 51230、 設(shè)文件索引節(jié)點(diǎn)中有 7 個(gè)地址項(xiàng)，其中 4 個(gè)地址項(xiàng)為直接地址索引，2 個(gè)地址 項(xiàng)是一級(jí)間接地址索引，1 個(gè)地址項(xiàng)是二級(jí)間接地址索引，每個(gè)地址項(xiàng)大小為4 字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256 字節(jié)，則可表示的單個(gè)文件的最大長度是（C）A： 33kbB： 519kbC： 1057kbD： 16513kb31、 設(shè)置當(dāng)前工作目錄的主要目的是（C）A:節(jié)省外存空間B:節(jié)省內(nèi)容空間C:加快文件的檢索速度D:加快文件的讀寫速度32、 本地用戶通過鍵盤登錄系統(tǒng)時(shí)，首先獲得鍵盤輸入信息的程序是（B）A

14、:命令解釋程序B:中斷處理程序C:系統(tǒng)調(diào)用程序D:用戶登錄程序33、 下列選項(xiàng)中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是（C）A:網(wǎng)絡(luò)的層次B:每一層使用的協(xié)議C:協(xié)議的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)D:每一層必須完成的功能34、在下圖所示的采用 存儲(chǔ)-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中，所有鏈路的數(shù)據(jù)傳輸速 度為100mbps，分組大小為 1000B,其中分組頭大小 20B，若主機(jī) H1 向主機(jī) H2 發(fā)送一個(gè)大小為 980000B 的文件，則在不考慮分組拆裝時(shí)間和傳播延遲的情況下，從 H1 發(fā)送到 H2 接收完為止，需要的時(shí)間至少是（ A）A: 80msB: 80.08msC: 80.16msD: 80.24ms 35

15、、某自治系統(tǒng)采用 RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器 R1 收到其鄰居路由器 R2 的距離矢量中包含信息vnet1 ,16 ，則可能得出的結(jié)論是（A ）A: R2 可以經(jīng)過 R1 到達(dá) netl，跳數(shù)為 17B: R2 可以到達(dá) netl，跳數(shù)為 168C: R1 可以經(jīng)過 R2 到達(dá) netl，跳數(shù)為 17D: R1 不能進(jìn)過 R2 到達(dá) net136、若路由器 R 因?yàn)閾砣麃G棄 IP 分組，貝V此時(shí) R 可以向發(fā)出該 IP 分組的源主機(jī)發(fā) 送的 ICMP 報(bào)文件類型是（ C ）A:路由重定向B:目的不可達(dá)C:源抑制D:超時(shí)37、某網(wǎng)絡(luò)的 IP 地址為 192.168.5.0/24 采用長子

16、網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248 ，貝該網(wǎng)絡(luò)的最大子網(wǎng)個(gè)數(shù)，每個(gè)子網(wǎng)內(nèi)的最大可分配地址個(gè)數(shù)為（B ）A: 32， 8B: 32， 6C: 8， 32D: 8， 3038、 下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風(fēng)暴的是（C ）I中繼器U集線器 川網(wǎng)橋W路由器A:僅I和UB:僅川C:僅川和WD:僅W39、主機(jī)甲和主機(jī)乙之間已建立一個(gè) TCP 連接，TCP 最大段長度為 1000 字節(jié)，若 主機(jī)甲的當(dāng)前擁塞窗口為 4000 字節(jié)，在主機(jī)甲向主機(jī)乙連接發(fā)送 2 個(gè)最大段后， 成 功收到主機(jī)乙發(fā)送的第一段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為 2000 字節(jié)， 貝此時(shí)主機(jī)甲還可以向主機(jī)乙發(fā)送的最

17、大字節(jié)數(shù)是（ A ）A: 1000B: 2000C: 3000D: 400040、如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域名時(shí)，用戶 主機(jī)本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為（ A ）A: 1 條， 1 條B: 1 條，多條C:多條，1 條D:多條，多條二、綜合應(yīng)用題: 41-47 小題，共計(jì) 70 分41. (10 分)將關(guān)鍵字序列( 7、8、11 、18、9、14 )散列存儲(chǔ)到散列列表中，散列 表的存儲(chǔ)空間是一個(gè)下標(biāo)從 0 開始的一個(gè)一維數(shù)組散列函數(shù)維：H (key) = (keyX3) MODT,處理沖突采用線性探測再散列法，要求裝填(載)因子為 0.7問題：( 1)

18、請畫出所構(gòu)造的散列表；9(2)分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長度。解答：(1) 由裝載因子 0.7，數(shù)據(jù)總數(shù) 7 個(gè)-存儲(chǔ)空間長度為10-P=10所以， 構(gòu)造的散列表為：01234567893071411818. 9 .H(7)=(7X3)MOD10=1( 2)查找成功的 ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的 ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.242. (13 分)設(shè)將 n(n,1)個(gè)整數(shù)存放到一維數(shù)組 R 中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩 方面盡可能有效的算法，將 R 中保有的序列循環(huán)左移 P (0 Pn)個(gè)位置，即將

19、R 中的數(shù)據(jù)由(X0X1Xn1)變換為(Xp Xp+1X&1 X0 X1Xp1)要求：(1 )給出算法的基本設(shè)計(jì)思想。(2) 根據(jù)設(shè)計(jì)思想，采用 C 或 C+或 JAVA 語言表述算法，關(guān)鍵之處給出注釋。( 3 )說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度解答：(1 )前 P 個(gè)數(shù)依次進(jìn)隊(duì)，while (1 n-p ) Ai-i+p: p 個(gè)數(shù)依次出對(duì)，進(jìn)入數(shù)組末尾( 2 )詳細(xì)程序略(3) 時(shí)間復(fù)雜度 O (N);空間復(fù)雜度 o(p)43. （11 分）某計(jì)算機(jī)字長為 16q 位，主存地址空間大小為 128KB,按字編址，采用字 長指令格式，指令名字段定義如下：12轉(zhuǎn)移指令采用相對(duì)尋址

20、方式，相對(duì)偏移是用補(bǔ)碼表示，尋址方式定義如下:10Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=(Rn)001B寄存器間接(Rn)操作數(shù)=(R n)010B寄存器間接、自增(Rn) +操作數(shù)=(Rn), (Rn) +1 Rn011B相對(duì)D (Rn)轉(zhuǎn)移目標(biāo)地址二（PC） + （Rn）注:（X）表示有儲(chǔ)蓄地址 X 或寄存器 X 的內(nèi)容，請回答下列問題：（1） 該指令系統(tǒng)最多可有多少條指令？該計(jì)算機(jī)最多有多少個(gè)通用寄存器？存儲(chǔ)器地址寄存器（MDR）至少各需多少位？（2） 轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？（3 ）若操作碼 0010B 表示加法操作（助記符為 a d d），寄存器 R4 和

21、R5 的編號(hào)分另 I為 100B 禾口 101B，R4 的內(nèi)容為 1 2 3 4 H，R5 的內(nèi)容為 5 6 7 8 H，地址 1 2 3 4 H中的內(nèi)容為 5 6 7 8 H 中的內(nèi)容為 1 2 3 4 H，則匯編語言為 a d d （R4） . （ R5） +（逗號(hào)前原操作數(shù)， 都號(hào)后為目的操作數(shù)）對(duì)應(yīng)的機(jī)器碼是什么（用十六進(jìn)制表示） ？ 該指令執(zhí)行后，哪些寄存器和存儲(chǔ)單元的內(nèi)容會(huì)改變？改變后的內(nèi)容是什么？11解答: 該題的考點(diǎn)是指令系統(tǒng)設(shè)計(jì)， 注意操作位數(shù)與指令條數(shù)的關(guān)系， 地址碼與寄存器數(shù) 的關(guān)系，指令字長與 MOR 的關(guān)系，存儲(chǔ)容量與 MAR 的關(guān)系，注意補(bǔ)碼計(jì)算的偏移 地址。44.

22、 （ 12 分）某計(jì)算機(jī)的主存地址空間為 256MB，按字節(jié)編址，指令 Cache 分離均 有8 個(gè) Cache 行，每個(gè) Cache 行的大小為 64MB，數(shù)據(jù) Cache 采用直接映射方式， 現(xiàn)有兩個(gè)功能相同的程序 A 和 B,其偽代碼如下所示：假定 int 類型數(shù)據(jù)用 32 位補(bǔ)碼表示，程序編譯時(shí) i,j, sum 均分配在寄存器中，數(shù)據(jù) a 按行優(yōu)先方式存放，其地址為 320 （十進(jìn)制數(shù)），請回答下列問題，要求說明理由 或給出計(jì)算過程。（1 ）、若不考慮用于 cache 一致性維護(hù)和替換算法的控制位，則數(shù)據(jù) Cache 的總?cè)萘渴嵌嗌?（2）、要組元素 a031和 a11各自所在的主存

23、塊對(duì)應(yīng)的 Cache 行號(hào)分別是多少（Cache 行號(hào)從 0 開始）？程序Ai Inta25635I n I s um.ary 1 () ftnl ijum= 0, forCi=0Pi25fi;l+)forfl0 ;j 2：5 fcj + +)Sum+-aUnj;Return sum,程序B:Int a 2 5 6 2 56I n ts um.y2()(int ij um= 0, Xor(j = 0+nr(i-0；i2 5 6;i+)Return sum;12（3）、程序 A 和 B 的數(shù)據(jù)訪問命令中各是多少？那個(gè)程序的執(zhí)行時(shí)間更短?簡答：考點(diǎn)：Cache 容量計(jì)算，直接映射方式的地址計(jì)算，以

24、及命中率計(jì)算（行優(yōu) 先遍歷與列優(yōu)先遍歷命中率分別很大）45、（ 7 分）假設(shè)計(jì)算機(jī)系統(tǒng)采用 CSCAN（循環(huán)掃描）磁盤調(diào)度策略，使用 2KB 的 內(nèi)存空間記錄 16384 個(gè)磁盤塊的空間狀態(tài)（1） 、請說明在上述條件下如何進(jìn)行磁盤塊空閑狀態(tài)管理。（2） 、設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘 6000 轉(zhuǎn)。每個(gè)磁道有 100 個(gè)扇區(qū)，相臨磁 道間的平均移動(dòng)時(shí)間為 1ms.若在某時(shí)刻，磁頭位于 100 號(hào)磁道處，并沿著磁道號(hào)大的方向移動(dòng)（如下圖所示）磁道號(hào)請求隊(duì)列為 50.90.30.120.對(duì)請求隊(duì)列中的每個(gè)磁道需讀取 1 個(gè)隨機(jī)分布的扇 區(qū)，則讀完這個(gè)扇區(qū)點(diǎn)共需要多少時(shí)間？要求給出計(jì)算過程。130號(hào)

25、磁道磁頭運(yùn)動(dòng)方向100號(hào)磁.道隨機(jī)分布的某扇區(qū)1446. （8 分）設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為 64KB.按字節(jié)編址。若 某進(jìn)程最多需要 6 頁（Page）數(shù)據(jù)存儲(chǔ)空間，頁的大小為 1KB.操作系統(tǒng)采用固定分 配局部置換策略為此進(jìn)程分配 4 個(gè)頁框（Page Fame）.當(dāng)該進(jìn)程執(zhí)行到時(shí)刻 260 時(shí)，要訪問邏輯地址為 仃 CAH 的數(shù)據(jù)，請問答下列問題:（1）、該邏輯地址對(duì)應(yīng)的頁號(hào)是多少?（2）、若采用先進(jìn)先出（FIFO）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要 求給出計(jì)算過程。（3）、若采用時(shí)鐘（CLOCK）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過程。（設(shè)搜索下一頁的指針沿順時(shí)針方向移動(dòng)， 且當(dāng)前指向 2