CSP 2020 提高组第一轮

第 1 题
请选出以下最大的数（）。
A.(550)^10?
B.(777)^8?
C.2^10
D.(22F)^16?
正确答案： C
本题共 2 分

第 2 题
操作系统的功能是（）
A.负责外设与主机之间的信息交换
B.控制和管理计算机系统的各种硬件和软件资源的使用
C.负责诊断机器的故障
D.将源程序编译成目标程序
正确答案： B
本题共 2 分

第 3 题
现有一段 8 分钟的视频文件，它的播放速度是每秒 24 帧图像，每帧图像是一幅分辨率为 2048×1024像素的 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（）。
A.30G
B.90G
C.150G
D.450G
正确答案： B
本题共 2 分

第 4 题
今有一空栈 S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（）。
A.b
B.a
C.d
D.c
正确答案： B
本题共 2 分

第 5 题
将(2, 7, 10, 18)分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数h(x)=（），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。
A.x^2 bmod{11}x2mod11
B.2x bmod{11}2xmod11
C.x bmod{11}xmod11
D.lfloor x/2 rfloor bmod{11}?x/2?mod11，其中lfloor x/2 rfloor?x/2?表示x/2下取整
正确答案： D
本题共 2 分

第 6 题
下列哪些问题不能用贪心法精确求解？（）
A.霍夫曼编码问题
B.0-1背包问题
C.最小生成树问题
D.单源最短路径问题
正确答案： B
本题共 2 分

第 7 题
具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（）。
A.O(n+e)O(n+e)
B.O(n^2)O(n2)
C.O(e^2)O(e2)
D.O(n)O(n)
正确答案： A
本题共 2 分

第 8 题
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（）条边。
A.144
B.100
C.48
D.122
正确答案： B
本题共 2 分

第 9 题
广度优先搜索时，一定需要用到的数据结构是( )
A.栈
B.二叉树
C.队列
D.哈希表
正确答案： C
本题共 2 分

