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