2010年全國研究生考試計算機統(tǒng)考真題及答案

2010年全國研究生考試計算機統(tǒng)考真題及答案

一、單選題

1、若元素@?,。,（1,0,￡依次進棧，允許進棧、退棧操作交替進行。但不允許連續(xù)三次進行

退棧工作，則不可能得到的出棧序列是（D）

A：dcebfaB：cbdaefC：dbcaefD：afedcb

2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順

序是（）

A：bacdeB：dbaceC：dbcaeD：ecbad

3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）

4、在下列所示的平衡二叉樹中插入關鍵字48后得到一棵新平衡二叉樹,在新平衡二叉樹中,

關鍵字37所在結點的左、右子結點中保存的關鍵字分別是（）

A：13,48B：24,48C：24,53D：24,90

5、在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結

點，10個度為1的結點，則樹T的葉節(jié)點個數(shù)是（）

A：41B：82C：113D：122

6、對n（n大于等于2）個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是

（）

A：該樹一定是一棵完全二叉樹B：樹中?定沒有度為1的結點

C：樹中兩個權值最小的結點一定是兄弟結點D：樹中任一非葉結點的權值一定不小于下一

任一結點的權值

7、若無向圖G-（V.E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊

數(shù)最少是（）

A：6B：15C：16D：21

8、對下圖進行拓補排序，可以得到不同的拓補序列的個數(shù)是()

A：4B：3C：2D：1

9、已知一個長度為16的順序表L,其元素按關鍵字有序排列，若采用折半查找法查找一個

不存在的元素，則比較次數(shù)最多是。

A：4B：5C：6D：7

10、采用遞歸方式對順序表進行快速排序，下列關于遞歸次數(shù)的敘述中，正確的是()

A：遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關

B：每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)

C：每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)

D：遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關

11、對一組數(shù)據(jù)(2,12,16,88,5,10)進行排序，若前三趟排序結果如下()

第一趟：2,12,16,5,10,88

第二趟：2,12,5,10,16,88

第三趟：2,5,10,12,16,88

則采用的排序方法可能是：

A：起泡排序B：希爾排序C：歸并排序I)：基數(shù)排序

12、下列選項中，能縮短程序執(zhí)行時間的措施是()

1提高CPU時鐘頻率，II優(yōu)化數(shù)據(jù)通過結構，HI對程序進行編譯優(yōu)化

A：僅I和IIB：僅I和IIIC：僅口和IIID：I,II,III

13、假定有4個整數(shù)用8位補碼分別表示rl=FEH,r2=F2H,r3=90H,r4=F8H,若將運算結果

存放在一個8位的寄存器中，則下列運算會發(fā)生溢出的是()

A：rl*r2B：r2*r3C：rl*r41)：r2*r4

14、假定變量I,f,d數(shù)據(jù)類型分別為int,floatdouble(int用補碼表示，float和double

分別用IEEE754單精度和雙精度浮點數(shù)據(jù)格式表示)，已知i=785,f=l.5678,d=L5若在32

位機器中執(zhí)行下列關系表達式，則結果為真是()

(I)

f=(int)(float)I(II)f=(float)(int)f(III)f=(float)(double)(IV)=(d

+f)-d=f

A：僅I和IIB：僅I和HIC：僅II和HID：僅III和IV

15、假定用若干個2k*4位芯片組成一個8*8位存儲器，則地址0B1FH所在芯片的最小地址

是()

A：0000HB：0600HC：0700HI)：0800H

16,下列有關RAM和ROM的敘述中,正確的是()

1、RAM是易失性存儲器，ROM是非易失性存儲器

II、RAM和ROM都是采用隨機存取的方式進行信息訪問

IlkRAM和ROM都可用作Cache

IV、RAM和ROM都需要進行刷新

A：僅I和IIB：僅n和inC：僅I,H,IIID：僅H,III,IV

17、下列命令組合情況中，一次訪存過程中，不可能發(fā)生的是()

A：TLB未命中，Cache未命中，Page未命中

B：TLB未命中，Cache命中，Page命中

C：TLB命中,Cache未命中,Page命中

D：TLB命中，Cache命中，Page未命中

18、下列存儲器中，匯編語言程序員可見的是()

A：存儲器地址寄存器(MAR)B：程序計數(shù)器(PC)

C.存儲區(qū)數(shù)據(jù)寄存器(MDR)

D.指令寄存器(IR)

