計(jì)算機(jī)考研真題及參考答案-考研必備

2009年統(tǒng)考計(jì)算機(jī)考研真題單項(xiàng)選擇題，每小題2分，共80分。.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧B.隊(duì)列C.樹D.圖.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧So若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素出隊(duì)的順序是bdcfeag,則棧S的容量至少是A.1B.2C.3D.4.給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,1,7,5,6,2,4,則其遍歷方式是A.LRNB.NRLC.RLND.RNL.下列二叉排序樹中，滿足平衡二叉樹定義的是.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是A.39B.52C.lllD.119.將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u和v可能具有的關(guān)系是I.父子關(guān)系II.兄弟關(guān)系III.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有11B.I和IIC.I和HI 和III.下列關(guān)于無向連通圖特性的敘述中，正確的是I.所有頂點(diǎn)的度之和為偶數(shù)IL邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1IIL至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.I和III.下列敘述中，不符合m階B樹定義要求的是A.根節(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接.已知關(guān)鍵序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入關(guān)鍵字3,調(diào)整后得到的小根堆是A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19.若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A.起泡排序B.插入排序C.選擇排序D.二路歸并排序.馮?諾依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中，CPU區(qū)分它們的依據(jù)是A.指令操作碼的譯碼結(jié)果B.指令和數(shù)據(jù)的尋址方式C.指令周期的不同階段D.指令和數(shù)據(jù)所在的存儲(chǔ)單元.一個(gè)C語言程序在一臺(tái)32位機(jī)器上運(yùn)行。程序中定義了三個(gè)變量xyz,其中x和z是int型，y為short型。當(dāng)x=127,y=~9時(shí)，執(zhí)行賦值語句z=x+y后，xyz的值分別是A.X=0000007FH,y=FFF9H,z=00000076HA.X=0000007FH,y=FFF9H,z=FFFF0076HA.X=0000007FH,y=FFF7H,z=FFFF0076HA.X=0000007FH,y=FFF7H,z=00000076H.浮點(diǎn)數(shù)加減運(yùn)算過程一般包括對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出等步驟。設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示，且位數(shù)分別為5位和7位（均含2位符號(hào)位）。若有兩個(gè)數(shù)X=27X29/32,丫=25X5/8,則用浮點(diǎn)加法計(jì)算X+Y的最終結(jié)果是A.001111100010B.001110100010C.010000010001D.發(fā)生溢出.某計(jì)算機(jī)的Cache共有16塊，采用2路組相聯(lián)映射方式（即每組2塊）。每個(gè)主存塊大小為32字節(jié)，按字節(jié)編址。主存129號(hào)單元所在主存塊應(yīng)裝入到的Cache組號(hào)是A.0B.2C.4D.6.某計(jì)算機(jī)主存容量為64KB,其中ROM區(qū)為4KB,其余為RAM區(qū)，按字節(jié)編址。現(xiàn)要用2KX8位的ROM芯片和4KX4位的RAM芯片來設(shè)計(jì)該存儲(chǔ)器，則需要上述規(guī)格的ROM芯片數(shù)和RAM芯片數(shù)分別是A.1、15B.2、15C.1,30D.2、30.某機(jī)器字長16位，主存按字節(jié)編址，轉(zhuǎn)移指令采用相對(duì)尋址，由兩個(gè)字節(jié)組成，第一字節(jié)為操作碼字段，第二字節(jié)為相對(duì)位移量字段。假定取指令時(shí)，每取一個(gè)字節(jié)PC自動(dòng)加1?若某轉(zhuǎn)移指令所在主存地址為20OOH,相對(duì)位移量字段的內(nèi)容為06H,則該轉(zhuǎn)移指令成功轉(zhuǎn)以后的目標(biāo)地址是A.2006HB.2007HC.2008HD.2009H.下列關(guān)于RISC的敘述中，錯(cuò)誤的是RISC普遍采用微程序控制器RISC大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成RISC的內(nèi)部通用寄存器數(shù)量相對(duì)CISC多RISC的指令數(shù)、尋址方式和指令格式種類相對(duì)CISC少.某計(jì)算機(jī)的指令流水線由四個(gè)功能段組成，指令流經(jīng)各功能段的時(shí)間（忽略各功能段之間的緩存時(shí)間）分別是90ns、80ns、70ns和60ns,則該計(jì)算機(jī)的CPU時(shí)鐘周期至少是A.90nsB.80nsC.70nsD.60ns.相對(duì)于微程序控制器，硬布線控制器的特點(diǎn)是A.指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展容易B.指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展難C.指令執(zhí)行速度快，指令功能的修改和擴(kuò)展容易D.指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難.假設(shè)某系統(tǒng)總線在一個(gè)總線周期中并行傳輸4字節(jié)信息，一個(gè)總線周期占用2個(gè)時(shí)鐘周期，總線時(shí)鐘頻率為10MHz,則總線帶寬是A.10MB/sB.20MB/SC.40MB/SD.80MB/S.假設(shè)某計(jì)算機(jī)的存儲(chǔ)系統(tǒng)由Cache和主存組成，某程序執(zhí)行過程中訪存1000次，其中訪問Cache缺失（未命中）50次，則Cache的命中率是A.5%B.9.5%C.50%D.95%.下列選項(xiàng)中，能引起外部中斷的事件是A.鍵盤輸入B.除數(shù)為0C浮點(diǎn)運(yùn)算下溢D.訪存缺頁.單處理機(jī)系統(tǒng)中，可并行的是I進(jìn)程與進(jìn)程II處理機(jī)與設(shè)備III處理機(jī)與通道IV設(shè)備與設(shè)備A.I、II和IIIB.I、II和IVC.I、HI和IVD.H、III和IV.下列進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是A.時(shí)間片輪轉(zhuǎn)調(diào)度算法B.短進(jìn)程優(yōu)先調(diào)度算法C.先來先服務(wù)調(diào)度算法D.高響應(yīng)比優(yōu)先調(diào)度算法.某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，有K個(gè)進(jìn)程競(jìng)爭使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（）A.2B.3C.4D.5.分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是A.界地址保護(hù)B.程序代碼保護(hù)C.數(shù)據(jù)保護(hù)D.棧保護(hù).一個(gè)分段存儲(chǔ)管理系統(tǒng)中，地址長度為32位，其中段號(hào)占8位，則段長最大A.2的8次方字節(jié)B.2的16次方字節(jié)C.2的24次方字節(jié)D.2的32次方字節(jié)28.下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問且易于文件擴(kuò)展的是A.連續(xù)結(jié)構(gòu) B.索引結(jié)構(gòu)C.鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定長D.鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長29.假設(shè)磁頭當(dāng)前位于第105道，正在向磁道序號(hào)增加的方向移動(dòng)?，F(xiàn)有一個(gè)磁道訪問請(qǐng)求序列為35,45,12,68,110,180,170,195,采用SCAN調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是A.110,170,180,195,68,45,35,12B.110,68,45,35,12,170,180,195C.110,170,180,195,12,35,45,68D.12,35,45,68,110,170,180,195.文件系統(tǒng)中，文件訪問控制信息存儲(chǔ)的合理位置是A.文件控制塊B.文件分配表C用戶口令表D.系統(tǒng)注冊(cè)表.設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為1,先建立F1的符號(hào)鏈接（軟鏈接）文件F2,再建立F1的硬鏈接文件F3,然后刪除FU此時(shí)，F(xiàn)2和F3的引用計(jì)數(shù)值分別是A.0、1B.l、1C.1,2D.2、1.程序員利用系統(tǒng)調(diào)用打開I/O設(shè)備時(shí)，通常使用的設(shè)備標(biāo)識(shí)是A.邏輯設(shè)備名B.物理設(shè)備名C.主設(shè)備號(hào)D.從設(shè)備號(hào).在OSI參考模型中，自下而上第一個(gè)提供端到端服務(wù)的層次是A.數(shù)據(jù)鏈路層B.傳輸層C.會(huì)話層D.應(yīng)用層.在無噪聲情況下，若某通信鏈路的帶寬為3kHz,采用4個(gè)相位，每個(gè)相位具有4種振幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是A.12kbpsB.24kbpsC.48kbpsD.96kbps.數(shù)據(jù)鏈路層采用了后退N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號(hào)為0?7的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若發(fā)送方只收到0、2、3號(hào)幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是A.2B.3C.4D.5.以太網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時(shí)使用的PDU地址是A.目的物理地址B.目的IP地址C.源物理地址D.源IP地址.在一個(gè)采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為IGbps,電纜中的信號(hào)傳播速度是2O0OOOkm/s。若最小數(shù)據(jù)幀長度減少800比特，則最遠(yuǎn)的兩個(gè)站點(diǎn)之間的距離至少需要A.增加160mB.增加80mC.減少160mD.減少80m.主機(jī)甲和主機(jī)乙間已建立一個(gè)TCP連接，主機(jī)甲向主機(jī)乙發(fā)送了兩個(gè)連續(xù)的TCP段，分別包含300字節(jié)和500字節(jié)的有效載荷，第一個(gè)段的序列號(hào)為200,主機(jī)乙正確接收到兩個(gè)段后，發(fā)送給主機(jī)甲的確認(rèn)序列號(hào)是A.500B.700C.800D.1000.一個(gè)TCP連接總是以1KB的最大段發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，如果接下來的4個(gè)RTT（往返時(shí)間）時(shí)間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是A.7KBB.8KBC.9KBD.16KB.FTP客戶和服務(wù)器間傳遞FTP命令時(shí)，使用的連接是A.建立在TCP之上的控制連接B.建立在TCP之上的數(shù)據(jù)連接C.建立在UDP之上的控制連接D.建立在UDP之上的數(shù)據(jù)連接二.綜合應(yīng)用題。共70分。（10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法：①設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；②選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v,加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v；③重復(fù)步驟②，直到u是目標(biāo)頂點(diǎn)時(shí)為止。請(qǐng)問上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說明。（15分）已知一個(gè)帶有表彳結(jié)點(diǎn)的單鏈率結(jié)點(diǎn)結(jié)構(gòu)區(qū)datalink假設(shè)該鏈表只給出了頭指針 listo在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回1；否則，只返回0。要求：（1）描述算法的基本設(shè)計(jì)思想（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟（3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用C或C++或JAVA語言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡要注釋。（8分）某計(jì)算機(jī)的CPU主頻為500MHz,CPI為5（即執(zhí)行每條指令平均需5個(gè)時(shí)鐘周期）。假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB/S,采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送，以32位為傳輸單位，對(duì)應(yīng)的中斷服務(wù)程序包含18條指令，中斷服務(wù)的其他開銷相當(dāng)于2條指令的執(zhí)行時(shí)間。請(qǐng)回答下列問題，要求給出計(jì)算過程。（1）在中斷方式下，CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少？（2）當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到5MB/S時(shí)，改用DMA方式傳送數(shù)據(jù)。假設(shè)每次DMA傳送大小為5000B,且DMA預(yù)處理和后處理的總開銷為500個(gè)時(shí)鐘周期，則CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少？（假設(shè)DMA與CPU之間沒有訪存沖突）（13分）某計(jì)算機(jī)字長16位，采用16位定長指令字結(jié)構(gòu)，部分?jǐn)?shù)據(jù)通路結(jié)構(gòu)如圖所示。圖中所有控制信號(hào)為1時(shí)表示有效、為0時(shí)表示無效。例如控制信號(hào)MDRinE為1表示允許數(shù)據(jù)從DB打入MDR,MDRin為1表示允許數(shù)據(jù)從內(nèi)總線打入MDR。假設(shè)MAR的輸出一直處于使能狀態(tài)。加法指令"ADD（RI）,R0”的功能為（R0）+（（RD）-（RI）,即將R0中的數(shù)據(jù)與R1的內(nèi)容所指主存單元的數(shù)據(jù)相加，并將結(jié)果送入R1的內(nèi)容所指主存單元中保存。

