漳浦第一中学信息学竞赛复习资料一.docx
- 文档编号:600168
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:54
- 大小:91.06KB
漳浦第一中学信息学竞赛复习资料一.docx
《漳浦第一中学信息学竞赛复习资料一.docx》由会员分享,可在线阅读,更多相关《漳浦第一中学信息学竞赛复习资料一.docx(54页珍藏版)》请在冰点文库上搜索。
漳浦第一中学信息学竞赛复习资料一
漳浦第一中学信息学竞赛复习资料一
——整理:
林文英2012-04-01
一、数据类型及函数1
二、全国青少年信息学(计算机)奥林匹克分区联赛竞赛大纲3
第一节计算机的基本常识4
第三节计算机网络常识10
第四节计算机信息安全基础知识12
第一章开始编写pascal语言程序14
第一章有关数论的算法14
第三章排列与组合20
第四章程序阅读类24
第一节栈和队列24
第三节 数组26
第六章排序算法29
一、数据类型及函数
1.数据类型
integer(整形:
-32768-32767)
longint(长整形:
-2147483648-2147483647)
shortint(短整型:
-128-127)
byte(字节类型:
0-255)
word(双字节类型:
0-65535)
int64(-9223372036854775808-9223372036854775807)
{但知道此类型不可用于循环变量,操作速度较慢}
2.实数类型:
real(基本实型,2.9e-39..1.7e)
single(但精度实型,1.5e-45..3.4e)
double(双精度实型,5.0e-324..1.7e)
extended(扩展实型)
comp(装配实型
布尔类型:
boolean(布尔型,false-true)
字符类型:
char(字符);string[x](字符串,串长0..255);AnsiString(x:
0-255)
//string[x]括号内数字x用于限定串长来节省空间,x可省略
3.常用标准
标准常量
False,Maxint,True,Maxlongint,Pi
标准类型
Boolean,Char,Real,Integer,Longint,等等
标准函数
Abs,Arctan,Chr,Cos,Eof,Eoln,Exp,Ln,Odd,Ord,Pred,Round,Sin,Sqr,Sqrt,Succ,Trunc
标准过程
Dispose,Get,New,Pack,Page,Put,Read,Readln,Reset,Rewrite,Unpack,Write,Writeln
标准文件
Input,Output
4.自变量必须为整型的标准函数:
(A)前趋函数:
Pred(x),函数结果类型为整型,如:
Pred(4)=3
(B)后继函数:
Succ(x),函数结果类型为整型,如:
Succ(4)=5
(C)奇函数:
odd(x),结果为布尔型。
如:
Odd(13)=True
(D)字符函数:
Chr(x)其中x为ASCII码,函数结果为字符型。
如:
Chr(65)='A'
(2)自变量为整型(或实型),但函数值类型为实型的标准函数;
(A)平方根函数:
Sqrt(x)
(B)整数函数:
Int(x)取整数部分,如:
INT(3.85)=3.0
(C)小数函数:
Frac(x)
(D)正弦函数:
Sin(x)
(E)余弦函数:
Cos(x)
(F)反正切函数:
Arctan(x),单位为弧度
Pascal中无正切函数,用Sin(x)/Cos(x)代替
(G)指数函数:
Exp(x),即求ex
(H)对数函数:
Ln(X),即求x的自然对数logex
幂运算∵xy=eylnx ,∴xy=Exp(y*ln(x)
注意:
在FreePascal中,幂的表示:
xy==power(x,y)或xy=x**y
(I)随机函数:
Random(x:
word),无x时,函数值取[0,1)之间的随机小数;有x且为Word
类型时,函数值取[0,x)之间的随机整数。
前面加上:
Randomize语句。
(J)圆周率函数PI=3.1415926536
5.自变量为整型(或实型),但函数值类型与x一致的标准函数
(A)Abs(x):
绝对值函数,如:
Abs(-2)=2 Abs(-2.0)=2.0000000000E+00
(B)Sqr(x):
平方函数如,如:
Sqr(4)=16 Sqr(4.0)=1.6000000000E+01
(4)自变量为整型(或实型),但函数值类型为整型的标准函数
(A)Trunc(x):
取整数部分,如:
Trunc(3.85)=3
(B)Round(x):
四舍五入,如:
Round(2.8)=3 Round(-2.8)=-3
(5)加1函数:
inc(x)如:
inc(5)=6,inc(5,8)=13
(6)减1函数dec(x)如:
dec(5)=4dec5,3)=2
6.文件函数:
(1)Eof(f)或Seekeof(f)未读到文件结束符“Chr(26)”或“Ctrl+Z”时,函数值为false;读到文件结束符时,函数值为true;
(2)Eoln(f)或SeekEolf(f)未读到行结束符“Chr(13)”时,函数值为false; 读到行结束符或文件结束符时,函数值为true;
7.字符函数
(1)小写字母转为大写字母Upcase('x'),如:
Upcase('a')='A'
(2)前趋函数:
Pred('x'),函数结果为字符型,如:
Pred('4')='3'
(3)后继函数:
Succ('x'),函数结果为字符型,如:
Succ('A')='B'
(4)序数函数:
Ord('x'),函数结果为整型,求字符对应的ASCII码,如:
Ord('A')=65
(5)字符函数:
Chr(x),x为整型,函数结果为字符型,,求ASCII码对应得字符,如:
Chr(65)='A'
8.字符串函数
(1)求长度length
定义:
functionLength(S:
String):
Integer;
(2)复制子串copy
定义:
functionCopy(S:
String;Index:
Integer;Count:
Integer):
String;
注意:
S是字符串类型的表达式。
Index和Count是整型表达式。
Copy返回S中从Index开始,Count个字符长的一个子串。
(3)插入子串insert
定义:
procedureInsert(Source:
String;varS:
String;Index:
Integer);
注意:
Source是字符串类型的表达式。
S是任意长度字符串类型变量。
Index是整型表达式。
Insert把Source插在S中Index处。
如果结果字符串的长度大于255,那么255之后的字符将被删除。
(4)删除子串delete
定义:
procedureDelete(varS:
String;Index:
Integer;Count:
Integer);
注意:
S是字符串类型变量。
Index和Countare是整型表达式。
Delete删除S中从Index开始的Count个字符。
如果Index大于S的长度,则不删除任何字符;如果Count大于S中从Index开始的实际字符数,则删除实际的字符数。
(5)字符串转为数值val
定义:
procedureVal(S;varV;varCode:
Integer);
在这里:
S是由一系列数字字符构成的字符串类型变量;。
V是整型或实型变量;Code是Integer型变量,注意:
Val将S转为它的数值形式。
(6)数值转为字符串str
定义:
procedureStr(X[:
Width[:
Decimals]];varS:
string);注意:
将数值X转成字符串形式。
(7)求子串起始位置pos
定义:
functionPos(Substr:
String;S:
String):
Byte;
注意:
Substr和S字符串类型表达式。
Pos在S中搜索Substr并返回一个integer值,这个值是Substr的第一个字符在S中的位置。
如果在S中没有找到Substr,则Pos返回0。
(8)字符完全串连+联
定义:
操作符加号+把两个字符串联在一起。
(9)字符串压缩空格串连-
定义:
操作符减号-去掉第一个字符串最后的空格后,将两个字符串联在一起。
(10)将数组批量填入初值,Fillchar(x,sizeof(x),0),将0填入到x数组中,
sizeof(x)表示填入的个数
HALT结束程序,返回操作系统
EXIT结束过程或函数,返回调用处(在主程序中同HALT)
BREAK是用来退出其所在的循环语句(CONTINUE是继续当前循环)
计算机对字符的排序是按照字符的ASCII码值的大小进行排序的。
汉字的排序则是根据汉语拼音的字母的ASCII码值进行排序。
二、全国青少年信息学(计算机)奥林匹克分区联赛竞赛大纲
一、初赛内容与要求:
(#表示普及组不涉及,以下同)
计基
算本
机常
的识
*诞生与发展 *特点 *在现代社会中的应用
*计算机系统的基本组成
*计算机的工作原理# *计算机中的数的表示
*计算机信息安全基础知识 *计算机网络
计基
算本
机操
的作
*MSDOS与Windows的使用基础
*常用输入/输出设备的种类、功能、使用
*汉字输入/输出方法
*常用计算机屏示信息
程
序
设
计
基
本
知
识
程序的表示
*自然语言的描述
*PASCAL或BASIC语言
数据结构的类型
*简单数据的类型
*构造类型:
数组、字符串
*了解基本数据结构(线性表、队列与栈)
程序设计
*结构化程序的基本概念
*阅读理解程序的基本能力
*具有完成下列过程的能力:
现实世界(指知识范畴的问题)
—>信息世界(表达解法)
—>计算机世界(将解法用计算机能实现的数据结构和算法描述出来)
基本算法处理
*简单搜索 *字串处理
*排序 *查找
*统计 *分类 *合并
*简单的回溯算法
*简单的递归算法
二、复赛内容与要求:
在初赛的内容上增加以下内容(2002年修改稿):
计算机
软件
*操作系统的使用知识
*编程语言的使用
数
据
结
构
*结构类型中的记录类型
*指针类型
*文件(提高组必须会使用文本文件输入)
*链表
*树
*图#
程
序
设
计
*程序设计能力
*设计测试数据的能力
*运行时间和占用空间的估算能力#
算
法
处
理
*排列组合的应用
*进一步加深回溯算法、递归算法
*分治法
*搜索算法:
宽度、深度优先算法
*表达式处理:
计算、展开、化简等#
*动态规划#
第一节计算机的基本常识
1.1计算机的产生和发展1.2计算机的系统及工作原理
1.3计算机中有关数、编码的基本常识
1.4原码、反码与补码1.5逻辑运算
1.1计算机的产生与发展
计算机的产生是20世纪最重要的科学技术大事件之一。
世界上的第一台计算机(ENIAC)于1946年诞生在美国宾夕法尼亚大学,到目前为止,计算机的发展大致经历了四代:
① 第一代电子管计算机,始于1946年,结构上以CPU为中心,使用计算机语言,速度慢,存储量小,主要用于数值计算;
②第二代晶体管计算机,始于1958年,结构上以存储器为中心,使用高级语言,应用范围扩大到数据处理和工业控制;
③第三代中小规模集成电路计算机,始于1964年,结构上仍以存储器为中心,增加了多种外部设备,软件得到了一定的发展,文字图象处理功能加强;
④第四代大规模和超大规模集成电路计算机,始于1971年,应用更广泛,很多核心部件可集成在一个或多个芯片上,从而出现了微型计算机。
我国从1956年开始电子计算机的科研和教学工作,1983年研制成功1亿/秒运算速度的“银河”巨型计算机,1992年11月研制成功10亿/秒运算速度的“银河II”巨型计算机,1997年研制了每秒130亿运算速度的“银河III”巨型计算机。
目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。
计算机的通信产业已经成为新型的高科技产业。
计算机网络的出现,改变了人们的工作方式、学习方式、思维方式和生活方式。
1.2计算机系统及工作原理
1.计算机的系统组成
计算机系统由软件和硬件两部分组成。
硬件即构成计算机的电子元器件;软件即程序和有关文档资料。
(1)计算机的主要硬件
输入设备:
键盘、鼠标、扫描仪等。
输出设备:
显示器、打印机、绘图仪等。
中央处理器(CPU):
包括控制器和运算器运算器,可以进行算术运算和逻辑运算;控制器是计算机的指挥系统,它的操作过程是取指令——分析指令——执行指令。
存储器:
具有记忆功能的物理器件,用于存储信息。
存储器分为内存和外存
①内存是半导体存储器(主存):
它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器(Cache);
ROM:
只能读,不能用普通方法写入,通常由厂家生产时写入,写入后数据不容易丢失,也可以用特殊方法(如紫外线擦除(EPROM)或电擦除(EEPROM_)存储器);
RAM:
可读可写,断电后内容全部丢失;
Cache:
因为CPU读写RAM的时间需要等待,为了减少等待时间,在RAM和CPU间需要设置高速缓存Cache,断电后其内容丢失。
②外存:
磁性存储器——软盘和硬盘;光电存储器——光盘,它们可以作为永久存器;
③存储器的两个重要技术指标:
存取速度和存储容量。
内存的存取速度最快(与CPU速度相匹配),软盘存取速度最慢。
存储容量是指存储的信息量,它用字节(Byte)作为基本单位,
1字节用8位二进制数表示,1KB=1024B,1MB=1024KB,lGB=1024MB
(2)计算机的软件
计算机的软件主要分为系统软件和应用软件两类:
①系统软件:
为了使用和管理计算机的软件,主要有操作系统软件如,WINDOWS95/98/2000/NT4.0、DOS6.0、UNIX等;WINDOWS95/98/2000/NT4.0是多任务可视化图形界面,而DOS是字符命令形式的单任务的操作系统。
②应用软件:
为了某个应用目的而编写的软件,主要有辅助教学软件(CAI)、辅助设计软件(CAD)、文字处理软件、工具软件以及其他的应用软件。
2.计算机的工作原理
到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计算机自动存取指令(计算机可执行的命令=操作码+操作数)并执行它。
工作原理图如下:
1.3计算机中有关数及编码的知识
1.计算机是智能化的电器设备
计算机就其本身来说是一个电器设备,为了能够快速存储、处理、传递信息,其内部采用了
大量的电子元件,在这些电子元件中,电路的通和断、电压高低,这两种状态最容易实现,
也最稳定、也最容易实现对电路本身的控制。
我们将计算机所能表示这样的状态,用0,1来
表示、即用二进制数表示计算机内部的所有运算和操作。
2.二进制数的运算法则
二进制数运算非常简单,计算机很容易实现,其主要法则是:
0+0=00+1=11+0=11+1=0 0*0=00*1=01*0=01*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
(11010)2=1*24+1*23+0*22+1*21+1*20
(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)任意进制的数转换十进制
按权值展开:
如:
(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编码
由于计算机是电器设备,计算机内部用二进制数,这样对于从外部输入给计算机的所有信息必须用二进制数表示,并且对于各种命令、字符等都需要转换二进制数,这样就牵涉到信息符号转换成二进制数所采用的编码的问题,国际上统一用美国标准信息编码(ASCII)它可用7位二进制数表示,存储时用一个字节,它的最高位为0。
因此基本的ASCII字符集有128个如:
0-9:
48-57:
00110000-...
A-Z:
65-90:
01000001-...
a-z:
97-122:
01100000-...
6.汉字编码与汉字输入法
(1)机内码
ASCII码不能表示汉字,因此要有汉字信息交换码,我国国家标准是gb2312,它也被称作国际码。
它由两个字节组成,两个字节的最高位都为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。
当真值为正时:
原码、反码、补码数值位完全相同;
当真值为负时:
原码的数值位保持原样,
反码的数值位是原码数值位的各位取反,
补码则是反码的最低位加一。
注意符号位不变。
如:
若机器数是16位:
十进制数17的原码、反码与补码均为:
0000000000010001
十进制数-17的原码、反码与补码分别为:
1000000000010001、111111*********0、111111*********1
1.5逻辑运算
1.逻辑运算
逻辑与:
同真则真
逻辑或:
有真就真
逻辑非:
你真我假
逻辑异或:
不同则真
2.按位运算
按位与∩:
同1则1如10010101∩10110111=10010101
按位或∪:
有1则1如10010101∪10110111=10110111
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=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.1DOS(DiskOperatingSystem)的组成
MS—DOS采用模块结构,它由五部分组成:
ROM中的BIOS模块、IO.SYS模块、
MSDOS.SYS模块、COMMAND.COM模块和引导程序。
(1)BIOS模块:
在PC机主板上有一个ROM芯片,该芯片中存有系统自测试程序,
CMOS设置程序和基本输入输出程序(BIOS)。
BIOS是一组程序和参
表,其中程序部份是可以通过中断方式调用的一组驱动程序,参数
给出外设的地址和参数。
BIOS是计算机硬件和操作系统之间的接口
通过它操作系统管理计算机硬件资源。
(2)IO.SYS模块:
IO.SYS是MS—DOS和ROMBIOS之间的接口程序。
它和RON
BIOS一起完成系统设备的管理。
(3)MSDOS.SYS模块:
MSDOS.SYS用于实现文件管理,包括文件管理、目录管理、
内存管理等功能。
它以功能调用的形式实现用户和MS—DOS
之间的程序级接口。
(4)COMMAND.COM模块:
COMMAND.COM的主要功能是负责接收、识别、解释和执行
用户从键盘输入的MS—DOS命令。
(5)引导程序:
引导程序又叫“引导记录”,其作用是检查当前盘上是否有两个系统文件,若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 漳浦 第一 中学 信息学 竞赛 复习资料