國科大的算法設計與分析相關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使10n22c時，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