CSP-J 初赛模拟

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

1. 下列关于计算机历史的叙述中，正确的是（ ） {{ select(1) }}

• 按照冯·诺依曼计算机体系结构，计算机硬件系统由四部分组成：运算器、存储器、输入设备和输出设备。
• 第一代计算机采用的元器件是晶体管。
• 图灵奖是计算机科学领域的最高奖项。
• 图灵被称为“现代计算机之父”。

2. 数 $(52)_8$ 和 $(A3)_{16}$ 的和为： {{ select(2) }}

• $(11001101)_2$
• $(321)_8$
• $(209)_{10}$
• $(CE)_{16}$

3. 设 a = true, b = false, c = true，以下逻辑表达式的值为真的是（ ） {{ select(3) }}

• (a∨b) ∧ c ∧ b
• a ∧ (b∨c) ∧ b
• (a∨b) ∧ (c∨b)
• (a∧b) ∨ (c∧b)

4. 下列程序段的输出结果是（ ）

int x = 5, y = 3, result = 1;
    while (x > 0) {
        if (x % 2 == 1)
            result *= y;
        y *= y;
        x /= 2;
    }
    cout << result;

{{ select(4) }}

• $25$
• $243$
• $125$
• $225$

5. 给定整数序列：$[1, 3, 5, 2, 4, 6, 8, 3]$，以下关于该序列的说法正确的是（ ） {{ select(5) }}

• 最长上升子序列长度为 $6$，最长上升子串长度为 $4$
• 最长上升子序列长度为 $6$，最长上升子串长度为 $5$
• 最长上升子序列长度为 $5$，最长上升子串长度为 $5$
• 最长上升子序列长度为 $5$，最长上升子串长度为 $4$

6. 以下函数用于在双向链表中某个节点 pos 之后插入新节点 node，请从选项中选出能正确完成插入操作的一组语句。

struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

void insertAfter(ListNode* pos, ListNode* node) {
    if (pos == nullptr || node == nullptr) return;

    // 【填空】缺失代码：插入 node 到 pos 之后
    ________________________;
}

{{ select(6) }}

• node->next = pos->next;
   pos->next = node;
   node->prev = pos;
   if (pos->next != nullptr)
   pos->next->prev = node;
  

• pos->next = node;
    node->prev = pos;
    if (node->next != nullptr)
    node->next->prev = node;
    node->next = pos->next;
  

• node->prev = pos;
    pos->next = node;
    node->next = pos->next;
    node->next->prev = node;
  

• node->next = pos->next;
    node->prev = pos;
    if (pos->next != nullptr)
    pos->next->prev = node;
    pos->next = node;
  

7. 一个栈的入栈序列为 a, b, c, d，以下哪一个不可能是出栈序列？ {{ select(7) }}

• a, b, c, d
• d, c, b, a
• c, d, b, a
• c, a, d, b

8. 已知后缀表达式为：3 4 + 5 2 - *，其对应的中缀表达式是： {{ select(8) }}

• 3 + 4 * 5 - 2
• (3 + 4) * (5 - 2)
• 3 + (4 * 5) - 2
• 3 + 4 * (5 - 2)

9. 循环队列使用数组 data[0...n-1] 存储元素，使用 front 指向队首元素，rear 指向下一个入队位置。则判断队列为空的条件是： {{ select(9) }}

• (rear + 1) % n == front
• rear == front
• rear + 1 == front
• rear == front + 1

10. 已知某通信中使用的字符及频率如下：

字符	频率
A	10
B	15
C	20
D	25
E	15

使用哈夫曼算法构造最优编码，则以下说法正确的是： {{ select(10) }}

• 字符 A 的编码长度一定小于字符 E 的编码长度
• 字符 C 的编码长度一定大于字符 B 的编码长度
• 字符 D 的哈夫曼编码长度一定是最短的
• 字符 B 的编码长度一定最长的

11. 给定一棵二叉树的前序遍历序列 [1, 2, 4, 8, 9, 5, 3, 6, 7] 和中序遍历序列 [8, 4, 9, 2, 5, 1, 6, 3, 7]，请问这棵树是否为完全二叉树？ {{ select(11) }}

• 是
• 不是
• 无法判断
• 需要后序遍历才能确定

12. 已知某二叉树的前序遍历序列为：A B D E C F G，中序遍历序列为：D B E A F C G，则该二叉树的后序遍历序列是： {{ select(12) }}

• D E B F G C A
• D E B F G A C
• E D B F G C A
• D E B G F C A

13. 根的高度为 $0$，那么一棵高度为 $4$ 的满三叉树的节点总数是： {{ select(13) }}

• 121
• 243
• 125
• 40

