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

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

1求整數(shù)n（n≥0）階乘的算法如下，其時間復雜度是（　　）。

A．O（log₂n）

B．O（n）

C．O（nlog₂n）

D．O（n²）

【答案】B

【解析】設fact（n）的運行時間函數(shù)是T（n）。

該函數(shù)中語句①的運行時間是O（1），語句②的運行時間是T（n－1）＋O（1），其中O（1）為乘法運算的時間。

因此，當n≤1時，T（n）－O（1）；當n＞1時，T（n）＝T（n－1）＋O（1）。則，T（n）＝O（1）＋T（n－1）＝2×O（1）＋T（n－2）＝（n－1）×O（1）＋T（1）＝n×O（1）＝O（n），即fact（n）的時間復雜度為O（n）。

2已知操作符包括‘＋’、‘－’、‘*’、‘/’、‘（’和‘）’。將中綴表達式a＋b－a*（（c＋d）/e－f）＋g轉(zhuǎn)換為等價的后綴表達式ab＋acd＋e/f－*－g＋時，用棧來存放暫時還不能確定運算次序的操作符。若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是（　　）。

A．5

B．7

C．8

D．11

【答案】A

【解析】基本思想是：采用運算符棧是為了比較運算符的優(yōu)先級，所有運算符必須進棧。只將大于棧頂元素優(yōu)先級的運算符直接進棧，否則需要退棧棧頂運算符（先出棧的運算符先計算，同優(yōu)先級的運算符在棧中的先計算）。表達式a＋b－a*（（c＋d）/e－f）＋g產(chǎn)生后綴表達式的過程如下表所列：

通過上表可以看出，顯然轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是5。

3若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點的孩子結(jié)點（　　）。

A．只有e

B．有e、b

C．有e、c

D．無法確定

【答案】A

【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，其中a為這棵二叉樹的根結(jié)點，接下來，在前序遍歷的第二個結(jié)點為e，而后序遍歷的倒數(shù)第二個結(jié)點為e，說明a的孩子結(jié)點只有e。

4若平衡二叉樹的高度為6，且所有非葉結(jié)點的平衡因子均為1，則該平衡二叉樹的結(jié)點總數(shù)為（　　）。

A．12

B．20

C．32

D．33

【答案】B

【解析】本題題目的實際問題是，具有6層結(jié)點的平衡二叉樹含有最少的結(jié)點數(shù)是多少。 N_h表示深度為h的平衡二叉樹中含有的最少結(jié)點數(shù)，有N₀＝0，N₁＝1，N₂＝2……N_h＝N_h－1＋N_h－2＋1。

由此可得N₅＝20。對應的平衡二叉樹如下圖所示。

5對有2個頂點e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法時間復雜度是（　　）。

A．O（n）

B．O（e）

C．O（n＋e）

D．O（n×e）

【答案】C

【解析】遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結(jié)構。當用二維數(shù)組表示鄰接矩陣圖的存儲結(jié)構時，查找每個頂點的鄰接點所需時間為O（n²），其中n為圖中頂點數(shù)。而當以鄰接表作圖的存儲結(jié)構時，找鄰接點所需時間為O（e），其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當以鄰接表作存儲結(jié)構時，深度優(yōu)先搜索遍歷圖的時間復雜度為O（n＋e）。即可得出正確答案。

6若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結(jié)論是（　　）。

A．存在，且唯一

B．存在，且不唯一不唯一

C．存在，可能不唯一

D．無法確定是否存在

【答案】C

【解析】圖的基本應用——拓撲排序，用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，說明該圖為有向無環(huán)圖，所以其拓撲序列存在，但不一定唯一，如圖的鄰接矩陣為，則存在兩個拓撲序列。

7有向帶權圖如題7圖所示，若采用迪杰斯特拉（Dijkstra）算法求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是b，第二條最短路徑的目標頂點是c，后續(xù)得到的其余各最短路徑的目標頂點依次是（　　）。

題7圖　有向帶權圖

A．d， e， f

B．e，d，f

C．f，d，e

D．f，e，d

【答案】C

【解析】本題主要考查Dijkstra算法的思想和解題步驟。題目執(zhí)行算法過程中各步的狀態(tài)如下表所示。

執(zhí)行Dijkstra算法過程中各步的狀態(tài)表，故后續(xù)目標頂點依次為f，d，e。

8下列關于最小生成樹的敘述中，正確的是（　　）。

Ⅰ．最小生成樹的代價唯一

Ⅱ．所有權值最小的邊一定會出現(xiàn)在所有的最小生成樹中

Ⅲ．使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同

Ⅳ．使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅲ

D．僅Ⅱ、Ⅳ

【答案】A

【解析】當圖中存在相同權值的邊時，其最小生成樹可能是不唯一的，但最小生成樹的代價一定是相同的，所以說法Ⅰ正確。從n個頂點的連通圖中選取n－1條權值最小的邊可能構成回路，所以說法Ⅱ錯誤。當某個頂點有權值相同的邊，使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹并不一定相同，所以說法Ⅲ錯誤。當最小生成樹不唯一時，使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹可能相同，也可能不同，所以說法Ⅳ錯誤。由此可得出正確答案。

9設有一棵3階B樹，如題9圖所示。刪除關鍵字78得到一棵新B樹，其最右葉結(jié)點所含的關鍵字是（　　）。

題9圖　3階二叉樹圖

A．60

B．60，62

C．62，65

D．65

【答案】D

【解析】本題主要考查B樹刪除操作。即被刪關鍵字所在的結(jié)點中的關鍵字個數(shù)等于［m/2］－1，而與該結(jié)點相鄰的右兄弟（或左兄弟）結(jié)點中的關鍵字數(shù)目大于［m/2］－1，則需將其兄弟結(jié)點中最小（或最大）的關鍵字上移至雙親結(jié)點中，而將雙親結(jié)點中小于（或大于）且緊靠該上移關鍵字的關鍵字下移至被刪關鍵字所在結(jié)點中。題目中刪除關鍵字78得到一棵新B樹如下，其最右葉結(jié)點所含的關鍵字是65。

10排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（　　）。

Ⅰ．簡單選擇排序

