計算機(jī)統(tǒng)考真題及解析

1、2014 年全國碩士研究生入學(xué)統(tǒng)一考試計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題：第 140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中， 只有一個選項最符合試題要求。1下列程序段的時間復(fù)雜度是 。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j+)count+;AO(log2n)BO(n)CO(nlog2n)DO(n2)2假設(shè)棧初始為空，將中綴表達(dá)式 a/b+(c*d-e*f)/g 轉(zhuǎn)換為等價的后綴表達(dá)式的過程中，當(dāng)掃描到 f 時，棧中的元素依次是 。A+ ( * -B+ ( - *C/ + ( * - *D

2、/ + - *3循環(huán)隊列放在一維數(shù)組 A0M-1中，end1 指向隊頭元素，end2 指向隊尾元素的后 一個位置。假設(shè)隊列兩端均可進(jìn)行入隊和出隊操作，隊列中最多能容納 M-1 個元素。初始時為空。下列判斷隊空和隊滿的條件中，正確的是 。A隊空：end1 = end2；隊滿：end1 = (end2+1)mod M B隊空：end1 = end2；隊滿：end2 = (end1+1)mod (M-1) C隊空：end2 = (end1+1)mod M； 隊滿：end1 = (end2+1)mod MD隊空：end1 = (end2+1)mod M；隊滿：end2 = (end1+1)mod (M

3、-1)4若對如下的二叉樹進(jìn)行中序線索化，則結(jié)點 x 的左、右線索指向的結(jié)點分別是 。ab cd xeAe、cBe、aCd、cDb、a5將森林 F 轉(zhuǎn)換為對應(yīng)的二叉樹 T，F(xiàn) 中葉結(jié)點的個數(shù)等于 。AT 中葉結(jié)點的個數(shù)BT 中度為 1 的結(jié)點個數(shù)CT 中左孩子指針為空的結(jié)點個數(shù)DT 中右孩子指針為空的結(jié)點個數(shù)65 個字符有如下 4 種編碼方案，不是前綴編碼的是 。A01,0000,0001,001,1B011,000,001,010,1C000,001,010,011,100D0,100,110,1110,11007對如下所示的有向圖進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁?。A3,1,2,4,5,6

4、B3,1,2,4,6,5C3,1,4,2,5,6D3,1,4,2,6,58用哈希（散列）方法處理沖突（碰撞）時可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項中， 會受堆積現(xiàn)象直接影響的是 。A存儲效率B散列函數(shù)C裝填(裝載)因子D平均查找長度9在一棵具有 15 個關(guān)鍵字的 4 階 B 樹中，含關(guān)鍵字的結(jié)點個數(shù)最多是 。A5B6C10D1510 用 希 爾 排 序 方 法 對 一 個 數(shù)據(jù)序列進(jìn)行排序時 ，若 第 1 趟 排 序 結(jié) 果 為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是 。A2B3C4D511下列選項中，不可能是快速排序第 2 趟排序結(jié)果的是 。A2,3,5,

5、4,6,7,9B2,7,5,6,4,3,9C3,2,5,4,7,6,9D4,2,3,5,7,6,912程序 P 在機(jī)器 M 上的執(zhí)行時間是 20 秒，編譯優(yōu)化后，P 執(zhí)行的指令數(shù)減少到原來 的 70%，而 CPI 增加到原來的 1.2 倍，則 P 在 M 上的執(zhí)行時間是 。A8.4 秒B11.7 秒C14 秒D16.8 秒13若 x=103，y=-25，則下列表達(dá)式采用 8 位定點補碼運算實現(xiàn)時，會發(fā)生溢出的 是 。Ax+yB-x+yCx-yD-x-y14float 型數(shù)據(jù)據(jù)常用 IEEE754 單精度浮點格式表示。假設(shè)兩個 float 型變量 x 和 y 分 別存放在 32 位寄存器 f1

6、和 f2 中，若(f1)=CC90 0000H，(f2)=B0C0 0000H，則 x 和 y 之間的 關(guān)系為 。Ax<y 且符號相同Bx<y 且符號不同Cx>y 且符號相同Dx>y 且符號不同15某容量為 256MB 的存儲器由若干 4M×8 位的 DRAM 芯片構(gòu)成，該 DRAM 芯片的 地址引腳和數(shù)據(jù)引腳總數(shù)是 。A19B22C30D3616采用指令 Cache 與數(shù)據(jù) Cache 分離的主要目的是 。 A降低 Cache 的缺失損失B提高 Cache 的命中率 C降低 CPU 平均訪存時間D減少指令流水線資源沖突17某計算機(jī)有 16 個通用寄存器，采用

7、 32 位定長指令字，操作碼字段（含尋址方式位） 為 8 位，Store 指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址方式。若 基址寄存器可使用任一通用寄存器，且偏移量用補碼表示，則 Store 指令中偏移量的取值范 圍是 。A-32768 +32767B-32767 +32768C-65536 +65535D-65535 +6553618某計算機(jī)采用微程序控制器，共有 32 條指令，公共的取指令微程序包含 2 條微指 令，各指令對應(yīng)的微程序平均由 4 條微指令組成，采用斷定法（下地址字段法）確定下條微指令地址，則微指令中下址字段的位數(shù)至少是。A5B6C8D919某同步總線采用數(shù)

8、據(jù)線和地址線復(fù)用方式，其中地址/數(shù)據(jù)線有 32 根，總線時鐘頻率為 66MHz，每個時鐘周期傳送兩次數(shù)據(jù)(上升沿和下降沿各傳送一次數(shù)據(jù))，該總線的最大 數(shù)據(jù)傳輸率(總線帶寬)是 。A132 MB/sB264 MB/sC528 MB/sD1056 MB/s20一次總線事務(wù)中，主設(shè)備只需給出一個首地址，從設(shè)備就能從首地址開始的若干連 續(xù)單元讀出或?qū)懭攵鄠€數(shù)據(jù)。這種總線事務(wù)方式稱為 。A并行傳輸B串行傳輸C突發(fā)傳輸D同步傳輸21下列有關(guān) I/O 接口的敘述中，錯誤的是 。A狀態(tài)端口和控制端口可以合用同一個寄存器 BI/O 接口中 CPU 可訪問的寄存器稱為 I/O 端口 C采用獨立編址方式時，I/O

9、 端口地址和主存地址可能相同 D采用統(tǒng)一編址方式時，CPU 不能用訪存指令訪問 I/O 端口22若某設(shè)備中斷請求的響應(yīng)和處理時間為 100ns，每 400ns 發(fā)出一次中斷請求，中斷 響應(yīng)所允許的最長延遲時間為 50ns，則在該設(shè)備持續(xù)工作過程中，CPU 用于該設(shè)備的 I/O 時間占整個 CPU 時間的百分比至少是 。A12.5%B25%C37.5%D50%23下列調(diào)度算法中，不可能導(dǎo)致饑餓現(xiàn)象的是 。 A時間片輪轉(zhuǎn)B靜態(tài)優(yōu)先數(shù)調(diào)度 C非搶占式短作業(yè)優(yōu)先D搶占式短作業(yè)優(yōu)先24某系統(tǒng)有 n 臺互斥使用的同類設(shè)備，三個并發(fā)進(jìn)程分別需要 3、4、5 臺設(shè)備，可確保系統(tǒng)不發(fā)生死鎖的設(shè)備數(shù) n 最小為

10、。A9B10C11D1225下列指令中，不能在用戶態(tài)執(zhí)行的是 。Atrap 指令B跳轉(zhuǎn)指令C壓棧指令D關(guān)中斷指令26一個進(jìn)程的讀磁盤操作完成后，操作系統(tǒng)針對該進(jìn)程必做的是 。 A修改進(jìn)程狀態(tài)為就緒態(tài)B降低進(jìn)程優(yōu)先級 C給進(jìn)程分配用戶內(nèi)存空間D增加進(jìn)程時間片大小27現(xiàn)有一個容量為 10GB 的磁盤分區(qū)，磁盤空間以簇(Cluster)為單位進(jìn)行分配，簇的 大小為 4KB，若采用位圖法管理該分區(qū)的空閑空間，即用一位(bit)標(biāo)識一個簇是否被分配，則存放該位圖所需簇的個數(shù)為 。A80B320C80KD320K28下列措施中，能加快虛實地址轉(zhuǎn)換的是 。I增大快表(TLB)容量II讓頁表常駐內(nèi)存III增大

11、交換區(qū)(swap)A僅 IB僅 IIC僅 I、IID僅 II、III29在一個文件被用戶進(jìn)程首次打開的過程中，操作系統(tǒng)需做的是 。A將文件內(nèi)容讀到內(nèi)存中 B將文件控制塊讀到內(nèi)存中 C修改文件控制塊中的讀寫權(quán)限 D將文件的數(shù)據(jù)緩沖區(qū)首指針返回給用戶進(jìn)程30在頁式虛擬存儲管理系統(tǒng)中，采用某些頁面置換算法，會出現(xiàn) Belady 異?，F(xiàn)象， 即進(jìn)程的缺頁次數(shù)會隨著分配給該進(jìn)程的頁框個數(shù)的增加而增加。下列算法中，可能出現(xiàn) Belady 異常現(xiàn)象的是 。ILRU 算法IIFIFO 算法IIIOPT 算法A僅 IIB僅 I、IIC僅 I、IIID僅 II、III31下列關(guān)于管道(Pipe)通信的敘述中，正確

12、的是 。A一個管道可實現(xiàn)雙向數(shù)據(jù)傳輸 B管道的容量僅受磁盤容量大小限制 C進(jìn)程對管道進(jìn)行讀操作和寫操作都可能被阻塞 D一個管道只能有一個讀進(jìn)程或一個寫進(jìn)程對其操作32下列選項中，屬于多級頁表優(yōu)點的是 。 A加快地址變換速度B減少缺頁中斷次數(shù) C減少頁表項所占字節(jié)數(shù)D減少頁表所占的連續(xù)內(nèi)存空間33在 OSI 參考模型中，直接為會話層提供服務(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 個 數(shù) 據(jù) 幀 ， 主 機(jī) 00-e1-d5-00-23-c1 收 到 該 幀

13、后 ， 向 主 機(jī)00-e1-d5-00-23-a1 發(fā)送 1 個確認(rèn)幀，交換機(jī)對這兩個幀的轉(zhuǎn)發(fā)端口分別是（）。A3和1B2,3和1C2,3和1,2D1,2,3和135下列因素中，不會影響信道數(shù)據(jù)傳輸速率的是 。A信噪比B頻率寬帶C調(diào)制速率D信號傳播速度36主機(jī)甲與主機(jī)乙之間使用后退 N 幀協(xié)議(GBN)傳輸數(shù)據(jù)，甲的發(fā)送窗口尺寸為 1000， 數(shù)據(jù)幀長為 1000 字節(jié)，信道帶寬為 100Mbps，乙每收到一個數(shù)據(jù)幀立即利用一個短幀(忽略 其傳輸延遲)進(jìn)行確認(rèn)，若甲乙之間的單向傳播延遲是 50ms，則甲可以達(dá)到的最大平均數(shù)據(jù) 傳輸速率約為 。A10MbpsB20MbpsC80MbpsD100

14、Mbps37站點 A、B、C 通過 CDMA 共享鏈路，A、B、C 的碼片序列(chipping sequence)分 別是(1,1,1,1)、(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ù)是 。A000B101C110D11138主機(jī)甲和主機(jī)乙已建立了 TCP 連接，甲始終以 MSS=1KB 大小的段發(fā)送數(shù)據(jù)，并 一直有數(shù)據(jù)發(fā)送；乙每收到一個數(shù)據(jù)段都會發(fā)出一個接收窗口為 10KB 的確認(rèn)段。若甲在 t 時刻發(fā)生超時時擁塞窗口為 8KB，則從 t 時刻起，不再發(fā)生超時的情況下，經(jīng)過

15、 10 個 RTT 后，甲的發(fā)送窗口是 。A10KBB12KBC14KBD15KB39下列關(guān)于 UDP 協(xié)議的敘述中，正確的是 。I提供無連接服務(wù) II提供復(fù)用/分用服務(wù) III通過差錯校驗，保障可靠數(shù)據(jù)傳輸A僅 IB僅 I、IIC僅 II、IIIDI、II、III40使用瀏覽器訪問某大學(xué) Web 網(wǎng)站主頁時，不可能使用到的協(xié)議是 。APPPBARPCUDPDSMTP二、綜合應(yīng)用題：4147 小題，共 70 分。41.(13 分)二叉樹的帶權(quán)路徑長度(WPL)是二叉樹中所有葉結(jié)點的帶權(quán)路徑長度之和。給 定一棵二叉樹 T，采用二叉鏈表存儲，結(jié)點結(jié)構(gòu)為：leftweightright其中葉結(jié)點的

16、weight 域保存該結(jié)點的非負(fù)權(quán)值。設(shè) root 為指向 T 的根結(jié)點的指針，請設(shè)計求 T 的 WPL 的算法，要求：1）給出算法的基本設(shè)計思想；2）使用 C 或 C+語言，給出二叉樹結(jié)點的數(shù)據(jù)類型定義；3）根據(jù)設(shè)計思想，采用 C 或 C+語言描述算法，關(guān)鍵之處給出注釋。42. (10 分)某網(wǎng)絡(luò)中的路由器運行 OSPF 路由協(xié)議，題 42 表是路由器 R1 維護(hù)的主要鏈 路狀態(tài)信息(LSI)，題 42 圖是根據(jù)題 42 表及 R1 的接口名構(gòu)造出來的網(wǎng)絡(luò)拓?fù)洹ｎ} 42 表 R1 所維護(hù)的 LSIR1 的 LSIR2 的 LSIR3 的 LSIR4 的 LSI備 注Router ID10.1

17、.1.110.1.1.210.1.1.510.1.1.6標(biāo)識路由器的 IP 地址Link1ID10.1.1.210.1.1.110.1.1.610.1.1.5所連路由器的 Router IDIP10.1.1.110.1.1.210.1.1.510.1.1.6Link1 的本地 IP 地址Metric3366Link1 的費用Link2ID10.1.1.510.1.1.610.1.1.110.1.1.2所連路由器的 Router IDIP10.1.1.910.1.1.1310.1.1.1010.1.1.14Link2 的本地 IP 地址Metric2424Link2 的費用Net1Prefix1

18、92.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 的費用請回答下列問題。題 42 圖 R1 構(gòu)造的網(wǎng)絡(luò)拓?fù)?）本題中的網(wǎng)絡(luò)可抽象為數(shù)據(jù)結(jié)構(gòu)中的哪種邏輯結(jié)構(gòu)？2）針對題 42 表中的內(nèi)容，設(shè)計合理的鏈?zhǔn)酱鎯Y(jié)構(gòu)，以保存題 42 表中的鏈路狀態(tài)信 息(LSI)。要求給出鏈?zhǔn)酱鎯Y(jié)構(gòu)的數(shù)據(jù)類型定義，并畫出對應(yīng)題 42 表的鏈?zhǔn)酱鎯Y(jié)構(gòu)示意 圖(示意圖中可僅以 ID 標(biāo)識結(jié)點)。3）按照迪杰斯特拉(Dijikstra)算法的策略，依次給出 R1 到達(dá)題 42 圖中子網(wǎng) 1.x的最短路徑

