目錄

第一部分沈陽師范大學教育技術(shù)學院862計算機學科專業(yè)基礎(chǔ)綜合

（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編

2014年沈陽師范大學教育技術(shù)學院867計算機學科專業(yè)基礎(chǔ)綜合（數(shù)

據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題

2013年沈陽師范大學教育技術(shù)學院867計算機學科專業(yè)基礎(chǔ)綜合（數(shù)

據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題

第二部分全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合

歷年真題及詳解

2012年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題

2012年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題及詳解

2011年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題

2011年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題及詳解

2010年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題

2010年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題及詳解

2009年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題

2009年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真

題及詳解

第一部分沈陽師范大學教育技術(shù)學院862

計算機學科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操

作系統(tǒng)）歷年考研真題匯編

2014年沈陽師范大學教育技術(shù)學院867計算機學科

專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題

科目代碼：867

科目名稱：計算機學科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）

適用專業(yè)名稱：計算機應用技術(shù)

考生注意：請將答案寫在答題紙上，寫在本題簽及草紙上無效。考

試后本題簽同答題紙一并交回。

一、單項選擇題（共10題，每題2分，合計20分）

1．某算法的時間復雜度為O(n2)，表明該算法（）。

A．問題規(guī)模是n2

B．執(zhí)行時間等于n2

C．執(zhí)行時間與n2成正比

D．問題規(guī)模與n2成正比

2設(shè)線性表有n個元素，以下操作中，（）在順序表上實現(xiàn)比在鏈表

上實現(xiàn)效率更高。

A．輸出第i（1≤i≤n）個元素

B．交換第1個元素與第2個元素的值

C．順序輸出這n個元素的值

D．輸出與給定值x相等的元素在線性表中的序號

3．給定一個空棧，若10、20、23、13依次進棧，然后有兩個數(shù)出

棧，又有3個數(shù)進棧，第一次進棧的23現(xiàn)在在（）。

A．已出棧

B．從棧底算起第3個

C．棧頂

D．從棧底算起第4個

4．循環(huán)隊列qu（其隊頭指針front指向隊列中隊頭元素的前一個位

置，隊尾指針rear指向隊尾元素的位置，隊列中的單元個數(shù)為MaxSize）

的隊滿足條件是（）。

A．（qu.rear+1）%MaxSize==(qu.front+1)%MaxSize

B．(qu.rear+1)%MaxSize==qu.front+1

C．(qu.rear+1)%MaxSize==qu.front

D．qu.rear==qu.front

5．一棵二叉樹的中序序列為ABDCEFG，后序序列為BDCAFGE，

則其左子樹中的節(jié)點個數(shù)為（）。

A．3

B．2

C．4

D．5

6．根據(jù)使用頻率為5個字符設(shè)計的哈夫曼編碼不可能是（）。

A．111,110,10,01,00

B．000,001,010,011,1

C．100,11,10,1,0

D．001,000,01,11,10

7．對所示的無向圖，從頂點1開始進行深度優(yōu)先遍歷，可得到的頂

點訪問序列為（）。

A．1243576

B．1243567

C．1245637

D．1234576

8．對于下圖，以下（）是其拓撲序列。

A．1,3,4,6,2,5,7

B．1,3,2,6,4,5,7

C．1,3,4,5,2,6,7

D．1,2,5,3,4,6,7

9．對數(shù)據(jù)序列{15,9,7,8,20,-1,4}進行排序,一趟排序后的結(jié)果為

{9,15,7,8,20,-1,4},采用的是（）。

A．簡單選擇排序

B．起泡排序

C．直接插入排序

D．堆排序

10．對一組數(shù)據(jù)(2,12,16,88,5,10)進行排序,若前三趟的結(jié)果如下:

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

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

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

則采用的排序方法可能是()。

A．起泡排序

B．希爾排序

C．歸并排序

D．基數(shù)排序

二、應用題（共4題，每題10分，合計40分）

11．使用普里姆算法構(gòu)造如圖所示的圖G中從頂點1開始的一棵最

小生成樹。

12．設(shè)有一組關(guān)鍵字{19,1,23,14,55,20,84,27,68,11,10,77}，其哈希

函數(shù)如下：

H(key)=key%13

采用開放地址法的線性探測法解決沖突，試在0~18的哈希表中對該

關(guān)鍵字序列構(gòu)造哈希表。

13．已知有6個頂點（頂點編號為0-5）的有向帶權(quán)圖G，其鄰接矩

陣A為上三角矩陣，按行為主序（行優(yōu)先）保存在如下的一維數(shù)組中。

46∞∞∞5∞∞

要求：

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

（2）畫出有向帶權(quán)圖G。

（3）求圖G的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。

14．將整數(shù)序列{4,5,7,2,1,3,6}中的數(shù)依次插入到一棵空的平衡二叉

樹中，構(gòu)造相應的平衡二叉樹。

三、算法設(shè)計題（共3題，每題10分，合計30分）

15．設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表，采用帶頭節(jié)點的hc單鏈

表存放，設(shè)計一個就地算法，將其拆分為兩個線性表（它們都用單鏈表

