數(shù)據(jù)結(jié)構(gòu)四川大學(xué)期終復(fù)習(xí)試題+答案

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ā)工具（如：VisualC+或C+Builder或BorlandC+）。下面按照主教材中各章次序給出每章的具體復(fù)習(xí)要求，以便同學(xué)們更好地進(jìn)行期末復(fù)習(xí)。第

2、一章緒論重點掌握的內(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 .一個簡單算法的最好、最差和平均這三種情況的時間復(fù)雜度的計算

3、。對于本章的其余內(nèi)容均作一般掌握。第二章線性表重點掌握的內(nèi)容：1 .線性表的定義及判別和抽象數(shù)據(jù)類型的描述，線性表中每一種操作的功能，對應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個參數(shù)的作用。2 .線性表的順序存儲結(jié)本的類型定義，即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é)

4、構(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 .特殊矩陣（包括對角矩陣）和壓縮存儲的下標(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)的時

6、間復(fù)雜度。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)程隊、打印

7、機隊。13 .鏈隊的各種存儲表示。一般掌握的內(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 .樹

8、和二叉樹的概念，如結(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ù)表達(dá)式的二叉樹表示

9、及逆波蘭表達(dá)式、中綴表示。一般掌握的內(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)，小根堆和大根堆的異同及堆的

10、判別、建立堆的過程。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 .存儲圖使用的v

11、exlist,adjmatrix,adjlist,edgenode,edgeset,edge等類型的定義及用途。5 .圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過程。6 .對分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行深度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時間復(fù)雜度。7 .對分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行廣度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時間復(fù)雜度。8 .圖的生成樹（若一個具有n個頂點，e條邊的無向圖是一個森林（ne）,則該森林中必有多少棵樹。）、深度優(yōu)先生成樹和廣度優(yōu)先生成樹、生成樹的權(quán)、最小生成樹等的定義。9 .根據(jù)普里姆算法求圖的最小生成樹的過程。10 .根據(jù)克魯斯卡爾算法求圖的最小生成

12、樹的過程。11 .圖的拓?fù)湫蛄泻屯負(fù)渑判虻母拍睿髨D的拓?fù)湫蛄械姆椒?，對用鄰接表表示的圖進(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ù)），二分查找對

13、應(yīng)的判定樹的性質(zhì)。3 .散列存儲的概念，散列函數(shù)、散列表、沖突、同義詞、裝填因子等術(shù)語的含義。4 .利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。5 .利用開放定址法中的線性探查法處理沖突進(jìn)行散列存儲和查找的過程，利用鏈接法處理沖突進(jìn)行散列存儲和查找的過程。6 .根據(jù)除留余數(shù)法構(gòu)造散列函數(shù)，采用線性探查法或鏈接法處理沖突，把一組數(shù)據(jù)散列存儲到散列表中，計算出一個給定值元素的查找長度和查找所有元素的平均查找長度。7 .B_樹中每個結(jié)點的結(jié)構(gòu)，樹根結(jié)點或非樹根結(jié)點中關(guān)鍵字的個數(shù)范圍和子樹的個數(shù)范圍，B的結(jié)構(gòu)特性，從B_M上查找一個給定值元素的過程。一般掌握的內(nèi)容：1 .B_樹查找算法。2 .向B

14、_M中插入元素的過程。對本章的其余內(nèi)容均作一般了解。第九章排序重點掌握的內(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 .

15、各種排序方法的不同數(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文件和VSAMd）的組織方式和特點。6 .在ISAM文件和VSA帔件上查找和更新操作的基本思想。7 .散列文件的組織方式和特點。8 .散列文件的查詢和更

16、新操作的基本思想。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中，若要在當(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)()不

17、是隊列的基本運算。A)在隊列第i個元素之后插入一個元素B)從隊頭刪除一個元素C)判斷一個隊列是否為空D)讀取隊頭元素的值(4)字符A、B、C依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成()個不同的字符串。A)14B)5C)6D)8(5)由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A)11以下6-8題基于下圖:B)35C)19D)53)。B)E、A、G、D)E、G、A、)。B)E、A、G、D)B、D、C、)。B)E、A、C、D)E、G、A、)。C、F、B、DC、D、F、BC、F、B、DA、F、G、EB、D、G、FC、D、F、B(6)該二叉樹結(jié)點的前

