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

认证时间:2024 年8 月11 日 09:30~11:30

考生注意事项:

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

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

1. C++是一种面向对象的程序设计语言。在C++中,下面哪个关键字用于声明一个类,其缺省继承方式为private 继承?( )
   {{ select(1) }}

• union
• struct
• class
• enum

2. 下述代码实现的数据结构是( )。

int data[100], f = 1, r;  
void insert(int value) {  
    data[++r] = value;  
}  
void pop() {  
    f++;  
}  

{{ select(2) }}

• 链表
• 栈
• 队列
• 平衡树

3. C++语言中,以0b 开头的数为( )进制数。
   {{ select(3) }}

• 二进制
• 八进制
• 十进制
• 十六进制

4. 根结点的高度为1,高度为5 的完全二叉树至少有( )个结点。
   {{ select(4) }}

• 15
• 16
• 31
• 32

5. 右图所示的二叉树,其后序遍历的结果是什么?( )

{{ select(5) }}

• acedgbf
• fbacdge
• edgcabf
• egdcfba

6. 考虑右图所示的数字电路,有关逻辑门的含义已在图中标出。高电平表示true,低电平表示false。当x,y,z 的输入依次为低电平、高电平、高电平时,输出为( )。

{{ select(6) }}

• 高电平
• 低电平
• 电路故障
• 高阻

7. 十进制数10.375 转换为八进制数的结果为( )。
   {{ select(7) }}

• 10.5
• 10.3
• 12.5
• 12.3

8. 假设有一组字符{g,h,i,j,k,l},它们对应的频率分别为8%,14%,17%,20%,23%,18%。请问以下哪个选项是字符g,h,i,j,k,l 分别对应的一组哈夫曼编码?( )
   {{ select(8) }}

• g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
• g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
• g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
• g: 110, h: 111, i: 101, l: 100, k: 0, j: 01

9. 中缀表达式 ((6 – 3) * 2 + 7) / (5 ^ (3 * 4 + 2))对应的后缀表达式为( )。
   {{ select(9) }}

• /+-6327 ^ 5+ 342
• 632-* 7+534 * 2+^ /
• 63-2 * 7+534 * 2+^ /
• 63-2 * 7+34 * 2+5 ^ /

10. 将3 个相同的红球和3 个相同的黑球装入三个不同的袋中,每袋均装2 个球,则不同的装法总数为( )。
    {{ select(10) }}

• 7
• 8
• 9
• 10

11. 从2 至8 的7 个整数中随机取2 个不同的数,这两个数互质的概率为( )。
    {{ select(11) }}

• 1/6
• 1/3
• 1/2
• 2/3

12. 以下哪一种算法典型地使用了分治法的思想来解决问题?( )
    {{ select(12) }}

• 线性搜索
• 快速排序
• 冒泡排序
• 插入排序

13. 奇偶校验编码是常见的校验编码方式。对于二进制编码 $A_{n} A_{n-1} ... A_{2} A_{1}$ ,奇偶校验编码在编码的最后增加一位校验位G,并将原编码与校验位作为整体发送。校验位分为奇校验位与偶校验位,奇校验位保证 $A_{n} xor A_{n-1} xor ... xor A_{2} xor A_{1} xor G=1$ ,偶校验位保证 $A_{n} XorA_{n-1}xor…xorA_2xorA_1xorG=0$。下列编码与校验位对应正确的是( )。
    {{ select(13) }}

• 编码11100111 奇校验位0
• 编码01100010 偶校验位0
• 编码00010010 奇校验位1
• 编码11100010 偶校验位1

14. 下列关于NOI 系列活动的有关说法,错误的是( )。
    {{ select(14) }}

• NOI 考试对C++语言的使用没有限制。
• 选手不可以携带草稿纸、手机、U 盘等进入考场。
• 主办单位CCF 的全称为中国计算机学会。
• 在CSP 第一轮考试中舞弊,可能会被给予取消考试资格、禁赛等处罚。

15. 考虑右图所示的无向图,度最大的结点为( )号结点。

{{ select(15) }}

• 3
• 4
• 5
• 6

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

（1）

#include <bits/stdc++.h>  
using namespace std;  
int x, y;  
unsigned int n;  
int main() {  
    cin >> n >> x >> y;  
    unsigned int mask = 0xff;  
    int x8 = x << 3;  
    int y8 = y << 3;  
    unsigned int nx = (n >> x8) & mask, ny = (n >> y8) & mask;  
    n &= (~(mask << x8));  
    n &= (~(mask << y8));  
    n |= (nx << y8);  
    n |= (ny << x8);  
    cout << "0x";  
    cout << std::hex << n << endl;  
    return 0;  
}  

