1、是考研備考中至關重要的一環，真題是必不可少的備考資料。為大家整理了2014年計算機考研專業課真題及答案供大家下載使用，并且提供計算機，更多 真題敬請關注！2014年全國碩士研究生入學統一考試?計算機科學與技術學科聯考計算機學科專業基礎綜合試題一、單項選擇題：第140小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求。？1 下列程序段的時間復雜度是。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. 假設棧

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

3、1+1)mod?(M-1)?C. 隊空：end2?=?(end1+1)mod?M ; ?隊滿：end1?=?(end2+1)mod?M?D. 隊空：end1?=?(end2+1)mod?M ; ?隊滿：end2?=?(end1+1)mod?(M-1)?4. 若對如下的二叉樹進行中序線索化，則結點 x的左、右線索指向的結點分別是。？f A. e、c?B. e、a?C. d、c?D. b、a?5. 將森林F轉換為對應的二叉樹 T，F中葉結點的個數等于。？A. T中葉結點的個數？ B. T中度為1的結點個數？C. T中左孩子指針為空的結點個數？D. T中右孩子指針為空的結點個數?6. 5個字符有如下

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.對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是。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?&用哈希（散列）方法處理沖突（碰撞）時可能出現堆積（聚集）現象，下列選項中， 會受堆積現象直接影響的是。A.存儲效率B.散列函數C.裝填（裝載）因子D.平均查找長度9在一棵具有15個關鍵字的4

5、階B樹中，含關鍵字的結點個數最多是。A. 5 B. 6C. 10 D. 1510. 用希爾排序方法對一個數據序列進行排序時，若第1趟排序結果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是。A. 2 B. 3C. 4 D. 511. 下列選項中，不可能是快速排序第2趟排序結果的是。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在機器M上的執行時間是20秒，編譯優化后，P執行的指令數減少到原來 的70%，而CPI增加到原來的1.2倍，貝U P在M上的執行時間是。A.

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

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

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

9、， 主設備只需給出一個首地址， 從設備就能從首地址開始的若干連 續單元讀出或寫入多個數據。這種總線事務方式稱為 。A.并行傳輸B.串行傳輸C.突發傳輸D.同步傳輸21下列有關 I/O 接口的敘述中，錯誤 的是 。A. 狀態端口和控制端口可以合用同一個寄存器B. I/O 接口中 CPU 可訪問的寄存器稱為 I/O 端口C. 采用獨立編址方式時，I/O端口地址和主存地址可能相同D. 采用統一編址方式時，CPU不能用訪存指令訪問I/O端口22. 若某設備中斷請求的響應和處理時間為100ns,每400ns發出一次中斷請求，中斷響應所允許的最長延遲時間為50ns,則在該設備持續工作過程中，CPU用于該設

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

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

12、針返回給用戶進程30在頁式虛擬存儲管理系統中,采用某些頁面置換算法,會出現Belady 異常現象,即進程的缺頁次數會隨著分配給該進程的頁框個數的增加而增加。下列算法中，可能出現Belady異常現象的是。I. LRU算法 II. FIFO算法III. OPT算法A.僅 II B.僅 I、IIC.僅 I、III D.僅 II、III31. 下列關于管道(Pipe)通信的敘述中，正確.的是。A. 個管道可實現雙向數據傳輸B. 管道的容量僅受磁盤容量大小限制C. 進程對管道進行讀操作和寫操作都可能被阻塞D. 個管道只能有一個讀進程或一個寫進程對其操作32. 下列選項中，屬于多級頁表優點的是。A.加快地

13、址變換速度B.減少缺頁中斷次數C.減少頁表項所占字節數D.減少頁表所占的連續內存空間33. 在OSI參考模型中，直接為會話層提供服務的是。A.應用層B.表示層C.傳輸層 D.網絡層34 .某以太網拓撲及交換機當前轉發表如下圖所示，主機00-e1-d5-00-23-a1向主機00-e1-d5-00-23-c1發送1個數據幀，主機00-e1-d5-00-23-c1收到該 幀后，向主機00-e1-d5-00-23-a1發送1個確認幀，交換機對這兩個幀的轉發端口分別是()。目的地址口2A. 3和1 B. 2,3和1 C. 2,3和1,2D. 1,2,3和135. 下列因素中，不會影響信道數據傳輸速率的

