數(shù)據(jù)結(jié)構(gòu)與算法分析模擬試卷2023

四川大學(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ù)組中元素的按下標和按地址的訪問方式以及相互轉(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．特殊矩陣（包括對角矩陣）和壓縮存儲的下標變換方法及所需存儲空間。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.二叉樹的先序、中序、后序、遍歷的遞歸過程和遞歸算法，中序遍歷的非遞歸算法，按層遍歷的過程和算法，每種算法的時間復(fù)雜度。8．二叉樹的先序、中序、后序遍歷序列，唯一確定一棵二叉樹的原則。9．算術(shù)表達式的二叉樹表示及逆波蘭表達式、中綴表示。一般掌握的內(nèi)容：1.普通樹的鏈接存儲結(jié)構(gòu)，GTreeNode類型的定義和每個域的定義及作用。2．普通樹的先根、后根和按層遍歷的過程及算法。3.在鏈接存儲的二叉樹上實現(xiàn)指定功能的算法分析和設(shè)計。對于本章的其余內(nèi)容均作一般了解。二叉樹的應(yīng)用重點掌握的內(nèi)容：1.二叉搜索樹的定義和性質(zhì)、建立。2.二叉搜索樹查找的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，查找一個元素的查找長度，即從樹根結(jié)點到該結(jié)點的路徑上的結(jié)點數(shù)。3.二叉搜索樹插入的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，根據(jù)一組數(shù)據(jù)生成一棵二叉搜索樹的過程。4.堆的定義和順序存儲結(jié)構(gòu)，小根堆和大根堆的異同及堆的判別、建立堆的過程。5.向堆中插入元素的過程、算法描述及時間復(fù)雜度。6.從堆中刪除元素的過程、算法描述及時間復(fù)雜度。7.哈夫曼樹的定義，樹的帶權(quán)路徑長度的計算，根據(jù)若干個葉子結(jié)點的權(quán)構(gòu)造哈夫曼樹的過程。8．順序二叉樹及二叉鏈表表示二叉樹。9．已知關(guān)鍵字序列{22,16,38,89,56，16，79}，試構(gòu)造平衡二叉樹。對本章的其余內(nèi)容均作一般了解。第七章

圖重點掌握的內(nèi)容：1.圖的頂點集和邊集的表示。2.圖的一些概念的含義，如頂點、邊、度、完全圖、子圖、路徑、路徑長度、連通圖、權(quán)、網(wǎng)等。3.圖的鄰接矩陣、鄰接表、鄰接多重表和十字鏈表四種存儲結(jié)構(gòu)及相應(yīng)的空間復(fù)雜度。4.存儲圖使用的vexlist,adjmatrix,adjlist,edgenode,edgeset,edge等類型的定義及用途。5.圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過程。6.對分別用鄰接矩陣和用鄰接表表示的圖進行深度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時間復(fù)雜度。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é)點或非樹根結(jié)點中關(guān)鍵字的個數(shù)范圍和子樹的個數(shù)范圍，B_的結(jié)構(gòu)特性，從B_樹上查找一個給定值元素的過程。一般掌握的內(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ù)雜度。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中，若要在當前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點，則執(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）（）不是隊列的基本運算。A）在隊列第i個元素之后插入一個元素B）從隊頭刪除一個元素C）判斷一個隊列是否為空

D）讀取隊頭元素的值（4）字符A、B、C依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個不同的字符串。A）14

B）5

C）6

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

B）35

C）19

D）53以下6-8題基于下圖：（6）該二叉樹結(jié)點的前序遍歷的序列為（）。A）E、G、F、A、C、D、B

B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F

D）E、G、A、C、D、F、B（7）該二叉樹結(jié)點的中序遍歷的序列為（）。A）A、B、C、D、E、G、FB）E、A、G、C、F、B、DC）E、A、C、B、D、G、FD）B、D、C、A、F、G、E

（8）該二叉樹的按層遍歷的序列為（）。A）E、G、F、A、C、D、B

B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D

D）E、G、A、C、D、F、B（9）下面關(guān)于圖的存儲的敘述中正確的是（）。A）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與頂點個數(shù)無關(guān)B）用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和頂點個數(shù)都有關(guān)C）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中頂點個數(shù)和邊數(shù)都有關(guān)D）用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與頂點個數(shù)無關(guān)（10）設(shè)有關(guān)鍵字序列('q','g','m','z','a','n','p','x','h')，下面哪一個序列是從上述序列出發(fā)建堆的結(jié)果?（）A）'a','g','h','m','n','p','q','x','z’B）'a','g','m','h','q','n','p','x','z'C）'g','m','q','a','n','p','x','h','z'D）'h','g','m','p','a','n','q','x','z'二、（每小題4分，共8分）已知一個65稀疏矩陣如下所示，試：（1）寫出它的三元組線性表；（2）給出三元組線性表的順序存儲表示。三、（本題8分）求網(wǎng)的最小生成樹有哪些算法？它們的時間復(fù)雜度分別下多少，各適用何種情況？四、（每小題4分，共8分）對于如下圖所示的有向圖采用鄰接表存儲結(jié)構(gòu)，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：（1）從頂點v1出發(fā)進行深度優(yōu)先搜索所得到的頂點序列；（2）從頂點v2出發(fā)進行廣度優(yōu)先搜索所得到的頂點序列。五、（本題8分）已知一個圖的頂點集V和邊集E分別為：V={1,2,3,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é)構(gòu)，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試給出得到的拓撲排序的序列（入度為零的頂點可采用?；蜿犃衼磉M行存儲）。六、（本題8分）對于序列{8,18,6,16,29,28}，試寫出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容。先序序列：aBdFkICEHjG中序序列：DbKFIAhEJCg后序序列：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）三元組線性表的順序存儲表示如下所示：三、（本題8分）求網(wǎng)的最小生成樹可使用Prim算法，時間復(fù)雜度為O(n2)，此算法適用于邊較多的稠密圖，也可使用Kruskal算法，時間復(fù)雜度為O(eloge)，此算法適用于邊較少的稀疏圖。四、（每小題4分，共8分）（1）DFS：v1v2v3v4v5（2）BFS：v2v3v4v5v1五、（本題8分）用棧存儲入度為零的頂點得到的拓撲排序為：4

3

6

5

7

2

1用隊列存儲入度為零的頂點得到的拓撲排序為：4

3

6

2

5

1

7六、（本題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分）哈希表如下圖所示：十、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。具體算法實現(xiàn)如下：//文件路徑名:exam1\alg.hssElemType>voidDisplayHelp(BinTreeNode<ElemType>*r,intlevel)//操作結(jié)果：按樹狀形式顯示以r為根的二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1{if(r!=NULL){//空樹不顯式，只顯式非空樹DisplayHelp<ElemType>(r->rightChild,level+1);//顯示右子樹cout<<endl;//顯示新行for(inti=0;i<level-1;i++)cout<<"";//確保在第level列顯示結(jié)點cout<<r->data;//顯示結(jié)點DisplayHelp<ElemType>(r->leftChild,level+1);//顯示左子樹}}template<classElemType>voidDisplay(constBinaryTree<ElemType>&bt)//操作結(jié)果：樹狀形式顯示二叉樹{DisplayHelp<ElemType>(bt.GetRoot(),1);//樹狀顯示以bt.GetRoot()為根的二叉樹cout<<endl;//換行}模擬試題（二）一、單項選擇題（每小題2分，共20分）（1）設(shè)Huffman樹的葉子結(jié)點數(shù)為m，則結(jié)點總數(shù)為（B）。A）2m

B）2m-1C）2m+1

D）m+1[rr（2）若元素a,b,c,d,e,f依次入棧，允許入棧、出棧操作交替進行。但不允許連續(xù)三次進行出棧操作，則不可能得到的出棧序列是（

D

）A）dcebfa

B）cbdaef

C）dbcaef

D）afedcb（3）在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉節(jié)點個數(shù)是（

）A）41

B）82

C）113

D）122（4）設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個元素占一個空間，問A[2][3](10)存放在什么位置？（腳注(10)表示用10進制表示，m>3）（D）。A）658

B）648

C）633

D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（A）。A）若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點B）若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序遍歷的最后一個結(jié)點C）若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序最后一個結(jié)點D）若一個樹葉是某二叉樹的前序最后一個結(jié)點，則它必是該二叉樹的中序遍歷最后一個結(jié)點（6）k層二叉樹的結(jié)點總數(shù)最多為（）。A）2k-1

B）2k+1

C）2K-1

D）2k-1（7）對線性表進行二分法查找，其前提條件是（）。A）線性表以鏈接方式存儲，并且按關(guān)鍵字值排好序B）線性表以順序方式存儲，并且按關(guān)鍵字值的檢索頻率排好序C）線性表以順序方式存儲，并且按關(guān)鍵字值排好序D）線性表以鏈接方式存儲，并且按關(guān)鍵字值的檢索頻率排好序（8）對n個記錄進行堆排序，所需要的輔助存儲空間為（C）。A）O(1og2n)

B）O(n)

C）O(1)

D）O(n2)（9）對于線性表（7，34，77，25，64，49，20，14）進行散列存儲時，若選用H（K）=K%7作為散列函數(shù)，則散列函數(shù)值為為0的元素有（）個。A）1

B）2

C）3

D）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分）有5個元素，其入棧次序為：A、B、C、D、E，在各種可能的出棧次序中，以元素C第一個出棧，D第二個出棧的次序有哪幾個？三、（每小題4分，共8分）已知一個無向圖的頂點集為{a,b,c,d,e}，其鄰接矩陣如下所示：（1）畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。四、（本題8分）樹有哪些遍歷方法？它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？五、（本題8分）將關(guān)鍵字序列（7、8、11、18、9、14,30）散列存儲到散列列表中，散列表的存儲空間是一個下標從0開始的一個一維數(shù)組，散列函數(shù)為：H(key)=（key*3）%m（m為表長），處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7，請畫出所構(gòu)造的散列表；計算查找成功的平均查找長度。六、（本題8分）試列出如下圖中全部可能的拓撲排序序列。七、（本題8分）請說明對一棵二叉樹進行按照先遍左子樹，后右子樹的方式進行前序、中序和后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？八、（本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。九、（本題9分）試畫出表達式(a+b/c)*(d-e*f)的二叉樹表示，并寫出此表達式的波蘭式表示，中綴表示及逆波蘭式表示。十、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸算法。模擬試題（二）參考答案一、單項選擇題（每小題2分，共20分）（1）B（2）D（3）B（4）D（5）A

（6）A

（7）C

（8）C

（9）D

（10）D二、（本題8分）按照棧的特點可知以元素C第一個出棧，D第二個出棧的次序有CDEBA、CDBAE和CDBEA3種。三、（每小題4分，共8分）【解答】（1）該圖的圖形如下圖所示：（2）深度優(yōu)先遍歷序列為：abdce；廣度優(yōu)先遍歷序列為：abedc。四、（本題8分）樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄浜蟮南刃虮闅v與中序遍歷方法。五、（本題8分）由裝載因子0.7，由于有7個數(shù)據(jù)元素，可得7/m=0.7，從而m=10，所以，構(gòu)造的散列表為：下標0123456789關(guān)鍵字3071411818.9.

比較次數(shù)111112

1

H（7）=（7*3）%

10=1H（8）=（8*3）%10=4H（11）=（11*3）%10=3H（18）=（18*3）%10=4H（9）=（9*3）%10=7H（14）=（14*3）%10=2H（30）=（30*3）%10=2（2）查找成功的ASL=(1+1+1+1+1+2+1)/7=8/7六、（本題8分）全部可能的拓撲排序序列為：1523634、152634、156234、561234、516234、512634、512364七、（本題8分）二叉樹任兩個中葉結(jié)點必在某結(jié)點的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進行遍歷的。所以在三種遍歷序列中葉結(jié)點的相對次序是不會發(fā)生改變的。八、（本題8分）九、（本題9分）表達式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達式的二叉樹表示的前序遍歷、中序遍歷及后序遍歷序列。二叉樹表示如下圖所示：(a+b/c)*(d-e*f)波蘭式表示(前序遍歷)：*+a/bc-d*ef中綴表示：a+b/c*d-e*f逆波蘭式表示：abc/+def*-*十、（本題15分）本題只要在遍歷二叉樹的過程序中對葉子結(jié)點進行記數(shù)即可。具體算法實現(xiàn)如下：//文件路徑名:exam2\alg.htemplate<classElemType>longLeafCountHelp(BinTreeNode<ElemType>*r)//操作結(jié)果：按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1{if(r==NULL){//空二叉樹return0;//空樹返回0}elseif(r->leftChild==NULL&&r->rightChild==NULL){//只有一個結(jié)點的樹return1;//只有一個結(jié)點的樹返回1}else{//其他情況,葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之和returnLeafCountHelp(r->leftChild)+LeafCountHelp(r->rightChild);}}template<classElemType>longLeafCount(constBinaryTree<ElemType>&bt)//操作結(jié)果：計算二叉樹中葉子結(jié)點數(shù)目{returnLeafCountHelp(bt.GetRoot());//調(diào)用輔助函數(shù)實現(xiàn)計算二叉樹中葉子結(jié)點數(shù)目}模擬試題（三）一、單項選擇題（每小題2分，共20分）（1）對一組數(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）。A）起泡排序

B）希爾排序

C）歸并排序

D）基數(shù)排序（2）在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（A）。A）p->next=HL->next;HL->next=p

B）p->next=HL;HL=pC）p->next=HL;p=HL

D）HL=p;p->next=HL（3）對線性表，在下列哪種情況下應(yīng)當采用鏈表表示？（B）A）經(jīng)常需要隨機地存取元素B）經(jīng)常需要進行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲空間D）表中元素的個數(shù)不變（4）一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是（C）。A）231B）321C）312

D）123（5）每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是（B）。A）冒泡排序B）簡單選擇排序C）希爾排序D）直接插入排序（6）采用開放定址法處理散列表的沖突時，其平均查找長度（B）。A）低于鏈接法處理沖突

B）高于鏈接法處理沖突C）與鏈接法處理沖突相同

D）高于二分查找（7）若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（D）參數(shù)。A）值

B）函數(shù)

C）指針

D）引用（8）為解決計算機與打印機之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（

B先進先出

）。A）棧

B）隊列

C）樹

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

B）列號

C）元素值

D）非零元素個數(shù)（9）快速排序在最壞情況下的時間復(fù)雜度為（D）。A）O(log2n)

B）O(nlog2n)

C）O(n)

D）O(n2)（10）從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（C）。A）O(n)

B）O(1)

C）O(log2n)

D）O(n2)二、（本題8分）已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,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）表示事件，有向邊上的權(quán)值表示活動的天數(shù)）。（1）找出所有的關(guān)鍵路徑。（2）v3事件的最早開始時間是多少。五、（本題8分）一棵非空的有向樹中恰有一個頂點入度為0，其他頂點入度為1。但一個恰有一個頂點入度為0、其他頂點入度為1的有向圖卻不一定是一棵有向樹。請舉例說明之。六、（本題8分）假設(shè)把n個元素的序列（a1,a2,…an）滿足條件ak<max{at|1≤t≤k}的元素ak稱為“逆序元素”。若在一個無序序列中有一對元素ai>aj(i<j)，試問，當ai與aj相互交換后，該序列中逆序元素的個數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。七、（本題8分）帶權(quán)圖（權(quán)值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑，現(xiàn)有一種解決該問題的方法：①設(shè)最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂點；②選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當前頂點u=v；③重復(fù)步驟②，直到u是目標頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。八、（本題8分）已知一組關(guān)鍵字為（19,14,23,1,68,20,84,27,55,11,10,79），哈希函數(shù)：H(key)=keyMOD13，哈希地址空間為0~12，請構(gòu)造用鏈地址法處理沖突的哈希表，并求平均查找長度。九、（本題9分）已知關(guān)鍵字序列{23，13，5，28，14，25}，試構(gòu)造二叉排序樹。十、（本題15分）編寫一個算法求二又樹的深度。模擬試題（三）參考答案一、單項選擇題（每小題2分，共20分）（1）A

（2）A

（3）B

（4）C

（5）B

（6）B

（7）D

（8）B

（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，以及v1→v4→v6。（2）v3事件的最早開始時間是13。五、（本題8分）如下圖所示的有向圖，只有一個頂點的入度為0外，其他每個頂點的入度都為1，因為非連通，所以此圖卻不是有向樹。六、（本題8分）不對，例如序列｛3、3、4、2、l｝的“逆序元素”個數(shù)是2，2和1是“逆序元素”；但是將第二個3和2交換后，成為｛3、2、4、3、l｝，此時“逆序元素”個數(shù)是3，2、3和1是“逆序元素”。然而交換后一定減少的是“逆序?qū)Α钡膫€數(shù)，例如上例中｛3、3、4、2、l｝的逆序?qū)Φ膫€數(shù)是7，交換第二個3和2后，｛3、2、4、3、1｝的逆序?qū)Φ膫€數(shù)是6。七、（每小題4分，共8分）該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為A→B→C，事實上其最短路徑為A→D→C。八、（本題8分）用鏈地址法處理沖突的哈希表如下圖所示：ASL=(1*6+2*4+3*1+4*1)=1.75九、（本題9分）構(gòu)造二叉排序樹的過程如下圖所示。構(gòu)造的二叉排序樹如下圖所示：十、（本題15分）若二叉樹為空，深度為0；若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。具體算法實現(xiàn)如下：//文件路徑名:exam3\alg.htemplate<classElemType>intDepthHelp(BinTreeNode<ElemType>*r)//操作結(jié)果：求二叉樹的深度{if(r==NULL){//空二叉樹return0;//空二叉樹的深度為0}else{//非空二叉樹intlDepth=DepthHelp(r->leftChild);//左子樹的深度intrDepth=DepthHelp(r->rightChild);//右子樹的深度return((lDepth>rDepth)?lDepth:rDepth)+1;//返回左右子樹的深度最大值加1}}template<classElemType>intDepth(BinaryTree<ElemType>&bt)//操作結(jié)果：求二叉樹的深度{returnDepthHelp(bt.GetRoot());//調(diào)用輔助函數(shù)求二叉樹的深度}模擬試題（四）一、單項選擇題（每小題2分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（）A）有向圖

