沈陽師范大學(xué)教育技術(shù)學(xué)院《862計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）》歷年考研真題匯編

目錄

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

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

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

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

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

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

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

歷年真題及詳解

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

題

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

題及詳解

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

題

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

題及詳解

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

題

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

題及詳解

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

題

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

題及詳解

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

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

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

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

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

科目代碼：867

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

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

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

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

一、單項(xiàng)選擇題（共10題，每題2分，合計(jì)20分）

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

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

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

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

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

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

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

A．輸出第i（1≤i≤n）個(gè)元素

B．交換第1個(gè)元素與第2個(gè)元素的值

C．順序輸出這n個(gè)元素的值

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

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

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

A．已出棧

B．從棧底算起第3個(gè)

C．棧頂

D．從棧底算起第4個(gè)

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

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

的隊(duì)滿足條件是（）。

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é)點(diǎn)個(gè)數(shù)為（）。

A．3

B．2

C．4

D．5

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

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．對所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷，可得到的頂

點(diǎn)訪問序列為（）。

A．1243576

B．1243567

C．1245637

D．1234576

8．對于下圖，以下（）是其拓?fù)湫蛄小?/p>

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}進(jìn)行排序,一趟排序后的結(jié)果為

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

A．簡單選擇排序

B．起泡排序

C．直接插入排序

D．堆排序

10．對一組數(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ù)排序

二、應(yīng)用題（共4題，每題10分，合計(jì)40分）

11．使用普里姆算法構(gòu)造如圖所示的圖G中從頂點(diǎn)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個(gè)頂點(diǎn)（頂點(diǎn)編號為0-5）的有向帶權(quán)圖G，其鄰接矩

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

46∞∞∞5∞∞

要求：

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

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

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

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

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

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

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

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

存放），使得：

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

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

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

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

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

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

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

20．說明什么是進(jìn)程間的直接制約與間接制約。

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

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

23．說明什么是中斷。

五、綜合題（共2題，每題15分，合計(jì)30分）

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

達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：

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

作業(yè)19小時(shí)

作業(yè)22小時(shí)

作業(yè)310小時(shí)

作業(yè)45小時(shí)

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

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

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

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

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

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

者—寫者問題。

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

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

代碼：868

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

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

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

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

一、單項(xiàng)選擇題（共30題，每題2分，合計(jì)60分）

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

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

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

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

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

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

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

A．刪除指定的元素

B．在最后一個(gè)元素的后面插入一個(gè)新元素

C．順序輸出前k個(gè)元素

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

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

指針s所指結(jié)點(diǎn)時(shí)的操作為（）。

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．已知一個(gè)棧的進(jìn)棧序列是1，2，3，……，n，其輸出序列是

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

A．i

B．n-i

C．n-i+1

D．不確定

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

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個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(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．一個(gè)有向圖的鄰接表存儲如圖1所示，現(xiàn)按深度優(yōu)先搜索遍

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

圖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．任意一個(gè)無向連通圖（）最小生成樹。

A．只有一棵

B．一定有多棵

C．有一棵或多棵

D．可能不存在

13．若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有

向圖（）。

A．是個(gè)有根有向圖

B．是個(gè)強(qiáng)連通圖

C．含有多個(gè)入度為0的頂點(diǎn)

D．含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量

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

A．哈希存儲

B．索引存儲

C．壓縮存儲

D．順序存儲或鏈?zhǔn)酱鎯?/p>

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

則依次比較的關(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．?dāng)?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)鍵活動不按期完成就會影響整個(gè)工程的完成時(shí)間

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

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

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

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

A．管理計(jì)算機(jī)裸機(jī)

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

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

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

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

A．用戶編寫的一個(gè)子程序

B．高級語言中的庫程序

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

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

23．在處理機(jī)管理中，當(dāng)（）時(shí)，進(jìn)程從阻塞狀態(tài)變?yōu)榫途w狀

態(tài)。

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

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

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

D．時(shí)間片用完

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

A．進(jìn)程調(diào)度

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

C．程序調(diào)度

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

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

A．一個(gè)緩沖區(qū)

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

C．一段程序

