2016考研計(jì)算機(jī)講義及模擬試卷

一、單項(xiàng)選擇題：第～4小題，每小題分，共分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符合試題要求。為解決計(jì)算機(jī)主機(jī)與之間速度不匹配問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，A． B．隊(duì) C． D． Ⅰ．父子關(guān)系Ⅱ．兄弟關(guān)系Ⅲ．u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系 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，1910．若數(shù)A．起泡排 B．排 C．選擇排 D．二路歸并排A．指令操作碼的譯碼結(jié) B．指令和數(shù)據(jù)的尋址方C．指令周期的不同階 D．指令和數(shù)據(jù)所在的單個(gè)數(shù)X=27×29/32，Y=25×58，則用浮點(diǎn)加法計(jì)算X+Y的最終結(jié)果是A．00111 某計(jì)算機(jī)主存容量為64KB，其中ROM區(qū)為4KB，其余為RAM區(qū)，按字節(jié)編址。A．1、 B．2、 C．1、 D．2、 下列關(guān)于RISC的敘述中，的A．RISCD．RISC的指令數(shù)、尋址方式和指令格式種類相對(duì)CISC段之間的緩存時(shí)間)分別為90ns、80ns、70ns和60ns，則該計(jì)算機(jī)的CPUA．90ns B．80ns C．70ns 鐘周期，總線時(shí)鐘頻率為10MHz，則總線帶寬是A．10 B．20 C．40 D．80假設(shè)某計(jì)算機(jī)的系統(tǒng)由Cache和主存組成。某程序執(zhí)行過程中訪存1000次，其中Cache缺失(未命中)50次，則Cache中率是 Ⅱ．處理機(jī)與設(shè)備Ⅲ．處理機(jī)與通道Ⅳ．設(shè)備與設(shè)備 C．先來先服務(wù)調(diào)度算 D．高響應(yīng)比優(yōu)先調(diào)度算 A．界地址保 D．棧保 D．232字C．鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定 D．鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變 文件控制 B．文件分配 C．用戶口令 D．系統(tǒng)設(shè)文件F1的當(dāng)前計(jì)數(shù)值為1，先建立F1的符號(hào)(軟)文件F2，再建立的硬文件F3，然后刪除F1。此時(shí)，F(xiàn)2和F3的計(jì)數(shù)值分別0、 D．2、程序員利用系統(tǒng)調(diào)用打開I/O D．應(yīng)用A．12 B．24 C．48kbpsD．96 A．目的物理地 B．目的IP地 C．源物理地址D．源IP地Gbps，電纜中的信號(hào)速度是200000km/s。若最小數(shù)據(jù)幀長(zhǎng)度減少800比特，則最遠(yuǎn)的A．增加160 B．增加80 C．減少160 D．減少80 D．1當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，如果接下來的4個(gè)RTT(往返時(shí)間)時(shí)間內(nèi)的TCP段的傳輸A．7 B．8 C．9 D．16FTP客戶和服務(wù)器間傳遞FTP命令時(shí)，使用的連接是A．建立在TCP之上的控制連接 42．(15分)已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為datalink，假設(shè)該鏈表只給出(3)根據(jù)設(shè)計(jì)思想步驟，采用程序設(shè)計(jì)語言描述算法(使用C、C++或Java語言43．(8分)某計(jì)算機(jī)的CPU主頻為500MHz，CPI為5(即執(zhí)行每條指令平均需5個(gè)時(shí)鐘周期)。假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB/s，采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送，以32位為(1)在中斷方式下，CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少的時(shí)間占整個(gè)CPU時(shí)間的百分比是多少?(假設(shè)DMA與CPU之間沒有訪存)表示允許數(shù)據(jù)從打入MRMDRin1MDRMR的輸出一直處于使能狀態(tài)。加法指令DR1，R0”(R0)+(R1→(R1，即將R0中的數(shù)據(jù)與R1R1無45．(7分)三個(gè)進(jìn)程P1、P2、P3互斥使用一個(gè)包含N(N>0)個(gè)單元的緩沖區(qū)。P1每次()011—021頁面大小為4KB，一次內(nèi)存的時(shí)間是100ns，一次快表(TLB)的時(shí)間是10ns，依次上述三個(gè)虛地址，各需多少時(shí)間?給出計(jì)算過程基于上述序列，虛地址1565H的物理地址是多少?請(qǐng)說明理由請(qǐng)采用路由聚合技術(shù)，給出R2到局域網(wǎng)1和局域網(wǎng)2的路由(2009年一、單項(xiàng)選二、綜合應(yīng)用【答案要點(diǎn)圖 圖【答案要點(diǎn)算法的基本設(shè)計(jì)思想算法的詳細(xì)實(shí)現(xiàn)步驟typedefstructLNode{intdata：intSearchN(LinkListlist，intint if(count<k)count++；/*計(jì)數(shù)器 }；}}【答案要點(diǎn)中斷方式下，CPU每次用于數(shù)據(jù)傳送的時(shí)鐘周期數(shù)：5×18+5×2=100為達(dá)到外設(shè)0.5MB/s的數(shù)據(jù)傳輸率，外設(shè)每秒申請(qǐng)的中斷次數(shù)：0.5MB/4B=125000。1秒鐘內(nèi)用于中斷的開銷：100×l25000=12500000=12.5M個(gè)時(shí)鐘周期。CPU用于DMA處理的總開銷：1000×500=500000=0.5M個(gè)時(shí)鐘周期?！癆←(R0)”也可在C7：“AC←(MDR)+(A)”之前單列的一個(gè)時(shí)鐘周期內(nèi)執(zhí)參考答案二【答案要點(diǎn)緩沖區(qū)是一互斥資源，因此設(shè)互斥信號(hào)量mutexsemaphoremutex=1;semaphoreodd=0,even=0;semaphoreempty=N;main()ProcessP1{number=produce();P(empty);P(mutex)put()V(mutex)ifnumber%2==0V(even);{ProcessP2P(odd);P(mutex)getodd()V(mutex)V(empty);{ProcessP3while{P(even)P(mutex);geteven();V(mutex)V(empty);{}【答案要點(diǎn)大小為4KB=212B，則得到頁內(nèi)位移占虛地址的低12位，頁號(hào)占剩余。頁號(hào)/頁框號(hào)（4位）頁內(nèi)偏移量（12位(1)可得三個(gè)虛地址的頁號(hào)P及時(shí)間如下(十六進(jìn)制的一位數(shù)字轉(zhuǎn)換成4位二進(jìn)制，因此，十六進(jìn)制的低12位正好為頁內(nèi)位移，最為頁號(hào))：ns+100ns=210ns．1565H：頁號(hào)P=1，有效位為0，不存在內(nèi)存中。先快表10ns，落空，頁表100ns，落空，進(jìn)行缺頁中斷處理108ns，理地址后主存100ns，共計(jì)10ns+100n8+108ns+100ns=100000220放入快表，因此花費(fèi)10ns便可理地址，主存100ns，共計(jì)10ns+100ns=110ns?！敬鸢敢c(diǎn)(若子網(wǎng)1分配給局域網(wǎng)1，子網(wǎng)2分配給局域網(wǎng)——(若子網(wǎng)1分配給局域網(wǎng)2，子網(wǎng)2分配給局域網(wǎng)——R2的路由表中，到局域網(wǎng)1和局域網(wǎng)2的路由表項(xiàng)如一、單項(xiàng)選擇題：第～4小題，每小題分，共分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符合題目要求。A．d，c，e，b，f，aB．c，b，d，a，e，fC．b，c．a(chǎn)，e，f，dD．a(chǎn)，f，e，d，c，b某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作。若元素 A．13、 D．24、 對(duì)n2的是D．樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的

A．僅Ⅰ和 B．僅Ⅰ和 C．僅Ⅱ和 D．Ⅰ、Ⅱ和 分別用IEEE754單精度和雙精度浮點(diǎn)數(shù)格式表示)，已知i=785，f=1.5678e3，d=1.5el00。若Ⅰ．i==(int)(float)iⅡ．Ⅲ．f==(float)(double)fⅣ．(d+f)-A．僅Ⅰ和 B．僅Ⅰ和 C．僅Ⅱ和 D．僅Ⅲ和假定用若干個(gè)2K×4位的組成一個(gè)8K×8位的器，則地址OB1FH所在 Ⅳ．RAM和ROM都需要進(jìn)行刷 A．器地址寄存器 B．程序計(jì)數(shù)器 D．資源A.PCI、CRT、USB、 C．ISA、SCSI、RAM、 D．ISA、EISA、PCI、PCI- Ⅴ．中斷事件處理Ⅵ．恢復(fù)現(xiàn)場(chǎng) 假定一臺(tái)計(jì)算機(jī)的顯示器用DRAM實(shí)現(xiàn)，若要求顯示分辨率為1A．245Mbps B．979Mbps C．1958Mbps I.用戶登錄成功Ⅱ．設(shè)備分 A.僅Ⅰ和 B．僅Ⅱ和 C．僅Ⅰ和 D．Ⅰ、Ⅱ和 intturn=0；若進(jìn)程P0和P1臨界資源的類C偽代碼實(shí)現(xiàn)如下voidP0(進(jìn)程{} 則并發(fā)執(zhí)行進(jìn)程P0和P1時(shí)產(chǎn)生的情形

voidP1( {}}某基于動(dòng)態(tài)分區(qū)管理的計(jì)算機(jī)，其主存容量為55MB(初始為空閑)，采用最佳分配6MB，此時(shí)主存中最大空閑分區(qū)的大小是 B．9 C．10 D．15 A．33 B．519 C．1057 D．16513 A．節(jié)省外存空 B．節(jié)省內(nèi)存空 C．系統(tǒng)調(diào)用服務(wù)程序D．用戶登錄網(wǎng)絡(luò)的層 B．每一層使用的協(xié)C．協(xié)議的實(shí)現(xiàn)細(xì) D．每一層必須完成的功為100Mbps，分組大小為1000B，其中分組頭大小為20B。若主機(jī)H1向主機(jī)H2發(fā)送一個(gè)大小為980000B的文件，則在不考慮分組拆裝時(shí)間和延遲的情況下，從H1發(fā)送開始到H2A．80 B．80.08 C．80.16 D．80.24 C．R1可以經(jīng)過R2到達(dá)net1，跳數(shù)為17D．R1不能經(jīng)過R2到達(dá)net1若路由器R因?yàn)閾砣麃G棄IP分組，則此時(shí)可向發(fā)出該IP分組的源主機(jī)發(fā)送的P D．超某網(wǎng)絡(luò)的IP地址空間為/24 中繼 Ⅲ．網(wǎng) 僅Ⅰ和ⅡB．僅ⅢC．僅Ⅲ和ⅣO主機(jī)甲和主機(jī)乙之間已建立了一個(gè)TCP連接，TCP最大段長(zhǎng)度為1000字節(jié)。若主機(jī)甲的當(dāng)前擁塞窗口為4000字節(jié)，在主機(jī)甲向主機(jī)乙連續(xù)發(fā)送兩個(gè)最大段后，成功收到主機(jī)乙發(fā)送的對(duì)第一個(gè)段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為2000字節(jié)，則此時(shí)主機(jī) B．2 C．3000D4主機(jī)、本地服務(wù)器發(fā)送的請(qǐng)求消息數(shù)分別為一條、一條B．一條、多條C．多條、一條D．多條、多條二儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一維數(shù)組，散列函數(shù)為：H(key)=(key×3)MOD7，處理采請(qǐng)畫出所構(gòu)造的散列表分別計(jì)算等概率情況下查找成功和查找不成功的平均查找長(zhǎng)給出算法的基本設(shè)計(jì)思想根據(jù)設(shè)計(jì)思想，采用C或c++或Java 源操作 操作數(shù)操作數(shù)操作數(shù)轉(zhuǎn)移目標(biāo)地址轉(zhuǎn)移指令的目標(biāo)地址范圍是多少若操作碼0010B表示加法操作(助記符為add)，寄存器R4和R5的分別為100B和44(12程序inta[256][256]；intsum_array1({inti，j，sum=0；returnSum：}

程序inta[256][256]；intsum_array2({inti，j，sum=0；returnsum：}從0開始(3)程序A和B的數(shù)據(jù)各是多少?哪個(gè)程序的執(zhí)行時(shí)間更短記錄16384個(gè)磁盤塊的空閑狀態(tài)。請(qǐng)說明在上述條件下如何進(jìn)行磁盤塊空閑狀態(tài)的管圖所示)，磁道號(hào)請(qǐng)求隊(duì)列為50、90、30、120，對(duì)請(qǐng)求隊(duì)列中的每個(gè)磁道需1個(gè)隨機(jī)分如果將磁盤替換為隨機(jī)的lash半導(dǎo)體器(如盤、SS等)，是否有比AN程最多需要6頁(Page)數(shù)據(jù)空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個(gè)頁框(PageFrame)。在時(shí)刻260前的該進(jìn)程情況如下表所示(位即位07l1391該邏輯地址對(duì)應(yīng)的頁號(hào)是多少47．(9分)某局域網(wǎng)采用CSMA/CD協(xié)議實(shí)現(xiàn)介質(zhì)控制，數(shù)據(jù)傳輸速率為10Mbps，主機(jī)甲和主機(jī)乙之間的距離為2km，信號(hào)速度是200000km/s。請(qǐng)回答下列問題，要求若主機(jī)甲和主機(jī)乙發(fā)送數(shù)據(jù)時(shí)發(fā)生，則從開始發(fā)送數(shù)據(jù)時(shí)刻起，到兩臺(tái)主機(jī)均若網(wǎng)絡(luò)不存在任何與差錯(cuò)，主機(jī)甲總是以標(biāo)準(zhǔn)的最長(zhǎng)以太網(wǎng)數(shù)據(jù)幀(1518字節(jié))計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案及解(2010年一、單項(xiàng)選20.二、綜合應(yīng)用【答案要點(diǎn)H(7)=(7×3)MODH(8)=(8×3)MODH(9)=(9×3)MOD0123456789789給出算法的基本設(shè)計(jì)思想算法實(shí)現(xiàn)voidreverse(intr[]，intleft，int{intk=left，j=right，temp； j-- //j左移一個(gè)}}voidleftShift(intr[]，intn，int{{ }}說明算法復(fù)雜性：上述算法的時(shí)間復(fù)雜度為0(n)，空間復(fù)雜度為0(1)【答案要點(diǎn)KB，按字編址，故共有64K個(gè)單元；地址位數(shù)為16位，所以MAR至少為16位；因?yàn)樽洲D(zhuǎn)移指令的目標(biāo)地址范圍為0000H～FFFFH對(duì)于匯編語句“add(R4)，(R5)+”，對(duì)應(yīng)的機(jī)器碼為：0010001100010101B，用十六【答案要點(diǎn)數(shù)據(jù)Cache的總?cè)萘繛椋?256位(532字節(jié))塊到Cache第6行，a[1][1]所在主存塊到Cache第5行。編譯時(shí)i，j，sum均分配在寄存器中，故數(shù)據(jù)僅考慮數(shù)組a的情況①程序A的數(shù)據(jù)為93.75％；②程序B的數(shù)據(jù)為0【答案要點(diǎn)384/32=512個(gè)字=512x4個(gè)字節(jié)=2KB，正好可放在系統(tǒng)提供的內(nèi)存中?？偟囊苿?dòng)磁道時(shí)間為170ms。由于轉(zhuǎn)速為6000r/m，則平均旋轉(zhuǎn)延遲為5ms，總的旋轉(zhuǎn)延遲時(shí)間=20ms由于轉(zhuǎn)速為6000r/m，則一個(gè)磁道上一個(gè)扇區(qū)的平均時(shí)間為0.1ms，總的扇區(qū)的時(shí)間為0.4ms。上述磁道上所有扇區(qū)所花的總時(shí)間為190.4ms【答案要點(diǎn)因17CAH=0001011111001010B，表示頁號(hào)的位為左邊6位，所以頁號(hào)為5根據(jù)FIFO算法，需要替換裝入時(shí)間最早的頁，故需要置換裝入時(shí)間最早的0并將對(duì)應(yīng)使用位設(shè)置為1，所以對(duì)應(yīng)的物理地址為0000101111001010B，換算成十六進(jìn)制為【答案要點(diǎn)主機(jī)甲和主機(jī)乙之間單向延遲時(shí)間：10μs兩個(gè)方向。因此，甲乙兩臺(tái)主機(jī)均檢測(cè)到時(shí)，最短需經(jīng)過10μs。機(jī)乙(或主機(jī)甲)也開始發(fā)送一個(gè)數(shù)據(jù)幀。這時(shí)，主機(jī)乙(或主機(jī)甲)將立即檢測(cè)到；而主機(jī)甲(或主機(jī)乙)要檢測(cè)到，信號(hào)還需要從主機(jī)乙(或主機(jī)甲)到主機(jī)甲(或主機(jī)乙)，因此，甲乙兩臺(tái)主機(jī)均檢測(cè)到時(shí)，最長(zhǎng)需經(jīng)過20μs。發(fā)送64B的確認(rèn)幀所用時(shí)間(傳輸延遲)：51.2μs。主機(jī)甲的有效數(shù)據(jù)傳輸速率=12000bits/1285.6μs≈9.33Mbps。一、單項(xiàng)選擇題：第1～40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng) C．O(n a，b，c，d，e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是 已知循環(huán)隊(duì)列在一維數(shù)組A[0．．n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素在A[0]處，則初始時(shí)front和rear的值分別是 4．若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是 1，2，3，44，3，2，1， 2011116，該樹對(duì)應(yīng)的二叉樹中無右孩 C．1 D．1 順序B．散列C．鏈?zhǔn)紻．索引11．已知序列25，13，10，12，9是大根堆，在序列尾部新元素18，將其再調(diào)整為大根堆，調(diào)整過程中元間進(jìn)行的比較次數(shù)是 A．C1040000H B．C2420000HC．C184 D．C1C2 A．22 B．23 D．25 D．26間接尋 B．基址尋 C．相對(duì)尋 D．變址尋某機(jī)器有一個(gè)標(biāo)志寄存器，其中有進(jìn)位/借位標(biāo)志CFZF B．SF C．CFZF D．CFSFIII.只有Load/Store指令才能對(duì)操作數(shù)A.僅Ⅰ、 B．僅Ⅱ、 C．僅Ⅰ、 D．Ⅰ、Ⅱ、Cache和指令預(yù)取技術(shù)，且機(jī)器處于“開中斷”狀態(tài)，則在下列有關(guān)指每個(gè)指令周期中 B．每個(gè)指令周期一定大于或等于一個(gè)CPU 某計(jì)算機(jī)處理器主頻為50MHz，采用定時(shí)查詢方式控制設(shè)備A的I/O，查詢程序 AP的代碼段BP用戶程序發(fā)出磁盤I/O請(qǐng)求后，系統(tǒng)的正確處理流程是200001021120132011131001200 A.僅 B．僅 C．僅 D．僅Ⅰ、編 B．編 C．D．裝A．1500μs、1000μs 有兩個(gè)并發(fā)執(zhí)行的進(jìn)程1和2，共享初值為1的變量x。1x1，2x1。加1P1//加1P2//減1loadloadincstoredecstore B．1200波特C．4800波 D．9600波 在子網(wǎng)/30中，能接收目的地址為的IP分組的最大主機(jī)數(shù) 連接，若主機(jī)乙接受該連接請(qǐng)求，則主機(jī)乙向主機(jī)甲發(fā)送的正確的TCP段可能 C．1 D．1二、綜合應(yīng)用題：第41～47小題，共7046∞∞∞5∞∞∞43∞∞33(3)求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑給出算法的基本設(shè)計(jì)思想根據(jù)設(shè)計(jì)思想，采用C或C++或Javaunsignedintx：134：unsignedinty=246；intm=x：intunsignedintz1=x-y：unsignedintz2=x+y：intk1=m-n：Int執(zhí)行上述程序段后，變量m和k1的值分別是多少?(用十進(jìn)制表示地址空間大小為1MB，頁面大小為4KB；Cache采用直接方式，共8行；主存與Cache 0000…11…21…31…40-…51…60-…71…01…10-…21…31…41…51…60-…71…題44-a圖頁表的部分內(nèi)容 題44-b圖Cache的部分內(nèi)容六進(jìn)制題4c圖示則時(shí)地04BC所在的頁面是否在主存中?要求說明理由。有效位標(biāo)記頁框號(hào)有效位標(biāo)記 頁位號(hào)00--10--1110--10--{process顧客{}process{{}} 為快速找到文件，對(duì)于FCB，是集中好，還是與對(duì)應(yīng)的文件數(shù)據(jù)塊連續(xù)好?題47-aWeb服務(wù)器的IP地址是什么?該主機(jī)的默認(rèn)網(wǎng)關(guān)的MAC地址是什么題47-b圖以太網(wǎng)數(shù)據(jù)幀(前80字節(jié)該幀所封裝的I分組經(jīng)過路由器轉(zhuǎn)發(fā)時(shí)，需修改IP分組頭中的哪些字段?注：以太網(wǎng)數(shù)據(jù)幀結(jié)構(gòu)和IP分組頭結(jié)構(gòu)分別如題47-c圖、題47-d圖所示。 目的MAC地 源MAC地 類 數(shù) 題47-c圖題47-d圖IP分組頭(2011年一、單項(xiàng)選【答案要點(diǎn)4605043460504300 3 3 3 0G如下：(2分下圖中雙線箭頭所標(biāo)識(shí)的4個(gè)活動(dòng)組G的關(guān)鍵路徑。(3分給出算法的基本設(shè)計(jì)思想：(5分A、Baba=bab即為所求的中位算法實(shí)現(xiàn)：(8分intM_Search(intA[],intB[],intintstart1,end1,mid1,start2,end2,mid2;start1=0;end1=n-1;start2=0;end2=n-1while(start1!=end1||start2!= mid1=(start1+end1)/2;mid2=(start2+end2)/2;if(A[mid1]==B[mid2])returnA[mid1];if(A[mid1]<B[mid2]) } start1=mid1+1；//舍棄A的前半部分 }}if((start1+end1)％2=：0){//若元素為奇 //舍棄B中間點(diǎn)以前的部分且保留中}else{//若元素為偶數(shù) start2=mid2+1；//B的前半部}}}return}上述所給算法的時(shí)間、空間復(fù)雜度分別是0(log2n)和0(1)。(2分【答案要點(diǎn)134=128+6=10000110B，所以x的機(jī)器數(shù)為10000110B，故R1的內(nèi)容為86H。(1分246=255-9=11110110B，所以y的機(jī)器數(shù)為11110110B。x-y：1000=(0)10010000，括弧中為加法器的進(jìn)位，故R5的內(nèi)容為90H。(1分x+y：10000110 示)時(shí)，其值為-1111010B=-122。(1分)表示)時(shí)，其值為-1110000B=-112。(1分)能。(1分法器實(shí)現(xiàn)，而a-b可用a加b的補(bǔ)數(shù)實(shí)現(xiàn)，即a-b=a+[-b]補(bǔ)(mod2n)，所以n位無符號(hào)整數(shù)加/減運(yùn)由于帶符號(hào)整數(shù)用補(bǔ)碼表示，補(bǔ)碼加/減運(yùn)算公式為：[a+b]補(bǔ)=[a]補(bǔ)+[b]補(bǔ)(mod2n)，[a-b]=[a]補(bǔ)+[-b]補(bǔ) 2n)，所以n位帶符號(hào)整數(shù)加/減運(yùn)算都可在n位加法器中實(shí)現(xiàn)。(1分且不同于輸出端(和)的符號(hào)，則結(jié)果溢出。(或加法器完成加法操作時(shí)，若次的進(jìn)位和最最后一條語句執(zhí)行時(shí)會(huì)發(fā)生溢出。因?yàn)?0000110 【答案要點(diǎn)虛擬地址001C60H=000000000001110001100000B，故虛頁號(hào)為000000000001B頁表001H處的頁框號(hào)(物理頁號(hào))為04H=00000100B，與頁內(nèi)偏移110001100000B拼接成物理地址：00000100110001100000B=04C60H。(1分)對(duì)于物理地址000001001100(4)虛擬地址024BACH=000000100100101110101100B，故虛頁號(hào)為0000別為00000010010B(即012H)和0B，因此，該虛擬地址所對(duì)應(yīng)物理頁面只可能到TLB的由于組0中存在有效位=1、標(biāo)記=012H的項(xiàng)，所以TLB命中，即虛擬地址【答案要點(diǎn)互斥資源：取號(hào)機(jī)(一次只允許一位顧客領(lǐng)號(hào))，因此設(shè)一個(gè)互斥信號(hào)量semaphoremutex=1； semaphoreempty=10； semaphorefull=0； semaphoreservice=0； {process顧客{ }process{{ }}【答案要點(diǎn)(1)在磁盤中連續(xù)存放(采取連續(xù)結(jié)構(gòu))，磁盤尋道時(shí)間更短，文件隨機(jī)效率更高)(【答案要點(diǎn)該主機(jī)在構(gòu)造題47-bAR協(xié)議確定目的MAC地址；(1)因?yàn)镻協(xié)議請(qǐng)求報(bào)文需要進(jìn)行廣播，所以封裝ARP協(xié)議請(qǐng)求報(bào)文的以太網(wǎng)幀的目的MAC地址是ff-ff-ff-ff-ff-ff。(1分該幀所封裝的IP分組經(jīng)過路由器R轉(zhuǎn)發(fā)時(shí)，需要修改IP分組頭中的字段有：源IP地址一、單項(xiàng)選擇題：第～4小題，每小題分，共分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。intfact(int returnn*fact(n-1)；} 只有 B．有e、 C．有e、 D．無法確 存在，且唯一B．存在，且不唯一 使用普里姆(Prim)使用普里姆算法和克魯斯卡爾(Kruskal)僅 B．僅 C．僅Ⅰ、 D．僅Ⅱ、 Ⅰ．簡(jiǎn)單選擇排序Ⅱ．希爾排序 D．僅Ⅲ、Ⅳ、是排序的總趟 B．元素的移動(dòng)次C．使用輔助空間的數(shù) D．元間的比較次假定基準(zhǔn)程序A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為100秒，其中90秒為CPU余為時(shí)間。若CPU速度提高50％，I/O速度不變，則運(yùn)行基準(zhǔn)程序A所耗費(fèi)的時(shí)間5 D．70假定編譯器規(guī)定int和short類型長(zhǎng)度分別為32位和16位，執(zhí)行下列Cunsignedshortx=65530；unsignedint A．0000 B．0000 C．FFFF7FFAHD．FFFFfloat類型(即IEEE754單精度浮點(diǎn)數(shù)格式)能表示的最大正整數(shù)是 struct 元由MOS管組成，是一種半導(dǎo)體 5 B．6 D．33某同步總線的時(shí)鐘頻率為100MHz，寬度為32位，地址/數(shù)據(jù)線復(fù)用，每傳輸一個(gè)A．20ns B．40ns C．50ns D．80nsA．可實(shí)現(xiàn)外設(shè)的即插即用和熱插 Ⅰ．I/O接口中令字 A．系統(tǒng)調(diào) B．外部中 C．進(jìn)程切 D．缺 C．虛擬容量只受外存容量的限 D．虛擬容量只受內(nèi)存容量的限323553235540353640540204425314424 Ⅱ．請(qǐng)求read系統(tǒng)調(diào)用會(huì)導(dǎo)致CPU從用戶態(tài)切換到態(tài)A.僅Ⅰ、 B．僅Ⅰ、 C．僅Ⅱ、 D．Ⅰ、Ⅱ和一個(gè)多道批處理系統(tǒng)中僅有P1和P2兩個(gè)作業(yè)，P2比P1晚5ms到達(dá)。它們的計(jì)算和P1：計(jì)算60ms，I/O80ms，計(jì)算20msP2：計(jì)算120ms，I/O40ms，計(jì)算40msA．240 B．260 C．340 D．360的是A．重排I/O請(qǐng)求次序B．在一個(gè)磁盤上設(shè)置多個(gè)分區(qū) C．有連接不可靠服務(wù)D．有連接可靠服務(wù) 下列關(guān)于IPⅣ．根據(jù)收到的IP分組的目的IP A．SMTP、SMTP、 B．POP3、SMTP、C．POP3、SMTP、 D．SMTP、SMTP、二、綜合應(yīng)用題：第41～47小題，共70給出完整的合并過程，并求出情況下比較的總次數(shù)設(shè)strl和str2分別指向兩個(gè)單詞所在單鏈表的頭結(jié)點(diǎn)鏈表結(jié)點(diǎn)結(jié)構(gòu) datanext給出算法的基本設(shè)計(jì)思想根據(jù)設(shè)計(jì)思想，采用C或c++或Java該計(jì)算機(jī)的MIPS數(shù)是多少?平均每秒Cache缺失的次數(shù)是多少?在不考慮DMA情況下，主存帶寬至少達(dá)到多少才能滿足CPU的訪存要求假定在Cache缺失的情況下主存時(shí)，存在0.0005％的缺頁率，則CPU平均每秒產(chǎn)CPU和DMA控制器同時(shí)要求使用器總線時(shí)，哪個(gè)優(yōu)先級(jí)更高?為什么每的周期為50ns，則該主存能提供的最大帶寬是多少?44表給出了指令系統(tǒng)中部分指令格式，其中Rs和Rd表示寄存器，mem表示單元地址表示寄存器x或單元x的內(nèi)容題44表指令系統(tǒng)中部分指令格ADD LOADSTORE若高級(jí)語言程序中某賦值語句為x=a+b，x、a和b均為int型變量，它們的單元地 LOAD LOAD STORE123456789MMMM題44圖指令序列及其執(zhí)行過程不意則這4條指令執(zhí)行過程中，Ⅰ3，的ID段和Ⅰ4的IF段被阻塞的原因各是什么(1)<0，4>時(shí)，對(duì)應(yīng)的頁框號(hào)是什么(2)<1，11>時(shí)，對(duì)應(yīng)的頁框號(hào)是什么?說明理由塊大小為1KB。文件控制塊(FCB)包含一個(gè)512B的索引表區(qū)。請(qǐng)回答下列問題。時(shí)預(yù)分配的連續(xù)空間，其中起始?jí)K號(hào)占6B，塊數(shù)占2B；剩余504字節(jié)采用直接索引結(jié)到最大，請(qǐng)起始?jí)K號(hào)和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。9b4080061dc0a800d344470bd913846b410000007002435db000245000000004031066ed34447c0a80013880be0599f846b4170121637e1003450000019c4080061dc0a800d344470bd913846b41e0599f5010432b32004450000019d4080061dc0a800d344470bd913846b41e0599f501843c655005450000681140310606d34447c0a80013880be0599f846b4150101657d200根據(jù)題47-a表中的IP分組，分析S已經(jīng)收到的應(yīng)用層數(shù)據(jù)字節(jié)數(shù)是多少47-a表中的某個(gè)I分組在發(fā)出時(shí)的前40字節(jié)如題47-b表所示，則該IP分組到達(dá)H?題47-bS4500006811404006ecd34447ca7601IP1388a1e0599f846b41501016b7d600注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題47-a圖、題47-b圖所示題47-a圖IP分組頭題47-h圖TCP段頭結(jié)計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案及解(2012年一、單項(xiàng)選二、綜合應(yīng)用【答案要點(diǎn)6個(gè)表的合并順序如下頁圖所示第4次合并：表ABC與表DE合并，生成含195個(gè)元素的表第5次合并：表ABCDE與表F合并，生成含395個(gè)元素的最終表。(5分進(jìn)行合并，可以獲得情況下最佳的合并效率。(3分)【答案要點(diǎn)給出算法的基本設(shè)計(jì)思想：(4分①分別求出str1和str2所指的兩個(gè)鏈表的長(zhǎng)度m和 Node{chardata；structNode*next；SNODE*str2){intm，n； /*求str1的長(zhǎng)度。 /$求str2的長(zhǎng)度。 for(q=str2；m<n；n while(p->next!=NULL&&p->next!=q- }returnp- /*返回共同后綴的起始點(diǎn)}intlistlen(SNODE*head){ intlen=0：}return}說明算法的時(shí)間復(fù)雜度：(1分【答案要點(diǎn)平均每秒CPU執(zhí)行的指令數(shù)為：80M/4=20M，故MIPS數(shù)為20；(1分平均每秒Cache缺失的次數(shù)為：20M×1.5×(1-99％)=300000=300K；(1分寬為：16B×300k/s=4.8MB/s。在不考慮DMA傳輸?shù)那闆r下，主存帶寬至少達(dá)到4.8MB/s才求的次數(shù)至少為：1.5×4KB/4B=1.5K=1536。(2分)4體交叉模式能提供的最大帶寬為：4×4B/50ns=320MB/s。(2分)1111111011111111B，即指令執(zhí)行后(R1)=FEFFH。(2分至少需要4+(5-1)=8個(gè)時(shí)鐘周期數(shù)。(2分Ⅰ1．LOADR1，[x] LOAD //或者 STORE123456789MMMMM頁框號(hào)為21。(1分頁框號(hào)為32。(1分頁框號(hào)為41。(1分適合。(1分46．【答案要點(diǎn)文件系統(tǒng)空間共有塊數(shù)242/210=232。為表示232個(gè)塊號(hào)，索引表項(xiàng)占 B。分塊號(hào)占6字節(jié)，塊數(shù)占2字節(jié)的情形下，最大文件長(zhǎng)KB=65620KB。(2分占4B或以上，就可表示4TB大小的文件長(zhǎng)度，達(dá)到文件系統(tǒng)的空間上限。(1分)47．【答案要點(diǎn)由于題47-a表中1、3、4號(hào)分組的源IP地址均為(eoa80008H)，所以1、34號(hào)分組是由H發(fā)送的；(3分題47-a表中l(wèi)號(hào)分組封裝的TCP段的FLAG為02H(即syn=1，ack=0)，seq=846b41c5H，2號(hào)分組封裝的TCP段的FLAG為12H(即syn=1，ack=1)，seq=e0599fefH，ack=846b41e6H，3裝的TCP段可知，ack為846b41d6H，所以S已經(jīng)收到的應(yīng)用層數(shù)據(jù)的字節(jié)數(shù)為846b41d6H-846b41c6H=10H=16B。(2分由于s發(fā)出的IP分組的標(biāo)識(shí)=6811H，所以該分組所對(duì)應(yīng)的是題47-a表中的5一、單項(xiàng)選擇題：～4小題。每小題分，共分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)符合試題要求。 A．n- D．無法確 若X是后序線索二叉樹中的葉結(jié)點(diǎn)，且X存在左兄弟結(jié)點(diǎn)Y，則X C．X的左兄弟結(jié)點(diǎn) D．以Y為根的子樹的最右下結(jié) B．e，a，f，g，b，h，c，dC．d，b，c， c和 D．f和 A2B3C4D5該機(jī)的MIPS A．-1.5×213 B．-1.5×212 C．-0.5×213 D．-0.5×212 B．0 C．1 D …0…1…某計(jì)算機(jī)主存地址空間大小為256MB，按字節(jié)編址。虛擬地址空間大小為4GB，采用頁式管理，頁面大小為4KB，…0…1…0…1…A．015 B．003 D．缺 A．0.25×109條指令/ D．1.03×109條指令/下列選項(xiàng)中，用于設(shè)備和設(shè)備控制器(I/O接口) D．PCI-下列選項(xiàng)中，用于提高RAID可靠性的措磁盤鏡 Ⅲ.奇偶校 僅Ⅰ、 D．僅Ⅱ、Ⅲ和盤控制器延遲為0.2ms，一個(gè)4KB的扇區(qū)所需的平均時(shí)間約為A．9 B．9.4 C．12 D．12.4下列關(guān)于中斷I/O方式和DMA中斷I/O方式請(qǐng)求的是CPU處理時(shí)間，DMA中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，DMA D．釋放與此文件關(guān)聯(lián)的內(nèi)存緩沖為支持CD-ROM中文件的快速隨機(jī)，性能最好的文件數(shù)據(jù)塊組織方是連續(xù)結(jié)．鏈?zhǔn)浇Y(jié) D．多級(jí)索引結(jié)用戶程序發(fā)出磁盤I/O請(qǐng)求后，系統(tǒng)的處理流程是：用戶程序→系統(tǒng)調(diào)用處理程A.用戶程序 Ⅱ.sin()函數(shù)調(diào)用 ADI/O B．?dāng)?shù)據(jù)格式轉(zhuǎn)換C．路由選擇 A．0011 B．1010 C．0101 D．1100主機(jī)甲通過1個(gè)路由器(轉(zhuǎn)發(fā)方式)與主機(jī)乙互聯(lián)，兩段鏈路的數(shù)據(jù)傳輸速率均為10Mbps，主機(jī)甲分別采用報(bào)文交換和分組大小為10kb的分組交換向主機(jī)乙發(fā)送1個(gè)大小為8Mb(1M=106)的報(bào)文。若忽略鏈路延遲、分組頭開銷和分組拆裝時(shí)間，則兩種交換A．800ms、16OO B．801ms、1b00600ms、800 D.1600ms、801 HDLC協(xié)議對(duì)0111110001111110A．0111110000111110 B．0111110001111101C．0111110001111101 D．01111