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

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

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

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

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

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

D．a(chǎn)，f，e，d，c，b

【答案】D

【解析】4個(gè)選項(xiàng)所給序列的進(jìn)、出棧操作序列分別為：

選項(xiàng)A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop

選項(xiàng)B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop

選項(xiàng)C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop

選項(xiàng)D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop

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

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

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ù)題意，隊(duì)列兩端都可以輸入數(shù)據(jù)元素，但是只能在一端輸出數(shù)據(jù)元素，這種隊(duì)列為輸出受限的雙端隊(duì)列。本題解題方法分別判斷每個(gè)選項(xiàng)如何入隊(duì)和出隊(duì)，從而得出不可能的情況。

假設(shè)L代表從左端入隊(duì)，R代表從右端入隊(duì)，出隊(duì)都是從左端L出。四個(gè)選項(xiàng)所給序列的進(jìn)隊(duì)操作序列分別為：

選項(xiàng)A：aL（或aR），bL，cR，dR，eR

選項(xiàng)B：aL（或aR），bL，cR，dL，eR

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

選項(xiàng)D：aL（或aR），bL，cL，dR，eL

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

【答案】D

【解析】線索二叉樹(shù)利用二叉鏈表的空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼信息，解題思路較簡(jiǎn)單。題中所給二叉樹(shù)的后序序列為dbca。結(jié)點(diǎn)d無(wú)前驅(qū)和左子樹(shù)，左鏈域空，無(wú)右子樹(shù)，右鏈域指向其后繼結(jié)點(diǎn)b；結(jié)點(diǎn)b無(wú)左子樹(shù)，左鏈域指向其前驅(qū)結(jié)點(diǎn)d；結(jié)點(diǎn)c無(wú)左子樹(shù)，左鏈域指向其前驅(qū)結(jié)點(diǎn)b，無(wú)右子樹(shù)，右鏈域指向其后繼結(jié)點(diǎn)a。所以正確選項(xiàng)為D。

4在下圖所示的平衡二叉樹(shù)中，插入關(guān)鍵字48后得到一棵新平衡二叉樹(shù)。在新平衡二叉樹(shù)中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（　　）。

A．13、48

B．24、48

C．24、53

D．24、90

【答案】C

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

顯然，在調(diào)整后的新平衡二叉樹(shù)中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是24，53。

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

A．41

B．82

C．113

D．122

【答案】B

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

6對(duì)n（n≥2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)。下列關(guān)于該哈夫曼樹(shù)的敘述中，錯(cuò)誤的是（　　）。

A．該樹(shù)一定是一棵完全二叉樹(shù)

B．樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)

C．樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D．樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值

【答案】A

【解析】哈夫曼樹(shù)為帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，但不一定是完全二叉樹(shù)，選項(xiàng)A錯(cuò)誤；哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，選項(xiàng)B正確；構(gòu)造哈夫曼樹(shù)時(shí)，最先選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，C正確；哈夫曼樹(shù)中任一非葉結(jié)點(diǎn)P的權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和，其權(quán)值不小于其左右子樹(shù)根結(jié)點(diǎn)的權(quán)值，在與結(jié)點(diǎn)P的左右子樹(shù)根結(jié)點(diǎn)處于同一層的結(jié)點(diǎn)中，若存在權(quán)值大于結(jié)點(diǎn)P權(quán)值的結(jié)點(diǎn)Q，那么結(jié)點(diǎn)Q與其兄弟結(jié)點(diǎn)中權(quán)值較小的一個(gè)應(yīng)該與結(jié)點(diǎn)P作為左右子樹(shù)構(gòu)造新的二叉樹(shù)，由此可知，哈夫曼樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。

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

A．6

B．15

C．16

D．21

【答案】C

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

8對(duì)下圖進(jìn)行拓?fù)渑判颍梢缘玫讲煌耐負(fù)湫蛄械膫€(gè)數(shù)是（　　）。

A．4

B．3

C．2

D．1

【答案】B

【解析】拓?fù)渑判虻牟襟E為：

（1）在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)并且輸出它；

（2）從圖中刪除該頂點(diǎn)和以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出。由于沒(méi)有前驅(qū)的頂點(diǎn)可能不唯一，所以拓?fù)渑判虻慕Y(jié)果也不唯一。題中所給圖有三個(gè)不同的拓?fù)渑判蛐蛄校謩e為abced，abecd，aebcd。

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

A．4

B．5

C．6

D．7

【答案】B

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

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

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

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

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

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

【答案】D

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

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

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