存放），使得：

A={a1,,a2,…,an}，B={b1,b2,…,bn}

16．假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，試設(shè)計一個算法，計算

一棵給定二叉樹的所有分支節(jié)點個數(shù)。

17．設(shè)計一個算法，判斷一個數(shù)據(jù)序列是否構(gòu)成一個小根堆。

四、簡答題（共6題，每題5分，合計30分）

18．什么是操作系統(tǒng)的基本功能？

19．描述系統(tǒng)調(diào)用的含義。

20．說明什么是進程間的直接制約與間接制約。

21．說明什么是虛擬存儲器。

22．請說明分區(qū)存儲管理方式的主要優(yōu)缺點。

23．說明什么是中斷。

五、綜合題（共2題，每題15分，合計30分）

24．若有以下四個作業(yè)以1、2、3、4的順序，在0時刻幾乎同時到

達系統(tǒng)并立即進入調(diào)度：

作業(yè)名所需CPU時間

作業(yè)19小時

作業(yè)22小時

作業(yè)310小時

作業(yè)45小時

假設(shè)系統(tǒng)中沒有其他作業(yè)，試給出對它們實施FCFS調(diào)度算法的計

算結(jié)果，并計算其平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

25．幾個并行進程共享一個數(shù)據(jù)集（如文件或表格）時，有些進程

可能只是要求讀這數(shù)據(jù)集的內(nèi)容，而另一些進程則可能要求修改這數(shù)據(jù)

集的內(nèi)容。這種情況在操作系統(tǒng)中是很普遍的。通常我們稱讀數(shù)據(jù)的進

程為讀者，而把要求修改數(shù)據(jù)的進程稱為寫者。用P、V操作來描述讀

者—寫者問題。

2013年沈陽師范大學教育技術(shù)學院867計算機學科

專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題

代碼：868

科目名稱：計算機學科專業(yè)基礎(chǔ)綜合

適用專業(yè)名稱：計算機應用技術(shù)

考生注意：請將答案寫在答題紙上，寫在本題簽及草紙上無效?？?/p>

試后本題簽同答題紙一并交回。

一、單項選擇題（共30題，每題2分，合計60分）

1．某算法的時間復雜度為O(n2)，表明該算法的（）。

A．問題規(guī)模是n2

B．執(zhí)行時間等于n2

C．執(zhí)行時間與n2成正比

D．問題規(guī)模與n2成正比

2．設(shè)線性表中有2n個元素，以下操作中，（）在單鏈表上實現(xiàn)

要比在順序表上實現(xiàn)效率更高。

A．刪除指定的元素

B．在最后一個元素的后面插入一個新元素

C．順序輸出前k個元素

D．交換第i個元素和第2n-i-1個元素的值(i=0,1…,n-1)

3．在一個單鏈表L中，指針p指向L的某個結(jié)點，在p之前插入一個

指針s所指結(jié)點時的操作為（）。

A．s->next=p->next；p->next=s；t=p->data；p->data=s->data；s-

>data=t；

B．p->next=s；s->next=p->next；t=p->data；p->data=s->data；s-

>data=t；

C．s->next=p->next；p->next=s；p->data=s->data；t=p->data；s-

>data=t；

D．p->next=s；s->next=p->next；t=s->data；s->datap->data；p-

>data=t；

4．已知一個棧的進棧序列是1，2，3，……，n，其輸出序列是

p1,p2,…,pn，若p1=n，則pi的值（）。

A．i

B．n-i

C．n-i+1

D．不確定

5．對稀疏矩陣進行壓縮存儲，常用的兩種方法是（）。

A．二元組和散列表

B．三元組和十字鏈表

C．三角矩陣和對角矩陣

D．對角矩陣和十字鏈表

6．廣義表（（a），a）的表頭和表尾分別是（）。

A．（a）和（a）

B．a(chǎn)和（a）

C．（a）和a

D．（（a））和（a）

7．已知二叉樹的先序序列為ABDEGCF，中序序列為DBGEACF，

則后序序列為（）。

A．GEDBFCA

B．DGEBFCA

C．DGEBAFC

D．EBFDGCA

8．一棵完全二叉樹上有1000個結(jié)點，其中葉子結(jié)點的個數(shù)是（

）。

A．250

B．500

C．505

D．501

9．線索二叉樹是一種（）結(jié)構(gòu)。

A．邏輯

B．邏輯和存儲

C．物理

D．線性

10．以數(shù)據(jù)集{2，5，7，9，13}為權(quán)值構(gòu)造一棵哈夫曼樹，則其帶

權(quán)路徑長為（）。

A．78

B．80

C．81

D．79

11．一個有向圖的鄰接表存儲如圖1所示，現(xiàn)按深度優(yōu)先搜索遍

歷，從頂點v1出發(fā)，所得到的頂點序列是（）。

圖1圖的鄰接表

A．v1，v2，v3，v4，v5

B．v1，v2，v3，v5，v4

C．v1，v2，v4，v5，v3

D．v1，v2，v5，v3，v4

12．任意一個無向連通圖（）最小生成樹。

