四川大學(xué)“精品課程”

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

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

考試說明與模擬試卷

第一部分考試說明

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

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

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

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

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

BorlandC++）。

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

習(xí)。

第一章緒論

重點(diǎn)掌握的內(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)的特點(diǎn)。

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í)

際參數(shù)的影響。

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

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

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

第二章線性表

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

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

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

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

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

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

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

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

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

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

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

9.Jospphus問題的求解過程c

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.廣義表上的求表頭、表尾運(yùn)算。

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

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

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

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

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

第四章棧和隊(duì)列

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

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

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

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

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

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

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

法。

6.給定n個棧元素，出棧可能或不可能的序列數(shù)。

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

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

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

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

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

11.雙端隊(duì)的概念及可能出隊(duì)序列.

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

13.鏈隊(duì)的各種存儲表示。

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

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

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

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

第五章字符串

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

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

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

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

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

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

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

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

第六章樹和二叉樹

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

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

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

等。

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

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

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

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

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

的定義及作用。

7.二叉樹的先序、中序、后序、遍歷的遞歸過程和遞歸算法，中序遍歷的非遞歸算法,

按層遍歷的過程和算法，每種算法的時間復(fù)雜度。

8.二叉樹的先序、中序、后序遍歷序列，唯一確定一棵二叉樹的原則。

9.算術(shù)表達(dá)式的二叉樹表示及逆波蘭表達(dá)式、中綴表示。

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

1.普通樹的鏈接存儲結(jié)構(gòu)，GTreeNode類型的定義和每個域的定義及作用。

2.普通樹的先根、后根和按層遍歷的過程及算法。

3.在鏈接存儲的二叉樹上實(shí)現(xiàn)指定功能的算法分析和設(shè)計。

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

二叉樹的應(yīng)用

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

1.二叉搜索樹的定義和性質(zhì)、建立。

2.二叉搜索樹查找的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，查找一個元素的查

找長度，即從樹根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)數(shù)。

3.二叉搜索樹插入的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，根據(jù)一組數(shù)據(jù)生成

一棵二叉搜索樹的過程.

4.堆的定義和順序存儲結(jié)構(gòu)，小根堆和大根堆的異同及堆的判別、建立堆的過程。

5.向堆中插入元素的過程、算法描述及時間復(fù)雜度。

6.從堆中刪除元素的過程、算法描述及時間復(fù)雜度。

7.哈夫曼樹的定義，樹的帶權(quán)路徑長度的計算，根據(jù)若干個葉子結(jié)點(diǎn)的權(quán)構(gòu)造哈夫曼

樹的過程。

8.順序二叉樹及二叉鏈表表示二叉樹。

9.已知關(guān)鍵字序列：2字16,38,89,56,16,79）,試構(gòu)造平衡二叉樹。

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

第七章圖

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

1.圖的頂點(diǎn)集和邊集的表示。

2.圖的一些概念的含義，如頂點(diǎn)、邊、度、完全圖、子圖、路徑、路徑長度、連通圖、

權(quán)、網(wǎng)等。

3.圖的鄰接矩陣、鄰接表、鄰接多重表和十字鏈表四種存儲結(jié)構(gòu)及相應(yīng)的空間復(fù)雜度。

4.存儲圖使用的vexlist.adjmatrix,adjlist,edgenode,edgeset.edge等類型的定義

及用途。

5.圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過程。

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

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

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

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

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

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

的定義。

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

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

11.圖的拓?fù)湫蛄泻屯負(fù)渑判虻母拍?，求圖的拓?fù)湫蛄械姆椒ǎ瑢τ绵徑颖肀硎镜膱D

進(jìn)行拓?fù)渑判虻倪^程。

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

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

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

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

3.對用鄰接表表示的圖進(jìn)行拓?fù)渑判虻暮退惴枋觥?/p>

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

第八章查找

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

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

和時間復(fù)雜度。

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

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

定樹的性質(zhì)。

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

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

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