第一趟：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í)從前往后依次比較，使大值“沉底”。希爾排序的基本思想是：先對(duì)序列進(jìn)行“宏觀調(diào)整”，待序列中的記錄“基本有序”時(shí)再進(jìn)行直接插入排序。宏觀調(diào)整的方法是：通過(guò)某種規(guī)則將大的待排序序列分割為若干小的待排序序列，再依次對(duì)這些小的序列直接插入排序。宏觀調(diào)整可以多次，每次分割的序列數(shù)逐漸增多，而每個(gè)序列中所包含的元素?cái)?shù)逐漸減少。歸并排序的基本操作是將多個(gè)小的有序序列合并為一個(gè)大的有序序列，然后“逐趟歸并”，直至整個(gè)序列為有序?yàn)橹埂；鶖?shù)排序是分配排序的一種，這類(lèi)排序不是通過(guò)關(guān)鍵字比較，而是通過(guò)“分配”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序的。本題中，很容易看出大值逐漸“沉底”，顯然使用的是起泡排序法。

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

Ⅰ．提高CPU時(shí)鐘頻率

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

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

A．Ⅰ、Ⅱ

B．Ⅰ、Ⅲ

C．Ⅱ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】D

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

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

A．r₁×r₂

B．r₂×r₃

C．r₁×r₄

D．r₂×r₄

【答案】B

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

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

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

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

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

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

A．Ⅰ、Ⅱ

B．Ⅰ、Ⅲ

C．Ⅱ、Ⅲ

D．Ⅲ、Ⅳ

【答案】B

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

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

A．0000H

B．0600H

C．0700H

D．0800H

【答案】D

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

16下列有關(guān)RAM和ROM的敘述中，正確的是（　　）。

Ⅰ．RAM是易失性存儲(chǔ)器，ROM是非易失性存儲(chǔ)器

Ⅱ．RAM和ROM都采用隨機(jī)存取方式進(jìn)行信息訪問(wèn)

Ⅲ．RAM和ROM都可用作Cache

Ⅳ．RAM和ROM都需要進(jìn)行刷新

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅱ、Ⅳ

D．Ⅱ、Ⅲ、Ⅳ

【答案】A

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

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

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

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

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

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

【答案】D

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

18下列寄存器中，匯編語(yǔ)言程序員可見(jiàn)的是（　　）。

A．存儲(chǔ)器地址寄存器（MAR）

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

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

D．指令寄存器（IR）

【答案】B

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

19下列選項(xiàng)中，不會(huì)引起指令流水線阻塞的是（　　）。

A．?dāng)?shù)據(jù)旁路（轉(zhuǎn)發(fā)）

B．?dāng)?shù)據(jù)相關(guān)

C．條件轉(zhuǎn)移

D．資源沖突

【答案】A

【解析】由于采用流水線方式，相鄰或相近的兩條指令可能會(huì)因?yàn)榇嬖谀撤N關(guān)聯(lián)，后一條指令不能按照原指定的時(shí)鐘周期運(yùn)行，從而使流水線斷流。有三種相關(guān)可能引起指令流水線阻塞：①結(jié)構(gòu)相關(guān)，又稱(chēng)資源相關(guān)；②數(shù)據(jù)相關(guān)；③控制相關(guān)，又稱(chēng)指令相關(guān)，主要由轉(zhuǎn)移指令引起。

20下列選項(xiàng)中的英文縮寫(xiě)均為總線標(biāo)準(zhǔn)的是（　　）。

A．PCI、CRT、USB、EISA

B．ISA、CPI、VESA、EISA

C．ISA、SCSl、RAM、MIPS

D．ISA、EISA、PCI、PCI-Express

【答案】D

【解析】選項(xiàng)A中的CRT和USB、選項(xiàng)B中的CPI、選項(xiàng)C中的RAM和MIPS均不是總線標(biāo)準(zhǔn)的英文縮寫(xiě)，只有選項(xiàng)D中的英文縮寫(xiě)均為總線標(biāo)準(zhǔn)。

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

Ⅰ．保護(hù)現(xiàn)場(chǎng)；

Ⅱ．開(kāi)中斷；

Ⅲ．關(guān)中斷；

Ⅳ．保存斷點(diǎn)；

Ⅴ．中斷事件處理；

Ⅵ．恢復(fù)現(xiàn)場(chǎng)；

Ⅶ．中斷返回

A．Ⅰ→Ⅴ→Ⅵ→Ⅱ→Ⅶ

B．Ⅲ→Ⅰ→Ⅴ→Ⅶ

C．Ⅲ→Ⅳ→Ⅴ→Ⅵ→Ⅶ

D．Ⅳ→Ⅰ→Ⅴ→Ⅵ→Ⅶ

【答案】A

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

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

A．245Mbps

B．979Mbps

C．1958Mbps

D．7834Mbps

【答案】D

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

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

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

B．中斷

C．庫(kù)函數(shù)

