2023 CCF第一轮认证CSP-S提高级C++真题及解析

第一次参加提高组这个级别的考试,感觉好难呀,看着这些数学式直接懵了。。。好吧,哪里难了?每年都是这样,不要乱说,要从自己身上找原因,都这么久了,有没有认真学习。。。

下面是本次考试的真题及解析:

单项选择题

1.在linux 系统终端中,以下哪个命令用于创建一个新的目录?
A. newdir
B.mkd:
C.creat
D.mkfold
【答案:】B
【解析】 linux 中创建目录命令是“mkdir”。 mkdir 命令是 make directories 的缩写

2. 0,1,2,3,4中选取 4个数字,能组成 ( )个不同四位数。(注: 最小的四位数是 1000,最大的四位数是 9999)
A.96
B.18
C.120
D.84
【答案】A
【解析】最高位 4种选择,后面的百位、十位、个位分别是 4、3、2 种,因此: 4*4*3*2=96

3.假设 n 是图的顶点的个数,m 是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于 m=O(n)的稀疏图而言,下面的四个选项,哪一项的渐进时间复杂度最小 ()
A. O(m√logn * loglogn)
B.O(n²+m)
C.O(n²/logm+mlogn)
D.O(m+nlogn)
【答案】A
【解析】 渐进时间复杂度就是当 n 趋于无穷大的时候,f(n)得到的极限值; m=O(n)指当 n 趋于无穷大的时候,m 趋近于 n。显然排除 B,C,而O(loglogn) < O(√logn), O(m√logn loglogn) = O(n√logn loglogn) < O(n√logn√logn) = 0(nlogn + m) ,故 选择 A。

4.假设有n根柱子,需要按照以下规则依次放置编号为 1.2.3,的圆柱:每根柱子的底部固定,顶部可以放入圆环:每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4个根柱子时,最多可以放置 ( ) 个圆环
A.7
B.9
C.11
D.5
【答案】C
解析: 假设四根柱子分别为a、b、c、d,放置的顺序和编号为a1、b2、c3、d4、d5、c6、b7.a8、b9、c10、d11,最多可以放置 11 个圆环

5.以下对数据结构表述不恰当的一项是()
A.队列是一种先进先出(FIFO)的线性结构
B.哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C.散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D.二叉树是一种每个结点最多有两个子结点的树结构
【答案】B
【解析】可参考哈夫曼树的定义

6.以下连通无向图中,() 一定可以用不超过两种颜色进行染色
A.完全三叉树
B.平面图
C.边双连通图
D.欧拉图
【答案】 A
【解析】完全三叉树可以用 2 种颜色进行染色,其他数据结构不一定会少于 2 种

7.最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下,给定两个序列X={x1,x2,x3,..xm)和 Y=y1,y2,y3,…yn],最长公共子序列 (LCS) 问题的目标是找到一个最长的新序列Z=fz1,z2.z3…zk,使得序列Z 既是序列X的子序列,又是序列Y的子序列,且序列Z的长度k在满足上述条件的序列里是最大的。(注: 序列A是序列 B 的子序列,当且仅当再保持序列 B 元素顺席的情况下,从序列B中删除若干个元素,可以使得剩余的元素构成序列 A.)则序列“ABCAAAABA和“ABABCBABA”的最长公共子序列长度为() 。
A.4
B.5
C.6
D.7
【答案】C
【解析】 分析一下2个字符串
ABCAAAABA
ABABCBABA
发现前 2 个和后 3 个是一样的,中间有 1 个公共子序列,因此答案是 C

