单项选择

1.B

答案解析

CPU,即central processing unit,中央处理器;CPU只能执行机器指令,也就是二进制的代码位数只能说明处理的字长，所在的系统硬件指令不同，速度很难说谁快；Intel最早发明的是微处理器，而CPU之前就由电子管、晶体管实现。

2.B

答案解析

(1111111111101101)补=(1000000000010011)原=(-19)$_{10}$。

3.B

答案解析

在计算机内部，用来传送、存储、加工处理的数据或指令(命令)都是以二进制码形式进行的。

4.C

答案解析

插入排序、基数排序、归并排序都是稳定排序。

5.C

答案解析

A是根节点，所以只有C答案正确。

6.B

答案解析

利用快速排序的特点：第一遍排序会确定一个数的位置，这个数左边都比它大，右边都比它小(降序)，当左边区间大于K时，说明我们求的第K大数在左边区间，这时我们可以舍弃右边区间，将范围缩小到左边区间从而重复上述过程，直到确定一个数的位置时，左边区间的小是K-1那么这个数字就是我们所求。右边同理。如果我们使用分治算法求得话，会得到一个线性的时间复杂度O(n)。

7.C

答案解析

可以画出这个有向图，矩阵存储的时候，矩阵为非对称，故为有向图；入度之和等于出度之和。

8.C

答案解析

1978―2019年间的闰年是1980年、1984年、1988年、1992年、1996年、2000年、2004年、2008年、2012年、2016年。 365/7=52......1 366/7=52......2 41-10=31个非闰年,31+10*2=51 51/7=7......2,所以星期一往回退两天就是星期六。

9.B

答案解析

先建一棵表达式树，其后序遍历就是后缀表达式。

10.B

设 $n=2^{k}$ , 则

$\begin{array}{l} T\left(\frac{n}{2}\right)=2 T\left(\frac{n}{2^{2}}\right)+\frac{n}{2} \\ T\left(\frac{n}{2^{2}}\right)=2 T\left(\frac{n}{2^{3}}\right)+\frac{n}{2^{2}} \\ T(n)=2 T\left(\frac{n}{2}\right)+n=2^{2} T\left(\frac{n}{2^{2}}\right)+2 \times \frac{n}{2}+n=2^{3} T\left(\frac{n}{2^{3}}\right)+2^{2} \times \frac{n}{2^{2}}+2 \times \frac{n}{2}+n \\ =2 k T(1)+\mathrm{kn}=n T(1)+k n=n(\operatorname{logn}+T(1))=O(n \operatorname{logn}) \text { 。 } \end{array}$

11.A

满二叉树的深度与叶子结点的个数关系 $2^{\mathrm{k-1}}$, 深度为 11 时, 叶子结点个数是 $2^{10}$ , 即为 1024 个, 所以不可能有 2011 个叶子节点。

12.B

原序列有 (7,5)(7,1)(7,3)(7,6)(7,4)(5,1)(5,3)(5,4)(9,3)(9,4)(9,6)(9,8) (9,4)(6,4)(8,4) 15 个逆序对, 当去掉 6 时, 会减少 (7,6)(9,6)(6,4) 3 个逆序对。

13.B

由题可知, 读过 a 的人数为 P(a)=8 , 同理知 P(b)=4, P(c)=3, P(a b)=2 , 则有 P(a b)= 4, P(a b)=2, P(a c)=2-P(a b c)=0, P(b c)=3-P(a b)=1 , 所以读过 a 的人数为 P(a)+ P(a b)+P(a b c)+P(a c)=8+2+2+0=12 .

答案解析

14.C

$\frac{\mathrm{C}_{3}^{2} \times \mathrm{A}_{365}^{2}}{365 \times 365 \times 365}=\frac{3 \times 364}{365 \times 365} $

15.D

