全国信息学奥赛复赛知识点梳理

补充：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：我国信息学奥赛的起源： 1、1984年2月16日，邓小平参观上海展览馆时，摸着正在用苹果电脑演示basic小程序的13岁学生李劲的头说了一句话“计算机普及要从娃娃抓起”！伟人的一句话，标志着一个时代的开始，当年即有中国科协和教育部联合举办了首届全国青少年计算机程序设计竞赛活动——这就是信息学奥赛的前身！ 2、为了与国际信息学奥林匹克竞赛活动接轨，全国青少年计算机程序设计竞赛从1988年起改名为“全国青少年信息学（计算机）奥林匹克竞赛”，简称信息学奥赛！已举办12届。 C：国际信息学奥林匹克竞赛( 简称IOI) 由联合国教科文组织于1988年发起、由来自世界各地20岁以下的中学生参加的在计算机科学领域的一项重要国际赛事，它的宗旨是在青少年中普及计算机科学，给来自世界各地的年轻人提供一个交流机会，并通过比赛和访问加深对主办国的了解。IOI首次比赛于1989年在保加利亚举行，至今已举办18届。 全国青少年信息学计算机奥林匹克联赛(NOIP) 为了进一步扩大普及的面，更进一步地在广大青少年中推动信息学知识的普及，鼓励更多的青少年参加到学习、应用计算机的行列中来，增加他们对于学习信息学知识的兴趣和参与意识，从1995年起NOI竞赛活动又予以延伸，组织开展了首届全国分区联赛（NOIP）的活动，至今已是第十二届 ，NOIP2006(第12界)山东赛区的复赛在寿光现代中学举行。 D：竞赛级别： 国际——IOI（国际竞赛） 国家——NOI（全国竞赛） 省级——NOIP（全国联赛） E：信息学锻炼什么能力：信息学奥林匹克竞赛属于智力与应用计算机解题能力的比赛，题目有相当的难度，解好这类题目，需要具备很强的综合能力． 1、观察和分析问题的能力； 2、将实际问题转化为数学模型的能力； 3、灵活地运用各种算法的能力； 4、熟练编写程序并将其调试通过的能力； 5、根据题目的要求，自己设计测试数据，检查自己的解法是否正确、是否完备的能力． 能够参加信息学竞赛的选手应该具有很强的自学能力，需要学习有关组合数学、图论、基本算法、数据结构、人工智能搜索算法及数学建模等知识，还要学会高级语言和编程技巧，要具备很强的上机操作能力． 3、与编程语言相关的知识： A：1972年PARC发布了Smalltalk的第一个版本。大约在此时，“面向对象”这一术语正式确定。Smalltalk被认为是第一个面向对象的语言 B：第一代语言：机器语言（0101001）；第二代语言：20世纪50年代，汇编语言，第三代语言：高级语言、算法语言，如BASIC，FORTRAN，COBOL，PASCAL，C；高级语言的特点是可读性强，编程方便；第四代语言：非过程化语言；SQL；第五代语言：智能性语言，PROLOG（代表）；还有：LISP，APL，SNOBOL，SIMULA。 C：编程时读入一个很大的二维数组，按行读和按列读相比，输入效率上（取决于数组的存储方式）。 4计算机算法知识： A：算法特点：算法的改进，在很大程度上推动了计算机科学与技术的进步；判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性；目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法； B：采用比较为主要操作的算法是：冒泡、插入、选择排序 9、函数或表达式： A：PASCAL语言中，表达式（21 XOR 2）的值是（23） B：PASCAL语言，判断a不等于0且 b不等于0的正确的条件表达式是（a<>0）and(b<>0) 5、数据结构基础： A：栈的出入顺序是先进后出，队列是先进先出；例如：某个车站呈狭长形，宽度只能容下一台车，并且出入口是一