第10章四川大學(xué)"精品課程〃

計算機科學(xué)與技術(shù)專業(yè)（本科）

《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程

考試說明與模擬試卷

第一部分考試說明

數(shù)據(jù)結(jié)構(gòu)與算法分析》是計算機科學(xué)與技術(shù)專業(yè)統(tǒng)設(shè)的一門重要的必修專業(yè)基礎(chǔ)課,

它主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和在計算機中的存儲結(jié)構(gòu)，還研究對數(shù)據(jù)進行的插入、查

找、刪除、排序、遍歷等基本運算或操作以及這些運算在各種存儲結(jié)構(gòu)上具體實現(xiàn)的算法。

由于本課程的主教材采用C++語言描述算法，期末卷面考試也采用C++語言描述，因而要

求在做平時作業(yè)和上機實驗操作時用C++開發(fā)工具（如：VisualC++或C++Builder或

BorlandC++）。

下面按照主教材中各章次序給出每章的具體復(fù)習(xí)要求，以便同學(xué)們更好地進行期末復(fù)

習(xí)。

第一章緒論

重點掌握的內(nèi)容：

1.數(shù)據(jù)結(jié)構(gòu)的二元組表示，對應(yīng)的圖形表示，序偶和邊之間的對應(yīng)關(guān)系。

2.集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)的特點。

3.抽象數(shù)據(jù)類型的定義和表示方法。

4.一維和二維數(shù)組中元素的按下標(biāo)和按地址的訪問方式以及相互轉(zhuǎn)換，元素地址和數(shù)

組地址的計算，元素占用存儲空間大小和數(shù)組占用存儲空間大小的計算。

5.普通函數(shù)重載和操作符函數(shù)重載的含義，定義格式和調(diào)用格式。

6.函數(shù)定義中值參數(shù)和引用參數(shù)的說明格式及作用，函數(shù)被調(diào)用執(zhí)行時對傳送來的實

際參數(shù)的影響。

7.算法的時間復(fù)雜度和空間復(fù)雜度的概念，計算方法，數(shù)量級表示。

8.一個簡單算法的最好、最差和平均這三種情況的時間復(fù)雜度的計算。

對于本章的其余內(nèi)容均作一般掌握。

第二章線性表

重點掌握的內(nèi)容：

1.線性表的定義及判別和抽象數(shù)據(jù)類型的描述，線性表中每一種操作的功能，對應(yīng)的

函數(shù)名、返回值類型和參數(shù)表中每個參數(shù)的作用。

2.線性表的順序存儲結(jié)構(gòu)的類型定義，即List類型的定義和每個域的定義及作用。

3.線性表的每一種運算在順序存儲結(jié)構(gòu)上實現(xiàn)的算法，及相應(yīng)的時間復(fù)雜度。

4.鏈接存儲的概念，線性表的單鏈接和雙鏈接存儲的結(jié)構(gòu)，向單鏈表中一個結(jié)點之后

插入新結(jié)點或從單鏈表中刪除一個結(jié)點的后繼結(jié)點的指針鏈接過程。

5.單鏈表中結(jié)點的結(jié)構(gòu)，每個域的定義及作用，即LNode類型的定義及結(jié)構(gòu)。

6.帶表頭附加結(jié)點的鏈表、循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點。

7.線性表的每一種運算在單鏈表上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。

8.在順序存儲或鏈接存儲的線性表上實現(xiàn)指定功能的算法的分析和設(shè)計。

9.Josephus問題的求解過程。

10.順序表和線性鏈表的性能比較及各自使用背景。

對于本章的其余內(nèi)容均作一般掌握。

第三章數(shù)組和廣義表

重點掌握的內(nèi)容：

1.多維數(shù)組的邏輯結(jié)構(gòu)特征。

2.多維數(shù)組的順序存儲結(jié)構(gòu)及地址計算公式。

3.數(shù)組是一種隨機存取結(jié)構(gòu)的原因。

4.特殊矩陣和稀疏矩陣的概念。

5.特殊矩陣（包括對角矩陣）和壓縮存儲的下標(biāo)變換方法及所需存儲空間。

6.稀疏犯陣的定義和二元組線性表及二列二維數(shù)組表示。

7.稀疏矩陣的順序存儲、帶行指針向量的鏈接存儲，在每一種存儲中非零元素結(jié)點的

結(jié)構(gòu)。

8.稀疏矩陣的轉(zhuǎn)置運算。

9.廣義表的定義和表示，廣義表長度和深度的計算。

10.廣義表上的求表頭、表尾運算。

5.廣義表的鏈接存儲結(jié)構(gòu)中結(jié)點類型的定義，分別求廣義表長度和深度的遞歸算

法，它們對應(yīng)的時間復(fù)雜度。

一般掌握的內(nèi)容：

稀疏矩陣轉(zhuǎn)置的算法描述。

對于本章的其余內(nèi)容均作一般了解。

第四章棧和隊列

重點掌握的內(nèi)容：

1.棧的定義和抽象數(shù)據(jù)類型的描述，棧中每一種操作的功能，對應(yīng)的函數(shù)名、返回值

