#KGT0010. CSP-S 第一轮初赛模拟试卷 · 第 3 套

0

CSP-S 第一轮初赛模拟试卷 · 第 3 套

CSP-S 第一轮（初赛）模拟试卷（第 3 套）

满分 100 分　时间 100 分钟　语言 C++

注意事项：

  • 本卷共三大题，43 小题。
  • 单项选择题共 15 题，每题 2 分，共 30 分。
  • 阅读程序共 3 题，40 分（判断题每题 2 分；选择题每题 2 分，其中第 21、27、32、33 题每题 3 分）。
  • 完善程序共 2 题，30 分（每题 5 空，每空 3 分）。

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

1. 设 a 为 32 位有符号整数，若表达式 a & (a - 1) 的值为 0，则（　）

{{ select(1) }}

  • a 一定是 2 的正整数次幂
  • a 是 0 或 2 的幂
  • a 一定是奇数
  • a 一定是 0

2. 某字符采用 UTF-8 编码，其字节序列为 E4 B8 AD（十六进制，共 3 个字节）。则该字符的 Unicode 码点值（十进制）是（　）

{{ select(2) }}

  • 19968
  • 20013
  • 21475
  • 25014

3. 某存储设备标称容量为 8 GB（此处 1 GB = 10⁹ 字节），则其实际容量最接近（　）

{{ select(3) }}

  • 8.59 GiB
  • 7.45 GiB
  • 8.00 GiB
  • 8.39 GiB

4. 下列排序算法中，最坏情况下时间复杂度为 O(n log n) 的是（　）

{{ select(4) }}

  • 快速排序
  • 插入排序
  • 堆排序
  • 冒泡排序

5. 已知递推式 T(n) = T(n−1) + n，T(1) = 1，则 T(n) 的渐近时间复杂度为（　）

{{ select(5) }}

  • O(n)
  • O(n log n)
  • O(n²)
  • O(log n)

6. 用数组实现循环队列，容量为 m，front 指向队首元素，rear 指向队尾元素的下一个位置。则当前队列中元素的个数为（　）

{{ select(6) }}

  • rear - front
  • (rear - front + m) % m
  • (front - rear + m) % m
  • rear - front + 1

7. 具有 n 个结点的二叉树采用二叉链表（每个结点含 left、right 两个指针）存储，则所有结点中空指针域的总个数为（　）

{{ select(7) }}

  • n
  • n − 1
  • n + 1
  • 2n

8. 由 4 个互不相同的结点可以构成（　）棵形态不同的二叉树

{{ select(8) }}

  • 10
  • 12
  • 14
  • 16

9. 对序列 5, 3, 8, 1, 9, 2 进行冒泡排序（升序，从前往后相邻比较交换），第一趟排序结束后的序列为（　）

{{ select(9) }}

  • 3, 5, 1, 8, 2, 9
  • 3, 5, 8, 1, 2, 9
  • 3, 1, 5, 8, 2, 9
  • 1, 3, 5, 2, 8, 9

10. 定义 f(0) = 0，f(1) = 1，f(n) = f(n−1) + f(n−2)（n ≥ 2），则 f(10) =（　）

{{ select(10) }}

  • 34
  • 55
  • 89
  • 144

11. gcd(2024, 748) =（　）

{{ select(11) }}

  • 22
  • 44
  • 88
  • 11

12. 将 10 个完全相同的小球放入 3 个不同的盒子中，允许盒子为空，共有（　）种不同的放法

{{ select(12) }}

  • 66
  • 120
  • 220
  • 45

13. 在计算复杂性理论中，若一个问题可以在多项式时间内验证某个候选解的正确性，则这个问题属于（　）

{{ select(13) }}

  • P 类
  • NP 类
  • NPC 类
  • 不可判定问题

14. IEEE 754 单精度浮点数共占 32 位，其中指数（阶码）部分占（　）位

{{ select(14) }}

  • 7
  • 8
  • 11
  • 23

15. 字符 a、b、c、d、e 的出现频率分别为 5、9、12、13、16。用哈夫曼（Huffman）编码对它们编码，则字符 a 的编码长度为（　）