處理沖突進(jìn)行散列存儲和查找的過程。

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

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

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

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

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

1.B樹查找算法。

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

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

第九章排序

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

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

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

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

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

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

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

和空間復(fù)雜度。

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

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

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

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

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

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

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

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

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

2.冒泡排序算法。

第十章文件

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

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

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

3.索引文件的組織方式和特點(diǎn)。

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

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

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

7.散列文件的組織方式和特點(diǎn)。

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

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

10.多重表文件和倒排文件組織方式和特點(diǎn)。

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

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

第二部分模擬試卷

模擬試題（一）

一、單項(xiàng)選擇題（每小題2分,共20分）

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

A）有向圖B）隊(duì)列C）線索二叉樹D）B樹

（2）在一個單鏈表HL+,若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個由q指

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

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

C）p->next=q->next;p=q;D）q->next=p->next;p->next=q;

(3)()不是隊(duì)列的基本運(yùn)算。

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

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

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

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

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

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

()0

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

以下6?8題基于下圖:

(6)該二叉樹結(jié)點(diǎn)的前序遍歷的序列為()。

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

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

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

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

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

C8)該一叉樹的按層遍歷的序列為()。

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é)點(diǎn)個數(shù)無

關(guān)

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

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

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

(10)設(shè)有關(guān)鍵碼序列(qgm,z,a,n,p,x,h),下面哪一個序列是從上述序列出發(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稀疏矩陣如下所示，試：

00001

00000

0-1000

0000-2

50000

00700

（1）寫出它的二元殂線性表:

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

三、（本題8分）

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

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

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

按照終點(diǎn)序號從小到大的次序鏈接的，試寫出：

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

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

五、（本題8分）

已知一個圖的頂點(diǎn)集V和邊集E分別為：

V={1,2,345,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>};

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

次序鏈接的，試給出得到的拓?fù)渑判虻男蛄小?/p>

六、（本題8分）

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

七、（本題8分）

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

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

先序序列：BF1CEHG

中序序列: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é)點(diǎn)所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按

如下圖所示的樹狀顯示一.叉樹.

模擬試題(一)參考答案

一、單項(xiàng)選擇題

(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"

15I

32-1

45-2

515

627_

三、(本題8分)

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

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

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

(1)DFS:vlv2V3V4V5

(2)BFS:v2v3v4v5vl

五、(本題8分)

拓?fù)渑判驗(yàn)椋?365721

六、(本題8分)

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

6

16,8

228

七、（本題8分）

在先序序列空格中依次填A(yù)DKJ,中序中依次填RHG,后序中依次填DIFC

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

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

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

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

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

九、（本題9分）

哈希表如下圖所示:

o

1三*d因

2-^7r=HT4-=HW^l

3二川23|八I

4

十、（本題15分）

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

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

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

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

template<classEntry>

voiddisplay_BT_with_tree_shape（constBinary_tree<Entry>&T）

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

)

template<cla$sEntry>

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

//按薪狀形彘示二叉嬴level為層次數(shù);句設(shè)根結(jié)點(diǎn)質(zhì)層次薪為1

(

if(sub_root!=NULL)

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

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

cout?cndl;〃顯示新行

for(inti=O;i<level-l；i++)

cout?,…；〃確保在第level列顯示結(jié)點(diǎn)

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

aux_display_BT_with」ree_shapevEntry>(sub_root?>left4evel+l);〃顯示左子樹

)

)

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

voidDisplayBTWithTreeShape(BiTrecT,intlevel=l)

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

(

if(T)

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

DisplayBTWithTreeShape(T->rchild,level+l);〃顯示右子樹

cout?endl;〃顯示新行

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

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

cout?T->data;〃顯示結(jié)點(diǎn)

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

)

)

模擬試題（二）

一、單項(xiàng)選擇題（每小題2分,共20分）

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

A）2mB）2m-1

C）2m+lD）m+1

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

個元素。

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

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

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

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

