信息学奥赛初赛复习知识点未完成稿.docx

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