《信息学奥赛NOIP初赛复习知识点》由会员分享，可在线阅读，更多相关《信息学奥赛NOIP初赛复习知识点（7页珍藏版）》请在金锄头文库上搜索。
1、信息学奥赛 NOIP 初赛复习知识点1、计算机相关科学家：A：被西方人誉为“计算机之父”的美籍匈牙利科学家、数学家冯诺依曼于1945年发表了一个 全新的”存储程序通用电子计算机方案一EDVAC。EDVAC方案提出了著名的“冯诺依曼体系结构” 理论：（1 ）采用二进制形式表示数据和指令（2）采用存储程序方式（3）由运算器、存储器、控制器、输 入设备和输出设备五大部件组成计算机系统B： “图灵机”与“冯诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另 一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。 与计算机有关的最高
2、奖项“图灵奖”。2、与竞赛有关的知识：A：信息学奥赛相关的软件有：anjuta 1.2.2版；Red Hat 9.0自带了 gcc/g+ 3.2.2版； Lazarus 0.9.10 版；free pasca 1 编译器 2.0.1 版；gdb 6.3 版；RHIDE；（turbo pasca 1 淘汰）3、与计算机系统相关的知识：A：常见的操作系统有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、WIN2007、 LINUX、 VISTA4、与计算机软件相关的知识：无5、与计算机硬件相关的知识：A：断电后能保存信息的有：ROM （只读存储器）、硬盘、
3、软盘、光盘、U盘、MP3、MP4等；不能 保存的主要是RAM （读写存储器）。B： CPU 又名中央处理器，它可以拆分成运算器、控制器空也器卑呼也P亍和申*卡+-理品H HhJ-VJ I 口刊壬 丄冃丰刊京 丄丄刖6、病毒及防火墙：A：防火墙的作用是防止黑客攻击7、与编程语言相关的知识：A： 1972年PARC发布了 Smalltalk的第一个版本。大约在此时，“面向对象”这一术语正式确定。 Smalltalk被认为是第一个真正面向对象的语言B：第一代语言：机器语言（0101001）；第二代语言：20世纪50年代，汇编语言，第三代语言： 高级语言、算法语言，如BASIC，FORTRAN，COB
4、OL，PASCAL，C；高级语言的特点是可读性强，编 程方便；第四代语言：非过程化语言；SQL；第五代语言：智能性语言，PROLOG （代表）；还有：LISP， APL， SNOBOL， SIMULA。C：编程时读入一个很大的二维数组，按行读和按列读相比，输入效率上（取决于数组的存储方式）。8、计算机算法知识：A：算法特点：算法的改进，在很大程度上推动了计算机科学与技术的进步；判断一个算法的好坏 的主要标准是算法的时间复杂性与空间复杂性；目前仍然存在许多涉及到国计民生的重大课题，还没有找 到能够在计算机上实施的有效算法；B：采用比较为主要操作的算法是：冒泡、插入、选择排序9、函数或表达式：A：
5、 PASCAL语言中，表达式（21 XOR 2）的值是（23）B： PASCAL语言，判断a不等于0且b不等于0的正确的条件表达式是（av0） and（bv0）10、数据结构基础：A：栈的出入顺序是先进后出，队列是先进先出；例如：某个车站呈狭长形，宽度只能容下一台车, 并且出入口是一个。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进、出、进、进、进、 出、出、进、进、出、出”。假设车辆入站的顺序为1， 2， 3， 4， 5， 6， 7则车辆出站的顺序为（1， 4， 3， 7， 6）。B：高度为N的均衡的二叉树是：如果去掉叶结点及相应的树枝，它应该是高度为N-1的满二叉树。 在这里，
6、树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381 个结点，则 该树的树高为（11）。C： （1）结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为 3,结点t的度为2,结点b的度为1。显然，所有树叶的度为0。（2）树的度：所有结点中最大的度称为 该树的度（宽度）。（3）树的深度（高度）：树是分层次的。结点所在的层次是从根算起的。根结点在第一 层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构 成兄弟关系。树中最大的层次称为树的深度，亦称高度。D：树的表示除自然界的树形表示法外（画图）还有括号表示
7、法：先将根结点放入一对圆括号中， 然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用 圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式（a（w, x（d （h）， e）， b（f）， c（s， t（i（m， o， n）， j）， u）E：二叉树的递归定义和基本形态：二叉树是以结点为元素的有限集，它或者为空，或者满足以下 条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R,其中L是根的左子树；R 是根的右子树； L 和 R 又是二叉树；F：二叉树的两个特殊形态：满二叉树：若深度为K的二叉树，共有2K-1个结点，
8、即第I层有21-1的结点，称为满二叉树。完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2,并且最下面一层的结点 都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树G：二叉树的三个主要性质：性质1：在二叉树的第i （三1）层上，最多有2i-1个结点性质2：在深度为k（k1）的二叉树中最多有2k-1个结点。性质 3：在任何二叉树中，叶子结点数总比度为2的结点多1。 n0=n2+1H：二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中 的信息，或对结点作其它的处理。如果用 L、 D、 R 分别表示遍历左子树、访问根结点、遍历右子树，限 定先左后右的
9、次序，三种组合DLR、LDR、 LRD；这三种遍历规则分别称为先（前）序遍历、中序遍历 和后序遍历（以根为标准）。a/d /f sh1样题：1、给出一棵二叉树的先序遍历：ABCDEFGH中序 遍历：CBEDAGHF并写出后序遍历结果。2、已知一棵二叉树，其中序与后序遍历为：中序遍历:CBGEAFHDIJ后序遍历:CGEBHFJIDA求先序前序遍历前序遍历的规则如下： 若二叉树为空，则退出。否则访问处理根结点；前序遍历左子树；前序遍历右子树；a b d e h i c f g中序遍历中序遍历的规则如下：若二叉树为空，则退出；否则中序遍历左子树；访问处理根结点；中序遍历右子树；若中序遍历上图中的二
10、叉树，可以得到如下的中序序列：d b h e i a f c g后序遍历后序遍历的规则如下：若二叉树为空，则退出；否则后序遍历左子树；后序遍历右子树； 访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列d h ieb f g ca11、进制相关知识：见G:小册子2日备份网站noi10-3.asp.htmlA： *进位计数制的基本概念 将数字符号按序排列成数位，并遵照某种由低位到高位的进位方式计数表示数值的方法，称作进 位计数制。1.十进制 十进制计数制由0、1、2、3、4、5、6、7、8、9共10个数字符号组成。相同数字符号 在不同的数位上表示不同的数值，每个数位计满十就向高位进
11、一，即“逢十进一”。KJCj-i. K.jK.j . tCm+j.心X10+.X1 Q!+X10 + K4X10 L+ K .2 X10-4.+K.11X 10+1XlO= gKixLO1 式中禺（匸址门“叮仍为十亍数字符号中的一个- i血B：八进制八进制计数制由0、 1、 2、 3、 4、 5、 6、 7共8个数字符号组成。相同数字符号在不同的数位上表示 不同的数值，每个数位计满八就向高位进一，即“逢八进一”。一个任意的十进制数都可以表示成：KjJCfci- - -. EC-iK-2. - ICjkh Km=KnXX Si_|_ . 4Kj X SKo X + K .j XSi+K.； X
12、S=L|-.+K X 8 +L4K X8-m=Z KS1 式中吃C I= g厂Z-1J丄卫）S A亍數宇符号中的一个-i-nC：二进制二进制计数制由0和1共2个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数 位计满二就向高位进一，即“逢二进一”。 一个任意的二进制数都可以表示成：KJCItl.K1K0.K.1K.2. J=Kax 2-K! X2-L+ . -HC1X214-KOX2+K .x xK .2 x 2-. .+K .1 x2 +14iCX2Hl讣吏 式中Kj C IMi.s-2,-l,Osl，,ik）为。和1两个数字苻号中的1个-iIID：其他进制在日常生活和日常工作
13、中还使用其他进制数如：十二进制数、十六进制数、百进制数和千进制数等。 无论哪种进制数，表示的方法都是类似的。如：十六进制数由0、1、2、3、4、5、6、7、8、9、A、B、C、 D、E和F共十六个符号组成，“逢十六进一”。不同的是用A、B、C、D、E和F分别表示10、11、12、 13、14和 15 六个数字符号。E：基数与权某进制计数制允许选用的基本数字符号的个数称为基数。一般而言，J进制数的基数为J,可供选用 的基本数字符号有J个，分别为0到J 1,每个数位计满J就向高位进一，即“逢J进一”。某进制计数制中各位数字符号所表示的数值表示该数字符号值乘以一个与数字符号有关的常数，该常 数称为“
14、位权”（简称“权”）。位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次 幂。 十进制数允许使用十个基本数字符号，所以基数为 10，每位数字符号代表的位数的大小是以 10 为底，数字符号所处位置的序号为指数的整数次幂。F：数的表示：为了表达方便起见，常在数字后加一缩写字母后缀作为不同进制数的标识。各种进 制数的后缀字母分别为：B： 二进制数。Q：八进制数。D：十进制数。H：十六进制数。对于十进制数通常不加后缀，也即十进制数后的字母D可省略。G：进制转换：将其他进制转换成10进制：“按权展开求和”如：（1011 01） 2 =（ IX 2?n-ox 22十 1XF十 1X2?十交十
15、1X2=10= 8+0+2+1 + 0+0.25） 10-i ： 1 .J io将十进制转换成二进制：对于整数部分，用被除数反复除以2，除第一次外，每次除以2 均取前一次商的整数部分作被除数并依次记下每次的余数。另外，所得到的商的最后一位余数是所求二进制数的最 高位。并依次取出的整数部分，直至结果的小数部分为0 为止。故该解：整数部分： “除以2 取余，逆序输出”对于小数部分，采用连续乘以基数 2 法称“乘基取整法”。例：将十进制117.625D转换成二进制数%（量（虑位）k&K&k（撮高位）小数部分: “乘以2 取整，顺序输出”O.u232X31.2500.251C Hi塢高山）0.50riC 4 )0.5xD21.01C I屁低術）所以 117.625D=1110101.101B将二进制数转换为对应的八进制数由于1 位八进制数对应3 位二进制数，所以二进制数转换成八
