以下代码的输出是?( )
set<int> s; s.insert(5); s.insert(2); s.insert(8); for (int x : s) cout << x <<" ";
查看答案与解析
C++ 的 set 是有序且元素唯一的容器,默认升序。
以下代码的输出是?( )
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 是基于红黑树实现的有序关联容器,元素有序、不重复。
二分查找时,需要保证搜索序列是有序的,否则无法保证正确性。( )
二分查找基本要求是序列有序。
二分查找可以用于查找旋转数组中的元素。( )
旋转数组(如 [4,5,6,7,0,1,2])虽然整体不是有序的,但它由两个有序部分组成,可以通过二分查找的变体来查找元素。
递归程序书写不当可能导致栈溢出。( )
递归调用占用系统堆栈,不当调用会是调用层数过多导致栈溢出。
前缀和可以用于解决任意区间求最大值的问题。( )
前缀和主要用于快速计算区间和,但区间求最大值是另一类问题,前缀和无法直接用来求区间最大值。
模运算中,(a-b) % m 必然等于(a % m) - (b % m)。( )
例如:(5 - 3) % 4 = 2,但(5 % 4) - (3 % 4)=1-3=-2。
如果一个数列满足递推关系 an = 2*a(n-1) - 3 ,那么该数列是等差数列。( )
等差数列的定义是相邻项之差为常数。
an??a(n?1?)=2*a(n?1?)?3 - a(n-1)=a(n-1)-3,如果a(n-1)不是常数,则不是等差数列。
map 中的一个键不能对应两组数据。( )
在 C++ 的 map(和 unordered_map)中,每个键只能对应一个值,如果插入相同键的新值,会覆盖旧值。
map 的查找单个键的时间复杂度是 O(log n)。( )
在 C++ 中,map 是基于红黑树(平衡二叉搜索树)实现的,插入、删除、查找操作的时间复杂度都是 O(log n)。
set 的元素按大小降序排列。( )
默认情况下,C++ 的 set 是按 升序(从小到大)排列的。
set 的 insert 操作不会插入重复元素。( )
C++ 的 set 是有序且元素唯一的容器。
字符串的不同字串
题目描述
给定一个由小写英文字母组成的字符串 s。请问 s的不同非空子串有多少种?
子串是指字符串中连续的一段字符。例如,xxx 是 yxxxy 的子串,但不是 xxyxx 的子串。
输入
输入一行,包含一个字符串 s。
输出
输出一个整数,表示 s的不同非空子串的数量。
数据范围
s仅由小写英文字母组成。
1≤∣s∣≤100,其中 ∣s∣表示字符串的长度。
输入样例1
aababc
输出样例1
17
输入样例2
abracadabra
输出样例2
54
坐标选点
题目描述
修建了一条长度为 m 公里的铁路,起点和终点已经建有火车站。铁路沿线有 n 座城市(城市不位于起点或终点),第 i 座城市到铁路起点的距离为 ai 公里。
现在计划在这 n 座城市中选择 c 座修建火车站,使得所有火车站(包括起点和终点的火车站)之间的最小相邻距离尽可能大。请你计算这个最小相邻距离的最大可能值。
输入
第一行包含三个正整数n、c、m,分别表示城市数量、计划修建的火车站数量以及铁路总长度。
第二行包含n个正整数a1,a2,...,an,表示每座城市到铁路起点的距离。
输出
输出一个整数,表示最小相邻距离的最大可能值。
数据范围
1≤c≤n≤10^6,1≤ai<m≤10^9,输入中的所有数值均为整数。
输入样例1
5 3 10 1 2 8 4 9
输出样例1
2