2024 LUOGU 非专业级别收容能力认证第一轮 (SCP-S1)提高级C++语言试题

认证时间:2024 年8 月18 日 14:30~16:30

考生注意事项:

• 试题纸共有13 页,满分100 分。请在洛谷作答,写在试题纸上的一律无效。
• 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。
• 试题由洛谷网校学术组命制,欢迎报名洛谷网校第一轮课程。课程内容包含专题讲解、真题讲评与本试题讲评。https://class.luogu.com.cn/course/yugu24acs

一、单项选择题(共15 题,每题2 分,共计30 分;每题有且仅有一个正确选项)

1. 下列编译命令,是CSP-S 第二轮评测时用于编译题目英文名为luogu 的传统型试题的选手代码的是( )。
   {{ select(1) }}

• gcc -std=c++14 -O2 -o * luogu.cpp
• g++ -std=c++14 -O2 -o * luogu.cpp
• g++ -O2 -o * luogu.cpp
• g++ -std=c++14 -o * luogu.cpp

2. 在2023 年的CSP-S 第二轮认证中,有四位同学对于某一题得0 分的情况提出了申诉。根据CCF NOI 竞赛委员会的相关规定,下列申诉中可能被接受的是( )。
   {{ select(2) }}

• 小明在提交的程序中并未删除用于输出调试信息的代码。
• 小红在提交的程序中使用了随机化算法。
• 小黄提交的程序在考场的Windows 电脑上正常编译,而在最终评测时编译失败。
• 小陈在与评测环境相同的电脑上运行程序,使用了850 毫秒运行得出正确答案,而该题的时间限制为1 秒。程序运行并未超出内存限制。

3. 大型语言模型(LLM)指使用大量文本数据训练的深度学习模型,它们可以生成自然语言文本或理解语言文本的含义。下列人工智能技术的应用中,不属于LLM 的是( )。
   {{ select(3) }}

• ChatGPT
• Stable Diffusion
• Gemini
• 文心一言

4. (47)₁₀与下列( )选项表示的数值一致?
   {{ select(4) }}

• ((56)_{8})
• ((1100110)_{2})
• ((142)_{5})
• ((2D)_{16})

5. 定义 正确 在模 p 意义下的乘法逆元为同余方程 (a x \equiv 1(\bmod p)) 的解 x 。请计算13 在模29 意义下的乘法逆元是( )。
   {{ select(5) }}

• 11
• 10
• 8
• 9

6. 仿照二项式系数,定义三项式系数 (T_{n}^{k}) 为 ((1+x+x^{2})^{n}) 的展开式中 (x^{k}) 项的系数。即:((1+x+x^{2})^{n}=T_{n}^{0}+T_{n}^{1} x^{1}+T_{n}^{2} x^{2}+\cdots+T_{n}^{2 n} x^{2 n}) 。现要计算 (T_{8}^{0}+T_{8}^{1}+T_{8}^{2}+\cdots+T_{8}^{16}) 的值,其结果为( )?
   {{ select(6) }}

• 4096
• 6561
• 8192
• 15625

7. 当在二叉排序树中插入一个新结点时,若树中不存在与待插入结点关键字相同的结点,且待插入结点的关键字小于根结点的关键字,则新结点将成为根结点的( )?
   {{ select(7) }}

• 左子树的某一叶子结点
• 右子树的某一叶子结点
• 左子树的某一非叶子结点
• 右子树的某一非叶子结点

8. 一个盒子里有4 个红球、5 个蓝球和6 个绿球。现在从盒子里随机抽取3 个球,则这3 个球中恰好有1 个红球、1 个蓝球和1 个绿球的概率是( )。
   {{ select(8) }}

• 136/455
• 24/91
• 5/66
• 1/11

9. 对前缀表达式 (- + 10 *2 3 + 5/62) 进行求值,得到的结果是()。
   {{ select(9) }}

• 8
• 9
• 10
• 11

