CSP 2020 第一轮（初赛）模拟解析

一、十进制数 \(114\) 的相反数的 \(8\) 位二进制补码是：

A. \(1000 1110\) $\ \ \ \ \ $ B. \(1000 1101\) $\ \ \ \ \ $C. \(01110010\) $\ \ \ \ \ $ D. \(01110011\)

根据原码补码反码的有关定义可得：
-114 的源码为 ：0111 0010
       反码为 ：1000 1101
     故补码为 ：1001 1110，  选A 
	 
下贴原码补码反码的相关定义：
	正数的原码、反码、补码均相同。
	原码：用最高位表示符号位，其余位表示数值位的编码称为原码。其中，正数的符号位为 0，负数的符号位为 1。
	负数的反码：把原码的符号位保持不变，数值位逐位取反，即可得原码的反码。
	负数的补码：在反码的基础上加 1 即得该原码的补码。
	
此题为简单题，熟记概念即可，不应扣分。

二、以下哪个网站不是 Online Judge（在线程序判题系统）？Online Judge 可以查看算法题目，提交自己编写的程序，然后可以获得评测机反馈的结果。

A. Luogu $\ \ \ \ \ $ B. Gitee $\ \ \ \ \ $ C. LeetCode $\ \ \ \ \ $ D. Codeforces

A.Luogu 洛谷是基于网页形式的信息学在线评测系统。同时具有多种社区功能
B.Gitee 又称码云，是基于Git的代码托管网站，约等于Github
C.LeetCode  又名力扣,是一个为全球程序员提供 IT 技术职业化提升的平台,提供了完善的在线判题服务（OJ）、学习工具、社区讨论及模拟面试功能
D.Codeforces 是一家为计算机编程爱好者提供在线评测系统的俄罗斯网站。

以上部分内容来自于百度

此题为简单题，不应扣分。

三、小 A 用字母 \(A\) 表示 \(1\)，\(B\) 表示 \(2\)，以此类推，用 \(Z\) 表示\(26\) 。对于 \(27\) 以上的数字，可以用两位或者更长的字符串来对应，例如 \(AA\) 对应 \(27\)，\(AB\) 对应 \(28\)，\(AZ\) 对应 \(52\)，\(AAA\) 对应 \(703\) \(\dots\dots\)那么 \(BYT\) 字符串对应的数字是什么？

A. \(2018\) $\ \ \ \ \ $ B.\(2020\) $\ \ \ \ \ $ C.\(2022\) $\ \ \ \ \ $ D.\(2024\)

本题可近似理解为进制转换：
故的以下等式：
BYT = 2*26*26 + 25*26 + 20 = 2022

此题为简单题，核心在理解题面，不应扣分。

四、UIM 拍摄了一张照片，其分辨率是 \(4096×2160\)，每一个像素都是 \(24\) 位真彩色。在没有压缩的情况下，这张图片占用空间接近以下哪个值？
A.8MB $\ \ \ \ \ $ B.25MB $\ \ \ \ \ $ C.200MB $\ \ \ \ \ $ D.200KB

带入图片内存大小运算公式：
图片所占内存大小 = 图片长度(像素) * 图片宽度(像素) * 一个像素所占内存空间
                = 4096 * 2160 * 24 = 212336640 bit = 26542080Byte
                = 25920 KB = 25.3125 MB

此题为简单题，理解核心公式，不应扣分。

五、在一个长度为 \(n\) 的数组中找到第 \(k\) 大的数字，平均的算法时间复杂度最低的是：

A.\(O(n)\) $\ \ \ \ \ $ B.\(O(nk)\) $\ \ \ \ \ $ C.\(O(nlog⁡n)\) $\ \ \ \ \ $ D.\(O(n2)\)

通过简单的朴素思路可以将BCD三个选项的算法设计
B 通过冒泡排序或者选择排序的排序规则，第k大值会在第k轮被排入有序序列，进行k轮冒泡或选择排序即可得到结果。
C 这个复杂度的算法非常多样，包括但不限于快速排序直接查找，构建平衡树
D 暴力枚举比大小，亦或插入排序
这时考虑如何设计A项复杂度的算法：（相对有点难度，不过是经典的模型）
1. 首先任选一个树x，将原数组A分为Sa，Sb两个部分，满足Sa中的元素均大于等于x，Sb中元素均小于等于x
      若Sa中的元素个数小于k，那么Sb中的第k-|Sa|大的元素即为答案
      反之，Sa中第k大的元素的答案
2.按照规则分治递归处理

故平均复杂度可以用递推表达式表示为 T(n) = 2T(n/2) + O(1)，即复杂度为 O(n)

此题难度较难，可以允许扣分

六、对于“树”这种数据结构，正确的有：
①一个有 \(n\) 个顶点、\(n−1\) 条边的图是树
②一个树中的两个顶点之间有且只有一条简单路径
③树中一定存在度数不大于 \(1\) 的顶点
④树可能存在环

A. ①②④ $\ \ \ \ \ $ B. ①②③ $\ \ \ \ \ $ C. ②③ $\ \ \ \ \ $ D. ①②

①树保证连通性
④根据树的定义树上不存在环

此题为简单题，熟记概念即可，不应扣分。