19、及費用。43（9 分）請根據(jù)題 42 描述的網(wǎng)絡(luò)，繼續(xù)回答下列問題。1）假設(shè)路由表結(jié)構(gòu)如下表所示，請給出題 42 圖中 R1 的路由表，要求包括到達(dá)題 42圖中子網(wǎng) 192.1.x.x 的路由，且路由表中的路由項盡可能少。目的網(wǎng)絡(luò)下一條接口2）當(dāng)主機(jī) 192.1.1.130 向主機(jī) 192.1.7.211 發(fā)送一個 TTL=64 的 IP 分組時，R1 通過哪個接口轉(zhuǎn)發(fā)該 IP 分組？主機(jī) 192.1.7.211 收到的 IP 分組 TTL 是多少？3）若 R1 增加一條 Metric 為 10 的鏈路連接 Internet，則題 42 表中 R1 的 LSI 需要增加 哪些信息？44. （1

20、2 分）某程序中有如下循環(huán)代碼段 p：:”for(int i = 0; i < N; i+) sum+=Ai;”。假 設(shè)編譯時變量 sum 和 i 分別分配在寄存器 R1 和 R2 中。常量 N 在寄存器 R6 中，數(shù)組 A 的 首地址在寄存器 R3 中。程序段 P 起始地址為 0804 8100H，對應(yīng)的匯編代碼和機(jī)器代碼如下 表所示。編號地址機(jī)器代碼匯編代碼注釋108048100H00022080Hloop: sll R4,R2,2(R2)<<2 ® R4208048104H00083020Hadd R4,R4,R3(R4)+(R3) ® R43080