14、是。A.信噪比B.頻率寬帶C.調制速率D.信號傳播速度36. 主機甲與主機乙之間使用后退N幀協議(GBN)傳輸數據，甲的發送窗口尺寸為1000,數據幀長為1000字節，信道帶寬為100Mbps，乙每收到一個數據幀立即利用一個短幀(忽略其傳輸延遲)進行確認，若甲乙之間的單向傳播延遲是50ms，則甲可以達到的最大平均數據傳輸速率約為。A. 10MbpsB. 20MbpsC. 80Mbps D. 100Mbps37. 站點A、B、C通過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發送的數據是。A. 000 B. 101 C. 110 D. 11138. 主機甲和主機乙已建立了TCP連接，甲始終以 MSS=1KB大小的段發送數據，并一直有數據發送；乙每收到一個數據段都會發出一個接收窗口為10KB的確認段。若甲在t時刻發生超時時擁塞窗口為8KB,則從t時刻起，不再發生超時的情況下，經過10個RTT后，甲的發送窗口是。A. 10KB B. 12KB C. 14KB D. 15KB39. 下列關于 UDP協議的敘述中，正確.的是。I.提供無連接服務 II.提供復用/分用服務HI.通過差錯校驗，

16、保障可靠數據傳輸A.僅 I B.僅 I、II C.僅 II、III D. I、II、III40. 使用瀏覽器訪問某大學 Web網站主頁時，不可能使用到的協議是。A. PPPB. ARP C. UDPD. SMTP二、綜合應用題：4147小題，共70分。41. （13分）二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結點的帶權路徑長度之和。給 定一棵二叉樹T,采用二叉鏈表存儲，結點結構為：丨丨 理 Eight:right I其中葉結點的weight域保存該結點的非負權值。設root為指向T的根結點的指針，請設計求T的WPL的算法，要求：1）給出算法的基本設計思想；2）使用C或C+語言，給出二叉樹

17、結點的數據類型定義；3）根據設計思想，采用 C或C+語言描述算法，關鍵之處給出注釋。42. （10分）某網絡中的路由器運行 OSPF路由協議，題 42表是路由器R1維護的主要鏈 路狀態信息（LSI）,題42圖是根據題42表及R1的接口名構造出來的網絡拓撲。RlJLSIR2 的 LSI艮3的LSI時的LSI#違Router ID1Q.1 1 IW1 1,110.1 15標識躍主器的IP迪址LinklID10 1.1 1所擬曲器的RLurciIDIP101.1210.1 1510 L1.6Link時澤地IF地址MetricA,536總Linkl的費貝IDJO.所趨由器的Rew斜IDIFIII I

18、iJ10.1104.1 1.010 1 1 1+Link：的乘地IF地址Metric24ALink的費冃Neel192.1.C.0 24192 J J.0 汨192.17.0 2-1直連剛第"：1的網絡前級1111Si±wi車網絡Nctl們用題42圖R1構造的網絡拓撲請回答下列問題：1）本題中的網絡可抽象為數據結構中的哪種邏輯結構？2） 針對題42表中的內容，設計合理的鏈式存儲結構，以保存題42表中的鏈路狀態信息（LSI）。要求給出鏈式存儲結構的數據類型定義，并畫出對應題42表的鏈式存儲結構示意圖（示意圖中可僅以ID標識結點）。3）按照迪杰斯特拉（Dijikstra）算法的

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

20、i < N; i+） sum+=Ai;。假設編譯時變量sum和i分別分配在寄存器 R1和R2中。常量N在寄存器R6中，數組A的首地 址在寄存器R3中。程序段P起始地址為0804 8100H,對應的匯編代碼和機器代碼如下表所 示。掃號地址機器代碼匯歸代畫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執庁上述代碼為計凳忙M采毛32位定V指令宇.芽中分玄吿令冗十采距如弋電式;3L25212016150OP I Fb I Md |OFFSETOP為操作碼;；Rs和Rd為寄存器編號；OFFSETS偏移量，用補碼表示。請回答下列問 題，并說明理由。1）M的存儲器編址單位是什么？2）已知sll指令實現左移功能，數組 A中每個元素占多少位？3） 題44表中bne指令的OFFSET段的值是多少？已知 bne指令采用相對尋址方式， 當前PC內容為bne指令地址，通過分析題 44表中指令地址和 bne指令內容，推斷出 bne

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

