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

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

1若元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（　　）。

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

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

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

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

【答案】D

【解析】4個選項所給序列的進、出棧操作序列分別為：

選項A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop

選項B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop

選項C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop

選項D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop

按照題目要求，不允許連續(xù)三次進行退棧操作，所以選項D所給序列為不可能得到的出棧順序。

2某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，元素a，b，c，d，e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是（　　）。

A．b，a，c，d，e

B．d，b，a，c，e

C．d，b，c，a，e

D．e，c，b，a，d

【答案】C

【解析】根據(jù)題意，隊列兩端都可以輸入數(shù)據(jù)元素，但是只能在一端輸出數(shù)據(jù)元素，這種隊列為輸出受限的雙端隊列。本題解題方法分別判斷每個選項如何入隊和出隊，從而得出不可能的情況。

假設L代表從左端入隊，R代表從右端入隊，出隊都是從左端L出。四個選項所給序列的進隊操作序列分別為：

選項A：aL（或aR），bL，cR，dR，eR

選項B：aL（或aR），bL，cR，dL，eR

選項C：不可能出現(xiàn)

選項D：aL（或aR），bL，cL，dR，eL

3下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（　　）。

【答案】D

【解析】線索二叉樹利用二叉鏈表的空鏈域來存放結點的前驅和后繼信息，解題思路較簡單。題中所給二叉樹的后序序列為dbca。結點d無前驅和左子樹，左鏈域空，無右子樹，右鏈域指向其后繼結點b；結點b無左子樹，左鏈域指向其前驅結點d；結點c無左子樹，左鏈域指向其前驅結點b，無右子樹，右鏈域指向其后繼結點a。所以正確選項為D。

4在下圖所示的平衡二叉樹中，插入關鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是（　　）。

A．13、48

B．24、48

C．24、53

D．24、90

【答案】C

【解析】題目中，插入48以后，樹根結點的平衡因子由－1變?yōu)椋?，失去平衡。這屬于RL（先右后左）型平衡旋轉，需做兩次（先右旋后左旋轉）旋轉操作。過程如下圖所示：

顯然，在調整后的新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是24，53。

5在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉結點個數(shù)是（　　）。

A．41

B．82

C．113

D．122

【答案】B

【解析】根據(jù)二叉樹的性質3的推廣公式：N₀＝l＋N₂＋2N₃＋…＋（m－1）N_m可直接在將數(shù)據(jù)帶入公式，即N₀＝l＋N₂＋2N₃＋3N4＝l＋1×1＋2×10＋3×20＝82。樹T的葉子結點的個數(shù)是82。如果考生不能熟練掌握二叉樹的性質3的推廣公式，得到本題的正確答案將費時費力。因此，需要熟練掌握二叉樹的性質及推廣。

6對n（n≥2）個權值均不相同的字符構成哈夫曼樹。下列關于該哈夫曼樹的敘述中，錯誤的是（　　）。

A．該樹一定是一棵完全二叉樹

B．樹中一定沒有度為1的結點

C．樹中兩個權值最小的結點一定是兄弟結點

D．樹中任一非葉結點的權值一定不小于下一層任一結點的權值

【答案】A

【解析】哈夫曼樹為帶權路徑長度最小的二叉樹，但不一定是完全二叉樹，選項A錯誤；哈夫曼樹中沒有度為1的結點，選項B正確；構造哈夫曼樹時，最先選取兩個權值最小的結點作為左右子樹構造一棵新的二叉樹，C正確；哈夫曼樹中任一非葉結點P的權值為其左右子樹根結點權值之和，其權值不小于其左右子樹根結點的權值，在與結點P的左右子樹根結點處于同一層的結點中，若存在權值大于結點P權值的結點Q，那么結點Q與其兄弟結點中權值較小的一個應該與結點P作為左右子樹構造新的二叉樹，由此可知，哈夫曼樹中任一非葉結點的權值一定不小于下一層任一結點的權值。

7若無向圖G＝（V，E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（　　）。

A．6

B．15

C．16

D．21

【答案】C

【解析】要保證無向圖G在任何情況下都是連通的，即任意變動圖G中的邊，G始終保持連通。首先需要圖G的任意6個結點構成完全連通子圖G₁，需n（n－l）/2＝6×（6—1）/2＝15條邊，然后再添加一條邊將第7個結點與G₁連接起來，共需l6條邊。本題非常容易錯誤地選擇選項A，主要原因是對“保證圖G在任何情況下都是連通的”的理解，分析選項A，在圖G中，具有7個頂點6條邊并不能保證其一定是連通圖，即有n－1條邊的圖不一定是連通圖。分析選項D，圖G有7個頂點21條邊，那么圖G一定是無向完全圖，無向完全圖能保證其在任何情況下都是連通的，但是這不符合題目中所需邊數(shù)最少的要求。

8對下圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是（　　）。

A．4

B．3

C．2

D．1

【答案】B

【解析】拓撲排序的步驟為：

（1）在有向圖中選一個沒有前驅的頂點并且輸出它；

（2）從圖中刪除該頂點和以它為尾的弧。重復上述兩步，直至全部頂點均已輸出。由于沒有前驅的頂點可能不唯一，所以拓撲排序的結果也不唯一。題中所給圖有三個不同的拓撲排序序列，分別為abced，abecd，aebcd。

9已知一個長度為l6的順序表L，其元素按關鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關鍵字的比較次數(shù)最多是（　　）。

A．4

B．5

C．6

D．7

【答案】B

