2020年（初赛S）CCF非专业级别软件能力认证全国卷真题（附详细答案解析）

2020 CCF 非专业级别软件能力认证第一轮 (CSP-S)提高级 C++语言试题 认证时间：2020 年 10 月 11 日 09:30-11:30 考生注意事项： •试题纸共有 13 页，答题纸共有 1 页，满分 100 分。请在答题纸上作答，写在试题纸上的一 律无效。 •不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 15 题，每题 2 分，共计 3。分；每题有且仅有一个正确选项) 1.请选出以下最大的数( ) A.(550)10 B. (778)8 C. 210 D. (22)16 2.操作系统的功能是()。 负责外设与主机之间的信息交换 控制和管理计算机系统的各种硬件和软件资源的使用 负责诊断机器的故障 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.x2 mod 11 B.2x mod 11 C.x mod 11 D.[x/2] mod 11,其中[x/2]表示 x/2 下取整 6.下列哪些问题不能用贪心法精确求解？( ) A.霍夫曼编码问题 B. 0-1 背包问题 C.最小生成树问题 D.单源最短路径问题 7.具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为()o A.0(n+e) B. 0(n2) C. 0(e2) 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+l层消耗 10k卡热量(k>l)。如果小 明想从1层开始，通过连续向上爬楼梯消耗1000 卡热量，至少要爬到第几层楼？ ( )o A. 14 B. 16 C. 15 D. 13 12.表达式 a*(b+c)-d 的后缀表达形式为（） A. abc*+d- B. -+*abcd C.abcd*+- D.abc+*d- 13.从一个 4×4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有 ()种方法。 A. 60 B. 72 C. 86 D. 64 14.对一个 n 个顶点、m条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不 使用堆或其它优先队列进行优化，则其时间复杂度为（）0 A. 0((m + n2) log n) B. 0(mn + n3) C. 0((m + n) log n) D. 0(n2) 15.1948 年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。 A. 欧拉(Leonhard Euler) B. 冯•诺伊曼(John von Neumann) C. 克劳德•香农(Claude Shannon) D. 图灵(Alan Turing) 二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填√, 错误填 X;除特 殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分) 1. 01 #include <iostream> 02 using namespace std; 03 04 int n; 05 int d[1000]; 06 07 int main（）{ 08 cin >> n; 09 for (int i = 0; i < n; ++i) 10 cin >> d[i]; 11 int