21、48108H8C850000Hload R5,0(R4)(R4)+0) ® R540804810CH00250820Hadd R1,R1,R5(R1)+(R5) ® R1508048110H20420001Hadd R2,R2,1(R2)+1 ® R2608048114H1446FFFAHbne R2,R6,loopif(R2)!=(R6) goto loop執(zhí)行上述代碼的計算機(jī) M 采用 32 位定長指令字，其中分支指令 bne 采用如下格式：3126 2521 2016 150OPRsRdOFFSETOP 為操作碼;；Rs 和 Rd 為寄存器編號；OFFSET

22、 為偏移量，用補碼表示。請回答下列問題，并說明理由。1）M 的存儲器編址單位是什么？2）已知 sll 指令實現(xiàn)左移功能，數(shù)組 A 中每個元素占多少位？3）題 44 表中 bne 指令的 OFFSET 字段的值是多少？已知 bne 指令采用相對尋址方式， 當(dāng)前 PC 內(nèi)容為 bne 指令地址，通過分析題 44 表中指令地址和 bne 指令內(nèi)容，推斷出 bne 指令的轉(zhuǎn)移目標(biāo)地址計算公式。4）若 M 采用如下“按序發(fā)射、按序完成”的 5 級指令流水線：IF（取值）、ID（譯碼 及取數(shù)）、EXE（執(zhí)行）、MEM（訪存）、WB（寫回寄存器），且硬件不采取任何轉(zhuǎn)發(fā)措施，分支指令的執(zhí)行均引起 3 個時鐘周