類型和參數(shù)表中每個參數(shù)的作用。

2.棧的順序存儲結(jié)構(gòu)的類型定義，即Stack類型的定義和每個域的定義及作用。

3.棧的每一種運算在順序存儲結(jié)構(gòu)上實現(xiàn)的算法，及相應(yīng)的時間復(fù)雜度。

4.棧的每一種運算在鏈接存儲結(jié)構(gòu)上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。

5.算術(shù)表達式的中綴表示和后綴表示，以及相互轉(zhuǎn)換的規(guī)則，后綴表達式求值的方

法。

6.給定n個棧元素，出?？赡芑虿豢赡艿男蛄袛?shù).

7.隊列的定義和抽象數(shù)據(jù)類型的描述，隊列中每一種操作的功能，對應(yīng)的函數(shù)名、返

回值類型和參數(shù)表中每個參數(shù)的作用。

8.隊列的順序存儲結(jié)構(gòu)的類型定義，即Queue類型的定義和每個域的定義及作用。

9.隊列的每一種運算在順序存儲結(jié)構(gòu)上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。

10.利用棧和隊列解決簡單問題的算法分析和設(shè)計。

11.雙端隊的概念及可能出隊序列。

12.隊和棧的應(yīng)用背景，如cpu隊、進程隊、打印機隊。

13.鏈隊的各種存儲表示。

一般掌握的內(nèi)容：

1.后綴表達式求值的算法，把中綴表達式轉(zhuǎn)換為后綴表達式的算法。

2.隊列的鏈接存儲結(jié)構(gòu)，以及實現(xiàn)每一種隊列運算的算法和相應(yīng)的時間復(fù)雜度。

對于本章的其余內(nèi)容均作一般了解。

第五章字符串

重點掌握的內(nèi)容：

1.串的有關(guān)概念及基本運算。

2.串與線性表的關(guān)系。

3.串的各種存儲結(jié)構(gòu)。

4.一個串中真子串天口子串個數(shù)的確定。

一般掌握的內(nèi)容：

1.串上各種運算的實現(xiàn)及其時間性能分析。

2.使用C++提供的操作函數(shù)構(gòu)造與串相關(guān)的算法解決簡單的應(yīng)用問題。

第六章樹和二叉樹

重點掌握的內(nèi)容：

1.樹和二叉樹的定義，對于一棵具體樹和二叉樹的二元組表示及廣義表表示。

2.樹和二叉樹的概念，如結(jié)點的度、樹的度、樹葉、分枝結(jié)點、樹的層數(shù)、樹的深度

等。

3.不同結(jié)點數(shù)的樹卻二叉樹的形態(tài)。

4.樹和二叉樹的性質(zhì)，如已知樹或二叉樹的深度h可求出相應(yīng)的最多結(jié)點數(shù)，已知結(jié)

點數(shù)n可求出對應(yīng)樹或二叉樹的最大和最小高度。

5.二叉樹中結(jié)點的編號規(guī)則和對應(yīng)的順序存儲結(jié)構(gòu)。

6.二義樹的鏈接存儲結(jié)構(gòu)及存儲結(jié)點的類型定義，即BTreeNode類型的定義和每個域

7.對分別用鄰接矩陣和用鄰接表表示的圖進行廣度優(yōu)先搜索遍歷的過程、算法描述以

及相應(yīng)的時間復(fù)雜度。

8.圖的生成樹（若一個具有n個頂點，e條邊的無向圖是一個森林（n>e）,則該森

林中必有多少棵樹。）、深度優(yōu)先生成樹和廣度優(yōu)先生成樹、生成樹的權(quán)、最小生成樹等

的定義。

9.根據(jù)普里姆算法求圖的最小生成樹的過程.

10.根據(jù)克魯斯卡爾算法求圖的最小生成樹的過程。

11.圖的拓撲序列和拓撲排序的概念，求圖的拓撲序列的方法，對用鄰接表表示的圖

進行拓撲排序的過程。

12.強連通圖的最少邊數(shù)。

一般掌握的內(nèi)容：

1.根據(jù)普里姆算法求圖的最小生成樹的算法描述。

2.根據(jù)克魯斯卡爾算法求圖的最小生成樹的算法描述。

3.對用鄰接表表示的圖進行拓撲排序的和算法描述。

對本章的其余內(nèi)容均作一般了解。

第八章查找

重點掌握的內(nèi)容：

1.在一維數(shù)組及單鏈表上進行順序查找的過程、算法、成功及不成功的平均查找長度

和時間復(fù)雜度。

2.在一維數(shù)組上進行二分查找的過程、遞歸和車遞歸算法、平均查找長度和時間復(fù)雜

度，二分查找一個給定值元素的查找長度（即查找路徑上的元素數(shù)），二分查找對應(yīng)的判

定樹的性質(zhì)。

3.散列存儲的概念，散列函數(shù)、散列表、沖突、同義詞、裝填因子等術(shù)語的含義。

4.利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。

5.利用開放定址法中的線性探查法處理沖突進行散列存儲和查找的過程，利用鏈接法