Ⅱ．希爾排序

Ⅲ．快速排序

Ⅳ．堆排

V．二路歸并排序

A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ

D．僅Ⅲ、Ⅳ、Ⅴ

【答案】A

【解析】其中簡單選擇排序、堆排序?qū)儆谶x擇類排序，每一趟排序結(jié)束時將確定最大（或最小）關鍵字所在的位置。快速排序每一趟排序結(jié)束時將確定基準關鍵字所在的位置。希爾排序、二路歸并排序每一趟排序結(jié)束時不一定能確定一個元素的最終位置。

11對同一待排序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是（　　）。

A．排序的總趟數(shù)

B．元素的移動次數(shù)

C．使用輔助空間的數(shù)量

D．元素之間的比較次數(shù)

【答案】D

【解析】折半插入排序所需附加存儲空間和直接插入排序相同，從時間上比較，折半插入排序僅減少了關鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變。折半插入排序的時間復雜度仍為O（n²），所以兩者之間的不同只可能是元素之間的比較次數(shù)。

12假定基準程序A在某計算機上的運行時間為l00秒，其中90秒為CPU時間，其余為I/O時間。若CPU速度提高50%，I/O速度不變，則運行基準程序A所耗費的時間是（　　）。

A．55秒

B．60秒

C．65秒

D．70秒

【答案】D

【解析】CPU速度提高50%，即CPU性能提高比為l.5，改進之后的CPU運行時間＝90÷1.5＝60秒。I/O速度不變，仍維持l0秒，所以運行基準程序A所耗費的時間為70秒。

13假定編譯器規(guī)定int和short類型長度分別為32位和16位，執(zhí)行下列C語言語句：unsigned short X＝65530；unsigned int y＝X：得到y(tǒng)的機器數(shù)為（　　）。

A．0000 7FFAH

B．0000 FFFAH

C．FFFF 7FFAH

D．FFFF FFFAH

【答案】B

【解析】X和y均為無符號數(shù)，其中X為16位，y為32位，將16位無符號數(shù)轉(zhuǎn)化成32位無符號數(shù)，前面要補零。因為X＝65530＝FFFAH，所以y＝0000 FFFAH。

14float類型（即IEEE754單精度浮點數(shù)格式）能表示的最大正整數(shù)是（　　）。

A．2¹²⁶－2¹⁰³

B．2¹²⁷－2¹⁰⁴

C．2¹²⁷－2¹⁰³

D．2¹²⁸－2¹⁰⁴

【答案】D

【解析】IEEE754單精度浮點數(shù)尾數(shù)采用隱藏位策略的原碼表示，且階碼用移碼表示的浮點數(shù)。規(guī)格化的短浮點數(shù)的真值為：（－1）^S×1.f×2^{（E－127）}，S為符號位，E的取值為1～254，f為23位；故float類型能表示的最大整數(shù)是1.111^1×2（254－127）＝2¹²⁷×（2－2^－23）＝ 2¹²⁸－2¹⁰⁴。

15某計算機存儲器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存儲。某C語言程序段如下：

若record變量的首地址為0xC008，則地址0xC008中內(nèi)容及record.c的地址分別為（　　）。

A．0x00、0xC00D

B．0x00、0xC00E

C．0x11、0xC00D

D．0x11、0xC00E

【答案】D

【解析】32位整數(shù)a需要占4個字節(jié)，l6位整數(shù)c需要占2個字節(jié)，而字符數(shù)據(jù)b占一個字節(jié)。a＝273，轉(zhuǎn)換成十六進制是111H，采用小端方式存放數(shù)據(jù)，地址0xC008中的內(nèi)容為11H。由于數(shù)據(jù)按邊界對齊存儲，地址0xC008～OxC00B中存放a，地址0xC00C中存放b，地址0xC00D中空閑，地址0xC00E～0xC00F中存放c。

16下列關于閃存（Flash Memory）的敘述中，錯誤的是（　　）。

A．信息可讀可寫，并且讀、寫速度一樣快

B．存儲元由MOS管組成，是一種半導體存儲器

C．掉電后信息不丟失，是一種非易失性存儲器

D．采用隨機訪問方式，可替代計算機外部存儲器

【答案】A

【解析】考查閃存的特性，閃存是EEPROM的進一步發(fā)展，可讀可寫，用MOS管的浮柵上有無電荷來存儲信息，它依然是ROM的一種，故寫速度比讀速度要慢不少。閃存是一種非易失性存儲器，它采用隨機訪問方式，現(xiàn)在常見的SSD固態(tài)硬盤就是由flash芯片組成的，故答案為A。

17假設某計算機按字編址，Cache有4個行，Cache和主存之間交換的塊大小為l個字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方式和LRU替換算法，當訪問的主存地址依次為0，4，8，2，0，6，8，6，4，8時，命中Cache的次數(shù)是（　　）。

A．1

B．2

C．3

D．4

【答案】C

【解析】Cache有4個行，2路組相聯(lián)，即Cache被分成2組，每組2行。主存地址為0～1、4～5、8～9可映射到第0組Cache中，主存地址為2～3、6～7可映射到第1組Cache中。Cache初始為空，采用LRU替換算法，當訪問主存的10個地址依次為0，4，8，2，0，6，8，6，4，8時，命中Cache的次數(shù)共有3次，分別發(fā)生在第7、8和10步時。

18某計算機的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有33個微命令，構成5個互斥類，分別包含7、3、12、5和6個微命令，則操作控制字段至少有（　　）。

A．5位

B．6位

C．15位

D．33位

【答案】C

【解析】33個微命令分成5個互斥類（即5個字段），根據(jù)每個類中微命令的多少可以分別確定字段的長度為3、2、4、3、3位，又因為采用直接編碼方式，所以它們之和3＋2＋4＋3＋3＝15也就是操作控制字段的位數(shù)。

19某同步總線的時鐘頻率為l00MHz，寬度為32位，地址/數(shù)據(jù)線復用，每傳輸一個地址或數(shù)據(jù)占用一個時鐘周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫”總線事務傳輸l28位數(shù)據(jù)所需要的時間至少是（　　）。）。

