计算机基础知识课件

目录

4.XJ.——1—

1、刖亘

2、计算机基础知识

3、算法及其描述

4、初次使用TURBO-PASCAL(FreePascal)

5、顺序结构程序设计

6、分支结构程序设计

7、循环结构程序设计

8、分支与循环应用加深

9、字符串与数组

10、枚举算法入门

11、数组应用举例

12、过程"函数的简单使用

第一章前言

一、有关NOI的几个问题

1.什么是NOI?

NOI就是NationalOlympiadinInformatics,即全国信息学奥林匹克，它

的分区联赛相当于数学的全国高中联赛,物理上的全国复赛和化学上的全国

初赛。分区联赛分为初赛和复赛，初赛为笔试，复赛为上机编程。复赛从

2001年开始已经改为由全国统一评奖,有的省市也把复赛成绩作为选拔NOI

选手的重要依据。自1995年开始举办，是一项全国性的奥林匹克学科竞赛

活动，是全国中学生五大学科奥林匹克活动之一，其它四项是数学、物理、

化学、生物。每年一届，初赛定于每年的十月份最后一个星期六的下午，复

赛一般在每年的十一月份最后一个星期六或十二月份第一个星期六。初赛和

复赛都是全国统一试题,统一时间考试。初赛以地级市为单位进行组织考试，

以书面考试形式进行，时间两小时。复赛以省为单位，根据初赛参赛人数，

选取5%以内的人参加复赛，根据成绩由高到低评选出省一、二、三等奖。

初赛•般考察计算机基本知识,基本数学能力和基本程序设计知识和能

力。初赛试题的类型一•般有：选择题（基础知识），数学题（•般是推公式），

写程序运行结果题，编程知识（考察范围不定，考过数据结构，算法复杂度

等）和程序填空。

复赛是上机编程，一般是3个小时，4个编程题目。初中组复赛一般是

键盘输入，屏幕输出（有点落后了），而高中组则是文件输入、输出。内容

涉及到搜索、动态规划、简单的图论算法以及一些数学技巧。难度虽不大，

但建议初学者不要眼光太高，尽力把自己有把握的题目做正确就可以了，不

要花很多精力想难题。记住：信息学竞赛从不会给“过程分”，如果程序没

有编完或者没有调试通过，除了你运气好撞到几分之外，几乎可以肯定该题

你将得0分。至于全国竞赛NOL相当于数理化的冬令营比赛，每个省有

3〜4名选手参加，选出国家集训队员20名左右，大家不要把它和分区联赛

搞混淆了，其中的优秀学生参加国家队的集训，并最终选出四名同学组成国

家队参加国际比赛（101）。江苏省这儿年活动开展得比较广泛，都是组织两

个代表队参加全国竞赛。

2、“信息学”学的是什么？

信息学学习内容主要有以下几个方面：

（1）掌握一种结构化的程序设计语言；

（2）计算机相关基础知识；

（3）初等组合，这是信息学解题的思维方式；

（4）图论，主要是基础概念方面的，用于理解算法；

(5)数学问题，这类题目考的是数学思维，其中有一部分是考创造能

力的；

(6)培养分析问题、解决问题的能力。

3、学习过程中要注意什么问题？

第一，要认清自己的位置。也就是根据自己的学习目的，判断自己是什

么水平，经过努力能到达什么水平。

第二，要能熟练的掌握自己使用的编程语言。常常看到有人问一些很简

单的语法问题什么的，其实这些东西都应是基础的知识，只需要翻翻书或看

看系统的帮助就可以弄懂的。如果连编程语言都不了解，又怎么能够编程

呢？这里说的编程语言指的是标准的程序设计语言，例如PASCAL,C/C++»

而一些集成开发环境(IDE)并不属于这个范围，例如DELPHI,VB,VC等。

第三，把一些基础打好，这个非常重要。所谓基础，就是一些基本的算

法，例如：求最小公倍数，高精度，排序，递归，回溯等。

第四，提高正确率。其实第三点说的“打好”基础的意思就是：对于基

础的题目，一定要争取百分百正确！简单的题目一定不能丢分，很难的题目

不要花太多时间，能拿分就可以了。当然，这些建议是对于入门者来说的。

在开始使用编程语言后，你会发现，程序中不能错一点点，哪怕是一个标点，

少一个或多一个，要么是语法不正确，不能运行，要么是另外一个含义，得

不到你想要的结果。因此提高正确率其实首先是要细心加耐心，在此基础上

再全面地考虑问题，得到较多的分数。

附注：程序的三种错误

1.语法错误就是不符合语言的基本规则，编译时不能通过。

2.语义错误程序虽然编译能通过，但是方法不正确或考虑得不全

面。

3.语用错误用户在使用程序时的错误，一个好的程序要有好的用户

界面，尽量避免用户在使用上的错误。对于信息学奥林匹克竞赛的

程序来说，这一点主要是要注意输入、输出的格式符合题目的要求。

第五，要懂得利用网络资源。学会在网络上收集资料，国内有许多学校

和部门都办了相关网站或网页，如我校的网站中的在线辅导

中专门有信息学奥林匹克栏目。当然有许多网页是大同小异。但是有一点要

注意：不要沉溺在网络上。网络能帮助你学习许多知识，也会使一些人荒废

时间，得不偿失。

4、用什么编程语言，什么IDE好？