存儲(chǔ)器M

MemRMemWDataAddr數(shù)據(jù)通路結(jié)構(gòu)下表給出了上述指令取值和譯碼階段每個(gè)節(jié)拍(時(shí)鐘周期)的功能和有效控制信號(hào)，請(qǐng)按表中描述方式用表格列出指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào)。功能和控制信號(hào)時(shí)鐘功能有效控制信號(hào)ClMAR-(PC)PCout,MARinC2MDR-M(MAR)PC-(PC)+1MemR,MDRinEPC+1C3IR-(MDR)MDRoutJRinC4指令譯碼無(7分)三個(gè)進(jìn)程Pl、P2、P3互斥使用一個(gè)包含N(N>0)個(gè)單元的緩沖區(qū)。P1每次

用produce()生成一個(gè)正整數(shù)并用put()送入緩沖區(qū)某一空單元中；P2每次用getodd

O從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd()統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用geteven()

從該緩沖區(qū)中取出一個(gè)偶數(shù)并用counteven()統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)

進(jìn)程的同步與互斥活動(dòng)，并說明所定義的信號(hào)量的含義。要求用偽代碼描述。46.（8分）請(qǐng)求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示。頁面大小為4KB,一次內(nèi)存的訪問時(shí)間是100ns,一次快表（TLB）的訪問時(shí)間是10ns,處理一次缺頁的平均時(shí)間為108ns（已含更新TLB和頁表的時(shí)間），進(jìn)程的駐留集大小固定為2,采用最近最少使用置換算法（LRU）和局部淘汰策略。假設(shè)頁號(hào)頁框號(hào)有效位（存在位）0101H11—02254H1①TLB初始為空；②地址轉(zhuǎn)換時(shí)先訪問TLB,若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時(shí)間）；③有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H,請(qǐng)問：（1）依次訪問上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過程。（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請(qǐng)說明理由。47.（9分）某公司網(wǎng)絡(luò)拓?fù)鋱D如下圖所示，路由器R1通過接口El、E2分別連接局域網(wǎng)1、局域網(wǎng)2,通過接口L0連接路由器R2,并通過路由器R2連接域名服務(wù)器與互聯(lián)網(wǎng)。R1的L0接口的IP地址是；R2的L0接口的IP地址是,L1接口的IP地址是130.口.120.1,E0接口的IP地址是；域名服務(wù)器的IP地址是,互聯(lián)網(wǎng)）互聯(lián)網(wǎng)）????■KI和R2的路由龍結(jié)構(gòu)為:目的網(wǎng)絡(luò)Ip地址子網(wǎng)撞碼了二itipu觸口"]將IP地址空間/24劃分為兩個(gè)子網(wǎng)，分配給局域網(wǎng)1、局域網(wǎng)2,每個(gè)局域網(wǎng)分配的地址數(shù)不少于120個(gè)，請(qǐng)給出子網(wǎng)劃分結(jié)果。說明理由或給出必要的計(jì)算過程。請(qǐng)給出R1的路由表，使其明確包括到局域網(wǎng)1的路由、局域網(wǎng)2的路由、域名服務(wù)器的主機(jī)路由和互聯(lián)網(wǎng)的路由。請(qǐng)采用路由聚合技術(shù)，給出R2到局域網(wǎng)1和局域網(wǎng)2的路由參考答案1234567B廠10B(1)HCBADB11121314151617181920CDD<DCAAB2122232425261728M)P \ D D- C A C B 「4 313233343536r3840P\ BB CD D c A 該方法求得的路徑不一定是最短路徑。例如，對(duì)于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為A-B-C,事實(shí)上其最短路徑為A-D-C.從A到C的最短路徑為A-BY,事實(shí)上其最短路竹:為(1)算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當(dāng)前節(jié)點(diǎn)的前K個(gè)節(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)節(jié)點(diǎn)時(shí)，指針P所指向的節(jié)點(diǎn)即為所查找的節(jié)點(diǎn)。(2)詳細(xì)實(shí)現(xiàn)步驟：增加兩個(gè)指針變量和一個(gè)整型變量，從鏈表頭向后遍歷，其中指針P1指向當(dāng)前遍歷的節(jié)點(diǎn)，指針P指向P1所指向節(jié)點(diǎn)的前K個(gè)節(jié)點(diǎn)，如果P1之前沒有K個(gè)節(jié)點(diǎn)，那么P指向表頭節(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少節(jié)點(diǎn)，當(dāng)>k時(shí)，指針p隨著每次遍歷，也向前移動(dòng)一個(gè)節(jié)點(diǎn)。當(dāng)遍歷完成時(shí)，p或者指向表頭就節(jié)點(diǎn)，或者指向鏈表中倒數(shù)第K個(gè)位置上的節(jié)點(diǎn)。(3)算法描述：IntLocateElement(linklistlist,intk){Pl=list->link;P=list;i=l；while(Pl){Pl=Pl->link;i++;if(i>k)p=p->next;〃如果i>L則p也往后移}if(p==list)return0;〃說明鏈表沒有k個(gè)結(jié)點(diǎn)else{print""%d\n",p->data);return1;I(1)在中斷方式下，每32位(4B)被中斷一次，故每秒中斷0.5MB/4B=0.5X106/4=12.5X104次要注意的是，這里是數(shù)據(jù)傳輸率，所以1MB=1O6B。因?yàn)橹袛喾?wù)程序包含18條指令，中斷服務(wù)的其他開銷相當(dāng)于2條指令的執(zhí)行時(shí)間，且執(zhí)行每條指令平均需5個(gè)時(shí)鐘周期，所以，1秒內(nèi)用于中斷的時(shí)鐘周期數(shù)為(18+2)X5X12.5X104=12.5X106(2)在DMA方式下，每秒進(jìn)行DMA操作5MB/5000B=5X106/5000=1X103次因?yàn)镈MA預(yù)處理和后處理的總開銷為500個(gè)時(shí)鐘周期，所以1秒鐘之內(nèi)用于DMA操作的時(shí)鐘周期數(shù)為500X1X103=5X105故在DMA方式下，占整個(gè)CPU時(shí)間的百分比是((5X105)/(500X106))X100%=0.1%44.指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào)如下所示時(shí)鐘功能有效控制信號(hào)時(shí)停功能有效控制信號(hào)C5MAR-(R1)FCout,MARinC6MDR*-V1(MAR)MemR.MDRinE<?7A—(R0)ROoul.AinC8AC-(MDR)+(A)MDRout.Addr.ACinC9MDR-(AC)ACoiiL'IDRinM(MAR)*-MDRMDRoutE.MemWC5MAR*(R1)PCout,MARinC6MDR-M(MAR)MemR,MDRinEC7A-(RO)ROout,AinC8AC-(MDR)+(A)MDRout^ddr,ACinC9MDR-(AC)ACout,MDRinCIOM(MAR)-MDRMDRoutE,MemW45.定義信號(hào)量SI控制Pl與P2之間的同步；S2控制Pl與P3之間的同步；empty控制生產(chǎn)者與消費(fèi)者之間的同步；mutex控制進(jìn)程間互斥使用緩沖區(qū)。程序如下：