23、組元素在同一頁，并存儲在磁盤同一個扇區。請回答下列問題并說明理由。1）P執行結束時，R2的內容是多少？2）M的指令Cache和數據Cache分離。若指令 Cache共有16行，Cache和主存交換的塊大小為32字節，則其數據區的容量是多少？若僅考慮程序段P的執行，則指令 Cache的命中率為多少？3）P在執行過程中，哪條指令的執行可能發生溢出異常？哪條指令的執行可能產生缺 頁異常？對于數組 A的訪問，需要讀磁盤和 TLB至少各多少次？46. 文件F由200條記錄組成，記錄從 1開始編號。用戶打開文件后，欲將內存中的一 條記錄插入到文件 F 中，作為其第 30 條記錄。請回答下列問題，并說明理由

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

25、沖區取走一件產品， 否則等待。 要求一個消費者進程 從緩沖區連續取出 10 件產品后， 其他消費者進程才可以取產品。 請使用信號量 P， V(wait() ， sign al()操作實現進程間的互斥與同步，要求寫出完整的過程，并說明所用信號量的含義和初值。2014 年計算機學科專業基礎綜合試題參考答案 一、單項選擇題 一)單選題答案1C2B3A4D 5C6D7D8D9D10B11C12D13 C14A15 A16D17 A18 C19 C20C21 D22B23A24B25D26A27A28C29B30A31 C32D33C34B35D36C37B38A39B40D(二)單選題答案解析1內層循

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

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

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

29、的運算單位加括號。式子變成了：(a/b)+(c*d)-(e*f)/g)第二步：轉換為前綴或后綴表達式。前綴：把運算符號移動到對應的括號前面，則變成了： +(/(ab)/(-(*(cd)*(ef)g)把括號去掉：+/ab/-*cd*efg 前綴式子出現。后綴：把運算符號移動到對應的括號后面，則變成了： (ab)/(cd)*(ef)*)-g)/)+把括號去掉：ab/cd*ef*-g/+后綴式子出現。當題目要求直接求前綴或后綴表達式時，這種方法會比上一種快捷得多。3 end1 指向隊頭元素，那么可知出隊的操作是先從Aend1 讀數，然后 end1 再加 1。end2 指向隊尾元素的后一個位置，那么可

30、知入隊操作是先存數到 Aend2 ，然后 end2 再加 1。若把A0儲存第一個元素，當隊列初始時，入隊操作是先把數據放到A0，然后end2自增，即可知end2初值為0;而endl指向的是隊頭元素，隊頭元素的在數組 A中的下標為0，所以得知 end1 初值也為 0，可知隊空條件為 end1=end2 ；然后考慮隊列滿時，因為隊 列最多能容納 M-1 個元素，假設隊列存儲在下標為 0 到下標為 M-2 的 M-1 個區域，隊頭為 A0，隊尾為AM-2，此時隊列滿，考慮在這種情況下endl和end2的狀態，endi指向隊頭元素，可知 end1=0， end2 指向隊尾元素的后一個位置，可知 end

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

32、點個數，選它的兄弟作為它的右子樹。 那么森林中的葉結點 該結點就沒有左結點， 所以F中葉結點的個數就 Co此題還可以通過一些特例來排除A、B、D選項。6前綴編碼的定義是在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前綴。D中編碼110是編碼1100的前綴，違反了前綴編碼的規則，所以D不是前綴編碼。7按照拓撲排序的算法，每次都選擇入度為0的結點從圖中刪去，此圖中一開始只有結點 3 的入度為 0;刪掉 3結點后，只有結點 1 的入度為 0;刪掉結點 1 后，只有結點 4 的 入度為 0;刪掉 4結點后，結點 2和結點 6的入度都為 0，此時選擇刪去不同的結點，會得 出不同的拓撲序列，分別