A．只有一棵

B．一定有多棵

C．有一棵或多棵

D．可能不存在

13．若一個有向圖中的頂點不能排成一個拓撲序列，則可斷定該有

向圖（）。

A．是個有根有向圖

B．是個強連通圖

C．含有多個入度為0的頂點

D．含有頂點數(shù)目大于1的強連通分量

14．順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。

A．哈希存儲

B．索引存儲

C．壓縮存儲

D．順序存儲或鏈式存儲

15．在含有27個結(jié)點的二叉樹排序樹上，查找關(guān)鍵字為35的結(jié)點，

則依次比較的關(guān)鍵字有可能是（）。

A．28，36，18，46，35

B．18，36，28，46，35

C．46，28，18，36，35

D．46，36，18，28，35

16．在有序表a[1..20]中，采用二分查找算法查找元素值等于a[12]

的元素，所比較過元素的次數(shù)為（）。

A．4

B．5

C．3

D．6

17．數(shù)據(jù)序列｛8，9，10，4，5，6，20，1，2｝只能是下列排序

算法中的（）的兩趟排序后的結(jié)果。

A．選擇排序

B．冒泡排序

C．插入排序

D．堆排序

18．就平均性能而言，目前最好的內(nèi)部排序方法是（）排序

法。

A．冒泡排序

B．希爾排序

C．插入排序

D．快速排序

19．有一組數(shù)據(jù)｛15，9，7，8，20，-1，7，4｝，用堆排序的篩

選方法建立的初始堆為（）。

A．-1，4，5，9，20，7，15，7

B．-1，7，15，7，4，8，20，9

C．-1，4，7，8，20，15，7，9

D．A，B，C都不對

20．下面說法不正確的是（）。

A．關(guān)鍵活動不按期完成就會影響整個工程的完成時間

B．任何一個關(guān)鍵活動提前完成，將使整個工程提前完成

C．所有關(guān)鍵活動都提前完成，則整個工程提前完成

D．某些關(guān)鍵活動若提前完成，將使整個工程提前完成

21．下列選項中，（）不是操作系統(tǒng)關(guān)心的主要問題。

A．管理計算機裸機

B．設(shè)計、提供用戶程序與計算機硬件系統(tǒng)的界面

C．管理計算機系統(tǒng)資源

D．高級程序設(shè)計語言的編譯器

22．系統(tǒng)功能調(diào)用是（）。

A．用戶編寫的一個子程序

B．高級語言中的庫程序

C．操作系統(tǒng)中的一條命令

D．操作系統(tǒng)向用戶程序提供的接口

23．在處理機管理中，當（）時，進程從阻塞狀態(tài)變?yōu)榫途w狀

態(tài)。

A．進程被調(diào)度程序選中

B．等待某一事件發(fā)生

C．等待的事件發(fā)生

D．時間片用完

24．高級調(diào)度是（）。

A．進程調(diào)度

B．作業(yè)調(diào)度

C．程序調(diào)度

D．設(shè)備調(diào)度

25．臨界區(qū)是（）。

A．一個緩沖區(qū)

B．一段共享數(shù)據(jù)區(qū)

C．一段程序

D．一個互斥資源

26．產(chǎn)生死鎖的根本原因是（）。

A．資源共享

B．并發(fā)執(zhí)行的進程太多

C．進程推進順序非法

D．以上3個因素全是

27．在下述存儲管理方案中，（）管理方式要求作業(yè)占用連續(xù)的

存儲空間。

A．分區(qū)

B．分頁

C．分段

D．段頁式

28．操作系統(tǒng)中對數(shù)據(jù)進行管理的部分叫做（）。

A．數(shù)據(jù)庫系統(tǒng)

B．文件系統(tǒng)

C．檢索系統(tǒng)

D．數(shù)據(jù)存儲系統(tǒng)

29．下列文件中屬于邏輯結(jié)構(gòu)的文件是（）。

A．連續(xù)文件

B．系統(tǒng)文件

C．散列文件

D．流式文件

30．在磁盤文件系統(tǒng)中，對于下列文件物理結(jié)構(gòu)，（）不具有直

接讀寫文件任意一個記錄的能力。

A．順序結(jié)構(gòu)

B．鏈接結(jié)構(gòu)

C．索引結(jié)構(gòu)

D．散列結(jié)構(gòu)

二、算法設(shè)計題（共2題，每題10分，合計20分）

31．設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表，采用帶頭結(jié)點的hc單

鏈表存放，設(shè)計一個就地算法，將其拆分為兩個線性表，使得：A={

a1,a2,…,an},B={b1,b2,…,bn}

32．冒泡排序的算法是把大的元素向上移動（氣泡的上升）也可以

把最小的元素向下移動（氣泡的下沉）。請給出上浮和下沉過程交替的

冒泡排序算法。

三、綜合應用題（共6題，合計70分）

33．寫出用Prim算法構(gòu)造圖2最小生成樹的過程。（10分）

圖2無向網(wǎng)

34．關(guān)鍵字序列A=(36,27,68,33,97,40,81,24,23,90,32,14)共12個數(shù)