23、期的阻塞，則 P 中哪些指令的執(zhí)行會由于數(shù)據(jù)相關(guān)而發(fā) 生流水線阻塞？哪條指令的執(zhí)行會發(fā)生控制冒險？為什么指令 1 的執(zhí)行不會因為與指令 5 的數(shù)據(jù)相關(guān)而發(fā)生阻塞？45假設(shè)對于 44 題中的計算機(jī) M 和程序 P 的機(jī)器代碼，M 采用頁式虛擬存儲管理；P 開始執(zhí)行時，(R1)=(R2)=0，(R6)=1000，其機(jī)器代碼已調(diào)入主存但不在 Cache 中；數(shù)組 A 未 調(diào)入主存，且所有數(shù)組元素在同一頁，并存儲在磁盤同一個扇區(qū)。請回答下列問題并說明理 由。1）P 執(zhí)行結(jié)束時，R2 的內(nèi)容是多少？2）M 的指令 Cache 和數(shù)據(jù) Cache 分離。若指令 Cache 共有 16 行，Cache 和主

24、存交換的 塊大小為 32 字節(jié)，則其數(shù)據(jù)區(qū)的容量是多少？若僅考慮程序段 P 的執(zhí)行，則指令 Cache 的 命中率為多少？3）P 在執(zhí)行過程中，哪條指令的執(zhí)行可能發(fā)生溢出異常？哪條指令的執(zhí)行可能產(chǎn)生缺 頁異常？對于數(shù)組 A 的訪問，需要讀磁盤和 TLB 至少各多少次？46. 文件 F 由 200 條記錄組成，記錄從 1 開始編號。用戶打開文件后，欲將內(nèi)存中的一條記錄插入到文件 F 中，作為其第 30 條記錄。請回答下列問題，并說明理由。1）若文件系統(tǒng)采用連續(xù)分配方式，每個磁盤塊存放一條記錄，文件 F 存儲區(qū)域前后均 有足夠的空閑磁盤空間，則完成上述插入操作最少需要訪問多少次磁盤塊？F 的文件控

25、制塊 內(nèi)容會發(fā)生哪些改變？2）若文件系統(tǒng)采用鏈接分配方式，每個磁盤塊存放一條記錄和一個鏈接指針，則完成 上述插入操作需要訪問多少次磁盤塊？若每個存儲塊大小為 1KB，其中 4 個字節(jié)存放鏈接 指針，則該文件系統(tǒng)支持的文件最大長度是多少？47. 系統(tǒng)中有多個生產(chǎn)者進(jìn)程和多個消費者進(jìn)程，共享一個能存放 1000 件產(chǎn)品的環(huán)形 緩沖區(qū)（初始為空）。當(dāng)緩沖區(qū)未滿時，生產(chǎn)者進(jìn)程可以放入其生產(chǎn)的一件產(chǎn)品，否則等待； 當(dāng)緩沖區(qū)未空時，消費者進(jìn)程可以從緩沖區(qū)取走一件產(chǎn)品，否則等待。要求一個消費者進(jìn)程從緩沖區(qū)連續(xù)取出 10 件產(chǎn)品后，其他消費者進(jìn)程才可以取產(chǎn)品。請使用信號量 P，V(wait()， signal

26、()操作實現(xiàn)進(jìn)程間的互斥與同步，要求寫出完整的過程，并說明所用信號量的含義和 初值。2014 年計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案一、單項選擇題（一）單選題答案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（二）單選題答案解析1內(nèi)層循環(huán)條件 j<=n 與外層循環(huán)的變量無關(guān)，每次循環(huán) j 自增 1，每次內(nèi)層循環(huán)都執(zhí) 行 n 次。外層循環(huán)條

27、件為 k<=n，增量定義為 k*=2，可知循環(huán)次數(shù)為 2k<=n，即 k<=log2n。 所以內(nèi)層循環(huán)的時間復(fù)雜度是 O(n)，外層循環(huán)的時間復(fù)雜度是 O(log2n)。對于嵌套循環(huán)，根 據(jù)乘法規(guī)則可知，該段程序的時間復(fù)雜度 T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。2將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法思想如下： 從左向右開始掃描中綴表達(dá)式； 遇到數(shù)字時，加入后綴表達(dá)式；遇到運算符時：a. 若為 '('，入棧；b. 若為 ')'，則依次把棧中的的運算符加入后綴表達(dá)式中，直到出現(xiàn)'('，從棧

28、中刪除'(' ；c. 若為除括號外的其他運算符， 當(dāng)其優(yōu)先級高于除'('以外的棧頂運算符時，直接入棧。 否則從棧頂開始，依次彈出比當(dāng)前處理的運算符優(yōu)先級高和優(yōu)先級相等的運算符，直到一個 比它優(yōu)先級低的或者遇到了一個左括號為止。當(dāng)掃描的中綴表達(dá)式結(jié)束時，棧中的所有運算符依次出棧加入后綴表達(dá)式。待處理序列棧后綴表達(dá)式當(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)先級低于棧頂?shù)?，彈出/+(c*d-e*f)/gab/+入棧(c*d

29、-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)先級低于棧頂?shù)?，彈出*-e*f)/g+(ab/cd*-棧頂為(，-入棧e*f)/g+(-ab/cd*ee 加入后綴表達(dá)式*f)/g+(-ab/cd*e*優(yōu)先級高于棧頂?shù)?，*入棧f)/g+(-*ab/cd*eff 加入后綴表達(dá)式)/g+(-*ab/cd*ef)把棧中(之前的符號加入表達(dá)式/g+ab/cd*ef*-/優(yōu)先級高于棧頂?shù)?，/入棧g+/ab/cd*ef*-gg 加入后綴表達(dá)