33、處理完畢后可知可能的拓撲序列為 314265 和 314625，選 Do8產生堆積現象， 即產生了沖突， 它對存儲效率、 散列函數和裝填因子均不會有影響， 而平均查找長度會因為堆積現象而增大，選 Do9關鍵字數量不變，要求結點數量最多，那么即每個結點中含關鍵字的數量最少。根 據 4 階 B 樹的定義，根結點最少含 1 個關鍵字，非根結點中最少含 ?4/2?-1=1 個關鍵字，所 以每個結點中，關鍵字數量最少都為 1 個，即每個結點都有 2個分支，類似與排序二叉樹， 而15個結點正好可以構造一個 4層的4階B樹，使得葉子結點全在第四層，符合B樹定義，因此選 Do10.首先，第二個元素為1，是整個

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

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

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

37、f2）的絕對值大，而符號為負， 真值大小相反，即（f1）的真值比（f2）的真值小，即x<y,選A。此題還有更為簡便的算法，（f1）與（f2）的前4位為1100與1011,可以看出兩數均為負數， 而階碼用移碼表示，兩數的階碼頭三位分別為100和011，可知（f1）的階碼大于（f2）的階碼，又因為是IEEE754規格化的數，尾數部分均為1.xxx，則階碼大的數，真值的絕對值必然大，可知（f1）真值的絕對值大于（f2）真值的絕對值，因為都為負數，則（f1）<（f2），即x<y。15. 4MX8位的芯片數據線應為 8根，地址線應為log24M=22根，而DRAM采用地址復 用技術,地

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

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

40、32bit/8=4B的數據，66MHz意味著有66M個時 鐘 周期 , 而 每個 時 鐘 周 期 傳 送 兩 次 數 據 , 可 知 總 線 每 秒傳 送 的 最 大 數 據 量 為 66MX 2 X 4B=528MB所以總線的最大數據傳輸率為 528MB/S，選C。20. 猝發 （突發 ）傳輸是在一個總線周期中,可以傳輸多個存儲地址連續的數據,即一次 傳輸一個地址和一批地址連續的數據, 并行傳輸是在傳輸中有多個數據位同時在設備之間進 行的傳輸,串行傳輸是指數據的二進制代碼在一條物理信道上以位為單位按時間順序逐位傳 輸的方式,同步傳輸是指傳輸過程由統一的時鐘控制,選 C。21. 采用統一編址時

41、，CPU訪存和訪問I/O端口用的是一樣的指令，所以訪存指令可以 訪問I/O端口，D選項錯誤，其他三個選項均為正確陳述，選D。22. 每400ns發出一次中斷請求，而響應和處理時間為100ns,其中容許的延遲為干擾 信息,因為在 50ns 內,無論怎么延遲,每 400ns 還是要花費 100ns 處理中斷的,所以該設 備的I/O時間占整個 CPU時間的百分比為 100ns/400ns=25%，選B。23. 采用靜態優先級調度時,當系統總是出現優先級高的任務時, 優先級低的任務會總是得不到處理機而產生饑餓現象； 而短作業優先調度不管是搶占式或是非搶占的， 當系統總 是出現新來的短任務時，長任務會總

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

43、才能執行，選D。26進程申請讀磁盤操作的時候，因為要等待I/O 操作完成，會把自身阻塞，此時進程就變為了阻塞狀態，當 I/O 操作完成后，進程得到了想要的資源，就會從阻塞態轉換到就緒 態(這是操作系統的行為) 。而降低進程優先級、分配用戶內存空間和增加進程的時間片大 小都不一定會發生，選 A。27. 簇的總數為10GB/4KB=2.5M,用一位標識一簇是否被分配，則整個磁盤共需要 2.5M 位，即需要 2.5M/8=320KB,則共需要 320KB/4KB=80個簇，選 A。28. 虛實地址轉換是指邏輯地址和物理地址的轉換。增大快表容量能把更多的表項裝入 快表中， 會加快虛實地址轉換的平均速率

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