Varsl=0,s2=0,empty=N,mutex=l;ParbeginPkbeginX=produce();P(empty);P(mutex);Put();Ifx%2=0V(s2);elseV(sl);V(mutex);end.P2:beginP(sl)；P(mutex);4KB,頁內(nèi)占4KB,頁內(nèi)占12位，即16機(jī)制的3位則2362H的最高位就是頁號(hào)2:10不命中+100頁表+100內(nèi)存地址1：10不命中+100頁表+108缺頁+100內(nèi)存地址2：10命中+100內(nèi)存地址1號(hào)頁內(nèi)偏移565H,缺頁，置換0,101565HCountodd():=countodd()+1;V(mutex);V(empty);end.P3:beginP(s2)P(mutex);Geteven();Counteven():=counteven()+1;V(mutex);V(empty);end.Parend.(1)根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁號(hào)和頁內(nèi)位移分解出來。頁面大小為4KB,即212,則得到頁內(nèi)位移占虛地址的低12位，頁號(hào)占剩余高位?？傻萌齻€(gè)虛地址的頁號(hào)P如下(十六進(jìn)制的一位數(shù)字轉(zhuǎn)換成4位二進(jìn)制，因此，十六進(jìn)制的低三位正好為頁內(nèi)位移，最高位為頁號(hào))：2362H：P=2,訪問快表10ns,因初始為空，訪問頁表100ns得到頁框號(hào)，合成物理地址后訪問主存100ns,共計(jì)10ns+100ns+100ns=210nso1565H：P=L訪問快表10ns,落空，訪問頁表100ns落空，進(jìn)行缺頁中斷處理108ns,合成物理地址后訪問主存100ns,共計(jì)10ns+100ns+108ns+100ns?108nso25A5H：P=2,訪問快表，因第一次訪問已將該頁號(hào)放入快表，因此花費(fèi)10ns便可合成物理地址，訪問主存100ns,共計(jì)10ns+100ns=110nso(2)當(dāng)訪問虛地址1565H時(shí)，產(chǎn)生缺頁中斷，合法駐留集為2,必須從頁表中淘汰一個(gè)頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號(hào)頁面，因此1565H的對(duì)應(yīng)頁框號(hào)為101H。由此可得1565H的物理地址為101565Ho(1)無類IP地址的核心是采用不定長的網(wǎng)絡(luò)號(hào)和主機(jī)號(hào)，并通過相應(yīng)的子網(wǎng)掩碼來表示(即網(wǎng)絡(luò)號(hào)部分為1,主機(jī)號(hào)部分為0)。本題中網(wǎng)絡(luò)地址位數(shù)是24,由于IP地址是32位,因此其主機(jī)號(hào)部分就是8位。因此，子網(wǎng)掩碼就是11111111111111111111111100000000,即=根據(jù)無類IP地址的規(guī)則，每個(gè)網(wǎng)段中有兩個(gè)地址是不分配的：主機(jī)號(hào)全0表示網(wǎng)絡(luò)地址，主機(jī)號(hào)全1表示廣播地址。因此8位主機(jī)號(hào)所能表示的主機(jī)數(shù)就是2的8次方一2,即254臺(tái)。該網(wǎng)絡(luò)要?jiǎng)澐譃閮蓚€(gè)子網(wǎng)，每個(gè)子網(wǎng)要120臺(tái)主機(jī)，因此主機(jī)位數(shù)X應(yīng)該滿足下面三個(gè)條件：X<8,因?yàn)槭窃谥鳈C(jī)號(hào)位長為8位的網(wǎng)絡(luò)進(jìn)行劃分，所以X一定要小于8位。2的X次方>120,因?yàn)楦鶕?jù)題意需要容納120臺(tái)主機(jī)。X是整數(shù)。解上述方程，得到X=7.子網(wǎng)掩碼就是11111111111111111111111110000000,即28o所以劃分的兩個(gè)網(wǎng)段是：/25與28/25,(2)填寫R1的路由表填寫到局域網(wǎng)1的路由。局域網(wǎng)1的網(wǎng)絡(luò)地址和掩碼在問題(1)已經(jīng)求出來了，為/25o則R1路由表應(yīng)填入的網(wǎng)絡(luò)地址為,掩碼為28。由于局域網(wǎng)1是直接連接到路由器R1的E1口上的，因此，下一跳地址填寫直接路由(Direct)。接口填寫El.填寫到局域網(wǎng)2的路由表1。局域網(wǎng)2的網(wǎng)絡(luò)地址和掩碼在問題(1)中已經(jīng)求出來了，為28/25o則R1路由表應(yīng)該填入的網(wǎng)絡(luò)地址為28,掩碼為28.由于局域網(wǎng)2是直接連接到路由器R1的E2口上的，因此，下一跳地址填寫直接路由。接口填寫E2。填寫到域名服務(wù)器的路由。由于域名服務(wù)器的IP地址為,而該地址為主機(jī)地址，因此掩碼為55。同時(shí)，路由器R1要到DNS服務(wù)器，就需要通過路由器R2的接口L0才能到達(dá)，因此下一跳地址填寫L0的IP地址()。填寫互聯(lián)網(wǎng)路由。本題實(shí)質(zhì)是編寫默認(rèn)路由。默認(rèn)路由是一種特殊的靜態(tài)路由，指的是當(dāng)路由表中與包的目的地址之間沒有匹配的表項(xiàng)時(shí)路由器能夠做出的選擇。如果沒有默認(rèn)路由器，那么目的地址在路由表中沒有匹配表項(xiàng)的包將被丟棄。默認(rèn)路由在某些時(shí)候非常有效，當(dāng)存在末梢網(wǎng)絡(luò)時(shí)，默認(rèn)路由會(huì)大大簡化路由器的配置，減輕管理員的工作負(fù)擔(dān),提高網(wǎng)絡(luò)性能。默認(rèn)路由叫做“0/0”路由，因?yàn)槁酚傻腎P地址,而子網(wǎng)掩碼也是O.O.O.Oo同時(shí)路由器R1連接的網(wǎng)絡(luò)需要通過路由器R2的L0□才能到達(dá)互聯(lián)網(wǎng)絡(luò)，因此下一跳地址填寫L0的IP為。綜上，填寫的路由表如下：R1路由表目的網(wǎng)格IP地址于網(wǎng)掩碼下一跳11?地址接口28DirectE12828DirectE2202.1183.2?55L0L0(3)填寫R2到局域網(wǎng)1和局域網(wǎng)2的路由表2o局域網(wǎng)1和局域網(wǎng)2的地址可以聚合為/24,而R2去往局域網(wǎng)1和局域網(wǎng)2都是同一條路徑。因此，路由表里面只需要填寫到/24網(wǎng)絡(luò)的路由即可，如下表所示R2路由表目的網(wǎng)絡(luò)IP地址 子網(wǎng)掩碼 下一跳IP地址 接口 L02010年統(tǒng)考計(jì)算機(jī)考研真題一、單項(xiàng)選擇題：1-40題，每題2分共80分。1、若元素a、b、c、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是。A、dcebfaB、cbdaefC>bcaefdD、afedcb2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順順序是。bacdedbacedbcaeecbad3、下列線索二叉樹中(用虛線表示線索)，符合后序線索樹定義的是()4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是()13,4824,4824,5324,905、在一棵度數(shù)為4的樹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)，則樹T的葉結(jié)點(diǎn)個(gè)數(shù)是()A、41B、82C、113D、1226、對(duì)n(n>=2)個(gè)權(quán)值均不相同的字符構(gòu)成哈弗曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是。A、該樹一定是一棵完全二交叉B、樹中一定沒有度為1的結(jié)點(diǎn)C、樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D、樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值7、若無向圖G=(V.E)中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是。A、6B、15C、16D,218、對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是。A、4B、3219、已知一個(gè)長度為16的順序表L,其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多的是()A、4B、5C,6D、710、采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是()A、遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關(guān)B、每次劃分后，(勤思考研)先處理較長的分區(qū)可以減少遞歸次數(shù)(勤思考研)C、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(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.歸并排序法D.基數(shù)排序法12.下列選項(xiàng)中，能縮短程序執(zhí)行時(shí)間的措施是01.提高CPU時(shí)鐘頻率2.優(yōu)化通過數(shù)據(jù)結(jié)構(gòu)3.優(yōu)化通過程序A.僅1和2B.僅1和3C,僅2和3D.1,2,313.假定有4個(gè)整數(shù)用8位補(bǔ)碼分別表示rl=FEH,r2=F2H,r3=90H,r4=F8H,若將運(yùn)算結(jié)果存放在一個(gè)8位寄存器中，則下列運(yùn)算會(huì)發(fā)生益處的是()rlxr2rlxr3rlxr4r2xr414.假定變量i,f,d數(shù)據(jù)類型分別為int,float,double(int用補(bǔ)碼表示，float和double用IEEE754單精度和雙精度浮點(diǎn)數(shù)據(jù)格式表示)，已知i=785,41.5678e3,d=1.5el00,若在32位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式，(勤思考研)則結(jié)果為真的是()i=(int)(float)I(II)f=(float)(int)f(III)f==(float)(double)f(IV)(d+f)-d=fa.僅i和nB.僅I和III僅n和in僅in和IV.假定用若干個(gè)2Kx4位芯片組成一個(gè)8Kx8為存儲(chǔ)器，則0B1FH所在芯片的最小地址是0A.0000HB.0600HC.0700HD.0800H.下列有關(guān)RAM和ROM得敘述中正確的是()IRAM是易失性存儲(chǔ)器，ROM是非易失性存儲(chǔ)器IIRAM和ROM都是采用隨機(jī)存取方式進(jìn)行信息訪問RAM和ROM都可用做CacheRAM和ROM都需要進(jìn)行刷新僅I和H僅II和IH僅I,II,III僅II,III,IV.下列命令組合情況，一次訪存過程中，不可能發(fā)生的是()A.TLB未命中，Cache未命中，Page未命中B.TLB未命中，Cache命中，Page命中C.TLB命中，Cache未命中，Page命中D.TLB命中,Cache命中，Page未命中.下列寄存器中，反匯編語言程序員可見的是0A.存儲(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)中的英文縮寫均為總線標(biāo)準(zhǔn)的是()PCI、CRT、USB、EISAISA,CPkVESA,EISAISA、SCSI、RAM、MIPSISA,EISA,PCI,PCI-Express21、單級(jí)中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是()I保護(hù)現(xiàn)場(chǎng)II開中斷III關(guān)中斷IV保存斷點(diǎn)V中斷事件處理VI恢復(fù)現(xiàn)場(chǎng)VII中斷返回A、I->V->VI->II->VIIB、IH->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%用來刷新屏幕，則需要的顯存總帶寬至少約為()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用戶登陸成功n設(shè)備分配HI啟動(dòng)程序執(zhí)行a、僅I和nB、僅II和IIIC、僅I和IIID、I、II、III25、設(shè)與某資源相關(guān)聯(lián)的信號(hào)量初值為3,當(dāng)前值為1,若M表示該資源的可用個(gè)數(shù)，(勤思考研)N表示等待該資源的進(jìn)程數(shù)，則M,N分別是()A、0,1B、1,0C、\,2D、2,026、下列選項(xiàng)中，降低進(jìn)程優(yōu)先權(quán)級(jí)的合理時(shí)機(jī)是。A、進(jìn)程的時(shí)間片用完B、進(jìn)程剛完成I/O,進(jìn)入就緒列隊(duì)C、進(jìn)程長期處于就緒列隊(duì)D、進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)27、進(jìn)行PO和P1的共享變量定義及其初值為。

