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

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

2、子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（）a、13，48b、24，48c、24，53d、24，905、在一棵度數(shù)為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、41b、82c、113d、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、6b、15

3、c、16d、218、對下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€數(shù)是（）a、4b、3c、2d、19、已知一個長度為16的順序表l，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（）a、4b、5c、6d、710、采用遞歸方式對順序表進(jìn)行快速排序，下列關(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)進(jìn)行排序，若前三趟排序結(jié)果如下：()第一趟

4、：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í)行時間的措施是()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位補(bǔ)碼分別表示r1=feh，r2=f2h，r3=90h，r4=f8h，若將運(yùn)算結(jié)果存放在一個8位寄存器中，則下列運(yùn)算會發(fā)生益處的是()a. r1 x r2b. r2 x r3c. r1 x r4d. r2 x r414.假定變量i

5、，f，d數(shù)據(jù)類型分別為int, float, double(int用補(bǔ)碼表示，float和double用ieee754單精度和雙精度浮點(diǎn)數(shù)據(jù)格式表示)，已知i=785，f=1.5678e3，d=1.5e100，若在32位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式，則結(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.假定用若干個2k x 4位芯片組成一個8k x 8為存儲器，則0b1fh所在芯片的最小地址是()a.0000

6、hb.0600hc.0700hd.0800h16.下列有關(guān)ram和rom得敘述中正確的是()i ram是易失性存儲器，rom是非易失性存儲器ii ram和rom都是采用隨機(jī)存取方式進(jìn)行信息訪問iii ram和rom都可用做cacheiv ram和rom都需要進(jìn)行刷新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未命

7、中18.下列寄存器中，反匯編語言程序員可見的是()a.存儲器地址寄存器(mar)b.程序計數(shù)器(pc)c.存儲區(qū)數(shù)據(jù)寄存器(mdr)d.指令寄存器(ir)19.下列不會引起指令流水阻塞的是()a.數(shù)據(jù)旁路b.數(shù)據(jù)相關(guān)c.條件轉(zhuǎn)移d.資源沖突20.下列選項(xiàng)中的英文縮寫均為總線規(guī)范的是()a. pci、crt、usb、eisab. isa、cpi、vesa、eisac. isa、scsi、ram、mipsd. isa、eisa、pci、pci-express21、單級中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（）i保護(hù)現(xiàn)場ii開中斷iii關(guān)中斷iv保存斷點(diǎn)v中斷事件處理vi恢復(fù)現(xiàn)場vii中斷返回a、i-v

8、-vi-ii-viib、iii-i-v-viic、iii-iv-v-vi-viid、iv-i-v-vi-vii22、假定一臺計算機(jī)的顯示存儲器用dram芯片實(shí)現(xiàn)，若要求顯示分辨率為1600*1200，顏色深度為24位，幀頻為85hz，現(xiàn)實(shí)總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為（）a、245mbpsb、979mbpsc、1958mbpsd、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í)行a、僅i和iib、僅ii和iiic、僅i和iii

9、d、i、ii、iii25、設(shè)與某資源相關(guān)聯(lián)的信號量初值為3，當(dāng)前值為1，若m表示該資源的可用個數(shù)，n表示等待該資源的進(jìn)程數(shù)，則m，n分別是（）a、0，1b、1，0c、1，2d、2，026、下列選項(xiàng)中，降低進(jìn)程優(yōu)先權(quán)級的合理時機(jī)是（）a、進(jìn)程的時間片用完b、進(jìn)程剛完成i/o，進(jìn)入就緒列隊c、進(jìn)程長期處于就緒列隊d、進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)27、進(jìn)行po和p1的共享變量定義及其初值為（）booleam turn=0。flag0=false。 flag1=false。若進(jìn)行p0和p1訪問臨界資源的類c代碼實(shí)現(xiàn)如下：void p0() / 進(jìn)程p0 void p1 () / 進(jìn)程

