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

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

一、單選題

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

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

A：dcebfaB：cbdaefC：dbcaefD：afedcb

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

序是（）

A：bacdeB：dbaceC：dbcaeD：ecbad

3、下列線(xiàn)索二叉樹(shù)中（用虛線(xiàn)表示線(xiàn)索），符合后序線(xiàn)索樹(shù)定義的是（）

4、在下列所示的平衡二叉樹(shù)中插入關(guān)鍵字48后得到一棵新平衡二叉樹(shù),在新平衡二叉樹(shù)中,

關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（）

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

5、在一棵度為4的樹(shù)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)，則樹(shù)T的葉節(jié)點(diǎn)個(gè)數(shù)是（）

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

6、對(duì)n（n大于等于2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的敘述中，錯(cuò)誤的是

（）

A：該樹(shù)一定是一棵完全二叉樹(shù)B：樹(shù)中?定沒(méi)有度為1的結(jié)點(diǎn)

C：樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D：樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一

任一結(jié)點(diǎn)的權(quán)值

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

數(shù)最少是（）

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

8、對(duì)下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是()

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

9、已知一個(gè)長(zhǎng)度為16的順序表L,其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)

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

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

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

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

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

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

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

11、對(duì)一組數(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：歸并排序I)：基數(shù)排序

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

1提高CPU時(shí)鐘頻率，II優(yōu)化數(shù)據(jù)通過(guò)結(jié)構(gòu)，HI對(duì)程序進(jìn)行編譯優(yōu)化

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

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

存放在一個(gè)8位的寄存器中，則下列運(yùn)算會(huì)發(fā)生溢出的是()

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

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

分別用IEEE754單精度和雙精度浮點(diǎn)數(shù)據(jù)格式表示)，已知i=785,f=l.5678,d=L5若在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=f

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

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

是()

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

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

1、RAM是易失性存儲(chǔ)器，ROM是非易失性存儲(chǔ)器

II、RAM和ROM都是采用隨機(jī)存取的方式進(jìn)行信息訪問(wèn)

IlkRAM和ROM都可用作Cache

IV、RAM和ROM都需要進(jìn)行刷新

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

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

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

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

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

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

18、下列存儲(chǔ)器中，匯編語(yǔ)言程序員可見(jiàn)的是()

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

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

D.指令寄存器(IR)

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

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

B.數(shù)據(jù)相關(guān)

C.條件轉(zhuǎn)移

D.資源沖突

20.下列選項(xiàng)中的英文縮寫(xiě)均為總線(xiàn)標(biāo)準(zhǔn)的是()

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

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

I保護(hù)現(xiàn)場(chǎng)

II開(kāi)中斷

III關(guān)中斷

IV保存斷點(diǎn)

V中斷事件處置懲罰

VI恢復(fù)現(xiàn)場(chǎng)

VII中斷歸回

A、I-V-VI-II-VIIB、III-I-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,現(xiàn)實(shí)總帶寬的50%用來(lái)刷新熒幕，則需要的顯存總帶寬至少約為()

A、245MbpsB、979MbpsC、1958MbpsD、7834Mbps2三、下列選項(xiàng)中，操作S供給的給應(yīng)

程序的接口是()

A、系統(tǒng)挪用

B、中斷

C、庫(kù)函數(shù)

D、原語(yǔ)

24、下列選項(xiàng)中，導(dǎo)制創(chuàng)進(jìn)新進(jìn)程項(xiàng)的操作是()

I用戶(hù)登陸成功II設(shè)備分配IH啟動(dòng)程序執(zhí)行

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

號(hào)量初值為3,當(dāng)前值為1,若M表示該資源的可用個(gè)數(shù)，N表示等待該資源的進(jìn)程項(xiàng)數(shù)，

則M,N分別是()

A、0,1B、1,0C、1,2D、2,026、下列選項(xiàng)中，降低進(jìn)程項(xiàng)優(yōu)先權(quán)級(jí)的合理機(jī)會(huì)是()

A、進(jìn)程項(xiàng)的時(shí)間片用完

B、進(jìn)程項(xiàng)剛完成I/O,進(jìn)入就緒列隊(duì)

