第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