據(jù)，哈希表長為13，采用的哈希函數(shù)為：h(key)=key%13。如果采用開

放定址的線性探測再散列方法解決沖突，請構(gòu)造哈希表并求其查找成功

時的平均查找長度。（10分）

35．在如圖3所示的AOE網(wǎng)，求：（10分）

（1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。

（2）是否存在某項活動，當其提高速度后能使整個工程縮短工期。

圖3AOE網(wǎng)

36．若有以下四個作業(yè)同時到達系統(tǒng)并立即進入調(diào)度：

作業(yè)名所需CPU時間（分鐘）

作業(yè)19

作業(yè)24

作業(yè)310

作業(yè)48

假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)對它們實施SJF調(diào)度算法。

給出作業(yè)調(diào)度順序并求出平均作業(yè)周轉(zhuǎn)時間T，平均帶權(quán)作業(yè)周轉(zhuǎn)

時間W。（15分）

37．在一個請求式頁式管理系統(tǒng)中，某程序在內(nèi)存中分配三個頁

面，初始為空.頁面走向為:4，3，2，1，4，3，5，4，3，2，1，5。用

學過的頁面值換算法FIFO算出缺頁次數(shù)。給出執(zhí)行過程中內(nèi)存頁面的變

化情況。（15分）

38．在4*100m接力賽中，4個運動員之間存在如下關(guān)系圖4，運動

員1跑到終點把接力棒交給運動員2，……，運動員4接到棒后跑完全

程。試用信號量機制進行描述。試寫出這四個并發(fā)進程能正確執(zhí)行的程

序。（10分）

圖4進程關(guān)系圖

第二部分全國碩士研究生入學統(tǒng)一考試

408計算機學科專業(yè)基礎(chǔ)綜合歷年真題及詳

解

2012年全國碩士研究生入學統(tǒng)一考試408計算

機學科專業(yè)基礎(chǔ)綜合真題

一、單項選擇題：l～40小題。每小題2分，共80分。下列每題給出

的四個選項中，只有一個選項是最符合題目要求的。

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

A．O（log2n）

B．0（n）

C．O（nlog2n）

D．O（n2）

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

3．若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列

為b，c，d，e，a，則根結(jié)點的孩子結(jié)點（）。

A．只有e

B．有e、b

C．有e、c

D．無法確定

4．若平衡二叉樹的高度為6，且所有非葉結(jié)點的平衡因子均為1，

則該平衡二叉樹的結(jié)點總數(shù)為（）。

A．12

B．20

C．32

D．33

5．對有2個頂點e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍

歷，其算法時間復雜度是（）。

A．0（n）

B．0（e）

C．O（n+e）

D．O（n×e）

6．若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為

零，則關(guān)于該圖拓撲序列的結(jié)論是（）。

A．存在，且唯一

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

C．存在，可能不唯一

D．無法確定是否存在

7．有向帶權(quán)圖如題7圖所示，若采用迪杰斯特拉（Dijkstra）算法

求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標

頂點是b，第二條最短路徑的目標頂點是c，后續(xù)得到的其余各最短路徑

的目標頂點依次是（）。

題7圖有向帶權(quán)圖

A．d,e,f

B．e，d，f

C．f，d，e

D．f，e，d

8．下列關(guān)于最小生成樹的敘述中，正確的是（）。

Ⅰ．最小生成樹的代價唯一Ⅱ．所有權(quán)值最小的邊一定會出現(xiàn)在

所有的最小生成樹中Ⅲ．使用普里姆（Prim）算法從不同頂點開始得

到的最小生成樹一定相同Ⅳ．使用普里姆算法和克魯斯卡爾

（Kruskal）算法得到的最小生成樹總不相同

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅲ

D．僅Ⅱ、Ⅳ

9．設(shè)有一棵3階B樹，如題9圖所示。刪除關(guān)鍵字78得到一棵新B

樹，其最右葉結(jié)點所含的關(guān)鍵字是（）。

題9圖3二叉樹圖

A．60

B．60，62

C．62，65

D．65

10．排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱

為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個

元素最終位置的方法是（）。

Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排

V．二路歸并排序

A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ

D．僅Ⅲ、Ⅳ、Ⅴ

11．對同一待排序列分別進行折半插入排序和直接插入排序，兩者

之間可能的不同之處是（）。

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

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

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

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

12．假定基準程序A在某計算機上的運行時間為l00秒，其中90秒為

CPU時間，其余為I/O時間。若CPU速度提高50％，I/O速度不變，則運

行基準程序A所耗費的時間是（）。

A．55秒

B．60秒

C．65秒

D．70秒

13．假定編譯器規(guī)定int和short類型長度分別為32位和16位，執(zhí)行下

列C語言語句：unsignedshortX＝65530；unsignedinty＝X：得到y(tǒng)的機

器數(shù)為（）。

A．00007FFAH

B．0000FFFAH

C．FFFF7FFAH

D．FFFFFFFAH

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

是（）。

A．2126-2103

B．2127-2104

C．2127-2103

D．2128-2104