编程语言主要在以下儿类：

BASIC：如果你是编程初学者，那么BASIC是最适合的，但是由于大

部分这类语言不是结构化的，不适合搞信息学。

PASCAL：这个是最适合初学者学习的，因为这种语言和BASIC一样

简单易学，而且现在国内中学生的竞赛资料都是用PASCAL写的。

C/C++：大学生基本都用这个的，参加ACM（大学生程序设计竞赛）

必学语言。C/C++里面有•些概念可能不太容易被初学编程的中学生接受，

而且如果用得不熟练是很容易出错的。不过，学过PASCAL的人要学C/C++

是很容易的，编程语言的学习是触类旁通的。

有人曾经戏称PASCAL语言是艺术性的语言，C语言是独具匠心的语

言，一个是艺术家用的，另一个是匠人用的，当然这话有点过分。

IDE：

PASCAL：建议初学者使用TurboPascal7.0或者BorlandPascal7.0,要

对调试的基本操作熟悉。以后到了高层次的竞赛，例如NOL是需要free

Pascal的，而且是Linux下的，现在有许多版本的FreePascal在Windows

下也可以使用，你可以从相关网站下载。不过虽然IDE变了，但是用几天

就会熟悉的了。至于DELPHI这种基本语法跟Pascal相似的可视化编程工

具，有点大材小用的感觉。

C/C++：GCC是首选，TurboC++3.0也不错。

选择什么IDE没有本质上的差别，关键是要看写什么程序，对复赛来

说，江苏省从2002年开始高中组建议使用FreePascal,有时也会出现一些

问题，如FreePascal可以充分使用系统内存，而一般的TP变量只能用64KB,

这样会造成选择不同的IDE出现不公平的现象，因此有的比赛指明程序变

量最大使用内存的大小，以体现公平。

二、分区联赛特点和历史回顾

从1995年第一届分区联赛开始，已经比较成熟了。题目的难度和考查

范围从总体来说是逐年增加。初赛主要是靠平时的积累。其中选择题部分各

年差别比较大，考查的范围很不相同。坦白地说，初赛的题目水平并不是很

高，虽然题目有时看起来不大规范，不过从另一方面讲，在选拔复赛选手的

角度讲，初赛题目还是比较成功的。只要基础好（选择题和填空题），有耐

心（完善程序）和细心（写运行结果），初赛一般都能得到高分。至于复赛，

全是上机完成。

三、备战NOI初赛策略

初赛考的知识点，大纲无非是计算机基本常识、基本操作和程序设计基

本知识。选择题考查的是知识，而填空、问题解决题更加重视能力的考查。

一般说来，选择题是不需要单独准备的，也无从准备，只要多用心积累就可

以了。到是问题解决题目比较固定，大家应当做做以前的题目。写运行结果

需要多做题目，培养良好的程序阅读和分析能力，而完善程序最好总结一下

以前题目常常要你填出来的语句类型。这个每年都差不多的，想不出来是可

以回忆一下有哪些可能填的语句，再放到程序里面看是否合适。

（一）、选择题

•般它们是比较容易得分的，一共30分，不可错过。从2003年起增加

了多项选择题，选择题的分数也增加了一些。但是选择题考查的知识范围比

较广，得全分的也只是很少的同学。近几年来，初赛的考查范围有了很大的

变化，越来越紧跟潮流了。这是好事情，不过需要大家有比较广泛的知识，

包括计算机硬件，软件，网络，数据结构（例如栈，队列，排序算法），程

序设计语言以及一些基本的数学知识和技巧（例如排列组合）。

（二）、填空与问题解决题（称之为解答题）

这部分题目对数学要求要高一点，往往考查的是代数变形、数列（一般

是考递推），也考查一些算法和数据结构知识。建议大家多花一点时间做，

尽量做对。

卜面是前几年相关初赛题:

1、数组A［30..100,20..100］以行优先的方式存储，每个元素占8个字节，且已

知A［40,30］的地址为2000,则A［60,90］的地址为:

如果以列优先存储,则为:

［说明］:本题考查了数据结构中数组存储方式，行优先就是先存储满一

行后再存储下一行，而二维数组•般是第一个下标表示行、第二个下标表示

列，行优先可以进行如下的运算:

A[40,31]--A[40,100]70个元素;

A[41,20]--A[41,100]81个元素;

A|42,20|A|42,100]81个元素;L满19行，19*81个

元素

A[59,20]--A[59,IOO]81个元素;

A[60,20]一一A[60,89]70个元素。

所以行优先方式下A［60,90］的存储地址为:

A［40,30］的存储地址+（70+19*81+70）*8

同样可以得到列优先方式下A［60,90］的存储地址为:

A［40,30］的存储地址+（60+59*71+30）*8

2、设栈S的初始状态为空，现有6个元素组成的序列{1,3,5,7,9,11},对该序列

在S栈上依次进行如下操作（从序列中的1开始，出栈后不在进栈）:进栈，出栈,

进栈,进栈，进栈，进栈，出栈，进栈，问出栈的元素序列是:栈顶指针

的值为栈顶元素为:

［说明］:考查了数据结构中的栈，只要熟悉栈的进出规则——“先进后

出”，操作起来并不难。

3、把中缀表达式写成后缀及前缀表达式

(1)(P+Q)*(A-B)/((C+D)/(E-F))-G

后:前:

