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;}