10、p1 while （true） while （true）flag0=true。 turn=1。 flag0=true。 turn=0。while flag1&(turn=1) while flag0&(turn=0)臨界區(qū)； 臨界區(qū)；flag0=false。 flag1=false。 則并發(fā)執(zhí)行進(jìn)程po和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ū)，不會出現(xiàn)“饑餓”現(xiàn)象28、某基于動態(tài)分區(qū)存儲經(jīng)管的計算機(jī)，其主存容量為55mb（初始為空）

11、，采用最佳適配（best fit）算法，分配和釋放的順序?yàn)椋悍峙?5mb，分配30mb，釋放15mb，分配6mb，此時主存中最大空閑分區(qū)的大小是（）a、7mbb、9mbc、10mbd、15mb29、某計算機(jī)采用二級頁表的分頁存儲經(jīng)管方式，按字節(jié)編制，頁大小為2（10）【2的10次方，下同】字節(jié)，頁表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為頁目錄號頁號頁內(nèi)偏移量邏輯地址空間大小為2（10）頁，則表示整個邏輯地址空間的頁目錄表中包含表項(xiàng)的個數(shù)至少是（）a、64b、128c、256d、51230設(shè)文件索引節(jié)點(diǎn)中有7個地址項(xiàng)，其中4個地址為直接地址索引，1個地址項(xiàng)是二級間接地址索引，每個地址項(xiàng)的大小為4字節(jié)，若

12、磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件最大長度是()a. 33kbb. 519kbc. 1057kbd. 16513kb31. 設(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é)議c.協(xié)議的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)d.每一層必須完成的功能34.在下圖所表示的采用”存儲-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中所

13、有的鏈路的數(shù)據(jù)傳輸速度為100mbps，分組大小為1000b，其中分組頭大小為20b若主機(jī)h1向主機(jī)h2發(fā)送一個大小為980000的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從h1發(fā)送到h2接受完為止，需要的時間至少是()a.80msb. 80.08msc. 80.16msd. 80.24ms35.某自治系統(tǒng)采用rip協(xié)議，若該自治系統(tǒng)內(nèi)的路由器r1收到其鄰居路由器r2的距離矢量中包含的信息，則可能得出的結(jié)論是()a. r2可以經(jīng)過r1到達(dá)net1，跳數(shù)為17b. r2可以到達(dá)net1，跳數(shù)為16c. r1可以經(jīng)過r2到達(dá)net1，跳數(shù)為17d.r1不能經(jīng)過r2到達(dá)net136.若路由器

14、r因?yàn)閾砣麃G棄ip分組，則此時r可向發(fā)出該ip分組的源主機(jī)的icmp報文件的類型是()a. 路由重定向b. 目的不可達(dá)c. 源抑制d. 超時37、某網(wǎng)絡(luò)的ip地址空間為/24采用長子網(wǎng)劃分，子網(wǎng)掩碼為48，則該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)為()a、32，8b、32，6c、8，32d、8，3038、下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風(fēng)暴的是（）i中斷器ii集線器iii網(wǎng)橋iv路由器a、僅i和iib、僅iiic、僅iii和ivd、僅iv39、主機(jī)甲和主機(jī)乙之間建立一個tcp連接，tcp最大段長度為1000字節(jié)，（勤思考研）若主機(jī)甲的當(dāng)

15、前擁塞窗口為4000字節(jié)，在主機(jī)甲向主機(jī)乙連續(xù)發(fā)送2個最大段后，成功收到主機(jī)乙發(fā)送的第一段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為2000字節(jié)，則此時主機(jī)甲還可以向主機(jī)乙發(fā)送的最大字節(jié)數(shù)是（）a、1000b、2000c、3000d、400040、如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解讀另一網(wǎng)絡(luò)某主機(jī)域名時，用戶主機(jī)本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為（）a、1條，1條b、1條，多條c、多條，1條d、多條，多條二、綜合應(yīng)用題：41-47小題，共70分41.（10分）將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲到散列表中，（勤思考研）散列表的存儲空間是一個下標(biāo)從0開始的一個一維數(shù)組

