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

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

1已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m＋n的降序鏈表，則最壞情況下的時間復雜度是（　　）

A．O（n）

B．O（m*n）

C．O（min（m，n））

D．O（max（m，n））

【答案】D

【解析】m和n是兩個升序鏈表長度分別為m和n，在合并過程中最壞的情況是兩個鏈表中的元素依次進行比較，比較的次數是m和n中的最大值。

2一個棧的入棧序列為1，2，3，……，n，其出棧序列是P₁，P₂，P₃……P_n。若，則P₂＝3，則P₃可能取值的個數是（　　）

A．n－3

B．n－2

C．n－1

D．無法確定

【答案】C

【解析】除了3本身以外，其他的值均可以取到，因此可能取值的個數為n－1。

3若將關鍵字1，2，3，4，5，6，7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結點的個數是（　　）

A．0

B．1

C．2

D．3

【答案】D

【解析】將圖中給定的關鍵字序列依次插入到平衡樹中，構成的平衡樹如下圖所示，由圖可知平衡因子為0的分支結點為3個葉子結點，故答案為D。

4已知三叉樹T中6個葉結點的權分別是2，3，4，5，6，7，T的帶權（外部）路徑長度最小是（　　）

A．27

B．46

C．54

D．56

【答案】B

【解析】利用三叉樹的6個葉子結點的權構建最小帶權生成樹，最小的帶權路徑長度為（2＋3）*3＋（4＋5）*2＋（6＋7）*1＝46

5若X是后序線索二叉樹中的葉結點，且X存在左兄弟結點Y，則X的右線索指向的是（　　）

A．X的父結點

B．以Y為根的子樹的最左下結點

C．X的左兄弟結點Y

D．以Y為根的子樹的最右下結點

【答案】A

【解析】根據后續線索二叉樹的定義，X結點為葉子結點且有左兄弟，那么這個結點為右孩子結點，利用后續遍歷的方式可知X結點的后繼是其父結點，即其右線索指向的是父結點。

6在任意一棵非空二叉排序樹T1中，刪除某結點v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關于T1與T3的敘述中，正確的是（　　）

I．若v是T1的葉結點，則T1與T3不同

II．若v是T1的葉結點，則T1與T3相同

III．若v不是T1的葉結點，則T1與T3不同

IV．若v不是T1的葉結點，則T1與T3相同

A．僅I、III

B．僅I、IV

C．僅II、III

D．僅II、IV

【答案】C

【解析】在一棵二叉排序樹中刪除一個結點后再將此結點插入到二叉排序樹中，如果刪除的結點是葉子結點那么在插入結點后，后來的二叉排序樹與刪除結點之前相同。如果刪除的結點不是葉子結點，那么再插入這個結點后，后來的二叉樹可能發生變化，不完全相同。

7設圖的鄰接矩陣A如下所示，各頂點的度依次是（　　）

A．1，2，1，2

B．2，2，1，1

C．3，4，2，3

D．4，4，2，2

【答案】C

【解析】當圖用鄰接矩陣存儲時，各頂點的度是矩陣中此結點對應的橫行和縱列非零元素之和。

8若對如下無向圖進行遍歷，則下列選項中，不是廣度優先遍歷序列的是（　　）

A．h，c，a，b，d，e，g，f

B．e，a，f，g，b，h，c，d

C．d，b，c，a，h，e，f，g

D．a，b，c，d，h，e，f，g

【答案】D

【解析】根據廣度優先遍歷的定義，可知選項A、B、C都為廣度優先遍歷，而選項D是深度優先遍歷而不是廣度優先遍歷，故答案為D。

9下列AOE網表示一項包含8個活動的工程。通過同時加快若干進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（　　）

A．c和e

B．d和e

C．f和d

D．f和h

【答案】C

【解析】根據AOE網的定義可知，同時縮短幾條關鍵路徑上的活動時間，可以縮短整個工期。

