全國碩士研究生入學(xué)統(tǒng)一考試

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)

學(xué)科專業(yè)基礎(chǔ)綜合模擬題(二)及參考答案一、單項(xiàng)選擇題：下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。.一個(gè)棧的輸入序列為123…n,若輸出序列的第一個(gè)元素是n,輸出第i(l<=i<=n)個(gè)元素是oA.不確定B.n-i+1C.iD.n-i.有六個(gè)元素6,5,4,3,2,1的順序進(jìn)棧，下列不是合法的出棧序列。A.543612B.453126C.346521D.234156.一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足OA.所有的結(jié)點(diǎn)均無左孩子B.所有的結(jié)點(diǎn)均無右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D.是任意一棵二叉樹.設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1則T中的葉子數(shù)為oA.5B.6C.7D.8.已知一棵二叉樹先序遍歷結(jié)果為ABDEFG,中序遍歷結(jié)果為BAEDGF,則后序遍歷結(jié)果為oA.BCDEFAB.BFDECAC.BEGFDAD.BEFGDA.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為A.24B.48C.72D.53.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有條邊。A.n-1B.n(n-l)/2C.n(n+l)/2D.0.散列表的地址區(qū)間為0—17,散列函數(shù)為H(K)=Kmod17。采用線性探測法處理沖突，并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲到散列表中。元素59存放在散列表中的地址是oA.8B.9C.10D.11.對序列｛15,9,7,8,20,-1,4｝進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)椋?,9,-1,8,20,7,15）；則采用的是排序。A.選擇B.快速C.希爾D.冒泡.下列四個(gè)序列中，是堆。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,15.軟件與硬件在（）上可以是等級的，在（）上是不等級的OA.效率功能B.功能效率C.方法結(jié)構(gòu)D.結(jié)構(gòu)方法.浮點(diǎn)數(shù)的格式為10位字長，階碼4位，基為2。當(dāng)階碼和尾數(shù)均用原碼表示，且為規(guī)格化形式（采用隱藏位），下面浮點(diǎn)數(shù)表示0.4。A.0101010011B.0100111001C.0000011001D.0000010011XY為定點(diǎn)二進(jìn)制數(shù)，其格式為1位符號位，n位數(shù)值位。若采用Booth補(bǔ)碼一位乘法實(shí)現(xiàn)乘法運(yùn)算，則最多需要次加法運(yùn)算。A.n-lB.nC.n+1D.n+2.某機(jī)器采用四體交叉存儲器，今執(zhí)行一段小循環(huán)程序，此程序存放在存儲器的連續(xù)地址單元中。假設(shè)每條指令的執(zhí)行時(shí)間相同，而且不需要用到存儲器存取數(shù)據(jù)，在下面兩種情況下（執(zhí)行指令數(shù)相等），程序運(yùn)行時(shí)間之比約為o（1）循環(huán)程序由6條指令組成，重復(fù)執(zhí)行80次（2）循環(huán)程序由8條指令組成，重復(fù)執(zhí)行60次。A.2:1B.1:2C.3:4D.4:3.以下哪種類型的存儲器的讀寫速度最快。A.DRAMB.磁盤C.SRAMD.EPROM.存儲器按字節(jié)編址，在向上生成（地址碼減小方向）堆棧中，若約定為實(shí)頂棧（即堆棧指針隨時(shí)指向?qū)嵱袛?shù)據(jù)的堆頂），設(shè)SP=1428H,AX為16位累加寄存器，則執(zhí)行一條指令PUSHAX后，SP內(nèi)容為oA.1427B.142AC.1430D.1426.在指令格式中，采用擴(kuò)展操作碼設(shè)計(jì)方案的目的是oA.減少指令字長度B.增加指令字長度C.保持指令字長度不變而增加指令操作的數(shù)量D.保持指令字長度不變而增加尋址空間.微程序控制器中，微程序的入口地址是由 形成的。A.機(jī)器指令的地址碼字段B.機(jī)器指令的操作碼字段C.微指令的微操作碼字段D.微指令的微地址碼字段.某機(jī)器采用微程序技術(shù)設(shè)計(jì)控制器。已知每一條機(jī)器指令的執(zhí)行過程均可由8條微指令組成的微程序來完成，該機(jī)器的指令系統(tǒng)采用6位定長操作碼格式，控制存儲器至少應(yīng)能容納條微指令。A.512B.48C.64D.256.某機(jī)CPU芯片的主振頻率為8MHz,每個(gè)機(jī)器周期平均包含4個(gè)時(shí)鐘周期，該機(jī)的平均指令執(zhí)行速度為0.8MIPS,平均指令周期是oA.1個(gè)機(jī)器周期B.1.5個(gè)機(jī)器周期C.3個(gè)機(jī)器周期D.2.5個(gè)機(jī)器周期.總線結(jié)構(gòu)的主要優(yōu)點(diǎn)是便于實(shí)現(xiàn)系統(tǒng)的模塊化，其缺點(diǎn)是oA.不能同時(shí)具有一個(gè)以上的總線主設(shè)備B.傳輸?shù)牡刂泛蛿?shù)據(jù)信息不能同時(shí)出現(xiàn)C.傳輸?shù)牡刂泛涂刂菩畔⒉荒芡瑫r(shí)出現(xiàn)D.不能同時(shí)使用多于兩個(gè)總線設(shè)備.CPU響應(yīng)中斷的時(shí)間是oA.取指周期結(jié)束B.執(zhí)行周期結(jié)束C.中斷源提出請求D.間址周期結(jié)束.操作系統(tǒng)的主要功能是管理計(jì)算機(jī)系統(tǒng)中的oA.程序和數(shù)據(jù)B.硬件C.資源D.中斷.如果系統(tǒng)中有n個(gè)進(jìn)程，則就緒隊(duì)列中進(jìn)程的個(gè)數(shù)最多為（）。A.n+1B.nC.n-1D.1.一種既有利于短小作業(yè)又兼顧到長作業(yè)的作業(yè)調(diào)度算法是oA.先來先服務(wù)B.輪轉(zhuǎn)C.最高響應(yīng)比優(yōu)先D.均衡調(diào)度.考慮頁面替換算法。系統(tǒng)有m個(gè)頁幀(frame)供調(diào)度，初始時(shí)全空；引用串(referencestring)長度為p,包含了n個(gè)不同的頁號。無論用什么算法，缺頁次數(shù)不會少于0A.mB.pC.nD.min(m,n).若處理器有32位地址，則它的虛擬地址空間為字節(jié)。A.2GB.4GC.100KD.640K一個(gè)系統(tǒng)，它的文件控制塊占64B,一個(gè)磁盤塊大小為1KB,采用一級目錄。假定文件目錄中有1600個(gè)目錄項(xiàng)。則查找一個(gè)文件平均需要次訪問磁盤。A.50B.54C.100D.200.磁盤上的每一個(gè)物理塊要用三個(gè)參數(shù)來定位，首先要把移動臂移動并定位到不同盤面上具有相同編號的磁道位置，表示該位置的參數(shù)稱oA.柱面B.盤面C.扇區(qū)D.磁頭.適用于長度不變的文件物理結(jié)構(gòu)是oA.索引結(jié)構(gòu)B.鏈接結(jié)構(gòu)C.多重索引結(jié)構(gòu)D.連續(xù)結(jié)構(gòu).不使用中斷機(jī)構(gòu)的I/O控制方式是oA.中斷控制方式B.程序I/O方式C.DMA控制方式D.I/O通道控制方式.設(shè)備的打開、關(guān)閉、讀、寫等操作是由 完成的。A.用戶程序B.編譯程序C.設(shè)備分配程序D.設(shè)備驅(qū)動程序.兩臺計(jì)算機(jī)利用電話線路傳輸數(shù)據(jù)信號時(shí)，必需的設(shè)備是oA.網(wǎng)卡B.調(diào)制解調(diào)器C.中繼器D.同軸電纜.OSI/RM的三個(gè)主要概念是oA.體系結(jié)構(gòu)、模型、交換B.子網(wǎng)、分層、元語C.服務(wù)、接口、協(xié)議D.WAN、MAN、LAN.一信道的帶寬為10KHZ,如果使用4個(gè)不同的物理狀態(tài)來表示數(shù)據(jù)，根據(jù)奈奎斯特定理，其限定的最高數(shù)據(jù)率是OA.5Kb/sB.10Kb/sC.20Kb/sD.40Kb/s.EIA-232E的機(jī)械特性規(guī)定使用的連接器類型為 。A.DB—15連接器B.DB—25連接器C.DB—20連接器D.RJ—45連接器.在一個(gè)采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為IGbps,電纜中的信號傳播速度是200000km/s。若最小數(shù)據(jù)幀長度減少400比特，則最遠(yuǎn)的兩個(gè)站點(diǎn)之間的距離至少需要oA.減少80nlB.增加80nlC.減少40nlD.增加40nl.TCP使用慢開始和擁塞避免，設(shè)慢開始門限ssthresh的初始值為8（單位為報(bào)文段）。當(dāng)擁塞窗口上升到12時(shí)網(wǎng)絡(luò)發(fā)生了超時(shí)，則第15個(gè)傳輸周期的擁塞窗口大小是oA.9B.11C.32D.6439.關(guān)于選擇重傳，下列說法不正確的是oA.發(fā)送方緩存未被確認(rèn)的分組B.采用累積確認(rèn)C.發(fā)送方僅重傳那些它懷疑在接收方出錯(cuò)的分組D.允許發(fā)送方發(fā)送多個(gè)分組而無需等待確認(rèn)40.互聯(lián)網(wǎng)上的服務(wù)通常都是基于某一種協(xié)議，WWW是基于下面的協(xié)議。A.SNMPB.SMTPC.HTTPD.TELNET二、綜合應(yīng)用題.設(shè)有關(guān)鍵字序列10,20,35,40,44,51,65,70,85,91,93,95。試按照最大關(guān)鍵字復(fù)寫原則畫出相應(yīng)的2階B+樹。.有n個(gè)記錄存儲在帶頭結(jié)點(diǎn)的雙向鏈表中，現(xiàn)用雙向冒泡排序法對其按升序進(jìn)行排序，請寫出這種排序的算法。（注：雙向冒泡排序即相鄰兩趟排序向相反方向起泡）。.某機(jī)字長為16位，數(shù)據(jù)總線也為16位，內(nèi)存容量64KB,包含8個(gè)16位通用寄存器：R0?R7。指令系統(tǒng)基本要求是：＞128條雙操作指令，且其中必有一操作數(shù)是寄存器直接尋址。＞另一操作數(shù)的尋址方式有4種：立即尋址，寄存器直接尋址，寄存器間接尋址，變址尋址。立即數(shù)和變址尋址時(shí)的位移量為16位。＞指令長度應(yīng)滿足16的倍數(shù)，且要求盡量短。（1）列出通常在指令系統(tǒng)格式設(shè)計(jì)過程中應(yīng)該考慮的主要因素。(2)給出該機(jī)指令系統(tǒng)的設(shè)計(jì)方案(提示：畫出指令格式圖，說明指令各字段的位數(shù)和含義)o.假設(shè)X、Y、Z寄存器均為16位(最高位為第0位)。在乘法指令開始前，被乘數(shù)已存于X中，并用丫〃Z存放乘積。要求：(1)畫出實(shí)現(xiàn)補(bǔ)碼Booth算法的運(yùn)算器框圖。(2)假設(shè)CU為硬布線控制器，且采用中央控制和局部控制相結(jié)合的辦法。寫出完成MULa指令(a為主存地址)的全部微操作及節(jié)拍安排(包括取指階段)。(3)指出哪些節(jié)拍屬于中央控制節(jié)拍；哪些節(jié)拍屬于局部控制節(jié)拍，局部控制最多需要多少拍？.有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記。該表中每個(gè)表項(xiàng)代表閱覽室中的一個(gè)座位。讀者離開時(shí)要消掉其登記信息。閱覽室共有50個(gè)座位。登記表每次僅允許一位讀者進(jìn)行登記或注銷。若閱覽室人員已滿，則在閱覽室外等待，直至有空位再登記進(jìn)入。試用P、V操作，描述讀者行為。.某采用頁式存儲管理系統(tǒng)中，主存容量為1M,共有0,1,2, 255塊，一作業(yè)的地址空間占4頁，其頁號為0,1,2,3,分別被分配到第2,3,1,5塊中。請回答：(1)主存地址應(yīng)該用多少位來表示？(2)作業(yè)每頁的長度為多少?邏輯地址中的頁號和頁內(nèi)地址應(yīng)該分別占多少位？(3)把作業(yè)中的每一頁分配到主存中的起始地址填入下表：頁號起始地址0123(4)若給出邏輯地址OB.4168B.8291B,請計(jì)算出相應(yīng)的內(nèi)存地址。.某網(wǎng)絡(luò)拓?fù)淙缦聢D,網(wǎng)內(nèi)所用的IP網(wǎng)段為/24。DHCP服務(wù)器(DHCPServer)的IP地址是53,Email服務(wù)器的IP地址是100.13.254,路由器以太口ip地址是以.100.13.252。由DHCP服務(wù)器自動為網(wǎng)絡(luò)內(nèi)主機(jī)(DHCP客戶端)分配IP地址。DHCP客戶端啟動后，通過四線會話，發(fā)出請求并獲得IP信息，簡單描述會話過程。(2)四線會話的第一步中，數(shù)據(jù)包中的源IP地址和目的IP地址分別是多少?源MAC地址和目的MAC地址分別是多少？(3)客戶端收到的IP地址在什么范圍之內(nèi)？子網(wǎng)掩碼是多少？網(wǎng)關(guān)是多少？模擬題(二)參考答案一、單項(xiàng)選擇題。1-5BCCCC6-10DBDCC11-15BACDC16-20DCBAD21-25ABCCC26-30CBAAD31-35BDBCD36-40BCABC［解析］.按照堆棧“后進(jìn)先出”的特點(diǎn)，n是最后一個(gè)入棧的，即n為棧頂元素。若輸出的第一個(gè)元素為n,則其余所有元素必定仍在堆棧中。第一個(gè)輸出元素為n,則第二個(gè)輸出元素為nT,第i個(gè)輸出元素為n-i+1,最后一個(gè)(第n個(gè))輸出元素為lo.考查堆棧“后進(jìn)先出”的特點(diǎn)。對選項(xiàng)A來說，第一個(gè)出棧元素是5,因?yàn)?先于5進(jìn)棧，所以必定在5之后出棧，其余的元素出棧順序任意；對選項(xiàng)B來說，第一個(gè)出棧元素是4,所以5和6兩個(gè)元素必定在4之后依次出棧；對選項(xiàng)C來說，第一個(gè)出棧元素是3,則必有4.5.6三個(gè)元素依次在3后面出棧，但是選項(xiàng)C中的順序是,這是不符合要求的；對選項(xiàng)D來說，第一個(gè)出棧元素是2,則必有依次在2后面出棧，D也是符合要求的，因此答案選Co.前序序列是“根左右”，后序序列是“左右根”，若要這兩個(gè)序列相反，只有單支樹，所以本題的A和B均對，單支樹的特點(diǎn)是只有一個(gè)葉子結(jié)點(diǎn)，故C是最合適的，選C。.n=no+ni+n2+n3+n.i，n=l*4+2*2+3*l+4*l,所以n（）=7。.1＞根據(jù)前序遍歷ABDEFG知，根結(jié)點(diǎn)一定是A；根據(jù)中序遍歷BAEDGF,得:A的左側(cè)全部為左子樹結(jié)點(diǎn)（B）,A的右側(cè)全部為右子樹結(jié)點(diǎn)（EDGF），于是有：因?yàn)樽笞訕渲挥幸粋€(gè)結(jié)點(diǎn)，故不必再分析，否則將分析左子樹。下面分析右子樹。2＞對右子樹的所有結(jié)點(diǎn)來說，其前序遍歷是DEFG,因此右子樹的根結(jié)點(diǎn)是D；根據(jù)中序遍歷EDGF,得：D的左側(cè)為E結(jié)點(diǎn)（構(gòu)成D的左子樹結(jié)點(diǎn)集合），D的右側(cè)為G、F結(jié)點(diǎn)（構(gòu)成D的右子樹結(jié)點(diǎn)集合），于是有：D的左子樹只有E,故不必再分析，否則將分析D的左子樹。下面直接分析D的右子樹。3＞對D的右子樹的所有結(jié)點(diǎn)來說，其前序遍歷是FG,因此D的右子樹的根結(jié)點(diǎn)是F；根據(jù)中序遍歷GF,得：F得左側(cè)為G結(jié)點(diǎn)，右側(cè)無結(jié)點(diǎn)。即F只有左子樹.沒有右子樹。于是有：