【解析】折半查找法在查找不成功時和給定值進行比較的關鍵字個數(shù)最多為（log₂n）＋1，在本題中，n＝l6，故比較次數(shù)最多為5。

10采用遞歸方式對順序表進行快速排序。下列關于遞歸次數(shù)的敘述中，正確的是（　　）。

A．遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關

B．每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)

C．每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)

D．遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關

【答案】D

【解析】快速排序是遞歸的，遞歸過程可用一棵二叉樹給出，遞歸調用層次數(shù)與二叉樹的深度一致。例如：待排序列{48，62，35，77，55，14，35，98），采用快速排序方法，其對應遞歸調用過程的二叉樹如下圖所示。

在最壞情況下，若初始序列按關鍵碼有序或基本有序時，快速排序反而蛻化為冒泡排序。即其對應遞歸調用過程的二叉樹是一棵單支樹。因此快速排序的遞歸次數(shù)與初始數(shù)據(jù)的排列次序有關。但快速排序的遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關，即先處理較長的分區(qū)或先處理較短的分區(qū)都不影響遞歸次數(shù)。

11對一組數(shù)據(jù)（2，12，16，88，5，10）進行排序，若前三趟排序結果如下：

第一趟：2，12，16，5，10，88

第二趟：2，12，5，10，16，88

第三趟：2，5，10，12，16，88

則采用的排序方法可能是（　　）。

A．起泡排序

B．希爾排序

C．歸并排序

D．基數(shù)排序

【答案】A

【解析】題目中所給的三趟排序過程，顯然是使用起泡排序方法，每趟排序時從前往后依次比較，使大值“沉底”。希爾排序的基本思想是：先對序列進行“宏觀調整”，待序列中的記錄“基本有序”時再進行直接插入排序。宏觀調整的方法是：通過某種規(guī)則將大的待排序序列分割為若干小的待排序序列，再依次對這些小的序列直接插入排序。宏觀調整可以多次，每次分割的序列數(shù)逐漸增多，而每個序列中所包含的元素數(shù)逐漸減少。歸并排序的基本操作是將多個小的有序序列合并為一個大的有序序列，然后“逐趟歸并”，直至整個序列為有序為止。基數(shù)排序是分配排序的一種，這類排序不是通過關鍵字比較，而是通過“分配”和“收集”過程來實現(xiàn)排序的。本題中，很容易看出大值逐漸“沉底”，顯然使用的是起泡排序法。

12下列選項中，能縮短程序執(zhí)行時間的措施是（　　）。

Ⅰ．提高CPU時鐘頻率

Ⅱ．優(yōu)化數(shù)據(jù)通路結構

Ⅲ．對程序進行編譯優(yōu)化

A．Ⅰ、Ⅱ

B．Ⅰ、Ⅲ

C．Ⅱ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】D

【解析】一般說來，CPU時鐘頻率（主頻）越高，CPU的速度就越快；優(yōu)化數(shù)據(jù)通路結構，可以有效提高計算機系統(tǒng)的吞吐量；編譯優(yōu)化可得到更優(yōu)的指令序列。所以Ⅰ、Ⅱ、Ⅲ都是有效措施。

13假定有4個整數(shù)用8位補碼分別表示為r₁＝FEH，r₂＝F2H，r₃＝90H，r₄＝F8H。若將運算結果存放在一個8位寄存器中，則下列運算會發(fā)生溢出的是（　　）。

A．r₁×r₂

B．r₂×r₃

C．r₁×r₄

D．r₂×r₄

【答案】B

【解析】用補碼表示時8位寄存器所能表示的整數(shù)范圍為－128～＋127。現(xiàn)在4個整數(shù)都是負數(shù)，r₁＝－2，r₂＝－14，r₃＝－112，r₄＝－8，在4個選項中，只有r₂×r₃＝1568，結果溢出，其余3個算式結果都未超過127，不發(fā)生溢出。

14假定變量i、f和d的數(shù)據(jù)類型分為int、float和double（int用補碼表示，float和double分別用IEEE754單精度和雙精度浮點數(shù)格式表示），已知i＝785，f＝1.5678e3，d＝1.5e100。若在32位機器中執(zhí)行下列關系表達式，則結果為“真”的是（　　）。

Ⅰ．i＝＝（int）（float）i

Ⅱ．f＝＝（float）（int）f

Ⅲ．f＝＝（float）（double）f

IV．（d＋f）－d＝＝f

A．Ⅰ、Ⅱ

B．Ⅰ、Ⅲ

C．Ⅱ、Ⅲ

D．Ⅲ、Ⅳ

【答案】B

【解析】數(shù)據(jù)類型不同的數(shù)據(jù)在運算之前需要進行數(shù)據(jù)類型的轉換。Ⅱ中，f的數(shù)據(jù)類型從float轉換為int時，小數(shù)點后面4位會丟失，故Ⅱ的結果不為真；Ⅳ中，d＋f時需要對階，對階后f的尾數(shù)有效位被舍去而變?yōu)?，故d＋f仍然為d，再減去d后結果為0，故Ⅳ的結果也不為真。Ⅰ和Ⅱ進行數(shù)據(jù)類型的轉換的時候并沒有改變其值。

15假定用若干個2K×4位的芯片組成一個8K×8位的存儲器，則地址0B1FH所在芯片的最小地址是（　　）。

A．0000H

B．0600H

C．0700H

D．0800H

【答案】D

【解析】由若干芯片構成存儲器，采用字和位同時擴展方法。8片2K×4位的芯片分成4組，每組2個芯片，各組芯片的地址分配分別為：第l組，0000H～07FFH；第2組，0800H～0FFFH；第3組，l000H～17FFH；第4組，l800H～1FFFH。地址0BIFH處于第2組內，其芯片的最小地址為0800H。