18、序遍歷的序列為(A)E、G、F、A、C、D、BC)E、A、C、B、D、G、F(7)該二叉樹結(jié)點的中序遍歷的序列為(A)A、B、C、D、E、G、FC)E、A、C、B、D、G、F(8)該二叉樹的按層遍歷的序列為(A)E、G、F、A、C、D、BC)E、A、G、C、F、B、D(9)下面關(guān)于圖的存儲的敘述中正確的是(A)用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)B)用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)C)用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)D)用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)(10)

19、設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h),下面哪一個序列是從上述序列出發(fā)建堆的結(jié)果？()A)a,g,h,m,n,p,q,x,zB)a,g,m,h,q,n,p,x,zC)g,m,q,a,n,p,x,h,zD)h,g,m,p,a,n,q,x,z二、（每小題4分，共8分）已知一個6x5稀疏矩陣如下所示，試：00001-000000/0000000_25000000700一（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=,;若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試給出得到的拓?fù)渑判虻男蛄?。六、（本題8分）對于序列8,18,6,16,29,28,試寫出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二

21、叉樹。先序序列：_B_F_ICEH_G中序序列：D_KFIA_EJC_后序序列：K_FBHJ_GA八、（每小題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

22、)D(3)A(4)B(5)B(6)CA(8)C(9)B(10)B二、(每小題4分，共8分)(1)(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)(2)三元組線性表的順序存儲表示如下所示：655-1 513 2口4 5-25 15：271三、(本題8分)求網(wǎng)的最小生成樹可使用Prim算法，時間復(fù)雜度為O(n2),此算法適用于邊較多的稠密圖，也可使用Kruskal算法，時間復(fù)雜度為O(eloge),此算法適用于邊較少的稀疏圖。四、(每小題4分，共8分)(1) DFS:v1v2v3v4v5(2) BFS:v2v3v4v5v1五、(本題8分)拓?fù)渑判驗椋?365721

23、六、(本題8分)所構(gòu)造的堆如下圖所示：16L1&七、（本題8分）在先序序列空格中依次填A(yù)DKJ,八、（每小題2分，共8分）中序中依次填BHG,后序中依次填DIEC。(1)二叉排序樹如下圖所示:(2)哈夫曼樹如下圖所示:(3)28,80,27,24,23（4）九、（本題9分）哈希表如下圖所示:十、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。C+語言版測試程序見exam110c+,具體算當(dāng)如下：templatevoiddi

24、splay_BT_with_tree_shape(constBinary_tree&T)(aux_display_BT_with_tree_shape(T.get_root();templatevoidaux_display_BT_with_tree_shape(Binary_node*sub_root,intlevel=1)/按旋狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)e1if(sub_root!=NULL)/空樹不顯式，只顯式非空樹aux_display_BT_with_tree_shape(sub_root-right,level+1);焜示右子樹coutendl;顯示新

25、行for(inti=0;ilevel-1;i+)cout”;/確保在第level列顯示結(jié)點coutdata;顯示結(jié)點aux_display_BT_with_tree_shape(sub_root-left,level+1);展示左子樹)C語言版測試程序見exam110G具體算當(dāng)如下:voidDisplayBTWithTreeShape(BiTreeT,intlevel=1)/按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1if(T)空樹不顯式，只顯式非空樹顯示右子樹顯示新行確保在第level列顯示結(jié)點顯示結(jié)點顯示左子樹DisplayBTWithTreeShape(T-rchil

26、d,level+1);coutendl;for(inti=0;ilevel-1;i+)cout”;coutdata;DisplayBTWithTreeShape(T-lchild,level+1);)模擬試題(二)-、單項選擇題(每小題2分，共20分)(1)設(shè)Huffman樹的葉子結(jié)點數(shù)為m,則結(jié)點總數(shù)為()。A)2mB)2m-1C)2m+1D)m+1(2)若順序存儲的循環(huán)隊列的QueueMaxSize=n則該隊列最多可存儲()個元素。A)nB)n-1C)n+1D)不確定(3)下述哪一條是順序存儲方式的優(yōu)點？()A)存儲密度大B)插入和刪除運算方便C)獲取符合某種條件的元素方便D)查找運算速度

27、快(4)設(shè)有一個二維數(shù)組Amn,假設(shè)A00存放位置在60Qi0),A33存放位置在67&10方每個元素占一個空間，問A23(io需放在什么位置？(腳注(10表示用10進(jìn)制表示,m3)()。A)658B)648C)633D)653(5)下列關(guān)于二叉樹遍歷的敘述中，正確的是()。A)若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點B)若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序遍歷的最后一個結(jié)點C)若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序最后一個結(jié)點D)若一個樹葉是某二叉樹的前序最后一個結(jié)點，則它必是該二叉樹的中