B）棧

C）二叉樹

D）B樹（2）若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用（）存儲方式最節(jié)省時間。A）單鏈表B）雙鏈表C）帶頭結(jié)點的雙循環(huán)鏈表D）單循環(huán)鏈表（3）（）不是隊列的基本運算。A）在隊列第i個元素之后插入一個元素

B）從隊頭刪除一個元素C）判斷一個隊列是否為空

D）讀取隊頭元素的值（4）字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個不同的字符串？A）15

B）14

C）16

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

B）37

C）19

D）53以下6-8題基于下面的敘述：若某二叉樹結(jié)點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。（6）則該二叉樹結(jié)點的前序遍歷的序列為（）。A）E、G、F、A、C、D、BB）E、A、G、C、F、B、DC）E、A、C、B、D、G、F

D）E、G、A、C、D、F、B（7）該二叉樹有（）個葉子。A）3

B）2

C）5

D）4（8）該二叉樹的按層遍歷的序列為（）。A）E、G、F、A、C、D、B

B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D

D）E、G、A、C、D、F、B（9）下面的二叉樹中，（C）不是完全二叉樹。（10）設(shè)有關(guān)鍵字序列('q','g','m','z','a')，（）序列是從上述序列出發(fā)建的小根堆的結(jié)果。A）'a','g','m','q','z'B）'a','g','m','z','q'C）'g','m','q','a','z'D）'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，13，22｝，請寫出快速排序第一趟的結(jié)果；堆排序時所建的初始堆。｛22,19,13,6,24,38,43,12｝五、（本題8分）設(shè)有帶權(quán)無向網(wǎng)Net如下圖所示。試給出：（1）Net的鄰接矩陣表示；（2）從V1開始的深度優(yōu)先遍歷；（3）從V1開始的廣度優(yōu)先遍歷；（4）從V1開始執(zhí)行的普里姆（Prim）算法過程中所選邊的序列。六、（本題8分）用一維數(shù)組存放一棵完全二叉樹：ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點序列。七、（本題8分）已知哈希表地址空間為0..8，哈希函數(shù)為H(key)=key%7，采用線性探測再散列處理沖突，將數(shù)據(jù)序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入時的比較次數(shù)，并求出在等概率下的平均查找長度。八、（本題8分）對于如下圖所示的G，用Kruskal算法構(gòu)造最小生成樹，要求圖示出每一步的變化情況。九、（本題9分）已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI十、（本題15分）試寫一遞歸算法，從大到小輸出二叉排序樹中所有的關(guān)鍵字值小于key的元素值。。模擬試題（四）參考答案一、單項選擇題（每小題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+1)+1；分塊查找法：若用順序查找確定所在的塊，平均查找長度為；若用折半確定所在塊，平均查找長度為。三、（本題8分）如下圖所示：四、（本題8分）快速排序的第一趟結(jié)果為｛22,19,13,6,24,38,43,12｝；堆排序時所建立的初始大頂堆如所圖所示：五、（本題8分）（1）Net的鄰接矩陣表示：（2）從V1開始的深度優(yōu)先遍歷：V1V2V4

