nbhkdz.com冰点文库

信息学奥赛NOIP初赛复习知识点(未完成稿)


信息学奥赛 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:

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)and(b<>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)树的深度(高度) 。 :树是分层次的。结点所在的层次是从根算起的。根结点在第一 层,根的儿子在第二层,其余各层依次类推。图中的树共有五层。在树中,父结点在同一层的所有结点构 成兄弟关系。树中最大的层次称为树的深度,亦称高度。

D:树的表示除自然界的树形表示法外(画图)还有括号表示法:先将根结点放入一对圆括号中, 然后把它的子树按由左而右的顺序放入括号中,而对子树也采用同样方法处理:同层子树与它的根结点用 圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。例如图可写成如下形式(r(a(w,x(d (h) ,e),b(f) ) ,c(s,t(i(m,o,n) ,u)) ,j) ) E:二叉树的递归定义和基本形态:二叉树是以结点为元素的有限集,它或者为空,或者满足以下 条件:⑴有一个特定的结点称为根;⑵余下的结点分为互不相交的子集 L 和 R,其中 L 是根的左子树;R 是根的右子树;L 和 R 又是二叉树; F:二叉树的两个特殊形态: ⑴满二叉树: 若深度为 K 的二叉树,共有 2K-1 个结点,即第 I 层有 2I-1 的结点,称为满二叉树。 ⑵完全二叉树:如果一棵二叉树最多只有最下面两层结点度数可以小于 2,并且最下面一层的结点 都集中在该层最左边的若干位置上,则称此二叉树为完全二叉树 G:二叉树的三个主要性质: 性质 1:在二叉树的第 i(≥1)层上,最多有 2i-1 个结点 性质 2:在深度为 k(k≥1)的二叉树中最多有 2k-1 个结点。 性质 3:在任何二叉树中,叶子结点数总比度为 2 的结点多 1。n0=n2+1 H:二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时,可以取出结点中 的信息,或对结点作其它的处理。如果用 L、D、R 分别表示遍历左子树、访问根结点、遍历右子树,限 定先左后右的次序,三种组合 DLR、LDR、 LRD;这三种遍历规则分别称为先(前)序遍历、中序遍历 和后序遍历(以根为标准) 。 前序遍历 前序遍历的规则如下: 若二叉树为空,则退出。否则 ⑴访问处理根结点; ⑵前序遍历左子 树; ⑶前序遍历右子树; abdehicfg 中序遍历 中序遍历的规则如下: 若二叉树为空,则退出;否则 ⑴中序遍历左子树;⑵访问处理根结点; ⑶中序遍历右子树; 若中序遍历上图中的二叉树,可以得到如下 的中序序列: dbheiafcg 样题:1、给出一棵二叉树的先序遍历:ABCDEFGH 中序 遍历:CBEDAGHF 并写出后序遍历结果。 2、已知一棵二叉树,其中序与后序遍历为:中序遍 历:CBGEAFHDIJ 后序遍历:CGEBHFJIDA 求先序 后序遍历 后序遍历的规则如下: 若二叉树为空,则退出;否则 ⑴后序遍历左子树;⑵后序遍历右子树; ⑶访问处理根结点; 若后序遍历上图中的二叉树,可以得到如 下的后序序列 dhiebfgca

11、进制相关知识:见 G:\小册子 2 日备份\网站\noi\10-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 个数字符号组成。相同数字符号在不同的数位上表示 不同的数值,每个数位计满八就向高位进一,即“逢八进一”。 一个任意的十进制数都可以表示成:

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 进制:“按权展开求和”如:

将十进制转换成二进制:对于整数部分,用被除数反复除以 2,除第一次外,每次除以 2 均取前一 次商的整数部分作被除数并依次记下每次的余数。另外,所得到的商的最后一位余数是所求二进制数的最 高位。 对于小数部分,采用连续乘以基数 2,并依次取出的整数部分,直至结果的小数部分为 0 为止。故该 法称“乘基取整法”。 例:将十进制 117.625D 转换成二进制数 解:整数部分:“除以 2 取余,逆序输出”

小数部分:“乘以 2 取整,顺序输出”

所以 117.625D=1110101.101B 将二进制数转换为对应的八进制数 由于 1 位八进制数对应 3 位二进制数,所以二进制数转换成八进制数时,只要以小数点为界,整数部 分向左, 小数部分向右每 3 位分成一组, 各组用对应的 1 位八进制数字表示, 即可得到对应的八进制数值。 最左最右端分组不足 3 位时,可用 0 补足。例:将 1101101.10101B 转换成对应的八进制数。解:

所以,1101101.10101B=155.52Q。 同理,用相反的方法可以将八进制数转换成对应的二进制数。

将二进制数转为对应的十六进制数

由于 1 位十六进制数对应 4 位二进制数,所以二进制数转换为十六进制时,只要以小数点为界,整数 部分向左,小数部分向右每 4 位分成一组,各组用对应的 1 位十六进制数字表示,即可得到对应的十六进 制数值。两端的分组不足 4 位时,用 0 补足。 例:将 1101101.10101B 转换成对应的十六进制数 解: 所以 1101101.10101B=6D.8AH。 同理,用相反的方法可以将十六进制数转换成对应的二进制数。 将十六进制数 5DF.9 转换成二进制:

例:将二进制数 1100001.111 转换成十六进制:

至于其他的转换方法,如八进制到十进制,十六进制到十进制之间的转换,同样可用按权展开的多项 式之和及整数部分用“除基取整数”来实现的。只不过此时基数分别为 8 和 16。当然,更简单实用的方法 是借用二进制数做桥梁,用“八——二——十”或“十六——二——八”的转换方法来实现。 12、集合: 13、字符串


信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 ·诺依曼 于 1945 年发表了一个 全新的...

信息学奥赛NOIP初赛复习知识点+基本函数

信息学奥赛 NOIP 初赛复习知识点+基本函数 1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个全新的 " 存储程序...

信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 全新...

信息学奥赛NOIP初赛复习

信息学奥赛NOIP初赛复习_学科竞赛_高中教育_教育专区。分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中选择题考查 的是知识...

信息学奥赛初赛谈

信息学奥赛初赛谈 对参加信息学联赛NOIP初赛的学生提供一点复习资料对参加信息学联赛NOIP初赛的学生提供一点复习资料隐藏>> NOIP 初赛知识是基础,能力最重要 知识...

信息学联赛初赛理论复习资料

NOIP 初赛理论知识复习资料... 20页 免费 信息学奥林匹克竞赛辅导Pa... 189页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点...

noip初赛复习资料(全)

noip初赛复习资料(全)_学科竞赛_高中教育_教育专区。noip初赛复习资料(全) 分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中...

高中信息技术信息学奥赛NOIP初赛复习

高中信息技术信息学奥赛NOIP初赛复习_其它考试_资格考试/认证_教育专区。高中信息技术信息学奥赛NOIP初赛复习全国信息学奥赛 NOIP 初赛复习 NOIP 初赛总复习初赛考的...

NOIP初赛复习(提高组)--精华版

NOIP初赛复习(提高组)--精华版_IT/计算机_专业资料...分区联赛初赛复习材料初赛考的知识点就是计算机基本...(信息学奥赛辅导)排列与... 暂无评价 13页 2下载...