判断题

16. 代码中mask 变量的值转化为二进制的低16 位结果是0000 0000 1111 1111。( )
    {{ select(16) }}

• 正确
• 错误

17. 当输入 $x=0$ 的时候,nx 表示n 中最低八位对应的字节的数据。( )
    {{ select(17) }}

• 正确
• 错误

18. 去掉程序第11 行至第12 行中(~(mask << x8))和(~(mask << y8))两处中的最内层括号不会改变程序的结果。( )
    {{ select(18) }}

• 正确
• 错误

单选题

19. 当输入为“15078 0 1”时,变量nx,ny 的值分别为多少?( )
    (提示:十进制数15078 与十六进制数3AE6 相同)
    {{ select(19) }}

• 0xE6, 0x3A
• 0x6, 0xE0
• 0x6, 0xE
• 0x6, 0xA

20. 当输入为“23270 0 1”时,输出为( )。
    (提示:十进制数23270 与十六进制数5AE6 相同)
    {{ select(20) }}

• 0x5A6E
• 0x5E6A
• 0xA56E
• 0xE65A

21. 以下哪一个变量的类型修改可能影响程序的输出?( )
    {{ select(21) }}

• 将x,y 修改为unsigned int 类型。
• 将x8,y8 修改为short 类型。
• 将mask 修改为int 类型。
• 将nx,ny 修改为unsigned long long 类型。

（2）

#include <bits/stdc++.h>  
using namespace std;  

int n, k;  

int func(vector <int> &nums) {  
    int ret = 0;  
    for(int i = n; i > k; i--) {  
        if(nums[i] > nums[i - k]) {  
            swap(nums[i], nums[i - k]);  
            ret++;  
        }  
    }  
    return ret;  
}  

int main() {  
    cin >> n >> k;  
    vector <int> a(n + 1, 0);  
    for(int i = 1; i <= n; i++)  
        cin >> a[i];  
    int counter = 0, previous = -1;  
    while(counter != previous){  
        previous = counter;  
        counter += func(a);  
    }  
    for(int i = 1; i <= n; i++)  
        cout << a[i] << ",";  
    cout << endl << counter << endl;  
    return 0;  
}  

判断题

22. 当输入的k 为1,程序将a 从小到大排序。( )
    {{ select(22) }}

• 正确
• 错误

23. 在题目限制的输入规模下,counter 可能会溢出。( )
    {{ select(23) }}

• 正确
• 错误

24. (1 分)当输入为“8 1 1 9 2 3 4 6 8 7”,输出共有18 个可见字符。( )
    {{ select(24) }}

• 正确
• 错误

单选题

25. 当输入的k 为1,该程序的排序方法最接近( )。
    {{ select(25) }}

• 冒泡排序
• 选择排序
• 计数排序
• 插入排序

26. 该程序的时间复杂度为( )。
    {{ select(26) }}

• $O\left(n+k^{2}\right)$
• $O\left(n^{2}\right)$
• $O(n k)$
• $O\left(\frac{n^{2}}{k}\right)$

27. 当输入为“8 3 1 5 2 6 3 7 4 8”,输出的第一行第三个数字为( )。
    {{ select(27) }}

• 2
• 6
• 7
• 8

（3）

#include <iostream>  
#include <vector>  
#include <queue>  
using namespace std;  
const int MAXN = 200001;  
int main() {  
    int n, m, l, r, w;  
    cin >> n >> m;  
    vector <int> dist(MAXN, -1);  
    vector <bool> vis(MAXN, false);  
    vector <vector <pair<int, int> > > go(MAXN);  
    for(int i = 1; i <= m; i++) {  
        cin >> l >> r >> w;  
        go[l].push_back(make_pair(r + 1, w));  
        go[r + 1].push_back(make_pair(l, -w));  
    }  
    queue <int> q;  
    dist[1] = 0, vis[1] = true;  
    q.push(1);  
    while(!q.empty()) {  
        int x = q.front(); q.pop();  
        for(auto i : go[x]) {  
            if(!vis[i.first]) {  
                vis[i.first] = true;  
                dist[i.first] = dist[x] + i.second;  
                q.push(i.first);  
            }  
        }  
    }  
    if(dist[n + 1] == -1) cout << "sorry" << endl;  
    else cout << dist[n + 1] << endl;  
    return 0;  
}  

判断题

28. 交换程序的第14 行与第15 行,不影响程序运行的结果。( )
    {{ select(28) }}

