2013年全國碩士研究生入學(xué)統(tǒng)一考試計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解

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

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

A．O（n）

B．O（m*n）

C．O（min（m，n））

D．O（max（m，n））

【答案】D

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

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

A．n－3

B．n－2

C．n－1

D．無法確定

【答案】C

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

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

A．0

B．1

C．2

D．3

【答案】D

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

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

A．27

B．46

C．54

D．56

【答案】B

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

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

A．X的父結(jié)點

B．以Y為根的子樹的最左下結(jié)點

C．X的左兄弟結(jié)點Y

D．以Y為根的子樹的最右下結(jié)點

【答案】A

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

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

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

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

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

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

A．僅I、III

B．僅I、IV

C．僅II、III

D．僅II、IV

【答案】C

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

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

A．1，2，1，2

B．2，2，1，1

C．3，4，2，3

D．4，4，2，2

【答案】C

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

8若對如下無向圖進(jìn)行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是（　　）

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(chǎn)，b，c，d，h，e，f，g

【答案】D

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

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

A．c和e

B．d和e

C．f和d

D．f和h

【答案】C

【解析】根據(jù)AOE網(wǎng)的定義可知，同時縮短幾條關(guān)鍵路徑上的活動時間，可以縮短整個工期。

10在一株高度為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是（　　）

A．5

B．7

C．8

D．14

【答案】A

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

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

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

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

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

該機(jī)的MIPS數(shù)是（　　）

A．100

B．200

C．400

D．600

【答案】C

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

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

A．－1.5×2¹³

B．－1.5×2¹²

C．－0.5×2¹³

D．－0.5×2¹²

【答案】A

【解析】IEEE754單精度浮點數(shù)格式為C640 0000H表示為二進(jìn)制格式為1100 0110 0100 0000 0000 0000 0000 0000，轉(zhuǎn)換為標(biāo)準(zhǔn)的格式為：

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

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

A．11000000

B．00100100

C．10101010

D．溢出

【答案】A

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

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

A．2

B．3

C．4

D．5

【答案】C

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

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

則對虛擬地址03FF F180H進(jìn)行虛實地址變換的結(jié)果是（　　）

A．015 3180H

B．003 5180H

C．TLB缺失

D．缺頁

【答案】A

【解析】虛擬地址為03FF F180H，其中頁號為03FFFH，頁內(nèi)地址為180H，根據(jù)題目中給出的頁表項可知頁標(biāo)記為03FFFH 所對應(yīng)的頁框號為0153H，頁框號與頁內(nèi)地址之和即為物理地址015 3180H。

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

A．1000H

B．2000H

C．3000H

D．4000H

【答案】D

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

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

A．0.25×109條指令/秒

B．0.97×109條指令/秒

C．1.0×109條指令/秒

D．1.03×109條指令/秒

【答案】C

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

19下列選項中，用于設(shè)備和控制器（I/O接口）之間互連的接口標(biāo)準(zhǔn)是（　　）

A．PCI

B．USB

C．AGP

D．PCI-Express

【答案】B

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

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

I．磁盤鏡像

II．條帶化

III．奇偶校驗

IV．增加Cache機(jī)制

A．僅I、II

B．僅I、III

C．僅I、III和IV

D．僅II、III和IV

【答案】B

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

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

A．9ms

B．9.4ms

C．12ms

D．12.4ms

【答案】B

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

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

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

B．中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，DMA響應(yīng)發(fā)生在一個總線事務(wù)完成后

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

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

【答案】D

【解析】中斷處理方式:在I/O設(shè)備輸入每個數(shù)據(jù)的過程中，由于無需CPU干預(yù)，因而可使CPU與I/O設(shè)備并行工作。僅當(dāng)輸完一個數(shù)據(jù)時，才需CPU花費極短的時間去做些中斷處理。因此中斷申請使用的是CPU處理時間，發(fā)生的時間是在一條指令執(zhí)行結(jié)束之后，數(shù)據(jù)是在軟件的控制下完成傳送。而DMA方式與之不同。DMA方式：數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊，即在CPU與I/O設(shè)備之間，每次傳送至少一個數(shù)據(jù)塊，DMA方式每次申請的是總線的使用權(quán)，所傳送的數(shù)據(jù)是從設(shè)備直接送入內(nèi)存的或者相反；僅在傳送一個或多個數(shù)據(jù)塊的開始和結(jié)束時，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送是在控制器的控制下完成的。答案D的說法不正確。

