一、单项选择题

1. A。 C 语言是面向过程的编程语言；C++、Python、Java均为面向对象的编程语言。
2. C。 $1GB = 1024MB = 1024 * 1024 KB = 1024 * 1024 * 1024 B = 2^30B$。
3. A。 八进制数 $356.433$ 对应的十六进制整数是 $EE.AD8$。
4. B。 二进制数 $00101100+00011101=01001001$。
5. A。 栈的特点是先进后出，后进先出（First In Last Out, Last In First Out）。
6. D。 $POP3$（邮局协议的第3个版本）、$SMTP$（简单邮件传输协议）、$IMAP$（交互式邮件存取协议）均为电子邮件中常用的协议；$P2P$对等网络是一种网络结构，与电子邮件传输无关。

7. C。 因要求男女相间，则男生和女生的位置共有如下两种不同方案： • 男生在第 $1、3、5$ 个位置，女生在第 $2、4、6$ 个位置； • 或者女生在第 $1、3、5$ 个位置，男生在第 $1、3、5$ 个位置。 其次，男生之间的排列方案数为 $A_3^3$ 种，女生之间的排列方案数为 $A_3^3$ 种，所以总的排列方案数为 $C_2^1×A_3^3×A_3^3=72$。

8. C。 包含 $100$ 个节点的二叉树中共有 $99$ 条边，对于任意一个节点，它若要包含 $2$ 个子节点，则需要 $2$ 条边分别连向它的两个子节点，所以最多有 $99/2=49$ 个节点具有 $2$ 个子节点。

9. C。 快速排序算法的平均时间复杂度为 $O(nlogn)$。
10. C。 • 以 A 开头共有 $6$ 个不同的子串，分别是 A、AB、ABB、ABBC、ABBCC、ABBCCC； • 以 B 开头共有 $5$ 个不同的子串，分别是 B、BB、BBC、BBCC、BBCCC、BC、BCC、BCCC； • 以 C 开头共有 $3$ 个不同的子串，分别是 C、CC、CCC。 所以共有 $6+8+3=17$ 个不同的非空子串。
11. C。 $3570$ 和 $2023$ 的最大公约数是 $119$。
12. D。基础二分查找的要求，元素有序，且能随机访问。
13. B。不妨想思考 $0 \sim 99$ 这 $100$ 个数中包含 $2$ 的数的个数，可以发现，除了 $20 \sim 29$ 这 $10$ 个数以外，还存在 $2、12、32、42、52、62、72、82、92$ 这 $9$ 个数是包含 $2$ 的，所以 $0 \sim 99$ 范围内共有 $10+9=19$ 个包含 $2$ 的数，据此可以推导出 $100 \sim 199$ 范围内包含 $2$ 的数的个数也为 $19$，对于 $300 \sim 399,400 \sim 499,...,900 \sim 999$ 也可以发现同样的规律，但是 $200 \sim 299$ 这 $100$ 个数的百位都是 $2$， 所以这 $100$ 个数都是包含 $2$ 的数。据此可以推导出 $0 \sim 999$ 范围内包含 $2$ 的数的个数 $=100+19x9=271$，同理可得 $1000 \sim 1999$ 范围内包含 $2$ 的数的个数也为 $271$ 。而 $2000 \sim 2023$这 $24$ 个数都是包含 $2$ 的数（因为千位为 $2$），所以 $0\ sim 2022$ 范围内包含 $2$ 的数的个数为 $271x2+24=566$ ，因 $0$ 不包含 $2$，所以可得： $1 \sim 2023$ 范围内的整数中包含 $2$ 的数的个数为 $566$。
14. B。根据函数的推导公式可得 $solve(5,6)$ 的结果为 $210$。
15. C。解析：冯·诺依曼体系结构的核心内容是采用存储程序和程序控制原理。

二、阅读程序

第一小题

1. 正确。解析：当 $n=1000$ 时，会使用到下标为 $1000$ 的数组元素 $a[1000]$，而数组的元素下标从 $0$ 到 $999$，所以会发生数组越界。
2. 错误。解析：解决本题最简单的办法就是找一个“反例”，可以发现，当 $n=3$ 时，$a[1]=2,a[2]=3,a[3]=2$，并不是一个 $1 \sim n$ 的排列。
3. 正确。解析：输入为 $5$ 时，输出的第一行为 $3$。
4. 错误。解析：输入为 $7$ 时，输出的第一行为 $1$。
5. D。解析：该程序的目的是将 $n$ 个数的最小值交换到 $a[1]$，将第二小的值交换到 $a[2]$，其中可能存在多个数的值均为最小值的情况，此时 $a[1]==a[2]$，如果数字都不相同则第一个数字小于第二个数字，所以答案是不确定
6. C。解析：当 $n=20$ 时，$a$ 数组中的 $20$ 个元素分别为 $11,14,9,4,19,14,9,4,19,14,9,4,19,14,9,4,19,14,9,4$，其中次小值为 $4$。

第二小题

