基础 NOIP 初赛.ppt

《基础 NOIP 初赛.ppt》由会员分享，可在线阅读，更多相关《基础 NOIP 初赛.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息学奥林匹克信息学奥林匹克分区联赛的基础知识分区联赛的基础知识 初赛试题结构初赛试题结构第一部分基础知识第二部分问题求解第三部分阅读程序第四部分完善程序第一部分一、计算机的发展与应用二、计算机概述三、多媒体技术应用四、计算机网络使用基础一、计算机的发展与应用一、计算机的发展与应用1、下面列出的四项中，不属于计算机病毒特征的是()A潜伏性B激发性C传播性D免疫性2、国产银河型数字式电子计算机是属于下列哪种类型计算机()A微型B小型C中型D巨型3、计算机病毒是指()A能传染给用户的磁盘病毒B已感染病毒的磁盘C具有破坏性的特制程序D已感染病毒的程序4、最早的计算机的用途是用于()A科学计算B自动控

2、制C辅助设计D系统仿真5、操作系统在第几代计算机开始应用()A第一代B第二代C第三代D第四代第二代晶体管计算机(1956-1963)1948年，晶体管的发明大大促进了计算机的发展，晶体管代替了体积庞大电子管，电子设备的体积不断减小。1956年，晶体管在计算机中使用，晶体管和磁芯存储器导致了第二代计算机的产生。第二代计算机体积小、速度快、功耗低、性能更稳定。首先使用晶体管技术的是早期的超级计算机，主要用于原子科学的大量数据处理，这些机器价格昂贵，生产数量极少。1960年，出现了一些成功地用在商业领域、大学和政府部门的第二代计算机。第二代计算机用晶体管代替电子管，还有现代计算机的一些部件还有现代计

3、算机的一些部件:打印机、磁带、磁盘、打印机、磁带、磁盘、内存、操作系统内存、操作系统等。等。计算机中存储的程序使得计算机有很好的适应性，可以更有效地用于商业用途。在这一时期出现了更高级的COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等语言，以单词、语句和数学公式代替了含混晦涩的二进制机器码，使计算机编程更容易。新的职业(程序员、分析员和计算机系统专家)和整个软件产业由此诞生。1什么是CISC机？什么是RISC机？2计算机的发展分为几个阶段？正在研制的新型计算机具有哪些特点？3简述“三金”工程的含义。4什么

4、是计算机病毒，它具有哪些特征，如何采取具体的防范措施？资料CISC微处理器是台式计算机系统的中心，这个核心中的核心就是运行指令的电路。指令由完成任务的多个步骤所组成，例如把数值传送进寄存器或进行相加运算，都是需要指令的，这些指令被称为微代码（microcode），不同制造商的微处理器有不同的微代码系统，制造商可按自己的意愿使微代码做得简单或复杂。指令系统越丰富，微处理器编程就越简单，然而，执行速度也相应越慢，而且设计这样的处理器的代价也就越大，但是由于指令系统丰富，对上层的支持就比较好。下面我们来看看两种处理器的比较：复杂指令系统计算机（CISC）包含一个丰富的微代码系统，简化了处理器上运行程

5、序的编制。精简指令系统计算机（RISC）有一个精简的指令系统。从而提高了微理器的效率，但需要更复杂的外部程序，也就是把在处理器层没有完成的工作放到了上层进行，而处理器层少的这些成本可以用对物理器件速度的提高上去。RISC方案基于JohnCocke在IBM公司的工作，他发现约20的计算机指令完成约80的工作。因此，RISC系统通常比CISC系统要快。他的8020规则促进了RISC体系结构的开发。大多数台式微处理器方案如Intel和Motorola芯片都采用CISC方案；工作站处理器加MIDS芯片DECAlpha和IBMRS系列芯片均采用RISC体系结构。将来的处理器会在RISC和CISC之间寻找

6、到一条合适的途径来保证处理器的成本较小，而且功能比较合适。二、计算机概述1.世界上首先实现存储程序的电子数字计算机是（）。AENIACB、UNIVACC、EDVACD、EDSAC2、计算机能直接执行的指令包括两部分，它们是()A源操作数与目标操作数B操作码与操作数CASCII码与汉字代码D数字与字符3、下列诸因素中，对微机工作影响最小的是()A尘土B噪声C温度D湿度4、在计算机中，ASCII码是几位二进制代码()A7B8C12D165、下面四个不同进制的数，最小的一个数是()A(11011001)2B(37)8C(75)10D(A7)16资料1简述冯诺依曼型计算机的组成与工作原理。2计算机硬件