8.一位玩家正在玩一个特殊的掷骰子的游戏,游戏要求连续掷两次骰子,收益规则如下: 玩家第一次掷出x点,得到 2x 元;第二次掷出y点,当y=x 时玩家会失去之前的得到 2x 元。而当y 时玩家能保住第一次获得的 2x元上述x,yE[1,2,3,4,5,6。例如:玩家第一次掷出3点得到6元后,但第二次再次掷出3点会失去之前得到的6元,玩家最终受益为 0元:如果玩家第一次掷出3 点,第二次掷出 4点,则最终受益是6元。假设般子挑出任意一点的概率为1/6,玩家连续掷两次般子后,所有可能情形下收益的平均值是多少?
A.7元
B.35/6 元
C.16/3 元
D.19/3 元
【答案】 B
【解析】共有 6*6=36种情况其中
(1) x=y: 6种,受益为 0
(2) xzy,x=1: 5种,受益为 2
(3) xzy,x=2: 5种,受益为4
(4) xzy,x=3: 5种,受益为 6
(5) xzy,x=4: 5种,受益为 8
(6) xzy,x=5: 5种,受益为 10
(7) xty,x=6: 5种,受益为 12
受益期望为: (6/36)*0+(5/36) * (2+4+6+8+10+12) =35/6

9.假设我们有以下的 c++代码
int a=5,b=3,c=4.bool res=a&blc^b&&alc
请问 res 的值是什么? (提示: 在 c++中,逻辑运算的优先级从高到低依次为: 逻辑非 (),逻辑与 (&&),逻辑或)位运算的优先级从高到低依次为: 位非 (~),位与&),位异或(),位或)。同时,双目位运算的优先级高于双目逻辑运算: 逻辑非和位非优先级相同,且高于所有双目运算符。
A、true
B、false
C、1
D、0
【答案】A
【解析】 根据优先级计算 3&5=1,后面跟着|运算,之后的计算可以不做,数据类型是 bool 类型答案选 A

10.假设快速排序算法的输入是一个长度为 n 的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?
A. 快速排序对于此类输入的表现最好,因为数组已经排序。
B. 快速排序对于此类输入的时间复杂度是 O(nlogn)。
C.快速排序对于此类输入的时间复杂度是 O(n²)
D.快速排序无法对此类数组进行排序,因为数组已经排序.
【答案】 C
【解析】 该数列是有序数列,是快速排序中遇到的最坏的情况,时间复杂度是 O(n)。因此选 C

11.以下哪个命令,能将一个名为”main .cpp”的 C++源文件,编译并生成一个名为”main”的可执行文件? ()
A.g++ -o main main.cpp
B.g++-o main.cpp main
C.g++ main -o main.cpp
D.g++ main.cpp -o main.cpp
【答案】 A
【解析】 g++的命令格式,选 A。

12.在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数量最少。一棵树可能有多个重心。请问下面哪种树一定只有一个
重心?( )
A.4个结点的树
B.6 个结点的树
C.7 个结点的树
D.8 个结点的树
【答案】C
【解析】 树的重心可以是 1到2个,奇数个结点,重心只有 1 个

13.如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这 6 个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?
2023 CCF第一轮认证CSP-S提高级C++真题及解析
A.1
B.2
C.3
D.4
【答案】 C
【解析】 根据图发现,3 条边 (1-3,3-4.4-1) 构成1个回路,去掉任意1条即可,因
此有3条边可作为候选,选C。

14.若
2023 CCF第一轮认证CSP-J提高级C++真题及解析
定义
2023 CCF第一轮认证CSP-J提高级C++真题及解析
其中xi E{0,1,…..,15}对于给定自然数n0、存在序列四n1,n2….nm、其中对于1<=i<=m都有ni=f(ni-1),且nm = nm-1,称为nm为n0关于f的不动点。问在10016至1A016中,关于f的不动点为 9 的自然数个数为()
A、10
B、11
C、12
D、13
【答案】B
【解析】f的作用是求某 16 进制数的各位数字之和,如果不动点为9,那么该数字有两种情况:(1)各位数字之和为 9,这种情况有108/117/126/135/144/153/162/171/180共9个数字,(2) 各位数字之和为 24- (18)16,所以f (24) =9,这种情况有18F和19E共2个数字。总共 11 个数字。

