算法分析的两个主要方面是时间复杂度和空间复杂度的分析。
(1分)
T
F
作者
DS课程组
单位
浙江大学
1-2
N
2
logN和NlogN
2
具有相同的增长速度。
(2分)
T
F
作者
DS课程组
单位
浙江大学
1-3
2
N
和N
N
具有相同的增长速度。
(2分)
T
F
作者
DS课程组
单位
浙江大学
1-4
100logN是O(N)的。
(1分)
T
F
作者
DS课程组
单位
浙江大学
1-5
(NlogN)/1000是O(N)的。
(1分)
T
F
作者
DS课程组
单位
浙江大学
1-6
在任何情况下，时间复杂度为O(n
2
) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。
(1分)
T
F
作者
干红华
单位
浙江大学
1-7
对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。
(1分)
下面代码段的时间复杂度是（）。
x=n; //n>1
y=0;
while( x≥(y+1)*(y+1) )
y++;
(2分)
A.
O(1)
B.
O(n
1/2
)
C.
O(n)
D.
O(log
2
n)
作者
周治国
单位
东北师范大学
2-2
下列代码
if ( A > B ) {
for ( i=0; i<N*N/100; i++ )
for ( j=N*N; j>i; j-- )
A += B;
}
else {
for ( i=0; i<N*2; i++ )
for ( j=N*3; j>i; j-- )
A += B;
}
的时间复杂度是：
(2分)
A.
O(N
3
)
B.
O(N
4
)
C.
O(N
5
)
D.
O(N
6
)
作者
徐镜春
单位
浙江大学
2-3
下列函数
int func ( int n )
{ int i = 0, sum = 0;
while ( sum < n ) sum += ++i;
return i;
}
的时间复杂度是：
(2分)
A.
O(logn)
B.
O(n
1/2
)
C.
O(n)
D.
O(nlogn)
作者
考研试卷
单位
浙江大学
2-4
下列代码
for(i=0; i<n; i++)
for(j=i; j>0; j/=2)
printf(“%d\n”, j);
的时间复杂度是：
(3分)
A.
O(N×i)
B.
O(N)
C.
O(N
2
)
D.
O(NlogN)
作者
DS课程组
单位
浙江大学
2-5
下面代码段的时间复杂度是（）。
x=0;
for( i=1; i<n; i++ )
for ( j=1; j<=n-i; j++ )
x++;
(2分)
A.
O(n)
B.
O(n
2
)
C.
O(n
3
)
D.
O(2
n
)
作者
周治国
单位
东北师范大学
2-6
要判断一个整数N（>10）是否素数，我们需要检查3到√
N
之间是否存在奇数可以整除N。则这个算法的时间复杂度是：
(2分)
A.
O(N/2)
B.
O(√
N
)
C.
O(√
N
logN)
D.
O(0.5logN)
作者
徐镜春
单位
浙江大学
2-7
下列函数中，哪个函数具有最慢的增长速度：
(2分)
A.
N
1.5
B.
NlogN
2
C.
N
2
logN
D.
N(logN)
2
作者
DS课程组
单位
浙江大学
2-8
给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：
(2分)
A.
O(N
2
)
B.
O(NlogN)
C.
O(N
3
logN)
D.
O(N
3
)
作者
DS课程组
单位
浙江大学
2-9
计算机算法指的是（）。
(2分)
A.
计算方法
B.
排序方法
C.
解决问题的有限运算序列
D.
调度方法
作者
严冰
单位
浙江大学城市学院
2-10
计算机算法必须具备输入、输出和（）等五个特性。
(2分)
A.
可行性、可移植性和可扩充性
B.
可行性、确定性和有穷性
C.
确定性、有穷性和稳定性
D.
易读性、稳定性和安全性
作者
严冰
单位
浙江大学城市学院
6-1 爆内存函数实例 (6分)
本题要求实现一个递归函数，用户传入非负整型参数n，用户依次输出1到n之间的整数。所谓递归函数就是指自己调用自己的函数。
说明：
（1）递归函数求解问题的基本思想是把一个大规模问题的求解归结为一个相对较小规模问题的求解，
小规模归结为小小规模，以此类推，直至问题规模小至边界（边界问题可直接求解）。递归函数由两
部分组成，一部分为递归边界，另一部分为递归关系式。以求阶乘函数为例，递归边界Factorial(1)=1;
递归公式： Factorial(n)=n*Factorial(n-1)，它对应的递归函数如下：
int GetFactorial(int n){
int result;
if(n==1) result = 1; //递归边界，此时问题答案易知，可直接求解
else result =n* GetFactorial(n-1); //递归关系，大问题求解归结为小问题求解
return result;
}
(2) 发生函数递归调用（自己调用自己）或者普通函数调用时，系统需要保存调用发生前的执行场景信
息（包括调用发生前的各个变量取值信息以及函数执行位置等），以便被调函数执行完毕后可以顺利返
回并继续执行后续操作。每次调用都需要保存一个场景信息，保存这些场景信息需要的辅助空间的大小
与函数调用的次数呈正比，或者说其空间复杂度是O(n)，当中n为调用次数。
(3)本例的目的是让学生编写一个递归函数，并在自己的机器上测试递归调用次数达到多少时会发生内存
被爆而出现内存溢出的错误（我办公室机器上设置参数为66000时会溢出）。同样的这个问题，如果不
用递归函数而改用普通的循环语句解决问题，则不会出现内存溢出！
函数接口定义：
void PrintN (long n);
其中n为用户传入的参数。
裁判测试程序样例：
在这里给出函数被调用进行测试的例子。例如：
#include <stdio.h>
void PrintN(long n);
int main()
{
PrintN(66000L);
return 0;
}
/* 请在这里填写答案 */
输入样例：
5
输出样例：
12345