7、系统由哪五个基本部分组成？它们各自的功能是什么？3机器指令由哪几部分组成？按其功能分为哪几种指令类型？4.在计算机中，带符号数有几种表示方法？它们之间的转换关系是什么？各自有什么用途？5ASCII码由几位二进制数组成？它能表示什么信息？6二进制的计算规则。三、多媒体技术应用1彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（）。A.红B.白C.蓝D.绿E.橙2下面哪个部件对于个人桌面电脑的正常运行不是必需的（）。A.CPUB.图形卡（显卡）C.光驱D.主板E.内存3.下列哪个（些）不是个人计算机的硬件组成部分（）。A.主板B.虚拟内存C.电源D.硬盘E.总线4.一个文本屏幕有25列及80

8、行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，屏幕左上角开始，位移为0，然后逐列逐列存储。求位于屏幕（X，Y）的第一个字节的位移是（）A.（Y*80+X）*2-1B.（Y-1）*80+X-1）*2C.（Y*80+X-1）*2D.（Y-1）*80+X）*2-11.多媒体计算机系统的基本配置包含了哪些设备？2CD-ROM的功能大小取决于哪几个参数？3显示存储空间由哪几个主要的因素决定？4目前国际上有哪几种压缩数据的标准？资料四、计算机网络使用基础1、Internet的规范译名应为()A英特尔网B因

9、特网C万维网D以太网2、下列哪些计算机网络不是按覆盖地域划分的()A局域网B都市网C广域网D星型网3、以下列举Internet的各种功能中，错误的是()A编译程序B传送电子邮件C查询信息D数据库检索4、计算机网络最突出的优点是()A传送信息速度高B共享资源C内存容量大D交互性好5、TCPIP协议共有()层协议A.3B.4C.5D.61什么是WAN网？什么是LAN网，他们各自的功能是什么？2什么是计算机网络的拓扑结构？常见的拓扑结构有几种？3.什么是计算机网络协议？说出OSI的七层协议的名称。4.在Internet中，IP地址和域名的作用是什么？它们之间有什么异同？资料第二部分数学知识组合、排列

10、、集合等数据结构图、树等第三部分阅读程序直接推理有流程图推断算法动态模拟由底向上阅读分析例一Varm,n,i:integer;t:extended;Beginread(n,m);t:=1;fori:=1tomdot:=t*(n-i+1)/i;writeln(t:0:0);End.输入：105输出：例二Label10,20,30;Vars,p:string;I,k,n,j,m:integer;Beginreadln(s);n:=length(s);readln(p);m:=length(p);i:=0;10:i:=i+1;j:=I;k:=1;例二（续）20:Ifsjpkthenbeginifin

11、-m+1thengoto10;i:=0;goto30;endelseifkmax then begin _(3)_;p1:=I;q1:=j;end;end;For i:=p1 to _(4)_ doBegin for j:=q1 to _(5)_do write(aI,j:3);writeln;end;readln end.例二例二Constmaxm=10000;VarI,k,m,n,rest,start,temp:longint;a:array0.maxmoflongint;Beginwrite(inputm,n:);readln(m,n);fori:=0tom-1doai:=random(

12、100);writeln(beforemove);fori:=0tom-1dowrite(ai:5);writeln;rest:=m;start:=0;while_(1)_dobegink:=start;repeatk:=(k+n)modmuntilk=n;if b=n then find:=_(2)_ else find:=_(3)_End;例（续）例（续）Procedurep(n:integer);Vara:integer;begina:=find(n);iffirstthenbeginwrite(a:4);first:=false;endelsewrite(+,a:4);ifa=0;X补

13、=2(n+1)+X，当-2n=X=1例如：X=+100101X补=0100101X=100101X补=1011011特点:1.补码的和等于和的补码补码的和等于和的补码,符号位和数值位一样参加符号位和数值位一样参加运算运算,不必单独处理不必单独处理,即即 X补补+Y补补=X+Y补补2.补码相减:X补-Y补=X补+-Y补Y补-Y补:符号位连同数值位一起取反加1反码表示法当X=0时，X反=X当X=0时，符号位为1，其余各位取反。特点:1.反码的和等于和的反码2.有二个零+0=000-0=1113.当最高位有进位而丢掉进位(即2)时,要在最低位加1(循环进位)原码,反码和补码之间的转换X反符号位不变符

14、号位不变数值位不变不变(符号位为0)变反(符号位为1)+,0,1X真值X原数值位不变数值位不变数值位不变不变(符号位为0)变反加1(符号位为1)符号位不变符号位不变X补当当X为正数，为正数，X反反=X原原=X补补=X，当当X为负数时，为负数时，X补补=X反反+1，X补补=X原原2.5ASCII码ASCII码是美国信息交换标准代码的缩略语。是目前国际上最为流行的字符信息编码方案。它包括数字09、大小写字母和专用符号等95种可打印字符，还有33种控制字符。一个字符ASCII码通常占一个字节，用七位二进制编码组成，ASCII码最多可表示128个不同的符号。字节的最高位被很多系统用做校验码，以便提高字

