广度优先搜索使用的数据结构（广度优先搜索需要用到的数据结构）

2020中国计算机协会CCF非专业级别软件能力认证第一轮

（CSP-S）提高级C++语言试题

认证时间：2020年10月11日09:30~11:30

2020中国计算机协会(CCF)C++语言第1轮提高级试题及答案_python

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 请选出以下最大的数：C

A. (500)₁₀

B. (777)₈

C. 2¹⁰

D. (22F)₁₆

2. 操作系统的功能是：B

A. 负责外设与主机之间的信息交换

B. 控制和管理计算机系统的各种硬件和软件资源的使用

C. 负责诊断机器的故障

D. 将源程序编译成目标程序

3. 现有一段8分钟的视频文件，它的播放速度是每秒24帧图像，每帧图像是一幅分辨率为2048*1024像素的32位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？：B

A. 30G

B. 90G

C. 150G

D. 450G

解析：(8*60*24*2048*1024*32bit/1024*1024*1024*8)=90G

4. 今有一空栈S，对下列待进栈的数据素序列a,b,c,d,e,f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底素为:B

A. b

B. a

C. d

D. c

5. 将(2, 7, 10,18)分别存储到某个地址区间为0〜10的哈希表中，如果哈希函数h( x ) = ( ) , 将不会产生冲突，其中a mod b表示a除以b的余数。:D

A. x2 mod 11

B. 2x mod 11

C. x mod 11

D. [x/2] mod 11,其中[x/2]表示x/2下取整

6. 下列哪些问题不能用贪心法精确求解？:B

霍夫曼编码问题
0-1背包问题
最小生成树问题
单源最短路径问题

7. 具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为：A

A.0(n+e) B.0(n2) C.0(e2) D. 0(n)

8. 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图，那么，24个顶点的二分图至多有多少条边：A

A. 144 B.100 C.48 D. 122

9.广度优先搜索时，一定需要用到的数据结构是：C

A.栈 B.二叉树 C.队列 D.哈希表

10. —个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数n在以下哪个区间？己知n<60：C

A.30<n<40

B.40<n<50

C.50<n<60

D.20<n<30

11,12,13,14,15...

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

01 #include<iostream>

02 using namespace std;

04 int n;

05 int d[1000];

07 int main() {

08 cin >>n;

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

10 cin >>d[i];

11 int ans =-1;

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

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

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

15 ans= max(ans> d[i] +d[j]

16 cout <<ans;

17 return 0;

18}

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

•判断题

1） n必须小于1000，否则程序可能会发生运行错误。×

2）输出一定大于等于0。×

3）若将第13行的“j = 0”改为“j = i + 1”，程序输出可能会改变。√

4）将第14行的“d[i] < d[j]”改为“d[i] != d[j]”，程序输出不会改变。√

•单选题

5）若输入n为100,且输出为127，则输入的d[i]中不可能有：C。

A.127 B.126 C.128 D.125

6）若输出的数大于0，则下面说法正确的是：C。

若输出为偶数，则输入的d[i]中最多有两个偶数
若输出为奇数，则输入的d[i]中至少有两个奇数
若输出为偶数，则输入的d[i]中至少有两个偶数
若输出为奇数，则输入的d[i]中最多有两个奇数

......

今天的文章广度优先搜索使用的数据结构（广度优先搜索需要用到的数据结构）分享到此就结束了，感谢您的阅读。

广度优先搜索使用的数据结构（广度优先搜索需要用到的数据结构）

相关推荐