2014年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合真題及詳解

一、單項選擇題：1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是符合題目要求的。

1下列程常段的時間復雜度是（　　）

A．O（log₂n）

B．O（n）

C．O（nlog₂n）

D．O（n²）

【答案】C

【解析】外部循環的退出條件是k＞n，而對于k，每次循環都執行k＝k*2，所以循環次數為log₂n；內部循環的退出條件是j＞n，對于j，每次循環都執行j＝j＋1，所以每次循環次數為n次。所以此程序段的時間復雜度為O（nlog₂n），即選C。

2假設棧初始為空，將中綴表達式a/b＋（c*d－e*f）/g轉換為等價后綴表達式的過程中，當掃描到f時，棧中的元素依次是（　　）

A．＋（*－

B．＋（－*

C．/＋（*－*

D．/＋－*

【答案】B

【解析】中綴表達式轉后綴表達式遵循以下原則：

（1）遇到操作數，直接輸出；

（2）棧為空時，遇到運算符，入棧；

（3）遇到左括號，將其入棧；

（4）遇到右括號，執行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，左括號不輸出；

（5）遇到其他運算符‘＋’、‘－’、‘*'、‘/’時，彈出所有優先級大于或等于該運算符的棧頂元素，然后將該運算符入棧；

（6）最終將棧中的元素依次出棧，輸出。

所以掃描到‘/’，入棧；掃描到‘＋’，由于‘＋’優先級比‘/’低，所以將‘/’彈出，‘＋’入棧；掃描到‘*’，優先級比‘＋’高，入棧；掃描到‘（’，入棧；掃描到‘－’，將棧中優先級更高的‘*’彈出，‘－’入棧；掃描到‘*’，優先級比‘－’高，入棧。所以掃描到f的時候，棧中元素為：＋（－*。