4＞對得到的樹進(jìn)行后序遍歷，得到BEGFDAo.無向圖G中邊數(shù)目的取值范圍：0V=eV=n(n-l)/2。有n(n-l)/2條邊的無向圖稱為完全圖。.H(26)=26%17=9H(25)=25%17=8H(72)=72%17=4H(38)=38%17=4H(8)=8%17=8H(18)=18%17=1H(59)=59%17=7較小的數(shù)在序列的較后面部分，則需要一步一步的向前移動，無疑是比較慢的。如果采用步長＞1的方法，則可以使較小的數(shù)向前推進(jìn)是“跳躍式”進(jìn)行，故可以提高排序效率。方法：將整個(gè)序列分成若干子序列，對各個(gè)子序列進(jìn)行直接插入排序，得到一趟希爾排序序列；然后縮短步長，重復(fù)以上動作，直到步長為1。具體步驟如下：①先取一正整數(shù)did1"Z? 把所有距離為d的倍數(shù)的記錄編在一組，組成一個(gè)子序列，這樣將整個(gè)待排序序列分成若干組；②在各個(gè)子序列中進(jìn)行直接插入排序；③取一個(gè)新的d（比原來的要小，一般取原來的1/2）,重復(fù)執(zhí)行1）,2）,直到d=l為止（此時(shí)，整個(gè)序列變成直接插入排序）。.堆排序是另一種基于選擇的排序方法。n個(gè)元素的序列｛k?k2,k3,...kJ,當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆：或者：其中i=l,2,n/2o若將同以上序列對應(yīng)的一維數(shù)組看成是一棵完全二叉樹，則堆的含義表明：該完全二叉樹的所有非終端結(jié)點(diǎn)均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的值。由此，若｛kl,k2,...kn）是堆，則堆頂元素（或完全二叉樹的根結(jié)點(diǎn)）必定是該序列n個(gè)元素中的最小值（或者最大值）o若將堆看成是一棵以kl為根的完全二叉樹，則這棵完全二叉樹中的每個(gè)非終端結(jié)點(diǎn)的值均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的值。由此可以看出，若一棵完全二叉樹是堆，則根結(jié)點(diǎn)一定是這n個(gè)結(jié)點(diǎn)中的最小者（或最大者）。下面圖給出的兩個(gè)堆的示例。逆堆正堆從堆的定義可以看出，若將堆用一棵完全二叉樹表示，則根結(jié)點(diǎn)是當(dāng)前堆中所有結(jié)點(diǎn)的最小者（或最大者）。堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造一個(gè)堆，此時(shí)，選出了堆中所有記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小（或次大）的記錄，以此類推,直到堆中只有一個(gè)記錄為止，每個(gè)記錄出堆的順序就是一個(gè)有序序列。.隨著VLSI技術(shù)的發(fā)展，任何操作（功能）可以由軟件來實(shí)現(xiàn)，也可以由硬件來實(shí)現(xiàn)，軟硬件在功能上是等級的，但是軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)在方法、結(jié)構(gòu)和效率上都不等級。.0.4=0.0110011B=l.10011X2-2,數(shù)符在前，其次是階碼，最后是尾數(shù)，且采用隱藏位，當(dāng)階碼和尾數(shù)均用原碼表示，則表示為0101010011c.Booth乘法運(yùn)算中，符號位也參與運(yùn)算，所以需要n+1次加法運(yùn)算。.假設(shè)取指周期為T,執(zhí)行時(shí)間為t,總線傳輸時(shí)間為，第一種情況，程序運(yùn)行的時(shí)間T1=（T+5T+6t）X80=80T+400T+480t,第二種情況,程序運(yùn)行的時(shí)間T2=（T+7T+8t）X60=60T+420T+480t,所以，T1:T2^80T:60T=4:3o.存儲器中FLASHMEMORY（閃存）的改寫速度比EPROM（可擦寫的只讀存儲器）的速度快10倍以上，但比RAM（隨機(jī)存取存儲器）的速度要慢得多，而RAM按存儲原理的不同，分為SRAM（靜態(tài)隨機(jī)存取存儲器）和DRAM（動態(tài)隨機(jī)存取存儲器），其中，DRAM由于采用等效電容存儲信息，需要一個(gè)充放電過程，所以速度比SRAM要慢。.據(jù)題意，應(yīng)該先使（SP）7,再寫入數(shù)據(jù)，而AX為16位寄存器，占用2個(gè)堆棧單元，所以SP的內(nèi)容減1兩次。.擴(kuò)展操作碼的重要規(guī)則是賦予使用頻率高的指令短的操作碼，目的是為了保持指令字長度不變而增加指令操作的數(shù)量，從而降低指令的平均長度，提高編碼效率。.當(dāng)執(zhí)行完公用的取指微程序從主存中取出機(jī)器指令后，由機(jī)器指令的操作碼字段指出各個(gè)微程序的入口地址（初始微地址）。.由于機(jī)器指令系統(tǒng)采用6位定長編碼，所以可知指令系統(tǒng)一共有2，=64條指令，又據(jù)題意每條機(jī)器指令都可以分解為8條微指令，這樣系統(tǒng)中的微指令的條數(shù)為8X64=512條，所以控制存儲器至少應(yīng)能容納512條微指令。.機(jī)器周期為4/（8MHz）=0.5us,每條指令的平均執(zhí)行時(shí)間是1/（0.8M）=1.25us,所以平均指令周期是1.25/0.5=2.5個(gè)機(jī)器周期。.總線是連接多個(gè)部件的信息傳輸線，是各部件共享的傳輸介質(zhì)。在某一時(shí)刻，只允許有一個(gè)主設(shè)備向總線發(fā)送信息，而多個(gè)總線設(shè)備可以同時(shí)從總線上接收相同的信息。.曬CPU是在指令周期的最后一個(gè)機(jī)器周期——執(zhí)行周期的結(jié)束時(shí)刻統(tǒng)一向所有中斷源發(fā)出中斷查詢信號，所以選B。.操作系統(tǒng)的定義就提到操作系統(tǒng)是控制和管理計(jì)算機(jī)硬件和軟件資源的,硬件和軟件資源統(tǒng)稱為資源。D項(xiàng)不屬于操作系統(tǒng)所管理的資源，選其它任何一個(gè)選項(xiàng)都不全面。.一個(gè)計(jì)算機(jī)系統(tǒng)中至少有一個(gè)處理機(jī)，能常處理機(jī)上有一個(gè)進(jìn)程執(zhí)行，因此就緒隊(duì)列中進(jìn)程個(gè)數(shù)最多為n-1。如果系統(tǒng)中有n個(gè)進(jìn)程，一個(gè)處理機(jī)，則處于就緒狀態(tài)的進(jìn)程最多有n-1個(gè)，最少有0個(gè)。若n-1個(gè)處于阻塞狀態(tài)，1個(gè)處于執(zhí)行狀態(tài)，則就緒狀態(tài)為0個(gè)。處于執(zhí)行狀態(tài)的最多1個(gè)，最少0個(gè)。若都正好處于阻塞狀態(tài)，則為0個(gè)。處于阻塞狀態(tài)的最多n個(gè)，最少0個(gè)。.最高響應(yīng)比優(yōu)先算法等待時(shí)間相同時(shí)，要求服務(wù)時(shí)間愈短，優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)，對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高，從而獲得處理機(jī)，因此該算法即有利于短作業(yè)又兼顧到了長作業(yè)。.缺頁次數(shù)的上限是P,下限是n,因?yàn)闊o論用什么算法有可能剛淘汰掉的頁又接著要使用，故頁故障上限為P;而不同的頁至少有一次缺頁故障，故下限為no.處理器有32位，則其虛地址空間為232字節(jié)，即為4*2嗎4G字節(jié)。.3200個(gè)目錄項(xiàng)，需要占有1GOO*64/1O24=1OO個(gè)磁盤塊，一級目錄平均訪盤次數(shù)為整個(gè)盤塊數(shù)的1/2,所以查找平均訪問磁盤次數(shù)為50。.略。.連續(xù)結(jié)構(gòu)文件結(jié)構(gòu)簡單，系統(tǒng)開銷小，順序存取速度快，因?yàn)槲募拈L度不變，還可以根據(jù)文件起始地址及記錄長度進(jìn)行隨機(jī)訪問。.耨I/O方式無中斷機(jī)構(gòu)，由CPU向控制器發(fā)出一條I/O指令啟動設(shè)備，然后要不斷地循環(huán)檢測設(shè)備是否完成，浪費(fèi)了大量CPU時(shí)間。.有關(guān)設(shè)備的基本操作都由設(shè)備驅(qū)動程序負(fù)責(zé)。.本題目主要考查了“計(jì)算機(jī)網(wǎng)絡(luò)的概念、組成與功能”。電話線路傳輸模擬信號，而數(shù)據(jù)信號是數(shù)字信號，必須使用調(diào)制解調(diào)器，用于數(shù)字信號和模擬信號之間的轉(zhuǎn)換。不需要網(wǎng)卡連接。網(wǎng)卡是工作在數(shù)據(jù)鏈路層的網(wǎng)路組件，是局域網(wǎng)中連接計(jì)算機(jī)和傳輸介質(zhì)的接口。中繼器是一個(gè)將輸入信號增強(qiáng)放大的模擬設(shè)備，而不考慮輸入信號種類(是模擬的還是數(shù)字的)。中繼器通常用在局域網(wǎng)連接中。同軸電纜是一種常見的傳輸介質(zhì)，可以在很高的速率上傳輸很長的距離，同軸電纜分50Q,基帶電纜和75。寬帶電纜兩類。基帶電纜僅僅用于數(shù)字傳輸，數(shù)據(jù)率可達(dá)1OMbpso寬帶電纜是CATV系統(tǒng)中使用的標(biāo)準(zhǔn)，它既可使用頻分多路復(fù)用的模擬信號發(fā)送，也可傳輸數(shù)字信號。.本題目主要考查了“IS0/0SI參考模型”。ISOOSI/RM模型中，清晰地定義了服務(wù)、接口和協(xié)議三個(gè)概念；接口：相鄰兩層之間交互的界面(interface)；服務(wù)：某一層及其以下各層的一種功能，通過接口提供給其直接相鄰上層；協(xié)議：通信雙方在通信中必須遵守的規(guī)則。.本題目主要考查了物理層的“通信基礎(chǔ)”中的“帶寬，碼元狀態(tài)數(shù)、碼元速率、數(shù)據(jù)速率、奈氏準(zhǔn)則等基本概念及其相互間的關(guān)系”這一知識點(diǎn)。題目中4種不同的物理狀態(tài)，即表示一個(gè)碼元攜帶2個(gè)二進(jìn)制數(shù)。奈氏準(zhǔn)則首先給出了在無噪聲情況下信道碼元速率的極限值與信道帶寬的關(guān)系：B=2*H。其中，B表示碼元速率的極限值，H表示信道的帶寬。H=10KHz,所以B為2Kbps最高碼元速率。這樣，我們可以得到表示信道數(shù)據(jù)傳輸能力的奈奎斯特公式：C=2*Hlog2NC表示信道最大的數(shù)據(jù)傳輸速率，N為一個(gè)碼元所取的有效離散值個(gè)數(shù)，也稱之為調(diào)制電平數(shù)，N一般取2的整數(shù)次方。如果一個(gè)碼元可以取N種離散值，那它能表示的位二進(jìn)制信息。題目中4種不同的物理狀態(tài)，所以N=4,代入得：C=40Kb/so.本題目考查物理層的“通信標(biāo)準(zhǔn)EIA-232E的機(jī)械特性”這一知識點(diǎn)。EIA—232E在機(jī)械特性方面，使用ISO關(guān)于插頭座的標(biāo)準(zhǔn)，就是使用25根引腳的DB-25插頭座。引腳分為上、下兩排，分別為13和12根引腳。.本題目主要考查了“CSMA/CD協(xié)議”。CSMA/CD協(xié)議即載波監(jiān)聽多點(diǎn)接入/碰撞檢測。“多點(diǎn)接入”表示許多計(jì)算機(jī)以多點(diǎn)接入的方式連接在一根總線上。“載波監(jiān)聽”是指每一個(gè)站在發(fā)送數(shù)據(jù)之前先要檢測一下總線上是否有其他計(jì)算機(jī)在發(fā)送數(shù)據(jù)，如果有，則暫時(shí)不要發(fā)送數(shù)據(jù)，以免發(fā)生碰撞。總線上并沒有什么“載波”。因此，“載波監(jiān)聽”就是用電子技術(shù)檢測總線上有沒有其他計(jì)算機(jī)發(fā)送的數(shù)據(jù)信號。“碰撞檢測”就是計(jì)算機(jī)邊發(fā)送數(shù)據(jù)邊檢測信道上的信號電壓大小。當(dāng)幾個(gè)站同時(shí)在總線上發(fā)送數(shù)據(jù)時(shí)，總線上的信號電壓擺動值將會增大(互相疊加)。當(dāng)一個(gè)站檢測到的信號電壓擺動值超過一定的門限值時(shí)，就認(rèn)為總線上至少有兩個(gè)站同時(shí)在發(fā)送數(shù)據(jù)，表明產(chǎn)生了碰撞。檢測到碰撞后在發(fā)生碰撞時(shí)，總線上傳輸?shù)男盘柈a(chǎn)生了嚴(yán)重的失真，無法從中恢復(fù)出有用的信息來。每一個(gè)正在發(fā)送數(shù)據(jù)的站，一旦發(fā)現(xiàn)總線上出現(xiàn)了碰撞，就要立即停止發(fā)送，免得繼續(xù)浪費(fèi)網(wǎng)絡(luò)資源，然后等待一段隨機(jī)時(shí)間后再次發(fā)送。CSMA/CD檢測沖突需要花費(fèi)時(shí)間。對于基帶總線而言，最壞情況下用于檢測一個(gè)沖突的時(shí)間等于任意兩個(gè)站之間傳播時(shí)延的兩倍。從一個(gè)站點(diǎn)開始發(fā)送數(shù)據(jù)到另一個(gè)站點(diǎn)開始接收數(shù)據(jù)，也即載波信號從一端傳播到另一端所需的時(shí)間，稱為信號傳播時(shí)延。信號傳播時(shí)延一兩站點(diǎn)的距離/信號傳播速度。假定A.B兩個(gè)站點(diǎn)位于總線兩端，兩站點(diǎn)之間的最大傳播時(shí)延為Tp。當(dāng)A站點(diǎn)發(fā)送數(shù)據(jù)后，經(jīng)過接近于最大傳播時(shí)延Tp時(shí)，B站點(diǎn)正好也發(fā)送數(shù)據(jù)，此時(shí)沖突便發(fā)生。發(fā)生沖突后，B站點(diǎn)立即可檢測到該沖突，而A站點(diǎn)需再經(jīng)過一份最大傳播時(shí)延Tp后，才能檢測出沖突。也即最壞情況下，對于基帶CSMA/CD來說.檢測出一個(gè)沖突的時(shí)間等于任意兩個(gè)站之間最大傳播時(shí)延的兩倍(2Tp)。數(shù)據(jù)幀從一個(gè)站點(diǎn)開始發(fā)送，到該數(shù)據(jù)幀發(fā)送完畢所需的時(shí)間和為數(shù)據(jù)傳輸時(shí)延；同理，數(shù)據(jù)傳輸時(shí)延也表示一個(gè)接收站點(diǎn)開始接收數(shù)據(jù)幀，到該數(shù)據(jù)幀接收完畢所需的時(shí)間。數(shù)據(jù)傳輸時(shí)延(S)=數(shù)據(jù)幀長度(bit)/數(shù)據(jù)傳輸速率(bps)。若不考慮中繼器引入的延遲，數(shù)據(jù)幀從一個(gè)站點(diǎn)開始發(fā)送，到該數(shù)據(jù)幀被另一個(gè)站點(diǎn)全部接收所需的總時(shí)間，等于數(shù)據(jù)傳輸時(shí)延與信號傳播時(shí)延之和。由上述分析可知，為了確保發(fā)送數(shù)據(jù)站點(diǎn)在傳輸時(shí)能檢測到可能存在的沖突,數(shù)據(jù)幀的傳輸時(shí)延至少要兩倍于傳播時(shí)延。換句話說，要求分組的長度不短于某個(gè)值，否則在檢測出沖突之前傳輸已經(jīng)結(jié)束，但實(shí)際上分組已被沖突所破壞。由此引出了CSMA/CD總線網(wǎng)絡(luò)中最短幀長的計(jì)算關(guān)系式：最短數(shù)據(jù)幀長(bit)=2倍的信號傳播時(shí)延(s)*數(shù)據(jù)傳輸速率(bps)=2*兩站點(diǎn)的距離(m)/信號傳播速度*數(shù)據(jù)傳輸速率(bps)o由題意知：數(shù)據(jù)傳輸速率為IGbps,信號傳播速度為200000km/s,所以，我們得到：最短數(shù)據(jù)幀長(bit)=2*兩站點(diǎn)的距離(m)/2000000(km/s)*l(Gbps)。題意問的是若最小數(shù)據(jù)幀長度減少400比特，則求最遠(yuǎn)的兩個(gè)站點(diǎn)之間的距離變化。兩站點(diǎn)的距離變化值(m)=最短數(shù)據(jù)幀長減少值(bit)*200000(km/s)/(2*1(Gbps))=40mo綜上所述，減少40m。.本題目主要考查了“TCP流量控制與擁塞控制”。題目條件是TCP連接的慢開始門限的初始值是8,當(dāng)擁塞窗口上升到12時(shí)網(wǎng)絡(luò)發(fā)生超時(shí)，并且TCP使用慢開始和擁塞避免。因此在開始的4個(gè)傳輸周期里擁塞窗口的大小分別是：1、2、4、80之后進(jìn)入擁塞避免階段，第5到8個(gè)傳輸周期里擁塞窗口的大小分別是：9、10、11、12。此時(shí)發(fā)生超時(shí)，慢開始門限設(shè)為6,擁塞窗口的大小變?yōu)?.因此，第9到12個(gè)傳輸周期里擁塞窗口的大小分別是：1、2、4、6O之后進(jìn)入擁塞避免階段，所以第13到15個(gè)傳輸周期里擁塞窗口的大小分別是：7、8、9o.本題主要考查“選擇重傳協(xié)議”的基本原理。數(shù)據(jù)鏈路層中幀傳送可采用停止等待協(xié)議，連續(xù)ARQ協(xié)議及選擇重傳ARQ協(xié)議。停止等待協(xié)議就是每發(fā)一個(gè)數(shù)據(jù)幀就要等待一個(gè)確認(rèn)幀，只有收到確認(rèn)幀后才發(fā)送第二幀，如果超時(shí)還沒收到確認(rèn)幀，或收到否認(rèn)幀時(shí)重發(fā)該幀。每發(fā)一個(gè)數(shù)據(jù)幀就要等待確認(rèn)幀，這樣信道的利用率就很低，于是便有了連續(xù)ARQ。所謂連續(xù)就是在發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)若干幀，邊發(fā)可以邊等待確認(rèn)幀，如果收到了確認(rèn)幀，又可以繼續(xù)發(fā)送數(shù)據(jù)幀，由于減少了等待的時(shí)間，利用率就提高了。但是連續(xù)ARQ在收到一個(gè)否認(rèn)幀或超時(shí)后，所有該幀后面的幀都要重發(fā)而不管該幀后面的幀是否正確傳送，于是便有了選擇重傳ARQ協(xié)議。所謂選擇就是指只選擇錯(cuò)誤的幀進(jìn)行重發(fā)，而不像連續(xù)ARQ那樣所有該錯(cuò)誤幀后面的幀都要重發(fā)。但是選擇重傳ARQ是以浪費(fèi)存儲空間來提高信道的利用率的，因?yàn)橹皇沁x擇性地重發(fā)錯(cuò)誤幀，那么后面的幀就有可能比前面的幀先到達(dá)接收端，這個(gè)時(shí)候如果一收到幀就往上傳用戶就有可能收到不正確的幀，例如A向B發(fā)送“我是A”，但是B很有可能收到這樣的信息“是A我”，為了避免這樣的錯(cuò)誤，在接收方就必須先將A發(fā)過來的信息保存起來，直到所有信息均到達(dá)后再對其進(jìn)行組裝，組裝完成后再往上傳，這樣就浪費(fèi)了存儲空間。.本題目主要考查了“WWW”服務(wù)。WWW是基于超文本的信息查詢系統(tǒng)，而超文本的傳輸是通過HTTP協(xié)議進(jìn)行傳輸?shù)摹TTP是Hypertexttransferprototcol,即超文本的傳輸。SNMP是專門設(shè)計(jì)用于在IP網(wǎng)絡(luò)管理網(wǎng)絡(luò)節(jié)點(diǎn)（服務(wù)器、工作站、路由器、交換機(jī)及HUBS等）的一種標(biāo)準(zhǔn)協(xié)議，它是一種應(yīng)用層協(xié)議。SNMP使網(wǎng)絡(luò)管理員能夠管理網(wǎng)絡(luò)效能，發(fā)現(xiàn)并解決網(wǎng)絡(luò)問題以及規(guī)劃網(wǎng)絡(luò)增長。SMTP是因特網(wǎng)電子郵件中主要的應(yīng)用層協(xié)議，它使用TCP可靠數(shù)據(jù)傳輸服務(wù)，從發(fā)送方的郵件服務(wù)器向接收方的郵件服務(wù)器發(fā)送郵件，默認(rèn)使用TCP端口為25。POP3是接收郵件協(xié)議，端口號是110。Telnet協(xié)議是TCP/IP協(xié)議族中的一員，是Internet遠(yuǎn)程登錄服務(wù)的標(biāo)準(zhǔn)協(xié)議和主要方式。它為用戶提供了在本地計(jì)算機(jī)上完成遠(yuǎn)程主機(jī)工作的能力。二、綜合應(yīng)用題typedefstructnodeElemTypedata；structnode*prior,*next；}node,*DLinkedList；voidTwoWayBubbleSort(DLinkedListla)〃對存儲在帶頭結(jié)點(diǎn)的雙向鏈表la中的元素進(jìn)行雙向起泡排序。(intexchange=l；〃設(shè)標(biāo)記DLinkedListp,temp,tail；head=la〃雙向鏈表頭，算法過程中是向下起泡的開始結(jié)點(diǎn)tail=null；〃雙向鏈表尾，算法過程中是向上起泡的開始結(jié)點(diǎn)while(exchange)(p=head—>next；〃p是工作指針，指向當(dāng)前結(jié)點(diǎn)exchanged；〃假定本趟無交換while(p->next!=tail)〃向下(右)起泡，一趟有一最大元素沉底if(p?—>data>p—>next—>data)〃交換兩結(jié)點(diǎn)指針，涉及6條鏈(temp=p—>next；exchange=l；〃有交換pm>next=temp->next；temp—>next->prior二p〃先將結(jié)點(diǎn)從鏈表上摘下temp—>next=p；p—>prior—>next=temp；〃將temp插到p結(jié)點(diǎn)前temp—>prior=p—>prior；p->prior=temp；)elsep=p>next；〃無交換，指針后移tail=p；〃準(zhǔn)備向上起泡p=tai1—>prior；while(exchange&&p一>prior!=head)〃向上(左)起泡，一趟有一最小元素冒出if(p—>data<p—>prior—>data)〃交換兩結(jié)點(diǎn)指針，涉及6條鏈{temp—p=>prior；exchalage=l；〃有交換p->prior=temp——>prior；temp—>prior——>next=p；〃先將temp結(jié)點(diǎn)從鏈表上摘下temp—>prior=p；p—>next—>prior=temp；〃將temp插到p結(jié)點(diǎn)后(右)temp——>next=p——>next；p——>next=temp；}elsep=p—>prior；〃無交換，指針前移}lead=p；〃準(zhǔn)備向下起泡(1)指令格式集中體現(xiàn)了指令系統(tǒng)的功能，因此，在確定指令格式時(shí)，必須從以下幾個(gè)方面綜合考慮：.操作類型：包括指令數(shù)以及操作的難易程度；.數(shù)據(jù)類型：確定哪些數(shù)據(jù)類型可以參與操作；.指令格式：包括指令字長、操作碼位數(shù)、地址碼位數(shù)、地址個(gè)數(shù)、尋址方式類型，以及指令字長和操作碼位數(shù)是否可變等；.尋址方式：包括指令和操作數(shù)具體有哪些尋址方式；.寄存器個(gè)數(shù)：寄存器的多少直接影響指令的執(zhí)行時(shí)間。(2)據(jù)題意，128條雙操作數(shù)指令，則操作碼取7位，其中必有一操作數(shù)是寄存器尋址，故取3位作為寄存器編號，另外一個(gè)操作數(shù)由尋址方式?jīng)Q定。由四種尋址方式可知，尋址特征位應(yīng)取2位，對于變址尋址和立即數(shù)尋址，應(yīng)該擴(kuò)展一個(gè)字存放16位的位移量，所以采用雙字長的指令碼。該指令系統(tǒng)的設(shè)計(jì)方案如下所示：操作碼通用寄存器尋址特征位通用寄存器空⑺位⑶位⑵位⑶位⑴位A(16)位

其中，A字段為16位偏移量，只出現(xiàn)在立即尋址和變址尋址中，指令字中空余一位，可用作變址寄存器的標(biāo)志。.分析：本題主要考查了Booth算法以及微操作的節(jié)拍安排。(1)補(bǔ)碼Booth算法的運(yùn)算器框圖如下所示(圖中n=15)：(2)A.取指周期:T1PCout和(2)A.取指周期:T1PCout和MARin有效,完成PC經(jīng)CPU內(nèi)部總線送到MAR的操作T2CU通過控制總線