2019 CSP-J 真题题目、答案以及解析-Toy模板网

这篇具有很好参考价值的文章主要介绍了2019 CSP-J 真题题目、答案以及解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面的话

最近快要CSP了，为了帮助大家[zì jǐ]更好的复习历年真题特地作此题解一篇。
我写完之后看了一遍，感觉有点啰嗦，大家看不看随意。
还有，有没有大佬讲讲阅读程序最后一题的倒数第二问?
蒟蒻我看不懂😭😭😭😭😭😭😭😭😭😭

题目

洛谷版
CCF版

建议使用CCF版。因为洛谷版有打印错误。
两种版本题目都有题目、答案所以这里不过多讲解，下面是解析内容↓

解析

单项选择题

1.

这题没什么可讲的，死知识，自己背就完了

2.

与运算即数位对齐，若两个数相同数位都为True，运算结果即为True, 否则为False
我们来将两数执行上述操作：

1 1 1 0 1 1 1 0 0 1 0 1 1 1
0 1 0 1 1 0 1 1 1 0 1 0 1 1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 1 0 0 1 0 1 0 0 0 0 0 1 1

答案就出来了。

3.

32位即为32个二进制位，一个字节8个二进制位，32 / 8 = 4
于是乎答案出来了。

4.

b从1~C，共循环了C次，减去C个1即为-C
于是乎，答案出来了

5.

折半查找的复杂度为O(long n)，log 100 为6~7之间，最大值即为7

6.

链表数据结构的特点为：

执行插入、删除等操作消耗O(1)的时间复杂度；
访问元素需要消耗O(n)的复杂度；
不必事先预估所需空间；
不可随机访问元素。
所消耗的空间与普通数组成正比例

所以，答案大家可以看出来了吧

7.

这题没什么好说的，直接人肉暴力一下就好了。

注意！袋子和袋子没有区别，球和球也没有区别，所以：

8 0 0 0 0
和
0 8 0 0 0

没有区别

有如下结果：

8 0 0 0 0
7 1 0 0 0
6 2 0 0 0
6 1 1 0 0
5 3 0 0 0
5 2 1 0 0
5 1 1 1 0
4 4 0 0 0
4 3 1 0 0
4 2 2 0 0
4 2 1 1 0
4 1 1 1 1
3 3 2 0 0
3 3 1 1 0
3 2 2 1 0
3 2 1 1 1
2 2 2 2 0
2 2 2 1 1

一共18个答案。

8.

用一维数组储存二叉树的方法题目中也说了：

（根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+l处）

那么,问题来了：如果某非叶子节点没有左孩子，那么这一个下标放什么呢？

空着。

因为如果把其他节点放过来了，就无法满足上述条件了，那么就无法正确访问该二叉树了。

所以，我们要将其余位置补全，使其变成一棵完全二叉树

原图如下：

2019csp,C++,CSP-J,算法,数据结构

更改为完全二叉树后如下：

2019csp,C++,CSP-J,算法,数据结构
可知共需15个节点的空间
（图画的有点抽象，请谅解）

9.

这个你要是不会，请到小学回炉重造

10.

将两数分别分解质因数即可。

11.

类似于背包问题
数据范围较小，人肉DP即可

12.

重复最少 即抽取结果各个花色尽可能平均，若每种花色各抽4张，一共12张，还需再抽一张，故最少5张花色相同。

13.

可颠倒的五位数：

第一位有5种情况（0、1、6、8、9）
第二位有5种情况（0、1、6、8、9）
第三位有3种情况（6、9不行，因为颠倒后与原来不符，而中间位颠倒后依然在原来的地方）
第四、第五位只有1种情况（必须与第一、第二位对应）

根据乘法原理，共5x5x3 = 75种情况。

愿意的可以人肉暴力一下。

14.

这是一道二叉树的遍历题。后中推前。
可以通过后序遍历 + 中序遍历还原二叉树。
还原过程如下：

后序遍历：D G J H E B I F C A

中序遍历：D B G E H J A C I F