D．一個(gè)互斥資源

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

A．資源共享

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

C．進(jìn)程推進(jìn)順序非法

D．以上3個(gè)因素全是

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

存儲空間。

A．分區(qū)

B．分頁

C．分段

D．段頁式

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

A．?dāng)?shù)據(jù)庫系統(tǒng)

B．文件系統(tǒng)

C．檢索系統(tǒng)

D．?dāng)?shù)據(jù)存儲系統(tǒng)

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

A．連續(xù)文件

B．系統(tǒng)文件

C．散列文件

D．流式文件

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

接讀寫文件任意一個(gè)記錄的能力。

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

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

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

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

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

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

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

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

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

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

冒泡排序算法。

三、綜合應(yīng)用題（共6題，合計(jì)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個(gè)數(shù)

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

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

時(shí)的平均查找長度。（10分）

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

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

（2）是否存在某項(xiàng)活動，當(dāng)其提高速度后能使整個(gè)工程縮短工期。

圖3AOE網(wǎng)

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

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

作業(yè)19

作業(yè)24

作業(yè)310

作業(yè)48

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

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

時(shí)間W。（15分）

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

面，初始為空.頁面走向?yàn)?4，3，2，1，4，3，5，4，3，2，1，5。用

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

化情況。（15分）

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

員1跑到終點(diǎn)把接力棒交給運(yùn)動員2，……，運(yùn)動員4接到棒后跑完全

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

序。（10分）

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

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

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

解

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

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

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

的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。

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

A．O（log2n）

B．0（n）

C．O（nlog2n）

D．O（n2）

2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。將中綴表達(dá)式

a+b-a*（（c+d）／e-f）+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e／f-*-

g+時(shí)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為

空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是（）。

A．5

B．7

C．8

D．11

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

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

A．只有e

B．有e、b

C．有e、c

D．無法確定

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

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

A．12

B．20

C．32

D．33

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

歷，其算法時(shí)間復(fù)雜度是（）。

A．0（n）

B．0（e）

C．O（n+e）

D．O（n×e）

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

零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。

A．存在，且唯一

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

C．存在，可能不唯一

D．無法確定是否存在

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

求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)

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

的目標(biāo)頂點(diǎn)依次是（）。

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

A．d,e,f

B．e，d，f

C．f，d，e

D．f，e，d

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

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

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

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

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

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅲ

D．僅Ⅱ、Ⅳ

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

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

題9圖3二叉樹圖

A．60

B．60，62

C．62，65

D．65

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

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

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

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

V．二路歸并排序

A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ

D．僅Ⅲ、Ⅳ、Ⅴ

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

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

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

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

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

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

12．假定基準(zhǔn)程序A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為l00秒，其中90秒為

CPU時(shí)間，其余為I/O時(shí)間。若CPU速度提高50％，I/O速度不變，則運(yùn)

行基準(zhǔn)程序A所耗費(fèi)的時(shí)間是（）。

A．55秒

B．60秒

C．65秒

D．70秒

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

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

器數(shù)為（）。

A．00007FFAH

B．0000FFFAH

C．FFFF7FFAH

D．FFFFFFFAH

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

是（）。

A．2126-2103

B．2127-2104

C．2127-2103

D．2128-2104

15．某計(jì)算機(jī)存儲器按字節(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）的敘述中，錯(cuò)誤的是

（）。

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

B．存儲元由MOS管組成，是一種半導(dǎo)體存儲器

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

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

17．假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交

換的塊大小為l個(gè)字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方

式和LRU替換算法，當(dāng)訪問的主存地址依次為0，4，8，2，0，6，8，

6，4，8時(shí)，命中Cache的次數(shù)是（）。

A．1

B．2

C．3

D．4

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

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

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

A．5位

B．6位

C．15位

D．33位

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

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

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

間至少是（）。）。

A．20ns

B．40ns

C．50ns

D．80ns

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

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

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

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

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

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

（）。

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

號

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

22．響應(yīng)外部中斷的過程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)

外，還包括（）。

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

序入口地址并送PC

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

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

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

B．外部中斷

C．進(jìn)程切換

