信息学奥赛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淘汰) 3、与计算机系统相关的知识:

A:常见的操作系统有:DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、WIN2007、LINUX、VISTA

4、与计算机软件相关的知识:无 5、与计算机硬件相关的知识:

A:断电后能保存信息的有:ROM(只读存储器)、硬盘、软盘、光盘、U盘、MP3、MP4等;不能保存的主要是RAM(读写存储器)。

B:CPU又名中央处理器,它可以拆分成运算器、控制器

6、病毒及防火墙:

A:防火墙的作用是防止黑客攻击。 7、与编程语言相关的知识:

A:1972年PARC发布了Smalltalk的第一个版本。大约在此时,“面向对象”这一术语正式确定。Smalltalk被认为是第一个真正面向对象的语言

B:第一代语言:机器语言(0101001);第二代语言:20世纪50年代,汇编语言,第三代语言:高级语言、算法语言,如BASIC,FORTRAN,COBOL,PASCAL,C;高级语言的特点是可读性强,编程方便;第四代语言:非过程化语言;SQL;第五代语言:智能性语言,PROLOG(代表);还有:LISP,APL,SNOBOL,SIMULA。

学习好资料 欢迎下载

C:编程时读入一个很大的二维数组,按行读和按列读相比,输入效率上(取决于数组的存储方式)。 8、计算机算法知识:

A:算法特点:算法的改进,在很大程度上推动了计算机科学与技术的进步;判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性;目前仍然存在许多涉及到国计民生的重大课题,还没有找到能够在计算机上实施的有效算法;

B:采用比较为主要操作的算法是:冒泡、插入、选择排序 9、函数或表达式:

A:PASCAL语言中,表达式(21 XOR 2)的值是(23)

B:PASCAL语言,判断a不等于0且 b不等于0的正确的条件表达式是(a<>0)and(b<>0) 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),j),u)))

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;这三种遍历规则分别称为先(前)序遍历、中序遍历和后序遍历(以根为标准)。

学习好资料 欢迎下载

前序遍历 前序遍历的规则如下: 若二叉树为空,则退出。否则 ⑴访问处理根结点; ⑵前序遍历左子树; ⑶前序遍历右子树; a b d e h i c f g 中序遍历 中序遍历的规则如下: 若二叉树为空,则退出;否则 ⑴中序遍历左子树;⑵访问处理根结点; ⑶中序遍历右子树; 若中序遍历上图中的二叉树,可以得到如下的中序序列: d b h e i a f c g 后序遍历 样题:1、给出一棵二叉树的先序遍历:ABCDEFGH中序后序遍历的规则如下: 遍历:CBEDAGHF并写出后序遍历结果。 若二叉树为空,则退出;否则 2、已知一棵二叉树,其中序与后序遍历为:中序遍⑴后序遍历左子树;⑵后序遍历右子树; 历:CBGEAFHDIJ后序遍历:CGEBHFJIDA 求先序 ⑶访问处理根结点; 若后序遍历上图中的二叉树,可以得到如下的后序序列 d h i e b f g c a 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个数字符号组成。相同数字符号在不同的数位上表示不同的数值,每个数位计满二就向高位进一,即“逢二进一”。 一个任意的二进制数都可以表示成:

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4