考研計算機學(xué)科專業(yè)基礎(chǔ)綜合-17（總分：150.00，做題時間：90分鐘）一、單項選擇題（總題數(shù)：40，分數(shù)：80.00）1?棧S最多只能容納4個元素，現(xiàn)在6個元素按A,B,C,D,E,F的順序進棧，下列哪一個序列是可能的出棧序列（）?A．EDCBAFB．BCEFADC．CBEDAFD．ADFEBC（分數(shù)：2.00）A.B.丿D.解析：由于棧只能容納4個元素，所以一次進棧最多4個，即ABCD同時在棧中，則EDCBAF不可能，E和F還沒有進棧就已經(jīng)出棧，B中的D元素不可能出棧在A的后面。D中最后兩個元素出棧順序也有誤。2?有A,B,C,D,E5個元素按次序入棧，在各種可能的出棧次序中，以元素C,D最先出棧的序列中，下列正確的一組是（）。A．CDBAECDABEB．CDEBACDBEAC．CDEABCDABED．CEBAECDAEB（分數(shù)：2.00）A.丿C.D.解析：要使得CD作為第一、二個元素出棧，應(yīng)是A、B、C先入棧，C出棧，D入棧，D出棧；接著就剩下A、B在棧中，E未入棧，共3個元素，此三者序列為BAE,BEA,EBA。3.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是（）。A．39B．52C．111D．119（分數(shù)：2.00）A.B.丿D.解析：4?將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和v可能具有的關(guān)系是（）。I?父子關(guān)系兄弟關(guān)系u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系只有IIB.I和IIC.I和IID.I、II和III分數(shù)：2.00）A.丿C.D.解析：5?線索化的二叉樹中，某結(jié)點*戸沒有孩子的充要條件是（）。p-〉lchild=NULLB.p-〉ltag=l&&p-〉rtag=lC.p-〉ltag=OD.p-〉lchild=NULL&&p-〉ltag=l（分數(shù)：2.00）A.丿C.D.解析：參考線索二叉樹的定義。6.設(shè)二叉排序樹中關(guān)鍵字由1?1000的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點，下列關(guān)鍵字序列不可能是在二叉排序樹上查找到的序列是（）。2，252.401，398，330，344，397，363B.924，220，911，244，898，258，362，363925，202，911，240，912，245，3632，399，387，219，266，382，381，278，363（分數(shù)：2.00）A.B.丿D.解析：可以把這四個序列各插入到一個初始為空的二叉排序樹中，結(jié)果可以發(fā)現(xiàn)，C序列形成的不是一條路徑，而是有分支的，可見它是不可能在查找過程中訪問到的序列。7?在下列查找的方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是（）。順序查找B.二分法C.利用二叉搜索樹D.利用哈希（hash）表（分數(shù)：2.00）A.B.C.丿解析：8?如下所示帶權(quán)圖G,其最小生成樹各邊權(quán)的總和為（）。[*]14B.19C.21D.26分數(shù)：2.00)A.B.