23用戶在刪除某文件的過程中，操作系統(tǒng)不可能執(zhí)行是（　　）

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

B．刪除與此文件關(guān)聯(lián)的目錄項

C．刪除與此文件對應(yīng)的控制塊

D．釋放與此文件關(guān)聯(lián)的內(nèi)存級沖區(qū)

【答案】A

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

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

A．連續(xù)結(jié)構(gòu)

B．鏈?zhǔn)浇Y(jié)構(gòu)

C．直接索引結(jié)構(gòu)

D．多級索引結(jié)鉤

【答案】A

【解析】為了實現(xiàn)快速隨機(jī)播放，要保證最短的查詢時間，即不能選取鏈表和索引結(jié)構(gòu)，因此連續(xù)結(jié)構(gòu)最優(yōu)。

25用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的處理系統(tǒng)的處理流程是：用戶程序→系統(tǒng)調(diào)用處理程序→設(shè)備駱動程序→中斷處理程序。其中，計算數(shù)據(jù)所在磁盤的柱面號、磁頭號、扇區(qū)號的程序是（　　）

A．用戶程序

B．系統(tǒng)調(diào)用處理程序

C．設(shè)備驅(qū)動程序

D．中斷處理程序

【答案】C

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

26若某文件系統(tǒng)索引結(jié)點（inode）中有直接地址項和間接地址項，則下列選項中，與單個文件長度無關(guān)的因素是（　　）

A．索引結(jié)點的總數(shù)

B．間接地址索引的級數(shù)

C．地址項的個數(shù)

D．文件塊大小

【答案】A

【解析】根據(jù)文件長度與索引結(jié)構(gòu)的關(guān)系可知，只有選項A是與單個文件長度無關(guān)的。

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

A．200

B．295

C．300

D．390

【答案】C

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

28下列選項中，會導(dǎo)致用戶進(jìn)程從態(tài)切換到內(nèi)核的操作是（　　）

I．整數(shù)除以零

II．sin（）函數(shù)調(diào)用

III．read系統(tǒng)調(diào)用

A．僅I、II

B．僅I、III

C．僅II、III

D．I、II和III

【答案】B

【解析】對于I，系統(tǒng)發(fā)生異常，需要進(jìn)入內(nèi)核態(tài)由操作系統(tǒng)進(jìn)行處理，而read系統(tǒng)調(diào)用函數(shù)也是在內(nèi)核態(tài)執(zhí)行，sin（）就是普通的用戶函數(shù)，在用戶態(tài)執(zhí)行，故答案為C。

29計算機(jī)開后，操作系統(tǒng)最終被加載到（　　）

A．BIOS

B．ROM

C．EPROM

D．RAM

【答案】D

【解析】系統(tǒng)開機(jī)后，操作系統(tǒng)的程序會被自動加載到內(nèi)存中的系統(tǒng)區(qū)，這段區(qū)城是RAM，故答案選D。

30若用戶進(jìn)程訪問內(nèi)存時產(chǎn)生缺頁，則下列選項中，操作系統(tǒng)可能執(zhí)行的是（　　）

I．處理越界錯

II．置換頁

III．分配內(nèi)存

A．僅I、II

B．僅II、III

C．僅I、III

D．I、II和III

【答案】B

【解析】用戶進(jìn)程訪問內(nèi)存時缺頁會發(fā)生缺頁中斷。發(fā)生缺頁中斷，系統(tǒng)地執(zhí)行的操作可能是置換頁面或分配內(nèi)存。系統(tǒng)內(nèi)沒有越界的錯誤，不會進(jìn)行越界出錯處理。

31某系統(tǒng)正在執(zhí)行三個進(jìn)程P1、P2和P3，各進(jìn)程的計算（CPU）時間和I/O時間比例如下表所示。

