资源描述：
《数据结构复习要点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、综合应用题1、树（二叉树四种遍历P1432、哈夫曼树P1436）2、查找（会求顺序、二分查找、哈希表的平均查找长度、会建哈希表、二叉排序树及二叉排序树、B树插入、删除）P213三、23、排序（各种排序算法的过程）P241三、14、图（两种遍历、最小生成树、拓朴排序、最短路径、关键路径）P180131820算法题：1、对单链表遍历，对某特征的结点进行某种操作。设有一个由正整数组成的无序（向后）单链表，编写能够完成下列功能的算法：①找出最小值结点，且打印该数值。②若该值是奇数，则将其与直接后继结点的数值交换。③若该值是偶数，则将其直接后继结点删除。单链表存储结构说明如下：typedefun
2、signedlongElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;2、用递归、遍历思想，对二叉树某特征的结点进行某种操作(如求某种类型结点的总数)。bintreelocate(bintreet,datatypex){/*在二叉树t中查找值为x的结点*/bintreep;if(t==NULL)returnNULL;elseif(t->data==x)returnt;else{p=locate(t->lchild,x);if(p)returnp;elsereturnlocate(t->r
3、child,x);}}3、栈或队列的应用（实现）。第8章查找1.假定查找有序表A[25]中每一元素的概率相等，试分别求出进行顺序、二分查找每一元素时的平均查找长度。解：(1)顺序查找：ASL=(1+2+3+…+25)/25=13(2)二分查找：ASL=(1+2*2+4*3+8*4+10*5)/25=99/25=3.96(参见下图的二分查找树)2.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。解：散列
4、函数：H(K)=K%m其中依题意取m=13H(32)=32%13=6H(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9H(94)=94%13=3(冲突)设d0=H(K)=H(94)=3d1=(d0+1)%m=(3+1)%13=4H(25)=25%13=12H(46)=46%13=7H(18)=18%13=5H(70)=70%13=5(冲突)设d0=H(K)=H(70)=5d1=(d0+1)%m=(5+1)%13=6(冲突)d2=(d1+1)%m=(6+1)%13=7(冲突)d3=(d2+1)%m=(7+1)%13=8ASL=(8
5、*1+1*2+1*4)/10=1.43.已知一组元素为(46,25,78,62,12,37,70,29)，画出按元素排列顺序输入生成的一棵二叉搜索树。解：第七章图1、已知一个图的顶点集V各边集G如下：V={0，1，2，3，4，5，6，7，8，9}；E={（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的
6、。图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时解:0123456789邻接表4567890011h0→4→11111h1→7→2→0211h2→8→1311h3→8→4411h4→3→05111h5→9→8→6611h6→7→57111h7→8→6→1811111h8→9→7→5→3→2911h9→8→5图深度优先序列广度优先序列邻接矩阵表示时0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9邻接表表示时0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，52、设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并
7、给出该图的最小生成树。答：深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}第六章树1、已知一棵二叉树的先序遍历的结果序列是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。解：由先序序列ABECDFGHIJ知，结点A为二叉树根，由中序序列EBCDAFHIGJ，知左子树的结点为：EBCD，右子树的结点为：FHIGJ。同理可确定左
