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.二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行按位或运算的结果是（ ）。（编者注：原题为“逻辑或”，但是根据题意应当是按位或。）
A. 11 1111 1101 1111
B. 11 1111 1111 1101
C. 10 1111 1111 1111
D. 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.由数字 所组成的不同的 位数的个数是（ ）。
A. 104
B. 102
C. 98
D. 100
7.排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。
A. 冒泡排序
B. 直接插入排序
C. 快速排序
D. 归并排序
8. 是一个非连通无向图（没有重边和自环），共有 条边，则该图至少有（ ）个顶点。
A. 10
B. 9
C. 11
D. 8
9.一些数字可以颠倒过来看，例如 颠倒过来还是本身， 颠倒过来是 ， 颠倒过来看还是 ，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 颠倒过来是 。假设某个城市的车牌只有 位数字，每一位都可以取 到 。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 位数能被 整除？（ ）
A. 40
B. 25
C. 30
D. 20
10.一次期末考试，某班有 人数学得满分，有 人语文得满分，并且有 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（ ）
A. 23
B. 21
C. 20
D. 22
11.设 和 是两个长为 的有序数组，现在需要将 和 合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（ ）
A.
B.
C.
D.
12.以下哪个结构可以用来存储图（ ）。
A. 栈
B. 二叉树
C. 队列
D. 邻接矩阵
13.以下哪些算法不属于贪心算法？（ ）
A. Dijkstra 算法
B. Floyd 算法
C. Prim 算法
D. Kruskal 算法
14.有一个等比数列，共有奇数项，其中第一项和最后一项分别是 和 ，中间一项是 ，请问以下哪个数是可能的公比？（ ）
A. 5
B. 3
C. 4
D. 2
15.正实数构成的数字三角形排列形式如图所示。第一行的数为 ；第二行的数从左到右依次为 ，第 行的数为 。从 开始，每一行的数 只有两条边可以分别通向下一行的两个数 和 。用动态规划算法找出一条从 向下通到 中某个数的路径，使得该路径上的数之和最大。令 是从 到 的路径上的数的最大和，并且 ，则 。
A.
B.
C.
D.
#include <cstdio>
using namespace std;
int n;
int a[100];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int ans = 1;
for (int i = 1; i <= n; ++i) {
if (i > 1 && a[i] < a[i - 1])
ans = i;
while (ans < n && a[i] >= a[ans + 1])
++ans;
printf("%d\n", ans);
}
return 0;
}
判断题
16.（1分）第 16 行输出 ans 时，ans 的值一定大于 i。（ ）
A. 正确
B. 错误
17.（1分）程序输出的 ans 小于等于 n。（ ）
A. 正确
B. 错误
18.若将第 12 行的 < 改为 !=，程序输出的结果不会改变。（ ）
A. 正确
B. 错误
19.当程序执行到第 16 行时，若 ans - i > 2，则 。（ ）
A. 正确
B. 错误
选择题
20.（3分）若输入的 a 数组是一个严格单调递增的数列，此程序的时间复杂度为（ ）。
A.
B.
C.
D.
21.最坏情况下，此程序的时间复杂度是（ ）。
A.
B.
C.
D.
#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];
int getRoot(int v) {
if (fa[v] == v) return v;
return getRoot(fa[v]);
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
fa[i] = i;
cnt[i] = 1;
}
int ans = 0;
for (int i = 0; i < n - 1; ++i) {
int a, b, x, y;
cin >> a >> b;
x = getRoot(a);
y = getRoot(b);
ans += cnt[x] * cnt[y];
fa[x] = y;
cnt[y] += cnt[x];
}
cout << ans << endl;
return 0;
}
判断题
22.（1分）输入的 a 和 b 值应在 的范围内。（ ）
A. 正确
B. 错误
23.（1分）第 16 行改成 fa[i] = 0;，不影响程序运行结果。（ ）
A. 正确
B. 错误
24.若输入的 a 和 b 值均在 的范围内，则对于任意 都有 。（ ）
A. 正确
B. 错误
25.若输入的 a 和 b 值均在 的范围内，则对于任意 都有 。（ ）
A. 正确
B. 错误
选择题
26.当 等于 50 时，若 的值都在 的范围内，且在第 25 行时 总是不等于 ，那么输出为（ ）。
A. 1276
B. 1176
C. 1225
D. 1250
27.此程序的时间复杂度是（ ）。
A.
B.
C.
D.
提示： 是 的子序列的意思是：从 中删去若干个字符，可以得到 ；特别的，如果 ，那么 也是 的子序列；空串是任何串的子序列。例如：acd 是 abcde 的子序列，acd 是 acd 的子序列，但 adc 不是 abcde 的子序列。 表示 共 个字符构成的字符串，若 则 是空串。 同理。
#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
int main() {
cin >> s >> t;
int slen = s.length(), tlen = t.length();
for (int i = 0, j = 0; i < slen; ++i) {
if (j < tlen && s[i] == t[j]) ++j;
pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
}
for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
if (j >= 0 && s[i] == t[j]) --j;
suf[i] = j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
}
suf[slen] = tlen - 1;
int ans = 0;
for (int i = 0, j = 0, tmp = 0; i <= slen; ++i) {
while (j <= slen && tmp >= suf[j] + 1) ++j;
ans = max(ans, j - i - 1);
tmp = pre[i];
}
cout << ans << endl;
return 0;
}
附加提示： 是 的子序列； 是 的子序列。
判断题
28.（1分）程序输出时，suf 数组满足：对任意 ，。（ ）
A. 正确
B. 错误
29.（2分）当 是 的子序列时，输出一定不为 。（ ）
A. 正确
B. 错误
30.（2分）程序运行到第 23 行时，j - i - 1 一定不小于 。（ ）
A. 正确
B. 错误
31.（2分）当 是 的子序列时，pre 数组和 suf 数组满足：对任意 ，。（ ）
A. 正确
B. 错误
选择题
32.若 tlen=10，输出为 ，则 slen 最小为（ ）。
A. 10
B. 12
C. 0
D. 1
33.若 tlen=10，输出为 ，则 slen 最小为（ ）。
A. 0
B. 10
C. 12
D. 1
一个匠人决定要学习 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数 ，以及已有经验值（）。接下来 行。第 行的两个正整数，分别表示学习第 个技术所需的最低经验值（），以及学会第 个技术后可获得的经验值（）。接下来 行。第 行的第一个数 ()，表示第 个技术的相关技术数量。紧跟着 个两两不同的数，表示第 个技术的相关技术编号。输出最多能学会的新技术个数。下面的程序以 的时间复杂度完成这个问题。
#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child[maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
bool find(){
int target = -1;
for (int i = 1; i <= n; ++i)
if(① && ②){
target = i;
break;
}
if(target == -1)
return false;
unlock[target] = -1;
③
for (int i = 0; i < cnt[target]; ++i)
④
return true;
}
int main(){
scanf("%d%d", &n, &points);
for (int i = 1; i <= n; ++i){
cnt[i] = 0;
scanf("%d%d", &threshold[i], &bonus[i]);
}
for (int i = 1; i <= n; ++i){
int m;
scanf("%d", &m);
⑤
for (int j = 0; j < m; ++j){
int fa;
scanf("%d", &fa);
child[fa][cnt[fa]] = i;
++cnt[fa];
}
}
int ans = 0;
while(find())
++ans;
printf("%d\n", ans);
return 0;
}
34.① 处应填（ ）
A. unlock[i] <= 0
B. unlock[i] >= 0
C. unlock[i] == 0
D. unlock[i] == -1
35.② 处应填（ ）
A. threshold[i] > points
B. threshold[i] >= points
C. points > threshold[i]
D. points >= threshold[i]
36.③ 处应填（ ）
A. target = -1
B. --cnt[target]
C. bonus[target] = 0
D. points += bonus[target]
37.④ 处应填（ ）
A. cnt[child[target][i]] -= 1
B. cnt[child[target][i]] = 0
C. unlock[child[target][i]] -= 1
D. unlock[child[target][i]] = 0
38.⑤ 处应填（ ）
A. unlock[i] = cnt[i]
B. unlock[i] = m
C. unlock[i] = 0
D. unlock[i] = -1
Alice 和 Bob 两个人在玩取石子游戏。他们制定了 条取石子的规则，第 条规则为：如果剩余石子的个数大于等于 且大于等于 ，那么他们可以取走 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 ，以及石子个数 。接下来 行。第 行有两个正整数 和 。()。如果先取石子的人必胜，那么输出 Win，否则输出 Loss。
提示：可以使用动态规划解决这个问题。由于 不超过 ，所以可以使用 位无符号整数去压缩必要的状态。status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。代码说明：~ 表示二进制补码运算符，它将每个二进制位的 变为 、 变为 ；而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 ，反之为 。ull 标识符表示它前面的数字是 unsigned long long 类型。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 64;
int n, m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win;
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i], &b[i]);
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j)
if (a[i] > a[j]){
swap(a[i], a[j]);
swap(b[i], b[j]);
}
status = ①;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i){
while (j < n && ②){
③;
++j;
}
win = ④;
⑤;
}
puts(win ? "Win" : "Loss");
return 0;
}
39.① 处应填（ ）
A. 0
B. ~0ull
C. ~0ull ^ 1
D. 1
40.② 处应填（ ）
A. a[j] < i
B. a[j] == i
C. a[j] != i
D. a[j] > 1
41.③ 处应填（ ）
A. trans |= 1ull << (b[j] - 1)
B. status |= 1ull << (b[j] - 1)
C. status += 1ull << (b[j] - 1)
D. trans += 1ull << (b[j] - 1)
42.④ 处应填（ ）
A. ~status | trans
B. status & trans
C. status | trans
D. ~status & trans
43.⑤ 处应填（ ）
A. trans = status | trans ^ win
B. status = trans >> 1 ^ win
C. trans = status ^ trans | win
D. status = status << 1 ^ win