C、進(jìn)程項(xiàng)持久處于就緒列隊(duì)

D、進(jìn)程項(xiàng)從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)

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

boolean)flag[2]；

intturn=0；

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

若進(jìn)行P0和Pl訪問(wèn)臨界資源的類(lèi)C代碼實(shí)現(xiàn)如下：

voidp0()〃進(jìn)程項(xiàng)p0voidpl()〃進(jìn)程項(xiàng)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í)行進(jìn)程項(xiàng)PO和P1時(shí)產(chǎn)生的情況是()

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

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

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

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

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

Fit)算法,分配和釋放的順序?yàn)椋悍峙?5Mb,分配30Mb,釋放15法,分配6Mb,此時(shí)主存

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

A、7MbB、9MbC.10MbD、15Mb29、某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理體式格局，按

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

構(gòu)為

頁(yè)目次號(hào)

頁(yè)號(hào)

蟲(chóng)內(nèi)偏移量

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

是()

A、64B、128C、2561)、51230.設(shè)文件索引節(jié)點(diǎn)中有7個(gè)地址項(xiàng)，此中4個(gè)地址為直接地

址索引，1個(gè)地址項(xiàng)是二級(jí)間接地址索引，每個(gè)地址項(xiàng)的大小為4字節(jié)，若磁盤(pán)索引塊和磁

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

A.33KBB.519KBC.1057KBD.16513KB31.設(shè)當(dāng)前工作目次的主要目的是0

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

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

C.加快文件的檢索速度

D.加快文件的讀寫(xiě)速度

32.本地用戶(hù)通過(guò)鍵盤(pán)登陸系統(tǒng)是，起首獲得鍵盤(pán)輸入信息的程序時(shí)0

A.號(hào)令解釋程序

B.中斷處置懲罰程序

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

D.用戶(hù)登錄程序

33.下列選項(xiàng)中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是0

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

B.每一層施用的和談

C.和談的內(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è)大

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

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

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

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

0

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

到達(dá)netl,跳數(shù)為17D.R1不能經(jīng)過(guò)R2到達(dá)netl36.若路由器R因?yàn)閾砣麃G棄IP分組，

則此時(shí)R可向發(fā)出該IP分組的源主機(jī)的ICMP報(bào)文件的類(lèi)型是()

A.路由重定向

B.目的不可達(dá)

C.源抑制

D.超時(shí)

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

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

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

I中斷器

II集線(xiàn)器

III網(wǎng)橋

IV路由器

A、僅I和IIB、僅inC、僅HI和IVD、僅IV39、主機(jī)甲和主機(jī)乙之間建立一個(gè)TCP

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

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

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

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

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

A、1條，1條

B、1條，多條

C、多條，1條

D、多條，多條

二、綜合應(yīng)用題：41-47小題，共70分

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

列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開(kāi)始的一個(gè)一維數(shù)組散列，函數(shù)為：H(key)=(keyx3)M0DT,

處置懲罰沖突采用線(xiàn)性探測(cè)再散列法，要求裝載因子為0.7

問(wèn)題：

(1).請(qǐng)畫(huà)出所構(gòu)造的散列表。

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

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

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

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

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

⑵、按照預(yù)設(shè)思想，采用C或C++或JAVA語(yǔ)言描述算法，關(guān)鍵的地方給出注釋。

(3)、說(shuō)明你所預(yù)設(shè)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

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

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

151211650

OPM5R5MdRd

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

轉(zhuǎn)移指令采用相對(duì)尋址，相對(duì)偏移是用補(bǔ)碼表示，尋址體式格局定義如下：

Ms/Md

尋址體式格局

助記符

含義

000B

寄存器直接

Rn

操作數(shù)=(Rn)

001B

寄存器間接

(Rn)

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

010B

寄存器間接、自增

(Rn)+

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

相對(duì)

D(Rn)

轉(zhuǎn)移目標(biāo)地址=(PC)+(Rn)

注：(X)表示有存儲(chǔ)地址X或寄存器X的內(nèi)容，請(qǐng)回答下列問(wèn)題：

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

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

⑵、轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？

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

