全国信息学奥赛NOI培训教程(最新整理).doc

1、全国信息学奥赛 NOI 培训教程第 1 页 共 231 页全国信息学奥赛 NOI 培训教程（最新整理）使用“视图“-“文档结构图“可大大方便阅读本文档目录计算机基础知识 -6第 1 章 计算机基础常识 第二章 操作系统简介 第三章 计算机网络 第四章 计算机信息安全基础知识 Pascal 语言 -19Pascal 语言概述与预备知识 第一章 开始编写 pascal 语言程序 第二章 Pascal 语言基础知识 第三章 顺序结构程序设计 第四章 选择结构程序设计 第五章 循环结构程序设计 第六章 数组与字符串 第七章 函数和过程 第八章 子界与枚举类型 第九章 集合类型 全国信息学奥赛 NOI

2、培训教程第 2 页 共 231 页第十章 记录与文件类型 第十一章 指针 第十二章 程序调试 常用算法与策略 -56 第一章 算法的概念 第二章 递归 第三章 回溯 第四章 排序 第五章 查找 第六章 穷举策略 第七章 贪心算法 第八章 分治策略 数据结构 -101第一章 什么是数据结构 第二章 线性表 第三章 栈 第四章 队 第五章 树 第六章 图 动态规划 -144第一章 什么叫动态规划 第二章 用动态规划解题 全国信息学奥赛 NOI 培训教程第 3 页 共 231 页第三章 典型例题与习题 第四章 动态规划的递归函数法 第五章 动态规划分类 1 数学知识及相关算法 第一章 有关数论的算法

3、 第二章 高精度计算 第三章 排列与组合 第四章 计算几何 第五章 其它数学知识及算法 图论算法 -192第一章 最小生成树 第二章 最短路径 第三章 拓扑排序（ AOV 网） 第四章 关键路径（ AOE 网） 第五章 网络流 第六章 图匹配 搜索算法与优化 -218第一章 双向广度优先搜索 第二章 分支定界法 第三章 A*算法 全国信息学奥赛 NOI 培训教程第 4 页 共 231 页青少年信息学奥林匹克竞赛情况简介信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成

4、了“地级市省(直辖市)全国国际 ”四级相互接轨的竞赛网络。现把有关赛事情况简介如下：全国青少年信息学（计算机）奥林匹克分区联赛：在举办1995年 NOI 活动之前，为了扩大普及的面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。从1995年起，至2001年共举办了七届全国青少年信息学奥林匹克分区联赛，每年举办一次，有选手个人奖项（省、国家级） 、选手等级证书、优秀参赛学校奖

5、项。广东省青少年信息学（计算机）奥林匹克决赛（简称 GDOI）：省级信息学奥赛是一个水平较高的、有较大影响力的学科竞赛。由各市组织代表队参赛，参赛名额实行动态分配制度，每年举办一次。从1984年起广东省奥林匹克竞赛活动得到了蓬勃发展。奖项有个人一、二、三等奖，女选手第一、二、三名，奖励学校团体总分1-8名、市团体总分1-8名。全国青少年信息学（计算机）奥林匹克竞赛（简称 NOI）：由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。1984年举办首届全国计算机竞赛。由各省市组织参赛，每年举办一次。奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队

6、。国际青少年信息学（计算机）奥林匹克竞赛（简称 IOI）：每年举办一次，由各参赛国家组队参赛。全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲一、初赛内容与要求：（#表示普及组不涉及，以下同）计 基算 本机 常的 识* 诞生与发展 *特点 *在现代社会中的应用* 计算机系统的基本组成* 计算机的工作原理# *计算机中的数的表示* 计算机信息安全基础知识 *计算机网络全国信息学奥赛 NOI 培训教程第 5 页 共 231 页计 基算 本机 操的 作* MS DOS 与 Windows 的使用基础* 常用输入/输出设备的种类、功能、使用* 汉字输入/输出方法* 常用计算机屏示信息程序的表示 *

