2020CCF非专业级别软件能力认证第--轮(CSP-S1)

(CSP-S1) 入门级C++语言试题
认证时间: 2020 年9月18日09:30~11:30 ;
考生注意事项：
•试题纸共有12页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的 一律无效。
♦不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每題有且仅有一个正确选项）
*
您的姓名：
*
1.请选出以下最大的数( )
A.(550)10
B. (777)8
C. 2^10
D. (22F)i6
*
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的哈希表中，如果 哈希函数*(x)=(),将不会产生冲突，其中a mod b表示a除以b的 余数。
A.x2 mod 11
B.2x mod 11
C.x mod 11
D.[x/2J mod 11,其中[x/2」表示x/2下取整
*
6.下列哪些问题不能用贪心法精确求解？( )
A. 霍夫曼编码问题
B. 0-1背包问题
C, 最小生成树问题
D, 单源最短路径问题
*
7.具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历运算的 时间复杂度为().
A. O(n+e)
B. O(n^2)
C.O(e^2)
D. O(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+l层消耗10k卡热量(k>l)o如果小 明想从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算法计算单源最短 路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为()0
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. 图灵
阅读程序一（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外， 判断题1.5分，选择题3分，共计40分）
1.

假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单选题：
•判断题
*
16. n必须小于1000,否则程序可能会发生运行错误。（）
对
错
*
17.  输出一定大于等于0。（）
对
错
*
18. 若将第13行的“j =。”改为“j = i + 1”，程序输出可能会改变。()
对
错
*
将第“行的“d[i] < d[j]”改为ffd[i] != d[j]”，程序输出不会改 变。（）
对
错
单选题
*
20. 若输入n为100,且输出为127,则输入的d[i]中不可能有（）。
A. 127
B. 126
C. 128
D. 125
*
21. 若输出的数大于。，则下面说法正确的是（）。
A.若输出为偶数，则输入的d[i]中最多有两个偶数
B. 若输出为奇数，则输入的d[i]中至少有两个奇数
C. 若输出为偶数，则输入的d[i]中至少有两个偶数
D. 若输出为奇数，则输入的d[i]中最多有两个奇数
阅读程序二（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外，判断题1.5分，选择题3分，共计40分）


假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
•判断题
*
22.第9行的“X”的数值范围是L+1到R,艮卩[L+l, R]。()
对
错
*
23.将第19行的“d[a]"改为"d[b]”，程序不会发生运行错误。()
对
错
单选题
*
24.当输入的d[i]是严格单调递增序列时, 第17行的“swap”平均执行次数是()。
A. o(n log n)
B.o(n)
C.o(n log n)
D. o(n^2)
*
25.当输入的d[i]是严格单调递减序列时，第17行的"swap” 平均执行次数是()。
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(log n)
*
26.若输入的d[i]为i，此程序①平均的时间复杂度和②最坏青况下的时间复杂度分别是( )
A. θ(n)，0(n^2)
B.0(n)，θ(n 1og n)
C. θ(n log n)，θ(n^2)
D. θ(n log n)，θ(n^2)
*
27.若输入的d[i]都为同一个数，此程序平均的时间复杂度是
A.o(n)
B.o(log n)
C. o(n 1og n)
D.o(n^2)
阅读程序三（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外， 判断题1.5分，选择题3分，共计40分）
3.





•判断题
*
28.输岀可能为0（）
对
错
*
29.若输入的两个字符串长度均为101时，则m=0时的输出与m=100时的 输出是一样的。（）
对
错
*
30. 若两个字符串的长度均为n,则最坏情况下，此程序的时间复杂度为 0（n!）（）
对
错
单选题
*
31.若输入的第一个字符串长度由100个不同的字符构成，第二 个字符串是第一个字符串的倒序，输入的m为0,则输出为（）。
A. 49
B. 50
C. 100
D. -1
*
32.已知当输入为“0123\n3210\n1”时输出为4,当输入为 “012345\n543210\n1”时输出为14,当输入为 “01234567里176543210\n1”时输出为28,则当输入为 “0123456789ab\nba9876543210\nl” 输出为（）。其中\n 为换行符。
A. 56
B. 84
C. 102
D. 68
*
33.若两个字符串的长度均为n,且0<m<n-l,且两个字符串的构 成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列 说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不 一样。
A.若n、m均为奇数，则输出可能小于0。
B.若n、m均为偶数，则输出可能小于0
C.若n为奇数、m为偶数，则输出可能小于0。
D.若n为偶数、m为奇数，则输出可能小于S
三、完善程序（单选题，每小题3分，共计30分）
(1)（分数背包）小S有n块蛋糕，编号从1到n。第i块蛋糕的价值是雄， 体积是引。他有一个大小为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<=w,v<=100;
提示：将所有的蛋糕按照性价比的wi/vi从大到小排序后进行贪心选择。 试补全程序。


*
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]
*
35. ②处应填（ ）
A.w[l] ＜= B
B. v[ 1 ] ＜= B
C. w[l] >= B
D. v[1 ] >= B
*
36.③处应填( )
A. print(v[l]> w[l]); return 0;
B. curV = 0; curW = 0;
C. prir)t(w[l]? v[l]); return 0;
D. curV = v[l]; curW = w[l];
*
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]
*
38 .⑤处应填（）
A. curWj curV
B. curW, 1
C. curV, curW
D. curV, 1
三、完善程序（单选题，每小题3分，共计30分）
(2)



*
38.①处应填（ ）
A. x>>=1
B.x^=x&(x^(x+1))
C. x-=x| -x
D.x-=x| -x
*
39 .②处应填（）
A. (a&MS)＜＜B
B.a>>B
C. a&(1＜＜B)
D.a&(MS＜＜B)
*
40.③处应填()
A.-INF
B. Max[y][x]
C. 0
D.Max[x][y]
*
41.④处应填( )
A. Max[x][z] + w(y ^z)
B.[Max[x][z] + W(a ^ z)
C.Max[x][z] + W(x A^(z＜＜ B))
D. Max[x][z] + W(x^z)
*
42.⑤处应填( )
A.to_max(Max[y][z],v + w(a ^(z ＜＜ B))) v
B.to_max(Max[z][y],+ w((x ^z) ＜＜ B)) v +
C.to_max(Max[z][y],w(a ^ (z ＜＜ B)))
D. to_max(Max[x][z],v + w(y ^ z))
问卷星提供技术支持
举报