2020年信奥赛C++提高组csp-s初赛真题及答案解析（选择题6-10）

2020年信奥赛C++提高组csp-s初赛真题及答案解析（选择题6-10）

第 6 题：下列哪些问题不能用贪心法精确求解？（ ）

A. 霍夫曼编码问题

B. 0-1 背包问题

C. 最小生成树问题

D. 单源最短路径问题

答案：B
**解析：**贪心法适用于具有最优子结构和贪心选择性质的问题。霍夫曼编码、最小生成树、单源最短路径（非负权）均可用贪心精确求解，而0-1背包问题贪心无法保证最优解。

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

A. O(n+e)

B. O(n 2 n^2n2)

C. O(e 2 e^2e2)

D. O(n)

答案：A
**解析：**深度优先遍历采用邻接表存储时，每个顶点和每条边均被访问一次，时间复杂度为 O(n+e)。

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

A. 144

B. 100

C. 48

D. 122

答案：A
**解析：**二分图边数最多当两部分顶点数尽可能平均，即各12个顶点时，边数最大为 12×12 = 144。

**第 9 题：**广度优先搜索时，一定需要用到的数据结构是( )

A. 栈

B. 二叉树

C. 队列

D. 哈希表

答案：C
**解析：**广度优先搜索依靠队列实现逐层访问，队列是必需的数据结构。

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

A. 30<n<40

B. 40<n<50

C. 50<n<60

D. 20<n<30

答案：C
**解析：**设学生人数为 n，满足：
n ≡ 2 (mod 3)
n ≡ 3 (mod 5)
n ≡ 4 (mod 7)
在 n<60 范围内解得 n=53，属于区间 50<n<60。

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}