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

CCF青少年计算机程序设计评级标准 一级标准 定义：了解什么是计算机程序，能够编写计算机程序解决简单问题。 知识要求： 程序的基本结构。 标识符和关键字。 基本数据类型。 常量和变量。 算术表达式和关系表达式。 整除，求余运算，常用数学函数。 赋值语句，输入输出语句，复合语句，条件语句（不嵌套），循环语句（不嵌套）。 能力要求： 能用自然语言描述解决简单问题的方法和步骤。 能用顺序，分支，循环语句实现知识要求中的方法和步骤，编写完整程序。 初步理解算法的意义。 题例： 试题名：求最小，最大数 试题描述： 给出N个数，请找出这N个数中的最小数和最大数。 输入数据： 第1行，一个整数n，n=1000。 接下来的一行，包含n个数，两个数之间用一个空格分隔。 输出数据： 第1行，最小数。 第2行，最大数。 输入样例： 4 1 2 3 4 输出样例： 1 4 二级标准 定义：了解什么是算法，能够用程序设计语言实现简单算法，解决问题。 知识要求： 逻辑表达式。 条件嵌套，循环嵌套，数组。 枚举，简单排序，简单查找算法。 素数与合数，最大公约数，最小公倍数，互质数。 能力要求： 能用简单枚举算法解决实际问题，能对数据进行简单排序和查找。 具备独立编写和调试简短程序的能力。 题例： 试题名：求第k小数 试题描述： 给出N个数，请找出第K小的数并输出该数值。 输入数据： 第1行，两个整数n,k，n,k=1000。 接下来的一行，包含n个数，两个数之间用1个空格分隔。 输出数据： 只有1行，为第k小数。 输入样例： 4 3 1 2 3 4 输出样例： 3 三级标准 定义：具有较强的程序实现能力，使用一种计算机程序设计语言编写程序，解决问题。 知识要求： 数制及其转化，信息编码，位运算。 字符串类型。 子程序。 递归。 逻辑运算，整数的质因数分解，随机函数。 筛选法，欧几里得算法 能力要求： 全面掌握一种计算机程序设计语言。 具有运用简单数学知识编写程序解决问题的能力。 题例： 试题名：分解质因数 试题描述： 给一个整数N，将N写成质因数的乘积。 输入数据： 一个整数n,n=100000。 输出数据： 质因数乘积表达式（请将质因数按从小到大顺序输出） 输入样例： 12 输出样例： 12=2*2*3 四级标准（NOIP普及组全国前70%） 定义：了解几种常用的算法，并运用这些算法编写程序，解决问题。 知识要求： 结构类型，文件操作。 数据类型的内在含义。 贪心法，递推，回溯法，模拟算法。 简单的字符串处理。 集合及集合的运算，加法原理和乘法原理，简单的排列和组合。 能力要求： 能根据实际额问题选择合适的数据类型。 能运用贪心、递推、回溯、模拟等算法解决实际问题。 能独立设计简单的测试数据，测试自己程序的正确性。 题例： 试题名：校门外的树 详见各oj，laoj也有。 五级标准（NOIP普及组全国前40%） 定义：掌握简单数据结构知识，并结合已学算法和数学知识编写程序，解决问题。 知识要求： 指针类型。 一般线性表，队列，堆栈，二叉树的存储和遍历。 排列和组合，高精度数值的处理。 二分算法，快速排序，深度优先有哪些信誉好的足球投注网站，宽度优先有哪些信誉好的足球投注网站，简单动态规划。 圆排列，可重集排列，鸽笼原理，素因数分解，幂函数，指数函数，对数函数，三角函数，模运算，不等式基础知识。 能力要求： 能运用常用算法和简单数据结构解决实际问题。 能从算法本质出发，分析相关算法之间的本质联系。 具备初步的数学建模能力。 题例： 试题名：摆花 详见NOIP2013普及组 六级标准（NOIP提高组全国前50%） 定义：掌握基本的数据结构知识，能够根据实际需求设计算法编写程序，解决问题。 知识要求： 树、图的存储。 哈希表、集合数据结构。 图的最短路，生成树算法，有向图的拓扑排序算法。 动态规划的常见模型，分治策略，各种排序算法。 可重集组合，二项式定理，数列与级数，归纳与递推，容斥原理，函数的连续性、函数的单调性和极值。 能力要求： 能对一些算法和数据结构估算时间复杂度和空间复杂度。 能根据实际问题的模型选择合适的算法和数据结构来解决问题。 具备知识收集和知识管理的能力。 题例： 试题名：最优贸易 详见NOIP2009提高组 七级标准（NOIP提高组全国前20%） 定义：综合运用算法和数据结构编写程序，解决问题。 知识要求： 并查集，线段树，哈弗曼树，二叉排序树，二叉堆。 图的连通性算法