《全国信息学奥林匹克联赛培训hpyq》由会员分享，可在线阅读，更多相关《全国信息学奥林匹克联赛培训hpyq（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应用的主要方式和特点）
3、6.人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作） 7.信息技术的新发展、新特点、新应用等。,分区联赛初赛大纲（计算机基本常识二）,分区联赛初赛大纲（计算机基本操作）,计算机的基本操作 1.WINDOWS和LINUX的基本操作知识 2.互联网的基本使用常识 （网上浏览、搜索和查询等） 3.常用的工具软件使用（文字编辑、电子邮件收发等）程序设计的基本知识,分区联赛初赛大纲（程序设计）,1.结构化程序设计的）基本概念 2.阅读理解程序的基本能力 3.具有将简单问题抽象成适合计算机解决的模型的基本能力 4.具有针对模型设计简单算法的基本能力 5.程序流程描述（自然语言/
4、伪码/NS图/其他） 6.程序设计语言（PASCAL/C/C+，2003年仍允许BASIC）,分区联赛初赛大纲（简单数据结构）,1.程序语言中基本数）据类型(字符、整数、长整数、浮点) 2.浮点运算中的精度和数值比较 3.一维数组（串）与线性表 4.记录类型（PASCAL）/ 结构类型（C）,分区联赛初赛大纲（基本算法）,1.初等算法（计数、统计、数学运算等） 2.排序算法（冒泡法、插入排序、合并排序、快速排序） 3.查找（顺序查找、二分法） 4.回溯算法,初赛目录,1、计算机的基本常识 2、计算机基本操作 3、简单的Pascal程序设计 4、简单的数据结构 5、基本算法处理,第一章 计算机的
5、基本常识,1.1 计算机概述 1.2 数字化信息编码与数据表示 1.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.
6、 信息高速公路(NII) 7. 电子商务（E-Business）,1.2 数字化信息编码与数据表示,一、数字化信息编码 信息：数值、文字、语音、图形和图象。 信息必须数字化编码，才能传送、存储和处理。,二、进位计数制,计算机中的数制及其转换 一、 计算机中数的表示方法-二进制 1 二进制数的运算 电子计算机一般采用二进制数。二进制数只有0和1两个基本数字，容易在 电气元件中实现。 二进制数的运算公式： 000 000 011 010 101 100 1110 111,三、不同进制之间的转换 1. r 进制转化成十进制 an .a1a0.a-1.a-m (r) = a*rn + + a*r1 +
7、 a*r0 +a*r-1+.a*r-m 10101(B)=24+22+1=21 101.11(B)=22+1+2-1+2-2=5.75 101(O)=82+1=65 71(O)=78+1=57 101A(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
8、,25,2,12,2,6,2,3,2,1,0,0,0,1,0,0,1,0.345,2,0.690,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 D 7123(O)=111 001 010 011(B) 7 1 2 3 4. 二进制转化成八进制和十六进制 整数部分：从右向左进行分组。,前边补两个零0100,64(H)=
9、0110 0100(B),144(O)=001 100 100(B),6 4,1 4 4,小数部分：从左向右进行分组。 转化成八进制三位一组。 转化成十六进制四位一组，不足补零。 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=N=2 n+1 -1,m+1位,n+1位,浮点数,阶码
10、,数符,110.011(B)=1.100112+10=11001.12-10=0.1100112+11,阶符,尾数,11,0,0,110011,N= 数符尾数2阶符阶码 尾数的位数决定数的精度。 阶码的位数决定数的范围。,2. 机器数的表示 机器数：一个数及其符号在机器中的表示数值化。 直值：机器数所代表的数。 假定一个数在机器中占用8位。,原码: 最高位位符号位,正数位0,负数位1,其余表示其绝对值.+17原=00010001 -39原=10100111 0有两种表示方式:+0=00000000,-0=10000000 反码: 正数的反码与原码相同,负数的反码是把其原码除符号位外的各位取反（
11、即0变1，1变0）+17反=00010001， 0有两种表示方式:+0=00000000,-0=11111111， -39反=11011000 补码:在进行减法运算时，数的原码表示显得很不方便，于是就引进了数的补码表示 正数的补码与原码反码相同,负数的补码是在其反码的最低有效位上加1（即等于正数的反码加1） 0有唯一的表示方式 +0补=-0补=00000000,X=6,y=2,求x-y -x补+-y补=00000110+11111110=00000100=4(D),逻辑元算： 与（,and）、或（,or）、非（）、异或(xor) A xor b=a*b+a*b,五、 常用的信息编码 1. BC
12、D码 每位十进制数用四位二进制数编码表示。 2. 西文字符编码: 每一个字符有一个编码。 (1) ACSII码(American Standard Code for Information Interchange) , 常用字符有128个，编码从0到127。 空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122 控制字符：032，127；普通字符：94个。 每个字符占一个字节，用7位，最高位为0。 (2) EBCDIC码: Extended Binary Coded Decimal Interchange Code 扩展的二十进制交换码
13、。,25=(0010 0101) BCD 2 5,3. 汉字编码 输入码、内码、字形码。 (1) 汉字输入码 国标区位码、全拼、双拼、微软拼音、五笔形等。,(2) 汉字内码： 汉字在设备或信息处理系统内部最基本的表达形式， 存储、处理、传输汉字的代码。 国标码(GB231280)及其机内码 一级汉字：3755个（按拼音排序）；二级汉字：3008个（按部首排序） 汉字代码表分94个区，每区94位，一个区号和一个位号就可唯一确定一个汉字或符号。 每个汉字占两个字节。,区号,区中位置,汉字 国标码 汉字内码 沪 2706(00011011 00000110B) 10011011 10000110B
14、久 3035(00011110 00100011B) 10011110 10100011B,机内码：最高位为1。,通常一个西文字符占一个字节（半角），一个中文字符占二个字节。 汉字的表示方法 1.汉字的输入编码 为能直接使用西文标准键盘输入汉字，必须为汉字设计相应的输入编码方法。 主要有以下三类： a数字编码： 常用的是国标区位码，用数字串代表一个汉字输入。区位码将6763个两级 汉字分为94个区，每个区分94位，实际上把汉字表示成二维数组，每个汉字在数组中的下标就是区位码。 区码和位码各两位十进制数字，如“中“字位于第54区48位，区位码为5448。 b拼音码： 拼音码是以汉语拼音为基础的输
15、入方法。因汉字同音字太多，重码率高，因此输入后还需进 行同音字选择。 c字形编码：字形编码是以汉字的形状来进行的编码。把汉字的笔划部件用字母或数字进行编码，按笔划 顺序依次输入，就能表示一个汉字。如五笔字型编码。 2.汉字内码,汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码，一般采用两个字节表示。 英文字符的机内代码是七位的ASCII码，当用一个字节表示时，最高位为0，为与之相区别，汉字机内代码中 两个字节的最高位均为1。 3.汉字字模码 字模码是用点阵表示的汉字字形代码，它是汉字的输出形式。 根据汉字输出要求不同， 点阵的多少也不同。简易型汉字为1616点阵，提高型汉字为2424点阵、3232点阵或更高。因此字模点 阵的信息量是很大的，所占存储空间也很大。如1616点阵，每个汉字占32字节，国标两级汉字要
