一、单项选择题

1. A。计算机缺少CPU将无法正常启动。
2. A。不妨将单位全都转成MB：36000 KB ≈ 35.2 MB，33 MB = 33 MB，0.03 GB = 30.72 MB，36500000 B ≈ 34.8 MB，所以 36000 KB 最大。
3. C。不妨设状态 $f_i$ 表示所有高度 $\leq i$ 的二叉树的不同形态树，则可得推导公式为 $f_i=(f_{i-1}+1)^2$，所以可得 $f_1=1，f_2=4，f_3=25$，所以高度为 $3$ 的二叉树的不同形态数为 $f_3-f_2=25-4=21$。
4. D。对于出栈序列 $e, d, b, c, a$，因为入栈序列是 $a,b,c,d,e$，在 $b,c$ 均未出栈的情况下，$e,d$ 先出栈，说明在 $e,d$,出栈时 $c$ 在 $b$ 的顶端，所以必然 $c$ 先出栈，与出栈序列矛盾，所以选项 D 错误。
5. B。二进制数 $11001.1=$ 十进制 $1x24+1x23+0x22+0x21+1x20+1x2-1=16+8+0+0+1+0.5=25.5$。

6. C。相同深度的二叉树中满二叉树包含的叶结点个数最多。一棵深度为 $h$ 的满二叉树具有 $2^{h-1}$ 个叶结点，因为深度为 $11$ 的满二叉树包含的叶结点个数为 $2^{10}=1024$，深度为 $12$ 的满二叉树包含的叶结点个数为 $2^{11}=2048$，且 $1024<2023 \leq 2048$，所以包含 $2023$ 个叶结点的二叉树深度至少为 $12$。

7. A。八进制的一位对应二进制的三位，所以八进制数的后 $99$ 位均对应二进制的 $3$ 位，总位数为 $99x3=297$，最高位可能对应二进制的 $1 \sim 3$ 位（八进制 $1$ 对应二进制 $1$，八进制 $2$ 对应二进制 $10$，八进制 $3$ 对应二进制 $11$，八进制 $4$ 对应二进制 $100$，八进制 $5$ 对应二进制 $101$，八进制 $6$ 对应二进制 $110$，八进制 $7$ 对应二进制 $111$），所以一个 $100$ 位的八进制数转成二进制数可能是 $298、299$ 或 $300$ 位。

8. B。对于 $2000$ 来说，它只包含两个不同的质因子—— $2$ 和 $5$。所以与 $2000$ 互质的数是即不包含因数 $2$ 也不包含因数 $5$的 所有数字，$2000$ 以内，包含因数 $2$ 的数共有 $2000/2=1000$ 个，包含因数 $5$ 的数共有 $2000/5=400$ 个，同时包含因数 $2$ 和 $5$ 的数（即包含因数 $10$ 的数）有 $2000/10=200$ 个，所以可得：包含因数 $2$ 或 $5$ 的数共有 $1000+400-200=1200$ 个，所以 $2000$ 以内与 $2000$ 互质的数的个数为 $2000-1200=800$ 个。
9. A。 x & -x 可得到 $x$ 在二进制表示下最低一位 $1$ 对应的整数。
10. A。可以将 $4$ 轮看成一个循环，每个循环执行完后，$x$ 将会 $-2$，$y$ 将会 $+2$，前 $2020$ 轮恰好 $2020/4=550$ 个循环，所以前 $2020$ 轮之后的坐标是 $(-1010,1010)$，第 $2021$ 轮 $x$ 增加了 $2021$（变成 $-1010+2021=1011$），第 $2022$ 轮 $y$ 减小了 $2022$（变成 $1010-2022=-1012$），第 $2023$ 轮 $x$ 减少 $2023$（变成 $1011-2023=-1012$)$，所以最终的坐标是 $(-1012,-1012)$。
11. D。相当于从 $5$ 行中选两行，再从 $5$ 列中选 $2$ 列，其中 $2$ 个方格之间有 $A_2^2$ 种排列，所以总的方案数为 $C_5^2⋅C_5^2⋅A_2^2=200$。
12. C。分析代码可得 C 错误。在比赛时考虑时间因素，也可采用“套例子”的方法，比如：设 $x=3,y=2$（期望的结果为 $2$），将其带入四个选项，可得A、B、D的结果均为 $2$，而 C 的结果为 $1$，所以选C。
13. B。$4$ 个人之间的排列数为 $A_4^4$ ，可以想象将连续的三个空位看成一组，另一个空位看成一组，将两组空位插入 $4$ 个人之间的五个位置，方案数有 $C_5^2$ ，两组空位之间的排列数为 $A_2^2$ ，所以总的方案数为 $A_4^4⋅C_5^2⋅A_2^2=480$。
14. B。画图即可。
15. C。图灵奖是计算机科学领域的最高奖。

二、阅读程序

第一小题