A．20ns

B．40ns

C．50ns

D．80ns

【答案】C

【解析】總線的時鐘頻率為l00MHz，則時鐘周期為10ns。數(shù)據(jù)是128位，總線寬度是32位，所以需要4個時鐘周期，而傳輸?shù)刂愤€需要一個周期，所以傳輸一個128位的數(shù)據(jù)至少需要5個時鐘周期，所以至少需要10ns*5＝50ns。

20下列關于USB總線特性的描述中，錯誤的是（　　）。

A．可實現(xiàn)外設的即插即用和熱插拔

B．可通過級聯(lián)方式連接多臺外設

C．是一種通信總線，可連接不同外設

D．同時可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高

【答案】D

【解析】USB總線即通用串行總線，它的特點有：（1）即插即用；（2）熱插拔；（3）有很強的鏈接能力能將所有外設鏈接起來，且不損失帶寬；（4）有很好的可擴展性；（5）高速傳輸，速度可達480Mbps。所有A，B，C都符合USB總線的特點。對于選項D，USB是串行總線，不能同時傳輸兩位數(shù)據(jù)，所以答案為D。

21下列選項中，在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔ǎā　。?/p>

Ⅰ．I/O接口中的命令字

Ⅱ．I/O接口中的狀態(tài)字

Ⅲ．中斷類型號

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔↖/O接口中的命令字、狀態(tài)字以及真正的數(shù)據(jù)，而中斷類型號也是通過數(shù)據(jù)線傳輸?shù)摹?/p>

22響應外部中斷的過程中，中斷隱指令完成的操作，除保護斷點外，還包括（　　）。

Ⅰ．開關中斷

Ⅱ．保存通用寄存器的內(nèi)容

Ⅲ．形成中斷服務程序入口地址并送PC

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】中斷隱指令完成的操作有3個：①保存斷點；②關中斷；③引出中斷服務程序（形成中斷服務程序入口地址并送PC）。而保存通用寄存器內(nèi)容的操作是由軟件來實現(xiàn)，不是由中斷隱指令實現(xiàn)的。

23下列選項中，不可能在用戶態(tài)發(fā)生的事件是（　　）。

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

B．外部中斷

C．進程切換

D．缺頁

【答案】C

【解析】我們在學習操作系統(tǒng)中知道，任何一個進程在現(xiàn)代操作系統(tǒng)中為了共享和保護，設定了用戶態(tài)和內(nèi)核態(tài)（可以通過設置軟、硬件標志位來實現(xiàn)），在用戶態(tài)運行用戶的程序，在內(nèi)核運行系統(tǒng)的程序。所以，從選項來看，系統(tǒng)調(diào)用可以在任何態(tài)發(fā)生，用戶可以發(fā)起系統(tǒng)調(diào)用，系統(tǒng)也可以；外部中斷是不可控的，也會在任何時刻發(fā)生，缺頁的發(fā)生也是不可控的，可以發(fā)生在用戶代碼之間；而進程切換卻不會在用戶態(tài)發(fā)生。我們可以考慮一下情形，進程切換是在什么時候發(fā)生的，進程切換前必定運行的是進程調(diào)度，只有進程調(diào)度選擇了下一次被調(diào)度的進程，進程切換才可以進行。進程調(diào)度是scheduler，進程切換是dispather，這體現(xiàn)了現(xiàn)代操作系統(tǒng)策略與機制分離的設計思想。所以，進程切換必定不會在用戶態(tài)發(fā)生（所謂發(fā)生指其起始的源頭時刻），必定是在內(nèi)核態(tài)（進程調(diào)度）發(fā)生的。

24中斷處理和子程序調(diào)用都需要壓棧以保護現(xiàn)場，中斷處理一定會保存而子程序調(diào)用不需要保存其內(nèi)容的是（　　）。

A．程序計數(shù)器

B．程序狀態(tài)字寄存器

C．通用數(shù)據(jù)寄存器

D．通用地址寄存器

【答案】B

【解析】中斷處理與子程序調(diào)用最大的區(qū)別是中斷處理程序與正在運行的進程可能無關，而子程序調(diào)用與正在運行的進程有關。中斷是要打斷處理器的正常工作次序，并要求其去處理某一事件的一種常用手段。因此，除了要保護當前程序的地址，計數(shù)器（指針）和數(shù)據(jù)寄存器以外，還需要保存程序狀態(tài)字。子程序調(diào)用是與當前進程有關，是正在運行的程序有意安排執(zhí)行的，這一類調(diào)用發(fā)生的時間以及位置具有確定性，處于同一個進程內(nèi)，因此不需要保存程序狀態(tài)字。所以中斷處理和子程序調(diào)用不同的區(qū)別是中斷處理程序必定會保存程序狀態(tài)字寄存器。

25下列關于虛擬存儲的敘述中，正確的是（　　）。

A．虛擬存儲只能基于連續(xù)分配技術

B．虛擬存儲只能基于非連續(xù)分配技術

C．虛擬存儲容量只受外存容量的限制

D．虛擬存儲容量只受內(nèi)存容量的限制

【答案】D

【解析】所謂虛擬存儲，是指運行的進程不必全部裝入內(nèi)存，只需要部分裝入便可以開始運行的一種技術，在運行過程中，當所需要的代碼部分不在內(nèi)存時，通過一種技術（例如缺頁中斷技術），將所需要的頁面調(diào)入內(nèi)存，從而繼續(xù)運行。虛擬存儲可以在較少的內(nèi)存中運行較大的程序。但是需要有較大的外存以及相應的軟、硬件機制配合才能實現(xiàn)。虛擬存儲器可以連續(xù)分配也可以非連續(xù)分配，虛擬存儲器和外存大小沒有關系，所以選項中的A，B，C都是錯誤的，所以答案是D項。

26操作系統(tǒng)的I/O子系統(tǒng)通常由四個層次組成，每一層明確定義了與鄰近層次的接口。其合理的層次組織排列順序是（　　）。

A．用戶級I/O軟件、設備無關軟件、設備驅(qū)動程序、中斷處理程序

B．用戶級I/O軟件、設備無關軟件、中斷處理程序、設備驅(qū)動程序

