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

CCF青少年计算机程序设计评级标准一级标准定义：了解什么是计算机程序，能够编写计算机程序解决简单问题。知识要求：1、 程序的基本结构。2、 标识符与关键字。3、 基本数据类型。4、 常量与变量。5、 算术表达式与关系表达式。6、 整除，求余运算，常用数学函数。7、 赋值语句，输入输出语句，复合语句，条件语句（不嵌套），循环语句（不嵌套）。能力要求：1、 能用自然语言描述解决简单问题的方法与步骤。2、 能用顺序，分支，循环语句实现知识要求中的方法与步骤，编写完整程序。3、 初步理解算法的意义。题例： 试题名：求最小，最大数 试题描述： 给出N个数，请找出这N个数中的最小数与最大数。 输入数据： 第1行，一个整数n，n<=1000。接下来的一行，包含n个数，两个数之间用一个空格分隔。输出数据：第1行，最小数。第2行，最大数。输入样例：41 2 3 4输出样例：14二级标准定义：了解什么是算法，能够用程序设计语言实现简单算法，解决问题。知识要求：1、 逻辑表达式。2、 条件嵌套，循环嵌套，数组。3、 枚举，简单排序，简单查找算法。4、 素数与合数，最大公约数，最小公倍数，互质数。能力要求：1、 能用简单枚举算法解决实际问题，能对数据进行简单排序与查找。2、 具备独立编写与调试简短程序的能力。题例：试题名：求第k小数试题描述： 给出N个数，请找出第K小的数并输出该数值。输入数据：第1行，两个整数n,k，n,k<=1000。接下来的一行，包含n个数，两个数之间用1个空格分隔。输出数据：只有1行，为第k小数。输入样例：4 31 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、 具备初步的数学建模能力。题例：试题名：摆花详见NOIP2013普及组六级标准（NOIP提高组全国前50%）定义：掌握基本的数据结构知识，能够根据实际需求设计算法编写程序，解决问题。知识要求：1、 树、图的存储。2、 哈希表、集合数据结构。3、 图的最短路，生成树算法，有向图的拓扑排序算法。4、 动态规划的常见模型，分治策略，各种排序算法。5、 可重集组合，二项式定理，数列与级数，归纳与递推，容斥原理，函数的连续性、函数的单调性与极值。能力要求：1、 能对一些算法与数据结构估算时间复杂度与空间复杂度。2、 能根据实际问题的模型选择合适的算法与数据结构来解决问题。3、 具备知识收集与知识管理的能力。题例：试题名：最优贸易详见NOIP2009提高组七级标准（NOIP提高组全国前20%）定义：综合运用算法与数据结构编写程序，解决问题。知识要求：1、 并查集，线段树，哈弗曼树，二叉排序树，二叉堆。2、 图的连通性算法，最短路，最小生成树的优化算法，二分图的构造、判定及匹配，搜索算法的优化，扩展欧几里得算法。3、 中国剩余定理，剩余类，概率基础知识，解析几何基础知识。能力要求：1、 能根据时间与空间复杂度的要求灵活构造算法与数据结构解决实际问题。2、 具备较强的程序代码实现能力。3、 具备较强的归纳、总结与表达能力。题例：试题名：关押罪犯详见NOIP2010提高组八级标准（NOI铜牌）定义：掌握高级数据结构知识，能运用恰当算法编写程序，解决较复杂问题。知识要求：1、 树状数组，字典树，优先队列，平衡树。2、 网络流算法，复杂的分治思想，树形动态规划，状态压缩动态规划，二分图的匹配，启发式搜索。3、 矩阵概念及其基本运算，线性方程组的解法，迭代法，费马小定理与欧拉定理，母函数。能力要求：1、 能针对复杂问题建立清晰的数学模型。2、 能运用数学知识、高级数据结构与算法解决复杂的问题。3、 能根据需要，开展基于写作的学习与研究。题例：试题名：能量采集详见NOI2010九级标准（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，意义如上所述。第2n-1行每行三个实数A，B，C表示直线的方程为Ax+By+C=0。第n+2n+m+1行每行两个实数x,y表示点的坐标。输出数据：输出文件名为line.out。按输入的顺序输出每个点所在的区域面积，每个一行，保留2为小数。输入样例：2 4 31 1 -1-1 1 -10 2-2 1 2 1 0 0输出样例：数据范围：对于20%的数据，n,m<=10。对于40%的数据，n,m<=300。对于100%的数据，n<=500,m<=100000。对于100%的数据，输入数据的绝对值<=107且最多保留2位小数十级标准（NOI金牌）定义：具有一定的提出问题、解决问题的研究能力，能构造算法与数据结构，解决开放性问题。知识要求：1、 最小树形图，自动机，动态树，树套树，一般图的匹配。2、 双重动态规划，基于连通性的动态规划，线性规划，极大极小搜索算法。3、 三维计算几何，组合游戏中的NIM问题与SG函数，群的概念，置换群，Burnside引理，Polya原理，莫比乌斯反演定理，FFT。能力要求1、 具备创造性地运用数据结构与算法解决开放性问题的能力。2、 具备很强的代码编写能力。3、 具备提出问题、并开展相关研究的创新能力。题例：试题名：管道取珠详见NOI2009第 11 页