15．某計算機存儲器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編

譯器規(guī)定int和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存

儲。某C語言程序段如下：

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

地址分別為（）。

A．0x00、0xC00D

B．0x00、0xCOOE

C．0x11、0xC00D

D．0x11、0xC00E

16．下列關(guān)于閃存（FlashMemory）的敘述中，錯誤的是

（）。

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

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

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

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

17．假設(shè)某計算機按字編址，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

18．某計算機的控制器采用微程序控制方式，微指令中的操作控制

字段采用字段直接編碼法，共有33個微命令，構(gòu)成5個互斥類，分別包

含7、3、12、5和6個微命令，則操作控制字段至少有（）。

A．5位

B．6位

C．15位

D．33位

19．某同步總線的時鐘頻率為l00MHz，寬度為32位，地址／數(shù)據(jù)

線復用，每傳輸一個地址或數(shù)據(jù)占用一個時鐘周期。若該總線支持突發(fā)

（猝發(fā)）傳輸方式，則一次“主存寫”總線事務(wù)傳輸l28位數(shù)據(jù)所需要的時

間至少是（）。）。

A．20ns

B．40ns

C．50ns

D．80ns

20．下列關(guān)于USB總線特性的描述中，錯誤的是（）。

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

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

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

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

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

（）。

Ⅰ.I／O接口中的命令字Ⅱ．I／0接口中的狀態(tài)字Ⅲ．中斷類型

號

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

22．響應外部中斷的過程中，中斷隱指令完成的操作，除保護斷點

外，還包括（）。

Ⅰ．開關(guān)中斷Ⅱ．保存通用寄存器的內(nèi)容Ⅲ．形成中斷服務(wù)程

序入口地址并送PC

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

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

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

B．外部中斷

C．進程切換

D．缺頁

24．中斷處理和子程序調(diào)用都需要壓棧以保護現(xiàn)場，中斷處理一定

會保存而子程序調(diào)用不需要保存其內(nèi)容的是（）。

A．程序計數(shù)器

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

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

D．通用地址寄存器

25．下列關(guān)于虛擬存儲的敘述中，正確的是（）。

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

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

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

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

26．操作系統(tǒng)的I／O子系統(tǒng)通常由四個層次組成，每一層明確定義

了與鄰近層次的接口。其合理的層次組織排列順序是（）。

A．用戶級I／O軟件、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動程序、中斷處理程

序

B．用戶級I／O軟件、設(shè)備無關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動程

序

C．用戶級I／O軟件、設(shè)備驅(qū)動程序、設(shè)備無關(guān)軟件、中斷處理程

序

D．用戶級I／O軟件、中斷處理程序、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動程

序

27．假設(shè)5個進程P0、Pl、P2、P3、P4共享三類資源Rl、R2、R3，

這些資源總數(shù)分別為l8、6、22。T0時刻的資源分配情況如題27表所

示，此時存在的一個安全序列是（）。

題27表資源分配情況表

已分配資源資源最大需求

進程R1R2R3R1R2R3

PO3235510

P14O3536

P24O54O11

P32O4425

P4314424

A．P0，P2，P4，Pl，P3

B．Pl，P0，P3，P4，P2

C．P2，Pl，P0，P3，P4

D．P3，P4，P2，Pl，P0P0

28．若一個用戶進程通過read系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)

據(jù)，則下列關(guān)于此過程的敘述中，正確的是（）。

Ⅰ．若該文件的數(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．Ⅰ、Ⅱ和Ⅲ

29．一個多道批處理系統(tǒng)中僅有Pl和P2兩個作業(yè)，P2比Pl晚5ms到

達。它們的計算和I／0操作順序如下：P1：計算60ms，I／O80ms，計

算20ms；P2：計算120ms，I／O40ms，計算40ms若不考慮調(diào)度和切換

時間，則完成兩個作業(yè)需要的時間最少是（）。

A．240ms

B．260ms

C．340ms

D．360ms

30．若某單處理器多進程系統(tǒng)中有多個就緒態(tài)進程，則下列關(guān)于處

理機調(diào)度的敘述中，錯誤的是（）。

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

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

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

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

31．下列關(guān)于進程和線程的敘述中，正確的是（）。

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

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

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

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

32．下列選項中，不能改善磁盤設(shè)備I／O性能的是（）。

A．重排I／0請求次序

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

C．預讀和滯后寫

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

33．在TCP／IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是

（）。

A．PPP

B．IP

C．UDP

D．TCP

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

的是（）。

A．機械特性

B．功能特性

C．過程特性

D．電氣特性

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

A．無連接不可靠服務(wù)

B．無連接可靠服務(wù)

C．有連接不可靠服務(wù)

D．有連接可靠服務(wù)

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

37．下列關(guān)于IP路由器功能的描述中，正確的是（）。

Ⅰ．運行路由協(xié)議，設(shè)置路由表；Ⅱ．監(jiān)測到擁塞時，合理丟棄IP

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

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

上。

A．僅Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅰ、Ⅱ、Ⅳ

D．Ⅰ、Ⅱ、Ⅲ、Ⅳ

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

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

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

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

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

39．某主機的IP地址為5，子網(wǎng)掩碼為。若

該主機向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（）。

A．

B．55

C．55

D．55

40．若用戶l與用戶2之間發(fā)送和接收電子郵件的過程如題40圖所

示，則圖中①、②、③階段分別使用的應用層協(xié)議可以是（）。

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

A．SMTP、SMTP、SMTP

B．POP3、SMTP、POP3

C．POP3、SMTP、SMTP

D．SMTP、SMTP、POP3

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

41．（10分）設(shè)有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）個不等長升序表的合并策

略，并說明理由。

42．（13分）假定采用帶頭結(jié)點的單鏈表保存單詞，當兩個單詞有

相同的后綴時，則可共享相同的后綴存儲空間。例

如，“l(fā)oading”和“being”的存儲映像如題42圖所示。

題42圖存儲映像示意圖

設(shè)strl和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)