28、序遍歷最后一個結(jié)點(6)k層二叉樹的結(jié)點總數(shù)最多為()。A)2k-1B)2k+1C)2K-1D)2k-1(7)對線性表進(jìn)行二分法查找，其前提條件是()。A)線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序B)線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C)線性表以順序方式存儲，并且按關(guān)鍵碼值排好序D)線性表以鏈接方式存儲，并且按關(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

29、的元素有()個。A)1B)2C)3D)4(10)下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是()。A)數(shù)組是不同類型值的集合B)遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C)樹是一種線性結(jié)構(gòu)D)用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法二、(本題8分)假定一棵二叉樹廣義表表示為a(b(c),d(e,f),分別寫出對它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。三、(每小題4分，共8分)已知一個無向圖的頂點集為a,b,c,d,e,其鄰接矩陣如下所示：0100110010000110110110110（1）畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。四、

30、（本題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）=key%7,采用線性探測再散列處理沖突，將數(shù)據(jù)序列100,20,21,35,3,78,99,45依次存入此哈希表中，列出插入時的比較次數(shù)，并求出在等概率下的平均查找長度。八、（本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是46,25,78,62,12,80）,試畫出從

31、空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。九、（本題9分）試畫出表達(dá)式（a+b/c）*（d-e*f）的二叉樹表示，并寫出此表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示。十、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸算法。模擬試題（二）參考答案、單項選擇題（每小題2分，共20分）(1)B(2)B(6)AC(3)A(8)C(4)D(5)A(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)先遍歷序列為：

32、abdce；廣度優(yōu)先遍歷序列為：abedc四、(本題8分)樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄浜蟮南刃虮闅v與中序遍歷方法。五、(本題8分)A1,1,1W儲位置=2000+(1-(-1)*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)*5=2465六、(本題8分)全部可能的拓?fù)渑判蛐蛄袨椋?523634、152634、156234、561234、516234、512634、512364七、(本題8分)哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示：哈希地址o1234567S關(guān)鍵字2135100378992025比較次數(shù)121145

33、151ASL=，(4X1+1X2+1X4+2X5)=2.58八、(本題8分)(bf(c(d)(a)(fJ九、(本題9分)表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達(dá)式的二叉樹表示的前序遍歷、中序遍歷及后序遍歷序列。二叉樹表示如下圖所示：波蘭式表示：*+a/bc-d*ef中綴表示：a+b/c*d-e*f逆波蘭式表示：abc/+def*-*十、(本題15分)本題只要在遍歷二叉樹的過程序中對葉子結(jié)點進(jìn)行記數(shù)即可。C+語言版測試程序見exam210c+,具體算當(dāng)如下：templatelongleaf_count(constBinary_tree&T)/計算二叉樹中葉子結(jié)點數(shù)目returnau

34、x_leaf_count(T.get_root();templatelongaux_leaf_count(Binary_node*sub_root)/按扇狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1if(sub_root=NULL)return0;空樹返回0elseif(sub_root-left=NULL&sub_root-right=NULL)return1;只有一個結(jié)點的樹返回1else/葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之和returnaux_leaf_count(sub_root-left)+aux_leaf_count(sub_root-right);C語言版測試程序

35、見exam210G具體算當(dāng)如下：longLeafCount(BiTreeT)/計算二叉樹中葉子結(jié)點數(shù)目if(T=NULL)return0;/座樹返回0elseif(T-lchild=NULL&T-rchild=NULL)return1;只有一個結(jié)點的樹返回1else/葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點數(shù)之和returnLeafCount(T-lchild)+LeafCount(T-rchild);模擬試題(三)一、單項選擇題(每小題2分，共20分)(1)對一個算法的評價，不包括如下()方面的內(nèi)容。A)健壯性和可讀性B)并行性C)正確性D)時空復(fù)雜度(2)在帶有頭結(jié)點的單鏈表HL中,要向表頭插入一個