16下列有關RAM和ROM的敘述中，正確的是（　　）。

Ⅰ．RAM是易失性存儲器，ROM是非易失性存儲器

Ⅱ．RAM和ROM都采用隨機存取方式進行信息訪問

Ⅲ．RAM和ROM都可用作Cache

Ⅳ．RAM和ROM都需要進行刷新

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅱ、Ⅳ

D．Ⅱ、Ⅲ、Ⅳ

【答案】A

【解析】RAM中的內容斷電后即丟失（易失性），ROM中的內容斷電后不會丟失（非易失性），同時RAM和ROM都采用隨機存取方式（即CPU對任何一個存儲單元的存取時間相同），區(qū)別在于RAM可讀可寫，ROM只讀不寫。而ROM顯然不可用作Cache，也不需要刷新，所以Ⅲ和Ⅳ的敘述都是錯誤的。

17下列命中組合情況中，一次訪存過程中不可能發(fā)生的是（　　）。

A．TLB未命中，Cache未命中，Page未命中

B．TLB未命中，Cache命中，Page命中

C．TLB命中，Cache未命中，Page命中

D．TLB命中，Cache命中，Page未命中

【答案】D

【解析】TLB（快表）和慢表（頁表，Page）構成二級存儲系統(tǒng)，若TLB命中，則Page必命中。因此不可能發(fā)生的是D選項。

18下列寄存器中，匯編語言程序員可見的是（　　）。

A．存儲器地址寄存器（MAR）

B．程序計數(shù)器（PC）

C．存儲器數(shù)據(jù)寄存器（MDR）

D．指令寄存器（IR）

【答案】B

【解析】CPU有5個專用寄存器，它們是程序計數(shù)器（PC）、指令寄存器（IR）、存儲器地址寄存器（MAR）、存儲器數(shù)據(jù)寄存器（MBR）和狀態(tài)標志寄存器（PSWR），這些寄存器中有些是CPU的內部工作寄存器，對匯編語言程序員來說是透明的，在匯編語言程序設計中不會出現(xiàn)。但匯編語言程序員可以通過制定待執(zhí)行指令的地址來設置PC的值，所以程序計數(shù)器（PC）對于匯編語言程序員可見的。

19下列選項中，不會引起指令流水線阻塞的是（　　）。

A．數(shù)據(jù)旁路（轉發(fā)）

B．數(shù)據(jù)相關

C．條件轉移

D．資源沖突

【答案】A

【解析】由于采用流水線方式，相鄰或相近的兩條指令可能會因為存在某種關聯(lián)，后一條指令不能按照原指定的時鐘周期運行，從而使流水線斷流。有三種相關可能引起指令流水線阻塞：①結構相關，又稱資源相關；②數(shù)據(jù)相關；③控制相關，又稱指令相關，主要由轉移指令引起。

20下列選項中的英文縮寫均為總線標準的是（　　）。

A．PCI、CRT、USB、EISA

B．ISA、CPI、VESA、EISA

C．ISA、SCSl、RAM、MIPS

D．ISA、EISA、PCI、PCI-Express

【答案】D

【解析】選項A中的CRT和USB、選項B中的CPI、選項C中的RAM和MIPS均不是總線標準的英文縮寫，只有選項D中的英文縮寫均為總線標準。

21單級中斷系統(tǒng)中，中斷服務程序內的執(zhí)行順序是（　　）。

Ⅰ．保護現(xiàn)場；

Ⅱ．開中斷；

Ⅲ．關中斷；

Ⅳ．保存斷點；

Ⅴ．中斷事件處理；

Ⅵ．恢復現(xiàn)場；

Ⅶ．中斷返回

A．Ⅰ→Ⅴ→Ⅵ→Ⅱ→Ⅶ

B．Ⅲ→Ⅰ→Ⅴ→Ⅶ

C．Ⅲ→Ⅳ→Ⅴ→Ⅵ→Ⅶ

D．Ⅳ→Ⅰ→Ⅴ→Ⅵ→Ⅶ

【答案】A

【解析】程序中斷有單級中斷和多級中斷之分，單級中斷在CPU執(zhí)行中斷服務程序的過程中不能被打斷，即不允許中斷嵌套。保存斷點與關中斷的任務是由硬件（中斷隱指令）完成的，所以在單級中斷系統(tǒng)中，中斷服務程序內應完成的任務有：①保存現(xiàn)場；②中斷事件處理；③恢復現(xiàn)場；④開中斷；⑤中斷返回。

22假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600×1200，顏色深度為24位，幀頻為85Hz，顯存總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為（　　）。

A．245Mbps

B．979Mbps

C．1958Mbps

D．7834Mbps

【答案】D

【解析】顯存的容量＝分辨率×色深，帶寬＝分辨率×色深×幀頻，考慮到50%的時間用來刷新屏幕，故顯存總帶寬應加倍。所以需要的顯存總帶寬至少約為：1600×1200×24×85×2＝7834Mbps。

23下列選項中，操作系統(tǒng)提供的給應用程序的接口是（　　）。

A．系統(tǒng)調用

B．中斷

C．庫函數(shù)

D．原語

【答案】A

【解析】操作系統(tǒng)提供給用戶應用程序的接口只有兩種：命令輸入和系統(tǒng)調用。其中，命令輸入又有不同的形式，例如常規(guī)的命令行、圖形化人機交互接口（GUI）、自然命令用戶接口（NUI）等，而系統(tǒng)調用中除了常規(guī)的一些傳統(tǒng)的系統(tǒng)調用（例如read（））以外，還有經過擴展的復雜調用（例如多種API），以及包含在Lib庫中的各種封裝好的過程調用（最終都是通過系統(tǒng)調用陷入到操作系統(tǒng)中去的）等。

