信息学奥赛初赛全部知识汇总(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息学奥林匹克,分区联赛的基础知识,1,初赛试题结构,第一部分 基础知识,第二部分 问题求解,第三部分 阅读程序,第四部分 完善程序,2,第一部分,一、计算机的发展与应用,二、计算机概述,三、多媒体技术应用,四、计算机网络使用基础,3,一、计算机的发展与应用,一、计算机的发展与应用,4,1,、下面列出的四项中，不属于计算机病毒特征的是,(),A,潜伏性,B,激发性,C,传播性,D,免疫性,2,、国产银河型数字式电子计算机是属于下列哪种类型计算机,(),A,微型,B,小型,C,中型,D,巨型,3,、计算机病毒是指,(),A,能传染给用户的磁盘病毒,B,已感染病毒的磁盘,C,具有破坏性的特制程序,D,已感染病毒的程序,4,、最早的计算机的用途是用于,(),A,科学计算,B,自动控制,C,辅助设计,D,系统仿真,5,、操作系统在第几代计算机开始应用,(),A,第一代,B,第二代,C,第三代,D,第四代,5,第二代晶体管计算机,(1956-1963),1948,年，晶体管的发明大大促进了计算机的发展，晶体管代替了体积庞大电子管，电子设备的体积不断减小。,1956,年，晶体管在计算机中使用，晶体管和磁芯存储器导致了第二代计算机的产生。第二代计算机体积小、速度快、功耗低、性能更稳定。首先使用晶体管技术的是早期的超级计算机，主要用于原子科学的大量数据处理，这些机器价格昂贵，生产数量极少。,1960,年，出现了一些成功地用在商业领域、大学和政府部门的第二代计算机。第二代计算机用晶体管代替电子管，,还有现代计算机的一些部件,:,打印机、磁带、磁盘、内存、操作系统,等。,计算机中存储的程序使得计算机有很好的适应性，可以更有效地用于商业用途。在这一时期出现了更高级的,COBOL(Common Business-Oriented Language),和,FORTRAN(Formula Translator),等语言，以单词、语句和数学公式代替了含混晦涩的二进制机器码，使计算机编程更容易。新的职业,(,程序员、分析员和计算机系统专家,),和整个软件产业由此诞生。,6,1,什么是,CISC,机？什么是,RISC,机？,2,计算机的发展分为几个阶段？正在研制的新型计算机具有哪些特点？,3,简述“三金”工程的含义。,4,什么是计算机病毒，它具有哪些特征，如何采取具体的防范措施？,资 料,7,CISC,微处理器是台式计算机系统的中心，这个核心中的核心就是运行指令的电路。指令由完成任务的多个步骤所组成，例如把数值传送进寄存器或进行相加运算，都是需要指令的，这些指令被称为微代码（,microcode,），不同制造商的微处理器有不同的微代码系统，制造商可按自己的意愿使微代码做得简单或复杂。指令系统越丰富，微处理器编程就越简单，然而，执行速度也相应越慢，而且设计这样的处理器的代价也就越大，但是由于指令系统丰富，对上层的支持就比较好。下面我们来看看两种处理器的比较：,复杂指令系统计算机（,CISC,）,包含一个丰富的微代码系统，简化了处理器上运行程序的编制。,精简指令系统计算机（,RISC,）,有一个精简的指令系统。从而提高了微理器的效率，但需要更复杂的外部程序，也就是把在处理器层没有完成的工作放到了上层进行，而处理器层少的这些成本可以用对物理器件速度的提高上去。,RISC,方案基于,John Cocke,在,IBM,公司的工作，他发现约,20,的计算机指令完成约,80,的工作。因此，,RISC,系统通常比,CISC,系统要快。他的,80,20,规则促进了,RISC,体系结构的开发。大多数台式微处理器方案如,Intel,和,Motorola,芯片都采用,CISC,方案；工作站处理器加,MIDS,芯片,DEC Alpha,和,IBM RS,系列芯片均采用,RISC,体系结构。将来的处理器会在,RISC,和,CISC,之间寻找到一条合适的途径来保证处理器的成本较小，而且功能比较合适。,8,二、计算机概述,9,1.,世界上首先实现存储程序的电子数字计算机是（）。,A,ENIAC B,、,UNIVAC,C,、,EDVAC D,、,EDSAC,2,、计算机能直接执行的指令包括两部分，它们是,(),A,源操作数与目标操作数,B,操作码与操作数,C,ASCII,码与汉字代码,D,数字与字符,3,、下列诸因素中，对微机工作影响最小的是,(),A,尘土,B,噪声,C,温度,D,湿度,4,、在计算机中，,ASCII,码是几位二进制代码,(),A,7 B,8 C,12 D,16,5,、下面四个不同进制的数，最小的一个数是,()A,(11011001),2,B,(37),8,C,(75),10,D,(A7),16,10,资 料,1,简述冯,诺依曼型计算机的组成与工作原理。,2,计算机硬件系统由哪五个基本部分组成？它们各自的功能是什么？,3,机器指令由哪几部分组成？按其功能分为哪几种指令类型？,4,.,在计算机中，带符号数有几种表示方法？它们之间的转换关系是什么？各自有什么用途？,5,ASCII,码由几位二进制数组成？它能表示什么信息？,6,二进制的计算规则。,11,三、多媒体技术应用,12,1,彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（）。,A.,红,B.,白,C.,蓝,D.,绿,E.,橙,2,下面哪个部件对于个人桌面电脑的正常运行不是必需的（）。,A.CPU B.,图形卡（显卡）,C.,光驱,D.,主板,E.,内存,3.,下列哪个（些）不是个人计算机的硬件组成部分（）。,A.,主板,B.,虚拟内存,C.,电源,D.,硬盘,E.,总线,4.,一个文本屏幕有,25,列及,80,行，屏幕的左上角以（,1,，,1,）表示，而右下角则以（,80,，,25,）表示，屏幕上每一个字符占用两字节（,byte,），整个屏幕则以线性方式存储在电脑的存储器内，屏幕左上角开始，位移为,0,，然后逐列逐列存储。求位于屏幕（,X,，,Y,）的第一个字节的位移是（）,A.,（,Y*80+X,）*,2-1,B.,（,Y-1,）*,80+X-1,）*,2C.,（,Y*80+X-1,）*,2,D.,（,Y-1,）*,80+X,）*,2-1,13,1.,多媒体计算机系统的基本配置包含了哪些设备？,2,CD-ROM,的功能大小取决于哪几个参数？,3,显示存储空间由哪几个主要的因素决定？,4,目前国际上有哪几种压缩数据的标准？,资 料,14,四、计算机网络使用基础,15,1,、,Internet,的规范译名应为,(),A,英特尔网,B,因特网,C,万维网,D,以太网,2,、下列哪些计算机网络不是按覆盖地域划分的,(d ),A,局域网,B,都市网,C,广域网,D,星型网,3,、以下列举,Internet,的各种功能中，错误的是,(),A,编译程序,B,传送电子邮件,C,查询信息,D,数据库检索,4,、计算机网络最突出的优点是,(),A,传送信息速度高,B,共享资源,C,内存容量大,D,交互性好,5,、,TCP,IP,协议共有,(),层协议,A.3B.4C.5D.6,16,1,什么是,WAN,网？什么是,LAN,网，他们各自的功能是什么？,2,什么是计算机网络的拓扑结构？常见的拓扑结构有几种？,3.,什么是计算机网络协议？说出,OSI,的七层协议的名称。,4.,在,Internet,中，,IP,地址和域名的作用是什么？它们之间有什么异同？,资 料,17,第二部分,数学知识,组合、排列、集合等,数据结构,图、树等,18,第三部分 阅读程序,直接推理,有流程图推断算法,动态模拟,由底向上阅读分析,19,例一,Var,m,n,i:integer;,t:extended;,Begin,read(n,m);,t:=1;,for i:=1 to m do t:=t*(n-i+1)/i;,writeln(t:0:0);,End.,输入：,10 5,输出：,1045120210252,20,例二,Label 10,20,30;,Var s,p:string;I,k,n,j,m:integer;,Begin,readln(s);n:=length(s);,readln(p);m:=length(p);,i:=0;,10:i:=i+1;j:=I;k:=1;,21,例二（续）,20:If s j p k,then begin,if in-m+1 then goto 10;,i:=0;,goto 30;,end,else if kmax then begin _(3)_;,p1:=I;q1:=j;end;,end;,For i:=p1 to _(4)_ do,Begin for j:=q1 to _(5)_do write(aI,j:3);writeln;end;readln,end.,28,例二,Const maxm=10000;,Var I,k,m,n,rest,start,temp:longint;,a:array0.maxm of longint;,Begin,write(input m,n:);,readln(m,n);,for i:=0 to m-1 do ai:=random(100);,writeln(before move);,for i:=0 to m-1 do write(ai:5);writeln;,rest:=m;start:=0;,while _(1)_do,begin k:=start;,repeat k:=(k+n)mod m until k=n;,if b=n then find:=_(2)_ else find:=_(3)_,End;,31,例（续）,Procedure p(n:integer);,Var a:integer;,begin,a:=find(n);,if first then begin write(a:4);first:=false;end,else write(+,a:4);,if a=0;,X,补,=2,(n+1),+X,，当,-2,n,=X=1,例如：,X=+100101 X,补,=0 100101,X=100101 X,补,=1 011011,特点,:1.,补码的和等于和的补码,符号位和数值位一样参加运算,不必单独处理,即,X,补,+Y,补,=X+Y,补,2.,补码相减,:X,补,-Y,补,=X,补,+-Y,补,Y,补,-Y,补,:,符号位连同数值位一起取反加,1,3,表示范围：,-128-+127,49,反码表示法,当,X=0,时，,X,反,=,X,当,X=0,时，符号位为,1,，其余各位取反。,特点,:1.,反码的和等于和的反码,2.,有二个零,+0=000,-0=111,3.,当最高位有进位而丢掉进位,(,即,2),时,要在最低位加,1(,循环进位,),表示范围：,-127-+127,50,原码,反码和补码之间的转换,X,反,符号位不变,数值位,不变,(,符号位为,0),变反,(,符号位为,1),+,0,1,X,真值,X,原,数值位不变,数值位,不变,(,符号位为,0),变反加,1(,符号位为,1),符号位不变,X,补,当,X,为正数，,X,反,=X,原,=X,补,=X,，,当,X,为负数时，,X,补,=X,反,+1,，,X,补,=X,原,51,2.5 ASCII,码,ASCII,码是美国信息交换标准代码的缩略语。是目前国际上最为流行的字符信息编码方案。它包括数字,09,、大小写字母和专用符号等,95,种可打印字符，还有,33,种控制字符。,一个字符,ASCII,码通常占一个字节，用七位二进制编码组成，,ASCII,码最多可表示,128,个不同的符号。字节的最高位被很多系统用做校验码，以便提高字符信息传输的可靠性。,52,2.12,汉字信息编码,3,、汉字交换码,（,1,）区位码：,GB2312-80,信息交换用汉字编码字符集,，组成一个,94*94,的矩阵。每一行称为一个,区,，每一列称为一个,位,。一个汉字的区号和位号合在一起构成,区位码,（,2,）汉字交换码（国标码,GB2312-80,）：国标码收入,6763,个汉字，其中一级汉字（最常用）,3755,个,(,按拼音排序,),，二级汉字,3008,个,(,按部首排序,),，另外还包括,682,个西文字符、图符。区位码（十进制）的两个字节分别转换为十六进制后加,20H,转换成国际码。,4,、汉字机内码：是计算机系统中对汉字的一种运行代码，系统内部的存储、传输都是对机内码进行的。它也和汉字存在着一一对应的关系。机内码也占两个字节，且最高位为,1,。同一个汉字，在同一种汉字操作系统中，内码是相同的。,汉字机内码是汉字交换码两个字节的最高位分别加,1,，即汉字交换码的两个字节分别加,80H,；或区位码（十进制）的两个字节分别转换为十六进制后加,A0H,。,53,由于,GB2312,80,是,80,年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的,GB18030,信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间,GB,码与,BIG5,码间的字码转换不便的问题。,字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模，有,1616,，,2424,，,6464,等，每一个点在存储器中用一个二进制位（,bit,）存储。例如，在,1616,的点阵中，需,832 bit,的存储空间，每,8 bit,为,1,字节，所以，需,32,字节的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。,54,2.6,二进制,采用二进制，优点：,（,1,）易于物理实现,（,2,）二进制运算简单,（,3,）机器可靠性高,（,4,）通用性强,乘法,除法,整数转换,小数转换,0+0=0 0+1=1,1+0=1 1+1=10,0*0=0 0*1=0,1*0=0 1*1=1,55,数的定点表示和浮点表示,(1),定点小数格式,任何一个,M,位的小数可以表示成：,N=Ns.N-1N-2N-m (,其中,Ns,是符号位，其值表示的范围,|N|=1-2-m),(2),定点整数格式,任何一个,N,位带符号的整数都可表示为：,N=Ns Nn-1Nn-2N0 (,其中,Ns,是符号位，其值表示的范围,|N|=2n-1),(3),数的浮点表示,浮点数是指小数点在数据中的位置可以左右移动的数。一个数,N,要用浮点表示可以写成：,N=MRE,其中,M,表示浮点数的尾数,E,表示浮点数的指数或称为阶码,R,指的是在这个指数下的基数。浮点数通常表示成如下格式：,1,位,m,位,n,位,M,：浮点数的尾数，用定点小数表示，小数点在尾数最高位之前，是默认的。尾数用于表示浮点数的有效位，其位数,N,的大小反映了此浮点数的精度。,E,：浮点数的阶码，用定点整数表示。,Ms,：浮点数的符号位，也就是尾数的符号位，一般放在整个浮点数的最高位,Ms,E,M,56,信息在计算中的存储地址,所有的存储单元都按顺序排列，计算机中以一个字节为单位处理，所以计算机对每个存储单元进行了编号，这种编号称为单元地址。通过地址编号寻找在存储器中的数据单元称为,寻址,1,、地址编号：用二进制数编码，存储器的总容量决定了地址的范围，也决定了地址编号的二进制数位数。,如存储器的总容量为,64MB,，那么它的地址编码为,0,64220-1,；对应的二进制数是,00 0000 0000 0000 0000 0000 0000,11 1111 1111 1111 1111 1111 1111,；对应的十六进制数是,0000000,3FFFFFF,；需要用,26,位二进制来表示，也就是需要,26,根地址线。,2,、地址和容量的计算,（,1,）由地址线，求寻址空间。,若地址线有,32,根，则它的寻址空间为,2,32,B=2,22,KB=2,12,MB=4GB,57,（,2,）由起始地址和末地址，求存储空间。,若编号为,4000H 4FFFH,的地址中，包含的单元数的计算：,方法一：用十六进制计算。,4FFFH,4000H,=FFFH,1=1000H=1 163=4096=4KB,方法二：转换成十进制计算。,4FFFH,4000H,=20479,16384,=4096=4KB,（,3,）由存储容量和起始地址，求末地址。,若存储器的容量,32KB,，地址起始编号为,0000H,，末地址的计算：,方法一：用十六进制计算。,0000H+32KB,1H=0000H+32 1024,1H=0000H+8000H,1H=7FFFH,方法二：转换成十进制计算。,0+32KB,1=0+32768,1=32767=7FFFH,方法三：转换成二进制计算。,0000 H+32KB,1 H=0000 H+32 210,1 H=0000 H+215,1 H,=0000 0000 0000 0000 B+1000 0000 0000 0000 B,0000 0000 0000 0001 B,=0111 1111 1111 1111 B=7FFFH,58,3.2 CD-ROM,光驱的技术指标,(1),数据传输率,(Data Transfer Rate),即大家常说的倍速，它是衡量光驱性能的最基本指标。单倍速光驱就是指每秒可从光驱存取,150KB,数据的光驱。现在年青一代的,40,或,48,倍速光驱每秒钟能读取,6000KB,和,7200KB,的数据。,(2),平均寻道时间,(Average,Access,Time),平均寻道时间是指激光头（光驱中用于读取数据的一个装置）从原来位置移到新位置并开始读取数据所花费的平均时间，显然，平均寻道时间越短，光驱的性能就越好。,(3),CPU,占用时间,(CPU,Loading),，,CPU,占用时间是指光驱在维持一定的转速和数据传输率时所占用,CPU,的时间，它也是衡量光驱性能好坏的一个重要指标。,CPU,占用时间越少，其整体性能就越好。,(4),数据缓冲区,(Buffer),，数据缓冲区是光驱内部的存储区。它能减少读盘次数，提高数据传输率。现在大多数光驱的缓冲区为,128K,或,256K,。,59,3.3,显示存储空间,显示存储空间,=,水平分辨率,垂直分辨率,色彩数目,例如，若采用,640 480,，,16,色显示模式，只需要,150KB,的存储空间。但是，如果想在,1280 1024,，,16M,色的显示模式下运行，,4MB,的显示存储空间是不可能运行的。,60,3.4,压缩标准,目前，国际上的压缩技术标准有,JPEG,，,MPEG,和,P 4,。,JPEG,适合于连续色调、多级灰度、彩色或单色静止图象数据压缩的国际标准。可获得,10,：,1,到,80,：,1,的压缩比。,MPEG,包括,MPEGeg:mp4,视频、,MPEGeg:MP3,音频和,MPEG,系统三部分，处理活动影象中的视频压缩、音频压缩，以及多种压缩后数据流的复合和同步问题。可获得,50,：,1,到,00,：,1,的压缩比。,P 4,目标是针对可视电话和电视会议的。适应各种通道容量的传输。,61,4.1,广域网和局域网,1,、,广域网,WAN,（,wide area network,）,是跨地域性的网络系统，大多数,WAN,都是网络互连而成的，如著名的,Internet,网络。,2,、,局域网,LAN,（,Local Area Network,）,一般由一个部门或公司组建，地理范围仅在建筑楼内或单位内部,。,3,、城域网：可以看成是广域网的一种。,62,4.2,计算机网络拓扑结构,网络中各个站点相互连接的方法和形式称之为网络拓扑。把向工作站、服务器等网络单元抽象成为“点”，把网络中的电缆等通信媒体抽象为“线”，从而抽象出了络系统的具体结构，即为逻辑结构。网络拓扑结构有：,63,计算机网络拓扑结构,64,4.3,网络协议,计算机通信协议指双方在通信中所应共同遵守的约定。计算机通信协议精确地定了计算机在彼此通信时的所有细节。它规定每台计算机发送每条信息的格式和含义，规定哪些情况下应发送那些特殊的信息，以及接受方的计算机所应作出什么反映等等。,65,OSI,七层协议,主机,A,主机,B,1,应用层 应用层,2,表示层 表示层,3,会话层 会话层,4,运输层 运输层,5,网络层 网络层,6,数据链路层 数据链路层,7,物理层 物理层,应用层协议,表示层协议,会话层协议,运输层协议,网络层协议,链路层协议,物理层协议,66,4.4 IP,地址,Internet,中的每台主机都被分配一个唯一的,32,位地址，即,IP,地址。该地址由网络号和主机号两部分组成，其中网络号表示一个网络，而主机号表示这个网络中的一台计算机。,IP,地址,由,4,个十进制数字字段组成,字段之间用点分开,4,个字段中的每个数字在,0255,之间，如,210.30.240.11,。,。,67,IP,地址类型,IP,地址按网络规模的大小主要可分成三类,:A,类地址、,B,类地址、,C,类地址。,A,类的第一个字段的值在,1,126,之间，一般用于大型网络；,B,类的第一个字段的值在,128,191,之间，一般用于中型网络或网络管理器，如路由器等；,C,类的第一个字段在值在,191,233,之间，一般用于小型网络。,网络地址数 网络主机数 主机总数,A,类,126 16,38 7,064 2,064,770,064,B,类,16,256 6 4,516 1,048,872,096,C,类,2,064,512 254 524,386,048,68,域名,用,IP,地址标识主机既没有规律，又很难记忆，用户很难用数字表示的,IP,地址与计算机的情况联系起来，给访问,Internet,带来了很大的不便如果采用域名系统，就可以很好地解决这些问题。,域名系统是由,TCP/IP,提供的一种服务，可以将域名翻译成相应的,IP,地址。域名系统采用层次结构，按地理域或组织域进行分层，各层间用圆点,“,.,”,隔开。在主机的域名表示中，从左向右，域名依次从小到大，例如在,中，最高域名为,cn,，次高域名为,com,，最后一个域名为,easthuman,。,69,数学相关题目,1,（第八届）在书架上放有编号为,1,，,2,，,.n,的,n,本书。现将,n,本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：,n=3,时,原来位置为,1 2 3,放回去时只能为：,3 1 2,或,2 3 1,这两种。问题：求当,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,门课程。,70,题目,3,(,第七届,),平面上有三条平行直线，每条直线上分别有,7,，,5,，,6,个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形,?,4,（第十届）已知,a,b,c,d,e,f,g,七个人中，,a,会讲英语；,b,会讲英语和汉语；,c,会讲英语、意大利语和俄语；,d,会讲汉语和日语；,e,会讲意大利语和德语；,f,会讲俄语、日语和法语；,g,会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“,a b”,开头写出你的安排方案：,。,71,从,n,个不同元素中,任取,m,个元素,按照一定的顺序排成一列,叫做从,n,个不同元素中取出,m,个元素的一个排列,.,2.,组合的定义,:,从,n,个不同元素中,任取,m,个元素,并成一组,叫做从,n,个不同元素中取出,m,个元素的一个组合,.,3.,排列数公式,:,4.,组合数公式,:,1.,排列的定义,:,排列与组合的区别与联系,:,与顺序有关的为排列问题,与顺序无关的为组合问题,.,72,例,1,学校师生合影，共,8,个学生，,4,个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？,解,先排学生共有 种排法,然后把老师插入学生之间的空档，共有,7,个空档可插,选其中的,4,个空档,共有 种选法,.,根据乘法原理,共有的不同坐法为 种,.,结论,1,插入法,:,对于某两个元素或者几个元素要求不相邻的问题,可以用插入法,.,即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可,.,分析,此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待,.,所涉及问题是排列问题,.,73,解,因为女生要排在一起,所以可以将,3,个女生看成是一个人,与,5,个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法,.,例,2,5,个男生,3,个女生排成一排,3,个女生要排在一起,有多少种不同的排法,?,结论,2,捆绑法,:,要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题,.,即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列,.,分析,此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题,.,74,解,把所有的硬币全部取出来,将得到,0.0523+0.1010=2.15,元,所以比,2,元多,0.15,元,所以剩下,0.15,元即剩下,3,个,5,分或,1,个,5,分与,1,个,1,角,所以共有 种取法,.,例,3,袋中有,5,分硬币,23,个,1,角硬币,10,个,如果从袋中取出,2,元钱,有多少种取法,?,结论,3,剩余法,:,在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法,.,分析,此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来,.,但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题,.,75,例,4,学校安排考试科目,9,门,语文要在数学之前考,有多少种不同的安排顺序,?,解,不加任何限制条件,整个排法有 种,“,语文安排在数学之前考,”,与,“,数学安排在语文之前考,”,的排法是相等的,所以语文安排在数学之前考的排法共有 种,.,结论,4,对等法,:,在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一,.,在求解中只要求出全体,就可以得到所求,.,分析,对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了,.,并且也避免了问题的复杂性,.,76,例,5,某个班级共有,43,位同学,从中任抽,5,人,正、副班长、团支部书记至少有一人在内的抽法有多少种,?,解,43,人中任抽,5,人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有,1,人在内的抽法有 种,.,结论,5,排异法,:,有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除,.,分析,此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况,.,而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便,.,这样就可以简化计算过程,.,77,数据结构相关题目,1.(,第六届,),已知，按中序遍历二叉树的结果为：,abc,问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。,2,(,第七届,),已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：,CBGEAFHDIJ,与,CGEBHFJIDA,，则该二叉树的先序遍历的顺序为：,_,。,3,（第九届）无向图,G,有,16,条边，有,3,个,4,度顶点、,4,个,3,度顶点，其余顶点的度均小于,3,，则,G,至少,_,个顶点。,扩展,78,二叉树,二叉树由结点的有限集合构成，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别成为这个根的左子树和右子树的二叉树（它们也是结点的集合）组成。,二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。,79,二叉树的五种形态,（,1,）（,2,）（,3,）（,4,）（,5,）,80,满二叉树,如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称为满二叉树。,在满二叉树里，树叶的个数等于分支结点个数加一。,81,完全二叉树,如果一棵二叉树最多只有最下面的两层结点度数可以小于,2,，并且最下面一层的结点都集中在该层左边的若干位置，则此二叉树称作完全二叉树。,82,二叉树的遍历,先序：根,-,左子树,-,右子树,(abcd),中序：左子树,-,根,-,右子树,(badc),后序：左子树,-,右子树,-,根,(bdca),a,b,c,d,83,图,习惯上，常用,G=(V,E),代表一个图，图中的结点又称为顶点，,V,是结点的有限集合，结点的偶对称为边，,E,是边的集合。,任意一个具有,n,个结点的无向图，其边数小于等于,n*(n-1)/2;,我们把边数恰好等于,n*(n-1)/2,的,n,个结点的无向图称为完全图。,在一个,n,个结点的有向图中，最大边数为,n*(n-1),。,一个结点的,度,就是与该结点相关联的边的数目。,84,1,(,第七届,),一棵二叉树的高度为,h,，所有结点的度为,0,，或为,2,，则此树最少有,(),个结点,A)2h-1B)2h1C)2h,十,1D)h,十,1,2,(,第七届,),无向图,G,(V,，,E),，其中,V,a,，,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,，,d C)a,，,e,，,b,，,c,，,f,，,dD)a,，,b,，,e,，,d,，,f,，,c,3,（第八届）按照二叉树的定义，具有,3,个结点的二叉树有,(),种。,A)3 B)4 C)5 D)6,4,（第八届）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的,(),倍。,A)1,2 B)1 C)2 D)4,5.,（第九届）假设我们用,d=(a1,a2,.,a5),表示无向图,G,的,5,个顶点的度数，下面给出的哪（些）组,d,值合理（）。,A,）,5,，,4,，,4,，,3,，,1 B,）,4,，,2,，,2,，,1,，,1 C,）,3,，,3,，,3,，,2,，,2 D,）,5,，,4,，,3,，,2,，,1 E,）,2,，,2,，,2,，,2,，,2,6,（第十届）满二叉树的叶结点个数为,N,，它的结点总数为,A.N B.2*N C.2*N 1 D.2*N+1 E.2N 1,85,