V8

V5

V3

V6

V7（3）從V1開始的廣度優(yōu)先遍歷：V1

V2

V3

V4

V5

V6

V7

V8（4）從V1開始執(zhí)行的普里姆（Prim）算法過程中所選邊的序列：(V1,V3)，(V3,V6)，(V3,V7)，(V1,V2)，(V2,V5)，(V2,V4)，(V5,V8)六、（本題8分）先畫出該二叉樹的樹形結(jié)構(gòu)。對其進行后序遍歷得到后序序列為：HIDJKEBLFGCA。七、（本題8分）哈希表及查找各關(guān)鍵字要比較的次數(shù)如下圖所示：ASL=(4×1+1×2+1×4+2×5)=2.5八、（本題8分）用Kruskal算法構(gòu)造最小生成樹的過程如下圖所示：九、（本題9分）先由先序序列的第一個結(jié)點確定二叉樹的根結(jié)點，再由根結(jié)點在中序序列中左側(cè)部分為左子樹結(jié)點，在右側(cè)部分為右子樹結(jié)點，再由先序序列的第一個結(jié)點確定根結(jié)點的左右孩子結(jié)點，由類似的方法可確定其他結(jié)點，如下圖所示。十、（本題15分）可按先遍歷右子樹，遍歷根結(jié)點，再遍歷左子樹進行中序遍歷，這樣可實現(xiàn)由大到小遍歷一棵二叉排序樹。具體算法實現(xiàn)如下：//文件路徑名:exam4\alg.h#include"binary_sort_tree.h"http://二叉排序樹類template<classElemType,classKeyType>voidInOrderHelp(BinTreeNode<ElemType>*r,constKeyType&key)//操作結(jié)果:從大到小輸出以r為根的二叉排序樹中所有的關(guān)鍵字值小于key的元素值{if(r!=NULL){//非空二叉排序樹InOrderHelp(r->rightChild,key);//遍歷右子樹if(r->data<key)cout<<r->data<<"

