信息学奥赛(初赛)辅导教材

信息学（计算机）奥林匹克竞赛辅导教程浙江金华第一中学《信息技术》教研组金华一中信息学（计算机）奥林匹克竞赛辅导教程目录I金华一中信息学（计算机）奥林匹克竞赛辅导教程目录第一部分试题的知识范围1一、初赛的要求1二、复赛内容与要求2第二部分计算机基础知识3一、计算机的诞生、发展、特点及应用31.计算机的诞生和发展32.计算机的分类33.计算机的特点34.PC机及其系统配置35计算机在现代社会中的应用4二、计算机系统组成及工作原理41.计算机的系统组成42.计算机语言的发展53.计算机的工作原理6三、计算机信息安全61.计算机系统的危害来源62.计算机系统的安全策略63.计算机病毒的概念64.计算机病毒的种类75.计算机病毒的特征76.计算机病毒的传染途径7四、计算机网络基础71.计算机网络的相关定义7金华一中信息学（计算机）奥林匹克竞赛辅导教程目录II2.计算机网络的功能73.计算机网络发展的几个阶段74.计算机网络的组成85.计算机网络的分类86.计算机网络的体系结构和网络协议97.网际协议IP与IP地址128Internet的域名139.常见计算机网络的应用13五、计算机中数的表示及运算151.十进制数162.二进制数163.八进制数与十六进制数174.其他进制数与十进制数之间的转换195.计算机中数的表示196.字符与汉字的编码22六图形化视窗操作系统231.图形用户操作系统232.Windows家族233.Windows98的主要功能与特性23七、数据库系统简述241.数据库的基本概念242.数据表的结构243.表结构24金华一中信息学（计算机）奥林匹克竞赛辅导教程第1页第一部分试题的知识范围一、初赛的要求1.1计算机的基本常识①计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）②信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）③信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令、程序，和存储程序原理、程序的三种基本控制结构）④信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）⑤信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互连网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）⑥人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））⑦信息技术的新发展、新特点、新应用等。1.2计算机的基本操作①Windows和Linux的基本操作知识②互联网的基本使用常识（网上浏览、搜索和查询等）③常用的工具软件使用（文字编辑、电子邮件收发等）1.3程序设计的基本知识1.3.1数据结构①程序语言中基本数据类型（字符、整数、长整数、浮点）②浮点运算中的精度和数值比较③一维数组（串）与线性表④记录类型（Pascal）/结构类型（C）1.3.2程序设计①结构化程序设计的基本概念②阅读理解程序的基本能力③具有将简单问题抽象成适合计算机解决的模型的基本能力④具有针对模型设计简单算法的基本能力⑤程序流程描述（自然语言/伪码/NS图/其他）⑥程序设计语言（Pascal/C/C++,2003年仍允许BASIC）1.3.3基本算法①初等算法（计数、统计、数学运算等）②排序算法（冒泡法、插入排序、合并排序、快速排序）金华一中信息学（计算机）奥林匹克竞赛辅导教程第2页③查找（顺序查找、二分法）④回溯算法二、复赛内容与要求2.1数据结构①指针类型②多维数组③单链表及循环链表④二叉树⑤文件操作（从文本文件中读入数据，并输出到文本文件中）2.2程序设计①算法的实现能力②程序调试基本能力③设计测试数据的基本能力④程序的时间复杂度和空间复杂度的估计2.3算法处理①离散数学知识的应用（如排列组合、简单图论、数理逻辑）②分治思想③模拟法④贪心法⑤简单搜索算法（深度优先广度优先）搜索中的剪枝⑥动态规划的思想及基本算法金华一中信息学（计算机）奥林匹克竞赛辅导教程第3页第二部分计算机基础知识一、计算机的诞生、发展、特点及应用1.计算机的诞生和发展1.1计算机的诞生1946年2月，世界上第一台电子计算机在美国宾西法尼亚大学诞生，取名为“ENIAC”1969年11月，计算机网络时代到来。1.2计算机的发展·第一代,1946～1957年电子管计算机·第二代,1958～1964年晶体管计算机·第三代,1965～1971年集成电路·第四代,1972年以来大规模集成电路·第五代，正在研制人工智能2.计算机的分类2.1以相对功能规模分类·巨型机(如CYBER205机,中国银河II机)·大型机·中型机(IBM360,370)·小型机(DEC公司的VAX-11,Alpha系列机)·微型机(如pc机)2.2按结构模式分类·集中式·计算机网络集中式系统是一个或多个用户同时使用一台计算机。它又分为：单用户机(pc机)和多用户机(DEC公司的ALPHA系列机,IBM360机)3.计算机的特点①运算速度快，精确度高②具有逻辑判断和记忆能力③高度的自动化和灵活性4.PC机及其系统配置4.1PC机的主要性能指标金华一中信息学（计算机）奥林匹克竞赛辅导教程第4页字长、运算速度、主频、内存容量、外设配置、软件配置。4.2总线连接PC机的CPU、存储器和外部设备的公共信息通道。三部分：数据总线、地址总线、控制总线。5计算机在现代社会中的应用①科学计算(数值计算)方面②数据处理方面③自动控制(过程控制)方面④办公自动化(OA)方面⑤计算机辅助设计(CAD)和辅助制造(CAM)方面⑥计算机辅助教学CAI(ComputerAssistedInstruction)方面⑦计算机在智能模拟方面的应用⑧计算机在通信方面的应用⑨计算机在信息高速公路方面的应用⑩计算机在文字处理方面的应用二、计算机系统组成及工作原理1.计算机的系统组成计算机硬件又称为“冯·诺依曼结构”（如图1所示）。由五个部分组成：输入设备、输出设备、存储器、运算器、控制器。其中计算机中央处理器（CPU）由运算器和控制器组成；输入、输出设备（I/O设备）又被人们称为外围（部）设备。计算机系统硬件系统运算器控制器存储器输入设备输出设备中央处理器（CPU）内（主）存储器外（辅助）存储器随机存储器（RAM）只读存储器（ROM）软件系统系统软件应用软件操作系统、标准程序库、服务性程序、语言处理程序、数据库管理系统、网络软件等专家系统、科学计算、数据处理、工程设计、事务管理、过程控制等程序图1计算机系统结构示意图金华一中信息学（计算机）奥林匹克竞赛辅导教程第5页计算机软件又可分为系统软件和应用软件两大类。计算机存储容量以字节为单位，它们是：字节B（1Byte=8bit）、千字节（1KB=1024B）、兆字节(1MB=1024KB)、千兆字节（1GB=1024MB)。外存又称辅助存储器，它容量更大，常用的外部存储器有软盘、硬盘、光盘、磁带。运算器：对信息进行加工处理的部件。它在控制器的控制下与内存交换信息，负责进行各类基本的算术运算和与、或、非、比较、移位等各种逻辑判断和操作。此外，在运算器中还有能暂时存放数据或结果的寄存器。控制器：是整个计算机的指挥中心。它对指令进行分析、判断，发出控制信号，使计算机的有关设备协调工作，确保系统自动运行。计算机的操作系统分类如下图所示：2.计算机语言的发展第一代：机器语言,二进制0、1构成的面向特定机器的低级语言。第二代：汇编语言。又称符号语言,对机器指令进行简单的符号化，比机器语言进了一步,但可读性、兼容性差,其优点是与机器比较靠近,因此效率较高。第三代：高级语言，完全接近人类习惯，各种机器指令用英文单词表示。其优点：可读性强，兼容性强，是目前广泛使用的一种面向过程的编程语言。如：BASIC，FORTRAN,C，PASCAL，FOXPRO等.第四代：面向对象的高级语言。如：VisualBasic,简称VBVisualC++,简称VCJava等。金华一中信息学（计算机）奥林匹克竞赛辅导教程第6页3.计算机的工作原理计算机的基本原理是存贮程序和程序控制。即预先要把指挥计算机如何进行操作的指令序列（称为程序）和原始数据通过输入设备输送到计算机内存储器中。每一条指令中明确规定了计算机从哪个地址取数，进行什么操作，然后送到什么地址去等步骤。程序与数据一样存贮，按程序编排的顺序，一步一步地取出指令，自动地完成指令规定的操作是计算机最基本的工作原理。这一原理最初是由美籍匈牙利数学家冯·诺依曼于1945年提出来的，故称为冯·诺依曼原理。其工作原理图如下所示：三、计算机信息安全1.计算机系统的危害来源计算机系统所面临的威胁大体可分为两种：一是对系统中信息的威胁；二是对系统中设备的威胁。2.计算机系统的安全策略①物理安全策略②访问控制策略③加密④防火墙控制防火墙是近期发展起来的一种控制两个不同网络之间访问的有效安全技术措施，也可称之为控制进／出两个方向通信的门槛。防火墙使用软件和硬件的组合，在网络边界上建立起网络通信监控系统来隔离内部和外部网络，以阻挡外部网络的敌意侵入。3.计算机病毒的概念①广义定义：能够引起计算机故障，破坏计算机数据的程序都属于计算机病毒。②狭义定义：指编制或者在计算机程序中插入的破坏计算机功能或者毁坏数据，影响计算机使用，并能自我复制的一组计算机指令或者程序代码。金华一中信息学（计算机）奥林匹克竞赛辅导教程第7页4.计算机病毒的种类4.1按其破坏性分类·良性病毒·恶性病毒4.2按其传染方式分类·引导型病毒·文件型病毒4.3按链接的方式分类·源码型病毒·入侵型病毒·操作系统型病毒·外壳型病毒5.计算机病毒的特征·隐蔽性·传染性·潜伏性·破坏性6.计算机病毒的传染途径软、硬磁盘，光盘，网络以及磁带等。四、计算机网络基础1.计算机网络的相关定义计算机网络是以各种通信设备和传输介质将处于不同位置的多台独立计算机连接起来，并在相应网络软件的管理下实现多台计算机之间信息传递和资源共享的系统。简单的说计算机网络指相互连接的独立自主的计算机的集合。·信息高速公路：是指数字化大容量光纤通信网络或无线通信、卫星通信网络与各种局域网络组成的高速信息传输通道。特征：交互性、高速性、广域性、广泛性、综合性、智能性Internet(国际互连网)，信息高速公路的代表。2.计算机网络的功能·资源共享（包括硬件资源、软件资源、数据与信息资源）·数据通信·提高可靠性3.计算机网络发展的几个阶段第一代：以主机为中心第二代：以通信子网为中心第三代：ISO/OSIRM，Internet第四代：可编程网络发展趋势：开放，集成，高性能，智能化金华一中信息学（计算机）奥林匹克竞赛辅导教程第8页4.计算机网络的组成从逻辑功能上分为两部分：通信子网和用户资源子网。·通信子网：负责信息通信，由一些专用的节点交换机和连接这些节点的通信链路组成。通信子网分两种类型：点对点通信子网和广播式通信子网；·用户资源子网：负责全网的信息处理，包括主机和其他信息资源设备。5.计算机网络的分类·按网络的拓扑结构分：①总线型拓扑结构。总线型拓扑通过一根传输线路将网络中所有结点连接起来，这根线路称为总线。网络中各结点都通过总线进行通信，在同一时刻只能允许一对结点占用总线通信。总线型拓扑简单，易实现，易维护，易扩充，但故障检测比较困难。②星型拓扑结构。星型拓扑中各结点都与中心结点连接，呈辐射状排列在中心结点周围。网络中任意两个结点的通信都要通过中心结点转接。单个结点的故障不会影响到网络的其它部分，但中心结点的故障会导致整个网络的瘫痪。③环型拓扑结构。环型拓扑中各结点首尾相连形成一个闭合的环，环中的数据沿着一个方向绕环逐站传输。环型拓扑的抗故障性能好，但网络中的任意一个结点或一条传输介质出现故障都将导致整个网络的故障。④树型拓扑结构。树型拓扑由总线型拓扑演变而来，其结构图看上去象一棵倒挂的树。树最上端的结点叫根结点，一个结点发送信息时，根结点接收该信息并向全树广播。树型拓扑易于扩展与故障隔离，但对根结点依赖性太大。金华一中信