D．缺頁

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

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

A．程序計(jì)數(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)通常由四個(gè)層次組成，每一層明確定義

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

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個(gè)進(jìn)程P0、Pl、P2、P3、P4共享三類資源Rl、R2、R3，

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

示，此時(shí)存在的一個(gè)安全序列是（）。

題27表資源分配情況表

已分配資源資源最大需求

進(jìn)程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．若一個(gè)用戶進(jìn)程通過read系統(tǒng)調(diào)用讀取一個(gè)磁盤文件中的數(shù)

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

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

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

用的參數(shù)應(yīng)包含文件的名稱

A．僅Ⅰ、Ⅱ

B．僅Ⅰ、Ⅲ

C．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

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

達(dá)。它們的計(jì)算和I／0操作順序如下：P1：計(jì)算60ms，I／O80ms，計(jì)

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

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

A．240ms

B．260ms

C．340ms

D．360ms

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

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

A．在進(jìn)程結(jié)束時(shí)能進(jìn)行處理機(jī)調(diào)度

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

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

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

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

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

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

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

D．同一進(jìn)程中的各個(gè)線程擁有各自不同的地址空間

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

A．重排I／0請求次序

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

C．預(yù)讀和滯后寫

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

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

（）。

A．PPP

B．IP

C．UDP

D．TCP

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

的是（）。

A．機(jī)械特性

B．功能特性

C．過程特性

D．電氣特性

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

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

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

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

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

36．兩臺主機(jī)之間的數(shù)據(jù)鏈路層采用后退N幀協(xié)議（GBN）傳輸數(shù)

據(jù)，數(shù)據(jù)傳輸速率為l6kbps，單向傳播時(shí)延為270ms，數(shù)據(jù)幀長度范圍

是128～512字節(jié)，接收方總是以與數(shù)據(jù)幀等長的幀進(jìn)行確認(rèn)。為使信道

利用率達(dá)到最高，幀序號的比特?cái)?shù)至少為（）。

A．5

B．4

C．3

D．237

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

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

分組；Ⅲ．對收到的IP分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?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．某主機(jī)的IP地址為5，子網(wǎng)掩碼為。若

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

A．

B．55

C．55

D．55

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

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

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

A．SMTP、SMTP、SMTP

B．POP3、SMTP、POP3

C．POP3、SMTP、SMTP

D．SMTP、SMTP、POP3

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

41．（10分）設(shè)有6個(gè)有序表A、B、C、D、E、F，分別含有10、

35、40、50、60和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過5

次兩兩合并，將6個(gè)表最終合并成1個(gè)升序表，并在最壞情況下比較的總

次數(shù)達(dá)到最小。請回答下列問題。

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

（2）根據(jù)你的合并過程，描述n（n≥2）個(gè)不等長升序表的合并策

略，并說明理由。

42．（13分）假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有

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

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

題42圖存儲映像示意圖

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

為[data，next]，請?jiān)O(shè)計(jì)一個(gè)時(shí)間上盡可能高效的算法，找出由strl和str2

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

p）。要求：

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

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

給出注釋。

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

43．（11分）假定某計(jì)算機(jī)的CPU主頻為80MHz，CPI為4，并且平

均每條指令訪存1.5次，主存與Cache之間交換的塊大小為168，Cache的

命中率為99％，存儲器總線寬度為32位。請回答下列問題。

（1）該計(jì)算機(jī)的MIPS數(shù)是多少?平均每秒Cache缺失的次數(shù)是多少?

在不考慮DMA傳送的情況下，主存帶寬至少達(dá)到多少才能滿足CPU的

訪存要求?

（2）假定在Cache缺失的情況下訪問主存時(shí)，存在0.0005％的缺頁

率，則CPU平均每秒產(chǎn)生多少次缺頁異常?若頁面大小為4KB，每次缺

頁都需要訪問磁盤，訪問磁盤時(shí)DMA傳送采用周期挪用方式，磁盤I／

O接口的數(shù)據(jù)緩沖寄存器為32位，則磁盤I／O接口平均每秒發(fā)出的DMA

請求次數(shù)至少是多少?