(4)設(shè)有一個二維數(shù)組假設(shè)A[0]⑼存放位置在600(10),A[3][3]存放位

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

用1()進(jìn)制表示,m>3)()。

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

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

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

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

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

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

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

序最后一個結(jié)點(diǎn)

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

一個結(jié)點(diǎn)

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

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

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

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

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

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

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

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

2

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

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

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

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,。)，分別寫出對它進(jìn)行先序、中序、后序、按

層遍歷的結(jié)果。

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

已知一個無向圖的頂點(diǎn)集為｛a,b,c,d,e),其鄰接矩陣如下所示：

01001

10010

（）0011

01101

10110

（1）畫出該圖的圖形：

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

序列。

四、（本題8分）

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

五、（本題8分）

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

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

六、（本題8分）

試列出如下圖中全部可能的拓?fù)渑判蛐蛄小?/p>

七、（本題8分）

已知哈希表地址空間為0..8,哈希函數(shù)為H（kcy）=kcy%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分）

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

表示及逆波蘭式表示。

十、（本題15分）

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

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

模擬試題(二)參考答案

一、單項(xiàng)選擇題(每小題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分)

全部可能的拓?fù)渑判蛐蛄袨椋?523634.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分）

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

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

二義樹表示如下圖所示：

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

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

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

十、(本題15分)

本題只要在遍歷二叉樹的過程序中對葉w迎進(jìn)行記數(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é)點(diǎn)的層次數(shù)為1

{

if(sub_root==NULL)

return0;〃空樹返回0

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

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

else

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

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

}

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

longLeafCount(BiTrecT)

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

(

if(T=NULL)

return0;〃空樹返回0

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

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

else

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

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

模擬試題（三）

一、單項(xiàng)選擇題（每小題2分，共20分）

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

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

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

執(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)常需要隨機(jī)地存取元素B）經(jīng)常需要進(jìn)行插入和刪除操作

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

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

（）。

A）231B）3210312D）123

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

（）。

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

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

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

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

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

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

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

的()。

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分)

已知一個圖的頂點(diǎn)集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=1,2,…,6)表示事件，弧上表示活動的天數(shù))。

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

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

五、(本題8分)

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

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

六、(本題8分)

假設(shè)把n個元素的序列(al,a2,…an)滿足條件akvmax(at|lWtWk}的元素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/00,57,18,65,2,78,30,14,20,17,99)，試列出：

(1)用內(nèi)排序求出初始?xì)w并段；

(2)用置換一選擇排序求初始?xì)w并段。

八、(本題8分)

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

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

九、(本題9分)

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

十、(本題15分)

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

模擬試題(三)參考答案

一、單項(xiàng)選擇題(每小題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)健路徑有：vl-^v2-v3->v5->v6,以及vl->v4fv6。

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

五、(本題8分)

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

=999999+=1000019次。

六、（本題8分）

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

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

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

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

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

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

歸并段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）用置換一選擇排序求初始?xì)w并段為：

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

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

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

八、（本題8分）

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

A

A

-55I-|-?|68IAI

A

A

I19I+1841Al

720|八|

A

A-

A

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_lsub>d_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((djsub>d_rsub)?djsub:d_rsub)+l;

)

}

模擬試題（四）

一、單項(xiàng)選擇題（每小題2分，共20分）

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

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

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

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

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

（3）（）不是隊(duì)列的基本運(yùn)算。

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

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

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

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

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

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

（）O

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

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

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

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

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é)點(diǎn)序列。

七、（本題8分）

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

變？為什么？

八、（本題8分）

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

九、(本題9分)

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

先序序列:ABCDEFGHIJ

中序序列:CBEDAGHFJI

十、(本題15分)

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

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

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

模擬試題(四)參考答案

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

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

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

二、(本題8分)

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

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

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

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

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

素的關(guān)鍵字。

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

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

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

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

平均查找長度為。

三、(本題8分)

如下圖所示:

四、(本題8分)

快速排序的第一趟結(jié)果為｛22