14. 有 $6$ 个人排队（甲、乙、丙、丁、戊、己），其中：甲不能排在第一位，乙不能排在第六位。满足上述条件的排法总数是：

{{ select(14) }}

• 504
• 520
• 582
• 600

15. 从 $5$ 本不同的数学书和 $4$ 本不同的英语书中选出 $3$ 本，要求至少包含 $1$ 本数学书和 $1$ 本英语书，问有多少种选法？ {{ select(15) }}

• 100
• 80
• 90
• 70

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

（一）阅读下列程序，回答问题。

#include <iostream>
#include <string>
using namespace std;
string s;
int a[303];
int main()
{
	cin >> s;
	for (int i = 0; i < s.length(); i++)
		a[s[i]] = 1;
	int cnt = 0;
	for (int i = 'A'; i <= 'z'; i++)
	{
		if (a[i])
		{
			if (a[i + 1])
				cnt++;
		}
	}
	cout << cnt;
	return 0;
}

注意：数据保证，输入的字符串仅包含大小写字母，且长度小于 $300$。

判断题

16. 如果输入的字符串长度为 $1$，输出结果一定为 $0$。 {{ select(16) }}

• 正确
• 错误

17. 如果输入的字符串长度为 $n$，输出的结果可能等于 $n$。 {{ select(17) }}

• 正确
• 错误

选择题

18. 若给出的输入为不合法字符串 1c2b3azA，输出结果为（） {{ select(18) }}

• 1
• 2
• 3
• 4

19. （4分）对于输出的结果 $3$，若输入的字符串长度为 $4$ ，则合法的输入有多少种可能 () {{ select(19) }}

• 552
• 624
• 1056
• 1104

（二）阅读下列程序，回答问题。

#include <iostream>
#include <cstring>
using namespace std;
int n, m, a[1003];
bool f[1003][100005];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	memset(f, 0, sizeof(f)); // 代码一
	f[0][0] = true;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= 100000; j++)
		{
			f[i][j] |= f[i - 1][j];
			if (j >= a[i]) f[i][j] |= f[i - 1][j - a[i]];
		}
	int ans = 0;
	for (int i = 1; i <= m; i++)
		ans += f[n][i];
	cout << ans;
	return 0;
}

保证 $1\le n \le 1000$，$1 \le m \le 10^5$，$1 \le a[i] \le 10^5$

判断题

20. 删掉代码一后，程序的输出结果一定不变。{{ select(20) }}

• 正确
• 错误

21. 当 $n$ 等于 $1$ 时，程序的输出结果一定为 $0$。{{ select(21) }}

• 正确
• 错误

22. 一定不存在一种合法的输入，使得最终输出结果为 $100000$。{{ select(22) }}

• 正确
• 错误

23. 一定存在一种合法的输入，使得最终输出结果为 $0$。 {{ select(23) }}

• 正确
• 错误

选择题

24. 对于以下输入，输出结果为（）

5 15
2 2 3 4 5

{{ select(24) }}

• 13
• 14
• 15
• 16

25. （4分）关于该程序说法正确的是 () {{ select(25) }}

• 该程序的时间复杂度为 $O(n^2)$
• 该程序是用于统计，给出的 $n$ 个数，能够组合出多少个正整数。
• 当 $m > 10^5$ 时，程序一定会输出错误答案。
• 该程序是用于统计，给出的 $n$ 个数，能够组合出多少个小于等于 $m$ 的正整数。

（三）阅读下列程序，回答问题。

#include <iostream>
using namespace std;
int n, k, a[1000005];
int q[1000005], h, t, ans[1000005];
int main()
{
	cin >> n >> k;
	h = 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		while (h <= t && a[q[t]] <= a[i]) --t;
		q[++t] = i;
		while (h <= t && q[h] + k <= i) ++h;
		if (i >= k)
			ans[i - k + 1] = a[q[h]];
	}
	for (int i = 1; i <= n - k + 1; i++)
		cout << ans[i] << " ";
	return 0;
}

保证 $1\le k \le n \le 10^6$，$-1000 \le a[i] \le 1000$

判断题

26. 若 n < k，则程序无输出。（）{{ select(26) }}

• 正确
• 错误

27. 若输出的数据大于 $2$，则相邻两个数一定不相等。{{ select(27) }}

• 正确
• 错误

28. 此程序的时间复杂度为 $O(n^2)$ {{ select(28) }}

• 正确
• 错误

选择题

29. （4分）若 $n = 3, k = 2$ 的输出结果为 $1, 2$，则 $a[i]$ 序列有多少种可能？ {{ select(29) }}

• 1001
• 1002
• 2002
• 2003

30. （4分）关于该程序，说法错误的是（） {{ select(30) }}

