2014年計(jì)算機(jī)考研真題

1、是考研備考中至關(guān)重要的一環(huán)，真題是必不可少的備考資料。為大家整理了2014年計(jì)算機(jī)考研專業(yè)課真題及答案供大家下載使用，并且提供計(jì)算機(jī)，更多 真題敬請(qǐng)關(guān)注！2014年全國(guó)碩士研究生入學(xué)統(tǒng)一考試?計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項(xiàng)選擇題：第140小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符合試題要求。？1 下列程序段的時(shí)間復(fù)雜度是。cou nt=0;?for(k=1;k<=n;k*=2)?for(j=1;j<=n;j+)?coun t+;?A. O(log2n)?B. 0(n)? C. 0(nlog2n)?D. 0(n2)?2. 假設(shè)棧

2、初始為空，將中綴表達(dá)式a/b+(c*d-e*f)/g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式的過(guò)程中， 當(dāng)掃描到f時(shí)，棧中的元素依次是 ？。?A. +?(?*?-?B. +?(?-?*?C. /?+?(?*?-?*?D. /?+?-?*?3. 循環(huán)隊(duì)列放在一維數(shù)組 A0 -M-1 中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后 一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空。下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是？。?A.隊(duì)空：end1?=?end2; ?隊(duì)滿：end1?=?(end2+1)mod?M?B. 隊(duì)空：end1?=?end2; ?隊(duì)滿：end2?=?(end

3、1+1)mod?(M-1)?C. 隊(duì)空：end2?=?(end1+1)mod?M ; ?隊(duì)滿：end1?=?(end2+1)mod?M?D. 隊(duì)空：end1?=?(end2+1)mod?M ; ?隊(duì)滿：end2?=?(end1+1)mod?(M-1)?4. 若對(duì)如下的二叉樹(shù)進(jìn)行中序線索化，則結(jié)點(diǎn) x的左、右線索指向的結(jié)點(diǎn)分別是。？f A. e、c?B. e、a?C. d、c?D. b、a?5. 將森林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、4種編碼方案，不是前綴編碼的是？。?A. 01,0000,0001,001,1?B. 011,000,001,010,1?C. 000,001,010,011,100?D. 0,100,110,1110,1100?7.對(duì)如下所示的有向圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)湫蛄锌赡苁?。A. 3,1,2,4,5,6? B. 3,1,2,4,6,5? C. 3,1,4,2,5,6? ?D. 3,1,4,2,6,5?&用哈希（散列）方法處理沖突（碰撞）時(shí)可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項(xiàng)中， 會(huì)受堆積現(xiàn)象直接影響的是。A.存儲(chǔ)效率B.散列函數(shù)C.裝填（裝載）因子D.平均查找長(zhǎng)度9在一棵具有15個(gè)關(guān)鍵字的4

5、階B樹(shù)中，含關(guān)鍵字的結(jié)點(diǎn)個(gè)數(shù)最多是。A. 5 B. 6C. 10 D. 1510. 用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是。A. 2 B. 3C. 4 D. 511. 下列選項(xiàng)中，不可能是快速排序第2趟排序結(jié)果的是。A. 2,3,5,4,6,7,9B. 2,7,5,6,4,3,9 C. 3,2,5,4,7,6,9D. 4,2,3,5,7,6,912. 程序P在機(jī)器M上的執(zhí)行時(shí)間是20秒，編譯優(yōu)化后，P執(zhí)行的指令數(shù)減少到原來(lái) 的70%，而CPI增加到原來(lái)的1.2倍，貝U P在M上的執(zhí)行時(shí)間是。A.

6、8.4 秒 B. 11.7 秒C. 14 秒 D. 16.8 秒13. 若x=103, y=-25,則下列表達(dá)式采用 8位定點(diǎn)補(bǔ)碼運(yùn)算實(shí)現(xiàn)時(shí)，會(huì)發(fā)生溢出的是。 A. x+y B. -x+yC. x-yD. -x-y14. float型數(shù)據(jù)據(jù)常用IEEE754單精度浮點(diǎn)格式表示。假設(shè)兩個(gè) float型變量x和y分 別存放在32位寄存器f1和f2中，若（f1）=CC90 0000H, （f2）=B0C0 0000H,則x和y之間的關(guān) 系為。A. x<y且符號(hào)相同B. x<y且符號(hào)不同C. x>y且符號(hào)相同D. x>y且符號(hào)不同15. 某容量為256MB的存儲(chǔ)器由若干 4MX

7、8位的DRAM芯片構(gòu)成，該 DRAM芯片的地 址引腳和數(shù)據(jù)引腳總數(shù)是。A. 19 B. 22 C. 30D. 3616. 采用指令 Cache與數(shù)據(jù)Cache分離的主要目的是。A.降低Cache的缺失損失 B.提高Cache的命中率C.降低CPU平均訪存時(shí)間D.減少指令流水線資源沖突17. 某計(jì)算機(jī)有16個(gè)通用寄存器，采用32位定長(zhǎng)指令字，操作碼字段（含尋址方式位） 為8位，Store指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址方式。若 基址寄存器可使用任一通用寄存器，且偏移量用補(bǔ)碼表示，則Store指令中偏移量的取值范圍是。A-32768 +32767B-32767 +3276

8、8C-65536 +65535D-65535 +6553618某計(jì)算機(jī)采用微程序控制器，共有32 條指令，公共的取指令微程序包含 2 條微指令，各指令對(duì)應(yīng)的微程序平均由 4 條微指令組成， 采用斷定法 （下地址字段法）確定下條微 指令地址，則微指令中下址字段的位數(shù)至少是 。A5B 6C8D919某同步總線采用數(shù)據(jù)線和地址線復(fù)用方式， 其中地址 / 數(shù)據(jù)線有 32 根，總線時(shí)鐘頻 率為 66MHz ，每個(gè)時(shí)鐘周期傳送兩次數(shù)據(jù) （上升沿和下降沿各傳送一次數(shù)據(jù) ），該總線的最大 數(shù)據(jù)傳輸率 （總線帶寬 ）是。A132 MB/sB264 MB/sC528 MB/sD1056 MB/s20一次總線事務(wù)中

9、， 主設(shè)備只需給出一個(gè)首地址， 從設(shè)備就能從首地址開(kāi)始的若干連 續(xù)單元讀出或?qū)懭攵鄠€(gè)數(shù)據(jù)。這種總線事務(wù)方式稱為 。A.并行傳輸B.串行傳輸C.突發(fā)傳輸D.同步傳輸21下列有關(guān) I/O 接口的敘述中，錯(cuò)誤 的是 。A. 狀態(tài)端口和控制端口可以合用同一個(gè)寄存器B. I/O 接口中 CPU 可訪問(wèn)的寄存器稱為 I/O 端口C. 采用獨(dú)立編址方式時(shí)，I/O端口地址和主存地址可能相同D. 采用統(tǒng)一編址方式時(shí)，CPU不能用訪存指令訪問(wèn)I/O端口22. 若某設(shè)備中斷請(qǐng)求的響應(yīng)和處理時(shí)間為100ns,每400ns發(fā)出一次中斷請(qǐng)求，中斷響應(yīng)所允許的最長(zhǎng)延遲時(shí)間為50ns,則在該設(shè)備持續(xù)工作過(guò)程中，CPU用于該設(shè)

10、備的I/O時(shí)間占整個(gè)CPU時(shí)間的百分比至少是。A. 12.5%B. 25%C. 37.5% D. 50%23. 下列調(diào)度算法中,不可能導(dǎo)致饑餓現(xiàn)象的是。A.時(shí)間片輪轉(zhuǎn)B.靜態(tài)優(yōu)先數(shù)調(diào)度C.非搶占式短作業(yè)優(yōu)先D.搶占式短作業(yè)優(yōu)先24某系統(tǒng)有 n 臺(tái)互斥使用的同類設(shè)備,三個(gè)并發(fā)進(jìn)程分別需要3、4、5 臺(tái)設(shè)備,可確保系統(tǒng)不發(fā)生 死鎖的設(shè)備數(shù) n 最小為。A9B10C11D1225下列指令中,不能 在用戶態(tài)執(zhí)行的是。A. trap指令B.跳轉(zhuǎn)指令 C.壓棧指令D.關(guān)中斷指令26一個(gè)進(jìn)程的讀磁盤操作完成后,操作系統(tǒng)針對(duì)該進(jìn)程必做的是。A.修改進(jìn)程狀態(tài)為就緒態(tài)B.降低進(jìn)程優(yōu)先級(jí)C.給進(jìn)程分配用戶內(nèi)存空間D

11、.增加進(jìn)程時(shí)間片大小27.現(xiàn)有一個(gè)容量為 10GB的磁盤分區(qū)，磁盤空間以簇（Cluster）為單位進(jìn)行分配，簇的大小為4KB,若采用位圖法管理該分區(qū)的空閑空間，即用一位（bit）標(biāo)識(shí)一個(gè)簇是否被分配，則存放該位圖所需簇的個(gè)數(shù)為。A80B320C80KD320K28下列措施中,能加快虛實(shí)地址轉(zhuǎn)換的是。I.增大快表（TLB容量II.讓頁(yè)表常駐內(nèi)存HI.增大交換區(qū)（swap）A.僅 I B.僅 IIC.僅 I、II D.僅 II、III29在一個(gè)文件被用戶進(jìn)程首次打開(kāi)的過(guò)程中,操作系統(tǒng)需做的是。A.將文件內(nèi)容讀到內(nèi)存中B.將文件控制塊讀到內(nèi)存中C.修改文件控制塊中的讀寫權(quán)限D(zhuǎn).將文件的數(shù)據(jù)緩沖區(qū)首指

12、針?lè)祷亟o用戶進(jìn)程30在頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)中,采用某些頁(yè)面置換算法,會(huì)出現(xiàn)Belady 異常現(xiàn)象,即進(jìn)程的缺頁(yè)次數(shù)會(huì)隨著分配給該進(jìn)程的頁(yè)框個(gè)數(shù)的增加而增加。下列算法中，可能出現(xiàn)Belady異?，F(xiàn)象的是。I. LRU算法 II. FIFO算法III. OPT算法A.僅 II B.僅 I、IIC.僅 I、III D.僅 II、III31. 下列關(guān)于管道(Pipe)通信的敘述中，正確.的是。A. 個(gè)管道可實(shí)現(xiàn)雙向數(shù)據(jù)傳輸B. 管道的容量?jī)H受磁盤容量大小限制C. 進(jìn)程對(duì)管道進(jìn)行讀操作和寫操作都可能被阻塞D. 個(gè)管道只能有一個(gè)讀進(jìn)程或一個(gè)寫進(jìn)程對(duì)其操作32. 下列選項(xiàng)中，屬于多級(jí)頁(yè)表優(yōu)點(diǎn)的是。A.加快地

