数据结构应用题整理

11、二叉树前序中序遍历（序列与图的相互转化）例题1：中序序列BDCEAFHG前序序列ABCDEFGH例题2前序序列：ABCDEFGHIJKLMPQRNO（参考：后序序列：BDEFCAIJKHGQRPMNOL）中序序列：BDEFCAIJKHGPQRMNOL2、哈夫曼树例题1：7,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。ABFCGDEHABCDFEGHKJILOMNPRQ2哈夫曼编码：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011例题2：w={5,29,7,8,14,23,3,11}例题3例如，设一组电文的字符集D及其概率分布W为：D={a,b,c,d，e}，W={0.12，0.40，0.15，0.08，0.25}，用哈夫曼算法构造哈夫曼树及其对应的编码如下图所示。3、最小生成树3Prim算法4、邻接矩阵（图-邻接矩阵-遍历序列（深度、宽度遍历））45、二分法检索又称为折半查找，采用二分法检索可以大大提高查找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用顺序存储结构。采用二分搜索时，先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:l[mid].Key=x，搜索成功；l[mid].Keyx，把搜索区间缩小到表的前半部分，再继续进行对分搜索；l[mid].Keyx，把搜索区间缩小到表的后半部分，再继续进行对分搜索。每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。例题1：有一组有序的线性表如下：（10，14，20，32，45，50，68，90，100，120）下面分析在其中二分检索关键字20的过程。下面分析二分检索关键字95的过程:下面给出二分检索法的非递归与递归实现算法，算法中使用seqlist.h中定义的顺序查找5表。/****************************************************//*二分查找算法文件名：b_search.c*//*函数名：binsearch1()、binsearch2()*//****************************************************//*--------二分查找的非递归实现------*/intbinsearch1(seqlistl,datatypekey){intlow=0,high=l.len-1,mid;while(low=high){mid=(low+high)/2;/*二分*/if(l.data[mid]==key)returnmid;/*检索成功返回*/if(l.data[mid]key)high=mid-1;/*继续在前半部分进行二分检索*/elselow=mid+1;/*继续在后半部分进行二分检索*/}return-1;/*当lowhigh时表示查找区间为空，检索失败*/}/*--------二分查找的递归实现------*/intbinsearch2(seqlistl,datatypekey,intlow,inthigh){intmid,k;if(lowhigh)return-1;/*检索不成功的出口条件*/else{mid=(low+high)/2;/*二分*/if(l.data[mid]==key)returnmid;/*检索成功返回*/if(l.data[mid]key)return/*递归地在前半部分检索*/elsereturn/*递归地在后半部分检索*/}}例题2看书218--219页算法复杂度=log2(n)+16、快速排序写序列例题1：书p275例题2：设待排序的7个记录的排序码序列为{126，272，8，165，123，12，28}，一次划分的过程如图所示6最坏情况：当待排序记录已经有序的情况下，排序时间最长。这时，第一次划分经过n-1次比较，将第一个记录定在原位置上；第二次递归调用，经过n-2次比较，将第二个记录定在它原来的位置上，．．．．．．，这样，总的比较次数为：C(n)=n(n-1)/2=O(n*n)；最好情况：每次划分所取的枢轴都是当前无序子序列中的中值记录，划分的结果是枢轴的左右两个子区的长度大致相等，这时总的比较次数为：C(n)≤n+2C(n/2)≤n+2[n/2+2C(n/22)]=2n+4(n/22)≤2n+4[n/4+2C(n/23)]=3n+8(n/23)≤．．．．．．≤kn+2kC(n/2k)=nlog2n+nC(1)=O(nlog2n)可以证明，快速排序的平均时间复杂度是O(nlog2n),它是目前基于比较的内部排序方法中速度最快的一种，快速排序也因此而得名。7、栈：入栈出栈序列1、设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop()，则出栈的数字序列为什么？7答:1324（2）能否得到出栈序列423和432？并说明为什么不能得到或如何得到。答：不能得到423。若先1，2，3，4进栈，然后4出栈，此时从栈底到栈顶为1,2,3，不可能2先出栈，所以423是不可能的出栈序列。可以得到432。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),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),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、二叉树的形态二叉排序树9、直接插入法排序例题1：设待排序的7记录的排序码为{312，126，272，226，28，165，123}，直接插入排序算法的执行过程如图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，312]，28，165，123i=5：（28）[28，126，226，272，312]，165，123i=6：（165）[28，126，165，226，272，312]，123i=7：（123）[28，123，126，165，226，272，312]8图10.2直接插入排序算法执行过程示意图例题2书p265—266