单项选择

1.B

答案解析

IPv4中,合法IP地址范围为(1~255).(0~255).(0~255).(0~255)。所以答案为B。

2.C

答案解析

A ∨ B = 1100 1111 0111 ， A ∨ C = 1111 1111 1011

故(A ∨ B)∧(A ∨ C)的值为1100 1111 0011

3.D

答案解析

最大:01111111(2),即 2⁷+2⁶+2⁵+2⁴+2³+2²+2+1=127, 最小:11111111(2),即一(2⁷+2⁶+2⁵+2⁴+2³+2²+2+1) =-127。

4.C

答案解析

先将八进制数转化为二进制数每1位转化为3位得111000100010，再将二进制数转化为十六进制每4位转化为1位得E22。

5.A

答案解析

BCD三个算法均需要比较关键字，而基数排序是将比较元素先放进表中，然后按顺序遍历取出，所以它并不需要进行关键字比较操作，所以选A。

6.C

答案解析

考虑三种颜色的球出现的顺序：红黄蓝、红蓝黄、蓝红黄、蓝黄红、黄蓝红、黄红蓝。对于第一种顺序，抽到的概率为(3/7)*(2/6)*(3/5)，同理求出剩下五种，求和即可。

7.B

答案解析

暴力枚举0~120内素数和回文数，注意11和101既是回文又是素数。

8.C

答案解析

深度为9的完全二叉树节点数范围在512-1023之间。

9.B

答案解析

2021分解为43*47。抽屉原理：取43为最大公约数时，剩余9个数的和取1-9，得到答案B；取47为最大公约数，9个数必然会有重复。

10.B

答案解析

B。冯·诺依曼是现代电子计算机与博弈论的重要创始人。

11.B

答案解析

a1,a2入栈,a2出栈,a3,a4进栈,a4,a3出栈,a5,a6进栈,a6,a5,a1出栈,所以栈的容量至少为3。

12.C

答案解析

19,88需要查找2次;56需要查找1次;13,37,75需要查找3次;5,21,64,92需要查找4次。

13.A

答案解析

强连通图的边数最少时为一个环。

14.C

答案解析

容斥原理,2015-503-403-335-100+67+167-33=1075。

15.A

答案解析

A错误，是n个节点的不同形态二叉树个数。

阅读程序

16.B

17.B

18.A

19.B

20.D

21.B

答案解析

(1)第四行与第十行函数应一致，故不能通过编译。

(2)若x，y，p均为-3，则程序运行永远不会停止。

(3)x=1时,直接返回。

(4)x可能为负数，故此题为错。

(5)(6)按题意模拟即可，计算量不大。

22.B

23.A

24.B

25.B

26.D

27.C

答案解析

(1)显然每两个数之间只会被比较一次，故程序必然结束，错误。

(2)a数组将原序列从小到大排序，b数组将原序列从大到小排序，故当且仅当输入的X[1],X[2],⋯,X[N]全部相同时输出的两行结果相同,正确。

(3)本题是冒泡排序，错误。

(4)a数组将原序列从小到大排序，b数组将原序列从大到小排序，故B正确。

(5)a数组将原序列从小到大排序，b数组将原序列从大到小排序，故ABC正确，且快速排序可以在O(NlogN)时间内完成这一过程，D错误。

(6)由于每两个数之间比较一次，时间复杂度为O(N²)。

28.B

29.B

30.B

31.D

32.D

33.A

答案解析

算法过程如下：找到一个当前num的最小质因子，并将其除干净，直到num为一个质数,因此 max_primedivisor= max(max_primedivisor, num);这句话是有必要的。并且因为最小质因子<$O(\sqrt{num})$, 所以最坏时间是复杂度$O(\sqrt{num})$,而当num=2ᵏ时,时间复杂度最优为$O(lognum)$。再通过计算或模拟发现cnt存的是num的约数个数，由此可解出正确答案。

完善程序

（1）

34.D

35.B

36.A

37.C

38.A

答案解析

仔细分析这道题，我们可以发现它的性质：一定是每行间隔或者每列间隔着选。

(1)考察数组基本概念和读题，a[][]数组存储n行n列的方阵电力值，n<=5000。

(2)、(3)、(4)考察发现性质或根据上下文程序推理猜测。

(5)求最大总电力值，应在ans1和ans2中取较大者。

(2)

39.A

40.C

41.D

42.D

43.B

答案解析

(以下的n/m都表示C++中的n整除m)

当n为偶数时,将1~n分为1~n/2(第一类),n/2+1~n(第二类),我们使A中的第一类匹配B中的第二类，使A中的第二类匹配B中的第一类，这样便可使排列B的字典序的值最小，因此我们可以从前往后贪心地放数，从前往后遍历排列A，遇到第一类数，放当前还没用过的最小的第二类数；遇到第二类数，放当前还没用过的最小的第一类数。

所以①处需要先判断n是否为偶数，故选A；②处的p2表示的是当前还没用过的第二类数的最小值-1，所以初始值应该赋n/2。

当n为偶数时，情况类似，但由于n/2+1的存在，我们需要分两种情况：A数组中的1~n/2匹配B数组中的n/2+2~n,B数组中的1~n/2+1匹配A数组中的n/2+1~n;或A数组中的1~n/2+1匹配B数组中的n/2+1~n,A数组中的n/2+2~n匹配B数组中的1~n/2(两种情况的值是相同的)。所以我们将两种情况分别算一遍，取字典序较小的即可。

对于③处，观察到上面的p2初始值为n/2，是上文提到的第二种情况，所以可与p1匹配的A[i]满足A[i]>n/2+1,选D;则下面是第一种情况,所以可与p1匹配的A[i]满足A[i]>=n/2+1，所以④处填D；对于⑤处，因为我们最后输出的都是B数组，如果C数组的字典序小于B数组，我们必须交换B数组和C数组，由上面的循环可知， flag=1时表示B数组的字典序小于C数组，所以flag！=1交换不影响答案，故选B。