";//輸出根結(jié)點elsereturn;InOrderHelp(r->leftChild,key);//遍歷左子樹}}template<classElemType,classKeyType>voidInOrder(constBinarySortTree<ElemType,KeyType>&t,constKeyType&key)//操作結(jié)果:從大到小輸出二叉排序樹中所有的關(guān)鍵字值不小于key的元素值{InOrderHelp(t.GetRoot(),key);//調(diào)用輔助函數(shù)實現(xiàn)從大到小輸出二叉排序樹中所有的關(guān)鍵字值不小于key的元素值}模擬試題（五）一、單項選擇題（每小題2分，共20分）（1）隊列的特點是（B）。A）先進后出B）先進先出C）任意位置進出D）前面都不正確（2）有n個記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進行（B）遍分配與收集。A）nB）dC）rD）n-d（3）在二叉樹結(jié)點的先序序列、中序序列和后序序列中，所有葉子結(jié)點的先后順序（B）。A）都不相同B）完全相同C）先序和中序相同，而與后序不同D）中序和后序相同，而與先序不同（4）限定在一端加入和刪除元素的線性表稱為（C）。A）雙向鏈表B）單向鏈表C）棧D）隊列（5）若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（B）。A）起泡排序

B）插入排序

C）選擇排序

D）二路歸并排序（6）設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹上的結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點個數(shù)是（D）。A）m-n-1B）n+1C）m-n+1D）m-n（7）對于具有n個頂點的強連有向圖，其弧條數(shù)的最小值為（B）。A）n+1B）nC）n-1D）n-2（8）下面關(guān)于廣義表的敘述中，不正確的是（B）。A）廣義表可以是一個多層次的結(jié)構(gòu)B）廣義表至少有一個元素C）廣義表可以被其他廣義表所共享D）廣義表可以是一個遞歸表（9）設(shè)二叉樹根結(jié)點的層次為0，一棵深度（高度）為k的滿二叉樹和同樣深度完全二叉樹各有f個結(jié)點和c個結(jié)點，下列關(guān)系式不正確的是（B）。A）f>=cB）c>fC）f=2k+1-1D）c>2k-1（10）設(shè)一棵二叉樹中沒有度為1的結(jié)點，已知葉子結(jié)點數(shù)為n，此樹的結(jié)點數(shù)為（D）。A）2n+2B）2n+1C）2nD）2n-1二、（每小題4分，共8分）寫出下列中綴表達式的后綴形式：（1）3X/(Y-2)+1（2）2+X*(Y+3)三、（每小題4分，共8分）試對如下圖中的二叉樹畫出其：（1）順序存儲表示；（2）二叉鏈表存儲表示的示意圖。四、（每小題4分，共8分）判斷以下序列是否是小根堆?如果不是，將它調(diào)整為小根堆。（1）{12,70,33,65,24,56,48,92,86,33}（2）{05,23,20,28,40,38,29,61,35,76,47,100}五、（本題8分）已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,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};按照普里姆算法從頂點1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。六、（每小題2分，共8分）設(shè)有12個數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58，它們存儲在散列表中，利用線性探測再散列處理沖突，取散列函數(shù)為H(key)=key%13。（1）順次將各個數(shù)據(jù)散列到表中，并同時列出各元素的比較次數(shù)。（2）計算查找成功的平均查找次數(shù)。七、（第1小題2分，第2、3小題每小題3分，本題8分）對于如下圖所示的圖G，鄰接點按從小到大的次序。（1）圖G有幾個連通分量？（2）按深度優(yōu)先搜索所得的樹是什么？（3）按深度優(yōu)先搜索所得的頂點序列是什么？八、（本題8分）已知一棵樹邊為：{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<C,B>,<G,L>,<G,K>,<A,G>,<A,F>,<A,H>,<C,A>}試畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點？（2）哪些是葉子結(jié)點？（3）樹的深度是多少？九、（本題9分）給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時第一趟結(jié)束時的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個記錄為樞軸）十、（本題15分）編寫復(fù)制一棵二叉樹的非遞歸算法。模擬試題（五）參考答案一、單項選擇題（每小題2分，共20分）（1）B（2）B（3）B（4）C（5）B（6）D（7）B（8）B（9）B（10）D二、（每小題4分，共8分）（1）3

