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

1、1、二叉樹(shù)前序 中序遍歷（序列與圖的相互轉(zhuǎn)化）例題1：中序序列BDCEAFHG前序序列ABCDEFGH例題2AGBLHCMIDNPJEQKFR前序序列：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, 11<>堿

2、® 例題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ù)9此取B. FT :B C 算法PrimE 卜-i-110:E jjuIDKruskal法構(gòu)琲最小殺膻樹(shù)的過(guò)程(&(0)-49七T(e)4、鄰接矩陣（圖 <-> 鄰接矩陣 <-> 遍歷序列（深度、寬度遍歷）園晞雜矩陣示例If'吐0 111<0100A仁10 10A2=10 10O1 1 Q 1110 010 10Lo 1 0 0-o

3、tt&7無(wú)空至塑1暨遵報(bào)接怖當(dāng)采用劇接表存睹結(jié)構(gòu)井且甘鰭結(jié)構(gòu)匕確 定的情況下，遍歷的結(jié)果將是確定的.DFS 宇列：Co -> c1 ->-> c4 c5 ->5、二分法檢索又稱(chēng)為折半查找，采用二分法檢索可以大大提高查找效率，它要求線(xiàn)性表結(jié) 點(diǎn)按其關(guān)鍵字從小到大（或從大到?。┌葱蚺帕胁⒉捎庙樞虼鎯?chǔ)結(jié)構(gòu)。采用二分搜索時(shí)，先求位于搜索區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵碼與給定值 x比較：?Imid. Key = x，搜索成功；lmid.Key > x，把搜索區(qū)間縮小到表的前半部分，再繼續(xù)進(jìn)行對(duì)分搜索;lmid.Key < x，把搜索區(qū)間縮小到表的后半部分

4、，再繼續(xù)講行對(duì)分搜索。每比較一次，搜索區(qū)間縮小一半。如果搜索區(qū)間已縮小到一個(gè)對(duì)象，仍未 找到想要搜索的對(duì)象，則搜索失敗。例題1：有一組有序的線(xiàn)性表如下：（10, 14， 20， 32， 45， 50， 68, 90， 100， 120）下面分析在其中二分檢索關(guān)鍵字20的過(guò)程。下標(biāo)； 01234567391014203245506890100120low=2 mid=2 hlgh=3第3灰比亂檢索成咖逋甸拉置NF面分析二分檢索關(guān)鍵字95的過(guò)程：下軌 0123567891014203245506890100120hlghi=7 lovr=3此略hiqzi晞即臺(tái)找區(qū)司為空，說(shuō)明檢叢知賂 迸宵檢宋知?jiǎng)?/p>

5、卑息°seqlist.h中定義的順序查找F面給出二分檢索法的非遞歸與遞歸實(shí)現(xiàn)算法，算法中使用表。*/*二分查找算法文件名：b_search.c */*函數(shù)名：binsearch1() 、binsearch2()*/*/* 二分查找的非遞歸實(shí)現(xiàn)*/int bin search1(seqlist datatype key) in t low=0,high=l.le n-1,mid; while (low<=high) mid=(low+high)/2;/*if (l.datamid=key) return mid; /* if (l.datamid>key) high=mid

6、-1; /* else low=mid+1; /* return -1; /* 二分*/檢索成功返回*/繼續(xù)在前半部分進(jìn)行二分檢索*/繼續(xù)在后半部分進(jìn)行二分檢索*/當(dāng)low>high時(shí)表示查找區(qū)間為空，檢索失敗*/* 二分查找的遞歸實(shí)現(xiàn)*/int bin search2(seqlist l,datatype key,i nt low,i nt high) int mid,k;if (low>high) return -1;/*else mid=(low+high)/2;/*if (l.datamid=key) return mid; /*檢索不成功的出口條件*/二分*/檢索成功返回

7、*/if (l.datamid>key) return/*遞歸地在前半部分檢索*/else retur n/*遞歸地在后半部分檢索*/例題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ò)程如圖所示左站也為leftrighta126272：81.651231228I=lentemp=kaleft=12Sj=nghtk>-2S(aj) af-2S(1)27281.6512312(2)itemp-k-apeft=126 k<27

8、2(ai) aj-272 jjJ1S1.6512272i11Jtenip=kaleft=126 k>12(ajD ai=12 i=i+l0)2312 8165123272itempS(ai)i=i 十 1J23128IdS1232721jtemp=k=aleft-125j-j-128128123165272temp-k-aleft-n(5 k>123(aj) ai=123 i-il28128123165272Ttemp=k=aleft=126 冃a.itanp=16(7)281281231261155272i=J一茂劃分結(jié)束最壞情況：當(dāng)待排序記錄已經(jīng)”有序”的情況下，排序時(shí)間最長(zhǎng)。

9、這時(shí)，第一次劃分經(jīng)過(guò)n-1次比較，將第一個(gè)記錄定在原位置上；第二次遞歸調(diào)用，經(jīng)過(guò)n-2次比較，將第二個(gè)記錄定在它原來(lái)的 位置上，這樣，總的比較次數(shù)為：C(n) = n (n-1) / 2 =0( n*n);最好情況：每次劃分所取的樞軸都是當(dāng)前無(wú)序子序列中的"中值"記錄，劃分的結(jié)果是樞軸的左右兩個(gè)子區(qū)的長(zhǎng)度大致相等，這時(shí)總的比較次數(shù)為：C(n) w n + 2C(n/2)< n + 2n/2+2C(n/22)=2n+4 (n/ 22) w 2n + 4n/4+2C(n/23 ) = 3n+8 (n/ 23)w wkn+2k C(n/2k)=nlog2n + nC(1)

10、= 0(nlog2n)可以證明，快速排序的平均時(shí)間復(fù)雜度是0(nlog2n),它是目前基于比較的內(nèi)部排序方法中速度最快的一種，快速排序也因此而得名。7、棧：入棧出棧序列1、設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入 其中，請(qǐng)回答下有問(wèn)題：(1) 若入棧次序?yàn)?push(1) , 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)

11、棧，然后4出棧，此時(shí)從棧底到棧頂為1,2,3，不可能2先出棧，所以423是不可能的出棧序列。可以得到 432。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),push(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),

12、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. 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(

13、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ù)附丁輕夫?qū)嵗?30. 20. 40t 10. 25, 45)肅去9馬創(chuàng)建二義排序協(xié)的過(guò)稈如Fi卄好 bi 插人 30d)M 4Oe)捕人10 f 1 tffr 259、直接插入法排序例題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, 31