24下列選項中，導致創(chuàng)建新進程的操作是（　　）。

Ⅰ．用戶登錄成功

Ⅱ．設備分配

Ⅲ．啟動程序執(zhí)行

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】C

【解析】進程創(chuàng)建是需要填寫PCB表的，其中唯一不需要的是Ⅱ。考察一個進程創(chuàng)建的過程是這樣的：當進程被創(chuàng)建，可以是用戶創(chuàng)建，例如雙擊相關圖標；也可以由父進程創(chuàng)建，例如lock（）時，操作系統(tǒng)首先到PCB表區(qū)搜索空閑的表格，若無則直接拒絕創(chuàng)建進程，若有則填寫PCB表創(chuàng)建進程。通常填寫PCB表的過程有一段時間（主要涉及資源分配需要協(xié)調），許多操作系統(tǒng)為此設立了一個中間狀態(tài)稱為“初始化”，也有的操作系統(tǒng)不設這個中間狀態(tài)。此時操作系統(tǒng)填寫進程ID號、處理機參數(shù)、進程參數(shù)（狀態(tài)、特權、優(yōu)先級）、分配內存（若是虛擬存儲就分配虛擬地址）、映射文件等，一切就緒，將控制權交給系統(tǒng)進行下一步調度。設備分配可能引起進程狀態(tài)的改變，但不會創(chuàng)建新進程，用戶登錄成功和啟動程序執(zhí)行都會創(chuàng)建新的進程，所以本題答案為C。

25設與某資源相關聯(lián)的信號量初值為3，當前為1，若M表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則M，N分別是（　　）。

A．0、1

B．1、0

C．1、2

D．2、0

【答案】B

【解析】信號量初值是3表示資源數(shù)有3個，當前為1表示已經用掉2個，剩余可用的資源數(shù)就只有1個了，由于資源有剩余，可見沒有其他進程等待使用該資源，故進程數(shù)為0。

26下列選項中，降低進程優(yōu)先級的合理時機是（　　）。

A．進程的時間片用完

B．進程剛完成I/O，進入就緒隊列

C．進程長期處于就緒隊列

D．進程從就緒狀態(tài)轉為運行態(tài)

【答案】A

【解析】進程時間片用完可以降低其優(yōu)先級，完成I/O的進程應該提升其優(yōu)先級，處于就緒隊列等待調度的進程一般不會改變其優(yōu)先級。進行這樣的操作主要是為了改善交互式系統(tǒng)的響應時間，并均衡各個作業(yè)的公平性。采用時間片輪轉技術主要為改善交互式用戶的感受，使其覺得是獨享計算機（時間片輪轉可以有效地防止計算繁忙型的進程獨占計算機），時間片用完后降低其優(yōu)先級是為了改善新進程的響應時間（新進程優(yōu)先級較高，老進程降低優(yōu)先級可以保證新進程具有優(yōu)先權），對于剛進入就緒隊列的新進程，往往在創(chuàng)建時已經根據(jù)其特點和要求確定好優(yōu)先級，不會隨意改變。而對于從阻塞狀態(tài)喚醒的進程，由于阻塞帶來了較長時間的等待，一般會根據(jù)阻塞隊列的不同適當?shù)靥岣邇?yōu)先級，以改善用戶響應時間。

27進程P0和P1的共享變量定義及若進程P0和P1訪問臨界資源的類C偽代碼實現(xiàn)如下：

則并發(fā)執(zhí)行進程P0和P1時產生的情況是（　　）。

A．不能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象

B．不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象

C．能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象

D．能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象

【答案】D

【解析】這是皮特森算法（Peterson’s Algorithm）的實現(xiàn)，保證進入臨界區(qū)的進程合理安全。該算法為了防止兩個進程為進入臨界區(qū)而無限期等待，設置變量turn，表示不允許進入臨界區(qū)的編號，每個進程在先設置自己標志后再設置turn標志，不允許另一個進程進入，這時，再同時檢測另一個進程狀態(tài)標志和不允許進入標志，這樣可以保證當兩個進程同時要求進入臨界區(qū)時只允許一個進程進入臨界區(qū)。保存的是較晚的一次賦值，則較晚的進程等待，較早的進程進入。先到先人，后到等待，從而完成臨界區(qū)訪問的要求。

28某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55MB（初始為空閑），采用最佳適配（BestFit）算法，分配和釋放的順序為：分配15MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時主存中最大空閑分，區(qū)的大小是（　　）。

A．7MB

B．9MB

C．10MB

D．15MB

【答案】B

【解析】對于簡單分區(qū)內存分配，需要將進程的所有代碼和數(shù)據(jù)裝入內存。故55MB先分配15MB余40MB，再分配30MB后余l(xiāng)0MB，釋放15MB后出現(xiàn)一個15MB和一個10MB的空閑空間，分配8MB時按最佳適配（BestFit）算法應該使用l0MB的空閑塊，余2MB的碎片，分配6MB時占用15MB的空間余9MB的碎片（空閑空間），因此最大空閑區(qū)為9MB。

29某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為2¹⁰字節(jié)，頁表項大小為2字節(jié)，邏輯地址結構為：

邏輯地址空間大小為2¹⁶頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是（　　）。

A．64

B．128

C．256

D．5l2

【答案】B