為提高系統(tǒng)資源利用率，合理的進(jìn)程優(yōu)先級設(shè)置應(yīng)（　　）

A．P1＞P2＞P3

B．P3＞P2＞P1

C．P2＞P1＝P3

D．P1＞P2＝P3

【答案】B

【解析】為了合理地設(shè)置進(jìn)程優(yōu)先級，應(yīng)該將進(jìn)程的CPU利用時間和I/O時間做綜合考慮，故答案選B。

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

A．銀行家算法可以預(yù)防死鎖

B．當(dāng)系統(tǒng)處于安全狀態(tài)時，系統(tǒng)中一定無死鎖進(jìn)程

C．當(dāng)系統(tǒng)處于不安全狀態(tài)時，系統(tǒng)中一定會出現(xiàn)死鎖進(jìn)程

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

【答案】B

【解析】銀行家算法是避免死鎖的方法。利用銀行家算法，系統(tǒng)處于安全狀態(tài)時沒有死鎖進(jìn)程，故答案選B。

33在OSI參考摸型中，下列功能需由應(yīng)用層的相鄰層實現(xiàn)的是（　　）

A．對話管理

B．?dāng)?shù)據(jù)格式轉(zhuǎn)換

C．路由選擇

D．可靠數(shù)據(jù)傳輸

【答案】B

【解析】應(yīng)用層的相鄰層即為表示層，表示層負(fù)責(zé)管理數(shù)據(jù)的壓縮、加密與解密、格式裝換等，故答案為B。

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

A．00110110

B．10101101

C．01010010

D．11000101

【答案】A

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

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

A．800ms、1600ms

B．801ms、1600ms

C．1600ms、800ms

D．1600ms、801ms

【答案】D

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

36下列介質(zhì)訪問控制方法中，可能發(fā)生沖突的是（　　）

A．CDMA

B．CSMA

C．TDMAC

D．FDMA

【答案】B

【解析】介質(zhì)訪向控制協(xié)議中能夠發(fā)生沖突的是CSMA協(xié)議，答案為B。

37HDLC37.HDLC37.HDLC協(xié)議對0111 1100 0111 1110組幀后對應(yīng)的比特串為（　　）

A．011111000011111010

B．011111000111110101111110

C．01111100011111010

D．011111000111111001111101

【答案】A

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

38對于100Mbps的以太網(wǎng)交換機(jī)，當(dāng)輸出端口無排隊直通（cut-through switching）方式轉(zhuǎn)發(fā)一個以太網(wǎng)幀（不包括前導(dǎo)碼）時，引入的轉(zhuǎn)發(fā)延遲至少是（　　）

A．0μs

B．0.48μs

C．5.12μs

D．121.44μs

【答案】B

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

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

A．2046、2012

B．2046、2013

C．2047、2012

D．2047、2012

【答案】B

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

40下列關(guān)于SMTP協(xié)議的敘述中，正確的是（　　）

I．只支持傳輸7比特ASCII碼內(nèi)容

II．支持在郵件服務(wù)器之間發(fā)送郵件

III．支持從用戶代理向郵件服務(wù)器發(fā)送郵件

IV．支持從郵件服務(wù)器向用戶代理發(fā)送郵件

A．僅I、II和III

B．僅I、II和IV

C．僅I、III和IV

D．僅II、III和IV

【答案】A

【解析】根據(jù)下圖可知，SMTP協(xié)議支持在郵件服務(wù)器之間發(fā)送郵件，也支持從用戶代理向郵件服務(wù)器發(fā)送信息。SMTP協(xié)議只支持傳輸7比特的ASCII碼內(nèi)容

二、綜合應(yīng)用題：41～47小題，共70分。

41已知一個整數(shù)序列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中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中，請設(shè)計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出－1。要求：

（1）給出算法的基本設(shè)計思想。

（2）根據(jù)設(shè)計思想，采用C或C＋＋或Java語言描述算法，關(guān)鍵之處給出注釋。

（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。

解：

（1）算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個可能成為主元素的元素Num。然后重新計數(shù)，確認(rèn)Num是否是主元素。