丿D.解析：9?將兩個長度為N的有序表歸并到一個長度為2N的有序表，最少需要比較的次數(shù)是()，最多需要比較的次數(shù)是()。A．N，2N-1B．N-1，2NC．N，2ND．N-1，2N-1(分數(shù)：2.00)丿B.C.D.解析：用直接插入排序方法對下列4個表進行(由小到大)的排序，比較次數(shù)最少的是()TOC\o"1-5"\h\zA．94，32， 40， 90， 80， 46， 21，69 B．21， 32， 46， 40， 80， 69， 90， 94C．32，40， 21， 46， 69， 94， 90，80 D．90， 69， 80， 46， 21， 32， 94， 40(分數(shù)：2.00)A.B.丿D.解析：CPU中決定指令執(zhí)行順序的是()。指令寄存器IRB.程序計數(shù)器PCC.程序狀態(tài)字寄存器PSWRD.主存地址寄存器MAR分數(shù)：2.00)A.丿C.D.解析：CPU中用程序計數(shù)器PC來跟蹤下一條將要執(zhí)行的指令的地址，即通過程序計數(shù)器PC來決定指令執(zhí)行順序?！獋€C語言程序在一臺32位機器上運行。程序中定義了三個變量x、y和z,其中x和z是int型，y為short型。當x=127，y=-9時，執(zhí)行賦值語句z=x+y后，x、y和z的值分別是()。A.x=0000007FH，y=FFF9H，z=00000076HA.x=0000007FH，y=FFF9H，z=00000076Hx=0000007FH，y=FFF9H，z=FFFF0076Hx=0000007FH，y=FFF7H，z=FFFF0076HD.x=0000007FH，y=FFF7H，z=00000076HD.x=0000007FH，y=FFF7H，z=00000076H分數(shù)：2.00)A.B.C.D.丿解析：結(jié)合題干及選項可知，int為32位，short為16位；又C語言的整型數(shù)據(jù)在內(nèi)存中為補碼形式，故x、y的機器數(shù)寫為十六進制為O000007FH、FFF7H；執(zhí)行z=x+y時，由于x為int型，y為short型，故需將y的類型強制轉(zhuǎn)換為int，在機器中通過符號位擴展實現(xiàn)，由于y的符號位為1,故在y的前面添加16個1,即可將y強制轉(zhuǎn)換為int型，其十六進制形式為FFFFFFF7H；然后執(zhí)行加法，即0000007FH+FFFFFFF7H=00000076H(最高位的進位1自然丟棄)。故選D。原碼兩位乘中，符號位單獨處理，參加操作的數(shù)是()。原碼B.補碼C.絕對值的原碼D.絕對值的補碼(分數(shù)：2.00)A.B.C.丿解析：原碼兩位乘中，符號位單獨處理，但運算過程中可能需要進行“減被乘數(shù)絕對值”的操作，計算機中減法一般通過補碼加法來實現(xiàn)，故原碼兩位乘運算過程中參加操作的數(shù)是絕對值的補碼。在Cache和主存構(gòu)成的兩級存儲系統(tǒng)中，Cache的存取時間為100ns，主存的存取時間為1^s，Cache訪問失敗后CPU才開始訪存。如果希望Cache—主存系統(tǒng)的平均存取時間不超過Cache存取時間的15%,則Cache的命中率至少應(yīng)為()。95%B.98%C.98.5%D.99.5%(分數(shù)：2.00)A.B.丿D.解析：設(shè)Cache—主存系統(tǒng)的平均存取時間為Cache存取時間的1.15倍時Cache命中率為p，則有100+1000X(l-p)=115，解之得，p=0.985=98.5%。雙端口存儲器之所以能高速讀寫是因為()。采用了兩套獨立的存儲體B.采用了兩套相互獨立的讀寫電路C.采用了新型的器件D.兩套讀寫電路分時使用存儲體(分數(shù)：2.00)A.丿C.D.解析：雙端口存儲器采用了兩套相互獨立的讀寫電路，兩套讀寫電路可以同時訪問共同的存儲體，故可以高速讀寫。某機主存容量64KB，按字節(jié)編址。主存地址0100H處有一條相對轉(zhuǎn)移指令，指令字長16位，其中，第一個字節(jié)為操作碼，第二個字節(jié)為相對位移量(用補碼表示)，則該指令執(zhí)行結(jié)束后，后繼指令的地址范圍可能是()。0000H?FFFFHB.0080H?017FHC.0082H?0181HD.0080H?01FFH(分數(shù)：2.00)A.B.丿D.解析：該指令取指結(jié)束后，PC值自動加2,即(PC)=0102H；相對位移量用8位補碼表示，故其范圍為80H7FH，擴展到16位為FF80H?007FH，與PC值相加就可得后繼指令的地址范圍為0082H?0181H。下列哪個選項不是RISC的特點()。只有取數(shù)和存數(shù)指令訪問存儲器，其余指令都在寄存器之間進行由使用頻率高的簡單指令和很有用且不復(fù)雜的指令組成使用RISC技術(shù)后，指令系統(tǒng)又回到了計算機發(fā)展早期的比較簡單的情況使用優(yōu)化的編譯程序(分數(shù)：2.00)A.B.丿D.解析：早期的指令系統(tǒng)簡單是由設(shè)計水平和器件水平?jīng)Q定的，而且RISC技術(shù)不是簡單地精簡了指令系統(tǒng),而是在合理選擇簡單指令的基礎(chǔ)上采取了很多優(yōu)化措施，如縮短機器周期，采用流水線技術(shù)，使用優(yōu)化的編譯程序等等，兩者不可等同。下列微指令的編碼方式中，執(zhí)行速度最快的是()。直接編碼B.字段直接編碼C.字段間接編碼D.無法判斷(分數(shù)：2.00)丿B.C.D.解析：直接編碼方式下，微指令操作控制字段中的每一位代表一個微操作命令，微操作命令的發(fā)出不需要通過譯碼，故執(zhí)行速度最快。相對于微程序控制器，硬布線控制器的特點是()。指令執(zhí)行速度慢，指令功能的修改和擴展容易指令執(zhí)行速度慢，指令功能的修改和擴展難指令執(zhí)行速度快，指令功能的修改和擴展容易指令執(zhí)行速度快，指令功能的修改和擴展難分數(shù)：2.00)A.B.C.解析：硬布線控制器采用硬連線邏輯，故一旦構(gòu)成，除非在物理上進行重新布線，否則指令功能無法修改和擴展；微程序控制器采用存儲邏輯，當需要對指令功能進行修改和擴展時，只要重新設(shè)計微代碼的碼點，并將其注入控制存儲器中即可；但是由于采用存儲邏輯，相比硬布線控制器多了從控制存儲器中讀出碼點的過程，故其執(zhí)行速度較慢。綜合上述分析，可知D正確。某機采用計數(shù)器定時查詢方式來進行總線判優(yōu)控制，共有4個主設(shè)備競爭總線使用權(quán)，當計數(shù)器初值恒為10時，4個主設(shè)備的優(yōu)先級順序為()。2設(shè)備0〉設(shè)備1〉設(shè)備2〉設(shè)備3B.設(shè)備2〉設(shè)備1〉設(shè)備0〉設(shè)備3C.設(shè)備2〉設(shè)備3〉設(shè)備0〉設(shè)備1D.設(shè)備2=設(shè)備3=設(shè)備0=設(shè)備1(分數(shù)：2.00)A.B.丿D.解析：計數(shù)器初值為10[]，故設(shè)備2的優(yōu)先級最高，計數(shù)器值會遞增然后返回到0，故優(yōu)先級順序為設(shè)備22〉設(shè)備3〉設(shè)備0〉設(shè)備1。下列通道中，以字節(jié)為單位進行數(shù)據(jù)傳送的是()。字節(jié)多路通道B.選擇通道C.數(shù)組多路通道D.以上都是(分數(shù)：2.00)丿B.C.D.解析：選擇通道和數(shù)組多路通道都是以數(shù)據(jù)塊為單位進行數(shù)據(jù)傳送下列選項中，能引起外部中斷的事件是()。鍵盤輸入B.除數(shù)為0C.浮點運算下溢D.訪存缺頁(分數(shù)：2.00)丿B.C.D.解析：浮點數(shù)下溢一般做“機器零”處理.不引起中斷；除數(shù)為0、訪存缺頁會引出內(nèi)部中斷；只有鍵盤輸入能引起外部中斷，故選Ao單處理機系統(tǒng)中，可并行的是()。I進程與進程II處理機與設(shè)備III處理機與通道IV設(shè)備與設(shè)備I、II和IIIB.I、II和VC.I、III和VD.II、III和V(分數(shù)：2.00)A.B.C.丿解析：進程和進程是不能并行的，因為只有一個CPUo下列進程調(diào)度算法中，綜合考慮進程等待時間和執(zhí)行時間的是（）。時間片輪轉(zhuǎn)調(diào)度算法B.短進程優(yōu)先調(diào)度算法C.先來先服務(wù)調(diào)度算法D.高響應(yīng)比優(yōu)先調(diào)度算法（分數(shù)：2.00）A.B.C.丿解析：響應(yīng)比=（等待時間+執(zhí)行時間）/要求服務(wù)的時間。某計算機系統(tǒng)中有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統(tǒng)可能會發(fā)生死鎖的K的最小值是（）。2B.3C.4D.5（分數(shù)：2.00）A.B.丿D.解析：每個進程都占有2臺打印機時，發(fā)生死鎖。在虛擬存儲系統(tǒng)中，若進程在內(nèi)存中占3位（開始時為空），采用先進先出頁面淘汰算法，當執(zhí)行訪問頁號序列為1，2，3，4，1，2，5，1，2，3，4，5，6時，將產(chǎn)生（）次缺頁中斷。7B.8C.9D.10B.C.A.前者比后者大B.前者比后者小C.二者相等D.不一定（分數(shù)：2.00）A.B.C.丿解析：虛擬存儲空間是由地址的位數(shù)決定的，可能比內(nèi)存加上外存大，也可能小。位示圖可用于磁盤空間的管理。設(shè)某系統(tǒng)磁盤共有500塊，塊號從0到499；第0字的第0位表示第0塊，第0字的第1位表示第1塊，依次類推。若用位示圖法管理這500塊的盤空間，當字長為32位時，第i個第j位對應(yīng)的塊號是（）。A.32i+jB.32i+j-1C．32i+j-32D．32i+j-32-1（分數(shù)：2.00）丿B.C.D.解析：因為從0開始編號，所以選A?？紤]一文件存放在100個數(shù)據(jù)塊中，文件控制塊、索引塊或索引信息都駐留內(nèi)存。那么，如果（），不需要做任何磁盤I/O操作。采用contiguousallocation策略，將最后一個數(shù)據(jù)塊搬到文件頭部采用singlelevelindexedallocation策略，將最后一個數(shù)據(jù)塊插入文件頭部采用linkedallocation策略，將最后一個數(shù)據(jù)塊插入文件頭部采用linkedallocation策略，將第一個數(shù)據(jù)塊插入文件尾部（分數(shù)：2.00）A.丿C.D.解析：采用索引分配：將最后一個數(shù)據(jù)塊插入文件頭部，只需修改索引表就行，不需要移動數(shù)據(jù)文件系統(tǒng)中，設(shè)立打開文件系統(tǒng)功能調(diào)用的基本操作是（）。把文件信息從輔存讀到內(nèi)存把文件的控制管理信息從輔存讀到內(nèi)存把文件的FAT表信息從輔存讀到內(nèi)存把磁盤的超級塊從輔存讀到內(nèi)存（分數(shù)：2.00）A.丿C.D.解析：本題考查文件打開的概念。文件系統(tǒng)采用樹形目錄結(jié)構(gòu)后，對于不同用戶的文件，其文件名（）A.應(yīng)該不同B.由操作系統(tǒng)類型決定C.可以相同也可以不同D.受系統(tǒng)約束（分數(shù)：2.00）A.B.丿D.解析：樹形目錄的引入提高了檢索的效率，解決了文件的重名問題，即允許不同的用戶使用相同的文件名因此，對于不同用戶文件而言其文件名既可以相同也可以不同。對于硬盤上存放的信息，物理上讀寫的最小單位是一個（）。A.二進制B.字節(jié)C.物理塊D.邏輯記錄（分數(shù)：2.00）A.B.丿D.解析：硬盤的讀取是以塊為單位的。33.IEEE的802委員會已經(jīng)標準化了很多種類的LAN,其中無線LAN標準是（）。A.IEEE802.3B.IEEE802.5C.IEEE802.11D.IEEES02.17（分數(shù)：2.00）A.B.丿D.解析：IEEE802.11是無線LAN的標準。有一條無噪聲的8KHz信道，每個信號包含8級，每秒采樣24K次，那么可以獲得的最大傳輸速率是（）。A.24KbpsB.32KbpsC.48KhpsD.72Kbps（分數(shù)：2.00）A.B.丿D.解析：無噪聲的信號應(yīng)該滿足尼奎斯特定理，即最大數(shù)據(jù)傳輸率=2Hlog》（位/秒）。將題目中的數(shù)據(jù)帶入,得到答案是48kHz。注意題目中給出的每秒采樣24kHz是無意義的，因為超過了2H,所以D是錯誤答案。下圖為一個modem的調(diào)制圖，那么當它要發(fā)送115200bps的數(shù)據(jù)時，需要達到（）波特率。[*]115200bps57600bps28800bps230400bps（分數(shù)：2.00）A.丿C.D.解析：如題的調(diào)制圖所示，信道上一個信號可以有四種變化，即可以表示2bit的數(shù)據(jù)。那么為了達到115200bps的數(shù)據(jù)率，只要57600bps的波特率就可以了。在Internet的幾種路由協(xié)議中，（）米用了鏈路狀態(tài)路由算法。A.RIPB.BGPC.OSF，F(xiàn)D.NAT（分數(shù)：2.00）A.B.丿D.解析：OSPF（開放的最短路徑優(yōu)先）內(nèi)部網(wǎng)關(guān)路由協(xié)議采用了鏈路狀態(tài)路由算法。—個3200bit上的TCP報文傳到IP層，數(shù)據(jù)鏈路層可以發(fā)送的最長數(shù)據(jù)幀中的數(shù)據(jù)部分只有1200bit。IP層需要向數(shù)據(jù)鏈路層發(fā)送（）。A．3200bitB．3400bitC．5400bitD．3680bit（分數(shù)：2.00）A.B.C.丿解析：在題目給出的情況中，必須要對IP包進行分片，需要分3200/1200=3片。那么共需要添加3個IP首部，每個IP首部的長度是160bit，那么總共需要發(fā)送3200+160X3=3680bit數(shù)據(jù)。某公司獲得了一個IP地址段，在不分子網(wǎng)的情況下,最多可以容納65534個主機，那么這個地址屬于（）。A.A類地址B.B類地址C.C類地址D.D類地址（分數(shù)：2.00）A.丿C.D.解析：B類地址的主機號的長度是16位，再去點全“0”和全“1”兩個地址，還可以分配65534個主機。39?在TCP/IP模型中，主機采用（）標識，運行在主機上的應(yīng)用程序采用（）標識A.端口號，主機地址B.主機地址，IP地址C.IP地址，主機地址D.IP地址，端口號（分數(shù)：2.00）A.B.C.丿解析：在TCP/IP模型中，IP地址用來標識主機，使用IP地址來完成數(shù)據(jù)包的路由。而端口號則存在于傳輸層的頭部中，用來標識主機上的不同進程。下面（）協(xié)議中，客戶端和服務(wù)器之間采用面向無連接的協(xié)議進行通信。A.FTPB.SMTPC.TELNETD.DHCP分數(shù)：2.00)A.B.C.丿解析：DHCP采用UDP來發(fā)送數(shù)據(jù)，所以D是采用面向無連接的協(xié)議的。二、綜合應(yīng)用題(總題數(shù)：7，分數(shù)：70.00)在平衡二叉樹中的每個結(jié)點上增設(shè)一個Lsize域，其值為它的左子樹中的結(jié)點個數(shù)加1，試寫一個時間復(fù)雜度為O(logn)的算法，確定樹中第k個結(jié)點的位置。(分數(shù)：10.00)正確答案：(A二叉排序樹中第k個結(jié)點，即為二叉排序樹中序序列中順序號為k的結(jié)點，根結(jié)點的Lsize域中存放的是根結(jié)點的順序號。要確定二叉排序樹中第k個結(jié)點，先需將k與根結(jié)點的順序號進行比較，若相等，則找到；若k小于根結(jié)點的順序號，k繼續(xù)與根的左孩子結(jié)點的順序號比較，依次類推。(注意,右孩子結(jié)點的順序號等于根結(jié)點的順序號與右孩子結(jié)點的Lsize域值之和。)由于查找過程中不超過樹的高度，故其算法復(fù)雜度為O(logn)。typedefstructNode{intkey:structNode*lchild,*rchild:intLsize}BSNode;BSNode*Locate(BSNode*T,intk){intj,i=0;BSNode*p=T;while(p){j=i+p-〉Lsize;if(j==k)returnp;//找到if(j〉k)p=p-〉lchild;else{i+=p-〉Lsize;p=P-〉rchild;}}returnNULL:})解析：如下圖所示的AOE網(wǎng)，求：[*](分數(shù)：15.00).每項活動a的最早開始時間e(a)和最遲開始時間l(a)。(分數(shù)：3.75)i i i正確答案：(所有事件的最早發(fā)生時間如下：Ve(1)=0Ve(2)=5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15

Ve(6)=ve(4)+4=16Ve(7)=ve(5)+1=16Ve(8)=ve(5)+4=19Ve(9)=max{ve(7)+5，ve(8)+2)=21Ve(10)=max{ve(6)+4，ve(9)+2}=23所有事件的最晚發(fā)生時間如下：Vl(10)=23Vl(9)=vl(10)-2=21Vl(8)=vl(9)-2=19Vl(7)=vl(9)-5=16vl(8)-4}=15vl(5)-3)=12vl(5)-3}=6vl(3)-6}=0Vl(6)=vl(10)-4=19vl(8)-4}=15vl(5)-3)=12vl(5)-3}=6vl(3)-6}=0Vl(5)=min{vl(7)-1Vl(4)=min{vl(6)-4Vl(3)=min{vl(4)-6Vl(2)=vl(4)-3=9Vl(1)=min{vl(2)-5因此，所有活動Ai的e(因此，所有活動Ai的e()，l()，d()如下Al:e(1)=ve(1)=0，A2:e(2)=ve(1)=0，A3:e(3)=ve(2)=5，A4:e(4)=ve(3)=6，A5:e(5)=ve(3)=6，A6:e(6)=ve(4)=12A7:e(7)=ve(4)=12A8:e(8)=ve(5)=15A9:e(9)=ve(5)=15，l(1)=vl(2)-5=4，l(2)=vl(3)-6=0l(3)=vl(4)-3=8l(4)=vl(4)-6=6l(5)=vl(5)-3=12，d(5)=6l(6)=vl(5)-3=12l(7)=vl(6)-4=15l(8)=vl(7)-1=15l(9)=vl(8)-4=15，d(1)=4d(2)=Od(3)=3d(4)=0d(6)=0d(7)=3d(8)=0d(9)=0A11:e(11)=ve(7)=19，l(11)=vl(9)-2=19，d(10)=0A10:e(12)=ve(8)=16，l(12)=vl(10)-4=19，d(10)=3A10:e(13)=ve(9)=21，l(13)=vl(10)-2=21，d(10)=0)解析：.完成此工程最少需要多少天(設(shè)邊上權(quán)值為天數(shù))?(分數(shù)：3.75)正確答案：（完成此工程最少需要23天。）解析：（3）.哪些是關(guān)鍵活動?（分數(shù)：3.75）正確答案：（從以上計算可知，關(guān)鍵活動為a2,a4,a6,a8,a9,alO,all,al3。這些活動構(gòu)成兩條關(guān)鍵路徑即：a2，a4，a6，a8，a10，a13和a2，a4，a6，a9，a11，a13。）解析：（4）.是否存在某項活動,當其提高速度后能使整個工程縮短工期?（分數(shù)：3.75）正確答案：（存在a2,a4,a6,a13活動，當其提高速度后能使整個工程縮短工期）解析：某32位機（機器字長32位）的一臺外設(shè)通過32位總線與系統(tǒng)內(nèi)存相連。CPU每秒執(zhí)行100條指令，平均每條指令需要5個機器周期，其中3個周期必須訪問內(nèi)存，內(nèi)存讀寫需一個機器周期，假定CPU在95%的時間內(nèi)持續(xù)執(zhí)行“背景程序”，且這段時間內(nèi)不執(zhí)行I/O指令。現(xiàn)該外設(shè)需要把一個非常大的數(shù)據(jù)塊傳送到內(nèi)存。分數(shù)：ll.00）.如果采用程序I/O方式，每傳送一32位字寬的數(shù)據(jù)需要CPU執(zhí)行2條指令。請計算最大數(shù)據(jù)傳輸率(單位：字/秒)。(分數(shù)：5.50)正確答案：((1)數(shù)據(jù)塊非常大，可認為其執(zhí)行時間遠遠大于1s,故可用其1s內(nèi)的最大數(shù)據(jù)傳輸率來近似表示其整個傳輸過程中的最大數(shù)據(jù)傳輸率，(2)同。CPU每秒執(zhí)行100條指令，且95%的時間內(nèi)持續(xù)執(zhí)行背景程序，故1s內(nèi)CPU可用來進行I/O傳送的指令條數(shù)為100X(l-95%)=5(條)最大數(shù)據(jù)傳輸率為5/2=2.5(字/秒))解析：.如果采用DMA方式，在DMA與CPU出現(xiàn)總線訪問沖突時，CPU優(yōu)先。請計算最大數(shù)據(jù)傳輸率(單位：字/秒)。(分數(shù)：5.50)正確答案：(CPU每秒內(nèi)共有(100X5=)500個機器周期，其中執(zhí)行“背景程序”時有(100X95%X3=)285個機器周期必須訪問內(nèi)存，由于DMA與CPU訪存沖突時，CPU優(yōu)先，故DMA控制器只能在余下的500-285=215個機器周期內(nèi)訪存；又內(nèi)存讀寫需要一個機器周期，故采用DMA傳輸方式時，1s內(nèi)可讀寫內(nèi)存215次，即最大數(shù)據(jù)傳輸率為215字/秒。)解析：42?下圖是某模型機CPU的組成框圖。設(shè)該CPU采用同步控制邏輯，分取指周期、取第一操作數(shù)周期，取第二操作數(shù)周期、執(zhí)行周期四個機器周期，每個機器周期有T、T、T三個節(jié)拍。試寫出如下雙操作數(shù)運算指012令的微操作命令及節(jié)拍安排。ADDR0，(R1)完成功能(R0)+((Rl))—R0[*]分數(shù)：10.00)正確答案：(各機器周期的微操作命令及節(jié)拍安排如下。取指周期T:PC-總線-MAR-主存，微操作命令形成部件發(fā)讀信號到主存0T:M(MAR)-MDR，微操作命令形成部件發(fā)+1信號到PC1T:MDR-總線一IR，0P(IR)-微操作命令形成部件2取第一操作數(shù)周期T:R0-總線-FIRST0T:1T:2取第二操作數(shù)周期T:R1-總線-MAR-主存，微操作命令形成部件發(fā)讀信號到主存0T:M(MAR)-MDR1T:MDR-總線-SECOND2執(zhí)行周期T:FIRST-總線-Y0T:微操作命令形成部件發(fā)Add信號到ALU，(Y)+(SECOND)-ALU-Z1T:Z-總線-R0)2解析：43.設(shè)有一緩沖池P，P中含有10個可用緩沖區(qū)，一個輸入進程將外部數(shù)據(jù)讀入P，另有一個輸出進程將P中數(shù)據(jù)取出并輸出(如下圖所示)。若進程每次操作均以一個緩沖區(qū)為單位，試用記錄型信號量寫出兩個進程的同步算法，要求寫出信號量的設(shè)置。輸入進程輸出進程L:讀入數(shù)據(jù)L:從一滿緩沖區(qū)中取出數(shù)據(jù)將數(shù)據(jù)寫入一空緩沖區(qū)將數(shù)據(jù)輸出GOTOLGOTOL分數(shù)：7.00)正確答案：((1)設(shè)置信號量mutex,empty,full初值，mutex=1,empty=10,full=O(2)設(shè)置Wflit,signal操作如下。輸入進程輸出進程L:讀入數(shù)據(jù)L：wait(full)wait(empty)wait(mutex)wait(mutex)從一滿緩沖區(qū)中取出數(shù)據(jù)將數(shù)據(jù)寫入一空緩沖區(qū)signal(mutex)signal(mutex)signal(empty)signal(full)將數(shù)據(jù)輸出)解析：請求分頁管理系統(tǒng)中,假設(shè)某進程的頁表內(nèi)容如下表所示。頁號頁框(PageFrame)號有效位(存在位)0101H11——02254H1頁面大小為4KB,—次內(nèi)存的訪問時間是100ns,—次快表(TLB)的訪問時間是10ns，處理一次缺頁的平均時間為108ns(已含更新TLB和頁表的時間)，進程的駐留集大小固定為2,采用最近最少使用置換算法(LRU)和局部淘汰策略。假設(shè)：①TLB初始為空；②地址轉(zhuǎn)換時先訪問TLB,若TLB未命中，再訪問頁表(忽略訪問頁表之后的TLB更新時間)；③有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H,請問：(分數(shù)：8.00)(1).依次訪問上述三個虛地址，各需多少時間?給出計算過程。(分數(shù)：4.00)正確答案：(根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁號和頁內(nèi)位移分解出來。頁面大小為4KB，即212,則得到頁內(nèi)位移占虛地址的低12位，頁號占剩余高位。可得三個虛地址的頁號P如下(十六進制的一位數(shù)字轉(zhuǎn)換成4位二進制，因此，十六進制的低三位正好為頁內(nèi)位移，最高位為頁號)：2362H:P=2,訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，合成物理地址后訪問主存100ns,共計10ns+100