10. 已知一个循环队列的存储空间为数组data q[21]且不浪费空间。且在队列的定义中,头指针指向队列的开头,尾指针指向队列末尾的下一个元素。现在若头指针和尾指针分别指向下标8 和3,则队列当前的长度为( )?
    {{ select(10) }}

• 5
• 6
• 17
• 16

11. 在使用下列算法对整数数列进行排序时,哪一个算法的运行时间复杂度与整数大小无关( )。
    {{ select(11) }}

• 基数排序
• 计数排序
• 希尔排序
• 以上排序算法的运行时间复杂度均与整数大小有关

12. 假设变量a,b,c 均为绝对值不超过 10⁹ 的32 位有符号整型变量,下列关于这三个变量,说法正确的是( )。
    {{ select(12) }}

• 若执行代码auto d = 正确 * b; 则d 的变量类型是64 位有符号整型变量。
• 逻辑表达式max(a, b) * 1LL * c == max(1LL * 正确 * c, 1LL * b * c) 的运算结果一定为真。
• 执行代码cout << sizeof(a); 后,输出的结果为4。
• for (unsigned i = a; i < b; i++) 可能是一个死循环。

13. 对于以下代码,假设执行单次rand()函数的时间复杂度为O(1),那么calc 函数的运行时间复杂度为?( )
    {{ select(13) }}

• Θ(n)
• (\Theta(n log n))
• (\Theta\left(n log ^{2} n\right))
• (\Theta\left(n log ^{3} n\right))

14. 给定一个无向图G,其中包含以下顶点和边:顶点集合:V = {A, B, C, D, E} 边集合:E = {(A, B), (A, C), (B, C), (B, D), (C, D), (C, E)} 请问以下哪一个选项正确描述了图G 的双连通性?( )。
    {{ select(14) }}

• 图G 是点双连通的,因为删除任意一个顶点后,图仍然连通。
• 图G 不是点双连通的,因为存在割点。
• 图G 是边双连通的,因为存在至少两个顶点的简单环。
• 图G 不是边双连通的,因为删除任意一条边后,图不再连通。

15. 使用哈希表存储元素 19,53,49,114,为了让哈希表不发生哈希冲突,可以使用( )选项的哈希函数?(定义:⌊x⌋ 为不超过 x 的最大整数,如 ([3.14] =3))
    {{ select(15) }}

• (f(x)=x mod 17)
• (f(x)=\lfloor\sqrt{x}\rfloor)
• (f(x)=\lfloor 100 lg x\rfloor)
• (f(x)=x^{2} mod 13)

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填A,错误填B;除特殊说明外,判断题1.5 分,选择题3 分,共计40 分)

（1）

#include <bits/stdc++.h>  
using namespace std;  
set <int> s1 = {1, 2, 3}, s2 = {2, 3, 1, 1},  
s3 = {1, 2, 100}, s4 = {3, 4, 5};  
map <set <int>, int> mp1, mp2;  
set <int> intersection(set <int> a, set <int> b) {  
    if (a.size() > b.size()) swap(a, b);  
    set <int> res = a;  
    for (int i : a)  
        if (b.count(i) == 0)  
            res.erase(i);  
    return res;  
}  
int main() {  
    cout << (s1 == s2) << endl;  
    mp1[s3] = 9; mp1[s1] = 1;  
    mp2[s2] = 1; mp2[s4] = 5;  
    cout << (mp1 < mp2) << ' ';  
    cout << mp2[s3] << ' ';  
    cout << (mp1 <= mp2) << endl;  
    mp1.clear();  
    int n, l, t;  
    cin >> n;  
    for (int i = 1; i <= n; i++) {  
        set <int> tmp;  
        for (cin >> l; l; l--) {  
            cin >> t;  
            tmp.emplace(t);  
        }  
        mp1[tmp] = i;  
    }  
    set <int> res = mp1.begin()->first;  
    for (auto i : mp1)  
        res = intersection(i.first, res);  
    cout << res.size();  
    return 0;  
}  

判断题