第 10 题
—个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 n 在以下哪个区间？已知 n<60。( ）
A.30<n<40
B.40<n<50
C.50<n<60
D.20<n<30
正确答案： C
本题共 2 分

第 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
正确答案： C
本题共 2 分

第 12 题
表达式 a*(b+c)-d 的后缀表达形式为（）。
A.abc*+d-
B.-+*abcd
C.abcd*+-
D.abc+*d-
正确答案： D
本题共 2 分

第 13 题
从一个 4 × 4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（）种方法。
A.60
B.72
C.86
D.64
正确答案： B
本题共 2 分

第 14 题
对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（）。
A.O((m + n^2) log n)O((m+n2)logn)
B.O(mn + n^3)O(mn+n3)
C.O((m + n) log n)O((m+n)logn)
D.O(n^2)O(n2)
正确答案： D
本题共 2 分

第 15 题
1948年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A.欧拉(Leonhard Euler)
B.冯·诺伊曼(John von Neumann)
C.克劳德·香农(Claude Shannon)
D.图灵(Alan Turing)
正确答案： C
本题共 2 分

第 16 题
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

#include <iostream>

using namespace std;

int n;

int d[1000];

int main() {

cin >> n;

for (int i = 0; i < n; ++i)

cin >> d[i];

int ans = -1;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

if (d[i] < d[j])

ans = max(ans, d[i] + d[j] - (d[i] & d[j]));

cout << ans;

return 0;

}

假设输入的 n 和 d[i] 都是不超过 10000 的正整数，完成下面的判断题和单选题：

·判断题
1） n 必须小于 1000,否则程序可能会发生运行错误。（）
2）输出一定大于等于 0。（）
3）若将第 13 行的“j=0” 改为 “j = i + 程序输出可能会改变。（）
4）将第 14 行的 “d[i] < d[j]” 改为“d[i] != d[j]”，程序输出不会改变。（）
·单选题
5）若输入 n 为 100，且输出为 127，则输入的 d[i] 中不可能有（）。
6）若输出的数大于 0，则下面说法正确的是( ）。

1.? A.正确? B.错误? 正确答案： B
2.? A.正确? B.错误? 正确答案： B
3.? A.正确? B.错误? 正确答案： A
4.? A.正确? B.错误? 正确答案： A
5.
A.127
B.126
C.128
D.125
正确答案： C
6.
A.若输出为偶数，则输入的d[i]中最多有两个偶数
B.若输出为奇数，则输入的d[i]中至少有两个奇数
C.若输出为偶数，则输入的d[i]中至少有两个偶数
D.若输出为奇数，则输入的d[i]中最多有两个奇数
正确答案： C

本题共 12 分

第 17 题

#include <iostream>

#include <cstdlib>

using namespace std;

int n;

int d[10000];

int find(int L, int R, int k) {

int x = rand() % (R - L + 1) + L;

swap(d[L], d[x]);

int a = L + 1, b = R;

while (a < b) {

while (a < b && d[a] < d[L])

++a;

while (a < b && d[b] >= d[L])

--b;

swap(d[a], d[b]);

}

if (d[a] < d[L])

++a;

if (a - L == k)

return d[L];

if (a - L < k)

return find(a, R, k - (a - L));

return find(L + 1, a - 1, k);

}

int main() {

int k;

cin >> n;

cin >> k;

for (int i = 0; i < n; ++i)

cin >> d[i];

cout << find(0, n - 1, k);

return 0;

}

假设输入的 n， k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

·判断题
1）第 9 行的“x”的数值范围是 L+1 到 R，即 [L+l,R]。（）
2）将第 19 行的“d[a]”改为“d[b]”，程序不会发生运行错误。（）

·单选题
3）(2.5分)当输入的 d[i] 是严格单调递增序列时，第 17 行的“swap”平均执行次数是( )。
4） (2.5分)当输入的 d[i] 是严格单调递减序列时，第 17 行的“swap”平均执行次数是( )。
5） (2.5分)若输入的 d[i] 为 i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。
6） (2.5分)若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )。

1.? A.正确? B.错误? 正确答案： B
2.? A.正确? B.错误? 正确答案： A
3.
A.O(n log n)O(nlogn)
B.O(n)O(n)
C.O(log n)O(logn)
D.O(n^2)O(n2)
正确答案： ABCD

4.
A.O(n^2)O(n2)
B.O(n)O(n)
C.O(n log n)O(nlogn)
D.O(log n)O(logn)
正确答案： B

5.
A.O(n)， O(n^2)
B.O(n)， O(n log n)
C.O(n log n)， O(n^2)
D.O(n log n)， O(n log n)
正确答案： A

6.
A.O(n)O(n)
B.O(log n)O(logn)
C.O(n log n)O(nlogn)
D.O(n^2)O(n2)
正确答案： D

本题共 13 分

第 18 题

100

101

#include <iostream>

#include <queue>

using namespace std;

const int maxl = 20000000;

class Map {

struct item {

string key; int value;

} d[maxl];

int cnt;

public:

int find(string x) {

for (int i = 0; i < cnt; ++i)

if (d[i].key == x)

return d[i].value;

return -1;

}

static int end() { return -1; }

void insert(string k, int v) {

d[cnt].key = k; d[cnt++].value = v;

}

} s[2];

class Queue {

string q[maxl];

int head, tail;

public:

void pop() { ++head; }

string front() { return q[head + 1]; }

bool empty() { return head == tail; }

void push(string x) { q[++tail] = x; }

} q[2];

string st0, st1;

int m;

string LtoR(string s, int L, int R) {

string t = s;

char tmp = t[L];

for (int i = L; i < R; ++i)

t[i] = t[i + 1];

t[R] = tmp;

return t;

}

string RtoL(string s, int L, int R) {

string t = s;

char tmp = t[R];

for (int i = R; i > L; --i)

t[i] = t[i - 1];

t[L] = tmp;

return t;

}

bool check(string st , int p, int step) {

if (s[p].find(st) != s[p].end())

return false;

++step;

if (s[p ^ 1].find(st) == s[p].end()) {

s[p].insert(st, step);

q[p].push(st);

return false;

}

cout << s[p ^ 1].find(st) + step << endl;

return true;

}

int main() {

cin >> st0 >> st1;

int len = st0.length();

if (len != st1.length()) {

cout << -1 << endl;

return 0;

}

if (st0 == st1) {

cout << 0 << endl;

return 0;

}

cin >> m;

s[0].insert(st0, 0); s[1].insert(st1, 0);

q[0].push(st0); q[1].push(st1);

for (int p = 0;

!(q[0].empty() && q[1].empty());

p ^= 1) {

string st = q[p].front(); q[p].pop();

int step = s[p].find(st);

if ((p == 0 &&

(check(LtoR(st, m, len - 1), p, step) ||

check(RtoL(st, 0, m), p, step)))

(p == 1 &&

(check(LtoR(st, 0, m), p, step) ||

check(RtoL(st, m, len - 1), p, step))))

return 0;

}

cout << -1 << endl;

return 0;

}

·判断题
1）输出可能为0。（）
2）若输入的两个字符串长度均为 101 时，则 m=0 时的输出与 m=100 时的输出是一样的。（）
3）若两个字符串的长度均为 n，则最坏情况下，此程序的时间复杂度为 O(n!)?。（）
·单选题
4）（2.5分）若输入的第一个字符串长度由 100 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 m 为 0，则输出为（）。
5）（4分）己知当输入为 0123n3210n1 时输出为 4，当输入为 012345n543210n1 时输出为14，当输入为 01234567n76543210n1 时输出为 28，则当输入为0123456789abnba9876543210nl 输出为
( ）。其中 n 为换行符。
6）（4分）若两个字符串的长度均为 n，且 0<m<n-l，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不一样。

1.? A.正确? B.错误? 正确答案： A
2.? A.正确? B.错误? 正确答案： B
3.? A.正确? B.错误? 正确答案： B
4.
A.49
B.50
C.100
D.-1
正确答案： D
5.
A.56
B.84
C.102
D.68
正确答案： D
6.
A.若 n、m 均为奇数，则输出可能小于 0。
B.若 n、m 均为偶数，则输出可能小于 0。
C.若 n 为奇数、m 为偶数，则输出可能小于 0。
D.若 n 为偶数、m 为奇数，则输出可能小于 0。
正确答案： C

本题共 15 分

第 19 题
三、完善程序（单选题，每小题3分，共计30分）
1.（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 w_iwi?，体积是 v_ivi?。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个a （0<a<l），并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 a·w，体积是 a·v，另一块的价值是(1-a)·w，体积是(1-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≤w_i,v_i≤100。提示：将所有的蛋糕按照性价比 w_i/v_iwi?/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;

}

1)①处应填（）
3)②处应填（）
3)③处应填( )
4)④处应填()
5）⑤处应填（）
1.
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]
正确答案： D

