《全国信息学奥林匹克联赛培训lyc》由会员分享,可在线阅读,更多相关《全国信息学奥林匹克联赛培训lyc(186页珍藏版)》请在金锄头文库上搜索。
1、全国信息学奥林匹克联赛培训,初赛 复赛初赛经验谈 复赛经验谈1 复赛经验谈3复赛经验谈2友情链接:基础知识 数据结构广西柳州高中电教组 何平英 2004.9.,全国信息学奥林匹克联赛大纲,信息学分区联赛2003新大纲2003-8-2大榕树 1.比赛中使用的程序设计语言是:2003年:初赛:BASIC、PASCAL或C/C+;复赛:BASIC、PASCAL或C/C+。2004年:初赛:BASIC、PASCAL或C/C+:复赛:PASCAL或C/C+。2005年及之后:初赛:PASCAL或C/C+: 复赛:PASCAL或C/C+。2.试题知识范围: 见如下试题知识范围。,分区联赛初赛大纲(计算机基
2、本常识一),初赛内容与要求:计算机的基本常识1.计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化)2.信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输入输出方式)3.信息的表示与处理(信息编码、微处理部件MPU、内存储结构、指令,程序,和存储程序原理、程序的三种基本控制结构),4.信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库管理) 5.信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点)6.人机交互界面的基本概念(
3、窗口系统、人和计算机交流信息的途径(文本及交互操作)7.信息技术的新发展、新特点、新应用等。,分区联赛初赛大纲(计算机基本常识二),分区联赛初赛大纲(计算机基本操作),计算机的基本操作1.WINDOWS和LINUX的基本操作知识2.互联网的基本使用常识 (网上浏览、搜索和查询等)3.常用的工具软件使用(文字编辑、电子邮件收发等)程序设计的基本知识,分区联赛初赛大纲(程序设计),1.结构化程序设计的)基本概念 2.阅读理解程序的基本能力3.具有将简单问题抽象成适合计算机解决的模型的基本能力4.具有针对模型设计简单算法的基本能力5.程序流程描述(自然语言/伪码/NS图/其他)6.程序设计语言(PA
4、SCAL/C/C+,2003年仍允许BASIC),分区联赛初赛大纲(简单数据结构),1.程序语言中基本数)据类型(字符、整数、长整数、浮点)2.浮点运算中的精度和数值比较3.一维数组(串)与线性表4.记录类型(PASCAL)/ 结构类型(C),分区联赛初赛大纲(基本算法),1.初等算法(计数、统计、数学运算等)2.排序算法(冒泡法、插入排序、合并排序、快速排序)3.查找(顺序查找、二分法)4.回溯算法,初赛目录,1、计算机的基本常识2、计算机基本操作3、简单的Pascal程序设计4、简单的数据结构5、基本算法处理,第一章 计算机的基本常识,1.1 计算机概述1.2 数字化信息编码与数据表示1.
5、3 计算机系统的组成1.4 计算机网络1.5 多媒体技术1.6 计算机数据的安全,1.1 计算机概述,一、电子计算机的发展第一台计算机:1946年2月诞生, 电子数字积分计算机(ENIAC), 每秒5000次。分代:,计算机发展趋势:巨型化、微型化、网络化和智能化。,二. 微型计算机的发展,第一台微型计算机: Intel 4004,4位,1969年由Intel公司的M.E.Hoff设计。,三. 计算机在各个领域中的应用 1. 科学计算 2. 数据处理 3. 过程控制 4. 计算机辅助系统 5. 人工智能(AI) 6. 信息高速公路(NII) 7. 电子商务(E-Business),1.2 数字
6、化信息编码与数据表示,一、数字化信息编码信息:数值、文字、语音、图形和图象。信息必须数字化编码,才能传送、存储和处理。,二、进位计数制,计算机中的数制及其转换一、 计算机中数的表示方法-二进制 1 二进制数的运算 电子计算机一般采用二进制数。二进制数只有0和1两个基本数字,容易在 电气元件中实现。 二进制数的运算公式: 000 000 011 010 101 100 1110 111,三、不同进制之间的转换1. r 进制转化成十进制an .a1a0.a-1.a-m (r) = a*rn + + a*r1 + a*r0 +a*r-1+.a*r-m 10101(B)=24+22+1=21101.1
7、1(B)=22+1+2-1+2-2=5.75101(O)=82+1=6571(O)=78+1=57101A(H)=163+16+104106,2. 十进制转化成 r 进制 整数部分:除以 r取余数,直到商为0,余数从右到左排列(反向取余)。 小数部分:乘以 r取整数,整数从左到右排列(顺序取整).直到小数部分乘积为0。,例 100.345(D)=1100100.01011(B),100(D)=144(O)=64(H),100(D)=144(O)=64(H)=1100100(B),100,2,50,2,25,2,12,2,6,2,3,2,1,0,0,0,1,0,0,1,0.345,2,0.690
8、,2,1.380,2,0.760,2,1.520,2,100,8,12,8,1,8,0,4,4,1,100,16,6,0,4,6,16,1,1.04,3. 八进制和十六进制转化成二进制 每一个八进制数对应二进制的三位。 每一个十六进制数对应二进制的四位。2C1D(H)=0010 1100 0001 1101(B) 2 C 1 D7123(O)=111 001 010 011(B) 7 1 2 34. 二进制转化成八进制和十六进制 整数部分:从右向左进行分组。,前边补两个零0100,64(H)=0110 0100(B),144(O)=001 100 100(B),6 4,1 4 4,小数部分:从
9、左向右进行分组。 转化成八进制三位一组。 转化成十六进制四位一组,不足补零。 11 0110 1111.1101 01(B)=36F.D4(H) 3 6 F D 4 1 101 101 110.110 101(B)= 1556.65(O) 1 5 5 6 6 5,四、二进制数在计算机中的表示1. 数的定点和浮点表示定点小数,S,符号位,小数点,|N|=1-2 -m,定点整数,S,小数点,符号位,无符号位,小数点,|N|=2n -1,0=Nx补+-y补=00000110+11111110=00000100=4(D),逻辑元算: 与(,and)、或(,or)、非()、异或(xor)A xor b=
10、a*b+a*b,五、 常用的信息编码1. BCD码每位十进制数用四位二进制数编码表示。2. 西文字符编码: 每一个字符有一个编码。(1) ACSII码(American Standard Code for Information Interchange) , 常用字符有128个,编码从0到127。 空格 20H32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122控制字符:032,127;普通字符:94个。每个字符占一个字节,用7位,最高位为0。(2) EBCDIC码: Extended Binary Coded Decimal Interchange
11、 Code 扩展的二十进制交换码。,25=(0010 0101) BCD 2 5,3. 汉字编码输入码、内码、字形码。 (1) 汉字输入码国标区位码、全拼、双拼、微软拼音、五笔形等。,(2) 汉字内码: 汉字在设备或信息处理系统内部最基本的表达形式, 存储、处理、传输汉字的代码。国标码(GB231280)及其机内码一级汉字:3755个(按拼音排序);二级汉字:3008个(按部首排序)汉字代码表分94个区,每区94位,一个区号和一个位号就可唯一确定一个汉字或符号。每个汉字占两个字节。,区号,区中位置,汉字 国标码 汉字内码沪 2706(00011011 00000110B) 10011011 1
12、0000110B久 3035(00011110 00100011B) 10011110 10100011B,机内码:最高位为1。,通常一个西文字符占一个字节(半角),一个中文字符占二个字节。 汉字的表示方法1.汉字的输入编码 为能直接使用西文标准键盘输入汉字,必须为汉字设计相应的输入编码方法。 主要有以下三类: a数字编码: 常用的是国标区位码,用数字串代表一个汉字输入。区位码将6763个两级 汉字分为94个区,每个区分94位,实际上把汉字表示成二维数组,每个汉字在数组中的下标就是区位码。 区码和位码各两位十进制数字,如中字位于第54区48位,区位码为5448。 b拼音码: 拼音码是以汉语拼音为基础的输入方法。因汉字同音字太多,重码率高,因此输入后还需进 行同音字选择。 c字形编码:字形编码是以汉字的形状来进行的编码。把汉字的笔划部件用字母或数字进行编码,按笔划 顺序依次输入,就能表示一个汉字。如五笔字型编码。 2.汉字内码,