第一部分　名?？佳姓骖}

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

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

1為解決計算機主機與打印機之間速度不匹配問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是（　?。?。

A．棧

B．隊列

C．樹

D．圖

【答案】B

【解析】這類問題一般都先分析題目中的數據具有什么操作特性或是結構特性比如“先進后出”“先進先出”等再判斷其邏輯結構。棧和隊列是操作受限的線性表，棧具有先進后出的特性而隊列具有先進先出的特性。由于本題中先進入打印數據緩沖區的文件先被打印，因此打印數據緩沖區具有先進先出性，則它的邏輯結構應該是隊列。

2設棧S和隊列Q的初始狀態均為空，元素a，b，c，d，e，f，g依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是b，d，c，f，e，a，g，則棧S的容量至少是（　　）。

A．1

B．2

C．3

D．4

【答案】C

【解析】由于棧具有先進后出的特性，隊列具有先進先出的特性，出隊順序即為人隊順序。在本題中，每個元素出棧S后立即進入隊列Q，出棧順序即為入隊順序，所以本題中隊列的作用形同虛設，根據題意出隊順序即為出棧順序。根據出棧順序可以分析各個元素進出棧的過程：第一個出棧元素為b，表明棧內還有元素a，b出棧前的深度為2；第二個出棧元素為d，棧內元素為a和c，d出棧前的深度為3；c出棧后，剩余元素為a，c出棧前的深度為2；f出棧后，剩余元素為a和e，f出棧前的深度為3；e出棧后，剩余元素為a，e出棧前的深度為2；a出棧后，無剩余元素，a出棧前的深度為1；g出棧后，無剩余元素，g出棧前的深度為1。所以棧容量至少是3。

3給定二叉樹如下圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷后的結點序列為3，1，7，5，6，2，4，則其遍歷方式是（　　）。

A．LRN

B．NRL

C．RLN

D．RNL

【答案】D

【解析】對“二叉樹”而言，一般有三條搜索路徑：

①先上后下的按層次遍歷；

②先左（子樹）后右（子樹）的遍歷；

③先右（子樹）后左（子樹）的遍歷。

其中第1種搜索路徑方式就是常見的層次遍歷，第2種搜索路徑方式包括常見的先序遍歷NLR、中序遍歷LNR、后序遍歷LRN，第3種搜索路徑方式則是不常使用的NRL、RNL、RLN。本題考查的是第3種搜索路徑方式的一種情況。根據遍歷的序列以及樹的結構圖，可以分析出該遍歷的順序是先右子樹再跟結點最后左子樹，故答案為D。

4下列二叉排序樹中，滿足平衡二叉樹定義的是（　　）。

【答案】B

【解析】平衡二叉樹是指左右子樹高度差（平衡因子）的絕對值不超過1的二叉樹。A項中根結點的平衡因子是2；B項中每個結點的平衡因子的絕對值均不超過1；C項中根結點的平衡因子是－2；D項中根結點的平衡因子是3。

5已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則該完全二叉樹的結點個數最多是（　?。?/p>

A．39

B．52

C．111

D．119

【答案】C

【解析】完全二叉樹的一個特點是：葉子結點只能出現在最下層和次下層。題目中沒有說明完全二叉樹的高度，首先由完全二叉樹的特點確定題目中樹的高度。根據題意，一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，可知此二叉樹的高度是6或7。題目中求二叉樹的結點數最多的情況，因此此完全二叉樹的高度為7。由于高度為7的完全二叉樹的前6層是一棵滿二叉樹，根據二叉樹的性質2可知，高度為6的滿二叉樹的結點數是2⁶－1＝63。又根據二叉樹的性質1可知，題目中二叉樹的第6層結點數是2⁵＝32個結點，已知有8個葉子結點，那么其余32－8＝24個結點均為分支結點，這些結點在第7層上最多有48個子結點（即葉子結點）。所以此二叉樹的結點數最多可達2⁶－1＋（2⁵－8）×2＝111。

6將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是（　　）。

Ⅰ．父子關系

Ⅱ．兄弟關系

Ⅲ．u的父結點與v的父結點是兄弟關系

A．只有Ⅰ

B．Ⅰ和Ⅱ

C．Ⅰ和Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】B

【解析】首先，在二叉樹中，若結點u是結點v的父結點的父結點，那么u和v的關系有如下4種情況：

接下來，根據森林與二叉樹的轉換規則，將這4種情況還原成森林中結點的關系。其中：

情況（1），在原來的森林中u是v的父結點的父結點；

情況（2），在森林中u是v的父結點；

情況（3），在森林中u是v的父結點的兄弟；

情況（4），在森林中u與v是兄弟關系。

由此可知，題目中的Ⅰ、Ⅱ是正確的。

7下列關于無向連通圖特性的敘述中，正確的是（　?。?/p>

Ⅰ．所有的頂點的度之和為偶數

Ⅱ．邊數大于頂點個數減1