10在一株高度為2的5階B樹中，所含關鍵字的個數最少是（　　）

A．5

B．7

C．8

D．14

【答案】A

【解析】根據B樹的定義可知，跟結點最少含有max（2，（m－1））個關鍵字，高度為2的階B樹最少有（5－1）＋1＝5個關鍵字，其中根節點含有（5－1）個關鍵字，第2層結點含有1關鍵字。

11對給定的關鍵字序列110，119，007，911，114，120，122進行基數排序，則第2趟分配收集后得到的關鍵字序列是（　　）

A．007，110，119，114，911，120，122

B．007，110，119，114，911，122，120

C．007，110，911，114，119，120，122

D．110，120，911，122，114，007，119

【答案】C

【解析】基數排序的第1趟排序是按照個位數字來排序的，第2趟排序是按然十位數字的大小進行排序的，故答案是C選項。

12某計算機主頻為1.2GHz，其指令分為4類，它們在基準程序中所占比例及CPI如下表所示。

該機的MIPS數是（　　）

A．100

B．200

C．400

D．600

【答案】C

【解析】基準程序的CPI＝2*0.5＋3*0.2＋4*0.1＋5*0.2＝3。計算機的主頻為1.2GHz，為1200MHz，該機器的MIPS為1200/3＝400。

13某數采用IEEE754單精度浮點數格式表示為C640 0000H，則該數的值是（　　）

A．－1.5×2¹³

B．－1.5×2¹²

C．－0.5×2¹³

D．－0.5×2¹²

【答案】A

【解析】IEEE754單精度浮點數格式為C640 0000H表示為二進制格式為1100 0110 0100 0000 0000 0000 0000 0000，轉換為標準的格式為：

因此，浮點數的值為－1.5*2¹³。

14某字長為8位的計算機中，已知整型變量x、y的機器數分別為[x]_補＝11110100，[y]_補＝10110000。若整型變量z＝2*x＋y/2，則z的機器數為（　　）

A．11000000

B．00100100

C．10101010

D．溢出

【答案】A

【解析】將x左移一位，y右移一位，兩個數的補碼相加的機器數為1 1000000，故答案選擇A。

15用海明碼對長度為8位的數據進行檢/糾錯時，若能糾正一位錯，則校驗位數至少為（　　）

A．2

B．3

C．4

D．5

【答案】C

【解析】設校驗位的位數為k，數據位的位數為n，根據海明碼編碼k和n應滿足下述關系。2^k≥n＋k＋1。n＝8，當k＝4時，2⁴＝16≥8＋4＋1＝13，符合要求，校驗位至少是4位，故答案為C。

16某計算機主存地址空間大小為256MB，按字節編址。虛擬地空間大小為4GB，采用頁式存儲管理，頁面大小為4KB，TLB（快表）采用全相聯映射，有4個頁表項，內容如下表所示。

則對虛擬地址03FF F180H進行虛實地址變換的結果是（　　）

A．015 3180H

B．003 5180H

C．TLB缺失

D．缺頁

【答案】A

【解析】虛擬地址為03FF F180H，其中頁號為03FFFH，頁內地址為180H，根據題目中給出的頁表項可知頁標記為03FFFH 所對應的頁框號為0153H，頁框號與頁內地址之和即為物理地址015 3180H。

17假設變址寄存器R的內容為1000H，指令中的形式地址為2000H；地址1000H中的內容為2000H，地址2000H中的內容為3000H，地址3000H中的內容為4000H，則變址尋方式下訪問到的操作數是（　　）

A．1000H

B．2000H

C．3000H

D．4000H

【答案】D

【解析】根據變址尋址的EA＝（IX）＋A，變址寄存器的內容與形式地址的內容相加之后得到操作數的實際地址，由題可知EA＝1000H＋2000H＝3000H，根據實際地址訪問內存，獲取操作數4000H。