算法可分為以下兩步：

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

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

（2）算法實現(xiàn)如下：

（3）時間復(fù)雜度為O（n），空間復(fù)雜度為O（1）。

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

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

（2）若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)保存S，且要求平均查找長度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時的平均查找長度是多少？

解：

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

（2）鏈?zhǔn)酱鎯t可以采用二叉鏈表存儲結(jié)構(gòu)，構(gòu)造二叉排序樹，元素存儲方式見下圖，

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

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

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

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

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

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

解：

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

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

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

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

（3）一次讀突發(fā)傳送總線事務(wù)包括一次地址傳送和32B數(shù)據(jù)傳送：用1個總線時鐘周期傳輸?shù)刂罚幻扛?0ns/8＝5ns啟動一個體工作（各進(jìn)行1次存取），第一個體讀數(shù)據(jù)花費40ns，之后數(shù)據(jù)存取與數(shù)據(jù)傳輸重疊；用8個總線時鐘周期傳輸數(shù)據(jù)。讀突發(fā)傳送總線事務(wù)時間：5ns＋ 40ns ＋8×5ns＝85ns。

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

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

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

（1）該計算機(jī)存儲器按字節(jié)編址，還是按字編址？該條件轉(zhuǎn)移指令向后（反向）最多可跳轉(zhuǎn)最多少條指令？

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

（3）實現(xiàn)“無符號數(shù)比較小于等時轉(zhuǎn)移”功能的指令中，C、Z和N應(yīng)各是什么？

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

解：

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

題中給出偏移量OFFSET為8位補(bǔ)碼，其范圍為－128～127，故相對當(dāng)前指令進(jìn)行條件跳轉(zhuǎn)，向后最多可跳轉(zhuǎn)127條指令。

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

（3）指令中的C、Z和N應(yīng)分別設(shè)置為C＝Z＝1，N＝0。

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

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

cobegin

參觀者進(jìn)程i：

{

…

進(jìn)門；

…

參觀；

…

出門；

…

}

coend

請?zhí)砑颖匾男盘柫亢蚉、V（或wait（　　）、signal（　　））操作，以實現(xiàn)上述操作過程中的互斥與同步。

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

解：

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

（1）若使用一級頁表的分存儲管理方式，邏輯地址結(jié)構(gòu)為：

則頁的大小是多少字節(jié)？頁表最大占用多少字節(jié)？

（2）若使用二級頁表的分存儲管理方式，邏輯地址結(jié)構(gòu)為：

設(shè)邏輯地址為LA，請分別給出其對應(yīng)的頁目錄號和表索引達(dá)式。

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

解：

（1）因為頁內(nèi)偏移量是12位，所以頁大小為4 KB。

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

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

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

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

47（9分）假設(shè)Internet的兩個自治系統(tǒng)構(gòu)成網(wǎng)絡(luò)如題47圖所示，自治系統(tǒng)ASI由路由器R1連接兩個子網(wǎng)構(gòu)成；自治系統(tǒng)AS2由路由器R2、R3互聯(lián)并連接3個子網(wǎng)構(gòu)成。各子網(wǎng)地址、R2的接口名、R1與R3的部分接口IP地址如題47圖所示。請回答下列問題。

題47圖網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

（1）假設(shè)路由表結(jié)構(gòu)如下所示。請利用路由聚合技術(shù)，給出R2的路由表，要求包括到達(dá)題47圖中所有子網(wǎng)的路由，且路由表中的路由項盡可能少。

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

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

解：

（1）在AS1中，子網(wǎng)153.14.5.0/25 和子網(wǎng)153.14.5.128/25可以聚合為子網(wǎng) 153.14.5.0/24，在AS2中，子網(wǎng)194.17.20.0/25和子網(wǎng)194.17.21.0/24可以聚合為子網(wǎng)194.17.20.0/23，但缺少194.17.20.128/25；子網(wǎng)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 兩個路由表項均匹配，根據(jù)最長匹配原則，R2將通過E0接口轉(zhuǎn)發(fā)該1P 分組。

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