2024 CCF第一轮认证CSP-S提高组真题及解析
一、 单项选择题
（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
1. 在 Linux 系统中，如果你想显示当前工作目录的路径，应该使用哪个命令?( ) A pwd B cd C ls D echo 题解： A pwd：这个命令是“print working directory”的缩写，它的作用是显示当前工作目录的路径。 cd：这个命令是“change directory”的缩写，它的作用是切换当前工作目录。 ls：这个命令是“list”的缩写，它的作用是列出当前工作目录下的文件和文件夹。 echo：这个命令用于在终端输出指定的文本。
2. 假设一个长度为n的整数数组中每个元索值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?( ) A O(n) B O(logn) C O(nlogn) D O(1) 题解： A 每个元索值互不相同，且这个数组是无序的，所以要逐一比较，需要比较n-1次
3. 在 C++中，以下哪个函数调用会造成溢出?( ) A int foo(){ return 0;} B int bar(){int x=1;return x; } C void baz(){ int a[1000];baz();) D void qux(){ return; } 题解： C C选项为，递归调用，没用递归出口，会造成存放函数的栈越来越多，最终程序溢出
4. 在一场比赛中，有10名选手参加、前三名将获得金、银、牌。若不允许并列、且每名 选手只能获得一枚奖牌，则不同的颁奖方式其有多少种?( ) A 120 B 720 C 504 D 1000 题解 B 题目要求不允许并列，从10名中选3名，A(10,3)=10*9*8=720
5. 下面哪个数据结构最适合实现先进先出(FIFO)的功能?( ) A 栈 B 队列 C 线性表 D 二叉搜索树 题解 B A 栈是一种后进先出（LIFO）的数据结构，它遵循“先进后出”的原则 B 队列是一种先进先出（FIFO）的数据结构，它遵循“先进先出”的原则。在队列中，第一个进入的元素总是第一个被取出。因此，队列非常适合实现先进先出（FIFO）的功能。 C 线性表是一种基本的数据结构，它可以用来表示一系列有序的数据元素。 D 二叉搜索树是一种特殊的二叉树，它的每个节点都满足左子树的所有节点的值小于等于该节点的值，右子树的所有节点的值大于等于该节点的值
6. 已知f(1)=1.且对于n≥2有f(n)=f(n-1)+f(⌊n/2⌋)，则f(4)的值为:( ) A 4 B 5 C 6 D 7 题解 B 根据递归公式计算，一般可以通过递推写表的方式 本题数据较少，可以直接计算每一项 f(1)=1 f(2)=f(1)+f(1)=2 f(3)=f(2)+f(1)=2+1=3 f(4)=f(3)+f(2)=3+2=5
7. 假设有一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确?( ) A 所有顶点的度数均为偶数 B 该图连通 C 该图存在一个欧拉回路 D 该图的边数是奇数 题解 D A 欧拉图没有奇点，没有奇数条边，所以所有顶点的度数都是偶数 B 欧拉图可以从一点出发，遍历所有点后回到原点，所以改图是连通的 C 欧拉图可以从一点出发，遍历所有点后回到原点，形成一个回路，称为欧拉回路 D 图的边数不一定是奇数，每个点被访问一次，边数为偶数时也可以是欧拉图
8. 对数组进行二分查找的过程中，以下哪个条件必须满足?( ) A 数组必须是有序的 B 数组必须是无序的 C 数组长度必须是2的幂 D 数组中的元素必须为整数 题解 A 而非查找的前提条件是必须是有序序列，这个是二分的关键
9. 考虑一个自然数n以及一个数m,你需要计算n的逆元(即n在m意义下的乘法逆元)，下列哪种算法最为适合?( ) A 使用暴力法依次尝试 B 使用扩展欧几里得算法 C 使用快速幂法 D 使用线性筛法 题解 B 逆元使用使用扩展欧几里得算法
10. 在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函效和冲突解决策略。已知某哈希表中有n个键值对，表的装载因子为a(0 < a <= 1)。在使用开放地址法解决冲突的过程中，最坏情况下查找一-个元素的时间复杂度为( ) A O(1) B O(logn) C O(1/(1-a)) D O(n) 题解 D 哈希表，使用哈希函数数学计算，一般时间复杂度为O(1) 如果有冲突，通过哈希函数计算后，还需要对有冲突的进行比较查找 特殊情况哈希函数都计算到一个值，就等于使用比较进行查找计算 找到对应值需要，O(n)的时间复杂度
11. 假设有一棵h层的完全二叉树，该树最多包含多少个结点?( ) A 2^h-1 B 2^(h+1)-1 C 2^h D 2^(h+1) 题解 A 除了最下层，其他每层都饱满，最下层的结点都集中在该层最左边的若干位置上 最多是满二叉树的情况 根据满二叉树的性质，结点数 1层 2^1-1=1 2层 2^2-1=3 3层 2^3-1=7 …. h层 2^h-1
12. 设有一个10个顶点的完全图,每两个顶点之间都有一条边。有多少个长度为4的环?( ) A 120 B 210 C 630 D 5040
题解 C 从10个点选4个的排列，A(10,4)=10*9*8*7 4个点的环，每个点没有位置关系顺序，所以A(10,4)/4 环上顺时针是一个环，所以A(10,4)/2=10*9*6=630
13. 对于一个整数n。定义f(n)为n的各位数字之和。问使f(f(x))=10 的最小自然数x是多少？( ) A 29 B 199 C 299 D 399
题解 B f(f(x))=10 数字和是10的有19，28，37，46…. 需要看ABCD相关选项中，哪一个的数字和是上面的 f(29)=11 f(199)=19 -对应上面的19 f(299)=20 f(399)=21
14. 设有一个长度为n的01字符串，其中有k个1，每次操作可以交换相邻两个字符。在最坏情况下将这k个1移到字符串最右边所要的交换次数是多少? ( ) A k B k*(k-1)/2 C (n-k) *k D (2n-k-1)*k/2
题解 C 移动交换类似冒泡排序，最坏的情况是k个1都在左端的情况，逐一比较移动到最右端比较n-k次 需要进行k趟 所以总交换次序为(n-k)*k
15. 如图是一张包含7个顶点的有向图，如果要除其中一些边，使得从节点1到节点7没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合?( )
A 1 B 2 C 3 D 4 题解 D 枚举共4种可行方案 1 删除1->2 ,4->6 2 删除2->5,4->6 3 删除4->6,5->7 4 删除5->7,6->7
二、 阅读程序
(程序输入不超过数组成字符串定义的范围:判断题正确填√，错误填×;除特殊说明外， 判断题1.5分，选择题3分，共计40分)
a. 题目代码
cpp
#include <iostream>
using namespace std;
const int N=1000;
int c[N];
int logic(int x,int y) {
return (x&y)^((x^y)|(~x&y));
}
void generate(int a, int b, int *c) {
for(int i=0;i<b; i++){
c[i]=logic(a,i)%(b + 1);
}
}
void recursion(int depth,int *arr,int size){
if(depth<0||size<= 1) return;
int pivot = arr[0];
int i=0,j=size -1;
while(i<=j){
while(arr[i] < pivot) i++;
while(arr[j] < pivot) j--;
if(i<=j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j]= temp;
i++; j--;
}
}
recursion(depth-1,arr,j + 1);
recursion(depth-1,arr+i,size-i);
}
int main() {
int a,b,d;
cin >> a >> b >> d;
generate(a,b,c);
recursion(d,c,b);
for(int i=0; i < b; ++i) cout << c[i] <<" ";
cout << endl;判断题 16. 当1000 >= d >= b时，输出的序列是有序的。( ) 题解 T
17 当输入”5 5 1″时，输出为”1 1 5 5 5”( ) 题解 F
18 假设数组c长度无限制，该程序所实现的算法的时间条度是0(b)的。( ) 题解 F
单选题 19 函数int logic(int x，int y)的功能是( ) A 按位与 B 按位或 C 按位异或 D 以上都不是 题解 B
20 (4分)当输入为“10 100 100”时，输出的第100个数是( ) A 91 B 94 C 95 D 98 题解 C
b.
cpp
#include <iostream>
#include <string>
using namespace std;
const int P = 998244353,N=1e4+10,M=20;
int n,m;
string s;
int dp[1<<M];
int solve() {
dp[0]=1;
for(int i=0;i<n; ++i){
for(int j=(1<<(m-1))-1;j>=0;--j){
int k = (j<<1)|(s[i]-'0');
if(j|=0 || s[i]=='1') {
dp[k]=(dp[k]+dp[j])%P;
}
}
}
int ans = 0;
for(int i=0; i<(1<<m);++i){
ans = (ans + 1ll*i*dp[i])%P;
}
return ans;
}
int solve2 {
int ans =0;
for(int i=0;i<(1<<n);++i){
int cnt = 0;
int num = 0;
for(int j=0; j<n;++j) {
if(i&(1<<j)) {
num = num*2+(s[j] - '0');
cnt++;
}
}
if(cnt <= m)(ans += num)%=p;
}
return ans;
}
int main(){
cin >> n >> m;
cin >> s;
if(n<=20) {
count << solve2 << endl;
}
count << solve() << endl;
return0;
}假设输入的s是包含 n个字符的 01串，完成下面的判断题和单选题
判断题 21. 假设数组 dp 长度无限制，函数solve()所实现的算法时间复杂度是 O(n*2^m) ( ) 题解 T
22. 输入“11 2 10000000001”时，程序输出两个数32和23 ( ) 题解 T
23. (2分)在 n<=10 时，solve()的返回值始终小于 4^10 ( ) 题解 T
单选题
24 当n=10 且 m=10 时，有多少种输入使得两行的结果完全一致? ( A 1024 B 11 C 10 D 0 题解 B
25 当n<=6 时，solve()的最大可能返回值为 ( ) A 65 B 211 C 665 D 2059 题解 C
26 若n=8，m=8，solve和solve2的返回值的最大可能的差值为 ( ) A 1477 B 1995 C 2059 D 2187 题解 C
c.
cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 5;
const int P1 = 998244353,P2 = 1000000007;
const int B1 = 2,B2 = 31;
const int K1 = 0,K2 = 13;
typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];
struct H {
int h1,h2,l;
H(bool b = false) {
h1 = b + K1;
h2 = b+ K2;
l= 1;
}
H operator + (const H &h)const {
H hh;
hh.l =l+ h.l;
hh.h1 = (1ll * h1 * p1[h.l] + h.h1)% P1;
hh.h2 = (1ll *h2* p2[h.l]+ h.h2)% P2;
return hh;
}
bool operator == (const H &h) const {
return l== h.l && h1 == h.h1 && h2 == h.h2;
}
bool operator < (const H &h) const {
if (l != h.l)return l < h.l;
else if (h1 != h.h1)return h1 < h.h1;
else return h2 < h.h2;
}
}h[maxn];
void init() {
memset(p, 1, sizeof(p));
p[0]= p[1]= false;
p1[0]= p2[0]= 1;
for (int i= 1;i<= n; i++){
p1[i]=(1ll*B1*p1[i-1])% P1;
p2[i]=(1ll * B2 *p2[i-1])% P2;
if (!p[i])continue;
for (int j= 2*i;j<= n;j+= i){
p[j] = false;
}
}
}
int solve(){
for(inti=n;i;i--){
h[i] = H(p[i]);
if (2*i+1<= n){
h[i] = h[2 *i]+ h[i] + h[2 *i+ 1];
} else if (2 *i<= n){
h[i] = h[2 * i] + h[i];
}
}
cout << h[1].h1 << endl;
sort(h + 1,h +n+ 1);
int m=unique(h+1,h+n+1)-(h + 1);
return m;
}
int main() {
cin>>n;
init();
cout << solve() << endl;
}判断题 27. 假设程序运行前能自动将 maxn 改为 n+1，所实现的算法的时间复杂度是O(nlogn) ( ) 题解 T
28. 时间开销的瓶颈是init()函数( ) 题解 F
29. 若修改常数 B1 或 K1 的值，该程序可能会输出不同呢的结果( ) 题解 T
单选题 30. 在 solve()函数中，h[]的合并顺序可以看作是( ) A 二叉树的 BFS 序 B 二叉树的先序遍历 C 二叉树的中序遍历 D 二叉树的后序遍历 题解 C
31. 输入10 ，输出的第1行是( ) A 83 B 424 C 54 D 110101000 题解 A
32. (4分)输入16 ，输出的第2行是( ) A 7 B 9 C 10 D 12 题解 C
三、完善程序
(单选题，每小题3分，共计 3 分) 1序列合并 有两个长度为N的单调不降序列 A和 B，序列的每个元素都是小于10^9 的非负整数。在A和B中各取一个 数相加可以得到N^2个和，求其中第k小的和。上述参数满足 N <= 10^5 和1 <= K <= N^2。 试补全程序。 [code title=cpp] #include <iostream> using namespace std; const int maxn = 100005; int n; long long k; int a[maxn], b[maxn]; int *upper_bound(int *a, int *an, int ai){ int l=0,r= (1); while (l < r) { int mid =(l +r) >> 1; if( (2) ){ r = mid; } else { l= mid + 1; } } return (3); } long long get_rank(int sum) { long long rank = 0; for (int i = 0;i < n; i++){ rank += upper_bound(b, b + n, sum - a[i])- b; } return rank; } int solve() { int l= 0,r= (4); while (l < r) { int mid = ((long long)l + r) >> 1; if( (5) ) { l= mid + 1; } else { r = mid; } } return l; } int main(){ cin >> n >> k; for (int i= 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; cout << solve() << endl; return 0; } [/code] 33. 1处应该填写( ) A an-a B an-a-1 C ai D ai+1 题解 A
34. 2处应该填写( ) A a[mid] > ai B a[mid] >= ai C a[mid] < ai D a[mid] <= ai 题解 A
35. 3处应该填写( ) A a+l B a+l+1 C a+l-1 D an-l 题解 A
36. 4处应该填写( ) A a[n-1]+b[n-1] B a[n]+b[n] C 2*maxn D maxn 题解 A
37. 5处应该填写( ) A get_rank(mid) < k B get_rank(mid) <= k C get_rank(mid) > k D get _rank(mid) >= k 题解 A
2 次短路 已知一个n个点m条边的有向图 G，并且给定图中的两个点s和t，求次短路(长度严格大于最短路的最短 路径)。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短 路的一个方案 试补全程序
cpp
#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
const int maxn=2e5 +10,maxm=1e6+ 10,inf=522133279;
int n, m, s, t;
int head[maxn],nxt[maxm], to[maxm],w[maxm], tot = 1;
int dis[maxn << 1],*dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];
void add(int a, int b, int c) {
++tot;
nxt[tot] = head[a];
to[tot] = b;
w[tot] = c;
head[a] = tot;
}
bool upd (int a, int b, int d, priority_queue<pair < int, int> > &q) {
if (d >= dis[b])return false;
if (b < n) (1）;
q.push( （2） );
dis[b] = d;
pre[b] = a;
return true;
}
void solve() {
priority_queue<pair<int, int> >q;
q.push(make_pair(0, s));
memset(dis, (3),sizeof(dis));
memset(pre, -1, sizeof(pre));
dis2 = dis + n;
pre2 = pre + n;
dis[s] = 0;
while (!q.empty()){
int aa = q.top().second; q.pop();
if (vis[aa])continue;
vis[aa] = true;
int a = aa % n;
for (int e = head[a]; e ; e = nxt[e]){
int b = to[e],c = w[e];
if (aa < n) {
if (!upd(a, b, dis[a]+ c, q))
（4）;
} else {
upd(n + a, n + b, dis2[a] + c, q);
}
}
}
}
void out(int a){
if (a != s) {
if (a < n)out(pre[a]);
else out( 5);
}
printf("%d%c", a %n + 1, " \n"[a == n + t]);
}
int main(){
scanf("%d%d%d%d", &n, &m,&s,&t);
s--,t--;
for (int i = 0; i < m; ++i){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a -1,b -1,c);
}
solve();
if (dis2[t]==inf)puts("-1");
else {
printf("%d\n", dis2[t]);
out(n + t);
}
return 0;
}38. 1处应填( ) A upd(pre[b], n+b, dis[b], q) B upd(a, n+b, d, q) C upd(pre[b], b, dis[b], q) D upd(a, b, d, q) 题解 A
39. 2处应填( ) A make_pair(-d, b) B make_pair(d, b) C make_pair(b, d) D make_pair(-b, d) 题解 A
40. 3处应填( ) A 0xff B 0x1f C 0x3f D 0x7f 题解 B
41. 4处应填( ) A upd(a, n+b, dis[a]+c, q) B upd(n+a, n+b, dis2[a]+c, q) C upd(n+a, b, dis2[a]+c, q) D upd(a, b, dis[a]+c, q) 题解 A
42. 5处应填( ) A pre2[a%n] B pre[a%n] C pre2[a] D pre[a%n]+1 题解 A
腾讯云开发者