16、散列,函數(shù)為： h(key)=(key x 3)modt，處理沖突采用線性探測再散列法，要求裝載因子為0.7問題：(1).請畫出所構(gòu)造的散列表。(2).分別計算等概率情況下，查找成功和查找不成功的平均查找長度。42.（13分）設(shè)將n(n1)個整數(shù)存放到一維數(shù)組r中。設(shè)計一個在時間和空間兩方面盡可能高效的算法。將r中的序列循環(huán)左移p（0prn011b相對d(rn)轉(zhuǎn)移目標(biāo)地址=(pc)+(rn)注：(x)表示有存儲地址x或寄存器x的內(nèi)容，請回答下列問題：(1)、該指令系統(tǒng)最多可有多少指令該計算機(jī)最多有多少個通用寄存器？（勤思教育）存儲地址寄存器(mar)和存儲數(shù)據(jù)寄存器(mdr)至少各需多少位？

17、(2)、轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？(3)、若操作碼0010b表示加法操作(助記符為add)，寄存器r4和r5得編號分別為100b何101b，r4的內(nèi)容為1234h，r5的內(nèi)容為5678h，地址1234h中的內(nèi)容為5678h，5678h中的內(nèi)容為1234h，則匯編語言為add(r4)，(r5) (逗號前為源操作符，逗號后目的操作數(shù))對應(yīng)的機(jī)器碼是什么(用十六進(jìn)制)該指令執(zhí)行后，（勤思教育）哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么？44、(12分)某計算機(jī)的主存地址空間大小為256m，按字節(jié)編址。指令cache分離，均有8個cache行，每個cache行大小為64mb，數(shù)據(jù)cach

18、e采用直接映射方式，（勤思教育）現(xiàn)有兩個功能相同的程序a和b，其偽代碼如下：程序a:int sum_array1()int i, j, sum = 0。for (i = 0。 i 256。 i+)for (j= 0。 j 256。 j+)sum += aij。return sum。程序b:int sum_array2()int i, j, sum = 0。for (j = 0。 j 256。 j+)for (i= 0。 i 256。 i+)sum += aij。return sum。假定int類型數(shù)據(jù)用32位補(bǔ)碼表示，程序編譯時i，j，sum

19、均分配在寄存器中，數(shù)組a按行優(yōu)先方式存放，其地址為320(十進(jìn)制)。請回答，要求說明理由或給出計算過程。(1)、若不考慮用于cache一致維護(hù)和替換算法的控制位，則數(shù)據(jù)cache的總?cè)萘繛槎嗌?2)、數(shù)組元素a031和a11各自所在的主存塊對應(yīng)的cache行號分別是多少(cache行號從0開始)(3)、程序a和b得數(shù)據(jù)訪問命中率各是多少？哪個程序的執(zhí)行時間短？45、（7分）假設(shè)計算機(jī)系統(tǒng)采用cscan(循環(huán)掃描)磁盤調(diào)度策略,使用2kb的內(nèi)存空間記錄16384個磁盤的空閑狀態(tài)(1)、請說明在上述條件如何進(jìn)行磁盤塊空閑狀態(tài)的經(jīng)管。(2)、設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)，（勤思教育）每個

20、磁道有100個扇區(qū)，相臨磁道間的平均移動的時間為1ms.若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動(如下圖所示),磁道號的請求隊列為50，90，30，120對請求隊列中的每個磁道需讀取1個隨機(jī)分布的扇區(qū)，則讀完這個扇區(qū)點(diǎn)共需要多少時間？需要給出計算過程。46.(8分)設(shè)某計算機(jī)的邏輯地址空間和物理地址空間均為64kb，按字節(jié)編址。（勤思教育）某進(jìn)程最多需要6頁數(shù)據(jù)存儲空間，頁的大小為1kb，操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框。頁號頁框號裝入時間訪問位071301142301222001391601當(dāng)該進(jìn)程執(zhí)行到時刻260時，要訪問邏輯地址為17cah的數(shù)據(jù)

21、。請回答下列問題：(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ù)傳輸率為100m/s，主機(jī)甲和主機(jī)已的距離為2km，信號傳播速速時200000m/s請回答下列問題，并給出計算過程。（1）、若主機(jī)甲和主機(jī)已發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機(jī)均檢測到?jīng)_突時刻為止，最短經(jīng)過多長時間？

