求NOIP考试大纲

千问 · 2011-10-30 10:34:47

1、排序算法（快排、选择、#冒泡、堆排序、*二叉排序树、桶排序）2、DFS/BFS也就是搜索算法，剪枝务必要学！学宽搜的时候再复习一下哈希表3、树①遍历②二叉树③二叉排序树（查找、生成、删除）④堆（二叉堆、堆排序）⑤*Trie树4、图（图论建模）①最小生成树②最短路径③计算图的传递闭包④*连通分量（其中要掌握并查集技术）⑤拓扑排序、关键路径⑥*哈密尔顿环⑦*欧拉回路⑧*Bell-manFord、SPFA（能解决负权回路）⑨*二分图（匈牙利算法）5、动态规划（背包问题只是其中一种）①线性动规②区间动规③树形动规6、分治（掌握了动规分治就好学了）7、贪心8、*位运算（可以用来进行优化）9、数学与程序设计差不多就这些了，打‘*’的为不一定要学的。二分啊二分，楼上没讲二分！还有，修改了一下。追问你就在冒泡前加了个#号..这也叫改..

千问 · 2011-10-30 10:34:47

饿。看错了。其实都一样，我们那群都没有系统研究，毕竟考试不考死算法的。而对于同种策略，不同算法是相通的，有些树用近似图的算法实现，已经动归与贪心的转换等。这些改变过的算法往往比原算法在特定情况下更高效。区间动规树形动规经常用到，而冒泡一般没人用吧。对于特定题目要求，也有随机化，DP优化等。还有，如果是普及组，这略有些超纲，提高组似乎也就多了线段树，并查集，以及更难的数论。

千问 · 2011-10-30 10:34:47

1、排序算法（快排、选择、冒泡、堆排序、*二叉排序树、桶排序）2、DFS/BFS也就是搜索算法，剪枝务必要学！学宽搜的时候再复习一下哈希表3、树①遍历②二叉树③*二叉排序树（查找、生成、删除）④堆（二叉堆、堆排序）⑤*Trie树4、图（图论建模）①最小生成树②最短路径③计算图的传递闭包④连通分量（其中要掌握并查集技术）⑤拓扑排序、关键路径⑥*哈密尔顿环⑦欧拉回路⑧Bell-manFord、SPFA（能解决负权回路）⑨*二分图（匈牙利算法）5、动态规划（背包问题只是其中一种）①线性动规②*区间动规③*树形动规6、分治（掌握了动规分治就好学了）7、贪心8、*位运算（可以用来进行优化）9、数学与程序设计差不多就这些了，打‘*’的为不一定要学的。赞同

千问 · 2011-10-30 10:34:47

http://imgsrc.baidu.com/forum/pic/item/9922720e0cf3d7cacf078732f21fbe096a63a985.jpg高精度a.加法b.减法c.乘法d.高精度除单精排序算法a.选择排序b.插入排序c.hash排序d.归并排序e.堆排序f.快排字符串匹配算法a.蛮力法b.KMP数论a.欧几里德算法b.扩展欧几里德算法(axby=c的正整数c.素数测试{O(sqrt(n))}d.筛法求素数e.快速乘方(请用高精)树论a.二叉搜索树b.优先队列c.线段树(RMQ问题建议使用st算法)d.平衡树一种(建议学习SBT)图论a.拓扑排序b.割顶，割边(桥){O(n)}c.强连通分支{O(n)}d.有向无回路图的最长路径(罕见用上的)e.欧拉回路f.最小生成树1.Prime2.Kruskal(这个个人觉得挺重要的)g.次小生成树{简单的删除最大边是不对的}h.最短路径1.Dijkstra2.Bellman-ford3.spfa4.flyod{推荐单源使用spfa，同样可以通过设上限发现图中是否有负权回路，而且这个思想在去除dp中的暂时后效性非常有用}计算几何学{noip不是不考几何}a.判断两条线段是否相交b.凸包算法{O(n)}其他算法并查集RMQ问题(通解：线段树，st算法)赞同