第1章 算法
一、选择题
1. 算法的时间复杂度是指（ ）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数
C）算法执行过程中所需要的基本运算次数 D）算法程序的长度
2. 算法的空间复杂度是指（ ）。 A）算法程序的长度
B）算法程序所占的存储空间
C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数
3.下面（ ）的时间复杂度最好（即执行时间最短）。
A）O(n ) B）O(log2n) C）O(nlog2n ) D）O(n)
2
4.下面累加求和程序段的时间复杂度为（ ）。 int sum(int a[],int n) {
int i, s=0;
for (i=0;i 5.下面是将两个n阶矩阵a[][]与b[][]相加的结果存放到n阶矩阵c[][]中的算法，该算法的时间复杂度为（ ）。 void matrixadd(int a[][],int b[][],c[][],int n) { int i,j; for (i=0;i for(j=0;j c[i][j]=a[i][j]+b[i][j]; } A）O(1 ) B）O(log2n) C）O( n ) D）O(n) 6.下面程序段的时间复杂度为（ ）。 1 2 2 int i=0,s1=0,s2=0; while(i if(i%2) s1+=i; else s2+=i; i++; } A）O(1 ) B）O(log2n ) C）O(n ) D）O(n) 7.下面程序段的时间复杂度为（ ）。 int prime(int n) { int i=1; int x=(int)sqrt(n); while(i<=x) { i++; if(n%i==0) break; } if(i>x) return 1; else return 0; } A）O(1 ) B）O(log2n) C）O(n ) D）O(n) 8.下面程序段的时间复杂度为（ ） int fun(int n) { int i=1,s=1; while(s i++; s+=i; } return i; } A）O(n/2) B）O(log2n) 2 2 C）O(n ) D）O(n) 9.下面程序段的时间复杂度为（ ） int i,j,m,n,a[][]; for(i=0;i A）O(m) B）O(n) C）O(m*n ) D）O(m+n) 10. 下面程序段的时间复杂度为（ ） int sum1(int n) { int i,p=1,s=0; for(i=1;i<=n;i++) { p*=i; s=s+p; } return s; } A）O(1 ) B）O(log2n) C）O(n ) D）O(n) 二、填空题 1.算法复杂度主要包括时间复杂度和 复杂度。 2.一个算法的时间复杂度的计算式为 ( 3n+2n+5 ) / n ，其数量级表示为 。 3.从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂度为 ，读取一个二维数组b[m][n]中任一元素的时间复杂度为 。 4.在下面程序段中，s = s+p语句的执行次数为 ，p*=j 语句的执行次数为 ，该程序段的时间复杂度为 。 int i=0, s=o; while(++i <=n) { int p=1; for(int j=1; j<=i ; j++ ) p*=j ; s=s+p ; } 5. 通常用平均性态分析和 两种方式来确定一个算法的工作量。 三、 简答题 3. 什么是算法？ 4. 算法的基本特征是什么？ 2 2 2 2 3 5. 算法的两种基本要素是什么？ 6. 递归是算法的基本方法之一，其基本思想是什么？ 7. 算法的描述方法有多种，试说出任意三种方法。 四、编写出求下列问题的算法 1.比较两个整型数据a1与a2的大小，对于a1 > a2、a1 == a2、a1< a2这三种不同情况应分别返回“>”、“=”、“<”字符。 2.求一维double型数组a[n]中的所有元素之乘积。 3.假定一维整型数组a[n]中的每个元素值x均在[0，200]区间内，分别统计出落在0≤x < 20、20≤x<50、50≤x<80、80≤x<130、13 ≤x≤200各区间内的元素个数。 参考答案 一、单选题 1.C 2.C 3.B 4.C 5.D 6.C 7.D 8.D 9.C 10.C 二、填空题 1. 空间 2. O(n) 3.O(n)，O(1) 4. n，n(n+1)/2，O(n) 5. 最坏情况复杂性 三、简答题 1. 答案：所谓算法是指解题方案的准确而完整的描述。 2. 答案：算法的基本特征为：1)可行性；2)确定性；3)有穷性；4)拥有足够的情报。 3. 答案：算法通常由两种基本要素组成；一是对数据对象的运算和操作；二是算法的控制结构。 4. 答案：人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解。而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。 5.答案：一个算法可以用多种方式来描述，如自然语言、程序语言、流程图等。 四、算法设计 1.比较两个整型数据a1与a2的大小。 char compare(int a1,int a2) { if(a1>a2) return \elase if(a1==a2) return \ 4 2 elase return \} 2.求一维double型数组a[n]中的所有元素之乘积。 double product(dluble a[],int n) { double p=1; for(int i=0;i< n;i++) p=p*a[i]; return p; } 3.统计数组a[n]中的每个元素值x分别落在0≤x<20、20≤x<50、50≤x< 80、80≤x<130、130≤x≤200各区间内的元素个数。 int count(int a[],int n,int c[5]) //用c[5]保存统计结果 { int d[5]={20,50,80,130,201}; //用d[5]保存各统计区间上限 int i,j; for(i=0;i if(a[i]<0; || a[i]>200) return 0; //数组中数据有错，统计失败 for(j=0;j< 5;j++) if(a[i] c[j]++; //使统计相应区间的元素数增1 } return 1; //表示统计成功 } 5