（3）CPU和DMA控制器同時(shí)要求使用存儲器總線時(shí)，哪個(gè)優(yōu)先級

更高?為什么?

（4）為了提高性能，主存采用4體交叉存儲模式，工作時(shí)每l/4個(gè)存

儲周期啟動一個(gè)體。若每個(gè)體的存儲周期為50ns，則該主存能提供的最

大帶寬是多少?

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

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

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

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

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

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

加法指令A(yù)DDRs，Rd（Rs）+（Rd）→Rd

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

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

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

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

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

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

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

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

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

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

令“SHRRl”后，Rl的內(nèi)容是多少?（用十六進(jìn)制表示）

（2）若某個(gè)時(shí)間段中，有連續(xù)的4條指令進(jìn)入流水線，在其執(zhí)行過

程中沒有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時(shí)鐘周期數(shù)為多少?

（3）若高級語言程序中某賦值語句為x＝a+b，x、a和b均為int型變

量，它們的存儲單元地址分別表示為[x]、[a]和[b]。該語句對應(yīng)的指令

序列及其在指令流水線中的執(zhí)行過程如題44圖所示。則這4條指令執(zhí)行

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

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

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

句至少需要多少個(gè)時(shí)鐘周期?要求模仿題44圖畫出這條語句對應(yīng)的指令

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

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

刻開始掃描，每隔5個(gè)時(shí)間單位掃描一輪駐留集（掃描時(shí)間忽略不

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

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

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

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

系統(tǒng)開銷，初始時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁框鏈表中頁框號依

次為32、15、21、41。進(jìn)程P依次訪問的<虛擬頁號，訪問時(shí)刻>是：

<1，1>、<3，2>、<0，4>、<0，6>、<1，11>、<0，13>、<2，14>。

請回答下列問題。

（1）訪問<0，4>時(shí)，對應(yīng)的頁框號是什么?

（2）訪問<1，11>時(shí)，對應(yīng)的頁框號是什么?說明理由。

（3）訪問<2，14>時(shí)，對應(yīng)的頁框號是什么?說明理由。

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

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

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

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

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

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

度是多少字節(jié)?

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

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

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

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

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

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

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

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

題47-a表

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

45000030019b40008006lde8coa80008d3444750

1

0bd91388846b41c500000000700243805db00000

450000300000400031066e833d3444750

2cOa80008

13880bd9e0599fef846b41c66701216d037e10000

45000028019c40008006ldefcOa80008d3444750

3

bd91388846b41c6e0599ff0501043802b320000

45000038019d400080061ddecOa80008d3444750

4

0bd91388846b4lc6e0599ff050184380c6550000

45000028681140003106067ad3444750cOa80008

5

13880bd9e0599ff0846b41d6501016d057d20000

請回答下列問題。

（1）題47-a表中的IP分組中，哪幾個(gè)是由H發(fā)送的?哪幾個(gè)完成了

TCP連接建立過程?哪幾個(gè)在通過快速以太網(wǎng)傳輸時(shí)進(jìn)行了填充?

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

數(shù)是多少?

（3）若題47-a表中的某個(gè)IP分組在S發(fā)出時(shí)的前40字節(jié)如題47-b表所

列，則該IP分組到達(dá)H時(shí)經(jīng)過了多少個(gè)路由器?

題47-b表

45000028681140004006eCadd3444750

來自S發(fā)出ca760106

的分組1388a108e0599ff0846b41d6501016dO

b7d60000

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

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

版本總長度（16-31）

度15）

標(biāo)識標(biāo)志片偏移

生存時(shí)（TTL）協(xié)議頭部校驗(yàn)和

源IP地址

目的IP地址

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

目的端口（16-

源端口（0-15）

31）

序號（seq）

確認(rèn)號（ack）

數(shù)據(jù)保

URGACKPSHRSTSYNFIN窗口

偏移留

校驗(yàn)和緊急指針

選項(xiàng)（長度可變）填充

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

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

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

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

的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。

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

A．O（log2n）

B．0（n）

C．O（nlog2n）

D．O（n2）

【答案】B。

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

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