D．原語(yǔ)

【答案】A

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

24下列選項(xiàng)中，導(dǎo)致創(chuàng)建新進(jìn)程的操作是（　　）。

Ⅰ．用戶(hù)登錄成功

Ⅱ．設(shè)備分配

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

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】C

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

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

A．0、1

B．1、0

C．1、2

D．2、0

【答案】B

【解析】信號(hào)量初值是3表示資源數(shù)有3個(gè)，當(dāng)前為1表示已經(jīng)用掉2個(gè)，剩余可用的資源數(shù)就只有1個(gè)了，由于資源有剩余，可見(jiàn)沒(méi)有其他進(jìn)程等待使用該資源，故進(jìn)程數(shù)為0。

26下列選項(xiàng)中，降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是（　　）。

A．進(jìn)程的時(shí)間片用完

B．進(jìn)程剛完成I/O，進(jìn)入就緒隊(duì)列

C．進(jìn)程長(zhǎng)期處于就緒隊(duì)列

D．進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行態(tài)

【答案】A

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

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

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

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

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

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

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

【答案】D

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

28某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存容量為55MB（初始為空閑），采用最佳適配（BestFit）算法，分配和釋放的順序?yàn)椋悍峙?5MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時(shí)主存中最大空閑分，區(qū)的大小是（　　）。

A．7MB

B．9MB

C．10MB

D．15MB

【答案】B

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

29某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式，按字節(jié)編址，頁(yè)大小為2¹⁰字節(jié)，頁(yè)表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為：

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

A．64

B．128

C．256

D．512

【答案】B

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

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

A．33KB

B．519KB

C．1057KB

D．16513KB

【答案】C

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

31設(shè)置當(dāng)前工作目錄的主要目的是（　　）。

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

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

C．加快文件的檢索速度

D．加快文件的讀/寫(xiě)速度

【答案】C

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

32本地用戶(hù)通過(guò)鍵盤(pán)登錄系統(tǒng)時(shí)，首先獲得的鍵盤(pán)輸入信息的程序是（　　）。

A．命令解釋程序

B．中斷處理程序

C．系統(tǒng)調(diào)用服務(wù)程序

D．用戶(hù)登錄程序

【答案】B

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

33下列選項(xiàng)中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是（　　）。

A．網(wǎng)絡(luò)的層次

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

C．協(xié)議的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)

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

【答案】C

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

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

A．80ms

B．80.08ms

C．80.16ms

D．80.24ms

【答案】C

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

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

A．R2可以經(jīng)過(guò)R1到達(dá)net1，跳數(shù)為17

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

C．R1可以經(jīng)過(guò)R2到達(dá)net1，跳數(shù)為17

D．R1不能經(jīng)過(guò)R2到達(dá)net1

【答案】D

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

36若路由器R因?yàn)閾砣麃G棄IP分組，則此時(shí)R可向發(fā)出該IP分組的源主機(jī)發(fā)送的ICMP報(bào)文件類(lèi)型是（　　）。

A．路由重定向

B．目的不可達(dá)

C．源抑制

D．超時(shí)

【答案】C

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

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

A．32，8

B．32，6

C．8，32

D．8，30

【答案】B

【解析】子網(wǎng)號(hào)為5位，在CIDR中可以表示2⁵＝32個(gè)子網(wǎng)，主機(jī)號(hào)為3位，除去全0和全1的情況可以表示6個(gè)主機(jī)地址，答案為B。

38下列網(wǎng)絡(luò)設(shè)備中，能夠抑制廣播風(fēng)暴的是（　　）。

Ⅰ．中繼器

Ⅱ．集線器

Ⅲ．網(wǎng)橋

Ⅳ．路由器

A．Ⅰ、Ⅱ

B．僅Ⅲ

C．Ⅲ、Ⅳ

D．僅Ⅳ

【答案】D

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

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

A．1000

B．2000

C．3000

D．4000

【答案】A

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

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

A．1條，1條

B．1條，多條

C．多條，1條

D．多條，多條

【答案】A

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

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

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

（1）請(qǐng)畫(huà)出所構(gòu)造的散列表。

（2）分別計(jì)算等概率情況下查找成功和查找不成功的平均查找長(zhǎng)度。

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

采用線性探測(cè)法再散列法處理沖突，所構(gòu)造的散列表為：

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

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

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

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

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

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

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

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

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

（2）用C語(yǔ)言算法描述如下：

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

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

轉(zhuǎn)移指令采用相對(duì)尋址方式，相對(duì)偏移量用補(bǔ)碼表示，尋址方式定義如下：

注：（X）表示存儲(chǔ)器地址X或寄存器X的內(nèi)容。請(qǐng)回答下列問(wèn)題：

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