C．用戶級I/O軟件、設備驅(qū)動程序、設備無關軟件、中斷處理程序

D．用戶級I/O軟件、中斷處理程序、設備無關軟件、設備驅(qū)動程序

【答案】A

【解析】對于一次設備的調(diào)用，操作系統(tǒng)為用戶準備了系統(tǒng)調(diào)用的接口，當用戶使用設備時，首先在用戶程序中發(fā)起一次系統(tǒng)調(diào)用，操作系統(tǒng)的設備無關層軟件接到該調(diào)用請求后調(diào)用處理程序進行處理，根據(jù)調(diào)用格式和形參，再轉(zhuǎn)到相應的設備驅(qū)動程序去處理；大部分設備在運行時是需要時間的，所以設備驅(qū)動程序會以中斷方式驅(qū)動設備，即設置好控制寄存器參數(shù)和中斷向量等參數(shù)后阻塞自己；當設備準備好或所需數(shù)據(jù)到達后設備硬件發(fā)出中斷，設備驅(qū)動程序喚醒，將數(shù)據(jù)按上述調(diào)用順序逆向回傳到用戶程序中，或繼續(xù)驅(qū)動設備執(zhí)行下一條指令。因此，I/O軟件從上到下分為四個層次：用戶層、與設備無關的軟件層、設備驅(qū)動程序以及中斷處理程序。

27假設5個進程P0、P1、P2、P3、P4共享三類資源Rl、R2、R3，這些資源總數(shù)分別為l8、6、22。T₀時刻的資源分配情況如題27表所示，此時存在的一個安全序列是（　　）。

題27表　資源分配情況表

A．P0，P2，P4，P1，P3

B．P1，P0，P3，P4，P2

C．P2，P1，P0，P3，P4

D．P3，P4，P2，P1，P0

【答案】D

【解析】典型的死鎖避免算法、銀行家算法的應用。本題的題型與2011年的27題相似。銀行家算法是操作系統(tǒng)中的一個重點知識單元，考生對此應該非常熟悉，本題并無難點。分析一下下表，可以看到，P3，P4，P2，P1，P0運行是可以的。

本題也可以排除法，T₀時刻可用資源是R1，R2，R3分別為2，3，3，此時刻，P0需要R1，R2，R3分別為2，3，7，故排除A，P1需要R1，R2，R3分別為1，3，3，P2還需要資源R1，R2，R3分別為0，0，6，故C排除，P3需要R1，R2，R3分別為2，2，1。所以正確答案在B，D之間。看B選項，P1之后的可用資源R1，R2，R3分別變?yōu)?，3，6，而P0尚需資源2，3，7，故B方案行不通。因而最終答案只有D項。

28若一個用戶進程通過read系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)據(jù)，則下列關于此過程的敘述中，正確的是（　　）。

Ⅰ．若該文件的數(shù)據(jù)不在內(nèi)存，則該進程進入睡眠等待狀態(tài)；

Ⅱ．請求read系統(tǒng)調(diào)用會導致CPU從用戶態(tài)切換到核心態(tài)；

Ⅲ．read系統(tǒng)調(diào)用的參數(shù)應包含文件的名稱

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】A

【解析】對于Ⅰ，當所讀文件的數(shù)據(jù)不再內(nèi)存時，產(chǎn)生中斷（缺頁中斷、缺段中斷），原進程進入睡眠等待狀態(tài)（阻塞狀態(tài)），直到所需數(shù)據(jù)從外村調(diào)入內(nèi)存后，將該進程喚醒，使其變?yōu)榫途w狀態(tài)。對于Ⅱ，read系統(tǒng)調(diào)用CPU將從用戶態(tài)切換到核心態(tài)，從而獲取操作系統(tǒng)提供的服務。對于Ⅲ，在操作系統(tǒng)中，要讀一個文件首先要open系統(tǒng)調(diào)用將該文件打開。Open系統(tǒng)調(diào)用的參數(shù)需要包含文件的路徑名與文件名，而read系統(tǒng)調(diào)用只需使用open返回的文件描述符，并不使用文件名作為參數(shù)。Read系統(tǒng)調(diào)用要求用戶提供三個輸入?yún)?shù)：①文件描述符；②buf緩沖區(qū)首址；③傳送的字節(jié)數(shù)n。read系統(tǒng)調(diào)用的功能是試圖從fd所指示的文件中讀入n個字節(jié)的數(shù)據(jù)，并將它們送至由指針buf所指示的緩沖區(qū)中。

29一個多道批處理系統(tǒng)中僅有P1和P2兩個作業(yè)，P2比P1晚5ms到達。它們的計算和I/O操作順序如下：P1：計算60ms，I/O 80ms，計算20ms；P2：計算120ms，I/O 40ms，計算40ms若不考慮調(diào)度和切換時間，則完成兩個作業(yè)需要的時間最少是（　　）。

A．240ms

B．260ms

C．340ms

D．360ms

【答案】B

【解析】考查處理系統(tǒng)的性能計算，由于P2比P1晚5ms到達，P1先占用CPU，根據(jù)P1和P2的執(zhí)行過程，作業(yè)運行的甘特圖如下所示，故答案為B。

30若某單處理器多進程系統(tǒng)中有多個就緒態(tài)進程，則下列關于處理機調(diào)度的敘述中，錯誤的是（　　）。

A．在進程結(jié)束時能進行處理機調(diào)度

B．創(chuàng)建新進程后能進行處理機調(diào)度

C．在進程處于臨界區(qū)時不能進行處理機調(diào)度

D．在系統(tǒng)調(diào)用完成并返回用戶態(tài)時能進行處理機調(diào)度

【答案】C

【解析】對于A、B、D顯然是可以進行處理機調(diào)度的，對于C，當進程處于臨界區(qū)時，只要不破壞臨界資源的使用規(guī)則，是不會影響處理機調(diào)度的，比如，通常訪問臨界資源可能是慢速的外設（如打印機），如果在進程訪問打印機時，不能處理機調(diào)度，那么系統(tǒng)的性能將是非常低的。幾種不進行處理機調(diào)度的情況如下：①在處理機中斷的過程中；②進程在操作系統(tǒng)內(nèi)核程序臨界區(qū)中；③其他需要完全屏蔽中斷的原子操作過程中。