15、现在用如下代码来计算下 2”,其时间复杂度为 ( )

cpp

double quick_power(double x,unsigned n)
    if(n == 0) return 1;
    if(n == 1) return x;
    return quick_power(x,n/2)
        * quick_power(x,n/2)
        * ((n&1))?x:1)
}

A、 O(n)
B、O(1)
C、O(logn)
D、 O(nlogn)
【答案】A
【解析】根据代码,要处理数据规模是 n 的函数可以推出 T(n)-2T(n/2),可以根据主定理,或者变量带入 n=2”求出时间复杂度是 O(n)。(主定理: a=2,b=2.f(n)=0)

阅读程序

(1)

cpp

#include <iostream>
using namespace std;

unsigned short f(unsigned short x){
    x^=x<<6.

    x^=x>>8.

    return x;
}

int main(){
    unsigned short x;
    cin>>x
    unsigned short y=f(x);
    cout << y << endl;
    return 0.
}

假设输入的x是不超过 65535 的自然数,完成下面的判断题和单选题
判断题
16.当输入非零时,输出一定不为零。()
【答案】 对
【解析】只有 X=0的时候,运算才可以是 0。

17.(2 分)将f函数的输入参数的类型政为 unsigned int,程序的输出不变。( )
【答案】 错
【解析】 unsignedint 是4个字节,unsigned shot 是 2个字节,会溢出

18.当输入为“65535”时,输出为“63”。( )
【答案】 对
【解析】 65535,二进制是 1111111111111111,位运算可以得出答案。

19.当输入为“1”时,输出为“64”。( )
【答案】 错
【解析】 1,二进制是 0000000000000001,位运算可以得出答案。

单选题
20.当输入为“512”时,输出为 ( )
A. “33280”
B. “33410”
C. “33106”
D. “33346”
【答案】 B
【解析】512的二进制是 1000000000,计算可得 B 选项

21.当输入为“64”时,执行完第 5行后x 的值为( )
A. “8256”
B. “4130”
C. “4128”
D. “4160”
【答案】D
【解析】64的二进制是 0000000001000000,计算可得 D 选项

(2)

cpp

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std,

long long solve1(int n){
    vector<bool> p(n+1,true);
    vector<long long> f(n+1,0),g(n+1,0)
    f[1]=1;
    for(int i=2;i*i<=n;i++){
        if(p[i]){
            vector<int>d;
            for(int k=i; k<=n;k*=1)  d.push_back(k);
            reverse(d.begin(),d.end())
            for(int k:D){
                for(int j=k;j<=n;j+=k){
                    if(p[j]){
                    p[j]=false;
                    f[j]=i;
                    g[j]=k;
                }
            }
        }
    }
    for(int i=sqrt(n)+1;i<=n;i++){
        if(p[i]){
            f[i]=i;
            g[i]=i;
        }
    }
    long long sum=1;
    for(int i=2;i<=n;i++){
        f[i]=f[i/g[i]] * (g[i]*f[i]-1)/(f[i]-1)
        sum+=f[i];
    }
    return sum;
}

long long solve2(int n){
    long long sum=0;
    for(int i=1;i<=n;i++){
        sum+=i*(n/i);
    }
    return sum;
}

int main(){
    int n;
    cin>>n;
    cout<<solve1(n)<<endle;
    cout<<solve2(n)<<endle;
    return 0;
}

假设输入的 n 是不超过 1000000 的自然数,完成下面的判断题和单选题

判断题
22.将第 15 行删去,输出不变。( )
【答案】 错
【解析】 reverse(d.begin0,d.end0); 这条语句是翻转整个数组,删除 15 行之后排列
的数组是正序,输出内容就发生改变。

23.当输入为“10”时,输出的第一行大于第二行。( )
【答案】 错
【解析】 solve2()和 solve1()求的是接近 n2的值,输出的结果都是相同的

24. 当输入为“1000”时,输出的第一行与第二行相等。( )
【答案】 对
【解析】 solve2()和 solve1()输出结果相同。

单选题样。
25.solve1 (n)的时间复杂度为 ( )
A. O(nlog2n)
B. O(n)
C. O(n log n)
D. O(n log log n)
【答案】 D
【解析】主要看 for 循环嵌套的循环次数,和埃氏筛法相似,每次循环变量变化不一

26.solve2 (n) 的时间复杂度为 ( )
A. O(n2)
B. O(n)
C. O(n log n)
D. O(√n)
【答案】 B
【解析】观察函数,里面是一重循环,时间复杂度是 O(n)。

27.输入为“5”时,输出的第二行为 ()
A.”20″
B.”21″
C.”22″
D.”23″
【答案】B
【解析】带入代码计算可得。

cpp

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool f0(vector<int>&a,int m,int k){
    int s=0;
    for(int i=0,j=0;i<a.size();i++){
        while (a[i]-a[j]>m)j++;
        s+=i-j;
    }
    return s>=k;
}

int f(vector<int>&a,int k){
    sort(a.begin(),a.end())
    int g=0;
    int h=a.back()-a[0];
    while(g<h){
        int m=g+(h-g)/2;
        if(f0(a,m,k)){
            h=m;
        }else{
            g=m+1
        }
    }

    return g;
}

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n,0);
    for(int i=0;n<=n;i++){
        cin>>a[i];
    }
    cout<<f(a,k)<<endl;
    return 0
}