booleamflag|2|;intturn=0;flag|O]=false;flag|l|=false;若進(jìn)行PO和Pl訪問臨界資源的類c代碼實(shí)現(xiàn)如下:voidp0()//voidp0()//進(jìn)程pOvoidpl()//進(jìn)程plwhile(TRUE){flag|O]=TRUE;turn=l;While(flag|l|&&(turn=l))臨界區(qū)；while(TRUE){flag|O]=TRUE;turn=l;While(flag|l|&&(turn=l))臨界區(qū)；flag|O|=FALSE;while(TRUE){flag|O]=TRUE;turn=0;While(flag|0|&&(turn=0));臨界區(qū)；nag|l|=FALSE;則并發(fā)執(zhí)行進(jìn)程PO和Pl時(shí)產(chǎn)生的情況是（）A、不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會(huì)出現(xiàn)“饑餓”現(xiàn)象B、不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會(huì)出現(xiàn)“饑餓”現(xiàn)象C、能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會(huì)出現(xiàn)“饑餓”現(xiàn)象D、能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會(huì)出現(xiàn)“饑餓”現(xiàn)象28、某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存容量為55Mb（初始為空），（勤思考研）采用最佳適配（BestFit）算法，分配和釋放的順序?yàn)椋悍峙?5Mb,分配30Mb,釋放15Mb,分配6Mb,此時(shí)主存中最大空閑分區(qū)的大小是（）A、7MbB、9MbC、10MbD、15Mb29、某計(jì)算機(jī)采用二級(jí)頁表的分頁存儲(chǔ)管理方式，按字節(jié)編制，頁大小為2（10）［2的10次方，下同】字節(jié)，頁表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為頁目錄號(hào)頁號(hào)頁內(nèi)偏移量邏輯地址空間大小為2（10）頁，則表示整個(gè)邏輯地址空間的頁目錄表中包含表項(xiàng)的個(gè)數(shù)至少是（）A、64B、128C、256D、51230.設(shè)文件索引節(jié)點(diǎn)中有7個(gè)地址項(xiàng)，其中4個(gè)地址為直接地址索引，（勤思考研）1個(gè)地址項(xiàng)是二級(jí)間接地址索引，每個(gè)地址項(xiàng)的大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個(gè)文件最大長度是（）33KB519KB1057KB16513KB.設(shè)當(dāng)前工作目錄的主要目的是0A.節(jié)省外存空間B.節(jié)省內(nèi)存空間C.加快文件的檢索速度D.加快文件的讀寫速度.本地用戶通過鍵盤登陸系統(tǒng)是，首先獲得鍵盤輸入信息的程序時(shí)()A.命令解釋程序B.中斷處理程序C.系統(tǒng)調(diào)用程序D.用戶登錄程序.下列選項(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.每一層必須完成的功能.在下圖所表示的采用“存儲(chǔ)-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中所有的鏈路的數(shù)據(jù)傳輸速度為100Mbps,分組大小為1000B,其中分組頭大小為20B若主機(jī)H1向主機(jī)H2發(fā)送一個(gè)大小為980000的文件，(勤思考研)則在不考慮分組拆裝時(shí)間和傳播延遲的情況下，從H1發(fā)送到H2接受完為止，需要的時(shí)間至少是0A.80ms80.08ms80.16ms80.24ms35.某自治系統(tǒng)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含的信息<netl,16>,則可能得出的結(jié)論是0R2可以經(jīng)過R1到達(dá)netl,跳數(shù)為17R2可以到達(dá)netl,跳數(shù)為16R1可以經(jīng)過R2到達(dá)netl,跳數(shù)為17D.R1不能經(jīng)過R2到達(dá)netl36.若路由器R因?yàn)閾砣麃G棄1P分組，則此時(shí)R可向發(fā)出該1P分組的源主機(jī)的ICMP報(bào)文件的類型是()A.路由重定向B.目的不可達(dá)C.源抑制D.超時(shí)37、某網(wǎng)絡(luò)的IP地址空間為/24采用長子網(wǎng)劃分，子網(wǎng)掩碼為48,則該網(wǎng)絡(luò)的最大子網(wǎng)個(gè)數(shù)、每個(gè)子網(wǎng)內(nèi)的最大可分配地址個(gè)數(shù)為032,832,68,328,3038、下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風(fēng)暴的是()I中斷器n集線器III網(wǎng)橋IV路由器A、僅I和Hb、僅mc、僅in和IVD、僅IV39、主機(jī)甲和主機(jī)乙之間建立一個(gè)TCP連接，TCP最大段長度為1000字節(jié)，(勤思考研)若主機(jī)甲的當(dāng)前擁塞窗口為4000字節(jié)，在主機(jī)甲向主機(jī)乙連續(xù)發(fā)送2個(gè)最大段后，成功收到主機(jī)乙發(fā)送的第一段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為2000字節(jié)，則此時(shí)主機(jī)甲還可以向主機(jī)乙發(fā)送的最大字節(jié)數(shù)是()A,100020003000400040、如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域名時(shí)，用戶主機(jī)本地域名服務(wù)器發(fā)送的域名請(qǐng)求條數(shù)分別為。A、1條，1條B、1條，多條C,多條，1條D、多條，多條二、綜合應(yīng)用題：41-47小題，共70分(10分)將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲(chǔ)到散列表中，(勤思考研)散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從。開始的一個(gè)一維數(shù)組散列，函數(shù)為：H(key)=(keyx3)MODT,處理沖突采用線性探測(cè)再散列法，要求裝載因子為0.7問題：.請(qǐng)畫出所構(gòu)造的散列表。.分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長度。(13分)設(shè)將n(n>l)個(gè)整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能高效的算法。將R中的序列循環(huán)左移P(0<P<n)個(gè)位置，即將R中的數(shù)據(jù)由(X0,XI Xn-1)變換為(Xp,Xp-1...Xn-1,X0,XI Xp-1)要求：(D、給出算法的基本設(shè)計(jì)思想。(2)、根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)、說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。43、(11分)某計(jì)算機(jī)字節(jié)長為16位，主存地址空間大小為128KB,按字編址。采用字長指令格式，指令名字段定義如下：15 1211 65OPM5R5MdRd源操作數(shù)目的操作數(shù)轉(zhuǎn)移指令采用相對(duì)尋址，相對(duì)偏移是用補(bǔ)碼表示，尋址方式定義如下:Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=(Rn)001B寄存器間接(Rn)操作數(shù)=((Rn))010B寄存能間接、自增(Rn)+操作數(shù)=((Rn)),(Rn)+1->Rn011B相對(duì)D(Rn)轉(zhuǎn)移目標(biāo)地址=(PC)+(Rn)注：(X)表示有存儲(chǔ)地址X或寄存器X的內(nèi)容，請(qǐng)回答下列問題:(1)、該指令系統(tǒng)最多可有多少指令?該計(jì)算機(jī)最多有多少個(gè)通用寄存器？(勤思教育)存儲(chǔ)地址寄存器(MAR)和存儲(chǔ)數(shù)據(jù)寄存器(MDR)至少各需多少位？(2)、轉(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,則匯編語言為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;I<256;i++)for(j=0;j<256;j++)sum+=a|i||j|;returnsum;程序B:inta|256||256|;intsum_array2()(inti,j,sum=0;for(j=0；j<256;j++)for(i=0;i<256;i++)

