考生注意事项：
1 满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。
2 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
1、 计算机的五大基本组成部分是什么？( ).
A 输入设备、输出设备、控制器、运算器、存储器
B 处理器、硬盘、内存、网络接口、显卡
C 电源、风扇、机箱、屏幕、键盘
D 操作系统、应用软件、语言编译器、数据库、安全软件
2、 以下关于switch说法不正确的是：( ).
A switch语句中的default语句可以放在任意位置
B switch语句中case后的表达式只能是常量表达式
C switch语句中case语句必须在default语句之前
D switch语句中case表达式不要求顺序
3、 程序运行后输出的结果是( ).
A 36
B 45
C 55
D 66
4、 某进制数: 347r =32134 , 则 r = ( ).
A 4
B 8
C 12
D 16
5、 关于位运算，下列不正确的是( ).
A x | (1 << n-1)，该运算可以将 x 的第 n 位设置为 1
B x & ~(1 << n-1)，该运算可以将 x 的第 n 位设置为1
C x ^ (1 << j-1)，该运算可以将 x 的第 j 位取反
D a ^= b ^= a ^= b，该运算可以交换a和b的值
6、 参加合唱的5名同学已经排好顺序，老师决定临时增加2名同学一同合唱。要将这2名同学插到队伍中，但二者不能相邻，那么有多少种不同的插法？
A 12
B 30
C 15
D 25
7、 5个人围着圆桌坐下，共有多少种坐法？
A 72
B 48
C 24
D 120
8、 已知二叉树的中序遍历序列为ACBDEFHGI，后序遍历序列为ACDBHIGFE。那么前序遍历序列为？
A BCADFGHIE
B ABCDEFGHI
C EBDCAFGHI
D EBCADFGHI
9、 一棵 n 层的满二叉树，总结点的数量和叶子结点数量之差是多少？
A 2n-1 – 2n – 1
B 2n-1 – 2n + 1
C 2n – 1 – 2n-1
D 2n – 1 – 2n-2
10、 现有2个空栈A、B，存在5个互不相同的元素s1、s2、s3、s4、s5，每个元素分别按照进栈A、出栈A、进栈B、出栈B的顺序操作，进入栈A的先后顺序为s1、s2、s3、s4、s5。那么51342、53421、12345、34521这4种出栈B的元素编号顺序有几个是可行的？
A 1
B 2
C 3
D 4
11、 以下代码在输入2 8时的结果是？
A 4
B 5
C 7
D 6
12、 以下代码在输入3时的结果是？
A 1
B 5
C 3
D 35
13、 期末考试结束要对班级里的同学分别按照总分从大到小排序，若总分数相同，按照数学成绩从大到小排序，如果总分与数学成绩都相同，则按照名字字典序从小到大排序，排版成绩单。使用sort函数进行排序，以下能够排版正确的cmp函数是？
struct stu{
int sum; //总分
int math; //数学成绩
string name; //名字
};
14、 对于数列{2, 16, 34(1), 71, 39, 34(2), 66, 77, 24}排序后，结果为{2, 16, 24, 34(2), 34(1), 39, 66, 71, 77}。以下说法正确的是？
A 使用的排序算法是稳定排序
B 使用的排序算法是不稳定排序
C 使用冒泡排序可以做到
D 以上都不对
15、 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历的是？
A bacdfe
B abfcde
C bafced
D facbed
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填T，错误填F；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
阅读程序1：对于输入的数据，1≤n≤64， 0≤k<2n 。
完成下面的判断题和单选题：
判断题：
1）第9行，把pow(2, n – 1)改为1 << (n – 1) 程序运行结果不变。（ ）
2）第15行和第24行，k-=len 改为 k^=len程序运行结果不变。（ ）
3）若n = 4, k = 15 和 n = 5, k = 15, 如果输出数据最高位补0对齐，除了最高位不同，其余位相同。（ ）
4）若n = 4, k = 15 和 n = 5, k = 16, 如果输出数据最高位补0对齐，除了最高位不同，其余位相同。（ ）
单选题：
5）当n,k为正确输入，输出结果为 11001011 时， k 的二进制 为（ ）
A. 11111011
B. 11000111
C. 10001101
D. 10101011
6）输出结果 110110111， 问 k 是（ ）
A. 292
B. 293
C. 294
D. 295
阅读程序2：输入的字符串s是一个合法的圆括号匹配序列，长度不超过2000。
判断题：
1）第29行的if语句只可能得到true。
2）如果s的长度是2n，那么输出的第二行一定是1到n的自然数，按照从小到大的顺序输出。
单选题：
3）如果输入()()(()())，那么输出的第一行是：
A. 13
B. 14
C. 15
D. 16
4）如果输入s的长度是20，那么输出的第一行的最大值是：
A. 45
B. 55
C. 66
D. 78
5）如果s的长度为100，并且s有且仅有两个子串是”()”，那么输出的第一行的最小值是：
A. 699
B. 701
C. 703
D. 705
6）如果输出的第三行是4 5 3 6 2 7 1，那么输出的第一行可能是：
A. 17
B. 18
C. 19
D. 20
阅读程序3：输入的 n≤1000，(a,b) 代表一条边，输入保证所有的边会组成一棵树。
判断题：
1）每次调用bfs()函数时，其返回值一定不会超过 n−1。
2）把代码中的emplace_back 替换成 push_back，代码的输出不会改变。
单选题：
3）如果n=100，那么输出的所有数的总和的最大值是：
A. 2475
B. 2525
C. 4925
D. 7450
4）如果n=100，那么输出的所有数的总和的最小值是：
A. 99
B. 100
C. 199
D. 200
5）如果n=1000，输入的所有(a,b) 都满足b / 2 == a，那么输出的所有数中出现次数最多的是：
A. 17
B. 18
C. 19
D. 20
6）如果输出的数中最大值是255，那么输出的数中最小值的最小值是：
A. 31
B. 32
C. 127
D. 128
三、完善程序（单选题，每小题 3 分，共计 30 分）
完善程序1：输入两个只包含小写字符的字符串a, b，每次操作只能改变1个字母，请输出最少需要操作多少次可以使得两个字符串满足下列三个条件之一。
1、字符串a中的字符均小于字符串b中的字符；
2、字符串a中的字符均大于字符串b中的字符；
3、两个字符串变成同一个字母。
①处应填
A. a[i] – ‘a’
B. (int)a[i]
C. a[i]
D. a[i] – ‘A’
②处应填
A. ca
B. ca + cb
C. cb
D. abs(ca – cb)
③处应填
A. c1[i] == 0
B. i == 25
C. i == 0
D. c2[i] == 0
④处应填
A. r1 += c1[j]
B. r1 += c2[j]
C. r2 += c1[j]
D. r2 += c2[j]
⑤处应填
A. max(ans, min(r1, r2))
B. min(ans, max(r1, r2))
C. min(ans, min(r1, r2))
D. min(r1, r2)
阅读程序2：小栗最近玩了一个特殊的消消乐游戏，给定n个数字，c1],c[2] … c[n]，如果其中的子串是回文的，那么小栗可以用1次机会销毁这个子串。请问小栗最少需要多少次才能销毁所有的数字。
注意：1.消完一次后剩下的数字会自动向开头补过来。2.回文的定义是正过来倒过来都一样。
输入：
第一行，一个正整数n。（1 <= n <= 500）
第二行，n个正整数，依次为c[1], c[2]…c[n]。(1<=c[i]<=n)
输出：
一个正整数，表示最少的次数。
样例1输入：
3
1 2 3
样例1输出：
3
样例2输入：
7
1 4 4 2 3 2 1
样例2输出：
2
样例解释：先消4 4，再消1 2 3 2 1，因此共2次。
①处应填
A. n
B. len
C. l + len – 1
D. l + len
②处应填
A. 1
B. 2
C. f[l+1 ][r]
D. f[l + 1][r – 1]
③处应填
A. 1
B. 2
C. i == 0
D. c2[i] == 0
④处应填
A. 1
B. 2
C. f[l+1 ][r]
D. f[l + 1][r – 1]
⑤处应填
A. f[l+1][k] + f[k + 1][r]
B. f[l+1][k-1] + f[k][r]
C. f[l][k] + f[k + 1][r]
D. f[l][k-1] + f[k][r]