19.下列不會引起指令流水阻塞的是()

A.數(shù)據(jù)旁路

B.數(shù)據(jù)相關

C.條件轉移

D.資源沖突

20.下列選項中的英文縮寫均為總線標準的是()

A.PCI、CRT、USB、EISAB.ISA.CPI、VESA、EISAC.ISA.SCSI、RAM、MIPSD.ISA>EISA、

PCI、PCI-Express21、單級中斷系統(tǒng)中，中斷服務程序執(zhí)行順序是()

I保護現(xiàn)場

II開中斷

III關中斷

IV保存斷點

V中斷事件處置懲罰

VI恢復現(xiàn)場

VII中斷歸回

A、I-V-VI-II-VIIB、III-I-V-VIIC、III-IV-V-VI-VIID、IV-I-V-VI-VII22、假定一臺

計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600*1200,色彩深度為24位,

幀頻為85HZ,現(xiàn)實總帶寬的50%用來刷新熒幕，則需要的顯存總帶寬至少約為()

A、245MbpsB、979MbpsC、1958MbpsD、7834Mbps2三、下列選項中，操作S供給的給應

程序的接口是()

A、系統(tǒng)挪用

B、中斷

C、庫函數(shù)

D、原語

24、下列選項中，導制創(chuàng)進新進程項的操作是()

I用戶登陸成功II設備分配IH啟動程序執(zhí)行

A、僅I和IIB、僅II和IIIC、僅1和HI1)、I、II.Ill25、設與某資源相關聯(lián)的信

號量初值為3,當前值為1,若M表示該資源的可用個數(shù)，N表示等待該資源的進程項數(shù)，

則M,N分別是()

A、0,1B、1,0C、1,2D、2,026、下列選項中，降低進程項優(yōu)先權級的合理機會是()

A、進程項的時間片用完

B、進程項剛完成I/O,進入就緒列隊

C、進程項持久處于就緒列隊

D、進程項從就緒狀態(tài)轉為運行狀態(tài)

27、進行P0和P1的共享變量定義及其初值為()

boolean)flag[2]；

intturn=0；

flag[0]=false；flag[l]=false；

若進行P0和Pl訪問臨界資源的類C代碼實現(xiàn)如下：

voidp0()〃進程項p0voidpl()〃進程項pl

