2023年考研計算機(jī)統(tǒng)考408真題

2014408真題一、單項選擇題以下程序段的時間簡單度是 1 。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;O(logn)2O(n)O(nlogn)2O(n2)假設(shè)棧初始為空將中綴表達(dá)式a/b+(c*d-e*f)/g轉(zhuǎn)換為等價的后綴表達(dá)式的過程中，當(dāng)掃描到f時，棧中的元素依次是 2 。A. +(*-B. +(-*C. /+(*-*D. /+-*循環(huán)隊列放在一維數(shù)組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置假設(shè)隊列兩端均可進(jìn)展入隊和出隊操作隊列中最多能容納M-1個元素。初始時為空。以下推斷隊空和隊滿的條件中，正確的選項是 3 。隊空：end1==end2; 隊滿：end1==(end2+1)modM隊空：end1==end2; 隊滿：end2==(end1+1)mod(M-1)隊空：end1==(end1+1)modM; 隊滿：end1==(end2+1)modM隊空：end1==(end2+1)modM; 隊滿：end2==(end1+1)mod(M-1)假設(shè)對如下的二叉樹進(jìn)展中序線索化，則結(jié)點x的左、右線索指向的結(jié)點分別是4 。e、ce、ad、cb、a將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T，F(xiàn)中葉子的個數(shù)等于 5 。T中葉結(jié)點的個數(shù)T1的結(jié)點個數(shù)T中左孩子指針為空的結(jié)點個數(shù)T中右孩子指針為空的結(jié)點個數(shù)5個字符有如下4種編碼方案，不是前綴編碼的是 6 。A. 01,0000,0001,001,1B. 011,000,001,010,1C. 000,001,010,011,100D. 0,100,110,1110,1100對如下所示的有向圖進(jìn)展拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁?7 。A. 3,1,2,4,5,6B. 3,1,2,4,6,5C. 3,1,4,2,5,6D. 3,1,4,2,6,5用哈〔散列方法處理沖〔碰撞時可能消滅積存〔聚焦現(xiàn)象以下選項中，會受積存現(xiàn)象直接影響的是 8 。存儲效率散列函數(shù)裝填〔裝載〕因子〕平均查找長度在一顆具有15個關(guān)鍵字的4階B樹中，含關(guān)鍵字的結(jié)點個數(shù)最多的是 9 。561015用希爾排序方法對一個數(shù)據(jù)序列進(jìn)展排序時，假設(shè)第1 趟排序結(jié)果為9,1,4,13,7,8,20,23,15，則該趟排序承受的增量〔間隔〕可能是 10 。2345以下選項中，不行能是快速排序第2趟排序結(jié)果的是 11 。A. 2,3,5,4,6,7,9B. 2,7,5,6,4,3,9C. 3,2,5,4,7,6,9D. 4,2,3,5,7,6,9程序P在機(jī)器M上的執(zhí)行時間是20秒，編譯優(yōu)化后，P執(zhí)行的指令數(shù)削減到原來的70%，而CPI增加到原來的1.2倍，則P在M上的執(zhí)行時間是 12 。8.4秒B. 11.7秒C. 14秒D. 16.8秒x=102,y=-258位定點補(bǔ)碼運算實現(xiàn)時，會發(fā)送溢出的是13 。x+y–x+yx-y–x-yfloatIEEE754float型變量xy分別存32位存放器f和f(f)=CC900000H,(f)=B0C00000Hxy之間的關(guān)1 2 1 2系為14 。x<y且符號一樣x<y且符號不同x>y且符號一樣x>y且符號不同256MB4M*8DRAMDRAM芯片的地址引腳和數(shù)據(jù)引腳總數(shù)是15。19223036承受指令Cache與數(shù)據(jù)Cache分別的主要目的是 16 。Cache的缺失損失Cache的命中率CPU平均訪存時間削減指令流水線資源沖突1632〔含尋址方式位〕為8位，Store指令的源操作數(shù)和目的操作數(shù)分別承受存放器直接尋址和基址尋址Store指令中偏移量的取值范圍是17。A. -32768~+32767B. -32767-~32768C. -65536~+65535D. -65535~+65536324條微指令組成，承受斷定法〔下地址字段法〕確定下條微指令地址，則微指令中下地址字段的位數(shù)至少是18。5689某同步總線承受數(shù)據(jù)線和地址線復(fù)用方式，其中地址/32根，總線時鐘頻率為，每個時鐘周期傳送兩次數(shù)據(jù)〔上升沿和下降沿各傳送一次數(shù)據(jù)，該總線的最大數(shù)據(jù)傳輸率〔總線帶寬〕是19。132MB/s264MB/s528MB/s1056MB/s一次總線事務(wù)中，主設(shè)備只需給出一個首地址，從設(shè)備就能從首地址開頭的假設(shè)干連續(xù)單元讀出或?qū)懭攵鄠€數(shù)據(jù)。這種總線事務(wù)方式稱為20 。并行傳輸串行傳輸突發(fā)傳輸同步傳輸以下有關(guān)I/O接口的表達(dá)中，錯誤的選項是 21 。狀態(tài)端口和掌握端口可以合用同一個存放器。I/OCPUI/O端口承受獨立編址方式時，I/O端口地址和主存地址可能一樣承受統(tǒng)一編址方式時，CPUI/O端口100ns，每400ns發(fā)出一次中斷懇求，中斷50ns，則在該設(shè)備持續(xù)工作過程中，CPU用于該設(shè)備I/OCPU時間的百分比至少是22。A. 12.5%B. 25%C. 37.5%D. 50%以下調(diào)度算法中，不行能導(dǎo)致饑餓現(xiàn)象的是23 。時間片輪轉(zhuǎn)靜態(tài)優(yōu)先數(shù)調(diào)度非搶占短作業(yè)優(yōu)先搶占式短作業(yè)優(yōu)先某系統(tǒng)有n臺互斥使用的同類設(shè)備，三個并發(fā)進(jìn)程分別需要3，4，5臺設(shè)備，可確保系統(tǒng)不發(fā)生死鎖的設(shè)備數(shù)n最小為 24 。9101112以下指令中，不能在用戶態(tài)執(zhí)行的是 25 。Trap指令跳轉(zhuǎn)指令壓棧指令關(guān)中斷指令一個進(jìn)程的讀磁盤操作完成后，操作系統(tǒng)針對該進(jìn)程必做的是26 。修改進(jìn)程狀態(tài)為就緒態(tài)降低進(jìn)程優(yōu)先級給進(jìn)程安排用戶內(nèi)存空間增加進(jìn)程時間片大小現(xiàn)有一個容量為10GB的磁盤分區(qū)，磁盤空間以簇〔Cluster〕為單位進(jìn)展安排，簇的大小為4KB，假設(shè)承受位圖法治理該分區(qū)的空閑空間，即用一位〔bit〕標(biāo)識一個簇是否被安排，則存放該位圖所需簇的個數(shù)為27。80B. 32080K320K以下措施中，能加快虛實地址轉(zhuǎn)換的是 28 。I.增大塊表〔TLB〕容量讓頁表常駐內(nèi)存增大交換區(qū)〔swap〕IIII、IIII、III在一個文件被用戶進(jìn)程首次翻開的過程中，操作系統(tǒng)需做的是29 。將文件內(nèi)容讀到內(nèi)存中將文件掌握塊讀到內(nèi)存中修改文件掌握塊中的讀寫權(quán)限將文件的數(shù)據(jù)緩沖區(qū)首指針返回給用戶進(jìn)程在頁式虛擬存儲治理系統(tǒng)中承受某此頁面轉(zhuǎn)換算法會消滅Belady特別現(xiàn)象，即進(jìn)程的缺頁次數(shù)會隨著安排給該進(jìn)程的頁框個數(shù)的增加而增加。以下算法中，可能現(xiàn)出Belady特別現(xiàn)象的是 30 。LRU算法FIFO算法OPT算法III、III、IIIII、III以下關(guān)于管道〔Pipe〕通信的表達(dá)中，正確的選項是 31 。一個管道可實現(xiàn)雙向數(shù)據(jù)傳輸管道的容量僅受磁盤容量大小限制進(jìn)程對管道進(jìn)展讀操作和寫操作都可能被堵塞一個管道只能有一個讀進(jìn)程或一個寫進(jìn)程對其操作以下選項中，屬于多級頁表優(yōu)點的是 32 。加快地址變換速度削減缺頁中斷次數(shù)削減頁表所占字節(jié)數(shù)削減所點的連續(xù)內(nèi)存空間在OSI參考模型中，直接為會話層供給效勞的是 33 。應(yīng)用層表示層傳輸層網(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個數(shù)據(jù)幀，主機(jī)00-e1-d5-00-23-c1收到該幀后，向主機(jī)00-e1-d5-00-23-a134。A. {3}和{1}B. {2,3}和{1}C. {2,3}和{1,2}D. {1,2,3}和{1}以下因素中，不會影響信道數(shù)據(jù)傳輸速率的是 35 。信噪比頻率寬帶調(diào)制速率信號傳播速度主機(jī)甲與主機(jī)乙之間使用后退N幀協(xié)議〔GBN〕傳輸數(shù)據(jù)，甲和窗口尺寸為1000，數(shù)據(jù)幀為1000字節(jié)，信道帶寬為100Mbps，乙每收到一個數(shù)據(jù)幀馬上利用一個短幀〔無視其傳輸延遲〕進(jìn)展確認(rèn)，假設(shè)甲、乙之間的單向傳播延遲是50ms，則甲可以到達(dá)的最大平均數(shù)據(jù)傳輸速率約為 36 。10Mbps20Mbps80Mbps100MbpsA、B、CCDMA共享鏈路，A、B、C的碼片序列〔chippingsequence〕分(1,1,1,1)(1,-1,1,-1)(1,1,-1,-1)。假設(shè)C(2,0,2,0,-2,0,-2,0,2,0,2)C收到A發(fā)送的數(shù)據(jù)是37。A. 000B. 101C. 110D. 111TCPMSS=KB大小的段發(fā)送數(shù)據(jù)，并始終有10KBt8KBt時刻起，不再發(fā)生超時的狀況下，經(jīng)過10RTT后，甲的發(fā)送窗口是38。10KB12KB14KB15KB以下關(guān)于UDP協(xié)議的表達(dá)中，正確的選項是 39 。I.供給無連接效勞供給復(fù)用/分用效勞通過過失校驗，保障牢靠數(shù)據(jù)傳輸II、IIII、IIII、II、III使用掃瞄器訪問某大學(xué)Web網(wǎng)站主頁時，不行能使用到的協(xié)議是 40 。PPPARPUDPSMTP二、綜合應(yīng)用題二叉樹的帶權(quán)路徑長度〔WPL〕是二叉樹中全部葉結(jié)點的帶權(quán)路徑長度之和。給定一棵二叉樹T，承受二叉鏈表存儲，結(jié)點構(gòu)造為：weight域保存該結(jié)點的非負(fù)權(quán)值root為指向T的根結(jié)點的指針，請設(shè)計求TWPL的算法，要求：給出算法的根本設(shè)計思想；使用CC++語言，給出二叉樹結(jié)點的數(shù)據(jù)類型定義；依據(jù)設(shè)計思想，承受C或C++語文描述算法，關(guān)鍵之處給出注釋。OSPF42R1維護(hù)的主要鏈路狀態(tài)信息，題2圖是依據(jù)題2表的接口名構(gòu)造出來的網(wǎng)絡(luò)拓?fù)?。請答?fù)以下問題。

42圖R1構(gòu)造的網(wǎng)絡(luò)拓?fù)浯祟}中的網(wǎng)絡(luò)可抽象為數(shù)據(jù)構(gòu)造中的哪種構(gòu)造？42表中的內(nèi)容，設(shè)計合理的鏈?zhǔn)酱鎯?gòu)造，以保存題42表中的鏈路狀態(tài)信息。要求給出鏈?zhǔn)酱鎯?gòu)造的數(shù)據(jù)定義，并畫出對應(yīng)題2存儲構(gòu)造示意圖〔ID標(biāo)識結(jié)點。依據(jù)迪杰斯特拉〔Dijkstra〕R142圖中子網(wǎng)192.1.x.x的最短路徑及費用42描述的網(wǎng)絡(luò)，連續(xù)答復(fù)以下問題。1) 42R1的路由表，要求包括到達(dá)題42192.1.x.x的路由，且路由表中的路由項盡可能少。) 當(dāng)計算機(jī)0向主機(jī)1發(fā)送一個4的P1通過IP192.1.7.211IPTTL是多少？3)R1Metric10Internet42R1LSI需要增加哪些信息？某程序中有如下循環(huán)代碼段p“for(inti=0;i<N;i++)sum+=A[i];”。假設(shè)編譯時變量sumiR1R2中。常量NR6A的首地址R3中。程序段P08048100H，對應(yīng)的匯編代碼和機(jī)器代碼如下表所示。執(zhí)行上述代碼的計算機(jī)M承受32bne承受如下格式：OP為操作碼，RsRd為存放器編號；OFFSET為偏移量，用補(bǔ)碼表示。請答復(fù)以下問題，并說明理由。M的存儲器編址單位是什么？sll指令實現(xiàn)左移功能，數(shù)組A中的每個元素占多少位？44bneOFFSETbne指令承受相對尋址方PCbne指令地址，通過分析題44bne指令內(nèi)bne指令的轉(zhuǎn)移目標(biāo)地址計算公式。M承受如下“按序放射、按序完成”的5級指令流水線：IF〔取值、ID〔譯碼及取數(shù)、〔執(zhí)行〔訪存、〔寫回存放器，且硬件不實行任何轉(zhuǎn)發(fā)措施，分支指令的執(zhí)行均引起3個時鐘周期的堵塞，則P中哪些指令的執(zhí)行會由于數(shù)據(jù)相關(guān)而發(fā)生流水線堵塞？哪條指令的執(zhí)行會發(fā)生掌握冒險？為15的數(shù)據(jù)相關(guān)而發(fā)生堵塞？44MP的機(jī)器代碼，M承受頁式虛擬存儲治理；P開頭執(zhí)行時，(R1)=(R2)=0，(R6)=1000，其機(jī)器代碼已調(diào)入主存但不在Cache中；數(shù)組A未調(diào)入主存，且全部數(shù)組元素在同一頁，并存儲在磁盤同一個扇區(qū)。請答復(fù)以下問題并說明理由。P執(zhí)行完畢時，R1的內(nèi)容是多少？MCacheCacheCache16行，Cache和主存交32字節(jié)，則其數(shù)據(jù)區(qū)的容量是多少？假設(shè)僅考慮程序段P的執(zhí)行，Cache的命中率為多少？P在執(zhí)行過程中，哪條指令的執(zhí)行可能發(fā)生溢出特別？哪條指令的執(zhí)行可能產(chǎn)生缺頁特別？對于數(shù)組ATLB至少各多少次？F200條記錄組成，記錄從1開頭編號。用戶翻開文件后，欲將內(nèi)存中的一條記錄插入到文件F30條記錄。請答復(fù)以下問題，并說明理由。假設(shè)文件系統(tǒng)承受連續(xù)安排方式，每個磁盤塊存放一條記錄，文件F存儲區(qū)域前后均有足夠的空閑磁盤空間，則完成上述插入操作最少需要訪問多少次磁盤塊？F的文件掌握塊內(nèi)容會發(fā)生哪些轉(zhuǎn)變？假設(shè)文件系統(tǒng)承受鏈接安