2026年03月CCF GESP C++五级判断题（共10题，每题2分，满分20分）
有一个存储了n个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是(O(1))，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是(O(1))。（）
{{ select(1) }}
若数组a已按升序排列，执行int lowerBound(vector<int>& a,int x){ int l=0, r=a.size(); while(l < r) { int mid = (l + r) / 2; if(a[mid] >= x) r = mid; else l = mid + 1; } return l; }代码，可以正确实现“在a中查找第一个大于等于x的元素的位置”。（）
{{ select(2) }}
快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。（）
{{ select(3) }}
若某算法满足递推式(T(n)=2T(n/2)+O(n))，则其时间复杂度为(O(n log n))。（）
{{ select(4) }}
在一个数组中，若两个元素a[i]和a[j]满足(i<j)且a[i] > a[j]，则a[i]和a[j]是一个逆序对。执行long long cnt=0; void merge_count(vector<int>& a, int l, int m, int r){ int i = l, j = m + 1; while(i <= m && j <= r) { if(a[i] <= a[j]) i++; else { cnt += (m - i + 1); j++; } } }代码，可以正确统计数组a区间[l,r]内的逆序对总数。（）
{{ select(5) }}
根据唯一分解定理，如果大于1的整数n不能被任何不超过其平方根的质数整除，那么n必定是质数。（）
{{ select(6) }}
假设数组a的值域范围是D，执行指定代码（sort排序+二分查找最大间距），该程序的时间复杂度是(O(n log n + n log D))。（）
{{ select(7) }}
若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。（）
{{ select(8) }}
线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过“每个合数只被其最大质因子筛去”的策略，保证每个合数恰好被标记一次，从而实现(O(n))的时间复杂度。（）
{{ select(9) }}
任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。（）
{{ select(10) }}
正确
错误当前文件内容过长，豆包只阅读了前 45%。
liuchengyu
标签> 