2010研究生入學(xué)考試計算機(jī)專業(yè)統(tǒng)考真題

1、2010年全國研究生考試計算機(jī)統(tǒng)考真題一、單選題1、若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（    ）A：dcebfa   B：cbdaef    C：dbcaef    D：afedcb2、某隊列允許在其兩端進(jìn)行入隊操作，但僅允許在一端進(jìn)行出隊操作，則不可能得到的順序是（ ）A：bacde    B：dbace     C：dbcae 

2、;    D：ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（    ）4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ ）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ù)是（）A：41   

3、  B：82   C：113   D：1226、對n(n大于等于2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）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 ：6  B：15  C：16  D：218、對下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個數(shù)是（ ）A：4&#

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

5、一組數(shù)據(jù)（2，12，16，88，5，10）進(jìn)行排序，若前三趟排序結(jié)果如下（）第一趟：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í)行時間的措施是（）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、60;  D：I，II，III13、假定有4個整數(shù)用8位補(bǔ)碼分別表示r1=FEH ,r2=F2H ,r3=90H,r4=F8H,若將運(yùn)算結(jié)果存放在一個8位的寄存器中，則下列運(yùn)算會發(fā)生溢出的是（）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ù)據(jù)格式表示)，已知i=785,f

7、=1.5678,d=1.5若在32位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式，則結(jié)果為真是（）（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所在芯片的最小地址是（）A：0000H     B：0600H     C： 0700H     D：0800H16、下列有關(guān)RAM和ROM的敘述中，正確的是（）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、60;  D：僅II，III，IV17、下列命令組合情況中，一次訪存過程中，不可能發(fā)生的是（）A：TLB未命中，Cache未命中，Page未命中B：TLB未命中，Cache命中，Page命中C：TLB命中，Cache未命中，Page命中D：TLB命中，Cache命中，Page未命中18、下列存儲器中，匯編語言程序員可見的是（）A：存儲器地址寄存器（MAR）  B：程序計數(shù)器（PC）C：存儲器數(shù)據(jù)寄存器（MDR）  D：指令寄存器（IR）19、下列不會引起指令流水阻塞的是（）A：數(shù)據(jù)旁路    B：數(shù)據(jù)相關(guān)  

10、60; C：條件轉(zhuǎn)移   D：資源沖突20、下列選項(xiàng)中的英文縮寫均為總線標(biāo)準(zhǔn)的是（）A：PCI、CRT、USB、EISA   B：ISA、CPI、VESA、EISAC：ISA、SCSI、RAM、MIPS   D：ISA、EISA、PCI、PCI-Express 21、單級中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（）I、保護(hù)現(xiàn)場  II、開中斷  III、關(guān)中斷  IV、保存斷點(diǎn)V、中斷事件處理   VI、恢復(fù)現(xiàn)場   VII、中斷返回A：I、V、VI、II、VII B：I

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

12、行A：僅I和II B：僅II和III C：僅I和III D：I，II，III25、設(shè)與某資源相關(guān)聯(lián)的信號量初值為3，當(dāng)前值為1，若M表示該資源的可用個數(shù)，N表示等待資源的進(jìn)程數(shù)，則M,N分別是（）A：0，1 B：1，0 C：1，2 D：2，026、下列選項(xiàng)中，降低進(jìn)程優(yōu)先權(quán)級的合理時機(jī)是（ ）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的共享變量定義及其初值為（ ）boolean flag2；int turn=0；flag0=faulse；flag1=faulse；若進(jìn)行P0和P1訪問臨界資源的類C代碼實(shí)現(xiàn)

13、如下：Void  p0（）/ 進(jìn)程p0                Void  p1（）/ 進(jìn)程p1while（TURE）                    while（TURE）Flag0=TURE;ture=1 

14、0;                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)程互斥進(jìn)入臨界區(qū)，不會出

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

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

19、議 C：協(xié)議的內(nèi)部實(shí)現(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：80ms B：80.08msC：80.16ms D：80.24ms35、某自治系統(tǒng)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含信息net1，16，則可能得出的結(jié)論是（ ）A：R2可以經(jīng)過R1到達(dá)net1，跳數(shù)為17 B：

20、R2可以到達(dá)net1，跳數(shù)為16C：R1可以經(jīng)過R2到達(dá)net1，跳數(shù)為17 D：R1不能進(jìn)過R2到達(dá)net136、若路由器R因?yàn)閾砣麃G棄IP分組，則此時R可以向發(fā)出該IP分組的源主機(jī)發(fā)送的ICMP報文件類型是（ ）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ù)為（ ）A：32，8 B：32，6 C：8，32 D：8，3038、下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風(fēng)暴的是（ ）中繼器   集線器 

