最近快要CSP了,为了帮助大家[zì jǐ]更好的复习历年真题特地作此题解一篇。 我写完之后看了一遍,感觉有点啰嗦,大家看不看随意。 还有,有没有大佬讲讲阅读程序最后一题的倒数第二问? 蒟蒻我看不懂😭😭😭
题目洛谷版 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 07 1 0 0 06 2 0 0 06 1 1 0 05 3 0 0 05 2 1 0 05 1 1 1 04 4 0 0 04 3 1 0 04 2 2 0 04 2 1 1 04 1 1 1 13 3 2 0 03 3 1 1 03 2 2 1 03 2 1 1 12 2 2 2 02 2 2 1 1一共18个答案。
8.用一维数组储存二叉树的方法题目中也说了:
(根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+l处)
那么,问题来了:如果某非叶子节点没有左孩子,那么这一个下标放什么呢?
空着。
因为如果把其他节点放过来了,就无法满足上述条件了,那么就无法正确访问该二叉树了。
所以,我们要将其余位置补全,使其变成一棵完全二叉树
原图如下:
更改为完全二叉树后如下:
可知共需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.P.S.P.S. 如果连前中后序遍历都不知道的同学,请自行学习相关知识。
15.死知识:“计算机领域的诺贝尔奖”为“图灵奖”
阅读程序题 一、 #include #include using namespace std;char st[100];int main() {scanf("%s", st);int n = strlen(st);for (int i = 1; i = '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
答案就出来了。 有兴趣的同学可以证明一下我提供的方法。
二、 #includeusing namespace std;int n, m;int a[100], b[100];int main() {scanf("%d%d", &n, &m);for (int i = 1; i n;for (int i = 0; i > a[i];for (int i = 0; i > b[i];cout