16. 代码运行后,输出的第一行是0。( )
    {{ select(16) }}

• 正确
• 错误

17. 设集合a,b 的元素个数分别为p,q,则执行函数intersection(a,b)的时间复杂度为 Θ(min(p, q) log max(p, q))。( )
    {{ select(17) }}

• 正确
• 错误

18. 将第32 行的begin()换成rbegin(),运行结果可能改变。( )
    {{ select(18) }}

• 正确
• 错误

19. 将第33 行的auto 换成pair <set , int>,运行结果不变。( )
    {{ select(19) }}

• 正确
• 错误

单选题

20. 输出的第二行是( )。
    {{ select(20) }}

• 0 0 0
• 1 0 1
• 0 1 1
• 1 0 0

21. 记所有输入的l 之和为L,则该程序最坏情况下的时间复杂度是( )?
    {{ select(21) }}

• (\Theta(L log L))
• (\Theta\left(L log ^{2} L\right))
• Θ(nL log L)
• (\Theta(n L log n log L))

（2）

#include <bits/stdc++.h>  
using namespace std;  
constexpr int mod = 998244353;  
int n, k, a[12], b[12], ans[12], fa[12];  
int findfa(int u) { return u == fa[u] ? u : fa[u] = findfa(fa[u]); }  
int functionUnknown(int a[], int n) {  
    if (n <= 1) return 0;  
    int i = n - 1, j, k;  
    while (true) {  
        j = i; --i;  
        if (a[i] < a[j]) {  
            for (k = n; a[i] >= a[--k];);  
            swap(a[i], a[k]);  
            reverse(a + j, 正确 + n);  
            return 1;  
        }  
        if (!i) {  
            reverse(a, 正确 + n);  
            return 0;  
        }  
    }  
    return -1;  
}  
int F(int x){  
    int ans=0;  
    for(int i=k-1;~i;--i)  
        ans=(111*ans*x%mod+a[i])%mod;  
    return ans;  
}  
int main(){  
    scanf("%d%d",&n,&k);  
    for(int i=0;i<k;++i)scanf("%d",a+i);  
    for(int m=1;m<=n;++m){  
        for(int i=0;i<m;++i)b[i]=i;  
        do {  
            for(int i=0;i<m;++i)fa[i]=i;  
            int res=m;  
            for(int i=0,u,v;i<m;++i){  
                u = findfa(i);v= findfa(b[i]);  
                if(u==v)continue;  
                --res; fa[u]=v;  
            }  
            int flag=0;  
            for(int i=0;i<m;++i)  
                if(b[i]==i)flag=1;  
            if (flag)continue;  
            ans[m]=(ans[m]+F(res))%mod;  
        }while(functionUnknown(b,m));  
        printf("%d%c",ans[m]," \n"[m==n]);  
    }  
    return 0;  
}  

判断题

22. functionUnknown函数的返回值不可能为-1。()
    {{ select(22) }}

• 正确
• 错误

23. 当输入的 (k=1) 时,输出的数值均能表示为 (t ×a[0]) 的形式,其中t是一个整数。()
    {{ select(23) }}

• 正确
• 错误

24. 如果把第34 行整行改为 (b[m-1]=m-1) ,则程序输出将会被改变。()
    {{ select(24) }}

• 正确
• 错误

单选题

25. 在主函数中,findfa 函数被调用的次数与以下哪个选项同阶( )。
    {{ select(25) }}

• Θ(n!)
• (\Theta(n ! n))
• (\Theta\left(n ! n^{2}\right))
• (\Theta\left(n ! n^{3}\right))

26. 对于以下的输入数据,输出结果为( )。
    5 5
    1 2 3 4 5
    {{ select(26) }}

• 0 15 30 261 1500
• 0 12 24 297 1788
• 0 15 30 477 2940
• 0 15 30 864 5520

27. functionUnknown 的功能接近于 C++ STL 库中的以下( )函数。
    {{ select(27) }}