{{

while(TRUE){while(TRUE){

flag[O]=TRUE；turn=l；flag[O]=TRUE；turn=O；

While{flag[l]&&(turn==l)While{flag[0]&&(turn==0)

臨界區(qū)；臨界區(qū)；

flag[0]=FALSE；flag[l]=FALSE；

}}

})

則并發(fā)執(zhí)行進程項PO和P1時產(chǎn)生的情況是()

A、不能保證進程項互斥進入臨界區(qū)，會呈現(xiàn)"饑餓”征象

B、不能保證進程項互斥進入臨界區(qū)，不會呈現(xiàn)"饑餓”征象

C、能保證進程項互斥進入臨界區(qū)，會呈現(xiàn)"饑餓”征象

D、能保證進程項互斥進入臨界區(qū)，不會呈現(xiàn)''饑餓"征象

28、某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55Mb(初始為空)，采用最好適配(Best

Fit)算法,分配和釋放的順序為：分配15Mb,分配30Mb,釋放15法,分配6Mb,此時主存

中最大余暇分區(qū)的大小是()

A、7MbB、9MbC.10MbD、15Mb29、某計算機采用二級頁表的分頁存儲管理體式格局，按

字節(jié)編制，頁大小為2(10)12的10次方，下同】字節(jié)，頁表項大小為2字節(jié)，邏輯地址結

構為

頁目次號

頁號

蟲內偏移量

邏輯地址空間大小為2(10)頁，則表示全般邏輯地址空間的頁目次表中包含表項的個數(shù)至少

是()

A、64B、128C、2561)、51230.設文件索引節(jié)點中有7個地址項，此中4個地址為直接地

址索引，1個地址項是二級間接地址索引，每個地址項的大小為4字節(jié)，若磁盤索引塊和磁

盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件最大長度是()

A.33KBB.519KBC.1057KBD.16513KB31.設當前工作目次的主要目的是0

A.節(jié)省外存空間

B.節(jié)省內存空間

C.加快文件的檢索速度

D.加快文件的讀寫速度

32.本地用戶通過鍵盤登陸系統(tǒng)是，起首獲得鍵盤輸入信息的程序時0

A.號令解釋程序

B.中斷處置懲罰程序

C.系統(tǒng)挪用程序

D.用戶登錄程序

33.下列選項中，不屬于網(wǎng)絡體系結構中所描述的內容是0

A.網(wǎng)絡的層次

B.每一層施用的和談

C.和談的內部實現(xiàn)細節(jié)

D.每一層必須完成的功能

34.在下圖所表示的采用"存儲-轉發(fā)”體式格局分組的交換網(wǎng)絡中所有的鏈路的數(shù)據(jù)傳輸速

度為100Mbps,分組大小為1000B,此中分組頭大小為20B若主機H1向主機H2發(fā)送一個大

小為980000的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送到H2接受

完為止，需要的時間至少是()

A.80msB.80.08msC.80.16msD.80.24ms35.某自治系統(tǒng)采用RIP和談，若該自治系統(tǒng)內的

路山器R1收到其鄰居路由器R2的距離矢量中包含的信息netl,16,則可能得出的結論是

0

A.R2可以經(jīng)過R1到達netl,跳數(shù)為17B.R2可以到達netl,跳數(shù)為16C.R1可以經(jīng)過R2

到達netl,跳數(shù)為17D.R1不能經(jīng)過R2到達netl36.若路由器R因為擁塞丟棄IP分組，

則此時R可向發(fā)出該IP分組的源主機的ICMP報文件的類型是()

A.路由重定向

B.目的不可達

C.源抑制

D.超時

37、某網(wǎng)絡的IP地址空間為192.168.5.0/24采用長子網(wǎng)劃分，子網(wǎng)掩碼為

255.255.255.248,則該網(wǎng)絡的最大子網(wǎng)個數(shù)、每個子網(wǎng)內的最大可分配地址個數(shù)為()

A、32,8B、32,6C、8,32D、8,3038、下列網(wǎng)絡設備中，能夠抑制網(wǎng)絡風暴的是()

I中斷器

II集線器

III網(wǎng)橋

IV路由器

A、僅I和IIB、僅inC、僅HI和IVD、僅IV39、主機甲和主機乙之間建立一個TCP

連接，TCP最大段長度為1000字節(jié)，(勤思考研)若主機甲的當前擁塞窗口為4000字節(jié)，在

主機甲向主機乙連續(xù)發(fā)送2個最大段后，成功收到主機乙發(fā)送的第一段的確認段，確認段中

通告的吸收窗口大小為2000字節(jié)，則此忖主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是()

A、1000B、2000C、3000D、400040、要是本地區(qū)名服務無緩存，當采用遞歸要領解析另

一網(wǎng)絡某主機域名時，用戶主機本地區(qū)名服務器發(fā)送的域名哀求條數(shù)分別為()

A、1條，1條

B、1條，多條

C、多條，1條

D、多條，多條

二、綜合應用題：41-47小題，共70分

41.(10分)將關鍵字序列(7、8、30、1。18、9、14)散列存儲到散列表中，(勤思考研)散

列表的存儲空間是一個下標從0開始的一個一維數(shù)組散列，函數(shù)為：H(key)=(keyx3)M0DT,

處置懲罰沖突采用線性探測再散列法，要求裝載因子為0.7

問題：

(1).請畫出所構造的散列表。

(2).分別計算等概率情況下，查找成功和查找不成功的平均查找長度。

42.(13分)設將n(n1)個整兒存放到一維數(shù)組R中。預設一個在時間和空間兩方面盡可能高

效的算法。將R中的序列循環(huán)左移P(OPn)個位置，即將R中的數(shù)據(jù)由(XO,X1,…XnT)變換

為(Xp,Xp-1-Xn-1,X0,Xl-Xp-1)要求：

(1)、給出算法的基本預設思想。

⑵、按照預設思想，采用C或C++或JAVA語言描述算法，關鍵的地方給出注釋。

(3)、說明你所預設算法的時間復雜度和空間復雜度。

43、(11分)某計算機字節(jié)長為16位，主存地址空間大小為128KB,按字編址。采用字長指

令格式，指令名兒段定義如下：

151211650

OPM5R5MdRd

源操作數(shù)目的操作數(shù)

轉移指令采用相對尋址，相對偏移是用補碼表示，尋址體式格局定義如下：

Ms/Md

尋址體式格局

助記符

含義

000B

寄存器直接

Rn

操作數(shù)=(Rn)

001B

寄存器間接

(Rn)

操作數(shù)=((Rn))

010B

寄存器間接、自增

(Rn)+

操作數(shù)=((Rn)),(Rn)+1-Rn01IB

相對

D(Rn)

轉移目標地址=(PC)+(Rn)

注：(X)表示有存儲地址X或寄存器X的內容，請回答下列問題：

(1)、該指令系統(tǒng)最多可有多少指令?該計算機最多有多少個通用寄存器？(勤思教育)存儲地

址寄存器(MAR)和存儲數(shù)據(jù)寄存器(MDR)至少各需多少位？

⑵、轉移指令的目標地址范圍是多少？

(3)、若操作碼0010B表示加法操作(助記符為add),寄存器R4和R5得編號分別為100B何

101B,R4的內容為1234H,R5的內容為5678H,地址1234H中的內容為5678H,5678H中的

內容為1234H,則匯編語言為add(R4),(R5)(逗號前為源操作符，逗號后目的操作數(shù))

對應的機器碼是啥子(用十六進制)？該指令執(zhí)行后，(勤思教育)哪一些寄存器和存儲單位的

內容會改變?改變后的內容是啥子？

44、(12分)某計算機的主存地址空間大小為256M,按字節(jié)編址。指令Cache分散，均有8

個Cache行，每個Cache行大小為64MB,數(shù)據(jù)Cache采用直接映射體式格局，(勤思教育)

現(xiàn)有兩個功能相同的程序A和B,其偽代碼如下：

程序A：

inta[256][256]；

intsum_arrayl()

(

inti,j,sum=0；

for(i=0；i256；i++)

for(j=0；j256；j++)

sum+=a[i][j]；

returnsum；

}

程序B：

inta[256][256]；

intsum_array2（）

{

inti,j,sum=O；

for（j=0；j256；j++）

for（i=0；i256；i++）

sum+=a[i][j]；

returnsum；

}

假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i,j,sum均分配在寄存器中，數(shù)組a按

行優(yōu)先體式格局存放，其地址為320（十進制）。請回答，要求說明理由或給出計算過程。

（1）、若不考慮用于Cache一致維護和替換算法的控制位，則數(shù)據(jù)Cache的總容量為多少？

⑵、數(shù)組元素a[0][31]和各自所在的主存塊對應的Cache行號分別是多少（Cache

行號從0開始）

（3）、程序A和B得數(shù)據(jù)訪問命中率各是多少?哪個程序的執(zhí)行時間短？

45、（7分）假預設算機系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調度策略，施用2KB的內存空間記錄

16384個磁盤的余暇狀態(tài)

（1）、請說明在上述條件如何進行磁盤塊余暇狀態(tài)的管理。

⑵、設某單面磁盤的旋轉速度為每分鐘6000轉，（勤思教育）每個磁道有100個扇區(qū)，相臨

磁道間的平均移動的時間為1ms.

若在某時刻，感應磁頭位于100號磁道處，并沿著磁道號增大的方向移動（如下圖所示），磁

道號的哀求隊列為50,90,30,120對哀求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，

則讀完這個扇區(qū)點共需要多少時間？需要給出計算過程。

46）設某計算機的邏輯地址空間和物理地址空間均為64KB,按字節(jié)編址。（勤思教育）某進程

項最多需要6頁數(shù)據(jù)存儲空間，頁的大小為1KB,操作系統(tǒng)采用固定分配局部置換策略為此

進程項分配4個頁框。

頁號

頁框號

裝入時間

訪問位

07

1301

14

2301

22

2001

39

1601

當該進程項執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：

（1）、該邏輯地址對應的頁號時多少？

⑵、若采用先進先出（FIFO）置換算法，該邏輯地址對應的物理地址?要求給出計算過程。

(3)、采用時鐘(Clock)置換算法，該邏輯地址對應的物理地址是多少?要求給出計算過程。(設

搜索下一頁的指針按順時針方向移動，且指向當前2號頁框，示意圖如下)

47、(9分)某局域網(wǎng)采用C000A/CD和談實現(xiàn)介質訪問控制，數(shù)據(jù)傳輸率為100M/S,主機甲

和主機已經(jīng)的距離為2KM,信號傳播速速時200000M/S請回答下列問題，并給出計算過程。

(1)、若主機甲和主機已經(jīng)發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機均

檢測到?jīng)_突時刻為止，最短經(jīng)過多長時間?最長經(jīng)過多長時間？(假設主機甲和主機已經(jīng)發(fā)送

數(shù)據(jù)時、其它主機不發(fā)送數(shù)據(jù))

