第一讲：计算机的基础知识

第三讲信息学竞赛基础知识

初赛试题结构第一部分基础知识(20*1.5=30)第二部分问题求解(2*5=10)第三部分阅读程序(4*8=32)第四部分完善程序(2*14=28)一、计算机发展及应用1、第一台电子计算机的诞生1946年，世界上第一台数字式电于计算机是由美固宾夕法尼亚大学的物理学家约翰·莫克利（JohnMauchly）和工程师普雷斯伯·埃克特（J.hesper.Eckert）领导研制的取名为ENIAC（ElecotmnicNurnericalIntegratorAndCalculator）的计算杌。

冯·诺依曼依据存储程序的工作原理设计出第一台具有存储程序功能的计算机EDVAC（离散变量自动电子计算机）。EDVAC由运算器、控制器、存储器、输人设备和输出设备这五部分组成，输入设备运算器存储器控制器输出设备输入输出第一台具有存储程序功能的计算机EDVAC2、计算机发展的几个阶段

第一代（1946～1958）第二代（1958～1964）第三代（1964～1975）第四代（1975～至今）主要电子器件电子管晶体管中小规模集成电路大规模／超大规模集成电路①微型计算机的问世是由于（）的出现。(NOIP8)A）中小规模集成电路B）晶体管电路C）（超）大规模集成电路D）电子管电路C3、计算机应用⑴科学计算（数值计算）：利用计算机解决科学研究和工程技术中所提出的复杂的数学问题。⑵数据处理（信息处理）：利用计算机对所获取的信息进行记录、整理、加工、存储和传输等。⑶人工智能：利用计算机来模仿人类的智力活动。⑷自动控制：利用计算机对动态的过程进行控制、指挥和协调。⑸计算机辅助设计和制造：利用计算机来辅助工程师们设计和制造产品。CAI（计算机辅助教学）CAM（计算机辅助制造）CAT（计算机辅助测试）CAD（计算机辅助设计）CAE(计算机辅助教育)CIMS（计算机集成制造系统）①图灵(AlanTuring)是（

）。(NOIP9)

A）美国人

B）英国人

C）德国人

D）匈牙利人

艾伦·麦席森·图灵（AlanMathisonTuring，1912年6月23日-1954年6月7日），英国数学家1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。图灵对于人工智能的发展有诸多贡献，例如：图灵曾写过一篇名为《机器会思考吗？》（CanMachineThink?）的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。图灵奖是美国计算机协会于1966年设立的，又叫"A.M.图灵奖"，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦·图灵，这个奖设立目的之一是纪念这位科学家。其他知识点：B②第一个给计算机写程序的人是（

）。(NOIP9)

A）AlanMathisonTuring

B）AdaLovelace

C）JohnvonNeumannD）JohnMc-Carthy

E）EdsgerWybeDijkstr1、英国著名诗人拜伦的女儿AdaLovelace曾设计了巴贝奇分析机上解伯努利方程的一个程序。她甚至还建立了循环和子程序的概念。由于她在程序设计上的开创性工作，AdaLovelace被称为世界上第一位程序员。2、董铁宝是“中国第一个程序员”。董铁宝1945年赴美国学习，在伊利诺伊大学学习、研究时，他参与了第一代电子计算机伊利亚克机的设计、编程和使用。董铁宝于1956年回到中国并任教于北京大学，成为王选（计算数学专业院士）的老师。董铁宝在1968年文化大革命期间自杀身亡。B二、保护知识产权：《计算机软件保护条例》最早是1991年6月4日国务院发布的<<计算机软件保护条例>>，现已废止。现公布《计算机软件保护条例》，自2002年1月1日起实施

。第二章软件著作权第八条

软件著作权人享有下列各项权利：（一）发表权（二）署名权（三）修改权（四）复制权；（五）发行权（六）出租权（七）信息网络传播权（八）翻译权（九）应当由软件著作权人享有的其他权利。①计算机软件保护法是用来保护软件()的（NOIP7）A)编写权B)复制权C)使用权D)著作权三、计算机病毒计算机病毒是一种功能较特殊的计算机程序，计算机病毒的特征可以归纳为下面两点：⑴能够将自身复制到其他程序中。⑵不独立以文件形式存在，仅附加在别的程序上。失去这两个特征中的任何一个，都不成其为病毒。D①计算机病毒是()(NOIP7)A)通过计算机传播的危害人体健康的一种病毒B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C)一种由于计算机元器件老化而产生的对生态环境有害的物质D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒②计算机病毒的特点是（）(NOIP6)

