(好)2010計算機(jī)考研真題及答案

1、2010年全國研究生考試計算機(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、某隊列允許在其兩端進(jìn)行入隊操作，但僅允許在一端進(jìn)行出隊操作，則不可能得到的順序是（ C ）A：bacde    B：dbace     C：dbca

2、e     D：ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（  B  ）4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ C ）A：13，48   B：24，48   C：24，53   D：24，905、在一棵度為4的樹T中，若有20個度為4的結(jié)點(diǎn)，10個度為3的結(jié)點(diǎn)，1個度為2的結(jié)點(diǎn)，10個度為1的結(jié)點(diǎn)，則樹T的葉節(jié)點(diǎn)個數(shù)是（B）A：41 &#

3、160;   B：82   C：113   D：1226、對n(n大于等于2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（B）A：該樹一定是一棵完全二叉樹 B：樹中一定沒有度為1的結(jié)點(diǎn)C：樹中兩個權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn) D：樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值7、若無向圖G-（V.E）中含7個頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（A）A ：6  B：15  C：16  D：218、對下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個

4、數(shù)是（B ）A：4    B：3   C：2   D：19、已知一個長度為16的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多是（A）A：4   B：5   C：6    D：710、采用遞歸方式對順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（D）A：遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B：每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C：每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D：遞歸次數(shù)與每次劃分后得到的

5、分區(qū)處理順序無關(guān)11、對一組數(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、下列選項中，能縮短程序執(zhí)行時間的措施是（D）I 提高CPU時鐘頻率，II優(yōu)化數(shù)據(jù)通過結(jié)構(gòu)，III對程序進(jìn)行編譯優(yōu)化A：僅I和II     B：僅I和III     C：僅II和III

6、     D：I，II，III13、假定有4個整數(shù)用8位補(bǔ)碼分別表示r1=FEH ,r2=F2H ,r3=90H,r4=F8H,若將運(yùn)算結(jié)果存放在一個8位的寄存器中，則下列運(yùn)算會發(fā)生溢出的是（C）A： r1*r2     B ：r2*r3     C：r1*r4     D：r2*r414、假定變量I,f,d數(shù)據(jù)類型分別為int,float和double(int用補(bǔ)碼表示，float和double分別用IEEE754單精度和雙精度浮點(diǎn)數(shù)

7、據(jù)格式表示)，已知i=785,f=1.5678,d=1.5若在32位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式，則結(jié)果為真是（C） （I）f=(int)(float)I   (II)f=(float)(int)f     (III)f=(float)(double)     (IV)=(d+f)-d=fA：僅I和II    B：僅I和III    C：僅II和III    D：僅III和IV15、假定用若干個2k*4位芯片組

8、成一個8*8位存儲器，則地址0B1FH所在芯片的最小地址是（D）A：0000H     B：0600H     C： 0700H     D：0800H16、下列有關(guān)RAM和ROM的敘述中，正確的是（A）I、 RAM是易失性存儲器，ROM是非易失性存儲器II、 RAM和ROM都是采用隨機(jī)存取的方式進(jìn)行信息訪問III、RAM和ROM都可用作CacheIV、RAM和ROM都需要進(jìn)行刷新A：僅I和II  B：僅II和III   C：僅I,II，III&

9、#160;  D：僅II，III，IV17、下列命令組合情況中，一次訪存過程中，不可能發(fā)生的是（D）A：TLB未命中，Cache未命中，Page未命中B：TLB未命中，Cache命中，Page命中C：TLB命中，Cache未命中，Page命中D：TLB命中，Cache命中，Page未命中18、下列存儲器中，匯編語言程序員可見的是（B）A：存儲器地址寄存器（MAR）  B：程序計數(shù)器（PC）C：存儲器數(shù)據(jù)寄存器（MDR）  D：指令寄存器（IR）19、下列不會引起指令流水阻塞的是（A） A：數(shù)據(jù)旁路    B：數(shù)據(jù)相關(guān) 

10、60;  C：條件轉(zhuǎn)移   D：資源沖突20、下列選項中的英文縮寫均為總線標(biāo)準(zhǔn)的是（D）A：PCI、CRT、USB、EISA   B：ISA、CPI、VESA、EISAC：ISA、SCSI、RAM、MIPS   D：ISA、EISA、PCI、PCI-Express21、單級中斷系統(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、

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

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

13、問臨界資源的類C代碼實現(xiàn)如下：Void  p0（）/ 進(jìn)程p0                Void  p1（）/ 進(jìn)程p1while（TURE）                    while（TURE）Flag0=TURE;ture

14、=1                  Flag1=TURE; ture=1While （flag1&&（turn=1）        While （flag0&&（turn=0）臨界區(qū)：Flag0=FALSE;         

15、0;             Flag1=FALSE;                                    &#

16、160;                                 則并發(fā)執(zhí)行進(jìn)程P0和P1時產(chǎn)生的情況是：A：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C：能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D：能保證進(jìn)程互

17、斥進(jìn)入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象28、某基于動態(tài)分區(qū)存儲管理的計算機(jī)，其主存容量為55mb（初試為空間），采用最佳適配（Best fit）算法，分配和釋放的順序為：分配15mb，分配30mb，釋放15mb，分配8mb，此時主存中最大空閑分區(qū)的大小是（ B ）A：7mb B：9mb C：10mb D：15mb29、某計算機(jī)采用二級頁表的分頁存儲管理方式，按字節(jié)編制，頁大小為216字節(jié)，頁表項大小為2字節(jié)，邏輯地址結(jié)構(gòu)為頁目編號頁號頁內(nèi)偏移量邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是（ B ）A：64 B：128 C：256 D：51230、設(shè)文件索引節(jié)點(diǎn)

18、中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件的最大長度是（ C ）A：33kb B：519kb C：1057kb D：16513kb31、設(shè)置當(dāng)前工作目錄的主要目的是（ C ）A：節(jié)省外存空間 B：節(jié)省內(nèi)容空間C：加快文件的檢索速度 D：加快文件的讀寫速度32、本地用戶通過鍵盤登錄系統(tǒng)時，首先獲得鍵盤輸入信息的程序是（B ）A：命令解釋程序 B：中斷處理程序C：系統(tǒng)調(diào)用程序 D：用戶登錄程序33、下列選項中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是（ C

19、 ）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，若主機(jī)H1向主機(jī)H2發(fā)送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送到H2接收完為止，需要的時間至少是（ A ）A：80ms B：80.08ms C：80.16ms D：80.24ms35、某自治系統(tǒng)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含信息net1，16，則可能得出的結(jié)論是（ A ）A：

20、R2可以經(jīng)過R1到達(dá)net1，跳數(shù)為17B：R2可以到達(dá)net1，跳數(shù)為16C：R1可以經(jīng)過R2到達(dá)net1，跳數(shù)為17D：R1不能進(jìn)過R2到達(dá)net136、若路由器R因為擁塞丟棄IP分組，則此時R可以向發(fā)出該IP分組的源主機(jī)發(fā)送的ICMP報文件類型是（ C ）A：路由重定向 B：目的不可達(dá)C：源抑制 D：超時37、某網(wǎng)絡(luò)的IP地址為192.168.5.0/24采用長子網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248，則該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)，每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)為（ B ）A：32，8 B：32，6C：8，32 D：8，3038、下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風(fēng)暴的是（ C ）中繼器&

21、#160;  集線器    網(wǎng)橋    路由器A：僅和 B：僅C：僅和 D：僅39、主機(jī)甲和主機(jī)乙之間已建立一個TCP連接，TCP最大段長度為1000字節(jié)，若主機(jī)甲的當(dāng)前擁塞窗口為4000字節(jié)，在主機(jī)甲向主機(jī)乙連接發(fā)送2個最大段后，成功收到主機(jī)乙發(fā)送的第一段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為2000字節(jié)，則此時主機(jī)甲還可以向主機(jī)乙發(fā)送的最大字節(jié)數(shù)是（ A ）A：1000 B：2000C：3000 D：400040、如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域名時，用戶主機(jī)本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別

22、為（ 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）=（key×3）MODT，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7問題：（1）請畫出所構(gòu)造的散列表；（2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。解答：（1）由裝載因子0.7，數(shù)據(jù)總數(shù)7個存儲空間長度為10P=10所以，構(gòu)造的散列表為：01234567893071411818.9.H（

23、7）=（7×3）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（0Pn）個位置，即將R中的數(shù)據(jù)由（X0 X1 Xn-1）變換為（Xp Xp+1 Xn-1  X0  X1 Xp-1）要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C+或JAVA語言表述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間

24、復(fù)雜度解答：（1）前P個數(shù)依次進(jìn)隊，while（1n-p）Ai-i+p：p個數(shù)依次出對，進(jìn)入數(shù)組末尾（2）詳細(xì)程序略（3）時間復(fù)雜度O（N）;空間復(fù)雜度o(p)43.(11分)某計算機(jī)字長為16q位，主存地址空間大小為128KB，按字編址，采用字長指令格式，指令名字段定義如下：轉(zhuǎn)移指令采用相對尋址方式，相對偏移是用補(bǔ)碼表示，尋址方式定義如下：Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=（Rn）001B寄存器間接（Rn）操作數(shù)=（(Rn)）010B寄存器間接、自增（Rn）+操作數(shù)=（(Rn)），（Rn）+1Rn011B相對D（Rn）轉(zhuǎn)移目標(biāo)地址=（PC）+（Rn）注：（X）表示有儲

25、蓄地址X或寄存器X的內(nèi)容，請回答下列問題：（1）該指令系統(tǒng)最多可有多少條指令？該計算機(jī)最多有多少個通用寄存器？存儲器地址寄存器（MDR）至少各需多少位？（2）轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？（3）若操作碼0010B表示加法操作（助記符為a d d），寄存器R4和R5的編號分別為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)的機(jī)器碼是什么（用十六進(jìn)制表示）？該指令執(zhí)行后，哪些寄存器和存儲單元的內(nèi)容會

