算法设计与分析习题第二章分治与递归

此为刘仁仁编写教材答案

算法设计与分析习题第二章 分治与递归

2010-12-28

此为刘仁仁编写教材答案

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

2010-12-28

此为刘仁仁编写教材答案

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

2010-12-28

此为刘仁仁编写教材答案

2.3 在一个由10个元素构成的数组中，用折半查找法 查各个位置上元素分别需要进行多少次元素值的比较？ 数组元素 0 1 2 3 4 5 6 7 8 9 分别对应的比较次数 3 2 3 4 1 3 4 2 3 4

2010-12-28

此为刘仁仁编写教材答案

2.4 试写出求二叉树中序遍历序列的递归程序。 void walk (T_Node *p) { if ( p == NULL )return; walk( p->left); printf( p->data ); walk( p->right); } for the other example: void walk (T_Node *p, int *visit) { if(p){ if(walk( p->left)) if(visit( p->data )) if(walk( p->right))return ok; }else return ok; }2010-12-28 5

此为刘仁仁编写教材答案

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

13 6 17 9 14 196

5

此为刘仁仁编写教材答案

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

2010-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.2010-12-28 8

此为刘仁仁编写教材答案

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

B

-1 0 C B 0 A 0

A为最下部的失衡结点。

2010-12-28

此为刘仁仁编写教材答案

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

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

2010-12-28

此为刘仁仁编写教材答案

Void Balance(BSTree &T) { 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作右旋平衡处理 }

2010-12-28

此为刘仁仁编写教材答案

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

2010-12-28

此为刘仁仁编写教材答案

2.11 编写针对链表的快速排序程序。需要保存指针信息。下面给出双向链表的快速排序算法 void fast_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 )2010-12-28 13

此为刘仁仁编写教材答案

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 ); } }2010-12-28 14

此为刘仁仁编写教材答案

2.12 编写针对数组的归并排序程序。void combine_sort( int a[], int s, int n ) //a[]为数组 { int k,b,c,m; int *r = new int[n]; if ( n>1 ) { k = n/2; combine_sort( a, s ,k ); //递归调用 combine_sort( a, s+k, n-k ); m = 0; b = s; c = s+k;

2010-12-28

此为刘仁仁编写教材答案

while ( (b<s+k) && (c<s+n) ) //比较 比较 { if ( a[b] < a[c] ) r[m++] = a[b++]; else r[m++] = a[c++]; } if ( b == s+k ) for ( b=c; b<s+n; b++) r[m++] = a[b]; else for ( c=b; c<s+k; c++) r[m++] = a[c]; for ( m=0; m<n; m++) a[s++] = r[m]; } delete r; }2010-12-28 16

此为刘仁仁编写教材答案

2.13 应用分治策略完成下面的整数乘法计算： 2348×3825。 套用公式(书上26) 2348 = 23*102 + 48, 3825 = 38*102 + 25 结果为：8981100

2.14 应用Strassen算法完成下面的矩阵乘法运算。 套用公式

(书上28)

2 4 6 5 = 24 34 AB = 5 7 3 6 51 67 2010-12-28 17

本文来源：https://www.bwwdw.com/article/wunm.html