7、自然语言的描述* PASCAL 或 BASIC 语言数据结构的类型* 简单数据的类型* 构造类型：数组、字符串* 了解基本数据结构（线性表、队列与栈）程序设计* 结构化程序的基本概念* 阅读理解程序的基本能力* 具有完成下列过程的能力：现实世界（指知识范畴的问题）信息世界（表达解法）计算机世界（将解法用计算机能实现的数据结构和算法描述出来）程序设计基本知识基本算法处理* 简单搜索 * 字串处理* 排序 * 查找* 统计 * 分类 * 合并* 简单的回溯算法* 简单的递归算法二、复赛内容与要求：在初赛的内容上增加以下内容(2002年修改稿)：计算机软 件*操作系统的使用知识*编程语言的使用数据结

8、构*结构类型中的记录类型*指针类型*文件（提高组必须会使用文本文件输入）*链表*树*图#程序设计*程序设计能力*设计测试数据的能力*运行时间和占用空间的估算能力#算法处理*排列组合的应用*进一步加深回溯算法、递归算法*分治法*搜索算法：宽度、深度优先算法*表达式处理：计算、展开、化简等#*动态规划#全国信息学奥赛 NOI 培训教程第 6 页 共 231 页三、初赛试题类型：注：试题语言两者选一（程序设计语言：基本 BASIC 或 TURBO PASCAL）*判断 *填空 *完善程序 *读程序写运行结果 *问答四、推荐读物：*分区联赛辅导丛书 *学生计算机世界报及少年电世界杂志计算机基础知识计算

9、机基础知识1.1 计算机的产生与发展计算机的产生是 20 世纪最重要的科学技术大事件之一。世界上的第一台计算机（ENIAC）于 1946 年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： 第一代电子管计算机，始于 1946 年，结构上以 CPU 为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于 1958 年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； 第三代中小规模集成电路计算机，始于 1964 年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； 第四代大规模和超大规

10、模集成电路计算机，始于 1971 年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机。 我国从 1956 年开始电子计算机的科研和教学工作，1983 年研制成功 1 亿/秒运算速度的“银河”巨型计算机，1992 年 11 月研制成功 10 亿/秒运算速度的“银河 II”巨型计算机，1997 年研制了每秒 130 亿运算速度的“银河 III”巨型计算机。 目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通信产业已经成为新型的高科技产业。计算机网络的出现，改变了人们的工作方式、学习方式、思维方式和生活方式。 1.2 计算机系统及工作原理1.计算机的系统组

11、成 计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元器件；软件即程序和有全国信息学奥赛 NOI 培训教程第 7 页 共 231 页关文档资料。 (1） 计算机的主要硬件 输入设备：键盘、鼠标、扫描仪等。 输出设备：显示器、打印机、绘图仪等。 中央处理器（CPU）：包括控制器和运算器运算器，可以进行算术运算和逻辑运算；控制器是计算机的指挥系统，它的操作过程是取指令分析指令执行指令。 存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存内存是半导体存储器(主存）：它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器（Cache)；ROM:只能读，不能用普通方法写

12、入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)；RAM:可读可写，断电后内容全部丢失；Cache:因为 CPU 读写 RAM 的时间需要等待，为了减少等待时间，在 RAM 和 CPU 间需要设置高速缓存 Cache,断电后其内容丢失。 外存：磁性存储器软盘和硬盘；光电存储器光盘，它们可以作为永久存器； 存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快(与 CPU 速 度相匹配)，软盘存取速度最慢。存储容量是指存储的信息量，它用字节(Byte)作为基本单位，1 字节用 8 位二进制数表示，1KB=10

13、24B，1MB=1024KB，lGB=1024MB (2)计算机的软件 计算机的软件主要分为系统软件和应用软件两类： 系统软件：为了使用和管理计算机的软件，主要有操作系统软件如，WINDOWS 9598 2000NT4 0、DOS 60、UNIX 等；WINDOWS 95982000NT40 是多任务可视化图形 界面，而 DOS 是字符命令形式的单任务的操作系统。 应用软件：为了某个应用目的而编写的软件，主要有辅助教学软件(CAI)、辅助设计软件(CAD) 、文 字处理软件、工具软件以及其他的应用软件。全国信息学奥赛 NOI 培训教程第 8 页 共 231 页2.计算机的工作原理到目前为止,电

