DS_Complexity
1-1
解决问题的效率，跟数据的组织方式无关。
F
1-2
抽象数据类型中，描述数据类型的方法与数据存储的物理结构有关。
F
1-3
抽象数据类型中，描述数据类型的方法与实现操作的算法和编程语言无关。
T
1-4
对应同一个数据结构，可以有不同的实现方法。
T
1-5
(NlogN)/1000是O(N)的。
F
1-6
斐波那契数列FN的定义为：F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, …。用递归函数计算FN的空间复杂度是O(N)。
T
1-7
斐波那契数列FN的定义为：F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, …。用循环函数计算FN的时间复杂度是Θ(FN).
F
1-8
算法可以没有输入，但是必须有输出。
T
1-9
空间复杂度是根据算法写成的程序在执行时占用存储单元的长度，往往与输入数据的规模有关。
T
1-10
递归程序往往简洁易懂，但占用较大空间。递归层数过大会造成系统堆栈溢出。
T
2-1
下列函数中，哪两个函数具有相同的增长速度：
A.2N和NN
B.N和2/N
C.N2logN和NlogN2
D.NlogN2和NlogN
2-2
给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：
A.O(N2)
B.O(NlogN)
C.O(N2logN)
D.O(N3)
2-3
给定程序时间复杂度的递推公式：T(1)=1，T(N)=2T(N/2)+N。则对该程序时间复杂度最接近的描述是：
A.O(logN)
B.O(N)
C.O(NlogN)
D.O(N2)
2-4
与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。
A.存储结构
B.存储实现
C.逻辑结构
D.运算实现
2-5
通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。
A.数据在同一范围内取值
B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C.每个数据元素都一样
D.数据元素所包含的数据项的个数要相等
2-6
下面的程序段违反了算法的（）原则。
void sam()
{ int n=2;
while (n%2==0) n+=2;
printf(“%d”,n);
}
A.有穷性
B.确定性
C.可行性
D.健壮性
2-7
T(n)表示当输入规模为n时的算法效率，以下算法中效率最优的是( )。
A.T(n)=T(n-1)+1,T(1)=1
B.T(n)=2n2
C.T(n)=T(n/2)+1,T(1)=1
D.T(n)=3nlog2n
2-8
下列程序段的时间复杂度是
int sum = 0;
for(int i=1;i<n;i*=2)
for(int j=0;j<i;j++)
sum++;
A.O(logn)
B.O(n)
C.O(nlogn)
D.O(n2)
2-9
空间复杂度分析(阶乘，循环+动态数组版)
下面算法的空间复杂度为 ▁▁▁▁▁。
double Fac(int n)
{
int k;
double p, *a;
a = (double*)malloc((n + 1) * sizeof(double));
a[0] = 1.0;
for (k = 1; k <= n; ++k)
{
a[k] = a[k - 1] * k;
}
p = a[n];
free(a);
return p;
}
A.O(n)
B.O(2n)
C.O(n2)
D.O(1)
2-10
设 0≤i,k<n，下面这段代码的时间复杂度是：
if (i>k) {
for (j=i; j<n; j++)
a[j] = a[j-k]+1;
}
else {
for (j=i; j>0; j--)
a[j] = a[k-j]+2;
}
A.O(n)
B.Θ(kn)
C.Ω(n)
D.Θ(nlogn)