sum+=a|i||j|;returnsum;假定int類型數(shù)據(jù)用32位補(bǔ)碼表示，程序編譯時(shí)i,j,sum均分配在寄存器中，數(shù)組a按行優(yōu)先方式存放，其地址為320(十進(jìn)制)。請(qǐng)回答，要求說明理由或給出計(jì)算過程。(1)、若不考慮用于Cache一致維護(hù)和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘繛槎嗌伲?2),數(shù)組元素a[0]|31]和a[1]111各自所在的主存塊對(duì)應(yīng)的Cache行號(hào)分別是多少(Cache行號(hào)從0開始)(3)、程序A和B得數(shù)據(jù)訪問命中率各是多少？哪個(gè)程序的執(zhí)行時(shí)間短？45、(7分)假設(shè)計(jì)算機(jī)系統(tǒng)采用CSCAN(循環(huán)掃描)磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個(gè)磁盤的空閑狀態(tài)(1)、請(qǐng)說明在上述條件如何進(jìn)行磁盤塊空閑狀態(tài)的管理。(2)、設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)，(勤思教育)每個(gè)磁道有100個(gè)扇區(qū)，相臨磁道間的平均移動(dòng)的時(shí)間為1ms.若在某時(shí)刻，磁頭位于100號(hào)磁道處，并沿著磁道號(hào)增大的方向移動(dòng)(如下圖所示),磁道號(hào)的請(qǐng)求隊(duì)列為50,90,30,120對(duì)請(qǐng)求隊(duì)列中的每個(gè)磁道需讀取1個(gè)隨機(jī)分布的扇區(qū)，則讀完這個(gè)扇區(qū)點(diǎn)共需要多少時(shí)間？需要給出計(jì)算過程。46.(8分)設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為64KB,按字節(jié)編址。(勤思教育)某進(jìn)程最多需要6頁數(shù)據(jù)存儲(chǔ)空間，頁的大小為1KB,操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個(gè)頁框。頁號(hào)頁框號(hào)裝入時(shí)間訪問位071301142301222001391601當(dāng)該進(jìn)程執(zhí)行到時(shí)刻260時(shí)，要訪問邏輯地址為17CAH的數(shù)據(jù)。請(qǐng)回答下列問題：(1),該邏輯地址對(duì)應(yīng)的頁號(hào)時(shí)多少？(2)、若采用先進(jìn)先出(FIFO)置換算法，該邏輯地址對(duì)應(yīng)的物理地址？要求給出計(jì)算過程。(3)、采用時(shí)鐘(Clock)置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過程。(設(shè)搜索下一頁的指針按順時(shí)針方向移動(dòng)，且指向當(dāng)前2號(hào)頁框，示意圖如下)f■?f■??WB?47、(9分)某局域網(wǎng)采用CSMA/CD協(xié)議實(shí)現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸率為100M/S,主機(jī)甲和主機(jī)已的距離為2KM,信號(hào)傳播速速時(shí)200000M/S請(qǐng)回答下列問題，并給出計(jì)算過程。(1)、若主機(jī)甲和主機(jī)已發(fā)送數(shù)據(jù)時(shí)發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時(shí)刻起，到兩臺(tái)主機(jī)均檢測(cè)到?jīng)_突時(shí)刻為止，最短經(jīng)過多長時(shí)間？最長經(jīng)過多長時(shí)間？(假設(shè)主機(jī)甲和主機(jī)已發(fā)送數(shù)據(jù)時(shí)，其它主機(jī)不發(fā)送數(shù)據(jù))(2)、若網(wǎng)絡(luò)不存在任何沖突與差錯(cuò)，主機(jī)甲總是以標(biāo)準(zhǔn)的最長以太數(shù)據(jù)幀(1518字節(jié))向主機(jī)已發(fā)送數(shù)據(jù)，主機(jī)已每成功收到一個(gè)數(shù)據(jù)幀后，立即發(fā)送下一個(gè)數(shù)據(jù)幀，(勤思教育)此時(shí)主機(jī)甲的有效數(shù)據(jù)傳輸速率是多少？(不考慮以太網(wǎng)幀的前導(dǎo)碼)參考答案1-5 DCBCB6-10 AABAD 11-15ADCBD 16-20 ADBAD21-25 ADACB 26-30 AABBC 31-35CBCAA 36-40 CBCAA(1)因?yàn)檠b填因子為0.7,數(shù)據(jù)總數(shù)為7,所以存儲(chǔ)空間長度為L=7/0.7=10因此可選T=10,構(gòu)造的散列函數(shù)為H(key)=(key*3)MOD10線性探測(cè)再散列函數(shù)為：Hi=(H(key)+di)MOD10,(di=1,2,3...9)因此，各數(shù)據(jù)的下標(biāo)為H(7)=(7*3)MOD10=1H(8)=(8*3)MOD10=4H(30)=(30*3)MOD10=0H(ll)=(11*3)MOD10=3H(18)=(18*3)MOD10=4Hl=(H(18)+1)MOD10=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+54-4+3+2+1+2+1+1)=3.2(1)建立一個(gè)可以放下p個(gè)整數(shù)的輔助隊(duì)列,將數(shù)組R中的前p個(gè)整數(shù)依次進(jìn)入輔助隊(duì)列，將R中后面的n-p個(gè)整數(shù)依次前移p個(gè)位置，將輔助隊(duì)列中的數(shù)據(jù)依次出隊(duì)，依次放入R中第n-p個(gè)整數(shù)開始的位置。(2)使用c語言描述算法如下：voidShift(int*pR,intn,intp)〃pR是指向數(shù)組R的指針，n為存放的整數(shù)個(gè)數(shù)，//p為循環(huán)左移的個(gè)數(shù){inttemplpl;//輔助數(shù)組，存放要移出的整數(shù)。inti=0;while(i<p){〃將R中前p個(gè)數(shù)據(jù)存入輔助數(shù)組中。temp|i]=pR|i|;i++；}=0;while(i<n-p){〃將R中從第p個(gè)整數(shù)開始的整數(shù)前移p個(gè)位置。pR|i|=pR|p+i|；i++；}=0;while(i<p){〃將輔助數(shù)組中的p個(gè)數(shù)據(jù)放到R中第n-p個(gè)數(shù)據(jù)的后面。pR[n-p+i|=temp|i|;i++;}return;}(3)所設(shè)計(jì)的算法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(p)OP字段占4個(gè)bit位，因此該指令系統(tǒng)最多有2八4=16條指令；Rs/Rd為3個(gè)bit,因此最多有27=8個(gè)通用寄存器；128K/2=64k=2八16,所以存儲(chǔ)器地址寄存器位數(shù)至少為16位，(勤思考研)指令字長度為16位，所以存儲(chǔ)器數(shù)據(jù)寄存器至少為16位。(2)因?yàn)镽n是16位寄存器，所以可以尋址的目標(biāo)地址范圍是64K,即整個(gè)存儲(chǔ)器空間。(3)對(duì)應(yīng)的機(jī)器碼是230DH,該指令執(zhí)行后R5的內(nèi)容變?yōu)?679H,地址5678H的內(nèi)容變?yōu)?8AC。解題思路：cache總?cè)萘康扔赾ache每一行的容量乘以cache的行數(shù)。(勤思考研)大家需要注意的是，本題cache總?cè)萘糠謩e等于數(shù)據(jù)cache和指令cache的總和。(2)分別計(jì)算出A|0H31|A|l||l|的地址的值，然后根據(jù)直接映射方式除以cache行的大小，與cache行數(shù)求余，所得的余數(shù)就是所映射的cache塊。cache的命中率等于訪問cache的次數(shù)除以cache的次數(shù)加上訪問內(nèi)存的次數(shù)。本題通過計(jì)算得知，命中率高的計(jì)算速度快。(1)2KB=2*1024*8bit=16384bit.因此可以使用位圖法進(jìn)行磁盤塊空閑狀態(tài)管理，(勤思考研)每1bit表示一個(gè)磁盤塊是否空閑。(2)每分鐘6000轉(zhuǎn)，轉(zhuǎn)一圈的時(shí)間為0.01s,通過一個(gè)扇區(qū)的時(shí)間為0.0001s。根據(jù)CSCAN算法，被訪問的磁道號(hào)順序?yàn)?00>120930950990,因此，尋道用去的總時(shí)間為：(20+90+20+40)*1ms=170ms總共要隨機(jī)讀取四個(gè)扇區(qū)，用去的時(shí)間為：(0.01*0.5+0.0001)*4=0.0204s=20.4ms所以，讀完這個(gè)扇區(qū)點(diǎn)共需要170ms+20.4ms=192.4ms,17CAH轉(zhuǎn)換為二進(jìn)制為：0001011111001010,頁的大小為1KB,(勤思考研)所以頁內(nèi)偏移為10位，于是前6位是頁號(hào)，所以其頁號(hào)為000101,轉(zhuǎn)換為10進(jìn)制為5,所以，17CA對(duì)應(yīng)的頁號(hào)為5。(2)若采用先進(jìn)先出置換算法，則被置換出的頁號(hào)對(duì)應(yīng)的頁框號(hào)是7,因此對(duì)應(yīng)的二進(jìn)制物理地址為：0001111111001010,轉(zhuǎn)換為16進(jìn)制位的物理地址為1FCAH。(3)若采用時(shí)鐘算法，且當(dāng)前指針指向2號(hào)頁框，則第一次循環(huán)時(shí)，訪問位都被置為0,在第二次循環(huán)時(shí)，將選擇置換2號(hào)頁框?qū)?yīng)的頁，因此對(duì)應(yīng)的二進(jìn)制物理地址為：0000101111001010,轉(zhuǎn)換為16進(jìn)制物理地址為0BCAH。47、(1)當(dāng)甲乙兩臺(tái)主機(jī)同時(shí)向?qū)Ψ桨l(fā)送數(shù)據(jù)時(shí)，兩臺(tái)主機(jī)均檢測(cè)到?jīng)_突的時(shí)間最短：Tmin=1KM/2OOOOOKM/S*2=10us當(dāng)一臺(tái)主機(jī)發(fā)送的數(shù)據(jù)就要到達(dá)另一臺(tái)主機(jī)時(shí)，另一臺(tái)主機(jī)才發(fā)送數(shù)據(jù)，(勤思考研)兩臺(tái)主機(jī)均檢測(cè)到?jīng)_突的時(shí)間最長：Tmax=2KM/200000KM/S*2=20us(2)主機(jī)甲發(fā)送一幀數(shù)據(jù)所需的時(shí)間為：Tl=1518B/10Mbps=1.2144ms數(shù)據(jù)在傳輸過程中所需的時(shí)間：T2=2KM/200000KM/S=0.01ms因此，主機(jī)甲的有效數(shù)據(jù)傳輸速率為：V=10Mbps*(Tl/(Tl+T2))=10Mbps*(1.2144ms/(1.2144ms+0.01ms))=9.92Mbps2011年計(jì)算機(jī)考研試題一、單項(xiàng)選擇題：1?40小題，每小題2分，共80分。