101B,R4的內(nèi)容為1234H,R5的內(nèi)容為5678H,地址1234H中的內(nèi)容為5678H,5678H中的

內(nèi)容為1234H,則匯編語(yǔ)言為add(R4),(R5)(逗號(hào)前為源操作符，逗號(hào)后目的操作數(shù))

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

內(nèi)容會(huì)改變?改變后的內(nèi)容是啥子？

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

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

現(xiàn)有兩個(gè)功能相同的程序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類(lèi)型數(shù)據(jù)用32位補(bǔ)碼表示，程序編譯時(shí)i,j,sum均分配在寄存器中，數(shù)組a按

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

（1）、若不考慮用于Cache一致維護(hù)和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘繛槎嗌伲?/p>

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

行號(hào)從0開(kāi)始）

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

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

16384個(gè)磁盤(pán)的余暇狀態(tài)

（1）、請(qǐng)說(shuō)明在上述條件如何進(jìn)行磁盤(pán)塊余暇狀態(tài)的管理。

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

磁道間的平均移動(dòng)的時(shí)間為1ms.

若在某時(shí)刻，感應(yīng)磁頭位于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ì)算過(guò)程。

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

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

進(jìn)程項(xiàng)分配4個(gè)頁(yè)框。

頁(yè)號(hào)

頁(yè)框號(hào)

裝入時(shí)間

訪問(wèn)位

07

1301

14

2301

22

2001

39

1601

當(dāng)該進(jìn)程項(xiàng)執(zhí)行到時(shí)刻260時(shí)，要訪問(wèn)邏輯地址為17CAH的數(shù)據(jù)。請(qǐng)回答下列問(wèn)題：

（1）、該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)時(shí)多少？

⑵、若采用先進(jìn)先出（FIFO）置換算法，該邏輯地址對(duì)應(yīng)的物理地址?要求給出計(jì)算過(guò)程。

(3)、采用時(shí)鐘(Clock)置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少?要求給出計(jì)算過(guò)程。(設(shè)

搜索下一頁(yè)的指針按順時(shí)針?lè)较蛞苿?dòng)，且指向當(dāng)前2號(hào)頁(yè)框，示意圖如下)

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

和主機(jī)已經(jīng)的距離為2KM,信號(hào)傳播速速時(shí)200000M/S請(qǐng)回答下列問(wèn)題，并給出計(jì)算過(guò)程。

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

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

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

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

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

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

2010年計(jì)算機(jī)考研答案真題

第一題：選擇題答案：

1-5DCBCB

6-10AABAD

11-15ADCBD

16-20ADBAD

21-25ADACB

26-30AABBC

31-35CBCAA

36-40CBCAA

第二題：綜合題答案

41、

(1)因?yàn)檠b填因子為0.7,數(shù)據(jù)總數(shù)為7,所以存儲(chǔ)空間長(zhǎng)度為

L=7/0.7=10

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

H(key)=(key*3)M0D10

線(xiàn)性探測(cè)再散列函數(shù)為：

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

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

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

所構(gòu)造的散列表如下：

01

23

45

67

89

307

14118

189

⑵查找成功的平均查找長(zhǎng)度為：

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

查找不成功的平均查找長(zhǎng)度為：

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

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

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

中第n-p個(gè)整兒開(kāi)始的位置。

⑵施用c語(yǔ)言描述算法如下：

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

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

(

inttemp

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

inti=0；

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

temp[i]=pR[i]；

i++；

)

i=0；

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

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

i++；

)

i=0；

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

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

i++;

}

return；

}

(3)所預(yù)設(shè)的算法的時(shí)間復(fù)雜度為0(n),空間復(fù)雜度為0(p)

4三、

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

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

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

⑵因?yàn)镽n是16位寄存器，所以可以尋址的目標(biāo)地址范圍是64K,即全般存儲(chǔ)器空間。

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

44.解題思緒：

(1)cache總?cè)萘康扔赾ache每一行的容量乘以cache的行數(shù)。大家需要注意的是，本題cache

總?cè)萘糠謩e等于數(shù)據(jù)cache和指令cache的全體。

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

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

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