13、址變換速度B.減少缺頁(yè)中斷次數(shù)C.減少頁(yè)表項(xiàng)所占字節(jié)數(shù)D.減少頁(yè)表所占的連續(xù)內(nèi)存空間33. 在OSI參考模型中，直接為會(huì)話層提供服務(wù)的是。A.應(yīng)用層B.表示層C.傳輸層 D.網(wǎng)絡(luò)層34 .某以太網(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ī)00-e1-d5-00-23-a1發(fā)送1個(gè)確認(rèn)幀，交換機(jī)對(duì)這兩個(gè)幀的轉(zhuǎn)發(fā)端口分別是()。目的地址口2A. 3和1 B. 2,3和1 C. 2,3和1,2D. 1,2,3和135. 下列因素中，不會(huì)影響信道數(shù)據(jù)傳輸速率的

14、是。A.信噪比B.頻率寬帶C.調(diào)制速率D.信號(hào)傳播速度36. 主機(jī)甲與主機(jī)乙之間使用后退N幀協(xié)議(GBN)傳輸數(shù)據(jù)，甲的發(fā)送窗口尺寸為1000,數(shù)據(jù)幀長(zhǎng)為1000字節(jié)，信道帶寬為100Mbps，乙每收到一個(gè)數(shù)據(jù)幀立即利用一個(gè)短幀(忽略其傳輸延遲)進(jìn)行確認(rèn)，若甲乙之間的單向傳播延遲是50ms，則甲可以達(dá)到的最大平均數(shù)據(jù)傳輸速率約為。A. 10MbpsB. 20MbpsC. 80Mbps D. 100Mbps37. 站點(diǎn)A、B、C通過(guò)CDMA共享鏈路，A、B、C的碼片序列(chipping sequenee)分別 是(1,1,1,1)、(1,-1,1,-1)和(1,1,-1,-1)。若 C 從鏈路

15、上收到的序列是 (2,0,2,0,0,-2,0,-2,0,2,0,2)，則 C收到A發(fā)送的數(shù)據(jù)是。A. 000 B. 101 C. 110 D. 11138. 主機(jī)甲和主機(jī)乙已建立了TCP連接，甲始終以 MSS=1KB大小的段發(fā)送數(shù)據(jù)，并一直有數(shù)據(jù)發(fā)送；乙每收到一個(gè)數(shù)據(jù)段都會(huì)發(fā)出一個(gè)接收窗口為10KB的確認(rèn)段。若甲在t時(shí)刻發(fā)生超時(shí)時(shí)擁塞窗口為8KB,則從t時(shí)刻起，不再發(fā)生超時(shí)的情況下，經(jīng)過(guò)10個(gè)RTT后，甲的發(fā)送窗口是。A. 10KB B. 12KB C. 14KB D. 15KB39. 下列關(guān)于 UDP協(xié)議的敘述中，正確.的是。I.提供無(wú)連接服務(wù) II.提供復(fù)用/分用服務(wù)HI.通過(guò)差錯(cuò)校驗(yàn)，

16、保障可靠數(shù)據(jù)傳輸A.僅 I B.僅 I、II C.僅 II、III D. I、II、III40. 使用瀏覽器訪問(wèn)某大學(xué) Web網(wǎng)站主頁(yè)時(shí)，不可能使用到的協(xié)議是。A. PPPB. ARP C. UDPD. SMTP二、綜合應(yīng)用題：4147小題，共70分。41. （13分）二叉樹(shù)的帶權(quán)路徑長(zhǎng)度（WPL）是二叉樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。給 定一棵二叉樹(shù)T,采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為：丨丨 理 Eight:right I其中葉結(jié)點(diǎn)的weight域保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)root為指向T的根結(jié)點(diǎn)的指針，請(qǐng)?jiān)O(shè)計(jì)求T的WPL的算法，要求：1）給出算法的基本設(shè)計(jì)思想；2）使用C或C+語(yǔ)言，給出二叉樹(shù)