.設(shè)〃是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是x=2;while(x<n/2)x=2*x;A.O(log2〃)B.O(fi) C.O(iilog?")D.O(n2).元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是A.3 B.4 C.5 D.6.已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是A.0,0 B.0, C.71-1,0 D.M-1,/1-1.若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是A.257 B.258 C.384 D.385.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1.則該二叉樹的中序遍歷序列不會(huì)是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1.已知一棵有2011個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)為116,該樹對(duì)應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是A.115 B.116 C.1895 D.1896.對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是A.95,22,91,24,94,71 B.92,20,91,34,88,35C.21,89,77,29,36,38 D.12,25,71,68,33,34.下列關(guān)于圖的敘述中，正確的是.回路是簡單路徑.存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間.若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅H B.僅I、IIC.僅III D.僅I、III.為提高散列(Hash)表的查找效率，可以采取的正確措施是增大裝填(載)因子H.設(shè)計(jì)沖突(碰撞)少的散列函數(shù)III.處理沖突(碰撞)時(shí)避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅I B.僅II C.僅I、II D.僅II、III.為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是A.順序存儲(chǔ) B.散列存儲(chǔ) C.鏈?zhǔn)酱鎯?chǔ) D.索引存儲(chǔ).已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18,將其再調(diào)整為大根堆,調(diào)整過程中元素之間進(jìn)行的比較次數(shù)是B.2C.B.2C.4D.5.下列選項(xiàng)中，描述浮點(diǎn)數(shù)操作速度指標(biāo)的是A.MIPS B.CPI C.IPC D.MFLOPS.float型數(shù)據(jù)通常用IEEE754單精度浮點(diǎn)數(shù)格式表示。若編譯器將float型變量x分配在一個(gè)32位浮點(diǎn)寄存器FR1中，且x=-8.25,貝UFR1的內(nèi)容是A.C1040000H B.C2420000H C.C1840000H D.C1C20000H.下列各類存儲(chǔ)器中，不采用隨機(jī)存取方式的是A.EPROM B.CDROM C.DRAM D.SRAM.某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，主存地址空間大小為64MB,現(xiàn)用4Mx8位的RAM芯片組成32MB的主存儲(chǔ)器，則存儲(chǔ)器地址寄存器MAR的位數(shù)至少是A.22位 B.23位 C.25位 D.26位.偏移尋址通過將某個(gè)寄存器內(nèi)容與一個(gè)形式地址相加而生成有效地址。下列尋址方式中，不屬于偏移尋址方式的是A.間接尋址B.基址尋址 C.相對(duì)尋址 D.變址尋址.某機(jī)器有一個(gè)標(biāo)志寄存器，其中有進(jìn)位/借位標(biāo)志CF、零標(biāo)志ZF、符號(hào)標(biāo)志SF和溢出標(biāo)志OF,條件轉(zhuǎn)移指令bgt（無符號(hào)整數(shù)比較大于時(shí)轉(zhuǎn)移）的轉(zhuǎn)移條件是A.CF+OF=1B.SF+ZF=1C.CF+ZF=1 D.CF+SF=1.下列給出的指令系統(tǒng)特點(diǎn)中，有利于實(shí)現(xiàn)指令流水線的是.指令格式規(guī)整且長度一致 II.指令和數(shù)據(jù)按邊界對(duì)齊存放III.只有Load/Store指令才能對(duì)操作數(shù)進(jìn)行存儲(chǔ)訪問A.僅I、IIB.僅II、HIC.僅I、IIID.I、II、III.假定不采用Cache和指令預(yù)取技術(shù)，且機(jī)器處于“開中斷”狀態(tài)，則在下列有關(guān)指令執(zhí)行的敘述中，錯(cuò)送的是A.每個(gè)指令周期中CPU都至少訪問內(nèi)存一次B.每個(gè)指令周期一定大于或等于一個(gè)CPU時(shí)鐘周期C.空操作指令的指令周期中任何寄存器的內(nèi)容都不會(huì)被改變D.當(dāng)前程序在每條指令執(zhí)行結(jié)束時(shí)都可能被外部中斷打斷.在系統(tǒng)總線的數(shù)據(jù)線上，不可能傳輸?shù)氖茿.指令 B.操作數(shù)C.握手（應(yīng)答）信號(hào) D.中斷類型號(hào).某計(jì)算機(jī)有五級(jí)中斷L4~Lo，中斷屏蔽字為M4M3M2MlM0,Mi=l（0WiW4）表示對(duì)L1級(jí)中斷進(jìn)行屏蔽。若中斷響應(yīng)優(yōu)先級(jí)從高到低的順序是L°fL|fL2fL3fL.且要求中斷處理優(yōu)先級(jí)從高到低的順序?yàn)長s-Lo-L2-L1-L3,則Li的中斷處理程序中設(shè)置的中斷屏蔽字是A.11110 B.01101 C.00011 D.01010.某計(jì)算機(jī)處理器主頻為50MHz,采用定時(shí)查詢方式控制設(shè)備A的I/O,查詢程序運(yùn)行一次所用的時(shí)鐘周期數(shù)至少為500。在設(shè)備A工作期間，為保證數(shù)據(jù)不丟失，每秒需對(duì)其查詢至少200次，則CPU用于設(shè)備A的I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比至少是A.0.02% B.0.05% C.0.20% D.0.50%.下列選項(xiàng)中，滿足短任務(wù)優(yōu)先且不會(huì)發(fā)生饑餓現(xiàn)象的調(diào)度算法是A.先來先服務(wù) B.高響應(yīng)比優(yōu)先C.時(shí)間片輪轉(zhuǎn) D.非搶占式短任務(wù)優(yōu)先.下列選項(xiàng)中，在用戶態(tài)執(zhí)行的是A.命令解釋程序 B.缺頁處理程序C.進(jìn)程調(diào)度程序 D.時(shí)鐘中斷處理程序.在支持多線程的系統(tǒng)中，進(jìn)程P創(chuàng)建的若干個(gè)線程不能共享的是A.進(jìn)程P的代碼段 B.進(jìn)程P中打開的文件C.進(jìn)程P的全局變量 D.進(jìn)程P中某線程的棧指針.用戶程序發(fā)出磁盤I/O請(qǐng)求后，系統(tǒng)的正確處理流程是A.用戶程序f系統(tǒng)調(diào)用處理程序一中斷處理程序一設(shè)備驅(qū)動(dòng)程序B.用戶程序一系統(tǒng)調(diào)用處理程序f設(shè)備驅(qū)動(dòng)程序一中斷處理程序C.用戶程序一設(shè)備驅(qū)動(dòng)程序一系統(tǒng)調(diào)用處理程序一中斷處理程序D.用戶程序一設(shè)備驅(qū)動(dòng)程序一中斷處理程序一系統(tǒng)調(diào)用處理程序27.某時(shí)刻進(jìn)程的資源使用情況如下表所示。進(jìn)程已分配資源尚需資源可用資源R1R2R3R1R2R3R1R2R3P1200001021P2120132P3011131P4001200此時(shí)的安全序列是A.Pl,P2,P3,P4 B.Pl,P3,P2,P4C.Pl,P4,P3,P2 D.不存在.在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能是.修改頁表 II.磁盤I/OIII.分配頁框A.僅I、II B.僅n C.僅III D.I、II和III.當(dāng)系統(tǒng)發(fā)生抖動(dòng)(thrashing)時(shí)，可以采取的有效措施是.撤銷部分進(jìn)程.增加磁盤交換區(qū)的容量.提高用戶進(jìn)程的優(yōu)先級(jí)A.僅I B.僅H C.僅III D.僅I、II

.在虛擬內(nèi)存管理中，地址變換機(jī)構(gòu)將邏輯地址變換為物理地址，形成該邏輯地址的階段是A.編輯 B.編譯 C.鏈接 D.裝載.某文件占10個(gè)磁盤塊，現(xiàn)要把該文件磁盤塊逐個(gè)讀入主存緩沖區(qū)，并送用戶區(qū)進(jìn)行分析。假設(shè)一個(gè)緩沖區(qū)與一個(gè)磁盤塊大小相同，把一個(gè)磁盤塊讀入緩沖區(qū)的時(shí)間為100”,將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時(shí)間是50州，CPU對(duì)一塊數(shù)據(jù)進(jìn)行分析的時(shí)間為50Ms.在單緩沖區(qū)和雙緩沖區(qū)結(jié)構(gòu)下，讀入并分析完該文件的時(shí)間分別是A.1500即、1000ps B.1550、1100C.1550ps、1550ps D.2000 2000gs.有兩個(gè)并發(fā)執(zhí)行的進(jìn)程Pl和P2,共享初值為1的變量x。P1對(duì)x加1,「2對(duì)工減1。加1和減1操作的指令序列分別如下所示。//加1操作 〃減1操作TOC\o"1-5"\h\zload RI,x // 取 x 到寄存器 R1 中 load R2,xinc RI dec R2store x,RI 〃將 RI 的內(nèi)容存入 x store x,R2兩個(gè)操作完成后，x的值B.只能為1D.可能為-1B.只能為1D.可能為-1、0、1或2B.無連接可靠的數(shù)據(jù)報(bào)服務(wù)D.有連接可靠的虛電路服務(wù)C.可能為0、1或2TCP/IP參考模型的網(wǎng)絡(luò)層提供的是A.無連接不可靠的數(shù)據(jù)報(bào)服務(wù)C.有連接不可靠的虛電路服務(wù)34.若某通信鏈路的數(shù)據(jù)傳輸速率為2400bps,采用4相位調(diào)制，則該鏈路的波特率是A.600波特B.1200波特C.4800波特D.9600波特.數(shù)據(jù)鏈路層采用選擇重傳協(xié)議(SR)傳輸數(shù)據(jù)，發(fā)送方已發(fā)送了0?3號(hào)數(shù)據(jù)幀，現(xiàn)已收到1號(hào)幀的確認(rèn)，而0、2號(hào)幀依次超時(shí)，則此時(shí)需要重傳的幀數(shù)是A.1 B.2 C.3 D.4.下列選項(xiàng)中，對(duì)正確接收到的數(shù)據(jù)幀進(jìn)行確認(rèn)的MAC協(xié)議是A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA.某網(wǎng)絡(luò)拓?fù)淙缦聢D所示，路由器R1只有到達(dá)子網(wǎng)/24的路由。為使R1可以將IP分組正確地路由到圖中所有子網(wǎng)，則在R1中需要增加的一條路由(目的網(wǎng)絡(luò),子網(wǎng)掩碼，下一跳)是R1A.,28,B.,,C.,28,D.,,.在子網(wǎng)192,168.4.0/30中，能接收目的地址為的IP分組的最大主機(jī)數(shù)是A.0 B.1 C.2 D.4.主機(jī)甲向主機(jī)乙發(fā)送一個(gè)(SYN=l,seq=11220)的TCP段，期望與主機(jī)乙建立TCP連接，若主機(jī)乙接受該連接請(qǐng)求，則主機(jī)乙向主機(jī)甲發(fā)送的正確的TCP段可能是(SYN=0,ACK=0,seq=11221,ack=11221)(SYN=1,ACK=1,seq=11220,ack=11220)(SYN=1,ACK=1,seq=11221,ack=11221)(SYN=0,ACK=0,seq=11220,ack=11220).主機(jī)甲與主機(jī)乙之間已建立一個(gè)TCP連接，主機(jī)甲向主機(jī)乙發(fā)送了3個(gè)連續(xù)的TCP段，分別包含300字節(jié)、400字節(jié)和500字節(jié)的有效載荷，第3個(gè)段的序號(hào)為900。若主機(jī)乙僅正確接收到第1和第3個(gè)段，則主機(jī)乙發(fā)送給主機(jī)甲的確認(rèn)序號(hào)是A.300 B.500 C.1200 D.1400二、綜合應(yīng)用題：41?47小題，共70分。(8分)已知有6個(gè)頂點(diǎn)(頂點(diǎn)編號(hào)為0~5)的有向帶權(quán)圖G,其鄰接矩陣A為上三角矩陣，按行為主序(行優(yōu)先)保存在如下的一維數(shù)組中。要求：(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權(quán)圖Go(3)求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長度。(15分)一個(gè)長度為L(L21)的升序序列S,處在第「L/21個(gè)位置的數(shù)稱為S的中位數(shù)。例如，若序列Sl=(ll,13,15,17,19),則S1的中位數(shù)是15.兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=(2,4,6,8,20),則S1和S2的中位數(shù)是11?，F(xiàn)有兩個(gè)等長升序序列A和B,試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列A和B的中位數(shù)。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。（11分）假定在一個(gè)8位字長的計(jì)算機(jī)中運(yùn)行如下類C程序段：unsignedintx=134;unsignedinty=246;intm=x;intn=y;unsignedintzl=x-y;unsignedintz2=x+y;intkl=m-n;intk2=m+n;若編譯器編譯時(shí)將8個(gè)8位寄存器Rl?R8分別分配給變量x、八〃?、〃、zl、dkl和A2。請(qǐng)回答下列問題。（提示：帶符號(hào)整數(shù)用補(bǔ)碼表示）（1）執(zhí)行上述程序段后，寄存器RI、R5和R6的內(nèi)容分別是什么？（用十六進(jìn)制表示）（2）執(zhí)行上述程序段后，變量機(jī)和X的值分別是多少？（用十進(jìn)制表示）（3）上述程序段涉及帶符號(hào)整數(shù)加/減、無符號(hào)整數(shù)加/減運(yùn)算，這四種運(yùn)算能否利用同一個(gè)加法器及輔助電路實(shí)現(xiàn)？簡述理由。（4）計(jì)算機(jī)內(nèi)部如何判斷帶符號(hào)整數(shù)加/減運(yùn)算的結(jié)果是否發(fā)生溢出？上述程序段中，哪些帶符號(hào)整數(shù)運(yùn)算語句的執(zhí)行結(jié)果會(huì)發(fā)生溢出？（12分）某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，虛擬（邏輯）地址空間大小為16MB,主存（物理）地址空間大小為1MB,頁面大小為4KB；Cache采用直接映射方式，共8行；主存與Cache之間交換的塊大小為32B。系統(tǒng)運(yùn)行到某一時(shí)刻時(shí)，頁表的部分內(nèi)容和Cache的部分內(nèi)容分別如題44-a圖、題44-b圖所示，圖中頁框號(hào)及標(biāo)記字段的內(nèi)容為十六進(jìn)制形式。虛頁號(hào)有效位頁框號(hào)- 行號(hào)有效位標(biāo)記 ...010601020110410-21152101D31023110540-41064512B5114D60-60-71327127A題44-a圖頁表的部分內(nèi)容題44-b圖Cache的部分內(nèi)容請(qǐng)回答下列問題。(1)虛擬地址共有幾位，哪幾位表示虛頁號(hào)？物理地址共有幾位，哪幾位表示頁框號(hào)(物理頁號(hào))？(2)使用物理地址訪問Cache時(shí)，物理地址應(yīng)劃分成哪幾個(gè)字段？要求說明每個(gè)字段的位數(shù)及在物理地址中的位置。(3)虛擬地址001C60H所在的頁面是否在主存中？若在主存中，則該虛擬地址對(duì)應(yīng)的物理地址是什么？訪問該地址時(shí)是否Cache命中？要求說明理由。(4)假定為該機(jī)配置一個(gè)4路組相聯(lián)的TLB,該TLB共可存放8個(gè)頁表項(xiàng)，若其當(dāng)前內(nèi)容(十六進(jìn)制)如題44-c圖所示，則此時(shí)虛擬地址024BACH所在的頁面是否在主存中？要求說明理由。組號(hào)有效位標(biāo)記頁框號(hào)有效位標(biāo)記頁框號(hào)有效位標(biāo)記頁框號(hào)有效位標(biāo)記頁框號(hào)0-—1001150-—10121F10132D0--10087E0-—題44y圖TLB的部分內(nèi)容(8分)某銀行提供1個(gè)服務(wù)窗口和1。個(gè)供顧客等待的座位。顧客到達(dá)銀行時(shí)，若有空座位，則到取號(hào)機(jī)上領(lǐng)取一個(gè)號(hào)，等待叫號(hào)。取號(hào)機(jī)每次僅允許一位顧客使用。當(dāng)營業(yè)員空閑時(shí)，通過叫號(hào)選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動(dòng)過程描述如下：cobegin{process顧客i(從取號(hào)機(jī)獲得一個(gè)號(hào)碼；等待叫號(hào)；獲得服務(wù)；}process營業(yè)員(while(TRUE)(叫號(hào)；為顧客服務(wù)；}coend請(qǐng)?zhí)砑颖匾男盘?hào)量和P、V(或wait。、signal())操作，實(shí)現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號(hào)量的含義并賦初值。

(7分)某文件系統(tǒng)為一級(jí)目錄結(jié)構(gòu)，文件的數(shù)據(jù)一次性寫入磁盤，已寫入的文件不可修改，但可多次創(chuàng)建新文件。請(qǐng)回答如下問題。(1)在連續(xù)、鏈?zhǔn)?、索引三種文件的數(shù)據(jù)塊組織方式中，哪種更合適？要求說明理由。為定位文件數(shù)據(jù)塊，需在FCB中設(shè)計(jì)哪些相關(guān)描述字段？(2)為快速找到文件，對(duì)于FCB,是集中存儲(chǔ)好，還是與對(duì)應(yīng)的文件數(shù)據(jù)塊連續(xù)存儲(chǔ)好？要求說明理由。(9分)某主機(jī)的MAC地址為00-15"C5CL5E-28,IP地址為00(私有地址題47-a圖是網(wǎng)絡(luò)拓?fù)?，題47-b圖是該主機(jī)進(jìn)行Web請(qǐng)求的1個(gè)以太網(wǎng)數(shù)據(jù)幀前80個(gè)字節(jié)的十六進(jìn)制及ASCII碼內(nèi)容。MTU=1500B題47-a圖網(wǎng)絡(luò)拓?fù)?000 00 21 27MTU=1500B題47-a圖網(wǎng)絡(luò)拓?fù)?000 00 21 27 210010 01 ef 11 3b0020 62 20 04 ff0030 fa fO la c40040 74 6d 6c 20562501064500074o8e45600046050510008540045ao4fcbo52cl5e28080045009d0a02806440aafa7bf9f8055018202f7266632e68312e31OdOa4163.!IQ A(?.E.???；@????????d@?b???P????{???P? GET/rfc.htmlHTTP/l.l..Ac題47?b圖以太網(wǎng)數(shù)據(jù)幀(前80字節(jié))請(qǐng)參考圖中的數(shù)據(jù)回答以下問題。Web服務(wù)器的IP地址是什么？該主機(jī)的默認(rèn)網(wǎng)關(guān)的MAC地址是什么？(2)該主機(jī)在構(gòu)造題47-b圖的數(shù)據(jù)幀時(shí)，使用什么協(xié)議確定目的MAC地址？封裝該協(xié)議請(qǐng)求報(bào)文的以太網(wǎng)幀的目的MAC地址是什么？(3)假設(shè)HTTP/1.1協(xié)議以持續(xù)的非流水線方式工作，一次請(qǐng)求-響應(yīng)時(shí)間為RTT,rfc.html頁面引用了5個(gè)JPEG小圖像，則從發(fā)出題47-b圖中的Web請(qǐng)求開始到瀏覽器收到全部內(nèi)容為止，需要多少個(gè)RTT?(4)該幀所封裝的IP分組經(jīng)過路由器R轉(zhuǎn)發(fā)時(shí)，需修改IP分組頭中的哪些字段？參考答案A2.B3.B4.C5.C6.D7.A8.C9.B10.All.B12.D13.A14,B15.D16.A17.C18.D19.C20.C21.D22.C23.B24.A25.D26.B27.D28.D29.A30.B31.B32.C33.A34.B35.B36.D37.D38.C39.CB(1)由題可以畫出待定上三角矩陣的結(jié)構(gòu)圖如下(圖中“？”待定元素)