⑵、若網(wǎng)絡不存在任何沖突與失閃，主機甲總是以標準的最長以太數(shù)據(jù)幀(1518字節(jié))向主

機已經(jīng)發(fā)送數(shù)據(jù)，主機已經(jīng)每成功收到一個數(shù)據(jù)幀后，立即發(fā)送下一個數(shù)據(jù)幀，(勤思教育)

此時主機甲的有效數(shù)據(jù)傳輸速率是多少？(不考慮以太網(wǎng)幀的前導碼)

2010年計算機考研答案真題

第一題：選擇題答案：

1-5DCBCB

6-10AABAD

11-15ADCBD

16-20ADBAD

21-25ADACB

26-30AABBC

31-35CBCAA

36-40CBCAA

第二題：綜合題答案

41、

(1)因為裝填因子為0.7,數(shù)據(jù)總數(shù)為7,所以存儲空間長度為

L=7/0.7=10

因此可選T=10,構造的散列函數(shù)為

H(key)=(key*3)M0D10

線性探測再散列函數(shù)為：

Hi=(H(key)+di)MOD10,(di=l,2,3.9)

因此，各數(shù)據(jù)的下標為

H(7)=(7*3)M0D10=1H(8)=(8*3)MOD10=4H(30)=(30*3)MOD10=0H(11)=(11*3)MOD10=3