2.
A.w[1] <= B
B.v[1] <= B
C.w[1] >= B
D.v[1] >= B
正确答案： B

3.
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];
正确答案： D

4.
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]
正确答案： D

5.
A.curW，curV
B.curW, 1
C.curV, curW
D.curV, 1
正确答案： B

本题共 15 分

第 20 题
2.（最优子序列）取 m = 16，给出长度为 n 的整数序列 a_1,a_2,dots,a_n(0 le a_i < 2^m)a1?,a2?,…,an?(0≤ai?<2m)。对于一个二进制数 x，定义其分值 w(x) 为 x + popcnt(x)，其中 popcnt(x) 表示 x 二进制表示中 1 的个数。对于一个子序列 b_1,b_2,dots,b_kb1?,b2?,…,bk?，定义其子序列分值 S 为 w(b_1 oplus b_2) + w(b_2 oplus b_3) + w(b_3 oplus b_4) + cdots + w(b_{k-1} oplus b_k)w(b1?⊕b2?)+w(b2?⊕b3?)+w(b3?⊕b4?)+?+w(bk?1?⊕bk?)。其中 oplus⊕ 表示按位异或。对于空子序列，规定其子序列分值为 0 求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数 n(1 le n le 40000)n(1≤n≤40000) 接下来一行包含 n 个整数 a_1,a_2,cdots,a_na1?,a2?,?,an?。提示：考虑优化朴素的动态规划算法，将前 m/2 位和后 m/2 位分开计算。 Max[x][y]表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。

试补全程序。

#inelude <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;

const LL INF = 1000000000000000LL;

LL Max[MS + 4][MS + 4];

int w(int x)

{

int s = x;

while(x)

{

①;

s++;

}

return s;

}

void to_max(LL &x, LL y)

{

if(x < y)

x = y;

}

int main()

{

int n;

LL ans = 0;

cin >> n;

for(int x = 0; x <= MS; x++)

for(int y = 0; y <= MS; y++)

Max[x][y] = -INF;

for(int i = 1; i <= n ; i++)

{

LL a;

cin >> a;

int x = ② , y = a & MS;

LL v = ③;

for(int z = 0; z < = MS; z++)

to_max(v, ④);

for(int z = 0; z < = MS; z++)

⑤;

to_max(ans , v);

}

cout << ans << endl;

return 0;

}

1）①处应填（）
2）②处应填（）
3）③处应填（）
4）④处应填（）
5）⑤处应填 ( )

1.
A.x >>= 1
B.x ^= x &(x ^ (x + 1))
C.x -= x | -x
D.x ^= x &(x ^ (x – 1))
正确答案： D

2.
A.(a & MS) << B
B.a >> B
C.a & (1 << B)
D.a & (MS << B)
正确答案： B

3.
A.-INF
B.Max[y][x]
C.0
D.Max[x][y]
正确答案： C

4.
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)
正确答案： A

5.
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[z][y], v + w(a ^ (z << B)))
D.to_max(Max[x][z], v + w(y ^ z))
正确答案： B

本题共 15 分

相关文章: