算法设计与分析习题解答1503

《算法设计与分析基础（第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 #include using namespace std;

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. 直接计算或许可以。