A.传播性、潜伏性、易读性与隐蔽性B.破坏性、传播性、潜伏性与安全性

C.传播性、潜伏性、破坏性与隐蔽性D.传播性、潜伏性、破坏性与易读性

③计算机病毒传染的必要条件是：（）。(NOIP8)A）在内存中运行病毒程序B）对磁盘进行读写操作C）在内存中运行含有病毒的可执行的程序D）复制文件BCB四、计算机的组成1、计算机的硬件系统由五个基本部分组成：运算器控制器存储器（有内存储器和外存储器之分）输人设备输出设备①CPU访问内存的速度比访问下列哪个（些）存储设备要慢（

）。（NOIP9）

A）寄存器

B）硬盘

C）软盘

D）高速缓存

E）光盘②微型计算机中，（）的存取速度最快。(NOIP8)A）高速缓存B）外存储器C）寄存器D）内存储器③在计算机硬件系统中，cache是()存储器(NOIP7)A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲ADAD2、三总线结构：

地址总线、数据（包括指令）总线和控制总线，分别传送地址信号、数据信号和控制信号。①中央处理器（CPU）能访问的最大存储器容量取决于（）。(NOIP8NOIP7)A）地址总线B）数据总线C）控制总线D）实际内存容量②计算机系统总线上传送的信号有（）(NOI6)

A.地址信号与控制信号B.数据信号、控制信号与地址信号

C.控制信号与数据信号D.数据信号与地址信号

AB五、计算机指令系统计算机能直接识别和执行的命令称为指令。指令本身是二进制代码。是要计算机执行某种操作的命令。用机器指令编写的程序称之为机器语言程序。一条指令通常由操作码和地址码两部分组成。六、计算机的数字系统数值信息在计算机内的表示方法就是用二进制数来表示。一般说来，如果数制只采用R个基本符号，则称为基R数值，R称为数制的基数，而数制中每一固定位置对应的单位值称为权。进制基数R基本符号二进制20，1八进制80,1,2,3,4,5,6,7十进制100,1,2,3,4,5,6,7,8,9十六进制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F（对应十进制数的10—15。）进位计数制的编码符合“逢R进位”的规则，各位的权是以R为底的幂，一个数可按权展开成为多项式。例如，一个十进制数256.47可按权展开为256.47=2×102＋5×101＋6×10°十4×10-1＋7×10-21、R进制转换为十进制基数为R的数字，只要将各位数字与它的权相乘，其积相加,和数就是十进制数例:3506.28=6×8°+0×81+5×82+3×83+2×8-1=1862.25

例:0.2A16=2×16-1+10×16-2

=0.16406252、十进制转换为R进制将＋进制数转换为基数为R的等效表示时，可将此数分成整数与小数两部分分别转换，然后再拼接起来即可实现。＋进制整数转换成R进制的整数，可用十进制数连续地除以R，其余数即为R系统的各位系数。此方法称之除R取余法。十进制小数转换成R进制时，可连续地乘以R，直到小数部分为0，或达到所要求的精度为止（小数部分可能永不为零），得到的整数即组成R进制的小数部分，此法称为“乘R取整”例：将0.312510转换成二进制数0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0所以0.312510=0.010123、二、八、十六进制的相互转换二、八、十六进制的相互转换在应用中占有重要的地位。由于这三种数制的权之间有内在的联系，即23=8，24=16，因而它们之间的转换比较容易.即每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，位组划分是以小数点为中心向左右两边延伸，中间的0不能省略，两头不够时可以补0。例如：将1011010.102转换成八进制和十六进制数001011010.1001011010.102＝132.48132.401011010.10001011010.102=5A.816

5A.8将十六进制数F7.28变为二进制数F7.28F7.2816=11110111.00101211110111.00101000①十进制数2003等值于二进制数（

）。(NOIP9)

A）0100000111

B）10000011

C）110000111

D）11111010011

E）1111010011②十进制书11/128可用二进制数码序列表示为:()。(NOIP8)A）1011/1000000B）1011/100000000C）0.001011D）0.0001011③算式（2047）10－（3FF）16＋（2000）8的结果是（）。(NOIP8NOIP7)A）（2048）10B）（2049）10C）（3746）8D）（1AF7）16④64KB的存储器用十六进制表示，它的最大的地址码是()(NOIP7)A)10000B)FFFFC)1FFFFD)EFFFFDDAB⑤十进制算术表达式3*512+7*64+4*8+5的运算结果，用二进制表示为().(NOIP5)A·10111100101B·11111100101C·11110100101D·11111101101⑥下列无符号数中，最小的数是（）(NOIP6)

