算法设计与分析习题其次章分治与递归

本文格式为Word版，下载可任意编辑——算法设计与分析习题其次章分治与递归

此为刘仁仁编写教材答案

算法设计与分析习题其次章分治与递归

2023-12-28

此为刘仁仁编写教材答案

2.1对于顺序查找算法，分析目标值存在于数组中的概率p趋于0的含义，这种状况下平均查找次数有什么样的变化？当p趋于1时呢？见教材P12。平均比较次数为n-p(n-1)/2。p趋于0,平均次数趋于n;p趋于1时，平均次数趋于(n+1)/2。(求极限)

2023-12-28

此为刘仁仁编写教材答案

2.2对于折半查找算法，分析目标值存在与数组中的概率p对算法的时间繁杂度的影响。见教材P12。平均比较次数为log2n。平均次数与p关系不大，趋向于log2n。

2023-12-28

此为刘仁仁编写教材答案

2.3在一个由10个元素构成的数组中，用折半查找法查各个位置上元素分别需要进行多少次元素值的比较？数组元素0123456789分别对应的比较次数3234134234

2023-12-28

此为刘仁仁编写教材答案

2.4试写出求二叉树中序遍历序列的递归程序。voidwalk(T_Node*p){if(p==NULL)return;walk(p-left);printf(p-data);walk(p-right);}fortheotherexample:voidwalk(T_Node*p,int*visit){if(p){if(walk(p-left))if(visit(p-data))if(walk(p-right))returnok;}elsereturnok;}2023-12-285

此为刘仁仁编写教材答案

2.5针对图2.1(b)的二叉排序树，若查找的命中率为100%,即不考虑查找的目标值不在树中的状况，则平均需要多少次元素值的比较？查找处于第k层的元素需要比较k次，对于图2.1(b),总的比较次数为11+22+33+45=34,平均次数34/11=3.1次。114312023-12-28

5

此为刘仁仁编写教材答案

2.6向一棵空二叉树中依次插入如下元素值：8,9,10,2,1,5,3,6,4,7,11,12,要求每插入一个元素后的二叉树都是二叉排序树，画出每次插入元素后的二叉排序树。892101534671112

2023-12-28

此为刘仁仁编写教材答案

2.7按2.2.4节的描述，编写从二叉树中删除一个结点的C语言程序二叉树节点删除有三种状况：(1)*p是叶子(即它的孩子数为0):无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。(2)*p只有一个孩子*child:只需将*child和*p的双亲直接连接后，即可删去*p。注意：*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态。(3)*p有两个孩子：先令q=p,将被删结点的地址保存在q中；然后找*q的中序后继*p,并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q.2023-12-288

此为刘仁仁编写教材答案

2.8针对平衡的二叉排序树LR型失衡的状况，写出调整使之恢复平衡的算法。2AC0

B

-10CB0A0

A为最下部的失衡结点。

2023-12-28

此为刘仁仁编写教材答案

破坏平衡的原因是由于在A的左子女(L)的

右子树(R)中插入结点，使A的平衡因子由-1变为-2而失去平衡。调整规则∶a、设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；b、原C的父结点B连同其左子树向左下旋转成为新根C的左子树，原C的左子树成为B的右子树；c、原根A连同其右子树向右下旋转成为新根C的右子树，原C的右子树成为A的左子树。

2023-12-28

此为刘仁仁编写教材答案

VoidBalance(BSTreeT){lc=T-lchild;//lc指向*T的左子数根节点rd=lc-rchild;//rd指向*T的左孩子的右子数根T-bf=lc-bf=EH;//修改*T及其左孩子的平衡因子rd-bf=EH;L.Rotate(T-lchild);//对*T的左子树作左旋平衡处理R.Rotate(T);//对*T作右旋平衡处理}

2023-12-28

此为刘仁仁编写教材答案

2.10用快速排序法对如下的数据进行排序：45,23,65,57,18,2,90,84,12,76。说明第一遍扫描的具体过程。4545,23,65,57,18,2,90,84,12,7612,23,65,57,18,2,90,84,45,7612,23,65,57,18,2,90,84,45,7612,23,45,57,18,2,90,84,65,7612,23,45,57,18,2,90,84,65,7612,23,2,57,18,45,90,84,65,7612,23,2,57,18,45,90,84,65,7612,23,2,45,18,57,90,84,65,7612,23,2,45,18,57,90,84,65,7612,23,2,18,45,57,90,84,65,76

2023-12-28

此为刘仁仁编写教材答案

2.11编写针对链表的快速排序程序。需要保存指针信息。下面给出双向链表的快速排序算法voidfast_sort(Sdata*a,Sdata*f,Sdata*t){Sdata*i,*j,k,p;i=f;j=t;if(t-lnext!=f){k=a-data;//用于比较的基准数值i=f;j=t;p=-1;while(j!=i)2023-12-2813

此为刘仁仁编写教材答案

if(p==1){

//从链表前面向后寻觅比基准值大的数从链表前面向后寻觅比基准值大的数

while((j!=i)(i-data=k))i=i-rnext;j-data=i-data;p=-1;}else{//从链表最终向前寻觅比基准值小的数从链表最终向前寻觅比基准值小的数while((j!=i)(j-data=k))j=j-lnext;i-data=j-data;p=1;}i-data=k;fast-sort(a,f,i-lnext);//递归递归fast-sort(a,i-rnext,t);}}2023-12-2814

此为刘仁仁编写教材答案

2.12编写针对数组的归并排序程序。voidcombine_sort(inta[],ints,intn)//a[]为数组{intk,b,c,m;int*r=newint[n];if(n1){k=n/2;combine_sort(a,s,k);//递归调用combine_sort(a,s+k,n-k);m=0;b=s;c=s+k;

2023-12-28

此为刘仁仁编写教材答案

while((bs+k)(cs+n))//比较比较{if(a[b]a[c])r[m++]=a[b++];elser[m++]=a[c++];}if(b==s+k)for(b=c;bs+n;b++)r[m++]=a[b];elsefor(c=b;cs+k;c++)r[m++]=a[c];for(m=0;mn;m++)a[s++]=r[m];}deleter;}2023-12-2816

此为刘仁仁编写教材答案

2.13应用分治策略完成下面的整数乘法计算：23483825。套用公式(书上26)2348