第一章 绪论作业答案（共 50 分） 一、分析如下程序中 (1)~ (10)各语句的频度（每个 1 分，共 10 分） Ex( ) { (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i , j int for( i=1 ; i<10 ; i++) , t ; printf(“\n %d” , i ); for(i=1; i<=2; i++) printf(“\n”); for(i=1; i<=9; i++) { for(j=1; j <= i ; j++) { //n =10 //n =9 //n =3 //n =2 //n =10 //n =54 t = i * j ; printf(“%5d”,t); //n =45 //n =45 } for(j=1; j<3 ; j++) printf(“\n”); //n =27 //n =18 } } 二、分析如下程序段中指定语句的执行次数（共 6 分）。 有如下程序段： x = 91 ; y = 100 ; while(y > 0) { if(x > 100) {x -= 10 ; y -- ;} else x ++ ; } 问 if 语句执行了多少次？（2 分） y--执行了多少次?（2 分） x ++执行了多少次?（2 分） 1100 100 1000 三、回答问题（共 25 分） 书中 16 页的起泡排序如下： void bubble_sort(int a[],int n){ //将 a 中整数序列重新排列成自小至大有序的整数序列。 for(i=n-1,change=TRUE;i>=1&&change;--i){ change=FALSE; for(j=0;ja[j+1]{a[j]<-->a[j+1];change=TRUE; } } 

}//bubble_sort 1.（共 15 分）分析该算法的最佳情况 ，最坏情况和平均情况下各自的时间复杂度（给出分 析思路与过程）。 (1)最佳情况的时间复杂度分析（5 分）：此种情况下的时间复杂度为 O（n）或 O(1)，即 数据本身不需要进行排序，如果以比较为原操作，时间复杂度为 O（n），以交换为原操作 的话则为 O(1)。 (2)最坏情况的时间复杂度分析（5 分）：此种情况下的时间复杂度为 O（n^2），即数据 全部需要进行排序，时间复杂度为 O（n(n-1)/2）=O(n^2)。 (3)平均情况的时间复杂度分析（5 分）：此种情况下的时间复杂度为 O（n^2），（因为 严格的数学分析较复杂，可以不给出分析思路）。 2.（共 10 分）比较与 C 语言书中的起泡排序异同，并从时空效率角度说明谁更优。 就时间效率而言，数据结构中的方法是：遇到上一次从未发生交换时，则功能函数运行 结束，而 C 语言的方法是都需要将数据全部逐个进行比较。因此，在最坏情况下（逆序）时， 两种方法运行过程一样；在最好情况下（正序时），数据结构的方法只会将外循环运行一次， 即结束功能函数，不再运行，而 C 语言的方法则不是，需要外循环运行 n-1 次，而实际上 只是比较，没有发生一次交换。 就空间效率而言，该算法相比 C 语言程序多定义一个变量，所占内存空间更多。 四、完成如下选择题（每空 3 分，共 9 分）。 1. 设 f 为原操作，则如下算法的时间复杂度是（ D ）。 for (i = 1; i*i<= n; i++) f; A.O(n) B. O( log2n ) C. O(n/ 2) D. 都不对 2. 算法的时间复杂度与（ A ）有关。 A．问题的规模 C．编译程序的质量 B．计算机硬件性能 D．程序设计语言 3．有程序段： for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) if(A[j]>A[j+1]) A[j]与 A[j+1]对换; 其中 n 为正整数，则算法在最坏情况下的时间复杂度为（ D ）。 A．O(n) D. O(n2) B．O(nlog2n) C. O(n3)