18某CPU主頻為1.03GHz，采用4級指令流水線，每個段的執行需要1個時鐘周期。假定CPU執行了100條指令，在其執行過程中沒有發生任何流水線阻塞，此時流水線的吞吐率為（　　）

A．0.25×10⁹條指令/秒

B．0.97×10⁹條指令/秒

C．1.0×10⁹條指令/秒

D．1.03×10⁹條指令/秒

【答案】C

【解析】采用4級流水線執行100條指令，在執行過程中共用4＋（100－1）＝103個時鐘周期。CPU的主頻是1.03GHz，也就是說每秒鐘有1.03G個時鐘周期。流水線的吞吐率為1.03G*100/103＝1.0*10⁹條指令/秒，故答案為C。

19下列選項中，用于設備和控制器（I/O接口）之間互連的接口標準是（　　）

A．PCI

B．USB

C．AGP

D．PCI-Express

【答案】B

【解析】設備和設備控制器之間的接口是USB接口，其余選項不符合，故答案為B。

20下列選項中，用于提高RAID可靠性的措施有（　　）

I．磁盤鏡像

II．條帶化

III．奇偶校驗

IV．增加Cache機制

A．僅I、II

B．僅I、III

C．僅I、III和IV

D．僅II、III和IV

【答案】B

【解析】能夠提高RAID可靠性的措施主要是對磁盤進行鏡像處理和進行奇偶校驗。其余選項不符合條件。

21某磁盤的轉速為10，000轉/分，平均尋道時間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個4KB的扇區所需平均時間約為（　　）

A．9ms

B．9.4ms

C．12ms

D．12.4ms

【答案】B

【解析】磁盤轉速是10 000轉/分鐘，平均轉一轉的時間是6ms，因此平均查詢扇區的時間是3ms，平均尋道時間是6ms，讀取4KB扇區信息的時間為0.2ms，信息延遲的時間為0.2ms，總時間為3＋6＋0.2＋0.2＝9.4 ms。

22下列關于中斷I/O方式和DMA方式比較的敘述中，錯誤的是（　　）

A．中斷I/O方式請求的是方式請求的是CPU處理時間，DMA方式請求的是總線使用權

B．中斷響應發生在一條指令執行結束后，中斷響應發生在一條指令執行結束后，DMA響應發生在一個總線事務完成后

C．中斷I/O方式下數據傳送通過軟件完成，方式下數據傳送通過軟件完成，DMA方式下數據傳送由硬件完成

D．中斷I/O方式適用于所有外部設備，方式適用于所有外部設備，DMA方式僅適用于快速外部設備

【答案】D

【解析】中斷處理方式:在I/O設備輸入每個數據的過程中，由于無需CPU干預，因而可使CPU與I/O設備并行工作。僅當輸完一個數據時，才需CPU花費極短的時間去做些中斷處理。因此中斷申請使用的是CPU處理時間，發生的時間是在一條指令執行結束之后，數據是在軟件的控制下完成傳送。而DMA方式與之不同。DMA方式：數據傳輸的基本單位是數據塊，即在CPU與I/O設備之間，每次傳送至少一個數據塊，DMA方式每次申請的是總線的使用權，所傳送的數據是從設備直接送入內存的或者相反；僅在傳送一個或多個數據塊的開始和結束時，才需CPU干預，整塊數據的傳送是在控制器的控制下完成的。答案D的說法不正確。

23用戶在刪除某文件的過程中，操作系統不可能執行是（　　）

A．刪除此文件所在的目錄

B．刪除與此文件關聯的目錄項

C．刪除與此文件對應的控制塊

D．釋放與此文件關聯的內存級沖區

【答案】A

【解析】刪除文件不需要刪除文件所在的目錄，而文件的關聯目錄項和文件控制塊需要隨著文件一同刪除，同時釋放文件的關聯緩沖區。

24為支持CD-ROM中視頻文件的快速隨機播放，播放性能最好的文件數據塊組織方式是（　　）