處理沖突進行散列存儲和查找的過程。

6.根據(jù)除留余數(shù)法構(gòu)造散列函數(shù)，采用線性探查法或鏈接法處理沖突，把一組數(shù)據(jù)散

列存儲到散列表中，計算出一個給定值元素的查找長度和查找所有元素的平均查找長度。

7.B_樹中每個結(jié)點的結(jié)構(gòu)，樹根結(jié)點或非樹根垢點中關(guān)鍵字的個數(shù)范圍和子樹的個數(shù)

范圍，的結(jié)構(gòu)特性，從也樹上查找一個給定值元素的過程。

一般掌握的內(nèi)容：

1.B_樹查找算法。

2.向B_樹中插入元素的過程。

對本章的其余內(nèi)容均作一般了解。

第九章排序

重點掌握的內(nèi)容：

1.直接插入、直接選擇和冒泡排序的方法，排序過程及時間復(fù)雜度。

2.在堆排序中建立初始堆的過程和利用堆排序的過程，對一個分支結(jié)點進行篩運算的

過程、算法及時間復(fù)雜度，整個堆排序的算法描述及時間復(fù)雜度。

3.快速排序的方法，對一組數(shù)據(jù)的排序過程，對應(yīng)的二叉搜索樹，快速排序過程中劃

分的層數(shù)和遞歸排序區(qū)間的個數(shù)。

4.遞歸排序的遞歸算法，它在平均情況下的時間和空間復(fù)雜度，在最壞情況下的時間

和空間復(fù)雜度C

5.二路歸并排序的方法和對數(shù)據(jù)的排序過程，每趟排序前、后的有序表長度，二路歸

并排序的趟數(shù)、時間復(fù)雜度和空間復(fù)雜度。

6.各種排序方法的不同數(shù)據(jù)序的比較、最好、最壞、平均情況。

7.哪些排序不受初始數(shù)據(jù)的影響。

一般掌握的內(nèi)容：

1.每一種排序方法的穩(wěn)定性。

2.直接插入排序和直接選擇排序的算法。

一般了解的內(nèi)容：

1.二路歸并排序過程中涉及的每個算法描述。

2.冒泡排序算法。

第十章文件

重點掌握的內(nèi)容：

1.文件的有關(guān)概念。

2.文件的邏輯結(jié)構(gòu)及其操作。

3.索引文件的組織方式和特點。

4.索引文件的的杳詢和更新操作的基本思想。

5.兩種最常用的索引順序文件（ISAM文件和VSAM文件）的組織方式和特點。

6.在ISAM文件和VSAM文件上查找和更新操作的基本思想。

7.散列文件的組織方式和特點。

8.散列文件的查詢和更新操作的基本思想。

9.多關(guān)鍵字文件和其它文件的差別。

10.多重表文件和倒排文件組織方式和特點。

11.多重表文件和倒排文件查詢和更新操作的基本思想。

本章其它內(nèi)容一般掌握

第二部分模擬試卷

模擬試題（一）

一、單項選擇題（每小題2分,共20分）

(1)以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？()

A)有向圖B)隊列C)線索二叉樹D)B樹

(2)在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指

向的結(jié)點，則執(zhí)行如下()語句序列。

A)p=q;p->next=q;B)p->next=q;q->next=p;

C)p->next=q->nexf;p=q;D)q->next=p->next;p->next=q;

(3)()不是隊列的基本運算。

A)在隊列第i個元素之后插入一個元素B)從隊頭刪除一個元素

C)判斷一個隊列是否為空D)讀取隊頭元素的值

(4)字符A.BC依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可

以組成()個不同的字符串。

A)14B)5C)6D)8

(5)由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為

()O

A)11B)35C)19D)53

以下6?8題基于下圖：

C6)該一叉樹結(jié)點的前序遍歷的序列為()。

A)E、G、F、A.C.D.BB)E、A.G、C.F、B.D

C)E、A.C、B、D、G、FD)E、G、A.C、D、F、B

(7)該二叉樹結(jié)點的中序遍歷的序列為()。

A)A.B.C.D.E、G、FB)E、A.G、C.F、B.D

C)E、AC、B、D、G、FD)B、D、C、A.F、G、E

(8)該二叉樹的按層遍歷的序列為()。

A)E、G、F、A.C.D.BB)E、A.C.B.D.G、F

C)E、A.G、C、F、B、DD)E、G、AC、D、F、B

(9)下面關(guān)于圖的存儲的敘述中正確的是()。

A)用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無

關(guān)

B)用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)

C)用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)

D)用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)

(10)設(shè)有關(guān)鍵碼序列何記,011招,11r又11),下面哪一個序列是從上述序列出發(fā)建堆

的結(jié)果？()

A)a,g,h,m,n,p,q,x,zB)a,g,m,h,q,n,p,x,zC)g,m,q,a,n,p,x,h,zD)h,g,m,p,a,n,q,x,z

二、(每小題4分，共8分)

