2014年408真題及答案解析

2014年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合試題2只有一個(gè)選項(xiàng)最符合試題要求。count=0;for(j=1;j<=n;j++)count=0;for(j=1;j<=n;j++)count++;A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)過(guò)程中，當(dāng)掃描到f時(shí)，棧中的元素依次是 。A．+(*- B．+(-* C．/+(*-* D．/+-*循環(huán)隊(duì)列放在一維數(shù)組A[0…M-1]中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空。下列判斷隊(duì)空和隊(duì)滿(mǎn)的條件中，的是 。A．隊(duì)空：end1==end2； 隊(duì)滿(mǎn)：end1==(end2+1)modMB．隊(duì)空：end1==end2； 隊(duì)滿(mǎn)：end2==(end1+1)mod(M-1)Mend1end2+1)modMMend2end1+1)mod(M-1)進(jìn)行中序線(xiàn)索化則結(jié)點(diǎn)x的左右線(xiàn)索指向的結(jié)點(diǎn)分別是 。aabcdxeA．e、c B．e、a C．d、c D．b、a5．將森林F轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)T，F(xiàn)中葉結(jié)點(diǎn)的個(gè)數(shù)等于 。A．T中葉結(jié)點(diǎn)的個(gè)數(shù) B．T中度為1的結(jié)點(diǎn)個(gè)數(shù)C．T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù) D．T中右孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)6．5個(gè)字符有如下4種編碼方案，前綴編碼的是 。A．01,0000,0001,001,1 B．011,000,001,010,1C．000,001,010,011,100 D．0,100,110,1110,1100對(duì)如下所示的有向圖進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁?。A．3,1,2,4,5,6 B．3,1,2,4,6,5C．3,1,4,2,5,6 D．3,1,4,2,6,5會(huì)受堆積現(xiàn)象直接影響的是 。A．存儲(chǔ)效率 B．散列函數(shù) C．裝填(裝載)因子 9．在一棵具有15個(gè)關(guān)鍵字的4階B樹(shù)中，含關(guān)鍵字的結(jié)點(diǎn)個(gè)數(shù)最多是 。A．5 B．6 C．10 D．1510．用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是 。A．2 B．3 C．4 是快速排序第2趟排序結(jié)果的是 。A．2,3,5,4,6,7,9 B．2,7,5,6,4,3,9C．3,2,5,4,7,6,9 D．4,2,3,5,7,6,9程序P在機(jī)器M上的執(zhí)行時(shí)間是20秒，編譯優(yōu)化后，P執(zhí)行的指令數(shù)減少到原來(lái)的70%，而CPI增加到原來(lái)的1.2倍，則P在M上的執(zhí)行時(shí)間是 。A．8.4秒 B．11.7秒 C．14秒 D．16.8秒若x=103，y=-25，則下列表達(dá)式采用8位定點(diǎn)補(bǔ)碼運(yùn)算實(shí)現(xiàn)時(shí)，會(huì)發(fā)生溢出的是 。x+y B．-x+y C．x-y D．-x-yfloat型數(shù)據(jù)據(jù)常用IEEE754單精度浮點(diǎn)格式表示。假設(shè)兩個(gè)float型變量x和y分存器f1和f2中，若(f1)=CC900000H，(f2)=B0C00000H，則x和y之間的關(guān)系為 。x<y且符號(hào)相同 B．x<y且符號(hào)不同C．x>y且符號(hào)相同 D．x>y且符號(hào)不同某容量為256MB的存儲(chǔ)器由若干4M×8位的DRAM芯片構(gòu)成，該DRAM芯片的地址引腳和數(shù)據(jù)引腳總數(shù)是 。A．19 B．22 C．30 D．3616．采用指令Cache與數(shù)據(jù)Cache分離的主要目的是 。降低Cache的缺失損失 B．提高Cache的命中率C．降低CPU平均訪(fǎng)存時(shí)間 D．減少指令流水線(xiàn)資源沖突某計(jì)算機(jī)有16個(gè)通用寄存器采用32位定長(zhǎng)指令字操作碼字（含尋址方式位指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址方式。且偏移量用補(bǔ)碼表示，則Store指令中偏移量的取值范圍是 。A．-32768~+32767 B．-32767~+32768C．-65536~+65535 D．-65535~+65536322條微指4（指令地址，則微指令中下址字段的位數(shù)至少是 。A．5 B．6 C．8 D．9大數(shù)據(jù)傳輸率(總線(xiàn)帶寬)是 。A．132MB/s B．264MB/s C．528MB/s D．1056MB/s續(xù)單元讀出或?qū)懭攵鄠€(gè)數(shù)據(jù)。這種總線(xiàn)事務(wù)方式稱(chēng)為 。A．并行傳輸 B．串行傳輸 C．突發(fā)傳輸 D．同步傳輸21．下列有關(guān)I/O接口的敘述中，的是 。狀態(tài)端口和控制端口可以合用同一個(gè)寄存器I/O接口中CPUI/O端口采用獨(dú)立編址方式時(shí)，I/O端口地址和主存地址可能相同CPUI/O端口求的響應(yīng)和處理時(shí)間為100ns，每400ns發(fā)出一次中斷請(qǐng)求，中斷響應(yīng)所允許的最長(zhǎng)延遲時(shí)間為50ns，則在該設(shè)備持續(xù)工作過(guò)程中，CPU用于該設(shè)備的I/O時(shí)間占整個(gè)CPU時(shí)間的百分比至少是 。A．12.5% B．25% C．37.5% D．50%下列調(diào)度算法中，不可能導(dǎo)致饑餓現(xiàn)象的是 。A．時(shí)間片輪轉(zhuǎn) 靜態(tài)優(yōu)先數(shù)調(diào)度C．非搶占式短作業(yè)優(yōu)先 D．搶占式短作業(yè)優(yōu)先保系統(tǒng)死鎖的設(shè)備數(shù)n最小為 。A．9 B．10 C．11 D．12下列指令中，在用戶(hù)態(tài)執(zhí)行的是 。A．trap指令 B．跳轉(zhuǎn)指令 C．壓棧指令 D．關(guān)中斷指令26．一個(gè)進(jìn)程的讀磁盤(pán)操作完成后，操作系統(tǒng)針對(duì)該進(jìn)程必做的是 。A．修改進(jìn)程狀態(tài)為就緒態(tài) B．降低進(jìn)程優(yōu)先級(jí)C．給進(jìn)程分配用戶(hù)內(nèi)存空間 D．增加進(jìn)程時(shí)間片大小10GB的磁盤(pán)分區(qū)，磁盤(pán)空間以簇(Cluster)為單位進(jìn)行分配，簇的采用位圖法管理該分區(qū)的空閑空間，即用一位(bit)標(biāo)識(shí)一個(gè)簇是否被分配，則存放該位圖所需簇的個(gè)數(shù)為 。A．80 B．320 C．80K D．320K28．下列措施中，能加快虛實(shí)地址轉(zhuǎn)換的是 。I．增大快表(TLB)容量II．讓頁(yè)表常駐內(nèi)存III．增大交換區(qū)(swap)A．僅I 僅II 僅I、II 29．在一個(gè)文件被用戶(hù)進(jìn)程首次打開(kāi)的過(guò)程中，操作系統(tǒng)需做的是 。A．將文件內(nèi)容讀到內(nèi)存中B．將文件控制塊讀到內(nèi)存中C．修改文件控制塊中的讀寫(xiě)權(quán)限D(zhuǎn)．將文件的數(shù)據(jù)緩沖區(qū)首指針?lè)祷亟o用戶(hù)進(jìn)程30．在頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)中，采用某些頁(yè)面置換算法，會(huì)出現(xiàn)Belady異?，F(xiàn)象，即進(jìn)程的缺頁(yè)次數(shù)會(huì)隨著分配給該進(jìn)程的頁(yè)框個(gè)數(shù)的增加而增加。下列算法中，可能出現(xiàn)Belady異常現(xiàn)象的是 。I．LRU算法 II．FIFO算法 III．OPT算法僅II I、II I、III 31．下列關(guān)于管道(Pipe)通信的敘述中，的是 。一個(gè)管道可實(shí)現(xiàn)雙向數(shù)據(jù)傳輸管道的容量?jī)H受磁盤(pán)容量大小限制進(jìn)程對(duì)管道進(jìn)行讀操作和寫(xiě)操作都可能被阻塞D．一個(gè)管道只能有一個(gè)讀進(jìn)程或一個(gè)寫(xiě)進(jìn)程對(duì)其操作32．下列選項(xiàng)中，屬于多級(jí)頁(yè)表優(yōu)點(diǎn)的是 。A．加快地址變換速度 B．減少缺頁(yè)中斷次數(shù)C．減少頁(yè)表項(xiàng)所占字節(jié)數(shù) D．減少頁(yè)表所占的連續(xù)內(nèi)存空間在OSI參考模型中，直接為會(huì)話(huà)層提供服務(wù)的是 。A．應(yīng)用層 B．表示層 C．傳輸層 D．網(wǎng)絡(luò)層某以太網(wǎng)拓?fù)浼敖粨Q機(jī)當(dāng)前轉(zhuǎn)發(fā)表如下圖所示，主機(jī)00-e1-d5-00-23-a1向主機(jī)00-e1-d5-00-23-c1發(fā)送1個(gè)數(shù)據(jù)幀，主機(jī)00-e1-d5-00-23-c1收到該幀后，向主機(jī)1個(gè)確認(rèn)幀，交換機(jī)對(duì)這兩個(gè)幀的轉(zhuǎn)發(fā)端口分別是（A．{3}和{1} B．{2,3}和{1} C．{2,3}和{1,2} D．{1,2,3}和{1}下列因素中，不會(huì)影響信道數(shù)據(jù)傳輸速率的是 。A．信噪比 B．頻率寬帶 C．調(diào)制速率 D．信號(hào)傳播速度36機(jī)與機(jī)之用后退N幀議N輸數(shù)的送口為100，傳輸速率約為 。A．10Mbps B．20Mbps C．80Mbps D．100Mbps37A、B、C通過(guò)CDMA共享鏈路，A、B、C的碼片序列(chippingsequence)分(1,-1,1,-1)和(1,1,-1,-1)C從鏈路上收到的序列是(2,0,2,0,0,-2,0,-2,0,2,0,2)，則C收到A發(fā)送的數(shù)據(jù)是 。A．000 B．101 C．110 D．111了TCP連接，甲始終以MSS=1KB大小的段發(fā)送數(shù)據(jù)，并送；乙每收到一個(gè)數(shù)據(jù)段都會(huì)發(fā)出一個(gè)接收窗口為10KB的確認(rèn)段。若甲在t8KB，則從t時(shí)刻起，不再發(fā)生超時(shí)的情況下，經(jīng)過(guò)10個(gè)RTT后，甲的發(fā)送窗口是 。A．10KB B．12KB C．14KB D．15KB列關(guān)于UDP協(xié)議的敘述中，的是 。I．提供無(wú)連接服務(wù)II．提供復(fù)用/分用服務(wù)III．通過(guò)差錯(cuò)校驗(yàn)，保障可靠數(shù)據(jù)傳輸A．僅I I、II II、III 、II、III網(wǎng)站主頁(yè)時(shí)，使用到的協(xié)議是 。A．PPP B．ARP C．UDP D．SMTP41—4770分。41.(13分)二叉樹(shù)的帶權(quán)路徑長(zhǎng)度(WPL)定一棵二叉樹(shù)T，采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為：leftweightrightweightrootT的根結(jié)點(diǎn)的指針，請(qǐng)TWPL的算法，要求：給出算法的基本設(shè)計(jì)思想；C或C++語(yǔ)言，給出二叉樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義；根據(jù)設(shè)計(jì)思想，采用CC++語(yǔ)言描述算法，關(guān)鍵之處給出注釋。(10分)OSPF42R1維護(hù)的主要鏈4242R1的接口名構(gòu)造出來(lái)的網(wǎng)絡(luò)拓?fù)?。表LSI備注RouterID10.1.1.110.1.1.210.1.1.510.1.1.6IP地址Link1ID10.1.1.210.1.1.110.1.1.610.1.1.5RouterIDIP10.1.1.110.1.1.210.1.1.510.1.1.6IP地址Metric3366Link1的費(fèi)用Link2ID10.1.1.510.1.1.610.1.1.110.1.1.2RouterIDIP10.1.1.910.1.1.1310.1.1.1010.1.1.14IP地址Metric2424Link2的費(fèi)用Net1Prefix192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/24直連網(wǎng)絡(luò)Net1的網(wǎng)絡(luò)前綴Metric1111到達(dá)直連網(wǎng)絡(luò)Net1的費(fèi)用R1構(gòu)造的網(wǎng)絡(luò)拓?fù)湔?qǐng)回答下列問(wèn)題。本題中的網(wǎng)絡(luò)可抽象為數(shù)據(jù)結(jié)構(gòu)中的哪種邏輯結(jié)構(gòu)？42表中的鏈路狀態(tài)信圖(ID標(biāo)識(shí)結(jié)點(diǎn))。按照迪杰斯特拉(Dijikstra)R142192.1.x.x的最短路徑及費(fèi)用。439）4242R142192.1.x.x的路由，且路由表中的路由項(xiàng)盡可能少。目的網(wǎng)絡(luò)下一條接口2）192.1.1.130192.1.7.211發(fā)送一個(gè)TTL=64IP分組時(shí)，R1通過(guò)哪個(gè)192.1.7.211IPTTL是多少？3）R1Metric10Internet42R1LSI需要增加哪些信息？p：:”for(inti=0;i<N;i++)sum+=A[i];”。假sumiR1R2NR6A的表所示。編號(hào)地址機(jī)器代碼匯編代碼注釋108048100H00022080Hloop:sllR4,R2,2(R2)<<2R4208048104H00083020HaddR4,R4,R3(R4)+(R3)R4308048108H8C850000HloadR5,0(R4)((R4)+0)R540804810CH00250820HaddR1,R1,R5(R1)+(R5)R1508048110H20420001HaddR2,R2,1(R2)+1R2608048114H1446FFFAHbneR2,R6,loopif(R2)!=(R6)gotoloopM32bne采用如下格式：31 2625 2120 1615 0OPRsRdOFFSET為偏移量，用補(bǔ)碼表示。請(qǐng)回答下列問(wèn)題，并說(shuō)明理由。1）M的存儲(chǔ)器編址單位是什么？sll指令實(shí)現(xiàn)左移功能，數(shù)組A中每個(gè)元素占多少位？44bne指令的OFFSETbne指令采用相對(duì)尋址方式，PCbne44bne指令內(nèi)容，推斷出bne指令的轉(zhuǎn)移目標(biāo)地址計(jì)算公式。5級(jí)指令流水線(xiàn)：IF（取值、ID（譯碼X（E（3P中哪些指令的執(zhí)行會(huì)由于數(shù)據(jù)相關(guān)而發(fā)生流水線(xiàn)阻塞？哪條指令的執(zhí)行會(huì)發(fā)生控制冒險(xiǎn)？為什么指令1的執(zhí)行不會(huì)因?yàn)榕c指令5的數(shù)據(jù)相關(guān)而發(fā)生阻塞？44M和程序P的機(jī)器代碼，M采用頁(yè)式虛擬存儲(chǔ)管理；P開(kāi)始執(zhí)行時(shí)，(R1)=(R2)=0，(R6)=1000，其機(jī)器代碼已調(diào)入主存但不在Cache中；數(shù)組A未由。1）P執(zhí)行結(jié)束時(shí)，R2的內(nèi)容是多少？Cache16行，Cache和主存交換的32字節(jié)，則其數(shù)據(jù)區(qū)的容量是多少？若僅考慮程序段P的執(zhí)行，則指令Cache的命中率為多少？3）P在執(zhí)行過(guò)程中，哪條指令的執(zhí)行可能發(fā)生溢出異常？哪條指令的執(zhí)行可能產(chǎn)生缺頁(yè)異常？對(duì)于數(shù)組A的訪(fǎng)問(wèn)，需要讀磁盤(pán)和TLB至少各多少次？F30條記錄。請(qǐng)回答下列問(wèn)題，并說(shuō)明理由。F存儲(chǔ)區(qū)域前后均F的文件控制塊內(nèi)容會(huì)發(fā)生哪些改變？若文件系統(tǒng)采用鏈接分配方式，每個(gè)磁盤(pán)塊存放一條記錄和一個(gè)鏈接指針，則完成1KB4個(gè)字節(jié)存放鏈接指針，則該文件系統(tǒng)支持的文件最大長(zhǎng)度是多少？1000件產(chǎn)品的環(huán)形signal())操作實(shí)現(xiàn)進(jìn)程間的互斥與同步，要求寫(xiě)出完整的過(guò)程，并說(shuō)明所用信號(hào)量的含義和初值。2014年計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合試題參考答案一、單項(xiàng)選擇題（一）單選題答案1．C2．B3．A4．D5．C6．D7．D8．D9．D10．B11．C12．D13．C14．A15．A16．D17．A18．C19．C20．C21．D22．B23．A24．B25．D26．A27．A28．C29．B30．A31．C32．D33．C34．B35．D36．C37．B38．A39．B40．D（二）單選題答案解析j<=nj1，每次內(nèi)層循環(huán)都執(zhí)k<=nk*=22k<=nk<=log2n。。對(duì)于嵌套循環(huán)，根T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法思想如下：從左向右開(kāi)始掃描中綴表達(dá)式；遇到數(shù)字時(shí)，加入后綴表達(dá)式；遇到運(yùn)算符時(shí)：'('，入棧；'('，從棧中刪除'('；比它優(yōu)先級(jí)低的或者遇到了一個(gè)左括號(hào)為止。待處理序列棧后綴表達(dá)式當(dāng)前掃描元素動(dòng)作a/b+(c*d-e*f)/gaa加入后綴表達(dá)式/b+(c*d-e*f)/ga//入棧b+(c*d-e*f)/g/abb加入后綴表達(dá)式+(c*d-e*f)/g/ab++優(yōu)先級(jí)低于棧頂?shù)?，彈出/+(c*d-e*f)/gab/++入棧(c*d-e*f)/g+ab/((入棧c*d-e*f)/g+(ab/cc加入后綴表達(dá)式*d-e*f)/g+(ab/c*(，*入棧d-e*f)/g+(*ab/cdd加入后綴表達(dá)式-e*f)/g+(*ab/cd--優(yōu)先級(jí)低于棧頂?shù)?，彈出*-e*f)/g+(ab/cd*-棧頂為(，-入棧e*f)/g+(-ab/cd*ee加入后綴表達(dá)式*f)/g+(-ab/cd*e**優(yōu)先級(jí)高于棧頂?shù)?，*入棧f)/g+(-*ab/cd*eff加入后綴表達(dá)式)/g+(-*ab/cd*ef)把棧中(之前的符號(hào)加入表達(dá)式/g+ab/cd*ef*-//優(yōu)先級(jí)高于棧頂?shù)?，/入棧g+/ab/cd*ef*-gg加入后綴表達(dá)式+/ab/cd*ef*-gab/cd*ef*-g/+完成f的時(shí)候，棧中的元素依次是+(-*B。表達(dá)式為例：第一步：按照運(yùn)算符的優(yōu)先級(jí)對(duì)所有的運(yùn)算單位加括號(hào)。式子變成了：((a/b)+(((c*d)-(e*f))/g))第二步：轉(zhuǎn)換為前綴或后綴表達(dá)式。前綴：把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)前面，則變成了：+(/(ab)/(-(*(cd)*(ef))g))把括號(hào)去掉：+/ab/-*cd*efg前綴式子出現(xiàn)。后綴：把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)后面，則變成了：((ab)/(((cd)*(ef)*)-g)/)+把括號(hào)去掉：ab/cd*ef*-g/+后綴式子出現(xiàn)。A[end1]end11。A[end2]end2再加1A[0]A[0]，然后end20M-2M-1個(gè)區(qū)域，隊(duì)頭為A[M-2]end1end2的狀態(tài)，end1指向隊(duì)end2=M-2+1=M-1，所以可end1==(end2+1)modMA。案，并可以畫(huà)出簡(jiǎn)單的草圖以方便解題。線(xiàn)索二叉樹(shù)的線(xiàn)索實(shí)際上指向的是相應(yīng)遍歷序列特定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，b、a，選D。將森林轉(zhuǎn)化為二叉樹(shù)即相當(dāng)于用孩子兄弟表示法表示森林。在變化過(guò)程中，原森林F中葉結(jié)點(diǎn)的個(gè)數(shù)T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)，選C。A、B、D選項(xiàng)。前綴編碼的定義是在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。D1101100的前綴，違反了前綴編碼的規(guī)則，所以D不是前綴編碼。0的結(jié)點(diǎn)從圖中刪去，此圖中一開(kāi)始只有3031014的04260，此時(shí)選擇刪去不同的結(jié)點(diǎn)，會(huì)得314265314625，選D。產(chǎn)生堆積現(xiàn)象，即產(chǎn)生了沖突，它對(duì)存儲(chǔ)效率、散列函數(shù)和裝填因子均不會(huì)有影響，而平均查找長(zhǎng)度會(huì)因?yàn)槎逊e現(xiàn)象而增大，選D。關(guān)鍵字?jǐn)?shù)量不變，要求結(jié)點(diǎn)數(shù)量最多，那么即每個(gè)結(jié)點(diǎn)中含關(guān)鍵字的數(shù)量最少。根B1個(gè)關(guān)鍵字，非根結(jié)點(diǎn)中最少含4/2-1=1個(gè)關(guān)鍵字，所12個(gè)分支，類(lèi)似與排序二叉樹(shù)，1544BB樹(shù)定義，D。197198要大，DB。ii個(gè)以上的數(shù)出現(xiàn)在它最終2個(gè)這樣的數(shù)的選項(xiàng)。A2、3、6、7、9A排除；B選項(xiàng)中，2、9B排除；D5、9DC選9一個(gè)數(shù)符合，所以C不可能是快速排序第二趟的結(jié)果。xCPI20/x，經(jīng)過(guò)編譯優(yōu)化后，指令條數(shù)減少*CPI=0.7x*24/x=24*0.7=16.8D。13．8位定點(diǎn)補(bǔ)碼表示的數(shù)據(jù)范圍為-128~127，若運(yùn)算結(jié)果超出這個(gè)范圍則會(huì)溢出，AA排除；B選項(xiàng)-x+y=-103-25=-128，符合范圍，B排除；更為麻煩和耗時(shí)，在實(shí)際考試中并不推薦。14．(f1)和(f2)對(duì)應(yīng)的二進(jìn)制分別是(110011001001……)2和(101100001100……)2，根據(jù)1100110011.001，而(f2)的數(shù)符B、D排除，(f1)的(f1)的真值比(f2)x<yA。411001011,可以看出兩數(shù)均為負(fù)數(shù)，100011，可知(f1)的階碼大于(f2)的階碼，真值的絕對(duì)值，因?yàn)槎紴樨?fù)數(shù)，則(f1)<(f2)x<y。log24M=22DRAM采用地址11+8=19A。DRAM是采用傳兩次地址的策略的，所以地址線(xiàn)為正常的一半，這是很多考生容易忽略的地方。么指令流水線(xiàn)中取指部分和取數(shù)部分就可以很好的避免沖突，即減少了指令流水線(xiàn)的沖突。832-8=24位，而16個(gè)4位，而目的操作數(shù)采用基址尋址也要指定一個(gè)寄存器，同樣用掉4位，則留給偏移址的位數(shù)為16位補(bǔ)碼的表示范圍為-32768~+32767A。324條，則指令對(duì)應(yīng)的微指令2128+2=130條，130C。3232bit/8=4B的數(shù)據(jù)，66MHz66M個(gè)時(shí)鐘周期，而每個(gè)時(shí)鐘周期傳送兩次數(shù)據(jù)，可知總線(xiàn)每秒傳送的最大數(shù)據(jù)量為66M×2×4B=528MB528MB/s，選C。C。采用統(tǒng)一編址時(shí)，CPU訪(fǎng)存和訪(fǎng)問(wèn)I/O端口用的是一樣的指令，所以訪(fǎng)存指令可DD。100ns，其中容許的延遲為干擾50ns400ns100ns處理中斷的，所以該設(shè)I/O時(shí)間占整個(gè)CPU100ns/400ns=25%B。采用靜態(tài)優(yōu)先級(jí)調(diào)度時(shí)，當(dāng)系統(tǒng)總是出現(xiàn)優(yōu)先級(jí)高的任務(wù)時(shí)，優(yōu)先級(jí)低的任務(wù)會(huì)總是出現(xiàn)新來(lái)的短任務(wù)時(shí)，長(zhǎng)任務(wù)會(huì)總是得不到處理機(jī)，產(chǎn)生饑餓現(xiàn)象，因此B、C、D都A。110臺(tái)設(shè)備時(shí)，這10。態(tài)轉(zhuǎn)換成為內(nèi)核態(tài)。而關(guān)中斷指令為特權(quán)指令，必須在核心態(tài)才能執(zhí)行，選D。態(tài)（這是操作系統(tǒng)的行為。而降低進(jìn)程優(yōu)先級(jí)、分配用戶(hù)內(nèi)存空間和增加進(jìn)程的時(shí)間片大小都不一定會(huì)發(fā)生，選A。1B4B=2.52.5M2.5M/8=320KB320KB/4KB=80個(gè)簇，選A。虛實(shí)地址轉(zhuǎn)換是指邏輯地址和物理地址的轉(zhuǎn)換。增大快表容量能把更多的表項(xiàng)裝表I、II正確，選C。Open操作，會(huì)把文件的FCB調(diào)入內(nèi)存，而不會(huì)把文件內(nèi)容讀到內(nèi)存中，只有進(jìn)程希望獲取文件內(nèi)容的時(shí)候才會(huì)讀入文件內(nèi)容；C、D明顯錯(cuò)誤，選B。FIFOBelady異常，選A。寫(xiě)管道會(huì)被阻塞，而當(dāng)管道空時(shí)，進(jìn)程讀管道會(huì)被阻塞，因此選C。換速度減慢；也不會(huì)減少缺頁(yè)中斷的次數(shù)，反而如果訪(fǎng)問(wèn)過(guò)程中多級(jí)的頁(yè)表都不在內(nèi)存中，會(huì)大大增加缺頁(yè)的次數(shù)，也并不會(huì)減少頁(yè)表項(xiàng)所占的字節(jié)數(shù)(詳細(xì)解析參考下段)，而多級(jí)頁(yè)制在一頁(yè)之內(nèi)，減少頁(yè)表所占的連續(xù)內(nèi)存空間，因此選D。32位邏輯地址空間，字節(jié)為編址單位，一3B，當(dāng)然，也可（例如取成41K直接為會(huì)話(huà)層提供服務(wù)的即會(huì)話(huà)層的下一層，是傳輸層，選C。00-e1-d5-00-23-c1發(fā)送數(shù)據(jù)幀時(shí)，交換機(jī)轉(zhuǎn)發(fā)表中沒(méi)有同時(shí)因?yàn)檗D(zhuǎn)發(fā)表中并沒(méi)有00-e1-d5-00-23-a1這項(xiàng)，所以轉(zhuǎn)發(fā)表會(huì)把目的地址發(fā)00-e1-d5-00-23-a11B。由香農(nóng)定理可知，信噪比和頻率帶寬都可以限制信道的極限傳輸速率，所以信噪A、B錯(cuò)誤；信道的傳輸速率實(shí)際上就是號(hào)在信道上傳播的速度，與信道的發(fā)送速率無(wú)關(guān)，選D?？紤]制約甲的數(shù)據(jù)傳輸速率的因素，首先，信道帶寬能直接制約數(shù)據(jù)的傳輸速率，N幀協(xié)議，那么因?yàn)镹幀協(xié)議傳輸數(shù)據(jù)，要考慮發(fā)送一個(gè)數(shù)據(jù)到接收到它的確認(rèn)之前，兩個(gè)值中小的那一個(gè)。甲的發(fā)送窗口的尺寸為1000，即收到第一個(gè)數(shù)據(jù)的確認(rèn)之前，最多50+50=100ms=0.1s100ms中，最多能傳輸1MB/0.1s=10MB/s=80Mbps100Mbps，所以答案為min{80Mbps,100Mbps}=80MbpsC。站的碼片序列(1,1,1,1)做內(nèi)積運(yùn)算，結(jié)果分別101B。ssthresh841KB。10個(gè)RTT2、4、5、6、7、8、9、10、11、12，而發(fā)10KB，所以此時(shí)的發(fā)送10KBA。10KB10KB，選項(xiàng)中只有AA。提供的是無(wú)連接的服務(wù)，IUDP也提供復(fù)用/分用服務(wù)，II正確；UDPUDP的差錯(cuò)校驗(yàn)只是檢查數(shù)據(jù)在傳輸?shù)倪^(guò)程中有沒(méi)有出錯(cuò)，UDP協(xié)議時(shí)，可靠傳輸必須由應(yīng)用層實(shí)現(xiàn)，III錯(cuò)誤；答案選B。IPMAC地址時(shí)會(huì)用到ARP協(xié)議，B可能用到；而當(dāng)訪(fǎng)問(wèn)WebDNSIPIP地址時(shí)要使用DNSWeb網(wǎng)頁(yè)不可能用到。二、綜合應(yīng)用題41．解答：的總和，可以使用先序遍歷或?qū)哟伪闅v解決問(wèn)題。1）算法的基本設(shè)計(jì)思想：staticwpl，把每個(gè)結(jié)點(diǎn)的深度作為遞歸函數(shù)的一個(gè)參數(shù)傳遞，算法步驟如下：wpl加上該結(jié)點(diǎn)的深度與權(quán)值之積；對(duì)右子樹(shù)調(diào)用遞歸算法，深度參數(shù)均為本結(jié)點(diǎn)的深度參數(shù)加一；wpl即可。②基于層次遍歷的算法思想是使用隊(duì)列進(jìn)行層次遍歷，并記錄當(dāng)前的層數(shù)，wpl；當(dāng)遍歷到非葉子結(jié)點(diǎn)時(shí)對(duì)該結(jié)點(diǎn)的把該結(jié)點(diǎn)的子樹(shù)加入隊(duì)列；1；隊(duì)列空時(shí)遍歷結(jié)束，返回wpltypedefstructBiTNode{typedefstructBiTNode{intweight;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;算法代碼如下：①基于先序遍歷的算法：intintWPL(BiTreeroot){returnwpl_PreOrder(root,0);}intwpl_PreOrder(BiTreeroot,intdeep){staticintwpl=0;if(root->lchildif(root->lchild==NULL&&root->lchild==NULL)wpl+=deep*root->weight;if(root->lchild!=NULL)wpl_PreOrder(root->lchild,deep+1);if(root->rchild!=NULL)wpl_PreOrder(root->rchild,deep+1);returnwpl;}//若左子樹(shù)不空，對(duì)左子樹(shù)遞歸遍歷//若右子樹(shù)不空，對(duì)右子樹(shù)遞歸遍歷②基于層次遍歷的算法：#define#defineMaxSize100intwpl_LevelOrder(BiTreeroot){BiTreeq[MaxSize];intend1,end2;end1=end2=0;intwpl=0,deep=0;BiTreelastNode;BiTreenewlastNode;lastNode=root;newlastNode=NULL;q[end2++]=root;while(end1!=end2){BiTreet=q[end1++];//設(shè)置隊(duì)列的最大容量//聲明隊(duì)列，end1為頭指針，end2為尾指針//頭指針指向隊(duì)頭元素，尾指針指向隊(duì)尾的后一個(gè)元素//lastNode用來(lái)記錄當(dāng)前層的最后一個(gè)結(jié)點(diǎn)//newlastNode用來(lái)記錄下一層的最后一個(gè)結(jié)點(diǎn)//lastNode初始化為根節(jié)點(diǎn)//newlastNode初始化為空//根節(jié)點(diǎn)入隊(duì)//層次遍歷，若隊(duì)列不空則循環(huán)//拿出隊(duì)列中的頭一個(gè)元素if(t->lchild==NULL&t->lchild==NULL){wpl+=deep*t->weight;} if(t->lchildNULL){ q[end2t->lchild;newlastNode=t->lchild;} if(t->rchildNULL){//處理葉節(jié)點(diǎn)q[end2++]=t->rchild;newlastNode=t->rchild;}if(tlastNode){ lastNodenewlastNode;deep1; }}returnwpl; //wpl}【評(píng)分說(shuō)明】①若考生給出能夠滿(mǎn)足題目要求的其他算法，且正確，可同樣給分。CC++語(yǔ)言，只要正確同樣給分。反映出算法思想且正確，參照①的標(biāo)準(zhǔn)給分。數(shù)值，可視同使用整型類(lèi)型。⑤若考生給出的答案中算法主要設(shè)計(jì)思想或算法中部分正確，可酌情給分。易，希望讀者能掌握。staticwpl并賦值為wpl0static關(guān)鍵字說(shuō)明，intwpl_PreOrder(BiTreeroot,intintwpl_PreOrder(BiTreeroot,intdeep){intlwpl,rwpl;lwpl=rwpl=0;if(root->lchild==NULL&&root->lchild==NULL)returndeep*root->weight;if(root->lchild!=NULL)lwpl=wpl_PreOrder(root->lchild,deep+1);if(root->rchild!=NULL)rwpl=wpl_PreOrder(root->rchild,deep+1);returnlwpl+rwpl;}wpl//若左子樹(shù)不空，對(duì)左子樹(shù)遞歸遍歷//若右子樹(shù)不空，對(duì)右子樹(shù)遞歸遍歷intwpl_PreOrder(BiTreeintwpl_PreOrder(BiTreeroot,intdeep){if(root->lchildNULL&&root->lchildNULL) returndeep*root->weight;return(root->lchild!=NULL?wpl_PreOrder(root->lchild,deep+1):0)+(root->rchild!=NULL?wpl_PreOrder(root->rchild,deep+1):0);}容易忘記三元式(x?y:z)兩端的括號(hào)，若不加括號(hào)，則答案就會(huì)是錯(cuò)誤的。lastNodenewlastNode的區(qū)別，lastNode指的是當(dāng)newlastNode指的是下一層的最后一個(gè)結(jié)點(diǎn)，是動(dòng)態(tài)變化的，習(xí)。42．解答：考察在給出具體模型時(shí)，數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。該題很多考生乍看之下以為是網(wǎng)絡(luò)的題目，結(jié)構(gòu)的內(nèi)容。(1)圖(1分)【評(píng)分說(shuō)明】樣給分。Flag=1NextIDFlag=1NextIDIPMetricFlag=2NextPrefixMaskMetricRouterIDLN_linkRouterIDLN_linkNext其數(shù)據(jù)類(lèi)型定義如下：(3分) typedefstruct{ unsignedunsignedintID,IP;}LinkNode; //Link的結(jié)構(gòu)typedefstruct{unsignedintPrefix,Mask;}NetNode; //Net的結(jié)構(gòu)typedefstructNode{intFlag; union{LinkNodeLnode;NetNodeNnode}LinkORNet;unsignedintMetric;structNode*next;}ArcNode; //弧結(jié)點(diǎn)typedefstructHNode{unsignedintRouterID;ArcNode*LN_link;StructHNode*next;}HNODE; //表頭結(jié)點(diǎn)10.1.1.2310.1.1.110.1.1.1210.1.1.9Flag=2192.1.1.0255.255.255.0110.1.1.5Flag=110.1.1.5310.1.1.210.1.1.210.1.1.2310.1.1.110.1.1.1210.1.1.9Flag=2192.1.1.0255.255.255.0110.1.1.5Flag=110.1.1.5310.1.1.210.1.1.2Flag=110.1.1.6Flag=110.1.1.1Flag=1410.1.1.13Flag=2192.1.6.0255.255.255.01210.1.1.10Flag=2210.1.1.10Flag=2192.1.5.0255.255.255.01Flag=2192.1.7.0255.255.255.0110.1.1.610.1.1.6610.1.1.510.1.1.1Flag=110.1.1.6Flag=110.1.1.610.1.1.6610.1.1.510.1.1.1Flag=110.1.1.6Flag=110.1.1.2Flag=110.1.1.5Flag=1410.1.1.146①若考生給出的答案是將鏈表中的表頭結(jié)點(diǎn)保存在一個(gè)一維數(shù)組中(即采用鄰接表形式)，同樣給分。LinkNet，同時(shí)在表頭結(jié)點(diǎn)中定義了兩個(gè)指針，分別指向由這兩種類(lèi)型的結(jié)點(diǎn)構(gòu)成的兩個(gè)鏈表，同樣給分。IP地址的前綴長(zhǎng)度，也可以與網(wǎng)絡(luò)地址保存在同一個(gè)域中。LSI信息，8個(gè)表頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，均可參照①~③的標(biāo)準(zhǔn)給分。42⑥若解答不完全正確，酌情給分。計(jì)算結(jié)果如下表所示。(4分)目的網(wǎng)絡(luò)路徑代價(jià)（費(fèi)用）1192.1.1.0/24直接到達(dá)12192.1.5.0/24R1R3192.1.5.0/2433192.1.6.0/24R1R2192.1.6.0/2444192.1.7.0/24R1R2R4192.1.7.0/248【評(píng)分說(shuō)明】①若考生給出的各條最短路徑的結(jié)果部分正確，可酌情給分。②若考生給出的從R1192.1.x.x減的次序，可酌情給分。43．解答：因?yàn)轭}目要求路由表中的的路由項(xiàng)盡可能少，所以這里可以把子網(wǎng)192.1.6.0/24和192.1.6.0/23。其他網(wǎng)絡(luò)照常，可得到路由表如下：(6分)目的網(wǎng)絡(luò)下一條接口192.1.1.0/24-E0192.1.6.0/2310.1.1.2L0192.1.5.0/2410.1.1.10L1【評(píng)分說(shuō)明】26分。3條，可酌情給分。通過(guò)查路由表可知：R1L0IP分組。(1分)3個(gè)路192.1.7.211IPTTL64-3=61。(1分)R1LSI需要增加一條特殊的直連網(wǎng)絡(luò)，網(wǎng)絡(luò)前綴Prefix為”0.0.0.0/0”,Metric10。(1分)【評(píng)分說(shuō)明】考生只要回答：增加前綴Prefix為”0.0.0.0/0”，Metric10，同樣給分。44．解答：CPU三個(gè)部分內(nèi)容，考生因注意各章節(jié)內(nèi)容之間的聯(lián)系，才能更好的把握當(dāng)前考試的趨勢(shì)。M24444B，一個(gè)地址單位就代表了1B，所以該計(jì)算機(jī)是按字節(jié)編址的。(2分)4個(gè)地址單位，而計(jì)算機(jī)按字節(jié)編址，所以數(shù)組A4B。(2分)2B的當(dāng)系統(tǒng)執(zhí)行到bne指令時(shí)，PC自動(dòng)加4，PC的內(nèi)容就為08048118H，而跳轉(zhuǎn)的目標(biāo)是18H24個(gè)單位的地址間隔，所以偏移址的一位即是真實(shí)跳轉(zhuǎn)