【解析】地址空間分為邏輯地址空間和物理地址空間。頁的大小為2¹⁰字節(jié)，頁表項大小為2B，采用二級頁表，一頁可存放2¹⁰/2＝2⁹個頁表項，本題中邏輯地址空間大小為2¹⁶字節(jié)，故最少需要2¹⁶/2⁹＝2⁷128個頁面來保存頁表項，故本題答案為B。

30設文件索引節(jié)點中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊的大小均為256字節(jié)，則可表示的單個文件最大長度是（　　）。

A．33KB

B．519KB

C．1057KB

D．16513KB

【答案】C

【解析】4個地址項為直接地址索引，其指向的數(shù)據(jù)塊大小4×256B＝1KB，一級間接地址索引可以索引256/4＝64個直接地址索引，故2個一級間接地址索引指向的數(shù)據(jù)塊大小為2×64×256B＝32KB，二級間接地址索引為256/4×256/4＝4096個直接地址索引，故1個二級間接地址索引指向的數(shù)據(jù)塊大小為4096×256B＝1024KB，共計1KB＋32KB＋1024KB＝1057KB。

31設置當前工作目錄的主要目的是（　　）。

A．節(jié)省外存空間

B．節(jié)省內存空間

C．加快文件的檢索速度

D．加快文件的讀/寫速度

【答案】C

【解析】工作目錄只是指出了當前操作的默認目錄，使得在每次訪問的時候不需要由根目錄一層一層地解析，在文件路徑比較長時，可以節(jié)省許多解析的時間，從而加快了文件的檢索速度。

32本地用戶通過鍵盤登錄系統(tǒng)時，首先獲得的鍵盤輸入信息的程序是（　　）。

A．命令解釋程序

B．中斷處理程序

C．系統(tǒng)調用服務程序

D．用戶登錄程序

【答案】B

【解析】外部設備在與計算機連接時有多種方式，中斷技術就是一種常用方式。其工作原理是：利用處理機中斷信號線，外部設備在需要服務的時候將該線設置為有效，計算機若同意接受中斷則會停止當前進程的運行，轉而服務發(fā)出中斷的物理設備（注意與陷阱，即軟中斷有區(qū)別），那么對不同外部設備進行服務的程序代碼是不同的，如何找到這些代碼呢？這就要借助中斷向量，中斷向量一般是由硬件根據(jù)中斷的類型（不同外設不同）計算所得，或計算機系統(tǒng)在開機配置時所配置的。處理機取得中斷向量，其實就是一個物理地址，該地址下存放的是為此中斷服務的代碼的起始地址。所以，當鍵盤按下的時候，鍵盤控制器獲得該操作動作，先將鍵盤掃描碼讀入鍵盤緩沖區(qū)，再向處理機發(fā)出鍵盤中斷，適當?shù)臅r候（一條指令的末尾或一條原語結束）處理機會響應中斷，調用指定服務程序將鍵盤緩沖區(qū)中的鍵盤掃描碼輸入到登錄進程中去。如此，最先響應鍵盤的必然是中斷處理程序。本題中，像命令解釋器（例如cmd窗口）、系統(tǒng)調用服務和用戶登錄程序都在中斷處理程序后面。

33下列選項中，不屬于網絡體系結構中所描述的內容是（　　）。

A．網絡的層次

B．每一層使用的協(xié)議

C．協(xié)議的內部實現(xiàn)細節(jié)

D．每一層必須完成的功能

【答案】C

【解析】體系結構僅規(guī)定協(xié)議的功能和消息格式，但對具體的實現(xiàn)細節(jié)由具體設備廠商來確定，對于網絡的層次，以及每一個層次的協(xié)議及其功能都是網絡體系結構所要描述的內容，因此答案為選項C。

34在下圖所示的采用“存儲一轉發(fā)”方式的分組交換網絡中，所有鏈路的數(shù)據(jù)傳輸速率為100Mbps，分組大小為1000B，其中分組頭大小20B，若主機Hl向主機H2發(fā)送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送開始到H2接收完為止，需要的時間至少是（　　）。

A．80ms

B．80.08ms

C．80.16ms

D．80.24ms

【答案】C

【解析】由題設可知，分組攜帶的數(shù)據(jù)長度為980B，文件長度為980000B，需拆分為1000個分組，加上頭部后，每個分組大小為1000B，總共需要傳送的數(shù)據(jù)量大小為lMB。由于所有鏈路的數(shù)據(jù)傳輸速度相同，因此文件傳輸經過最短路徑時所需時間最少，最短路徑經過分組交換機。當t＝1M×8/100Mbps＝80ms時，HI發(fā)送完最后一個比特；到達目的地，最后一個分組，需經過兩個分組交換機的轉發(fā)，每次轉發(fā)的時間為t₀＝lK×8/100Mbps＝0.08ms，所以，在不考慮分組拆裝時間和傳播延時的情況下，當t＝80ms＋2t₀＝80.16ms時，H2接受完文件，即所需的時間至少為80.16ms。

35某自治系統(tǒng)內采用RIP協(xié)議，若該自治系統(tǒng)內的路由器R1收到其鄰居路由器R2的距離矢量，距離矢量中包含信息“＜net1，16＞”，則能得出的結論是（　　）。

A．R2可以經過R1到達net1，跳數(shù)為17

B．R2可以到達net1，跳數(shù)為16

C．R1可以經過R2到達net1，跳數(shù)為17

D．R1不能經過R2到達net1

【答案】D

【解析】RIP允許一條路徑最多只能包含l5個路由器，因此距離等于16時相當于不可達，因此RIP協(xié)議里規(guī)定16為路由不可達，答案為D。

