国科大算法设计与分析2017-2018作业与答案.zip

国科大算法设计与分析2017-2018作业与答案.zip
国科大的算法设计与分析相关1-5章复习题第一章样例：1.讲义习题一:第1(执行步改为关键操作数)、第2、3、6、7题习题一1答：执行步4pmn+3pm+2m+1;关键操作2n*m*p2方法一答：2n-2次方法二答：2n-2次31）证明：任给c，n＞c,则10n2＞cn。
不存在c使10n22c时，logn＞c，从而n2logn＞=cn2,同上。
6答：logn，n2/3，20n，4n2，3n，n!7答：1)6+n2)3)任意n2.讲义习题二：第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]输出：按递增次序排序的AFori:=1ton-1Forj:=i+1tonIfA[j]＜A[i]thenA[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))12n3+3n100n2+2n+100FTF250n+logn10n+loglognTTT350nlogn10nloglognFTF4lognLog2nTFF5n!5nFTF6.用迭代法求解下列递推方程：(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 本软件ID:11755941