NOIP初赛知识点复习总结 本文关键词：初赛，知识点，复习，NOIP
NOIP初赛知识点复习总结 本文简介：NOIP2011初赛指导课程大纲NOIP初赛情况的简单分析基础知识二叉树图排列组合程序阅读题程序填空题总结初赛试卷题型分析单项选择15分不定项选择15分（多选少选均不得分）问题求解10分阅读程序32分完善程序28分初赛试卷题型分析初赛考的知识点，大纲说：计算机基本常识，基本操作和程序设计基本知识。选
NOIP初赛知识点复习总结 本文内容：
NOIP2011初赛指导
课程大纲
NOIP初赛情况的简单分析
基础知识
二叉树
图
排列组合
程序阅读题
程序填空题
总结
初赛试卷题型分析
单项选择
15分
不定项选择
15分（多选少选均不得分）
问题求解
10分
阅读程序
32分
完善程序
28分
初赛试卷题型分析
初赛考的知识点，大纲说：计算机基本常
识，基本操作和程序设计基本知识。选择
题考查的是知识，而问题解决题、填空更
加重视能力的考查。
一般说来，选择题是不需要单独准备
的
，也无从准备。只要多用心积累就可以
了。到是问题解决题目比较固定，大家应
当多作以前的题目。写运行结果需要多做
题目，培养良好的程序阅读和分析能力，
而完善程序最好总结一下以前题目常常要
你填出来的语句类型。
初赛试卷题型分析
1.选择题一般它们是比较容易得分的，一共30分，不可
错过！
近几年来，初赛的考查范围有了很大的变化，越来
越紧跟潮流，需要大家有比较广泛的知识，包括计算机
硬件，软件，网络，数据结构（例如栈，队列，排序算
法），程序设计语言以及一些基本的数学知识和技巧
（例如排列组合等）。
2.填空、问题解决
这部分题目对数学要求要高一点，往往考查的是代数
变形、集合论、数列（一般是考递推），也考查
一些算
法和数据结构知识。建议大家多花一点时间做，尽量做
对。
初赛试卷题型分析
3.
阅读程序写出运行结果
占的分数多，但得分率却不高，较易失分，一
旦结果不正确，将丢失全分。
这种题型主要考察选手：
①
程序设计语言的掌握能力
②
数学运算能力
③
耐心、细心的心理品质一般做这类题目的
关键在于能够分析程序的结构及程序段的功能，
找出程序目的，即这个程序想干什么。
初赛试卷题型分析
完成这类题目的一般方法和步骤是：
①
从头到尾通读程序，大致掌握程序的算法；
②
通过给程序分段，清理程序的结构和层次，达到读懂程序
的目的；
③
阅读程序中特别注意跟踪主要变量值的变化，也可以用列
表的方法，了解变量变化和程序运行的结果，要注意发现规律。
迄今为止考过的题目还没有“乱写”的，总有一点“写作目的”
的。抓住了它，得出答案就变得很容易了，而且对结果也会有信
心。写程序运行结果大纲规定是必考的。试卷中给出的程序并不
复杂，语句的含义容易明白，因此悟性好的选手总是很快就能体
会到程序的设计思路并得出正确的答案，而机械模仿计算机硬算
出结果的同学往往做的慢的多，而且容易失误。
初赛试卷题型分析
4.完善程序
这部分题目得分率似乎不高。没关
系，尽量做吧。把一些简单的填好就行了。
建议大家把以前的初赛题目都做做。
常常让大家填的是：
①初始化
②一些明显的动作：
a.结果没有储存在需要的地方。
b.累加器没有做加法
c.输出
③关键动作。
在算法描述中出现的比较关键的步骤。例如交换
排序程序的“交换”操作等很明显需要完成的操作。
分析方法和写运行结果类似，注意分析变量和
程序结构，理解变量和模块的作用是解题的关键。
进制转换
1．二进制与十进制间的相互转换：
（1）二进制转十进制
方法：“按权展开求和”
例：
（1011.01）2
＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2）10
＝（8＋0＋2＋1＋0＋0.25）10
＝（11.25）10
规律：个位上的数字的次数是0，十位上的数字的次数是
1，，依次递增，而十
分位的数字的次数是-1，百分位上数字的次数是-
2，，依次递减。
注意：不是任何一个十进制小数都能转换成有限位的二进
制数。
进制转换
进制转换
1．二进制与十进制间的相互转换：
（1）二进制转十进制
方法：“按权展开求和”
例：
（1011.01）2
＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2）10
＝（8＋0＋2＋1＋0＋0.25）10
＝（11.25）10
规律：个位上的数字的次数是0，十位上的数字的次数是
1，，依奖递增，而十分位的数字的次数是-1，百分
位上数字的次数是-2，，依次递减。
注意：不是任何一个十进制小数都能转换成有限位的二进
制数。
进制转换
以下二进制数与十进制数23.456最接近的
是（）
A
10111.0101B
11011.1111
C
11011.0111D
10111.0111
E.10111.1111
D
把下面的数转换为10进制数再进行比较
位运算
位运算主要有：
按位与(
i
a[j+1])//这就是比较
公式：
最少比较次数
=
┏
log
2
n!┓
10．将
5
个数的序列排序，不论原先的顺
序如何，最少都可以通过（B）次比较，
完成从小到大的排序。
A.
6B.
7C.
8D.
9E.
10
排序
思考:最坏情况下最少需要交换多少次?
n-1
1.
将数组{32,74,25,53,28,43,86,47}
中的元素按从小到大的顺序排列，每
次可以交换任意两个元素，最少需要
交换___5__次。
排序
稳定排序包括：
插入排序、冒泡排序
不稳定排序包括：
选择排序、希尔排序、快速排序、堆排序
时间复杂度：
冒泡排序O(n2)，选择排序O(n2)，快速排
序O(nlog2n)，堆排序O(nlog2n)
二叉树
定义：n个结点的有限集，每个结点至多
只有两棵子树，子树也是二叉树。每个结
点可以有左孩子和右孩子，顺序不可颠倒。
概念：
度：某个结点孩子的个数
叶子：度为0的结点
深度：二叉树的层数
满二叉树：深度为n且结点数为2n-1的二叉
树
完全二叉树：深度为k，1~k-1层为满二叉
树，第k层叶子节点集中在左边的二叉树
二叉树
二叉树的遍历：先根，中根，后根遍历以
及深度优先遍历和广度优先遍历，具体方
法参看资料。
根据前根中根或中根后根遍历确定一颗二
叉树的形态以及另一种遍历。
二叉树知识点补充
n个结点所组成的不同形态的二叉树数目
为：
C(2n,n)/(n+1)
二叉树
二叉树T，已知其前序遍历序列为1
2
4
3
5
7
6，中序遍历序列为4
2
1
5
7
3
6，则
其后序遍历序列为（
B）。
A.
4
2
5
7
6
3
1B.
4
2
7
5
6
3
1
C.
4
2
7
5
3
6
1D.
4
7
2
3
5
6
1
E.
4
5
2
6
3
7
1
二叉树
已知7个节点的二叉树的先根遍历是1
2
4
5
6
3
7(数字为结点的编号，以下同)，
后
根遍历是4
6
5
2
7
3
1，
则该二叉树的可
能的中根遍历是（
ABD
）
A.
4
2
6
5
1
7
3B.
4
2
5
6
1
3
7
C.
4
2
3
1
5
4
7D.
4
2
5
6
1
7
3
只知道前根遍历和后根遍历是无法确定一棵二叉树的，
所以这题采用反推验证
二叉树
4.
完全二叉树的结点个数为4
N
+
3，则
它的叶结点个数为（E）。
A.
2
NB.
2
N
-
1
C.
2
N
+
1D.
2
N
-
2
E.
2
N
+
2
4n+3=2*2(n+1)
-
1，多么熟悉的公式啊
2*叶子结点数-1，这不是满二叉树的结点数
么？
二叉树
8．高度为
n
的均衡的二叉树是指：如果
去掉叶结点及相应的树枝，它应该是高度
为
n-1
的满二叉树。在这里，树高等于叶
结点的最大深度，根结点的深度为
0，如
果某个均衡的二叉树共有
2381
个结点，
则该树的树高为（B）。
A.
10B.
11C.
12D.
13
E.
210
–
1
211
void
fun(inta,intb)
{
}
intk;
k=a;
a=b;
b=k;
fun是耍人的意思，其实根
本没交换两个变量的值。当
时很多人被fun了
int
main(
)
{
}
int
a=3,b=6,*x=
fun(x,y);
printf(“No.1:
%d,%d
“,a,b);
fun(
printf(“No.2:
%d,%d/n“,a,b);
return
0;
程序填空
这种题与编程经验和算法学习的程度有
关，拿得一分是一分。不过对于编程经验
不足和算法练习少的人来说也不是没分可
拿。比如说——
for(i=n;
⑤
)
printf(“%1d“,gr[i]);
/*
在
“%1d“中出现的是数字1，不是字
母l/
printf(“/n“);
虽然无头无尾，也没有题目描述，但是一眼
就可以看出这个是个输出结果的语句。于是
乎——
i>0;i--
凡此种种，不胜枚举……抓住机会！
程序填空总结
1、分析语句是干什么的，回到开头讲的内容：
①初始化
②一些明显的动作：
a.结果没有储存在需要的地方。
b.累加器没有做加法
c.输出
③关键动作。
2、不懂就根据上下文猜
3、不写白不写，蒙一下总是好的。
4、千万注意开头和结尾，常常有送分题目喔！
几个小问题
20.
近20年来，
许多计算机专家都大力推崇
递归算法，认为它是解决较复杂问题的强有
力的工具.
在下列关于递归的说法中，
正确
的是（
AC
）。
A.
在1977年前后形成标准的计算机高级语言
“FORTRAN77“禁止在程序使用递归，
原因
之一是该方法可能会占用更多的内存空间.
B.
和非递归算法相比，
解决同一个问题，
递归算法一般运行得更快一些
C.
对于较复杂的问题，
用递归方式编程往往
比非递归方式更容易一些
D.
对于已定义好的标准数学函数sin(x)，
应
用程序中的语句“y=sin(sin(x));”就是一种
递归调用
16.在下列各软件中，属于
NOIP
竞赛（复
赛）推荐使用的语言环境有（）。
A.
gccB.
g++
ABD
C.
Turbo
CD.
free
pascal
16.在下列各软件中，属于
NOIP
竞赛（复
赛）推荐使用的语言环境有（）。
A.
gcc/g++B.
Turbo
Pascal
C.
Turbo
CD.
free
pascal
18.
在下列关于计算机语言的说法中，正
确的有（
AB
）。
A.
Pascal和C都是编译执行的高级语言
B.
高级语言程序比汇编语言程序更容易从
一种计算机移植到另一种计算机上
C.
C++是历史上的第一个支持面向对象的
计算机语言
D.
高级语言比汇编语言更高级，是因为它
的程序的运行效率更高
3.在下面各世界顶级的奖项中，为计算机
科学与技术领域作出杰出贡献的科学家设
立的奖项是（）。
A.
沃尔夫奖B.
诺贝尔奖C.
菲尔
兹奖
D.
图灵奖E.
南丁格尔奖
D
2.
在关系数据库中,存放在数据库中的数
据的逻辑结构以()为主。
A.
二叉树B.
多叉树C.
哈希表
D.
B+树E.
二维表
E
19.
在下列关于计算机算法的说法
中，正确的有（
BD
）。
A.
一个正确的算法至少要有一个输入
B.
算法的改进，在很大程度上推动了
计算机科学与技术的进步由
C.
判断一个算法的好坏，主要依据它
在某台计算机上具体实现时的运行时
间
D.
目前仍然存在许多涉及到国计民生
的重大课题，还没有找到能够在计算
机上实施的有效算法
19.
下列活动中属于信息学奥赛系列活动
的是（
）。
A.
NOIP
B.
NOI
C.
IOI
D.
冬令营
E.
国家队选拔赛
ABCDE
16.
处理器A
每秒处理的指令数是处理器B
的2
倍。某一特定程序P
分别编译为处理器A
和处理器B
的指令，编译结果处理器A
的指令数
是处理器B
的4
倍。已知程序P
的算
法时间复杂度为O(n2)，如果处理器A执行程序P
时能在一小时内完成的输入规模为n，
则处理器B执行程序P时能在一小时内完成的输
入规模为（
）。
A.
4
n
B.
2
n
C.
n
D.
n
/
2
E.
n
/
4
B
彩色显示器所显示的五彩斑斓的色彩，是
由哪三色混合而成的（）。
A.
红B.
白C.
蓝D.
绿E.
橙
不懂你的物理就没学好。
美籍匈牙利数学家冯·诺依曼对计算机科学发展
所做出的贡献包括（）。
A提出理想计算机的数学模型，成为计算机科学
的理论基础。
B提出存储程序工作原理，对现代电子计算机的
发展产生深远影响。
C设计出第一台具有存储程序功能的计算机
EDVAC。
D采用集成电路作为计算机的主要功能部件。
E指出计算机性能将以每两年翻一番的速度向前
发展。
下列哪个（些）是64位处理器（）。
A.
Intel
ItaniumB.
Intel
Pentium
IIIC.
AMD
Athlon64
D.
AMD
OpteronE.
IBM
Power
5
补充：
双核处理器：
AMD速龙（althon）系列，奔腾D，酷睿
系列
20.
在下列关于青少年信息学竞赛的说法中，你赞成的
是（）
A.
举行信息学竞赛的目的，是为了带动广大青少年学科
学、爱科学，为造就一大批优秀的计算机科学
与技术人
才奠定良好的基础
B.
如果竞赛优胜者不能直接保送上大学，我今后就不再
参与这项活动了
C.
准备竞赛无非要靠题海战术，为了取得好成绩，就得
拼时间、拼体力
D.
为了取得好成绩，不光要看智力因素，还要看非智力
因素。优秀选手应该有坚韧不拔的意志，有严谨求实的
作风，既要努力奋进，又要胜不骄败不馁
不是空着就得分