A．連續結構

B．鏈式結構

C．直接索引結構

D．多級索引結鉤

【答案】A

【解析】為了實現快速隨機播放，要保證最短的查詢時間，即不能選取鏈表和索引結構，因此連續結構最優。

25用戶程序發出磁盤I/O請求后，系統的處理系統的處理流程是：用戶程序→系統調用處理程序→設備駱動程序→中斷處理程序。其中，計算數據所在磁盤的柱面號、磁頭號、扇區號的程序是（　　）

A．用戶程序

B．系統調用處理程序

C．設備驅動程序

D．中斷處理程序

【答案】C

【解析】計算磁盤號、磁頭號和扇區號的工作是由設備驅動程序完成的，所以答案選C。

26若某文件系統索引結點（inode）中有直接地址項和間接地址項，則下列選項中，與單個文件長度無關的因素是（　　）

A．索引結點的總數

B．間接地址索引的級數

C．地址項的個數

D．文件塊大小

【答案】A

【解析】根據文件長度與索引結構的關系可知，只有選項A是與單個文件長度無關的。

27設系統緩沖區和用戶工作均采單，從外讀入1個數據塊到系統緩沖區的時間為100，從系統緩沖區讀入1個數據塊到用戶工作區的時間為5，對用戶工作區中的1個數據塊行分析的時間為90（如下圖所示）。進程從外設讀入并分析2個數據塊的最短時間是（　　）

A．200

B．295

C．300

D．390

【答案】C

【解析】數據塊1從外設到用戶工作區的總時間為105，在這段時間中數據塊2沒有進行操作。在數據塊1進行分析處理時，數據塊2從外設到用戶工作區的總時間為105，這段時間是并行的。再加上數據塊2進行處理的時間90，總共是300，故答案為C。

28下列選項中，會導致用戶進程從態切換到內核的操作是（　　）

I．整數除以零

II．sin（）函數調用

III．read系統調用

A．僅I、II

B．僅I、III

C．僅II、III

D．I、II和III

【答案】B

【解析】對于I，系統發生異常，需要進入內核態由操作系統進行處理，而read系統調用函數也是在內核態執行，sin（）就是普通的用戶函數，在用戶態執行，不會切換到內核，故答案為B。

29計算機開后，操作系統最終被加載到（　　）

A．BIOS

B．ROM

C．EPROM

D．RAM

【答案】D

【解析】系統開機后，操作系統的程序會被自動加載到內存中的系統區，這段區城是RAM，故答案選D。

30若用戶進程訪問內存時產生缺頁，則下列選項中，操作系統可能執行的是（　　）

I．處理越界錯

II．置換頁

III．分配內存

A．僅I、II

B．僅II、III

C．僅I、III

D．I、II和III

【答案】B

【解析】用戶進程訪問內存時缺頁會發生缺頁中斷。發生缺頁中斷，系統地執行的操作可能是置換頁面或分配內存。系統內沒有越界的錯誤，不會進行越界出錯處理。

31某系統正在執行三個進程P1、P2和P3，各進程的計算（CPU）時間和I/O時間比例如下表所示。

為提高系統資源利用率，合理的進程優先級設置應（　　）

A．P1＞P2＞P3

B．P3＞P2＞P1

C．P2＞P1＝P3

D．P1＞P2＝P3

【答案】B

【解析】為了合理地設置進程優先級，應該將進程的CPU利用時間和I/O時間做綜合考慮，故答案選B。

32下列關于銀行家算法的敘述中，正確的是（　　）

A．銀行家算法可以預防死鎖

B．當系統處于安全狀態時，系統中一定無死鎖進程

C．當系統處于不安全狀態時，系統中一定會出現死鎖進程

D．銀行家算法破壞了死鎖必要條件中的“請求和保持”條件

【答案】B

