CCF青少年计算机程序设计评级标准-(简版).doc

CCF青少年计算机程序设计评级原则一级原则定义：理解什么是计算机程序，可以编写计算机程序解决简朴问题知识规定：1、 程序的基本构造2、 标记符和核心字3、 基本数据类型4、 常量和变量5、 算术体现式和关系体现式6、 整除，求余运算，常用数学函数7、 赋值语句，输入输出语句，复合语句，条件语句（不嵌套），循环语句（不嵌套）能力规定：1、 能用自然语言描述解决简朴问题的措施和环节2、 能用顺序，分支，循环语句实现知识规定中的措施和环节，编写完整程序3、 初步理解算法的意义题例： 试题名：求最小，最大数 试题描述： 给出N个数，请找出这N个数中的最小数和最大数 输入数据： 第1行，一种整数n，n<=1000接下来的一行，涉及n个数，两个数之间用一种空格分隔 输出数据： 第1行，最小数第2行，最大数 输入样例： 4 1 2 3 4 输出样例： 1 4二级原则定义：理解什么是算法，可以用程序设计语言实现简朴算法，解决问题知识规定：1、 逻辑体现式2、 条件嵌套，循环嵌套，数组3、 枚举，简朴排序，简朴查找算法。

4、 素数与合数，最大公约数，最小公倍数，互质数能力规定：1、 能用简朴枚举算法解决实际问题，能对数据进行简朴排序和查找2、 具有独立编写和调试简短程序的能力题例： 试题名：求第k小数 试题描述： 给出N个数，请找出第K小的数并输出该数值 输入数据： 第1行，两个整数n,k，n,k<=1000 接下来的一行，涉及n个数，两个数之间用1个空格分隔 输出数据： 只有1行，为第k小数 输入样例： 4 3 1 2 3 4 输出样例： 3三级原则 定义：具有较强的程序实现能力，使用一种计算机程序设计语言编写程序，解决问题 知识规定：1、 数制及其转化，信息编码，位运算2、 字符串类型3、 子程序4、 递归5、 逻辑运算，整数的质因数分解，随机函数6、 筛选法，欧几里得算法能力规定：1、 全面掌握一种计算机程序设计语言2、 具有运用简朴数学知识编写程序解决问题的能力题例： 试题名：分解质因数 试题描述：给一种整数N，将N写成质因数的乘积 输入数据： 一种整数n,n<=100000 输出数据： 质因数乘积体现式（请将质因数按从小到大顺序输出） 输入样例： 12 输出样例： 12=2*2*3四级原则（NOIP普及组全国前70%） 定义：理解几种常用的算法，并运用这些算法编写程序，解决问题。

知识规定：1、 构造类型，文献操作2、 数据类型的内在含义3、 贪心法，递推，回溯法，模拟算法4、 简朴的字符串解决5、 集合及集合的运算，加法原理和乘法原理，简朴的排列和组合能力规定：1、 能根据实际额问题选择合适的数据类型2、 能运用贪心、递推、回溯、模拟等算法解决实际问题3、 能独立设计简朴的测试数据，测试自己程序的对的性题例： 试题名：校门外的树 详见各oj，laoj也有五级原则（NOIP普及组全国前40%） 定义：掌握简朴数据构造知识，并结合已学算法和数学知识编写程序，解决问题 知识规定：1、 指针类型2、 一般线性表，队列，堆栈，二叉树的存储和遍历3、 排列和组合，高精度数值的解决4、 二分算法，迅速排序，深度优先搜索，宽度优先搜索，简朴动态规划5、 圆排列，可重集排列，鸽笼原理，素因数分解，幂函数，指数函数，对数函数，三角函数，模运算，不等式基本知识能力规定：1、 能运用常用算法和简朴数据构造解决实际问题2、 能从算法本质出发，分析有关算法之间的本质联系3、 具有初步的数学建模能力题例：试题名：摆花详见NOIP普及组六级原则（NOIP提高组全国前50%） 定义：掌握基本的数据构造知识，可以根据实际需求设计算法编写程序，解决问题。