36若路由器R因為擁塞丟棄IP分組，則此時R可向發(fā)出該IP分組的源主機發(fā)送的ICMP報文件類型是（　　）。

A．路由重定向

B．目的不可達

C．源抑制

D．超時

【答案】C

【解析】當路由器或主機由于擁塞而丟棄數(shù)據(jù)報時，就向源點發(fā)送源點抑制報文，使源點知道把數(shù)據(jù)報的發(fā)送速率放慢，正確選項為C。

37某網絡的IP地址空間為192.168.5.0/24，采用定長子網劃分，子網掩碼為255.255.255.248，則該網絡的最大子網個數(shù)、每個子網內的最大可分配地址個數(shù)分別是（　　）。

A．32，8

B．32，6

C．8，32

D．8，30

【答案】B

【解析】子網號為5位，在CIDR中可以表示2⁵＝32個子網，主機號為3位，除去全0和全1的情況可以表示6個主機地址，答案為B。

38下列網絡設備中，能夠抑制廣播風暴的是（　　）。

Ⅰ．中繼器

Ⅱ．集線器

Ⅲ．網橋

Ⅳ．路由器

A．Ⅰ、Ⅱ

B．僅Ⅲ

C．Ⅲ、Ⅳ

D．僅Ⅳ

【答案】D

【解析】中繼器和集線器工作在物理層，不能抑制網絡風暴。為了解決沖突域的問題，提高共享介質的利用率，通常利用網橋和交換機來分隔互聯(lián)網的各個網段中的通信量，以建立多個分離的沖突域。但是，當網橋和交換機接收到一個未知轉發(fā)信息的數(shù)據(jù)幀時，為了保證該幀能被目的結點正確接收，將該幀從所有的端口廣播出去。于是可以看出，網橋和交換機的沖突域等于端口的個數(shù)，廣播域為1。因此網橋不能抑制網絡風暴。

39主機甲和主機乙之間已建立了一個TCP連接，TCP最大段長度為1000字節(jié)，若主機甲的當前擁塞窗口為4000字節(jié)，在主機甲向主機乙連續(xù)發(fā)送兩個最大段后，成功收到主機乙發(fā)送的對第一個段的確認段，確認段中通告的接收窗口大小為2000字節(jié)，則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是（　　）。

A．1000

B．2000

C．3000

D．4000

【答案】A

【解析】發(fā)送方的發(fā)送窗口的上限值應該取接收方窗口和擁塞窗口這兩個值中較小的一個，于是此時發(fā)送方的發(fā)送窗口為min{4000，2000）＝2000字節(jié)，由于發(fā)送方還沒有收到第二個最大段的確認，所以此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)為2000－1000＝1000字節(jié)，正確選項為A。

40如果本地域名服務無緩存，當采用遞歸方法解析另一網絡某主機域名時，用戶主機、本地域名服務器發(fā)送的域名請求消息數(shù)分別為（　　）。

A．1條，1條

B．1條，多條

C．多條，1條

D．多條，多條

【答案】A

【解析】所謂遞歸查詢方式就是：如果主機所詢問的本地域名服務器不知道被查詢域名的IP地址，那么本地域名服務器就以DNS客戶的身份向其他服務器繼續(xù)發(fā)出查詢請求報文，而不是讓該主機自行下一步的查詢。所以主機只需向本地域名服務器發(fā)送一條域名請求，采用遞歸查詢方法，本地域名服務器也只需向上一級的根域名服務器發(fā)送一條域名請求，然后依次遞歸。正確選項為A。

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

41（10分）將關鍵字序列（7，8，30，11，18，9，14）散列存儲到散列表中，散列表的存儲空間是一個下標從0開始的一維數(shù)組。散列函數(shù)是：H（key）＝（key×3）MOD7，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。

（1）請畫出所構造的散列表。

（2）分別計算等概率情況下查找成功和查找不成功的平均查找長度。

解：（1）要求裝填因子為0.7，數(shù)組的長度應該為7/0.7＝10，數(shù)組下標為0～9。各關鍵字的散列函數(shù)值如下表：

采用線性探測法再散列法處理沖突，所構造的散列表為：

（2）查找成功時，在等概率情況下，查找表中每個元素的概率是相等的，因此是根據(jù)表中元素個數(shù)來計算平均查找長度，各關鍵字的比較次數(shù)如下表所示：

故查找成功的平均查找長度為（1＋1＋1＋1＋3＋3＋2）/7＝12/7。

在不成功的情況下，由于任意關鍵字key，H（key）的值只能是0～6之間，H（key）為0需要比較3次，H（key）為1需要比較2次，H（key）為2需要比較l次，H（key）為3需要比較2次，H（key）為4需要比較l次，H（key）為5需要比較5次，H（key）為6需要比較4次，共7種情況，如下表所示：

所以，在等概率下，查找失敗的平均查找長度為：（3＋2＋1＋2＋1＋5＋4）/7＝18/7。

42（13分）設將n（n＞1）個整數(shù)存放到一維數(shù)組R中。試設計一個在時間和空間兩方面都盡可能高效的算法，將R中存有的序列循環(huán)左移P（0＜P＜n）個位置，即將R中的數(shù)據(jù)由（X₀，X₁，…， X_n－1）變換為（x_p，x_p＋1，…，x_n－1，x₀，x₁，…，x_p－1）。要求：

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

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

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