【解析】銀行家算法是避免死鎖的方法。利用銀行家算法，系統處于安全狀態時沒有死鎖進程，故答案選B。

33在OSI參考摸型中，下列功能需由應用層的相鄰層實現的是（　　）

A．對話管理

B．數據格式轉換

C．路由選擇

D．可靠數據傳輸

【答案】B

【解析】應用層的相鄰層即為表示層，表示層負責管理數據的壓縮、加密與解密、格式裝換等，故答案為B。

34若下圖為10BaseT網卡接收到的信號波形，則該比特串是（　　）

A．00110110

B．10101101

C．01010010

D．11000101

【答案】A

【解析】以太網采用曼徹斯特編碼，其將一個碼元分成兩個相等的間隔，前一個間隔為高電平而后一個間隔為低電平表示1，反之則表示0。故根據波形圖，可得答案為A。

35主機甲通過1個路由器個路由器（存儲轉發方式）與主機乙互聯，兩段鏈路的數據傳輸速率均為10Mbps，主機甲分別采用報文交換和組大小為10kb的分組交換向主機乙發送1個大小為8Mb（1M＝106）的報文。若忽略鏈路傳播延遲、分組頭開銷和拆裝時間，則兩種交換方式完成該報文傳輸所需的總時間分別為（　　）

A．800ms、1600ms

B．801ms、1600ms

C．1600ms、800ms

D．1600ms、801ms

【答案】D

【解析】不進行分組時，發送一個報文的時延是8 Mb/10 Mb/s＝800 ms，在接收端接收此報文件的時延也是800ms共計1600ms。進行分組后發送一個報文的時延是10kb/10Mb/s＝1 ms，接收一個報文的時延也是1 ms，但是在發送第二個報文時，第一個報文已經開始接收。共計有800個分組，總時間為801 ms。

36下列介質訪問控制方法中，可能發生沖突的是（　　）

A．CDMA

B．CSMA

C．TDMAC

D．FDMA

【答案】B

【解析】介質訪向控制協議中能夠發生沖突的是CSMA協議，答案為B。

37HDLC37.HDLC37.HDLC協議對0111 1100 0111 1110組幀后對應的比特串為（　　）

A．011111000011111010

B．011111000111110101111110

C．01111100011111010

D．011111000111111001111101

【答案】A

【解析】HDLC協議對比特串進行組幀時，HDLC數據幀以位模式0111 1110標識每一個幀的開始和結束，因此在幀數據中凡是出現了5個連續的位“1”的時候，就會在輸出的位流中填充一個“0”。所以答案為A。

38對于100Mbps的以太網交換機，當輸出端口無排隊直通（cut-through switching）方式轉發一個以太網幀（不包括前導碼）時，引入的轉發延遲至少是（　　）

A．0μs

B．0.48μs

C．5.12μs

D．121.44μs

【答案】B

【解析】直通交換方式是指以太網交換機可以在各端口間交換數據。它在輸入端口檢測到一個數據包時，檢查該包的包頭，獲取包的目的地址，啟動內部的動態查找表轉換成相應的輸出端口，在輸入與輸出交叉處接通，把數據包直通到相應的端口，實現交換功能。通常情況下，直通交換方式只檢查數據包的包頭即前14個字節，由于不需要考慮前導碼，只需要檢測目的地址的6 B，所以最短的傳輸延遲是0.48μs。

39主機甲與乙之間已建立一個TCP連接，雙方持續有數據傳輸，且無差錯與丟失。若甲收到1個來自乙的TCP段，該段的序號為1913、確認序號為2046、有效載荷為100字節，則甲立即發送給乙的TCP段的序號和確認分別是（　　）

A．2046、2012

B．2046、2013

C．2047、2012

D．2047、2012

【答案】B

【解析】若甲收到1個來自乙的TCP段，該段的序號seq＝1913、確認序號ack＝2046、有效載荷為100 字節，則甲立即發送給乙的TCP段的序號seq1＝ack＝2046 和確認序號ack1＝seq＋100＝2013，答案為B。

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