判断题
28.将第 24行的“m”改为“m-1”,输出有可能不变,而剩下情况为少1。()
【答案】对
【解析】原来的代码,在左区间查找,挪动h=m,包含了中间值m的情况,如果改成 m-1,即中间-1,不包含中间值,那么在中间值不是我们要找的结果的时候,是正确的。所以题里面说输出有可能不变是正确的,剩下的情况,因为把中间值-1,不包含中间值的情况,因此题里面说剩下情况少 1,也是正确的。

29.将第22行的“g+(h-g)/2”改为“(h+g)>>1”,输出不变( )
【答案】 对
【解析】“g+(h-g)/2=g+h/2-g/2=(g+h)/2=(g+h)>>1

30.当输入为“572-451-3”,输出为“5”。()
【答案】对
【解析】本题二分求逆序对的数量,2-451-3 共计5个逆序对

单选题
31.设 a 数组中最大值减最小值加 1为 A,则f函数的时间复杂度为 ()
A. O(nlogA)
B. O(n2logA)
C. O(nlog(nA))
D. O(nlogn)
【答案】 C
【解析】f函数的 sot 排序是 nogn,二分时间复杂度是 logA,fo 函数是双指针算法
是0(n),时间复杂度是 nlogn+nlogA=O(nlog(An))

32.将第 10 行中的”>”替换为“>=”,那么原输出与现输出的大小关系为 ( )
A.一定小于
B.一定小于等于且不一定小于
C.一定大于等于且不一定大于
D.以上三种情况都不对
【答案】B
【解析】加上>=相同的数也统计,所以一定小于等于且不一定小于是正确的

33.当输入为”582-538-12”时,输出为 ()
A.”13” B.“14”C.“8” D. 15”
【答案】B
【解析】此题为二分求逆序对的数量,如: (2,-5)、(2,12) …,可以数出一共有14对

完善程序

(1)(第 k小路径)给定一张n个点 m 条边的有向无环图,顶点编号从0到n-1。对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k 小的路径。保证存在至少k条路径。上述参数满足 1<=n,m<105和1<k<1018
在程序中,我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。
试补全程序.

cpp

#include <jostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000
const long long LIM = 100000000000000000011:

int n, m, deglMAXN]
std::vector<int> E[MAXN];
long long k,flMAXN];

int next(std::vector<int> cand, long long &k) {
    std::sort(cand.begin(),cand.end0),
    for (int u : cand) {
        if (①) return u;
        k-=f[u];
    }
    return -1
}