已知一個6(5稀疏矩陣如下所示，試：

0000I

00000

0000

0000-2

50000

00700

（1）寫出它的三元組線性表；

（2）給出三元組線性表的順序存儲表示。

三、（本題8分）

求網(wǎng)的最小生成樹有哪些算法？它們的時間復(fù)雜度分別下多少，各適用何種情況？

四、（每小題4分，共8分）

對于如下圖所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是

按照終點序號從小到大的次序鏈接的，試寫出：

（1）從頂點vl出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；

（2）從頂點v2出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹。

五、（本題8分）

己知一個圖的頂點集V和邊集E分別為：

V={123,4,5,6,7};

E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>）;

若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的

次序鏈接的，試給出得到的拓撲排序的序列。

六、（本題8分）

對于序列{8,18,6,16,29,28},試寫出堆頂元素最小的初始堆。

七、（本題8分）

一棵二叉樹的先序、中序和后序序列分別如卜，其中有一部分未顯示出來。試求出空

格處的內(nèi)容，并畫出該二叉樹。

先序序列：BFICEHG

中序序列:DKFIAEJC

后序序列：KFBHJGA

八、（每小題2分，共8分）

設(shè)有序列:w={23,24,27,80,28},試給出：

（1）二叉排序樹；

(2)哈夫曼樹；

(3)平衡二叉樹；

(4)對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果。

九、(本題9分)

有關(guān)鍵字序列{7,23,6,9,17,19,21,22,5},Hash函數(shù)為H(key尸key%5,采用鏈地址法處

理沖突，試構(gòu)造哈希表.

十、(本題15分)

假設(shè)二叉樹中每個結(jié)點所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按

如下圖所示的樹狀顯示二叉樹。

模擬試題(一)參考答案

一、單項選擇題

(1)B(2)D(3)A(4)B(5)B

(6)C(7)A(8)C(9)B(10)B

二、(每小題4分，共8分)

(1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))

(2)三元組線性表的順序存儲表示如下所示：

655'

151

32-1

45-2

5I5

627

三、(本題8分)

求網(wǎng)的最小生成樹可使用Priin算法，時間復(fù)雜度為O(n2),此算法適用丁?邊較多的稠

密圖，也可使用Kruskal算法，時間復(fù)雜度為O(eloge),此算法適用于邊較少的稀疏圖。

四、(每小題4分，共8分)

(1)DFS:vlv2v3v4v5

(2)BFS:v2v3v4v5vl

五、(本題8分)

拓撲排序為：4365721

六、(本題8分)

所構(gòu)造的堆如下圖所示:

七、（本題8分）

在先序序列空格中依次填A(yù)DKJ,中序中依次填BHG,后序中依次填DIEC。

八、（每小題2分，共8分）

（1）二叉排序樹如下圖所示:

（2）哈夫修樹如下圖所示:

（3）平衡二又樹如下圖所示:

（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果:28,80,27,24,23

九、（本題9分）

哈希表如下圖所示:

o

1三*d因

2

3二323|八|

4二*S3

十、（本題15分）

從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第

三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹、也就是以

先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。

C++語言版測試程序見examl\10c++,具體算當(dāng)如下：

template〈classEntry〉

voiddisplay_BT_witli_tree_shape(coiistBinary_tree<Entry>&T)

{

aux_display_BT_with_tree_shape<Entry>(T.get_root());

)

template<classEntry>

voidaux_display_BT_with_tree_shape(Binary_node<Entry>*sub_root,intlevel=1)

//按薪狀形支顯示二叉嬴level為層次數(shù)：3設(shè)根結(jié)點質(zhì)層次裝為1

(

if(sub_root!=NULL)

{〃空樹木顯式，只顯式非空樹

aux_display_BT_with」ree_shapevEntry>(sub_root->right,level+l);〃顯示右子樹

cout?endi;〃顯示新行

for(inti=O;i<leve!-l;i++)

coutvV，”；〃確保在第level列顯示結(jié)點

cout?sub_root->data;〃顯示結(jié)點

aux_display_BT_with_tree_shapevEnti*y>(sub_root->IeftJevel+1);〃顯示左子樹

)

)

C語言版測試程序見examlUOc,具體算當(dāng)如下：

voidDisplayBTVVithTrecShape(BiTreeT,intlevel=l)

//按樹扇形式顯示二叉樹,level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1

(

if(T)

{〃空樹不顯式，只顯式非空樹

DisplayBTWithTreeShape(T->rchildJevel+l):〃顯示右子樹

cout?endl;〃顯示新行

for(inti=O;i<leve!-l;i++)

coutv<°”；〃確保在第level列顯示結(jié)點

cout<<r->data;〃顯示結(jié)點

DisplayBTWithTreeShape(T->lchild,level+l)；〃顯示左子樹

}

模擬試題（二）

一、單項選擇題（每小題2分,共20分）

（1）設(shè)Huffman樹的葉子結(jié)點數(shù)為m,則結(jié)點總數(shù)為（）。

A）2mB）2m-1

C）2m+lD）m+1

（2）若順序存儲的循環(huán)隊列的QueueMaxSize=n,則該隊列最多可存儲（）

個元素。

A)nB)n-1C)n+1D)不確定