17、結(jié)點(diǎn)的數(shù)據(jù)類型定義；3）根據(jù)設(shè)計(jì)思想，采用 C或C+語(yǔ)言描述算法，關(guān)鍵之處給出注釋。42. （10分）某網(wǎng)絡(luò)中的路由器運(yùn)行 OSPF路由協(xié)議，題 42表是路由器R1維護(hù)的主要鏈 路狀態(tài)信息（LSI）,題42圖是根據(jù)題42表及R1的接口名構(gòu)造出來(lái)的網(wǎng)絡(luò)拓?fù)?。RlJLSIR2 的 LSI艮3的LSI時(shí)的LSI#違Router ID1Q.1 1 IW1 1,110.1 15標(biāo)識(shí)躍主器的IP迪址LinklID10 1.1 1所擬曲器的RLurciIDIP101.1210.1 1510 L1.6Link時(shí)澤地IF地址MetricA,536總Linkl的費(fèi)貝IDJO.所趨由器的Rew斜IDIFIII I

18、iJ10.1104.1 1.010 1 1 1+Link：的乘地IF地址Metric24ALink的費(fèi)冃Neel192.1.C.0 24192 J J.0 汨192.17.0 2-1直連剛第"：1的網(wǎng)絡(luò)前級(jí)1111Si±wi車網(wǎng)絡(luò)Nctl們用題42圖R1構(gòu)造的網(wǎng)絡(luò)拓?fù)湔?qǐng)回答下列問(wèn)題：1）本題中的網(wǎng)絡(luò)可抽象為數(shù)據(jù)結(jié)構(gòu)中的哪種邏輯結(jié)構(gòu)？2） 針對(duì)題42表中的內(nèi)容，設(shè)計(jì)合理的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以保存題42表中的鏈路狀態(tài)信息（LSI）。要求給出鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的數(shù)據(jù)類型定義，并畫出對(duì)應(yīng)題42表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖（示意圖中可僅以ID標(biāo)識(shí)結(jié)點(diǎn)）。3）按照迪杰斯特拉（Dijikstra）算法的

19、策略，依次給出 R1到達(dá)題42圖中子網(wǎng)的 最短路徑及費(fèi)用。43. （ 9分）請(qǐng)根據(jù)題 42描述的網(wǎng)絡(luò)，繼續(xù)回答下列問(wèn)題。1）假設(shè)路由表結(jié)構(gòu)如下 表所示，請(qǐng)給出題42圖中R1的路由表，要求包括到達(dá)題42圖中子網(wǎng)的路由，且 路由表中的路由項(xiàng)盡可能少。丨 目的兀絡(luò) I 一下一條 1 畫口 |2） 當(dāng)主機(jī)向主機(jī)發(fā)送一個(gè)TTL=64的IP分組時(shí)，R1通過(guò)哪個(gè) 接口轉(zhuǎn)發(fā)該IP分組？主機(jī)收到的IP分組TTL是多少？3） 若R1增加一條Metric為10的鏈路連接In ternet，則題42表中R1的LSI需要增加哪 些信息？44. （ 12分）某程序中有如下循環(huán)代碼段p: ” for（int i = 0;

20、i < N; i+） sum+=Ai;。假設(shè)編譯時(shí)變量sum和i分別分配在寄存器 R1和R2中。常量N在寄存器R6中，數(shù)組A的首地 址在寄存器R3中。程序段P起始地址為0804 8100H,對(duì)應(yīng)的匯編代碼和機(jī)器代碼如下表所 示。掃號(hào)地址機(jī)器代碼匯歸代畫1OBiMSWH00022080H:acp- sll(R2 w? 08W81O4EaddOSM810EESCSSCO'OOHlead £5,0 R1)(R1 3) R54C80431 DCH00 2508 20HadcJRlRg(R1V(RS? ->Rl0S04S11CH2C4：0001H60804S114Hl44t

21、iHTAHbne R2:R6hloop:f(R2 i!-iR6) goio leap執(zhí)庁上述代碼為計(jì)凳忙M采毛32位定V指令宇.芽中分玄吿令冗十采距如弋電式;3L25212016150OP I Fb I Md |OFFSETOP為操作碼;；Rs和Rd為寄存器編號(hào)；OFFSETS偏移量，用補(bǔ)碼表示。請(qǐng)回答下列問(wèn) 題，并說(shuō)明理由。1）M的存儲(chǔ)器編址單位是什么？2）已知sll指令實(shí)現(xiàn)左移功能，數(shù)組 A中每個(gè)元素占多少位？3） 題44表中bne指令的OFFSET段的值是多少？已知 bne指令采用相對(duì)尋址方式， 當(dāng)前PC內(nèi)容為bne指令地址，通過(guò)分析題 44表中指令地址和 bne指令內(nèi)容，推斷出 bne

22、 指令的轉(zhuǎn)移目標(biāo)地址計(jì)算公式。4） 若M采用如下 按序發(fā)射、按序完成”的5級(jí)指令流水線：IF （取值）、ID （譯碼及取 數(shù)）、EXE（執(zhí)行）、MEM （訪存）、WB （寫回寄存器），且硬件不采取任何轉(zhuǎn)發(fā)措施，分支 指令的執(zhí)行均引起 3個(gè)時(shí)鐘周期的阻塞，則P中哪些指令的執(zhí)行會(huì)由于數(shù)據(jù)相關(guān)而發(fā)生流水線阻塞？哪條指令的執(zhí)行會(huì)發(fā)生控制冒險(xiǎn)？為什么指令1的執(zhí)行不會(huì)因?yàn)榕c指令 5的數(shù)據(jù)相關(guān)而發(fā)生阻塞？45. 假設(shè)對(duì)于44題中的計(jì)算機(jī) M和程序P的機(jī)器代碼，M采用頁(yè)式虛擬存儲(chǔ)管理；P開(kāi)始執(zhí)行時(shí)，（R1）=（R2）=0, （R6）=1000,其機(jī)器代碼已調(diào)入主存但不在Cache中；數(shù)組A未調(diào)入主存，且所有數(shù)

23、組元素在同一頁(yè)，并存儲(chǔ)在磁盤同一個(gè)扇區(qū)。請(qǐng)回答下列問(wèn)題并說(shuō)明理由。1）P執(zhí)行結(jié)束時(shí)，R2的內(nèi)容是多少？2）M的指令Cache和數(shù)據(jù)Cache分離。若指令 Cache共有16行，Cache和主存交換的塊大小為32字節(jié)，則其數(shù)據(jù)區(qū)的容量是多少？若僅考慮程序段P的執(zhí)行，則指令 Cache的命中率為多少？3）P在執(zhí)行過(guò)程中，哪條指令的執(zhí)行可能發(fā)生溢出異常？哪條指令的執(zhí)行可能產(chǎn)生缺 頁(yè)異常？對(duì)于數(shù)組 A的訪問(wèn)，需要讀磁盤和 TLB至少各多少次？46. 文件F由200條記錄組成，記錄從 1開(kāi)始編號(hào)。用戶打開(kāi)文件后，欲將內(nèi)存中的一 條記錄插入到文件 F 中，作為其第 30 條記錄。請(qǐng)回答下列問(wèn)題，并說(shuō)明理由

