首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 2024年CCF非专业级别软件能力认证第一轮 (CSP-S)提高级C++语言试题

2024年CCF非专业级别软件能力认证第一轮 (CSP-S)提高级C++语言试题 VIP

信息学奥赛-提高级 共 43 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

在Linux系统中,如果你想显示当前工作目录的路径,应该使用哪个命令?( )

  • A pwd
  • B cd
  • C Ls
  • D echo
查看答案与解析
答案:A
解析:

Linux基础知识。pwd是当前工作目录,cd是改变目录,Ls是查看文件列表,echo是输出内容

2. 单选题

假设一个长度为n的整数数组中每个元素互不相同,且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?( )

  • A O(n)
  • B O(log n)
  • C O(n log n)
  • D O(1)
查看答案与解析
答案:A
这道题暂未补解析。
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种情况,银牌9种,铜牌8种,10*9*8=720

5. 单选题

下面那个数据结构最适合实现先进先出(FIFO)的功能?( )

  • A 栈
  • B 队列
  • C 线性表
  • D 二叉搜索树
查看答案与解析
答案:B
解析:

队列的基础知识

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)=3,f(4)=f(3)+f(2)=5

7. 单选题

假设一个包含n个顶点的无向图,且该图是欧拉图。以下关于该图的描述中哪项不一定正确?( )

  • A 所有顶点的度数均为偶数
  • B 该图联通
  • C 该图存在一个欧拉回路
  • D 该图的边数是奇数
查看答案与解析
答案:D
解析:

通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图,称为欧拉图。很容易构造一个偶数条边的欧拉图

8. 单选题

对数组进行二分查找的过程中,以下哪个条件必须满足?( )

  • A 数组必须是有序的
  • B 数组必须是无序的
  • C 数组长度必须是2的幂
  • D 数组中的元素必须是整数
查看答案与解析
答案:A
解析:

二分查找的基础知识

9. 单选题

考虑一个自然数n以及一个模数m,你需要计算n的逆元(即n在模m意义下的乘法逆元)。下列哪种算法最为合适?( )

  • A 使用暴力方法依次尝试
  • B 使用扩展欧几里得解法
  • C 使用快速幂解法
  • D 使用线性筛法
查看答案与解析
答案:B
解析:

如果一个线性同余方程ax≡1(modb),则x称为a mod b的逆元,记作a-1。扩展欧几里德算法找到两个整数x和y满足ax+by=gcd(a, b)。当a和b互质时,即gcd(a,b)=1,这个方程变为ax+by=1。在模b意义下,ax与1在模b时同余,因此x就是a的模b的逆元。快速幂法使用了费马小定理,要求b是一个素数;而扩展欧几里得法只要求gcd(a,b)=1

10. 单选题

在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对,表的装载因子为α(0<α≤1)。在使用开放地址法解决冲突的过程中,最坏情况下查找一个元素的时间复杂度为( )?

  • A O(1)
  • B O(log n)
  • C O(1/(1-α))
  • D O(n)
查看答案与解析
答案:D
解析:

开放地址法当计算出来的地址被占用时,用再寻址的方法寻找下一个地址,如果还是占用就接着寻找,直到找到一个空的地址,在最坏情况下可能会遍历所有已经占用的地址

11. 单选题

假设有一颗h层的完全二叉树,该树最多包含( )个节点?

  • A 2h−1
  • B 2(h+1)−1
  • C 2h
  • D 2h+1
查看答案与解析
答案:A
解析:

第一层1,第二层2,第h层2h-1,加起来2h-1

12. 单选题

设有一个10个顶点的完全图,每两个顶点之间都有一条边,有多少个长度为4的环( )?

  • A 120
  • B 210
  • C 630
  • D 5040
查看答案与解析
答案:C
解析:

完全图,所以任意找四个点都可以构成长度为4的环,选4个点的方案数是C(10,4)=210。4个点的圆排列4!/4=6;无向图,所以正反方向视为同一种环,6/2=3。210*3=630

13. 单选题

对于一个整数n,定义f(n)为n的各个位数之和,问使f(f(x))=10的最小自然数x是( )?

  • A 29
  • B 199
  • C 299
  • D 399
查看答案与解析
答案:B
解析:

f(f(29))=f(11)=2,不满足,f(f(199))=f(19)=10,满足

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都在最左侧,此时,第K个1移到第n,需要(n-k)步,一共k*(n-k)

15. 单选题

如图是一张包含7个顶点的有向图。如果要删除一些边,使得从节点1到节点7没有可行路径,且删除的边数最少,请问总共有多少种可行的删除边的集合( )?

  • A 1
  • B 2
  • C 3
  • D 4
查看答案与解析
答案:D
解析:

首先发现至少需要删除两条边。枚举,可以找到四种删除方案,删除②→⑤和④→⑥、删除⑤→⑦和⑥→⑦、删除①→②和④→⑥、删除⑤→⑦和④→⑥

20. 单选题

函数int logic(int x,int y)的功能是()?

  • A 按位与
  • B 按位或
  • C 按位异或
  • D 以上都不是
