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
问卷星提供技术支持
举报