信息学奥赛CSP-S考试大纲-提高级
一、计算机基础知识与编程环境- 在Linux系统终端中使用mkdir，cp、rm、mv等命令新建、复制、删除、移动文件或目录
- 在Linux系统终端中使用cd，pwd，ls等命令更改、显示目录路径和查看目录中的文件
- 在Linux系统下使用Gedit，Vim或 Emacs等文本编辑工具编写代码
- 熟悉g 、gcc等编译器以及优化、数学库等常见编译选项
- 在Linux系统终端中运行程序，并使用time令查看程序用时（区分real time，sys time和user time）
- 了解调试工具 gdb及其break, display, continue，step等命令
二、 C 程序设计2.1 类（class）2.2 STL模板- 集合（set）
- 列表（list），双端队列（deque），优先队列（priority_queue）
- 多重集合（multiset）
- 映射（map），多重映射（multimap）
- 对（pair），元组（tuple）
三、数据结构3.1 线性结构3.2 集合与森林3.3 特殊树- 线段树与树状数组
- 字典树（trie树）
- 笛卡尔树
- 二叉平衡树AVL，treap，splay等
- 基环树
3.4 常见图- 稀疏图
- 偶图（二分图）
- 欧拉图
- 有向无环图
- 连通图与强连通图
- 重连通图
3.5 哈希表- 数值哈希函数构造
- 排列哈希函数构造
- 字符串哈希函数构造
- 哈希函数冲突的常用解决方法
四、算法4.1 复杂度分析4.2 基础算法4.3 排序算法- 归并排序
- 快速排序
- 堆排序
- 树形选择排序（锦标赛排序）
- 桶排序
- 基数排序
4.4 字符串相关算法4.5 搜索算法- 搜索的剪枝优化
- 记忆化搜索
- 启发式搜索
- 双向宽度优先搜索
- 选代加深搜索
- 搜索对象的压缩存储
4.6 图论算法- Prim和kruskal等求最小生成树算法
- 求次小生成树算法
- Dijkstra，bellman_ford、SPFA 等求单源最短路算法
- 求单源次短路径算法
- Floyd-Warshall 算法求任意两点间的最短路和传递闭包
- 有向无环图的拓扑排序算法
- 求欧拉道路和欧拉回路算法
- 二分图的构造及其判定算法
- 最近公共祖先
- 求强联通分量算法
- 强连通分量的缩点算法
- 求割点、割边算法
4.7 动态规划五、数学5.1 高中数学5.2 初等数论- 同余式
- 欧拉定理和欧拉函数
- 费马小定理
- 威尔逊定理
- 装蜀定理
- 逆元
- 扩展欧几里得算法
- 孙子定理
5.3 组合数学- 可重集排列
- 可重集组合
- 错排列、圆排列
- 鸽巢原理
- 二项式定理
- 容斥原理
- 卡特兰数
5.4 线性代数- 矩阵概念
- 特殊矩阵：稀疏矩阵，三角矩阵，对称矩阵
- 矩阵的初等变换
- 矩阵的加减乘和转置运算
- 线性方程组的高斯消元法
大家还看了
也许喜欢
更多游戏