22、最長經(jīng)過多長時間？(假設(shè)主機(jī)甲和主機(jī)已發(fā)送數(shù)據(jù)時，其它主機(jī)不發(fā)送數(shù)據(jù))（2）、若網(wǎng)絡(luò)不存在任何沖突與差錯，主機(jī)甲總是以規(guī)范的最長以太數(shù)據(jù)幀(1518字節(jié))向主機(jī)已發(fā)送數(shù)據(jù)，主機(jī)已每成功收到一個數(shù)據(jù)幀后，立即發(fā)送下一個數(shù)據(jù)幀，（勤思教育）此時主機(jī)甲的有效數(shù)據(jù)傳輸速率是多少？(不考慮以太網(wǎng)幀的前導(dǎo)碼)答案1-5 d c b c b6-10 a a b a d11-15 a d c b d16-20 a d b a d21-25 a d a c b26-30 a a b b c31-35 c b c a a36-40 c b c a a41、(1)因?yàn)檠b填因子為0.7，數(shù)據(jù)總數(shù)為7，所以存儲空間長度

23、為l = 7/0.7 = 10因此可選t=10，構(gòu)造的散列函數(shù)為h(key) = (key*3) mod 10線性探測再散列函數(shù)為：hi = ( h(key)+ di ) mod 10 , (di = 1,2,3.9)因此，各數(shù)據(jù)的下標(biāo)為h(7) = (7*3) mod 10 = 1h(8) = (8*3) mod 10 = 4h(30) = (30*3) mod 10 = 0h(11) = (11*3) mod 10 = 3h(18) = (18*3) mod 10 = 4h1 = ( h(18) +1) mod 10 = 5h(9) = (9*3) mod 10 = 7h(14) = (1

24、4*3) mod 10 = 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ù)依次進(jìn)入輔助隊列，將r中后面的n-p個整數(shù)依次前移p個位置，將輔助隊列中的數(shù)據(jù)依次出隊，依次放入r中第n-p個整數(shù)開始的位置。（2）使用c語言描述算法如下：void shift(int *pr, int n, int p) /pr是指向數(shù)組r的指針，

25、n為存放的整數(shù)個數(shù)，/p為循環(huán)左移的個數(shù)int tempp。 / 輔助數(shù)組，存放要移出的整數(shù)。int i=0。while(ip) /將r中前p個數(shù)據(jù)存入輔助數(shù)組中。tempi = pri。i+。i = 0。while(i n-p) /將r中從第p個整數(shù)開始的整數(shù)前移p個位置。pri = prp+i。i+。i = 0。while(i p) /將輔助數(shù)組中的p個數(shù)據(jù)放到r中第n-p個數(shù)據(jù)的后面。prn-p+i = tempi。i+。return。（3）所設(shè)計的算法的時間復(fù)雜度為o(n),空間復(fù)雜度為o(p)43、（1）op字段占4個bit位，因此該指令系統(tǒng)最多有24 = 16條指令；rs/rd為3

26、個bit，因此最多有23 = 8 個通用寄存器；128k/2 = 64k = 216,所以存儲器地址寄存器位數(shù)至少為16位，指令字長度為16位，所以存儲器數(shù)據(jù)寄存器至少為16位。（2）因?yàn)閞n是16位寄存器，所以可以尋址的目標(biāo)地址范圍是64k，即整個存儲器空間。（3）對應(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的總和。（2）分別計算出a031a11的地址的值，然后根據(jù)直接映射方式除以cache行的大小，與cache行數(shù)求余，所得的余數(shù)就是所映射的cache塊。（3）cache的命中率等于訪問cache的次數(shù)除以cache的次數(shù)加上訪問內(nèi)存的次數(shù)。本題通過計算得知，命中率高的計算速度快。45、（1）2kb = 2*1024*8bit = 16384bit。因此可以使用位圖法進(jìn)行磁盤塊空閑狀