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

1、四川大學(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ù)進(jìn)行的插入、查找、刪除、排序、遍歷等基本運算或操作以及這些運算在各種存儲結(jié)構(gòu)上具體實現(xiàn)的算法。由于本課程的主教材采用C+語言描述算法，期末卷面考試也采用C+語言描述，因而要求在做平時作業(yè)和上機實驗操作時用C+開發(fā)工具（如：Visual C+或 C+ Builder或Borland C+）。下面按照主教材中各章次序給出每章的具體復(fù)習(xí)要求，以便同學(xué)們更好地進(jìn)行

2、期末復(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. 一個簡單算法的最好、最差和平均這三種情況的時

3、間復(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)鏈表

4、、雙向鏈表的結(jié)構(gòu)特點。7. 線性表的每一種運算在單鏈表上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。8. 在順序存儲或鏈接存儲的線性表上實現(xiàn)指定功能的算法的分析和設(shè)計。9Josephus問題的求解過程。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. 稀疏矩陣的順序存儲、帶行指針向量的鏈接存

5、儲，在每一種存儲中非零元素結(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ù)雜度

6、。4. 棧的每一種運算在鏈接存儲結(jié)構(gòu)上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。5. 算術(shù)表達(dá)式的中綴表示和后綴表示，以及相互轉(zhuǎn)換的規(guī)則，后綴表達(dá)式求值的方法。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隊、進(jìn)程隊、打印機隊。13鏈隊的各

7、種存儲表示。一般掌握的內(nèi)容：1. 后綴表達(dá)式求值的算法，把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法。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é)點的度

8、、樹的度、樹葉、分枝結(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ù)表達(dá)式的二叉樹表示及逆波蘭表達(dá)式、中綴表示。一般掌握的內(nèi)

9、容：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. 向堆中插入元素的過

10、程、算法描述及時間復(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,

11、 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個頂點，e條邊的無向圖是一個森林（ne），則該森林中必有多少棵樹。）、深度優(yōu)先生成樹和廣度優(yōu)先生成樹、生成樹的權(quán)、最小生成樹等的定義。9.根據(jù)普里姆算法求圖的最小生成樹的過程。10根據(jù)克魯斯卡爾算法求圖的最小生成樹的過程。11. 圖的拓?fù)湫蛄泻屯負(fù)渑判虻母拍?，求圖

12、的拓?fù)湫蛄械姆椒ǎ瑢τ绵徑颖肀硎镜膱D進(jìn)行拓?fù)渑判虻倪^程。12強連通圖的最少邊數(shù)。一般掌握的內(nèi)容：1根據(jù)普里姆算法求圖的最小生成樹的算法描述。2根據(jù)克魯斯卡爾算法求圖的最小生成樹的算法描述。3. 對用鄰接表表示的圖進(jìn)行拓?fù)渑判虻暮退惴枋?。對本章的其余?nèi)容均作一般了解。第八章 查找重點掌握的內(nèi)容：1. 在一維數(shù)組及單鏈表上進(jìn)行順序查找的過程、算法、成功及不成功的平均查找長度和時間復(fù)雜度。2. 在一維數(shù)組上進(jìn)行二分查找的過程、遞歸和非遞歸算法、平均查找長度和時間復(fù)雜度，二分查找一個給定值元素的查找長度（即查找路徑上的元素數(shù)），二分查找對應(yīng)的判定樹的性質(zhì)。3. 散列存儲的概念，散列函數(shù)、散列表、沖突

13、、同義詞、裝填因子等術(shù)語的含義。4. 利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。5. 利用開放定址法中的線性探查法處理沖突進(jìn)行散列存儲和查找的過程，利用鏈接法處理沖突進(jìn)行散列存儲和查找的過程。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)容均作一般了解。第九章

14、排序重點掌握的內(nèi)容：1. 直接插入、直接選擇和冒泡排序的方法，排序過程及時間復(fù)雜度。2. 在堆排序中建立初始堆的過程和利用堆排序的過程，對一個分支結(jié)點進(jìn)行篩運算的過程、算法及時間復(fù)雜度，整個堆排序的算法描述及時間復(fù)雜度。3. 快速排序的方法，對一組數(shù)據(jù)的排序過程，對應(yīng)的二叉搜索樹，快速排序過程中劃分的層數(shù)和遞歸排序區(qū)間的個數(shù)。4. 遞歸排序的遞歸算法，它在平均情況下的時間和空間復(fù)雜度，在最壞情況下的時間和空間復(fù)雜度。5. 二路歸并排序的方法和對數(shù)據(jù)的排序過程，每趟排序前、后的有序表長度，二路歸并排序的趟數(shù)、時間復(fù)雜度和空間復(fù)雜度。6各種排序方法的不同數(shù)據(jù)序的比較、最好、最壞、平均情況。7哪些排

