一、单选题
1、请选出以下最大的数( )
A (550)10
B (777)8
C 210
D (22F)16
2、操作系统的功能是()。
A 负责外设与主机之间的信息交换
B 控制和管理计算机系统的各种硬件和软件资源的使用
C 负责诊断机器的故障
D 将源程序编译成目标程序
3、现有一段8分钟的视频文件，它的播放速度是每秒24帧图像，每帧图像是 一幅分辨率为2048x1024像素的32位真彩色图像。请问要存储这段原始无 压缩视频.需要多大的存储空间？（）。
A 30G
B 90G
C 150G
D 450G
4、今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进 栈,进栈,出栈,进栈,进栈，出栈的操作，则此操作完成后,栈底元素为( ）
A b
B a
C d
D c
5、将(2, 7, 10, 18)分别存储到某个地址区间为如0~10的哈希表中，如果 哈希函数h（x）=(),将不会产生冲突，其中a mod b表示a除以b的 余数。
A x^2 mod 11
B 2x mod 11
C x mod 11
D 
6、下列哪些问题不能用贪心法精确求解？( )
A 霍夫曼编码问题
B 0-1背包问题
C 最小生成树问题
D 单源最短路径问题
7、具有n个顶点，e条边的图釆用邻接表存储结构，进行深度优先遍历运算的 时间复杂度为()
A 0(n+e)
B 0(n^2)
C 0(e^2)
D 0(n)
8、二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么,24个顶点的二分图至多有(）条边。
A 144
B 100
C 48
D 122
9、广度优先搜索时,一定需要用到的数据结构是（）
A 栈
B 二叉树
C 队列
D 哈希表
10、一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数n在以下哪个区间？己知n<60。（）
A 30<n<40
B 40<n<50
C 50<n<60
D 20<n<30
11、小明想通过走楼梯来锻炼身体，假没从第1层走到第2层消耗10卡热量，接着从第2层走到第3层消耗20卡热量，再从第3层走到第4层消耗30 卡热量，依此类推，从第k层走到第k+1层消耗10K卡热量(k>l)。如果小 明想从1层开始，通过连续向上爬楼梯消耗1000卡热量，至少要爬到第几 层楼？ ( )
A 14
B 16
C 15
D 13
12、表达式a*(b+c)-d的后缀表达形式为( )
A abc*+d-
B -+*abcd
C abcd*+-
D abc+*d-
13、从一个4X4的棋盘中选取不在同一行也不在同一列上的两个方格，共有 ()种方法。
A 60
B 72
C 86
D 64
14、对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为()。
A 0((m + n^2) log n)
B 0(mn + n^3)
C 0((m + n) log n)
D 0(n^2)
15、1948年，()将热力学中的熵引入信息通信领域，标志着信息论研究的 开端。
A 欧拉(Leonhard Euler)
B 冯•诺伊曼(John von Neumann)
C 克劳徳•香农(Claude Shannon)
D 图灵(Alan Turing)
二、判断题
假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
16、n必须小于1000,否则程序可能会发生运行错误。()
A 正确
B 错误
假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
17、输出一定大于等于0。()
A 正确
B 错误
假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
18、若将第13行的“j =0”改为“j = i +1” 程序输出可能会改变。（）
A 正确
B 错误
假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
19、将第14行的“d[i] < d[j]"改为wd[i] != d[j]”，程序输出不会改 变。()
A 正确
B 错误
三、单选题
假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
20、若输入n 100.且输出为127.则输入的d[i]中不可能有()。
A 127
B 126
C 128
D 125
假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
21、若输出的数大于0,则下面说法正确的是()。
A 若输出为偶数，则输入的d[i]，中最多有两个偶数
B 若输出为奇数，则输入的d[i]中至少有两个奇数
C 若输出为偶数，则输入的d [ i ]中至少有两个偶数
D 若输出为奇数，则输入的d[i]中最多有两个奇数
四、判断题
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
22、第9行的“x”的数值范围是L+1到R.即[L+l, R]。()
A 正确
B 错误
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
23、将第19行的“d[a]”改为“d[b]“，程序不会发生运行错误。（）
A 正确
B 错误
五、简答题
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
24、(2.5分)当输入的d[i]是严格单调递增序列时，第17行的 “swap”平均执行次数是()。
参考答案：由于输入的d[i]是严格单调递增序列，因此在进行插入排序时，每次插入新元素时，该元素都会直接插入到正确的位置，无需进行任何交换操作。因此，第17行的“swap”语句平均执行次数为0次。
六、单选题
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
25、(2.5分)当输入的d[i]是严格单调递减序列时，第17行的“swap” 平均执行次数是()。
A 0(n^2)
B 0(n)
C 0(n log n)
D 0(log n)
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
26、(2.5分)若输入的d[i]为i,此程序①平均的时间复杂度和②最坏 情况下的时间复杂度分别是()
A 0(n), 0(n^2)
B 0(n), 0(n log n)
C 0(n log n), 0(n^2)
D 0(n log n), 0(n log n)
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
27、(2.5分)若输入的d[i]都为同一个数，此程序平均的时间复杂度是（）
A 0（n）
B 0(log n)
C 0(n log n)
D 0(n^2)
七、判断题
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
28、输出可能为0 （）
A 正确
B 错误
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
29、若输入的两个字符串长度均为101时，则m=0时的输出, m=10O时的 输出是一样的。（）
A 正确
B 错误
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
30、若两个字符串的长度均为n,则最坏情况下，此程序的时间复杂度为 0（n!）。 （）
A 正确
B 错误
八、单选题
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
31、（2.5分）若输入的第一个字符串长度由100个不同的字符构成，第二 个字符串是第一个字符串的倒序，输入的m为0，则输岀为（）。
A 49
B 50
C 100
D -1
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
32、（4分）已知当输入为“0123\n3210\n1”时输出为4,当输入为 “012345\n543210\n1”时输出为14,当输入为 “01234567\n76543210\n1”时输出为28,则当输入为 “0123456789ab\nba9876543210\n1” 输出为（）。其中“\n”为换行符。
A 56
B 84
C 102
D 68
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
33、（4分）若两个字符串的长度均为n, 且0<m<n-1,且两个字符串的构 成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列 说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不 一样。
A 若n、m均为奇数，则输出可能小于0
B 若n、m均为偶数，则输出可能小于 0
C 若n为奇数、m为偶数，则输出可能小于0
D 若n为偶数、m为奇敎.则输出可能小于0
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
34、①处应填()
A W[j] / v[j] < w[j+1]/v[j+1]
B W[j] / v[j]> w[j+1]/v[j+1]
C v[j] * w[j+1]< v[j+1]*w[j]
D w[j] * v[j+1]< w[j+1]*v[j]
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
35、②处应填（）
A w[1] <= B
B v[1] <= B
C w[1] >= B
D v[1] >= B
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
36、③处应填()
A print(v[1]w[1]); return 0;
B curV = 0; curW = 0;
C print(w[1] v[1]); return 0;
D curV = v[1]; curW = w[1];
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
37、④处应填（）
A curW * v[i] + curV * w[i], v[i]
B (curW - w[i]) * v[i] + (B - curV) * w[i], v[i]
C curW + v[i], w[i]
D curW * v[i] * (B - curV) * w[i], v[i]
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
38、⑤处应填（）
A curW, curV
B curW，1
C curV, curW
D curV，1
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前
位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
39、①处应填（）
A X >>= 1
B X ^=X & (x ^ (x + 1))
C X -= X | -X
D X ^= X & (X ^ (x - 1))
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
40、②处应填（）
A (a & MS) « B
B a>>B
C a&(1<<B)
D a&(MS<<B)
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
41、③处应填（）
A -INF
B Max[y] [x]
C 0
D Max[x][yJ
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
42、④处应填（）
A Max[x] [z]+w（y^z）
B Max[x][z] + w(a ^ z)
C Max[x] [z]+w（x^(z<<B）)
D Max[x][z] + w(x ^ z)
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
43、⑤处应填()
A to_max(Max[y][z],v + w(a ^(z << B)))
B to_max(Max[z][y],v + w((x ^ z) << B))
C to_max(Max[zJ[y],v + w(a ^ (z << B)))
D to_max(Max[x][z],v + w(y ^ z))
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
