《数据结构习题课》PPT课件.ppt
数据结构习题 第 8 章,吉林大学计算机科学与技术学院谷方明,第8章作业,8-48-7，8-8，8-9，8-108-138-22，8-23,8-4,设有关键词为A、B、C和D，按照不同的输入顺序，共可能组成多少种不同的二叉查找树。请画出其中高度较小的6种。,参考答案,以A为根的BST共5种B为第2个元素：2种C为第2个元素：1种（高度为2）D为第2个元素：2种以B为根的BST共2种（高度为2）以C为根的BST共2种（高度为2）以D为根的BST共5种（类似A）一共有14种。高度为2的有6种，为3的有8种,8-7,画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。,参考答案,ASLsucc=(1+2*2+3*4+4*3)/10=29/10ASLunsucc=(5*3+6*4)/11=39/11,8-8,对长度为12的有序表（a1,a2,a12）（其中ai a12,aixai+1（i=1,2,11）等情况发生的概率相等，则查找不成功的平均查找长度是多少？,二叉判定树如下：ASLUNSUCC En/(n+1)(3*3+4*10)/13 49/13,参考答案,8-9,假设按下述递归方法进行顺序表的查找：若表长n 10，则进行顺序查找，否则进行折半查找。试画出对表长n=50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。,ASL=(1+2*2+3*4+(4+5+6+7+8)*8+9*3)/50=284/50,参考答案,8-10,已知下列关键词和它们对应的散列函数值：由此构造哈希表，用线性探测法冲突，计算平均查找长度ASL。若用拉链法解决冲突情况又如何?,参考答案,线性探测法（假设散列表的长度是8，下标从0开始）查找成功ASL=(1*5+3*1+7*1)/7=15/7,拉链法（假设散列表长度是8，下标从0开始）查找成功ASL=(1*5+2*1+2*1)/7=9/7,合并拉链法（算法C）,拉链法（假设散列表的长度是8，下标从0开始）查找成功ASL=(1*5+2*1+2*1)/7=9/7,8-13,已知序列(17,31,13,11,20,35,25,8,4,11,24,40,27)，请画出该序列的二叉查找树，并分别给出下列操作后的二叉查找树。（1）插入数据9（2）删除节点17（3）再删除节点13,参考答案,动态插入创建二叉查找树：(17,31,13,11,20,35,25,8,4,11,24,40,27),17,(17,31,13,11,20,35,25,8,4,11,24,40,27),插入数据9,删除17,再删除节点13,8-22,编写判定给定的二叉树是否是二叉查找树的算法。,提示判定二叉树是否为二叉查找树是建立在中根遍历的框架基础下，在遍历中附设一指针pre指向当前访问节点的中根直接前驱，每访问一个节点便比较前驱节点pre和此节点是否有序，若遍历结束后各节点和其中根直接前驱均满足有序，则此二叉树为二叉查找树；否则，只要有一个节点不满足，那么此二叉树就不是二叉查找树。,算法BST(t.pre,flag)/*使用中根遍历和pre指针判断t是否是二叉查找树*/B1 特判 flag TRUE.IF t=NULL THEN RETURN.B2 中根遍历 BST(left(t),pre,flag).IF(!flag)THEN RETURN.IF(pre!=NULL AND data(pre)data(t)THEN(flag FALSE.RETURN.).pre t.BST(right(t),pre,flag).,C+,bool bst(BinTreeNode*t,BinTreeNode*,8-23,给定整型数组B0.m,0.n.已知B中数据在每一维方向上都按从小到大的次序排列。且整型变量x在B中存在。试设计一个算法，找出一对满足Bi,j=x的i,j值，要求比较次数不超过m+n.,【提示】本题中主要是要确定每次进行比较的对象。其中，二维数组右上角的元素是一个较为特殊的元素。可以逐次跟二维数组右上角的元素进行比较。每次比较有3种可能的结果：若相等则结束比较；若右上角的元素小于x，则可断定二维数组的最上面一行中肯定不包含x，下次比较时搜索范围即可减少一行；若右上角的元素大于x，则可断定二维数组的最右面一列中肯定不包含x，下次比较时搜索范围即可减少一列。这样，每次至少可使搜索范围减少一列或一行，最多经过m+n次即可找到x.,参考答案,算法Find(B,m,n,x)/*在B中查找x，时间复杂度O(m+n)*/F1初始化 i 0.j n.F2比较Bi,j与x WHILE(i=0)DO(IF(Bi,j=x)THEN RETURN TRUE.IF(Bi,jx)THEN i i+1.IF(Bi,jx)THEN j j-1.)RETURN FALSE.,1.（8分）数组A中存放n个整数（0=Ai=10000，1=i=n），设计算法求出数组A中的第k小数（1=k=n=10000）。例如：若数组A中包含4个整数为1、9、4、16，则A中第2小数为4.(1)给出算法的基本设计思想（2分），高效算法有额外加分（2分）；(2)描述算法，并要求对算法中的关键步骤给出注释（3分）；(3)给出算法的时间复杂性分析（1分）。,分析,本题方法较多，典型有三种。方法一：先排序（任意一种排序方法），输出第k大的数O(nlogn)；方法二：执行k步选择最小值，可以用堆优化；O(k*n)方法三：利用快排的分划思想O(logn*logn)。方法四：桶排序O(n)方法三、四都认为是较优的算法。,参考答案（方法三）,算法思想：利用快排的分划思想求第k小元素。若分划位置 j=k，则查找成功；若jk则在(j+1,e)这段里查找第k小位置;若jk，则在(s.j-1)查找第k小位置时间复杂度（logn*logn）,算法描述：,int search(int k,int n)int s=1,e=n;while(1)int i=s,j=e;while(i=ai if(kj),第1步：s=1，e=n;第2步：循环做如下操作 2.1 分划，得到i.2.2 如果k=i，那么返回Ai;如果ki，那么s=i+1,k=k-i;如果ki，那么e=i-1；,（12分）给定无向连通正权图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)，头指针数组Edge tHeadMAXN;,
