二、综合题（选自教材《数据结构》各章习题，采用word文件格式上传） 【1，1，3】试分析下面一段代码的时间复杂度：
if ( A > B ) {
for ( i=0; i for ( j=N*N; j>i; j-- ) A += B; } else { for ( i=0; i for ( j=N*2; j>i; j-- ) A += B; } 答： if A>B为真，则for语句的外循环N次，内循环为N（N-1）次，因此时间复杂度为O(N* N（N-1）)，也就是N的三次方。 if A>B为假，则for语句的外循环2N次，内循环为N次，因此时间复杂度为O（2N*N），也就是N的平方。 整段取最大的，时间复杂度就是N立方。 【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令f(x)?1?利用clock()函数得到两种算法在同一机器上的运行时间。 答： 直接法：0.1μ s 秦九韶算法：0.04μ s 【3，1，3】 试分析最大子列和算法1.3的空间复杂度。 答： 算法1.3的基本思路是将原问题拆分成若干小型问题，分别解决后再将结果合而治之，用递归方法实 6 ?100ix/i，计算f(1.1)的值。i?1现。 算法1.3的负责度分析略有难度：若记整体时间复杂度为T(N)，则函数DivideAndConquer中通过递归实现“分”的复杂度为2T(N/2)，因为我们解决了2个长度减半的字问题。求跨分界线的最大子列和时，有两个简单的for循环，所用步骤一共不超过N，所以可以在O(N)时间完成。其他步骤都只需常熟O(1)时间。 综上分析则有递推式： T(1)=O(1)； T(N)=2T(N/2)+O(N) =2[2T((N/2)/2+O(N/2)]+O(N)=2T(N/2)+2O(N) =?=2T(N/2)+kO(N) 当不断对分直到N/2=1,即2=N时，就得到T(N)=NT(1)+logN*O(N)=O(N log N)。此算法比算法1.2又快了一些，当N=10时，效果会非常明显。但是这仍然不是最快的算法。 【4，1，3】试给出判断N是否为质数的O(答: int sushu(int N) { int i; int flag=1; if (N==1) return false; //1既不是合数也不是质数 if (N==2) return true for (i=2;i<=sqrt(N);i++) { if (N%i==0) 7 4 k k K k 2 2 N)的算法。 { flag=0； break; } } return flag; } 【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+?＋aa?a(n个a)的结果。 答： #include\int main() { int a,b,n,i,s=0; scanf(\ b=a; for(i=1;i<=n;i++) { s+=a; a=a*10+b; } printf(\} 【6，2，3】请编写递归函数，输出123..n的全排列（n小于10）,并观察n逐步增大时程序的运行时间。 8 答： #include void swap(int *a, int *b) { int m; m=*a; *a=*b; *b=m; } void perm(int list[], int k, int m) { int i; if(k > m) { for(i = 0; i <= m; i++) printf(\ printf(\ n++; 9 } else { for(i = k; i <= m; i++) { swap(&list[k],&list[i]); perm(list,k + 1, m); swap(&list[k],&list[i]); } } } int main() { int list[N]; int num,i=0; printf(\ scanf(\ while(num != 0) { list[i]=num; 10