24、。1) 若文件系統(tǒng)采用連續(xù)分配方式，每個(gè)磁盤塊存放一條記錄，文件F 存儲(chǔ)區(qū)域前后均 有足夠的空閑磁盤空間， 則完成上述插入操作最少需要訪問(wèn)多少次磁盤塊？ F 的文件控制塊 內(nèi)容會(huì)發(fā)生哪些改變？2) 若文件系統(tǒng)采用鏈接分配方式，每個(gè)磁盤塊存放一條記錄和一個(gè)鏈接指針，則完成上述插入操作需要訪問(wèn)多少次磁盤塊？若每個(gè)存儲(chǔ)塊大小為1KB,其中4個(gè)字節(jié)存放鏈接指針，則該文件系統(tǒng)支持的文件最大長(zhǎng)度是多少？47. 系統(tǒng)中有多個(gè)生產(chǎn)者進(jìn)程和多個(gè)消費(fèi)者進(jìn)程，共享一個(gè)能存放1000 件產(chǎn)品的環(huán)形緩沖區(qū) (初始為空)。當(dāng)緩沖區(qū)未滿時(shí)，生產(chǎn)者進(jìn)程可以放入其生產(chǎn)的一件產(chǎn)品，否則等待； 當(dāng)緩沖區(qū)未空時(shí)， 消費(fèi)者進(jìn)程可以從緩

25、沖區(qū)取走一件產(chǎn)品， 否則等待。 要求一個(gè)消費(fèi)者進(jìn)程 從緩沖區(qū)連續(xù)取出 10 件產(chǎn)品后， 其他消費(fèi)者進(jìn)程才可以取產(chǎn)品。 請(qǐng)使用信號(hào)量 P， V(wait() ， sign al()操作實(shí)現(xiàn)進(jìn)程間的互斥與同步，要求寫出完整的過(guò)程，并說(shuō)明所用信號(hào)量的含義和初值。2014 年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案 一、單項(xiàng)選擇題 一)單選題答案1C2B3A4D 5C6D7D8D9D10B11C12D13 C14A15 A16D17 A18 C19 C20C21 D22B23A24B25D26A27A28C29B30A31 C32D33C34B35D36C37B38A39B40D(二)單選題答案解析1內(nèi)層循

26、環(huán)條件 j<=n 與外層循環(huán)的變量無(wú)關(guān)，每次循環(huán) j 自增 1，每次內(nèi)層循環(huán)都執(zhí) 行n次。外層循環(huán)條件為 k<=n，增量定義為k*=2，可知循環(huán)次數(shù)為 2k<=n,即k<=log2n。 所以內(nèi)層循環(huán)的時(shí)間復(fù)雜度是 0(n)，外層循環(huán)的時(shí)間復(fù)雜度是 O(log2n)。對(duì)于嵌套循環(huán)，根 據(jù)乘法規(guī)則可知,該段程序的時(shí)間復(fù)雜度 T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n) 。2將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法思想如下：從左向右開(kāi)始掃描中綴表達(dá)式； 遇到數(shù)字時(shí)，加入后綴表達(dá)式；遇到運(yùn)算符時(shí)：a. 若為 '(' ，入棧；b. 若

27、為 ')'，則依次把棧中的的運(yùn)算符加入后綴表達(dá)式中， 直到出現(xiàn) '('，從棧中刪除 '(' ；c. 若為除括號(hào)外的其他運(yùn)算符， 當(dāng)其優(yōu)先級(jí)高于除 '('以外的棧頂運(yùn)算符時(shí)， 直接入棧。否則從棧頂開(kāi)始， 依次彈出比當(dāng)前處理的運(yùn)算符優(yōu)先級(jí)高和優(yōu)先級(jí)相等的運(yùn)算符，直到一個(gè)比它優(yōu)先級(jí)低的或者遇到了一個(gè)左括號(hào)為止。當(dāng)掃描的中綴表達(dá)式結(jié)束時(shí)，棧中的所有運(yùn)算符依次出棧加入后綴表達(dá)式。障處理序列冶綴裳達(dá)式當(dāng)前匚1鳩元素a:1加入后猱燕達(dá)式f：號(hào)aab打加入后綴叢達(dá)式ab亠優(yōu):先級(jí)低于棧頂?shù)膹棾鰅t-F-r訪(入槎c*d-eKf; gabe匚加入后

28、製表達(dá)式gab c購(gòu)棧頂沏*入撓d氓星ab cde加入腳表達(dá)式-rab od-優(yōu)先級(jí)吐于核頂?shù)纳讖?qiáng)出*+(ib cd*棧頂-A棧%”at? 0e加入后緩表匹式x-ab cd*e電”優(yōu)先級(jí)書于檯頂?shù)陌葪ab cd* 亡ff加入后鍍表迷式ab cd*e:)把棧中(之前的符號(hào)加入表達(dá)式+ab cd* eP-憂先級(jí)有于禮頂?shù)?人挨gab cd* tf*-gg加入后緩表達(dá)式-/ah掃苗完畢運(yùn)算符気諛退棧加入表辻式ah-由此可知，當(dāng)掃描到 f的時(shí)候，棧中的元素依次是 +(-*，選B。在此，再給出中綴表達(dá)式轉(zhuǎn)換為前綴或后綴表達(dá)式的一種手工做法，以上面給出的中綴 表達(dá)式為例：第一步：按照運(yùn)算符的優(yōu)先級(jí)對(duì)所有

29、的運(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)。當(dāng)題目要求直接求前綴或后綴表達(dá)式時(shí)，這種方法會(huì)比上一種快捷得多。3 end1 指向隊(duì)頭元素，那么可知出隊(duì)的操作是先從Aend1 讀數(shù)，然后 end1 再加 1。end2 指向隊(duì)尾元素的后一個(gè)位置，那么可

30、知入隊(duì)操作是先存數(shù)到 Aend2 ，然后 end2 再加 1。若把A0儲(chǔ)存第一個(gè)元素，當(dāng)隊(duì)列初始時(shí)，入隊(duì)操作是先把數(shù)據(jù)放到A0，然后end2自增，即可知end2初值為0;而endl指向的是隊(duì)頭元素，隊(duì)頭元素的在數(shù)組 A中的下標(biāo)為0，所以得知 end1 初值也為 0，可知隊(duì)空條件為 end1=end2 ；然后考慮隊(duì)列滿時(shí)，因?yàn)殛?duì) 列最多能容納 M-1 個(gè)元素，假設(shè)隊(duì)列存儲(chǔ)在下標(biāo)為 0 到下標(biāo)為 M-2 的 M-1 個(gè)區(qū)域，隊(duì)頭為 A0，隊(duì)尾為AM-2，此時(shí)隊(duì)列滿，考慮在這種情況下endl和end2的狀態(tài)，endi指向隊(duì)頭元素，可知 end1=0， end2 指向隊(duì)尾元素的后一個(gè)位置，可知 end