Ⅲ．至少有一個頂點的度為1

A．只有Ⅰ

B．只有Ⅱ

C．Ⅰ和Ⅱ

D．Ⅰ和Ⅲ

【答案】A

【解析】在圖中，頂點的度TD（V_i）之和與邊的數目滿足關系式：

其中，n為圖的總結點數，e為總邊數。因此，Ⅰ項正確。對于Ⅱ、Ⅲ項中的特性不是一般無向連通圖的特性，可以輕松地舉出反例?！爸辽儆幸粋€頂點的度為1”的反例如下圖（1）所示，“邊數大于頂點個數減1”的反例如下圖（2）所示。

（1）

（2）

8下列敘述中，不符合m階B樹定義要求的是（　?。?。

A．根結點最多有m棵子樹

B．所有葉結點都在同一層上

C．各結點內關鍵字均升序或降序排列

D．葉結點之間通過指針鏈接

【答案】D

【解析】B樹就是指B-樹。根據B-樹的定義，m階B-樹中每個結點最多有m個分支，因此，根結點最多有m棵子樹，A項正確；B-樹中所有葉結點都在最底層，位于同一層，B項正確；結點內各關鍵字互不相等且有序排列，C項正確。但是，所有葉子結點之間通過指針鏈接，是B＋樹的定義，而B-樹中沒有。因此，D項是錯誤的。

9已知關鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關鍵字3，調整后的小根堆是（　?。?。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

【答案】A

【解析】在堆中插入或刪除一個元素后，將不再滿足堆的性質。為了使其成為新堆，在輸出堆頂元素后，需要調整剩余元素。具體過程如圖（1）～（5）所示，（1）為原堆，（2）為插入3后，（3）、（4）為調整過程，（5）為調整后的小根堆。

10若數據元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結果，則該排序算法只能是（　?。?。

A．起泡排序

B．插入排序

C．選擇排序

D．二路歸并排序

【答案】B

【解析】經過兩趟排序后，A項起泡排序的結果是兩個最小或最大的元素放到了序列的最終位置；B項插入排序的結果是前三個數有序即可；C項選擇排序結果是兩個最小的元素在最前面按順序排好；D項二路歸并排序的結果是長度為4的子序列有序，即前4個數排好序，接下來的4個數排好序。顯然題目中的元素序列只能是插入排序第二趟排序后的結果，因此，B項正確。

11馮·諾依曼計算機中指令和數據均以二進制形式存放在存儲器中，CPU區分它們的依據是（　　）。

A．指令操作碼的譯碼結果

B．指令和數據的尋址方式

C．指令周期的不同階段

D．指令和數據所在的存儲單元

【答案】C

【解析】在馮·諾依曼結構計算機中指令和數據均以二進制形式存放在同一個存儲器中，CPU可以根據指令周期的不同階段來區分是指令還是數據，通常在取指階段取出的是指令，其他階段（分析取數階段、執行階段）取出的是數據。所以，CPU區分指令和數據的依據是指令周期的不同階段。

12一個C語言程序在一臺32位機器上運行。程序中定義了3個變量x、Y和z，其中x和z為int型，Y為short型。當x＝127，Y＝－9時，執行賦值語句z＝x＋Y后，x、Y和z的值分別是（　　）。

A．x＝0000 007FH，Y＝FFFF FFF9H，z＝0000 0076H

B．x＝0000 007FH，Y＝FFFF FFF9H，z＝FFFF 0076H

C．x＝0000 007FH，Y＝FFFF FFF7H，z＝FFFF 0076H

D．x＝0000 007FH，Y＝FFFF FFF7H，z＝0000 0076H

【答案】D

【解析】當兩個不同長度的數據，要想通過算術運算得到正確的結果，必須將短字長數據轉換成長字長數據，這被稱為“符號擴展”。例如，x和z為int型，數據長32位，Y為short型，數據長16位，因此首先應將y轉換成32位的數據，然后再進行加法運算。運算采用補碼的形式，而x的補碼是0000 007FH，Y的補碼是FFFF FFF7H，所以x＋Y＝0000 0076H。

13浮點數加、減運算一般包括對階、尾數運算、規格化、舍入和判溢出等步驟。設浮點數的階碼和尾數均采用補碼表示，且位數分別為5位和7位（均含2位符號位）。若有兩個數X＝2⁷×29/32，Y＝2⁵×5/8，則用浮點加法計算X＋Y的最終結果是（　　）。

A．0011 1110 0010

B．0011 1010 0010

C．0100 0001 0001

D．發生溢出

【答案】D

【解析】浮點數加、減運算一般包括對階、尾數運算、規格化、舍入和判溢出等步驟，難點在對階、規格化、判溢出這三步。X和Y的階碼不同，所以應該先對階，對階原則為：小階向大階看齊。因此將Y對階后得到：Y＝2⁷×5/32，然后將尾數相加，得到尾數之和為：34/32。因為這是兩個同號數相加，尾數大于1，則需要右規，階碼加1。由于階碼的位數為5位，且含兩位符號位，即階碼的表示范圍在－8～＋7之間。而階碼本身等于7，再加1就等于8。因此，最終結果發生溢出。