15、符信息传输的可靠性。2.12汉字信息编码汉字信息也采用二进制的数字化信息编码。目前的汉字编码方案有二字节、三字节甚至四字节的。国标码（国家标准信息交换用汉字编码），是二字节码，用七位二进制数编码表示一个汉字。目前国标码收入6763个汉字，其中一级汉字（最常用）3755个，二级汉字3008个，另外还包括682个西文字符、图符。2.6二进制采用二进制，优点：（1）易于物理实现（2）二进制运算简单（3）机器可靠性高（4）通用性强乘法除法整数转换小数转换0+0=00+1=11+0=11+1=100*0=00*1=01*0=01*1=13.2CD-ROM光驱的技术指标光驱的技术指标(1)数据传输率(Da

16、taTransferRate),即大家常说的倍速，它是衡量光驱性能的最基本指标。单倍速光驱就是指每秒可从光驱存取150KB数据的光驱。现在年青一代的40或48倍速光驱每秒钟能读取6000KB和7200KB的数据。(2)平均寻道时间(AverageAccessTime),平均寻道时间是指激光头（光驱中用于读取数据的一个装置）从原来位置移到新位置并开始读取数据所花费的平均时间，显然，平均寻道时间越短，光驱的性能就越好。(3)CPU占用时间(CPULoading)，CPU占用时间是指光驱在维持一定的转速和数据传输率时所占用CPU的时间，它也是衡量光驱性能好坏的一个重要指标。CPU占用时间越少，其整体

17、性能就越好。(4)数据缓冲区(Buffer)，数据缓冲区是光驱内部的存储区。它能减少读盘次数，提高数据传输率。现在大多数光驱的缓冲区为128K或256K。3.3显示存储空间显示存储空间=水平分辨率垂直分辨率色彩数目例如，若采用640480，16色显示模式，只需要150KB的存储空间。但是，如果想在12801024，16M色的显示模式下运行，4MB的显示存储空间是不可能运行的。3.4压缩标准目前，国际上的压缩技术标准有JPEG，MPEG和P4。JPEG适合于连续色调、多级灰度、彩色或单色静止图象数据压缩的国际标准。可获得10：1到80：1的压缩比。MPEG包括MPEG视频、MPEG音频和MPEG

18、系统三部分，处理活动影象中的视频压缩、音频压缩，以及多种压缩后数据流的复合和同步问题。可获得50：1到00：1的压缩比。P4目标是针对可视电话和电视会议的。适应各种通道容量的传输。4.1 广域网和局域网 1、广域网WAN（Wide Area Network）是跨地域性的网络系统，大多数WAN都是网络互连而成的，如著名的Internet网络。2、局域网LAN（Local Area Network）一般由一个部门或公司组建，地理范围仅在建筑楼内或单位内部。3、城域网：可以看成是广域网的一种。4.2 计算机网络拓扑结构网络中各个站点相互连接的方法和形式称之为网络拓扑。把向工作站、服务器等网络单元抽象

19、成为“点”，把网络中的电缆等通信媒体抽象为“线”，从而抽象出了络系统的具体结构，即为逻辑结构。网络拓扑结构有：计算机网络拓扑结构4.3网络协议计算机通信协议指双方在通信中所应共同遵守的约定。计算机通信协议精确地定了计算机在彼此通信时的所有细节。它规定每台计算机发送每条信息的格式和含义，规定哪些情况下应发送那些特殊的信息，以及接受方的计算机所应作出什么反映等等。OSI七层协议主机A主机B1应用层应用层2表示层表示层3会话层会话层4运输层运输层5网络层网络层6数据链路层数据链路层7物理层物理层应用层协议表示层协议会话层协议运输层协议网络层协议链路层协议物理层协议4.4IP地址Internet中的每

20、台主机都被分配一个唯一的32位地址，即IP地址。该地址由网络号和主机号两部分组成，其中网络号表示一个网络，而主机号表示这个网络中的一台计算机。IP地址由4个十进制数字字段组成,字段之间用点分开,4个字段中的每个数字在0255之间，如210.30.240.11。IP地址类型IP地址按网络规模的大小主要可分成三类:A类地址、B类地址、C类地址。A类的第一个字段的值在1126之间，一般用于大型网络；B类的第一个字段的值在128 191之间，一般用于中型网络或网络管理器，如路由器等；C类的第一个字段在值在191 233之间，一般用于小型网络。网络地址数网络主机数主机总数A类12616,387,0642

