选择题（每题2分，共15题。）
1. 摩尔定律（Moore‘s law)是由英特尔创始人之一戈登·摩尔(Gordon Moor)提出来的。根据摩尔定律，单块集成电路的集成度是6年前的（ ）倍。
A.4
B.8
C.16
D.32
2. 关于汇编语言，下列说法正确的是( ).
A.是一种与软件相关的高级程序设计语言
B.在编写复杂程序时，相对于高级语言而言代码量较大，但更易调试
C.可以直接访问寄存器、内存单元、以及I/O端口
D.随着高级语言的诞生，如今已完全被淘汰，不再使用
3. 如果主存容量为16MB，且按字节编址，则表示该主存地址至少需要( )位.
A.16
B.24
C.26
D.32
4. 当输入＆％￥＃＊１２３４时，以下程序结束后，x＝（ ）
A.0
B.4321
C.1234
D.无法确定
5. 十进制数字2020转化为二进制数字为（ ）。
A.11111100100
B.11110110100
C.11111101100
D.11110100100
6. 班级中A、B、C、D四名同学参加百米竞赛，甲、乙、丙三位同学对比赛结果进行了预测，预测结果如下：
甲：C第一，B第二
乙：C第二，D第三
丙：A第二，D第四
比赛结果发现，甲、乙、丙三位同学各预测对了一半，试问比赛结果排名是（）。
A.ABCD
B.BCAD
C.CADB
D.CDAB
7. 设 a=true, b=false, c=false，以下逻辑运算表达式值为假的是（ ）。
A.(a∨c)∨b∧a
B.a∧(c∨b)∧c
C.(c∧b)∨a
D.(a∨b)∧(a∨c)
8. 后缀表达式的1 7 3 5 + * + 9 +计算结果为( )
A.38
B.66
C.72
D.80
9. 链表具有的特点是( )。
A.可随机访问任一元素
B.必须事先估计存储空间
C.插入删除不需要移动元素
D.所需空间与线性表长度成反比
10. 一棵结点数为4068 的二叉树最少有( )个叶子结点；二叉树的根节点高度为 1，一棵结点数为2048的二叉树最小的高度值是( )。
A.2020 11
B.1 11
C.1 12
D.2020 12
11. 将20个相同的苹果放进3个相同的盘子，每个盘子至少放一个苹果，共有( )种方法。
A.30
B.33
C.43
D.64
12. 一棵二叉树有10个叶子节点，则总节点数不可能是( )
A.18
B.31
C.32
D.2022
13. 5个男生，4个女生共9人站成一排，要求5个男生必须相邻。有多少种排法？
A.4! × 4！
B.5! × 5！
C.\(A_{9}^{5}\) × \(A_{4}^{4}\)
D.\(C_{9}^{5}\) × \(A_{4}^{4}\)
14. 一个序列的入栈顺序为abcdefg，请问下面四种出栈顺序中合法的有( )个.
1）abcdefg 2) gfedcba 3) cbdefag 4) efcdbag
A.1
B.2
C.3
D.4
15. 以下逻辑表达式的值恒为真的是( ).
A.P∨(¬P∧Q)∨(¬P∧¬Q)
B.Q∨(¬P∧Q)∨(P∧¬Q)
C.P∨Q∨(P∧¬Q)∨(¬P∧Q)
D.P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)
阅读程序1（13分）
输入是一个长度不超过1000的，只有大写字母构成的字符串。
判断题（正确的选T，错误的选F）：
1.输出的字符串由大写字母组成，并且所有相邻的字符最多只有一对ASCII码的奇偶性不同。（ ）
2.如果输入的字符串长度为n，那么程序的时间复杂度是O(n2)，而不是O(n)。 ( )
3.将程序的第10行和第11行的while中的l < r改为l <= r，则对于相同的输入，程序输出不会发生改变。（ ）
4.如果输入的字符串只由两种不同的字母组成，那么输出的字符串中所有相邻的字符最多只有一对字符不相同。（ ）
单选题：
5.如果输入是ABCDEF，那么程序输出（ ）。
A. AEDCFB
B. AECDFB
C. ACEDBF
D. AFCDEB
6.如果输入的字符串长度为n，那么程序中的swap操作最多执行（ ）次。
A. n/2
B. n/2 + 1
C. n – 1
D. n
阅读程序2（13.5分）
假设输入是只包含大小写字母以及 ‘#’ 的字符串 。
判断题：
1）程序的输入如果以 ‘#’ 开头，则输出可能是invalid input。（ ）
2）程序的输入如果不以 ‘#’ 开头，则输出长度至少为3。（ ）
3）若输入中的字母个数为 a (a ≠ 0)， ‘#’ 号的个数为 b ，输出中的字母个数为 a ，且输出不为 invalid input ，则b的最小值是a+1 。( )
单选题：
4）若输入为 ADa##E#G##CF### 时，输出为（ ）
A. ##A##D#aE###GCF
B. ##a###GED##F#CA
C. a#DE#G##A##FC##
D. invalid input
5）若输入为 ABC####ABC#### 时，输出为( )
A. AB##CA#BC
B. C##B##A##CB#A#
C. ##C#B#A
D. invalid input
6）如果输入是由A、B、C、D、E 各一个和6个’#’，共11个字符组成的字符串，并且A、B、C、D、E的相对顺序和字母顺序相同。则输出共有( )种可能。
A. 66
B. 65
C. 64
D. 63
阅读程序3（13.5分）
假设输入的n代表一张图中的顶点数(1<n≤100)，m代表边数(0<m≤200)，u和v描述了一条从u到v的有向边，最终查询以s为起点，以e为终点的所有简单路径(0<u,v,s,e<n,u≠v,s≠e)。
判断题：
(1)只要输出数据不为空，则输出的每一行至少包含两个数字。( )
(2)如果输出数据为空，说明输入数据描述的图不满足强连通。( )
(3)该程序的最坏时间复杂度为O(n×m)。( )
单选题：
(4)输入以下数据后，输出的数据为( )。
输入数据：
4 5
2 4
1 2
3 4
1 3
3 2
1 4
A.
1 2 4
1 3 4
1 3 2 4
B.
1 3 4
1 3 2 4
1 2 4
C.
1 2 4
1 3 2 4
1 3 4
D.
1 3 2 4
1 3 4
1 2 4
(5)当输入数据满足以下( )条件时，不论s和e如何改变，输出数据一定为一行。
A. m = n – 1，第i条边满足ui=i, vi=i+1
B. m = n，第i条边的u和v满足ui=i, vi=i+1，其中第m条边满足um=n,vm=1
C. m = n – 1，第i条边满足ui=i+1,vi<ui
D. m = n – 1，第i条边满足vi=i+1,ui<vi
(6)如果n=7，输出数据的行数最多为( )。
A. 5
B. 206
C. 326
D. 720
完善程序1（15分）
现有一个长度为n的数组a，我们把数组的相等性看成数组中相邻的相等数字的对数，即当1≤i≤n−1时，ai=ai+1 的数字对个数。现在对于数组a，我们可以进行以下操作：选择两个整数i和x（1≤i≤n−1，1≤x≤109），可以把ai和ai+1 设为x。求使得该数组的相等性小于等于1的最小操作数。
输入描述：
第一行一个整数n (2≤n≤2×105)，表示数组a的长度；第二行n个元素表示数组a里每个元素的值ai( 1≤ai≤109 )。
输出描述：最小需要的操作数。
输入样例：
5
2 1 1 1 2
输出样例：
1
①处应填（）
A. i < n
B. i + 1 < n
C. i + 1 <= n
D. i – 1 <= n
②处应填（）
A. if (maxv > i) maxv = i +1;
B. if (maxv > i) maxv = i;
C. if (maxv < i) maxv = i;
D. if (maxv < i) maxv = i +1;
③处应填（）
A. maxv == -1
B. maxv == n
C. maxv == 0
D. maxv = -1
④处应填（）
A. maxv – minv == 0
B. maxv – minv == 1
C. maxv – minv == 2
D. maxv – minv == -1
⑤处应填（）
A. maxv – minv
B. maxv – minv + 1
C. max(maxv, minv)
D. maxv – minv – 1
完善程序2:（15分）
一个数轴上，有n+1个传送点，位于数学公式: 0,a1,a2,a3,…,an 的位置。如果从传送点x到传送点y，需要消耗数学公式：(x-y)2 的能量，且x、y必须都是传送点。
问：若想从数轴数学公式: 0 点到数学公式：an 点，在现有n+1个传送点的前提下，若要消耗的总能量不超过m，最少需要再铺设几个传送点。（注意：传送点只能在整数点上）
输入描述：
第一行1个整数n(1≤n≤2×105)
第二行n个整数a1,a2,a3,…,an(1<a1<a2<a3<…<an≤109 )
第三行1个整数m( an≤m≤1018 )
输出描述： 输出一个整数，表示从0 点到an 点，在现有n+1个传送点的前提下，若要消耗的总能量不超过 m，最少需要再铺设传送点的个数。
输入样例：
2
1 5
7
输出样例：
2
①处应填：
A. f(d[i], mid-1) – f(d[i], mid)
B. f(d[i], mid) – f(d[i], mid+1)
C. f(d[i], mid+1) – f(d[i], mid+2)
D. f(d[i], mid)
②处应填：
A. ans
B. ans – 1
C. cnt + ans
D. cnt + ans – 1
③处应填：
A. f(d[i], ans)
B. f(d[i], ans-1)
C. sum + f(d[i], ans)
D. sum + f(d[i], ans-1)
④处应填：
A. r – l >= 0
B. r – l > 0
C. r – l > 1
D. r – l > 2
⑤处应填：
A. l
B. r
C. l + 1
D. r + 1