31下列關于進程和線程的敘述中，正確的是（　　）。

A．不管系統(tǒng)是否支持線程，進程都是資源分配的基本單位

B．線程是資源分配的基本單位，進程是調(diào)度的基本單位

C．系統(tǒng)級線程和用戶級線程的切換都需要內(nèi)核的支持

D．同一進程中的各個線程擁有各自不同的地址空間

【答案】A

【解析】利用排除法來確定正確答案：“線程是資源分配的基本單位，進程是調(diào)度的基本單位”這句話說反了，明顯錯誤。“系統(tǒng)級線程和用戶級線程的切換都需要內(nèi)核的支持”也不正確，因為用戶級線程的切換由用戶編寫的Runtime System執(zhí)行的，內(nèi)核并不感知。“同一進程中的各個線程擁有各自不同的地址空間”明顯錯誤，引入線程的目的就是為了同一進程的所有線程能共享進程的地址空間，故“不管系統(tǒng)是否支持線程，進程都是資源分配的基本單位”是正確的。

32下列選項中，不能改善磁盤設備I/O性能的是（　　）。

A．重排I/O請求次序

B．在一個磁盤上設置多個分區(qū)

C．預讀和滯后寫

D．優(yōu)化文件物理塊的分布

【答案】B

【解析】磁盤I/O性能主要是指其讀寫速度。相對而言，磁盤的I/O性能是計算機性能提高的一個瓶頸。“重排I/O請求次序”可以優(yōu)化磁臂調(diào)度的算法，減少讀寫時間，故正確；“預讀和滯后寫”是利用內(nèi)存作為磁盤的緩存，使得對磁盤的訪問變?yōu)閷?nèi)存的訪問，也可以在總體上提高其性能；“優(yōu)化文件物理塊的分布”減少磁臂調(diào)度和旋轉(zhuǎn)調(diào)度的等待時間，也可以提高磁盤I/O性能，而磁盤分區(qū)僅在磁盤空間的組織上進行劃分，對磁盤I/O性能的提升沒有什么幫助，是不能改善磁盤設備I/O性能的，故答案為B。

33在TCP/IP體系結(jié)構中，直接為ICMP提供服務的協(xié)議是（　　）。

A．PPP

B．IP

C．UDP

D．TCP

【答案】B

【解析】首先明確ICMP是網(wǎng)絡層的協(xié)議，由于服務必須是下一層向上一層提供服務的，因此選項C項中的UDP和選項D項中的TCP屬于傳輸層，在網(wǎng)絡層上面，所以顯然錯誤，而PPP協(xié)議是廣域網(wǎng)數(shù)據(jù)鏈路層協(xié)議，直接為網(wǎng)絡層，也就是IP層提供服務，ICMP協(xié)議是封裝在網(wǎng)絡層，因此PPP不能直接為ICMP提供服務，ICMP報文直接封裝在IP分組中，故答案是B。

34在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（　　）。

A．機械特性

B．功能特性

C．過程特性

D．電氣特性

【答案】C

【解析】物理層的主要任務描述為確定與傳輸媒體接口的一些特性；機械特性：主要定義物理連接的邊界點，即接插裝置；電氣特性：規(guī)定傳輸二進制位時，線路上信號的電壓高低、阻抗匹配、傳輸速率和距離限制；功能特性：主要定義各條物理線路的功能；規(guī)程特性：主要定義各條物理線路的工作規(guī)程和時序關系。而從題干可以分析描述事件先后順序的就是規(guī)程，也就是過程特性，答案是C。

35以太網(wǎng)的MAC協(xié)議提供的是（　　）。

A．無連接不可靠服務

B．無連接可靠服務

C．有連接不可靠服務

D．有連接可靠服務

【答案】A

【解析】考查以太網(wǎng)MAC協(xié)議，考慮到局域網(wǎng)信道質(zhì)量好，以太網(wǎng)采取了兩項重要的措施以使通信更簡潔：①采用無連接的工作方式；②不對發(fā)送的數(shù)據(jù)幀進行編號，也不要求對方發(fā)回確認。因此，以太網(wǎng)提供的服務是不可靠的服務，即盡最大努力交付，差錯的糾正由高層完成。

36兩臺主機之間的數(shù)據(jù)鏈路層采用后退N幀協(xié)議（GBN）傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為l6kbps，單向傳播時延為270ms，數(shù)據(jù)幀長度范圍是128～512字節(jié)，接收方總是以與數(shù)據(jù)幀等長的幀進行確認。為使信道利用率達到最高，幀序號的比特數(shù)至少為（　　）。

A．5

B．4

C．3

D．237

【答案】B

【解析】GBN的工作原理如下圖所示，本題求解的是發(fā)送一個幀到接收到這個幀的確認期間最多可以發(fā)送多少數(shù)據(jù)幀，要盡可能多發(fā)送幀，應以短的數(shù)據(jù)幀計算，注意幀的單位是字節(jié)，因此首先計算出發(fā)送一幀的時間t1＝128×8/16kbps＝64ms，故發(fā)送一幀到收到確認為止的總時間為；64＋270*2＋64＝668ms，這段時間總共可以發(fā)送668/64＝10.4（幀），為了保證發(fā)送幀序號和確認幀序號在此期間不重復，因此幀序號的比特數(shù)至少為4，答案為B

37下列關于IP路由器功能的描述中，正確的是（ 　 ）。

Ⅰ．運行路由協(xié)議，設置路由表；

Ⅱ．監(jiān)測到擁塞時，合理丟棄IP分組；

Ⅲ．對收到的IP分組頭進行差錯校驗，確保傳輸?shù)腎P分組不丟失；

Ⅳ．根據(jù)收到的IP分組的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上。

A．僅Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅰ、Ⅱ、Ⅳ

D．Ⅰ、Ⅱ、Ⅲ、Ⅳ

【答案】C

