狄斯奎诺算法 c语言,算法设计与分析期末复习题【试题.知识点】（11页）

狄斯奎诺算法 c语言,算法设计与分析期末复习题【试题.知识点】（11页）

算法设计与分析期末考试复习题

1．算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的

算法?

2．证明下面的关系成立：(参考例题1.5--1.6)

n n+1

(1)logn!=Θ (nlogn) (2)2=Θ (2 )

n 2 2

(3)n!= Θ (n) (4)5n-6n=Θ (n)

1

3.考虑下面的算法：

输入：n 个元素的数组A

输出：按递增顺序排序的数组A

1. void sort(int A[],int n)

2. {

3. int i,j,temp;

4. for(i=0;i

5. for(j=i+1;j

6. if(A[j]

7. temp=A[i];

8. A[i]=A[j];

9. A[j]=temp;

10. }

11. }

(1) 什么时候算法所执行的元素赋值的次数最少？最少多少次？

(2 ) 什么时候算法所执行的元素赋值的次数最多？最多多少次？

4.考虑下面的算法：

输入：n 个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n)

2. {

3. int j,i,sorted;

4. i=sorted=0;

5. while(i

6. sorted=1;

7. for(j=n-1;j>i;j--) {

8. if(A[j]