int main(){
    std::cin>>n>>mk;
    for (int i=0; i<m;++i){
        int u,v;
        std::cin>>u>>v; //一条从u到v的边
        E[u].push_back(v);
        ++deg[v];
    }
    std::vector<int> Q;
    for (int i = 0;i<n;++i)
        if(!deg[i]) Q.push_back(i);
    for (int i=0; i < n;++i){
        int u = Q[i];
        for (int v:E[u]){
            if(②) Q.push_back(v);
            --deg[v];
        }
    }
    std::reverse(Q.begin(),Q.end());
    for (int u:Q) {
        f[u] = 1;
        for(int v:E[u])f[u] = ③;
    }
    int u = next(Q,k);
    std::cout<<u<<std::endl;
    while(④){
        ⑤;
        u = next(E[u].k);
        std::cout<<u<<std::endl;
    }
    return 0;
}

34.①处应填()
A. k >= f[u]
B. k <= f[u] C. k > f[u]
D. k < f[u] 【答案】B
【解析】f[u]]记录的是从u开始向后可以走的路径数量,当f[u]>=k 时,说明要走第k
大的路下一步需要走u,故选 B。同时若 f[u]

35.②处应填()
A. deg[v] == 1
B. deg[v] == 0
C. deg[v] > 1
D. deg[v] > 0
【答案】A
【解析】求图的拓扑序,当点度数为 0 时将该点放入队列,因为在–deg[v]之前操作
需要判断 deg[v] == 1,故选 A。

36.③处应填()
A. std::min(f[u] + f[v],LIM)
B. std:min(f[u] + f[v] + 1, LIM)
C. std::min(f[u] * f[v], LIM)
D. std::min(f[u] * (f[v] + 1), LIM)
【答案】 A
【解析】 求出拓扑序后 dp求f[u],f[u]=1+\sum_{v\in E[u]}f[v],故选A, 与LIM取 min
是为了保证不爆long long。

37.④处应填()
A. u!= -1
B. !E[u].empty()
C. k > 0
D. k> 1
【答案】 D
【解析】 结合38题,当k=1时,再–k后,k=0,此时已经找到了答案,因而不需要再继续循环找新的节点,故需要再 k=1 时退出循环,即 while(k>1),选 D。

38.⑤处应填( )
A. k += f[u]
B. k -= f[u]
C. –k
D. ++k
【答案】C
【解析】每次走到一个新点,需要减去从初始节点走到该节点的方案,所以需要–k,选 C

(2)(最大值之和)给定整数序列a0…,an-1,求该序列所有**非空连续子序列**的最大值之和。上述参数满足 1 < n < 105和1 <= ai <= 108
一个序列的非空连续子席列可以用两个下标l和r(其中 0<=l<=r<n)表示,对应的序列为 al,al+1…, ar。两个非空连续子序列不同,当且仅当下标不同。
例如,当原序列为[1,2,1,2] 时,要计算子序列 [1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1].[2,1,2]、[1,2,1,2] 的最大值之和,答案为 18。注意[1,1]和[2,2]虽然是原序列的子序列,但不是连续子席列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子席列,所以会被分别计算。解决该问题有许多算法,以下程序使用分治算法,时间复杂度 O(nlogn)。试补全程序。

cpp

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000:
int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
    if(l+1 == r){
        ans += a[l];
        return;
    }

    int mid = (l+r)>>1;
    std::vector<int> pre(a+mid,a+r);
    for (int i = i; I<r -mid;++i)①;
    std::vector<long long> sum(r - mid +1);
    for (int i=0;i<r - mid,++i) sum[i+1] = sum[i] + pre[i];
    for (int i = mid - 1,j = mid,max = 0; I>=l; --i) {
        while (j < r && ②) ++j;
        max = std::max(max,a[i]);
        ans += ③;
        ans += ④;
    }
    solve(l,mid);
    solve(mid,r);
}

int main(){
    std::cin >> n;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    ⑤;
    std::cout << ans << std::endl;
    return 0; 
}