(3)下述哪一條是順序存儲方式的優(yōu)點？()

A)存儲密度大B)插入和刪除運算方便

C)獲取符合某種條件的元素方便D)查找運算速度快

(4)設(shè)有一個二維數(shù)組A[m][磯假設(shè)A[0]⑼存放位置在6OO(1O),A[3][3]存放位

置在678(10),每個元素占一個空間，問A⑵[3](10)存放在什么位置？(腳注(10)表示

用10進制表示,m>3)()()

A)658B)648C)633D)653

(5)下列關(guān)于二叉樹遍歷的敘述中，正確的是()。

A)若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前

序遍歷最后一個結(jié)點

B)若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序

遍歷的最后一個結(jié)點

C)若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前

序最后一個結(jié)點

D)若一個樹葉是某二叉樹的前序最后一個結(jié)點，則它必是該二叉樹的中序遍歷最后

一個結(jié)點

(6)k層二叉樹的結(jié)點總數(shù)最多為(),

A)2k-lB)2k+,C)2K-1D)2k',

(7)對線性表進行二分法查找，其前提條曄是()。

A)線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序

B)線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

C)線性表以順序方式存儲；并且按關(guān)鍵碼值排好序

D)線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

(8)對n個記錄進行堆排序，所需要的輔助存儲空間為()。

2

A)O(1og2n)B)O(n)C)0(1)D)O(n)

(9)對于線性表(7,34,77,25,64,49,20,14)進行散列存儲時,若選用H(K)

=K%7作為散列函數(shù)，則散列地址為0的元素有()個。

A)1B)2C)3D)4

(10)下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是()。

A)數(shù)組是不同類型值的集合

B)遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉

C)樹是一種線性結(jié)構(gòu)

D)用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法

二、(本題8分)

假定一棵二叉樹廣義表表示為a(b(c),d(e,f)),分別寫出對它進行先序、中序、后序、按

層遍歷的結(jié)果。

三、(每小題4分，共8分)

已知一個無向圖的頂點集為｛a,b,c,d,e｝,其鄰接矩陣如下所示:

01001

10010

00011

01101

10110

（1）畫出該圖的圖形；

（2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷

序列。

四、（本題8分）

樹有哪些遍歷方法？它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？

五、（本題8分）

設(shè)有數(shù)組A[-1:306,-2:3],按行為主序存放在200（）開始的連續(xù)空間中，如元素的長度

是5,試計算出A[l,1,1]的存儲位置。

六、（本題8分）

試列出如下圖中全部可能的拓撲排序序列。

七、（本題8分）

已知哈希表地址空間為0..8,哈希函數(shù)為H（key）=key%7,采用線性探測再散列處理沖

突,將數(shù)據(jù)序列｛100,20,21,35,3,78,99,45｝依次存入此哈希表中,列出插入時的比較次數(shù),并

求出在等概率下的平均查找長度。

八、（本題8分）

設(shè)有一個輸入數(shù)據(jù)的序列是｛46,25,78,62,12,80）,試畫出從空樹起，逐個輸

入各個數(shù)據(jù)而生成的二叉搜索樹。

九、（本題9分）

試畫出表達式（a+b/c）*（d-e*D的二叉樹表示，并寫出此表達式的波蘭式表示，中綴

表示及逆波蘭式表示。

十、（本題15分）

以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子

結(jié)點數(shù)目的遞歸算法。

模擬試題(二)參考答案

一、單項選擇題(每小題2分,共20分)

(1)B(2)B(3)A(4)D(5)A

(6)A(7)C(8)C(9)D(10)D

二、(本題8分)

先序:a,b,c,d,e,f

中序：c,b,a,e,d,f

后序：c,b,e,f,d,a

按層：a,b,d,c,e,f

三、(每小題4分，共8分)

【解答】

(1)該圖的圖形如下圖所示：

(2)深度優(yōu)先遍歷序列為:abdce；廣度優(yōu)先遍歷序列為:abedc。

四、(本題8分)

樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄浜蟮南?/p>

序遍歷與中序遍歷方法。

五、(本題8分)

