計算機考研專業(yè)課真題及答案解析

1、一、單項選擇題：1-40題，每題20分共80分。在每個小題給出的四個選項中選正確答案。1、若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（）A、dcebfaB、cbdaefC、bcaefdDafedcb2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順順序是（）AbacdeBdbaceCdbcaeDecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保

2、存的關(guān)鍵字分別是（）A13,48B、24,48C、24,53D24,905、在一棵度數(shù)為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉結(jié)點個數(shù)是（）A41B、82C、113D1226、對n（n=2）個權(quán)值均不相同的字符構(gòu)成哈弗曼樹，關(guān)于該樹的敘述中，錯誤的是（）A、該樹一定是一棵完全二交叉B、樹中一定沒有度為1的結(jié)點C、樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值7、若無向圖G=（V.E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（）A6B、15C、16D218、對下

3、圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是（）A4B、3C、2D19、已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（）A4B、5C、610、采用遞歸方式對順序表進行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（）A、遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關(guān)B、每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)（勤思考研）C、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)11、對一組數(shù)據(jù)（2,12,16,88,5,10）進行排序，若前三趟排序結(jié)果如下：（）第一趟：2,12,16,5,10,88第二趟

4、：2,12,5,10,16,88第三趟：2,5,10,12,16,88則采用的排序方法可能是A.冒泡排序法B.希爾排序法C.歸并排序法D.基數(shù)排序法12.下列選項中，能縮短程序執(zhí)行時間的措施是（）1.提高CPU寸鐘頻率2.優(yōu)化通過數(shù)據(jù)結(jié)構(gòu)3.優(yōu)化通過程序A.僅1和2B.僅1和3C,僅2和3D.1,2,313.假定有4個整數(shù)用8位補碼分別表示r1=FEHr2=F2H,r3=90H,r4=F8H,若將運算結(jié)果存放在一個8位寄存器中，則下列運算會發(fā)生益處的是（）A. r1xr2B. r2xr3C. r1xr4D. r2xr414.假定變量i,f,d數(shù)據(jù)類型分別為int,float,double（in

5、t用補碼表示，float和double用IEEE754單精度和雙精度浮點數(shù)據(jù)格式表示）,已知i=785,f=1.5678e3,d=1.5e100,若在32位機器中執(zhí)行下列關(guān)系表達式，則結(jié)果為真的是()(I)i=(int)(float)I(II)f=(float)(int)f(III)f=(float)(double)f(IV)(d+f)-d=fA.僅I和IIB.僅I和IIIC.僅II和IIID.僅III和IV15 .假定用若干個2Kx4位芯片組成一個8Kx8為存儲器，則0B1FHff在芯片的最小地址是()A.0000HB.0600HC.0700HD.0800H16 .下列有關(guān)RAMf口ROW敘

6、述中正確的是()IRAM是易失性存儲器,ROMI1非易失性存儲器IIRAM和ROM?是采用隨機存取方式進行信息訪問III RAM和ROMfB可用做CacheIV RAM和ROMfB需要進行刷新A.僅I和IIB.僅II和IIIC.僅I,II,IIID,僅II,III,IV17 .下列命令組合情況，一次訪存過程中，不可能發(fā)生的是（）A.TLB未命中，Cache未命中，Page未命中B.TLB未命中，Cache命中，Page命中C.TLB命中，Cache未命中，Page命中D.TLB命中，Cache命中，Page未命中18 .下列寄存器中，反匯編語言程序員可見的是（）A.存儲器地址寄存器（MAR）B

7、.程序計數(shù)器（PC）C.存儲區(qū)數(shù)據(jù)寄存器（MDR）D.指令寄存器（IR）19.下列不會引起指令流水阻塞的是（）A.數(shù)據(jù)旁路B.數(shù)據(jù)相關(guān)C.條件轉(zhuǎn)移D.資源沖突20.下列選項中的英文縮寫均為總線規(guī)范的是（）A. PCI、CRTUSBEISAB. ISA、CPI、VESAEISAC. ISA、SCSIRAMMIPSD. ISA、EISAPCI、PCI-Express21、單級中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（）I保護現(xiàn)場II開中斷III關(guān)中斷IV保存斷點V中斷事件處理VI恢復(fù)現(xiàn)場VII中斷返回A、I-V-VI-II-VIIB、III-I-V-VIIC、III-IV-V-VI-VIIDIV-I-V

