數(shù)據(jù)結(jié)構應用題整理

1、1、二叉樹前序 中序遍歷（序列與圖的相互轉(zhuǎn)化）例題1：中序序列BDCEAFHG前序序列 ABCDEFGHABFCGDEH例題2ABCDFEGHKJILOMNPRQ前序序列：ABCDEFGHIJKLMPQRNO（參考：后序序列：BDEFCAIJKHGQRPMNOL）中序序列：BDEFCAIJKHGPQRMNOL2、哈夫曼樹例題1：7,19,2,6,32,3,21,10其對應字母分別為a,b,c,e,f,g,h。哈夫曼編碼： a：0010b：10c：00000d：0001e：01f：00001g：11h：0011例題2： w=5, 29, 7, 8, 14, 23, 3, 11例題3例如，設一組電

2、文的字符集D及其概率分布W為：D=a,b,c,d，e，W=0.12，0.40，0.15，0.08，0.25，用哈夫曼算法構造哈夫曼樹及其對應的編碼如下圖所示。3、最小生成樹 Prim算法4、鄰接矩陣（圖<->鄰接矩陣<->遍歷序列（深度、寬度遍歷）5、二分法檢索又稱為折半查找，采用二分法檢索可以大大提高查找效率，它要求線性表結(jié)點按其關鍵字從小到大（或從大到小）按序排列并采用順序存儲結(jié)構。 采用二分搜索時，先求位于搜索區(qū)間正中的對象的下標mid，用其關鍵碼與給定值x比較:Ø lmid. Key = x，搜索成功；Ø lmid. Key > x，把

3、搜索區(qū)間縮小到表的前半部分，再繼續(xù)進行對分搜索；Ø lmid. Key < x，把搜索區(qū)間縮小到表的后半部分，再繼續(xù)進行對分搜索。Ø每比較一次，搜索區(qū)間縮小一半。如果搜索區(qū)間已縮小到一個對象，仍未找到想要搜索的對象，則搜索失敗。例題1：有一組有序的線性表如下：（10，14，20，32，45，50，68，90，100，120）下面分析在其中二分檢索關鍵字20的過程。 下面分析二分檢索關鍵字95的過程:下面給出二分檢索法的非遞歸與遞歸實現(xiàn)算法，算法中使用seqlist.h中定義的順序查找表。 /*/* 二分查找算法 文件名：b_search.c */* 函數(shù)名：binse

4、arch1()、binsearch2() */*/*-二分查找的非遞歸實現(xiàn)-*/int binsearch1(seqlist l,datatype key) int low=0,high=l.len-1,mid; while (low<=high) mid=(low+high)/2; /*二分*/if (l.datamid=key) return mid; /*檢索成功返回*/ if (l.datamid>key) high=mid-1; /*繼續(xù)在前半部分進行二分檢索*/ else low=mid+1; /*繼續(xù)在后半部分進行二分檢索*/ return -1; /* 當low&g

5、t;high時表示查找區(qū)間為空，檢索失敗*/*-二分查找的遞歸實現(xiàn)-*/int binsearch2(seqlist l,datatype key,int low,int high) int mid,k; if (low>high) return -1; /*檢索不成功的出口條件*/ else mid=(low+high)/2; /*二分*/ if (l.datamid=key) return mid; /*檢索成功返回*/ if (l.datamid>key) return /*遞歸地在前半部分檢索*/ else return /*遞歸地在后半部分檢索*/ 例題2 看書218-2

6、19頁算法復雜度 <=log2(n)+16、快速排序 寫序列例題1：書p275例題2： 設待排序的7個記錄的排序碼序列為126，272，8，165，123，12，28，一次劃分的過程如圖所示 最壞情況：當待排序記錄已經(jīng)"有序"的情況下，排序時間最長。這時，第一次劃分經(jīng)過n-1次比較，將第一個記錄定在原位置上；第二次遞歸調(diào)用，經(jīng)過n-2次比較，將第二個記錄定在它原來的位置上，這樣，總的比較次數(shù)為：C(n) = n (n-1) / 2 =O(n*n)；最好情況：每次劃分所取的樞軸都是當前無序子序列中的"中值"記錄，劃分的結(jié)果是樞軸的左右兩個子區(qū)的長度大

7、致相等，這時總的比較次數(shù)為： C(n) n + 2C(n/2) n + 2n/2+2C(n/22) = 2n+4 (n/ 22) 2n + 4n/4+2C(n/23 ) = 3n+8 (n/ 23) kn+2k C(n/2k) = nlog2n + nC(1) = O(nlog2n) 可以證明，快速排序的平均時間復雜度是O(nlog2n),它是目前基于比較的內(nèi)部排序方法中速度最快的一種，快速排序也因此而得名。7、棧：入棧 出棧序列1、設將整數(shù)1、2、3、4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下有問題：（1）若入棧次序為push(1)，pop()，push(2)

8、，push(3)，pop()，pop( )，push(4)，pop( )，則出棧的數(shù)字序列為什么？答:1 3 2 4（2）能否得到出棧序列423和432？并說明為什么不能得到或如何得到。答：不能得到423。若先1，2，3，4進棧，然后4出棧，此時從棧底到棧頂為1,2,3，不可能2先出棧，所以423是不可能的出棧序列?？梢缘玫?32。Push(1),push(2),push(3),push(4),pop(4),pop(3),pop(2)即可得到。（3）請分析1、2、3、4的24種排列中，哪些序列可以通過相應的入出棧得到。答：1234。Push(1),pop(1),push(2),pop(2),p

9、ush(3),pop(3),push(4),pop(4).1243. Push(1),pop(1),push(2),pop(2),push(3), push(4),pop(4), pop(3)1432. Push(1),pop(1),push(2),push(3),push(4),pop(4),pop(3),pop(2).4321. push(1), push(2),push(3),push(4),pop(4),pop(3),pop(2),pop(1).2134. push(1),push(2),pop(2),pop(1),push(3),pop(3),push(4),pop(4).2143.

10、 push(1),push(2),pop(2),pop(1),push(3),push(4),pop(4),pop(3).3214. push(1), push(2),push(3),pop(3),pop(2),pop(1),push(4),pop(4).1324. push(1),pop(1),push(2),push(3),pop(3),pop(2),push(4),pop(4).8、二叉樹的形態(tài) 二叉排序樹9、直接插入法排序例題1：設待排序的7記錄的排序碼為312，126，272，226，28，165，123，直接插入排序算法的執(zhí)行過程如圖10.2所示。哨兵 排序碼 312，126，272，226，28，165，123初始 （） 312，126，272，226，28，165，123i=2： （126） 126，312，272，226，28，165，123i=3： （272） 126，272，312，226，28，165，123i=4： （226） 126，22