跳转至

提高级

计算机基础知识与编程环境

计算机基础知识与编程环境
  1. 在Linux系统终端中使用mkdir、cp、rm、mv等命令新建、复制、删除、移动文件或目录
  2. 在Linux系统终端中使用cd、pwd、ls等命令更改、显示目录路径和查看目录中的文件
  3. 在Linux系统下使用Gedit、Vim或Emacs等文本编辑工具编写代码
  4. 熟悉g++、gcc等编译器以及优化、数学库等常见编译选项
  5. 在Linux系统终端中运行程序，并使用time命令查看程序用时（区分real time、sys time和user time）
  6. 了解调试工具gdb及其break、display、continue、step等命令

C++程序设计

C++程序设计

  1. 类（class）

    • 类的概念及简单应用
    • 成员函数和运算符重载

  2. STL模板

    • 集合（set）
    • 列表（list），双端队列（deuqe），优先队列（priority_queue）
    • 多重集合（multiset）
    • 映射（map），多重映射（multimap）
    • 对（pair），元组（tuple）

数据结构

数据结构

  1. 线性结构

  2. 集合与森林

    • 等价类
    • 并查集
    • 树与二叉树的转化——孩子兄弟表示法

  3. 特殊树

    • 线段树与树状数组
    • 字典树（trie树）
    • 笛卡尔树
    • 二叉平衡树AVL、treap、splay等
    • 基环树

  4. 常见图

    • 稀疏图
    • 偶图（二分图）
    • 欧拉图
    • 有向无环图
    • 连通图与强连通图
    • 重连通图

  5. 哈希表

    • 数值哈希函数构造
    • 排列哈希函数构造
    • 字符串哈希函数构造
    • 哈希函数冲突的常用解决办法

算法

算法

  1. 复杂度分析

    • 空间复杂度分析
    • 时间复杂度分析

  2. 基础算法

    • 分治算法

  3. 排序算法

    • 归并排序
    • 快速排序
    • 堆排序
    • 树形选择排序（锦标赛排序）
    • 桶排序
    • 基数排序

  4. 字符串相关算法

    • 字符串匹配算法——KMP

  5. 搜索算法

    • 搜索的剪枝优化
    • 记忆化搜索
    • 启发式搜索
    • 双向宽度优先搜索
    • 迭代加深搜索
    • 搜索对象的压缩存储

  6. 图论算法

    • Prim和kruskal等求最小生成树算法
    • 求次小生成树算法
    • Dijkstra、bellman_ford、SPFA等求单源最短路算法
    • 求单源次短路径算法
    • Floyd-Warshall算法求任意两点间的最短路和传递闭包
    • 有向无环图的拓扑排序算法
    • 求欧拉道路和欧拉回路算法
    • 二分图的构造及其判定算法
    • 最近公共祖先
    • 求强连通分量算法
    • 强连通分量的缩点算法
    • 求割点、割边算法

  7. 动态规划

    • 树型动态规划
    • 状态压缩动态规划
    • 动态规划的常用优化

数学

数学

  1. 高中数学

    • 代数
    • 解析几何
    • 立体几何

  2. 初等数论

    • 同余式
    • 欧拉定理和欧拉函数
    • 费马小定理
    • 威尔逊定理
    • 裴蜀定理
    • 逆元
    • 扩展欧几里得算法
    • 孙子定理（中国剩余定理）

  3. 组合数学

    • 可重集排列
    • 可重集组合
    • 错排列、圆排列
    • 鸽巢原理
    • 二项式定理
    • 容斥原理
    • 卡特兰数

  4. 线性代数

    • 矩阵概念
    • 特殊矩阵：稀疏矩阵、三角矩阵、对称矩阵
    • 矩阵的初等变换
    • 矩阵的加减乘和转置运算
    • 线性方程组的高斯消元法
最后更新: 2021-09-16
Back to top