8、-VI-VII22、假定一臺計算機的顯示存儲器用DRAMS片實現(xiàn)，若要求顯示分辨率為1600*1200,顏色深度為24位，幀頻為85HZ；現(xiàn)實總帶寬的50刈來刷新屏幕,則需要的顯存總帶寬至少約為（）A245MbpsB、979MbpsC、1958MbpsD7834Mbps23、下列選項中，操作S提供的給應(yīng)程序的接口是（）A、系統(tǒng)調(diào)用B、中斷C、庫函數(shù)D原語24、下列選項中，導(dǎo)制創(chuàng)進新進程的操作是（）I用戶登陸成功II設(shè)備分配III啟動程序執(zhí)行A、僅I和IIB、僅II和IIIC、僅I和IIIDI、II、III25、設(shè)與某資源相關(guān)聯(lián)的信號量初值為3,當前值為1,若M表示該資源的可用個數(shù)，N表示等待該

9、資源的進程數(shù)，則MN分別是()A、0,1B、1,0C、1,2D2,026、下列選項中，降低進程優(yōu)先權(quán)級的合理時機是()A進程的時間片用完B、進程岡I完成I/O,進入就緒列隊C、進程長期處于就緒列隊D進程從就緒狀態(tài)轉(zhuǎn)為運行狀態(tài)27、進行PO和P1的共享變量定義及其初值為()booleamflag2。intturn=0。flag0=false。flag1=false。若進行P0和P1訪問臨界資源的類C代碼實現(xiàn)如下：voidp0()進程p0voidp1()/進程p1while(TRUEwhile(TRUEflag0=TRUE。turn=1。flag0=TRUE。turn=0。Whileflag1&(

10、turn=1)Whileflag0&(turn=0)臨界區(qū)；臨界區(qū)；flag0=FALSE。flag1=FALSE。）則并發(fā)執(zhí)行進程PO和P1時產(chǎn)生的情況是（）A、不能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B、不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C、能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象28、某基于動態(tài)分區(qū)存儲經(jīng)管的計算機，其主存容量為55Mb（初始為空），采用最佳適配（BestFit）算法，分配和釋放的順序為：分配15Mb分配30Mb釋放15Mb分配6Mb此時主存中最大空閑分區(qū)的大小是（）A、7MbB、9MbC、10MbD

11、15Mb29、某計算機采用二級頁表的分頁存儲經(jīng)管方式，按字節(jié)編制，頁大小為2（10）【2的10次方，下同】字節(jié)，頁表項大小為2字節(jié)，邏輯地址結(jié)構(gòu)為頁目錄號頁號頁內(nèi)偏移量邏輯地址空間大小為2（10）頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是（）A、64B、128C、256D51230.設(shè)文件索引節(jié)點中有7個地址項，其中4個地址為直接地址索引，1個地址項是二級間接地址索引，每個地址項的大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件最大長度是（）A. 33KBB. 519KBC. 1057KBD. 16513KB31 .設(shè)當前工作目錄的主要目的是（）A.

12、節(jié)省外存空間B.節(jié)省內(nèi)存空間C.加快文件的檢索速度D.加快文件的讀寫速度32 .本地用戶通過鍵盤登陸系統(tǒng)是，首先獲得鍵盤輸入信息的程序時（）A.命令解釋程序B.中斷處理程序C.系統(tǒng)調(diào)用程序D.用戶登錄程序33 .下列選項中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是（）A.網(wǎng)絡(luò)的層次B.每一層使用的協(xié)議C.協(xié)議的內(nèi)部實現(xiàn)細節(jié)D.每一層必須完成的功能34.在下圖所表示的采用存儲-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中所有的鏈路的數(shù)據(jù)傳輸速度為100Mbps分組大小為1000B,其中分組頭大小為20B若主機H1向主機H2發(fā)送一個大小為980000的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送到H2接受完

13、為止，需要的時間至少是（）A.80msB. 80.08msC. 80.16msD. 80.24ms35 .某自治系統(tǒng)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含的信息,則可能得出的結(jié)論是（）A. R2可以經(jīng)過R1到達net1,跳數(shù)為17B. R2可以到達net1,跳數(shù)為16C. R1可以經(jīng)過R2到達net1,跳數(shù)為17D.R1不能經(jīng)過R2到達net136 .若路由器R因為擁塞丟棄IP分組，則此時R可向發(fā)出該IP分組的源主機的ICMP報文件的類型是（）A.路由重定向B.目的不可達C.源抑制D.超時37、某網(wǎng)絡(luò)的IP地址空間為192.168.5.0/24采用長子網(wǎng)

14、劃分，子網(wǎng)掩碼為255.255.255.248,則該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)為（）A、32,8B、32,6C、8,32D8,3038、下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風暴的是（）I中斷器II集線器III網(wǎng)橋IV路由器A、僅I和IIB、僅IIIC、僅III和IVD僅IV39、主機甲和主機乙之間建立一個TCP接，TCRR大段長度為1000字節(jié)，（勤思考研）若主機甲的當前擁塞窗口為4000字節(jié)，在主機甲向主機乙連續(xù)發(fā)送2個最大段后，成功收到主機乙發(fā)送的第一段的確認段，確認段中通告的接收窗口大小為2000字節(jié)，則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是（）A1000B、2000

15、C、3000D400040、如果本地域名服務(wù)無緩存，當采用遞歸方法解讀另一網(wǎng)絡(luò)某主機域名時，用戶主機本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為（）A1條，1條B、1條，多條C、多條，1條D多條，多條二、綜合應(yīng)用題：41-47小題，共70分41. （10分）將關(guān)鍵字序列（7、8、30、11、18、9、14）散列存儲到散列表中，（勤思考研）散列表的存儲空間是一個下標從0開始的一個一維數(shù)組散列，函數(shù)為：H（key）=（keyx3）MODT,處理沖突采用線性探測再散列法，要求裝載因子為0.7問題：(1) .請畫出所構(gòu)造的散列表。(2),分別計算等概率情況下，查找成功和查找不成功的平均查找長度。42. (1

16、3分)設(shè)將n(n1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個在時間和空間兩方面盡可能高效的算法。將R中的序列循環(huán)左移P(0PRn011B相對D(Rn)轉(zhuǎn)移目標地址=(PC)+(Rn)注：(X)表示有存儲地址X或寄存器X的內(nèi)容，請回答下列問題：(1)、該指令系統(tǒng)最多可有多少指令該計算機最多有多少個通用寄存器？(勤思教育)存儲地址寄存器(MAR劑存儲數(shù)據(jù)寄存器(MDR片少各需多少位？(2)、轉(zhuǎn)移指令的目標地址范圍是多少？、若操作碼0010B表示加法操作(助記符為add),寄存器R4和R5得編號分別為100B何101B,R4的內(nèi)容為1234H,R5的內(nèi)容為5678H地址1234H中的內(nèi)容為5678H,56

17、78H中的內(nèi)容為1234H,則匯編語言為add(R4),(R5)(逗號前為源操作符，逗號后目的操作數(shù))對應(yīng)的機器碼是什么(用十六進制)該指令執(zhí)行后，(勤思教育)哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么？44、（12分）某計算機的主存地址空間大小為256M按字節(jié)編址。指令Cache分離,均有8個Cache行，每個Cache行大小為64MB數(shù)據(jù)Cache采用直接映射方式，（勤思教育）現(xiàn)有兩個功能相同的程序A和B,其偽代碼如下：程序A:inta256256。intsum_array1()(inti,j,sum=0。for(i=0。i256。i+)for(j=0。j256。j+)sum+=

18、aij。returnsum。程序B:inta256256。intsum_array2()(inti,j,sum=0。for(j=0。j256。j+)for(i=0。i256。i+)sum+=aij。returnsum。假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i,j,sum均分配在寄存器中，數(shù)組a按行優(yōu)先方式存放，其地址為320(十進制)。請回答，要求說明理由或給出計算過程。(1)、若不考慮用于Cache一致維護和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘繛槎嗌?2)、數(shù)組元素a031和a11各自所在的主存塊對應(yīng)的Cache行號分別是多少(Cache行號從0開始)(3)、程序A和B得數(shù)據(jù)訪

19、問命中率各是多少？哪個程序的執(zhí)行時間短？45、(7分)假設(shè)計算機系統(tǒng)采用CSCAN環(huán)掃描)磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤的空閑狀態(tài)(1)、請說明在上述條件如何進行磁盤塊空閑狀態(tài)的經(jīng)管。(2)、設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)，(勤思教育)每個磁道有100個扇區(qū)，相臨磁道間的平均移動的時間為1ms.若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動(如下圖所示)，磁道號的請求隊列為50,90,30,120對請求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，則讀完這個扇區(qū)點共需要多少時間？需要給出計算過程。46.(8分)設(shè)某計算機的邏輯地址空間和物理地址空間

20、均為64KB按字節(jié)編址。(勤思教育)某進程最多需要6頁數(shù)據(jù)存儲空間，頁的大小為1KB,操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框。頁號頁框號裝入時間訪問位071301142301222001391601當該進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH勺數(shù)據(jù)。請回答下列問題：(1)、該邏輯地址對應(yīng)的頁號時多少(2)、若采用先進先出(FIFO)置換算法，該邏輯地址對應(yīng)的物理地址？要求給出計算過程。(3)、采用時鐘(Clock)置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。(設(shè)搜索下一頁的指針按順時針方向移動，且指向當前2號頁框，示意圖如下）47、（9分）某局域網(wǎng)采用C

21、SMA/CD、議實現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸率為100M/S,主機甲和主機已的距離為2KM信號傳播速速時200000M/S請回答下列問題，并給出計算過程。（1）、若主機甲和主機已發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機均檢測到?jīng)_突時刻為止，最短經(jīng)過多長時間？最長經(jīng)過多長時間？（假設(shè)主機甲和主機已發(fā)送數(shù)據(jù)時，其它主機不發(fā)送數(shù)據(jù)）（2）、若網(wǎng)絡(luò)不存在任何沖突與差錯，主機甲總是以規(guī)范的最長以太數(shù)據(jù)幀（1518字節(jié)）向主機已發(fā)送數(shù)據(jù)，主機已每成功收到一個數(shù)據(jù)幀后，立即發(fā)送下一個數(shù)據(jù)幀，（勤思教育）此時主機甲的有效數(shù)據(jù)傳輸速率是多少？（不考慮以太網(wǎng)幀的前導(dǎo)碼）答案1-5DCBCB6-10AA

22、BAD11-15ADCBD16-20ADBAD21-25ADACB26-30AABBC31-35CBCAA36-40CBCAA41、(1)因為裝填因子為0.7,數(shù)據(jù)總數(shù)為7,所以存儲空間長度為L=7/0.7=10因此可選T=10,構(gòu)造的散列函數(shù)為H(key)=(key*3)MOD10線性探測再散列函數(shù)為：Hi=(H(key)+di)MOD10,(di=1,2,3.9)因此，各數(shù)據(jù)的下標為H(7)=(7*3)MOD10=1H(8)=(8*3)MOD10=4H(30)=(30*3)MOD10=0H(11)=(11*3)MOD10=3H(18)=(18*3)MOD10=4H1=(H(18)+1)MO

23、D10=5H(9)=(9*3)MOD10=7H(14)=(14*3)MOD10=2所構(gòu)造的散列表如下:012345678930714118189(2)查找成功的平均查找長度為：ASL1=(1+1+1+1+2+1+1)/7=8/7查找不成功的平均查找長度為：ASL2=(7+6+5+4+3+2+1+2+1+1)=3.242、(1)建立一個可以放下p個整數(shù)的輔助隊列，將數(shù)組R中的前p個整數(shù)依次進入輔助隊列，將R中后面的n-p個整數(shù)依次前移p個位置，將輔助隊列中的數(shù)據(jù)依次出隊，依次放入R中第n-p個整數(shù)開始的位置。(2)使用c語言描述算法如下：voidShift(int*pR,intn,intp)/p

24、R是指向數(shù)組R的指針，n為存放的整數(shù)個數(shù)，/p為循環(huán)左移的個數(shù)inttempp。/輔助數(shù)組，存放要移出的整數(shù)。inti=0owhile(ip)/將R中前p個數(shù)據(jù)存入輔助數(shù)組中。tempi=pRi。i+oi=0owhile(in-p)/將R中從第p個整數(shù)開始的整數(shù)前移p個位置。pRi=pRp+i。i+o)i=0owhile(ip)/將輔助數(shù)組中的p個數(shù)據(jù)放到R中第n-p個數(shù)據(jù)的后面pRn-p+i=tempi。i+o)return。)(3)所設(shè)計的算法的時間復(fù)雜度為O(n),空間復(fù)雜度為O(p)43、(1) OP?段占4個bit位，因此該指令系統(tǒng)最多有2A4=16條指令；Rs/Rd為3個bit,因

25、此最多有2A3=8個通用寄存器；128K/2=64k=2A16,所以存儲器地址寄存器位數(shù)至少為16位，指令字長度為16位，所以存儲器數(shù)據(jù)寄存器至少為16位。(2)因為Rn是16位寄存器，所以可以尋址的目標地址范圍是64K,即整個存儲器空間。(3)對應(yīng)的機器碼是230DH該指令執(zhí)行后R5的內(nèi)容變?yōu)?679H,地址5678H的內(nèi)容變?yōu)?8AG44、 解題思路：(1) cache總?cè)萘康扔赾ache每一行的容量乘以cache的行數(shù)。大家需要注意的是，本題cache總?cè)萘糠謩e等于數(shù)據(jù)cache和指令cache的總和。(2)分別計算出A031A11的地址的值，然后根據(jù)直接映射方式除以cache行的大小，與cache行數(shù)求余，所得的余數(shù)就是所映射的cache塊。(3) cache的命中率等于訪問cache的次數(shù)除以cache的次數(shù)加上訪問內(nèi)存的次數(shù)。本題通過計算得知，命中率高的計算速度快。45、(1) 2KB=2*1024*8bit=16