{{ select(15) }}

  • 2
  • 3
  • 4
  • 5

二、阅读程序（共 3 题，40 分）

说明： 每题给出一段完整可编译的 C++ 程序。判断题（每题 2 分）：正确的选 T，错误的选 F；选择题（每题 2 分，其中标注「3 分」的每题 3 分）：每题有且仅有一个正确选项。

第 1 题（判断题 16–18，选择题 19–21）

#include <iostream>
using namespace std;

int popcount(int x) {
    int c = 0;
    while (x) { c++; x &= x - 1; }
    return c;
}

int gray(int x) { return x ^ (x >> 1); }

int revbits(int x) {
    int r = 0;
    while (x) { r = (r << 1) | (x & 1); x >>= 1; }
    return r;
}

int main() {
    int n;
    cin >> n;
    cout << popcount(n) << " " << gray(n) << " " << revbits(n) << endl;
    return 0;
}

判断题：

16. popcount(n) 返回的是 n 的二进制表示的位数（不含前导零）。（　）

{{ select(16) }}

  • 正确
  • 错误

17. 对于任意正整数 n，gray(n) 与 n 的二进制位数相同。（　）

{{ select(17) }}

  • 正确
  • 错误

18. 对于任意正整数 n，revbits(n) 都是奇数。（　）

{{ select(18) }}

  • 正确
  • 错误

选择题：

19. 若输入为 6，程序输出为（　）

{{ select(19) }}

  • 2 5 3
  • 2 3 5
  • 3 5 2
  • 2 5 6

20. 若输入为 10，程序输出为（　）

{{ select(20) }}

  • 2 5 5
  • 2 15 5
  • 2 5 10
  • 3 15 5

21. （3 分）若输入为 2024，程序输出的第一个数是（　）

{{ select(21) }}

  • 5
  • 6
  • 7
  • 8

第 2 题（判断题 22–24，选择题 25–27）

#include <iostream>
using namespace std;

long long f[50][50];

long long c(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (f[n][k]) return f[n][k];
    return f[n][k] = c(n - 1, k - 1) + c(n - 1, k);
}

int main() {
    int n;
    cin >> n;
    long long s = 0;
    for (int k = 0; k <= n; k++) s += c(n, k);
    cout << s << endl;
    return 0;
}

判断题：

22. 该程序输出的结果等于 2^n − 1。（　）

{{ select(22) }}

  • 正确
  • 错误

23. 函数 c(n, k) 返回的是组合数 C(n, k)。（　）

{{ select(23) }}

  • 正确
  • 错误

24. 若删去 if (f[n][k]) return f[n][k]; 这一行，程序输出的结果不变，但运行时间会显著增加。（　）

{{ select(24) }}

  • 正确
  • 错误

选择题：

25. 若输入为 10，程序输出为（　）

{{ select(25) }}

  • 512
  • 1024
  • 2048
  • 3628800

26. 若输入为 30，程序输出为（　）

{{ select(26) }}

  • 536870912
  • 1073741824
  • 2147483648
  • 43589145600

27. （3 分）在保留记忆化（memoization）的情况下，该程序的时间复杂度为（　）

{{ select(27) }}

  • O(n)
  • O(n log n)
  • O(n²)
  • O(2ⁿ)

第 3 题（判断题 28–30，选择题 31–33）

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

int n, m, a[105][105], vis[105][105];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int bfs(int x, int y) {
    queue<pair<int,int>> q;
    q.push({x, y});
    vis[x][y] = 1;
    int sz = 0;
    while (!q.empty()) {
        pair<int,int> p = q.front();
        q.pop();
        sz++;
        for (int d = 0; d < 4; d++) {
            int nx = p.first + dx[d], ny = p.second + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && a[nx][ny]) {
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    return sz;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    int cnt = 0, mx = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] && !vis[i][j]) {
                int s = bfs(i, j);
                cnt++;
                mx = max(mx, s);
            }
    cout << cnt << " " << mx << endl;
    return 0;
}

判断题：

28. 程序输出的第二个数等于网格中由相邻（上、下、左、右）的 1 构成的连通块个数。（　）

{{ select(28) }}

  • 正确
  • 错误