查看答案与解析
答案:B
这道题暂未补解析。
21. 单选题

当输入为“10 100 100”时,输出的第100个数是()?

  • A

    91

  • B

    94

  • C

    95

  • D

    98

查看答案与解析
答案:C
这道题暂未补解析。
26. 单选题

当n=10且m=10时,有多少种输入使得两行的结果完全一致?()

  • A 1024
  • B 11
  • C 10
  • D 0
查看答案与解析
答案:B
这道题暂未补解析。
27. 单选题

当n≤5时,solve()的最大可能返回值为()?

  • A 65
  • B 211
  • C 665
  • D 2059
查看答案与解析
答案:C
这道题暂未补解析。
28. 单选题

若n=8,m=8,solve和solve2的返回值的最大可能的差值为()?

  • A 1477
  • B 1995
  • C 2059
  • D 2187
查看答案与解析
答案:C
这道题暂未补解析。
33. 单选题

在solve()函数种,h[]的合并顺序可以看作是()

  • A 二叉树的BFS序
  • B 二叉树的先序遍历
  • C 二叉树的中序遍历
  • D 二叉树的后序遍历
查看答案与解析
答案:C
这道题暂未补解析。
34. 单选题

输入“10”,输出的第一行是( )?

  • A 83
  • B 424
  • C 54
  • D 110101000
查看答案与解析
答案:A
这道题暂未补解析。
35. 单选题

输入“16”,输出的第二行是()?

  • A 7
  • B 9
  • C 10
  • D 12
查看答案与解析
答案:C
这道题暂未补解析。
37. 单选题

①处应填()

  • A an-a
  • B an-a-1
  • C ai
  • D ai+1
查看答案与解析
答案:A
这道题暂未补解析。
38. 单选题

②处应填()

  • A a[mid]>ai
  • B a[mid]≥ai
  • C a[mid]<ai
  • D a[mid]≤ai
查看答案与解析
答案:A
这道题暂未补解析。
39. 单选题

③处应填()

  • A a+l
  • B a+l+1
  • C a+l-1
  • D an-l
查看答案与解析
答案:A
这道题暂未补解析。
40. 单选题

④处应填()

  • A a[n-1]+b[n-1]
  • B a[n]+b[n]
  • C 2*maxn
  • D maxn37.
查看答案与解析
答案:A
这道题暂未补解析。
41. 单选题

处应填()

  • A get_rank(mid)<k
  • B get_rank(mid)≤k
  • C get_rank(mid)>k
  • D get_rank(mid)≥k
查看答案与解析
答案:A
这道题暂未补解析。
43. 单选题

⑤处应填()

  • A pre2[a%n]
  • B pre[a%n]
  • C pre2[a]
  • D pre[a%n]+1
查看答案与解析
答案:A
这道题暂未补解析。

二、简答题

16. 简答题

阅读程序

#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] << " ";
}
查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
22. 简答题
#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) {
        cout << solve2() << endl;
    }
    cout << solve() << endl;
    return 0;
}


查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
29. 简答题
#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 (int i = 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;
}
查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
36. 简答题

合并序列。有两个长度为N的单调不降序列A和B,序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和,求其中第k小的和。上述参数满足N≤105和1≤K≤N2。

#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 = ( ① );
    while (l < r) {
        int mid = (l + r) >> 1;
        if (②) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ( ③ );
}

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 =( ④ );
    while (l < r) {
        int mid = ((long long)l + r) >> 1;
        if  ( ⑤ ) {
            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;
}
查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
42. 简答题

次短路。已知有一个n个点m条边的有向图G,并且给定图中的两个点s和t,求次短路(长度严格大于最短路的最短路径)。如果不存在,输出一行“-1”。如果存在,输出两行,第一行表示此段路经的长度,第二行表示此段路的一个方案。

#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)  ( ① );
    q.push( ② );
    dis[b] = d;
    pre[b] = a;
    return true;
}

void solve() {
    priority_queue<pair<int, int> >q;
    q.push(make_pair(0, s));
    memset(dis,  ( ③ ), 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))
                   ( ④ );
            }
            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( ⑤ );
    }
    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;
}
查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。

三、判断题

17. 判断题

当1000≥d≥b时,输出的序列是有序的()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
18. 判断题

当输入“5 5 1”时,输出为“1 1 5 5 5”( )

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
19. 判断题

假设数组c长度无限制,该程序所实现的算法的时间复杂度是O(b)的( )

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
23. 判断题

假设输入的s是包含n个字符的01串,函数solve()所实现的算法时间复杂度是O(n*2m)()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
24. 判断题

输入“11 2 10000000001”时,程序输出两个数32和23()


  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
25. 判断题

在n≤10时,solve()的返回值始终小于410()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
30. 判断题

假设程序运行前能自动将maxn改为n+1,所实现的算法的时间复杂度是O(nlogn)()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
31. 判断题

时间开销的瓶颈是init()函数()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
32. 判断题

若修改常数B1或K1的值,该程序可能会输出不同的结果()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。