21、,064,770,064B类16,25664,5161,048,872,096C类2,064,512254524,386,048域名用用IPIP地地址址标标识识主主机机既既没没有有规规律律，又又很很难难记记忆忆，用用户户很很难难用用数数字字表表示示的的IPIP地地址址与与计计算算机机的的情情况况联联系系起起来来，给给访访问问InternetInternet带带来来了了很很大大的的不不便便如如果果采采用用域域名名系系统，就可以很好地解决这些问题。统，就可以很好地解决这些问题。域域名名系系统统是是由由TCP/IPTCP/IP提提供供的的一一种种服服务务，可可以以将将域域名名翻翻译译成成相相应应的的

22、IPIP地地址址。域域名名系系统统采采用用层层次次结结构构，按按地地理理域域或或组组织织域域进进行行分分层层，各各层层间间用用圆圆点点“.”.”隔隔开开。在在主主机机的的域域名名表表示示中中，从从左左向向右右，域域名名依依次次从从小小到到大大，例例如如在在中中，最最高高域域名名 为为 cncn，次次 高高 域域 名名 为为 comcom，最最 后后 一一 个个 域域 名名 为为easthumaneasthuman。数学相关题目1（第八届）在书架上放有编号为1，2，.n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时,原来位置为123,放回去时

23、只能为：312或231这两种。问题：求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)2.(第九届)某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci的学生集合。已知S(Ci)S(C6)，i=1，2，.，5，S(Ci)S(Ci+1)，i=1，2，3，4，S(C5)S(C1)，问至少安排_天才能考完这6门课程。题目3(第七届)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形?4（第十届）已

24、知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ab”开头写出你的安排方案：。从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.2.2.组合的定义组合的定义:从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.3.3.排列数公式排列数公式:4.4.组合数公式组合数公式:1.1.排列的定义排列的定义:排列与组

25、合的区别与联系排列与组合的区别与联系:与顺序有关的为排列问题与顺序有关的为排列问题,与顺序与顺序无关的为组合问题无关的为组合问题.例例1 1 学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？解解 先排学生共有 种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种.结论结论1 1 插入法插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.分析分析 此题涉及到的是不相邻问题,并且是对

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

27、解决问题.解 把所有的硬币全部取出来,将得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.例3 袋中有5分硬币23个,1角硬币10个,如果从袋中取出2元钱,有多少种取法?结论3 剩余法剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.例4 学校安排考试科目9门,语文要在数学之前考,有多少种不同

28、的安排顺序?解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种.结论4 对等法对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求.分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性.例5 某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?解 4

29、3人中任抽5人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有1人在内的抽法有 种.结论5 排异法排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.数据结构相关题目1.(第六届)已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2(第七届)已知一棵

30、二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA，则该二叉树的先序遍历的顺序为：_。3（第九届）无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_个顶点。扩展二叉树二叉树由结点的有限集合构成，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别成为这个根的左子树和右子树的二叉树（它们也是结点的集合）组成。二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。二叉树的五种形态（1）（2）（3）（4）（5）满二叉树如果一棵二叉树的任何结点，或者是树叶，或

31、者恰有两棵非空子树，则此二叉树称为满二叉树。在满二叉树里，树叶的个数等于分支结点个数加一。完全二叉树如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层左边的若干位置，则此二叉树称作完全二叉树。二叉树的遍历先序：根-左子树-右子树(abcd)中序：左子树-根-右子树(badc)后序：左子树-右子树-根(bdca)abcd图习惯上，常用G=(V,E)代表一个图，图中的结点又称为顶点，V是结点的有限集合，结点的偶对称为边，E是边的集合。任意一个具有n个结点的无向图，其边数小于等于n*(n-1)/2;我们把边数恰好等于n*(n-1)/2的n个结点的无向图称为完全图。

32、在一个n个结点的有向图中，最大边数为n*(n-1)。一个结点的度就是与该结点相关联的边的数目。1(第七届)一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点A)2h-1B)2h1C)2h十1D)h十12(第七届)无向图G(V，E)，其中Va，b，c，d，e，fE(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，对该图进行深度优先遍历，得到的顶点序列正确的是()A)a，b，e，c，d，fB)a，c，f，e，b，dC)a，e，b，c，f，dD)a，b，e，d，f，c3（第八届）按照二叉树的定义，具有3个结点的二叉树有()种。A)3B)4C)5D)64（第八届）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A)12B)1C)2D)45.（第九届）假设我们用d=(a1,a2,.,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d值合理（）。A）5，4，4，3，1B）4，2，2，1，1C）3，3，3，2，2D）5，4，3，2，1E）2，2，2，2，26（第十届）满二叉树的叶结点个数为N，它的结点总数为A.NB.2*NC.2*N1D.2*N+1E.2N1