noip提高组初赛知识点（noip2016提高组复赛试题）

本文目录一览：

• 1、NOIP 提高组 考试内容
• 2、拜请各位神牛提供一些NOIP初赛技巧
• 3、c语言各种算法详细讲解及NOIP提高组初赛的复习资料，要全，急！！！
• 4、noip需要准备哪些方面的基础知识。复赛需要做哪些类型的题目（提高组）？
• 5、noip 提高组 需要掌握哪些数学及计算机基础知识
• 6、noip初赛选择题会考些什么内容

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.动态规划的思想及基本算法

拜请各位神牛提供一些NOIP初赛技巧

全国青少年信息学奥林匹克联赛大纲（节选）一、总则

由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛（NOIP）是全国信息学奥林匹克竞赛（NOI）整个系列中的一个重要组成部分，旨在向中学生普及计算机基础知识，培养计算机科学和工程领域的后备人才。普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些核心内容有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。对学生的能力培养将注重以下的几个方面：

● 想象力与创造力；

● 对问题的理解和分析能力；

● 数学能力和逻辑思维能力；

● 对客观问题和主观思维的口头和书面表达能力；

● 人文精神：包括与人的沟通能力，团队精神与合作能力，恒心和毅力，审美能力等。

二、命题程序和组织机构

命题是选拔过程的重要一环，同时对计算机的普及内容起着导向性的作用。命题应注重趣味性、新颖性、知识性、应用性和中学生的心智特点，不直接从大学专业教材中选题。

在命题和审题工作中，坚持开放和规范的原则。在NOI科学委员会主持下成立的联赛命题委员会负责命题工作，命题委员会成员主要来自参加联赛的省（包括直辖市、自治区、下同。每个省最多派一名委员），也可来自社会计算机界。联赛命题委员会的主要职责是提供联赛的备选题目，并承担对所提供的题目保密的责任。

1. 联赛命题委员会委员应具备如下资格：

● 从事一线计算机教学或信息学奥赛辅导工作两年（含）以上；

● 有精力和时间从事该项工作；

● 对此项工作有兴趣并愿意作为志愿者从事NOIP命题及其相关工作。

2. 联赛命题委员会委员的产生过程：

● 本人提出申请（填写表格）；

● 中学教师需所在单位同意或省奥赛主管部门同意；

● 科学委员会批准，由中国计算机学会颁发聘书（每一聘期为两年）。

3. 联赛命题委员会委员的职责：

● 每年为NOIP提供备选题题目若干，在9月1日之前提交科学委员会；

● 备选试题的保密期为2年，在该段时间内不得泄密或另作他用；

● 搜集本省信息学奥赛的有关信息并向科学委员会通报；

题目一经提交，即表明同意授权中国计算机学会科学委员会全权处理，包括使用、修改和出版。无论是委员提交的题目还是科学委员会直接提交的题目，试题版权均归中国计算机学会所有，试题原型一旦被正式采用，中国计算机学会将出具试题录用证明。科学委员会确定当年的联赛试题，这些试题可能从备选题库中选取并做适当修改后成型，也可能直接命题。

三、竞赛形式和成绩评定

联赛分两个等级组：普及组和提高组。每组竞赛分两轮；初试和复试。

● 初试形式为笔试，测重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。初试为资格测试，各省初试成绩在本赛区前15%的学生进入复赛。

● 复试形式为上机，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。各省联赛的等第奖在复试的优胜者中产生。

比赛中使用的程序设计语言是：

● 2003年：初赛：BASIC、PASCAL或C/C++；复赛：BASIC、PASCAL或C/C++。

● 2004年：初赛：BASIC、PASCAL或C/C++；复赛：PASCAL或C/C++。

● 2005年及之后：初赛： PASCAL或C/C++；复赛：PASCAL或C/C++。

每年复赛结束后，各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。经复审确认后，由中国计算机学会报送中国科协和教育部备案。中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见，各省可按照成绩确定获奖名单。

四、试题形式

每次联赛的试题分四组：普及组初赛题A1、普级组复赛题A2、提高组初赛题B1和提高组复赛题B2。其中，A1和B1类型相同，A2和B2类型相同，但题目不完全相同，提高组难度高于普及组。

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

1. 选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。2. 问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。

3. 程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。

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

● 复赛：复赛的题型和考试形与NOI类似，全部为上机编程题，但难度比NOI低。题目包括4道题，每题100分，共计400分。每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10-20分，累计分即为该道题的得分。

五、试题的知识范围

（一） 初赛内容与要求：

计算机基本的常识

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. 动态规划的思想及基本算法

注：本大纲由中国计算机学会NOI科学委员会制定和修订，并由其负责解释。

本大纲于2003年6月16日科学委员会审议通过，从2003年7月10日起执行。