人口,1,1］的存儲(超=200(比(1(1))*(6^1)*(3(2川升14)*(34-2升1)+(1<2)))*5=2465<>

六、(本題8分)

全部可能的拓撲排序序列為：1523634.152634.156234.561234.516234.512634.512364

七、(本題8分)

哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示：

哈希地址012345678

關(guān)鍵字2135100378992025

比較次數(shù)12114515

ASL=_!■(4義1+1X2+1X4+2X5)=2.5

九、（本題9分）

表達式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達式的二叉樹表示的前序

遍歷、中序遍歷及后序遍歷序列。

二義樹表示如下圖所示：

波蘭式表示:*+a/bc-d*ef

中綴表示:a+b/c*d-e*f

逆波蘭式表示:abc/4-def*-*

十、(本題15分)

本題只要在遍歷二叉樹的過程序中對葉w迎進行記數(shù)即可。

C++語言版測試程序見exam2\10c++,具體算當(dāng)如下：

template〈classEntry>

longleaf_count(constBinary_tree<Entry>&T)

//計*二叉樹中葉子結(jié)女?dāng)?shù)目

(

returnaux_leaflcount<Entry>(T.get_root());

}

template<classEntry>

longaux_leaCcount(Biiiary_node<Entry>*sub_root)

//按薪狀弦式顯示二叉扁,level為層次數(shù)，目設(shè)根結(jié)點的層次數(shù)為1

{

if(sub_root==NULL)

return0;〃空樹返回0

elseif(sub_root->left==NULL&&sub_root->right==NULL)

return1;〃只有一個結(jié)點的樹返回1

else

〃葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之和

returnaux_leaf_count(sub_root->left)+aux_leaflcount(sub_root->right);

}

C語言版測試程序見exam2\10c,具體算當(dāng)如下：

longLeafCount(BiTrecT)

//計算二叉樹中葉子結(jié)點數(shù)目

(

if(T=NULL)

return0;〃空樹返回0

elseif(T->lchild==NULL&&T->rchild==NULL)

return1;〃只有一個結(jié)點的樹返回1

else

〃葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之和

returnLeafCount(T->lchiid)+LeafCount(T->rchild);

)

模擬試題（三）

一、單項選擇題（每小題2分，共20分）

（1）對一個算法的評價，不包括如下（）方面的內(nèi)容。

A）健壯性和可讀性B）并行性C）正確性D）時空復(fù)雜度

（2）在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則

執(zhí)行（）。

A）p->next=HI.->next;HI.->next=pR）p->next=HTHI.=p

C）p->next=HL;p=HLD）HL=p;p->next=HL

（3）對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）

A）經(jīng)常需要隨機地存取元素B）經(jīng)常需要進行插入和刪除操作

C）表中元素需要占據(jù)一片連續(xù)的存儲空間D）表中元素的個數(shù)不變

（4）一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是

（）O

A）231B）3210312D）123

（5）每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是

（）。

A）冒泡排序B）簡單選擇排序C）希爾排序D）直接插入排序

（6）采用開放定址法處理散列表的沖突時，其平均查找長度（）。

A）低于鏈接法處理沖突B）高于鏈接法處理沖突

C）與鏈接法處理沖突相同D）高于二分查找

（7）若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（）參數(shù)。

A）值B）函數(shù)C）指針D）引用

（8）在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同

的()。

A)行號B)列號C)元素值D)非零元素個數(shù)

(9)快速排序在最壞情況下的時間復(fù)雜度為()。

A)O(log2n)B)O(nlog2n)C)0(n)D)0(n2)

(10)從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為()。

A)O(n)R)0(1)C)O(log2n)D)O(n2)

二、(本題8分)

已知一個圖的頂點集V和邊集E分別為：

V={1,2,3,456,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。

三、(本題8分)

請畫出如下圖所示的鄰接矩陣和鄰接表。

四、(每小題4分，共8分)

設(shè)有如下圖所示的AOE網(wǎng)(其中vi(i=l,2,…,6)表示事件，弧上表示活動的天數(shù))。

(1)找出所有的關(guān)鍵路徑。

(2)v3事件的最早開始時間是多少。

五、(本題8分)

如果在100(XXX)個記錄中找出兩個最小的記錄，你認為采用什么樣的排序方法所需的

關(guān)鍵字比較次數(shù)最少？最多比較多少次？

六、(本題8分)

假設(shè)把n個元素的序列(al,a2,…an)滿足條件ak<max{at|lWWk}的元素ak稱為“逆

序元素”。若在一個無序序列中有一對元素ai>aj(i<j),試問，當(dāng)ai與aj相互交換后，該序

列中逆序元素的個數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不

對，請舉一例說明。

七、(每小題4分，共8分)

設(shè)內(nèi)存有大小為6個記錄的緩沖區(qū)供內(nèi)排序使用，文件的關(guān)鍵字序列為

{29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99),試列出：

(1)用內(nèi)排序求出初始歸并段；

(2)用置換一選擇排序求初始歸并段。

八、(本題8分)

已知一組關(guān)鍵字為(19,14,23,1,68,20,84,27,55,11,10,79),哈希函數(shù):H(key尸keyMOD

13,哈希地址空間為0~12,請構(gòu)造用鏈地址法處理沖突的哈希表，并求平均查找長度。

九、(本題9分)

已知關(guān)鍵字序列{23,13,5,28,14,25},試構(gòu)造二叉排序樹。

十、(本題15分)

編寫一個算法求二又樹的深度。

模擬試題(三)參考答案

一、單項選擇題(每小題2分,共20分)

(1)B(2)A(3)B(4)C(5)B

(6)B(7)D(8)A(9)D(10)C

二、(本題8分)

用克魯斯卡爾算法得到的最小生成樹為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

三、(本題8分)

鄰接矩陣：

鄰接表如下圖所示：

四、(每小題4分，共8分)

(1)找出所有的關(guān)健路徑有：v1-*v2-*v3-*v5-*v6,以及vl-*v4-*v6。

(2)v3事件的最早開始時間是13。

五、(本題8分)

采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)

=999999+=1000019次。

六、(本題8分)

不對，例如序列｛3.3.4.2.1）的“逆序元素”個數(shù)是2,2和1是“逆序元素”；但是將

第二個3和2交換后，成為｛324.31｝,此時“逆序元素”個數(shù)是3,2.3和1是“逆序元素”。

然而交換后一定減少的是“逆序?qū)Α钡膫€數(shù)，例如上例中｛33421｝的逆序?qū)Φ膫€數(shù)是7,