1）+O（1），其中O（1）為乘法運(yùn)算的時(shí)間。

因此，當(dāng)n≤1時(shí)，T（n）-0（1）；當(dāng)n>1時(shí)，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）的時(shí)間復(fù)雜度為O（n）。

2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。將中綴表達(dá)式

a+b-a*（（c+d）／e-f）+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e／f-*-

g+時(shí)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為

空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是（）。

A．5

B．7

C．8

D．11

【答案】A。

【解析】基本思想是：采用運(yùn)算符棧是為了比較運(yùn)算符的優(yōu)先級，

所有運(yùn)算符必須進(jìn)棧。只將大于棧頂元素優(yōu)先級的運(yùn)算符直接進(jìn)棧，否

則需要退棧棧頂運(yùn)算符（先出棧的運(yùn)算符先計(jì)算，同優(yōu)先級的運(yùn)算符在

棧中的先計(jì)算）。表達(dá)式a+b-a*（（c+d）／e-f）+g產(chǎn)生后綴表達(dá)式的

過程如下表所列：

當(dāng)運(yùn)算符棧

后綴表達(dá)式說明

前字符內(nèi)容

a

++“+”進(jìn)棧

b+ab

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

--ab+

相同，則“+”出棧，“-”進(jìn)棧

a-ab+a

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

*-*ab+a

素“-”，則“*”進(jìn)棧

“（”對它之前后的運(yùn)算符起

（-*（ab+a

隔離作用

“（”對它之前后的運(yùn)算符起

（-*（（ab+a

隔離作用

-*（（ab+ac

+-*（（+ab+ac“+”進(jìn)棧

d-*（（+ab+acd

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

）-*（ab+acd+

有運(yùn)算符出棧

／-*（／ab+acd+“／”進(jìn)棧

e-*（／ab+acd+e

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

--*（-ab+acd+e／素“／”，則“／”出棧，“-”進(jìn)

棧

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

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

）-*ab+acd+e／f-有運(yùn)算符出棧

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

+-

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

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

+

*-相同，則“-”出棧，“+”進(jìn)棧

ab+acd+e／f-

g+

*-g

ab+acd+e／f-

全部出棧

*-g+

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

大個(gè)數(shù)是5。

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

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

A．只有e

B．有e、b

C．有e、c

D．無法確定

【答案】A。

【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b，

d，c，后序遍歷序列為b，c，d，e，a，其中a為這棵二叉樹的根結(jié)點(diǎn)，

接下來，在前序遍歷的第二個(gè)結(jié)點(diǎn)為e，而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)

為e，說明a的孩子結(jié)點(diǎn)只有e。

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

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

A．12

B．20

C．32

D．33

【答案】B。

【解析】本題題目的實(shí)際問題是，具有6層結(jié)點(diǎn)的平衡二叉樹含有最

少的結(jié)點(diǎn)數(shù)是多少。Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)

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

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

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

歷，其算法時(shí)間復(fù)雜度是（）。

A．0（n）

B．0（e）

C．O（n+e）

D．O（n×e）

【答案】C。

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

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

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

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

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

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

可得出正確答案。

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

零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。

A．存在，且唯一

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

C．存在，可能不唯一

D．無法確定是否存在

【答案】C。

【解析】圖的基本應(yīng)用——拓?fù)渑判?，用鄰接矩陣存儲有向圖，矩

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

序列存在，但不一定唯一，如圖的鄰接矩陣為，則存在兩個(gè)拓?fù)湫?/p>

列。

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

求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)

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

的目標(biāo)頂點(diǎn)依次是（）。

題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ù)目標(biāo)頂點(diǎn)依次為

f,d,e。

頂點(diǎn)

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)于最小生成樹的敘述中，正確的是（）。

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

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

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

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

A．僅Ⅰ

B．僅Ⅱ

C．僅Ⅰ、Ⅲ

D．僅Ⅱ、Ⅳ

【答案】A。

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

的，但最小生成樹的代價(jià)一定是相同的，所以說法Ⅰ正確。從n個(gè)頂點(diǎn)

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

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