30、式+/ab/cd*ef*-g掃描完畢，運算符依次退棧加入表達(dá)式ab/cd*ef*-g/+完成由此可知，當(dāng)掃描到 f 的時候，棧中的元素依次是+(-*，選 B。在此，再給出中綴表達(dá)式轉(zhuǎn)換為前綴或后綴表達(dá)式的一種手工做法，以上面給出的中綴 表達(dá)式為例：第一步：按照運算符的優(yōu)先級對所有的運算單位加括號。 式子變成了：(a/b)+(c*d)-(e*f)/g) 第二步：轉(zhuǎn)換為前綴或后綴表達(dá)式。前綴：把運算符號移動到對應(yīng)的括號前面，則變成了：+(/(ab)/(-(*(cd)*(ef)g) 把括號去掉：+/ab/-*cd*efg 前綴式子出現(xiàn)。 后綴：把運算符號移動到對應(yīng)的括號后面，則變成了：(ab)/(c

31、d)*(ef)*)-g)/)+ 把括號去掉：ab/cd*ef*-g/+ 后綴式子出現(xiàn)。 當(dāng)題目要求直接求前綴或后綴表達(dá)式時，這種方法會比上一種快捷得多。3end1 指向隊頭元素，那么可知出隊的操作是先從 Aend1讀數(shù)，然后 end1 再加 1。end2 指向隊尾元素的后一個位置，那么可知入隊操作是先存數(shù)到 Aend2，然后 end2 再加1。若把 A0儲存第一個元素，當(dāng)隊列初始時，入隊操作是先把數(shù)據(jù)放到 A0，然后 end2自增，即可知 end2 初值為 0；而 end1 指向的是隊頭元素，隊頭元素的在數(shù)組 A 中的下標(biāo)為0，所以得知 end1 初值也為 0，可知隊空條件為 end1=end

32、2；然后考慮隊列滿時，因為隊列 最多能容納 M-1 個元素，假設(shè)隊列存儲在下標(biāo)為 0 到下標(biāo)為 M-2 的 M-1 個區(qū)域，隊頭為 A0，隊尾為 AM-2，此時隊列滿，考慮在這種情況下 end1 和 end2 的狀態(tài)，end1 指向隊 頭元素，可知 end1=0，end2 指向隊尾元素的后一個位置，可知 end2=M-2+1=M-1，所以可 知隊滿的條件為 end1=(end2+1)mod M，選 A。注意：考慮這類具體問題時，用一些特殊情況判斷往往比直接思考問題能更快的得到答 案，并可以畫出簡單的草圖以方便解題。4線索二叉樹的線索實際上指向的是相應(yīng)遍歷序列特定結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點， 所以

33、先寫出二叉樹的中序遍歷序列：edbxac，中序遍歷中在 x 左邊和右邊的字符，就是它在 中序線索化的左、右線索，即 b、a，選 D。5將森林轉(zhuǎn)化為二叉樹即相當(dāng)于用孩子兄弟表示法表示森林。在變化過程中，原森林 某結(jié)點的第一個孩子結(jié)點作為它的左子樹，它的兄弟作為它的右子樹。那么森林中的葉結(jié)點 由于沒有孩子結(jié)點，那么轉(zhuǎn)化為二叉樹時，該結(jié)點就沒有左結(jié)點，所以 F 中葉結(jié)點的個數(shù)就等于 T 中左孩子指針為空的結(jié)點個數(shù)，選 C。此題還可以通過一些特例來排除 A、B、D 選項。6前綴編碼的定義是在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的 前綴。D 中編碼 110 是編碼 1100 的前綴，違反

34、了前綴編碼的規(guī)則，所以 D 不是前綴編碼。7按照拓?fù)渑判虻乃惴?，每次都選擇入度為 0 的結(jié)點從圖中刪去，此圖中一開始只有 結(jié)點 3 的入度為 0；刪掉 3 結(jié)點后，只有結(jié)點 1 的入度為 0；刪掉結(jié)點 1 后，只有結(jié)點 4 的 入度為 0；刪掉 4 結(jié)點后，結(jié)點 2 和結(jié)點 6 的入度都為 0，此時選擇刪去不同的結(jié)點，會得 出不同的拓?fù)湫蛄?，分別處理完畢后可知可能的拓?fù)湫蛄袨?314265 和 314625，選 D。8產(chǎn)生堆積現(xiàn)象，即產(chǎn)生了沖突，它對存儲效率、散列函數(shù)和裝填因子均不會有影響， 而平均查找長度會因為堆積現(xiàn)象而增大，選 D。9關(guān)鍵字?jǐn)?shù)量不變，要求結(jié)點數(shù)量最多，那么即每個結(jié)點中含關(guān)鍵

