2022年信息学奥赛NOIP初赛复习知识点.pdf

《2022年信息学奥赛NOIP初赛复习知识点.pdf》由会员分享，可在线阅读，更多相关《2022年信息学奥赛NOIP初赛复习知识点.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 pascal编译器 2.0.1版； gdb 6.3版； RHIDE ；（ turbo pascal淘汰）3、与计算机系统相关的知识：A：常见的操作系统有：DOS 、 WIN32 、 WIN95 、WIN98 、WIN2000 、WINXP 、WIN2003 、WIN2007 、LINUX 、VISTA 4、与计算机软件相关的知识：无5、与

3、计算机硬件相关的知识：A：断电后能保存信息的有：ROM （只读存储器） 、硬盘、软盘、光盘、U 盘、 MP3 、MP4 等；不能保存的主要是RAM （读写存储器） 。B：CPU 又名中央处理器，它可以拆分成运算器、控制器6、病毒及防火墙：A：防火墙的作用是防止黑客攻击。7、与编程语言相关的知识：A：1972 年 PARC 发布了 Smalltalk的第一个版本。大约在此时，“ 面向对象 ” 这一术语正式确定。Smalltalk被认为是第一个真正面向对象的语言B：第一代语言： 机器语言 （0101001 ） ；第二代语言：20 世纪 50 年代， 汇编语言 ，第三代语言：高级语言、算法语言，如

4、BASIC ，FORTRAN ，COBOL ，PASCAL ，C；高级语言的特点是可读性强，编程方便； 第四代语言： 非过程化语言 ；SQL ；第五代语言： 智能性语言 ，PROLOG （代表）；还有： LISP ，APL ，SNOBOL ，SIMULA 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 8 页 - - - - - - - - - - C：编程时读入一个很大的二维数组，按行读和按列读相比，输入效率上 （取决于数组的存储方式）。8、计算机算法知识：A：算法特点：算法的改进，在很大

5、程度上推动了计算机科学与技术的进步；判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性；目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法；B：采用 比较 为主要操作的算法是：冒泡、插入、选择排序9、函数或表达式：A：PASCAL 语言中，表达式（21 XOR 2 ）的值是（ 23）B：PASCAL 语言，判断a 不等于 0 且 b 不等于 0 的正确的条件表达式是（a0 ）and(b0) 10、数据结构基础：A：栈的出入顺序是先进后出，队列是先进先出；例如：某个车站呈狭长形，宽度只能容下一台车，并且出入口是一个。已知某时刻该车站状态为空，从这一时刻开始的