14某計算機的Cache共有16塊，采用2路組相聯映射方式（即每組2塊）。每個主存塊大小為32字節，按字節編址。主存129號單元所在主存塊應裝入到的Cache組號是（　　）。

A．0

B．2

C．4

D．6

【答案】C

【解析】首先根據主存地址計算所在的主存塊號，然后根據組相聯映射的映射關系K＝I mod Q （K代表Cache的組號，I代表主存的塊號，Q代表Cache的組數）來計算Cache的組號。由于每個主存塊大小為32字節，按字節編址，那么主存129號單元所在的主存塊號是4，Cache共有16塊，采用2路組相聯映射方式（即每組2塊），故Cache有8組，按照上面的公式可以計算得到Cache的組號＝4 mod 8＝4。

15某計算機主存容量為64 KB，其中ROM區為4 KB，其余為RAM區，按字節編址。現要用2 K×8位的ROM芯片和4 K×4位的RAM芯片來設計該存儲器，則需要上述規格的ROM芯片數和RAM芯片數分別是（　　）。

A．1、15

B．2、15

C．1、30

D．2、30

【答案】D

【解析】主存儲器包括RAM和ROM兩部分，由于ROM區為4KB，則RAM區為60KB。存儲容量的擴展方法有字擴展、位擴展、字和位同時擴展三種。選用2K×8位的ROM芯片，只需采用2片芯片進行字擴展便可得到4KB的ROM區；選用4K×4位的RAM芯片，需采用（60）/4*2片芯片進行字和位同時擴展便可得60KB的RAM區。

16某機器字長16位，主存按字節編址，轉移指令采用相對尋址，由兩個字節組成，第1字節為操作碼字段，第2字節為相對位移量字段。假定取指令時，每取一個字節PC自動加1。若某轉移指令所在主存地址為2000H，相對位移量字段的內容為06H，則該轉移指令成功轉移后的目標地址是（　?。?。

A．2006H

B．2007H

C．2008H

D．2009H

【答案】C

【解析】相對尋址方式的有效地址EA＝（PC）＋D，其中PC為程序計數器，D為相對偏移量。主存按字節編址，取指令時，每取一個字節PC值自動加1。由于轉移指令由兩個字節組成，取出這條轉移指令之后的PC值自動加2，為2002H，故轉移的目標地址為2002H＋06H＝2008H。

17下列關于RISC的敘述中，錯誤的是（　?。?。

A．RISC普遍采用微程序控制器

B．RISC大多數指令在一個時鐘周期內完成

C．RISC的內部通用寄存器數量相對CISC多

D．RISC的指令數、尋址方式和指令格式種類相對CISC少

【答案】A

【解析】B項、C項、D項都是RISC的特點之一，所以它們都是正確的，只有A項是CISC的特點，因為RISC的速度快，所以普遍采用硬布線控制器，而非微程序控制器。

18某計算機的指令流水線由4個功能段組成，指令流經各功能段的時間（忽略各功能段之間的緩存時間）分別為90ns、80ns、70ns和60ns，則該計算機的CPU時鐘周期至少是（　?。?/p>

A．90ns

B．80ns

C．70ns

D．60ns

【答案】A

【解析】對于各功能段執行時間不同的指令流水線，計算機的CPU時鐘周期應當以最長的功能段執行時間為準。

19相對于微程序控制器，硬布線控制器的特點是（　　）。

A．指令執行速度慢，指令功能的修改和擴展容易

B．指令執行速度慢，指令功能的修改和擴展難

C．指令執行速度快，指令功能的修改和擴展容易

D．指令執行速度快，指令功能的修改和擴展難

【答案】D

【解析】在同樣的半導體工藝條件下，硬布線（組合邏輯）控制器的速度比微程序控制器的速度快。這是因為硬布線控制器的速度主要取決于邏輯電路的延遲，而微程序控制器增加了一級控制存儲器，執行的每條微指令都要從控制存儲器中讀取，影響了速度。由于硬布線控制器一旦設計完成就很難改變，所以指令功能的修改和擴展難。因此，硬布線控制器的特點是指令執行速度快，指令功能的修改和擴展難。

20假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10MHz，則總線帶寬是（　　）。

A．10MB/s

B．20MB/s

C．40MB/s

D．80MB/s

【答案】B

【解析】因為一個總線周期占用2個時鐘周期，完成一個32位數據的傳送。總線時鐘頻率為10MHz，時鐘周期為0.1μs，總線周期占用2個時鐘周期，為0.2μs。一個總線周期中并行傳輸4字節信息，則總線帶寬是4B÷0.2μs ＝20MB/s。

21假設某計算機的存儲系統由Cache和主存組成。某程序執行過程中訪存1000次，其中訪問Cache缺失（未命中）50次，則Cache的命中率是（　?。?。