36、由指針p指向的結(jié)點，則執(zhí)行()。A)p-next=HL-next;HL-next=pB)p-next=HL;HL=pC)p-next=HL;p=HLD)HL=p;p-next=HL(3)對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？()A)經(jīng)常需要隨機地存取元素B)經(jīng)常需要進(jìn)行插入和刪除操作C)表中元素需要占據(jù)一片連續(xù)的存儲空間D)表中元素的個數(shù)不變(4) 一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是()。A)231B)321C)312D)123(5)每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是()。A)冒泡排序B)簡單選擇排序C)希爾排序D)直接插入排序(6

37、)采用開放定址法處理散列表的沖突時，其平均查找長度()。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(1)C)O(log2n)D)O(n2)二、(本題8

38、分)已知一個圖的頂點集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事件的最早開始時間是多少。五、(本題8分)如果在1000000個記錄中找出兩個

39、最小的記錄，你認(rèn)為采用什么樣的排序方法所需的關(guān)鍵字比較次數(shù)最少？最多比較多少次？六、(本題8分)假設(shè)把n個元素的序列(ai,a2,&)滿足條件akaj(ij),試問，當(dāng)a與可相互交換后，該序列中逆序元素的個數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。七、(每小題4分，共8分)設(shè)內(nèi)存有大小為6個記錄的緩沖區(qū)供內(nèi)排序使用，文件的關(guān)鍵字序列為29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,90,試列出：(1)用內(nèi)排序求出初始?xì)w并段；(2)用置換一選擇排序求初始?xì)w并段。八、(本題8分

40、)已知一組關(guān)鍵字為(19,14,23,1,68,20,84,27,55,11,10,79,哈希函數(shù)：H(key)=keyMOD13,哈希地址空間為012,請構(gòu)造用鏈地址法處理沖突的哈希表，并求平均查找長度。九、(本題9分)已知關(guān)鍵字序列23,13,5,28,14,25,試構(gòu)造二叉排序樹。十、(本題15分)編寫一個算法求二又樹的深度。模擬試題(三)參考答案一、單項選擇題(每小題2分，共20分)(1)B(2)A(3)B(4)C(5)B(6)BD(8)A(9)D(10)C二、(本題8分)用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,

41、7)20三、(本題8分)鄰接矩陣：0111。一01011011010101110鄰接表如下圖面示：四、(每小題4分，共8分)(1)找出所有的關(guān)鍵路徑有：v1-v2-v3-v5fv6,以及v1fv4fv6。(2)v3事件的最早開始時間是13。五、(本題8分)采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)=999999+Tog210000001=1000019次。六、(本題8分)不對，例如序列3、3、4、2、l的“逆序元素”個數(shù)是2,2和1是“逆序元素”；但是將第二個3和2交換后，成為3、2、4、3、l,此時“逆序元素”個數(shù)是3,2、3和1是“逆序元素”。然而交換后一定減少的是“逆序?qū)?/p>

42、”的個數(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,18,25,28,31,36,57,65,78,99;歸并段3:2,14,17,20,30.八、(本題8分)用鏈地址法處理沖突的哈希表如

43、下圖所示：I-HIa二l+l四I八ASL=1(1*6+2*4+3*1+4*1)=1.7512九、(本題9分)構(gòu)造二叉排序樹的過程如下圖所示。十、(本題15分)若二叉樹為空，深度為0;若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。C+語言版測試程序見exam310c+,具體算當(dāng)如下：templateintbitree_depth(constBinary_tree&T)/求二叉樹的深度returnaux_bitree_depth(T.get_root();templateintaux_bitree_depth(Binary_node*sub_root)/求二叉樹

44、的深度if(sub_root=NULL)return0;/空二叉樹的深度為0elseintd_lsub,d_rsub;d_lsub=aux_bitree_depth(sub_root-left);/左子樹的深度d_rsub=aux_bitree_depth(sub_root-right);右子樹的深度返回左右子局的7度最大值加1return(d_lsubd_rsub)?d_lsub:d_rsub)+1;C語言版測試程序見exam310G具體算當(dāng)如下：intBiTreeDepth(BiTreeT)/求二叉樹的深度if(T=NULL)return0;/空二叉樹的深度為0elseintd_lsub,

45、d_rsub;d_lsub=BiTreeDepth(T-lchild);/莊子樹的深度d_rsub=BiTreeDepth(T-rchild);/盾子樹的深度返回左右子樹的7度最大值加1return(d_lsubd_rsub)?d_lsub: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

46、個元素之后插入一個元素B)從隊頭刪除一個元素C)判斷一個隊列是否為空D)讀取隊頭元素的值D)21它的帶權(quán)路徑長度為(4)字符A、B、C、D依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成()個不同的字符串？A)15B)14C)16(5)由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹,A)11B)37C)19D)以下6-8題基于下面的敘述：若某二叉樹結(jié)點的中序遍歷的序列為53A、B、C、D、E、F、G,后序遍歷的序列為B、D、C、A、F、G、E。(6)則該二叉樹結(jié)點的前序遍歷的序列為(A)E、G、F、C)E、A、C、(7)該二叉樹有(A) 3A、B、C、D、BD、G、F)個葉子。

