数据结构习题课8

数据结构习题第8章吉林大学计算机科学与技术学院谷方明第8章作业8-48-7，8-8，8-9，8-108-138-22，8-238-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/10ASLunsucc=(5*3+6*4)/11=39/114528169710a5a8a9a10a2a1a3a6a4a73a28-8对长度为12的有序表（a1,a2,…,a12）（其中aiaj，当ij时）进行折半查找，在设定查找不成功的情况时，关键词xa1,xa12,aixai+1（i=1,2,…,11）等情况发生的概率相等，则查找不成功的平均查找长度是多少？56391711812a6a9a11a12a3a1a4a7a5a82410a2a10二叉判定树如下：ASLUNSUCC＝En/(n+1)＝(3*3+4*10)/13＝49/13参考答案56391711812a6a9a11a12a3a1a4a7a5a82410a2a108-9假设按下述递归方法进行顺序表的查找：若表长n≤10，则进行顺序查找，否则进行折半查找。试画出对表长n=50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。ASL=(1+2*2+3*4+(4+5+6+7+8)*8+9*3)/50=284/50参考答案26-3013-171-519-2432-3725123863144a25a38a44a12a6a18a31187-1145-5039-43a28-10已知下列关键词和它们对应的散列函数值：由此构造哈希表，用线性探测法冲突，计算平均查找长度ASL。若用拉链法解决冲突情况又如何?keyZhaoSunLiWangChenLiuZhangH(key)6574164参考答案线性探测法（假设散列表的长度是8，下标从0开始）查找成功ASL=(1*5+3*1+7*1)/7=15/7下标元素7Li6Zhao5Sun4Wang32Zhang1Chen0Liu拉链法（假设散列表长度是8，下标从0开始）查找成功ASL=(1*5+2*1+2*1)/7=9/7下标指针76543Λ2Λ10ΛLiΛZhaoLiuΛSunΛWangZhangΛChenΛ合并拉链法（算法C）拉链法（假设散列表的长度是8，下标从0开始）查找成功ASL=(1*5+2*1+2*1)/7=9/7下标元素Link7Li-16Zhao35Sun-14Wang23Liu-12Zhang-11Chen-108-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)171731173113173113111731131120173113112035(17,31,13,11,20,35,25,8,4,11,24,40,27)1731131120352517311311203584244027插入数据9251731131120358424402792517311311203584244027删除17251731131120358424402724203113112535844027再删除节点13242031131125358440272420311182535440278-22编写判定给定的二叉树是否是二叉查找树的算法。[提示]判定二叉树是否为二叉查找树是建立在中根遍历的框架基础下，在遍历中附设一指针pre指向当前访问节点的中根直接前驱，每访问一个节点便比较前驱节点pre和此节点是否有序，若遍历结束后各节点和其中根直接前驱均满足有序，则此二叉树为二叉查找树；否则，只要有一个节点不满足，那么此二叉树就不是二叉查找树。算法BST(t.pre,flag)/*使用中根遍历和pre指针判断t是否是二叉查找树*/B1[特判]flagTRUE.IFt=NULLTHENRETURN.B2[中根遍历]BST(left(t),pre,flag).IF(!flag)THENRETURN.IF(pre!=NULLANDdata(pre)data(t))THEN(flagFALSE.RETURN.).pret.BST(right(t),pre,flag).▌C++boolbst(BinTreeNodeT*t,BinTreeNodeT*&pre)/*t指向根结点；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-23给定整型数组B[0..m,0..n].已知B中数据在每一维方向上都按从小到大的次序排列。且整型变量x在B中存在。试设计一个算法，找出一对满足B[i,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[比较B[i,j]与x]WHILE(i=mANDj=0)DO(IF(B[i,j]=x)THENRETURNTRUE.IF(B[i,j]x)THENi←i+1.IF(B[i,j]x)THENj←j-1.)RETURNFALSE.▌1.（8分）数组A中存放n个整数（0=A[i]=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）算法描述：intsearch(intk,intn){ints=1,e=n;while(1){inti=s,j=e;while(ij){while(a[j]=a[i]&&j=i)j--;while(a[j]=a[i]&&j=i)i++;if(ij)swap(a[i][j])}if(k==j)returnj;if(kj)s=j+1;if(kj)}}第1步：s=1，e=n;第2步：循环做如下操作2.1分划，得到i.2.2如果k==i，那么返回A[i];如果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*Head[MAXN];最短路径长度dis[MAXN]；支撑树T使用邻接链表存储：边的存储结构使用Edge(VerAdj,Weight,Link)，头指针数组EdgetHead[MAXN];