X

*Y

2

-/1

+

（2）2

X

Y

3

+

*

+

三、（每小題4分，共8分）（1）二叉樹的順序存儲表示如下所示：0123456789101112131415161718

1234

56

7

8

9（2）二叉樹的二叉鏈表存儲表示的示意圖如下圖所示：四、（每小題4分，共8分）（1）不是小根堆。調(diào)整為：{12,24,33,65,33,56,48,92,86,70}（2）是小根堆。五、（本題8分）普里姆算法從頂點1出發(fā)得到最小生成樹為：(1,2)3,

(1,3)5,

(1,4)8,

(4,6)4,

(2,5)10,

(4,7)20六、（每小題2分，共8分）（1）取散列函數(shù)為H(key)=key%13。（2）順次將各個數(shù)據(jù)散列到表中，并同時列出各元素的比較次數(shù)如下表所示。表1-1各元素的比較次數(shù)地址01234567891011121314關(guān)鍵字

406694

55833477287222512

比較

121

111132312

（4）計算查找成功的平均查找次數(shù)=（1×7+2×3+3×2）/12=19/12。七、（第1小題2分，第2、3小題每小題3分，本題8分）（1）圖G有2個連通分量。（2）按深度優(yōu)先搜索所得的樹如下圖所示：Q（3）按深度優(yōu)先搜索所得的頂點序列：ABHFGCDE八、（本題8分）（1）樹，如下圖所示：（2）C是根結(jié)點。（3）F，K，L，H，D，M，N是葉子結(jié)點。（3）深度是5。九、（本題9分）（1）（12,2,10,20,6,18,4,16,30,8,28）（2）（6,2,10,4,8,12,28,30,20,16,18）十、（本題15分）將算法實現(xiàn)函數(shù)聲明為二叉樹類的友元函數(shù)，可采用層次遍歷的方式進行復(fù)制，將已復(fù)制的結(jié)點進入一個隊列中即可。具體算法實現(xiàn)如下：//文件路徑名:exam5\alg.htemplate<classElemType>voidCopyBitree(BinaryTree<ElemType>*fromBtPtr,BinaryTree<ElemType>*&toBtPtr)//操作結(jié)果:復(fù)制二叉樹fromBt到toBt的非遞歸算法{if(toBtPtr!=NULL)deletetoBtPtr;//釋放toBtPtrif(fromBtPtr->Empty()){//空二叉樹toBtPtr=NULL;//空二叉樹}else{//非空二叉樹LinkQueue<BinTreeNode<ElemType>*>fromQ,toQ;//隊列BinTreeNode<ElemType>*fromPtr,*toPtr,*fromRoot,*toRoot;fromRoot=fromBtPtr->GetRoot();//取出fromBtPtr的根toRoot=newBinTreeNode<ElemType>(fromRoot->data);//復(fù)制根結(jié)點fromQ.InQueue(fromRoot);toQ.InQueue(toRoot);//入隊while(!fromQ.Empty()){//fromQ非空fromQ.OutQueue(fromPtr);//出隊toQ.OutQueue(toPtr);//出隊if(fromPtr->leftChild!=NULL){//左子樹非空toPtr->leftChild=newBinTreeNode<ElemType>(fromPtr->leftChild->data);//復(fù)制fromPtr左孩子fromQ.InQueue(fromPtr->leftChild);toQ.InQueue(toPtr->leftChild);//入隊}if(fromPtr->rightChild!=NULL){//右子樹非空toPtr->rightChild=newBinTreeNode<ElemType>(fromPtr->rightChild->data);//復(fù)制fromPtr左孩子fromQ.InQueue(fromPtr->rightChild);toQ.InQueue(toPtr->rightChild);//入隊}}toBtPtr=newBinaryTree<ElemType>(toRoot);//生成toBtPtr}}模擬試題（六）一、單項選擇題（每小題2分，共20分）（1）設(shè)二叉樹中有n2個度為2的結(jié)點，n1個度為1的結(jié)點，n0個葉子結(jié)點，則此二叉樹采用二叉鏈表存儲時空指針域個數(shù)為（）。A）n0+n1+n2B）n2+n1+2n0C）2n2+n1D）2n0+n1（2）若需在O(nlogn)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇（）。A）快速排序B）堆排序C）歸并排序D）直接插入排序