1. 错误。也可包含小写英文字母，因为程序中有将小写英文转成大写英文字母的实现。
2. 正确。程序实现的功能就是将输入的字符串中的字符全部转成大写英文字母并从小到大排序后输出，所以输出的字符串长度与输入的字符串长度相同。
3. 正确 rUiBA时，输出应为 abiru。
4. 错误。当输入为 niceToMeetYou，输出应为 ceeeimnoottuy。
5. B。当输入的字符串是升序的且仅由小写英文字母组成时，输出的字符串与输入的字符串一样。
6. C。当输入为 codeInRUIBA 时对应的输出结果为 abcdeiinoru。

第二小题

本程序使用二分查找算法寻找 $x$ 在数组 $a$ 中对应的下标 $p$（若 $x$ 在数组中不存在则 $p=-1$），同时使用 $count$ 记录二分查找的次数。

1. 错误。解析：变量 $x$ 并不对应数组下标，所以 $x$ 的值并不会造成数组越界。
2. 正确。解析：因为 $p$ 对应数组 $a$ 的下标，所以若找到 $a[p]==x$，则 $p$ 的值介于 $0 \sim 14$ 范围内，若没有找到，则 $p=-1$，所以 $p$ 的值不会超过 $14$。
3. 正确。解析：变量 $count$ 的值对应二分查找的次数，对于长度为 $15$ 的数组 $a$，二分查找的次数不会超过 $⌈log_215⌉=4$。
4. C。解析：$a[2]==5$。
5. A。解析：$a$ 数组中不存在任何一个元素等于 $12$，所以输出的第一行为 $-1$。
6. D。解析：一共二分查找了 $4$ 次，对应的 $mid$ 及 $a[mid]$ 分别为 $a[7]=22,a[11]=62,a[9]=45,a[8]=37$。

第三小题

1. 正确。 设 $len$ 表示 $s$ 的二进制表示中共有多少位为 $1$，而 $cnt=2^{len}-1$，而具有 $len$ 位 $1$ 的所有二进制整数中数值最小的即为 $2^{len}-1$，所以 $cnt \le s$ 成立，或者换个简单的思路，i 永远在变小，那么最起码也是每次 $-1$,所以 $i$ 的变化次数最多就是 $s$
2. 错误。 $bitcount(x)$ 函数计算的是 $x$ 的二进制表示中共有多少位为 $1$。
3. 错误。数组下标对应的是 $i$ 的二进制数表示中 $1$ 出现的位数，对于 $1 \sim 10^9$ 范围内的整数，其二进制表示中 $1$ 出现的位数不会超过 $100$，所以不会发生数组越界。
4. C。$(23)_{10}=(10111)_2$，所以 $len=4$，得 $cnt=2^{len}-1=15$。
5. D。 $c[1]=8+2+1=11,c[2]=10+9+3=22,c[3]=11$，得 $ans=22$。
6. B。通过分析代码可得 $c[i]=(C_{len}^i⋅i)/len⋅127$，所以 $c[1] = 127,c[2] = 762,c[3] = 1905,c[4] = 2540,c[5] = 1905,c[6] = 762,c[7] = 127$，得 $ans=2540$。

三、完善程序

第一小题

1. B。当 $d < f(y,m)$ 时， $y$ 年 $m$ 月 $d$ 日的下一天是 $y$ 年 $m$ 月 $d+1$ 日。
2. C。当 $d < f(y,m)$ 不成立(即 $d==f(y,m)$ )时，说明是该月的最后一天，此时若 $m < 12$，则 $y$ 年 $m$ 月 $d$ 日的下一天是 $y$ 年 $m+1$ 月 $1$ 日。
3. C。当 $d < f(y,m)$ 和 $m < 12$ 均不成立是，说明 $m==12$ 且 $d==31$，说明是 $y$ 年的最后一天，所以它对应的下一天是 $y+1$ 年 $1$ 月 $1$日。
4. A。
5. A。

第二小题

1. C。该空与下一空与快速排序的逻辑相同，易得第 (1) 空填 $j--$，也可以联系上下文对称来选择
2. B。理由同上，当然这里可以发现，第 $11$ 行 $a[i] = a[j]$ 后，$a[j]$ 的值在逻辑上已经空出来了，这里肯定是给 $a[j]$ 赋值
3. D。循环操作结束后能保证区间 $[l,i-1]$ 范围内的数都 $>= a[i]$，区间 $[i+1,r]$ 范围内的数都 $<= a[i]$，所以若 $i-l+1==k$，则说明 $a[i]$ 恰为区间 $[l,r]$ 范围内第 $k$ 大的数。
4. C。若 $i-l+1 > k$，则进区间 $[l,i-1]$ 继续查找第 $k$ 大的数。
5. C。若 $i-l+1 < k$，则区间 $[l,r]$ 范围内第 $k$ 大的是应该在区间 $[i+1,r]$ 范围内，但是因为区间 $[l,i]$ 范围内的 $i-l+1$ 个数都大于等于区间 $[i+1,r]$ 范围内的数，所以应去区间 $[i+1,r]$ 范围内找第 $k-(i-l+1)=k+l-i-1$ 大的数。