【解析】路由器的主要功能是路由和轉(zhuǎn)發(fā)，因此Ⅰ和Ⅳ是正確的，而針對Ⅱ和Ⅲ，可以從ICMP協(xié)議的差錯控制出發(fā)，注意檢測到擁塞時，合理丟棄IP分組，并回傳ICMP源抑制報文，Ⅱ是正確的，而Ⅲ對收到的IP分組頭進行差錯校驗，確保傳輸?shù)腎P分組不丟失，差錯校驗是正確的，但網(wǎng)絡層不保證IP分組不丟失，也就是不可靠的，因此Ⅲ的說法錯誤，正確的說法僅Ⅰ、Ⅱ、Ⅳ，因此答案是C。

38ARP協(xié)議的功能是（　　）。

A．根據(jù)IP地址查詢MAC地址

B．根據(jù)MAC地址查詢IP地址

C．根據(jù)域名查詢IP地址

D．根據(jù)IP地址查詢域名

【答案】A

【解析】ARP協(xié)議是網(wǎng)絡層協(xié)議，因此只能和傳輸層和數(shù)據(jù)鏈路層有關系，從這一點出發(fā)，域名是應用層的范疇，選項C和D是不正確的，根據(jù)MAC地址查詢IP地址是RARP協(xié)議的功能，因此進而得出正確答案是A。

39某主機的IP地址為180.80.77.55，子網(wǎng)掩碼為255.255.252.0。若該主機向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（　　）。

A．180.80.76.0

B．180.80.76.255

C．180.80.77.255

D．180.80.79.255

【答案】D

【解析】IPv4地址中的特殊地址，直接廣播地址，也就是把主機位全部設置為1，這里77的二進制是01001101，子網(wǎng)掩碼252的二進制是11111100，由此可以看到77的前6位作為子網(wǎng)位，后四位作為主機位，由此可以知道其廣播地址是l80.80.01001111.255，也就是l80.80.79.255，因此答案是D。

40若用戶1與用戶2之間發(fā)送和接收電子郵件的過程如題40圖所示，則圖中①、②、③階段分別使用的應用層協(xié)議可以是（　　）。

題40圖　電子郵件發(fā)送接收示意圖

A．SMTP、SMTP、SMTP

B．POP3、SMTP、POP3

C．POP3、SMTP、SMTP

D．SMTP、SMTP、POP3

【答案】D

【解析】題中電子郵件的工作過程如下：

①用戶1調(diào)用用戶代理來編輯要發(fā)送的郵件，用戶代理用SMTP將郵件傳送給用戶1的發(fā)送端郵件服務器。

②發(fā)送端郵件服務器也就是用戶1的郵件服務器將郵件放入郵件緩存隊列中，等待發(fā)送。

③運行在發(fā)送端郵件服務器的SMTP客戶進程，發(fā)現(xiàn)在郵件緩存中有待發(fā)送的郵件，就向運行在接收端郵件服務器也就是用戶2的郵件服務器的SMTP服務器進程發(fā)起TCP連接建立。當TCP連接建立后，SMTP客戶進程開始向遠程的SMTP服務器發(fā)送郵件。當所有的待發(fā)郵件發(fā)完了，SMTP就關閉所建立的TCP連接。

④運行在接收端郵件服務器中的SMTP服務器進程收到郵件后，將郵件放人收信人的用戶郵箱中，等待收信人在他方便時進行讀取。收信人在打算收信時，調(diào)用用戶代理，使用POP協(xié)議將自己的郵件從接收端郵件服務器的用戶郵箱中取回（如果郵箱中有來信的話）。

因此題中1，2，3階段分別使用的應用層協(xié)議可以是SMTP，SMTP，POP3，因此答案是D。SMTP采用“推”的通信方式，用于用戶代理向郵件服務器發(fā)送郵件、以及郵件服務器之間發(fā)送郵件。POP3采用“拉”的通信方式，用于用戶從目的郵件服務器上讀取郵件。

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

41（10分）設有6個有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個表最終合并成1個升序表，并在最壞情況下比較的總次數(shù)達到最小。請回答下列問題。

（1）給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。

（2）根據(jù)你的合并過程，描述n（n≥2）個不等長升序表的合并策略，并說明理由。

解：

（1）6個表的合并順序如下圖所示。

對應于合并過程的哈夫曼樹

根據(jù)上圖中的哈夫曼樹，6個序列的合并過程為：

第1次合并：表A與表B合并，生成含45個元素的表AB；

第2次合并：表AB與表C合并，生成含85個元素的表ABC；

第3次合并：表D與表E合并，生成含110個元素的表DE；

第4次合并：表ABC與表DE合并，生成含195個元素的表ABCDE；

第5次合并：表ABCDE與表F合并，生成含395個元素的最終表。

由于合并兩個長度分別為m和n的有序表，最壞情況下需要比較m＋n－1次，故最壞情況下比較的總次數(shù)計算如下：

第1次合并：最多比較次數(shù)＝10＋35－1＝44；

第2次合并：最多比較次數(shù)＝45＋40－1＝84；

第3次合并：最多比較次數(shù)＝50＋60－1＝109；

第4次合并：最多比較次數(shù)＝85＋110－1＝194；

第5次合并：最多比較次數(shù)＝195＋200－1＝394；比較的總次數(shù)最多為：44＋84＋109＋194＋394＝825。

（2）各表的合并策略是：在對多個有序表進行兩兩合并時，若表長不同，則最壞情況下總的比較次數(shù)依賴于表的合并次序。可以借用哈夫曼樹的構造思想，依次選擇最短的兩個表進行合并，可以獲得最壞情況下最佳的合并效率。

解析：本題具有較強的綜合性，主要考查了構造哈夫曼樹的算法思想和過程、歸并排序的過程等。

42（13分）假定采用帶頭結(jié)點的單鏈表保存單詞，當兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如，“l(fā)oading”和“being”的存儲映像如題42圖所示。

題42圖　存儲映像示意圖

設str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構為[data，next]，請設計一個時間上盡可能高效的算法，找出由str1和str2所指的兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點的位置p）。要求：

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

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

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

解：

（1）算法的基本設計思想：

①分別求出str1和str2所指的兩個鏈表的長度m和n；