29. 若把 queue<pair<int,int>> 换成栈（stack，入队改为入栈、出队改为出栈），程序输出的两个数都不变。（　）

{{ select(29) }}

  • 正确
  • 错误

30. 该程序的时间复杂度为 O(n × m)。（　）

{{ select(30) }}

  • 正确
  • 错误

选择题：

31. 若输入为：

4 5
1 1 0 0 1
0 1 0 1 1
1 0 0 0 1
1 1 0 1 0

则程序输出为（　）

{{ select(31) }}

  • 3 3
  • 4 4
  • 4 5
  • 5 4

32. （3 分）若输入为：

1 1
0

则程序输出为（　）

{{ select(32) }}

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

33. （3 分）函数 bfs(x, y) 的返回值表示（　）

{{ select(33) }}

  • 从 (x, y) 出发 BFS 访问的层数
  • 包含 (x, y) 的连通块中值为 1 的格子数（面积）
  • 网格中 1 的总个数
  • 距离 (x, y) 最远的 1 的距离

三、完善程序（共 2 题，30 分；每题 5 空，每空 3 分）

第 1 题（欧拉筛求质数个数，第 34–38 题）

题目： 以下程序使用欧拉筛（线性筛）在 O(n) 时间内筛出不超过 n 的所有质数，并输出质数的个数。该算法的关键在于保证每个合数只被它的最小质因数筛掉一次，从而把复杂度降到 O(n)。请补全下面的程序。

#include <iostream>
using namespace std;

const int N = 1000000;
int primes[N], cnt;
bool notPrime[N];   // notPrime[i] 为 true 表示 i 是合数

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) primes[①] = i;
        for (int j = 0; j < ② && i * primes[j] <= ③; j++) {
            notPrime[④] = true;
            if (i % primes[j] == 0) ⑤;
        }
    }
}

int main() {
    int n;
    cin >> n;
    sieve(n);
    cout << cnt << endl;
    return 0;
}

34. ① 处应填（　）

{{ select(34) }}

  • cnt
  • cnt++
  • ++cnt
  • cnt - 1

35. ② 处应填（　）

{{ select(35) }}

  • j < n
  • j < cnt
  • j <= cnt
  • j < i

36. ③ 处应填（　）

{{ select(36) }}

  • n
  • i
  • primes[j]
  • N

37. ④ 处应填（　）

{{ select(37) }}

  • i * primes[j]
  • i + primes[j]
  • i
  • primes[j]

38. ⑤ 处应填（　）

{{ select(38) }}

  • continue
  • break
  • return
  • j++

第 2 题（归并排序求逆序对，第 39–43 题）

题目： 以下程序使用归并排序（分治法）在 O(n log n) 时间内计算一个长度为 n 的序列的逆序对个数。逆序对是指满足 i < j 且 a[i] > a[j] 的二元组 (i, j)。请补全下面的程序。

#include <iostream>
using namespace std;

const int N = 100000;
int a[N], tmp[N];
long long ans;

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = ①;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[②];
        else { tmp[k++] = a[j++]; ans += ③; }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = ④;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(1, n);
    cout << ⑤ << endl;
    return 0;
}

39. ① 处应填（　）

{{ select(39) }}

  • 0
  • l
  • mid
  • r

40. ② 处应填（　）

{{ select(40) }}

  • i++
  • j++
  • i
  • j

41. ③ 处应填（　）

{{ select(41) }}

  • j - mid
  • mid - i + 1
  • r - j + 1
  • i - mid

42. ④ 处应填（　）

{{ select(42) }}

  • a[t]
  • tmp[t]
  • tmp[t - l]
  • tmp[k]

43. ⑤ 处应填（　）

{{ select(43) }}

  • ans
  • a[1]
  • a[n]
  • tmp[n]

—— 试卷结束 ——

  1. 测评记录
  2. 服务状态
  3. 兼容模式
  4. 主题
    1. 亮色
    2. 暗色
  5. 帮助
  6. 友链与鸣谢
  1. Powered by Hydro v5.0.6 Community
  3. 冀ICP备2021025055号-3 | 冀公网安备13098402000493号