2021普及组真题

阅读程序部分难度比较高，其他的难度还可以，整体来说必之前难一点。

一、单项选择

1.D

2.B

3.A

4.C

​ N个数字找最大值，一般做法就是把第一个数字作为最大值直接存下来，然后和后面的每个数字比较，这种方法的比较次数是N-1,同时也是答案中的最小值了，故选 C。

5.D

模拟入栈出栈操作就可以。

6.D

​ 图有m条表，树的边数是n-1，即m - ( ) = n-1. 需要删除 m-n+1条边。

7.C

8.A

​ 高度为5的完全二叉树最后最后一层的节点数取值范围为1 - 16 故选 A

9.B

10.B

​ C~6~^2^ * C~4~^2^ * C~2~^2^ / A~3~^3^ 先给每一组选人，因为不区分编号，消除因为组号带来的不同，故需要除以 A~3~^3^

11.B

12.A

​ 分情况讨论：

​ 无重复数字：只能选123，然后A~3~^3^

​ 有重复数字：先从1,2选出重复数字具体是谁，然后再选出唯一的数字，这样的三个数字有三种排列方法。

​ C~2~^1^ * C~2~^1^ * 3

​ 所以共有 A~3~^3^ + C~2~^1^ * C~2~^1^ * 3 = 18种情况

13.C

​ 7 * 5 * 3 * 2 * 1

14.B

15.B

​ 这里过河有两种策略：

​ 策略1：让快的人送慢的人过河 然后快的人划船回来 可以节省回来的时间

​ 策略2：让两个慢的人一起过河 这样整体来说可能会节省一些时间

​ 过河过程：

​ 1 2 → 过河 ←1 回来

​ 4 8 → 过河 ←2 回来

​ 1 2 → 过河

​ 总的过河时间： 2 + 1 + 8 + 2 + 2 = 15

二、阅读程序

（1）

​ 题目重点是要知道 f(x) 和 g(x)的作用。

​ 首先看f(x)：

​ 假设 x 是 5,转换成补码进行运算

​ x： 0000 0000 0000 0101

​ x-1： 0000 0000 0000 0100

​ x&x-1： 0000 0000 0000 0100

​ x变成4:，继续运算

​ x： 0000 0000 0000 0100

​ x-1： 0000 0000 0000 0011

​ x&x-1： 0000 0000 0000 0000

​ 那么，不难看出，x&x-1的作用相当于去掉了二进制x中最低位的1，

​ f(x)这个算法叫做pop_count()，作用是统计一个数字的二进制形式中有含有的 1 的数量。

​ 然后看g(x):

​ 假设 x 是 5,转换成补码进行运算

​ x： 0000 0000 0000 0101

​ -x： 1111 1111 1111 1011

​ x&-x: 0000 0000 0000 0101

​ 假设 x 是 4,转换成补码进行运算

​ x： 0000 0000 0000 0100

​ -x： 1111 1111 1111 1100

​ x&-x: 0000 0000 0000 0100

​ 那么，不难看出，x&-x的作用相当于取到了二进制x中最低位的1的权重。

​ g(x)其实就是树状数组中常用的 lowbit()操作。

1. 错误

2. 错误

3. 错误

   根据代码分析进行计算

   2：2+1 = 3 正确

   11：3+1 = 4 正确

   9： 2+1 = 3 正确

   16: 1+16 = 17正确

   10: 2+2 = 4 错误

4. 正确
   直接计算：
   511998 = 0111 1100 1111 1111 1110
   16 + 2 = 18

20： 错误
需要有函数声明才行

1. B
   2147483647这个数字可能大家会比较眼熟，他就是int的最大值 0后面跟31个1，所以第二个输出是31+1=32，故选B。

（2）
首先简单介绍下什么是 base64。
base64是一种加密算法。

加密：
一个char在计算机中对应的是8个bit。
比如 'a' 在计算机中对应的 是97，对应的存储内容是0110 0001，占用8个bit。
这样的话 把三个char 对应的 24个bit 每6个一组变成4个元素，重新编码就达到了加密的目的。
解密：把四个元素转回三个字符。

1. 错误
   不可能出现等号。

2. 正确
   中间如果有换行符，可以使第二行相同 ，第三行不同。

3. 正确
   0xFF = FF(16) = 11111111(2) = char(-1)
   即 int(char(-1))==-1 ? 不一定 和编译器有关 目前主流认为是正确的

25.B

1. B
   代入计算即可
   Y3Nx 每个字符对应6个比特位、
   Y -> 24 -> 011 000
   3 -> 55 -> 110 111
   N -> 13 -> 001 101
   x -> 49 -> 110 001

   把数据拼接并重新编码：
   01100011 01110011 01110001
   99->c 115->s 113->q

2. C
   方法同上。

（3）
这是一个欧拉筛法的代码。
a[] 标记数组 a[i]为false，表示i是质数。
b[] 存储所有质数
f[] 存储x的约数个数
g[] x的所有约数之和

28.正确
29.错误
30.错误
代数即可
31.A
32.C
约数个数为2，就是质数。
其实就是问有几个质数，100以内质数有25个

1. C
   1000 = 2^3^ * 5^3^

   约数个数：

   ​ 幂次+1 的累乘： (3+1) * (3+1) = 16

   约数和：

   ​ 幂次对应等比数列和的累乘：（1+2+4+8）* （1+5+25+125）= 2340

三、完善程序：

（1）约瑟夫问题
结合选项读代码，可知：
F[i] == 0表示没出圈。
单层循环：循环结束则任务完成，那么循环条件就和出队数有关
i是下标，c是剩余人数，还需要一个变量记录当前这个人报0还是1，这个应该就是p

1. D
   筛掉n-1个人，任务结束，故循环的条件是 c<n-1

   1. C
      满足条件被筛掉 所以是判断 P==1 所以算 C

   2. c
      筛掉的人数+1

   3. D
      改变P的状态，下一个人应该报不同的数字。

   4. B
      无论是否被筛掉都需要进行的操作，就是让i从前往后周而复始的扫描。

（2）矩形计数
结合选项读代码，可知题目大致思路。
equals() 用来判断两个点是否相同，cmp()按照某种方式比较两点，sort（）冒泡排序，unique()用来去重，binary_search()查找某个点点是否存在。
主函数读入所有点，排序去重。i,j分别是左上和右下两个点，然后在看是否存在对应的左下和右上的点，就可以知道能组成多少个矩形。
二分处的代码要一起分析，根据已有的二分的代码，可知空白4处条件是A[mid]小于p的情况，A[mid]大于等于p时 b=mid，相当于是找一个坐标第一次出现的位置，空白3处取mid时不用+1.

39.B
    以x为第一关键字,y为第二关键字进行升序排列。
40.D
    第一个点或者不重复的点，保留下来.
41.C
    二分查找左边界，不用+1.
42.B
  A[mid]小于p的情况，故A[mid]在前。
43.D
    为了避免重复，必须前面的点坐标小于后面的点。