交換第二個3和2后，｛324.3.1｝的逆序?qū)Φ膫€數(shù)是6。

七、（每小題4分，共8分）

（1）用內(nèi)排序求出初始歸并段為：

歸并段1:29,33,38,50,60,70:

歸并段2:9,25,28,31,36,43

歸并段3:2,18,57,65,80,100:

歸并段4:14,17,20,30,78.99.

（2）用置換一選擇排序求初始歸并段為：

歸并段1:2933,38,50,60,70,80,100

歸并段2:9,18,25,28,31,36,57,65,78,99;

歸并段3:2,14,17,20,30.

八、（本題8分）

用鏈地址法處理沖突的哈希表如下圖所示：

ASL=—（1*6+2*4+3*1+4*1）=1.75

12

九、（本題9分）

構(gòu)造二叉排序樹的過程如下圖所示。

23

23

構(gòu)造的二叉排序樹如下圖所示:

十、（本題15分）

若二叉樹為空，深度為0;若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加

Io本題最簡單算法是遞歸算法。

C++語言版測試程序見exam3\10c++,具體算當(dāng)如下：

template〈classEntry>

intbitree_depth(constBinary_tree<Entrv>&T)

//求二叉樹的深度.“

{

returnaux_bitree_depth(T.get_root());

}

template<classEntry>

intaux_bitree_depth(Binarv_node<Entrv>*sub_root)

//第二叉癡的深度”

