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

1

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

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

（满分 100 分，考试时间 100 分钟，语言 C++）

一、单项选择题（共 15 题，每题 2 分，共 30 分）

每题有且仅有一个正确选项。

1. 在 8 位二进制补码表示中，二进制串 11000111 表示的十进制整数是（　）

{{ select(1) }}

  • -71
  • -57
  • 199
  • -199

2. 下列关于字符编码的说法，错误的是（　）

{{ select(2) }}

  • ASCII 码用一个字节表示一个字符
  • UTF-8 是一种变长编码
  • UTF-8 编码中，任意一个汉字都固定占用 2 个字节
  • Unicode 为每个字符分配唯一的码点

3. 一张分辨率为 2048×1024、颜色深度为 24 位（真彩色）的位图，不压缩存储大约需要（　）MB。

{{ select(3) }}

  • 6
  • 2
  • 24
  • 0.75

4. 下列程序段的时间复杂度为（　）

int sum = 0;
for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

{{ select(4) }}

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

5. 元素 1、2、3、4、5 依次入栈（入栈过程中允许出栈），下列出栈序列中不可能出现的是（　）

{{ select(5) }}

  • 1, 2, 3, 4, 5
  • 5, 4, 3, 2, 1
  • 3, 2, 5, 4, 1
  • 4, 3, 1, 2, 5

6. 设循环队列用数组 q[0..9] 存储，front = 8 指向队首元素，rear = 3 指向队尾元素的下一个位置，则队列中元素的个数是（　）

{{ select(6) }}

  • 3
  • 4
  • 5
  • 6

7. 在单链表中，要在指针 p 所指向的结点之后插入一个新结点（用指针 s 指向），正确的操作序列是（　）

{{ select(7) }}

  • s->next = p->next; p->next = s;
  • p->next = s; s->next = p->next;
  • s->next = p; p->next = s;
  • p->next = s; s->next = p;

8. 一棵完全二叉树共有 2024 个结点，则它的叶子结点数是（　）

{{ select(8) }}

  • 1011
  • 1012
  • 1013
  • 2023

9. 一个无向图有 10 个顶点、15 条边，用邻接矩阵存储时，矩阵中“1”的个数为（　）

{{ select(9) }}

  • 15
  • 20
  • 30
  • 25

10. 下列排序算法中，平均时间复杂度和最坏时间复杂度均为 O(n log n)、且是稳定排序的是（　）

{{ select(10) }}

  • 快速排序
  • 堆排序
  • 归并排序
  • 希尔排序

11. 在长度为 1000 的升序数组中二分查找一个确定存在的元素，最坏情况下最多需要比较约（　）次。

{{ select(11) }}

  • 500
  • 100
  • 10
  • 3

12. 定义 f(0) = f(1) = 1，f(n) = f(n-1) + f(n-2)。用递归程序计算 f(6) 时，f(2) 一共被调用了（　）次。

{{ select(12) }}

  • 3
  • 5
  • 8
  • 13

13. gcd(2024, 748) = （　）

{{ select(13) }}

  • 4
  • 22
  • 44
  • 88

14. 5 个互不相同的元素依次入栈（入栈过程中允许出栈），所有可能的出栈序列共有（　）种。

{{ select(14) }}

  • 24
  • 32
  • 42
  • 120

15. 将 C++ 源代码转换成可执行文件，正确的步骤顺序是（　）

{{ select(15) }}

  • 预处理 → 编译 → 汇编 → 链接
  • 编译 → 预处理 → 链接 → 汇编
  • 预处理 → 汇编 → 编译 → 链接
  • 编译 → 汇编 → 预处理 → 链接

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

说明：阅读程序部分，判断题每题 2 分（9 道，共 18 分）；选择题每题 2 分，其中标注「3 分」的选择题每题 3 分（共 4 题）；本部分合计 40 分。判断题正确的写「对」，错误的写「错」。

阅读程序一（位运算与子集枚举）

阅读以下程序，输入均为合法的整数 n。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int total = 1 << n;
    int cnt = 0;
    for (int mask = 0; mask < total; mask++) {
        int bits = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) bits++;
        cnt += bits;
    }
    cout << cnt << endl;
    return 0;
}

判断题：

16. 该程序的功能是：枚举集合 {0, 1, …, n-1} 的所有子集，并求出所有子集的元素个数（即二进制表示中 1 的个数）之和。

{{ select(16) }}

  • 正确
  • 错误

17. 当输入 n = 0 时，外层 for 循环一次也不会执行。

{{ select(17) }}

  • 正确
  • 错误

18. 该程序的时间复杂度为 O(n·2ⁿ)。

{{ select(18) }}

  • 正确
  • 错误

选择题：

19. 输入 n = 3 时，程序输出为（　）

{{ select(19) }}

  • 6
  • 8
  • 12
  • 16

20. 输入 n = 10 时，程序输出为（　）

{{ select(20) }}

  • 512
  • 1024
  • 5120
  • 10240

21. （3 分）若将外层循环 for (int mask = 0; mask < total; mask++) 改为 for (int mask = 0; mask < total - 1; mask++)，输入 n = 3 时输出变为（　）

{{ select(21) }}

  • 9
  • 10
  • 11
  • 12

阅读程序二（归并排序求逆序对）

阅读以下程序。

#include <iostream>
using namespace std;
const int N = 100005;
int a[N], tmp[N];
long long ans = 0;
void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else { tmp[k++] = a[j++]; ans += mid - i + 1; }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ans = 0;
    merge_sort(1, n);
    cout << ans << endl;
    return 0;
}

判断题：

22. 该程序用于统计数组 a 中逆序对的个数。

{{ select(22) }}

  • 正确
  • 错误

