GESP-C++五级 题库
下面代码用分治求“最大连续子段和”,其时间复杂度为( )。
int solve(vector<int>& a, int l, int r){
if(l == r) return a[l];
int mid = l + (r - l) / 2;
int left = solve(a, l, mid);
int right = solve(a, mid + 1, r);
int sum = 0, lmax = INT_MIN;
for(int i = mid; i >= l; i--){
sum += a[i];
lmax = max(lmax, sum);
}
sum = 0;
int rmax = INT_MIN;
for(int i = mid + 1; i <= r; i++){
sum += a[i];
rmax = max(rmax, sum);
}
return max({left, right, lmax + rmax});
}游戏大赛决赛,两组选手分别按得分从小到大排好队,现在要把他们合并成一个有序排行榜。
A组: A = {12, 35, 67, 89} ,B组: B = {20, 45, 55, 78} ,下面是归并合并函数的核心循环,横线处应填入( )。
int i = 0, j = 0;
vector<int> result;
while (i < A.size() && j < B.size()) {
if (A[i] <= B[j]) {
result.push_back(A[i++]);
} else {
result.push_back(B[j++]);
}
}
while (i < A.size()) {
result.push_back(A[i++]);
}
while (j < B.size()) {
result.push_back(B[j++]);
}有 位同学的成绩已经从小到大排好序,现在对它执行下面这段以第一个元素为 pivot 的快速排序,请问此次排序的时间复杂度是( )。
下面关于排序算法的描述中,不正确的是( )。
下面代码实现两个整数除法,其中被除数为一个“大整数”,用字符串表示,除数是一个小整数,用 int 表 示,则横线处应该填写( )。
int main(){
string s;
int b;
cin >> s >> b;
vector<int> a;
for(char c : s){
a.push_back(c - '0');
}
vector<int> c;
long long rem = 0;
for(int i = 0; i < a.size(); i++){
rem = rem * 10 + a[i];
int q = rem / b;
c.push_back(q);
---------------------
}
int pos = 0;
while(pos < c.size() - 1 && c[pos] == 0) pos++;
for(int i = pos; i < c.size(); i++){
cout << c[i];
}
cout << endl;
cout << rem << endl;
return 0;
}数组和链表都是线性表。链表的优点是插入删除不需要移动元素,并且能随机查找。
假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。
在单链表中,已知指针 p 指向要删除的结点(非尾结点),想在删除 p ,可行做法是用 p->next 覆盖 p 的值与 next ,然后删除 p->next 。
在求解所有不大于 n 的素数时,线性筛法(欧拉筛)都应当优先于埃氏筛法使用,因为线性筛法的时间复杂度为O(n),低于埃氏筛法的O(n log log n)。
二分查找仅适用于有序数据。若输入数据无序,当仅进行一次查找时,为了使用二分而排序通常不划算。
通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。
贪心算法在每一步都做出当前看来最优的局部选择,并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解,再将子问题的解合并得到原问题的解。
以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为为O(n)。
递归函数一定要有终止条件,否则可能会造成栈溢出。
使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解。
基于下面定义的函数,通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果 一个数能被9整除,则它的各位数字之和能被9整除。

假设函数 gcd() 能正确求两个正整数的最大公约数,则下面的 findMusicalPattern(4,6) 函数返回2。



