C/C++编程五级 题库
有递推公式`f(n) = 2*f(n-1) + 1`,`f(1)=1`,则`f(4)`的值是?( )
以下关于贪心算法的说法,正确的是?( )
已知数组`arr[6] = {2,4,6,8,10,12}`,前缀和数组`preSum[0]=0`,`preSum[i] = arr[0]+arr[1]+…+arr[i-1]`,则区间[2,4](下标从0开始)的元素和为?( )
对原数组的区间[l, r]全部加上val,对差分数组的操作是?( )
在长度为n的有序数组中,二分查找的最坏时间复杂度是?( )
以下哪个STL容器是基于红黑树实现的,元素自动有序且不重复?( )
STL中,用于在容器中查找指定元素的函数是?( )
以下关于`vector`容器的说法,错误的是?( )
以下代码的输出是?( )
set<int> s; s.insert(5); s.insert(2); s.insert(8); for (int x : s) cout << x <<" ";
C++ 的 set 是有序且元素唯一的容器,默认升序。
以下代码的输出是?( )
int f[10];
f[0] = 0;
f[1] = 1;
for (int i = 2; i<10; i++){
f[i] = f[i-1] + f[i-2];
}
cout << f[8];斐波那契序列,各项为:0 1 1 2 3 5 8 13 21 34,所以f[8]为21。
计算斐波那契序列应使用哪种算法?( )
递推:用循环从前往后计算,时间复杂度 O(n),效率高,是标准做法。
在一个有序序列里,二分查找一个给定的键值,算法的时间复杂度是?( )
二分查找每次将查找范围缩小一半,时间复杂度为 O(log n)。
以下代码的时间复杂度为?( )
for(int step=1; step<n; step=step*2){
std::cout <<step<<"\n";
}循环变量 step 从 1 开始,每次乘以 2,直到不再小于 n。
循环停止条件:2^{k-1} < n,可以推出: k-1 < log n,因此时间复杂度是 O(log n)。
以下代码的输出是?( )
int f(int n) {
if(n == 0) return 2;
return n*f(n-1);
}
int main() {
cout << f(3);
}调用f(3)时,递归调用:3*f(2),f(2)=2*f(1),f(1)=1*f(0);
f(0)=2,所以f(1)=2,f(2)=2*2=4,f(3)=3*4=12。
若 pre[i] = a[1] + … + a[i],则能表示 a[3] 到 a[9] 的和公式是?( )
pre[9]为:a[1]+a[2]+……+a[9],a[3]前面是a[1]+a[2](即:pre[2]),则a[3]到a[9]是:pre[9]-pre[2]。
以下代码的输出是?( )
map<string, int> m; m["apple"]= 5; m["banana"] = 3; cout << m["apple"];
map 是 C++ 标准模板库的字典,m["apple"] 的值已经设为 5,输出为:5。
查找键 "key" 是否存在,正确的代码是?( )
find() 返回迭代器,如果等于 end() 说明没找到,否则存在。
count() 对于 map 返回 0 或 1,可以判断键是否存在。
set 的组织特点是?( )
C++ 中的 set 是基于红黑树实现的有序关联容器,元素有序、不重复。