（3）對于有n個頂點的有向圖，由弗洛伊德（Floyd）算法求每一對頂之間的最短路徑的時間復(fù)雜度是（）。A）O(1)B）O(n)C）O(n)D）O(n3)（4）對n個元素的序列進行并歸排序，所需要的輔助存儲空間為（）。A）O（1）B）O（log2n）C）O（n）D）O（n2）（5）哈夫曼樹中一定不存在（）。A）度為0的結(jié)點B）度為1的結(jié)點C）度為2的結(jié)點D）帶權(quán)的結(jié)點（6）設(shè)D={A,B,C,D}，R={<C,A>,<A,B>,<B,D>,<D,C>,<D,A>}，則數(shù)據(jù)結(jié)構(gòu)(D,{R})是（）。A）樹B）圖C）線性表D）前面都正確（7）（）關(guān)鍵字序列不符合堆的定義。A）'A'、'C'、'D'、'G'、'H'、'M'、'P'、'Q'、'R'、'X'B）'A'、'C'、'M'、'D'、'H'、'P'、'X'、'G'、'Q'、'R'C）'A'、'D'、'P'、'R'、'C'、'Q'、'X'、'M'、'H'、'G'D）'A'、'D'、'C'、'M'、'P'、'G'、'H'、'X'、'R'、'Q'（8）一組記錄的排序碼為(48,24,18,53,16,26,40)，采用冒泡排序法進行排序，則第一趟排序需要進行記錄交換的次數(shù)是（）。A）3B）4C）5D）6（9）下面（）可以判斷出一個有向圖中是否有環(huán)（回路）？A）求關(guān)鍵路徑B）拓撲排序C）求最短路徑D）前面都不正確（10）對線性表進行二分法查找，其前提條件是（）。A）線性表以順序方式存儲，并且按關(guān)鍵字值排好序B）線性表以順序方式存儲，并且按關(guān)鍵字值的檢索頻率排好序C）線性表以鏈接方式存儲，并且按關(guān)鍵字值排好序D）線性表以鏈接方式存儲，并且按關(guān)鍵字值的檢索頻率排好序二、（本題8分）在如下表所示的數(shù)組A中鏈接存儲了一個線性表，表頭指針存放在A[0].next，試寫出該線性表。表1-2線性表A01234567Data

6050789034

40Next405271

