2024年CSP-S1 提高级试题

ID: 2552

Type: Default

1000ms

256MiB

Tried: 0

Accepted: 0

Difficulty: (None)

Uploaded By:

admin

Tags>

其他

csp-j初赛

No testdata at current.

2024 CCF 非专业级别软件能力认证第一轮

(CSP-S1) 提高级 C++语言试题

认证时间：2024年9月21日 14:30~16:30

考生注意事项：
• 该题纸共有16页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。
• 不得使用任何电子设备（如计算机、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（） {{ select(1) }}

pwd
cd
ls
echo

假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的，要找到这个数组中最大元素的时间复杂度是多少？（） {{ select(2) }}

O(n)
O(log n)
O(n log n)
O(1)

在C++中，以下哪个函数调用会造成栈溢出？（） {{ select(3) }}

int foo() { return 0; }
int bar() { int x = 1; return x; }
void baz() { int a[1000]; baz(); }
void qux() { return; }

在一场比赛中，有10名选手参加，前三名将获得金、银、铜牌。若不允许并列，且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？（） {{ select(4) }}

120
720
504
1080

下面哪个数据结构最适合实现先进先出（FIFO）的功能？（） {{ select(5) }}

栈
队列
线性表
二叉搜索树

已知f(1) = 1，且对于n ≥ 2有f(n) = f(n - 1) + f(⌊n/2⌋)，则f(4)的值为：（） {{ select(6) }}

假设有一个包含n个顶点的无向图，且该图是欧拉图，以下关于该图的描述中哪一项不一定正确？（） {{ select(7) }}

所有顶点的度数均为偶数
图是连通的
图中存在一个欧拉回路
图的边数是奇数

对数组进行二分查找的过程中，以下哪个条件必须满足？（） {{ select(8) }}

数组必须是有序的
数组必须是无序的
数组长度必须是2的幂
数组中的元素必须是整数

考虑一个自然数n以及一个模数m，你需要计算n的逆元（即n在模m意义下的乘法逆元）。下列哪种算法最为适合？（） {{ select(9) }}

使用暴力法依次尝试
使用扩展欧几里得算法
使用快速幂法
使用线性筛法

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

O(1)
O(log n)
O(1 / (1 - α))
O(n)

假设有一棵h层的完全二叉树，该树最多包含多少个结点？（） {{ select(11) }}

2^h-1
2^(h+1)-1
2^h
2^(h+1)

设有一个10个顶点的完全图，每两个顶点之间都有一条边，有多少个长度为4的环？（）
{{ select(12) }}

120
210
630
5040

对于一个整数n，定义f(n)为n的各位数字之和。问使f(f(x))=10的最小自然数x是多少？（） {{ select(13) }}

设有一个长度为n的01字符串，其中有k个1，每次操作可以交换相邻两个字符。在最坏情况下将这k个1移到字符串中最右边所需要的交换次数是多少？（） {{ select(14) }}

k
k*(n-k)/2
(n-k)*k
(2n-k-1)*k/2

如图是一张包含7个顶点的有向图，如果要删除其中一些边，使得从节点1到节点7没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（） {{ select(15) }}

A. 1
B. 2
C. 3
D. 4

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

#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(4, b, c);
    recursion(a, c, b);
    for (int i = 0; i < b; ++i) cout << c[i] << " ";
    cout << endl;
}

• 判断题 16. 当1000≥d≥b时，输出的序列是有序的。（） {{ select(16) }}

正确
错误

当输入"5 5 1"时，输出为"1 1 5 5 5"。（） {{ select(17) }}

正确
错误

假设数组c长度无限制，该程序所实现的算法的时间复杂度是O(b log b)。（） {{ select(18) }}

正确
错误

• 单选题

函数 int logic(int x, int y) 的功能是（） {{ select(19) }}

按位与
按位或
按位异或
以上都不是

(4分) 当输入为 "10 100 100" 时，输出的第 100 个数是（） {{ select(20) }}

(2)

#include <iostream>
#include <string>
using namespace std;

const int P = 998244353, N = 1e4+10, M = 26;
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; 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 + i!=1 * dp[i]) % P;
    }
    return ans;
}
int solve2() {
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < (1<<n); ++i) {
        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;
}

假设输入的s是包含n个字符的01串，完成下面的判断题和单选题：