A．5%

B．9.5%

C．50%

D．95%

【答案】D

【解析】Cache的命中率H＝N₁/（N₁＋N₂），其中N₁為訪問Cache的次數，N₂為訪存主存的次數，程序總訪存次數為N₁＋N₂，程序訪存次數減去失效次數就是訪問Cache的次數N_1，。所以根據公式可得：H＝（1000－50）/1000＝95%。

22下列選項中，能引起外部中斷的事件是（　?。?。

A．鍵盤輸入

B．除數為0

C．浮點運算下溢

D．訪存缺頁

【答案】A

【解析】所謂外部中斷是指由外部事件引起的中斷，在這4個選項中，只有鍵盤輸入是真正由外部事件引起的中斷。

23單處理機系統中，可并行的是（　?。?。

Ⅰ．進程與進程

Ⅱ．處理機與設備

Ⅲ．處理機與通道

Ⅳ．設備與設備

A．Ⅰ、Ⅱ和Ⅲ

B．Ⅰ、Ⅱ和Ⅳ

C．Ⅰ、Ⅲ和Ⅳ

D．Ⅱ、Ⅲ和Ⅳ

【答案】D

【解析】注意區分并發和并行。在單處理機系統中，進程只能并發。微觀上同一時刻占用處理機的進程只有一個，因此，進程之間不是并行的。通道是獨立于CPU控制的輸入/輸出的設備，處理機與通道兩者是可以并行。顯然，設備和設備之間也是可以并行的。

24下列進程調度算法中，綜合考慮進程等待時間和執行時間的是（　?。?。

A．時間片輪轉調度算法

B．短進程優先調度算法

C．先來先服務調度算法

D．高響應比優先調度算法

【答案】D

【解析】時間片輪轉法和先來先服務算法都是公平的方法，并未考慮進程等待時間和執行時間，而短進程優先考慮的是進程執行時間。最高響應比優先調度算法是最先執行響應比最高的進程（響應比＝1＋等待時間/估計運行時間）。該算法綜合了先來先服務（FCFS）和短作業優先（SJF）算法，FCFS只考慮每個作業的等待時間，而未考慮執行時間的長短。SJF只考慮執行時間的長短，而未考慮等待時間的長短，HRRN算法則同時考慮執行時間和等待時間。

25某計算機系統中有8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K最小值是（　?。?。

A．2

B．3

C．4

D．5

【答案】C

【解析】死鎖的抽屜原理一般描述是：將5個蘋果放進4個抽屜，那么，必然有1個抽屜中至少有2個蘋果。計算機系統的資源分配充分體現了這一原理?？疾爝M程運行的特點，只要有一個進程能夠運行，則運行結束后必然會歸還資源，其余的進程也就會得到滿足從而可以執行（這里考慮的資源主要是可重用的資源，不可重用的資源會消失，就不可用上述方法分析）。所以最少需要4個進程競爭使用，每個進程占用2臺打印機，此時會產生死鎖。

26分區分配內存管理方式的主要保護措施是（　?。?/p>

A．界地址保護

B．程序代碼保護

C．數據保護

D．棧保護

【答案】A

【解析】對于連續分配算法，無論固定分區或動態分區方法，程序都必須全部調入內存，不同的進程放于不同的內存塊中，相互之間不可越界，因此需要進行界地址保護。通常的界地址保護方法采用軟硬件結合的方法?？忌⒁獗绢}與虛擬存儲方法的區別。

27一個分段存儲管理系統中，地址長度為32位，其中段號占8位，則最大段長是（　?。?。

A．2⁸字節

B．2¹⁶字節

C．2²⁴字節

D．2³²字節

【答案】C

【解析】段內位移的最大值就是最大段長。段號長度占了8位，剩下32－8＝24位是段內位移空間，因此最大段長為2²⁴B。

28下列文件物理結構中，適合隨機訪問且易于文件擴展的是（　　）。

A．連續結構

B．索引結構

C．鏈式結構且磁盤塊定長

D．鏈式結構且磁盤塊變長

【答案】B

【解析】連續結構的優點是結構簡單，缺點是不易于文件擴展，不易隨機訪問。鏈式結構的優點是文件易于擴展，缺點是不易隨機訪問。索引結構的優點是具有鏈式結構的優點并克服了它的缺點，可隨機存取，易于文件擴展。

29假設磁頭當前位于第105道，正在向磁道序號增加的方向移動。現有一個磁道訪問請求，序列為35，45，12，68，110，180，170，195，采用SCAN調度（電梯調度）算法得到的磁道訪問序列是（　　）。

A．110，170，180，195，68，45，35，12

B．110，68，45，35，12，170，180，195

C．110，170，180，195，12，35，45，68

D．12，31，45，68，110，170，180，195

【答案】A