為[data，next]，請設(shè)計一個時間上盡可能高效的算法，找出由strl和str2

所指的兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點的位置

p）。要求：

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

（2）根據(jù)設(shè)計思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處

給出注釋。

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

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，則該主存能提供的最

大帶寬是多少?

44．（12分）某16位計算機中，帶符號整數(shù)用補碼表示，數(shù)據(jù)

Cache和指令Cache分離。題44表給出了指令系統(tǒng)中部分指令格式，其中

Rs和Rd表示寄存器，mem表示存儲單元地址，（X）表示寄存器X或存

儲單元X的內(nèi)容。

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

名稱指令的匯編格式指令功能

加法指令ADDRs，Rd（Rs）+（Rd）→Rd

算術(shù)／邏輯左移SHLRd2*（Rd）→Rd

算術(shù)右移SHRRd（Rd）／2→Rd

取數(shù)指令LOADRD，mem（mem）→Rd

存數(shù)指令STORERs，mem（Rs）→mem

該計算機采用5段流水方式執(zhí)行指令，各流水段分別是取指

（IF）、譯碼／讀寄存器（ID）、執(zhí)行／計算有效地址（EX）、訪問

存儲器（M）和結(jié)果寫回寄存器（WB），流水線采用“按序發(fā)射，按序

完成”方式，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一個寄存器的讀

和寫操作不能在同一個時鐘周期內(nèi)進行。請回答下列問題。

（1）若int型變量x的值為-513，存放在寄存器Rl中，則執(zhí)行指

令“SHRRl”后，Rl的內(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í)行

過程中，I3的ID段和I4的IF段被阻塞的原因各是什么?

（4）若高級語言程序中某賦值語句為x＝2*x+a，x和a均為unsigned

int類型變量，它們的存儲單元地址分別表示為[x]、[a]，則執(zhí)行這條語

句至少需要多少個時鐘周期?要求模仿題44圖畫出這條語句對應的指令

序列及其在流水線中的執(zhí)行過程示意圖。

45．（7分）某請求分頁系統(tǒng)的局部頁面置換策略如下：系統(tǒng)從0時

刻開始掃描，每隔5個時間單位掃描一輪駐留集（掃描時間忽略不

計），本輪沒有被訪問過的頁框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈

尾，其中內(nèi)容在下一次被分配之前不被清空。當發(fā)生缺頁時，如果該頁

曾被使用過且還在空閑頁框鏈表中，則重新放回進程的駐留集中；否

則，從空閑頁框鏈表頭部取出一個頁框。假設(shè)不考慮其他進程的影響和

系統(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）該策略是否適合于時間局部性好的程序?說明理由。

46．（8分）某文件系統(tǒng)空間的最大容量為4TB（1T＝240），以磁

盤塊為基本分配單位，磁盤塊大小為lKB。文件控制塊（FCB）包含一

個512B的索引表區(qū)。請回答下列問題。

（1）假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的

磁盤塊號。索引表項中塊號最少占多少字節(jié)?可支持的單個文件最大長

度是多少字節(jié)?

（2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第0～7字節(jié)采用<起始塊號，塊

數(shù)>格式表示文件創(chuàng)建時預分配的連續(xù)存儲空間，其中起始塊號占6B，

塊數(shù)占2B；剩余504字節(jié)采用直接索引結(jié)構(gòu)，一個索引項占6B，則可支

持的單個文件最大長度是多少字節(jié)?為了使單個文件的長度達到最大，

請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。

47．（9分）主機H通過快速以太網(wǎng)連接Internet，IP地址為

，服務(wù)器S的IP地址為0。H與S使用TCP通信時，

在H上捕獲的其中5個IP分組如題47-a表所示。

題47-a表

編號IP分組的前40字節(jié)內(nèi)容（十六進制）

45000030019b40008006lde8coa80008d3444750

1

0bd91388846b41c500000000700243805db00000

450000300000400031066e833d3444750

2cOa80008

13880bd9e0599fef846b41c66701216d037e10000

45000028019c40008006ldefcOa80008d3444750

3

bd91388846b41c6e0599ff0501043802b320000

45000038019d400080061ddecOa80008d3444750

4

0bd91388846b4lc6e0599ff050184380c6550000

45000028681140003106067ad3444750cOa80008

5

13880bd9e0599ff0846b41d6501016d057d20000

請回答下列問題。

（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表

45000028681140004006eCadd3444750

來自S發(fā)出ca760106

的分組1388a108e0599ff0846b41d6501016dO

b7d60000

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

頭部長服務(wù)類型（8-

版本總長度（16-31）

度15）

標識標志片偏移

生存時（TTL）協(xié)議頭部校驗和

源IP地址

目的IP地址

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

目的端口（16-

源端口（0-15）

31）

序號（seq）

確認號（ack）

數(shù)據(jù)保

URGACKPSHRSTSYNFIN窗口

偏移留

校驗和緊急指針

選項（長度可變）填充

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

2012年全國碩士研究生入學統(tǒng)一考試408計算機學

科專業(yè)基礎(chǔ)綜合真題及詳解

一、單項選擇題：l～40小題。每小題2分，共80分。下列每題給出

的四個選項中，只有一個選項是最符合題目要求的。

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

A．O（log2n）

B．0（n）

C．O（nlog2n）

D．O（n2）

【答案】B。

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

該函數(shù)中語句①的運行時間是0（1），語句②的運行時間是T（n-

1）+O（1），其中O（1）為乘法運算的時間。

因此，當n≤1時，T（n）-0（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)生后綴表達式的

