CSP-J模拟卷15

ID: 2514

客观题

尝试: 11

已通过: 1

难度: 10

上传者:

yhxx

标签>

CSP-J

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

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

鼠标与光驱都属于计算机的外设，计算机硬件系统由四部分组成：运算器、存储器、输入设备和输出设备。
第一代计算机采用的主要逻辑元件是晶体管。
图灵奖是计算机科学领域的最高奖项。
图灵被称为“现代计算机之父”。

数（52）₁₀和（A3）₁₆的和为（）{{ select(2) }}

（11010111）₂
（329）₈
（213）₁₀
（D5）₁₆

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

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

下列程序的输出结果是（）{{ select(4) }}

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

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

最长上升子序列长度为6，最长连续上升子序列长度为4
最长上升子序列长度为6，最长连续上升子序列长度为5
最长上升子序列长度为5，最长连续上升子序列长度为5
最长上升子序列长度为5，最长连续上升子序列长度为4

以下函数用于在双向链表中某个节点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 之后
}

选项1：

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

选项2：

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

选项3：

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

选项4：

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

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

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

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

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

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

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

已知某赫夫曼树的字符及频率如下：

字符频率

A 10

B 15

C 20

D 25

E 15

使用该赫夫曼树对消息编码，则以下说法正确的是（）{{ select(10) }}

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

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

已知一棵二叉树的前序遍历序列为1, 2, 4, 8, 9, 5, 3, 6, 7，中序遍历序列为8, 4, 9, 2, 5, 1, 6, 3, 7，请问这棵树是否为完全二叉树？（）{{ select(11) }}

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

已知某二叉树的前序遍历序列为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

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

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

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题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) }}

正确
错误

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

正确
错误

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

（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 \leq n \leq 1000$ ， $1 \leq m \leq 10^5$ ， $1 \leq a[i] \leq 10^5$

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

正确
错误

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

正确
错误

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

正确
错误

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

正确
错误

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

5 15
2 2 3 4 5

（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 \leq k \leq n \leq 10^6$ ， $-1000 \leq a[i] \leq 1000$

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

正确
错误

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

正确
错误

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

正确
错误

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

1001
1002
2002
2003

（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处应填入（）{{ select(31) }}

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

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

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

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处应填入（）{{ 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处应填入（）{{ 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$ 次操作，操作分为以下两种类型：

1 l r：询问有多少个二元组 $(i,j)$ 满足： $l \leq i,j \leq r, x_i < x_j, y_i < y_j$ ；
2 p x y：将 $x_p$ 的值改为 $x$ ， $y_p$ 的值改为 $y$ 。

输入数据保证 $1 \leq n,q \leq 8000$ ， $1 \leq x_i,y_i \leq 200$ ，操作2中 $1 \leq x,y \leq 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处应填入（）{{ 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处应填入（）{{ 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处应填入（）{{ 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处应填入（）{{ select(39) }}

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

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

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

在下列比赛中:

cspj初赛模拟赛5

#YHCSPJ0015. CSP-J模拟卷15

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

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

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

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

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

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

（一）完善程序第一题

（二）完善程序第二题

相关

状态

开发

支持

关于

#YHCSPJ0015. CSP-J模拟卷15

CSP-J模拟卷15

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

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

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

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

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

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

（一）完善程序第一题

（二）完善程序第二题

相关

状态

开发

支持

关于

还没有账户？

登录