【解析】SCAN算法類似電梯工作原理，即朝一個固定方向前進，經過的磁道有訪問請求則馬上服務，直至到達一端頂點，再掉頭往回移動以服務經過的磁道，并這樣在兩端之間往返。因此，當磁頭從105道向序號增加的方向移動時，便會服務所有大于105的磁道號（從小到大的順序）；往回返時又會按照從大到小的順序進行服務。注意與循環掃描算法的區別，所以SCAN算法的訪問序列是：110，170，180，195，68，45，35，12。

30文件系統中，文件訪問控制信息存儲的合理位置是（　?。?。

A．文件控制塊

B．文件分配表

C．用戶口令表

D．系統注冊表

【答案】A

【解析】文件控制塊是文件存在的標志，文件的相關信息（基本信息、存取控制信息以及使用信息）都存儲在文件控制塊中，系統對文件的管理全是依靠文件控制塊里的信息。

31設文件F1的當前引用計數值為1，先建立F1的符號鏈接（軟鏈接）文件F2，再建立F1的硬鏈接文件F3，然后刪除F1。此時，F2和F3的引用計數值分別是（　　）。

A．0、1

B．1、1

C．1、2

D．2、1

【答案】B

【解析】為了使文件實現共享，通常在使用該形式文件系統的文件索引節點中設置一個鏈接計數字段，用來表示鏈接到本文件的用戶目錄項的數目（引用計數值），這是共享的一種方法。當新文件建立時，一般默認引用計數值為1。硬鏈接可以看作是已存在文件的另一個名字，新文件和被鏈接文件指向同一個節點，引用計數值加1。當刪除被鏈接文件時，只是把引用計數值減1，直到引用計數值為0時，才能真正刪除文件。軟鏈接又叫符號鏈接，在新文件中只包含了被鏈接文件的路徑名，新文件和被鏈接文件指向不同的節點。建立軟鏈接文件時，文件的引用計數值不會增加。在這種方式下，當被鏈接文件刪除時，新文件仍然是存在的，只不過是不能通過新文件的路徑訪問被鏈接文件而已。因此，在本題中，當建立F2時，F1和F2的引用計數值都為1。當再建立F3時，F1和F3的引用計數值就都變成了2。當后來刪除F1時，F3的引用計數值為2－1＝1。F2的引用計數值仍然保持不變，所以F2和F3的引用計數值分別是：1，1。

32程序員利用系統調用打開I/O設備時，通常使用的設備標識是（　?。?。

A．邏輯設備名

B．物理設備名

C．主設備號

D．從設備號

【答案】A

【解析】設備管理具有設備獨立性的特點，操作系統以系統調用方式提供給應用程序使用邏輯設備名來請求使用某類設備時，調用中使用的是邏輯設備名，例如LPT1或COM1等。而操作系統內部管理設備使用的是設備編號。

33在OSI參考模型中，自下而上第一個提供端到端服務的層次是（　?。?。

A．數據鏈路層

B．傳輸層

C．會話層

D．應用層

【答案】B

【解析】題目中指明了這一層能夠實現端到端傳輸，也就是端系統到端系統的傳輸，數據鏈路層主要負責傳輸路徑上相鄰結點間的數據交付，這些結點包括了交換機和路由器等數據通信設備，這些設備不能被稱為端系統，因此數據鏈路層不滿足題意。題目中指明了這一層能夠實現傳輸，會話層只是在兩個應用進程之間建立會話而已，應用層只是提供應用進程之間通信的規范，都不涉及傳輸。所以本題答案應該是B項。在OSI模型中網絡層提供的是主機到主機的通信服務。

34在無噪聲情況下，若某通信鏈路的帶寬為3kHz，采用4個相位，每個相位具有4種振幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是（　?。?/p>

A．12 kbps

B．24 kbps

C．48 kbps

D．96 kbps

【答案】B

【解析】首先要根據信道有無噪聲來確定是否采用奈奎斯特定理。解題難點在于離散數值的確定，先確定調制技術的碼元數，此處為4個相位乘以4種振幅，共16種，即該通信鏈路的最大數據傳輸速率＝2×3×log₂（4×4）＝6×4＝24kbps。

35數據鏈路層采用后退N幀（GBN）協議，發送方已經發送了編號為0～7的幀。當計時器超時，若發送方只收到0、2、3號幀的確認，則發送方需要重發的幀數是（　?。?。

A．2

B．3

C．4

D．5

【答案】C

【解析】后退N幀協議，即GO-BACK—N策略的基本原理是，當接收方檢測出失序的信息幀后，要求發送方重發最后一個正確接收的信息幀之后的所有未被確認的幀；或者當發送方發送了N個幀后，若發現該N幀的前一個幀在計時器超時后仍未返回其確認信息，則該幀被判為出錯或丟失，此時發送方就不得不重新發送出錯幀及其后的N幀。本題收到3號幀的確認，說明0，1，2，3號幀已經收到，丟失的是4，5，6，7號幀，共4幀。因此答案為C項。

