noip完整考纲

《noip完整考纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、由本人精心整理，得到的童鞋赚到了哦标有★的都是noip中几乎不可能出现的，没有标的最好是完全掌握，才好拿国一哦。2.排序冒泡排序（起泡排序）选择排序插入排序★Shell排序快速排序线性时间排序查找第k大元素带第二关键字的排序1.语言与计算机递归调用向前引用随机化指针类型按位运算4.数论（二）求最大公约数求最小公倍数★扩展的辗转相除★求解一元一次同余式★中国剩余定理★高斯消元3.数论（一）素性判断筛选建立素数表分解质因数进制转换二分取幂★二分求解线性递推方程6.图论：最小生成树Prim算法Kruskal算法★Boruvka算法次小生成树5.四则运算表达式计算高精度加法高精度减法高精度乘法★

2、高精度除法8.图论：DFS遍历深度优先搜索欧拉回路求弱连通分量★求强连通分量★求割点★求桥7.图论：求最短路Dijkstra算法Bellman-Ford算法Floyd-Warshall算法次短路★差分约束系统10.图论：二分图验证二分图匈牙利算法★KM算法★稳定婚姻系统9.图论：BFS遍历广度优先搜索（宽度优先搜索）求不带权的最短路求图的直径AOV问题（拓扑排序）AOE问题11.树求树的最短链二叉树的四种遍历已知先序中序求后序已知中序后序求先序★已知先序后序求中序★LCA问题的Tarjan离线算法★Huffman编码12.数据结构（一）表和栈Hash表与开散列★分段Hash并查集堆二叉查

3、找树14.排列与组合生成所有排列生成所有组合生成下一个排列生成下一个组合13.数据结构（二）★平衡二叉树★树状数组★线段树★块状链表16.动态规划（二）最长上升序列（LIS）最长公共子串（LCM）最小代价子母树15.动态规划（一）0-1背包完全背包乘法问题数塔问题装箱问题18.贪心最优装载问题部分背包问题独立区间的选择覆盖区间的选择区间的最小点覆盖点的最小区间覆盖17.分治与递归二分查找归并排序最近点对问题求最大子序列和的O(nlogn)算法Hanoi塔问题及其变种棋盘覆盖问题循环赛日程表问题20.其它★网络流★置换群★KMP算法19.递推Fibonacci数的若干应用Catalan数的

4、若干应用拆分数差分序列