408計算機專業(yè)基礎(chǔ)綜合歷年真題 09-17

考研計算機計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)408真題及答案2009年-2017年1考研計算機2009年全國碩士研究生入學(xué)統(tǒng)一考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題：第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求。1．為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，的邏輯結(jié)構(gòu)應(yīng)該是A．棧B．隊列C．樹．圖2．設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a，b，c，de，f，g依次進入棧S。若每個元素出棧后立即進入隊列Q7個元素出隊的順序是bcfeagS的容量至少是A．1B．2C．3D．43．給定二叉樹如右圖所示。設(shè)代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3，175，62，，則其遍歷方式是A．LRNB．NRLC．RLND．RNL4．下列二叉排序樹中，滿足平衡二叉樹定義的是56層(設(shè)根為第1層)有8數(shù)最多是A．39B．52C．111D．1196．將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和可能具有的關(guān)系是Ⅰ．父子關(guān)系Ⅱ．兄弟關(guān)系Ⅲ．u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系A(chǔ)．只有ⅡB．Ⅰ和ⅡC．Ⅰ和Ⅲ．Ⅰ、Ⅱ和Ⅲ7．下列關(guān)于無向連通圖特性的敘述中，正確的是3新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機Ⅰ．所有頂點的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點個數(shù)減1Ⅲ．至少有一個頂點的度為1A．只有ⅠB．只有ⅡC．Ⅰ和Ⅱ．Ⅰ和Ⅲ8．下列敘述中，不符合階B樹定義要求的是．A．根結(jié)點最多有棵子樹B．所有葉結(jié)點都在同一層上C．各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列．葉結(jié)點之間通過指針鏈接9．已知關(guān)鍵字序列，8，12，，282015，22是小根堆(最小堆)，插入關(guān)鍵字3，調(diào)整后得到的小根堆是A．3，，128，，201522，B．3，512，192015，22，8C．3，，125，，152228，D．3，12，8，28，，152210．若數(shù)據(jù)元素序列111213，78，，234，是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A．起泡排序11·CPU區(qū)分它們的依據(jù)是A．指令操作碼的譯碼結(jié)果C．指令周期的不同階段B．插入排序C．選擇排序．二路歸并排序B．指令和數(shù)據(jù)的尋址方式．指令和數(shù)據(jù)所在的存儲單元12C語言程序在一臺32位機器上運行。程序中定義了三個變量x和zx和z為int型，為short型。當(dāng)x=127，y=-9時，執(zhí)行賦值語句z=z+y后，x、和z的值分別是A．x=0000007FH，y=FFF9H，z=00000076HB．x=0000007FH，y=FFF9H，z=FFFF0076HC．x=0000007FH，y=FFF7H，z=FFFF0076HD．x=0000007FH，y=FFF7H，z=00000076H13．浮點數(shù)加、減運算過程一般包括對階、尾數(shù)運算、規(guī)格化、舍入和判溢出等步驟。設(shè)浮點數(shù)的階碼和尾數(shù)均采用補碼表示，且位數(shù)分別為57位(均含位符號位)。若有兩75個數(shù)X=2×29/32，×5/8，則用浮點加法計算X+Y的最終結(jié)果是A．001111100010B．001110100010C．010000010001D．發(fā)生溢出14．某計算機的Cache共有16塊，采用2路組相聯(lián)映射方式(即每組2塊)。每個主存塊大小為32字節(jié)，按字節(jié)編址。主存129號單元所在主存塊應(yīng)裝入到的Cache組號是A．0B．2C．4．615．某計算機主存容量為64，其中ROM區(qū)為4KB，其余為RAM區(qū)，按字節(jié)編址?，F(xiàn)要用2K×8位的ROM芯片和4K×4RAM芯片來設(shè)計該存儲器，則需要上述規(guī)格的ROM芯片數(shù)和RAM芯片數(shù)分別是A．1、B．2、C．1、D．2、301616一字節(jié)為操作碼字段，第二字節(jié)為相對位移量字段。假定取指令時，每取一個字節(jié)PC自動加12000H06H功轉(zhuǎn)移后的目標(biāo)地址是A．2006HB．2007HC．2008H．2009H17．下列關(guān)于RISC的敘述中，錯誤的是．．A．RISC普遍采用微程序控制器B．RISC大多數(shù)指令在一個時鐘周期內(nèi)完成C．RISC的內(nèi)部通用寄存器數(shù)量相對CISC多D．RISC的指令數(shù)、尋址方式和指令格式種類相對CISC少4新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機18．某計算機的指令流水線由四個功能段組成，指令流經(jīng)各功能段的時間(忽略各功能段之間的緩存時間)分別為90ns、ns、70ns60ns，則該計算機的CPU時鐘周期至少是A．90nsB．80nsC．70nsD．60ns19．相對于微程序控制器，硬布線控制器的特點是A．指令執(zhí)行速度慢，指令功能的修改和擴展容易B．指令執(zhí)行速度慢，指令功能的修改和擴展難C．指令執(zhí)行速度快，指令功能的修改和擴展容易D．指令執(zhí)行速度快，指令功能的修改和擴展難2042周期，總線時鐘頻率為10MHz，則總線帶寬是A．10MB/sB．20MB/sC．40MB/sD．80MB/s21Cache1000中訪問Cache缺失(未命中)50次，則Cache的命中率是A．5％22．下列選項中，能引起外部中斷的事件是A．鍵盤輸入B．除數(shù)為0C．浮點運算下溢D．訪存缺頁23．單處理機系統(tǒng)中，可并行的是B．9.5％C．50％D．95％Ⅰ．進程與進程Ⅱ．處理機與設(shè)備Ⅲ．處理機與通道Ⅳ．設(shè)備與設(shè)備A．Ⅰ、Ⅱ和ⅢB．Ⅰ、Ⅱ和ⅣC．Ⅰ、Ⅲ和ⅣD．Ⅱ、Ⅲ和Ⅳ24．下列進程調(diào)度算法中，綜合考慮進程等待時間和執(zhí)行時間的是A．時間片輪轉(zhuǎn)調(diào)度算法B．短進程優(yōu)先調(diào)度算法C．先來先服務(wù)調(diào)度算法D．高響應(yīng)比優(yōu)先調(diào)度算法258K3臺打印機。該系統(tǒng)可能會發(fā)生死鎖的K的最小值是A．226．分區(qū)分配內(nèi)存管理方式的主要保護措施是A．界地址保護B．程序代碼保護C．?dāng)?shù)據(jù)保護B．3C．4D．5D．棧保護27．一個分段存儲管理系統(tǒng)中，地址長度為32位，其中段號占8位，則最大段長是A．28B．216字節(jié)C．224字節(jié)D．232字節(jié)28．下列文件物理結(jié)構(gòu)中，適合隨機訪問且易于文件擴展的是A．連續(xù)結(jié)構(gòu)B．索引結(jié)構(gòu)C．鏈式結(jié)構(gòu)且磁盤塊定長D．鏈式結(jié)構(gòu)且磁盤塊變長29．假設(shè)磁頭當(dāng)前位于第105道，正在向磁道序號增加的方向移動。現(xiàn)有一個磁道訪問請求序列為35，45，1268110，180，170195，采用SCAN調(diào)度(電梯調(diào)度)算法得到的磁道訪問序列是A．110，170，180，195，68453512170，180195C．110，170，180，195，12354568170，18019530．文件系統(tǒng)中，文件訪問控制信息存儲的合理位置是A．文件控制塊B．文件分配表C．用戶口令表D．系統(tǒng)注冊表B110453512，12354568110，31．設(shè)文件F1的當(dāng)前引用計數(shù)值為1，先建立F1的符號鏈接(軟鏈接)文件F2，再建立F1的硬鏈接文件F3，然后刪除F1。此時，F(xiàn)2和F3的引用計數(shù)值分別是A．0、1B．1、1C．1、2D．2、15新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機32．程序員利用系統(tǒng)調(diào)用打開I/O設(shè)備時，通常使用的設(shè)備標(biāo)識是A．邏輯設(shè)備名33．在參考模型中，自下而上第一個提供端到端服務(wù)的層次是A．?dāng)?shù)據(jù)鏈路層B．傳輸層C．會話層D．應(yīng)用層B．物理設(shè)備名C．主設(shè)備號D．從設(shè)備號34．在無噪聲情況下，若某通信鏈路的帶寬為3kHz，采用4個相位、每個相位具有4種振幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是A．12kbpsB．24kbpsC．48kbps．96kbps35．?dāng)?shù)據(jù)鏈路層采用后退N幀(GBN)協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號為～7的幀。當(dāng)計時器超時時，若發(fā)送方只收到0、2號幀的確認，則發(fā)送方需要重發(fā)的幀數(shù)是A．236．以太網(wǎng)交換機進行轉(zhuǎn)發(fā)決策時使用的PDU地址是A．目的物理地址B．目的IP地址C．源物理地址D．源IP地址B．3C．4D．537．在一個采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為1Gbps，電纜中的信號傳播速度是200000km/s。若最小數(shù)據(jù)幀長度減少800比特，則最遠的兩個站點之間的距離至少需要A．增加160mB．增加80mC．減少160m．減少80m38TCPTCP段，分別包含300字節(jié)和500字節(jié)的有效載荷，第一個段的序列號為200，主機乙正確接收到兩個段后，發(fā)送給主機甲的確認序列號是A．500B．700C．800D．100039．一個TCP連接總是以1KB的最大段長發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時發(fā)生了超時，如果接下來的4個RTT(往返時間)時間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)趥€RTT時間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時，擁塞窗口大小是A．7KBB．8KBC．9KBD．16KB40．FTP客戶和服務(wù)器間傳遞FTP命令時，使用的連接是A．建立在TCP之上的控制連接B．建立在TCP之上的數(shù)據(jù)連接C．建立在UDP之上的控制連接D．建立在UDP之上的數(shù)據(jù)連接二、綜合應(yīng)用題：第41～47小題，共70分。41．分)帶權(quán)圖(權(quán)值非負，表示邊連接的兩頂點間的距離)的最短路徑問題是找出從一種解決該問題的方法：①設(shè)最短路徑初始時僅包含初始頂點，令當(dāng)前頂點u為初始頂點；②選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當(dāng)前頂點u=v；③重復(fù)步驟②，直到u是目標(biāo)頂點時為止。請問上述方法能否求得最短路徑?若該方法可行，請證明之；否則，請舉例說明。42分)已知一個帶有表頭結(jié)點的單鏈表，結(jié)點結(jié)構(gòu)為datalink了頭指針listk個位置上的結(jié)點(k為正整數(shù))data1只返回0。要求：(1)描述算法的基本設(shè)計思想；(2)描述算法的詳細實現(xiàn)步驟；(3)根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言描述算法(使用C、C++或Java語言實6新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機現(xiàn))，關(guān)鍵之處請給出簡要注釋。43．(8)某計算機的CPU主頻為500MHz，為5(即執(zhí)行每條指令平均需5個時鐘周期)。假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB/s，采用中斷方式與主機進行數(shù)據(jù)傳送，以32位為傳輸單位，對應(yīng)的中斷服務(wù)程序包含18條指令，中斷服務(wù)的其他開銷相當(dāng)于2條指令的執(zhí)行時間。請回答下列問題，要求給出計算過程。(1)在中斷方式下，CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比是多少?(2)當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達到5MB/sDMADMA傳送塊大小為5000BDMA預(yù)處理和后處理的總開銷為500CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比是多少?(假設(shè)與CPU之間沒有訪存沖突)44(13分)某計算機字長1616位定長指令字結(jié)構(gòu)，部分數(shù)據(jù)通路結(jié)構(gòu)如下圖所示，圖中所有控制信號為1時表示有效、為0時表示無效，例如控制信號MDRinE1表示允許數(shù)據(jù)從DB打入MDRMDRin1表示允許數(shù)據(jù)從內(nèi)總線打入MDRMAR的輸出一直處于使能狀態(tài)。加法指令“ADD(R1)，R0”的功能為(R0)+((R1))→(R1)，即將R0中的數(shù)據(jù)與R1的內(nèi)容所指主存單元的數(shù)據(jù)相加，并將結(jié)果送人R1的內(nèi)容所指主存單元中保存。下表給出了上述指令取指和譯碼階段每個節(jié)拍(時鐘周期)表中描述方式用表格列出指令執(zhí)行階段每個節(jié)拍的功能和有效控制信號。．．．．．．．．功能時鐘有效控制信號C1MAR←(PC)PCoutMARinMDR←IM(MAR)MemR，MDRinEC2PC←(PC)+1PC+1C3C4IR←(MDR)MDRout，IRin指令譯碼無45．(7)三個進程P1、P2、P3互斥使用一個包含N(N>0)個單元的緩沖區(qū)。P1每次用7新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機produce(生成一個正整數(shù)并用put(送入緩沖區(qū)某一空單元中；P2每次用getodd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd(統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven(從該緩沖區(qū)中取出一個偶數(shù)并用counteven(明所定義信號量的含義。要求用偽代碼描述。46．(8)請求分頁管理系統(tǒng)中，假設(shè)某進程的頁表內(nèi)容如下表所示：頁號頁框(PageFrame)號有效位(存在位)012101H—101254H頁面大小為4KB，一次內(nèi)存的訪問時間是100ns，一次快表(TLB)的訪問時間是10ns，處理一次缺頁的平均時間為108ns(已含更新TLB和頁表的時間)2，采用最近最少使用置換算法(LRU)和局部淘汰策略。假設(shè)①TLB初始為空；②地址轉(zhuǎn)換時先訪問TLBTLB未命中，再訪問頁表(忽略訪問頁表之后的TLB更新時間)；③有效位為0行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：(1)依次訪問上述三個虛地址，各需多少時間?給出計算過程。(2)基于上述訪問序列，虛地址1565H的物理地址是多少?請說明理由。47．(9)某網(wǎng)絡(luò)拓撲如下頁圖所示，路由器R1通過接口E1、E2分別連接局域網(wǎng)1域網(wǎng)2，通過接口L0連接路由器R2，并通過路由器R2連接域名服務(wù)器與互聯(lián)網(wǎng)。R1的L0接口的IP地址是；R2的L0接口的IP地址是，L1接口的IP地址是，E0接口的IP地址是；域名服務(wù)器的IP地址是。R1和的路由表結(jié)構(gòu)為：目的網(wǎng)絡(luò)IP地址子網(wǎng)掩碼下一跳IP地址接口(1)將IP地址空間/24劃分為2個子網(wǎng)，分別分配給局域網(wǎng)12域網(wǎng)需分配的IP地址數(shù)不少于120個。請給出子網(wǎng)劃分結(jié)果，說明理由或給出必要的計算過程。(2)請給出R1的路由表，使其明確包括到局域網(wǎng)1的路由、局域網(wǎng)2的路由、域名服務(wù)器的主機路由和互聯(lián)網(wǎng)的路由。(3)請采用路由聚合技術(shù)，給出R2到局域網(wǎng)和局域網(wǎng)2的路由。8新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機計算機學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案及解析(2009年)一、單項選擇題1．B2．C3．D4．B5．C6．B7．A8．D9．A10．B11．C12．D13．D14．C15．D16．C17．A18．A19．D20．B21．D22．A23．D24．D25．C26．A27．C28．B29．A30．A31．B32．A33．B34．B35．C36．A37．D38．D39．C9新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機40．A二、綜合應(yīng)用題41．【答案要點】該方法不一定能(或不能)求得最短路徑。舉例說明如下：圖a圖b圖a中，設(shè)初始頂點為1，目標(biāo)頂點為4，欲求從頂點1到頂點4之間的最短路徑。顯然，這兩點之間的最短路徑長度為23這兩點之間的最短路徑。圖b中，設(shè)初始頂點為1，目標(biāo)頂點為3，欲求從頂點1到頂點3之間的最短路徑。利用給定的方法，無法求出頂點1到頂點的路徑。42．【答案要點】(1)算法的基本設(shè)計思想：定義兩個指針變量和q，初始時均指向頭結(jié)點的下一個結(jié)點。p指針沿鏈表移動；當(dāng)p指針移動到第k個結(jié)點時，q指針開始與pp指針移動到鏈表最后一個結(jié)點時，q指針?biāo)冈貫榈箶?shù)第個結(jié)點。以上過程對鏈表僅進行一遍掃描。(2)算法的詳細實現(xiàn)步驟：①count=0，pq指向鏈表表頭結(jié)點的下一個結(jié)點；②若p為空，轉(zhuǎn)⑤；③若count等于k指向下一個結(jié)點；否則，count=count+1；④p指向下一個結(jié)點，轉(zhuǎn)步驟②；⑤若count等于kdata1回0：⑥算法結(jié)束。(3)算法實現(xiàn)：typedefstructLNode{intdata：structLNode*link；}*LinkList；intSearchN(LinkListlist，intk){LinkListp，q；intcount=0：/*計數(shù)器賦初值*/p=q=list->link；while(p!=NULL){/*pq指向鏈表表頭結(jié)點的下一個結(jié)點*/if(count<k)count++；/*計數(shù)器+1*/elseq=q->link；/*q移到下一個結(jié)點*//*p移到下一個結(jié)點*/p=p->link；10新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機}if(count<k)return(0)；/*如果鏈表的長度小于，查找失敗//else{printf(”％d”，q->data)；/*查找成功*/return(1)；}}43．【答案要點】(1)中斷方式下，CPU每次用于數(shù)據(jù)傳送的時鐘周期數(shù)：5×18+5×2=100。為達到外設(shè)0.5MB/s的數(shù)據(jù)傳輸率，外設(shè)每秒申請的中斷次數(shù)：0.5MB/4B=125000。1秒鐘內(nèi)用于中斷的開銷：100×l25000=12500000=12.5M個時鐘周期。CPU用于外設(shè)I/O的時間占整個CPU時間的百分比：12.5M/500M=2.5％。(2)外設(shè)數(shù)據(jù)傳輸率提高到5MB/s時，1秒鐘內(nèi)需產(chǎn)生的DMA次數(shù)：5MB/5000B=1000。CPU用于DMA處理的總開銷：1000×500=500000=0.5個時鐘周期。CPU用于外設(shè)I/O的時間占整個CPU時間的百分比：0.5M/500M=0.144．【答案要點】參考答案一：時鐘功能有效控制信號C5MAR←(R1)R1outMARinMDR←M(MAR)MemR，MDRinEC6C7C8C9A←(R0)R0out，AC←(MDR)+(A)MDR←(AC)MDRout，Add，ACinACoutMDRinM(MAR)←(MDR)MDRoutEMemW←(R0)”也可在C7“AC←(MDR)+(A)”時鐘C5功能有效控制信號R1outMARinMAR←(R1)C6MDR←M(MAR)A←(MDR)MemR，MDRinEMDRout，C7C8AC←(A)+(RO)MDR←(AC)R0out，，ACinACoutMDRinMDRoutEMemWC9C10M(MAR)←(MDR)45．【答案要點】(1)緩沖區(qū)是一互斥資源，因此設(shè)互斥信號量mutex。(2)P1P2oddP1P3因為偶數(shù)的放置與取用而同步，設(shè)同步信號量even；P1、P2、P3因為共享緩沖區(qū)，設(shè)同步信號量empty。semaphoremutex=1;semaphoreodd=0,even=0;semaphoreempty=N;()cobegin{新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機ProcessP1while(True){number=produce();P(empty);P(mutex);put();V(mutex);ifnumber%2==0V(even);elseV(odd);{ProcessP2while(True)P(odd);P(mutex);getodd();V(mutex);V(empty);countodd();{ProcessP3while(true){P(even);P(mutex);geteven();V(mutex);V(empty);counteven();{}coend46．【答案要點】大小為4KB=212B，則得到頁內(nèi)位移占虛地址的低12位，頁號占剩余高位。頁號/頁框號（4位）頁內(nèi)偏移量（12位）(1)可得三個虛地址的頁號P及訪問時間如下(十六進制的一位數(shù)字轉(zhuǎn)換成4位二進制，因此，十六進制的低12位正好為頁內(nèi)位移，最高位為頁號)：1)2362HP=2110ns100ns100ns10ns+100ns+100ns=210ns．2)1565HP=1010ns100ns，落空，進行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，共計10ns+10012新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機n8+108ns+100ns=100000220ns．3)25A5H：頁號P=2，有效位為，存在內(nèi)存中。訪問快表，因第一次訪問已將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存100ns，共計10ns+100ns=110ns。(2)當(dāng)訪問虛地址1565H時，產(chǎn)生缺頁中斷，由于駐留集大小固定為，必須從頁表中淘汰一個頁面。根據(jù)題目規(guī)定的最近最少使用置換算法，應(yīng)淘汰0號頁面，因此1565H的對應(yīng)頁框號為101H。由此可得1565H的物理地址為101565H。47．【答案要點】(1)把IP地址空間/24劃分為2個等長的子網(wǎng)。劃分結(jié)果為：子網(wǎng)1：子網(wǎng)地址為，子網(wǎng)掩碼為28(或子網(wǎng)1：/25)子網(wǎng)2：子網(wǎng)地址為28，子網(wǎng)掩碼為28(或子網(wǎng)2：28/25)地址分配方案：子網(wǎng)1分配給局域網(wǎng)1，子網(wǎng)2分配給局域網(wǎng)2；或子網(wǎng)1分配給局域網(wǎng)2，子網(wǎng)2分配給局域網(wǎng)1。(2)R1的路由表如下：參考答案一：(若子網(wǎng)1分配給局域網(wǎng)1，子網(wǎng)分配給局域網(wǎng)2)目的網(wǎng)絡(luò)IP地址子網(wǎng)掩碼28285下一跳IP地址—接口E128—E2L0L0參考答案二：(若子網(wǎng)1分配給局域網(wǎng)2，子網(wǎng)分配給局域網(wǎng)1)目的網(wǎng)絡(luò)IP地址28子網(wǎng)掩碼28285下一跳IP地址—接口E1—E2L0L0(3)R2的路由表中，到局域網(wǎng)1和局域網(wǎng)2的路由表項如下：目的網(wǎng)絡(luò)IP地址子網(wǎng)掩碼下一跳IP地址接口L013新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機2010年全國碩士研究生入學(xué)統(tǒng)一考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題：第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合題目要求。1．若元素a，b，cd，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是A．d，c，e，b，f，aB．c，b，a，e，fC．b，．a(chǎn)，e，f，dD．a(chǎn)，f，e，d，c，b2b，d，e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是A．b，a，c，d，eB．d，b，c，eC．d，，c，a，eD．e，e，，a，d3．下列線索二叉樹中(用虛線表示線索)，符合后序線索樹定義的是4．在下圖所示的平衡二叉樹中，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是A．1348B．2448C．2453．24、54T個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉結(jié)點個數(shù)是A．41B．82C．113D．1226．對n(n≥2)個權(quán)值均不相同的字符構(gòu)造哈夫曼樹。下列關(guān)于該哈夫曼樹的敘述中，錯．誤的是．14新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結(jié)點C．樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D．樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值7G=(VE)中含有7G邊數(shù)最少是A．68．對下圖進行拓撲排序，可以得到不同拓撲序列的個數(shù)是B．15C．16．21A．4B．3C．2D．19．已知一個長度為16的順序表，其元素按關(guān)鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是A．4B．5C．6D．710．采用遞歸方式對順序表進行快速排序。下列關(guān)于遞歸次數(shù)的敘述中，正確的是A．遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B．每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C．每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D．遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關(guān)11．對一組數(shù)據(jù)(2，121688，5，10)進行排序，若前三趟排序結(jié)果如下：第一趟排序結(jié)果：，1216，1088第二趟排序結(jié)果：，125，，1688第三趟排序結(jié)果：，5，10，，1688則采用的排序方法可能是A．起泡排序B．希爾排序C．歸并排序D．基數(shù)排序12．下列選項中，能縮短程序執(zhí)行時間的措施是Ⅰ．提高CPU時鐘頻率Ⅱ．優(yōu)化數(shù)據(jù)通路結(jié)構(gòu)Ⅲ．對程序進行編譯優(yōu)化A．僅Ⅰ和ⅡB．僅Ⅰ和ⅢC．僅Ⅱ和ⅢD．Ⅰ、Ⅱ和Ⅲ134個整數(shù)用8位補碼分別表示為r1=FEHr2=F2Hr3=90Hr4=F8H算結(jié)果存放在一個8位寄存器中，則下列運算中會發(fā)生溢出的是A．r1×r2B．r2×r3C．r1×r4D．r2×r414if和d的數(shù)據(jù)類型分別為intfloatdouble(intfloatdouble分別用IEEE754單精度和雙精度浮點數(shù)格式表示)i=785f=1.5678e3d=1.5el00在32位機器中執(zhí)行下列關(guān)系表達式，則結(jié)果為“真”的是Ⅰ．i==(int)(float)iⅢ．f==(float)(double)fA．僅Ⅰ和ⅡⅡ．f==(float)(int)fⅣ．(d+f)-d==fB．僅Ⅰ和ⅢC．僅Ⅱ和ⅢD．僅Ⅲ和Ⅳ152K×4位的芯片組成一個8K×8OB1FH所在芯片的最小地址是A．0000HB．0600HC．0700H．0800H15新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機16．下列有關(guān)RAM和ROM的敘述中，正確的是Ⅰ．RAM是易失性存儲器，ROM是非易失性存儲器Ⅱ．RAM和ROM都采用隨機存取方式進行信息訪問Ⅲ．RAM和ROM都可用作CacheⅣ．RAM和ROM都需要進行刷新A．僅Ⅰ和ⅡB．僅Ⅱ和ⅢC．僅Ⅰ、Ⅱ和ⅣD．僅Ⅱ、Ⅲ和Ⅳ17．下列命中組合情況中，一次訪存過程中不可能發(fā)生的是．A．TLB未命中、Cache未命中、Page未命中B．TLB未命中、Cache命中、Page命中C．TLB命中、Cache未命中、Page命中D．TLB命中、Cache命中、Page未命中18．下列寄存器中，匯編語言程序員可見的是A．存儲器地址寄存器(MAR)B．程序計數(shù)器(PC)D．指令寄存器(IR)C．存儲器數(shù)據(jù)寄存器(MDR)19．下列選項中，不會引起指令流水線阻塞的是．A．?dāng)?shù)據(jù)旁路(轉(zhuǎn)發(fā))B．?dāng)?shù)據(jù)相關(guān)C．條件轉(zhuǎn)移D．資源沖突20．下列選項中的英文縮寫均為總線標(biāo)準的是A.PCI、CRT、USB、EISAB.、CPI、VESA、EISAD．ISA、EISA、PCI、PCI-ExpressC．ISA、SCSI、RAM、MIPS21．單級中斷系統(tǒng)中，中斷服務(wù)程序內(nèi)的執(zhí)行順序是Ⅰ．保護現(xiàn)場Ⅱ．開中斷Ⅲ．關(guān)中斷Ⅳ．保存斷點Ⅶ．中斷返回Ⅴ．中斷事件處理Ⅵ．恢復(fù)現(xiàn)場A．Ⅰ→Ⅴ→Ⅵ→Ⅱ→ⅦB．Ⅲ→Ⅰ→Ⅴ→ⅦC．Ⅲ→Ⅳ→Ⅴ→Ⅵ→ⅦD．Ⅳ→Ⅰ→Ⅴ→Ⅵ→Ⅶ22．假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600×1200248550寬至少約為A．245Mbps23．下列選項中，操作系統(tǒng)提供給應(yīng)用程序的接口是A．系統(tǒng)調(diào)用B．中斷C．庫函數(shù)24．下列選項中，導(dǎo)致創(chuàng)建新進程的操作是Ⅰ．用戶登錄成功Ⅱ．設(shè)備分配Ⅲ．啟動程序執(zhí)行A．僅Ⅰ和ⅡB．僅Ⅱ和ⅢC．僅Ⅰ和ⅢB．979MbpsC．1958Mbps．7834MbpsD．原語D．Ⅰ、Ⅱ和Ⅲ25．設(shè)與某資源關(guān)聯(lián)的信號量初值為31M表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則M、N分別是A．0、1B．1、0C．1、2D．2、026．下列選項中，降低進程優(yōu)先級的合理時機是A．進程的時間片用完B．進程剛完成I/O，進入就緒隊列C．進程長期處于就緒隊列中D．進程從就緒態(tài)轉(zhuǎn)為運行態(tài)27．進程P0和P1的共享變量定義及其初值為：booleanflag[2]；intturn=0；flag[0]=FALSE；flag[1]=FALSE；若進程P0和P1訪問臨界資源的類C偽代碼實現(xiàn)如下：16新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機voidP0()//進程voidP1()//進程{while(TRUE){{while(TRUE){flag[0]=TRUEturn=1；nag[1]=TRUEturn=0；while(flag[1]&&(turn==1))；臨界區(qū)；while(flag[0]&&(tum==0))；臨界區(qū)；flag[0]=FALSE；flag[1]=FALSE；}}}}則并發(fā)執(zhí)行進程P0和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ū)存儲管理的計算機，其主存容量為55MB(初始為空閑)，采用最佳適配(BestFit)15MB30MB15MB8MB、分配6MB，此時主存中最大空閑分區(qū)的大小是A．729．某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為210字節(jié)，頁表項大小為字節(jié)，邏輯地址結(jié)構(gòu)為：B．9C．10MBD．15頁目錄號頁號頁內(nèi)偏移量，邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少．．是A．64B．128C．256D．51230．設(shè)文件索引節(jié)點中有7個地址項，其中個地址項是直接地址索引，2個地址項是一級間接地址索引，1和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件最大長度是A．33B．519KBC．1057KBD．16513KB31．設(shè)置當(dāng)前工作目錄的主要目的是A．節(jié)省外存空間B．節(jié)省內(nèi)存空間C．加快文件的檢索速度D．加快文件的讀/寫速度32．本地用戶通過鍵盤登錄系統(tǒng)時，首先獲得鍵盤輸入信息的程序是A．命令解釋程序B．中斷處理程序C．系統(tǒng)調(diào)用服務(wù)程序D．用戶登錄程序33．下列選項中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)所描述的內(nèi)容是A．網(wǎng)絡(luò)的層次B．每一層使用的協(xié)議D．每一層必須完成的功能C．協(xié)議的內(nèi)部實現(xiàn)細節(jié)34存儲一轉(zhuǎn)發(fā)”為100Mbps，分組大小為1000B，其中分組頭大小為20。若主機H1向主機H2發(fā)送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送開始到H2接收完為止，需要的時間至少是A．80B．80.08C．80.16D．80.2417新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機35RIPR1收到其鄰居路由器R2的距離矢量，距離矢量中包含信息<net1，16>，則能得出的結(jié)論是A．R2可以經(jīng)過R1到達net1，跳數(shù)為17B．R2可以到達net1，跳數(shù)為16C．R1可以經(jīng)過R2net1，跳數(shù)為17D．不能經(jīng)過R2到達net136．若路由器R因為擁塞丟棄IP分組，則此時R可向發(fā)出該IP分組的源主機發(fā)送的ICMP報文類型是A．路由重定向B．目的不可達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．328B．326C．8、D．8、3038．下列網(wǎng)絡(luò)設(shè)備中，能夠抑制廣播風(fēng)暴的是Ⅰ．中繼器Ⅱ．集線器B．僅ⅢⅢ．網(wǎng)橋Ⅳ．路由器C．僅Ⅲ和ⅣA．僅Ⅰ和Ⅱ．僅Ⅳ39TCP連接，TCP最大段長度為1000甲的當(dāng)前擁塞窗口為4000字節(jié)，在主機甲向主機乙連續(xù)發(fā)送兩個最大段后，成功收到主機乙發(fā)送的對第一個段的確認段，確認段中通告的接收窗口大小為2000字節(jié)，則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是A．1000B．2000C．3000D400040機、本地域名服務(wù)器發(fā)送的域名請求消息數(shù)分別為A．一條、一條B．一條、多條C．多條、一條D．多條、多條二、綜合應(yīng)用題：第41～47小題，共70分。41分)將關(guān)鍵字序列(78301118914)儲空間是一個下標(biāo)從0開始的一維數(shù)組，散列函數(shù)為：H(key)=(key×3)MOD7，處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7。(1)請畫出所構(gòu)造的散列表。(2)分別計算等概率情況下查找成功和查找不成功的平均查找長度。42．分)設(shè)將n(n>1)個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都R中保存的序列循環(huán)左移p(0<p<n)R中的數(shù)據(jù)由(xx，01x)變換為(x，x，，xxx，…，x)。要求：n-1pp+1n-101p-1(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或c++或Java語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。43分)某計算機字長為16128KB指令格式，指令各字段定義如下：151211OPMsRs目的操作數(shù)轉(zhuǎn)移指令采用相對尋址方式，相對偏移量用補碼表示。尋址方式定義如下：Md0Rd源操作數(shù)Ms/Md000B001B010B尋址方式寄存器直接助記符Rn含義操作數(shù)=(Rn)寄存器間接(Rn)操作數(shù)=((Rn))寄存器間接、自增(Rn)+操作數(shù)=((Rn))，(Rn)+1Rn18新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機011B相對D(Rn)轉(zhuǎn)移目標(biāo)地址=(PC)+(Rn)注：(x)表示存儲器地址x或哥存器x的內(nèi)容。請回答下列問題：(1)該指令系統(tǒng)最多可有多少條指令?該計算機最多有多少個通用寄存器?存儲器地址寄存器(MAR)和存儲器數(shù)據(jù)寄存器(MDR)至少各需要多少位?(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)+”()對應(yīng)的機器碼是什么(用十六進制表示)?該指令執(zhí)行后，哪些寄存器和存儲單元中的內(nèi)容會?改變后的內(nèi)容是什么?44(12分)某計算機的主存地址空間大小為256MBCache和數(shù)據(jù)Cache8個CacheCache行大小為64BCache功能相同的程序A和B，其偽代碼如下所示：程序A：程序B：inta[256][256]；intsum_array1(){inta[256][256]；intsum_array2(){inti，，sum=0；for(i_0i<256i++)for(j=0j<256j++)sum+=a[i][j]；return：}inti，，sum=0；for(j=0j<256j++)for(i=0i<256i++)sum+=a[i][j]；return：}假定int類型數(shù)據(jù)用32isuma按行優(yōu)先方式存放，其首地址為320(十進制數(shù))。請回答下列問題，要求說明理由或給出計算過程。(1)若不考慮用于CacheCache的總?cè)萘繛槎嗌?(2)數(shù)組元素a[0][31]和a[1][1]各自所在的主存塊對應(yīng)的Cache行號分別是多少(Cache行號從0開始(3)程序A和B的數(shù)據(jù)訪問命中率各是多少?哪個程序的執(zhí)行時間更短?45．(7)假設(shè)計算機系統(tǒng)采用CSCAN(循環(huán)掃描)磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤塊的空閑狀態(tài)。(1)請說明在上述條件下如何進行磁盤塊空閑狀態(tài)的管理。(2)設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘6000100移動時間為1ms100(如下圖所示)，磁道號請求隊列為5090、30120，對請求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，則讀完這4個扇區(qū)總共需要多少時間?要求給出計算過程。19新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機(3)如果將磁盤替換為隨機訪問的Flash半導(dǎo)體存儲器(如U盤、SSD等)CSCAN更高效的磁盤調(diào)度策略?若有，給出磁盤調(diào)度策略的名稱并說明理由；若無，說明理由。46(8)設(shè)某計算機的邏輯地址空間和物理地址空間均為64KB程最多需要頁(Page)數(shù)據(jù)存儲空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框(PageFrame)260前的該進程訪問情況如下表所示(訪問位即使用位)。頁號頁框號裝入時刻130訪問位01237429l230111200160當(dāng)該進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：(1)該邏輯地址對應(yīng)的頁號是多少?(2)若采用先進先出(FIFO)置換算法，該邏輯地址對應(yīng)的物理地址是多少?要求給出計算過程。(3)若采用時鐘(CLOCK)?要求給出計算過程(設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下)。47．(9)某局域網(wǎng)采用CSMA/CD協(xié)議實現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸速率為10Mbps，主機甲和主機乙之間的距離為2km，信號傳播速度是200km/s。請回答下列問題，要求說明理由或?qū)懗鲇嬎氵^程。(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ò)不存在任何沖突與差錯，主機甲總是以標(biāo)準的最長以太網(wǎng)數(shù)據(jù)幀(1518字節(jié))向主機乙發(fā)送數(shù)據(jù)，主機乙每成功收到一個數(shù)據(jù)幀后立即向主機甲發(fā)送一個64字節(jié)的確認幀，主機甲收到確認幀后方可發(fā)送下一個數(shù)據(jù)幀。此時主機甲的有效數(shù)據(jù)傳輸速率是多?(不考慮以太網(wǎng)幀的前導(dǎo)碼)20新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機計算機學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案及解析(2010年)一、單項選擇題1．D2．C3．D4．C5．B6．A7．C8．B9．B10．D11．A12．D13．B14．B15．D16．A17．D18．B19．A20.D21．A22．D23．A24．C25．B26．A27．D28．B29．B30．C31．C32．B33．C34．C35．D36．C37．B38．D39．A21新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機40．A二、綜合應(yīng)用題41．【答案要點】(1)由裝載因子0.7，數(shù)據(jù)總數(shù)7→存儲空間長度為10→P=10。所以，構(gòu)造的散列表為：H(7)=(7×3)MOD7=0H(8)=(8×3)MOD7=3H(11)=(11×3)MOD7=5H(18)=(18×3)MOD7=5H(9)=(9×3)MOD7=6H(14)=(14×3)MOD7=0H(30)=(30×3)MOD7=6下標(biāo)0712384567899關(guān)鍵字14113018(2)查找成功的平均查找長度：ASL成功=(1+1+1+1+2+3+3)/7=12/7。查找不成功的平均查找長度：AsL不成功=(3+2+1+2+1+5+4)/7=18/7。42．【答案要點】(1)給出算法的基本設(shè)計思想：先將n個數(shù)據(jù)xxx…x…xxxxx，01pn-1n-1n-1pp-10然后再將前n-p個和后pxx…xxx…，pp+1n-101x。p-1(2)算法實現(xiàn)：voidreverse(int，leftintright){intk=left，j=righttemp；//k等于左邊界left，j等于右邊界rightwhile(k<j){//r[k]與r[j]temp：r[k]；r[k]=r[j]；r[j]=temp；k++：//k右移一個位置j--；左移一個位置}}voidleftShift(intr[，intn，intp){if(p>0&&p<n){reverse(r，0，n-1)；//將全部數(shù)據(jù)逆置reverse(r，0，n-p-1)；//n-p個元素逆置reverse(r，n-p，n-1)；//p個元素逆置}}(3)說明算法復(fù)雜性：上述算法的時間復(fù)雜度為0(n)，空間復(fù)雜度為0(1)。22新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機43．【答案要點】(1)該指令系統(tǒng)最多可有168128KB，按字編址，故共有64K個存儲單元；地址位數(shù)為16位，所以MAR至少為16位；因為字長為16位，所以MDR至少為16位。(2)轉(zhuǎn)移指令的目標(biāo)地址范圍為0000H～FFFFH。(3)對于匯編語句“add(R4)，(R5)+”，對應(yīng)的機器碼為：0010001100010101B，用十六進制表示為2315H?！癮dd(R4)(R5)+”R5和存儲單元5678HR5的內(nèi)容從5678H5679H，存儲單元5678H中的內(nèi)容從1234H變?yōu)?8ACH。44．【答案要點】(1)數(shù)據(jù)Cache的總?cè)萘繛椋?256位(532字節(jié))。(2)數(shù)組a在主存的存放位置及其與Cache之間的映射關(guān)系如下圖所示。a[0][31]所在主存塊映射到Cache第6a[1][1]所在主存塊映射到Cache第5行。(3)編譯時i，j，sum均分配在寄存器中，故數(shù)據(jù)訪問命中率僅考慮數(shù)組a的情況。①程序A的數(shù)據(jù)訪問命中率為93.75％；②程序B的數(shù)據(jù)訪問命中率為0。根據(jù)上述計算出的命中率，得知程序B每次取數(shù)都要訪問主存，所以程序A的執(zhí)行比程序B快得多。45．【答案要點】(1)用位圖表示磁盤的空閑狀態(tài)。每一位表示一個磁盤塊的空閑狀態(tài)，共需要16384/32=512=512x4個字節(jié)=2KB，正好可放在系統(tǒng)提供的內(nèi)存中。(2)采用CSCAN120305090170，總的移動磁道時間為170。由于轉(zhuǎn)速為6000，則平均旋轉(zhuǎn)延遲為5，總的旋轉(zhuǎn)延遲時間=20ms。由于轉(zhuǎn)速為6000，則讀取一個磁道上一個扇區(qū)的平均讀取時間為0.1，總的讀取扇區(qū)的時間為0.4。讀取上述磁道上所有扇區(qū)所花的總時間為190.4。23新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機(3)采用FCFS(先來先服務(wù))調(diào)度策略更高效。因為Flash半導(dǎo)體存儲器的物理結(jié)構(gòu)不需要考慮尋道時間和旋轉(zhuǎn)延遲，可直接按I/O請求的先后順序服務(wù)。46．【答案要點】(1)因17CAH=0001011111001010B，表示頁號的位為左邊位，所以頁號為5。(2)根據(jù)FIFO0將5號頁裝入70001111111001010B1FCAH。(3)根據(jù)CLOCK算法，如果當(dāng)前指針?biāo)疙摽虻氖褂梦粸椋瑒t替換該頁；否則將使用24次查找頁框號的順序為→4→79，并將對應(yīng)頁框的使用位清零。在第次查找中，指針指向22號頁框的使用位為02號頁框?qū)?yīng)的25號頁裝入2號頁框中，并將對應(yīng)使用位設(shè)置為0000101111001010B0BCAH。47．【答案要點】(1)主機甲和主機乙之間單向傳播延遲時間：10μs。兩臺主機均檢測到?jīng)_突時，最短所需時間和最長所需時間對應(yīng)下面兩種極端情況：兩個方向傳播。因此，甲乙兩臺主機均檢測到?jīng)_突時，最短需經(jīng)過10s。②主機甲(或主機乙)先發(fā)送一個數(shù)據(jù)幀，當(dāng)該數(shù)據(jù)幀即將到達主機乙(或主機甲)時，主機乙(或主機甲)也開始發(fā)送一個數(shù)據(jù)幀。這時，主機乙(或主機甲)將立即檢測到?jīng)_突；而主機甲(或主機乙)要檢測到?jīng)_突，沖突信號還需要從主機乙(或主機甲)傳播到主機甲(或主機乙)，因此，甲乙兩臺主機均檢測到?jīng)_突時，最長需經(jīng)過20s。(2)發(fā)送1518B的數(shù)據(jù)幀所用時間(傳輸延遲)：1214.4μs。發(fā)送64B的確認幀所用時間(傳輸延遲)：51.2s。主機甲從發(fā)送數(shù)據(jù)幀開始到收完確認幀為止的時間記為T，則T=1285.6μs?？偪傊鳈C甲的有效數(shù)據(jù)傳輸速率=12000bits/1285.6μs≈9.33Mbps。24新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機2011年全國碩士研究生入學(xué)統(tǒng)一考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題1～40小題，每小題2分。下列每題給出的四個選項中，只有一個選項最符合試題要求。1．設(shè)n是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間復(fù)雜度是x=2；while(x<n/2)x=2*x：A．O(log2n)B．O(n)C．O(nlog2)D．O(n2)2a，b，cd，e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數(shù)是A．3B．4C．5D．63．已知循環(huán)隊列存儲在一維數(shù)組A[0n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是A．0，04．若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是A．257B．258C．384D．385B．0，nC．n-10D．n-1，n-15．若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1，2，，4和4，，2，1，則該二叉樹的中序遍歷序列不會是．A．1，，3，4B．2，3，1C．3，2，1D．4，3，，162011116的結(jié)點個數(shù)是A．115B．116C．1895．18967．對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是．A．95229124，9471C．21897729，36388．下列關(guān)于圖的敘述中，正確的是Ⅰ．回路是簡單路徑B．9220913488，35．12，25716833，34Ⅱ．存儲稀疏圖，用鄰接矩陣比鄰接表更省空間Ⅲ．若有向圖中存在拓撲序列，則該圖不存在回路A．僅ⅡB．僅Ⅰ、ⅡC．僅ⅢD．僅Ⅰ、Ⅲ9．為提高散列(Hash)表的查找效率，可以采取的正確措施是Ⅰ．增大裝填(載)因子Ⅱ．設(shè)計沖突(碰撞)少的散列函數(shù)Ⅲ．處理沖突(碰撞)時避免產(chǎn)生聚集(堆積)現(xiàn)象A．僅ⅠB．僅ⅡC．僅Ⅰ、ⅡD．僅Ⅱ、Ⅲ10．為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是25新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機A．順序存儲B．散列存儲C．鏈式存儲D．索引存儲11．已知序列25131012，9是大根堆，在序列尾部插入新元素18，將其再調(diào)整為大根堆，調(diào)整過程中元素之間進行的比較次數(shù)是A．112．下列選項中，描述浮點數(shù)操作速度指標(biāo)的是A．MIPSB．CPIC．IPCB．2C．4D．5．MFLOPS13float型數(shù)據(jù)通常用IEEE754float型變量x分配在一個位浮點寄存器FR1中，且x=-8.25FR1的內(nèi)容是A．C1040000HB．C2420000HC．C1840000HD．C1C20000H14．下列各類存儲器中，不采用隨機存取方式的是．A．EPROMB．CDROMC．DRAMD．SRAM15．某計算機存儲器按字節(jié)編址，主存地址空間大小為64MB，現(xiàn)用4M×8位的RAM芯片組成32MB的主存儲器，則存儲器地址寄存器MAR的位數(shù)至少是A．22位B．位D．25位D．26位16式中，不屬于偏移尋址方式的是．A．間接尋址B．基址尋址C．相對尋址D．變址尋址17/借位標(biāo)志CFZFSF和溢出標(biāo)志OF，條件轉(zhuǎn)移指令bgt(無符號整數(shù)比較大于時轉(zhuǎn)移)的轉(zhuǎn)移條件是A．CF+OF=1B．SF+ZF=1C．CFZF=1D．CFSF=118．下列給出的指令系統(tǒng)特點中，有利于實現(xiàn)指令流水線的是Ⅰ．指令格式規(guī)整且長度一致Ⅱ．指令和數(shù)據(jù)按邊界對齊存放Ⅲ．只有Load/Store指令才能對操作數(shù)進行存儲訪問A．僅Ⅰ、ⅡB．僅Ⅱ、ⅢC．僅Ⅰ、ⅢD．Ⅰ、Ⅱ、Ⅲ19Cache開中斷”執(zhí)行的敘述中，錯誤的是．．A．每個指令周期中CPU都至少訪問內(nèi)存一次B．每個指令周期一定大于或等于一個CPU時鐘周期C．空操作指令的指令周期中任何寄存器的內(nèi)容都不會被改變D．當(dāng)前程序在每條指令執(zhí)行結(jié)束時都可能被外部中斷打斷20．在系統(tǒng)總線的數(shù)據(jù)線上，不可能傳輸?shù)氖牵瓵．指令B．操作數(shù)C．握手(應(yīng)答)信號D．中斷類型號21L～LMMMMMMi=1(0≤i4)表示對4043210LL→L→L→L→Li01234處理優(yōu)先級從高到低的順序為L→L→L→LL，則L的中斷處理程序中設(shè)置的中斷屏402131蔽字是A．11110B．01101C．00011．0101022．某計算機處理器主頻為50MHz，采用定時查詢方式控制設(shè)備A的I/O，查詢程序運行一次所用的時鐘周期數(shù)至少為500A26新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機其查詢至少200次，則CPU用于設(shè)備A的I/O的時間占整個CPU時間的百分比至少是A．0.02％B．0.05％C．0.20％D．0.50％23．下列選項中，滿足短任務(wù)優(yōu)先且不會發(fā)生饑餓現(xiàn)象的調(diào)度算法是．A．先來先服務(wù)B．高響應(yīng)比優(yōu)先C．時間片輪轉(zhuǎn)D．非搶占式短任務(wù)優(yōu)先24．下列選項中，在用戶態(tài)執(zhí)行的是A．命令解釋程序B．缺頁處理程序C．進程調(diào)度程序D．時鐘中斷處理程序25．在支持多線程的系統(tǒng)中，進程P創(chuàng)建的若干個線程不能共享的是．A．進程P的代碼段B．進程P中打開的文件C．進程P的全局變量D．進程P中某線程的棧指針26．用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的正確處理流程是A．用戶程序→系統(tǒng)調(diào)用處理程序→中斷處理程序→設(shè)備驅(qū)動程序B．用戶程序→系統(tǒng)調(diào)用處理程序→設(shè)備驅(qū)動程序→中斷處理程序C．用戶程序→設(shè)備驅(qū)動程序→系統(tǒng)調(diào)用處理程序→中斷處理程序D．用戶程序→設(shè)備驅(qū)動程序→中斷處理程序→系統(tǒng)調(diào)用處理程序27．某時刻進程的資源使用情況如下表所示。已分配資源尚需資源可用資源進程R1R2R3R1R2R3R10R2R312100021000110112033012102此時的安全序列是A．P1，P2，P3，B．P1，P3P2，P4C．P1，P4，P3，D．不存在28．在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能是Ⅰ．修改頁表A．僅Ⅰ、ⅡC．僅ⅢⅡ．磁盤I/OⅢ．分配頁框B．僅ⅡD．Ⅰ、Ⅱ和Ⅲ29．當(dāng)系統(tǒng)發(fā)生抖動(thrashing)時，可以采取的有效措施是Ⅰ．撤銷部分進程Ⅱ．增加磁盤交換區(qū)的容量Ⅲ．提高用戶進程的優(yōu)先級A．僅Ⅰ30階段是A．編輯B．僅ⅡC．僅ⅢD．僅Ⅰ、ⅡB．編譯C．鏈接D．裝載3110分析。假設(shè)一個緩沖區(qū)與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區(qū)的時間為100μs，27新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時間是50μs對一塊數(shù)據(jù)進行分析的時間為50s。在單緩沖區(qū)和雙緩沖區(qū)結(jié)構(gòu)下，讀入并分析完該文件的時間分別是A．1500μs、1000μsB．1550μs1100μsC．1550μs、1550μsD．2000μs2000μs32P1和P21的變量xP1對加1P2對減11和減1操作的指令序列分別如下所示。P1//加操作load，xincR1P2//操作loadR2xdec//到寄存器R1中storexR1//將的內(nèi)容存入xstore，R2兩個操作完成后，的值A(chǔ)．可能為-1或3B．只能為1D．可能為-1、0、12C．可能為0、1233．TCP/IP參考模型的網(wǎng)絡(luò)層提供的是A．無連接不可靠的數(shù)據(jù)報服務(wù)B．無連接可靠的數(shù)據(jù)報服務(wù)C．有連接不可靠的虛電路服務(wù)D．有連接可靠的虛電路服務(wù)34．若某通信鏈路的數(shù)據(jù)傳輸速率為2400bps，采用4相位調(diào)制，則該鏈路的波特率是A．600波特B．1200C．4800波特D．960035(SR)0～3收到1號幀的確認，而02號幀依次超時，則此時需要重傳的幀數(shù)是A．136．下列選項中，對正確接收到的數(shù)據(jù)幀進行確認的MAC協(xié)議是A．CSMAB．CDMAC．CSMA/CDD．CSMA/CAB．2C．3D．437．某網(wǎng)絡(luò)拓撲如下圖所示，路由器R1只有到達子網(wǎng)/24的路由。為使R1可以將IP分組正確地路由到圖中所有子網(wǎng)，則在R1中需要增加的一條路由(目的網(wǎng)絡(luò)，子網(wǎng)掩碼，下一跳)是A．，28，B．，，C．，28，D．，，38．在子網(wǎng)/30中，能接收目的地址為的IP分組的最大主機數(shù)是A．0B．1C．2D．439．主機甲向主機乙發(fā)送一個(SYN=1，seq=11220)的TCP段，期望與主機乙建立TCP28新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機連接，若主機乙接受該連接請求，則主機乙向主機甲發(fā)送的正確的TCP段可能是A．(SYN＝0，ACK=0，seq=11221，ack=11221)B．(SYN=1，ACK=1，seq=11220，ack=11220)C．(SYN=1，ACK=1，seq=11221，ack=11221)D．(SYN=0，ACK=0，seq=11220，ack=11220)40．主機甲與主機乙之間已建立一個TCP連接，主機甲向主機乙發(fā)送了3個連續(xù)的TCP段，分別包含300字節(jié)、400字節(jié)和500字節(jié)的有效載荷，第3個段的序號為900。若主機乙僅正確接收到第1和第3個段，則主機乙發(fā)送給主機甲的確認序號是A300B．500C．1200．1400二、綜合應(yīng)用題：第41～47小題，共70分。41(8分)已知有6個頂點(頂點編號為0～5)的有向帶權(quán)圖GA為上三角矩陣，按行為主序(行優(yōu)先)保存在如下的一維數(shù)組中。46∞∞∞5∞∞∞43∞∞33要求：(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權(quán)圖G。(3)求圖G的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。42．分)一個長度為L(L≥1)的升序序列S，處在第[L/2]個位置的數(shù)稱為s的中位數(shù)。例S1(11131517S1的中位數(shù)是15有元素的升序序列的中位數(shù)。例如，若S2=(24，68，20)，則S1和S2的中位數(shù)是11。現(xiàn)有兩個等長升序序列A和B，試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。43．分)假定在一個8位字長的計算機中運行如下類C程序段：unsignedintx134：unsignedinty=246；intm=x：intn=y；unsignedintz1=x-y：unsignedintz2=x+y：intk1=m-n：Intk2=m+n：若編譯器編譯時將個8位寄存器R1～R8分別分配給變量ymz1z2k1k2。請回答下列問題。(提示：帶符號整數(shù)用補碼表示)(1)執(zhí)行上述程序段后，寄存器R1、R5R6的內(nèi)容分別是什么?(用十六進制表示)(2)執(zhí)行上述程序段后，變量和k1的值分別是多少?(用十進制表示)(3)上述程序段涉及帶符號整數(shù)加//個加法器及輔助電路實現(xiàn)?簡述理由。(4)計算機內(nèi)部如何判斷帶符號整數(shù)加/減運算的結(jié)果是否發(fā)生溢出?帶符號整數(shù)運算語句的執(zhí)行結(jié)果會發(fā)生溢出?29新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機44(12分)(邏輯)地址空間大小為16MB物理)地址空間大小為1MB，頁面大小為4KB；Cache采用直接映射方式，共行；主存與Cache之間交換的塊大小為32B。系統(tǒng)運行到某一時刻時，頁表的部分內(nèi)容和Cache的部分內(nèi)容分別如題44-a圖、題44-b圖所示，圖中頁框號及標(biāo)記字段的內(nèi)容為十六進制形式。虛頁號有效位頁框號…行號有效位標(biāo)記…012345670111010106041502-……0123456710111101020-……01D10506414D-2B-3227A44-a圖頁表的部分內(nèi)容請回答下列問題。(1)?(物理頁號題44-b圖Cache(2)使用物理地址訪問Cache時，物理地址應(yīng)劃分成哪幾個字段?要求說明每個字段的位數(shù)及在物理地址中的位置。(3)虛擬地址001C60H所在的頁面是否在主存中?若在主存中，則該虛擬地址對應(yīng)的物理地址是什么?訪問該地址時是否Cache?要求說明理由。(4)假定為該機配置一個4路組相聯(lián)的TLBTLB共可存放8(十六進制)如題44-c圖所示，則此時虛擬地址024BACH所在的頁面是否在主存中?要求說明理由。編號有效位標(biāo)記頁框號有效位標(biāo)記頁框號有效位標(biāo)記頁框號有效位標(biāo)記頁框號0101--10001-15-0--1012-1F-0132D10087E0題44-c圖的部分內(nèi)容45(8)某銀行提供1個服務(wù)窗口和10閑時，通過叫號選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動過程描述如下：cobegin{process顧客i{從取號機獲得一個號碼；等待叫號；獲得服務(wù)；}process營業(yè)員{while(TRUE){30新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機叫號；為顧客服務(wù)；}}}coend請?zhí)砑颖匾男盘柫亢蚉、V(或wait(、signal())操作，實現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。46．(7)某文件系統(tǒng)為一級目錄結(jié)構(gòu)，文件的數(shù)據(jù)一次性寫入磁盤，已寫入的文件不可修改，但可多次創(chuàng)建新文件。請回答如下問題。(1)在連續(xù)、鏈式、索引三種文件的數(shù)據(jù)塊組織方式中，哪種更合適?定位文件數(shù)據(jù)塊，需在FCB中設(shè)計哪些相關(guān)描述字段?(2)為快速找到文件，對于FCB，是集中存儲好，還是與對應(yīng)的文件數(shù)據(jù)塊連續(xù)存儲好?要求說明理由。47．(9)某主機的MAC地址為00-15-C5-C1-5E-28，IP地址為00(私有地址)。題47-a47-b圖是該主機進行Web請求的1個以太網(wǎng)數(shù)據(jù)幀前80個字節(jié)的十六進制及ASCII碼內(nèi)容。題47-a圖網(wǎng)絡(luò)拓撲請參考圖中的數(shù)據(jù)回答以下問題。(1)Web服務(wù)器的IP地址是什么?該主機的默認網(wǎng)關(guān)的MAC地址是什么?題47-b圖以太網(wǎng)數(shù)據(jù)幀(前80字節(jié))(2)該主機在構(gòu)造題47-bMAC?封裝該協(xié)議請求報文的以太網(wǎng)幀的目的MAC地址是什么?(3)假設(shè)HTTP/1.1協(xié)議以持續(xù)的非流水線方式工作，一次請求-響應(yīng)時間為RTTrfc.html頁面引用了個JPEG小圖像，則從發(fā)出題47-b圖中的Web請求開始到瀏覽器收到全部內(nèi)容為止，需要多少個RTT?(4)該幀所封裝的IP分組經(jīng)過路由器R轉(zhuǎn)發(fā)時，需修改IP分組頭中的哪些字段?注：以太網(wǎng)數(shù)據(jù)幀結(jié)構(gòu)和IP分組頭結(jié)構(gòu)分別如題47-c圖、題47-d圖所示。6B6B2B46-1500B4B目的MAC地址源MAC地址類型數(shù)據(jù)CRC題47-c圖以太網(wǎng)幀結(jié)構(gòu)31新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機題47-d圖IP分組頭結(jié)構(gòu)32新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機計算機學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案及解析(2011年)一、單項選擇題1．A2．B3．B4．C5．C6．D7．A8．C9．D10．A11．B12．D13．A14．B15．D16．A17．C18．D19．C20．C21．D22．C23．B24．A25．D26．B27．D28．D29．A30．C31．B32．C33．A34．B35．B36．D37．D38．C39．C33新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機40．B二、綜合應(yīng)用題41．【答案要點】(1)圖G的鄰接矩陣A如下：(2分)0406504303300(2)圖G如下：(2分)(3)下圖中雙線箭頭所標(biāo)識的4個活動組成圖G的關(guān)鍵路徑。(3分)圖G的關(guān)鍵路徑的長度為16。分)42．【答案要點】(1)給出算法的基本設(shè)計思想：(5分)分別求兩個升序序列A、B的中位數(shù)，設(shè)為a和b。若a=b，則a或b即為所求的中位ab均只含一個元素時為止，則較小者即為所求的中位數(shù)。(2)算法實現(xiàn)：(8分)intM_Search(int],intB[],intn){intstart1,end1,mid1,start2,end2,mid2;start1=0;end1=n-1;start2=0;end2=n-1;while(start1!=end1||start2!=end2){=(start1+end1)/2;=(start2+end2)/2;if(A[mid1]==B[mid2])returnA[mid1];if(A[mid1]<B[])34新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機{//分別考慮奇數(shù)和偶數(shù)，保持兩個子數(shù)組元素個數(shù)相等if((start1+end1)％2==0){//若元素為奇數(shù)個start1=mid1；end2=mid2；}//A中間點以前的部分且保留中間點//B中間點以后的部分且保留中間點else{若元素為偶數(shù)個start1=mid1+1；//A的前半部分end2=mid2；//B的后半部分}}else{if((start1+end1)％：0){//若元素為奇數(shù)個end1=mid1；start2=mid2；}//A中間點以后的部分且保留中間點//B中間點以前的部分且保留中間點else{//若元素為偶數(shù)個end1=mid1；//A的后半部分start2=mid2+1；//B的前半部分}}}returnA[start1]<B[start2]?A[start1]：B[start2]；}(3)上述所給算法的時間、空間復(fù)雜度分別是0(log2n)和0(1)。(2分)43.【答案要點】(1)134=128+6=10000110B，所以的機器數(shù)為10000110BR1的內(nèi)容為86H。(1)246=255-9=11110110B，所以的機器數(shù)為11110110Bx-y：10000110+00001010=(0)10010000，括弧中為加法器的進位，故R5的內(nèi)容為。(1分)x+y10000110+11110110=(1)01111100R6的內(nèi)容為7CH。(1分)(2)m的機器數(shù)與x86H=10000110B用補碼表示)時，其值為-1111010B=-122。(1分)的機器數(shù)與x-y的機器數(shù)相同，皆為90H=10010000B，解釋為帶符號整數(shù)k1(表示)時，其值為-1110000B=-112。分)(3)能。(1分)n位加法器實現(xiàn)的是模2na和ba+b可以直接用加n法器實現(xiàn)，而a-b可用ab的補數(shù)實現(xiàn)，即a-b=a+[-b](mod2)，所以n位無符號整數(shù)加/減運補算都可在n位加法器中實現(xiàn)。(1分)由于帶符號整數(shù)用補碼表示，補碼加/減運算公式為：[a+b]=[a]+[b](mod2)[a-b]補n補補補n=[a]+[-b](mod2)，所以n位帶符號整數(shù)加/減運算都可在n位加法器中實現(xiàn)。(1分)補補(4)帶符號整數(shù)加/(加數(shù))的符號相同，且不同于輸出端(和)(高位的進位不同，則結(jié)果溢出)(2分)35新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機10000110+11110110=(1)01111100法器的進位，根據(jù)上述溢出判斷規(guī)則，可知結(jié)果溢出。(1分)44．【答案要點】241220(1)16M=24K=22412(1分)1M=2地址為20位，其中高8位為物理頁號。(1分)(2)2053位為Cache12(3分)(3)在主存中。(1分)虛擬地址001C60H=000000000001110001100000B，故虛頁號為000000000001B看000000000001B=001H處的頁表項，由于對應(yīng)的有效位為001C60H所在的頁面在主存中。(1分)頁表001處的頁框號(物理頁號)為04H=00000100B，與頁內(nèi)偏移110001100000B拼接成物理地址：00000100110001100000B=04C60H。(1分)對于物理地址00000100110001100000BCache第3行(011B行)=1(值為105H)≠#04CH(物理地址高12位)，故訪問該地址時Cache不命中。(2分)(4)虛擬地址024BACH=000000100100101110101100B，故虛頁號為000000100100B；由于TLB8/4=2個組，故虛頁號中高11位為TLB標(biāo)記，最低1位為TLB組號，它們的值分別為00000010010B(即012H)和0BTLB的第0組。(1分)由于組中存在有效位=1、標(biāo)記=012H的項，所以訪問TLB命中，即虛擬地址024BACH所在的頁面在主存中。(1分)45．【答案要點】(1)互斥資源：取號機(一次只允許一位顧客領(lǐng)號)，因此設(shè)一個互斥信號量mutex；(2)同步問題：顧客需要獲得空座位等待叫號，當(dāng)營業(yè)員空閑時，將選取一位顧客并為其服務(wù)。空座位的有、無影響等待顧客數(shù)量，顧客的有、無決定了營業(yè)員是否能開始服務(wù)，故分別設(shè)置信號量empty和fullservice來完成這一同步過程。semaphoremutex=1；semaphoreempty=10；semaphorefull=0；semaphoreservice=0；cobegin//互斥使用取號機//空座位的數(shù)量//已占座位的數(shù)量//等待叫號{process顧客i{P(empty)；P(mutex)；從取號機獲得一個號；V(mutex)；V(full)；P(service)；獲得服務(wù)；}//等待叫號process營業(yè)員36新東方在線[]網(wǎng)絡(luò)課堂電子教材系列考研計算機{while(TRUE){P(full)；V(empty)；V(service)；//為顧客服務(wù)；}}}coend46．【答案要點】(1)在磁盤中連續(xù)存放(采取連續(xù)結(jié)構(gòu))，磁盤尋道時間更短，文件隨機訪問效率更高；(2分)在FCB中加入的字段為：<起始塊號，塊數(shù)>或者<起始塊號，結(jié)束塊號>。(1分)(2)將所有FCB集中存放，文件數(shù)據(jù)集中存放。(2分)這樣在隨機查找文件名時，只需訪問FCB對應(yīng)的塊，可減少磁頭移動和磁盤I/O訪問次數(shù)。(2分)47．【答案要點】(1)從題47-bIP分組的目的地址就是Web服務(wù)器的IP