21、0;  網(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：1000 B：2000 C：3000 D：400040、如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域名時，用戶主機(jī)本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為（ ）A：1條，1條 B：1條，多條 C：多條，

22、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）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。42.（13分）設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P（0Pn）個位置，即將R中的數(shù)據(jù)由（X0 X1 Xn-1）變換

23、為（Xp Xp+1 Xn-1  X0  X1 Xp-1）要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C+或JAVA語言表述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度43.(11分)某計算機(jī)字長為16q位，主存地址空間大小為128KB，按字編址，采用字長指令格式，指令名字段定義如下：轉(zhuǎn)移指令采用相對尋址方式，相對偏移是用補(bǔ)碼表示，尋址方式定義如下：Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=（Rn）001B寄存器間接（Rn）操作數(shù)=（(Rn)）010B寄存器間接、自增（Rn）+操作數(shù)=（(Rn)），（Rn）+1Rn

24、011B相對D（Rn）轉(zhuǎn)移目標(biāo)地址=（PC）+（Rn）注：（X）表示有儲蓄地址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ī)

25、器碼是什么（用十六進(jìn)制表示）？該指令執(zhí)行后，哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么？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）、若不考慮用于cache一致性維護(hù)和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘渴嵌嗌伲浚?）、要組

26、元素a031和a11各自所在的主存塊對應(yīng)的Cache行號分別是多少（Cache行號從0開始）？（3）、程序A和B的數(shù)據(jù)訪問命令中各是多少？那個程序的執(zhí)行時間更短？簡答：考點(diǎn)：Cache容量計算，直接映射方式的地址計算，以及命中率計算（行優(yōu)先遍歷與列優(yōu)先遍歷命中率分別很大）假定int 類型數(shù)據(jù)用32位補(bǔ)碼表示，程序編譯時i,j, sum 均分配在寄存器中，數(shù)據(jù)a按行優(yōu)先方式存放，其地址為320（十進(jìn)制數(shù)），請回答下列問題，要求說明理由或給出計算過程。（1）、若不考慮用于cache一致性維護(hù)和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘渴嵌嗌伲浚?）、要組元素a031和a11各自所在的主存塊對應(yīng)的C

27、ache行號分別是多少（Cache行號從0開始）？（3）、程序A和B的數(shù)據(jù)訪問命令中各是多少？那個程序的執(zhí)行時間更短？簡答：考點(diǎn)：Cache容量計算，直接映射方式的地址計算，以及命中率計算（行優(yōu)先遍歷與列優(yōu)先遍歷命中率分別很大） 46.（8分）設(shè)某計算機(jī)的邏輯地址空間和物理地址空間均為64KB.按字節(jié)編址。若某進(jìn)程最多需要6頁（Page）數(shù)據(jù)存儲空間，頁的大小為1KB.操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框（Page Fame）.頁號頁根號裝入時刻訪問位071301142301222001391601當(dāng)該進(jìn)程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請問答下

28、列問題：（1）、該邏輯地址對應(yīng)的頁號是多少？（2）、若采用先進(jìn)先出（FIFO）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（3）、若采用時鐘（CLOCK）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下。）47、（9分）某局域網(wǎng)采用CSMA/CD協(xié)議實(shí)現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸速率為10MBPS,主機(jī)甲和主機(jī)乙之間的距離為2KM，信號傳播速度是200 000KMS.請回答下列問題，并給出計算過程。（1）若主機(jī)甲和主機(jī)乙發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機(jī)均檢測到?jīng)_突時刻止，最短需經(jīng)多長時間？最長需經(jīng)過多長時間？（假設(shè)主機(jī)甲和主機(jī)乙發(fā)送數(shù)據(jù)過程中，其他主機(jī)不發(fā)送數(shù)據(jù)）（2）若網(wǎng)絡(luò)不存在任何沖突與差錯，主機(jī)甲總是以標(biāo)準(zhǔn)的最長以大網(wǎng)