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

1、四川大學(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)行的插入、查找、刪除、排序、遍歷等基本運算或操作以及這些運算在各種存儲結(jié)構(gòu)上具體實現(xiàn)的算法。由于本課程的主教材采用C+語言描述算法，期末卷面考試也采用C+語言描述，因而要求在做平時作業(yè)與上機(jī)實驗操作時用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ù)組是一種隨機(jī)存取結(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)程隊、打印機(jī)隊。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á)式、中綴表示。一般掌握

9、的內(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. 向堆中插入

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, ad

11、jlist, 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ù)湫蛄信c拓?fù)?/p>

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

13、數(shù)、散列表、沖突、同義詞、裝填因子等術(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ù)序的比較、最好、最壞、平

15、均情況。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)鍵字文件與其它文件

16、的差別。10. 多重表文件與倒排文件組織方式與特點。11. 多重表文件與倒排文件查詢與更新操作的基本思想。 本章其它內(nèi)容一般掌握第二部分 模擬試卷模擬試題（一）一、單項選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（）A）有向圖 B）隊列 C）線索二叉樹 D）B樹（2）在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點，則執(zhí)行如下（）語句序列。A）p=q; p->next=q; B）p->next=q; q->next=p;C）p->next=q->next; p=q; D）q->next=p->nex

17、t; p->next=q;（3）（）不是隊列的基本運算。A）在隊列第i個元素之后插入一個元素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、

18、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、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)，而及結(jié)點個數(shù)無關(guān)B）用鄰接表法存儲圖，占用的存儲空間大小及圖中邊數(shù)與結(jié)點個數(shù)都有關(guān)C）用鄰接矩陣法存儲圖，占用的存儲空間大小及圖中結(jié)點個數(shù)與邊數(shù)都有關(guān)D）用鄰接矩陣

19、法存儲圖，占用的存儲空間大小只及圖中邊數(shù)有關(guān)，而及結(jié)點個數(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分）已知一個6´5稀疏矩陣如下所示，試：（1）寫出它的三元組線性表；（2）給出三元組線性表的順序存儲表示。三、（本題8分）求網(wǎng)的最小生成樹有哪些算法？它們的時間復(fù)雜度分別下多少，各適用何種情況？四、（每小題4分，共8分）對于如下圖所示的有向

20、圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：（1）從頂點v1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；（2）從頂點v2出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(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>若存儲它采用鄰接表，并且每個頂點

21、鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試給出得到的拓?fù)渑判虻男蛄?。六、（本題8分）對于序列8,18,6,16,29,28，試寫出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹的先序、中序與后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： 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

22、,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)，此算

23、法適用于邊較多的稠密圖，也可使用Kruskal算法，時間復(fù)雜度為O(eloge)，此算法適用于邊較少的稀疏圖。四、（每小題4分，共8分）（1）DFS：v1 v2 v3 v4 v5 （2）BFS：v2 v3 v4 v5 v1 五、（本題8分）拓?fù)渑判驗椋?4 3 6 5 7 2 1六、（本題8分）所構(gòu)造的堆如下圖所示：七、（本題8分）在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。八、（每小題2分，共8分）（1）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23九、（

24、本題9分）哈希表如下圖所示：十、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。C+語言版測試程序見exam110c+，具體算當(dāng)如下：template <class Entry>void display_BT_with_tree_shape(const Binary_tree<Entry> &T)aux_display_BT_with_tree_shape<Entry>(T.ge

25、t_root();template <class Entry>void aux_display_BT_with_tree_shape(Binary_node<Entry> *sub_root,int level = 1)/按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1if(sub_root != NULL)/空樹不顯式，只顯式非空樹aux_display_BT_with_tree_shape<Entry>(sub_root->right,level+1);/顯示右子樹cout<<endl;/顯示新行for(int i=0;

26、i<level-1;i+)cout<<" "/確保在第level列顯示結(jié)點cout<<sub_root->data;/顯示結(jié)點aux_display_BT_with_tree_shape<Entry>(sub_root->left,level+1);/顯示左子樹C語言版測試程序見exam110c，具體算當(dāng)如下：void DisplayBTWithTreeShape(BiTree T,int level=1)/按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1if(T)/空樹不顯式，只顯式非空樹Display

27、BTWithTreeShape(T->rchild,level+1);/顯示右子樹cout<<endl;/顯示新行for(int i=0;i<level-1;i+)cout<<" "/確保在第level列顯示結(jié)點cout<<T->data;/顯示結(jié)點DisplayBTWithTreeShape(T->lchild,level+1);/顯示左子樹模擬試題（二）一、單項選擇題（每小題 2 分，共20分）（1）設(shè)Huffman樹的葉子結(jié)點數(shù)為m，則結(jié)點總數(shù)為（）。A）2m B）2m-1C）2m+1 D）m+1（2）若順序

28、存儲的循環(huán)隊列的QueueMaxSize=n，則該隊列最多可存儲（）個元素。A）n B）n-1 C）n+1 D）不確定（3）下述哪一條是順序存儲方式的優(yōu)點？（）A）存儲密度大 B）插入與刪除運算方便 C）獲取符合某種條件的元素方便 D）查找運算速度快（4）設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在600(10)，A33存放位置在678(10)，每個元素占一個空間，問A23(10)存放在什么位置？（腳注(10)表示用10進(jìn)制表示，m>3）（）。A）658 B）648 C）633 D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（）。A）若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則

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

30、存儲，并且按關(guān)鍵碼值的檢索頻率排好序（8）對n個記錄進(jìn)行堆排序，所需要的輔助存儲空間為（）。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ù)，則散列地址為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分）假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別