35、字的數(shù)量最少。根據(jù) 4 階 B 樹的定義，根結(jié)點最少含 1 個關(guān)鍵字，非根結(jié)點中最少含é4/2ù-1=1 個關(guān)鍵字，所 以每個結(jié)點中，關(guān)鍵字?jǐn)?shù)量最少都為 1 個，即每個結(jié)點都有 2 個分支，類似與排序二叉樹， 而 15 個結(jié)點正好可以構(gòu)造一個 4 層的 4 階 B 樹，使得葉子結(jié)點全在第四層，符合 B 樹定義， 因此選 D。10首先，第二個元素為 1，是整個序列中的最小元素，所以可知該希爾排序為從小到 大排序。然后考慮增量問題，若增量為 2，第 1+2 個元素 4 明顯比第 1 個元素 9 要大，A 排 除；若增量為 3，第 i、i+3、i+6 個元素都為有序序列(i=1,

36、2,3)，符合希爾排序的定義；若增 量為 4，第 1 個元素 9 比第 1+4 個元素 7 要大，C 排除；若增量為 5，第 1 個元素 9 比第 1+5 個元素 8 要大，D 排除，選 B。11快排的階段性排序結(jié)果的特點是，第 i 趟完成時，會有 i 個以上的數(shù)出現(xiàn)在它最終將要出現(xiàn)的位置，即它左邊的數(shù)都比它小，它右邊的數(shù)都比它大。題目問第二趟排序的結(jié)果， 即要找不存在 2 個這樣的數(shù)的選項。A 選項中 2、3、6、7、9 均符合，所以 A 排除；B 選 項中，2、9 均符合，所以 B 排除；D 選項中 5、9 均符合，所以 D 選項排除；最后看 C 選 項，只有 9 一個數(shù)符合，所以 C 不

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

38、項 x-y=103+25=128，超過了 127，選 C。該題也可按照二進(jìn)制寫出兩個數(shù)進(jìn)行運算觀察運算的進(jìn)位信息得到結(jié)果，不過這種方法 更為麻煩和耗時，在實際考試中并不推薦。此題還有更為簡便的算法，(f1)與(f2)的前 4 位為 1100 與 1011,可以看出兩數(shù)均為負(fù)數(shù)， 而階碼用移碼表示，兩數(shù)的階碼頭三位分別為 100 和 011，可知(f1)的階碼大于(f2)的階碼， 又因為是 IEEE754 規(guī)格化的數(shù)，尾數(shù)部分均為 1.xxx，則階碼大的數(shù)，真值的絕對值必然大， 可知(f1)真值的絕對值大于(f2)真值的絕對值，因為都為負(fù)數(shù)，則(f1)<(f2)，即 x<y。154M

39、×8 位的芯片數(shù)據(jù)線應(yīng)為 8 根，地址線應(yīng)為 log24M=22 根，而 DRAM 采用地址 復(fù)用技術(shù)，地址線是原來的 1/2，且地址信號分行、列兩次傳送。地址線數(shù)為 22/2=11 根，所以地址引腳與數(shù)據(jù)引腳的總數(shù)為 11+8=19 根，選 A。此題需要注意的是 DRAM 是采用傳兩次地址的策略的，所以地址線為正常的一半，這 是很多考生容易忽略的地方。16把指令 Cache 與數(shù)據(jù) Cache 分離后，取指和取數(shù)分別到不同的 Cache 中尋找，那么 指令流水線中取指部分和取數(shù)部分就可以很好的避免沖突，即減少了指令流水線的沖突。17采用 32 位定長指令字，其中操作碼為 8 位，兩

40、個地址碼一共占用 32-8=24 位，而 Store 指令的源操作數(shù)和目的操作數(shù)分別采用寄存器直接尋址和基址尋址，機(jī)器中共有 16 個 通用寄存器，則尋址一個寄存器需要 log216=4 位，源操作數(shù)中的寄存器直接尋址用掉 4 位， 而目的操作數(shù)采用基址尋址也要指定一個寄存器，同樣用掉 4 位，則留給偏移址的位數(shù)為24-4-4=16 位，而偏移址用補碼表示，16 位補碼的表示范圍為-32768+32767，選 A。18計算機(jī)共有 32 條指令，各個指令對應(yīng)的微程序平均為 4 條，則指令對應(yīng)的微指令 為 32*4=128 條，而公共微指令還有 2 條，整個系統(tǒng)中微指令的條數(shù)一共為 128+2=1

41、30 條，所以需要élog2130ù=8 位才能尋址到 130 條微指令，答案選 C。19數(shù)據(jù)線有 32 根也就是一次可以傳送 32bit/8=4B 的數(shù)據(jù)，66MHz 意味著有 66M 個 時 鐘 周 期 ， 而 每 個 時 鐘 周 期 傳 送 兩 次 數(shù) 據(jù) ， 可 知 總 線 每 秒 傳 送 的 最 大 數(shù) 據(jù) 量 為66M×2×4B=528MB，所以總線的最大數(shù)據(jù)傳輸率為 528MB/s，選 C。20猝發(fā)(突發(fā))傳輸是在一個總線周期中，可以傳輸多個存儲地址連續(xù)的數(shù)據(jù)，即一次 傳輸一個地址和一批地址連續(xù)的數(shù)據(jù)，并行傳輸是在傳輸中有多個數(shù)據(jù)位同時在設(shè)

42、備之間進(jìn) 行的傳輸，串行傳輸是指數(shù)據(jù)的二進(jìn)制代碼在一條物理信道上以位為單位按時間順序逐位傳 輸?shù)姆绞?，同步傳輸是指傳輸過程由統(tǒng)一的時鐘控制，選 C。21采用統(tǒng)一編址時，CPU 訪存和訪問 I/O 端口用的是一樣的指令，所以訪存指令可以訪問 I/O 端口，D 選項錯誤，其他三個選項均為正確陳述，選 D。22每 400ns 發(fā)出一次中斷請求，而響應(yīng)和處理時間為 100ns，其中容許的延遲為干擾 信息，因為在 50ns 內(nèi)，無論怎么延遲，每 400ns 還是要花費 100ns 處理中斷的，所以該設(shè) 備的 I/O 時間占整個 CPU 時間的百分比為 100ns/400ns=25%，選 B。23采用靜態(tài)