（2）轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？

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

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

（2）由于寄存器字長(zhǎng)為16位，所以轉(zhuǎn)移指令的目標(biāo)地址范圍為0000H～FFFFH。。

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

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

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

（1234H）＝（ACC）＝68ACH

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

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

（1）若不考慮用于Cache一致性維護(hù)和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘繛槎嗌伲?/p>

（2）數(shù)組數(shù)據(jù)a[0][31]和a[1][1]各自所在的主存塊對(duì)應(yīng)的Cache行號(hào)分別是多少（Cache行號(hào)從0開(kāi)始）？

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

解：（1）每個(gè)Cache行對(duì)應(yīng)一個(gè)標(biāo)記項(xiàng)，標(biāo)記項(xiàng)包括有效位、臟位、替換控制位以及標(biāo)記位。由主存空間大小為256M可知地址總長(zhǎng)度為28位，其中塊內(nèi)地址為log₂64＝6位，Cache塊號(hào)為log₂8＝3位，不考慮一致性維護(hù)和替換算法的控制位，則Tag的位數(shù)為28－6－3＝19位，還需一位有效位，數(shù)據(jù)Cache共有8行，故Cache的總?cè)萘繛?*（64＋20/8）B＝532B

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

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

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

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

（1）請(qǐng)說(shuō)明在上述條件下如何進(jìn)行磁盤(pán)空閑狀態(tài)的管理。

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

（3）如果將磁盤(pán)替換為隨機(jī)訪問(wèn)的Flash半導(dǎo)體存儲(chǔ)器（如U盤(pán)、SSD等），是否有比CSCAN更高效的磁盤(pán)調(diào)度策略？若有，給出磁盤(pán)調(diào)度策略的名稱(chēng)并說(shuō)明理由；若無(wú)，說(shuō)明理由。

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

（2）采用CSCAN調(diào)度算法，訪問(wèn)磁道的順序和移動(dòng)的磁道數(shù)如下表所示：

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

（3）采用先來(lái)先服務(wù)（FCFS）調(diào)度策略更高效，因?yàn)镕lash半導(dǎo)體存儲(chǔ)器的物理結(jié)構(gòu)不需要考慮尋道時(shí)間和旋轉(zhuǎn)延遲，可直接按I/O請(qǐng)求的先后順序服務(wù)。

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

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

（1）該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)是多少？

（2）若采用先進(jìn)先出（FIFO）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過(guò)程。

（3）若采用時(shí)鐘（CLOCK）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過(guò)程。（設(shè)搜索下一頁(yè)的指針沿順時(shí)針?lè)较蛞苿?dòng)，且當(dāng)前指向2號(hào)頁(yè)框，如圖所示）

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

地址17CA＝0001 0111 1100 1010B，故可知其邏輯頁(yè)號(hào)為000101B＝5。

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

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

47（9分）某局域網(wǎng)采用CSMA/CD協(xié)議實(shí)現(xiàn)介質(zhì)訪問(wèn)控制，數(shù)據(jù)傳輸率為10Mbps，主機(jī)甲和主機(jī)乙之間的距離為2km，信號(hào)傳播速度是200000km/s。請(qǐng)回答下列問(wèn)題，要求說(shuō)明理由或?qū)懗鲇?jì)算過(guò)程。

（1）若主機(jī)甲和主機(jī)乙發(fā)送數(shù)據(jù)時(shí)發(fā)生沖突，則從開(kāi)始發(fā)送數(shù)據(jù)時(shí)刻起，到兩臺(tái)主機(jī)均檢測(cè)到?jīng)_突時(shí)刻止，最短需經(jīng)過(guò)多長(zhǎng)時(shí)間？最長(zhǎng)需經(jīng)過(guò)多長(zhǎng)時(shí)間？（假設(shè)主機(jī)甲和主機(jī)乙發(fā)送數(shù)據(jù)過(guò)程中，其他主機(jī)不發(fā)送數(shù)據(jù)）

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

解：（1）當(dāng)甲乙兩臺(tái)主機(jī)同時(shí)向?qū)Ψ桨l(fā)送數(shù)據(jù)時(shí)，兩臺(tái)主機(jī)均檢測(cè)到?jīng)_突的時(shí)間最短：T_min＝（1km/200000km/s）×2＝10μs；當(dāng)一臺(tái)主機(jī)發(fā)送的數(shù)據(jù)就要到達(dá)另一臺(tái)主機(jī)時(shí)，另一臺(tái)主機(jī)才發(fā)送數(shù)據(jù)，兩臺(tái)主機(jī)均檢測(cè)到?jīng)_突的時(shí)間最長(zhǎng)：T_min＝（2km/200000km/s）×2＝20μs

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