根据后序遍历确定根节点为A
根据中序遍历确定左子树为D B G E H J，右子树为C I F
根据后序遍历分别确定两个子树的根节点
根据中序遍历确定两个子树的左右子树
以此类推

最终，可以还原二叉树。
然后进行前序遍历即可。

$P . S .$ 如果连前中后序遍历都不知道的同学，请自行学习相关知识。

15.

死知识：“计算机领域的诺贝尔奖”为“图灵奖”

阅读程序题

一、

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
    scanf("%s", st);
    int n = strlen(st);
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            char c = st[i - 1];
            if (c >= 'a')
                st[i - 1] = c - 'a' + 'A';
        }
    }
    printf("%s", st);
    return 0;
}

1

错
输入字符串可以由任意字符组成，只不过本代码仅仅处理小写字母而已。

2

对
若进行上述更改，第九行则会发生÷0问题，RE

3

很明显错误。
举个反例：aaaaaaaa
原程序运行结果：AAaAaaaA
修改后运行结果：AAaaaaaa

大家可以自行复制代码尝试一下。

4

正确
简单看一看代码就会发现：特定字符的ASCLL码≥97时，才会进行修改，而大写字母Z的ASCLL码也才71。
所以不会进行任何更改

5

至多

符合情况的都要算。
有两层筛选条件：
第九行：n % i == 0
第十一行：c >= 'a'
只要输入的都是小写字母，就可以满足第十一行的条件。
而第九行的条件可理解为：“是n的因数”

若输入的字符串长度为18

即：n = 18
18的因数共有6个：1、2、3、6、9、18

可知答案。

6

本题是上一题的变体，相信看懂了上一题的同学一定可以明白：本题问的是“？有36个因数”
这里教大家一个快速求因数个数的方法：
先将其分解质因数
然后将所有质因数的指数+1，在相乘。

我们来逐一分解：

36 = 2² * 3²
(2+1)(2+1) = 9

100000 = 2⁵ * 5⁵
(5+1)(5+1) = 36

答案就出来了。
有兴趣的同学可以证明一下我提供的方法。

二、

#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        a[i] = b[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (a[x] < y && b[y] < x) {
            if (a[x] > 0)
                b[a[x]] = 0;
            if (b[y] > 0)
                a[b[y]] = 0;
            a[x] = y;
            b[y] = x;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0)
            ++ans;
        if (b[i] == 0)
            ++ans;
    }
    printf("%d", ans);
    return 0;
}

1

错误
可以尝试证明一下：
第一次运行一定会进入第13行的if语句，则一定会有两个数被身为非零的数。

之后如果没有进入if语句，则这两个数一直非零，直到运行结束，ans = n - 2
如果进入了，则会将两个数设为0，两个数设为非0，此时最好情况下0的个数也不会改变

综上所述：ans最大为n-2

2

错误
举个反例：

3 1
1 2

在执行完第十行的循环之后，数组如下：

下标：	1	2	3
数组a:	2	0	0
数组b:	0	1	0

在第一次执行完27行的ans++时，ans == 1

3

错
举个反例：

1 1
1 1

很明显了吧？

4

依然错
举个反例：
2 1
1 2
大家自己算一算

5

自己造一组数据即可：
例如：

3 3
1 1
2 2
3 3

ans：0

有兴趣的同学可以自行证明，愿意的话发给我看看

6

同样，自己造数据

3 3
1 1
2 1
3 1

ans：4

三、

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    cout << f(0, n - 1, 1) << endl;
    return 0;
}

1

错误
相等的数字对该程序没有任何影响

这题选错的讲讲你的思路呗😁😁😁

2

正确
返回值有两种情况：

return 0
return lres + rres + depth * b[mink];

第一种情况不受b数组的影响，不用考虑
第二种情况受四个因素的影响：左孩子、右孩子、数组b、depth
由于数组b全部为零，第二种情况只受左右孩子的影响。

左右孩子又有两种情况了：叶子节点、非叶子节点
前一个继续往下递归，后一个return 0

所以，发现了吗？返回值要么是0，要么是0+0+0

所以， ans = ……

3