39.①处应填())
A. pre[i] = std::max(pre[i – 1], a[i – 1])
B. pre[i + 1] = std::max(pre[i], pre[i + 1])
C. pre[i] = std::max(pre[i – 1], a[i])
D. pre[i] = std::max(pre[i], pre[i – 1])
【答案】 D
【解析】 pre 数组求出[mid,r)中的前缀 max,sum 数组求出[mid,r)中的前缀 max 和,故选择 D

40.②处应填()
A. a[j] < max B. a[j] < a[i] C. pre[j - mid] < max D. pre[j - mid] > max
【答案】 C
【解析】 对于固定的左端点i, 求解右端点在[mid,r)的所有答案,可以发现区间[mid,r)中的点被分为左右两份,对于左半部分[mid,j),$\forall x\in[mid,j],\max\a_i,a{i+1},…,a_x\
}=max$,其中max就是题中维护的max,由于右侧部分 [j,r), $\forall x\in[j,r),\max\{a_i,a_{i+1},…,a_x\}=max\{a_{mid},a_{mid+1},…,a_x\} = pre_x$,而两部分的边界j,就是第一个满足 pre[j-mid] >= max 的j,即 while (j < r &&pre[j-mid] < max ),因而选择 C

41.③处应填()
A. (long long)(j – mid) * max
B. (long long)(j – mid) * (i – l)* max
C. sum[j – mid]
D. sum[j – mid] * (i – l)
【答案】A
【解析】该部分在统计 40 题的解析提到的左半部分[mid,j)的贡献,由定义可知,左端点为i.右端点在[mid,i)中时,区间的最大值即为统计的 max,故这些区间的总贡献为(r-j)*max,选A。

42.④处应填()
A. (long long)(r – j)* max
B. (long long)(r – j)* (mid – i) * max
C. sum[r – mid] – sumlj – mid]
D. (sum[r – mid] – sum[j – mid]) * (mid – i)
【答案】 C
【解析】 该部分在统计 40 题的解析提到的右半部分)的贡献,由定义可知,左端点为 i右端点在[i,r)中时,区间的最大值即为max{amid,amid+1,…,ax}=prex,故这些区间的总贡献为
2023 CCF第一轮认证CSP-J提高级C++真题及解析

43.⑤处应填()
A. solve(0,n)
B. solve(0, n – 1)
C. solve(1,)
D. solve(1, n – 1)
【答案】A
【解析】根据 solve 中的实现和边界条件 if(l+ 1== r),可以发现 solve(l,r)在统计区间[l,r)中的答案,故应为 solve(0,n),选择 A。

那年 • 今日
发布于2023-09-16 23:00
没有伞的孩子,必须学会努力奔跑。

赞助 点赞 4

王润泽, ejsoon, 独元殇, 阿和, 青灯暮雨等人对本文发表了10条热情洋溢的评论。
  • 王润泽说道: 2
    太卷了,从娃娃抓起
  • ejsoon说道: 0
    年初用c++做過東西,但是,要我去考試,可能會不及格…
  • 独元殇说道: 2
    啥时候降温呐~ (ó﹏ò。)
    1. 老王说道:
      回复 独元殇: 差不多要到月底了。。。😀
  • 阿和说道: 6
    把试卷搬到电脑上,还要排版处理,真是有耐心啊
    1. 老王说道:
      回复 阿和: 说明WordPress真的强大,欢迎加入。。😏
      1. 阿和说道: 6
        回复 老王: 年纪大了,折腾不动了
        1. 老王说道:
          回复 阿和: 你都说年纪大了,让我们这些老人家情何以堪。。。
  • 青灯暮雨说道: 1
    现在的娃太强了,自愧不如 ::wb:wl::
    1. 老王说道:
      回复 青灯暮雨: 也没有呀,才刚学。。。
  • 发表回复

    您的电子邮箱地址不会被公开。 必填项已用 * 标注