26、改變？改變后的內(nèi)容是什么？解答：該題的考點(diǎn)是指令系統(tǒng)設(shè)計，注意操作位數(shù)與指令條數(shù)的關(guān)系，地址碼與寄存器數(shù)的關(guān)系，指令字長與MOR的關(guān)系，存儲容量與MAR的關(guān)系，注意補(bǔ)碼計算的偏移地址。44.（12分）某計算機(jī)的主存地址空間為256MB，按字節(jié)編址，指令Cache分離均有8個Cache行，每個Cache行的大小為64MB，數(shù)據(jù)Cache采用直接映射方式，現(xiàn)有兩個功能相同的程序A和B,其偽代碼如下所示：假定int 類型數(shù)據(jù)用32位補(bǔ)碼表示，程序編譯時i,j, sum 均分配在寄存器中，數(shù)據(jù)a按行優(yōu)先方式存放，其地址為320（十進(jìn)制數(shù)），請回答下列問題，要求說明理由或給出計算過程。（1）、若不考慮用

27、于cache一致性維護(hù)和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘渴嵌嗌?？?）、要組元素a031和a11各自所在的主存塊對應(yīng)的Cache行號分別是多少（Cache行號從0開始）？（3）、程序A和B的數(shù)據(jù)訪問命令中各是多少？那個程序的執(zhí)行時間更短？簡答：考點(diǎn)：Cache容量計算，直接映射方式的地址計算，以及命中率計算（行優(yōu)先遍歷與列優(yōu)先遍歷命中率分別很大）45、（7分）假設(shè)計算機(jī)系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤塊的空間狀態(tài)（1）、請說明在上述條件下如何進(jìn)行磁盤塊空閑狀態(tài)管理。（2）、設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)。每個磁道有100個扇區(qū)，相臨磁道間的平均移動時間為1ms.若在某時刻，磁頭位于100號磁道處，并沿著磁道號大的方向移動（如下圖所示），磁道號請求隊列為50.90.30.120.對請求隊列中的每個磁道需讀取1個隨機(jī)分布的扇區(qū)，則讀完這個扇區(qū)點(diǎn)共需要多少時間？要求給出計算過程。46.（8分）設(shè)某計算機(jī)的邏輯地址空間和物理地址空間均為64KB.按字節(jié)編址。若某進(jìn)程最多需要6頁（Page）數(shù)據(jù)存儲空間，頁的大小為1KB.操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框（Page Fame）.頁號頁根號裝入時刻訪問位071301142301222001391601當(dāng)