I．只支持傳輸7比特ASCII碼內容

II．支持在郵件服務器之間發送郵件

III．支持從用戶代理向郵件服務器發送郵件

IV．支持從郵件服務器向用戶代理發送郵件

A．僅I、II和III

B．僅I、II和IV

C．僅I、III和IV

D．僅II、III和IV

【答案】A

【解析】根據下圖可知，SMTP協議支持在郵件服務器之間發送郵件，也支持從用戶代理向郵件服務器發送信息。SMTP協議只支持傳輸7比特的ASCII碼內容

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

41已知一個整數序列A＝（a₀，a₁，……，a_n－1），其中0≤a_i＜n（0≤i≤n），若存在a_p1＝a_p2＝……＝a_pm＝x且m＞n/2（0≤p_k≤n，1≤k≤m），則稱x為A的主元素。例如A＝（0，5，5，3，5，7，5，5），則稱5為主元素；又如A＝（0，5，5，3，5，1，5，7）則A中沒有主元素。假設A中的n個元素保存在一個一維數組中，請設計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出－1。要求：

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

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

（3）說明你所設計算法的時間復雜度和空間復雜度。

解：（1）算法的策略是從前向后掃描數組元素，標記出一個可能成為主元素的元素Num。然后重新計數，確認Num是否是主元素。

算法可分為以下兩步：

①選取候選的主元素：依次掃描所給數組中的每個整數，將第一個遇到的整數Num保存到c中，記錄Num的出現次數為1；若遇到的下一個整數仍等于Num，則計數加1否則計數減1；當計數減到0時，將遇到的下一個整數保存到c中，計數重新記為1，開始新一輪計數，即從當前位置開始重復上述過程，直到掃描完全部數組元素。

②判斷c中元素是否是真正的主元素，再次掃描該數組，統計c中元素出現的次數，若大于n/2，則為主元素；否則，序列中不存在主元素。

（2）算法實現如下：

（3）時間復雜度為O（n），空間復雜度為O（1）。

42（10分）設包含4個數據元素的集合S＝{“do”，“or”，“repeat”，“while”}，各元素的查找概率依次為：p1＝0.35，p2＝0.15，p3＝0.15，p4＝0.35。將S保存在一個長度為4的順序表中，采用折半查找法，查找成功時的平均查找長度為2.2。請回答：

（1）若采用順序存儲結構保存S，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？

（2）若采用鏈式存儲結構保存S，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？

解：（1）由于個元素的查找概率不同，很自然的把查找小的位置用于存放查找概率大的元素，故要使查找長度更短，應該采用順序存儲結構，數據元素按其查找概率降序排列。這樣查找成功時的平均查找長度ASL＝0.35*1＋0.35*2＋0.15*3＋0.15*4＝2.1。

（2）鏈式存儲則可以采用二叉鏈表存儲結構，構造二叉排序樹，元素存儲方式見下圖，

采用二叉排序樹的查找方法，查找成功時的平均查找長度ASL＝0.15*1＋0.35*2＋0.35*2＋0.15*5＝2.0。

43（9分）某32位計算機，CPU主頻為800MHz，Cache命中時的CPI為4，Cache塊大小為32字節；主存采用8體交叉存儲方式，每個體的存儲字長為32位、存儲周期為40ns；存儲器總線寬度為32位，總線時鐘頻率為200MHz，支持突發傳送總線事務。每次讀突發傳送總線事務的過程包括：送首地址和命令、存儲器準備數據、傳送數據。每次突發傳送32字節，傳送地址或32位數據均需要一個總線時鐘周期。請回答下列問題，要求給出理由或計算過程。

（1）CPU和總線的時鐘周期各為多少？總線的帶寬（即最大數據傳輸率）為多少？

