一、单选题（共15题，每题2分，共计30分；每题有且只有一个正确选项。）

1. 若有定义：int a=7; float x=2.5, y=4.7，则表达式 x+a%3*(int) (x+y)%2 的值是：（）

A. 0.000000 B. 2.750000 C. 2.500000 D. 3.500000

2. 下列属于图像文件格式的有（）

A. WMV B. MPEG C. JPEG D. AVI

3. 二进制数 $\text{11 1011 1001 0111}$ 和 $\text{01 0110 1110 1011}$ 进行逻辑或运算的结果是（）。

A. $\text{11 1111 1101 1111}$ B. $\text{11 1111 1111 1101}$ C. $\text{10 1111 1111 1111}$ D. $\text{11 1111 1111 1111}$

4. 编译器的功能是（）

A. 将源程序重新组合 B. 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言） C. 将低级语言翻译成高级语言 D. 将一种编程语言翻译成自然语言

5. 设变量 $x$ 为 float 型且已赋值，则以下语句中能将 $x$ 中的数值保留到小数点后两位，并将第三位四舍五入的是（）

A. x= (x*100+0. 5)/100.0; B. x=(int) (x*100+0. 5)/100.0; C. x=(x/100+0. 5）*100.0; D. x=x*100+0. 5/100. 0;

6. 由数字 $1, 1, 2, 4, 8, 8$ 所组成的不同的 $4$ 位数的个数是（）。

A. 104 B. 102 C. 98 D. 100

7. 排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 归并排序

8. $G$ 是一个非连通无向图（没有重边和自环），共有 $28$ 条边，则该图至少有 （）个顶点。

A. 10 B. 9 C. 11 D. 8

9. 一些数字可以颠倒过来看，例如 $0,1,8$ 颠倒过来还是本身，$6$ 颠倒过来是 $9$,$9$ 颠倒过来看还是 $6$,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 $106$ 颠倒过来是 $901$。假设某个城市的车牌只有 $5$ 位数字，每一位都可以取 $0$ 到 $9$。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 $5$ 位数能被 $3$ 整除？（）

A. 40 B. 25 C. 30 D. 20

10. —次期末考试，某班有 $15$ 人数学得满分，有 $12$ 人语文得满分，并且有 $4$ 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。

A. 23 B. 21 C. 20 D. 22

11. 设 $A$ 和 $B$ 是两个长为 $n$ 的有序数组，现在需要将 $A$ 和 $B$ 合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。

A. $n^2$ B. $n \log n$ C. $2n$ D. $2n - 1$

12. 以下哪个结构可以用来存储图（）

A. 栈 B. 二叉树 C. 队列 D. 邻接矩阵

13. 以下哪些算法不属于贪心算法？（）

A. Dijkstra 算法 B. Floyd 算法 C. Prim 算法 D. Kruskal 算法

14. 有一个等比数列，共有奇数项，其中第一项和最后一项分别是 $2$ 和 $118098$，中间一项是 $486$,请问以下哪个数是可能的公比？（）

A. 5 B. 3 C. 4 D. 2

A. A B. B C. C D. D

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 1.5 分，选择题 4分，共计 40 分） 1. 判断题 1）（1 分）第 16 行输出 $ans$ 时，$ans$ 的值一定大于 $i$。（）

A. 正确 B. 错误

2）（1 分）程序输出的 $ans$ 小于等于 $n$。（）

A. 正确 B. 错误

3）若将第 12 行的 < 改为 !=，程序输出的结果不会改变。（）

A. 正确 B. 错误

4）当程序执行到第 16 行时，若 $ans - i> 2$，则 $a[i + 1] \leq a[i]$。 （）

A. 正确 B. 错误

选择题

5）（3 分）若输入的 $a$ 数组是一个严格单调递增的数列, 此程序的时间复杂度（）

A. $O(\log n)$ B. $O(n^2)$ C. $O(n\log n)$ D. $O(n)$

6）最坏情况下，此程序的时间复杂度是（）。

A. $O(n^2)$ B. $O(\log n)$ C. $O(n)$ D. $O(n\log n)$

判断题

1）（1 分）输入的 $a$ 和 $b$ 值应在 $[0, n-1]$的范围内。（）

A. 正确 B. 错误

2）（1 分）第 16 行改成 fa[i] = 0;，不影响程序运行结果。（）

A. 正确 B. 错误

3）若输入的 $a$ 和 $b$ 值均在 $[0, n-1]$ 的范围内，则对于任意 $0\leq i<n$ 都有 $0 \leq fa[i] <n$ （）

A. 正确 B. 错误

4）若输入的 $a$ 和 $b$ 值均在 $[0, n-1]$ 的范围内，则对于任意 $0\leq i<n$ 都有 $1 \leq cnt[i]\leq n$ （）

A. 正确 B. 错误

选择题

5）当 $n$ 等于$50$时，若 $a,b$ 的值都在 $[0,49]$ 的范围内，且在第 $25$ 行时 $x$ 总是不等于 $y$，那么输出为（）。

A. $1276$ B. $1176$ C. $1225$ D. $1250$

6）此程序的时间复杂度是（）。

A. $O(n)$ B. $O(\log n)$ C. $O(n^2)$ D. $O(n\log n)$

判断题

1）（1分）程序输出时，suf 数组满足：对任意 $0 \leq i < slen, suf[i] \leq suf[i + 1]$。 （）

A. 正确 B. 错误

2）（2分）当 $t$ 是 $s$ 的子序列时，输出一定不为 $0$。（）

A. 正确 B. 错误

3）（2分）程序运行到第 $23$ 行时，$j - i - 1$ 一定不小于 $0$。（）

A. 正确 B. 错误

4）（2分）当 $t$ 是 $s$ 的子序列时，pre 数组和 suf 数组满足：对任意 $0 \leq i < slen, pre[i] > suf[i + 1] + 1$。 （）

A. 正确 B. 错误

选择题

5）若 tlen=10，输出为 $0$，则 slen 最小为（）。

A. 10 B. 12 C. 0 D. 1

6）若 tlen=10，输出为 $2$，则 slen 最小为（）。

A. 0 B. 10 C. 12 D. 1

三、完善程序（单选题，每小题 33 分，共计 3030 分）

1. （匠人的自我修养） 一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $n(l\leq n\leq 10^3)$,以及己有经验值$（\le10^7）$。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值$（\le10^7）$,以及学会第i个技术后可获得的经验值$（\leq 10^7)$

