全国信息学奥赛NOI培训教程(Pascal2016)重点.pdf
《全国信息学奥赛NOI培训教程(Pascal2016)重点.pdf》由会员分享,可在线阅读,更多相关《全国信息学奥赛NOI培训教程(Pascal2016)重点.pdf(369页珍藏版)》请在三一文库上搜索。
1、全国信息学奥赛NOI 培训教程 (Pascal 2016) 目录 计算机基础知识 -6 第 1 章 计算机基础常识 第二章 操作系统简介 第三章 计算机网络 第四章 计算机信息安全基础知识 Pascal 语言 -19 Pascal 语言概述与预备知识 第一章 开始编写pascal语言程序 第二章 Pascal 语言基础知识 第三章 顺序结构程序设计 第四章 选择结构程序设计 第五章 循环结构程序设计 第六章 数组与字符串 第七章 函数和过程 第八章 子界与枚举类型 第九章 集合类型 第十章 记录与文件类型 第十一章指针 第十二章程序调试 常用算法与策略 -56 第一章 算法的概念 第二章 递归
2、 第三章 回溯 第四章 排序 第五章 查找 第六章 穷举策略 第七章 贪心算法 第八章 分治策略 数据结构 -101 第一章 什么是数据结构 第二章 线性表 第三章 栈 第四章 队 第五章 树 第六章 图 动态规划 -144 第一章 什么叫动态规划 第二章 用动态规划解题 第三章 典型例题与习题 第四章 动态规划的递归函数法 第五章 动态规划分类1 数学知识及相关算法 第一章 有关数论的算法 第二章 高精度计算 第三章 排列与组合 第四章 计算几何 第五章 其它数学知识及算法 图论算法-192 第一章 最小生成树 第二章 最短路径 第三章 拓扑排序( AOV 网) 第四章 关键路径(AOE 网
3、) 第五章 网络流 第六章 图匹配 搜索算法与优化-218 第一章 双向广度优先搜索 第二章 分支定界法 第三章 A*算法 青少年信息学奥林匹克竞赛情况简介 信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动,重在培养学生能力,使得有潜质 有才华的学生在竞赛活动中锻炼和发展。近年来,信息学竞赛活动组织逐步趋于规范和完善,基本 上形成了 “ 地级市 省(直辖市 全国 国际 ” 四级相互接轨的竞赛网络。现把有关赛事情况 简介如下: 全国青少年信息学(计算机)奥林匹克分区联赛: 在举办 1995 年 NOI 活动之前,为了扩大普及的面,并考虑到多数省、直辖市、自治区已经开展了 多年省级竞赛,举
4、办了首届全国青少年信息学(计算机)奥林匹克分区联赛。考虑到不同年级学生 的知识层次,也为了鼓励更多的学生积极参与,竞赛设提高组、普及组,并分初、复赛进行,这样 可以形成一个梯队,确保每年的竞赛活动有比较广泛扎实的基础。 从 1995 年起,至2001 年共举办了七届全国青少年信息学奥林匹克分区联赛,每年举办一次, 有选手个人奖项(省、国家级)、选手等级证书、优秀参赛学校奖项。 全国青少年信息学(计算机)奥林匹克竞赛(简称NOI ): 由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。1984 年举办首届全国计算机竞赛。由各省市组织参赛,每年举办一次。奖项有个人一、
5、二、三等奖,女 选手第一、二、三名,各省队团体总分名次排队。 国际青少年信息学(计算机)奥林匹克竞赛(简称IOI ): 每年举办一次,由各参赛国家组队参赛。 全国青少年信息学(计算机)奥林匹克分区联赛竞赛大纲 一、初赛内容与要求:(#表示普及 组不涉及,以下同) 计 基 算 本 机 常 的 识 * 诞生与发展 *特点 *在现代社会中的应用 * 计算机系统的基本组成 * 计算机的工作原理# *计算机中的数的表示 * 计算机信息安全基础知识 *计算机网络 计 基 算 本 机 操 的 作 * MS DOS 与 Windows 的使用 基础 * 常用输入 /输出设备的种类、 功能、使用 * 汉字输入
6、/输出方法 * 常用计算机屏示信息 程 序 设 计 基 本 知 识 程序的表示 * 自然语言的描述 * PASCAL或 BASIC 语 言 数据结构的类型 * 简单数据的类型 * 构造类型:数组、字符串 * 了解基本数据结构(线性 表、队列与栈) 程序设计 * 结构化程序的基本概念 * 阅读理解程序的基本能力 * 具有完成下列过程的能力: 现实世界(指知识范畴的问 题) 信息世界(表达解法) 计算机世界(将解法用计算 机能实现的数据结构和算法描 述出来) 基本算法处理 * 简单搜索 * 字串处理 * 排序 * 查找 * 统计 * 分类 * 合并 * 简单的回溯算法 * 简单的递归算法 二、复赛
7、内容与要求: 在初赛的内容上增加以下内容 ( 2002 年修改稿 : 计算 机 软 件 * 操作系统的使用知识 * 编程语言的使用 数 据 结 构 * 结构类型中的记录类型 * 指针类型 * 文件( 提高组必须会使用文 本文件输入 ) * 链表 * 树 * 图# 程 序 设 计 * 程序设计能力 * 设计测试数据的能力 * 运行时间和占用空间的估算 能力 # 算 法 * 排列组合的应用 * 进一步加深回溯算法、递归 算法 * 分治法 处 理 * 搜索算法:宽度、深度优先 算法 * 表达式处理:计算、展开、 化简等 # * 动态规划 # 三、初赛试题类型:注:试题语言 两者选一 (程序设计语言:
8、基本BASIC 或 TURBO PASCAL ) *判断 * 填空 * 完善程序 * 读程 序写运行结果 * 问答 四、推荐读物: *分区联赛辅导丛书 * 学生计算 机世界报及少年电世界杂志 计算机基础知识 计算机基础知识 1.1 计算机的产生与发展 计算机的产生是 20世纪最重要的科学技术大事件之一。世界上的第一台计算机 (ENIAC)于 1946年诞生在美国宾夕法尼亚大学,到目前为止,计算机的发展大 致经历了四代: 第一代电子管计算机,始于1946年,结构上以 CPU为中心,使用计算机语 言,速度慢,存储量小,主要用于数值计算; 第二代晶体管计算机,始于1958年,结构上以存储器为中心,使
9、用高级语言, 应用范围扩大到数据处理和工业控制; 第三代中小规模集成电路计算机,始于1964年,结构上仍以存储器为中心,增 加了多种外部设备,软件得到了一定的发展,文字图象处理功能加强; 第四代大规模和超大规模集成电路计算机,始于1971年,应用更广泛,很多核 心部件可集成在一个或多个芯片上,从而出现了微型计算机。 我国从 1956年开始电子计算机的科研和教学工作,1983年研制成功 1亿/秒运算速 度的“ 银河” 巨型计算机, 1992年 11月研制成功 10亿/秒运算速度的 “ 银河 II ”巨型 计算机, 1997年研制了每秒 130亿运算速度的 “ 银河 III ”巨型计算机。 目前计
10、算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通信 产业已经成为新型的高科技产业。计算机网络的出现,改变了人们的工作方式、学 习方式、思维方式和生活方式。 1.2 计算机系统及工作原理 1.计算机的系统组成 计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元器件;软件即程 序和有关文档资料。 (1) 计算机的主要硬件 输入设备:键盘、鼠标、扫描仪等。 输出设备:显示器、打印机、绘图仪等。 中央处理器( CPU):包括控制器和运算器运算器,可以进行算术运算和逻辑运 算;控制器是计算机的指挥系统,它的操作过程是取指令分析指令 执行指 令。 存储器:具有记忆功能的物理器件,用
11、于存储信息。存储器分为内存和外存 内存是半导体存储器 (主存): 它分为只读存储器 (ROM 和随机存储器 (RAM 和高速缓冲存储器( Cache ; ROM:只能读,不能用普通方法写入,通常由厂家生产时写入,写入后数据不容易 丢失,也可以用特殊方法(如紫外线擦除(EPROM 或电擦除 (EEPROM_存储器; RAM: 可读可写,断电后内容全部丢失; Cache: 因为 CPU 读写 RAM 的时间需要等待,为了减少等待时间,在RAM 和 CPU 间需要设置高速缓存Cache, 断电后其内容丢失。 外存:磁性存储器 软盘和硬盘;光电存储器 光盘,它们可以作为永久存 器; 存储器的两个重要技
12、术指标:存取速度和存储容量。内存的存取速度最快(与 CPU速 度相匹配,软盘存取速度最慢。存储容量是指存储的信息量,它用字节 (Byte 作为基本单位, 1字节用 8位二进制数表示, 1KB=1024B,1MB=1024KB ,lGB=1024MB (2 计算机的软件 计算机的软件主要分为系统软件和应用软件两类: 系统软件:为了使用和管理计算机的软件,主要有操作系统软件如,WINDOWS 9598 2000NT40、DOS 60、UNIX 等;WINDOWS 95 982000 NT40 是多任务可视化图形界面,而 DOS 是字符命令形式的单任务的操作系 统。 应用软件:为了某个应用目的而编写
13、的软件,主要有辅助教学软件(CAI、辅助 设计软件 (CAD、文 字处理软件、工具软件以及其他的应用软件。 2.计算机的工作原理 到目前为止 ,电子计算机的工作原理均采用冯.若依曼的存储程序方式 ,即把程序存储 在计算机内 ,由计算机自动存取指令(计算机可执行的命令=操作码 +操作数)并执 行它。工作原理图如下: 1.3 计算机中有关数及编码的知识 1.计算机是智能化的电器设备 计算机就其本身来说是一个电器设备,为了能够快速存储、处理、传递信息,其内 部采用了 大量的电子元件,在这些电子元件中,电路的通和断、电压高低,这两种状态最容 易实现, 也最稳定、也最容易实现对电路本身的控制。我们将计算
14、机所能表示这样的状态, 用 0,1 来 表示、即用二进制数表示计算机内部的所有运算和操作。 2.二进制数的运算法则 二进制数运算非常简单,计算机很容易实现,其主要法则是: 0+0=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
15、,2,.,9,A,B,C,D,E,F 逢十六进一 (2)数的权 不同进制的数,基数不同,每位上代表的值的大小(权)也不相同。 如:( 21910=2*102+1*101+9*100 (110102=1*24+1*23+0*22+1*21+1*20 (2738=2*82+7*81+3*80 (27AF16=2*163+7*162+10*161+15*160 (3 十进制数转换任意进制 1 将十进制整数除以所定的进制数,取余逆序。 (3910=(1001112 (24510=(3658 2将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分 ,直到为零或精 确到小数点后几位。 如:( 0.3
16、510=(0.010112 (0.12510=(0.0012 (4 任意进制的数转换十进制 按权值展开 : 如:(21910=2*102+1*101+9*100 (110102=1*24+1*23+0*22+1*21+1*20=26 (2738=2*82+7*81+3*80=187 (7AF16=7*162+10*161+15*160=1867 4.定点数与浮点数 定点数是指数据中的小数点位置固定不变。由于它受到字长范围的限制,所能表示 的数的范围有限,计算结果容易溢出。 浮点数的形式可写成: N=M*2E( 其中 M 代表尾数 ,E 代表阶码)其形式如下: 阶码 尾数(包括符号位) 5.AS
17、CII 编码 由于计算机是电器设备 ,计算机内部用二进制数 ,这样对于从外部输入给计算机的所 有信息必须用二进制数表示,并且对于各种命令、字符等都需要转换二进制数,这 样就牵涉到信息符号转换成二进制数所采用的编码的问题,国际上统一用美国标准 信息编码( ASCII)它可用 7 位二进制数表示,存储时用一个字节,它的最高位为 0。因此基本的 ASCII 字符集有 128 个如: 0-9:48-57:00110000-. A-Z:65-90 :01000001-. a-z:97-122:01100000-. 6.汉字编码与汉字输入法 (1)机内码 ASCII 码不能表示汉字,因此要有汉字信息交换码
18、,我国国家标准是gb2312,它也 被称作国际码。它由两个字节组成,两个字节的最高位都为1。 gb2312共收纳 6763个汉字,其中,一级汉字(常用字)3755个按汉字拼音字母顺序排列,二级 汉字 3008个按部首笔画次序排列。 (2)汉字输入码(外码) 目前,汉字输入法主要有键盘输入、文字识别和语音识别。键盘输入法是当前汉字 输入的主要方法。它大体可以分为: 流水码:如区位码、电报码、通信密码,优点重码律少,缺点难于记忆; 音码:以汉语拼音为基准输入汉字,优点是容易掌握,但重码律高; 形码:根据汉字的字型进行编码,优点重码少,但不容易掌握; 音形码:将音码和形码结合起来,能减少重码律同时提
19、高汉字输入速度。 (3)汉字字模 供计算机输出汉字(显示和打印)用的二进制信息叫汉字字形信息也称字模。通用 汉字字模点阵规格有16*16,24*24,32*32,48*48,64*64,每个点在存储器中用 一个二进制位( (bit 存储,如一个 16*16 点阵汉字需要 32个字节的存储空间。 1.4 原码、反码与补码 在计算机中,数据是以补码的形式存储的: 在 n 位的机器数中,最高位为符号位,该位为零表示为正,为1 表示为负; 其余 n-1 位为数值位,各位的值可为0 或 1。 当真值为正时 :原码、反码、补码数值位完全相同; 当真值为负时 : 原码的数值位保持原样, 反码的数值位是原码数
20、值位的各位取反, 补码则是反码的最低位加一。 注意符号位不变。 如:若机器数是 16位: 十进制数 17 的原码、反码与补码均为: 0000000000010001 十进制数 -17 的原码、反码与补码分别为:1000000000010001 、 1111111111101110 、1111111111101111 1.5 逻辑运算 1.逻辑运算 逻辑与 :同真则真 逻辑或 :有真就真 逻辑非 :你真我假 逻辑异或 :不同则真 2.按位运算 按位与 : 同 1 则 1 如 1001010110110111=10010101 按位或 :有 1则 1 如 1001010110110111=1011
21、0111 3.逻辑化简 化简定律 : (1)交换律: A + B = B + A ,A B = B A (2)结合律: (A + B)+ C = A + (B + C ), (A B) C = A (B C) (3)幂等律: A A = A , A + A = A (4)吸收律: A (A + B )= A , A +(A B)= A (5)分配律: A (B + C )= A B + A C , A +(B C)=(A + B) (A + C) (6)互补律: A + A = 1 ,A A = 0 (7)非深入: A + B = A B, A B = A +B (8)0-1律: A + 0
22、= A , A + 1 = 1 , A 1 = A , A 0 = 0 例:化简函数 Q = AD + AD + AB + ACEF 。这个函数有 5 个自变量,化简过程如 下: Q = AD + AD + AB + ACEF = A + AB + ACEF = A + ACEF = A 练习:求证:(A+B(A+C=AB+AC 操作系统简介 2.1 DOS(Disk Operating System的组成 MSDOS采用模块结构,它由五部分组成:ROM 中的 BIOS 模块、 IOSYS 模 块、 MSDOSSYS模块、 COMMAND COM 模块和引导程序。 (1BIOS 模块:在 PC
23、机主板上有一个ROM 芯片,该芯片中存有系统自测试程序, CMOS 设置程序和基本输入输出程序(BIOS。BIOS 是一组程序和参 表,其中程序部份是可以通过中断方式调用的一组驱动程序,参数 给出外设的地址和参数。BIOS 是计算机硬件和操作系统之间的接口 通过它操作系统管理计算机硬件资源。 (2IOSYS 模块: IOSYS 是 MSDOS和 ROMBIOS 之间的接口程序。它和 RON BIOS 一起完成系统设备的管理。 (3MSDOS.SYS 模块: MSDOSSYS 用于实现文件管理,包括文件管理、目录管 理、 内存管理等功能。它以功能调用的形式实现用户和MSDOS 之间的程序级接口。
24、 (4COMMAND COM 模块: COMMAND COM 的主要功能是负责接收、识别、 解释和执行 用户从键盘输入的MSDOS 命令。 (5 引导程序:引导程序又叫 “ 引导记录 ” ,其作用是检查当前盘上是否有两个系统文 件,若有系统文件则把DOS 系统从磁盘装人内存。 一张系统盘上应该包含有:引导记录、IOSYS、MSDOSSYS和 COMMAND COM 等模块。 2.2 DOS的文件和目录 1文件概念:文件是指记录在存储介质(如磁盘、光盘上的一组相关信息的集合。 2文件标识 :驱动器号 +路径+文件名 (1 到 8 各字符 +扩展名 (1 到 3 个字符代表文件的 类型 3通配符
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 信息学 NOI 培训 教程 Pascal2016 重点
链接地址:https://www.31doc.com/p-4958223.html