acm考什么

问题描述

精选答案

1、时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）

2、排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序，拓扑排序）

4、指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）

5、按位运算（and，or，xor，shl，shr，一些应用）

7、计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）

8、数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）

9、组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）