⑵A-C*D+B/E*(D/A)

后:前:

4、根据后缀表达式，写出前缀及中缀表达式

ABC/DE+GH-/*+

前:中:

［说明］:这两题考查了数据结构中的表达式树。

5、用一个字节来表示整数，最高位用作符号位(1为正,0为负)，其他位表示数

值：

(1)、这样的表示法称为原码表示法，表示数的范围为:

(2)、原码表示法，将出现有两种表示

(3)、实际上计算机中是用补码表示数，其表示范围为:

［说明］:考查了数的原码，补码表示形式，知道了原码就是直接二十进制的

转化，补码是反码的基础上加1,而补码只对非正数应用。

6、已知N*N个数据成方阵排列：

AllA12A13...Ain

A21A22A23...A2n

AnlAn2An3...Ann

已知Aij=Aji,

(1)、将Al1,A21,A22,A31,A32,A33...存储至U一维数组

A(1),A(2),A(3)...A(K)

给出i,j写出求K的表达式:

(2)、将All,A12,...Aln,A22,A23,...A2n,A33...Ann存储到一维数组

A(1),A(2),A(3)...A(K),给出i,j写出求K的表达式:

7、已知一个数列Ul,U2,U3...Un.…往往可以找到一个最小的K值和K个数

al,a2,..,ak,使得数列从某项开始都满足:U(n+k)=al*U(n+k-l)+

a2*U(n+k-2)+...+akUn(式A)例如数列1,1,2,3,5...可以发现：当

K=2,al=l,a2=l时，从第3项起(N>=1)满足:U(n+2)=U(n+l)+Un

试对数列1A3,2八3,3八3，…,N”,..，求K和al,a2,...ak,使得式A成立.

［说明］:这两题实质是考数学。

8、给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,画出

此二叉树。

［说明］:考查你对二叉树遍历的基本了解。

9、给出二叉树的前序遍历与后序遍历，能确定一棵二叉树吗，举例说明。

［说明］:同样考查你对二叉树遍历的基本了解，其实由前序和后序遍历的结

果不能确定二叉树的结构。

10、下面是一个利用完全二叉树特性，用顺序表来存储的一个二叉树,结点数

据为字符型（结点层次从小到大，同一层从左到右顺序存储,#表示空结点,@表

示存储数据结束）

结点123456789101112131415

数据ABC##DE#####GF@

画出对应的二叉树：

［说明］:考查了数据结构中的二叉树

11、用邻接矩阵表示有向图（图略）

［说明］:考查了数据结构中的图的表示

12、根据Nocomachns定理，任何个正整数n的立方，•定可以表示成n

个连续的奇数的和。

例如：

13=1

23=3+5

33=7+9+11

43=13+15+17+19

在这里，若将每一个式中的最小奇数称为X,那么当给出n之后，请写出X

与n之间的关系表达式：

［说明］:其实是考代数

12、某班有50名学生，每位学生发一张调查卡，上写&b,c三本书的书名，

将读过的书打“*”，结果统计数字如下：

只读a者8人；只读b者4人：只读c者3人；全部读过的有2人；读

过a,b两本书的有4人；读过a,c两本书的有2人：读过b,c两本书的有3

人。

（1）读过a的人数是（）。

（2）一本书也没读过的人数是（）。

[说明]:考查逻辑推理的能力，数学好的小学生大概都可以做。

（三）、写运行结果

这是初赛分数占比例最大的部分，是同学得分最多的地方也是部分同学

失分最多的地方。

一般做这类题目的核心是找程序目的，即这个程序想干什么。迄今为止

考过的题目还没有“乱写”的，总有一点“写作目的”的。抓住了它，不仅

得出答案变得很容易了，而且对自己的结果也会比较有信心。写程序运行结

果大纲规定是必考的。试卷中给出的程序并不复杂，语句的含义容易明白，

因此悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案，

而机械模仿计算机硬算出结果的同学往往做得很慢，而且容易失误。

有部分同学在读懂了程序的意思后结果却写错了，主要原因是没有把握

住“临界点”，即条件的具体限定，循环的起始点、结束点等等，往往是多

算一个点或少算一个点。

另外一个就是要注意输出格式，因为写程序运行结果的题一般只有输出

语句才有输出结果，如果读懂了却将格式写错了得不到分数那是最可惜的

了。

1.（1999年分区联赛）

Programexcpl;

var

x,y,yl,jk,jl,g,e:Integer;

a:array[1..2O]of0..9;

begin

x:=3465;y:=264;jk:=20;

forj1:=1to20doa[j1]:=0;

whiley<>0do

begin

yl:=ymod10;y:=ydiv10;

whileyl<>0do

begin

g：=x;

fore:=Jkdownto1do

begin

g:=g+a[e];a[e]:=gmod10;g:=gdiv10

end;

yl:=yl-l

end;

jk:=jk-l

end;

whilea[jl]=Odojl:=jl+l;

forJk:=j1to20dowrite(a[jk]:4);

writein

end.

程序不长，但是有一定的难度。高手最多半分钟就看懂了程序的意思，

但初学者往往算了很久得出了结果却是错的。下面我们还是先以一个初学者

的身份分析•下这个程序。记住，不要一开始就模拟电脑来一个个语句“执

行”。

分析程序一般从以下几点入手：

I、变量

首先是变量的名字。可惜分区联赛题目中的变量不是I就是J,很讨厌。

I和J•般作为循环计数器，没有什么意思，因此不要管它了。然后要看变

量在程序的哪里出现过，着重看它与其他变量的相互引用关系，猜测它的作

用。例如上题。x只在g:=x中出现，暂时不要管它，因为它很可能只是一

个初始数据。y有三处:1)whiley<>0do2)yl:=ymod10;3)y:=ydiv10;

很明显，y每次少了最后一位数字，把这位数字给了yU有经验的选手应该

体会到了什么，不过我们继续。现在我们知道了：y对程序的作用是：每次

提供最后一位给yl,即yl每次的值依次是：4,6,2

yi：

l)whileyloOdo

2)yl=yl-l

很明显就是一个循环嘛！循环yl次！

jk:

l)fore:=jkdownto1do

2)jk:=jk-l

jk作为循环初始值，居然一次比一次少…其原因有待进一步分析。

jl：

l)forjl:=lto20doa[j1]:=0;

2)jl：=l；

3)whilea[jl]=Odojl:=jl+l;

4)forJk:=j1to20dowrite(a[jk]:4);

显然，jl和其它变量没有什么联系。1)是初始化，2)3)4)是输出数组a

g：出现的位置是几层循环之内了，应该很重要！一会儿再分析！

e:作为循环变量，没有什么意思。

通过变量分析，我们知道了：x.y是数据，y每次提供最后一位给yl,

循环yl次。jl和g的作用有待分析。

2、程序结构

我们把程序分成几块。

1)x:=3465;y:=264;jk:=20;

forjl:=lto20doa|jl]:=0;

初始化。不要管它。

2)whiley<>0do

begin

yl:=ymod10;y:=ydiv10;

whileyloOdo

begin

«g：=x;

fore:=Jkdownto1do

begin

g:=g+a[e];a[e]:=gmod10;g:=gdiv10

end;

»

yl:=yl-l

end;

jk=k-l

end;

3)

whilea[jl]=0dojl:=jl+l;

forJk:=jlto20dowrite(a[jk]:4);

writein

输出结果，也不要管它。

块2最重要。它的思想是：每次取Y的最第位yl,执行<o>yl次，每

次把jk减一。现在最重要的是<<>>中的在干什么。注意到最后输出的a[],

要留意叫的变化!a[e]总是取个位(gmod10),g每次少一位,和a[e-l](别

忘了e在循环！)相加…难道是...高精度加法？？？它执行了yl次，yl每次

都是y的个位…对了。程序就是在做x*y所以答案就是3465*264=914760

再看它的输出格式，输出的应该是：―9—1—4—7—6—0

其实有经验的话，看到g这个变量名和g:=g+a[e];a[e]:=gmod10;这几

个标志句子。就可以一下子知道程序的用意了。

<<>>中只有6行，你可以模拟电脑“执行”几个语句在找规律。方法

是：把循环“展开”，再写一个变量值表，即：语句执行后变量情况：

g：=x；

g:=g+a[e];g=x+a[e];

a[e]:=gmod10;a[e]:=x+a[e]的个位

g：=gdiv10;g=（x+a[e]）的前111位

g:=g+a[e-l];g=（x+a[e]）的前几位+a[e-l];

a[e-l]:=gmod10;a[e-l]=a[e-l]+（x+a[e]）的进位

（四）完善程序

这部分题目得分率似乎不高。许多同学有这样的感觉，这道题如果纯粹

作为一•个编程题，自己还能写出程序，但是试题中必须要根据它所设定的算

法来实现，通常的感觉是不知道程序中要你做什么，不能读懂它的算法基本

思想。对于这一类题目，往往要先多读几遍题意，理解要实现什么，然后是

理程序中的数据结构、变量含义，最后才去考虑填什么语句。

这类试题常常让大家填的是：

1、初始化（i：=0；j：=0；fori:=1tondoa[i]:=0之类的）

2、一些明显的动作：

（1）结果没有储存在需要的地方。

（2）累加器没有做加法

（3）输出

3、关键动作。在算法描述中出现的比较关键的步骤。例如交换排序程序的

“交换”操作等很明显需要完成的操作。分析方法和写运行结果类似，注意

分析变量和程序结构，理解变量和模块的作用是解题的关键。

以2003年初赛题为例（初中组第二题、高中组第一题）：

“翻硬币”

[题意]:

有M枚硬币堆在一起，从上面开始先一次将一枚翻过来，再一次将两枚

一起翻过来……最后将M枚一起翻过来,再从上面开始第一次将上面一枚翻

过来,一次将上面两枚一起翻过来……直到最后还有所有M枚全部正面朝上

为止。要求总的翻硬币次数。

[说明]:

这道题如果纯粹作为•个编程题，大家可能会用“模拟法”写出相关程

序，设置一个标志数组，模拟这个过程，每翻一次都检查一下是否是全部正

面朝上，最后输出翻的次数就可以。问题是题中给出的程序不是用这种方法,

而是用的数学推导关系，也就是说要求你找出翻的总次数跟M的关系。在短

的时间内找出这样的规律很难，因此此题得分率很低，几乎没有同学当场能

做出。

［程序清单］:

programprogram42;

varm:integer;

functionsolve(m:integer):longint;

vari,t,d:longint;

flag:boolean;

begin

ifm=lthen(1)

else

begin

d:=2*m+l;t:=2;i:=1;flag:=false;

repeat

ift=lthenbeginsolve:=i*m;flag:=true;end

elseift=_______(2)then

beginsolve:=(3)______;flag:=true;end

else(4);

i:=i+l;

untilflag;

end;

end;

begin

read(m);

if(m>0)and(m<2000)thenwriteln((5));

end.

［分析］:

仔细阅读和分析题意，可以能够填出第一个和第五个，因为只有一枚时

要翻两次，而主程序中没有引用函数，在输出时直接引用0问题是其它三个

如何填，在短时间内很难找出相关数学关系，如果有一台电脑，先写出模拟

法的程序，运算出m不同数值时的对应结果，再从中找出关系还好些，初

赛的性质决定了只能由人工来模拟计算机工作，找出其中的规律。

从solve函数中可以看出分成了M=1和M>1两种大的情况，在M>1

的情况下，结果的不同与t有关，程序中根据t分为三种情况，其中t=l时

的结果已经给出(为i*m),而另外两种情况是要求你自己完成的，其中一

种情况是能够决定翻的次数的，而整个程序中没有看到对t进行处理的语句，

所以要完成的任务一是：t为另一值时所确定的翻硬币的次数，任务二是：t

为其它情况时对t的处理，这个处理的赋值语句肯定与m有关。仔细看一看

程序，其中又引进了一个变量d,它的值是2*m+l,已有的代码中也没有用

到这个变量，可以猜想给t赋值的表达式肯定是一个跟d有关的式子。

如果能结合“模拟法”程序运行得出的结果，比较结果跟i、m的关

系，就能方便地找出规律（通项公式）。

以下是m为不同值时;相关几个变量跟结果的关系：

m=3d=72*m=6重复t:=t*2modd运算，直到t=l或t=2*m

i123

t241solve=i*m=9

m=4d=92*m=8

i123

t248solve=i*m-l=3*4-l=ll

m=5d=ll2*m=10

i12345

t248510solve=1*01-1=5*5-1=24

m=6d=132*m=12

i123456

t2483612solve:=i*m-1=6*6-1=35

m=7d=152*m=14

i1234

t2481solve:=i*m=4*m=28

m=15d=312*IIF30

i12345

t248161solve:=i*m=5*l5=75

m=16d=332*m=32

i12345

t2481632solve:=i*田一1=5*16T=79

m=30d=612*m=60

i1234567891011121314151617181920212223

24252627282930

t248163236122448359183611224427544733510

20401938153060

solve:=I*m-1=899

所以本题应填的结果为：

(1)solve:=2

⑵2*m

(3)i*m-l

(4)t:=2*tmodd

(5)solve(m)

综上所述，初赛还是有一定的难度的，但是只要基础打牢，系统训练

过的同学正常发挥应该能拿到50以上的分数的。

至于复赛题型与内容，在后续的内容里再向大家介绍。

附：

全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲（修改稿）

1.试题知识范围：

初赛内容与要求

1.计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网

络的主要特征、数字化）

2.信息输入输出基本原理（信息交换环境、文字图形多媒体信息输入输出方式）

计

3.信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，

算和存储程序原理、程序的三种基本控制结构）

机

4.信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）

的

5.信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可

扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、

WEB应用的主要方式和特点）

6.人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及

交互操作））

7.信息技术的新发展、新特点、新应用等。

基

本1.Windows和LINUX的基本操作知识

操2.互联网的基本使用常识（网上浏览、搜索和查询等）

作3.常用的工具软件使用（文字编辑、电子邮件收发等）

程1.程序语言中基本数据类型（字符、整数、长整数、浮点）

序2.浮点运算中的精度和数值比较

3.一维数组（串）与线性表

设4.记录类型（PASCAL）/结构类型（C）

计1.结构化程序设计的基本概念

2.阅读理解程序的基本能力

的3.具有将简单问题抽象成适合计算机解决的模型的基本能力

基4.具有针对模型设计简单算法的基本能力

5.程序流程描述（自然语言/伪码/NS图/其他）

本6.程序设计语言（PASCAL/C/C++,2003年仍允许BASIC）

知1.初等算法（计数、统计、数学运算等）

基本算法2.排序算法（冒泡法、插入排序、合并排序、快速排序）

识处理3.查找（顺序查找、二分法）

4.回溯算法

复赛内容与要求

在初赛的内容上增加以下内容：

数1.指针类型

据2.多维数组

结3.单链表及循环链表

构4.二叉树

5.文件操作（从文本文件中读入数据，并输出到文本文件中）

1.算法的实现能力

2.程序调试基本能力

3.设计测试数据的基本能力

4.程序的时间复杂度和空间复杂度的估计

1.离散数学知识的应用（如排列组合、简单图论、数理逻辑）

2.分治思想

3.模拟法

4.贪心法

5.简单搜索算法（深度优先广度优先）搜索中的剪枝

6.动态规划的思想及基本算法

2.比赛中使用的程序设计语言是：

2003年：初赛：BASIC、PASCAL或C/C++；

复赛：BASIC、PASCAL或C/C++。

2004年：初赛：BASIC、PASCAL或C/C++

复赛：PASCAL或C/C++。

2005年及之后：初赛：PASCAL或C/C++

复赛：PASCAL或C/C++。

第二章计算机基础知识

一、二进制数

计算机内信息的存储、运算等主要通过二进制。

二进制的特点：只有两个基本数字。和1;逢二进一位。

二进制的优点：因为它只有两个基本数字0和I,所以容易物理实现。

所谓物理实现，指的是通过不同的物理状态来表示不同的数字。如在计算机

的内部，对于0和1可以通过高电平（电压稍高一点的电流）和低电平（电

压稍低一点的电流）来表示。又如在软磁盘上存放一个0或1,可以通过磁

性的强弱来表示。

二进制的缺点：读写不方便。有时又引进八进制或十六进制来方便描述。

因为8是2的3次方，所以三位二进制跟一位八进制相对应；同样四位二

进制跟一位十六进制相对应。八进制有8个基本数字：01234567,它的特点

是逢八进一位。而十六进制的有十六个基本数字：0123456789ABCDEF,它

的特点是逢十六进一位。下面是几种进制的对照表：

十进制二进制八进制十六进制

0000

1111

21022

31133

410044

510155

611066

711177

81000108

91001119

10101012A

11101113B

12110014C

13110115D

14111016E

15111117F

16100002010

19100112313

20101002414

我们知道十进制的每一位的权代表的是十的若干次方，不同进制的数,

基数不同，其每位上所代表的值大小也不同，我们称之为“权”。

①十进制数，逢十进一。如(219)IO=2*1O2+1*1OI+9*1O0

432

②二进制数，逢二进一。如(11010)2=1*2+1*2+0*2+1*2'+0*2°=26

③八进制数，逢八进一。如(273)8=2*82+7*8'+3*8°=187

21

④十六进制数，逢十六进一。如(27B)l6=2*16+7*16+11*16°=635

从以上.的计算中可以看到：进制不同，基数不同，每位上权值大小也不

同，数值大小也不相同。

将十进制数转换为任意进制数的基本方法为：将十进制数除以所定的进

制数反向取余，如将十进制数39转为二进制数：

2I39_________

2I191

2I91

2I41

2\J20

21_10

201

39(10)=100111(2)39=32+4+2+1=100111(2)

又如将245转为八进制:245(10)=365(8)

8I245

8I305八

8I36

803

对于十进制小数转为其他进制的小数，则是不断将小数部分乘以进制数

取整，作为转换后的小数部分，直到为零或精确到小数点后第几位。如

0.35(10)=0.01011(2),0.125(10)=0.001(2)

任意进制数转为十进制数的基本方法是按权展开求和，前面①②③④例

子已说明。

二、信息代码及ASCH码

信息在计算机内存储或运算是通过二进制来实现的，计算机本身并不要

求你按什么规律来将信息转换为什么代码，只有你给出对应规律就行。也就

是说谁都可以来定义代码，但如果这样各自乱定义没有统一的规定，对于计

算机与计算机之间的信息交换就不能保证了。

国际上统一使用美国信息交换标准代码ASCH码。ASCII码用八位的二

进制表示，基本的ASCII字符集共128(2的7次方)个，其二进制代码最

高位为0,如“A”对的编码为01000001(2),相当于十进制65。中国汉字

编码用两个字节表示，为了区别一般编码，其最高位设为1。汉字国标区位

码GB2312-80又称区位码，共分94个区，两位的区号和两位的位号惟一确

定一个汉字或符号，01到15区为符号区，16到55区为一级汉字(以拼音

为序）共3755个，56以后的二级汉字（以部首为序）共3008个。

其它常见的代码有BCD码等（四位二进制只取前面的4位从而方便地

跟十进制对应起来）。

三、原码、反码、补码

对于正数，在计算机内部都是采用原码表示的，即原来是什么就表示成

相应的二进制数。一般第一位为符号位。

如+65,对应的二进制数是100（）001,加上符号位为01000001。

对于负数或0可能用补码表示。补码是在反码的基础上加上1。而反码

就是取反的操作，将0变为1,1变为0。

由于采用了补码，使0的表示唯一了。

（问题：如果都是用原码表示，0的两种表示是什么？）

四、其它一些计算机基础知识

I.计算机的产生与发展

1946年世界上第一台电子计算机——埃尼阿克（ENIAC）于美国产生。

计算机的发展经历了四代：第一代电子管计算机、第二代晶体管计算机、第

三代中小规模集成电路计算机、第四代大规模和超大规模集成电路计算机。

我国从1956年开始电子计算机的科研与教学工作，1983年12月成功

地研制成功每秒运行1亿次以上的“银河”巨型计算机。1992年11月研制

成功每秒运行10亿次的“银河H”巨型计算机，1997年又研制成功每秒运

行130亿次的“银河HI”巨型计算机。

2.计算机系统及其工作原理

（1）计算机系统组成

计算机系统由硬件和软件两部分组成。硬件指计算机的各种元器件；软

件指程序的有关的文档资料。

主要硬件：

①输入设备常见的有键盘、鼠标、扫描仪等。

②输出设备常见的有显示器、打印机、绘图仪等。

③中央处理器CPU它包括运算器和控制器，运算器进行算术运算和逻

辑运算，控制器是计算机的指挥系统，它的操作过程是取指令——分

析指令——执行指令，循环执行。

④存储器具有记忆功能的物理器件，用于存储信息，存储器分为内存

和外存。内存是半导体存储器，它分为只读存储器（ROM）、随机存储

器（RAM）和高速缓存（cache）,一般所说的计算机内存大小是指RAM

的大小，如128MB、64MB、32MB等。外存现在主要有磁性存储器（软

盘和硬盘、磁带等）和光电存储器（光盘等），它们可以作为永久性

存储器。存储器的两个重要技术指标：存取速度和存储容量，内存的

存取速度快，叮CPU速度相匹配，软盘的存取速度慢。存储容量是指

存储信息量的大小，它用字节（Byte）作为基本单位，1个字节用8

位二进制（Bit）表示（即lByte=8bit）,1KB=1O24B,1MB=1024KB,

1GB=1024MB...«

计算机的软件：

分为系统软件和应用软件。系统软件是管理和使用计算机的软件，主要

有操作系统软件如Windows95/98/2000/NT、DOS、UNIX等，其中Windows

系列是多任务可视化图形界面，而DOS是字符命令格式的单任务的操作系

统。应用软件是为了某个应用目的而编写的软件，主要有辅助教学软件、辅

助设计软件、文字处理软件、工具软件以及其它的应用软件。

（2）计算机的工作原理

到目前为止，电子计算机的工件原理均采用冯.诺依曼的存储程序思想，

其工作过程如下图：（控制器发出控制信号控制其它器件工作）

程序中的数据、指令都采用数字化编码方式，保存在存储器中，程序中

的指令必须是属于这台机器的指令系统。

（3）计算机病毒：是一种程序，是人为设计的具有破坏性的程序。

3、DOS的常用命令及其应用

（1）文件

文件是指记录在存储介质（如磁盘、光盘等）上的一组相关信息的集合。

文件夹（又称子目录）将文件人为地分组存放，每一组给定一个名字，

则称这个组为文件夹。

文件的基本操作有建立、存储、复制、删除、重命名、移动、建立子目

录（文件夹）、删除子目录（文件夹）、进入子目录（文件夹）、退出子目录

（文件夹）。

（2）内部命令

是指当DOS启动后，计算机引导程序将系统以及常用的命令处理模块驻

留在计算机的内存中。

常用的内部命令有：

目录类DIR（显示文件目录）、MD,CD,RD（建立、进入、删除子目录）。

文件类COPY（拷贝）、DEL（册U除）、TYPE（显示内容）、REN（或RENAME

改名）

功能类CLS（清屏）、TIME（查或改系统时间）、DATE（查或改系统日期）、

VER（查有关版本信息）等。

（3）外部命令

存储在外存储器上的DOS可执行文件（扩展名为COM、EXE或BAT

的），当用户使用外部命令时，计算机就从外存调入内存，当执行完命令，

就自动从内存中退出。常用的外部命令有：FORMAT（格式化磁盘）、

DISKCOPY（磁盘拷贝）等。

4.Windows基本知识

系统资源与资源管理器，文件与文件夹

运行程序：窗口执行、命令执行（可执行文件exe、com、bat）、不可直

接执行文件（要其它可执行系统的支持或提供给其它程序使用）o

文件的类型：主要通过扩展名来区别，如.pas表示PASCAL的源文件。

5.网络的基本知识

（1）概念

将地理位置不同的计算机用通信手段连接起来，并共同遵守一定的协

议，共享计算机的软、硬件资源。因特网是网络的集合，是全球最大的网络。

（2）网络类型

网络分为局域网（局限于某个范围内的网络连接）和广域网（跨地区的

范围广的网络，因特网是覆盖全球的广域网）。

（3）因特网提供的服务主要功能有：

信息浏览（WWW）文件传输（FTP）发送电子邮件（E-mail）

电子公告牌（BBS）远程登录（telnet）电子商务

网址的结构如http:〃

其是http:〃超文本浏览协议www.sina表示主机域名

com——网络机构域名，这里是商业网，其它的如net、gov等

cn——地区域名，这里是中国域名，其它如hk为香港、tw为台湾，

不加地区域名的为国际域名。

电子邮件地址：如yuekingl21@163.com这里yuekingl21是用户名，

@是分隔符号，163是主机名。

网络内容比较多，请参见本章后阅读材料。

6.Linux操作系统

是一种免费的操作系统，使用越来广泛，详见阅读材料。

7.汉字输入方法

汉字的输入方法很多，大体分为：流水码（序码）、音码、形码、音形

码。

流水码：区位码、电报码、通讯密码等均属于流水码，优点是重码少（几

乎没有重码），缺点是难于记忆。其中区位码比较早的有GB2013/80,每个

汉字或符号均对应一个四位数，前两位为区号，后两位为位号。如“、”的

区位码为“0102”。前15个区为基本符号,16-55区为一级汉字（常用汉字）,

根据拼音的顺序排列，56区以后为二级汉字（不常用的汉字），按部首的顺

序排列。

音码：以汉语拼音作为编码输入汉字，优点是大多数人都易于掌握，但

同音字多，重码率高，影响输入的速度。

形码：以汉字的字形进行编码，编码的规则比较多，难于记忆，要经过

训练才能较好地掌握，一般重码很少，能达到较高的速度。

音形码：将音码和形码结合起来，减少重码率，提高汉字输入速度。

五、计算机语言

计算机语言是人与计算机进行交流的一种工具，通过它可以编写程序，

让计算机完成交给它的系列任务。

计算机语言分为机器语言、汇编语言、高级语言。

机器语言是计算机唯一能够直接识别的语言，无论是操作符和操作数都

是由0和1组成的，其优点是简单，执行效率高，缺点是读写起来很不方便，

且通用性差，不同的计算机其机器语言也不一样。

汇编语言是机器语言的符号化，只是增加了可读性，但仍然是通用性不

强，编程时要对相应机器有所了解，换句话说就是要有一定的计算机专业基

础才能写出程序。不同类型、不同档次的计算机其汇编语言也不一样的。

由于机器语言和汇编语言都是针对机器而言的，汲及到底层的操作，有

人把它称为低级语言。而直接面向应用的是高级语言，只要用户能够确定好

算法，不需要对机器了解多少就能够写出程序，且高级语言都跟自然语言比

较接近（几乎都是英语）。一般所说的程序设计语言都是指的高级语言。高

级语言很多，常见的有BASIC、PASCAL.C、FORTRAN等。

由于计算机能直接执行的只有机器语言，所以其它语言写的程序都要有

一个“翻译”的过程。这种翻译分为两种：解释方式和编译方式。

解释方式就是一边翻译一边执行，下一次执行时还要翻译，还要依赖于

程序系统。

编译方式是将整个程序翻译成机器能够执行的代码，以后只要执行这个

翻译好的代码就行了，不要重新翻译了。在TurboPascal7.0里，运行程

序前会自动编译，一般情况下会在磁盘里生成一个同主名的exe（可执行）

文件。

［阅读材料］:

一、网络基础知识

1、网络的概念：计算机网络(Network)是将处在不同地理位置且相互独立

的计算机或设备，通过传输介质和网络设备按照特定的结构和协

议相互连接起来，利用网络操作系统进行管理和控制，从而实现信息传

输和资源共享的一种信息系统。

2、网络的发展：

ARPAnet

ARPAnetC高级研究计划署网络，AdvancedResearchProjectsAgencynet)

是世界上第一个计算机网络，出现在20世纪60年代后期，由美国国防部资

助。其第一个节点于1969年在加利福利亚大学洛杉矶分校安装，最终发展

成为今天的Internet。

我国Internet的发展

1987年9月下旬，钱天白教授发出我国第一封电子邮件“越过长城，

通向世界“，揭开了中国人使用Internet的序幕。

3、网络的分类：

(1)按照地理范围分类

局域网(LocalAreaNetwork,LAN)

覆盖范围一般不超过数十公里，通常是一幢建筑物内、相邻的几幢建筑

物之间或者是一个园区的网络。

广域网(WideAreaNetwork,WAN)

覆盖范围通常为数百公里到数千公里，甚至数万公里，可以是一个地区

或一个国家，甚至世界几大洲或整个地球。

城域网(MetropolitanAreaNetwork,MAN)

覆盖的地理范围介于局域网和广域网之间，通常为数十公里到数百公里

的一座城市内。

(2)按照管理方式分类

对等网(PeertoPeer)

通常是由很少几台计算机组成的工作组。对等网采用分散管理的方式，

网络中的每台计算机既作为客户机又可作为服务器来工作，每个用户都管理

自己机器上.的资源。

客户机/服务器网(Client/Server)

网络的管理工作集中在运行特殊网络操作系统服务器软件的计算机上进

行，这台计算机被称为服务器，它可以验证用户名和密码的信息，处理客户

机的请求。而网络中其余的计算机则不需要进行管理，而是将请求通过转发

器(Redirector)发给服务器。

(3)按照数据传输方式分类

广播网络(BroadcastingNetwork)

网络中的计算机或设备通过一条共享的通信介质进行数据传播，所有节

点都会收到任何节点发出的数据信息。这种传输方式主要应用于局域网中。

广播网络中有三种传输类型：单播、组播和广播。

点对点网络(PointtoPointNetwork)

网络中的计算机或设备通过单独的链路进行数据传输，并且两个节点间

都可能会有多条单独的链路。这种传播方式主要应用于广域网中。

4、网络拓扑结构：总线拓扑、星形拓扑、环形拓扑、网状拓扑、混合拓扑、

蜂窝拓扑

二、协议和参考模型

1、什么是协议：

协议是网络中计算机或设备之间进行通信的一系列规则的集合。

协议示例，以发送消息“HELLOSTUDENTS”为例：

|0口|4|H|E|L|L|O|S|T|U|D|E|N|T|S-|

常用协议有：IP、TCP、HTTP,POP3、SMTP

2、分层结构的优点：

各层间相互独立，某一层的变化不会影响其他层

促进标准化工作

使网络易于实现和维护

3、分层结构的工作原理：

纵向通信

在分层结构中，低层服务为高层服务提供服务，高层服务使用低层服务

提供的服务。

横向通信

分层结构中，对应的分层协同工作，以保证能够成功的完成通信。

4、OSI参考模型

具体7层数据格式功能与连接方式典型设备

应用层网络服务与使用者应

Application用程序间的一个接口

表示层数据表示、数据安全、

Presentation数据压缩

会话层

建立、管理和终止会话

Session

传输层数据组织成数据用一个寻址机制来标

Transport段(Segment)识一个特定的应用程

序(端口号)

网络层分割和重新组合基于网络层地址(IP地

Network数据包(Packet)址)进行不同网络系统路由器

间的路径选择

数据链路层将比特信息封装通过使用