0??9?000????000009??0000oo097000000000900000000000可以看出，第一行至第五行主對(duì)角線上方的元素分別5、4、3、2、1個(gè)，由此可以畫出壓縮存儲(chǔ)數(shù)組中的元素所屬行的情況，如下圖所示:第一行第二行第三行第一行第二行第三行將個(gè)元素填入各行即得鄰接矩陣：（2分）（2）根據(jù)第一步所得矩陣A（2）根據(jù)第一步所得矩陣A容易做出有向帶權(quán)圖G,如下：（2分）04600000000050000000000043000000000003000000000300000000000（3）下圖中粗線箭頭所標(biāo)識(shí)的4個(gè)活動(dòng)組成G的關(guān)鍵路徑（3分）由上圖容易求得圖的關(guān)鍵路徑長度為：4+5+4+3=16。42.【答案解析】此題考察的知識(shí)點(diǎn)是基本算法的靈活運(yùn)用。(1)算法的基本設(shè)計(jì)思想：(5分)1)比較笨的方法：將兩升序序列歸并排序，然后求其中位數(shù)，時(shí)間復(fù)雜度是O(n),空間復(fù)雜度O(n)。2)高效的方法：分別求兩個(gè)升序序列A和B的中位數(shù)，設(shè)為a和b。如果a=b,則a或者b即為所求的中位數(shù)。原因：如果將兩序列歸并排序，則最終序列中，排在子序列ab前邊的元素為先前兩序列中排在a和b前邊的元素；排在子序列ab后邊的元素為先前兩序列a和b后邊的元素。所以子序列ab一定位于最終序列的中間，有因?yàn)閍=b,顯然a就是中位數(shù)。如果a#b(假設(shè)a<b),中位數(shù)只能出現(xiàn)在(a,b)范圍內(nèi)。原因：同樣可以用歸并排序后的序列來驗(yàn)證，歸并后排序后必然有形如…a…b…的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在(a,b)范圍內(nèi)。因此可以做如下處理：舍棄a所在序列A之中比較小的一半，同時(shí)舍棄b所在序列B之中比較大的一半。在保留的兩個(gè)升序序列中求出新的中位數(shù)a和b,重復(fù)上述過程，直到兩個(gè)序列只含一個(gè)元素為止，則較小者即為所求中位數(shù)。(2)算法實(shí)現(xiàn)(高效方法)：(8分)intSearch(intA[],intB[],intn)(intsi,el,midi,s2,e2,mid2;sl=O;el=n-l;s2=l;e2=n-l;while(si!=el||s2!=e2)(midl=(sl+el)/2;mid2=(s2+e2)/2;if(A[midl]==B[mid2])returnA[midl];if(A[midl]