6、出入记录为：“进、出、进、进、进、出、出、进、进、出、出”。假设车辆入站的顺序为1，2，3，4，5，6，7 则车辆出站的顺序为（1， 4，3，7，6） 。B：高度为 N 的均衡的二叉树是：如果去掉叶结点及相应的树枝，它应该是高度为N-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381 个结点，则该树的树高为（11） 。C： （ 1）结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i 度为3，结点 t 的度为 2，结点 b 的度为 1。显然，所有树叶的度为0。 （2）树的度： 所有结点中最大的度称为该树的度 (宽度）。

7、（3）树的深度（高度） ：树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。D：树的表示除 自然界的树形表示法外（画图）还有括号表示法 ：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式（r（a（w，x（d（h） ，e） ） ，b（f） ，c（ s，t（i（m，o，n） ，j） ，u） ） ）E：二叉树

8、的递归定义和基本形态：二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L 和 R，其中 L 是根的左子树；R是根的右子树；L 和 R 又是二叉树；F：二叉树的两个特殊形态：满二叉树：若深度为 K 的二叉树，共有2K-1 个结点，即第I 层有 2I-1 的结点，称为满二叉树。完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树G：二叉树的三个主要性质：性质 1：在二叉树的第i（ 1）层上，最多有2i-1 个结点性质 2：在深度为k(k 1)的二叉

9、树中最多有2k-1 个结点。性质 3：在任何二叉树中，叶子结点数总比度为2 的结点多1。n0=n2+1 H：二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。如果用L、 D、 R 分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合DLR 、LDR 、LRD ；这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 8 页 - - - - - - -

10、 - - - 样题： 1、给出一棵二叉树的先序遍历：ABCDEFGH中序遍历： CBEDAGHF并写出后序遍历结果。2、 已 知 一 棵 二 叉 树 ， 其 中 序 与 后 序 遍 历 为： 中 序 遍历:CBGEAFHDIJ后序遍历 :CGEBHFJIDA 求先序前序遍历前序遍历的规则如下：若二叉树为空，则退出。否则访问处理根结点；前序遍历左子树；前序遍历右子树；a b d e h i c f g 中序遍历中序遍历的规则如下：若二叉树为空，则退出；否则中序遍历左子树；访问处理根结点；中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：d b h e i a f c g 后序遍历

11、后序遍历的规则如下：若二叉树为空，则退出；否则后序遍历左子树；后序遍历右子树；访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列d h i e b f g c a 11、进制相关知识：见小册子 2 日备份 网站 noi10-3.asp.html A：进位计数制的基本概念将数字符号按序排列成数位，并遵照某种由低位到高位的进位方式计数表示数值的方法，称作进位计数制。 1.十进制十进制计数制由0、1、 2、3、4、5、6、7、8、9 共 10 个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满十就向高位进一，即“逢十进一”。B：八进制八进制计数制由0、1、2、3、4

12、、5、6、7 共 8 个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满八就向高位进一，即“逢八进一”。一个任意的十进制数都可以表示成：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 8 页 - - - - - - - - - - C：二进制二进制计数制由0 和 1共 2 个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位 计 满 二 就 向 高 位 进 一 ， 即 “ 逢 二 进 一 ” 。一 个 任 意 的 二 进 制 数 都 可 以 表 示 成 ：D：

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 到 J1，每个数位计满J 就向高位进一，即“逢J 进一”。某进制计数制中各位数字符号所表示的数值表示该数字符号值

14、乘以一个与数字符号有关的常数，该常数称为“位权”（简称“权”）。位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次幂。十进制数允许使用十个基本数字符号，所以基数为10，每位数字符号代表的位数的大小是以10为底，数字符号所处位置的序号为指数的整数次幂。F：数的表示：为了表达方便起见，常在数字后加一缩写字母后缀作为不同进制数的标识。各种进精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 8 页 - - - - - - - - - - 制数的后缀字母分别为：B ：二进制数。Q：八进制数。D

15、：十进制数。H：十六进制数。对于十进制数通常不加后缀，也即十进制数后的字母D可省略。G：进制转换：将其他进制转换成10 进制：“按权展开求和”如：将十进制转换成二进制：对于 整数部分 ，用被除数反复除以2，除第一次外，每次除以2 均取前一次商的整数部分作被除数并依次记下每次的余数。另外，所得到的商的最后一位余数是所求二进制数的最高位。对于 小数部分 ，采用连续乘以基数2，并依次取出的整数部分，直至结果的小数部分为0 为止。故该法称“乘基取整法”。例：将十进制117.625D 转换成二进制数解：整数部分：“除以 2 取余， 逆序 输出 ”小数部分 : “乘以 2取整， 顺序 输出”精品资料 -

16、- - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 8 页 - - - - - - - - - - 所以 117.625D1110101.101B 将二进制数转换为对应的八进制数由于 1位八进制数对应3 位二进制数，所以二进制数转换成八进制数时，只要以小数点为界，整数部分向左， 小数部分向右每3 位分成一组， 各组用对应的1 位八进制数字表示，即可得到对应的八进制数值。最左最右端分组不足3 位时，可用0 补足。例：将1101101.10101B 转换成对应的八进制数。解：所以， 1101101.10101B 1

17、55.52Q。同理，用相反的方法可以将八进制数转换成对应的二进制数。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 8 页 - - - - - - - - - - 将二进制数转为对应的十六进制数由于 1位十六进制数对应4 位二进制数，所以二进制数转换为十六进制时，只要以小数点为界，整数部分向左，小数部分向右每4 位分成一组，各组用对应的1 位十六进制数字表示，即可得到对应的十六进制数值。两端的分组不足4位时，用0 补足。例：将 1101101.10101B 转换成对应的十六进制数解：所以 11

18、01101.10101B 6D.8AH。同理，用相反的方法可以将十六进制数转换成对应的二进制数。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 8 页 - - - - - - - - - - 将十六进制数5DF.9 转换成二进制：例：将二进制数1100001.111 转换成十六进制：至于其他的转换方法，如八进制到十进制，十六进制到十进制之间的转换，同样可用按权展开的多项式之和及整数部分用“除基取整数”来实现的。只不过此时基数分别为8 和 16。当然， 更简单实用的方法是借用二进制数做桥梁，用“八二十”或“十六二八”的转换方法来实现。12、集合：13、字符串精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 8 页 - - - - - - - - - -