36以太網交換機進行轉發決策時使用的PDU地址是（　?。?/p>

A．目的物理地址

B．目的IP地址

C．源物理地址

D．源IP地址

【答案】A

【解析】交換機會監測發送到每個端口的數據幀，通過數據幀中的有關信息（源結點的MAC地址、目的結點的MAC地址），就會得到與每個端口所連接結點的MAC地址，并在交換機的內部建立一個“端口-MAC地址”映射表。建立映射表后，當某個端口接收到數據幀后，交換機會讀取出該幀中的目的結點的MAC地址，并通過“端口-MAC地址”的對應關系，迅速將數據幀轉發到相應的端口，注意這里的交換機工作在數據鏈路層，因此關于IP地址的選項是不對的，因此答案為A。

37在一個采用CSMA/CD協議的網絡中，傳輸介質是一根完整的電纜，傳輸速率為1Gbps，電纜中的信號傳播速度是200000km/s。若最小數據幀長度減少800bit，則最遠的兩個站點之間的距離至少需要（　?。?/p>

A．增加160m

B．增加80m

C．減少160m

D．減少80m

【答案】D

【解析】以太網采用CSMA/CD訪問協議，在發送的同時要進行沖突檢測，這就要求在能檢測出沖突的最大時間內數據包不能夠發送完畢，否則沖突檢測不能有效地工作。所以，當發送的數據包太短時必須進行填充。最小幀長度＝碰撞窗口大小×報文發送速率，本題最小數據幀長度減少800b，那么碰撞的窗口也要減少，因此距離也要減少，從而（800×2×10⁸）/（1×10⁹）＝160m，由于時間延時存在兩倍的關系，因此減少的距離為80m。

38主機甲和主機乙間已建立一個TCP連接，主機甲向主機乙發送了兩個連續的TCP段，分別包含300字節和500字節的有效載荷，第一個段的序列號為200，主機乙正確接收到兩個段后，發送給主機甲的確認序列號是（　　）。

A．500

B．700

C．800

D．1000

【答案】D

【解析】TCP使用滑動窗口流控協議，窗口大小的單位是字節，本題中分別包含300字節和500字節的有效載荷，第一個段的序列號為200，那么確認序列號為200＋300＋500＝1000。

39一個TCP連接總是以1KB的最大段發送TCP段，發送方有足夠多的數據要發送。當擁塞窗口為16KB時發生了超時，如果接下來的4個RTT（往返時間）時間內的TCP段的傳輸都是成功的，那么當第4個RTT時間內發送的所有TCP段都得到肯定應答時，擁塞窗口大小是（　?。?。

A．7KB

B．8KB

C．9KB

D．16KB

【答案】C

【解析】回顧TCP流量控制和擁塞控制（慢啟動）的知識點，從第一個MSS開始，每次發送成功，擁塞窗口值翻倍，四次以后，應該為16，但是由于擁塞閾值變為16/2＝8，故三次成功后為8，以后為線性增長，故為8＋1＝9，答案為C。

40FTP客戶和服務器間傳遞FTP命令時，使用的連接是（　　）。

A．建立在TCP之上的控制連接

B．建立在TCP之上的數據連接

C．建立在UDP之上的控制連接

D．建立在UDP之上的數據連接

【答案】A

【解析】對于FTP，為了保證可靠性，選擇TCP。FTP應用需要建立兩條TCP連接：一條為控制連接，另一條為數據連接。FTP服務器打開21號端口，被動的等待客戶的連接建立請求?？蛻魟t以主動方式與服務器建立控制連接，客戶通過控制連接將命令傳給服務器，而服務器則通過控制連接將應答傳給客戶，命令和響應都是以NVTASCII形式表示的。

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

41（10分）帶權圖（權值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑，假設從初始頂點到目標頂點之間存在路徑，現有一種解決該問題的方法：

①該最短路徑初始時僅包含初始頂點，令當前頂點為初始頂點；

②選擇離υ最近且尚未在最短路徑中的頂點ν，加入到最短路徑中，修改當前頂點υ＝ν；

③重復步驟②，直到υ是目標頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則請舉例說明。

解：題目中方法不一定能（或不能）求得最短路徑。舉例說明：

圖（a）中，假設初始頂點1到目標頂點4之間有一條邊，權值x＝2。顯然圖（a）中這頂點1和頂點4之間的最短路徑長度為2。若按照題目中給定的方法找到的路徑為初始頂點1經過中間結點2、3到目標頂點4，即初始頂點1—2—3—目標頂點4，所經過的邊的權值分別為y₁＝1、y₂＝1、y₃＝1。顯然，y₁＋y₂＋y₃＝3大于2。因此按照題目中給定的方法所求得的路徑并不是這兩個頂點之間的最短路徑。

圖（b）中，假設初始頂點為1、目標頂點為4，欲求從頂點1到頂點4之間的最短路徑。顯然，按照題目中給定的方法無法求出頂點1到頂點4的路徑，而事實上頂點1到頂點4的最短路徑為1到4。