• 正确
• 错误

29. 输入的r 的最大值为n 时,程序可以正常运行。( )
    {{ select(29) }}

• 正确
• 错误

30. 在程序的第17 行至第29 行,相同的数可能重复进入队列。( )
    {{ select(30) }}

• 正确
• 错误

选择题

31. 当输入的l 最小值为x,输入的r 的最大值为y,最多有( )个元素进入过队列。
    {{ select(31) }}

• 1
• $y-x$
• $y-x+1$
• $y-x+2$

32. 当输入的n为偶数,且 $r=l+1$ 时,m至少为()时输出不为sorry。
    {{ select(32) }}

• n/2
• n/2+1
• n/2-1
• n

33. 当输入为"5 3 1 3 4 3 4 2 4 5 3"时,输出为()。
    {{ select(33) }}

• 4
• 5
• 6
• 7

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

（1）(优美的进制)

问题:给出整数n:k进制是优美的,当且仅当n在k进制下至少有两位,且每一位的数值都不同。求对于给定的n,有哪些进制是优美的,不存在则输出-1。
试补全程序。

#include <bits/stdc++.h>  
using namespace std;  
const int MAXN = 100000;  
int n;  
int vis[MAXN], a[MAXN];  
vector<int> ans;  
int check(int k) {  
    int x = n, top = 0;  
    for(int i = 0; i <= k; i++) vis[i] = 0;  
    while (①) {  
        a[++top] = ②;  
        x = ③;  
    }  
    if(top < 2)  
        return 0;  
    for(int i = 1; i <= top; i++) {  
        if(④)  
            return 0;  
        vis[a[i]] = 1;  
    }  
    return 1;  
}  
int main() {  
    cin >> n;  
    for(int i = ⑤; i <= n; i++) {  
        if(check(i))  
            ans.push_back(i);  
    }  
    if(ans.empty()) {  
        cout << -1;  
    }  
    for (int i = 0; i < ans.size(); i++)  
        cout << ans[i] << " ";  
    return 0;  
}  

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

• x > 0
• x > 1
• x/k > 0
• x/k > 1

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

• x/k
• x%k
• (x-1)/k+1
• (x-1)%k+1

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

• x/k
• x%k
• (x-1)/k+1
• (x-1) % k+1

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

• vis[i] == 1
• vis[a[i]] == 0
• vis[i] == 0
• vis[a[i]] == 1

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

• 1
• n-1
• 2
• 0

（2）(好运的日期)

一个日期可以用x年y月z日来表示。我们称一个日期是好运的,当且仅当xy(w-z+1)为质数,其中w为x年y月的总天数。输入x,y,z,判断其对应的日期是否好运。保证x是不超过2024的正整数,y是不超过12的正整数,x,y,z可以构成一个合法的日期。
试补全线性筛法算法,空间限制512MiB。

#include<bits/stdc++.h>  
using namespace std;  

const int MAXW = ①;  
const int days[13] = {0,31, ,31,30,31,30,31,31,30,31,30,31};  
int prime[MAXW], cnt;  
bool not_prime[MAXW];  

void linear_prime(int n) {  
    --n;  
    not_prime[0] = not_prime[1] = true;  
    for(int i = 2; i <= n; i++) {  
        if(not_prime[i] == false)  
            prime[++cnt] = i;  
        for(int j = 1; ②; j++) {  
            not_prime[i * prime[j]] = 1;  
            if(i % prime[j] == 0)  
                ③;  
        }  
    }  
}  

bool check(int n) {  
    return ④;  
}  

int main() {  
    linear_prime(MAXW);  
    int x, y, z, w;  
    cin >> x >> y >> z;  
    if(y == ⑤)  
        w = check(x) ? 29 : 28;  
    else  
        w = days[y];  
    if(not_prime[x * y * (w – z + 1)])  
        cout << "unlucky" << endl;  
    else  
        cout << "lucky" << endl;  
    return 0;  
}  

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

• 753005
• 10000000000
• 725041
• 2024

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

• j <= cnt
• i * prime[j] <= n
• (j <= cnt) && (i * prime[j] <= n)
• (i <= cnt) && (prime[i] * prime[j] <= n)

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

• not_prime[i] = true
• return
• continue
• break

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

• $n \% 4 == 0$
• (n \% 400 == 0 || (n \% 4 == 0 && n \% 100 != 0))
• (n \% 4 == 0 && n \% 100 != 0)
• (n \% 100 == 0 || (n \% 4 == 0 && n \% 100 != 0))

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

• 1
• 7
• 8
• 2