A.（11011001）2B.(75)10C.(37)8D.(2A)16⑦运算式(2008)10-(3723)8的结果是（

）。NOIP9

A）(-1715)10

B)(5)10

C)(5)16

D)(101)2

E)(3263)8

BCBCD七、在计算机中带符号数的表示法原码在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各位表示数值部分。如：10000010，00000010补码正数的补码就是该正数本身。[01100100]补＝01000100对于负数:两头的1不变，中间取反。[10100100]补＝11011100

[+0]补＝[-0]补＝00…0。反码〈0ne’sComplement〉反码的定义如下:⑴对于正数，它的反码表示与原码相同。即[x]反=[x]原⑵对于负数，则除符号位仍为“1”外，其余各位“1”换成”0”，”0”换成1”，即得到反码[X]反。例如[-1101001]反=10010110。⑶对于0，它的反码有两种表示:[+0]反=00…0[-0]反=11…1BCD码（8421码）BCD码就是用二进制代码表示的十进制数，也称BCD数。它是用二进制代码0000—1001来表示十进制数0---9。如：39的BCD码为00111001。①已知x=（0.1011010）2，则[x/2]补=（）2。(NOIP8)A）0.1011101B）11110110C）0.0101101D）0.100110②[x]补码=10011000，其原码为()(NOIP7)A)011001111B)11101000C)11100110D)01100101CB八、信息存储单位⑴位（bit，缩写为b）：度量数据的最小单位，表示一位二进制信息。⑵字节(byte，缩写为B)：一个字节由八位二进制数字组成（lbyte＝8bit）。字节是信息存储中最常用的基本单位。计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。常用的单位有：KB1K=1024MB1M=1024KGB1G=1024MTB1t=1024G机器字（word）：字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它取决于机器的类型、字长以及使用者的要求。常用的固定字长有8位、16位、32位等。九、计算机网络知识1、计算机网络的拓扑结构网络中各个站点相互连接的方法和形式称之为网络拓扑总线拓扑星型拓扑

环型拓扑

树型拓扑

2、计算机网络体系结构的核心是OSI模型国际标准化组织（ISO）提出的开放系统互联参考模型（OSI）已成为网络体系结构的标准在这些层中，除了最高的第7层没有需要服务的上一层、最低的第1层没有可利用服务的下一层外，其它的每一层都建立在下一层的基础上，利用下一层来实现自己的功能，并向上一级提供服务。主机A与主机B进行通信时，通信协议是在对等层之间进行的。其中，物理层与物理层之间的通信协议是直接的，其他对等层之间的通信协议都是间接的。3、Internet网络地址(IP地址)A类网络为大型网络；B类网络为中型网络；C类网络为小型网络。这三类网络的地址特征为⑴A类网络以0开头，网络号码是7位，主机号码是24位⑵B类网络以10开头，网络号码是14位，主机号码是16位⑶C类网络以110开头，C类网络的网络号码是21位，主机号码是8位D类地址以1110开头，E类地址以11110开头。八、逻辑运算：与/\、或：\/,运算优先级：/\>\/①假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A/\B\/C/\D的值是（

）。(NOIP9)

A）true

B）false

C）0

D）1

E）NULL②已知A=35H，A/\05H\/A/\30H的结果是：（）。(NOIP8)A）30HB）05HC）35HD）53HAC

九、其他

①(NOIP6)电线上停着两种鸟：A，B，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类；

一类是两端的小鸟相同；另一类则是两端的小鸟不相同。

已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）。

A.奇数B.偶数C.可奇可偶D.数目固定B②(NOIP8)要使1．．．8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（）。12345678461-17

32A）6B）0C）5D）3③(NOI2003)32只球队参加比赛，要想最后决出冠亚军，至少进行（）场比赛。（A）31(B)33(C)34(D)35CD信息学竞赛中的数学知识从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.2.组合的定义:从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.3.排列数公式:4.组合数公式:1.排列的定义:排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.加法原理和乘法原理从A到C共有多少中走法？ABC例1

学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？解先排学生共有种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有种选法.根据乘法原理,共有的不同坐法为种.结论1插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.分析此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待.所涉及问题是排列问题.例25个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?

解

因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有种排法,其中女生内部也有种排法,根据乘法原理,共有种不同的排法.结论2捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.分析此题涉及到的是排队问题,对于女生有特殊的限制,因