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

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

1設n是描述問題規模的非負整數，下面程序片段的時間復雜度是（　　）。

A．O（log₂n）

B．O（n）

C．O（nlog₂n）

D．O（n₂）

【答案】A

【解析】其中，以基本的原操作重復執行的次數作為算法的時間度量。題目中的基本運算是語句x＝2×x，設其執行時間為T（n），則有2^T（n）＜n/2即T（n）＜log₂（n/2）＝O（log₂n）。

2元素a，b，c，d，e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是（　　）。

A．3

B．4

C．5

D．6

【答案】B

【解析】d首先出棧后的狀態如下圖所示。

此時可有以下4種操作：

（1）e進棧后出棧，出棧序列為decba。

（2）c出棧，e進棧后出棧，出棧序列為dceba。

（3）cb出棧，e進棧后出棧，出棧序列為dcbea。

（4）cba出棧，e進棧后出棧，出棧序列為dcbae。

3已知循環隊列存儲在一維數組A[0…n－1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是（　　）。

A．0，0

B．0，n－1

C．n－1，0

D．n－1，n－1

【答案】B

【解析】題目要求隊列非空時front和rear分別指向隊頭元素和隊尾元素，若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則此時front和rear的值都為0。由于進隊操作要執行（rear＋1）% n，則初始時front的值為0、rear的值為n－1。

4若一棵完全二叉樹有768個結點，則該二叉樹中葉結點的個數是（　　）。

A．257

B．258

C．384

D．385

【答案】C

【解析】由n＝n₀＋n₁＋n₂和n₀＝n₂＋1可知，n＝2n₀－1＋n₁，即2n₀－1＋n₁＝768，顯然n₁＝1，2n₀＝768，則n₀＝384，所以二叉樹的葉結點個數是384。還可以根據完全二叉樹的另一個性質：最后一個分支結點的序號為[768/2]，故非葉子結點數為384，而葉子結點的個數為768－384＝384。（［x］表示不大于x的最大整數，比如［3.14］＝3）。

5若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為l，2，3，4和4，3，2，1，則該二叉樹的中序遍歷序列不會是（　　）。

A．1，2，3，4

B．2，3，4，1

C．3，2，4，1

D．4，3，2，1

【答案】C

【解析】題目中的二叉樹的先序序列和后序序列正好相反，這樣的二叉樹每層只有一個結點。該二叉樹的形態如下圖所示。

從左至右，這8棵二叉樹的中序序列分別為：

（1）4，3，2，1，

（2）3，4，2，1

（3）2，4，3，1

（4）2，3，4，1

（5）1，4，3，2

（6）1，3，4，2

（7）1，2，4，3

（8）1，2，3，4

顯然選項C的中序序列不會出現。

6已知一棵有2011個結點的樹，其葉結點個數為ll6，該樹對應的二叉樹中無右孩子的結點個數是（　　）。

A．115

B．116

C．1895

D．1896

【答案】D

【解析】每個非終端結點轉換成二叉樹后都對應一個無右孩子的結點（因為一個非終端結點至少有一個孩子結點，其最右邊的孩子結點轉換成二叉樹后一定沒有右孩子），另外，樹根結點轉換成二叉樹后也沒有右孩子。題目中樹的總結點數是2011，葉結點個數是116，則非終端結點個數是2011－116＝1895，則該樹對應的二叉樹中無右孩子的結點個數是1895＋1＝1896。

7對于下列關鍵字序列，不可能構成某二叉排序樹中一條查找路徑的序列是（　　）。

A．95，22，91，24，94，71

B．92，20，91，34，88，35

C．21，89，77，29，36，38

D．12，25，71，68，33，34

【答案】A

【解析】各選項對應的查找過程如下圖所示，從中看到選項B、C、D對應的查找樹都是二叉排序樹，只有選項A對應的查找樹不是一棵二叉排序樹，因為在以91為根的左子樹中出現了比91大的結點94。

8下列關于圖的敘述中，正確的是（　　）。

Ⅰ．回路是簡單路徑

Ⅱ．存儲稀疏圖，用鄰接矩陣比鄰接表更省空間

Ⅲ．若有向圖中存在拓撲序列，則該圖不存在回路

A．僅Ⅱ

B．Ⅰ、Ⅱ

C．僅Ⅲ

D．Ⅰ、Ⅲ

【答案】C

【解析】第一個頂點和最后一個頂點相同的路徑稱為回路；序列中頂點不重復出現的路徑稱為簡單路徑；回路顯然不是簡單路徑，所以選項Ⅰ錯誤。稀疏圖用鄰接表表示比鄰接矩陣節省存儲空間，稠密圖適合用鄰接矩陣的存儲表示，所以選項Ⅱ錯誤。利用拓撲排序算法可以判斷圖中是否存在回路，即在拓撲排序輸出結束后所余下的頂點都有前驅，則說明了只得到了部分頂點的拓撲有序序列，圖中存在回路。所以選項Ⅲ正確。

9為提高散列（Hash）表的查找效率，可以采用的正確措施是（　　）。

Ⅰ．增大裝填（載）因子

Ⅱ．設計沖突（碰撞）少的散列函數

Ⅲ．處理沖突（碰撞）時避免產生聚集（堆積）現象

A．僅Ⅰ

B．僅Ⅱ

C．Ⅰ、Ⅱ

D．Ⅱ、Ⅲ

【答案】D

【解析】散列表的查找效率（比較次數）取決于：散列函數、處理沖突的方法和散列表的裝填因子α。α標志著散列表的裝滿程度，通常情況下，α越小，發生沖突的可能性越小；反之，α越大，表示已填入的記錄越多，再填入記錄時，發生沖突的可能性越大。因此選項Ⅰ錯誤，越是增大裝填因子，發生沖突的可能性就越大，查找效率也越低。選項Ⅱ正確。選項Ⅲ正確。采用合適的處理沖突的方法避免產生聚集現象，也將提高查找效率。例如，用拉鏈法解決沖突時不存在聚集現象，用線性探測法解決沖突時易引起聚集現象。

10為實現快速排序算法，待排序序列宜采用的存儲方式是（　　）。

A．順序存儲

B．散列存儲

C．鏈式存儲

D．索引存儲

【答案】A

【解析】對絕大部分內部排序而言，只適用于順序存儲結構，快速排序在排序過程中，既要從后向前查找，也要從前向后查找，因此宜采用順序存儲。

11已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，將其再調整為大根堆，調整過程中元素之間進行的比較次數是（　　）。

A．1

B．2

C．4

D．5

【答案】B

【解析】對堆插入或刪除一個元素，有可能不滿足堆的性質，堆被破壞，需要調整為新堆。

（1）為原堆，

（2）為插入18后，

（3）比較10與18，交換后，

（4）比較25與18，不交換，即為調整后的新的大根堆。

因此調整過程中元素之間進行的比較次數為2。

12下列選項中，描述浮點數操作速度指標的是（　　）。

A．MIPS

B．CPI

C．IPC

D．MFLOPS

【答案】D

【解析】MFLOPS（Million Floating-point Operations per Second）表示每秒執行多少百萬次浮點運算，用來描述計算機的浮點運算速度，適用于衡量處理機的性能。

MIPS（Million Instructions per Second）表示每秒執行多少百萬條指令。對于一個給定的程序，MIPS定義為

這里所說的指令一般是指加、減運算這類短指令。

CPI（Cycles per Instruction）就是每條指令執行所用的時鐘周期數。由于不同指令的功能不同，造成指令執行時間不同，也即指令執行所用的時鐘數不同，所以CPI是一個平均值。

IPC（Instructions per Cycle）每個時鐘周期執行的指令數。

13float型數據通常用IEEE754單精度浮點數格式表示。若編譯器將float型變量x分配在一個32位浮點寄存器FRl中，且x＝－8.25，則FR1的內容是（　　）。

A．C104 0000H

B．C242 0000H

C．C184 0000H

D．C1C2 0000H

【答案】A

【解析】首先將十進制數轉換為二進制數－1000.01，接著把它寫成規格化形式－1.00001×2³（按IEEE754標準），然后計算階碼的移碼＝偏置值＋階碼真值＝127＋3＝130，最后短浮點數代碼：數符位＝1，階碼＝1000 0010，尾數00 0010 0000 0000 0000 00000，寫成十六進制為C104 0000H。選項D是一個很容易被誤選的選項，其錯誤在于沒有考慮IEEE754標準中隱含最高位1的情況，偏置值是128。

14下列各類存儲器中，不采用隨機存取方式的是（　　）。

A．EPROM

B．CDR0M

C．DRAM

D．SRAM

【答案】B

【解析】隨機存取方式是指存儲器的任何一個存儲單元的內容都可以存取，而且存取時間與存儲單元的物理位置無關。CDROM是只讀的光盤存儲器，采用串行存取方式而不是隨機存取方式。

15某計算機存儲器按字節編址，主存地址空間大小為64MB，現用4M×8位的RAM芯片組成32MB的主存儲器，則存儲器地址寄存器MAR的位數至少是（　　）。

A．22位

B．23位

C．25位

D．26位

【答案】D

【解析】雖然實際的主存儲器（RAM區）只有32MB，但不排除還有ROM區，考慮到存儲器擴展的需要，MAR應保證能訪問到整個主存地址空間。因為主存的地址空間大小為64MB，所以MAR的位數至少需要26位。

16偏移尋址通過將某個寄存器內容與一個形式地址相加而生成有效地址。下列尋址方式中，不屬于偏移尋址方式的是（　　）。

A．間接尋址

B．基址尋址

C．相對尋址

D．變址尋址

【答案】A

【解析】在四種不同的尋址方式中，間接尋址按指令的形式地址從主存中取出操作數的有效地址，然后再按此有效地址從主存中讀出操作數。其余三種尋址方式可以統稱為偏移尋址。

17某機器有一個標志寄存器，其中有進位/借位標志CF、零標志ZF、符號標志SF和溢出標志OF，條件轉移指令bgt（無符號整數比較大于時轉移）的轉移條件是（　　）。

A．CF＋OF＝0

B．SF＋ZF＝0

C．CF＋ZF＝0

D．CF＋SF＝0

【答案】C

【解析】判斷無符號整數A＞B成立，滿足的條件是結果不等于0，即零標志ZF＝0，且不發生進位，即進位/借位標志CF＝0。所以正確選項為C。其余選項中用到了符號標志SF和溢出標志OF，顯然可以排除掉。

18下列給出的指令系統特點中，有利于實現指令流水線的是（　　）。

Ⅰ．指令格式規整且長度一致

Ⅱ．指令和數據按邊界對齊存放

Ⅲ．只有Load/Store指令才能對操作數進行存儲訪問

A．僅Ⅰ、Ⅱ

B．僅Ⅱ、Ⅲ

C．僅Ⅰ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】特點Ⅰ和Ⅲ都是RISC機的特征，而特點Ⅱ則有利于指令和數據的存放，所以以上三個特點都有利于實現指令流水線。

19假定不采用Cache和指令預取技術，且機器處于“開中斷”狀態，則在下列有關指令執行的敘述中，錯誤的是（　　）。

A．每個指令周期中CPU都至少訪問內存一次

B．每個指令周期一定大于或等于一個CPU時鐘周期

C．空操作指令的指令周期中任何寄存器的內容都不會被改變

D．當前程序在每條指令執行結束時都可能被外部中斷打斷

【答案】C

【解析】本題涉及的概念比較多。首先，如果不采用Cache和指令預取技術，每個指令周期中至少要訪問內存一次，即從內存中取指令。其次，指令有的簡單有的復雜，每個指令周期總大于或等于一個CPU時鐘周期。第三，即使是空操作指令，在指令周期中程序計數器PC的內容也會改變（PC值加“1”），為取下一條指令做準備。第四，如果機器處于“開中斷”狀態，在每條指令執行結束時都可能被新的更高級的中斷請求所打斷。所以應選擇選項C。

20在系統總線的數據線上，不可能傳輸的是（　　）。

A．指令

B．操作數

C．握手（應答）信號

D．中斷類型號型號

【答案】C

【解析】握手（應答）信號屬于通信聯絡控制信號應該在通信總線上傳輸，不可能在數據總線上傳輸。而指令、操作數和中斷類型碼都可以在數據線上傳輸。

21某計算機有五級中斷L₄～L₀，中斷屏蔽字為M₄M₃M₂M₁M₀，M_i＝1（0≤i≤4）表示對L_i級中斷進行屏蔽。若中斷響應優先級從高到低的順序是L₀→L₁→L₂→L₃→L₄，且要求中斷處理優先級從高到低的順序為L₃→L₀→L₂→L₁→L₃，則L₁的中斷處理程序中設置的中斷屏蔽字是（　　）。

A．11110

B．01101

C．00011

D．01010

【答案】D

【解析】由于L₂的中斷處理優先級下降，屏蔽字中需要3個0，所以可以將選項A、B排除掉。L₁需要對L₄、L₀、L₂開放，所以相應位應該為“0”，即為01010。

22某計算機處理器主頻為50MHz，采用定時查詢方式控制設備A的I/O，查詢程序運行一次所用的時鐘周期數至少為500。在設備A工作期間，為保證數據不丟失，每秒需對其查詢至少200次，則CPU用于設備A的I/O的時間占整個CPU時間的百分比至少是（　　）。

A．0.02%

B．0.05%

C．0.20%

D．0.50%

【答案】C

【解析】對于設備A，每秒中查詢至少200次，每次查詢至少500個時鐘周期，總的時鐘周期數為100000，又因為處理器主頻為50MHz。所以CPU用于設備A的I/O的時間占整個CPU時間的百分比至少為100000/50＝0.20%。

23下列選項中，滿足短任務優先且不會發生饑餓現象的調度算法是（　　）。

A．先來先服務

B．高響應比優先

C．時間片輪轉

D．非搶占式短任務優先

【答案】B

【解析】分析該題目可以看到，本題所提到的問題是涉及短任務調度也就是屬于作業調度，因此首先排除時間片輪轉算法；因為作業調度算法中沒有時間片輪轉的算法。其次，因為問題提到短任務，則先來先服務的算法也可以排除了，它與短任務無關。剩余高響應比優先算法和非搶占式短任務優先是哪一個？我們可以通過分析得到，非搶占式短任務優先算法不能解決饑餓問題，因為當一個系統短任務源源不斷到達是，長任務必然會得不到調度，產生饑餓。而解決此方法的最好方式就是采用計算響應比的方法，并以高響應比值優先調度。這樣，無論短任務或長任務，均可以得到調度，而且，較短任務會得到優先的調度。故滿足短任務優先且不會發生饑餓現象的調度算法只有高響應比優先算法。

24下列選項中，在用戶態執行的是（　　）。

A．命令解釋程序

B．缺頁處理程序

C．進程調度程序

D．時鐘中斷處理程序

【答案】A

【解析】題目是問用戶態執行，可見是有關操作系統基本概念的問題。四個選項中，用戶唯一能面對的是命令解釋程序，缺頁處理程序和時鐘中斷都屬于中斷，在核心態執行，而進城調度屬于系統調用在核心態執行。只有命令解釋程序屬于命令接口，可以運行在用戶態，接受用戶的命令操作控制。

25在支持多線程的系統中，進程P創建的若干個線程不能共享的是（　　）。

A．進程P的代碼段

B．進程P中打開的文件

C．進程P的全局變量

D．進程P中某線程的棧指針

【答案】D

【解析】現代操作系統中，進程是資源分配的基本單位，線程是處理機調度的基本單位。因此，進程是線程運行的容器，本題中，進程的代碼段，進程打開的文件，進程的全局變量等都是進程的資源，唯有進程中某線程的棧指針是屬于線程的，那么，屬于進程的資源可以共享，屬于線程的棧是獨享的，不能共享。

26用戶程序發出磁盤I/O請求后，系統的正確處理流程是（　　）。

A．用戶程序→系統調用處理程序→中斷處理程序→設備驅動程序

B．用戶程序→系統調用處理程序→設備驅動程序→中斷處理程序

C．用戶程序→設備驅動程序→系統調用處理程序→中斷處理程序

D．用戶程序→設備驅動程序→中斷處理程序→系統調用處理程序

【答案】B

【解析】對于一次設備的調用，操作系統為用戶準備了系統調用的接口，當用戶使用設備時，首先在用戶程序中發起一次系統調用，操作系統的內核接到該調用請求后調用處理程序進行處理，根據調用格式和形參，再轉到相應的設備驅動程序去處理；大部分設備在運行時是需要時間的，所以設備驅動程序會以中斷方式驅動設備，即設置好控制寄存器參數和中斷向量等參數后阻塞自己；當設備準備好或所需數據到達后設備硬件發出中斷，設備驅動程序喚醒，將數據按上述調用順序逆向回傳到用戶程序中，或繼續驅動設備執行下一條指令。因此，正確的順序應該是用戶到系統調用到驅動到中斷處理。中斷處理處于最底層。

27某時刻進程的資源使用情況如下表所示

此時的安全序列是（　　）。

A．P1，P2，P3，P4

B．P1，P3，P2，P4

C．P1，P4，P3，P2

D．不存在

【答案】D

【解析】典型的死鎖避免算法，銀行家算法的應用。銀行家算法是操作系統中的一個重點知識單元，考生對此應該非常熟悉，本題并無難點。分析一下下表，可以看到，經過P1，P4的運行以后，可用資源是2，2，1，而P2，P3所需資源分別是1，3，2和1，3，1。所以剩余資源已經不夠P2或P3的分配，亦即找不到能夠安全運行的序列，因此此時是處于不安全狀態，所以不存在這樣的安全序列。

28在缺頁處理過程中，操作系統執行的操作可能是（　　）。

Ⅰ．修改頁表

Ⅱ．磁盤I/O

Ⅲ．分配頁框

A．僅Ⅰ、Ⅱ

B．僅Ⅱ

C．僅Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】D

【解析】首先我們要考慮的是，為什么會發生缺頁中斷？當然，在一個采用虛擬存儲管理技術的系統中，程序是部分裝入的，還有部分是處于外存上的，因此，當需要訪問那部分位于外存上的代碼或數據時，系統會產生缺頁中斷。產生缺頁中斷的目的是要將位于外存上的代碼或數據裝入內存，據此，缺頁中斷接下去所做的工作就是首先要在內存中找到空閑頁框并分配給需要訪問的頁（若沒有空閑的頁面則要調用頁面置換程序找到一處頁面，將該頁面的內容處理掉，或回寫磁盤，或覆蓋掉，然后將此頁分配給需要訪問的頁），分配妥當以后，缺頁中斷處理程序調用設備驅動程序做磁盤I/O，將位于外存（一般是磁盤）上的頁面調入內存，調入后轉身去修改頁表，將頁表中代表該頁是否在內存的標志位（一般稱為存在位或有效位、在位位）修改為“真”，將物理頁框號填入相應位置，若必要還需修改其它相關表項等。完成上述任務后，缺頁中斷處理程序返回，繼續程序的執行。從上述過程可以看出，涉及的相關處理非常多，因此，答案就顯而易見了。

29當系統發生抖動（thrashing）時，可以采取的有效措施是（　　）。

Ⅰ．撤銷部分進程

Ⅱ．增加磁盤交換區的容量

Ⅲ．提高用戶進程的優先級

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅲ

D．僅Ⅰ、Ⅱ

【答案】A

【解析】“抖動”現象是指剛剛被換出的頁很快又要被訪問，為此，又要換出其他頁，而該頁又很快被訪問，必須換入，如此頻繁地置換頁面，以致操作系統的大部分時間都花在頁面置換上，引起系統性能下降甚至崩潰。引起系統抖動現象的原因是對換的信息量過大，內存容量不足，置換算法選擇不當。所以解決的辦法就是降低交換頁面數量，加大內存容量，改變置換選擇算法。但是降低交換頁面數量和改變置換選擇算法對于一個應用系統來講是不可能的，只能增加內存容量。增加內存容量可以是直接添加物理內存（大型計算機都可以在不關機的情況下增加物理內存條），或者，降低進程數量，相對地增加內存。而增加交換區容量并不能解決物理內存不足的問題，提高用戶進程的優先級會使系統的狀態更加惡化。

30在虛擬存儲管理中，地址變換機構將邏輯地址變換為物理地址，形成該邏輯地址的階段是（　　）。

A．編輯

B．編譯

C．鏈接

D．裝載

【答案】B

【解析】程序的編輯階段一般都是程序員能夠識別的高級語言或低級語言的文本，不涉及到任何與計算機運行相關的事；編譯是由編譯程序將用戶源代碼編譯成若干個目標模塊，源地址編譯成目標程序時，會形成邏輯地址；鏈接是由鏈接程序將編譯后形成的一組目標模塊，以及所需庫函數鏈接，形成完整的裝入模塊；裝入是由裝入程序將裝入模塊裝入內存。

31某文件占10個磁盤塊，現要把該文件磁盤塊逐個讀入主存緩沖區，并送用戶區進行分析。假設一個緩沖區與一個磁盤塊大小相同，把一個磁盤塊讀人緩沖區的時間為100μs，將緩沖區的數據傳送到用戶區的時間是50μs，CPU對一塊數據進行分析的時間為50μs。在單緩沖區和雙緩沖區結構下，讀人并分析完該文件的時間分別是（　　）。

A．1500μs、1000μs

B．1550μs、1100μs

C．1550μs、1550μs

D．2000μs、2000Μs

【答案】B

【解析】這是一個簡單的緩沖區的問題。由于緩沖區的訪問是互斥的，所以對單一緩沖區，從磁盤寫入和讀出到用戶區的操作必須串行執行，也就是要保證互斥操作。而CPU對數據的分析與從用戶區讀數據也是需要互斥操作，但是CPU分析與從磁盤寫入緩沖區的操作可以并行。從本題看，由于分析所用的時間小于從磁盤寫入緩沖區的時間，因此，CPU會空閑。單緩沖區的總時間＝（磁盤寫入緩沖區時間＋緩沖區讀出時間）×10＋CPU處理最后一塊數據的時間＝（100＋50）×10＋50＝1550μs。當采用雙緩沖區時，每塊緩沖區的操作也必須滿足互斥操作，但是，對兩塊緩沖區的操作卻可以并行，所以，當第一個緩沖區寫滿以后，磁盤緊接著寫另一個緩沖區，同時，前一個已經滿了的緩沖區被讀出到用戶區，并立即進行CPU的數據分析。讀出操作和數據分析必須互斥進行，故從時間上看，當數據被讀出并分析后，恰好另一個緩沖區也寫滿了，可以立即進行讀出數據到用戶區并進行數據分析。兩塊緩沖區交替進行讀寫，直到數據分析完畢，因此，總時間＝（磁盤寫入緩沖區時間）×10＋讀出最后一塊數據時間＋CPU分析最后一塊數據時間＝（100）×10＋50＋50＝1100μs。

32有兩個并發執行的進程P1和P2，共享初值為l的變量x。P1對x加1，P2對x減1。加1和減1操作的指令序列分別如下所示。

兩個操作完成后，2的值（　　）。

A．可能為－1或3

B．只能為1

C．可能為0、1或2

D．可能為－1、0、1或2

【答案】C

【解析】這是在數據庫中常有的操作。為保證數據的正確，避免產生錯誤，系統必須保證數據的同步。而保證數據的同步一般采取加鎖的方法，讓進程P1和P2互斥訪問共享變量x。當然用信號量和P、V操作也是可以保證互斥操作，達到數據同步的。本例中，由于沒有采取保證數據同步的相應措施，則最后結果就會出現差錯。例如，當正常情況下，進程P1和P2先后對x操作，可以看到x值的變化為初始1→2→1的過程，若P2，P1先后操作，則x值的變化為初始1→0→1，這是正確的。若考慮一種并發的情況，進程P1和P2先后執行了取數load的操作，它們得到的x值均為1，運算后，P1和P2的x值分別為2和0，此時要看哪個進程后執行存數store的操作了，哪個進程后操作，結果就是那個進程的x值，所以可能的結果為0或2，加上前面正確的x值1，則可能的結果就有3種了。

33TCP/IP參考模型的網絡層提供的是（　　）。

A．無連接不可靠的數據報服務

B．無連接可靠的數據報服務

C．有連接不可靠的虛電路服務

D．有連接可靠的虛電路服務

【答案】A

【解析】TCP/IP的網絡層向上只提供簡單靈活的、無鏈接的、盡最大努力交付的數據服務，因此答案是A。

34若某通信鏈路的數據傳輸速率為2400bps，采用4相位調制，則該鏈路的波特率是（　　）。

A．600波特

B．1200波特

C．4800波特

D．9600波特

【答案】B

【解析】注意無噪聲下的碼元速率極限值B與信道帶寬H的關系：B＝2×H（Baud），而奈奎斯特公式——無噪信道傳輸能力公式是C＝2×H×log₂N（bps），N為一個碼元所取的離散值個數。從而可以得到波特率與數據傳輸速率的關系，即C＝B×log₂N（bps），在本題中數據傳輸速率C＝2400，N＝4，因此波特率是1200，答案是B。

35數據鏈路層采用選擇重傳協議（SR）傳輸數據，發送方已發送了0H3號數據幀，現已收到1號幀的確認，而0、2號幀依次超時，則此時需要重傳的幀數是（　　）。

A．1

B．2

C．3

D．4

【答案】B

【解析】在選擇重傳協議中，接收方逐個地確認正確接收的分組，不管接收到的分組是否有序，只要正確接收就發送選擇ACK分組進行確認。因此選擇重傳不支持累積確認，要特別注意其與GBN協議的區別。本題收到l號幀的確認，說明1號幀正確接收，0和2號幀依次超時，因此必須重傳，然而3號幀尚未超時，是否正確接收未知，故不用重傳，因此必須重傳0和2號幀，答案是B。

36下列選項中，對正確接收到的數據幀進行確認的MAC協議是（　　）。

A．CSMA

B．CDMA

C．CSMA/CD

D．CSMA/CA

【答案】D

【解析】可采用排除法。CDMA是碼分多址復用，是物理層的內容；CSMA/CD即帶沖突檢測的載波監聽多路訪問，接收方并不需要確認；CSMA/CD是CSMA的加強版，故CSMA也無確定；CSMA/CD是802.11中的協議，其利用ACK信號來避免沖突的發生，也就是說，只有當客戶端收到網絡上返回的ACK信號后才確認送出的數據已經正確到達目的地址，因此答案是D。

37某網絡拓撲如下圖所示，路由器Rl只有到達子網l92.168.1.0/24的路由。為使R1可以將IP分組正確地路由到圖中所有子網，則在R1中需要增加一條路由（目的網絡，子網掩碼，下一跳）是（　　）。

A．192.168.2.0，255.255.255.128，192.168.1.1

B．192.168.2.0，255.255.255.0，192.168.1.1

C．192.168.2.0，255.255.255.128，192.168.1.2

D．192.168.2.0，255.255.255.0，192.168.1.2

【答案】D

【解析】首先從題目給出的路由表項可以確定下一跳肯定是路由器R1直接相連的R2的地址，因此是192.168.1.2，此時可以排除A和B兩個選項了。進而分析路由器R2所連接的網絡特點，注意其連接了2個網絡分別是l92.168.2.0/25和192.168.2.128/25，但答案選項中只有一條信息，因此這里用到了超網的概念，超網是與子網類似的概念——IP地址根據子網掩碼被分為獨立的網絡地址和主機地址。但是，與子網把大網絡分成若干小網絡相反，它是把一些小網絡組合成一個大網絡——超網，這里192.168.2.00000000/25和192.168.2.10000000/25前24位是相同的，因此所構成的超網就是l92.168.2.0/24，那么子網掩碼就是255.255.255.00000000即255.255.255.0，因此答案是D。

38在子網l92.168.4.0/30中，能接收目的地址為l92.168.4.3的IP分組的最大主機數是（　　）。

A．0

B．1

C．2

D．4

【答案】C

【解析】每個子網中忽略子網內全為0和全為1的地址剩下的就是有效主機地址，本題中由于子網的比特數是30，因此用于主機的只有2位，即O0，01，10，11，有效主機地址是2個，這里192.168.4.3顯然是其廣播地址，因此答案是C。

39主機甲向主機乙發送一個（SYN一1，seq一11220）的TCP段，期望與主機乙建立TCP連接，若主機乙接受該連接請求，則主機乙向主機甲發送的正確的TCP段可能是（　　）。

A．（SYN＝0，ACK＝0，seq＝11221，ack＝11221）

B．（SYN＝1，ACK＝1，seq＝11220，ack＝11220）

C．（SYN＝1，ACK＝1，seq＝11221，ack＝11221）

D．（SYN＝0，ACK＝0，seq＝11220，ack＝11220）

【答案】C

【解析】TCP是面向連接的，所謂面向連接，就是當計算機雙方通信時必需先建立連接，然后數據傳送，最后拆除三個過程，也就是客戶主動打開TCP傳輸，服務器被動打開。第一次握手：客戶發送SYN＝1，seq＝x給服務器，即客戶的TCP向服務器發出連接請求報文段，其首部中的同步位SYN＝1，并選擇序號seq＝x，表明傳送數據時的第一個數據字節的序號是x。第二次握手：服務器發送SYN＝1，ACK＝l，seq＝y，ack＝x＋1給客戶，即服務器的TCP收到連接請求報文段后，如同意則發回確認。服務器在確認報文段中應使SYN＝1，使ACK＝1，其確認號ack＝x＋1，自己選擇的序號seq＝y。第三次握手：客戶發送ACK＝1，seq＝x＋1，ack＝y＋1給服務器，即客戶收到此報文段后向服務器給出確認，其ACK＝1，確認號ack＝y＋1。客戶的TCP通知上層應用進程，連接已經建立。服務器的TCP收到主機客戶的確認后，也通知其上層應用進程：TCP連接已經建立。因此，本題中x＝11220，y是主機乙自動選取的序號，可以與x相同，也可以不相同，從而主機乙所發出的TCP段應該是SYN＝1，ACK＝1，seq＝y，ack＝x＋1，即SYN＝1，ACK＝1，seq＝y，ack＝11221，從而答案是C。

40主機甲與主機乙之間已建立一個TCP連接，主機甲向主機乙發送了3個連續的TCP段，分別包含300字節、400字節和500字節的有效載荷，第3個段的序號為900。若主機乙僅正確接收到第1和第3個段，則主機乙發送給主機甲的確認序號是（　　）。

A．300

B．500

C．1200

D．1400

【答案】B

【解析】本題考查TCP的確認機制，TCP首部的序號字段是指本報文所發送的數據的第一個字節的序號。本題中首先根據第3個段的序號為900，可以得出第2個段的序號為500，第l個段的序號為200，這里主機乙僅正確接收了第1段和第3段，這意味著第2段丟失，需要超時重傳，因此主機乙發送給主機甲的確認序號，也就是此時接收端期望收到的下一個數據包中第一個字節的序號應該是第二段的第一個字節的序號，也就是500，因此答案是B。

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

41（8分）已知有6個頂點（頂點編號為0～5）的有向帶權圖G，其鄰接矩陣A為上三角矩陣，按行為主序（行優先）保存在如下的一維數組中。

要求：

（1）寫出圖G的鄰接矩陣A。

（2）畫出有向帶權圖G。

（3）求圖G的關鍵路徑，并計算該關鍵路徑的長度。

解：（1）由題可以畫出待定上三角矩陣的結構圖如下（圖中？為待定元素）：

可以看出，第一行至第五行主對角線上方的元素分別為5，4，3，2，1個，由此可以畫出壓縮存儲數組中的元素所屬行的情況，如下圖所示：

將各元素填入各行即得鄰接矩陣：

（2）根據第一步所得矩陣A容易做出有向帶權圖G，如下：

（3）下圖中粗線箭頭所標識的4個活動組成圖G的關鍵路徑。

由上圖容易求得圖的關鍵路徑長度為：4＋5＋4＋3＝16。

42（15分）一個長度為L（L≥1）的升序序列S，處在第「L/2」個位置的數為S的中位數。例如，若序列S1＝（11，13，15，17，19），則Sl的中位數是15。兩個序列的中位數是含它們所有元素的升序序列的中位數。例如，若S2＝（2，4，6，8，20），則Sl和S2的中位數是11。現有兩個等長升序序列A和B，試設計一個時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數。要求：

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

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

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

解：（1）算法的基本設計思想：分別求兩個升序序列A和B的中位數，設為a和b。

①若a＝b，則a或b即為所求的中位數。

②否則，若a＜b，中位數只能出現（a，b）范圍內，舍棄a所在序列A的較小一半，同時舍棄b所在序列B的較大一半。若a＞b，中位數只能出現（b，a）范圍內，舍棄b所在序列B的較小一半，同時舍棄a所在序列A的較大一半。

③在保留的兩個升序序列中求出新的中位數a和b，重復上述過程，直到兩個序列中只含一個元素時為止，則較小者即為所求的中位數。

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

（3）說明算法的復雜性：算法的時間復雜度、空間復雜度分別是O（1og₂n）和O（1）。

43（11分）假定在一個8位字長的計算機中運行下列C程序段：

若編譯器編譯時將8個8位寄存器Rl～R8分別分配給變量x、y、m、n、z1、z2、k1和k2。請回答下列問題。（提示：帶符號整數用補碼表示）

（1）執行上述程序段后，寄存器R1、R5和R6的內容分別是什么？（用十六進制表示）

（2）執行上述程序段后，變量m和kl的值分別是多少？（用十進制表示）

（3）上述程序段涉及帶符號整數加/減、無符號整數加/減運算，這四種運算能否利用同一個加法器及輔助電路實現？簡述理由。

（4）計算機內部如何判斷帶符號整數加/減運算的結果是否發生溢出？上述程序段中，哪些帶符號整數運算語句的執行結果會發生溢出？

解：（1）無符號整數運算，（R1）＝x＝134＝1000 0110B＝86H、（R5）＝x－y＝246＝1001 0000B＝90H、（R6）＝x＋y＝0111 1100B＝7CH。

（2）m的機器數與x的機器數相同為86H＝1000 0110B，解釋為帶符號整數（用補碼表示）時，其值為－111 1010B＝－112；同理k1＝（m－n）＝（x－y）＝90H＝1001 0000B，解釋為帶符號整數（用補碼表示）時，其值為－111 1010B＝－112；

（3）四種運算可以利用同一個加法器及輔助電路實現，n位加法器實現的是模2ⁿ無符號整數加法運算。對于無符號整數a和b，a＋b可以直接用加法器實現，而a－b＝a＋[－b]_補（mod2ⁿ）實現；對于帶符號整數用補碼表示，補碼加減運算公式為：[a＋b] _補＝[a] _補＋[b] _補（mod2ⁿ），[a－b] _補＝[a] _補＋[－b] _補（mod2ⁿ），所以四種運算都可在n位加法器中實現。

（4）判斷溢出的方法有3種：一位符號位、進位位和雙符號位。上述程序段中只有int k2＝m＋n語句會發生溢出，因為2個帶符號整數均為負數，它們相加之后，結果小于8位二進制所能表示的最小負數。

44（12分）某計算機存儲器按字節編址，虛擬（邏輯）地址空間大小為16MB，主存（物理）地址空間大小為1MB，頁面大小為4KB；Cache采用直接映射方式，共8行；主存與Cache之間交換的塊大小為32B。系統運行到某一時刻時，頁表的部分內容和Cache的部分內容分別如題44-a圖、題44-b所示，圖中頁框號及標記字段的內容為十六進制形式。

題44-a圖　頁表的部分內容

題44-b圖　Cache的部分內容

請回答下列問題。

（1）虛擬地址共有幾位，哪幾位表示虛頁號？物理地址共有幾位，哪幾位表示頁框號（物理頁號）？

（2）使用物理地址訪問Cache時，物理地址應劃分哪幾個字段？要求說明每個字段的位數及在物理地址中的位置。

（3）虛擬地址001C60H所在的頁面是否在主存中？若在主存中，則該虛擬地址對應的物理地址是什么？訪問該地址時是否Cache命中？要求說明理由。

（4）假定為該機配置一個4路組相聯的TLB，該TLB共可存放8個頁表項，若其當前內容（十六進制）如題44-c圖所示，則此時虛擬地址024BACH所在的頁面是否在主存中？要求說明理由。

題44-c圖　TLB的部分內容

解：（1）由于頁面大小為4KB，頁內地址需要12位，所以虛擬地址24位，其中虛頁號占12位；物理地址20位，其中頁框號（實頁號）占8位。

（2）主存物理地址20位，從左至右應劃分3個字段：標記字段、塊號字段、塊內地址字段。其中標記12位，塊號3位，塊內地址5位。

（3）虛擬地址001C60H＝0000 0000 0001 1100 0110 0000B，該虛擬地址的虛頁號為001H，查頁表可以發現，虛頁號1對應的有效位為“1”，表明此頁在主存中，頁框號為04H，對應的20位物理地址是04C60H＝0000 0100 1100 0110 0000B。

訪問該地址時，Cache不命中，因為Cache采用直接映射方式，對應的物理地址應該映射到Cache的第3行中，其有效位為1，標記值105H≠04CH（物理地址高12位），故訪問該地址時Cache不命中。

（4）虛擬地址024BACH＝0000 0010 0100 1011 1010 1100B，虛頁號為024H，TLB中存放8個頁表項，采用4路組相聯，即TLB分為2組，每組4個頁表項。12位虛頁號字段中最低位作為組索引，其余11位為標記位。現在最低位為0，表明選擇第0組，11位的標記為012H，根據標記可以知道TLB命中，所在的頁面在主存中。因為如果在TLB中查到了頁表項，即TLB命中，說明所在頁一定命中

45（8分）某銀行提供1個服務窗口和10個供顧客等待的座位。顧客到達銀行時，若有空座位，則到取號機上領取一個號，等待叫號。取號機每次僅允許一位顧客使用。當營業員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業員的活動過程描述如下：

請添加必要的信號量和P、V（或wait（）、signal（））操作，實現上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。

解：（1）互斥資源：取機號，故設一個互斥信號量mutex。

（2）同步問題：顧客需要獲得空座位等待叫號，當營業員空閑時，將選取一位顧客為其服務。空座位的有、無影響等待顧客數量，顧客的有、無決定兩營業員是否能開始服務。另外，顧客獲得空座位后，需要等待叫號和被服務，顧客與營業員就服務何時開始有同步關系。設信號量teller，customer和mutex初值分別為0，0和1，設waiting為整型量，表示排隊的儲戶數量，其初始為0，表示顧客初始時為0，最大不超過10（10把座椅），各進程的具體實現如下所示：

46．（7分）某文件系統為一級目錄結構，文件的數據一次性寫入磁盤，已寫入的文件不可修改，但可多次創建新文件。請回答如下問題。

（1）在連續、鏈式、索引三種文件的數據塊組織方式中，哪種更合適？要求說明理由。為定位文件數據塊。需要在FCB中設計哪些相關描述字段？

（2）為快速找到文件，對于FCB，是集中存儲好，還是與對應的文件數據塊連續存儲好？要求說明理由。

解：根據題目所給條件，文件系統為一級目錄結構，文件的數據一次性寫入磁盤，已寫入的文件不可修改，但是可以多次創建新文件，我們得知該文件系統是不能修改原文件的，只能將修改后的文件按新文件來存儲，這與一次刻錄光盤的存儲方式相似。對于這樣的系統，因為不需要隨時添加或刪除文件的內容，所以一次寫入的文件的大小是固定不變的，也是可預知的，而連續存放文件的方式就有其優點。這種方式只需要知道文件的起始地址和文件的大小，便可以通過計算的方法找到文件的任何位置。文件若需要修改，則原文件作廢，修改以后的文件以新文件的形式重新寫入，不會產生存儲碎片，高效，高利用率。所以，如下作答。

（1） 連續的數據塊組織方式更合適，因為文件的數據一次性寫入磁盤，已寫入的文件不可修改，但是可以多次創建新文件，我們得知該文件系統是不能修改原文件的，只能將修改后的文件按新文件來存儲。不需要隨時添加或刪除文件的內容，所以一次寫入的文件的大小是固定不變的，也是可預知的。這樣，只需要知道文件的起始地址和文件的大小，便可以通過計算的方法訪問文件的任意位置。

為定位文件數據塊。需要在FCB中設計相關描述字段有：＜起始塊號，塊數＞或者＜起始塊號，結束塊號＞。

（2）將所有的FCB集中存放，文件數據集中存放。這樣在隨機查找文件名時，只需訪問FCB對應的塊，可減少磁頭移動和磁盤I/O訪問次數。

47（9分）某主機的MAC地址為00-15-C5-Cl-5E-28，IP地址為10.2.128.100（私有地址）。題47-a圖是網絡拓撲，題47-b圖是該主機進行Web請求的1個以太網數據幀前80個字節的十六進制及ASCII碼內容。

題47-a圖　網絡拓撲

題47-b圖　以太網數據幀（前80字節）

請參考圖中的數據回答以下問題。

（1）Web服務器的IP地址是什么？該主機的默認網關的MAC地址是什么？

（2）該主機在構造題47-b圖的數據幀時，使用什么協議確定目的MAC地址？封裝該協議請求報文的以太網幀的目的MAC地址是什么？

（3）假設HTTP/1.1協議以持續的非流水線方式工作，以此請求一響應時間為RTT，rfc.html頁面引用了5個JPEG小圖像，則從發出題47-b圖中的Web請求開始到瀏覽器收到全部內容為止，需要多少個RTT？

（4）該幀所封裝的IP分組經過路由器R轉發時，需修改IP分組頭中的哪些字段？注：以太網數據幀結構和IP分組頭結構分別如題47-c圖、題47-d圖所示。

題47-c圖　以太網幀結構

題47-d圖　IP分組頭結構

解：（1）以太網的數據部分是IP數據報，只要找出相應字段所在的字節即可。根據圖47-c可知以太網頭部有6＋6＋2＝14字節，根據圖47-d可知IP地址有16字節，從圖47-b第一個字節開始數14＋16＝30字節，得目的IP地址為40.aa.62.20即64.170.98.32。而以太網幀的前6字節00-21-27-21-51-ee是目的MAC地址，即為主機的默認網關10.2.128.1端口的MAC地址。

（2）該主機在構造題47-b圖的數據幀時，使用ARP協議確定目的MAC地址。封裝該協議請求報文的以太網幀的目的MAC地址是廣播地址即FF-FF-FF-FF-FF-FF。

（3）假設HTTP/1.1協議以持續的非流水線方式工作，客戶機在收到前一個請求的響應后才能發出下一個請求。第一個RTT用于請求Web頁面，客戶機收到第一個請求的響應后，每訪問一次對象就需一個RTT。rfc.html頁面引用了5個JPEG小圖像，則從發出題47-b圖中的Web請求開始到瀏覽開始到瀏覽器受到全部內容為止，故共需1＋5＝6個RTT后瀏覽器收到全部內容。

（4）私有地址要和Internet上的主機通信時，須由NAT路由器進行網絡地址轉換，轉換為一個全球IP地址。IP數據報沒經過一個路由器，生存時間TTL值就減少1，并重新計算首部校驗和。所以需修改的信息有源IP地址，頭部校驗和，生存時間。