子串的定义是原字符串中连续的一段字符组成的字符串, 不同的子串是当且仅当两个子 串长度不一样,或者长度一样但有至少任意一位不一样时成立。那么将“abcab”先看成 5 个不同字符, 不同字符的子串个数是 $\frac{\mathrm{n}(\mathrm{n}+1)}{2}+1=15$ , 不包含空串。字串只有一个字符 时,多了一个“ a ”,一个“ b ”; 字串只有 2 个字符是多了一个“ a b ”。 15-3=12 。

阅读程序

16.B

答案解析

若输入的b数组都是奇数，程序运行到第15行时，b[1]没有发生变化。

17.A

答案解析

运算的先后顺序改变，可能会影响程序的结果。

18.B

答案解析

若输入2357，当程序运行到第15行时，a数组的值不等于b数组的值。

19.A

答案解析

输入b数组都是偶数，经过第11行和第12行后，a数组中的值也全部为偶数。

20.C

答案解析

该程序能输出的最大结果为 18×18×18×18=104976。

21.B

答案解析

模拟程序执行过程,b={94,8,49,33},a={2,5,26,92},结果为5850。

22.A

答案解析

不包含“-”号, s2 和 s1 必定相同。

23.A

答案解析

输入a1-a2，输出的字符串为a1-a2，则输出的字符串长度与输入的相同。

24.A

答案解析

if(c=='-')才会处理字符串，若输人的字符串不包含“-”号，则输出的字符串和输入相同。

25.B

答案解析

如果输入A-D,输出结果是ABCD。

26.C

答案解析

A-Z-A-Z,输出26×2=52个字符。

27.C

答案解析

A~Z一组可以输出26个字符，至少输入60个字符。

28.A

答案解析

选择排序算法实现了对一个长度为n的序列进行排序。

29.A

答案解析

代码没有使用scanf和printf,去掉头文件“#include 译运行的。

30.B

答案解析

去掉“using namespace std;”, cin cout前面就需要加std::,才能编译成功。

31.C

答案解析

选择排序算法的基本思路是为每一个位置选择当前最小的元素。

32.C

答案解析

选择排序算法的时间复杂度为O($n^2$)。

33.C

答案解析

32154一>12354执行两次,12354一>12345执行一次,共3次。

34.A

beg存储的是当前最优数列的首项的前一项序号，初始化为0。

35.C

如果a[j]+tmp与ans相等时，和最大的前提下还要求该子数列包含的元素个数最多,当i-beg大于len,就会更新len=i-beg。

36.C

当tmp要清零时，i位置的元素不会是最优数列的元素，此时a[i]+tmp<0。

37.C

当a[i]+tmp<0,i位置的元素不会是最优数列的元素, beg会更新到i位置。

38.D

答案解析

a[i]+tmp>=0时,a[i]加入tmp中。

39.C

答案解析

将棋盘分成了四等份，如果特殊方格(dr， dc)落在左上角的子棋盘中，即(dr<tr+s)&&(dc<tc+s)则需要进一步递归,(tr, tc)和(dr, dc)不变并且只缩小棋盘s=s/2。

40.B

答案解析

如果特殊方格落(dr， dc)不落在左上角的子棋盘中，用编号为t的骨牌覆盖子棋盘右下角, board[tr+s-1][tc+s-1]=t,并进行覆盖其余方格chessboard(tr, tt, tr+s-1, tc+s-1,s)。

41.D

答案解析

如果特殊方格(dr， dc)不落在右上角的子棋盘中，用编号为t的骨牌覆盖子棋盘左下角, board[tr+s-1][tc+s]=t,并进行覆盖其余方格chessboard(tr, tc+s, tr+s-1, tc+s,s)。

42.D

答案解析

如果特殊方格(dr， dc)不落在左下角的子棋盘中，用编号为t的骨牌覆盖子棋盘右上角, broad[tr+s][tc+s-1]=t,并进行覆盖其余方格chessboard(tr+s, tc, tr+s, tc+s-1 ,s) 。

43.D

答案解析

如果特殊方格(dr， dc)不落在右下角的子棋盘中，用编号为t的骨牌覆盖子棋盘左上角，board[tr+s][tc+s]=t,并进行覆盖其余方格chessboard(tr+s, tc+s, tr+s, tc+s,s)。