Olympiad_in_Informatics/学习资料/《初赛真题解析》PPT课件/第2章 程序设计基础知识/第1节 程序基本常识/题目.md

1. 【NOIP2011 】在使用高级语言编写程序时， 一般提到的“ 空间复杂度”中的“ 空间”是指（ ） 。 A. 程序运行时理论上所占的内存空间B． 程序运行时理论上所占的数组空I,j] c ． 程序运行时理论上所占的硬盘空间D 鲁程序源文件理论上所占的硬盘空间
2. 【NOIP2013 】斐波那契数列的定义如下： f1 = 1, F2 = 1., F111 = Fn _ 1 + Fn _ 2 (n 之3)飞如果用下面 的函数计算斐波那契数列的第n 项，则其时间复杂度为（ ） 。 int F( i nt n){ if (n <= 2) return 1; else retur-1n IF (n 一1) + F(n - 2); } A.0(1) B.O(n) C.. O(n2) D 鲁O(Fn) 3 【NOIP2013 】T(n) 表示某个算法输入规模为n 时的运算次数。如果T (l) 为常数，且有递归式T(n) =2*T(n / 2) + 2n, 那么T (n) = ( )o A. ,o(n) B.O(n log n) C.0( 1n2) ID.. O·(n2 log n)

4 【NOIP2015 】设某算法的计算时间表示为递推关系式T ( n) = T(n - 1) + n(n 为正整数） 及T(0) = 1 则该符法的时间复杂度为( ) 。 A. 0 (log n ) B. 0 (n log n) C. 0 (n) D. 0 (n2) 5. 【NO IP201.S 】设某算法的时间复杂度函数的递推方程是T ( n) = T(n - 1) + n ( n 为正整数）及T (0) = 1 , 则该算法的时间复杂度为（ ） 。 A 昜O( l og 1n) B. O(n log n) C. 0(11) D. O(n2) 6 . 【NO IP2016 】假设某算法的计算时间表示为递推关系式 T(n) =2T （旦）＋ 5 4 T('l) = 1 则尊法的时间复杂度为（） 。 A. O(n) B.,0 （五） C. 0 （丘log 叶 7. 【NOIP 2 10 17 】若某算法的计算时间表示为递推关系式 T( IN) = 2T(N / 2) + N log N T(l) = 1 则该算法的时间复杂度为（） 。 A. O(N) B. O( NI log N),C. O(N log2 N) D. O(n2) ID.. O(N2)