《数据结构习题课》PPT课件.ppt

《《数据结构习题课》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构习题课》PPT课件.ppt（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构习题数据结构习题 第第 8 章章吉林大学计算机科学与技术学院谷方明第第8章作章作业l8-4l8-7，8-8，8-9，8-10l8-13l8-22，8-238-4l设有关键词为A、B、C和D，按照不同的输入顺序，共可能组成多少种不同的二叉查找树。请画出其中高度较小的6种。参考答案参考答案l以A为根的BST共5种lB为第2个元素：2种lC为第2个元素：1种（高度为2）lD为第2个元素：2种l以B为根的BST共2种（高度为2）l以C为根的BST共2种（高度为2）l以D为根的BST共5种（类似A）l一共有14种。高度为2的有6种，为3的有8种8-7l画出对长度为10的有序表进行折半查找的判定树

2、，并求其等概率时查找成功的平均查找长度。参考答案参考答案lASLsucc=(1+2*2+3*4+4*3)/10=29/10lASLunsucc=(5*3+6*4)/11=39/114528169710a5a8a9a10a2a1a3a6a4a73a28-8l对长度为12的有序表（a1,a2,a12）（其中aiaj，当ij时）进行折半查找，在设定查找不成功的情况时，关键词xa12,aixdata(t)THEN(flag FALSE.RETURN.).pre t.BST(right(t),pre,flag).C+boolbst(BinTreeNode*t,BinTreeNode*&pre)/*t指向

3、根结点；pre指向t的中根前驱，初值NULL*/if(t=NULL)returntrue;if(!bst(left(t),pre)returnfalse;if(pre&pre-datat-data)returnfalse;pre=t;returnbst(right(t),pre);8-23l给定整型数组B0.m,0.n.已知B中数据在每一维方向上都按从小到大的次序排列。且整型变量x在B中存在。试设计一个算法，找出一对满足Bi,j=x的i,j值，要求比较次数不超过m+n.l【提示】本题中主要是要确定每次进行比较的对象。其中，二维数组右上角的元素是一个较为特殊的元素。可以逐次跟二维数组右上角的元素

4、进行比较。每次比较有3种可能的结果：若相等则结束比较；若右上角的元素小于x，则可断定二维数组的最上面一行中肯定不包含x，下次比较时搜索范围即可减少一行；若右上角的元素大于x，则可断定二维数组的最右面一列中肯定不包含x，下次比较时搜索范围即可减少一列。这样，每次至少可使搜索范围减少一列或一行，最多经过m+n次即可找到x.参考答案参考答案l算法Find(B,m,n,x)/*在B中查找x，时间复杂度O(m+n)*/F1初始化i0.jn.F2比较Bi,j与xWHILE(i=0)DO(IF(Bi,j=x)THENRETURNTRUE.IF(Bi,jx)THENii+1.IF(Bi,jx)THENjj-1

5、.)RETURNFALSE.1.（8分分）数组A中存放n个整数（0=Ai=10000，1=i=n），设 计 算 法 求 出 数 组 A中 的 第 k小 数（1=k=nk则在(j+1,e)这段里查找第k小位置;若jk，则在(s.j-1)查找第k小位置l时间复杂度（logn*logn）算法描述：算法描述：int search(int k,int n)int s=1,e=n;while(1)int i=s,j=e;while(i=ai&j=i)j-;while(aj=ai&j=i)i+;if(ij)s=j+1;if(ki，那么s=i+1,k=k-i;如果ki，那么e=i-1；（12分分）给定无向连通

6、正权图G和G中的一个结点v.求G的支撑树T，并使其满足如下两个条件：第一，T的根为v；第二，T中v到任一顶点u的路径长度等于G中v到u的最短路径长度。要求：(1)给出算法的基本设计思想（3分）；(2)设计图G和支撑树T的存储结构（2分）；(3)基于以上设计的存储结构，用算法描述语言描述算法，并要求对算法中的关键步骤给出注释（7分）。（1）算法设计思想：利用Dijkstra算法求该支撑树。即在用Dijkstra算法求以v作为源点的最短路的过程中，把每次确定为最短路的点和边加入到生成树T中。（2）图G用邻接表存储：边的存储结构为Edge(VerAdj,Weight,Link)，头指针数组Edge*HeadMAXN;最短路径长度disMAXN；支撑树T使用邻接链表存储：边的存储结构使用Edge(VerAdj,Weight,Link)，头指针数组EdgetHeadMAXN;