15、序不受初始數(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.

16、多重表文件和倒排文件組織方式和特點。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-next; p=q; D）q-next=p-next; p-next=q;（3）（）不是隊列的基本運算。A）在隊列第i個元

17、素之后插入一個元素B）從隊頭刪除一個元素C）判斷一個隊列是否為空 D）讀取隊頭元素的值（4）字符A、B、C依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個不同的字符串。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

18、）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、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)鍵字

19、序列(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, zC）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分）對于如下圖所示的有向圖采用鄰接表存

20、儲結(jié)構(gòu)，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：（1）從頂點v1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的頂點序列；（2）從頂點v2出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的頂點序列。五、（本題8分）已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7;E=,;若采用鄰接表存儲結(jié)構(gòu)，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試給出得到的拓?fù)渑判虻男蛄校ㄈ攵葹榱愕捻旤c可采用棧或隊列來進(jìn)行存儲）。六、（本題8分）對于序列8,18,6,16,29,28，試寫出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示

21、出來。試求出空格處的內(nèi)容。先序序列： aB dF kICEH jG中序序列：D bKFIA hEJC g后序序列： K FBHJ G A八、（每小題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)，試編寫算法按如下圖所示的樹狀顯示二叉樹。模擬試

22、題（一）參考答案一、單項選擇題（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：v1 v2 v3 v4 v5（2）BFS：v2 v3 v4 v5 v1五、（本題8分）用棧存儲

23、入度為零的頂點得到的拓?fù)渑判驗椋?4 3 6 5 7 2 1用隊列存儲入度為零的頂點得到的拓?fù)渑判驗椋?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é)點，從上至

24、下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。具體算法實現(xiàn)如下：/ 文件路徑名:exam1alg.hss ElemTypevoid DisplayHelp(BinTreeNode *r, int level)/ 操作結(jié)果：按樹狀形式顯示以r為根的二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1if(r != NULL)/ 空樹不顯式，只顯式非空樹DisplayHelp(r-rightChild, level + 1);/ 顯示右子樹cout endl;/ 顯示新行for(int i = 0; i level - 1; i+)cout

25、;/ 確保在第level列顯示結(jié)點cout data;/ 顯示結(jié)點DisplayHelp(r-leftChild, level + 1);/ 顯示左子樹template void Display(const BinaryTree&bt)/ 操作結(jié)果：樹狀形式顯示二叉樹DisplayHelp(bt.GetRoot(), 1);/ 樹狀顯示以bt.GetRoot()為根的二叉樹cout 3）（D）。A）658 B）648 C）633 D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（A）。A）若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點B）若一個結(jié)點是某

26、二叉樹的前序遍歷最后一個結(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）對線性表進(jìn)行二分法查找，其前提條件是（）。A）線性表以鏈接方式存儲，并且按關(guān)鍵字值排好序B）線性表以順序方式存儲，并且按關(guān)鍵字值的檢索頻率排好序C）線性表以順序方式存儲，并且按關(guān)鍵字值排好序D）線性表以鏈接方式存儲，并且按關(guān)鍵字值的檢索頻率排好序（8）對n個記錄進(jìn)行

27、堆排序，所需要的輔助存儲空間為（C）。A）O(1og2n) B）O(n) C）O(1) D）O(n2)（9）對于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲時，若選用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第二個出棧的次

28、序有哪幾個？三、（每小題4分，共8分）已知一個無向圖的頂點集為a, b, c, d, e，其鄰接矩陣如下所示：（1）畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。四、（本題8分）樹有哪些遍歷方法？它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？五、（本題8分）將關(guān)鍵字序列（7、8、11、18、9、14, 30）散列存儲到散列列表中，散列表的存儲空間是一個下標(biāo)從0開始的一個一維數(shù)組，散列函數(shù)為：H(key)=（key * 3）% m（m為表長），處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7，請畫出所構(gòu)造的散列表；計算查找成功的平均查找

29、長度。六、（本題8分）試列出如下圖中全部可能的拓?fù)渑判蛐蛄?。七、（本題8分）請說明對一棵二叉樹進(jìn)行按照先遍左子樹，后右子樹的方式進(jìn)行前序、中序和后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？八、（本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。九、（本題9分）試畫出表達(dá)式(a+b/c)*(d-e*f)的二叉樹表示，并寫出此表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示。十、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸算法。模擬試題（二）參考答案一、單項選擇題（每小題 2 分，

30、共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 和CDBEA 3種。三、（每小題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)造的散列表為：下標(biāo)0123456789關(guān)

31、鍵字3071411818.9.比較次數(shù)1111121H（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分）全部可能的拓?fù)渑判蛐蛄袨椋?523634、152634、156234、561234、516234、512634、512364七、（本題8分）二叉樹任兩個中葉結(jié)點必在某結(jié)點的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹

32、在前、右子樹在后的順序進(jìn)行遍歷的。所以在三種遍歷序列中葉結(jié)點的相對次序是不會發(fā)生改變的。八、（本題8分）九、（本題9分）表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達(dá)式的二叉樹表示的前序遍歷、中序遍歷及后序遍歷序列。二叉樹表示如下圖所示：(a+b/c)*(d-e*f)波蘭式表示(前序遍歷)：*+a/bc-d*ef中綴表示：a+b/c*d-e*f逆波蘭式表示：abc/+def*-*十、（本題15分）本題只要在遍歷二叉樹的過程序中對葉子結(jié)點進(jìn)行記數(shù)即可。具體算法實現(xiàn)如下：/ 文件路徑名:exam2alg.htemplate long LeafCountHelp(BinTreeNode *r

33、)/ 操作結(jié)果：按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1if (r = NULL)/ 空二叉樹return 0;/ 空樹返回0else if (r-leftChild = NULL & r-rightChild = NULL)/ 只有一個結(jié)點的樹return 1;/ 只有一個結(jié)點的樹返回1else/ 其他情況, 葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之和return LeafCountHelp(r-leftChild) + LeafCountHelp(r-rightChild);template long LeafCount(const BinaryTree&bt)/ 操作結(jié)

34、果：計算二叉樹中葉子結(jié)點數(shù)目return LeafCountHelp(bt.GetRoot();/ 調(diào)用輔助函數(shù)實現(xiàn)計算二叉樹中葉子結(jié)點數(shù)目模擬試題（三）一、單項選擇題（每小題 2 分，共20分）（1）對一組數(shù)據(jù)（2，12，16，88，5，10）進(jìn)行排序，若前三趟排序結(jié)果如下第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序方法可能是（ A ）。A）起泡排序 B）希爾排序 C）歸并排序 D）基數(shù)排序（2）在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（A）。A）p-next=HL-next; H

35、L-next=p B）p-next=HL; HL=pC）p-next=HL; p=HL D）HL=p; p-next=HL（3）對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（B）A）經(jīng)常需要隨機地存取元素 B）經(jīng)常需要進(jìn)行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲空間D）表中元素的個數(shù)不變（4）一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（C）。A）2 3 1B）3 2 1C）3 1 2 D）1 2 3（5）每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是（B）。A）冒泡排序B）簡單選擇排序C）希爾排序D）直接插入排序（6）采用開放定址法處理散列表的沖

36、突時，其平均查找長度（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 先進(jìn)先出 ）。A）棧 B）隊列 C）樹 D）圖? 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（A）。A）行號 B）列號 C）元素值 D）非零元素個數(shù)（9）快速排序在最壞情況下的

37、時間復(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分）請畫出如下圖所示的鄰接

38、矩陣和鄰接表。四、（每小題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）滿足條件akaj(ij)，試問，當(dāng)ai與aj相互交換后，該序列中逆序元素的個數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。七、（本題8分）帶權(quán)圖（權(quán)值非負(fù)，

39、表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標(biāo)頂點之間的一條最短路徑。假定從初始頂點到目標(biāo)頂點之間存在路徑，現(xiàn)有一種解決該問題的方法：設(shè)最短路徑初始時僅包含初始頂點，令當(dāng)前頂點u為初始頂點；選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當(dāng)前頂點u=v；重復(fù)步驟，直到u是目標(biāo)頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。八、（本題8分）已知一組關(guān)鍵字為（19,14,23,1,68,20,84,27,55,11,10,79），哈希函數(shù)：H(key)=key MOD 13，哈希地址空間為012，請構(gòu)造用鏈地址法處理沖突的哈希

40、表，并求平均查找長度。九、（本題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)鍵路徑有：v1v2v3v5v6，以及v1v4v6。

41、（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)圖，如果按照

42、題中的原則，從A到C的最短路徑為ABC，事實上其最短路徑為 ADC。八、（本題8分）用鏈地址法處理沖突的哈希表如下圖所示：ASL=(1*6+2*4+3*1+4*1)=1.75九、（本題9分）構(gòu)造二叉排序樹的過程如下圖所示。構(gòu)造的二叉排序樹如下圖所示：十、（本題15分）若二叉樹為空，深度為0；若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。具體算法實現(xiàn)如下：/ 文件路徑名:exam3alg.htemplate int DepthHelp(BinTreeNode *r)/ 操作結(jié)果：求二叉樹的深度if (r = NULL)/ 空二叉樹return 0;/ 空二叉樹

43、的深度為0else/ 非空二叉樹int lDepth = DepthHelp(r-leftChild);/ 左子樹的深度int rDepth = DepthHelp(r-rightChild);/ 右子樹的深度return (lDepth rDepth) ? lDepth : rDepth) + 1;/ 返回左右子樹的深度最大值加1template int Depth(BinaryTree&bt)/ 操作結(jié)果：求二叉樹的深度return DepthHelp(bt.GetRoot();/ 調(diào)用輔助函數(shù)求二叉樹的深度模擬試題（四）一、單項選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個

44、是線性結(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依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個不同的字符串？A）15 B）14 C）16 D）21（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A）11 B）37

45、 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, 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, 8