《信息学奥赛初赛复习知识点.docx》由会员分享，可在线阅读，更多相关《信息学奥赛初赛复习知识点.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点信息学奥赛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
3、 、WIN2007 、LINUX 、VISTA4、与运算机软件相关的学问：无5、与运算机硬件相关的学问：A：断电后能储存信息的有：ROM （只读储备器） 、硬盘、软盘、光盘、U 盘、 MP3 、MP4 等。不能储存的主要是RAM （读写储备器） 。B： CPU 又名中心处理器，它可以拆分成运算器、掌握器6、病毒及防火墙：A ： 防火墙的作用是防止黑客攻击。7、与编程语言相关的学问：A ： 1972 年 PARC发布了 Smalltalk的第一个版本。大约在此时，“面对对象 ”这一术语正式确定。Smalltalk被认为是第一个真正面对对象的语言B ： 第一代语言：机器语言 （ 0101001 ）
4、。其次代语言：20 世纪 50 岁月， 汇编语言 ，第三代语言： 高级语言、算法语言，如 BASIC ，FORTRAN ，COBOL ，PASCAL ，C。高级语言的特点是可读性强，编 程便利。 第四代语言： 非过程化语言。SQL 。第五代语言： 智能性语言 ，PROLOG （代表）。仍有： LISP ， APL ， SNOBOL ， SIMULA 。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 -
5、 - - - - - - - - - - -名师整理精华学问点C：编程时读入一个很大的二维数组，按行读和按列读相比，输入效率上 （取决于数组的储备方式）。8、运算机算法学问：A ：算法特点：算法的改进，在很大程度上推动了运算机科学与技术的进步。判定一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性。目前仍旧存在很多涉及到国计民生的重大课题，仍没有找 到能够在运算机上实施的有效算法。B ： 采纳 比较 为主要操作的算法是：冒泡、插入、挑选排序9、函数或表达式：A ： PASCAL语言中，表达式（21 XOR 2 ）的值是（ 23）B ： PASCAL语言，判定a 不等于 0 且 b 不等于
6、0 的正确的条件表达式是（a0 ）andb0 10 、数据结构基础：A ：栈的出入次序是先进后出，队列是先进先出。例如：某个车站呈狭长形，宽度只能容下一台车，并且出入口是一个。已知某时刻该车站状态为空，从这一时刻开头的出入记录为：“进、出、进、进、进、出、出、进、进、出、出”。假设车辆入站的次序为1，2 ， 3 ，4 ， 5 ， 6， 7 就车辆出站的次序为（1， 4， 3， 7 ， 6）。B ：高度为 N 的均衡的二叉树是：假如去掉叶结点及相应的树枝，它应当是高度为N-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，假如某个均衡的二叉树共有2381个结点，就该树的树高为（
7、11）。C：（ 1）结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i 度为 3，结点 t 的度为 2 ，结点 b 的度为 1 。明显，全部树叶的度为0 。（ 2 ）树的度： 全部结点中最大的度称为 该树的度 宽度）。（ 3） 树的深度（高度） ： 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在其次层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的全部结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。D： 树的表示除 自然界的树形表示法外（画图）仍有括号表示法 ：先将根结点放入一对圆括号中，然后把它的子树按由左而右的次序放入括
8、号中，而对子树也采纳同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最终用闭括号括起来。例如图可写成如下形式（r（ 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 个结点，即第I 层有 2I-1 的
9、结点，称为满二叉树。完全二叉树：假如一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的如干位置上，就称此二叉树为完全二叉树G： 二叉树的三个主要性质：性质 1：在二叉树的第i（ 1 ）层上，最多有2i-1 个结点性质 2：在深度为kk 1 的二叉树中最多有2k-1 个结点。性质 3：在任何二叉树中，叶子结点数总比度为2 的结点多1 。n0=n2+1H：二叉树的遍历是不重复的拜访二叉树中的每一个结点。在拜访到每个结点时，可以取出结点中的信息，或对结点作其它的处理。假如用 L、 D、 R 分别表示遍历左子树、拜访根结点、遍历右子树，限定先左后右的次序，三种组合
10、 DLR 、LDR 、 LRD 。这三种遍历规章分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准） 。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点可编辑资料 - - - 欢迎下载精品名师归纳总结样题： 1 、给出一棵二叉树的先序遍历：ABCDEFGH中序遍历： CBEDAGHF并写出后序遍历结果。2 、 已 知 一 棵 二 叉
11、树 ， 其 中 序 与 后 序 遍 历 为 ： 中 序 遍历:CBGEAFHDIJ后序遍历 :CGEBHFJIDA求先序前序遍历前序遍历的规章如下：如二叉树为空，就退出。否就拜访处理根结点。前序遍历左子树。前序遍历右子树。a b d e h i c f g中序遍历中序遍历的规章如下：如二叉树为空，就退出。否就中序遍历左子树。拜访处理根结点。中序遍历右子树。如中序遍历上图中的二叉树，可以得到如下的中序序列：d b h e i a f c g后序遍历后序遍历的规章如下：如二叉树为空，就退出。否就后序遍历左子树。后序遍历右子树。拜访处理根结点。如后序遍历上图中的二叉树，可以得到如下的后序序列d h
12、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、5、6、7 共 8 个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满八就
13、向高位进一，即“逢八进一”。一个任意的十进制数都可以表示成：C：二进制二进制计数制由0 和 1 共 2 个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位 计 满 二 就 向 高 位 进 一 ， 即 “ 逢 二 进 一 ” 。一 个 任 意 的 二 进 制 数 都 可 以 表 示 成 ：可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师整
14、理精华学问点D：其他进制在日常生活和日常工作中仍使用其他进制数如：十二进制数、十六进制数、百进制数和千进制数等。无论哪种进制数，表示的方法都是类似的。如：十六进制数由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 进一”。某进制计数制中各位数字符号所表示
15、的数值表示该数字符号值乘以一个与数字符号有关的常数，该常数称为“位权”（简称“权”）。位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次幂。十进制数答应使用十个基本数字符号，所以基数为10，每位数字符号代表的位数的大小是以10为底，数字符号所处位置的序号为指数的整数次幂。F ：数的表示：为了表达便利起见，常在数字后加一缩写字母后缀作为不同进制数的标识。各种进制数的后缀字母分别为：B：二进制数。Q：八进制数。D：十进制数。H：十六进制数。对于十进制数通常不加后缀，也即十进制数后的字母D可省略。G：进制转换：将其他进制转换成10 进制：“按权绽开求和”如：将十进制转换成二进制：对于 整
16、数部分 ，用被除数反复除以2，除第一次外，每次除以2 均取前一次商的整数部分作被除数并依次登记每次的余数。另外，所得到的商的最终一位余数是所求二进制数的最高位。对于 小数部分 ，采纳连续乘以基数2，并依次取出的整数部分，直至结果的小数部分为0 为止。故该法称“乘基取整法”。例：将十进制117.625D 转换成二进制数解：整数部分：“除以 2 取余， 逆序 输出 ”小数部分 : “乘以 2 取整， 次序 输出”可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 6 页 - - - - - - - - - -可编辑资料 - -
17、- 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点所以 117.625D 1110101.101B将二进制数转换为对应的八进制数由于 1 位八进制数对应3 位二进制数，所以二进制数转换成八进制数时，只要以小数点为界，整数部分向左， 小数部分向右每3 位分成一组， 各组用对应的1 位八进制数字表示，即可得到对应的八进制数值。最左最右端分组不足3 位时，可用0 补足。例：将1101101.10101B 转换成对应的八进制数。解：所以， 1101101.10101B 155.52Q 。同理，用相反的方法可以将八进制数转换成对应的二
18、进制数。将二进制数转为对应的十六进制数由于 1 位十六进制数对应4 位二进制数，所以二进制数转换为十六进制时，只要以小数点为界，整数 部分向左，小数部分向右每4 位分成一组，各组用对应的1 位十六进制数字表示，即可得到对应的十六进制数值。两端的分组不足4 位时，用0 补足。例：将 1101101.10101B 转换成对应的十六进制数解：所以 1101101.10101B 6D.8AH。同理，用相反的方法可以将十六进制数转换成对应的二进制数。将十六进制数5DF.9 转换成二进制：可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，
19、共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师整理精华学问点例：将二进制数1100001.111 转换成十六进制：至于其他的转换方法，如八进制到十进制，十六进制到十进制之间的转换，同样可用按权绽开的多项式之和及整数部分用“除基取整数”来实现的。只不过此时基数分别为8 和 16。当然， 更简洁有用的方法是借用二进制数做桥梁，用“八二十”或“十六二八”的转换方法来实现。12、集合：13、字符串可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载