数据结构应用题整理

1、1、二叉树前序 中序遍历（序列与图的相互转化）例题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、二分法检索又称为折半查找，采用二分法检索可以大大提高查找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用顺序存储结构。 采用二分搜索时，先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:Ø lmid. Key = x，搜索成功；Ø lmid. Key > x，把

3、搜索区间缩小到表的前半部分，再继续进行对分搜索；Ø lmid. Key < x，把搜索区间缩小到表的后半部分，再继续进行对分搜索。Ø每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。例题1：有一组有序的线性表如下：（10，14，20，32，45，50，68，90，100，120）下面分析在其中二分检索关键字20的过程。 下面分析二分检索关键字95的过程:下面给出二分检索法的非递归与递归实现算法，算法中使用seqlist.h中定义的顺序查找表。 /*/* 二分查找算法 文件名：b_search.c */* 函数名：binse

4、arch1()、binsearch2() */*/*-二分查找的非递归实现-*/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; /*继续在前半部分进行二分检索*/ else low=mid+1; /*继续在后半部分进行二分检索*/ return -1; /* 当low&g

5、t;high时表示查找区间为空，检索失败*/*-二分查找的递归实现-*/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，一次划分的过程如图所示 最坏情况：当待排序记录已经"有序"的情况下，排序时间最长。这时，第一次划分经过n-1次比较，将第一个记录定在原位置上；第二次递归调用，经过n-2次比较，将第二个记录定在它原来的位置上，这样，总的比较次数为：C(n) = n (n-1) / 2 =O(n*n)；最好情况：每次划分所取的枢轴都是当前无序子序列中的"中值"记录，划分的结果是枢轴的左右两个子区的长度大

7、致相等，这时总的比较次数为： 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),它是目前基于比较的内部排序方法中速度最快的一种，快速排序也因此而得名。7、栈：入栈 出栈序列1、设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2)

8、，push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？答:1 3 2 4（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),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、二叉树的形态 二叉排序树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，22