42（15分）已知一個帶有表頭結點的單鏈表，結點結構為，假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點（k為正整數）。若查找成功，算法輸出該結點的data域的值，并返回1；否則，只返回0。要求：

（1）描述算法的基本設計思想；

（2）描述算法的詳細實現步驟；

（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C＋＋或JAVA語言實現），關鍵之處請給出簡要注釋。

解：（1）算法的基本設計思想定義兩個指針變量p和q，初始時均指向頭結點的下一個結點。p指針沿鏈表移動；當p指針移動到第k個結點時，q指針開始與p指針同步移動；當p指針移動到鏈表最后一個結點時，因為p和q相隔k，故q指針所指元素為倒數第k個結點。以上過程對鏈表僅進行一遍掃描。

（2）算法的詳細實現步驟

①count＝0，p和q指向鏈表表頭結點的下一個結點；

②若p為空，轉⑤；

③若count等于k，則q指向下一個結點；否則，count＝count＋1；

④p指向下一個結點，轉步驟②；

⑤若count等于k，則查找成功，輸出該結點的data域的值，返回1；否則，查找失敗，返回0；

⑥算法結束。

（3）算法實現

43（8分）某計算機的CPU主頻為500MHz，CPI為5（即執行每條指令平均需要5個時鐘周期）。假定某外設的數據傳輸率為0.5 MB/s，采用中斷方式與主機進行數據傳送，以32位為傳輸單位，對應的中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執行時間。請回答下列問題，要求給出計算過程。

（1）在中斷方式下，CPU用于該外設I/O的時間占整個CPU時間的百分比是多少？

（2）當該外設的數據傳輸率達到5MB/s時，改用DMA方式傳送數據。假定每次DMA傳送塊大小為5000B，且DMA預處理和后處理的總開銷為500個時鐘周期，則CPU用于該外設I/O時間占整個CPU時間的百分比是多少？（假設DMA與CPU之間沒有訪存沖突）

解：（1）已知主頻為500MHz，則時鐘周期＝1÷500MHz ＝2ns，因為CPI＝5，所以每條指令平均5×2＝10ns。又已知每中斷一次傳送32位（4個字節），數據傳輸率為0.5MB/s，所以傳送時間＝4÷0.5MB/s＝8μs。CPU用于該外設I/O共需20條指令（中斷服務程序包括18條指令＋其他開銷折合2條指令），花費時間＝20×10＝200ns。CPU用于該外設I/O的時間占整個CPU時間的百分比＝（200/8000）×100%＝0.025×100%＝2.5%。

（2）改用DMA方式傳送數據，數據傳輸率為5MB/s，傳送5000B的時間＝5000B÷5MB/s＝1ms。預處理和后處理的總開銷時間＝500×2ns＝1μs。CPU用于該外設I/O時間占整個CPU時間的百分比＝預處理和后處理的總開銷時間÷傳送數據的時間＝（1/1000）×100%＝0.001×100%＝0.1%。

44（13分）某計算機字長16位，采用16位定長指令字結構，部分數據通路結構如下圖所示，圖中所有控制信號為1時表示有效，為0時表示無效，例如控制信號MDRinE為1表示允許數據從DB打入MDR，MDRin為1表示允許數據從內總線打入MDR。假設MAR的輸出一直處于使能狀態。加法指令“ADD（R1），R0”的功能為（R0）＋（（R1））－（R1），即將R0中的數據與R1的內容所指主存單元的數據相加，并將結果送入R1的內容所指主存單元中保存。

下表給出了上述指令取指和譯碼階段每個節拍（時鐘周期）的功能和有效控制信號，請按表中描述方式用表格列出指令執行階段每個節拍的功能和有效控制信號。

解：執行階段每個節拍（時鐘周期）的功能和有效控制信號見下表。

45（7分）三個進程P1、P2，P3互斥使用一個包含N（N＞0）個單元的緩沖區。P1每次用produce（）生成一個正整數并用put（）送入緩沖區某一空單元中；P2每次用getodd（）從該緩沖區中取出一個奇數并用countodd（）統計奇數個數；P3每次用geteven（）從該緩沖區中取出一個偶數并用counteven（）統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義信號量的含義。要求用偽代碼描述。

解：定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產者與消費者之間的同步；mutex控制進程間互斥使用緩沖區，程序如下：

46（8分）請求分頁管理系統中，假設某進程的頁表內容如下表所示：

頁面大小為4KB，一次內存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（已含更新TLB和頁表的時間），進程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設①TLB初始為空；②地址轉換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；③有效位為0表示頁面不在內存，產生缺頁中斷，缺頁中斷處理后，返回到產生缺頁中斷的指令處重新執行。設有虛地址訪問序列2362H、1565H、25A5H，請問：

（1）依次訪問上述三個虛地址，各需多少時間？給出計算過程。

（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。

解：（1）210ns；10⁸ns；110ns。

