国科大的算法设计与分析相关1-5章复习题
第一章样例：
1.讲义习题一: 第1(执行步改为关键操作数)、第2、3、6、7题
习题一
1答：执行步4pmn+3pm+2m+1;关键操作2n*m*p
2方法一答：2n-2次
方法二答：2n-2次
3 1）证明：任给c，n>c,则10n2>cn 。不存在c使10n2<=cn,证毕。
2) 证明：任给c，当n>2c时，logn>c，从而n2logn>=cn2,同上。
6 答：logn，n2/3，20n，4n2，3n，n!
7 答：1)6+n 2) 3)任意n
2.讲义习题二：第5题。
答：c、e是割点。每点的DFN、L值：A1,1、B2,1、C3,1、D4,4、E5,1、F6,5、G7,5。最大连通分支CD、EFG、ABCE。
3.考虑下述选择排序算法：
输入：n个不等的整数的数组A[1..n]
输出：按递增次序排序的A
For i:=1 to n-1
For j:=i+1 to n
If A[j]<A[i] then A[i] A[j]
问：(1)最坏情况下做多少次比较运算？答1+2+..+n-1=n(n-1)/2
(2)最坏情况下做多少次交换运算？在什么输入时发生？
n(n-1)/2，每次比较都交换，交换次数n(n-1)/2。
4.考虑下面的每对函数f(n)和g(n) ,比较他们的阶。
(1) f(n)=(n2-n)/2, g(n)=6n (2)f(n)=n+2 , g(n)=n2
(3)f(n)=n+nlogn, g(n)=n (4)f(n)=log(n!), g(n)=
答：(1)g(n)=O(f(n)) (2)f(n)=O(g(n)
(3)f(n)=O(g(n) (4)f(n)=O(g(n)
5.在表中填入true或false . 答案：
f(n) g(n) f(n)=O(g(n) f(n)=(g(n)) f(n)=(g(n))
1 2n3+3n 100n2+2n+100 F T F
2 50n+logn 10n+loglogn T T T
3 50nlogn 10nloglogn F T F
4 logn Log2n T F F
5 n! 5n F T F
6.用迭代法求解下列递推方程：
(1)
(2) ,n=2k
答：(1)T(n)=T(n-1)+n-1=T(n-2)+n-2+n-1
=…=T(1)+1+2+…+n-1=n(n-1)/2=O(n2)
(2)T(n)=2T(n/2)+n-1=2(2T(n/4)+n/2-1)+n-1
=4T(n/4)+n-2+n-1=4(2T(n/23)+n/4-1)+n-2+n-1
=23T(n/23)+n-4+n-2+n-1