• 该程序计算的是每相邻 $k$ 个元素中的最大值。
• 该程序中的 $q$ 数组模拟的是一个队列，该队列维护的是一个递增的序列。
• 当 $h > t$ 时，队列为空。
• 将代码中的 h = 1 改为 h = 0 不会影响程序的正确性。

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

（一）完善程序第一题

国际象棋中，车可以攻击所有同一行或者同一列的地方。

$n \times n$ 的棋盘上有 $k$ 个棋子，现在给出每个棋子的坐标，求至少被一个车攻击的格子数量。

#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int R[1000005], C[1000005];
long long cnt1, cnt2;
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
		cin >> R[i] >> C[i];
	________31________
	________32________
	for (int i = 1; i <= k; i++)
		________33________
	cnt2 = ________34________;
	cout << ________35________;
	return 0;
}

31. 31处应填入（） {{ select(31) }}

• sort(R + 1, R + 1 + k);
• sort(R, R + k);
• sort(R + 1, R + k);
• sort(R , R + 1 + k);

32. 32处应填入（） {{ select(32) }}

• sort(C + 1, C + 1 + k);
• sort(C, C + k);
• sort(C + 1, C + k);
• sort(C, C + 1 + k);

33. 33处应填入（） {{ select(33) }}

• if (R[i] != R[i - 1]) ++cnt2;
• if (C[i] != C[i + 1]) ++cnt1;
• if (R[i] != R[i - 1]) ++cnt1;
• if (R[i] != R[i + 1]) ++cnt2;

34. 34处应填入（） {{ select(34) }}

• unique(C + 1, C + k)
• unique(C, C + k) - C
• unique(C + 1, C + 1 + k) - C
• unique(C + 1, C + 1 + k) - C - 1

35. 35处应填入（）{{ select(35) }}

• n * cnt1 * cnt2 - cnt1 - cnt2
• n * (cnt1 + cnt2) - cnt1 * cnt2
• n * (cnt1 + cnt2)
• n * (cnt1 + cnt2) + cnt1 * cnt2

（二）完善程序第二题

给出 $n$ 个二元组 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$，并依次进行 $q$ 次操作，操作分为以下两种类型：

$\bull$ 1 l r：询问有多少个二元组 $(i,j)$ 满足：$l\le i,j\le r,x_i<x_j,y_i<y_j$；

$\bull$ 2 p x y：将 $x_p$ 的值改为 $x$，$y_p$ 的值改为 $y$。

输入数据保证 $1\le n,q\le 8000$，$1\le x_i,y_i\le 200$，$2$ 操作中 $1\le x,y\le 200$。

#include <bits/stdc++.h>
using namespace std;
int n, q;
int cnt[203][203];
struct node
{
	int x, y;
} Node[8003];

void calc(int l, int r)
{
	for (int i = l; i <= r; i++)
		____36____;
	long long ans = 0;
	for (int i = 1; i <= 200; i++)
		for (int j = 1; j <= 200; j++)
		{
			ans += ____37____;
			cnt[i][j] += ____38____;;
		}
	cout << ans << endl;
	memset(cnt, 0, sizeof(cnt));
}

int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> Node[i].x >> Node[i].y;
	int opt, l, r, p, x, y;
	for (int i = 1; i <= q; i++)
	{
		cin >> opt;
		if (opt == 1)
		{
			cin >> l >> r;
			____39____;
		}
		else
		{
			cin >> p >> x >> y;
			____40____;
		}
	}
	return 0;
}

36. 36处应填入（） {{ select(36) }}

• cnt[Node[i].x][Node[i].y] = 1
• cnt[Node[i].x][Node[i].y] = 0
• cnt[Node[i].x][Node[i].y]++
• cnt[Node[i].x][Node[i].y] += cnt[Node[i-1].x][Node[i-1].y]

37. 37处应填入（） {{ select(37) }}

• cnt[i][j] + cnt[i - 1][j - 1]
• cnt[i][j] * cnt[i - 1][j - 1]
• cnt[i][j] * cnt[i][j]
• cnt[i][j] + cnt[i][j]

38. 38处应填入（） {{ select(38) }}

• cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1]
• cnt[i - 1][j - 1] - cnt[i][j - 1] - cnt[i - 1][j];
• cnt[i - 1][j - 1] + cnt[i][j - 1] - cnt[i - 1][j]
• cnt[i - 1][j] + cnt[i - 1][j - 1] - cnt[i][j - 1]

39. 39处应填入（） {{ select(39) }}

• calc(l, r)
• calc(x, y)
• calc(l - 1, r - 1)
• calc(x - 1, y - 1)

40. 40处应填入（） {{ select(40) }}

• Node[p].x = x, Node[p].y = y;
• calc(x, y)
• calc(x - 1, y - 1)
• cnt[x][y]++