31、寫出對它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。三、（每小題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分）設(shè)有數(shù)組A-1:3,0:6,-2:3，按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5，試計算出A1,1,1的存儲位置。六、（本題8分）試列出如下圖中全部可能的拓?fù)渑判蛐蛄?。七、（本題8分）已知哈希表地址空間為0.8，哈希函數(shù)為H(key)=ke

32、y%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*f)的二叉樹表示，并寫出此表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示。十、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸算法。模擬試題（二）參考答案一、單項選擇題（每小題 2 分，共20分）（1）B（2）B（3

33、）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)槎鏄浜蟮南刃虮闅v及中序遍歷方法。五、（本題8分）A1,1,1的存儲位置=2000+(1-(-1)*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(

34、1-(-2)*5=2465。六、（本題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分）本題只

35、要在遍歷二叉樹的過程序中對葉子結(jié)點進(jìn)行記數(shù)即可。C+語言版測試程序見exam210c+，具體算當(dāng)如下：template <class Entry>long leaf_count(const Binary_tree<Entry> &T)/計算二叉樹中葉子結(jié)點數(shù)目return aux_leaf_count<Entry>(T.get_root();template <class Entry>long aux_leaf_count(Binary_node<Entry> *sub_root)/按樹狀形式顯示二叉樹，level為層次數(shù)，可

36、設(shè)根結(jié)點的層次數(shù)為1if(sub_root=NULL)return 0;/空樹返回0else if(sub_root->left=NULL&&sub_root->right=NULL)return 1;/只有一個結(jié)點的樹返回1else/葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之與return aux_leaf_count(sub_root->left)+aux_leaf_count(sub_root->right);C語言版測試程序見exam210c，具體算當(dāng)如下：long LeafCount(BiTree T)/計算二叉樹中葉子結(jié)點數(shù)目if(T=NULL)re

37、turn 0;/空樹返回0else if(T->lchild=NULL&&T->rchild=NULL)return 1;/只有一個結(jié)點的樹返回1else/葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之與return LeafCount(T->lchild)+LeafCount(T->rchild);模擬試題（三）一、單項選擇題（每小題 2 分，共20分）（1）對一個算法的評價，不包括如下（）方面的內(nèi)容。A）健壯性與可讀性 B）并行性 C）正確性 D）時空復(fù)雜度（2）在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（）。A）p->next

38、=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)當(dāng)采用鏈表表示？（）A）經(jīng)常需要隨機(jī)地存取元素 B）經(jīng)常需要進(jìn)行插入與刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲空間D）表中元素的個數(shù)不變（4）一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（）。A）2 3 1B）3 2 1C）3 1 2 D）1 2 3（5）每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是（）。A）冒泡排序B）簡單選擇排序C）希

39、爾排序D）直接插入排序（6）采用開放定址法處理散列表的沖突時，其平均查找長度（）。A）低于鏈接法處理沖突 B）高于鏈接法處理沖突C）及鏈接法處理沖突相同 D）高于二分查找（7）若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（）參數(shù)。A）值 B）函數(shù) C）指針 D）引用（8）在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（）。A）行號 B）列號 C）元素值 D）非零元素個數(shù)（9）快速排序在最壞情況下的時間復(fù)雜度為（）。A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2)（10）從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（）。A）O(n) B）O

40、(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）表示事件，弧上表示活動的天數(shù)）。（1）找出所有的關(guān)鍵路徑。（2）v3事件的最早開始時間

41、是多少。五、（本題8分）如果在1000000個記錄中找出兩個最小的記錄，你認(rèn)為采用什么樣的排序方法所需的關(guān)鍵字比較次數(shù)最少？最多比較多少次？六、（本題8分）假設(shè)把n個元素的序列（a1,a2,an）滿足條件ak<maxat|1tk的元素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,2

42、5,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)=key MOD 13，哈希地址空間為012，請構(gòu)造用鏈地址法處理沖突的哈希表，并求平均查找長度。九、（本題9分）已知關(guān)鍵字序列23，13，5，28，14，25，試構(gòu)造二叉排序樹。十、（本題15分）編寫一個算法求二又樹的深度。模擬試題（三）參考答案一、單項選擇題（每小題 2 分，共20分）（1）B （2）A （3）

43、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)鍵路徑有：v1v2v3v5v6，以及v1v4v6。（2）v3事件的最早開始時間是13。五、（本題8分）采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)=999999+=1000019次。六、（本題8分）不對，例如序列3、3、4、2、l的“逆序元素”個數(shù)是2，2與1是“逆序元素”