• next_permutation
• prev_permutation
• is_sorted
• is_permutation

（3）

#include <bits/stdc++.h>  
using namespace std;  
unsigned f(unsigned x) {  
    x ^= x << 3;  
    x ^= x >> 5;  
    return x;  
}  
unsigned g(unsigned x) {  
    return (x >> 5) ^ (x >> 2) ^ x ^ (x << 3);  
}  
int main() {  
    unsigned y, l, r;  
    cin >> y >> l >> r;  
    for (unsigned long long i = l; i <= r; i++)  
        if (f(i) == y)  
            cout << i % 11 << endl;  
    return 0;  
}  

判断题

28. 若输入 2024 1 -1,那么程序将不会输出任何数字。( )
    {{ select(28) }}

• 正确
• 错误

29. 若把第14 行i 的类型改为unsigned int,则程序可能无法结束运行。( )
    {{ select(29) }}

• 正确
• 错误

30. 对于所有符合要求的输入,输出的数字不可能超过一个。( )
    {{ select(30) }}

• 正确
• 错误

选择题

31. 若从所有unsigned int 当中随机均匀选取一个x，则 (f(x)=g(x)) 成立的概率和( )的差最小。
    {{ select(31) }}

• 0
• (\frac{1}{15})
• (\frac{1}{2})
• 1

32. (4 分)定义 (f^{n}(x)) 表示对 x 用函数 f 作用 n 次的结果,例如 (f^{2}(x)=f(f(x))) 假设unsigned 类型具有 ω 个二进制位,且已知存在某种计算 (f^{n}(x)) 的算法的时间复杂度为 (\Theta(T(n) P(\omega))) ,其中 (P(\omega)) 是一个关于 ω 的幂函数。则 (T(n)) 最小是( )?
    {{ select(32) }}

• Θ(1)
• Θ(log n)
• (\Theta\left(log ^{2} n\right))
• Θ(n)

33. 当输入为 50 1 4294967295 时,输出的第一个数是( )。
    {{ select(33) }}

• 1
• 8
• 9
• 10

三、完善程序(单选题,每小题3 分,共计30 分)

（1）(最小垄断集)

问题:你有一张n 个结点(结点编号从1 到n),m 条边的无向无权图 (G=(V, E)) ,其中V 为点集,E 为边集。称V 的一个子集S 垄断了图G,当且仅当 (\forall(u, v) \in E) , u,v 中必然恰有一个结点在S 内。求垄断了G 的子集S 至少有多少个元素,或报告不存在这样的子集。试补全程序。

#include <bits/stdc++.h>  
using namespace std;  
int n, m, is[100005];  
vector <int> g[100005];  
queue <int> q;  
int main() {  
    cin >> n >> m;  
    for (int i = 1; i <= m; i++) {  
        int u, v;  
        cin >> u >> v;  
        g[u].emplace_back(v);  
        g[v].emplace_back(u);  
    }  
    int tot = 0;  
    for (int k = 1; k <= n; k++) {  
        if (①) continue;  
        q.emplace(k);  
        is[k] = 1;  
        int cnt[3] = ②;  
        while (q.size()) {  
            for (int i = 0; i < g[q.front()].size(); i++) {  
                int to = g[q.front()][i];  
                if (is[to] == 0) {  
                    is[to] = ③;  
                    cnt[is[to]]++;  
                    q.emplace(to);  
                } else if (④) {  
                    puts("No such subset.");// 报告不存在这样的子集  
                    return 0;  
                }  
            }  
            q.pop();  
        }  
        tot += ⑤;  
    }  
    cout << tot;  
    return 0;  
}  

34. ①处应填( )
    {{ select(34) }}

• is[k]
• is[k] == 0
• q.empty()
• tot > k

35. ②处应填( )
    {{ select(35) }}

• {0, 0, 0}
• {0, 0, 1}
• {1, 0, 0}
• {0, 1, 0}

36. ③处应填( )
    {{ select(36) }}

