一、单项选择题（共7题，每题5分，共计35分;每题有且仅有一个正确选项）

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

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

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

{{ select(2) }}

• O(1)
• O(n)
• O(n2)
• O(Fn)

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

• Θ$(n)$
• Θ$(n log 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(n/4)+\sqrt{n}$ $T(1)=1$

则算法的时间复杂度为（）。{{ select(5) }}

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

6.若某算法的计算时间表示为递推关系式: $T(N) = 2T(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(2n)。 {{ select(7) }}

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