3三、（本題8分）已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ，中序遍歷的結(jié)果是KBCDAFHIGJ，試畫出這棵二叉樹。四、（本題8分）已知一個圖的頂點集V為：V={1,2,3,4,5,6,7}，弧如下表所示。表1-3圖的弧集起點1225522613終點6454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。五、（本題8分）向最小根堆中依次插入數(shù)據(jù)4,2,5,8,3,6,10,1時，畫出每插入一個數(shù)據(jù)后堆的變化。六、（本題8分）有二叉樹中序序列為：ABCEFGHD；后序序列為：ABFHGEDC；請畫出此二叉樹。七、（每小題4分，共8分）對給定的有7個頂點的有向圖的鄰接矩陣如下：（l）畫出該有向圖；（2）若將圖看成是AOE-網(wǎng)，畫出關(guān)鍵路徑。八、（本題8分）給出一組關(guān)鍵字29、18、25、47、58、12、51、10，分別寫出按下列各種排序方法進行排序時的變化過程：（1）歸并排序，每歸并一次書寫一個次序。（2）快速排序，每劃分一次書寫一個次序以及最后排好序后的序列。（3）堆排序，先建成一個堆，然后每從堆頂取下一個元素后，將堆調(diào)整一次。

九、（本題9分）試分別畫出具有3個結(jié)點的樹和具有3個結(jié)點的二叉樹的所有不同形態(tài)。十、（本題15分）已知兩個帶頭結(jié)點的單鏈表A和B分別表示兩個集合，元素值遞增有序，設(shè)計算法求出A，B的交集C，并同樣以遞增的形式存儲。模擬試題（六）參考答案一、單項選擇題（每小題2分，共20分）（1）D（2）C（3）D（4）C（5）B（6）B（7）C（8）C（9）B（10）A二、（本題8分）線性表為：(90,40,78,50,34,60)三、（本題8分）四、（本題8分）用克魯斯卡爾算法得到的最小生成樹為：(1,6)1,

(2,4)1,(2,5)2,

(5,7)2,

(2,6)3,