3循環兩列放在一維數組A[0…M－1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M－1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是（　　）

A．隊空：end1＝＝end2；隊滿：end1＝＝（end2＋1）modM

B．隊空：end1＝＝end2；隊滿：end2＝＝（end1＋1）mod（M－1）

C．隊空：end2＝＝（end1＋1）modM；隊滿：end1＝＝（end2＋1）modM

D．隊空：end1＝＝（end2＋1）modM；隊滿：end2＝＝（end1＋1）mod（M－1）

【答案】A

【解析】在循環隊列中，在少用一個元素空間的前提下，可約定入隊前，測試尾指針在循環意義下加1后是否等于頭指針，若相等，則隊滿。而隊空的條件還是首尾指針是否相等。

4若對如下的二叉樹進行中序線索化，則結點x的左、右線索指向的結點分別是（　　）

A．e，c

B．e，a

C．d，c

D．b，a

【答案】D

【解析】此二叉樹的中序遍歷序列為：debxac，由于節點x左右孩子都為空，所有進行中序線索化時，它的左右孩子指針分別指向它的中序遍歷序列的直接前驅結點b和直接后繼結點a，所以選D。

5將森林F轉換為對應的二叉樹T，F中葉結點的個數等于（　　）

A．T中葉結點的個數

B．T中度為1的結點個數

C．T中左孩子指針為空的結點個數

D．T中右孩子指針為空的結點個數

【答案】C

【解析】森林轉化為對應的二叉樹是‘孩子-兄弟’存儲的，即左孩子指針指向當前節點的孩子節點，右孩子指針指向當前節點的兄弟節點，所以在T中左孩子指針為空則代表它在森林中并沒有孩子即為葉結點。所以選C。

65個字符有如下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

【答案】D

【解析】在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前綴。約定左分支表示字符‘0’，右分支表示字符‘1’，則可以用從根結點到葉子結點的路徑上的分支字符串作為該葉子結點字符的編碼。如此得到的編碼必是前綴編碼。D選項中，編碼110是編碼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

【答案】D

【解析】拓撲排序方法如下:

（1）從有向圖中選擇一個沒有前驅（即入度為0）的頂點并且輸出它；

（2）從圖中刪去該頂點，并且刪去從該頂點發出的全部有向邊；

（3）重復上述兩步，直到剩余的網中不再存在沒有前趨的頂點為止。

對于此有向圖進行拓撲排序所有序列為：3，1，4，6，2，5和3，1，4，2，6，5。所以選D。

8用哈希（散列）方法處理沖突（碰撞）時可能出現堆積（聚集）現象，下列選項中，會受堆積現象直接影響的是（　　）

A．存儲效率

B．數列函數

C．裝填（裝載）因子

D．平均查找長度

【答案】D

【解析】哈希方法沖突會使在查找沖突的關鍵字時，還要根據沖突處理辦法多次比較關鍵字，則直接影響了平均查找長度。

9在一棵具有15個關鍵字的4階B樹中，含關鍵字的結點數最多是（　　）

A．5

B．6

C．10

D．15

【答案】D

【解析】m階B樹非根結點含關鍵字個數j有：?m/2?－1＜＝j＜＝m－1。4階B樹非根結點含關鍵字1～3個，所以要使關鍵字結點數量最多，那么每個結點只有一個關鍵字，一共有15個關鍵字那么最多有15個含有關鍵字的結點。

10用希爾排序方法對一個數據序列進行排序時，若第1趟排序結果為9，1，4，13，7，8，20，23，15，則該趟排序采用的增量（間隔）可能是（　　）

A．2

B．3

C．4

D．5

【答案】B

【解析】對于A，增量為2，那么9，4，7，20，15是一組，而它們是無序的，所以A錯誤；對于C，增量為4，那么9，7，15是一組，而它們是無序的，所以C錯誤；對于D，增量為5，那么9，8是一組，降序，1，20是一組，而它們是升序，所以D也錯誤。對于B，分為3組：9，13，20；1，7，23；4，8，15都是升序有序，所以B正確。

11下列選項中，不可能是快速排序第2趟排序結果的是（　　）

A．2，3，5，4，6，7，9

B．2，7，5，6，4，3，9

C．3，2，5，4，7，6，9

D．4，2，3，5，7，6，9

【答案】C

【解析】對于快速排序，每一趟都會使一個元素位于有序時的位置，而有序序列為2，3，4，5，6，7，9，與C進行對比，只有9位于它有序的時候的位置，顯然不是第二趟快速排序的結果。

12程序P在機器M上的執行時間是20秒，編譯優化后，P執行的指令數減少到原來的70%，而CPI增加到原來的1.2倍，則P在M上的執行時間是（　　）

A．8.4秒

B．11.7秒

C．14秒

D．16.8秒

【答案】D

【解析】20*0.7*1.2＝16.8

13若x＝103，y＝－25，則下列表達式采用8位定點補碼運算實現時，會發生溢出的是（　　）

A．x＋y

B．－x＋y

C．x－y

D．－x－y

【答案】C

【解析】8位定點補碼能表示的數的范圍為：－128～127。A結果為78，B結果為－128，D結果為－78都在此范圍內，只有C結果128超過了8位定點補碼能表示的數的范圍，會發生溢出。

14float型整數據常用IEEE754單精度浮點格式表示，假設兩個float型變量x和y分別在32為寄存器f1和f2中，若（f1）＝CC900000H，（f2）＝B0C00000H，則x和y之間的關系為：（　　）

A．x＜y且符號相同

B．x＜y且符號不同

C．x＞y且符號相同

D．x＞y且符號不同

【答案】A

【解析】兩個數對應的IEEE754的標準形式為；

將IEEE754單精度形式的二進制轉化為浮點數公式為V＝（－1）^s*2^（E－Bias）*M

由于f1，f2的符號位都是1，所以f1，f2符號相同，而階碼上f1＞f2，所以f1＞f2，所以f1的絕對值比f2大，而他們都是負數，所以f1＜f2，所以選A。

15某容量為256M的存儲器，由若干4M*8位的DRAM芯片構成，該DRAM芯片的地址引腳和數據引腳總數是：（　　）

A．19

B．22

C．30

D．36

【答案】A

【解析】DRAM地址線復用，4M為2的22次方，因此除2為11根，數據線8根。因此地址引腳和數據引腳總數為19根。

16采用指令Cache與數據Cache分離的主要目的是（　　）

A．減低Cache的缺失損失

B．提高Cache的命中率

C．減低CPU平均訪問時間

D．減少指令流水線資源沖突

【答案】D

【解析】指令流水線不會斷流，預取過來的都是指令。

17某計算機有16個通用寄存器，采用32位定長指令字操作碼字段（含尋址方式位）為8位，Store指令的源操作數和目的操作數分別采用寄存器直接尋址和基址尋址方式，若基址寄存器可使用任一通用寄存器，且偏移量用補碼表示，則Store指令中偏移量的取值范圍是（　　）

A．－32768～＋32767

B．－32767～＋32768

C．－65536～＋65535

D．－65535～＋65536

【答案】A

【解析】寄存器個數16＝2⁴，偏移量有32－8－4－4＝16位

指令編址方式如下所示：

16位補碼取值范圍為－32768～＋32767，所以偏移量取值范圍為－32768～＋32767。

18某計算機采用微程序控制器，共有32條指令，公共的取指令微程序包含2條微程序，各指令對應的微程序平均由4條微指令組成，采用斷定法（下址字段法）確定下條微指令的地址，則微指令中下址字段的位數至少是：（　　）

A．5

B．6

C．8

D．9

【答案】C

【解析】32*4＋2＝130，2⁷＝128＜130＜2⁸＝256，所以至少需要8位才能表示完130個地址。

19某同步總線采用數據線和地址線復用方式。其中地址數據線有8根，總線時鐘頻率為66MHZ，每個時鐘同期傳送兩次數據。（上升沿和下降沿各傳送一次數據）該總線的最大數據傳輸率是（總線帶寬）：（　　）

A．132MB/S

B．264MB/S

C．528MB/S

D．1056MB/S

【答案】C

【解析】總線帶寬＝總線工作頻率×（總線寬度/8），由于地址線與數據線復用，所以在兩次數據傳輸過程中總線上數據一共傳輸了8次，那么總線帶寬為66*8＝528，所以選C。

20一次總線事物中，主設備只需給出一個首地址，從設備就能從首地址開始的若干連續單元格讀出或寫入的個數，這種總線事務方式稱為（　　）

A．并行傳輸

B．串行傳輸

C．突發

D．同步

【答案】C

【解析】猝發數據傳輸方式：在一個總線周期內傳輸存儲地址連續的多個數據字的總線傳輸方式。

21下列有關I/O接口的敘述中錯誤的是：（　　）

A．狀態端口和控制端口可以合用同一寄存器

B．I/O接口中CPU可訪問寄存器，稱為I/O端口

C．采用獨立編址方式時，I/O端口地址和主存地址可能相同

D．采用統一編址方式時，CPU不能用訪存指令訪問I/O端口

【答案】D

【解析】采用統一編碼方式，存儲器和I/O端口共用統一的地址空間，不需要專用的I/O指令，任何對存儲器數據進行操作的指令都可用于I/O端口的數據操作。所以D錯誤。

22某設備中斷請求的相應和處理時間為100ns，每400ns發出一次中斷請求，中斷相應所容許的最長延遲時間為50ns，則在該設備持續工作過程中CPU用于該設備的I/O時間占整個CPU時間百分比至少是（　　）

A．12.5%

B．25%

C．37.5%

D．50%

【答案】B

【解析】每400ns響應一次中斷并且用100ns進行處理，所以該設備的I/O時間占用CPU時間百分比為100/400＝25%，中斷響應容許的延遲時間對此沒有影響，屬于干擾條件。

23下列調整中，不可能導致饑餓現象的是（　　）

A．時間片轉移

B．靜態優先及調度

C．非搶占式作業優先

D．搶占式短作業優先

【答案】A

【解析】時間片轉移方法能在一個周期內使每個進程都得到一個時間片的CPU使用時間，不會產生饑餓的現象，其余三個都會產生饑餓。

24某系統有n臺互斥使用的同類設備，3個并發進程需要3，4，5臺設備，可確保系統不發生死鎖的設備數n最小為（　　）

A．9

B．10

C．11

D．12

【答案】B

【解析】2＋3＋4＋1＝10。

25下列指令中，不能在用戶態執行的是（　　）

A．trap指令

B．跳轉指令

C．后棧指令

D．關中斷指令

【答案】D

【解析】關中斷指令必須在和心態才能執行，trap指令可以在用戶態下執行，執行了就轉到和心態，跳轉與退棧指令都是可以在用戶態下執行的指令。

26一個進程的讀磁區操作完成后，操作系統針對該進程必做的是（　　）

A．修改進程狀態為就緒態

B．降低進程優先級

C．進程分配用戶內存空間

D．增加進程的時間片大小

【答案】A

【解析】進程等待的I/O操作完成便會從等待狀態轉移到就緒狀態。

27現有容量為10GB的磁盤分區，磁盤空間以簇（cluster）為單位進行分配，簇的大小為4KB，若采用位圖法管理該分區的空閑空間，即用一位（bit）標識一個簇是否被分配，則存放該位圖所需簇的個數為（　　）

A．80

B．320

C．80K

D．320K

【答案】A

【解析】磁盤的簇的個數為：10GB/4KB＝2.5*2²⁰個，而一個簇的位示圖能管理的簇的個數為：4KB*8＝32K，所以需要簇的個數為2.5*2²⁰/32K＝80個。

28下列措施中，能加快虛實地址轉換的是1增大快表（TLB）2讓頁表常駐內存3增大交換區（　　）

A．僅1

B．僅2

C．僅1，2

D．僅2，3

【答案】C

【解析】加大快表能增加快表的命中率，即減少了訪問內存的次數；讓頁表常駐內存能夠使CPU不用訪問內存找頁表，從也加快了虛實地址轉換。而增大交換區只是對內存的一種擴充作用，對虛實地址轉換并無影響

29在一個文件被用戶進程首次打開的過程中，操作系統需做的是（　　）

A．將文件內容讀到內存中

B．將文件控制塊讀到內存中

C．修改文件控制塊中的讀寫權限

D．將文件的數據緩沖區首指針返回給用戶進程

【答案】B

【解析】主要考查的是open系統調用主要做了什么。open最終返回的是文件描述符fd。為后面的讀寫做準備。至于文件緩沖區的首指針，這是在read和write需要傳入的，open只做到減少查詢，避免按名查找，通過維護的打開文件表，快速索引到文件。FCB主要是文件的描述信息，也是open工作的核心：把FCB或者Linux下的inode調入內存。

30在頁式存儲管理系統中，采用某些頁面置換算法，會出現Belady異常現象，即進程的缺頁次數會隨著分配給該進程的頁框個數的增加而增加。下列算法中，可能出現Belady異常現象的是（　　）

Ⅰ．LRU算法

Ⅱ．FIFO算法

Ⅲ．OPT算法

A．僅Ⅱ

B．Ⅰ、Ⅱ

C．Ⅰ、Ⅲ

D．Ⅱ、Ⅲ

【答案】A

【解析】Belady現象只有FIFO算法才會出現。

31下列關于管道（Pipe）通信的敘述中，正確的是（　　）

A．一個管道可實現雙向數據傳輸

B．管道的容量僅受磁盤容量大小限制

C．進程對管道進行讀操作和寫操作都可以被阻塞

D．一個管道只能有一個讀寫進程或一個寫進程對其操作

【答案】C

【解析】只有寫進程才能對管道寫入數據，讀進程對管道進行讀取數據，只能半雙工通信，即某一時刻只能單向傳輸。管道為空，則讀操作被堵塞，而如果有寫操作對管道進行寫的話那就要堵塞了。那么C正確。

32下列選項中，屬于多級頁表優點的是（　　）

A．加快地址變換速度

B．減少缺頁中斷次數

C．減少頁表項所占字節數

D．減少頁表所占的連續內存空間

【答案】D

【解析】多級頁表避免了把所有的頁表一直保存在內存中。

33在OSI參考模型中，直接為會話層提供服務的是（　　）

A．應用層

B．表示層

C．傳輸層

D．網絡層

【答案】C

【解析】OSI參考模型中，下層直接為上層提供服務，而會話層的下層為傳輸層。

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發送一個確認幀，交換機對這兩個幀的轉發端口分別是（　　）

A．{3}和{1}

B．{2，3}和{1}

C．{2，3}和{1，2}

D．{1，2，3}和{1}

【答案】B

【解析】第一次交換機沒有00-e1-d5-00-23-c1的信息，只能選擇從其他端口全部發送，同時記錄這個數據報源MAC地址的信息00-e1-d5-00-23-a1，確認幀發送時已經有00-e1-d5-00-23-a1的信息了所以只用從1端口轉發。

35下列因素中，不會影響信道數據傳輸速率的是（　　）

A．信噪比

B．頻率寬帶

C．調制速率

D．信號傳播速度

【答案】D

【解析】信道數據傳輸速率與信噪比、頻率寬度、調制速率都有關。

36主機甲與主機乙之間使用后退N幀協議（GBN）傳輸數據，甲的發送窗口尺寸為1000，數據幀長為1000字節，信道寬帶為100Mbps，乙每收到一個數據幀立即利用一個短幀（忽略其傳輸延遲）進行確認，若甲乙之間的單向傳播延遲是50ms，則甲可以達到的最大平均數據傳輸速率約為（　　）

A．10 Mbps

B．20 Mbps

C．80 Mbps

D．100 Mbps

【答案】C

【解析】1000B*1000/（50*2ms）＝10MB＝80Mbps。

37站點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發送的數據是（　　）

A．000

B．101

C．110

D．111

【答案】B

【解析】用A的碼片與信息做內積運算。

38主機甲和乙已建立了TCP連接，甲始終以MSS＝1KB大小的段發送數據，并一直有數據發送；乙每收到一個數據段都會發出一個接收窗口為10KB的確認段。若甲在t時刻發生超時時擁塞窗口為8KB，則從t時刻起，不再發生超時的情況下，經過10個RTT后，甲的發送窗口是（　　）

A．10KB

B．12KB

C．14KB

D．15KB

【答案】A

【解析】發送窗口是接受窗口和擁塞窗口的最小值，這里接收窗口總是10KB。擁塞窗口到那個時候是大于10KB的，取最小值。

39下列關于UDP協議的敘述中，正確的是（　　）

Ⅰ．提供無連接服務

Ⅱ．提供復用/分用服務

Ⅲ．通過差錯校驗，保障可靠數據傳輸

A．僅Ⅰ

B．僅Ⅰ、Ⅱ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】UDP無連接創建，提供多路復用服務。雖然有差錯檢驗，但是不能保證可靠數據傳輸，所以Ⅲ錯誤。

40使用瀏覽器訪問某大學Web網站主頁時，不可能使用的協議是（　　）

A．PPP

B．ARP

C．UDP

D．SMTP

【答案】D

【解析】SMTP是簡單郵件傳輸協議，訪問主頁時并不涉及郵件相關協議。

二、綜合應用題：41～47小題，共70分。

41（10分）二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結點的帶權路徑長度之和，給定一棵二叉樹T，采用二叉鏈表存儲，節點結構為：

其中葉節點的weight域保存該結點的非負權值。設root為指向T的根節點的指針，設計求T的WPL的算法。要求：

（1）給出算法的基本設計思想；

（2）使用C或C＋＋語言，給出二叉樹結點的數據類型定義；

（3）根據設計思想，采用C或C＋＋語言描述算法，關鍵之處給出注釋。

答：（1）算法的基本思路是利用利用遞歸的思想來求解二叉樹的帶權路徑長度，如果當前節點不是葉子節點，那么當前節點為根的樹的帶權路徑長度便等于它的子樹的帶權路徑長度之和，對于此函數要傳入一個當前節點的樹高的形參，那么遞歸調用孩子節點時只需要將這個形參加一即可。

（2）

（3）具體算法實現如下：

42（10分）某網絡中的路由器運行OSPF路由協議，題42表是路由器R1維護的主要鏈路狀態信息（LSI），題42圖是根據題42表及R1的接口名構造出來的網絡拓撲。

題42表　R1所維護的LSI

題42圖　R1構造的網絡拓撲

請回答下列問題。

本題中的網絡可抽象為數據結構中的哪種邏輯結構？

針對題42表中的內容，設計合理的鏈式存儲結構，以保存題42表中的鏈路狀態信息（LSI）。要求給出鏈式存儲結構的數據類型定義，并畫出對應題42表的鏈式存儲結構示意圖（示意圖中可僅以ID標識節點）。

按照迪杰斯特拉（Dijikstra）算法的策略，依次給出R1到達題42圖中子網192.1.x.x的最短路徑及費用。

答：（1）圖

（2）使用圖的鄰接表存儲結構進行存儲，數據類型定義如下：

鏈式存儲結構示意圖如下圖所示：

（3）目標網絡192.1.1.0/24記為N1，192.1.5.0/24記為N2，192.1.6.0/24記為N3，192.1.7.0/24記為N4，使用dijkstra算法找最短路徑步驟如下表所示：

所以R1到達子網192.1.1.0/24最短路徑為：R1->子網，費用為1；

R1到達子網192.1.6.0/24的最短路徑為：R1->R2->子網，費用為3；

R1到達子網192.1.5.0/24的最短路徑為：R1->R3->子網，費用為4；

R1到達子網192.1.7.0/24的最短路徑為R1->R2->R4->子網，費用為8。

43（9分）請根據題42描述的網絡，繼續回答下列問題。

（1）假設路由表結構如下表所示，請給出題42圖中R1的路由表，要求包括到達題42圖中子網192.1.x.x的路由，且路由表中的路由項盡可能少。

（2）當主機192.1.1.130向主機192.1.7.211發送一個TTL＝64的IP分組時，R1通過哪個接口轉發該IP分組？主機192.1.7.211收到的IP分組的TTL是多少？

（3）若R1增加一條Metric為10的鏈路鏈接Internet，則題42表中R1的LSI需要增加哪些信息？

答：（1）

（2）通過接口L0轉發該IP分組，由于要經過R1，R2，R4三個路由器，所以主機192.1.7.211收到的IP分組的TTL為64－3＝61。

（3）只需要在R1的LSI中增加一項信息，prefix＝目的internet，Metric＝10。

44（11分）某程序中有如下循環代碼段p：

假設編譯時變量sum和i分別分配在寄存器R1和R2中。常量N在寄存器R6中，數組A的首地址在寄存器R3中，程序段P起始地址為0804 8100H，對應的匯編代碼和機器代碼如題44表所示

執行上述代碼的計算機M采用32位定長指令字，其中分支指令Bne采用如下格式，

Op為操作碼：Rs和Rd為寄存器編號：OFFSET為偏移量，用補碼表示。請回答下列問題，并說明理由。

（1）M的存儲器編址單位是什么？

（2）已知sll指令實現左移功能，數組A中每個元素占多少位？

（3）題44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相對尋址方式，當前PC內容為bne指令地址，通過分析題44表中指令地址和bne指令內容，推斷出bne指令的轉移目標地址計算公式。

（4）若M采用如下“按序發射、按序完成”的5級指令流水線：IF（取指）、ID（譯碼及取數）、EXE（執行）、MEM（訪存）、WB（寫回寄存器），且硬件不采取任何轉發措施，分支指令的執行均引起3個時鐘周期阻塞，則P中哪些指令的執行會由于數據相關而發生流水線阻塞？哪條指令的執行會發生控制冒險？為什么指令1的執行不會因為與指令5的數據相關而發生阻塞？

答：（1）由題可知，指令為32為即4個字節，而程序執行時是以4為間隔逐條取指令的，故可知M的存儲器是采用字節編址。

（2）32位，因為sll中實現左移，而（R2）＜＜2→R4即左移兩位就是乘以4，所以是4*8＝32位。

（3）由Bne的指令格式可知其OFFSET為指令的后16位，而Bne的機器碼碼為1446 FFFAH，所以Bne的OFFSET為FFFAH即－6。

由題可知Bne采用相對尋址方式，故有效地址EA＝（PC）＋A＝（PC）＋OFFSET，而PC的值為當前Bne指令的地址即（PC）＝08048114H，而取完Bne指令后，（PC）＋4→PC，故（PC）＝0804 8118H。而要跳轉到指令1的地址08048100H，兩者相差了18H也就是24個字節，而OFFSET是－6，故轉移目標地址計算公式為（PC）＋OFFSET*（24/6）＝（PC）＋OFFSET*4。

（4）由指令序列可知，指令1需寫R4而指令2需讀R4，故指令2會因為數據相關而發生阻塞，同理指令3、指令4也會因為數據相關而發生阻塞；而指令6為分支指令，故其存在控制冒險。因為分支指令會有3個時鐘周期的阻塞，故指令1的執行不會因為指令5的數據相關而發生阻塞。

45（10分）假設對于44題中的計算機M和程序P的機器代碼，M采用頁式虛擬存儲管理。P開始執行時，（R1）＝（R2）＝0，（R6）＝1000，其機器代碼已調入主存但不在Cache中；數組A未調入主存，其所有數組元素在同一頁，并存儲在磁盤同一個扇區，請回答下列問題，并說明理由。

（1）P執行結束時，R2的內容是多少？

（2）M的指令Cache和數據Cache分離，若Cache共有16行，Cache和主存交換的塊大小為32字節，則其數據區的容量是多少？若僅考慮程序段P的執行，則指令Cache的命中率為多少？

（3）P在執行過程中，哪條指令的執行可能發生溢出異常？哪條指令的執行可能產生缺頁異常？對于數組A的訪問，需要讀磁和TLB至少各多少次？

答：（1）R2是保存變量i的內容，當P執行完即i＜N不滿足，故i＝N＝（R6）＝1000。

（2）Cache共有16行，每行大小為32B，而本段指令大小為6*4B＝24B，故指令占一行Cache，所以數據Cache的大小為15*32B＝160B。

由題可知N＝1000，故循環了1000次，所以共執行了1000*6＝6000條指令，而只有第一次循環執行指令1時指令不在Cache中，故指令Cache命中率＝（6000－1）/6000＝99.9%。

（3）指令4有可能發生溢出，該指令是統計數組A[0]～A[i]的和，而數組A的各元素的值未知，故該指令是可能發生溢出的。

第一次執行指令2時需要訪問數組A，而數組A未在內存中，故會發生缺頁異常。由題可知數組A的所有元素在同一頁，并存儲在磁盤同一個扇區，故經過一次便將該頁調入內存，所以以后訪問便不會發生缺頁中斷，故只需讀一次磁盤，999次TLB。

46（9分）文件F由200條記錄組成，記錄從1開始編號，用戶打開文件后，欲將內存中的一條記錄插入文件F中，作為其第30條記錄，請回答下列問題，并說明理由。

（1）若文件系統為順序分配方式，每個存儲塊存放一條記錄，文件F的存儲區域前后均有足夠空閑的存儲空間，則要完成上述操作最少要訪問多少存儲塊？F的文件控制區內容會有哪些改變？

（2）若文件系統為鏈接分配方式，每個存儲塊存放的一條記錄和一個鏈接指針，則要完成上述操作最少要訪問多少存儲塊？若每個存儲塊大小為1KB，其中4個字節存放指針，則該系統支撐文件的最大長度是多少？

答：（1）因為要最少訪問，所以選擇將前29塊前移一個存儲塊單元，然后將要寫入的記錄寫入到當前的第30條的位置上。由于前移都要先訪問原存儲塊將數據讀出，再訪問目標存儲塊將數據寫入，所以最少需要訪問29*2＋1＝59塊存儲塊。F的文件區的文件長度加1，起始塊號減1。

（2）采用鏈接方式則需要順序訪問前29塊存儲塊，然后將新紀錄的存儲塊插入鏈中即可，把新的塊存入磁盤要1次訪存，然后修改第29塊的鏈接地址存回磁盤又一次訪存。一共就是29＋1＋1＝31次。4個字節的指針的地址范圍為2³²。所以此系統支撐文件的最大長度為2³²*（1KB－4B）＝4080GB。

47（11分）系統中有多個生產者進程和消費者進程，共享用一個可以存1000個產品的緩沖區（初始為空），當緩沖區為未滿時，生產者進程可以放入一件其生產的產品，否則等待；當緩沖區為未空時，消費者進程可以取走一件產品，否則等待。要求一個消費者進程從緩沖區連續取出10件產品后，其他消費者進程才可以取產品，請用信號量P，V（wait，signed）操作實現進程間的互斥和同步，要求寫出完整的過程；并指出所用信號量的含義和初值

答：設置5個信號量，

empty：表示緩沖區是否為空，初值為1000；

full：表示緩沖區是否為滿，初值為0；

mutex1：生產者之間的互斥信號，初值為1；

mutex2：消費者之間的互斥信號，初值為1；

available：當前消費者能否訪問緩沖區，初值為1；

定義變量in，out分別為生產者和消費者進程所要使用的指針，指向下一個可用的緩沖區單元，MaxNum＝1000為緩沖區的大小，count標志當前消費者已經取的產品的數量，初值為0。

生產者進程：

消費者進程