(

if(sub_root==NULL)

return0;〃空二叉樹的深度為0

else

(

intd_lsub,d_rsub;

d_lsub=aux_bitree_depth(sub_root->left);〃左子樹的深度

d_rsub=aux_bitree_depth(sub_root->right);〃右子樹的深度

〃五回左右于樹的聚度最大值加1

return((d_lsubxi_rsub)?d_lsub:d_rsub)+l;

■)

C語言版測試程序見exam3\10c,具體算當(dāng)如下：

intBiTrceDepth(BiTrceT)

//求二叉樹的深度

(

if(T=NULL)

return0;〃空二叉樹的深度為0

else

(

intd_lsub,d_rsub;

d_lsub=BiTreeDepth(T->lchild);〃左子樹的深度

d_rsub=BiTreeDepth(T->rchild);//^子樹的深度

〃國回左右子樹的深度最大值加1

return((d_lsub>d_rsub)?djsub:d_rsub)+l;

)

}

模擬試題（四）

一、單項選擇題（每小題2分，共20分）

（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（）

A）有向圖B）棧C）二叉樹D）B樹

（2）若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一

個結(jié)點，則采用（）存儲方式最節(jié)省時間。

A）單鏈表R）雙鏈表C）帶頭結(jié)點的雙循環(huán)鏈表D）單循環(huán)鏈表

（3）（）不是隊列的基本運算。

A）在隊列第i個元素之后插入一個元素B）從隊頭刪除一個元素

C）判斷一個隊列是否為空D）讀取隊頭元素的值

（4）字符A.B.C.D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多

可以組成（）個不同的字符串？

A）15B）14C）16D）21

（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為

（）O

A）11B）37C）19D）53

以下6?8題基于下面的敘述：若某二叉樹結(jié)點的中序遍歷的序列為A.B.C.D.E、F、G,

后序遍歷的序列為B?D?C.A.F、G、Eo

（6）則該二叉樹結(jié)點的前序遍歷的序列為（）。

A）E、G、F、A.C.D.BB）E、A.G、C.F、B.D

C）E、A.C、B、D、G、FD）E、G、A.C、D、F、B

（7）該二叉樹有（）個葉子。

A）3B）2C）5D）4

（8）該二叉樹的按層遍歷的序列為（）O

A）E、G、F、A.C.D.BB）E、A.C.B.D.G、F

C）E、A.G、C.F、B.DD）E、G、A.C.D.F、B

（9）下面的二叉樹中，（）不是完全二叉樹。

（10）設(shè)有關(guān)鍵碼序列（q,g,m,z,a）,（）序列是從上述序列出發(fā)建的小根堆

的結(jié)果。

A）a,g,m,q,zB）a,g,m,z,qC）g,m,q,a,zD）g,m,a,q,z

二、（本題8分）

試述順序查找法、折半查找法和分塊查找法對被查找的表中元素的要求，對長度為n

的查找表來說，三種查找法在查找成功時的查找長度各是多少？

三、（本題8分）

設(shè)有一個輸入數(shù)據(jù)的序列是｛46,25,78,62,12,80）,試畫出從空樹起，逐個輸入各個

數(shù)據(jù)而生成的二叉排序樹。

四、（本題8分）

給定一個關(guān)鍵字序列｛24,19,32,43,38,6,序列2｝,請寫出快速排序第一趟的結(jié)果;

堆排序時所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小,

在最壞情況下哪種方法的時間復(fù)雜度最差？

五、（本題8分）

設(shè)二維數(shù)組A[0:10,-5:0],按行優(yōu)先順序存儲，每個元素占4個單元，A[0][.5]的存儲地

址為1000,則A[9][-2]的存儲地址為多少？

六、（本題8分）

用一維數(shù)組存放的一-棵完全二叉樹:ABCDEFGHIJKLo請寫出后序遍歷該二叉樹的訪

問結(jié)點序列。

七、（本題8分）

請說明對一棵二叉枕進行前序、中序和后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改

變？為什么？

八、（本題8分）

對于如下圖所示的G,用Kruskal算法構(gòu)造最小生成樹，要求圖示出每一步的變化情況。

九、(本題9分)

已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。

先序序列:ABCDEFGHIJ

中序序列:CBEDAGHFJI

十、(本題15分)

已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的

指針為T,請寫出遞歸算法，從小到大輸出該二叉排

序樹中所有關(guān)鍵字值2K的結(jié)點的關(guān)鍵字的值。

模擬試題(四)參考答案

一、單項選擇題(每小題2分，共20分)

(I)B(2)C(3)A(4)B(5)B

(6)C(7)A(8)C(9)C(10)B

二、(本題8分)

?三種方法對查找的要求分別如下：

?順序查找法：表中元素可以任意存放；

?折半杳戰(zhàn)法：表中元素必須以關(guān)鍵字的大小遞增或遞減的次序存放：

?分塊查找法：表中元素每塊內(nèi)的元素可任意存放，但塊與塊之間必須以關(guān)鍵字的

大小遞增(或遞減)存放，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大于(或小)后

一塊內(nèi)任何元素的關(guān)鍵字。

?三種方法的平均查找長度分別如下：

?順序查找法：查找成功的平均查找長度為：

?折半查找法：查找成功的平均查找長度為log2(n+l)+1;

分塊查找法：若用順序查找確定所在的塊，平均查找長度為；若用折半確定所在塊,

平均查找長度為。

三、(本題8分)

如下圖所示:

四、(本題8分)

快速排序的第一趟結(jié)果為｛22,19,13,6,24,38,43,12｝；堆排序時所建立的初始大頂堆如所圖

所示:

兩種排序方法所需輔助空間：堆是0(1),快速排序是O(logn),可見堆排序所

需輔助空間較少；在最壞情況下兩種排序方法所需時間：堆是O(nbgn),快速

排序是0(n2),所以，可見快速排序時間復(fù)雜度最差。

注意：快速排序的平均時排序速度最快，但在最壞情況下不一定比其他排序方法快。

五、(本題8分)

依題意A的起始地址為1000,則有：

Loc(9,-2)=1000+[(9-0)*(0-(-5)+l)+(-2-(-5))]M=1228。

六、(本題8分)

先畫出該二叉樹的樹形結(jié)構(gòu)。對其進行后序遍歷得到后序序列為:HIDJKEBLFGCAo

七、(本題8分)

二叉樹任兩個中葉結(jié)點必在某結(jié)點的左/右子樹中，三種遍歷方法對左右子樹的遍歷

都是按左子樹在前、右子樹在后的順序進行遍歷的。所以在三種遍歷序列中葉結(jié)點的相對

次序是不會發(fā)生改變的。

八、(本題8分)

用Kruskal算法構(gòu)造最小生成樹的過程如下圖所示：

?

。

。

九、(本題9分)

先由先序序列的第一個結(jié)點確定二叉樹的根結(jié)點，再由根結(jié)點在中序序列中左側(cè)部分為左

子樹結(jié)點，在右側(cè)部分為右子樹結(jié)點，再由先序序列的第一個結(jié)點確定根結(jié)點的左右孩子

結(jié)點，由類似的方法可確定其他垢點，如下圖所示。

十、(本題15分)

由于二叉排序樹是中序有序的，因此對二叉排序樹采用中序遍歷依次輸出大于等于K

的結(jié)點即可。

C++語言版采用教材所提供的二叉排序樹的存儲結(jié)構(gòu)，并使用友元方式共享二叉排序的根指針，測

試程序見exam4\10c++,具體算當(dāng)如下：

template<classRecord>

voiddisplav_key(constBinarv_tree<Record>&T,RecordK)

//從小藥大M出該二又排良樹中所有關(guān)鍵字值2K的結(jié)點的關(guān)鍵字的值

(

aux_(iisplay_key<Record>(T.get_root(),K);

)

template<classRecord>

voidaux_display_key(Binary_node<Record>*sub_root,RecordK)

//從示到大露出前二又泉良樹中所有關(guān)鍵字值的結(jié)點的關(guān)鍵字的值的輔助函數(shù)

(

if(sub_root)

aux_display_key<Record>(sub_