23. 若输入的数组已经按升序排列，程序输出 0。

{{ select(23) }}

  • 正确
  • 错误

24. 该程序的时间复杂度为 O(n²)。

{{ select(24) }}

  • 正确
  • 错误

选择题：

25. 输入 n = 5，数组为 2 3 8 6 1 时，程序输出为（　）

{{ select(25) }}

  • 4
  • 5
  • 6
  • 7

26. 程序运行结束后，数组 a 中的元素顺序为（　）

{{ select(26) }}

  • 降序
  • 升序
  • 原样不变
  • 随机排列

27. （3 分）该程序的空间复杂度为（　）

{{ select(27) }}

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

阅读程序三（Dijkstra 单源最短路）

阅读以下程序。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool vis[N];
int main() {
    int n, m, s;
    cin >> n >> m >> s;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == -1 || dist[i] < dist[u])) u = i;
        if (u == -1) break;
        vis[u] = true;
        for (int v = 1; v <= n; v++)
            if (!vis[v] && g[u][v] != INF)
                dist[v] = min(dist[v], dist[u] + g[u][v]);
    }
    for (int i = 1; i <= n; i++)
        if (dist[i] == INF) cout << -1 << " ";
        else cout << dist[i] << " ";
    cout << endl;
    return 0;
}

判断题：

28. 该程序实现的是单源最短路径（Dijkstra）算法。

{{ select(28) }}

  • 正确
  • 错误

29. 当图中存在负权边时，该程序也一定能得到正确结果。

{{ select(29) }}

  • 正确
  • 错误

30. 该程序的时间复杂度为 O(n²)。

{{ select(30) }}

  • 正确
  • 错误

选择题：

31. 输入为 n=4, m=4, s=1，边为 (1,2,5)、(2,3,2)、(1,3,10)、(3,4,1)，程序输出为（　）

{{ select(31) }}

  • 0 5 7 8
  • 0 5 10 11
  • 0 5 7 9
  • 0 5 2 1

32. （3 分）该算法属于（　）

{{ select(32) }}

  • 贪心算法
  • 动态规划
  • 分治算法
  • 回溯算法

33. （3 分）该程序的空间复杂度为（　）

{{ select(33) }}

  • O(n)
  • O(n²)
  • O(n+m)
  • O(1)

三、完善程序（共 2 题，共 30 分）

每题有一段代码和 5 处空缺（①~⑤），每处空缺 3 分。每处空缺有且仅有一个正确选项。

完善程序一（用数组模拟循环队列）

以下程序用一个数组 q 实现循环队列。head 指向队首元素，tail 指向队尾元素的下一个位置；约定当 (tail+1) % MAXN == head 时队列判满，故最多同时存放 MAXN-1 个元素。程序实现入队（操作类型 1）与出队（操作类型 2），入队满时输出 FULL，出队空时输出 EMPTY，否则出队输出队首元素。

#include <iostream>
using namespace std;
const int MAXN = 10; // 数组容量；此实现最多同时存放 MAXN - 1 个元素
int q[MAXN];
int head = 0, tail = 0;

bool empty() { return ①; }
bool full()  { return ②; }

bool push(int x) {
    if (full()) return false;
    ③;
    tail = ④;
    return true;
}

int pop() {
    int x = q[head];
    head = ⑤;
    return x;
}

34. ① 处应填（　）

{{ select(34) }}

  • head == tail
  • head > tail
  • tail == MAXN
  • head == 0

35. ② 处应填（　）

{{ select(35) }}

  • tail == MAXN
  • (tail + 1) % MAXN == head
  • tail + 1 == head
  • head == tail

36. ③ 处应填（　）

{{ select(36) }}

  • q[tail] = x;
  • q[head] = x;
  • tail = x;
  • x = q[tail];

37. ④ 处应填（　）

{{ select(37) }}

  • tail + 1
  • (tail + 1) % MAXN
  • tail % MAXN
  • tail - 1

38. ⑤ 处应填（　）

{{ select(38) }}

  • head + 1
  • (head + 1) % MAXN
  • head % MAXN
  • (head - 1) % MAXN

完善程序二（最长上升子序列，O(n log n)）

以下程序求一个整数序列的最长上升子序列（严格上升）的长度。算法使用数组 d：d[k] 表示当前长度为 k 的上升子序列的最小可能末尾元素；对每个 a[i]，用二分在 d[1..len] 中找到第一个不小于 a[i] 的位置 pos 并更新，从而保证 O(n log n)。

#include <iostream>
using namespace std;
const int N = 100005;
int a[N], d[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int len = 0;
    for (int i = 1; i <= n; i++) {
        int l = 1, r = len, pos = ①;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (②) { pos = mid; ③; }
            else ④;
        }
        ⑤;
        if (pos == len + 1) len++;
    }
    cout << len << endl;
    return 0;
}

39. ① 处应填（　）

{{ select(39) }}

  • len
  • len + 1
  • 0
  • 1

40. ② 处应填（　）

{{ select(40) }}

  • d[mid] > a[i]
  • d[mid] >= a[i]
  • d[mid] < a[i]
  • d[mid] == a[i]

41. ③ 处应填（　）

{{ select(41) }}

  • r = mid - 1;
  • l = mid + 1;
  • r = mid;
  • r = mid + 1;

42. ④ 处应填（　）

{{ select(42) }}

  • r = mid - 1;
  • l = mid + 1;
  • l = mid;
  • l = mid - 1;

43. ⑤ 处应填（　）

{{ select(43) }}

  • d[pos] = a[i];
  • a[pos] = d[i];
  • d[i] = a[pos];
  • len = pos;

（试卷结束）

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