過程如下表所列：

當運算符棧

后綴表達式說明

前字符內(nèi)容

a

++“+”進棧

b+ab

“-”與棧頂元素“+”的優(yōu)先級

--ab+

相同，則“+”出棧，“-”進棧

a-ab+a

“*”的優(yōu)先級大于棧頂元

*-*ab+a

素“-”，則“*”進棧

“（”對它之前后的運算符起

（-*（ab+a

隔離作用

“（”對它之前后的運算符起

（-*（（ab+a

隔離作用

-*（（ab+ac

+-*（（+ab+ac“+”進棧

d-*（（+ab+acd

與其配對的左括號及其前所

）-*（ab+acd+

有運算符出棧

／-*（／ab+acd+“／”進棧

e-*（／ab+acd+e

“-”的優(yōu)先級小于棧頂元

--*（-ab+acd+e／素“／”，則“／”出棧，“-”進

棧

f-*（-ab+acd+e／f

與其配對的左括號及其前所

）-*ab+acd+e／f-有運算符出棧

ab+acd+e／f-“+”的優(yōu)先級小于棧頂元

+-

*素“*”，則“*”出棧

ab+acd+e／f-“+”與棧頂元素“-”的優(yōu)先級

+

*-相同，則“-”出棧，“+”進棧

ab+acd+e／f-

g+

*-g

ab+acd+e／f-

全部出棧

*-g+

通過上表可以看出，顯然轉(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ù)是多少。Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點

數(shù)，有N0＝0，N1＝1，N2＝2……Nh＝Nh-1+Nh-2+1

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

5．對有2個頂點e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍

歷，其算法時間復雜度是（）。

A．0（n）

B．0（e）

C．O（n+e）

D．O（n×e）

【答案】C。

【解析】遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。

其耗費的時間則取決于所采用的存儲結(jié)構(gòu)。當用二維數(shù)組表示鄰接矩陣

圖的存儲結(jié)構(gòu)時，查找每個頂點的鄰接點所需時間為O（n2），其中n為

圖中頂點數(shù)。而當以鄰接表作圖的存儲結(jié)構(gòu)時，找鄰接點所需時間為

0（e），其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當以鄰接

表作存儲結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復雜度為O（n+e）。即

可得出正確答案。

6．若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為

零，則關(guān)于該圖拓撲序列的結(jié)論是（）。

A．存在，且唯一

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

C．存在，可能不唯一

D．無法確定是否存在

【答案】C。

【解析】圖的基本應用——拓撲排序，用鄰接矩陣存儲有向圖，矩

陣中主對角線以下的元素均為零，說明該圖為有向無環(huán)圖，所以其拓撲

序列存在，但不一定唯一，如圖的鄰接矩陣為，則存在兩個拓撲序

列。

7．有向帶權(quán)圖如題7圖所示，若采用迪杰斯特拉（Dijkstra）算法

求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標

頂點是b，第二條最短路徑的目標頂點是c，后續(xù)得到的其余各最短路徑

的目標頂點依次是（）。

題7圖有向帶權(quán)圖

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。

頂點

bcdef集合S

趟

數(shù)

25

k＝1（a，b）

（，

a（a，c）

b）

（a，b，（a，

k＝2{a，b，c}

c）b，d）

（a，4（a，b，（a，b，

k＝3{a，b，c，f}

b，d）c，f）c，e）