• 判断题 21. 假设数组dp长度无限制，函数solve()所实现的算法的时间复杂度是O(n*2^n)。（） {{ select(21) }}

正确
错误

输入"11 2 100000000001"时，程序输出两个数32和23。（ √ ） {{ select(22) }}

正确
错误

(2分)在n≤10时，solve()的返回值始终小于4^m。（ √ ） {{ select(23) }}

正确
错误

• 单选题 24. 当n = 10且m = 10时，有多少种输入使得两行的结果完全一致？（） {{ select(24) }}

1024
11
10
6

当n <= 6时，solve()的最大可能返回值为（） {{ select(25) }}

65
211
665
2059

若n = 8，m = 8，solve和solve2的返回值的最大可能的差值为（） {{ select(26) }}

1477
1995
2059
2187

(3)

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

const int maxn = 100000+5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;

const long long l1;

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 = (lll * h1 * plh(h.l) + h.h1) % P1;
        hh.h2 = (lll * h2 * p2l(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] = (lll * B1 * p1[i-1]) % P1;
        p2[i] = (lll * 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;
}

• 判断题 27. 假设程序运行时能自动将maxn改为n+1，所实现的算法的时间复杂度是O(n log n)。（ × ） {{ select(27) }}

正确
错误

时间开销的瓶颈是init()函数。（） {{ select(28) }}

正确
错误

若修改常数B1或K1的值，该程序可能会输出不同的结果。（） {{ select(29) }}

正确
错误

• 单选题 30. 在solve()函数中，h[]的合并顺序可以看作是：（） {{ select(30) }}

二叉树的BFS序
二叉树的先序遍历
二叉树的中序遍历
二叉树的后序遍历

输入“10”，输出的第一行是？（） {{ select(31) }}

83
424
54
1101010000

（4分）输入“16”输出的第二行是？（） {{ select(32) }}

三、完善程序（单选题，每小题3分，共计30分）

(1)（序列合并）有两个长度为n的单调不降序列A和B。序列的每个元素都是小于10^9的非负整数。在A和B中各取一个数相加可以得到N≥2个和，求其中第K小的和。上述参数满足N <= 10^5和1 <= K <= N^2。

#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;
}

①处应填（） A. an-a
B. an-a-1
C. ai
D. ai-1
②处应填（） A. a[mid] > ai
B. a[mid] >= ai
C. a[mid] < ai
D. a[mid] <= ai
③处应填（） A. a+1
B. an+1
C. a+1-1
D. an-1
④处应填（） A. a[n-1]+b[n-1]
B. a[n]+b[n]
C. 2 * maxn
D. maxn
⑤处应填（） A. get_rank(mid) < k
B. get_rank(mid) <= k
C. get_rank(mid) > k
D. get_rank(mid) >= k

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

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 2e5+10, maxm = 1e6+10, inf = 52213279;
int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn], c1, *dis2;
int pre[maxn], *pre2;
bool vis[maxn];
void add(int a, int b, int c) {
    nxt[tot] = head[a];
    head[a] = tot++;
    to[tot] = b;
    w[tot] = c;
}
void init() {
    memset(p, 1, sizeof(p));
    p[0] = p[1] = false;
    for (int i = 1; i <= n; ++i)
        p[2*i] = p[2*i+1] = 1;
    for (int i = 2; i <= n; ++i) {
        p[i] = (p[i>>1] && p[i-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. make_pair(-d, b)
B. make_pair(d, b)
C. make_pair(-b, d)
D. make_pair(b, d)
③处应填（） A. 0xff
B. 0x1f
C. 0x3f
D. 0x7f
④处应填（） 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. pre2[a%n]
B. pre[a%n]
C. pre2[a]
D. pre[a%n]+1

#V6. 2024年CSP-S1 提高级试题

2024 CCF 非专业级别软件能力认证第一轮

(CSP-S1) 提高级 C++语言试题

认证时间：2024年9月21日 14:30~16:30

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

(2)

(3)

三、完善程序（单选题，每小题3分，共计30分）

Status

Development

Support

#V6. 2024年CSP-S1 提高级试题

2024年CSP-S1 提高级试题

2024 CCF 非专业级别软件能力认证第一轮

(CSP-S1) 提高级 C++语言试题

认证时间：2024年9月21日 14:30~16:30

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

(2)

(3)

三、完善程序（单选题，每小题3分，共计30分）

Status

Development

Support

Don't have an account?

SIGN IN