31、2=M-2+1=M-1 ，所以可 知隊(duì)滿的條件為 end1=(end2+1)mod M ，選 A。注意：考慮這類具體問(wèn)題時(shí)， 用一些特殊情況判斷往往比直接思考問(wèn)題能更快的得到答 案，并可以畫出簡(jiǎn)單的草圖以方便解題。4線索二叉樹(shù)的線索實(shí)際上指向的是相應(yīng)遍歷序列特定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，所以先寫出二叉樹(shù)的中序遍歷序列：edbxac,中序遍歷中在x左邊和右邊的字符，就是它在中序線索化的左、右線索，即b、a，選Do5將森林轉(zhuǎn)化為二叉樹(shù)即相當(dāng)于用孩子兄弟表示法表示森林。在變化過(guò)程中，原森林某結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)作為它的左子樹(shù)， 由于沒(méi)有孩子結(jié)點(diǎn)， 那么轉(zhuǎn)化為二叉樹(shù)時(shí)， 等于 T 中左孩子指針為空的結(jié)

32、點(diǎn)個(gè)數(shù)，選它的兄弟作為它的右子樹(shù)。 那么森林中的葉結(jié)點(diǎn) 該結(jié)點(diǎn)就沒(méi)有左結(jié)點(diǎn)， 所以F中葉結(jié)點(diǎn)的個(gè)數(shù)就 Co此題還可以通過(guò)一些特例來(lái)排除A、B、D選項(xiàng)。6前綴編碼的定義是在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。D中編碼110是編碼1100的前綴，違反了前綴編碼的規(guī)則，所以D不是前綴編碼。7按照拓?fù)渑判虻乃惴?，每次都選擇入度為0的結(jié)點(diǎn)從圖中刪去，此圖中一開(kāi)始只有結(jié)點(diǎn) 3 的入度為 0;刪掉 3結(jié)點(diǎn)后，只有結(jié)點(diǎn) 1 的入度為 0;刪掉結(jié)點(diǎn) 1 后，只有結(jié)點(diǎn) 4 的 入度為 0;刪掉 4結(jié)點(diǎn)后，結(jié)點(diǎn) 2和結(jié)點(diǎn) 6的入度都為 0，此時(shí)選擇刪去不同的結(jié)點(diǎn)，會(huì)得 出不同的拓?fù)湫蛄校謩e

33、處理完畢后可知可能的拓?fù)湫蛄袨?314265 和 314625，選 Do8產(chǎn)生堆積現(xiàn)象， 即產(chǎn)生了沖突， 它對(duì)存儲(chǔ)效率、 散列函數(shù)和裝填因子均不會(huì)有影響， 而平均查找長(zhǎng)度會(huì)因?yàn)槎逊e現(xiàn)象而增大，選 Do9關(guān)鍵字?jǐn)?shù)量不變，要求結(jié)點(diǎn)數(shù)量最多，那么即每個(gè)結(jié)點(diǎn)中含關(guān)鍵字的數(shù)量最少。根 據(jù) 4 階 B 樹(shù)的定義，根結(jié)點(diǎn)最少含 1 個(gè)關(guān)鍵字，非根結(jié)點(diǎn)中最少含 ?4/2?-1=1 個(gè)關(guān)鍵字，所 以每個(gè)結(jié)點(diǎn)中，關(guān)鍵字?jǐn)?shù)量最少都為 1 個(gè)，即每個(gè)結(jié)點(diǎn)都有 2個(gè)分支，類似與排序二叉樹(shù)， 而15個(gè)結(jié)點(diǎn)正好可以構(gòu)造一個(gè) 4層的4階B樹(shù)，使得葉子結(jié)點(diǎn)全在第四層，符合B樹(shù)定義，因此選 Do10.首先，第二個(gè)元素為1，是整個(gè)

34、序列中的最小元素，所以可知該希爾排序?yàn)閺男〉?大排序。然后考慮增量問(wèn)題，若增量為2，第1+2個(gè)元素4明顯比第1個(gè)元素9要大，A排除；若增量為3,第i、i+3、i+6個(gè)元素都為有序序列(i=1,2,3)，符合希爾排序的定義；若增 量為4,第1個(gè)元素9比第1+4個(gè)元素7要大，C排除；若增量為5,第1個(gè)元素9比第1+5 個(gè)元素 8 要大, D 排除,選 Bo11 快排的階段性排序結(jié)果的特點(diǎn)是，第i趟完成時(shí)，會(huì)有i個(gè)以上的數(shù)出現(xiàn)在它最終將要出現(xiàn)的位置，即它左邊的數(shù)都比它小，它右邊的數(shù)都比它大。題目問(wèn)第二趟排序的結(jié)果， 即要找不存在2個(gè)這樣的數(shù)的選項(xiàng)。 A選項(xiàng)中2、3、6、7、9均符合，所以A排除；B選

35、項(xiàng) 中，2、9均符合，所以B排除；D選項(xiàng)中5、9均符合，所以D選項(xiàng)排除；最后看 C選項(xiàng)， 只有9一個(gè)數(shù)符合，所以 C不可能是快速排序第二趟的結(jié)果。12.不妨設(shè)原來(lái)指令條數(shù)為 x,那么原CPI就為20/x，經(jīng)過(guò)編譯優(yōu)化后，指令條數(shù)減少 到原來(lái)的70%，即指令條數(shù)為 0.7x,而CPI增加到原來(lái)的1.2倍，即24/x，那么現(xiàn)在P在M 上的執(zhí)行時(shí)間就為指令條數(shù) *CPI=0.7x*24/x=24*0.7=16.8 秒，選 D。138 位定點(diǎn)補(bǔ)碼表示的數(shù)據(jù)范圍為 -128127，若運(yùn)算結(jié)果超出這個(gè)范圍則會(huì)溢出，A選項(xiàng)x+y=103-25=78，符合范圍，A排除；B選項(xiàng)-x+y=-103-25=-128

36、，符合范圍，B排除；D 選項(xiàng)-x-y=-103+25=-78，符合范圍，D 排除；C選項(xiàng) x-y=103+25=128,超過(guò)了 127，選 C。該題也可按照二進(jìn)制寫出兩個(gè)數(shù)進(jìn)行運(yùn)算觀察運(yùn)算的進(jìn)位信息得到結(jié)果，不過(guò)這種方法更為麻煩和耗時(shí)，在實(shí)際考試中并不推薦。14. （和（f2）對(duì)應(yīng)的二進(jìn)制分別是和 ,）根據(jù)IEEE754浮點(diǎn)數(shù)標(biāo)準(zhǔn)，可知（f1）的數(shù)符為1,階碼為10011001，尾數(shù)為1.001，而（f2）的數(shù)符為 1，階碼為01100001，尾數(shù)為1.1，則可知兩數(shù)均為負(fù)數(shù)，符號(hào)相同，B、D排除，（f1）的絕對(duì)值為1.001 X 226 （f2）的絕對(duì)值為1.1 x 2-30則（的絕對(duì)值比（