（2）Cache缺失時，需要用幾個讀突發傳送總線事務來完成一個主存塊的讀取？

（3）存儲器總線完成一次讀突發傳送總線事務所需的時間是多少？

（4）若程序BP執行過程中，共執行了100條指令，平均每條指令需進行1.2次訪存，Cache缺失率為5%，不考慮替換等開銷，則BP的CPU執行時間是多少？

解：（1）因為CPU主頻為800MHz，故CPU的時鐘周期為：1/800MHz＝1.25ns。

總線時鐘頻率為200MHz，故總線的時鐘周期為：1/200MHz＝5ns。

總線寬度為32bit＝4B，故總線帶寬為4B/5ns＝800MB/s。

（2）因為Cache塊大小為32B，因此Cache缺失時需要一個讀突發傳送總線事務讀取一個貯存塊。

（3）一次讀突發傳送總線事務包括一次地址傳送和32B數據傳送：用1個總線時鐘周期傳輸地址；每隔40ns/8＝5ns啟動一個體工作（各進行1次存取），第一個體讀數據花費40ns，之后數據存取與數據傳輸重疊；用8個總線時鐘周期傳輸數據。讀突發傳送總線事務時間：5ns＋40ns＋8×5ns＝85ns。

（4）BP的CPU執行時間包括Cache命中時的指令執行時間和Cache缺失時帶來的額外開銷。即執行時間＝指令條數*CPI*時鐘周期*命中率＋訪存次數*缺失率*缺失損失。命中時的指令執行時間：100×4×1.25ns＝500ns。指令執行過程中 Cache缺失時的額外開銷1.2×100×5%×85ns＝510ns。BP的CPU執行時間：500ns＋510ns＝1010ns。

44（14分）某計算機采用16位定長指令字格式，其CPU中有一個標志寄存器，其中包含進位/借位標志CF、零標志ZF和符號標志NF。假定為該機設計了條件轉移指令，其格式如下：

其中，00000為操作碼OP；C、Z和N分別為CF、ZF和NF的對應檢測位，某測位為1時表示需檢測對應標志，需檢測的標志位中只要有一個為1就轉移，否則就不轉移，例如，若C＝1，Z＝0，N＝1，則需檢測CF和NF的值，當CF＝1或NF＝1時發生轉移；OFFSET是相對偏移量，用補碼表示。轉移執行時，轉移目標地址為（PC）＋2＋2×OFFSET；順序執行時，下條指令地址為（PC）＋2。請回答下列問題。

（1）該計算機存儲器按字節編址，還是按字編址？該條件轉移指令向后（反向）最多可跳轉最多少條指令？

（2）某條件轉移指令的地址為200CH，指令內容如下圖所示，若該執行時CF＝0，ZF＝0，NF＝1，則該指令執行后PC的值是多少？若該指令執行時CF＝1，ZF＝0Z，NF＝0，則該指令執行后PC的值又是多少？請給出計算過程。

（3）實現“無符號數比較小于等時轉移”功能的指令中，C、Z和N應各是什么？

（4）以下是該指令對應的數據通路示意圖，要求給出中部件①～③的名稱或功能說明。

解：（1）因為指令長度為16位且下條指令地址為（PC）＋2，故編址單位是字節。

題中給出偏移量OFFSET為8位補碼，其范圍為－128～127，故相對當前指令進行條件跳轉，向后最多可跳轉127條指令。

（2）指令中C＝0，Z＝1，N＝1，故應根據ZF和NF的值來判斷是否轉移。當CF＝0，ZF＝0，NF＝1時需轉移。已知指令中偏移量為1110 0011B＝E3H，符號擴展后為FFE3H，左移一位（乘2）后為FFC6H，故PC的值（即轉移目標地址）為200CH＋2＋FFC6H＝1FD4H當CF＝1，ZF＝0，NF＝0時不轉移。PC的值為200CH＋2＝200EH。

