公務(wù)員計(jì)算機(jī)類《數(shù)據(jù)結(jié)構(gòu)》-期終復(fù)習(xí)試題+答案

四川大學(xué)“精品課程”計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程考試說明與模擬試卷第一部分考試說明數(shù)據(jù)結(jié)構(gòu)與算法分析》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)統(tǒng)設(shè)的一門重要的必修專業(yè)基礎(chǔ)課，它主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)與在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，還研究對(duì)數(shù)據(jù)進(jìn)行的插入、查找、刪除、排序、遍歷等基本運(yùn)算或操作以及這些運(yùn)算在各種存儲(chǔ)結(jié)構(gòu)上具體實(shí)現(xiàn)的算法。由于本課程的主教材采用C++語言描述算法，期末卷面考試也采用C++語言描述，因而要求在做平時(shí)作業(yè)與上機(jī)實(shí)驗(yàn)操作時(shí)用C++開發(fā)工具（如：VisualC++或C++Builder或BorlandC++）。下面按照主教材中各章次序給出每章的具體復(fù)習(xí)要求，以便同學(xué)們更好地進(jìn)行期末復(fù)習(xí)。第一章緒論重點(diǎn)掌握的內(nèi)容：1.數(shù)據(jù)結(jié)構(gòu)的二元組表示，對(duì)應(yīng)的圖形表示，序偶與邊之間的對(duì)應(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ù)組地址的計(jì)算，元素占用存儲(chǔ)空間大小與數(shù)組占用存儲(chǔ)空間大小的計(jì)算。5.普通函數(shù)重載與操作符函數(shù)重載的含義，定義格式與調(diào)用格式。6.函數(shù)定義中值參數(shù)與引用參數(shù)的說明格式及作用，函數(shù)被調(diào)用執(zhí)行時(shí)對(duì)傳送來的實(shí)際參數(shù)的影響。7.算法的時(shí)間復(fù)雜度與空間復(fù)雜度的概念，計(jì)算方法，數(shù)量級(jí)表示。8.一個(gè)簡單算法的最好、最差與平均這三種情況的時(shí)間復(fù)雜度的計(jì)算。對(duì)于本章的其余內(nèi)容均作一般掌握。第二章線性表重點(diǎn)掌握的內(nèi)容：1.線性表的定義及判別與抽象數(shù)據(jù)類型的描述，線性表中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型與參數(shù)表中每個(gè)參數(shù)的作用。2.線性表的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即List類型的定義與每個(gè)域的定義及作用。3.線性表的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時(shí)間復(fù)雜度。4.鏈接存儲(chǔ)的概念，線性表的單鏈接與雙鏈接存儲(chǔ)的結(jié)構(gòu)，向單鏈表中一個(gè)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)或從單鏈表中刪除一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針鏈接過程。5.單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)，每個(gè)域的定義及作用，即LNode類型的定義及結(jié)構(gòu)。6.帶表頭附加結(jié)點(diǎn)的鏈表、循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點(diǎn)。7.線性表的每一種運(yùn)算在單鏈表上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。8.在順序存儲(chǔ)或鏈接存儲(chǔ)的線性表上實(shí)現(xiàn)指定功能的算法的分析與設(shè)計(jì)。9．Josephus問題的求解過程。10．順序表與線性鏈表的性能比較及各自使用背景。對(duì)于本章的其余內(nèi)容均作一般掌握。第三章數(shù)組與廣義表重點(diǎn)掌握的內(nèi)容：1.多維數(shù)組的邏輯結(jié)構(gòu)特征。2.多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及地址計(jì)算公式。3．?dāng)?shù)組是一種隨機(jī)存取結(jié)構(gòu)的原因。4．特殊矩陣與稀疏矩陣的概念。5．特殊矩陣（包括對(duì)角矩陣）與壓縮存儲(chǔ)的下標(biāo)變換方法及所需存儲(chǔ)空間。6.稀疏矩陣的定義與三元組線性表及三列二維數(shù)組表示。7.稀疏矩陣的順序存儲(chǔ)、帶行指針向量的鏈接存儲(chǔ)，在每一種存儲(chǔ)中非零元素結(jié)點(diǎn)的結(jié)構(gòu)。8.稀疏矩陣的轉(zhuǎn)置運(yùn)算。9.廣義表的定義與表示，廣義表長度與深度的計(jì)算。10．廣義表上的求表頭、表尾運(yùn)算。5.廣義表的鏈接存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)類型的定義，分別求廣義表長度與深度的遞歸算法，它們對(duì)應(yīng)的時(shí)間復(fù)雜度。一般掌握的內(nèi)容：稀疏矩陣轉(zhuǎn)置的算法描述。對(duì)于本章的其余內(nèi)容均作一般了解。第四章棧與隊(duì)列重點(diǎn)掌握的內(nèi)容：1.棧的定義與抽象數(shù)據(jù)類型的描述，棧中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型與參數(shù)表中每個(gè)參數(shù)的作用。2.棧的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即Stack類型的定義與每個(gè)域的定義及作用。3．棧的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時(shí)間復(fù)雜度。4.棧的每一種運(yùn)算在鏈接存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。5.算術(shù)表達(dá)式的中綴表示與后綴表示，以及相互轉(zhuǎn)換的規(guī)則，后綴表達(dá)式求值的方法。6．給定n個(gè)棧元素,出棧可能或不可能的序列數(shù)。7.隊(duì)列的定義與抽象數(shù)據(jù)類型的描述，隊(duì)列中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型與參數(shù)表中每個(gè)參數(shù)的作用。8.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即Queue類型的定義與每個(gè)域的定義及作用。9.隊(duì)列的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。10.利用棧與隊(duì)列解決簡單問題的算法分析與設(shè)計(jì)。11．雙端隊(duì)的概念及可能出隊(duì)序列。12．隊(duì)與棧的應(yīng)用背景，如cpu隊(duì)、進(jìn)程隊(duì)、打印機(jī)隊(duì)。13．鏈隊(duì)的各種存儲(chǔ)表示。一般掌握的內(nèi)容：1.后綴表達(dá)式求值的算法，把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法。2.隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)，以及實(shí)現(xiàn)每一種隊(duì)列運(yùn)算的算法與相應(yīng)的時(shí)間復(fù)雜度。對(duì)于本章的其余內(nèi)容均作一般了解。第五章字符串重點(diǎn)掌握的內(nèi)容：1.串的有關(guān)概念及基本運(yùn)算。2.串與線性表的關(guān)系。3．串的各種存儲(chǔ)結(jié)構(gòu)。4．一個(gè)串中真子串與子串個(gè)數(shù)的確定。一般掌握的內(nèi)容：1.串上各種運(yùn)算的實(shí)現(xiàn)及其時(shí)間性能分析。2.使用C++提供的操作函數(shù)構(gòu)造與串相關(guān)的算法解決簡單的應(yīng)用問題。第六章樹與二叉樹重點(diǎn)掌握的內(nèi)容：1.樹與二叉樹的定義，對(duì)于一棵具體樹與二叉樹的二元組表示及廣義表表示。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可求出對(duì)應(yīng)樹或二叉樹的最大與最小高度。5.二叉樹中結(jié)點(diǎn)的編號(hào)規(guī)則與對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)。6.二叉樹的鏈接存儲(chǔ)結(jié)構(gòu)及存儲(chǔ)結(jié)點(diǎn)的類型定義，即BTreeNode類型的定義與每個(gè)域的定義及作用。7.二叉樹的先序、中序、后序、遍歷的遞歸過程與遞歸算法，中序遍歷的非遞歸算法，按層遍歷的過程與算法，每種算法的時(shí)間復(fù)雜度。8．二叉樹的先序、中序、后序遍歷序列，唯一確定一棵二叉樹的原則。9．算術(shù)表達(dá)式的二叉樹表示及逆波蘭表達(dá)式、中綴表示。一般掌握的內(nèi)容：1.普通樹的鏈接存儲(chǔ)結(jié)構(gòu)，GTreeNode類型的定義與每個(gè)域的定義及作用。2．普通樹的先根、后根與按層遍歷的過程及算法。3.在鏈接存儲(chǔ)的二叉樹上實(shí)現(xiàn)指定功能的算法分析與設(shè)計(jì)。對(duì)于本章的其余內(nèi)容均作一般了解。二叉樹的應(yīng)用重點(diǎn)掌握的內(nèi)容：1.二叉搜索樹的定義與性質(zhì)、建立。2.二叉搜索樹查找的遞歸算法與非遞歸算法，相應(yīng)的時(shí)間復(fù)雜度，查找一個(gè)元素的查找長度，即從樹根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)數(shù)。3.二叉搜索樹插入的遞歸算法與非遞歸算法，相應(yīng)的時(shí)間復(fù)雜度，根據(jù)一組數(shù)據(jù)生成一棵二叉搜索樹的過程。4.堆的定義與順序存儲(chǔ)結(jié)構(gòu)，小根堆與大根堆的異同及堆的判別、建立堆的過程。5.向堆中插入元素的過程、算法描述及時(shí)間復(fù)雜度。6.從堆中刪除元素的過程、算法描述及時(shí)間復(fù)雜度。7.哈夫曼樹的定義，樹的帶權(quán)路徑長度的計(jì)算，根據(jù)若干個(gè)葉子結(jié)點(diǎn)的權(quán)構(gòu)造哈夫曼樹的過程。8．順序二叉樹及二叉鏈表表示二叉樹。9．已知關(guān)鍵字序列{22,16,38,89,56，16，79}，試構(gòu)造平衡二叉樹。對(duì)本章的其余內(nèi)容均作一般了解。第七章圖重點(diǎn)掌握的內(nèi)容：1.圖的頂點(diǎn)集與邊集的表示。2.圖的一些概念的含義，如頂點(diǎn)、邊、度、完全圖、子圖、路徑、路徑長度、連通圖、權(quán)、網(wǎng)等。3.圖的鄰接矩陣、鄰接表、鄰接多重表與十字鏈表四種存儲(chǔ)結(jié)構(gòu)及相應(yīng)的空間復(fù)雜度。4.存儲(chǔ)圖使用的vexlist,adjmatrix,adjlist,edgenode,edgeset,edge等類型的定義及用途。5.圖的深度優(yōu)先與廣度優(yōu)先搜索遍歷的過程。6.對(duì)分別用鄰接矩陣與用鄰接表表示的圖進(jìn)行深度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時(shí)間復(fù)雜度。7.對(duì)分別用鄰接矩陣與用鄰接表表示的圖進(jìn)行廣度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時(shí)間復(fù)雜度。8.圖的生成樹（若一個(gè)具有n個(gè)頂點(diǎn)，e條邊的無向圖是一個(gè)森林（n＞e），則該森林中必有多少棵樹。）、深度優(yōu)先生成樹與廣度優(yōu)先生成樹、生成樹的權(quán)、最小生成樹等的定義。9.根據(jù)普里姆算法求圖的最小生成樹的過程。10．根據(jù)克魯斯卡爾算法求圖的最小生成樹的過程。11.圖的拓?fù)湫蛄信c拓?fù)渑判虻母拍?，求圖的拓?fù)湫蛄械姆椒ǎ瑢?duì)用鄰接表表示的圖進(jìn)行拓?fù)渑判虻倪^程。12．強(qiáng)連通圖的最少邊數(shù)。一般掌握的內(nèi)容：1．根據(jù)普里姆算法求圖的最小生成樹的算法描述。2．根據(jù)克魯斯卡爾算法求圖的最小生成樹的算法描述。3.對(duì)用鄰接表表示的圖進(jìn)行拓?fù)渑判虻呐c算法描述。對(duì)本章的其余內(nèi)容均作一般了解。第八章查找重點(diǎn)掌握的內(nèi)容：1.在一維數(shù)組及單鏈表上進(jìn)行順序查找的過程、算法、成功及不成功的平均查找長度與時(shí)間復(fù)雜度。2.在一維數(shù)組上進(jìn)行二分查找的過程、遞歸與非遞歸算法、平均查找長度與時(shí)間復(fù)雜度，二分查找一個(gè)給定值元素的查找長度（即查找路徑上的元素?cái)?shù)），二分查找對(duì)應(yīng)的判定樹的性質(zhì)。3.散列存儲(chǔ)的概念，散列函數(shù)、散列表、沖突、同義詞、裝填因子等術(shù)語的含義。4.利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。5.利用開放定址法中的線性探查法處理沖突進(jìn)行散列存儲(chǔ)與查找的過程，利用鏈接法處理沖突進(jìn)行散列存儲(chǔ)與查找的過程。6.根據(jù)除留余數(shù)法構(gòu)造散列函數(shù)，采用線性探查法或鏈接法處理沖突，把一組數(shù)據(jù)散列存儲(chǔ)到散列表中，計(jì)算出一個(gè)給定值元素的查找長度與查找所有元素的平均查找長度。7.B_樹中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)，樹根結(jié)點(diǎn)或非樹根結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)范圍與子樹的個(gè)數(shù)范圍，B_的結(jié)構(gòu)特性，從B_樹上查找一個(gè)給定值元素的過程。一般掌握的內(nèi)容：1.B_樹查找算法。2.向B_樹中插入元素的過程。對(duì)本章的其余內(nèi)容均作一般了解。第九章排序重點(diǎn)掌握的內(nèi)容：1.直接插入、直接選擇與冒泡排序的方法，排序過程及時(shí)間復(fù)雜度。2.在堆排序中建立初始堆的過程與利用堆排序的過程，對(duì)一個(gè)分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的過程、算法及時(shí)間復(fù)雜度，整個(gè)堆排序的算法描述及時(shí)間復(fù)雜度。3.快速排序的方法，對(duì)一組數(shù)據(jù)的排序過程，對(duì)應(yīng)的二叉搜索樹，快速排序過程中劃分的層數(shù)與遞歸排序區(qū)間的個(gè)數(shù)。4.遞歸排序的遞歸算法，它在平均情況下的時(shí)間與空間復(fù)雜度，在最壞情況下的時(shí)間與空間復(fù)雜度。5.二路歸并排序的方法與對(duì)數(shù)據(jù)的排序過程，每趟排序前、后的有序表長度，二路歸并排序的趟數(shù)、時(shí)間復(fù)雜度與空間復(fù)雜度。6．各種排序方法的不同數(shù)據(jù)序的比較、最好、最壞、平均情況。7．哪些排序不受初始數(shù)據(jù)的影響。一般掌握的內(nèi)容：1.每一種排序方法的穩(wěn)定性。2.直接插入排序與直接選擇排序的算法。一般了解的內(nèi)容：1.二路歸并排序過程中涉及的每個(gè)算法描述。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)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖B）隊(duì)列C）線索二叉樹D）B樹（2）在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由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個(gè)元素之后插入一個(gè)元素 B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空D）讀取隊(duì)頭元素的值（4）字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串。A）14B）5C）6D）8（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A）11B）35C）19D）53以下6-8題基于下圖：（6）該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（）。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é)點(diǎn)的中序遍歷的序列為（）。A）A、B、C、D、E、G、F B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E（8）該二叉樹的按層遍歷的序列為（）。A）E、G、F、A、C、D、BB）E、A、C、B、D、G、FC）E、A、G、C、F、B、DD）E、G、A、C、D、F、B（9）下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（）。A）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)B）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)與結(jié)點(diǎn)個(gè)數(shù)都有關(guān)C）用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)與邊數(shù)都有關(guān)D）用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h)，下面哪一個(gè)序列是從上述序列出發(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分）已知一個(gè)65稀疏矩陣如下所示，試：（1）寫出它的三元組線性表；（2）給出三元組線性表的順序存儲(chǔ)表示。三、（本題8分）求網(wǎng)的最小生成樹有哪些算法？它們的時(shí)間復(fù)雜度分別下多少，各適用何種情況？四、（每小題4分，共8分）對(duì)于如下圖所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：（1）從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；（2）從頂點(diǎn)v2出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹。五、（本題8分）已知一個(gè)圖的頂點(diǎn)集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>};若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試給出得到的拓?fù)渑判虻男蛄小Ａ?、（本題8分）對(duì)于序列{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）對(duì)于增量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分）模擬試題（一）參考答案一、單項(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）三元組線性表的順序存儲(chǔ)表示如下所示：三、（本題8分）求網(wǎng)的最小生成樹可使用Prim算法，時(shí)間復(fù)雜度為O(n2)，此算法適用于邊較多的稠密圖，也可使用Kruskal算法，時(shí)間復(fù)雜度為O(eloge)，此算法適用于邊較少的稀疏圖。四、（每小題4分，共8分）（1）DFS：v1v2v3v4v5（2）BFS：v2v3v4v5v1五、（本題8分）拓?fù)渑判驗(yàn)椋?365721六、（本題8分）所構(gòu)造的堆如下圖所示：七、（本題8分）在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。八、（每小題2分，共8分）（1）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對(duì)于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23九、（本題9分）哈希表如下圖所示：十、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個(gè)結(jié)點(diǎn)，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點(diǎn)。C++語言版測試程序見exam1\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<classEntry>voidaux_display_BT_with_tree_shape(Binary_node<Entry>*sub_root,intlevel=1)// 按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1if(sub_root!=NULL) { //空樹不顯式，只顯式非空樹 aux_display_BT_with_tree_shape<Entry>(sub_root->right,level+1);//顯示右子樹cout<<endl; //顯示新行 for(inti=0;i<level-1;i++) cout<<""; //確保在第level列顯示結(jié)點(diǎn) cout<<sub_root->data; //顯示結(jié)點(diǎn)aux_display_BT_with_tree_shape<Entry>(sub_root->left,level+1);//顯示左子樹C語言版測試程序見exam1\10c，具體算當(dāng)如下：voidDisplayBTWithTreeShape(BiTreeT,intlevel=1)// 按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1 if(T){ //空樹不顯式，只顯式非空樹DisplayBTWithTreeShape(T->rchild,level+1); //顯示右子樹 cout<<endl; //顯示新行 for(inti=0;i<level-1;i++) cout<<""; //確保在第level列顯示結(jié)點(diǎn)cout<<T->data; //顯示結(jié)點(diǎn) DisplayBTWithTreeShape(T->lchild,level+1); //顯示左子樹模擬試題（二）一、單項(xiàng)選擇題（每小題2分，共20分）（1）設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（）。A）2m B）2m-1C）2m+1 D）m+1（A）nB）n-1C）n+1D）不確定（3）下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（）A）存儲(chǔ)密度大 B）插入與刪除運(yùn)算方便C）獲取符合某種條件的元素方便D）查找運(yùn)算速度快（A）658 B）648 C）633 D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（）。A）若一個(gè)葉子是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)B）若一個(gè)結(jié)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)C）若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn)D）若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)（6）k層二叉樹的結(jié)點(diǎn)總數(shù)最多為（）。A）2k-1B）2k+1C）2K-1D）2k-1（7）對(duì)線性表進(jìn)行二分法查找，其前提條件是（）。A）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序（8）對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為（）。A）O(1og2n) B）O(n) C）O(1) D）O(n2)（9）對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%7作為散列函數(shù)，則散列地址為0的元素有（）個(gè)。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ù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法二、（本題8分）假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。三、（每小題4分，共8分）已知一個(gè)無向圖的頂點(diǎn)集為{a,b,c,d,e}，其鄰接矩陣如下所示：（1）畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷與廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。四、（本題8分）樹有哪些遍歷方法？它們分別對(duì)應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？五、（本題8分）設(shè)有數(shù)組A[-1:3,0:6,-2:3]，按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5，試計(jì)算出A[1,1,1]的存儲(chǔ)位置。六、（本題8分）試列出如下圖中全部可能的拓?fù)渑判蛐蛄?。七、（本題8分）已知哈希表地址空間為0..8，哈希函數(shù)為H(key)=key%7，采用線性探測再散列處理沖突，將數(shù)據(jù)序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入時(shí)的比較次數(shù)，并求出在等概率下的平均查找長度。八、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。九、（本題9分）試畫出表達(dá)式(a+b/c)*(d-e*f)的二叉樹表示，并寫出此表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示。十、（本題15分）以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫計(jì)算二叉樹中葉子結(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分）樹的遍歷方法有先根序遍歷與后根序遍歷，它們分別對(duì)應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄浜蟮南刃虮闅v與中序遍歷方法。五、（本題8分）A。六、（本題8分）全部可能的拓?fù)渑判蛐蛄袨椋?523634、152634、156234、561234、516234、512634、512364七、（本題8分）哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示：ASL=(4×1+1×2+1×4+2×5)=2.5八、（本題8分）九、（本題9分）表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達(dá)式的二叉樹表示的前序遍歷、中序遍歷及后序遍歷序列。二叉樹表示如下圖所示：波蘭式表示：*+a/bc-d*ef中綴表示：a+b/c*d-e*f逆波蘭式表示：abc/+def*-*十、（本題15分）本題只要在遍歷二叉樹的過程序中對(duì)葉子結(jié)點(diǎn)進(jìn)行記數(shù)即可。C++語言版測試程序見exam2\10c++，具體算當(dāng)如下：template<classEntry>longleaf_count(constBinary_tree<Entry>&T)// 計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)目returnaux_leaf_count<Entry>(T.get_root());template<classEntry>longaux_leaf_count(Binary_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; //只有一個(gè)結(jié)點(diǎn)的樹返回1 else //葉子結(jié)點(diǎn)數(shù)為左右子樹的葉子結(jié)點(diǎn)數(shù)之與returnaux_leaf_count(sub_root->left)+aux_leaf_count(sub_root->right); C語言版測試程序見exam2\10c，具體算當(dāng)如下：longLeafCount(BiTreeT)// 計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)目 if(T==NULL) return0; //空樹返回0elseif(T->lchild==NULL&&T->rchild==NULL) return1; //只有一個(gè)結(jié)點(diǎn)的樹返回1 else //葉子結(jié)點(diǎn)數(shù)為左右子樹的葉子結(jié)點(diǎn)數(shù)之與 returnLeafCount(T->lchild)+LeafCount(T->rchild); 模擬試題（三）一、單項(xiàng)選擇題（每小題2分，共20分）（1）對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。A）健壯性與可讀性 B）并行性C）正確性D）時(shí)空復(fù)雜度（A）p->next=HL->next;HL->next=pB）p->next=HL;HL=pC）p->next=HL;p=HLD）HL=p;p->next=HL（3）對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）A）經(jīng)常需要隨機(jī)地存取元素B）經(jīng)常需要進(jìn)行插入與刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 D）表中元素的個(gè)數(shù)不變（4）一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是（）。A）231 B）321 C）312 D）123（5）A）冒泡排序 B）簡單選擇排序C）希爾排序 D）直接插入排序（6）采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（）。A）低于鏈接法處理沖突 B）高于鏈接法處理沖突C）與鏈接法處理沖突相同 D）高于二分查找（7）若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（）參數(shù)。A）值 B）函數(shù) C）指針 D）引用（8）在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。A）行號(hào) B）列號(hào) C）元素值 D）非零元素個(gè)數(shù)（9）快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2)（10）從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。A）O(n)B）O(1)C）O(log2n)D）O(n2)二、（本題8分）已知一個(gè)圖的頂點(diǎn)集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分）請(qǐng)畫出如下圖所示的鄰接矩陣與鄰接表。四、（每小題4分，共8分）設(shè)（1）找出所有的關(guān)鍵路徑。（2）v3事件的最早開始時(shí)間是多少。五、（本題8分）如果在1000000個(gè)記錄中找出兩個(gè)最小的記錄，你認(rèn)為采用什么樣的排序方法所需的關(guān)鍵字比較次數(shù)最少？最多比較多少次？六、（本題8分）假設(shè)把n個(gè)元素的序列（a1,a2,…an）滿足條件ak<max{at|1≤t≤k}的元素ak稱為“逆序元素”。若在一個(gè)無序序列中有一對(duì)元素ai>aj(i<j)，試問，當(dāng)ai與aj相互交換后，該序列中逆序元素的個(gè)數(shù)一定不會(huì)增加，這句話對(duì)不對(duì)？如果對(duì)，請(qǐng)說明為什么？如果不對(duì)，請(qǐng)舉一例說明。七、（每小題4分，共8分）設(shè)內(nèi)存有大小為6個(gè)記錄的緩沖區(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)排序求出初始?xì)w并段；（2）用置換一選擇排序求初始?xì)w并段。八、（本題8分）已知一組關(guān)鍵字為（19,14,23,1,68,20,84,27,55,11,10,79），哈希函數(shù)：H(key)=keyMOD13，哈希地址空間為0~12，請(qǐng)構(gòu)造用鏈地址法處理沖突的哈希表，并求平均查找長度。九、（本題9分）已知關(guān)鍵字序列{23，13，5，28，14，25}，試構(gòu)造二叉排序樹。十、（本題15分）編寫一個(gè)算法求二又樹的深度。模擬試題（三）參考答案一、單項(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)鍵路徑有：v1→v2→v3→v5→v6，以及v1→v4→v6。（2）v3事件的最早開始時(shí)間是13。五、（本題8分）采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)=999999+=1000019次。六、（本題8分）不七、（每小題4分，共8分）（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分）用鏈地址法處理沖突的哈希表如下圖所示：ASL=(1*6+2*4+3*1+4*1)=1.75九、（本題9分）構(gòu)造二叉排序樹的過程如下圖所示。構(gòu)造的二叉排序樹如下圖所示：十、（本題15分）若二叉樹為空，深度為0；若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。C++語言版測試程序見exam3\10c++，具體算當(dāng)如下：template<classEntry>intbitree_depth(constBinary_tree<Entry>&T)// 求二叉樹的深度 returnaux_bitree_depth(T.get_root());template<classEntry>intaux_bitree_depth(Binary_node<Entry>*sub_root)// 求二叉樹的深度if(sub_root==NULL)return0; //空二叉樹的深度為0 elseintd_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)+1;C語言版測試程序見exam3\10c，具體算當(dāng)如下：intBiTreeDepth(BiTreeT)// 求二叉樹的深度 if(T==NULL) return0; //空二叉樹的深度為0else intd_lsub,d_rsub;d_lsub=BiTreeDepth(T->lchild); //左子樹的深度 d_rsub=BiTreeDepth(T->rchild); //右子樹的深度 //返回左右子樹的深度最大值加1 return((d_lsub>d_rsub)d_lsub:d_rsub)+1;模擬試題（四）一、單項(xiàng)選擇題（每小題2分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖B）棧C）二叉樹D）B樹（2）若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)與刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A）單鏈表 B）雙鏈表 C）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D）單循環(huán)鏈表（3）（）不是隊(duì)列的基本運(yùn)算。A）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空D）讀取隊(duì)頭元素的值（4）字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串？A）15B）14C）16D）21（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A）11B）37C）19D）53以下6-8題基于下面的敘述：若某二叉樹結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。（6）則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（）。A）E、G、F、A、C、D、BB）E、A、G、C、F、B、DC）E、A、C、B、D、G、FD）E、G、A、C、D、F、B（7）該二叉樹有（）個(gè)葉子。A）3B）2C）5D）4（8）該二叉樹的按層遍歷的序列為（）。A）E、G、F、A、C、D、BB）E、A、C、B、D、G、FC）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分）試述順序查找法、折半查找法與分塊查找法對(duì)被查找的表中元素的要求，對(duì)長度為n的查找表來說，三種查找法在查找成功時(shí)的查找長度各是多少？三、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80}，試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。四、（本題8分）給定一個(gè)關(guān)鍵字序列｛24，19，32，43，38，6，13，22｝，請(qǐng)寫出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時(shí)間復(fù)雜度最差？五、（本題8分）設(shè)二維數(shù)組A[0:10,-5:0]，按行優(yōu)先順序存儲(chǔ)，每個(gè)元素占4個(gè)單元，A[0][-5]的存儲(chǔ)地址為1000，則A[9][-2]的存儲(chǔ)地址為多少？六、（本題8分）用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL。請(qǐng)寫出后序遍歷該二叉樹的訪問結(jié)點(diǎn)序列。七、（本題8分）請(qǐng)說明對(duì)一棵二叉樹進(jìn)行前序、中序與后序遍歷，其葉結(jié)點(diǎn)的相對(duì)次序是否會(huì)發(fā)生改變？為什么？八、（本題8分）對(duì)九、（本題9分）已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI十、（本題15分）已知二叉排序樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，根結(jié)點(diǎn)的指針為T，請(qǐng)寫出遞歸算法，從小到大輸出該二叉排序樹中所有關(guān)鍵字值≥K的結(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分）三種方法對(duì)查找的要求分別如下：順序查找法：表中元素可以任意存放；折半查找法：表中元素必須以關(guān)鍵字的大小遞增或遞減的次序存放：分塊查找法：表中元素每塊內(nèi)的元素可任意存放，但塊與塊之間必須以關(guān)鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大于（或?。┖笠粔K內(nèi)任何元素的關(guān)鍵字。三種方法的平均查找長度分別如下：順序查找法：查找成功的平均查找長度為；折半查找法：查找成功的平均查找長度為log2(n+1)+1；分塊查找法：若用順序查找確定所在的塊，平均查找長度為；若用折半確定所在塊，平均查找長度為。三、（本題8分）如下圖所示：四、（本題8分）快速排序的第一趟結(jié)果為｛22,19,13,6,24,38,43,12｝；堆排序時(shí)所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是O(1)，快速排序是O(logn)，可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時(shí)間：堆是O(nlogn)，快速排序是O(n2)，所以，可見快速排序時(shí)間復(fù)雜度最差。注意：快速排序的平均時(shí)排序速度最快，但在最壞情況下不一定比其他排序方法快。五、（本題8分）依題意A的起始地址為1000，則有：Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。六、（本題8分）先畫出該二叉樹的樹形結(jié)構(gòu)。對(duì)其進(jìn)行后序遍歷得到后序序列為：HIDJKEBLFGCA。七、（本題8分）二叉樹任兩個(gè)中葉結(jié)點(diǎn)必在某結(jié)點(diǎn)的左/右子樹中，三種遍歷方法對(duì)左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進(jìn)行遍歷的。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對(duì)次序是不會(huì)發(fā)生改變的。八、（本題8分）用Kruskal算法構(gòu)造最小生成樹的過程如下圖所示：九、（本題9分）先由先序序列的第一個(gè)結(jié)點(diǎn)確定二叉樹的根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序序列中左側(cè)部分為左子樹結(jié)點(diǎn)，在右側(cè)部分為右子樹結(jié)點(diǎn)，再由先序序列的第一個(gè)結(jié)點(diǎn)確定根結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)，由類似的方法可確定其他結(jié)點(diǎn)，如下圖所示。十、（本題15分）由于二叉排序樹是中序有序的，因此對(duì)二叉排序樹采用中序遍歷依次輸出大于等于K的結(jié)點(diǎn)即可。C++語言版采用教材所提供的二叉排序樹的存儲(chǔ)結(jié)構(gòu)，并使用友元方式共享二叉排序的根指針，測試程序見exam4\10c++，具體算當(dāng)如下：template<classRecord>voiddisplay_key(constBinary_tree<Record>&T,RecordK)// 從小到大輸出該二又排序樹中所有關(guān)鍵字值≥K的結(jié)點(diǎn)的關(guān)鍵字的值aux_display_key<Record>(T.get_root(),K);template<classRecord>voidaux_display_key(Binary_node<Record>*sub_root,RecordK)// 從小到大輸出該二又排序樹中所有關(guān)鍵字值≥K的結(jié)點(diǎn)的關(guān)鍵字的值的輔助函數(shù) if(sub_root)aux_display_key<Record>(sub_root->left,K); //輸出左子樹 if(sub_root->data>=K) cout<<sub_root->data<<""; //輸出滿足條件的關(guān)鍵值aux_display_key<Record>(sub_root->right,K); //輸出右子樹C語言版測試程序見exam4\10c，具體算當(dāng)如下：voidDisplayKey(BiTreeT,KeyTypeK)// 從小到大輸出該二叉排序樹中所有關(guān)鍵字值≥K的結(jié)點(diǎn)的關(guān)鍵字的值if(T) DisplayKey(T->lchild,K); //輸出左子樹if(T->data.key>=K)cout<<T->data.key<<""; //輸出滿足條件的關(guān)鍵值 DisplayKey(T->rchild,K); //輸出右子樹模擬試題（五）一、單項(xiàng)選擇題（每小題2分，共20分）（1）隊(duì)列的特點(diǎn)是（）。A）先進(jìn)后出 B）先進(jìn)先出 C）任意位置進(jìn)出 D）前面都不正確（2）有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行（）遍分配與收集。A）n B）d C）r D）n-d（3）在二叉樹結(jié)點(diǎn)的先序序列、中序序列與后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。A）都不相同 B）完全相同C）先序與中序相同，而與后序不同 D）中序與后序相同，而與先序不同（4）限定在一端加入與刪除元素的線性表稱為（）。A）雙向鏈表 B）單向鏈表 C）棧D）隊(duì)列（5）快速排序執(zhí)行一遍之后，已經(jīng)到位的元素個(gè)數(shù)是（）。A）1 B）3 C）D）（6）設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（）。A）m-n-1 B）n+1 C）m-n+1 D）m-n（7）設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為（）。A）12 B）13 C）14D）15（8）下面關(guān)于廣義表的敘述中，不正確的是（）。A）廣義表可以是一個(gè)多層次的結(jié)構(gòu) B）廣義表至少有一個(gè)元素C）廣義表可以被其他廣義表所共享 D）廣義表可以是一個(gè)遞歸表（9）設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵深度（高度）為k的滿二叉樹與同樣深度完全二叉樹各有f個(gè)結(jié)點(diǎn)與c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是（）。A）f>=c B）c>f C）f=2k+1-a D）c>sk-1（10）從L=((apple,pear),(orange,banana))中，取出banana元素的表達(dá)式為（）。A）head(tail(L)) B）head(head(tail(L)))C）tail(head(tail(L))) D）head(tail(head(tail(L))))二、（每小題4分，共8分）寫出下列中綴表達(dá)式的后綴形式：（1）3X/(Y-2)+1（2）2+X*(Y+3)三、（每小題4分，共8分）試對(duì)如下圖中的二叉樹畫出其：（1）順序存儲(chǔ)表示；（2）二叉鏈表存儲(chǔ)表示的示意圖。四、（每小題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分）已知一個(gè)圖的頂點(diǎn)集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};按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。六、（每小題2分，共8分）設(shè)有12個(gè)數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58，它們存儲(chǔ)在散列表中，利用線性探測再散列處理沖突，取散列函數(shù)為H(key)=key%13。（1）順次將各個(gè)數(shù)據(jù)散列到表中，并同時(shí)列出各元素的比較次數(shù)。（2）計(jì)算查找成功的平均查找次數(shù)。七、（第1小題2分，第2、3小題每小題3分，本題8分）對(duì)于如下圖所示的圖G，鄰接點(diǎn)按從小到大的次序。（1）圖G有幾個(gè)連通分量？（2）按深度優(yōu)先搜索所得的樹是什么？（3）按深度優(yōu)先搜索所得的頂點(diǎn)序列是什么？八、（本題8分）已知一棵樹邊的結(jié)點(diǎn)為：{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)}試畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）樹的深度是多少？九、（本題9分）給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個(gè)記錄為樞軸）十、（本題15分）編寫復(fù)制一棵二叉樹的非遞歸算法。模擬試題（五）參考答案一、單項(xiàng)選擇題（每小題2分，共20分）（1）B （2）B （3）B （4）C （5）A（6）D （7）C （8）B （9）B （10）D二、（每小題4分，共8分）（1）3X*Y2-/1+（2）2XY3+*+三、（每小題4分，共8分）（1）二叉樹的順序存儲(chǔ)表示如下所示：0123456789101112131415161718123456789（2）二叉樹的二叉鏈表存儲(chǔ)表示的示意圖如下圖所示：四、（每小題4分，共8分）（1）不是小根堆。調(diào)整為：{12,24,33,65,33,56,48,92,86,70}（2）是小根堆。五、（本題8分）普里姆算法從頂點(diǎn)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）順次將各個(gè)數(shù)據(jù)散列到表中，并同時(shí)列出各元素的比較次數(shù)如下表所示。各元素的比較次數(shù)地址01234567891011121314關(guān)鍵字40669455833477287222512比較121111132312（4）計(jì)算查找成功的平均查找次數(shù)=（1×7+2×3+3×2）/12=19/12。七、（第1小題2分，第2、3小題每小題3分，本題8分）（1）圖G有2個(gè)連通分量。（2）按深度優(yōu)先搜索所得的樹如下圖所示：（3）按深度優(yōu)先搜索所得的頂點(diǎn)序列：ABHFGCDE八、（本題8分）【解答】樹，如下圖所示：（1）C是根結(jié)點(diǎn)。（2）F，K，L，H，D，M，N是葉子結(jié)點(diǎn)。（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分）可采用層次遍歷的方式進(jìn)行復(fù)制，將已復(fù)制的結(jié)點(diǎn)進(jìn)入一個(gè)隊(duì)列中即可。C++語言版測試程序見exam5\10c++，具體算當(dāng)如下：template<classEntry>voidcopy_bitree(Binary_tree<Entry>*T_from,Binary_tree<Entry>*&T_to)// 復(fù)制二叉樹T_from到T_to的非遞歸算法 if(T_from->empty()){ //空二叉樹的處理T_to=newBinary_tree<Entry>; return; Queue<Binary_node<Entry>*>Q_from,Q_to;Binary_node<Entry>*e_from,*e_to,*from_root,*to_root; from_root=T_from->get_root();to_root=newBinary_node<Entry>(from_root->data); //復(fù)制根結(jié)點(diǎn) Q_from.append(from_root);Q_to.append(to_root); //入隊(duì)while(!Q_from.empty()) Q_from.retrieve(e_from);Q_from.serve(); //出隊(duì) Q_to.retrieve(e_to);Q_to.serve(); //出隊(duì) if(e_from->left!=NULL) { //復(fù)制e_from左孩子 e_to->left=newBinary_node<Entry>(e_from->left->data); Q_from.append(e_from->left);Q_to.append(e_to->left);//入隊(duì) if(e_from->right!=NULL) { //復(fù)制e_from右孩子 e_to->right=newBinary_node<Entry>(e_from->right->data); Q_from.append(e_from->right);Q_to.append(e_to->right);//入隊(duì) T_to=newBinary_tree<Entry>(to_root);C語言版測試程序見exam5\10c，具體算當(dāng)如下：voidCopyBiTree(BiTreeT_from,BiTree&T_to)// 復(fù)制二叉樹T_from到T_to的非遞歸算法if(T_from==NULL) { //空二叉樹的處理 T_to=NULL;return; LinkQueueQ_from,Q_to; BiTNode*e_from,*e_to;InitQueue(Q_from);InitQueue(Q_to); T_to=newBiTNode; T_to->data=T_from->data; //復(fù)制根結(jié)點(diǎn) EnQueue(Q_from,T_from);EnQueue(Q_to,T_to); //入隊(duì)while(QueueEmpty(Q_from)==FALSE) DeQueue(Q_from,e_from);DeQueue(Q_to,e_to); //出隊(duì)if(e_from->lchild!=NULL) { //復(fù)制e_from左孩子 e_to->lchild=newBiTNode; e_to->lchild->data=e_from->lchild->data; EnQueue(Q_from,e_from->lchild);EnQueue(Q_to,e_to->lchild);//入隊(duì) else e_to->lchild=NULL; //左孩子為空if(e_from->rchild!=NULL) { //復(fù)制e_from右孩子 e_to->rchild=newBiTNode; e_to->rchild->data=e_from->rchild->data;EnQueue(Q_from,e_from->rchild);EnQueue(Q_to,e_to->rchild);//入隊(duì) else e_to->rchild=NULL; //右孩子為空模擬試題（六）一、單項(xiàng)選擇題（每小題2分，共20分）（1）下列文件的物理結(jié)構(gòu)中，不利于文件長度動(dòng)態(tài)增長的文件物理結(jié)構(gòu)是（）。A）順序結(jié)構(gòu)B）鏈接結(jié)構(gòu)C）索引結(jié)構(gòu)D）Hash結(jié)構(gòu)（2）在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由（）。A）實(shí)體 B）域 C）數(shù)據(jù)項(xiàng) D）字段（3）對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德（Floyd）算法求每一對(duì)頂之間的最短路徑的時(shí)間復(fù)雜度是（）。A）O(1) B）O(n) C）O(n) D）O(n3)（4）對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為（）。A）O（1） B）O（log2n） C）O（n） D）O（n2）（5）哈夫曼樹中一定不存在（）。A）度為0的結(jié)點(diǎn) B）度為1的結(jié)點(diǎn) C）度為2的結(jié)點(diǎn) D）帶權(quán)的結(jié)點(diǎn)（6）設(shè)D={A,B,C,D}，R={<E,A>,<A,B>,<B,D>,<D,E>,<D,A>}，則數(shù)據(jù)結(jié)構(gòu)(D,{R})是（）。A）樹 B）圖 B）線性表 D）前面都正確（7）（）關(guān)鍵碼序列不符合堆的定義。A）A、C、D、G、H、M、P、Q、R、XB）A、C、M、D、H、P、X、G、Q、RC）A、D、P、R、C、Q、X、M、H、GD）A、D、C、M、P、G、H、X、R、Q（8）假定關(guān)鍵字K=442205883，允許存儲(chǔ)地址為四位十進(jìn)制數(shù)，并且Hash地址為6111，則所采用的構(gòu)造Hash函數(shù)的方法是（）。A）直接定址法 B）平方取中法 C）除留余數(shù)法，模為97 D）折疊法（9）在算法的時(shí)間復(fù)雜度中，n表示問題規(guī)模，f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，則隨問題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率同（）相同。A）f(n)B）n C）O(n) D）前面都不正確（10）對(duì)線性表進(jìn)行二分法查找，其前提條件是（）。A）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序二、（本題8分）在如下表所示的數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A[0].next，試寫出該線性表。線性表A01234567Data605078903440next4052713三、（本題8分）已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ，中序遍歷的結(jié)果是KBCDAFHIGJ，試畫出這棵二叉樹。四、（本題8分）已知一個(gè)圖的頂點(diǎn)集V為：V={1,2,3,4,5,6,7}，弧如下表所示。圖的弧集起點(diǎn)1225522613終點(diǎn)6454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。五、（本題8分）向最小根堆中依次插入數(shù)據(jù)4,2,5,8,3,6,10,1時(shí)，畫出每插入一個(gè)數(shù)據(jù)后堆的變化。六、（本題8分）已知廣義表L=(((b,c),d),((a),((b,c),d)),())，試畫出它的存儲(chǔ)結(jié)構(gòu)。七、（每小題4分，共8分）對(duì)給定的有7個(gè)頂點(diǎn)的有向圖的鄰接矩陣如下：（l）畫出該有向圖；（2）若將圖看成是AOE-網(wǎng)，畫出關(guān)鍵路徑。八、（本題8分）給出一組關(guān)鍵字29、18、25、47、58、12、51、10，分別寫出按下列各種排序方法進(jìn)行排序時(shí)的變化過程：（1）歸并排序，每歸并一次書寫一個(gè)次序。（2）快速排序，每劃分一次書寫一個(gè)次序以及最后排好序后的序列。（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)（3）堆排序，先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次。九、（本題9分）試分別畫出具有3個(gè)結(jié)點(diǎn)的樹與具有3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。十、（本題15分）設(shè)計(jì)以單鏈表存儲(chǔ)的兩個(gè)集合求交集的算法。模擬試題（六）參考答案一、單項(xiàng)選擇題（每小題2分，共20分）（1）A （2）C （3）D （4）B （5）B（6）B （7）C （8）D （9）A （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分）本題廣義表存儲(chǔ)結(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)（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個(gè)結(jié)點(diǎn)的樹的不同形態(tài)如下圖所示。具有3個(gè)結(jié)點(diǎn)的二叉樹的不同形態(tài)如下圖所示。十、（本題15分）用單鏈表lc表示集合C。分別將la中元素取出，再在lb中進(jìn)行查找，如在lb中出現(xiàn)，則將其插入到lc中。C++語言版測試程序見exam6\10c++，具體算當(dāng)如下：template<classList_entry>voidinteraction(List<List_entry>*&la,List<List_entry>*&lb,List<List_entry>*&lc)// 將鏈表la與lb中共同出現(xiàn)的元素插入到鏈表lc中 List_entryla_it,lb_it;lc=newList<List_entry>; //生成lc for(inti=0;i<la->size();i++)la->retrieve(i,la_it); for(intj=0;j<lb->size();j++) lb->retrieve(j,lb_it);if(la_it==lb_it)break; if(j<lb->size()) //定位成功 lc->insert(lc->size(),la_it);C語言版測試程序見exam6\10c，具體算當(dāng)如下：voidinteraction(LinkListla,LinkListlb,LinkList&lc)// 將鏈表la與lb中共同出現(xiàn)的元素插入到鏈表lc中 LinkListpa,pb,pc;lc=newLNode; //生成lc的頭結(jié)點(diǎn) pc=lc; //pc永遠(yuǎn)指向lc的尾結(jié)點(diǎn)pa=la->next; //pa指向la的第一個(gè)元素 while(pa)pb=lb->next; while(pb&&pb->data!=pa->data) pb=pb->next; //在pb中定位pa->dataif(pb) //定位成功 pc->next=newLNode; //生成lc新的尾結(jié)點(diǎn) pc=pc->next; //pc指向新的尾結(jié)點(diǎn) pc->data=pa->data; //將pa->data復(fù)制到pc中pa=pa->next; pc->next=NULL; //pc為尾結(jié)點(diǎn)，其后繼為空*模擬試題（七）注：本套試題選作一、單項(xiàng)選擇題（每小題2分，共20分）（1）若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限雙端隊(duì)列得到，也不能由輸出受限雙端隊(duì)列得到的輸出序列是（）。A）1234 B）4132 C）4231 D）4213（2）將一個(gè)A[1..100,1..100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[298]中，A中元素a66,65（即該元素下標(biāo)）在B數(shù)組中的位置k為（）（假設(shè)B[0]的位置是1）。 A）198 B）195 C）197 D）198【（3）若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為（）。A）n-1 B）C） D）（4）若一個(gè)有向圖具有拓?fù)渑判蛐蛄?，并且頂點(diǎn)按拓?fù)渑判蛐蛄芯幪?hào)，則它的鄰接矩陣必定為（）。A）對(duì)稱矩陣 B）稀疏矩陣 C）三角矩陣 D）一般矩陣（5）設(shè)森林F對(duì)應(yīng)的二叉樹為有m個(gè)結(jié)點(diǎn)，此二叉樹根的左子樹的結(jié)點(diǎn)個(gè)數(shù)為k，則另一棵子樹的結(jié)點(diǎn)個(gè)數(shù)為（）。A）m-k+1 B）k+1 C）m-k-1 D）m-k（6）假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行（）次探測。A）K-1次B）K次C）K＋l次D）K(K+1)/2次（7）一棵深度為k的平衡二叉樹，其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0，則該樹共有（）個(gè)結(jié)點(diǎn)。A）2k-1-1 B）2k-1C）2k-1+1D）2k-1（8）如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用（）方法比較次數(shù)較少。A）直接插入排序 B）快速排序 C）歸并排序 D）選擇排序（9）如果只考慮有序樹的情形，則具有7個(gè)結(jié)點(diǎn)的不同形態(tài)的樹共有（）棵。A）132 B）154 C）429 D）前面均不正確（10）對(duì)ISAM文件的刪除記錄時(shí)，一般()A）只需做刪除標(biāo) B）需移動(dòng)記錄C）需改變指針 D）一旦刪除就要做整理二、（本題8分）斐波那契數(shù)列Fn定義如下：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2請(qǐng)就此斐波那契數(shù)列，回答下列問題：（1）在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn-1，F(xiàn)n-2，…，F(xiàn)1，F(xiàn)0精確計(jì)算多少次？（2）若用有關(guān)大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度是多少？三、（本題8分）證明：如果一棵二叉樹的后序序列是,,…,，中序序列是,,…,，則由序列1,2,…,n可通過一個(gè)棧得到序列,,…,。四、（本題8分）如下圖所示為5個(gè)鄉(xiāng)鎮(zhèn)之間的交通圖，鄉(xiāng)鎮(zhèn)之間道路的長度如圖中邊上所注?，F(xiàn)在要在這5個(gè)鄉(xiāng)鎮(zhèn)中選擇一個(gè)鄉(xiāng)鎮(zhèn)建立一個(gè)消防站，問這個(gè)消防站應(yīng)建在哪個(gè)鄉(xiāng)鎮(zhèn)，才能使離消防站最遠(yuǎn)的鄉(xiāng)鎮(zhèn)到消防站的路程最短。試回答解決上述問題應(yīng)采用什么算法，并寫出應(yīng)用該算法解答上述問題的每一步計(jì)算結(jié)果。圖鄉(xiāng)鎮(zhèn)交通圖五、（本題8分）證明一個(gè)深度為n的AVL樹中的最少結(jié)點(diǎn)數(shù)為：Nn=Fn+2-1(n≥0)其中，F(xiàn)i為Fibonacci數(shù)列的第i項(xiàng)。六、（本題8分）簡單回答有關(guān)AVL樹的問題：（北方名校經(jīng)典試題）（1）在有n個(gè)結(jié)點(diǎn)的AVL樹中，為結(jié)點(diǎn)增加一個(gè)存放結(jié)點(diǎn)高度的數(shù)據(jù)成員，則每一個(gè)結(jié)點(diǎn)需要增加多少個(gè)字位（bit）？（2）若每一個(gè)結(jié)點(diǎn)中的高度計(jì)數(shù)器有8bit，則這樣的AVL樹可以有多少層？最少有多少個(gè)關(guān)鍵碼？七、（本題8分）（1）該散列表的大小m應(yīng)設(shè)計(jì)多大？（2）試為該散列表設(shè)計(jì)相應(yīng)的散列函數(shù)。（3）順次將各個(gè)數(shù)據(jù)散列到表中。（4）計(jì)算查找成功的平均查找次數(shù)。八、（本題8分）已知某電文中共出現(xiàn)了10種不同的字母，每個(gè)字母出現(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)在對(duì)這段電文用三進(jìn)制進(jìn)行編碼（即碼字由0，l，2組成），問電文編碼總長度至少有多少位？請(qǐng)畫出相應(yīng)的圖。九、（本題9分）已知一棵度為m的樹中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，…，Nm個(gè)度為m的結(jié)點(diǎn)。試問該樹中有多少個(gè)葉子結(jié)點(diǎn)？（北方名校經(jīng)典試題）十、（本題15分）試用遞歸法編寫輸出從n個(gè)數(shù)中挑選k個(gè)進(jìn)行排列所得序列的算法。模擬試題（七）參考答案一、單項(xiàng)選擇題（每小題2分，共20分）（1）參考答案：C）（2）【參考答案：B）（3）【分析】在哈夫曼樹的非葉結(jié)點(diǎn)中最多只有1個(gè)結(jié)點(diǎn)的度不為m，設(shè)非葉結(jié)點(diǎn)的個(gè)數(shù)為k，則其中有k-1個(gè)結(jié)點(diǎn)的度為m，設(shè)另1個(gè)結(jié)點(diǎn)的度為u，則2≤u≤m，設(shè)結(jié)點(diǎn)總數(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è)頂點(diǎn)按拓?fù)渑判蛐蛄袨椋簐0,v1,…,vn-1，則對(duì)于鄰接矩陣A，只有當(dāng)i<j時(shí)，才可能有弧<vi,vj>，也就是當(dāng)i>j時(shí)，一定沒有弧<vi,vj>，所以這時(shí)A[i][j]=0，可知鄰接矩陣為三角矩陣。參考答案：C）（5）【分析】設(shè)另一棵子樹的結(jié)點(diǎn)個(gè)數(shù)為n，所以有m=n+k+1，可知n=m-k-l。參考答案：C）（6）【分析】因?yàn)?/p>