1. 正确。循环过程中时刻能保证对于任意 $a[i]$，若 $i>1$，则 $a[i/2]<=a[i]$，所以 $a[1]$ 最小。
2. 错误。是能保证 $a[i/2]$ 和 $a[i]$之间的大小关系，所以数组中一些元素的大小关系是无法确定的，比如 $a[2]$ 和 $a[3]$，所以程序并不能保证 $a[1] \sim a[n]$ 是升序的。
3. 正确。可以发现，当 $n$ 个元素按逆序输入时，输出的 $cnt$ 是最大的，不妨设 $a[1]=10,a[2]=9,...,a[10]=1$，可以发现：输入 $a[1]$ 后交换了 $0$ 次、输入 $a[2]$ 后交换了 $1$ 次、输入 $a[3]$ 后交换了 $1$ 次、输入 $a[4]$ 后交换了 $2$ 次、输入 $a[5]$ 后交换了 $2$ 次、输入 $a[6]$ 后交换了 $2$ 次、输入 $a[7]$ 后交换了 $2$ 次、输入 $a[8]$ 后交换了 $3$ 次、输入 $a[9]$ 后交换了 $3$ 次、输入 $a[10]$ 后交换了 $3$ 次。所以总共交换了 $0+1+1+2+2+2+2+3+3+3=19$ 次。
4. 错误。当 $n$ 个元素按逆序输入时，输出的 $cnt$ 最大，同时对于第 $i$ 个元素 $a[i]$，交换次数为 $⌊log2i⌋-1$ 次。所以： 对于第 $1$ 个数（共1个数），各交换了0次； 对于第 $2 \sim 3$ 个数（共2个数），各交换了 $1$ 次； 对于第 $4 \sim 7$ 个数（共4个数），各交换了 $2$ 次； 对于第 $8 \sim 15$ 个数（共8个数），各交换了 $3$ 次； 对于第 $16 \sim 31$ 个数（共16个数），各交换了 $4$ 次； 对于第 $32 \sim 63$ 个数（共32个数），各交换了 $5$ 次； 对于第 $64 \sim 100$ 个数（共37个数），各交换了 $6$ 次。 总的交换次数为 $1×0+2×1+4×2+8×3+16×4+32×5+37×6=480$次 $>450$ 次。
5. D。输入 $a[3](2)$后交换了1次，输入 $a[4](4)$ 后交换了 $1$ 次，输入 $a[5](1)$ 后交换了 $2$ 次，共交换了 $4$ 次。
6. A。只在输入 $a[3](1)$ 后交换了 $1$ 次。

第三小题

1. 错误。 $init()$ 函数调用结束后，$m$ 的值为 $1 \sim 1000$ 范围内素数的个数，虽然我们不能很快得出这个结果，但是容易发现 $1 \sim 1000$ 范围内素数的个数肯定比非素数的个数要少，所以 $m$ 不可能是 $500$ 。
2. 正确。 $init()$ 函数调用结束后，所以素数 $i$ 对应的 $f[i]$ 均为 $0$，所有非素数 $i$ 对应的 $f[i]$ 均为 $1$。因为 $103$ 是素数，所以 $f[103]=0$。
3. 正确。 $g[1000]$ 表示的是 $1 \sim 1000$ 中非素数的个数， $m$ 表示的是 $1 \sim 1000$ 中素数的个数，所以 $g[1000]+m$ 等于 $1000$。
4. B。因为 $123$ 不是素数，所以 $f[123]=1$。
5. C。 $g[30]$ 表示 $1 \sim 30$ 范围内非素数的个数，$1 \sim 30$ 范围内共有 $20$ 个非素数，所以 $g[30]=20$。
6. B。 $p[i]$ 表示第 $i$ 个素数，我们可以依次列举出前 $25$ 个素数：$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$，可得第 $25$ 个素数 $p[25]=97$。

三、完善程序

第一小题

1. A。解析：喝了 $n$ 瓶汽水，已喝汽水总量增加$n（s+=n）$。
2. A。解析：喝了 $n$ 瓶汽水，瓶盖总量增加 $n（t+=n）$。
3. D。解析：用 $t$ 个瓶盖最多可兑换 $t/k$ 瓶汽水，所以 $n$ 更新为 $t/k$。
4. B。解析：兑换尽可能多的汽水后，剩余瓶盖数量为 $t%k$。
5. A。解析：只要能对话至少 $1$ 瓶汽水$（n>0）$，就继续循环。

第二小题

1. C。解析：第 $i$ 小的应与第 $x+1-i$ 大数（即 $a[n-x+i]$）的比较。
2. C。解析：根据输入是从 $a[1]$ 输入 $a[n]$，所以排序也是给 $a[1]$ 到 $a[n]$ 排序，对应的 $sort$ 函数应写为 $sort(a+1, a+n+1)$。
3. C。解析：根据二分的写法，可知判断的区间范围是 $[l,r]$，所以二分的判断条件是 $l <= r$。
4. B。解析：因为 $check(x)$ 判断能够凑成 $x$ 对，所以当条件成立时应让 $l = mid + 1$ 以寻找更大的答案；当条件不成立是应让 $r = mid - 1$ 以寻找更小的答案。
5. C。