1.  [S-2023-3]假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 m=Θ(n) 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

 A. $O(m*\sqrt{logn}*loglogn)$
 B. $O(n^2+m)$
 C. $O(n^2/logm+mlogn)$
 D. $O(m+nlogn)$
2. [J-2011-12][S-2011-6]在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。
 A. 程序运行时理论上所占的内存空间
 B. 程序运行时理论上所占的数组空间
 C. 程序运行时理论上所占的硬盘空间
 D. 程序源文件理论上所占的硬盘空间
3. [S-2013-7]斐波那契数列的定义如下：F1=1, F2=1, Fn = Fn-1 + Fn-2 (n≥3) 。如果用下面的函数计算斐波那契数列的第 n 项，则其时间复杂度为（ ）。
int F(int n) 
{ 
 if (n <= 2) 
  return 1; 
 else 
  return F(n - 1) + F(n - 2); 
}
 A. O(1)  B. O(n)   C. O(n²)    D. O(Fn)
4. [S-2016-14]假设某算法的计算时间表示为递推关系式
T(n)=2T(n/4)+sqrt(n)
T(1)=1
则算法的时间复杂度为（ ）。
A.$O(n)$               B. $O(\sqrt{n})$
C.$O(\sqrt{n}*log n)$     D. $O(n^2)$
5. [S-2013-15]T(n) 表示某个算法输入规模为 n 时的运算次数。如果 T(1) 为常数，且有递归式 T(n)=2T(n/2)+2n，T(n)= （ ）。
A.$O(n)$     B.$O(nlogn)$
C.$O(n^2)$   D.$O(n^2 logn)$
6. [S-2012-11]如果对于所有规模为 n 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 $O(2^n)$
 A. $2^n+1$     B. $3^n$ 
 C. $n×2^n$     D. $2^{2n}$
7. [S-2014-15]以下程序实现了找第二小元素的算法。输入时 n 个不等的数构成的数组 S，输出 S 中第二小的数 SecondMin。在最坏的情况下，该算法需要做（ ）次比较。
if ( S[1] < S[2] )
{
FirstMin = S[1];
SecondMin = S[2];
} else {
FirstMin = S[2];
SecondMin = S[1];
}
for ( i = 3; i <= n; i++ )
if ( S[i] < SecondMin )
if ( S[i] < FirstMin )
{
SecondMin = FirstMin;
FirstMin = S[i];
} else {
SecondMin = S[i];
}

 A. 2n     B. n-1
 C. 2n-3    D. 2n-2
8. [S-2013-19]（多选）（ ）属于 NP 类问题。
 A. 存在一个 P 类问题
 B. 任何一个 P 类问题
 C. 任何一个不属于 P 类的问题
 D. 任何一个在（输入规模的）指数时间内能够解决的问题
9. [S-2023-15]现在用如下代码来计算 $x^n$，其时间复杂度为（）。
double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2)
        * quick_power(x, n / 2)
        * ((n & 1) ? x : 1);
}
 A. O(n)
 B. O(1))
 C. O(log n)
 D. O(nlogn)
10. [S-2018-8]关于 Catalan 数 C_n = (2n)!/((n + 1)!n !)，下列说法中错误的是（ ）。
 A. C_n表示有 n+1 个结点的不同形态的二叉树的个数。
 B. C_n表示含 n 对括号的合法括号序列的个数。
 C. C_n表示长度为 n 的入栈序列对应的合法出栈序列个数。
 D. C_n表示通过连接顶点而将 n + 2 边的凸多边形分成三角形的方法个数。