43、優(yōu)先級調(diào)度時，當(dāng)系統(tǒng)總是出現(xiàn)優(yōu)先級高的任務(wù)時，優(yōu)先級低的任務(wù)會總 是得不到處理機(jī)而產(chǎn)生饑餓現(xiàn)象；而短作業(yè)優(yōu)先調(diào)度不管是搶占式或是非搶占的，當(dāng)系統(tǒng)總 是出現(xiàn)新來的短任務(wù)時，長任務(wù)會總是得不到處理機(jī)，產(chǎn)生饑餓現(xiàn)象，因此 B、C、D 都錯 誤，選 A。24三個并發(fā)進(jìn)程分別需要 3、4、5 臺設(shè)備，當(dāng)系統(tǒng)只有(3-1)+(4-1)+(5-1)=9 臺設(shè)備時， 第一個進(jìn)程分配 2 臺，第二個進(jìn)程分配 3 臺，第三個進(jìn)程分配 4 臺。這種情況下，三個進(jìn)程均無法繼續(xù)執(zhí)行下去，發(fā)生死鎖。當(dāng)系統(tǒng)中再增加 1 臺設(shè)備，也就是總共 10 臺設(shè)備時，這 最后 1 臺設(shè)備分配給任意一個進(jìn)程都可以順利執(zhí)行完成，因此保證系

44、統(tǒng)不發(fā)生死鎖的最小設(shè) 備數(shù)為 10。25trap 指令、跳轉(zhuǎn)指令和壓棧指令均可以在用戶態(tài)執(zhí)行，其中 trap 指令負(fù)責(zé)由用戶態(tài) 轉(zhuǎn)換成為內(nèi)核態(tài)。而關(guān)中斷指令為特權(quán)指令，必須在核心態(tài)才能執(zhí)行，選 D。26進(jìn)程申請讀磁盤操作的時候，因為要等待 I/O 操作完成，會把自身阻塞，此時進(jìn)程 就變?yōu)榱俗枞麪顟B(tài)，當(dāng) I/O 操作完成后，進(jìn)程得到了想要的資源，就會從阻塞態(tài)轉(zhuǎn)換到就緒 態(tài)（這是操作系統(tǒng)的行為）。而降低進(jìn)程優(yōu)先級、分配用戶內(nèi)存空間和增加進(jìn)程的時間片大 小都不一定會發(fā)生，選 A。27簇的總數(shù)為 10GB/4KB=2.5M，用一位標(biāo)識一簇是否被分配，則整個磁盤共需要 2.5M位，即需要 2.5M/8=

45、320KB，則共需要 320KB/4KB=80 個簇，選 A。28虛實地址轉(zhuǎn)換是指邏輯地址和物理地址的轉(zhuǎn)換。增大快表容量能把更多的表項裝入 快表中，會加快虛實地址轉(zhuǎn)換的平均速率；讓頁表常駐內(nèi)存可以省去一些不在內(nèi)存中的頁表從磁盤上調(diào)入的過程，也能加快虛實地址變換；增大交換區(qū)對虛實地址變換速度無影響，因此 I、II 正確，選 C。29一個文件被用戶進(jìn)程首次打開即被執(zhí)行了 Open 操作，會把文件的 FCB 調(diào)入內(nèi)存， 而不會把文件內(nèi)容讀到內(nèi)存中，只有進(jìn)程希望獲取文件內(nèi)容的時候才會讀入文件內(nèi)容；C、 D 明顯錯誤，選 B。30只有 FIFO 算法會導(dǎo)致 Belady 異常，選 A。31管道實際上是一

46、種固定大小的緩沖區(qū)，管道對于管道兩端的進(jìn)程而言，就是一個文 件，但它不是普通的文件，它不屬于某種文件系統(tǒng)，而是自立門戶，單獨構(gòu)成一種文件系統(tǒng)， 并且只存在于內(nèi)存中。它類似于通信中半雙工信道的進(jìn)程通信機(jī)制，一個管道可以實現(xiàn)雙向 的數(shù)據(jù)傳輸，而同一個時刻只能最多有一個方向的傳輸，不能兩個方向同時進(jìn)行。管道的容 量大小通常為內(nèi)存上的一頁，它的大小并不是受磁盤容量大小的限制。當(dāng)管道滿時，進(jìn)程在寫管道會被阻塞，而當(dāng)管道空時，進(jìn)程讀管道會被阻塞，因此選 C。32多級頁表不僅不會加快地址的變換速度，還因為增加更多的查表過程，會使地址變 換速度減慢；也不會減少缺頁中斷的次數(shù)，反而如果訪問過程中多級的頁表都不在

47、內(nèi)存中， 會大大增加缺頁的次數(shù)，也并不會減少頁表項所占的字節(jié)數(shù)(詳細(xì)解析參考下段)，而多級頁 表能夠減少頁表所占的連續(xù)內(nèi)存空間，即當(dāng)頁表太大時，將頁表再分級，可以把每張頁表控 制在一頁之內(nèi)，減少頁表所占的連續(xù)內(nèi)存空間，因此選 D。補充：頁式管理中每個頁表項的大小的下限如何決定？ 頁表項的作用是找到該頁在內(nèi)存的位置，以 32 位邏輯地址空間，字節(jié)為編址單位，一頁 4KB 為例，地址空間內(nèi)一共含有 232B/4KB=1M 頁，則需要 log21M=20 位才能保證表示范圍能容納所有頁面，又因為以字節(jié)作為編址單位，即頁表項的大小20/8=3B。所以在這個條件下，為了保證頁表項能夠指向所有頁面，那么頁