②將兩個鏈表以表尾對齊：令指針p、q分別指向str1和str2的頭結(jié)點，若m＞n，則使p指向鏈表中的第n＋1個結(jié)點；若m＜n，則使q指向鏈表中的第m＋1個結(jié)點，即使指針p和q所指的結(jié)點到表尾的長度相等。

③反復將指針p和q同步向后移動，并判斷它們是否指向同一結(jié)點。若p和q指向同一結(jié)點，則該點即為所求的共同后綴的起始位置。

（2）用C語言算法描述如下：

（3）參考答案的時間復雜度為：O（m＋n）或O（max（m，n））。其中m、n分別為兩個鏈表的長度。

43（11分）假定某計算機的CPU主頻為80MHz，CPI為4，并且平均每條指令訪存1.5次，主存與Cache之間交換的塊大小為168，Cache的命中率為99%，存儲器總線寬度為32位。請回答下列問題。

（1）該計算機的MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA傳送的情況下，主存帶寬至少達到多少才能滿足CPU的訪存要求？

（2）假定在Cache缺失的情況下訪問主存時，存在0.0005%的缺頁率，則CPU平均每秒產(chǎn)生多少次缺頁異常？若頁面大小為4KB，每次缺頁都需要訪問磁盤，訪問磁盤時DMA傳送采用周期挪用方式，磁盤I/O接口的數(shù)據(jù)緩沖寄存器為32位，則磁盤I/O接口平均每秒發(fā)出的DMA請求次數(shù)至少是多少？

（3）CPU和DMA控制器同時要求使用存儲器總線時，哪個優(yōu)先級更高？為什么？

（4）為了提高性能，主存采用4體交叉存儲模式，工作時每l/4個存儲周期啟動一個體。若每個體的存儲周期為50ns，則該主存能提供的最大帶寬是多少？

解：

（1）平均每秒CPU執(zhí)行的指令數(shù)為：80M/4＝20M，故MIPS數(shù)為20；

平均每秒Cache缺失的次數(shù)為：20M×1.5×（1－99%）＝300000；

當Cache缺失時，CPU訪問主存，主存與Cache之間以塊為單位傳送數(shù)據(jù)，此時，主存帶寬為：16B×300000/s＝4.8MB/s。在不考慮DMA傳輸?shù)那闆r下，主存帶寬至少達到4.8MB/s才能滿足CPU的訪存要求。

（2）平均每秒鐘“缺頁”異常次數(shù)為：300000×0.0005%＝l.5次；

因為存儲器總線寬度為32位，所以，每傳送32位數(shù)據(jù)，磁盤控制器發(fā)出一次DMA請求，故平均每秒磁盤DMA請求的次數(shù)至少為：1.5×4KB/4B＝1.5K＝1536。

（3）CPU和DMA控制器同時要求使用存儲器總線時，DMA請求優(yōu)先級更高；因為若DMA請求得不到及時響應，I/O傳輸數(shù)據(jù)可能會丟失。

（4）4體交叉存儲模式能提供的最大帶寬為：4×4B/50ns＝320MB/s。

44（12分）某16位計算機中，帶符號整數(shù)用補碼表示，數(shù)據(jù)Cache和指令Cache分離。題44表給出了指令系統(tǒng)中部分指令格式，其中Rs和Rd表示寄存器，mem表示存儲單元地址，（X）表示寄存器X或存儲單元X的內(nèi)容。

表　指　令系統(tǒng)中部分指令格式

該計算機采用5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器（ID）、執(zhí)行/計算有效地址（EX）、訪問存儲器（M）和結(jié)果寫回寄存器（WB），流水線采用“按序發(fā)射，按序完成”方式，沒有采用轉(zhuǎn)發(fā)技術處理數(shù)據(jù)相關，并且同一個寄存器的讀和寫操作不能在同一個時鐘周期內(nèi)進行。請回答下列問題。

（1）若int型變量x的值為－513，存放在寄存器R1中，則執(zhí)行指令“SHR R1”后，R1的內(nèi)容是多少？（用十六進制表示）

（2）若某個時間段中，有連續(xù)的4條指令進入流水線，在其執(zhí)行過程中沒有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時鐘周期數(shù)為多少？

（3）若高級語言程序中某賦值語句為x＝a＋b，x、a和b均為int型變量，它們的存儲單元地址分別表示為[x]、[a]和[b]。該語句對應的指令序列及其在指令流水線中的執(zhí)行過程如題44圖所示。則這4條指令執(zhí)行過程中，I₃的ID段和I₄的IF段被阻塞的原因各是什么？

題44圖　指令序列及其執(zhí)行過程示意圖

（4）若高級語言程序中某賦值語句為x＝2*x＋a，x和a均為unsigned int類型變量，它們的存儲單元地址分別表示為[x]、[a]，則執(zhí)行這條語句至少需要多少個時鐘周期？要求模仿題44圖畫出這條語句對應的指令序列及其在流水線中的執(zhí)行過程示意圖。

解：

（1）x的機器碼為[x]補＝1111 1101 1111B，即指令執(zhí)行前（R1）＝FDFFH，右移1wei后為1111 1110 1111 1111B，即指令執(zhí)行后（R1）＝FEFFH。

（2）至少需要5＋（4－1）＝8個時鐘周期數(shù)。

（3）I₃的ID段被阻塞的原因：因為I₃與I₁和I₂都存在數(shù)據(jù)相關，需等到I₁和I₂將結(jié)果寫回寄存器后，I₃才能讀寄存器內(nèi)容，所以I₃的ID段被阻塞。

I₄的IF段被阻塞的原因：因為I₄的前一條指令I₃在ID段被阻塞，所以I₄的IF段被阻塞。

（4）x＝2*x＋a對應的指令序列為：

這5條指令在流水線中的執(zhí)行過程如下圖所示，執(zhí)行x＝2*x＋a語句最少需要l7個時鐘周期。