（a，（a，b，{a，b，c，f，

k＝4

b，d）c，e）d）

（a，b，{a,b，c，f，

k＝5

d，e）d，e}

8．下列關(guān)于最小生成樹的敘述中，正確的是（）。

Ⅰ．最小生成樹的代價唯一Ⅱ．所有權(quán)值最小的邊一定會出現(xiàn)在

所有的最小生成樹中Ⅲ．使用普里姆（Prim）算法從不同頂點開始得

到的最小生成樹一定相同Ⅳ．使用普里姆算法和克魯斯卡爾

（Kruskal）算法得到的最小生成樹總不相同

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅲ

D．僅Ⅱ、Ⅳ

【答案】A。

【解析】當圖中存在相同權(quán)值的邊時，其最小生成樹可能是不唯一

的，但最小生成樹的代價一定是相同的，所以說法Ⅰ正確。從n個頂點

的連通圖中選取n-1條權(quán)值最小的邊可能構(gòu)成回路，所以說法Ⅱ錯誤。

當某個頂點有權(quán)值相同的邊，使用普里姆（Prim）算法從不同頂點開始

得到的最小生成樹并不一定相同，所以說法Ⅲ錯誤。當最小生成樹不唯

一時，使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹

可能相同，也可能不同，所以說法Ⅳ錯誤。由此可得出正確答案。

9．設(shè)有一棵3階B樹，如題9圖所示。刪除關(guān)鍵字78得到一棵新B

樹，其最右葉結(jié)點所含的關(guān)鍵字是（）。

題9圖3二叉樹圖

A．60

B．60，62

C．62，65

D．65

【答案】D。

【解析】本題主要考查B樹刪除操作。即被刪關(guān)鍵字所在的結(jié)點中的

關(guān)鍵字個數(shù)等于［m/2］-1，而與該結(jié)點相鄰的右兄弟（或左兄弟）結(jié)

點中的關(guān)鍵字數(shù)目大于［m/2］-1，則需將其兄弟結(jié)點中最?。ɑ蜃?/p>

大）的關(guān)鍵字上移至雙親結(jié)點中，而將雙親結(jié)點中小于（或大于）且緊

靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點中。題目中刪除關(guān)

鍵字78得到一棵新B樹如下，其最右葉結(jié)點所含的關(guān)鍵字是65。

10．排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱

為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個

元素最終位置的方法是（）。

Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排

V．二路歸并排序

A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ

D．僅Ⅲ、Ⅳ、Ⅴ

【答案】A。

【解析】其中簡單選擇排序、堆排序?qū)儆谶x擇類排序，每一趟排序

結(jié)束時將確定最大（或最?。╆P(guān)鍵字所在的位置。快速排序每一趟排序

結(jié)束時將確定基準關(guān)鍵字所在的位置。希爾排序、二路歸并排序每一趟

排序結(jié)束時不一定能確定一個元素的最終位置。

11．對同一待排序列分別進行折半插入排序和直接插入排序，兩者

之間可能的不同之處是（）。

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

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

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

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

【答案】D。

【解析】折半插入排序所需附加存儲空間和直接插入排序相同，從

時間上比較，折半插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移

動次數(shù)不變。折半插入排序的時間復雜度仍為O（n2）,所以兩者之間的

不同只可能是元素之間的比較次數(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語言語句：unsignedshortX＝65530；unsignedinty＝X：得到y(tǒng)的機

器數(shù)為（）。

A．00007FFAH

B．0000FFFAH

C．FFFF7FFAH

D．FFFFFFFAH

【答案】B。

【解析】X和y均為無符號數(shù)，其中X為16位，y為32位，將16位無符

號數(shù)轉(zhuǎn)化成32位無符號數(shù)，前面要補零。因為X＝65530＝FFFAH，所

以y＝0000FFFAH。

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

是（）。

A．2126-2103

B．2127-2104

C．2127-2103

D．2128-2104

【答案】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）＝2127×（2-2-23）＝

2128-2104。

15．某計算機存儲器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編

譯器規(guī)定int和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存

儲。某C語言程序段如下：

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

地址分別為（）。

A．0x00、0xC00D

B．0x00、0xCOOE

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～OxCOOB中存放a，地址0xC00C中存放b，地址0xC00D中空

閑，地址0xC00E～0xC00F中存放c。

16．下列關(guān)于閃存（FlashMemory）的敘述中，錯誤的是

（）。

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

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

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

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

【答案】A。

【解析】考查閃存的特性，閃存是EEPROM的進一步發(fā)展，可讀可

寫，用MOS管的浮柵上有無電荷來存儲信息，它依然是ROM的一種，

故寫速度比讀速度要慢不少。閃存是一種非易失性存儲器，它采用隨機

訪問方式，現(xiàn)在常見的SSD固態(tài)硬盤就是由flash芯片組成的，故答案為

A。

17．假設(shè)某計算機按字編址，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個微命令，構(gòu)成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ā)）傳輸方式，則一次“主存寫”總線事務(wù)傳輸l28位數(shù)據(jù)所需要的時

間至少是（）。）。

A．20ns

B．40ns

C．50ns

D．80ns

【答案】C。

【解析】總線的時鐘頻率為l00MHz，則時鐘周期為10ns。數(shù)據(jù)是

128位，總線寬度是32位，所以需要4個時鐘周期，而傳輸?shù)刂愤€需要一

個周期，所以傳輸一個128位的數(shù)據(jù)