「CSP2020 S」笔试
测试数据来自 oistream/1143
说明与提示
本题为笔试评测,具体评测方式请参考 7FOJ 笔试评测方式。
因为 Vijos 不支持浮点数测试点分值,因此本题所有小题分数均做 处理,本题满分为 分,您的实际得分为本题得分 。
一、单项选择题
1.请选出以下最大的数( )
A.
B.
C.
D.
2.操作系统的功能是( )。
A. 负责外设与主机之间的信息交换
B. 控制和管理计算机系统的各种硬件和软件资源的使用
C. 负责诊断机器的故障
D. 将源程序编译成目标程序
3.现有一段 分钟的视频文件,它的播放速度是每秒 帧图像,每帧图像是一幅分辨率为 像素的 位真彩色图像。请问要存储这段原始无压缩视频,需要多大的存储空间?( )。
A.
B.
C.
D.
4.今有一空栈 ,对下列待进栈的元素序列 依次进行:进栈,进栈,出栈,进栈,进栈,出栈的操作,则此操作完成后,栈底元素为( )。
A.
B.
C.
D.
5.将 分别存储到某个地址区间为 的哈希表中,如果哈希函数 ( ),将 不会 产生冲突,其中 表示 除以 的余数。
A.
B.
C.
D.
6.下列哪些问题 不能 使用贪心法精确求解?( )
A. 霍夫曼编码问题
B. 0-1
背包问题
C. 最小生成树问题
D. 单源最短路径问题
7.具有 个顶点, 条边的图采用邻接表存储结构,进行深度优先遍历运算的时间复杂度为( )。
A.
B.
C.
D.
8.二分图是指能将顶点划分成两个部分,每一部分内的顶点间没有边相连的简单无向图。那么, 个顶点的二分图 至多 有( )条边。
A.
B.
C.
D.
9.广度优先搜索时,一定需要用到的数据结构是( )。
A. 栈
B. 二叉树
C. 队列
D. 哈希表
10.一个班学生分组做游戏,如果每组三人就多两人,每组五人就多七人,每组七人就多四人,问这个班的学生人数 在以下哪个区间?已知 。( )。
A.
B.
C.
D.
11.小明想通过走楼梯来锻炼身体,假设从第 层走到第 层消耗 卡热量,接着从第 层走到第 层消耗 卡热量,再从第 层走到第 层消耗 卡热量,依此类推,从第 层走到第 层消耗 卡热量 。如果小明想从 层开始,通过连续向上爬楼梯消耗 卡热量,**至少** 要爬到第几层楼?( )。
A.
B.
C.
D.
12.表达式 a*(b+c)-d
的后缀表达形式为( )。
A. abc*+d-
B. -+*abcd
C. abcd*+-
D. abc+*d-
13.从一个 的棋盘中选取不在同一行也不在同一列上的两个方格,共有( )种方法。
A.
B.
C.
D.
14.对一个 个顶点、 条边的带权有向简单图用 算法计算单源最短路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为( )。
A.
B.
C.
D.
15. 年,( )将热力学中的熵引入信息通信领域,标志着信息论研究的开端。
A. 欧拉()
B. 冯 · 诺依曼()
C. 克劳德 · 香农()
D. 图灵()
二、阅读程序
1.
假设输入的 和 都是不超过 的正整数,完成下面的判断题和单选题:
判断题
(1) 必须小于 ,否则程序 可能 会发生运行错误。( )
(2) 输出 一定 大于等于 。( )
(3) 若将第 行的 j = 0
改为 j = i + 1
,程序输出 可能 会改变。( )
(4) 将第 行的 d[i] < d[j]
改为 d[i] != d[j]
,程序输出 不会 改变。( )
单选题
(5) 若输入 为 ,且输出为 ,则输入的 中不可能有( )。
A.
B.
C.
D.
(6) 若输出的数大于 ,则下面说法 正确 的是( )。
A. 若输出为偶数,则输入的 中 最多 有两个偶数。
B. 若输出为奇数,则输入的 中 至少 有两个奇数。
C. 若输出为偶数,则输入的 中 至少 有两个偶数。
D. 若输出为奇数,则输入的 中 最多 有两个奇数。
2.
假设输入的 和 都是不超过 的正整数,且 不超过 ,并假设 rand()
函数产生的是均匀的随机数,完成下面的判断题和单选题:
判断题
(1) 第 行的 的数值范围是 到 ,即 。( )
(2) 将第 行的 d[a]
改为 d[b]
,程序 不会 发生运行错误。( )
单选题
(3) ( 分) 当输入的 是严格 单调递增 序列时,第 行的 swap
的平均执行次数是( )。
A.
B.
C.
D.
(4) ( 分) 当输入的 是严格 单调递减 序列时,第 行的 swap
平均执行次数是( )。
A.
B.
C.
D.
(5) ( 分) 若输入的 为 ,此程序 ① 平均时间复杂度 和 ② 最坏情况下的时间复杂度 分别是( )。
A.
B.
C.
D.
(6) ( 分) 若输入的 都为同一个数,此程序平均的时间复杂度是( )。
A.
B.
C.
D.
3.
判断题
(1) 输出 可能 为 。( )
(2) 若输出的两个字符串长度均为 时,则 时的输出与 时的输出是一样的。( )
(3) 若两个字符串的长度均为 ,则最坏情况下,此程序的时间复杂度为 。( )
单选题
(4) ( 分) 若输入的第一个字符串长度由 个不同的字符构成,第二个字符串是第一个字符串的倒序,输入的 为 ,则输出为( )。
A.
B.
C.
D.
(5) ( 分) 已知当输入为 0123\n3210\n1
时输出为 ,当输入为 012345\n543210\n1
时输出为 ,当输入为 01234567\n76543210\n1
时输出为 ,则当输入为 0123456789ab\bba9876543210\n1
时输出为( )。其中 \n
为换行符。
A.
B.
C.
D.
(6) ( 分) 若两个字符串的长度均为 ,且 ,且两个字符串的构成相同(即任何一个字符在两个字符串中出现的次数均相同),则下列说法 正确 的是( )。提示:考虑输入与输出有多少对字符前后顺序不一样。
A. 若 均为奇数,则输出 可能 小于 。
B. 若 均为偶数,则输出 可能 小于 。
C. 若 为奇数、 为偶数,则输出 可能 小于 。
D. 若 为偶数、 为奇数,则输出 可能 小于 。
三、完善程序
1.**分数背包** · 小 有 块蛋糕,编号从 到 。第 块蛋糕的价值是 ,体积是 。他有一个大小为 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 。
他打算选择一些蛋糕装入盒子,他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大,他可以任意切割蛋糕。具体来说,他可以选择一个 ,并加一块价值是 ,体积为 的蛋糕切割成两块,其中一块的价值是 ,体积是 ,另一块的价值是 ,体积是 。他可以重复无限次切割操作。
现要求编程输出最大可能的价值,以分数的形式输出。
比如 ,三块蛋糕的价值分别是 、、,体积分别是 、、。那么最优的方案就是将体积为 的蛋糕切成两份,一份体积是 ,价值是 ,另一份体积是 ,价值是 ,然后把体积是 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 ,故程序输出 42/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]
(2) ② 处应填( )。
A. w[1] <= B
B. v[1] <= B
C. w[1] >= B
D. v[1] >= 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];
(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]
(5) ⑤ 处应填( )。
A. curW, curV
B. curW, 1
C. curV, curW
D. curV, 1
2.**最优子序列** · 取 ,给出长度为 的整数序列 。对于一个二进制数 ,定义其分值 为 ,其中 表示 二进制表示中 的个数。对于一个子序列 ,定义其子序列分值 为 。其中 表示按位异或。对于空子序列,规定其子序列分值为 。求一个子序列使得其子序列分值最大,输出这个最大值。
输入第一行包含一个整数 。接下来一行包含 个整数 。
提示:考虑优化朴素的动态规划算法,将前 位和后 位分开计算。
表示当前的子序列下一个位置的高 位是 、最后一个位置的低 位是 时的最大价值。
试补全程序。
(1) ① 处应填( )。
A. x >>= 1
B. x ^= x & (x ^ (x + 1))
C. x -= x | -x
D. x ^= x & (x ^ (x - 1))
(2) ② 处应填( )。
A. (a & MS) << B
B. a >> B
C. a & (1 << B)
D. a & (MS << B)
(3) ③ 处应填( )。
A. -INF
B. Max[y][x]
C. 0
D. Max[x][y]
(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)
(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))
信息
- ID
- 2608
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者