NOIP 提高组 考试内容

　　全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲

　　竞赛形式和成绩评定

　　联赛分两个年龄组：初中组和高中组。每组竞赛分两轮：初试和复试。

　　初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Pascal或Basic或C/C++。各省市初试成绩在本赛区前百分之十五的学生进入复赛。

　　复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Pascal、Basic、C/C++或Java。各省市竞赛的等第奖在复试的优胜者中产生。为鼓励学生多学习较新技术，使用C/C++或Java的学生可以得到适当加分

　　试题形式

　　每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高，以体现年龄特点和层次要求。

　　初试：初试全部为笔试，满分100分。试题由四部分组成：

　　选择题：共20题，每题1.5分，共30分。每题有5个备选方案，前10个题为单选题（即每题有且只有一个正确答案），后10题为复选题（即每题有1至5个正确答案，只有全部选对才得分）。

　　问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。

　　程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（不一定有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。

　　程序完善题：共2题，每题14分，共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。

　　复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10分，累计分即为该道题的得分。

　　试题的知识范围

　　一、初赛内容与要求:

　　计算机的基本常识
　　1.计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）
　　2.信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
　　3.信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
　　4.信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
　　5.信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）
　　6.人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
　　7.信息技术的新发展、新特点、新应用等。

　　计算机的基本操作
　　1.WINDOWS和LINUX的基本操作知识
　　2.互联网的基本使用常识 （网上浏览、搜索和查询等）
　　3.常用的工具软件使用（文字编辑、电子邮件收发等）

　　程序设计基本知识
　　数据结构
　　1.程序语言中基本数据类型(字符、整数、长整数、浮点)
　　2.浮点运算中的精度和数值比较
　　3.一维数组（串）与线性表
　　4.记录类型（PASCAL）/ 结构类型（C）

　　程序设计
　　1.结构化程序设计的基本概念
　　2.阅读理解程序的基本能力
　　3.具有将简单问题抽象成适合计算机解决的模型的基本能力
　　4.具有针对模型设计简单算法的基本能力
　　5.程序流程描述（自然语言/伪码/NS图/其他）
　　6.程序设计语言（PASCAL/C/C++，2003年仍允许BASIC）

　　基本算法

　　处理
　　1.初等算法（计数、统计、数学运算等）
　　2.排序算法（冒泡法、插入排序、合并排序、快速排序）
　　3.查找（顺序查找、二分法）
　　4.回溯算法

　　二、复赛内容与要求：

　　在初赛的内容上增加以下内容：

　　数据结构
　　1.指针类型
　　2.多维数组
　　3.单链表及循环链表
　　4.二叉树
　　5.文件操作（从文本文件中读入数据，并输出到文本文件中）

　　程序设计
　　1.算法的实现能力
　　2.程序调试基本能力
　　3.设计测试数据的基本能力
　　4.程序的时间复杂度和空间复杂度的估计

　　算法处理
　　1.离散数学知识的应用（如排列组合、简单图论、数理逻辑）
　　2.分治思想
　　3.模拟法
　　4.贪心法
　　5.简单搜索算法（深度优先 广度优先）搜索中的剪枝
　　6.动态规划的思想及基本算法

初赛分为4大题：
1、选择（多选）
2、问题求解（一些数学题）
3、看程序写结果
4、完善程序
（注：3和4都比普及组难）
复赛一共有4题，每题总分100分，前三题10个测试点，每个点10分，第4题一般有20个测试点，每个点5分
内容不一定，你可以去找一些历年真题来做做