頁面大小為4KB，因此，虛地址的低12位是頁內偏移，其余高位是頁號。

訪問虛地址2362H，虛頁號為2，頁內偏移362H。查找TLB，TLB初始為空，未命中，耗時10ns；訪問頁表，2號頁面所在頁框號為254H，耗時100ns；計算得到的物理地址254362H，訪問內存，耗時100ns。因此，總共用時10＋100＋100＝210ns。

訪問虛地址1565H，虛頁號為1，頁內偏移565H。查找TLB，未命中，耗時10ns；訪問頁表，有效位是0，未命中，耗時100ns；產生缺頁中斷，進行缺頁中斷處理，耗時108ns；采用LRU置換算法，虛頁1裝入頁幀號101H，缺頁中斷處理完后，再次訪問頁表，命中，耗時100ns；計算得到物理地址101565H，再次訪問內存，耗時100ns。因此，總共用時10＋100＋10⁸＋100≈10⁸ns。

訪問虛地址25A5H，虛頁號為2，頁內偏移5A5H。查找TLB，命中，耗時10ns；虛頁2對應的頁幀為254H，因此計算得物理地址為2545A5H，訪問內存，耗時100ns。因此，總共用時10＋100＝110ns。

（2）當訪問虛地址1565H時，產生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據題目的置換算法，應淘汰0號頁面，因此1565H的對應的頁框號為101H，故可知虛地址1565H的物理地址為101565H。

47（9分）某公司網絡拓撲圖如下圖所示，路由器R1通過接口E1、E2分別連接局域網1、局域網2，通過接口10連接路由器R2，并通過路由器R2連接域名服務器與互聯網。R1的10接口的IP地址是202.118.2.1；R2的10接口的IP地址是202.118.2.2，11接口的IP地址是130.11.120.1，E0接口的IP地址是202.118.3.1；域名服務器的IP地址是202.118.3.2。

R1和R2的路由表結構為：

（1）將IP地址空間202.118.1.0/24劃分為兩個子網，分配給局域網1、局域網2，每個局域網分配的地址數不少于120個，請給出子網劃分結果。說明理由或給出必要的計算過程。

（2）請給出R1的路由表，使其明確包括到局域網1的路由、局域網2的路由、域名服務器的主機路由和互聯網的路由。

（3）請采用路由聚合技術，給出R2到局域網1和局域網2的路由。

解：（1）把IP地址空間202.118.1.0/24劃分為2個等長的字網。兩個局域網的IP地址數都不能少于120個，所以劃分子網后，IP中主機所占的位數不能少于7位，要劃分為兩個子網又子少需要1位。可以將IP地址空間202.118.1.0/24的最后一個字節，劃分為1位和7位兩個部分，高一位表示子網號，低7位表示主機號，故劃分結果為:

①子網1：子網地址為202.118.1.0，子網掩碼為255.255.255.128（或者子網1：202.118.1.0/25）。

②子網2：子網地址為202.118.1.128，子網掩碼為255.255.255.128（或者子網1：202.118.1.128/25）。地址分配方案：子網1分配給局域網1，子網2分配給局域網2；或子網1分配給局域網2，子網2分配給局域網1。每個子網可分配的地址數為2⁷－2＝126大于120滿足題目要求。

（2）填寫到局域網1和局域網2的路由。兩個局域網的網絡地址和掩碼在問題（1）已經求出來了，分別為202.118.1.0/25和202.118.1.128/25。則R1路由表應該填入的網絡地址為202.118.1.0和202.118.1.128，掩碼為255.255.255.128和255.255.255.0。由于兩個局域網是分別直接連接到路由器R1的E1口、E2口上的，因此，下一跳地址填寫直接路由（Direct）。接口填寫E1、E2。

填寫到域名服務器的路由。由于圖6給出了域名服務器的IP地址為202.118.3.2，而該地址為主機地址，因此掩碼為255.255.255.255。同時，路由器R1要到DNS服務器，就需要通過路由器R2的接口L0才能到達，因此下一跳地址填寫L0的IP地址（202.118.2.2）。

填寫互聯網路由。本題的實質是編寫默認路由，默認路由叫做“0/0”路由，因為路由的IP地址是0.0.0.0，而子網掩碼也是0.0.0.0。同時路由器R1連接的網絡需要通過路由器R2的L0口才能到達互聯網絡，因此下一跳地址填寫L0的IP為202.118.2.2。

綜合以上敘述，所填寫的路由表如下表所示：

參考答案一

（若子網1分配給局域網1。子網2分配給局域網2）

參考答案二

（若子網1分配給局域網2，子網2分配給局域網1）

（3）填寫R2到局域網1和局域網2的路由表2。局域網1和局域網2的地址可以聚合為202.118.1.0/24，而R2去往局域網1和局域網2都是同一條路徑。因此，路由表里面只需要填寫到202.118.1.0/24網絡的路由即可，如下表所示：

R2路由表