知识规定：1、 树、图的存储2、 哈希表、集合数据构造3、 图的最短路，生成树算法，有向图的拓扑排序算法4、 动态规划的常用模型，分治方略，多种排序算法5、 可重集组合，二项式定理，数列与级数，归纳与递推，容斥原理，函数的持续性、函数的单调性和极值能力规定：1、 能对某些算法和数据构造估算时间复杂度和空间复杂度2、 能根据实际问题的模型选择合适的算法和数据构造来解决问题3、 具有知识收集和知识管理的能力题例： 试题名：最优贸易 详见NOIP提高组七级原则（NOIP提高组全国前20%） 定义：综合运用算法和数据构造编写程序，解决问题 知识规定：1、 并查集，线段树，哈弗曼树，二叉排序树，二叉堆2、 图的连通性算法，最短路，最小生成树的优化算法，二分图的构造、鉴定及匹配，搜索算法的优化，扩展欧几里得算法3、 中国剩余定理，剩余类，概率基本知识，解析几何基本知识能力规定：1、 能根据时间和空间复杂度的规定灵活构造算法和数据构造解决实际问题2、 具有较强的程序代码实现能力3、 具有较强的归纳、总结和体现能力题例： 试题名：关押罪犯 详见NOIP提高组八级原则（NOI铜牌） 定义：掌握高档数据构造知识，能运用恰当算法编写程序，解决较复杂问题。

知识规定：1、 树状数组，字典树，优先队列，平衡树2、 网络流算法，复杂的分治思想，树形动态规划，状态压缩动态规划，二分图的匹配，启发式搜索3、 矩阵概念及其基本运算，线性方程组的解法，迭代法，费马小定理和欧拉定理，母函数能力规定：1、 能针对复杂问题建立清晰的数学模型2、 能运用数学知识、高档数据构造和算法解决复杂的问题3、 能根据需要，开展基于写作的学习和研究题例： 试题名：能量采集 详见NOI九级原则（NOI银牌） 定义：具有对问题进行抽象和数学建模能力，能选用合适的数据构造和算法编写程序，解决较难问题 知识规定：1、 块状链表，后缀数组，后缀树，复杂的线段树2、 动态规划优化，模拟退火算法3、 计算几何基本知识（点积、叉积、凸包、半平面等知识及应用），数学盼望能力规定：1、 能针对疑难问题建立清晰的数学模型2、 能灵活运用数学知识、高档数据构造和算法解决疑难问题3、 具有发现问题、解决问题的摸索研究能力题例： 试题名：直线和点 文献名：line 试题描述：平面的n条直线将平面分割成了若干区域，给出m个点，求每个点所在区域的面积为了避免浮现面积无穷大的状况，有额为的四条直线框定了平面区域的大小，分别是x=L，y=L，x=-L，y=-L。

其中L是给定的正实数，所有的点都在这个框定的区域内此外为了避免精度问题，任意一种点到任意一条直线的距离>10^-7 输入数据： 输入文献名为line.in 第一行两个正整数和一种正实数，n,m,L，意义如上所述 第2~n-1行每行三个实数A，B，C表达直线的方程为Ax+By+C=0 第n+2~n+m+1行每行两个实数x,y表达点的坐标 输出数据： 输出文献名为line.out 按输入的顺序输出每个点所在的区域面积，每个一行，保存2为小数 输入样例： 2 4 3 1 1 -1 -1 1 -1 0 2 -2 1 2 1 0 0 输出样例： 4.00 8.50 8.50 15.00 数据范畴： 对于20%的数据，n,m<=10 对于40%的数据，n,m<=300 对于100%的数据，n<=500,m<=100000 对于100%的数据，输入数据的绝对值<=10^7且最多保存2位小数十级原则（NOI金牌） 定义：具有一定的提出问题、解决问题的研究能力，能构造算法与数据构造，解决开放性问题 知识规定：1、 最小树形图，自动机，动态树，树套树，一般图的匹配。

2、 双重动态规划，基于连通性的动态规划，线性规划，极大极小搜索算法3、 三维计算几何，组合游戏中的NIM问题和SG函数，群的概念，置换群，Burnside引理，Polya原理，莫比乌斯反演定理，FFT能力规定1、 具有发明性地运用数据构造和算法解决开放性问题的能力2、 具有很强的代码编写能力3、 具有提出问题、并开展有关研究的创新能力题例： 试题名：管道取珠 详见NOI。