（3）指令中的C、Z和N應分別設置為C＝Z＝1，N＝0。

（4）部件①指令寄存器：用于存放當前指令；部件②移位寄存器：用于左移一位；部件③加法器：地址相加。

45（7分）某博物館最多可容納500人同時參觀，有一個出入口，該出入口一次僅允許個通過。參觀者的活動描述如下：

cobegin

參觀者進程i：

{

…

進門；

…

參觀；

…

出門；

…

}

coend

請添加必要的信號量和P、V（或wait（　　）、signal（　　））操作，以實現上述操作過程中的互斥與同步。

要求寫出完整的過程，說明信號量含義并賦初值。

解：

46（8分）某計算機主存按字節編址，邏輯地址和物理地址都是32位，頁表項大小為4字節。請回答下列問題。

（1）若使用一級頁表的分存儲管理方式，邏輯地址結構為：

則頁的大小是多少字節？頁表最大占用多少字節？

（2）若使用二級頁表的分存儲管理方式，邏輯地址結構為：

設邏輯地址為LA，請分別給出其對應的頁目錄號和表索引達式。

（3）采用（1）中的分頁存儲管理方式，一個代碼段起始邏輯地址為00008000H，其長度為8KB，被裝載到從物理地址00900000H開始的連續主存空間中。頁表從主存0020 0000H 0020 0000H開始的物理地址處連續存放，如下圖所示（地址大小自下向上遞增）。請計算出該代碼段對應的兩個頁表項物理地址、這中框號以及計算出該代碼段對應的兩個頁表項物理地址、這中框號以及計算出該代碼段對應的兩個頁表項物理地址、這兩個頁表項中的框號以及代碼頁面2的起始物理地址。

解：（1）因為頁內偏移量是12位，所以頁大小為4 KB。

頁表項數為232/4K＝220該一級頁表最大為220×4 B＝4 MB。

（2）頁目錄號可表示為：（（（unsigned int）（LA））＞＞22）&0x3FF。

頁表索引可表示為：（（（unsigned int）（LA））＞＞12）&0x3FF。

（3）代碼頁面1的邏輯地址為0000 8000H，表明其位于第8個頁處，對應頁表中的第8個頁表項，所以第8個頁表項的物理地址＝頁表起始地址＋8×頁表項的字節數＝0020 0000H＋8×4 ＝0020 0020H，如下圖所示。

47（9分）假設Internet的兩個自治系統構成網絡如題47圖所示，自治系統ASI由路由器R1連接兩個子網構成；自治系統AS2由路由器R2、R3互聯并連接3個子網構成。各子網地址、R2的接口名、R1與R3的部分接口IP地址如題47圖所示。請回答下列問題。

題47圖網絡拓撲結構

（1）假設路由表結構如下所示。請利用路由聚合技術，給出R2的路由表，要求包括到達題47圖中所有子網的路由，且路由表中的路由項盡可能少。

（2）若R2收到一個目的IP地址為194.17.20.200的IP分組，R2會通過哪個接口轉發該IP分組？

（3）R1與R2之間利用哪個路由協議交換信息？該路由協議的報文被封裝到哪個議的分組中進行傳輸？

解：

（1）在AS1中，子網153.14.5.0/25 和子網153.14.5.128/25可以聚合為子網 153.14.5.0/24，在AS2中，子網194.17.20.0/25和子網194.17.21.0/24可以聚合為子網194.17.20.0/23，但缺少194.17.20.128/25；子網194.17.20.128/25單獨連接到R2的接口E0。

于是可以得到R2的路由表如下：

（2）該IP分組的目的IP地址194.17.20.200與路由表中194.17.20.0/23和194.17.20.128/25兩個路由表項均匹配，根據最長匹配原則，R2將通過E0接口轉發該1P 分組。

（3）R1與R2之間利用BGP4（或BGP）交換路由信息；BGP4的報文被封裝到TCP協議段中進行傳輸。