37、f2）的絕對(duì)值大，而符號(hào)為負(fù)， 真值大小相反，即（f1）的真值比（f2）的真值小，即x<y,選A。此題還有更為簡(jiǎn)便的算法，（f1）與（f2）的前4位為1100與1011,可以看出兩數(shù)均為負(fù)數(shù)， 而階碼用移碼表示，兩數(shù)的階碼頭三位分別為100和011，可知（f1）的階碼大于（f2）的階碼，又因?yàn)槭荌EEE754規(guī)格化的數(shù)，尾數(shù)部分均為1.xxx，則階碼大的數(shù)，真值的絕對(duì)值必然大，可知（f1）真值的絕對(duì)值大于（f2）真值的絕對(duì)值，因?yàn)槎紴樨?fù)數(shù)，則（f1）<（f2），即x<y。15. 4MX8位的芯片數(shù)據(jù)線應(yīng)為 8根，地址線應(yīng)為log24M=22根，而DRAM采用地址復(fù) 用技術(shù),地

38、址線是原來(lái)的 1/2,且地址信號(hào)分行、列兩次傳送。地址線數(shù)為 22/2=11 根,所以 地址引腳與數(shù)據(jù)引腳的總數(shù)為 11+8=19 根,選 A。此題需要注意的是 DRAM 是采用傳兩次地址的策略的,所以地址線為正常的一半,這 是很多考生容易忽略的地方。16. 把指令Cache與數(shù)據(jù)Cache分離后，取指和取數(shù)分別到不同的Cache中尋找，那么 指令流水線中取指部分和取數(shù)部分就可以很好的避免沖突,即減少了指令流水線的沖突。17. 采用 32 位定長(zhǎng)指令字,其中操作碼為 8 位,兩個(gè)地址碼一共占用 32-8=24 位,而Store指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址，機(jī)器中共

39、有16個(gè)通用寄存器,則尋址一個(gè)寄存器需要 log216=4 位,源操作數(shù)中的寄存器直接尋址用掉 4 位, 而目的操作數(shù)采用基址尋址也要指定一個(gè)寄存器,同樣用掉4 位,則留給偏移址的位數(shù)為24-4-4=16 位,而偏移址用補(bǔ)碼表示, 16 位補(bǔ)碼的表示范圍為 -32768+32767,選 A。18. 計(jì)算機(jī)共有 32 條指令,各個(gè)指令對(duì)應(yīng)的微程序平均為 4 條,則指令對(duì)應(yīng)的微指令 為 32*4=128 條,而公共微指令還有 2 條,整個(gè)系統(tǒng)中微指令的條數(shù)一共為 128+2=130 條, 所以需要?log2130?=8位才能尋址到130條微指令，答案選 G19. 數(shù)據(jù)線有32根也就是一次可以傳送

40、32bit/8=4B的數(shù)據(jù)，66MHz意味著有66M個(gè)時(shí) 鐘 周期 , 而 每個(gè) 時(shí) 鐘 周 期 傳 送 兩 次 數(shù) 據(jù) , 可 知 總 線 每 秒傳 送 的 最 大 數(shù) 據(jù) 量 為 66MX 2 X 4B=528MB所以總線的最大數(shù)據(jù)傳輸率為 528MB/S，選C。20. 猝發(fā) （突發(fā) ）傳輸是在一個(gè)總線周期中,可以傳輸多個(gè)存儲(chǔ)地址連續(xù)的數(shù)據(jù),即一次 傳輸一個(gè)地址和一批地址連續(xù)的數(shù)據(jù), 并行傳輸是在傳輸中有多個(gè)數(shù)據(jù)位同時(shí)在設(shè)備之間進(jìn) 行的傳輸,串行傳輸是指數(shù)據(jù)的二進(jìn)制代碼在一條物理信道上以位為單位按時(shí)間順序逐位傳 輸?shù)姆绞?同步傳輸是指?jìng)鬏斶^(guò)程由統(tǒng)一的時(shí)鐘控制,選 C。21. 采用統(tǒng)一編址時(shí)

41、，CPU訪存和訪問(wèn)I/O端口用的是一樣的指令，所以訪存指令可以 訪問(wèn)I/O端口，D選項(xiàng)錯(cuò)誤，其他三個(gè)選項(xiàng)均為正確陳述，選D。22. 每400ns發(fā)出一次中斷請(qǐng)求，而響應(yīng)和處理時(shí)間為100ns,其中容許的延遲為干擾 信息,因?yàn)樵?50ns 內(nèi),無(wú)論怎么延遲,每 400ns 還是要花費(fèi) 100ns 處理中斷的,所以該設(shè) 備的I/O時(shí)間占整個(gè) CPU時(shí)間的百分比為 100ns/400ns=25%，選B。23. 采用靜態(tài)優(yōu)先級(jí)調(diào)度時(shí),當(dāng)系統(tǒng)總是出現(xiàn)優(yōu)先級(jí)高的任務(wù)時(shí), 優(yōu)先級(jí)低的任務(wù)會(huì)總是得不到處理機(jī)而產(chǎn)生饑餓現(xiàn)象； 而短作業(yè)優(yōu)先調(diào)度不管是搶占式或是非搶占的， 當(dāng)系統(tǒng)總 是出現(xiàn)新來(lái)的短任務(wù)時(shí)，長(zhǎng)任務(wù)會(huì)總

42、是得不到處理機(jī)，產(chǎn)生饑餓現(xiàn)象，因此B、 C、D 都錯(cuò)誤，選 A。24三個(gè)并發(fā)進(jìn)程分別需要 3、4、5 臺(tái)設(shè)備，當(dāng)系統(tǒng)只有 (3-1)+(4-1)+(5-1)=9 臺(tái)設(shè)備時(shí)， 第一個(gè)進(jìn)程分配 2 臺(tái)，第二個(gè)進(jìn)程分配 3 臺(tái)，第三個(gè)進(jìn)程分配 4臺(tái)。這種情況下，三個(gè)進(jìn)程 均無(wú)法繼續(xù)執(zhí)行下去，發(fā)生死鎖。當(dāng)系統(tǒng)中再增加 1 臺(tái)設(shè)備，也就是總共 10 臺(tái)設(shè)備時(shí)，這 最后 1 臺(tái)設(shè)備分配給任意一個(gè)進(jìn)程都可以順利執(zhí)行完成， 因此保證系統(tǒng)不發(fā)生死鎖的最小設(shè) 備數(shù)為 10。25 trap 指令、跳轉(zhuǎn)指令和壓棧指令均可以在用戶態(tài)執(zhí)行，其中trap 指令負(fù)責(zé)由用戶態(tài)轉(zhuǎn)換成為內(nèi)核態(tài)。而關(guān)中斷指令為特權(quán)指令，必須在核心態(tài)

