CSP初赛 第9节 程序基本常识

第二章 程序设计基础知识
本题库配套信息学奥赛一本通（初赛真题解析）第51页-第53页真题在线评测。
本套题目共7题，满分35分。
需要下载错题集微信联系tony老师：makytony
*
您的姓名：
一、单项选择题（共7题，每题5分，共计35分;每题有且仅有一个正确选项）
*
1.在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。
A. 程序运行时理论上所占的内存空间
B. 程序运行时理论上所占的数组空间
C. 程序运行时理论上所占的硬盘空间
D. 程序源文件理论上所占的硬盘空间
*
2.斐波那契数列的定义如下:



如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（）。



A.O(1)
B.O(n)
C.O(n*n)
D.O(F(n))
*
3.T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式T(n) = 2*T(n / 2) + 2n，那么T(n) = （）。
A.Θ(n)
B.Θ(n log n)
C.Θ(n2)
D.Θ(n2 log n)
*
4.设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n(n为正整数)及T(0) = 1，则该算法的时间复杂度为（）。
A.O(log n)
B.O(n log n)
C.O(n)
D.O(n2)
*
5.假设某算法的计算时间表示为递推关系式,



则算法的时间复杂度为（）。*
A. O(𝑛)
B. O(√𝑛)
C. O(√𝑛 log 𝑛)
D. O(𝑛2)
*
6.若某算法的计算时间表示为递推关系式:
T(N) = 2T(N / 2) + N log N
T(1) = 1
则该算法的时间复杂度为（ ）。*
A. O(N)
B. O(N log N)
C. O(N log2 N)
D. O(N^2)
*
7.如果对于所有规模为n的输入，一个算法均恰好进行（）次运算，我们可以说该算法的时间复杂度为O(2n)。

A.2^n+1
B.3^n
C.n*2^n
D.2^2n
问卷星提供技术支持
举报