(好)2010計算機考研真題及答案報告

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

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

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

4、，先處理較短的分區(qū)可以減少遞歸次數(shù)D:遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)11、對一組數(shù)據(jù)（ 2， 12， 16， 88， 5， 10）進行排序，若前三趟排序結(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、 下列選項中，能縮短程序執(zhí)行時間的措施是( D)4I 提高 CPU 時鐘頻率， II 優(yōu)化數(shù)據(jù)通過結(jié)構(gòu)， III 對程序進行編譯優(yōu)化A:僅 I 和 II B:僅 I 和 III C

5、:僅 II 和 III D: 1,11 , III13、 假定有 4 個整數(shù)用 8 位補碼分別表示 r1=FEH ,r2=F2H ,r3=90H,r4=F8H, 若將 運算結(jié)果存放在一個 8 位的寄存器中,則下列運算會發(fā)生溢出的是( C)A: r1*r2 B : r2*r3C: r1*r4 D: r2*r414、 假定變量 I,f,d 數(shù)據(jù)類型分別為 int,float 和 double(int 用補碼表示, float 和 double 分別用 IEEE754 單精度和雙精度浮點數(shù)據(jù)格式表示 ),已知 i=785,f=1.5678,d=1.5 若在 32 位機器中執(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、 假定用若干個 2k*4 位芯片組成一個 8*8 位存儲器,則地址 0B1FH 所在芯片的 最小地址是( D )A: 0000HB: 0600HC: 0700HD: 0800H16、 下列有關(guān) RAM 和 ROM 的敘述中，正確的是(A)I 、 RAM 是易失性存儲器, ROM 是非易失性存儲器II、 RAM 和 ROM 都是采用隨機

7、存取的方式進行信息訪問III、 RAM 和 ROM 都可用作 CacheIV、 RAM 和 ROM 都需要進行刷新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、下列存儲器中,匯編語言程序員可見的是( B)5A:存儲器地址寄存器（MAR）B:程序計數(shù)器（

8、PC）C:存儲器數(shù)據(jù)寄存器（MDR）D:指令寄存器（IR）19、 下列不會引起指令流水阻塞的是（ A）A:數(shù)據(jù)旁路B:數(shù)據(jù)相關(guān)C:條件轉(zhuǎn)移D:資源沖突20、 下列選項中的英文縮寫均為總線標(biāo)準(zhǔn)的是（ D）A: PCI、CRT、USB、EISAB: ISA、CPI、VESA、EISAC: ISA、SCSI、RAM、MIPSD: ISA、EISA、PCI、PCI-Express21、 單級中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（ A）I、保護現(xiàn)場 II、開中斷 III、關(guān)中斷 IV、保存斷點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、 假定一臺計算機的顯示存儲器用 DRAM 芯片實現(xiàn)，若要求顯示分辨率為1600*1200，顏色深度為 24 位，幀頻為 85Hz，顯示總帶寬的 50%用來刷新屏幕, 則需要的顯存總帶寬至少約為（ D）A : 245 MbpsB: 979 MbpsC: 1958 MbpsD: 7834Mbps23、 下列選項中，操作 S 提供的給應(yīng)用程序的接口是（A）A:系統(tǒng)調(diào)用B:中斷C:庫函數(shù)D :原語24、 下列選項中，導(dǎo)致創(chuàng)進新進程的操作是（ C）I 用戶成功登陸 II 設(shè)備分配 III 啟動

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

11、ulse ；flag 1 =faulse ；若進行 P0 和 P1 訪問臨界資源的類 C 代碼實現(xiàn)如下：Void p0() / 進程 p0Void p1 () / 進程 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í)行進程 P0 和 P1 時產(chǎn)生的情況是:A：不能保證進程互斥進入臨界區(qū)，會出現(xiàn) 饑餓”現(xiàn)象B:不能保證進程互斥進入臨界區(qū)，

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

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

14、:命令解釋程序B:中斷處理程序C:系統(tǒng)調(diào)用程序D:用戶登錄程序33、 下列選項中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是（C）A:網(wǎng)絡(luò)的層次B:每一層使用的協(xié)議C:協(xié)議的內(nèi)部實現(xiàn)細(xì)節(jié)D:每一層必須完成的功能34、在下圖所示的采用 存儲-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中，所有鏈路的數(shù)據(jù)傳輸速 度為100mbps，分組大小為 1000B,其中分組頭大小 20B，若主機 H1 向主機 H2 發(fā)送一個大小為 980000B 的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從 H1 發(fā)送到 H2 接收完為止，需要的時間至少是（ 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 不能進過 R2 到達(dá) net136、若路由器 R 因為擁塞丟棄 IP 分組，貝V此時 R 可以向發(fā)出該 IP 分組的源主機發(fā) 送的 ICMP 報文件類型是（ C ）A:路由重定向B:目的不可達(dá)C:源抑制D:超時37、某網(wǎng)絡(luò)的 IP 地址為 192.168.5.0/24 采用長子

16、網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248 ，貝該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)，每個子網(wǎng)內(nèi)的最大可分配地址個數(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、主機甲和主機乙之間已建立一個 TCP 連接，TCP 最大段長度為 1000 字節(jié)，若 主機甲的當(dāng)前擁塞窗口為 4000 字節(jié)，在主機甲向主機乙連接發(fā)送 2 個最大段后， 成 功收到主機乙發(fā)送的第一段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為 2000 字節(jié)， 貝此時主機甲還可以向主機乙發(fā)送的最

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

18、請畫出所構(gòu)造的散列表；9(2)分別計算等概率情況下，查找成功和查找不成功的平均查找長度。解答：(1) 由裝載因子 0.7，數(shù)據(jù)總數(shù) 7 個-存儲空間長度為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)個整數(shù)存放到一維數(shù)組 R 中，試設(shè)計一個在時間和空間兩 方面盡可能有效的算法，將 R 中保有的序列循環(huán)左移 P (0 Pn)個位置，即將

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

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

21、R5 的編號分另 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） +（逗號前原操作數(shù)， 都號后為目的操作數(shù)）對應(yīng)的機器碼是什么（用十六進制表示） ？ 該指令執(zhí)行后，哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么？11解答: 該題的考點是指令系統(tǒng)設(shè)計， 注意操作位數(shù)與指令條數(shù)的關(guān)系， 地址碼與寄存器數(shù) 的關(guān)系，指令字長與 MOR 的關(guān)系，存儲容量與 MAR 的關(guān)系，注意補碼計算的偏移 地址。44.

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

23、塊對應(yīng)的 Cache 行號分別是多少（Cache 行號從 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ù)訪問命令中各是多少？那個程序的執(zhí)行時間更短?簡答：考點：Cache 容量計算，直接映射方式的地址計算，以

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

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