H(18)=(18*3)MOD10=4H1=(H(18)+1)MOD10=5H(9)=(9*3)MOD10=7H(14)=(14*3)MOD10=2

所構造的散列表如下：

01

23

45

67

89

307

14118

189

⑵查找成功的平均查找長度為：

ASLl=(l+l+l+l+2+l+l)/7=8/7

查找不成功的平均查找長度為：

ASL2=(7+6+5+4+3+2+1+2+1+1)=3.242、

(1)建立一個可以放下p個整兒的匡助隊列，將數(shù)組R中的前p個整兒依次進入匡助隊列，

將R中后面的n-p個整兒依次前移p個位置，將匡助隊列中的數(shù)據(jù)依次出隊，依次放入R

中第n-p個整兒開始的位置。

⑵施用c語言描述算法如下：

voidShift(int*pR,intn,intp)〃pR是指向數(shù)組R的指針,n為存放的整兒個數(shù),

//p為循環(huán)左移的個數(shù)

(

inttemp

;//匡助數(shù)組，存放要移出的整兒。

inti=0；

while(ip){〃將R中前p個數(shù)據(jù)存入匡助數(shù)組中。

temp[i]=pR[i]；

i++；

)

i=0；

while(in-p){〃將R中從第p個整兒開始的整兒前移p個位置。

pR[i]=pR[p+i]；

i++；

)

i=0；

while(ip){〃將匡助數(shù)組中的p個數(shù)據(jù)放到R中第n-p個數(shù)據(jù)的后面。

pR[n-p+i]=temp[i]；

i++;

}

return；

}

(3)所預設的算法的時間復雜度為0(n),空間復雜度為0(p)

4三、

(D0P字段占4個bit位，因此該指令系統(tǒng)最多有2~4=16條指令；Rs/Rd為3個bit,因此

最多有2~3=8個通用寄存器；128K/2=6妹=216,所以存儲器地址寄存器位數(shù)至少為16位，

指令字長度為16位，所以存儲器數(shù)據(jù)寄存器至少為16位。

⑵因為Rn是16位寄存器，所以可以尋址的目標地址范圍是64K,即全般存儲器空間。

(3)對應的機器碼是230DH,該指令執(zhí)行后R5的內容變?yōu)?679H，地址5678H的內容變?yōu)?8AC。

44.解題思緒：

(1)cache總容量等于cache每一行的容量乘以cache的行數(shù)。大家需要注意的是，本題cache

總容量分別等于數(shù)據(jù)cache和指令cache的全體。

⑵分別計算出A[0][1]的地址的值，然后按照直接映射體式格局除以cache行的大

小，與cache行數(shù)求余，所得的余數(shù)就是所映射的cache塊。

(3)cache的命中率等于訪問cache的次數(shù)除以cac