44、；但是將第二個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分）（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

45、,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+語言版測試程序見exam310c+，具體算當(dāng)如下：template <class Entry>int bitree_depth(const Binary_tree<Entry&g

46、t; &T)/求二叉樹的深度return aux_bitree_depth(T.get_root();template <class Entry>int aux_bitree_depth(Binary_node<Entry> *sub_root)/求二叉樹的深度if(sub_root=NULL)return 0;/空二叉樹的深度為0elseint d_lsub,d_rsub;d_lsub=aux_bitree_depth(sub_root->left);/左子樹的深度d_rsub=aux_bitree_depth(sub_root->right);/

47、右子樹的深度/返回左右子樹的深度最大值加1 return (d_lsub>d_rsub)?d_lsub:d_rsub)+1;C語言版測試程序見exam310c，具體算當(dāng)如下：int BiTreeDepth(BiTree T)/求二叉樹的深度if(T=NULL)return 0;/空二叉樹的深度為0elseint d_lsub,d_rsub;d_lsub=BiTreeDepth(T->lchild);/左子樹的深度d_rsub=BiTreeDepth(T->rchild);/右子樹的深度/返回左右子樹的深度最大值加1 return (d_lsub>d_rsub)?d_ls

48、ub:d_rsub)+1;模擬試題（四）一、單項選擇題（每小題 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依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個不同的字符串？A）15 B）14 C）16

49、 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、

50、C、F、B、D D）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，1

51、9，32，43，38，6，13，22，請寫出快速排序第一趟的結(jié)果；堆排序時所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時間復(fù)雜度最差？五、（本題8分）設(shè)二維數(shù)組A0:10,-5:0，按行優(yōu)先順序存儲，每個元素占4個單元，A0-5的存儲地址為1000，則A9-2的存儲地址為多少？六、（本題8分）用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點序列。七、（本題8分）請說明對一棵二叉樹進(jìn)行前序、中序與后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？八、（本題8分）對于如下圖所示的G，用Kruskal算法構(gòu)造

52、最小生成樹，要求圖示出每一步的變化情況。九、（本題9分）已知一棵二叉樹的先序序列及中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI十、（本題15分）已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為T，請寫出遞歸算法，從小到大輸出該二叉排序樹中所有關(guān)鍵字值K的結(jié)點的關(guān)鍵字的值。模擬試題（四）參考答案一、單項選擇題（每小題 2 分，共20分）（1）B （2）C （3）A （4）B （5）B （6）C （7）A （8）C （9）C （10）B二、（本題8分）三種方法對查找的要求分別如下：l 順序查找法：表中元素可以任意存放；l 折半查找法：表中元素必須

53、以關(guān)鍵字的大小遞增或遞減的次序存放：l 分塊查找法：表中元素每塊內(nèi)的元素可任意存放，但塊及塊之間必須以關(guān)鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大于（或?。┖笠粔K內(nèi)任何元素的關(guān)鍵字。三種方法的平均查找長度分別如下：l 順序查找法：查找成功的平均查找長度為；l 折半查找法：查找成功的平均查找長度為log2(n+1)+1；l 分塊查找法：若用順序查找確定所在的塊，平均查找長度為；若用折半確定所在塊，平均查找長度為。三、（本題8分）如下圖所示：四、（本題8分）快速排序的第一趟結(jié)果為22,19,13,6,24,38,43,12；堆排序時所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是O(1)，快速排序是O(logn)，可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時間：堆是O(nlogn)，快速排序是O(n2)，所以，可見快速排序時間復(fù)雜度最差。U 注意：快速排序的平均時排序速度最快，但在最壞情況下不一定比其他排序方法快。五、（本題8分）依題意A的起始