47、B) 2B)D)E、E、)。A、G、G、A、C)5C、C、F、D、B、F、D)4(8)該二叉樹的按層遍歷的序列為(A)E、G、F、A、C、D、BC) E、A、G、C、F、B、DOB)D)E、A、C、B、D、G、E、G、A、C、D、F、(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分)試述順序查找法、折半查找法和分塊查找法對被查找的表中元素的要求，對長度為的查找表來說，三種查找法在查找成功時的查找長度各是多少?三、（

48、本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是46,25,78,62,12,80，試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。四、（本題8分）給定一個關(guān)鍵字序列24,19,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é)點序列

49、。七、（本題8分）請說明對一棵二叉樹進(jìn)行前序、中序和后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？八、（本題8分）對于如下圖所示的G,用Kruskal算法構(gòu)造最小生成樹，要求圖示出每一步的變化情況。九、（本題9分）已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI十、（本題15分）已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為請寫出遞歸算法，從小到大輸出該二叉排序樹中所有關(guān)鍵字值K的結(jié)點的關(guān)鍵字的值。模擬試題（四）參考答案-、單項選擇題(每小題2分，共20分)(5)B(10)B(1)B(2)C(3)A(4)B(6)

50、CA(8)C(9)C二、（本題8分）三種方法對查找的要求分別如下：順序查找法：表中元素可以任意存放；折半查找法：表中元素必須以關(guān)鍵字的大小遞增或遞減的次序存放：分塊查找法：表中元素每塊內(nèi)的元素可任意存放，但塊與塊之間必須以關(guān)鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大于（或小）后一塊內(nèi)任何元素的關(guān)鍵字。三種方法的平均查找長度分別如下：n1順序查找法：查找成功的平均查找長度為-1;2折半查找法：查找成功的平均查找長度為10g2（n+1）+1；1.n分塊查找法：若用順序查找確定所在的塊，平均查找長度為一（一十s）十1；若用2s折半確定所在塊，平均查找長度為1og2（n+1）+-

51、0s2三、（本題8分）(b)U)te)(f)四、（本題8分）快速排序的第一趟結(jié)果為22,19,13,6,24,38,43,12;堆排序時所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是0（1）,快速排序是O（logn）,可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時間：堆是O（nlogn）,快速排序是0（n2）,所以,可見快速排序時間復(fù)雜度最差。注意：快速排序的平均時排序速度最快，但在最壞情況下不一定比其他排序方法快。五、(本題8分)依題意A的起始地址為1000,則有：Loc(9,-2)=1000+(9-0)*(0-(-5)+1)+(-2-(-5)*4=1228。六、(

52、本題8分)先畫出該二叉樹的樹形結(jié)構(gòu)。對其進(jìn)行后序遍歷得到后序序列為：HIDJKEBLFGCA。七、(本題8分)二叉樹任兩個中葉結(jié)點必在某結(jié)點的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進(jìn)行遍歷的。所以在三種遍歷序列中葉結(jié)點的相對次序是不會發(fā)生改變的。八、(本題8分)用Kruskal算法構(gòu)造最小生成樹的過程如下圖所示：QQQ九、(本題9分)先由先序序列的第一個結(jié)點確定二叉樹的根結(jié)點，再由根結(jié)點在中序序列中左側(cè)部分為左子樹結(jié)點，在右側(cè)部分為右子樹結(jié)點，再由先序序列的第一個結(jié)點確定根結(jié)點的左右孩子結(jié)點，由類似的方法可確定其他結(jié)點，如下圖所示。十、(本題15分)由于二叉排序樹是中序有序的，因此對二叉排序樹采用中序遍歷依次輸出大于等于K的結(jié)點即可。C+語言版采用教材所提供的二叉排序樹的存儲結(jié)構(gòu)，并使用友元方式共享二叉排序的根指針，測試程序見exam410c+,具體算當(dāng)如下：templatevoiddisplay_key(constBinary_tree&T,RecordK)/從小到裝輸出該二又排序機鬲所有關(guān)鍵字值)K的結(jié)點的關(guān)鍵字的值aux_display_k