(3,5)7五、（本題8分）如下圖所示：六、（本題8分）根據(jù)后序序列知根結(jié)點為C，所以左子樹：中序序列為AB，后序序列為AB；右子樹：中序序列為EFGHD，后序序列為FHGED，以此類推得該二叉樹結(jié)構(gòu)如下圖所示。七、（每小題4分，共8分）（1）由鄰接矩陣所畫的有向圖如下圖所示：（2）關(guān)鍵路徑如下圖所示：八、（本題8分）變化過程如下：（1）歸并排序：(l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,12,18,25,29,47,51,58)（2）快速排序：(10,18,25,12)29(58,51,47)(10(18,25,12)29((47,51)58)(10((12)18(25))29((47(51))58)(10,12,18,25,29,47,51,58)29、18、25、47、58、12、51、10（3）堆排序：初始堆（大頂推）：(58,47,51,29,18,12,25,10)第一次調(diào)整：(51,47,25,29,18,12,10)(58)第二次調(diào)整：(47,29,25,10,18,12)(51,58)第三次調(diào)整：(29,18,25,10,12)(47,51,58)第四次調(diào)整：(25,18,12,10)(29,47,51,58)第五次調(diào)整：(l8,10,12)(25,29,47,51,58)第六次調(diào)整：(l2,10)(18,25,29,47,51,58)第七次調(diào)整：(l0,12,18,25,29,47,51,58)九、（本題9分）具有3個結(jié)點的樹的不同形態(tài)如下圖所示。具有3個結(jié)點的二叉樹的不同形態(tài)如下圖所示。十、（本題15分）解答：由于單鏈表A和B是遞增有序的，可設(shè)置兩個整型變量分別表示兩個單鏈表的當前元素的位置，依次取出A與B的元素進行比較，當A的數(shù)據(jù)元素小于B的值時，將指向A的當前位置都后移；當A的數(shù)據(jù)元素大于B的值時，將指向B的當前位置都后移，否則復(fù)將A（或B）的當前元素制到C中，并同時將A與B的當前位置后移。具體算法如下：用單鏈表la表示集合la，用單鏈表lb表示集合lb，用單鏈表lc表示集合lc，具體算法如下：//文件路徑名:exam6\alg.htemplate<classElemType>voidInteraction(constLinkList<ElemType>&la,constLinkList<ElemType>&lb,LinkList<ElemType>&lc)//初始條件:la和lb中數(shù)據(jù)元素遞增有序//操作結(jié)果:lc返回la與lb表示的集合的交集，并使lc中數(shù)據(jù)元素仍遞增有序{ElemTypeaItem,bItem;//la和lb中當前數(shù)據(jù)元素intaLength=la.Length(),bLength=lb.Length();//la和lb的長度intaPosition=1,bPosition=1;//la和lb的當前元素序號lc.Clear();//清空lcwhile(aPosition<=aLength&&bPosition<=bLength){//取出la和lb中數(shù)據(jù)元素進行歸并la.GetElem(aPosition,aItem);//取出la中數(shù)據(jù)元素lb.GetElem(bPosition,bItem);//取出lb中數(shù)據(jù)元素if(aItem<bItem){//aItem插入到lcaPosition++;//指向la下一數(shù)據(jù)元素}elseif(aItem>bItem){//lb后移bPosition++;//指向lb下一數(shù)據(jù)元素}else{//aItem==bItem，la和lb同時后移lc.Insert(lc.Length()+1,aItem);//插入aItem到lcaPosition++;//指向la下一數(shù)據(jù)元素bPosition++;//指向lb下一數(shù)據(jù)元素}}}*模擬試題（七）注：本套試題選作一、單項選擇題（每小題2分，共20分）（1）若以1234作為雙端隊列的輸入序列，則既不能由輸入受限雙端隊列得到，也不能由輸出受限雙端隊列得到的輸出序列是（）。A）1234

B）4132

C）4231D）4213（2）將一個A[1..100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[298]中，A中元素a66,65在B數(shù)組中的位置k為（）（假設(shè)B[0]的位置是1）。A）198B）195C）197D）198（3）若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（）。A）n-1B）C）D）（4）若一個有向圖具有拓撲排序序列，并且頂點按拓撲排序序列編號，那么它的鄰接矩陣必定為（）。A）對稱矩陣B）稀疏矩陣C）三角矩陣D）一般矩陣（5）設(shè)森林F對應(yīng)的二叉樹為有m個結(jié)點，此二叉樹根的左子樹的結(jié)點個數(shù)為k，則另一棵子樹的結(jié)點個數(shù)為（）。A）m-k+1B）k+1C）m-k-1D）m-k（6）假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字存入散列表中，至少要進行（）次探測。A）K-1次B）K次C）K＋l次D）K(K+1)/2次（7）一棵深度為k的平衡二叉樹，其每個非終端結(jié)點的平衡因子均為0，則該樹共有（）個結(jié)點。A）2k-1-1B）2k-1C）2k-1+1D）2k（8）如表r有100000個元素，前99999個元素遞增有序，則采用（

）方法比較次數(shù)較少。A）直接插入排序B）快速排序C）歸并排序D）選擇排序（9）如果只考慮有序樹的情形，那么具有7個結(jié)點的不同形態(tài)的樹共有（）棵。A）132B）154C）429D）前面均不正確（10）對n(n>=2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（

）。A）該樹一定是一棵完全二叉樹

B）樹中一定沒有度為1的結(jié)點C）樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點

D）樹中任一非葉結(jié)點的權(quán)值一定不小于下一任一結(jié)點的權(quán)值二、（本題8分）斐波那契數(shù)列Fn定義如下：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2請就此斐波那契數(shù)列，回答下列問題：（1）在遞歸計算Fn的時候，需要對較小的Fn-1，F(xiàn)n-2，…，F(xiàn)1，F(xiàn)0精確計算多少次？（2）若用有關(guān)大O表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度是多少？三、（本題8分）證明：如果一棵二叉樹的后序序列是,,…,，中序序列是,,…,，則由序列1,2,…,n可通過一個棧得到序列,,…,。四、（本題8分）如下圖所示為5個鄉(xiāng)鎮(zhèn)之間的交通圖，鄉(xiāng)鎮(zhèn)之間道路的長度如圖中邊上所注?，F(xiàn)在要在這5個鄉(xiāng)鎮(zhèn)中選擇一個鄉(xiāng)鎮(zhèn)建立一個消防站，問這個消防站應(yīng)建在哪個鄉(xiāng)鎮(zhèn)，才能使離消防站最遠的鄉(xiāng)鎮(zhèn)到消防站的路程最短。試回答解決上述問題應(yīng)采用什么算法，并寫出應(yīng)用該算法解答上述問題的每一步計算結(jié)果。五、（本題8分）證明一個深度為n的AVL樹中的最少結(jié)點數(shù)為：Nn=Fn+2-1(n≥0)其中，F(xiàn)i為Fibonacci數(shù)列的第i項。六、（本題8分）簡單回答有關(guān)AVL樹的問題：（北方名校經(jīng)典試題）（1）在有n個結(jié)點的AVL樹中，為結(jié)點增加一個存放結(jié)點高度的數(shù)據(jù)成員，那么每一個結(jié)點需要增加多少個字位（bit）？（2）若每一個結(jié)點中的高度計數(shù)器有8bit，那么這樣的AVL樹可以有多少層？最少有多少個關(guān)鍵字？七、（本題8分）設(shè)有12個數(shù)據(jù){25，40，33，47，12，66，72，87，94，22，5，58}，它們存儲在散列表中，利用線性探測再散列解決沖突，要求插入新數(shù)據(jù)的平均查找次數(shù)不超過3次。（1）該散列表的大小m應(yīng)設(shè)計多大？（2）試為該散列表設(shè)計相應(yīng)的散列函數(shù)。（3）順次將各個數(shù)據(jù)散列到表中。（4）計算查找成功的平均查找次數(shù)。八、（本題8分）已知某電文中共出現(xiàn)了10種不同的字母，每個字母出現(xiàn)的頻率分別為A：8，B：5，C：3，D：2，E：7，F(xiàn)：23，G：9，H：11，I：2，J：35，現(xiàn)在對這段電文用三進制進行編碼（即碼字由0，l，2組成），問電文編碼總長度至少有多少位？請畫出相應(yīng)的圖。九、（本題9分）已知一棵度為m的樹中有N1個度為1的結(jié)點，N2個度為2的結(jié)點，…，Nm個度為m的結(jié)點。試問該樹中有多少個葉子結(jié)點？（北方名校經(jīng)典試題）十、（本題15分）試用遞歸法編寫輸出從n個數(shù)中挑選k個進行排列所得序列的算法。模擬試題（七）參考答案一、單項選擇題（每小題2分，共20分）（1）參考答案：C）（2）【分析】如下所示，三對角矩陣第1行和最后1行非零元素個數(shù)為2個，其余各行的非零元素個數(shù)是3個，所知a66,65前面共有2+3*64＝194個非零元素，a66,65本身是第195個非零元。參考答案：B）（3）【分析】在哈夫曼樹的非葉結(jié)點中最多只有1個結(jié)點的度不為m，設(shè)非葉結(jié)點的個數(shù)為k，則其中有k-1個結(jié)點的度為m，設(shè)另1個結(jié)點的度為u，則2≤u≤m，設(shè)結(jié)點總數(shù)為n總，則有如下關(guān)系：n總-1=m(k-1)+u①n總=k+n②將②代入①可得：k+n-1=m(k-1)+u，解得：，由于2≤u≤m，所以可得0≤m-u＜m-1，所以可得：≤k＜+1，可知。參考答案：C）（4）【分析】設(shè)頂點按拓撲排序序列為：v0,v1,…,vn-1，則對于鄰接矩陣A，只有當i<j時，才可能有弧<vi,vj>，也就是當i>j時，一定沒有弧<vi,vj>，所以這時A[i][j]=0，可知鄰接矩陣為三角矩陣。參考答案：C）（5）【分析】設(shè)另一棵子樹的結(jié)點個數(shù)為n，所以有m=n+k+1，可知n=m-k-l。參考答案：C）（6）【分析】因為K個關(guān)鍵