48、表項的大小應(yīng)該大于 3B，當(dāng)然，也可以選擇更大的頁表項大小以至于讓一個頁面能夠正好容下整數(shù)個頁表項以方便存儲（例如取 成 4B，那么一頁正好可以裝下 1K 個頁表項），或者增加一些其他信息。33直接為會話層提供服務(wù)的即會話層的下一層，是傳輸層，選 C。34主機(jī) 00-e1-d5-00-23-a1 向 00-e1-d5-00-23-c1 發(fā)送數(shù)據(jù)幀時，交換機(jī)轉(zhuǎn)發(fā)表中沒有00-e1-d5-00-23-c1 這項，所以向除 1 接口外的所有接口廣播這幀，即 2、3 端口會轉(zhuǎn)發(fā)這幀， 同 時 因 為 轉(zhuǎn) 發(fā) 表 中 并 沒 有 00-e1-d5-00-23-a1 這 項 ， 所 以 轉(zhuǎn) 發(fā) 表 會 把

49、 ( 目 的 地 址00-e1-d5-00-23-a1，端口 1)這項加入轉(zhuǎn)發(fā)表。而當(dāng) 00-e1-d5-00-23-c1 向 00-e1-d5-00-23-a1 發(fā) 送確認(rèn)幀時，由于轉(zhuǎn)發(fā)表已經(jīng)有 00-e1-d5-00-23-a1 這項，所以交換機(jī)只向 1 端口轉(zhuǎn)發(fā)，選 B。35由香農(nóng)定理可知，信噪比和頻率帶寬都可以限制信道的極限傳輸速率，所以信噪比和頻率帶寬對信道的數(shù)據(jù)傳輸速率是有影響的，A、B 錯誤；信道的傳輸速率實際上就是信 號的發(fā)送速率，而調(diào)制速度也會直接限制數(shù)據(jù)的傳輸速率，C 錯誤；信號的傳播速度是信號 在信道上傳播的速度，與信道的發(fā)送速率無關(guān)，選 D。36考慮制約甲的數(shù)據(jù)傳輸速率

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

51、 的數(shù)據(jù)，因此此時的最大傳輸速率為 1MB/0.1s=10MB/s=80Mbps。信道帶寬為 100Mbps，所以答案為 min80Mbps,100Mbps=80Mbps，選 C。37把收到的序列分成每 4 個數(shù)字一組，即為(2,0,2,0)、(0,-2,0,-2)、(0,2,0,2)，因為題目求的是 A 發(fā)送的數(shù)據(jù)，因此把這三組數(shù)據(jù)與 A 站的碼片序列(1,1,1,1)做內(nèi)積運算，結(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ā)

52、送的數(shù)據(jù)是 101，選 B。38當(dāng) t 時刻發(fā)生超時時，把 ssthresh 設(shè)為 8 的一半，即為 4，且擁塞窗口設(shè)為 1KB。 然后經(jīng)歷 10 個 RTT 后，擁塞窗口的大小依次為 2、4、5、6、7、8、9、10、11、12，而發(fā) 送窗口取當(dāng)時的擁塞窗口和接收窗口的最小值，而接收窗口始終為 10KB，所以此時的發(fā)送 窗口為 10KB，選 A。實際上該題接收窗口一直為 10KB，可知不管何時，發(fā)送窗口一定小于等于 10KB，選 項中只有 A 選項滿足條件，可直接得出選 A。39UDP 提供的是無連接的服務(wù)，I 正確；同時 UDP 也提供復(fù)用/分用服務(wù)，II 正確；UDP 雖然有差錯校驗機(jī)制

53、，但是 UDP 的差錯校驗只是檢查數(shù)據(jù)在傳輸?shù)倪^程中有沒有出錯， 出錯的數(shù)據(jù)直接丟棄，并沒有重傳等機(jī)制，不能保證可靠傳輸，使用 UDP 協(xié)議時，可靠傳輸必須由應(yīng)用層實現(xiàn)，III 錯誤；答案選 B。40當(dāng)接入網(wǎng)絡(luò)時可能會用到 PPP 協(xié)議，A 可能用到；而當(dāng)計算機(jī)不知道某主機(jī)的 MAC 地址時，用 IP 地址查詢相應(yīng)的 MAC 地址時會用到 ARP 協(xié)議，B 可能用到；而當(dāng)訪問 Web 網(wǎng)站時，若 DNS 緩沖沒有存儲相應(yīng)域名的 IP 地址，用域名查詢相應(yīng)的 IP 地址時要使用 DNS 協(xié)議，而 DNS 是基于 UDP 協(xié)議的，所以 C 可能用到，SMTP 只有使用郵件客戶端發(fā)送郵件， 或是郵件

54、服務(wù)器向別的郵件服務(wù)器發(fā)送郵件時才會用到，單純的訪問 Web 網(wǎng)頁不可能用到。二、綜合應(yīng)用題41解答： 考查二叉樹的帶權(quán)路徑長度，二叉樹的帶權(quán)路徑長度為每個葉子結(jié)點的深度與權(quán)值之積的總和，可以使用先序遍歷或?qū)哟伪闅v解決問題。1）算法的基本設(shè)計思想：基于先序遞歸遍歷的算法思想是用一個 static 變量記錄 wpl，把每個結(jié)點的深度作為 遞歸函數(shù)的一個參數(shù)傳遞，算法步驟如下：若該結(jié)點是葉子結(jié)點，那么變量 wpl 加上該結(jié)點的深度與權(quán)值之積； 若該結(jié)點非葉子結(jié)點，那么若左子樹不為空，對左子樹調(diào)用遞歸算法，若右子樹不為空，對右子樹調(diào)用遞歸算法，深度參數(shù)均為本結(jié)點的深度參數(shù)加一； 最后返回計算出的 wpl 即可?；趯哟伪闅v的算法思想是使用隊列進(jìn)行層次遍歷，并記錄當(dāng)前的層數(shù)， 當(dāng)遍歷到葉子結(jié)點時，累計 wpl；