14、子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计算机自动存取指令（计算机可执行的命令=操作码+操作数）并执行它。工作原理图如下：1.3 计算机中有关数及编码的知识 1.计算机是智能化的电器设备计算机就其本身来说是一个电器设备，为了能够快速存储、处理、传递信息，其内部采用了大量的电子元件，在这些电子元件中，电路的通和断、电压高低，这两种状态最容易实现，也最稳定、也最容易实现对电路本身的控制。我们将计算机所能表示这样的状态，用 0，1来表示、即用二进制数表示计算机内部的所有运算和操作。2.二进制数的运算法则二进制数运算非常简单，计算机很容易实现，其主要法则是：0+0=

15、0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*0=0 1*1=1由于运算简单，电器元件容易实现，所以计算机内部都用二进制编码进行数据的传送和计算。3.十进制与二进制、八进制、十六进制数之间的相互转换(1)数的进制与基数计数的进制不同，则它们的基数也不相同，如表 1-1 所示。进制 基数 特点 二进制 0 ,1 逢二进一 八进制 0,1,2,3,4,5,6,7 逢八进一 十六进制 0,1,2,.,9,A,B,C,D,E,F 逢十六进一 （2）数的权 不同进制的数，基数不同，每位上代表的值的大小（权）也不相同。 如：（219)10=2*102+1*101+9*100 （110

16、10)2=1*24+1*23+0*22+1*21+1*20 全国信息学奥赛 NOI 培训教程第 9 页 共 231 页（273)8=2*82+7*81+3*80 (27AF)16=2*163+7*162+10*161+15*160 (3)十进制数转换任意进制 1) 将十进制整数除以所定的进制数,取余逆序。 （39)10=(100111)2 (245)10=(365)8 2)将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分,直到为零或精确到小数点后几位。 如：（0.35)10=(0.01011)2 (0.125)10=(0.001)2 (4)任意进制的数转换十进制 按权值展开: 如:（

17、219)10=2*102+1*101+9*100 （11010)2=1*24+1*23+0*22+1*21+1*20=26 （273)8=2*82+7*81+3*80=187 (7AF)16=7*162+10*161+15*160=1867 4.定点数与浮点数 定点数是指数据中的小数点位置固定不变。由于它受到字长范围的限制，所能表示的数的范围有限，计算结果容易溢出。 浮点数的形式可写成：N=M*2E(其中 M 代表尾数,E 代表阶码）其形式如下： 阶码 尾数（包括符号位） 5.ASCII 编码 由于计算机是电器设备,计算机内部用二进制数,这样对于从外部输入给计算机的所有信息必须用二进制数表示,

18、并且对于各种命令、字符等都需要转换二进制数，这样就牵涉到信息符号转换成二进制数所采用的编码的问题，国际上统一用美国标准信息编码（ASCII）它可用 7 位二进制数表示，存储时用一个字节，它的最高位为 0。因此基本的 ASCII 字符集有全国信息学奥赛 NOI 培训教程第 10 页 共 231 页128 个如: 0-9：48-57:00110000-. A-Z:65-90 :01000001-. a-z:97-122:01100000-. 6.汉字编码与汉字输入法 （1）机内码 ASCII 码不能表示汉字，因此要有汉字信息交换码，我国国家标准是 gb2312,它也被称作国际码。它由两个字节组成，

19、两个字节的最高位都为 1。 gb2312 共收纳 6763 个汉字，其中，一级汉字（常用字）3755 个按汉字拼音字母顺序排列，二级汉字 3008 个按部首笔画次序排列。 （2）汉字输入码（外码） 目前，汉字输入法主要有键盘输入、文字识别和语音识别。键盘输入法是当前汉字输入的主要方法。它大体可以分为： 流水码：如区位码、电报码、通信密码，优点重码律少，缺点难于记忆； 音码：以汉语拼音为基准输入汉字，优点是容易掌握，但重码律高； 形码：根据汉字的字型进行编码，优点重码少，但不容易掌握； 音形码：将音码和形码结合起来，能减少重码律同时提高汉字输入速度。 （3）汉字字模 供计算机输出汉字（显示和打印）用的二进制信息叫汉字字形信息也称字模。通用汉字字模点阵规格有 16*16，24*24，32*32，48*48，64*64，每个点在存储器中用一个二进制位（(bit)存储，如一个 16*16 点阵汉字需要 32 个字节的存储空间。 1.4 原码、反码与补码 在计算机中，数据是以补码的形式存储的: 在 n 位的机器数中，最高位为符号位，该位为零表示为正，为 1 表示为负； 其余 n-1 位为数值位，各位的值可为 0 或 1。