七、博艾中学进行了一次信息学会考测试，其优、良、及格、不及格的试卷数量分别为 $10,13,14,5 $张。现在这些卷子混在一起，要将这些卷子按照等级分为 \(4\) 叠。分卷子的方法是，每次将一叠有不同等级答卷的卷子分为两堆，使得这两堆中没有相同等级的卷子，然后可以再分，直到分为 \(4\) 叠。要分完这些卷子，至少需要多少次“分卷子”的操作？将一堆数量为 \(n\) 的卷子分成两堆，就会产生 \(n\) 次分卷子的操作。

A. 84 $\ \ \ \ \ $ B. 93 $\ \ \ \ \ $ C. 78$\ \ \ \ \ $ D. 85

由题目题面的“将一堆数量为 n 的卷子分成两堆，就会产生 n 次分卷子的操作”。
那么可以得到很直观的贪心思维，应该让每一轮产生还继续分的堆的卷子尽量少：
于是得到两个算法，相对平均分成两堆在分开 ： 10+13+14+5+13+10+14+5 = 84
                从大到小挑出卷子： 10+13+14+5+10+13+5+10+5+5=85
故得到答案

此题为简单题，争取不扣分。

八、一个二叉树的前序遍历是 \(HGBDAFEC\)，中序遍历是 \(BGHFAEDC\)，同时采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 \(1\)，若某结点的下标为 \(i\)，则其左孩子位于下标 \(2i\) 处、右孩子位于下标 \(2i+1\) 处），则该数组的最大下标至少为（ ）

A. 7 $\ \ \ \ \ $ B. 13 $\ \ \ \ \ $ C. 15 $\ \ \ \ \ $ D. 12

1.先序遍历
(1)访问根结点；
(2)先序遍历左子树；
(3)先序遍历右子树。
2.中序遍历
(1)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。
3.后序遍历
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根结点。

第一步：还是先求root根节点，根据前序遍历规则我们可知root为前序遍历序列的第一个节点，因此该二叉树的root节点为H。
第二步：求root的左子树和右子树，这点我们还是从中序遍历序列中找出，位于root节点H左侧的B-G为root的左子树，位于H右侧的F-A-E-D-C为右子树。
第三步：求root的左子树的根节点和右子树的根节点。我们可以找到左子树B-G在前遍历序列中的排列顺序为G-B，由于前序遍历最先访问根节点，所以G为左子树的根节点，右子树同理
第四步：我们可以根据上面的步骤找到G的左子树和右子树，以及D的左子树和右子树，然后分别求出左右子树的根节点。以此类推，只要求出根节点及其和，剩下的过程都是递归的，最后我们就可以还原整个二叉树。

一直后序和中序求前序同理

此题为简单题，不应扣分。

九、在 C++ 语言中，如果 a=1 ;b=0 ;c=1 ; 那么以下表达式中为 \(1\) 的是：

A. a&&b||b&&c $\ \ \ \ \ $ B. a+b>c||b $\ \ \ \ \ $ C. !(!c&&(!a||b)) $\ \ \ \ \ $ D. a+b+c

A a&&b||b&&c = 0 || 0 = 0
B a+b>c||b = 1 + 0 > 1 || 0 = 0 || 0 = 0
C !(!c&&(!a||b)) = !(!c&&(0||0)) = !(0&&0) = !0 = 1
D a+b+c = 2

十、在一个初始长度为 \(n\) 的链表中连续进行 \(k\) 次操作，每次操作是读入两个数字 \(a_i\) 和 \(b_i\)，在链表中找到元素为 \(a_i\) 的结点（假设一定可以找到），然后将 \(b_i\) 这个元素插入到这个结点前面。在最理想的情况下，链表访问的结点数量最少可能是多少（不算将要插入的结点）？

A. \(n\) 次 $\ \ \ \ \ $ B. \(k\) 次 $\ \ \ \ \ $ C. \(nk\) 次 $\ \ \ \ \ $ D. \(n+k\) 次

每次均插在第二个，即只需要遍历 n 次

此题为简单题，牢记运算优先级，不应扣分。

十一、A 班有 \(5\) 名风纪委员，B 班有 \(4\) 名风纪委员，C 班有 \(3\) 名风纪委员。现在需要这些同学中选取 \(6\) 名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有几种不同的方案？

A. 9 $\ \ \ \ \ $ B. 12 $\ \ \ \ \ $ C. 15 $\ \ \ \ \ $ D. 18

暴力分类讨论计算：以C班选几个人为分类依据得：答案为4+5+5+4 = 18

此题为简单题，牢记运算优先级，不应扣分。

十二、以下哪种排序算法的时间复杂度是 \(O(n^2)\)？

A. 计数排序 $\ \ \ \ \ $ B. 插入排序 $\ \ \ \ \ $ C. 希尔排序 $\ \ \ \ \ $ D. 归并排序

此题为简单题，不应扣分。

十三、已知 rand() 可以生成一个 \(0\) 到 \(32767\) 的随机整数，如果希望得到一个范围在 \([a,b)\) 的随机整数，\(a\) 和 \(b\) 均是不超过 \(100\) 的正整数且 \(a<b\)，那么可行的表达式是什么？

A. (rand()%(b-a))+a $\ \ \ \ \ $ B. (rand()%(b-a+1))+a $\ \ \ \ \ $ C. (rand()%(b-a))+a+1 $\ \ \ \ \ $ D. (rand()%(b-a+1))+a+1

根据rand函数的定义得：
A:[a,b)
B:[a,b]
C:(a,b]
D:(a,b+1]

此题为简单题，不应扣分。