數(shù)據(jù)結(jié)構(gòu)應(yīng)用題整理

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1、二叉樹(shù)前序 中序遍歷（序列與圖的相互轉(zhuǎn)化）例題1：中序序列BDCEAFHG前序序列 ABCDEFGHABFCGDEH例題2ABCDFEGHKJILOMNPRQ前序序列：ABCDEFGHIJKLMPQRNO（參考：后序序列：BDEFCAIJKHGQRPMNOL）中序序列：BDEFCAIJKHGPQRMNOL2、哈夫曼樹(shù)例題1：7,19,2,6,32,3,21,10其對(duì)應(yīng)字母分別為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,

2、 11例題3例如，設(shè)一組電文的字符集D及其概率分布W為：D=a,b,c,d，e，W=0.12，0.40，0.15，0.08，0.25，用哈夫曼算法構(gòu)造哈夫曼樹(shù)及其對(duì)應(yīng)的編碼如下圖所示。3、最小生成樹(shù) Prim算法4、鄰接矩陣（圖<->鄰接矩陣<->遍歷序列（深度、寬度遍歷）5、二分法檢索又稱為折半查找，采用二分法檢索可以大大提高查找效率，它要求線性表結(jié)點(diǎn)按其關(guān)鍵字從小到大（或從大到?。┌葱蚺帕胁⒉捎庙樞虼鎯?chǔ)結(jié)構(gòu)。 采用二分搜索時(shí)，先求位于搜索區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵碼與給定值x比較:Ø lmid. Key = x，搜索成功；Ø lmid.

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

4、*/* 函數(shù)名：binsearch1()、binsearch2() */*/*-二分查找的非遞歸實(shí)現(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ù)在前半部分進(jìn)行二分檢索*/ else low=mid+1; /*繼續(xù)在后半部分進(jìn)行二分檢索*/ return

5、-1; /* 當(dāng)low>high時(shí)表示查找區(qū)間為空，檢索失敗*/*-二分查找的遞歸實(shí)現(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 /*遞歸地在后半部分檢索*

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

7、樞軸的左右兩個(gè)子區(qū)的長(zhǎng)度大致相等，這時(shí)總的比較次數(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) 可以證明，快速排序的平均時(shí)間復(fù)雜度是O(nlog2n),它是目前基于比較的內(nèi)部排序方法中速度最快的一種，快速排序也因此而得名。7、棧：入棧 出棧序列1、設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下有問(wèn)題：（1）若入棧次序?yàn)閜ush(1)，

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

9、h(2),pop(2),push(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)

10、,pop(4).2143. 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、二叉樹(shù)的形態(tài) 二叉排序樹(shù)9、直接插入法排序例題1：設(shè)待排序的7記錄的排序碼為312，126，272，226，28，165，123，直接插入排序算法的執(zhí)行過(guò)程如圖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，226，272，