45（7分）某請求分頁系統(tǒng)的局部頁面置換策略如下：系統(tǒng)從0時刻開始掃描，每隔5個時間單位掃描一輪駐留集（掃描時間忽略不計），本輪沒有被訪問過的頁框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。當發(fā)生缺頁時，如果該頁曾被使用過且還在空閑頁框鏈表中，則重新放回進程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。假設不考慮其他進程的影響和系統(tǒng)開銷，初始時進程駐留集為空。目前系統(tǒng)空閑頁框鏈表中頁框號依次為32、15、21、41。進程P依次訪問的＜虛擬頁號，訪問時刻＞是：＜1，1＞、＜3，2＞、＜0，4＞、＜0，6＞、＜1，11＞、＜0，13＞、＜2，14＞。請回答下列問題。

（1）訪問＜0，4＞時，對應的頁框號是什么？

（2）訪問＜1，11＞時，對應的頁框號是什么？說明理由。

（3）訪問＜2，14＞時，對應的頁框號是什么？說明理由。

（4）該策略是否適合于時間局部性好的程序？說明理由。

解：

（1）頁框號為21。因為起始駐留集為空，而0頁對應的頁框為空閑鏈表中的第三個空閑頁框，其對應的頁框號為21。

（2）頁框號為32。理由：因11＞10故發(fā)生第三輪掃描，頁號為l、3的頁框32、15在第二輪已處于空閑頁框鏈表中，此刻1頁又被重新訪問，因此應被重新放回到駐留集中。其頁框號為32。

（3）頁框號為41。理由：因為第2頁從來沒有被訪問過，它不在駐留集中，因此從空閑頁框鏈表中取出鏈表頭的頁框41，頁框號為41。

（4）適合。理由：如果程序的時間局部性越好，從空閑頁框鏈表中重新取回的機會越大，該策略的優(yōu)勢越明顯。

46（8分）某文件系統(tǒng)空間的最大容量為4TB（1T＝2⁴⁰），以磁盤塊為基本分配單位，磁盤塊大小為lKB。文件控制塊（FCB）包含一個512B的索引表區(qū)。請回答下列問題。

（1）假設索引表區(qū)僅采用直接索引結(jié)構，索引表區(qū)存放文件占用的磁盤塊號。索引表項中塊號最少占多少字節(jié)？可支持的單個文件最大長度是多少字節(jié)？

（2）假設索引表區(qū)采用如下結(jié)構：第0～7字節(jié)采用＜起始塊號，塊數(shù)＞格式表示文件創(chuàng)建時預分配的連續(xù)存儲空間，其中起始塊號占6B，塊數(shù)占2B；剩余504字節(jié)采用直接索引結(jié)構，一個索引項占6B，則可支持的單個文件最大長度是多少字節(jié)？為了使單個文件的長度達到最大，請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。

解：

（1）文件系統(tǒng)存儲空間共有塊數(shù)2⁴²/2¹⁰＝2³²。為表示2³²個塊號，索引表項占32/8＝4B，512B可存放2⁷個索引項，每個索引項對應一個磁盤塊，故最大文件長度：2⁷×2¹⁰B＝2¹⁷B＝128KB。

（2）塊號占6字節(jié)，塊數(shù)占2字節(jié)的情形下，最大文件長度：2¹⁶×2¹⁰＋（504/6） ×2¹⁰＝64MB＋84KB＝65620KB。

合理的起始塊號和塊數(shù)所占字節(jié)數(shù)分別為＜4，4＞（或＜0，8＞或＜1，7＞或＜2，6＞或＜3，5＞）。理由：塊數(shù)占4B或以上，就可表示4TB大小的文件長度，達到文件系統(tǒng)的空間上限。

47（9分）主機H通過快速以太網(wǎng)連接Internet，IP地址為192.168.0.8，服務器S的IP地址為211.68.71.80。H與S使用TCP通信時，在H上捕獲的其中5個IP分組如題47-a表所示。

題47-a表

請回答下列問題。

（1）題47-a表中的IP分組中，哪幾個是由H發(fā)送的？哪幾個完成了TCP連接建立過程？哪幾個在通過快速以太網(wǎng)傳輸時進行了填充？

（2）根據(jù)題47-a表中的IP分組，分析S已經(jīng)收到的應用層數(shù)據(jù)字節(jié)數(shù)是多少？

（3）若題47-a表中的某個IP分組在S發(fā)出時的前40字節(jié)如題47-b表所列，則該IP分組到達H時經(jīng)過了多少個路由器？

題47-b表

注：IP分組頭和TCP段頭結(jié)構分別如題47-a圖、題47-b圖所示：

題47-a圖　IP分組頭結(jié)構

題47-b圖　TCP段頭結(jié)構

解：（1）由于題47-a表中1、3、4號分組的源IP地址（第13～16字節(jié)）均為l92.168.0.8（coa80008H），所以1、3、4號分組是由H發(fā)送的。

題47-a表中1號分組封裝的TCP段的FLAG為02H（即SYN＝1，ACK＝0），seq＝846b 41c5H，2號分組封裝的TCP段的FLAG為12H（即SY＝1，ACK＝1），seq＝e059 9fefH，ack＝846b 41c6H，3號分組封裝的TCP段的FLAG為10H（即ACK＝1），seq＝846b 41c6H，ack＝e059 9ff0H，所以1、2、3號分組完成了TCP連接建立過程。

由于快速以太網(wǎng)數(shù)據(jù)幀有效載荷的最小長度為46字節(jié)，表中3、5號分組的總長度為40（28H）字節(jié)，小于46字節(jié)，其余分組總長度均大于46字節(jié)，所以3、5號分組在通過快速以太網(wǎng)傳輸時進行了填充。

（2）由3號分組封裝的TCP段可知，發(fā)送應用層數(shù)據(jù)初始序號為846b 41c6H，由5號分組封裝的TCP段可知，ack為846b 41d6H，所以5號已經(jīng)收到的應用層數(shù)據(jù)的字節(jié)數(shù)為846b 41d6H－846b 41c6H＝10H＝16B。

（3）由于S發(fā)出的IP分組的標識＝6811H，所以該分組所對應的是題47－a表中的5號分組。S發(fā)出的IP分組的TTL＝40H＝64，5號分組的TTL＝31H＝49，64－49＝15。所以，可以推斷該IP分組到達H時經(jīng)過了15個路由器。