解：（1）算法的基本設計思想：先將n個數(shù)據(jù)由x₀，x₁，…，x_p，…，x_n－1原地逆置，得到x_n－1，…，x_p，x_p－1，…，x₀然后再將數(shù)組R中的前，n－P個數(shù)和后P個數(shù)分別原地逆置，最終得到結果x_p，x_p＋1，…，x_n－1，x₀，x₁，…，x_p－1。

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

（3）說明算法的復雜性：上述算法中3個Reverse函數(shù)的的時間復雜度分別為O（p/2）、O（（p－2）/2）為O（n/2），故算法的時間復雜度為O（n），算法的空間復雜度為O（1）。

43（11分）某計算機字長16位，主存地址空間大小為128KB，按字編址，采用單字長指令格式，指令各字段定義如下：

轉移指令采用相對尋址方式，相對偏移量用補碼表示，尋址方式定義如下：

注：（X）表示存儲器地址X或寄存器X的內容。請回答下列問題：

（1）該指令系統(tǒng)最多可有多少條指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器（MAR）和存儲器數(shù)據(jù)寄存器（MDR）至少各需要多少位？

（2）轉移指令的目標地址范圍是多少？

（3）若操作碼0010B表示加法操作（助記符為add），寄存器R4和R5的編號分別為100B和101B，R4的內容為l234H，R5的內容為5678H，地址1234H的內容為5678H，地址5678H中的內容為1234H，則匯編語句“add（R4），（R5）＋”（逗號前為源操作數(shù)，逗號后為目的操作數(shù)）對應的機器碼是什么（十六進制表示）？該指令執(zhí)行后，哪些寄存器和存儲單元的內容會改變？改變后的內容是什么？

解：（1）指令操作碼占4位，則指令系統(tǒng)最多可有2⁴＝16條不同的指令；指令操作上占6位，尋址方式占3位，于是寄存器編號占3位，該計算機最多可以有2³＝8個通用寄存器；主存容量為128KB，計算機字長為16位，故主存有l(wèi)28KB/2B＝2¹⁶個存儲單元，故MDR和MAR至少各需l6位。

（2）由于寄存器字長為l6位，所以轉移指令的目標地址范圍為0000H～FFFFH。。

（3）匯編語句add（R4），（R5）＋對應的機器碼為0010 0011 0001 0101B＝2315H，該指令執(zhí)行后，寄存器R5和地址為5678H的存儲單元的內容會改變，改變后的內容分別為：

（ACC）＝（（R4））＋（（R5））＝5678H＋1234H＝68ACH

（R5）＝（R5）＋1＝5678H＋1＝5679H

（1234H）＝（ACC）＝68ACH

44（12分）某計算機的主存地址空間大小為256MB，按字節(jié)編址，指令Cache和數(shù)據(jù)Cache分離，均有8個Cache行，每個Cache行大小為64B，數(shù)據(jù)Cache采用直接映射方式。現(xiàn)有兩個功能相同的程序A和B，其偽代碼如下所示：程序A：程序B：

假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i，j，sum均分配在寄存器中，數(shù)組a按行優(yōu)先方式存放，首地址320（十進制數(shù)）。請回答下列問題，要求說明理由或給出計算過程。

（1）若不考慮用于Cache一致性維護和替換算法的控制位，則數(shù)據(jù)Cache的總容量為多少？

（2）數(shù)組數(shù)據(jù)a[0][31]和a[1][1]各自所在的主存塊對應的Cache行號分別是多少（Cache行號從0開始）？

（3）程序A和B的數(shù)據(jù)訪問命中率各是多少？哪個程序的執(zhí)行時間更短？

解：

（1）每個Cache行對應一個標記項，標記項包括有效位、臟位、替換控制位以及標記位。由主存空間大小為256M可知地址總長度為28位，其中塊內地址為log₂64＝6位，Cache塊號為log₂8＝3位，不考慮一致性維護和替換算法的控制位，則Tag的位數(shù)為28－6－3＝19位，還需一位有效位，數(shù)據(jù)Cache共有8行，故Cache的總容量為8*（64＋20/8）B＝532B

（2）數(shù)組a在主存的存放位置及其與Cache之間的映射關系如下圖所示：

數(shù)組按行優(yōu)先方式存放，首地址為320，數(shù)組元素占4個字節(jié)。a[0][31]所在的主存塊對應的Cache行號為（320＋31*4）/64＝6；a[1][1]所在的主存塊對應的Cache行號為（320＋256*4＋1*4）/64%8＝5。

（3）數(shù)組a的大小為256*256*4B＝2¹⁸B，占用2¹⁸/64＝212個主存塊，按行優(yōu)先存放，程序A逐行訪問數(shù)組a，共需訪問的次數(shù)為2¹⁶次，每個字塊的第一個數(shù)未面中，因此未面中次數(shù)為2¹²次，程序A的數(shù)據(jù)訪問命中率為（2¹⁶－2¹²）/2¹⁶*100%＝93.75%；Cache總容量為64B*8＝512B，數(shù)組a一行的大小為1KB正好是Cache容量的2倍，可知不同行的同一列數(shù)組元素使用的是同一個Cache單元，而程序B逐列訪問數(shù)組a的數(shù)據(jù)時，都會將之前的字塊置換出，也即每次訪問都不會面中，故程序B的數(shù)據(jù)訪問命中率是0，因此程序A的執(zhí)行過程更短。

45（7分）假設計算機系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調度策略。使用2KB的內存空間記錄16384個磁盤塊的空閑狀態(tài)。

（1）請說明在上述條件下如何進行磁盤空閑狀態(tài)的管理。