c语言各种算法详细讲解及NOIP提高组初赛的复习资料，要全，急！！！

noip提高组的试题总体来说不是很难，

主要是好好熟悉基本概念，

基础题的比重占了很大比例，难题很少。

离散数学和数据结构的知识可以看看屈婉玲写的那一本《离散数学》，以及严蔚敏的《数据结构》，不要看老外的书（虽然它们很好，但不适合noip考试），noip不会这么深入的考察。

不用太深入，只要熟悉常见的算法（比如图和树的常见遍历算法以及最短距离算法），还有比较重要的是集合论，总之离散数学不要太过于纠缠细节，noip考试不是考博，不会出男的算法分析题。

计算机的基础知识比较零散，各种常见硬件的原理可以在网上搜到。同样，大概知道工作远里就行，不要过分深入。

C语言编程部分，随便找一本国人写的入门书就行，主要是要知道各种基本数据结构如何用C语言实现，以及会编写简单的算法就行（如查找排序遍历）。

全是自己打的字，我08年参加noip的经验就这些，希望对你有用。

noip需要准备哪些方面的基础知识。复赛需要做哪些类型的题目（提高组）？

Noip算法（小超）

以下用n表示图的点数，m表示边数，k表示一个常数，log均以2为底数，存储边都采用边表。

【模拟】

高精度加、减、乘，除应该不需要

表达式求值（中缀转后缀，栈的操作）

【图论】

图的表示：邻接矩阵，邻接表，边表

单源最短路：dijkstra（O(n2)），bellman（spfa优化，O(km)）

传递闭包和floyd

最小生成树算法：prim（O(n2)），kruskal（O(m log m)）

拓扑排序（O(m)）

欧拉路（边一次）

汉密尔顿回路（点一次）

强连通分量

匹配算法（最大匹配，最小点覆盖，最小路径覆盖，最大独立集）

网络流算法（最大流dinic，最小费用流spfa）

差分约束系统

【树】

树的先序、中序、后序遍历

树中的最长路（两遍bfs）

特殊的树：二叉树

树形动态规划

并查集

字母树

【搜索】

深搜，一般需要剪枝，有可行性剪枝和最优性剪枝两种经常考。还有迭代深搜。

宽搜，双向广搜，估价函数。

【动态规划】

背包问题：01背包，无限背包，多重背包，有依赖的背包，二维费用背包。（参照背包九讲）

树形动态规划

状态压缩的动态规划

最长不下降子序列

最长公共子序列和最长公共子串

动态规划的优化（快速幂，改变状态，优化转移，单调性，四边形不等式）

【贪心】

也有一些经典的模型，如取线段的问题，一般从小规模数据找规律，再适当的有一些证明。

【排序】

选择排序、冒泡排序

快速排序（快排）、堆排序

插入排序

希尔排序

归并排序

【分治】

二分查找

二分答案（这个好像不是分治）

【串】

串的基本操作

Kmp（字串匹配）

Kmp扩展

AC自动机

【数论】

欧几里得算法，最大公约数和最小公倍数

判断质数（sqrt式与筛法求素数）

进制转换

同余定理

中国剩余定理

概率与期望

欧拉函数

【几何】

线段相交

凸包（水平序和极角序）

半平面交

【有序表】

顺序表、链表、块状链表

线段树及其基本操作

树状数组

平衡树（sbt、treap、splay）

后缀数组

【其他】

Hash

随机化算法

矩形切割（与线段树的比较）

Lca（最近公共祖先）与rmq（区间最值）

高斯消元

noip 提高组 需要掌握哪些数学及计算机基础知识

计算机基础知识就是为了过初赛的，你只要考过普及组就知道了（顺便说一下你如果没考过普及组还是先别考提高，初赛瞎考考保证过！)然后数学知识个人认为要会组合，小学奥数学过的应该知道，还要会递归（递推）。其实考noip，所谓数学知识就是思维能力，在提高组复赛中很重要

noip初赛选择题会考些什么内容

NOIP初赛考的知识点，大纲上有3块：计算机基本常识、计算机基本操作、程序设计基本知识。具体来说：选择题考查的是计算机基本常识、基本操作和程序设计中的一些基本数据结构与基本算法；而填空题更加重视能力（尤其是队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理等）的考查；读程序写运行结果考察的是对程序的理解和跟踪，重在分析推理能力。读程序的4条题目往往有一定的层次，试卷中给出程序的并不复杂，语句的含义容易明白，但是悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案，机械模仿计算机手工逐步算出结果的同学往往做的很慢，造成时间不够，而且容易失误；完善程序更是考察程序设计能力，尤其是在明确算法和数据结构的条件下，如何编程。读程序和完善程序，需要在平时的学习中提高，经常阅读、讨论和研究别人的优秀程序，提高自己的理解力和速度。