43、才能執(zhí)行，選D。26進(jìn)程申請(qǐng)讀磁盤操作的時(shí)候，因?yàn)橐却齀/O 操作完成，會(huì)把自身阻塞，此時(shí)進(jìn)程就變?yōu)榱俗枞麪顟B(tài)，當(dāng) I/O 操作完成后，進(jìn)程得到了想要的資源，就會(huì)從阻塞態(tài)轉(zhuǎn)換到就緒 態(tài)(這是操作系統(tǒng)的行為) 。而降低進(jìn)程優(yōu)先級(jí)、分配用戶內(nèi)存空間和增加進(jìn)程的時(shí)間片大 小都不一定會(huì)發(fā)生，選 A。27. 簇的總數(shù)為10GB/4KB=2.5M,用一位標(biāo)識(shí)一簇是否被分配，則整個(gè)磁盤共需要 2.5M 位，即需要 2.5M/8=320KB,則共需要 320KB/4KB=80個(gè)簇，選 A。28. 虛實(shí)地址轉(zhuǎn)換是指邏輯地址和物理地址的轉(zhuǎn)換。增大快表容量能把更多的表項(xiàng)裝入 快表中， 會(huì)加快虛實(shí)地址轉(zhuǎn)換的平均速率

44、； 讓頁(yè)表常駐內(nèi)存可以省去一些不在內(nèi)存中的頁(yè)表 從磁盤上調(diào)入的過(guò)程， 也能加快虛實(shí)地址變換； 增大交換區(qū)對(duì)虛實(shí)地址變換速度無(wú)影響， 因 此 I、 II 正確，選 C。29. 個(gè)文件被用戶進(jìn)程首次打開(kāi)即被執(zhí)行了Open操作，會(huì)把文件的 FCB調(diào)入內(nèi)存，而不會(huì)把文件內(nèi)容讀到內(nèi)存中，只有進(jìn)程希望獲取文件內(nèi)容的時(shí)候才會(huì)讀入文件內(nèi)容；C、D 明顯錯(cuò)誤，選 B。30. 只有FIFO算法會(huì)導(dǎo)致Belady異常，選A。31. 管道實(shí)際上是一種固定大小的緩沖區(qū)，管道對(duì)于管道兩端的進(jìn)程而言， 就是一個(gè)文件，但它不是普通的文件， 它不屬于某種文件系統(tǒng)， 而是自立門戶， 單獨(dú)構(gòu)成一種文件系統(tǒng)， 并且只存在于內(nèi)存中。

45、它類似于通信中半雙工信道的進(jìn)程通信機(jī)制， 一個(gè)管道可以實(shí)現(xiàn)雙向 的數(shù)據(jù)傳輸， 而同一個(gè)時(shí)刻只能最多有一個(gè)方向的傳輸， 不能兩個(gè)方向同時(shí)進(jìn)行。 管道的容 量大小通常為內(nèi)存上的一頁(yè)， 它的大小并不是受磁盤容量大小的限制。 當(dāng)管道滿時(shí)， 進(jìn)程在 寫管道會(huì)被阻塞，而當(dāng)管道空時(shí)，進(jìn)程讀管道會(huì)被阻塞，因此選C。32. 多級(jí)頁(yè)表不僅不會(huì)加快地址的變換速度，還因?yàn)樵黾痈嗟牟楸磉^(guò)程， 會(huì)使地址變換速度減慢；也不會(huì)減少缺頁(yè)中斷的次數(shù)，反而如果訪問(wèn)過(guò)程中多級(jí)的頁(yè)表都不在內(nèi)存中， 會(huì)大大增加缺頁(yè)的次數(shù)，也并不會(huì)減少頁(yè)表項(xiàng)所占的字節(jié)數(shù)(詳細(xì)解析參考下段 )，而多級(jí)頁(yè)表能夠減少頁(yè)表所占的連續(xù)內(nèi)存空間， 即當(dāng)頁(yè)表太大時(shí)，

46、 將頁(yè)表再分級(jí)， 可以把每張頁(yè)表控 制在一頁(yè)之內(nèi)，減少頁(yè)表所占的連續(xù)內(nèi)存空間，因此選D。 補(bǔ)充：頁(yè)式管理中每個(gè)頁(yè)表項(xiàng)的大小的下限如何決定？ 頁(yè)表項(xiàng)的作用是找到該頁(yè)在內(nèi)存的位置， 以 32位邏輯地址空間， 字節(jié)為編址單位， 一頁(yè)4KB為例，地址空間內(nèi)一共含有 232B/4KB=1M頁(yè)，則需要log21M=20 位才能保證表示范圍能容納所有頁(yè)面，又因?yàn)橐宰止?jié)作為編址單位，即頁(yè)表項(xiàng)的大小> ?2G8?=3B。所以在這個(gè)條件下，為了保證頁(yè)表項(xiàng)能夠指向所有頁(yè)面，那么頁(yè)表項(xiàng)的大小應(yīng) 該大于3B,當(dāng)然，也可以選擇更大的頁(yè)表項(xiàng)大小以至于讓一個(gè)頁(yè)面能夠正好容下整數(shù)個(gè)頁(yè) 表項(xiàng)以方便存儲(chǔ)(例如取成4B,那么一

47、頁(yè)正好可以裝下1K個(gè)頁(yè)表項(xiàng))，或者增加一些其他信息。33. 直接為會(huì)話層提供服務(wù)的即會(huì)話層的下一層，是傳輸層，選C。34. 主機(jī) 00-e1-d5-00-23-a1 向 00-e1-d5-00-23-c1 發(fā)送數(shù)據(jù)幀時(shí)，交換機(jī)轉(zhuǎn)發(fā)表中沒(méi)有00-e1-d5-00-23-c1 這項(xiàng)，所以向除 1 接口外的所有接口廣播這幀，即2、3 端口會(huì)轉(zhuǎn)發(fā)這幀，同 時(shí) 因 為 轉(zhuǎn) 發(fā) 表 中并 沒(méi) 有 00-e1-d5-00-23-a1 這 項(xiàng) ， 所 以 轉(zhuǎn) 發(fā) 表 會(huì)把 (目 的 地 址 00-e1-d5-00-23-a1 ，端口 1)這項(xiàng)加入轉(zhuǎn)發(fā)表。 而當(dāng) 00-e1-d5-00-23-c1 向 00-e

48、1-d5-00-23-a1 發(fā) 送確認(rèn)幀時(shí)， 由于轉(zhuǎn)發(fā)表已經(jīng)有 00-e1-d5-00-23-a1 這項(xiàng)，所以交換機(jī)只向 1 端口轉(zhuǎn)發(fā)， 選 B。35由香農(nóng)定理可知， 信噪比和頻率帶寬都可以限制信道的極限傳輸速率， 所以信噪比 和頻率帶寬對(duì)信道的數(shù)據(jù)傳輸速率是有影響的，A、B 錯(cuò)誤；信道的傳輸速率實(shí)際上就是信號(hào)的發(fā)送速率，而調(diào)制速度也會(huì)直接限制數(shù)據(jù)的傳輸速率， C 錯(cuò)誤；信號(hào)的傳播速度是信號(hào) 在信道上傳播的速度，與信道的發(fā)送速率無(wú)關(guān)，選D。36考慮制約甲的數(shù)據(jù)傳輸速率的因素，首先，信道帶寬能直接制約數(shù)據(jù)的傳輸速率， 傳輸速率一定是小于等于信道帶寬的；其次，主機(jī)甲乙之間采用后退 N 幀協(xié)議，那么

