《算法设计与分析基础（第3版）》习题解答
第一章 绪论
第6页 习题1.1 5
SameElement( a[0..m-1],b[0..n-1] )
// find same elements in sorted array a[m] and b[n] i=0;j=0;
While i if ( a[i] > b[j] ) j++ else if ( a[i] { cout< i++;j++; } } 最大比较次数应该是，两个列表中没有相同的元素;并且a数组所有元素全部大于b数组元素，或a数组所有元素全部小于b数组时候，比较次数最大； 此时 最大比较次数应该是：m*n 实现程序 // same element //#include \#include void main() { int a[]={ 2,5,5,5 }; int b[]={2,2,3,5,5,7}; int i=0,j=0,m=4,n=6; while ( i if ( a[i] > b[j] ) j++; else if ( a[i] { cout< } cout<<\} 第6页 习题1.1 6 a. gcd(31415,14142)= gcd(14142,31415 mod 14142) =gcd(14142,3131)=gcd(3131,1618) =gcd(1618,1513)=gcd(1513,105) =gcd(105,43)=gcd(43,19) =gcd(19,5)=gcd(5,4) =gcd(4,1)=gcd(1,0)=1 b. 由上述计算可以知道： gcd运算次数= 11 次 Min(m,n)运算次数=14141次 倍数=14141/11=1286 倍 第14页 习题1.2 8 例如：排序问题，算法很多，有插入排序、冒泡排序、快速排序等等。 其中：快速排序性能较佳。 第20页 习题1.3 1 a. 过程：S 输出：14 35 47 60 81 98 b. 不稳定，因为当两数相等的时候，原排在前面的数，会移动到后面去 c. 不在位，因为它需要额外的空间S. 第29页 习题1.4 1 a. 将最后一个元素移到此位置。 // 将i后面的元素向前移一位。 b. 该位置的元素置为一个不可能的字符。 //从第i个元素开始往后，将比他大的元素往前移一位，直到最后。 第二章 算法效率分析基础 第39页 习题 2.1 2 解答: a. 基本操作是加法运算， 以矩阵阶数来表示：f(n)= n2 若元素个数为m, 则以矩阵元素个数来表示：f(m)= m b 对于矩阵乘法运算基本操作是乘法运算： 以矩阵阶数来表示：f(n)= n3 若元素个数为m, 以矩阵元素个数来表示：f(n)= m* ∠m 第39页 习题 2.1 3 解答: 有差异. 每次查找运算需要比较所有的元素，他的效率与经典顺序查找算法的最差效率相同。 第46页 习题 2.2 1 a. Q(n) b. 1 c. n/2 第46页 习题 2.2 2 a. T b. T c. F d. T 第46页 习题2.2 4 a. 是的， b. 用极限的方法来证明。 第52页 习题2.3 4 a. 求和 ∑n2 b 基本操作是乘法运算 c 基本操作执行了 n次 d. 效率类型是 线性阶 e. 直接计算或许可以。 第三章 蛮力法 第79-80页 习题3.1 8 11 8. 原始顺序：A E(前） E（后） L M P X 选择排序结果： E(前） X A M P L E(后） 选择排序过程： E(前） X A M P L E（后） A X E(前） M P L E（后） A E(前） X M P L E（后） A E(前） E（后） M P L X A E (前）E（后） L P M X A E(前） E（后） L M P X A E(前） E（后） L M P X A E(前） E（后） L M P X 11. 原始顺序：A E(前） E（后）冒泡排序结果： A E(前） E（后） L M P X 冒泡排序过程： E(前） X A M P L E（后） E(前） A X M P L E（后） E(前） A M X P L E（后） E(前） A M P X L E（后） E(前） A M P L X E（后） E(前） A M P L E（后） X A E(前） M P L E（后） X A E(前） M P L E（后） X A E(前） M L P E（后） X A E(前） M L E（后） P X L M P X