接下来 $n$ 行。第 $i$ 行的第一个数 $m_i$ $（0\le m_i<n）$，表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号。

输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$的时间复杂度完成这个问题，试补全程序。  

①处应填（）

A. unlock[i] <= 0 B. unlock[i] >= 0 C. unlock[i] == 0 D. unlock[i] == -1

②处应填（）

A. threshold[i] > points B. threshold[i] >= points C. points > threshold[i] D. points >= threshold[i]

③处应填（）

A. target = -1 B. --cnt[target] C. bonus[target] = 0 D. points += bonus[target]

④处应填（）

A. cnt[child[target][i]] -= 1 B. cnt[child[target][i]] = 0 C. unlock[child[target][i]] -= 1 D. unlock[child[target][i]] = 0

⑤处应填（）

A. unlock[i] = cnt[i] B. unlock[i] = m C. unlock[i] = 0 D. unlock[i] = -1

2. （取石子） Alice 和 Bob 两个人在玩取石子游戏。他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余石子的个数大于等于 $a[i]$ 且大于等于 $b[i]$，那么他们可以取走 $b[i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $n(l<n<64)$, 以及石子个数 $m( \le 10^7)$。

接下来 $n$ 行。第 $i$ 行有两个正整数 $a[i]$ 和 $b[i]$。$(l \le a[i] \le 10^7,l \le b[i] \le 64)$。

如果先取石子的人必胜，那么输出 $\texttt{Win}$，否则输出 $\texttt{Loss}$。

提示：

可以使用动态规划解决这个问题。由于 $b[i]$ 不超过 $64$ ,所以可以使用 $64$ 位无符号整数去压缩必要的状态。

status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

试补全程序。

代码说明：

~ 表示二进制补码运算符，它将每个二进制位的 $0$ 变为 $1$、$1$ 变为 $0$;

而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ,反之为 $1$。

ull 标识符表示它前面的数字是 unsigned long long 类型。

①处应填（ )

A. 0 B. ~0ull C. ~0ull^1 D. 1

②处应填（ )

A. a[j] < i B. a[j] == i C. a[j] !=i D. a[j]>1

③处应填（ )

A. trans |=1ull << (b[j] - 1) B. status |=1ull << (b[j] - 1) C. status +=1ull << (b[j] - 1) D. trans +=1ull << (b[j] - 1)

④处应填（ )

A. ~status| trans B. status & trans C. status | trans D. ~status & trans

⑤处应填（ )

A. trans =status | trans ^ win B. status = trans >> 1 ^ win C. trans =status ^ trans | win D. status = status << 1 ^ win

参考答案(请提交答案后再看)： 参考答案