1. 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。 {{ select(1) }}

• 程序运行时理论上所占的内存空间
• 程序运行时理论上所占的数组空间
• 程序运行时理论上所占的硬盘空间
• 程序源文件理论上所占的硬盘空间

2. 斐波那契数列的定义如下：$F_1=1,F_2=2,F_n=F_{n-1}+F_{n-2}(n>=3)$ 如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（）。

int F(int n)
{
    if(n<=2)
        return 1;
    else 
        return F(n-1)+F(n-2);
}

{{ select(2) }}

• O(1)
• O(n)
• O($n^2$)
• O(Fn)

3. $T(n)$表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式$T(n) = 2*T(\frac n 2) + 2n$，那么$T(n)$ = （）。 {{ select(3) }}

• Θ(n)
• Θ($nlog^n$)
• Θ($n^2$)
• Θ($n^2 log^n$)

4. 设某算法的计算时间表示为递推关系式$T(n) = T(n - 1) + n(n$为正整数)及$T(0) = 1$，则该算法的时间复杂度为（）。 {{ select(4) }}

• O($log^n$)
• O($n log^n$)
• O($n$)
• O($n^2$)

5. 假设某算法的计算时间表示为递推关系式 $T(n)=2T(\frac n 4)+\sqrt n$ ,$T(n)=1$ 则算法的时间复杂度为( )。。 {{ select(5) }}

• O(𝑛)
• O($\sqrt n$)
• O($\sqrt n log ^n$)
• O($𝑛^2$)

6. 若某算法的计算时间表示为递推关系式： $T(N) = 2T(\frac N 2) + N log^N$, $T(1) = 1$ 则该算法的时间复杂度为（）。。 {{ select(6) }}

• O($N$)
• O($N log^N$)
• O($N log_2 ^N$)
• O($N^2$)

7. 如果对于所有规模为n的输入，一个算法均恰好进行（）次运算，我们可以说该算法的时间复杂度为O($2^n$)。 {{ select(7) }}

• $2^{n+1}$
• $3^n$
• $n*2^n$
• $2^{2^n}$