得到的最小生成樹并不一定相同，所以說法Ⅲ錯(cuò)誤。當(dāng)最小生成樹不唯

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

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

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

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

題9圖3二叉樹圖

A．60

B．60，62

C．62，65

D．65

【答案】D。

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

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

點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于［m/2］-1，則需將其兄弟結(jié)點(diǎn)中最小（或最

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

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

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

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

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

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

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

V．二路歸并排序

A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ

D．僅Ⅲ、Ⅳ、Ⅴ

【答案】A。

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

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

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

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

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

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

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

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

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

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

【答案】D。

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

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

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

不同只可能是元素之間的比較次數(shù)。

12．假定基準(zhǔn)程序A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為l00秒，其中90秒為

CPU時(shí)間，其余為I/O時(shí)間。若CPU速度提高50％，I/O速度不變，則運(yùn)

行基準(zhǔn)程序A所耗費(fèi)的時(shí)間是（）。

A．55秒

B．60秒

C．65秒

D．70秒

【答案】D。

【解析】CPU速度提高50％，即CPU性能提高比為l.5，改進(jìn)之后的

CPU運(yùn)行時(shí)間＝90÷1.5＝60秒。I/O速度不變，仍維持l0秒，所以運(yùn)行基

準(zhǔn)程序A所耗費(fèi)的時(shí)間為70秒。

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

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

器數(shù)為（）。

A．00007FFAH

B．0000FFFAH

C．FFFF7FFAH

D．FFFFFFFAH

【答案】B。

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

號數(shù)轉(zhuǎn)化成32位無符號數(shù)，前面要補(bǔ)零。因?yàn)閄＝65530＝FFFAH，所

以y＝0000FFFAH。

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

是（）。

A．2126-2103

B．2127-2104

C．2127-2103

D．2128-2104

【答案】D。

【解析】IEEE754單精度浮點(diǎn)數(shù)尾數(shù)采用隱藏位策略的原碼表示，且

階碼用移碼表示的浮點(diǎn)數(shù)。規(guī)格化的短浮點(diǎn)數(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．某計(jì)算機(jī)存儲器按字節(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個(gè)字節(jié)，l6位整數(shù)c需要占2個(gè)字節(jié)，而字

符數(shù)據(jù)b占一個(gè)字節(jié)。a＝273,轉(zhuǎn)換成十六進(jìn)制是111H，采用小端方式存

放數(shù)據(jù)，地址0xC008中的內(nèi)容為11H。由于數(shù)據(jù)按邊界對齊存儲，地址

0xC008～OxCOOB中存放a，地址0xC00C中存放b，地址0xC00D中空

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

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

（）。

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

B．存儲元由MOS管組成，是一種半導(dǎo)體存儲器

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

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

【答案】A。

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

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

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

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

A。

17．假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交

換的塊大小為l個(gè)字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方

式和LRU替換算法，當(dāng)訪問的主存地址依次為0，4，8，2，0，6，8，

6，4，8時(shí)，命中Cache的次數(shù)是（）。

A．1

B．2

C．3

D．4

【答案】C。

【解析】Cache有4個(gè)行，2路組相聯(lián)，即Cache被分成2組，每組2

行。主存地址為0～1、4～5、8～9可映射到第0組Cache中，主存地址為

2～3、6～7可映射到第1組Cache中。Cache初始為空，采用LRU替換算

法，當(dāng)訪問主存的10個(gè)地址依次為0，4，8，2，0，6，8，6，4，8時(shí)，

命中Cache的次數(shù)共有3次，分別發(fā)生在第7、8和10步時(shí)。

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

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

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

A．5位

B．6位

C．15位

D．33位

【答案】C。

【解析】33個(gè)微命令分成5個(gè)互斥類（即5個(gè)字段），根據(jù)每個(gè)類中

微命令的多少可以分別確定字段的長度為3、2、4、3、3位，又因?yàn)椴?/p>

用直接編碼方式，所以它們之和3+2+4+3+3＝15也就是操作控制字段的

位數(shù)。

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

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

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

間至少是（）。）。

A．20ns

B．40ns

C．50ns

D．80ns

【答案】C。

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

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

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