49、因?yàn)?甲乙主機(jī)之間采用后退 N 幀協(xié)議傳輸數(shù)據(jù)，要考慮發(fā)送一個(gè)數(shù)據(jù)到接收到它的確認(rèn)之前， 最多能發(fā)送多少數(shù)據(jù)， 甲的最大傳輸速率受這兩個(gè)條件的約束， 所以甲的最大傳輸速率是這 兩個(gè)值中小的那一個(gè)。甲的發(fā)送窗口的尺寸為1000，即收到第一個(gè)數(shù)據(jù)的確認(rèn)之前，最多能發(fā)送 1000 個(gè)數(shù)據(jù)幀，也就是發(fā)送 1000*1000B=1MB 的內(nèi)容，而從發(fā)送第一個(gè)幀到接收到 它的確認(rèn)的時(shí)間是一個(gè)往返時(shí)延，也就是50+50=100ms=0.1s，即在100ms中，最多能傳輸1MB 的數(shù)據(jù)，因此此時(shí)的最大傳輸速率為 1MB/0.1s=10MB/s=80Mbps 。信道帶寬為 100Mbps， 所以答案為 min8

50、0Mbps,100Mbps=80Mbps ，選 C。37把收到的序列分成每 4個(gè)數(shù)字一組，即為 (2,0,2,0)、(0,-2,0,-2)、(0,2,0,2)，因?yàn)轭}目 求的是A發(fā)送的數(shù)據(jù)，因此把這三組數(shù)據(jù)與A站的碼片序列(1,1,1,1)做內(nèi)積運(yùn)算，結(jié)果分別是(2,0,2,0) (1；1,1,1)/4=1、(0,-2,0,-2) (1,1,1,1)/4=-1、(0,2,0,2) (1,1,1,1)/4=1，所以 C 接收到的 A 發(fā)送的數(shù)據(jù)是 101，選 B。38當(dāng) t 時(shí)刻發(fā)生超時(shí)時(shí)，把 ssthresh 設(shè)為 8 的一半，即為 4，且擁塞窗口設(shè)為 1KB。 然后經(jīng)歷10個(gè)RTT后，擁塞窗

51、口的大小依次為2、4、5、6、7、8、9、10、11、12,而發(fā)送窗口取當(dāng)時(shí)的擁塞窗口和接收窗口的最小值，而接收窗口始終為10KB,所以此時(shí)的發(fā)送窗口為10KB,選A。實(shí)際上該題接收窗口一直為10KB,可知不管何時(shí)，發(fā)送窗口一定小于等于10KB,選項(xiàng)中只有 A選項(xiàng)滿足條件，可直接得出選Ao39. UDP提供的是無(wú)連接的服務(wù)，I正確；同時(shí)UDP也提供復(fù)用/分用服務(wù)，II正確； UDP雖然有差錯(cuò)校驗(yàn)機(jī)制，但是UDP的差錯(cuò)校驗(yàn)只是檢查數(shù)據(jù)在傳輸?shù)倪^(guò)程中有沒(méi)有出錯(cuò)，出錯(cuò)的數(shù)據(jù)直接丟棄,并沒(méi)有重傳等機(jī)制,不能保證可靠傳輸,使用UDP 協(xié)議時(shí),可靠傳輸必須由應(yīng)用層實(shí)現(xiàn), III 錯(cuò)誤；答案選 Bo40.

52、當(dāng)接入網(wǎng)絡(luò)時(shí)可能會(huì)用到 PPP協(xié)議，A可能用到；而當(dāng)計(jì)算機(jī)不知道某主機(jī)的 MAC 地址時(shí)，用IP地址查詢相應(yīng)的 MAC地址時(shí)會(huì)用到 ARP協(xié)議，B可能用到；而當(dāng)訪問(wèn) Web 網(wǎng)站時(shí)，若DNS緩沖沒(méi)有存儲(chǔ)相應(yīng)域名的 IP地址，用域名查詢相應(yīng)的IP地址時(shí)要使用 DNS 協(xié)議，而DNS是基于UDP協(xié)議的，所以 C可能用到，SMTP只有使用郵件客戶端發(fā)送郵件，或是郵件服務(wù)器向別的郵件服務(wù)器發(fā)送郵件時(shí)才會(huì)用到，單純的訪問(wèn) Web網(wǎng)頁(yè)不可能用到。二、綜合應(yīng)用題41 .解答： 考查二叉樹(shù)的帶權(quán)路徑長(zhǎng)度, 二叉樹(shù)的帶權(quán)路徑長(zhǎng)度為每個(gè)葉子結(jié)點(diǎn)的深 度與權(quán)值之積的總和，可以使用先序遍歷或?qū)哟伪闅v解決問(wèn)題。1) 算

53、法的基本設(shè)計(jì)思想： 基于先序遞歸遍歷的算法思想是用一個(gè)static變量記錄wpl，把每個(gè)結(jié)點(diǎn)的深度作為遞歸函數(shù)的一個(gè)參數(shù)傳遞,算法步驟如下：若該結(jié)點(diǎn)是葉子結(jié)點(diǎn),那么變量 wpl 加上該結(jié)點(diǎn)的深度與權(quán)值之積； 若該結(jié)點(diǎn)非葉子結(jié)點(diǎn), 那么若左子樹(shù)不為空, 對(duì)左子樹(shù)調(diào)用遞歸算法, 若右子樹(shù)不為空, 對(duì)右子樹(shù)調(diào)用遞歸算法,深度參數(shù)均為本結(jié)點(diǎn)的深度參數(shù)加一；最后返回計(jì)算出的 wpl即可。 基于層次遍歷的算法思想是使用隊(duì)列進(jìn)行層次遍歷，并記錄當(dāng)前的層數(shù)，當(dāng)遍歷到葉子結(jié)點(diǎn)時(shí)，累計(jì)wpl ；當(dāng)遍歷到非葉子結(jié)點(diǎn)時(shí)對(duì)該結(jié)點(diǎn)的把該結(jié)點(diǎn)的子樹(shù)加入隊(duì)列；當(dāng)某結(jié)點(diǎn)為該層的最后一個(gè)結(jié)點(diǎn)時(shí)，層數(shù)自增1；隊(duì)列空時(shí)遍歷結(jié)束，返回

54、wpl2) 二叉樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：weight;struct BiTNM *1 血Id嚴(yán)代hUd;JBiTXod? *SiTrw:3) 算法代碼如下： 基于先序遍歷的算法：int WPL(B 訂 ree roat)return_Prr0rdrfroor. 0)c "int 話卩:-PieOnierCB iTt代 root, mt deep i sialic inc'w'pt = 0:定義static 變晁存儲(chǔ) “plifTit)ac->lchil(l = CLL £& roo»Ichild = XULL).f(reob>lchiU f-NULL)_Pi eO rd e: (rooch il dr deep-1):if(rtiDt->rchild != NULL i：_PreOrdrooc->rchi I ci. deep-1 j. ?etvm 叭衛(wèi)1;若為葉于結(jié)自，累稅A'p：若左子崗不空.襯千子杭遙=|遍歷若右子樹(shù)不空，對(duì)右子檢矍日遍歷 基于層次遍歷的算法:int np 1_LfvelQrdfr<31Trfe root kBiTnee q|MaxSizeiint