45、它類似于通信中半雙工信道的進程通信機制， 一個管道可以實現雙向 的數據傳輸， 而同一個時刻只能最多有一個方向的傳輸， 不能兩個方向同時進行。 管道的容 量大小通常為內存上的一頁， 它的大小并不是受磁盤容量大小的限制。 當管道滿時， 進程在 寫管道會被阻塞，而當管道空時，進程讀管道會被阻塞，因此選C。32. 多級頁表不僅不會加快地址的變換速度，還因為增加更多的查表過程， 會使地址變換速度減慢；也不會減少缺頁中斷的次數，反而如果訪問過程中多級的頁表都不在內存中， 會大大增加缺頁的次數，也并不會減少頁表項所占的字節數(詳細解析參考下段 )，而多級頁表能夠減少頁表所占的連續內存空間， 即當頁表太大時，

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

47、頁正好可以裝下1K個頁表項)，或者增加一些其他信息。33. 直接為會話層提供服務的即會話層的下一層，是傳輸層，選C。34. 主機 00-e1-d5-00-23-a1 向 00-e1-d5-00-23-c1 發送數據幀時，交換機轉發表中沒有00-e1-d5-00-23-c1 這項，所以向除 1 接口外的所有接口廣播這幀，即2、3 端口會轉發這幀，同 時 因 為 轉 發 表 中并 沒 有 00-e1-d5-00-23-a1 這 項 ， 所 以 轉 發 表 會把 (目 的 地 址 00-e1-d5-00-23-a1 ，端口 1)這項加入轉發表。 而當 00-e1-d5-00-23-c1 向 00-e

48、1-d5-00-23-a1 發 送確認幀時， 由于轉發表已經有 00-e1-d5-00-23-a1 這項，所以交換機只向 1 端口轉發， 選 B。35由香農定理可知， 信噪比和頻率帶寬都可以限制信道的極限傳輸速率， 所以信噪比 和頻率帶寬對信道的數據傳輸速率是有影響的，A、B 錯誤；信道的傳輸速率實際上就是信號的發送速率，而調制速度也會直接限制數據的傳輸速率， C 錯誤；信號的傳播速度是信號 在信道上傳播的速度，與信道的發送速率無關，選D。36考慮制約甲的數據傳輸速率的因素，首先，信道帶寬能直接制約數據的傳輸速率， 傳輸速率一定是小于等于信道帶寬的；其次，主機甲乙之間采用后退 N 幀協議，那么

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

50、0Mbps,100Mbps=80Mbps ，選 C。37把收到的序列分成每 4個數字一組，即為 (2,0,2,0)、(0,-2,0,-2)、(0,2,0,2)，因為題目 求的是A發送的數據，因此把這三組數據與A站的碼片序列(1,1,1,1)做內積運算，結果分別是(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 發送的數據是 101，選 B。38當 t 時刻發生超時時，把 ssthresh 設為 8 的一半，即為 4，且擁塞窗口設為 1KB。 然后經歷10個RTT后，擁塞窗

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

52、當接入網絡時可能會用到 PPP協議，A可能用到；而當計算機不知道某主機的 MAC 地址時，用IP地址查詢相應的 MAC地址時會用到 ARP協議，B可能用到；而當訪問 Web 網站時，若DNS緩沖沒有存儲相應域名的 IP地址，用域名查詢相應的IP地址時要使用 DNS 協議，而DNS是基于UDP協議的，所以 C可能用到，SMTP只有使用郵件客戶端發送郵件，或是郵件服務器向別的郵件服務器發送郵件時才會用到，單純的訪問 Web網頁不可能用到。二、綜合應用題41 .解答： 考查二叉樹的帶權路徑長度, 二叉樹的帶權路徑長度為每個葉子結點的深 度與權值之積的總和，可以使用先序遍歷或層次遍歷解決問題。1) 算

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

54、wpl2) 二叉樹結點的數據類型定義如下：weight;struct BiTNM *1 血Id嚴代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 變晁存儲 “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 叭衛1;若為葉于結自，累稅A'p：若左子崗不空.襯千子杭遙=|遍歷若右子樹不空，對右子檢矍日遍歷 基于層次遍歷的算法:int np 1_LfvelQrdfr<31Trfe root kBiTnee q|MaxSizeiint