这题的代码是一道递归题，它的最好/最坏情况类似于快速排序
所以，最坏情况为每次将最左边/右边的一个端点去掉，一共需要去掉n次而每一层递归都会比较n次
总复杂度约为O(n²)，n = 100时，约为10000次，最接近的即为A

4

最好情况下，每次都能二分整个区间，复杂度为O(n log n)，n = 100时，在600到700之间，故选D

5

要想输出最大，递归的深度也要最大，每次都去掉左端点（权值最小）
这样，ans将会达到1² + 2² + 3² + … + n²，n = 10时，答案为385。

6

$T i p s ：$ 使用“洛谷有题”的同学注意了，题目打错了，原题应当为：

当 n=100 时，若 b 数组满足，对于任意 0 ≤ i < n，都有 b[i] = 1，那么输出最小为( )

要想结果最小，就要让二叉树尽可能平衡，最平衡的二叉树即为完全二叉树
用100个节点搭建一棵完全二叉树，每层的节点数依次为：1，2，4，8，16，32，37
将每层的节点数与其对应的权值相乘，求出总和即可。

（有没有人像我一样把最后一层的节点数算成64，然后抓耳挠腮想不明白？有的话在评论区里打一个心有灵犀😁😁😁）

完善程序题

一、

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}

int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

1

t表示这一个格子应当写什么
就算你想不明白这一点，换个角度想：要是这里不用t，t有什么用？

2

根据一开始的例子，可知：每一次变换之后，右下格变为与自己不同的一项，右、下、自己变为自己原本的数字。

而这一行t没有变，所以是右、下、自己中的一个。
而右、下已经写过了，所以x、y不用变

3

用CCF提供的题库的同学注意了！
该题的解析似乎有错：
2019csp,C++,CSP-J,算法,数据结构
当然，也有可能是我错了，欢迎指出

下面是我的思路：
这里t做了变化，所以是右下角，即两个都+step

4

初始位置应该为0（见题目），深度应该为n（初始状态为递归0次）

5

矩阵最终大小应当为2ⁿ，即 1 << n

二、

本题与计数排序有着密切的关系，不会的同学可以先学习一下相关知识

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i) 
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);

    return 0;
}

1

有了注释应该很容易理解，这里在对第二个参数进行计数排序（一下称之为初排）

2

ord[i]表示：在输入时下标为i的数字在对第二个关键字排序之后的下标
知道了这个应该很好选

3

对第一个关键字进行计数排序（以下称之为复排）

4 //部分思路（我到现在也没搞懂）懂了的跟我说一声啊！！！

答案为 res[--cnt[a[ord[i]]]] = ord[i]
我们来理一理思路（一层层数组看的我头晕）

首先，i表示输入时的第i个数
ord[i] 表示第i个数现在（初排后）的位置
a[ord[i]] 表示 i初排后的位置上初排前的元素的第一个关键字
--cnt[a[ord[i]]] 表示 i初排后的位置上初排前的元素的第一个关键字复排后应该在的位置
res[--cnt[a[ord[i]]]] 表示复排后 i初排后的位置上初排前的元素的第一个关键字复排后应该在的位置的下标
res[--cnt[a[ord[i]]]] = ord[i] 表示……
将复排后 i初排后的位置上初排前的元素的第一个关键字复排后应该在的位置的下标设为初排后 i 的位置

然后……
我就懵了

恳请大佬帮忙！！！

5

res存储的就是最终结果了

尾声

这篇文章对你的帮助大吗？
谢谢阅读。
有什么改进建议欢迎评论区讲。文章来源地址https://www.toymoban.com/news/detail-677412.html

到了这里，关于2019 CSP-J 真题题目、答案以及解析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

2019 CSP-J 真题 题目、答案以及解析

写在前面的话

题目

解析

单项选择题

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

阅读程序题

一、

1

2

3

4

5

6

二、

1

2

3

4

5

6

三、

1

2

3

4

5

6

完善程序题

一、

1

2

3

4

5

二、

1

2

3

4 //部分思路（我到现在也没搞懂）懂了的跟我说一声啊！！！

5

尾声

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

2019 CSP-J 真题题目、答案以及解析