（2）設某單面磁盤旋轉速度為每分鐘6000轉，每個磁道有100個扇區(qū)，相鄰磁道間的平均移動時間為1ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動（如下圖所示），磁道號請求隊列為50，90，30，120，對請求隊列中的每個磁道需要讀取1個隨機分布的扇區(qū)，則讀完這4個扇區(qū)總共需要多少時間？要求給出計算過程。

（3）如果將磁盤替換為隨機訪問的Flash半導體存儲器（如U盤、SSD等），是否有比CSCAN更高效的磁盤調度策略？若有，給出磁盤調度策略的名稱并說明理由；若無，說明理由。

解：

（1）采用位示圖法管理磁盤空閑塊，每一位表示一個磁盤塊的狀態(tài)，共需要16384/32＝512 個字節(jié)即2KB的空間，正好可放在系統(tǒng)提供的內存中。

（2）采用CSCAN調度算法，訪問磁道的順序和移動的磁道數(shù)如下表所示：

故移動的磁道數(shù)為20＋90＋20＋40＝170，所花的時間為170ms。由于轉速為6000r/min，則平均旋轉延遲為5ms，總的旋轉延遲時間為20ms，讀取一個扇區(qū)的平均時間為0.1ms，故讀取4個扇區(qū)所花的時間為0.4ms。綜上所述，讀取磁道上所有扇區(qū)所花的總時間為170＋5*4＋0.4＝190.4ms。

（3）采用先來先服務（FCFS）調度策略更高效，因為Flash半導體存儲器的物理結構不需要考慮尋道時間和旋轉延遲，可直接按I/O請求的先后順序服務。

46（8分）設某計算機的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若某進程最多需要6頁（Page）數(shù)據(jù)存儲空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框（PageFrame）。在時刻260前的該進程訪問情況如下表所示（訪問位即使用位）。

當該進程執(zhí)行到時刻260時，要訪問的邏輯地址為17CAH的數(shù)據(jù)，請回答下列問題：

（1）該邏輯地址對應的頁號是多少？

（2）若采用先進先出（FIFO）置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。

（3）若采用時鐘（CLOCK）置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。（設搜索下一頁的指針沿順時針方向移動，且當前指向2號頁框，如圖所示）

解：

（1）由題可知計算機的邏輯地址空間和物理地址空間均為64KB＝216B，按字節(jié)編址，并且頁的大小為1K＝210，故邏輯地址和物理地址的地址格式均為:

地址17CA＝0001 0111 1100 1010B，故可知其邏輯頁號為000101B＝5。

（2）根據(jù)FIFO算法，需要替換出最早裝入的頁，故需置換0號頁，將5號頁裝入7號頁框中，所以物理地址為0001 1111 1100 1010B＝1FCAH。

（3）根據(jù)CLOCK算法，如果當前指針所指頁框的使用位為0，則替換該頁，否則將使用位清零，并將指針指向下一個頁框，繼續(xù)查找。由題可知，將從2號頁框開始，前4次查找頁框號的順序為2、4、7、9，并將對應頁框的使用位清零。在第5次查找中，指針指向2號頁框，因2號頁框的使用位已經為0，故將2號頁框的頁將5號裝入2號頁框，并將其對應使用位設置為1，所以對應的物理地址為0000 1011 1100 1010B＝0BCAH。

47（9分）某局域網采用CSMA/CD協(xié)議實現(xiàn)介質訪問控制，數(shù)據(jù)傳輸率為10Mbps，主機甲和主機乙之間的距離為2km，信號傳播速度是200000km/s。請回答下列問題，要求說明理由或寫出計算過程。

（1）若主機甲和主機乙發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機均檢測到沖突時刻止，最短需經過多長時間？最長需經過多長時間？（假設主機甲和主機乙發(fā)送數(shù)據(jù)過程中，其他主機不發(fā)送數(shù)據(jù)）

（2）若網絡不存在任何沖突與差錯，主機甲總是以標準的最長以太網數(shù)據(jù)幀（1518字節(jié)）向主機乙發(fā)送數(shù)據(jù)，主機乙每成功收到一個數(shù)據(jù)幀后立即向主機甲發(fā)送一個64字節(jié)的確認幀，主機甲收到確認幀后方可發(fā)送下一個數(shù)據(jù)幀，此時主機甲的有效數(shù)據(jù)傳輸速率是多少？（不考慮以太網幀的前導碼）

解：（1）當甲乙兩臺主機同時向對方發(fā)送數(shù)據(jù)時，兩臺主機均檢測到沖突的時間最短：T_min＝（1km/200000km/s）×2＝10μs；當一臺主機發(fā)送的數(shù)據(jù)就要到達另一臺主機時，另一臺主機才發(fā)送數(shù)據(jù)，兩臺主機均檢測到沖突的時間最長：T_min＝（2km/200000km/s）×2＝20μs

（2）有效數(shù)據(jù)傳輸速率＝發(fā)送的有效數(shù)據(jù)/發(fā)送有效數(shù)據(jù)所用的總時間。發(fā)送的有效數(shù)據(jù)＝l500B＝1500×8bit＝12000bit；發(fā)送l518B的發(fā)送時間＝l518×8/10Mbps＝1214.4μs；數(shù)據(jù)幀的傳播時間＝2km/200000km/s＝10μs；確認幀的發(fā)送時間＝64×8/10Mbps＝51.2μs ；確認幀的傳播時間＝2km/200000km/s＝10μs ；發(fā)送l518B所用的總時間為1214.4μs＋10μs＋10μs＋51.2μs＝1285.6μs主機甲的有效數(shù)據(jù)傳輸率為l2000bit/1285.6μs＝9.33Mbps。