• is[q.front()]
• 3 – is[q.front()]
• !is[q.front()]
• q.front()

37. ④处应填( )。
    {{ select(37) }}

• is[to] == is[q.front()]
• is[to] != is[q.front()]
• is[to] && is[q.front()]
• abs(is[to] – is[q.front()]) == 1

38. ⑤处应填( )。
    {{ select(38) }}

• cnt[1]
• min(cnt[0], cnt[1])
• min(cnt[1], cnt[2])
• cnt[1]+cnt[2]

（2）(最长公共前缀)

定义LCP(s,t)为两个字符串的最长公共前缀。例如:s=abcde, t=abcabc,则 (LCP(s, t)=abc) 。定义 (|s|) 为字符串s 的长度,在上一例中 (|s|=5) 。现在给定了 n 个字符串 (s_{1}, s_{2}, ..., s_{n}) 。现在需要统计所有同时满足如下两个条件的 (|LCP(s_{i}, s_{j})|) 之和对 998244353 取模的值:条件1: (i<j) 。条件2: (s_{i}<s_{j}) 。若 (1 ≤n ≤2 ×10^{5}) , (1 \leq|s_{i}| ≤20) ,字符串仅由小写字母构成,试补全程序。

#include <bits/stdc++.h>  
using namespace std;  
const int maxn = 2e5 + 9, mod = 998244353;  
char s[maxn][22];  
int n;  
int tmp[27][maxn], a[maxn];  
int dfs(int l, int r, int p) {  
    if (l >= r || p >= 20) return 0;  
    int tail[27], ans = 0;  
    memset(tail, 0, sizeof(tail));  
    for (int i = l; i <= r; ++i) {  
        int ch = ①;  
        ②;  
        for (int j = 0; j < ch; ++j)  
            ③;  
    }  
    int tot = l,pos = l;  
    for (int i = 0; i < 27; ++i)  
        for (int j = 0; j < tail[i]; ++j)  
            a[tot++] = tmp[i][j];  
    for (int i = 0; i < 27; ++i) {  
        ④;  
        pos +=tail[i];  
    }  
    return ans;  
}  
int main() {  
    scanf("%d", &n);  
    for (int i = 1; i <= n; ++i)  
        scanf("%s", s[i]);  
    for (int i = 1; i <= n; ++i)  
        a[i] = i;  
    printf("%d\n", ⑤);  
    return 0;  
}  

39. ①处可以填( )
    {{ select(39) }}

• s[i][p] ? s[i][p] - 'a': 0
• s[i][p] ? s[i][p] - 'a' + 1 : 0
• s[a[i]][p] ? s[a[i]][p] - 'a': 0
• s[a[i]][p] ? s[a[i]][p] - 'a' + 1 : 0

40. ②处应填( )
    {{ select(40) }}

• tmp[ch][tail[ch]++] = a[i]
• tmp[ch][++tail[ch]] = a[i]
• tmp[ch][tail[ch]++] = i
• tmp[ch][++tail[ch]] = i

41. ③处应填( )
    {{ select(41) }}

• ans = (ans + 1ll * (p - 1) * tail[j] % mod) % mod
• ans = (ans + 1ll * p * tail[j] % mod) % mod
• ans = (ans + 1ll * (p + 1) * tail[j] % mod) % mod
• ans = (ans + 1ll * (p + 2) * tail[j] % mod) % mod

42. ④处应填( )。
    {{ select(42) }}

• ans = (ans + dfs(pos + 1, pos + tail[i], p + 1)) % mod
• ans = (ans + dfs(pos + 1, pos + tail[i], p - 1)) % mod
• ans = (ans + dfs(pos, pos + tail[i] - 1, p + 1)) % mod
• ans = (ans + dfs(pos, pos + tail[i] - 1, p - 1)) % mod

43. ⑤处应填( )。
    {{ select(43) }}

• dfs(0, n - 1, 0)
• dfs(1, n, 0)
• dfs(1, n, 1)
• dfs(1, n - 1, 1)