资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,NOIP2014,初赛指导,初赛的目的,进入复赛（本赛区前,15%,）,考察计算机基础知识和编程的基本能力，并对知识面的广度进行测试,复赛排名重要依据,初赛试题形式,初赛：初赛全部为笔试，满分,100,分。试题由四部分组成：,1,、选择题：共,20,题，每题,1.5,分，共计,30,分。提高组每题有,5,个备选答案，前,10,个题为单选题,(,即每题有且只有一个正确答案，选对得分,),，后,10,题为不定项选择题,(,即每题有,1,至,5,个正确答案，只有全部选对才得分,),。普及组,4,个备选答案，全为单选题。,2,、问题求解题：共,2,题，每题,5,分，共计,10,分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。,3,、程序阅读理解题：共,4,题，每题,8,分，共计,32,分。题目给出一段程序,(,不一定有关于程序功能的说明,),，考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。,4,、程序完善题：共,2,题，每题,14,分，共计,28,分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。,知识范围,内容与要求,1,、计算机的基本常识,计算机和信息社会,(,信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化,),信息输入输出基本原理,(,信息交换环境、文字图形多媒体信息的输入输出方式,),信息的表示与处理,(,信息编码、微处理部件,MPU,、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构,),信息的存储、组织与管理,(,存储介质、存储器结构、文件管理、数据库管理,),信息系统组成及互连网的基本知识,(,计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、,TCP,IP,协议、,HTTP,协议、,WEB,应用的主要方式和特点,),人机交互界面的基本概念,(,窗口系统、人和计算机交流信息的途径,(,文本及交互操作,),信息技术的新发展、新特点、新应用等。,2,、计算机的基本操作,WINDOWS,和,LINUX,的基本操作知识,联网的基本使用常识,(,网上浏览、搜索和查询等,),常用的工具软件使用,(,文字编辑、电子邮件收发等,),3,、程序设计的基本知识,数据结构,程序语言中基本数据类型,(,字符、整数、长整数、浮点,),浮点运算中的精度和数值比较,一维数组,(,串,),与线性表,记录类型,(PASCAL),结构类型,(C),程序设计,结构化程序设计的基本概念,阅读理解程序的基本能力,具有将简单问题抽象成适合计算机解决的模型的基本能力,具有针对模型设计简单算法的基本能力,程序流程描述,(,自然语言伪码,NS,图其他,),程序设计语言,(PASCAL,C,C+,，,),基本算法处理,初等算法,(,计数、统计、数学运算等,),排序算法,(,冒泡法、插入排序、合并排序、快速排序,),查找,(,顺序查找、二分法,),回溯算法,课程大纲,NOIP初赛情况的简单分析,基础知识,二叉树,图,排列组合,程序阅读题,程序填空题,总结,初赛试卷题型分析,(,提高组,)单项选择,15分,(,提高组,) 不定项选择,15分（多选少选均不得分）,问题求解,10分,阅读程序,32分,完善程序,28分,初赛试卷题型分析,初赛考的知识点，大纲说：计算机基本常,识，基本操作和程序设计基本知识。选择,题考查的是知识，而问题解决题、填空更,加重视能力的考查。,一般说来，选择题是不需要单独准备,的,，也无从准备。只要多用心积累就可以,了。到是问题解决题目比较固定，大家应,当多,做,以前的题目。写运行结果需要多做,题目，培养良好的程序阅读和分析能力，,而完善程序最好总结一下以前题目常常要,你填出来的语句类型。,初赛试卷题型分析,1.选择题,一般它们是比较容易得分的，一共30分，不可,错过！,近几年来，初赛的考查范围有了很大的变化，越来,越紧跟潮流，需要大家有比较广泛的知识，包括计算机,硬件，软件，网络，数据结构（例如栈，队列，排序算,法），程序设计语言以及一些基本的数学知识和技巧,（例如排列组合等）。,2.填空、问题解决,这部分题目对数学要求要高一点，往往考查的是代数,变形、集合论、数列（一般是考递推），也考查,一些算,法和数据结构知识。建议大家多花一点时间做，尽量做,对。,初赛试卷题型分析,3.,阅读程序写出运行结果,占的分数多，但得分率却不高，较易失分，一,旦结果不正确，将丢失全分。,这种题型主要考察选手：,程序设计语言的掌握能力,数学运算能力,耐心、细心的心理品质一般做这类题目的,关键在于能够分析程序的结构及程序段的功能，,找出程序目的，即这个程序想干什么。,初赛试卷题型分析,完成这类题目的一般方法和步骤是：,从头到尾通读程序，大致掌握程序的算法；,通过给程序分段，清理程序的结构和层次，达到读懂程序,的目的；,阅读程序中特别注意跟踪主要变量值的变化，也可以用列,表的方法，了解变量变化和程序运行的结果，要注意发现规律。,迄今为止考过的题目还没有“乱写”的，总有一点“写作目的”,的。抓住了它，得出答案就变得很容易了，而且对结果也会有信,心。写程序运行结果大纲规定是必考的。试卷中给出的程序并不,复杂，语句的含义容易明白，因此悟性好的选手总是很快就能体,会到程序的设计思路并得出正确的答案，而机械模仿计算机硬算,出结果的同学往往做,得,慢的多，而且容易失误。,初赛试卷题型分析,4.,完善程序这部分题目得分率似乎不高。,尽量把一些简单的填好就行了。,建议大家把以前的初赛题目都做,一下,。,常常让大家填的是：,初始化,一些明显的动作：,a.,结果没有储存在需要的地方。,b.,累加器没有做加法,c.,输出,关键动作。,在算法描述中出现的比较关键的步骤。例如交换,排序程序的“交换”操作等很明显需要完成的操作。,分析方法和写运行结果类似，注意分析变量和,程序结构，理解变量和模块的作用是解题的关键。,进制转换,1二进制与十进制间的相互转换：,（1）二进制转十进制,方法：“按权展开求和”,例：,（1011.01）,2,（12,3,02,2,12,1,12,0,02,1,12,2,）,10,（802100.25）,10,（11.25）,10,规律：个位上的数字的次数是0，十位上的数字的次数是,1，.，依次递增，而十,分位的数字的次数是-1，百分位上数字的次数是-,2，.，依次递减。,注意：不是任何一个十进制小数都能转换成有限位的二进,制数。,进制转换,进制转换,1二进制与十进制间的相互转换：,（1）二进制转十进制,方法：“按权展开求和”,例：,（1011.01）,2,（12,3,02,2,12,1,12,0,02,1,12,2,）,10,（802100.25）,10,（11.25）,10,规律：个位上的数字的次数是0，十位上的数字的次数是,1，.，依奖递增，而十分位的数字的次数是-1，百分,位上数字的次数是-2，.，依次递减。,注意：不是任何一个十进制小数都能转换成有限位的二进,制数。,进制转换,以下二进制数与十进制数23.456最接近的,是（）,A,10111.0101,B,11011.1111,C,11011.0111,D,10111.0111,E.10111.1111,D,把下面的数转换为10进制数再进行比较,位运算,位运算主要有：,按位与(,&,)，按位或(,|,)，按位异或(,)，,取反,运算法则：,1、先将两边的数转化为二进制，右边第,一位对齐，对于每一位进行按位运算。,2、只有1&1为真，其余情况为假,3、只有0|0为假，其余为真,4、只有10和01为真，其余为假,5、优先级&,|,6、(00001001),2,=(11110110),2,切记：,25,不是,2,5,而是,2,异或,5,位运算,补充：负数在计算机内的表示是取对应正,数的补码。,补码,=,反码,+,1,如1表示为(0001),2,，那么-1就表示为：,(1111),2,。,10表示为(1010),2,，那么-10就表示为,(0110),2,。,位运算,比如，计算212,先转换为二进制,21,=,(10101),2,2,=,(10),2,10101,10,10111,(10111),2,=23,位运算,练习题：,23|25的值是多少？,23,23|25,=,23|7,=,23,这个内容比较重要，至少会占1,分，请大家务必学透！,逻辑,真真假假很容易判断的，总之复赛前要看一,下！需要结合C语言的逻辑判断！,设A,=,true，B,=,false，C,=,false，D,=,true，,以下逻辑运算表达式值为真的有（,）。,A.,(AB)(CD),B.,(AB)C)D,C.,A(BC)D),D.,(A(BC),D,E.,(AB)(CD),CDE,逻辑,A.,!,(a!=0),|,(b!=0),|,(c!=0),B.,!,(a!=0),&,(b!=0),&,(c!=0),C.,!,(a=0),&,(b=0),|,(c=0),D.(a=0),&,(b=0),&,(c=0),E.,!,(a=0),|,(b=0),|,(c=0),6在,C语言中，判断整数a,等于,0,或b等于,0或,c等于0,的正确的条件表达式是（,）,B,A.,PQ,C.,(PQ),B.,PQ,D.,(QP,),需要注意优先级,逻辑,12.,命题“PQ”可读做P蕴含Q，,其中,P、Q是两个独立的命题.,只有当命题P成,立而命题Q不成立时，,命题PQ的值为,false，,其它情况均为true.,与命题PQ,等价的逻辑关系式是（ ）。,AD,PQ,p=true,p=false,q=true,true,true,q=false,false,true,PQ,p=true,p=false,q=true,true,false,q=false,false,false,(,Q,P),p=true,p=false,q=true,true,true,q=false,false,true,PQ,p=true,p=false,q=true,true,true,q=false,false,true,逻辑,集合论,集合我们刚刚学过，但是我们学的东西还,是少了点。另外，注意信息学竞赛中的一,些符号和数学书上略有不同。,需要学会的运算：,交集，并集，补集，差集,集合论,集合我们刚刚学过，但是我们学的东西还,是少了点。另外，注意信息学竞赛中的一,些符号和数学书上略有不同。,需要学会的运算：,交集，并集，补集，差集,建议学会,“鸽巢原理”,差集符号：,(就是减号),A,B,就相当于去掉A中(AB)的元素。,集合论,A.,c,e,B.,d,e,C.,e,D.,c,d,e,E.,d,f,设全集I,=,a,b,c,d,e,f,g,h，集合B,A,=,a,b,c,d,e,f，,CA=,c,d,e，,B,A=,a,d，那么集合CBA为,（ ）。,A,集合论,设全集I,=,a,b,c,d,e,f,g，集合A,=,a,b,c，B,=,b,d,e，C,=,e,f,g，那么集,A.,a,b,c,d,B.,a,b,d,e,C.,b,d,e,D.,b,c,d,e,E.,d,f,g,合(A,B)(CB)为（ ）。,A,储存单位的计算,bit,位,Byte,比特，字节,KB,千字节,MB，兆字节,其它单位：GB,TB,速率单位（声音，视频，网络）：,bps,bit,per,second,bit/s,Kbps,Kbit,per,second,Kbit/s,Mbps,Mbit,per,second,Mbit/s,储存单位的计算,1,Byte,=,8,bit,1,KB,=,1024,Byte,1,MB,=,1024,KB,=,1024,2,Byte,=,8*1024,3,bit,1,GB,=,1024,MB,=,1024,2,KB,=,1024,3,Byte,=.,.自己去推了,1Mbps,=,1024,Kbps,=,1024,2,bps,Attention,，大,B,小,b,有区别的，一个是,bit,，一个是,Byte,，,所以,KB,和,Kb,是不一样的，比如说,“ADSL,宽带,512Kb”,当然，现在很多人都混着用了,但是考试还是要严格点。,储存单位的计算,声音文件的大小等于：,速率*长度（注意单位）,下载时间与网络速度的关系：,下载时间,=,文件大小,/,下载速率,注意下载速率的基本单位是bit/s，而文件大小的,单位是Byte，所以要乘以8。,公式不用死记，用物理的量纲理论就可以了。由,单位确定公式。,(bit/s),*,(s),=,bit,下载速率*时间,=,文件大小,储存单位的计算,例题：一个音乐爱好者收藏有100首MP3,格式的音乐，这些音乐的编码率都是,192Kbps，平均每首音乐的时长为3min，,他要通过网络将这些音乐传送给另一个,人，假设网络速度恒定为512KB/s，则他,传送这些音乐大概需要（,）。,A.,72s,B.,843s,C.,112.5min,D.,3h48min16s,E.,超过24小时,100,*,192Kb/s,*,3min,/,(512KB/s),=,843.75s,切记要换算单位！,储存单位的计算,A.,1,B.,10,C.,100,D.,1000,E.,10000,Hint：真彩色通常指每像素32位的图形,10.,一位艺术史学家有20000,幅1024,*,768,的真彩色图像，如果将这些图像以位,图形式保存在CD,光盘上（一张CD,光盘,的容量按600M计算），大约需要（,）张,CD光盘。,1024*768*20000*32bit/600MB,=,100,C,栈和队列,类比火车站。一个是这样的,另一个是这样的,栈和队列,某个车站呈狭长形，宽度只能容下一台车，并且,只有一个出入口。已知某时刻该车站状态为空，,从,这一时刻开始的出入记录为：“进，出，,进，进，进，出，出，进，进，进，出,出”。,假设车辆入站的,顺序为,1，2，3，则车,辆出站的顺序为（,）。,A.,1,2,3,4,5,B.,1,2,4,5,7,C.,1,4,3,7,6,D.,1,4,3,7,2,E.,1,4,3,7,5,C,log,n,!,2,排序,n个数排序，最少需要比较多少次？,for(i=1;,i=n;,i+),for(j=1;,j,aj+1),/这就是比较,.,公式：,最少比较次数,=,A.,6,B.,7,C.,8,D.,9,E.,10,10将,5,个数的序列排序，不论原先的顺,序如何，最少都可以通过（ ）次比较，,完成从小到大的排序。,B,排序,思考:最坏情况下最少需要交换多少次?,n-1,1.,将数组32,74,25,53,28,43,86,47,中的元素按从小到大的顺序排列，每,次可以交换任意两个元素，最少需要,交换_次。,5,排序,稳定排序包括：,插入排序、冒泡排序,不稳定排序包括：,选择排序、希尔排序、快速排序、堆排序,时间复杂度：,冒泡排序O(n,2,)，选择排序O(n,2,)，快速排,序O(nlog,2,n,)，堆排序O(nlog,2,n,),二叉树,定义：n个结点的有限集，每个结点至多,只有两棵子树，子树也是二叉树。每个结,点可以有左孩子和右孩子，顺序不可颠倒。,概念：,度：某个结点孩子的个数,叶子：度为0的结点,深度：二叉树的层数,满二叉树：深度为n且结点数为2,n,-1的二叉,树,完全二叉树：深度为k，1k-1层为满二叉,树，第k层叶子节点集中在左边的二叉树,二叉树,二叉树的遍历：先根，中根，后根遍历以,及深度优先遍历和广度优先遍历，具体方,法参看资料。,根据前根中根或中根后根遍历确定一颗二,叉树的形态以及另一种遍历。,二叉树知识点补充,n个结点所组成的不同形态的二叉树数目,为：,C(2n,n)/(n+1),二叉树,A.,4,2,5,7,6,3,1,B.,4,2,7,5,6,3,1,C.,4,2,7,5,3,6,1,D.,4,7,2,3,5,6,1,E.,4,5,2,6,3,7,1,二叉树T，已知其前序遍历序列为1,2,4,3,5,7,6，中序遍历序列为4,2,1,5,7,3,6，则,其后序遍历序列为（ ）。,B,A.,4,2,6,5,1,7,3,C.,4,2,3,1,5,4,7,B.,4,2,5,6,1,3,7,D.,4,2,5,6,1,7,3,二叉树,已知7个节点的二叉树的先根遍历是1,2,4,5,6,3,7(数字为结点的编号，以下同)，,后,根遍历是4,6,5,2,7,3,1，,则该二叉树的可,能的中根遍历是（,）,只知道前根遍历和后根遍历是无法确定一棵二叉树的，,所以这题采用反推验证,ABD,A.,2,*,N,B.,2,*,N,-,1,二叉树,4.,完全二叉树的结点个数为4,*,N,+,3，则,它的叶结点个数为（ ）。,C.,2,*,N,+,1,D.,2,*,N,-,2,E.,2,*,N,+,2,E,4n+3=2*2(n+1),-,1，熟悉的公式,2*叶子结点数-1，这不是满二叉树的结点数,吗,？,A.,10,B.,11,C.,12,D.,13,E.,2,10,1,二叉树,8高度为,n,的均衡的二叉树是指：如果,去掉叶结点及相应的树枝，它应该是高度,为,n-1,的满二叉树。在这里，树高等于叶,结点的最大深度，,根结点的深度为,0,，如,果某个均衡的二叉树共有,2381,个结点，,则该树的树高为（ ）。,B,2,11,23812,12,二叉树,5.,一个高度为h,的二叉树最小元素数目是,（,C）,2h-1,A）,2h+1,D）,2h,B）,h,E）,2h-1,）。,此时二叉树退化成一条链,B,图,图是由顶点和边所组成的数据结构。分为,有向图,和,无向图,。,带权图：权的含义，不加权的图也可以认为所,有边上的权都是1。,阶和度：一个图的阶是指图中顶点的个数,如果顶点A和B之间有一条边相连，则称A和B是,关联的,顶点的度：与该顶点相关联的边的数目，有奇点、,偶点之分,对于有向图：有入度和出度之分,图,大家记住定义，然后就见招拆招了。图论,的题目考得比较少，而且大家知道定义，,运用各种方法应该不难得到答案。,下面就简单地讲一下几道出现过的题目。,图,假设我们用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,BE,图,9.,欧拉图G是指可以构成一个闭回路的,图，且图G的每一条边恰好在这个闭回路,上出现一次（即一笔画成）。在以下各个,描述中,不一定是欧拉图的是：（,）。,A.,图G中没有度为奇数的顶点,B.,包括欧拉环游的图(欧拉环游是指通过,图中每边恰好一次的闭路径),C.,包括欧拉闭迹的图(欧拉迹是指通过途,中每边恰好一次的路径),D.,存在一条回路,通过每个顶点恰好一次,E.,本身为,闭迹,的图,D 解释：闭迹，一条路径，起点和终点是一个点,图,A.8,B.7+,5,C.9,D.6+,5,E.4+2,2,+,5,5.,平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G,的,顶点，每两点之间的直线距离是图G,中对应,边的权值。图G,的最小生成树中的所有边的,权值和为（,）,讲解：最小生成树算法,D,图,1.,无向图G有16条边，有3个4度顶点、4,个3度顶点，其余顶点的度均小于3，则G,至少_个顶点。,11,排列组合,前置知识：乘法原理，加法原理，排列组,合公式C(n,r)，A(n,r)的计算方法以及基本,定理和推论。,排列组合,公式：,1、不可重复的n个元素取r个的排列数为：,A(n,r),2、可重复的n个元素取r个的排列数为：,n,r,3、不可重复的n个元素取r个的组合数为：,C(n,r),4、可重复的n个元素取r个的组合数为：,C(n+r-1,r),排列组合,练习：,1.有五个不同颜色的球，从中依次拿出三,个，可能的排列有多少种,2.有五种不同颜色的球，从中依次拿出三,个，可能的排列有多少种,3.有五个不同颜色的球，从中拿出三个，,可能的组合有多少种,4.有五种不同颜色的球，从中拿出三个，,可能的组合有多少种,排列组合,A.,40320,B.,39600,C.,840,D.,780,E.,60,由3个a，5个b和2个c构成的所有字符串,中，包含子串“abc”的共有（,）个。,C(8,1),*,C(7,2),*C(5,4),*,C(1,1),-,C(6,2),*,C(4,1),*C(3,3),取出,出abc，变成2个a，4个b和1个c和abc构成字符串的,数目。一共有,有2+5+1+1=8个位置，任取1个给abc，方,法数是C(8,1)，剩下7个取2个给a，方法数C(7,2)，剩下5,个取4个放b，以此类推。但是要考虑abcabc出现两次重,复计算的情况，所以要减去，怎么减大家自己思考一下。,D,排列组合,练习字符串success重新排列，包括其本,身，共可以组成多少个不同的字符串？,C(7,2)*C(5,2)*A(3,3),=,1260,问题求解,75名儿童到游乐场去玩。他们可以骑旋转,木马，坐滑行铁道，乘宇宙飞船。已知其,中20人这三种东西都玩过，55人至少玩过,其中的两种。若每样乘坐一次的费用是5,元，游乐场总共收入700，可知有_名儿,童没有玩过其中任何一种。,集合类问题，通常可以运用数学方法解决,10,已知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语,和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日,语；e会讲意大利语和德语；f会讲俄语、日语和法语；g,会讲德语和法语。能否将他们的座位安排在圆桌旁，使,得每个人都能与他身边的人交谈？如果可以，请以“a,b”,开头写出你的安排方案：_。,abdfgc,英,汉,意,俄,日,德,法,a,O,b,O,O,c,O,O,O,d,O,O,e,O,O,f,O,O,O,g,O,O,2.,取火柴游戏的规则如下：一堆火柴有N,根，A、B两人轮流取出。每人每次可以取,1,根或2,根，最先没有火柴可取的人为败,方，另一方为胜方。如果先取者有必胜策,略则记为1，先取者没有必胜策略记为0。,当N,分别为100，200，300，400，500,时，先取者有无必胜策略的标记顺序为,（回答应为一个由0,或1,组成的字符串）。,11011,，简单的博弈论，小学奥数题,（取石子游戏）,现有,5,堆石子,石子数依,次为,3，5，7，19，50，甲乙两人轮流从,任一堆中任取（每次只能取自一堆，不能,不取）,取最后一颗石子的一方获胜。甲,先取，问甲有没有获胜策略（即无论,乙怎,样取，甲只要不失误，都能获胜）？,T=3571950=32，取掉32后T=0，面对,T=0的状态时，先取者必败,普及组的题目。,第一次在第五堆里面取32枚石子。,1将,2006,个人分成若干不相交的子集，,每个子集至少有,3,个人，并且：,（1）在每个子集中，没有人认识该子集,的所有人。,（2）同一子集的任何,3,个人中，至少,有,2,个人互不认识。,（3）对同一子集中任何,2,个不相识的,人，在该子集中恰好只有,1,个人认识这两,个人。,则满足上述条件的子集最多能有,_个？,401，主要方法是根据(1)，(2)，(3)进行假设，,发现至少需要5个人才能同时满足(1)，(2)，(3)，,于是2006/5，一个6人，其余5人,2,将边长为,n,的正三角形每,边,n,等分，过每个分点分别,做另外两边的平行线，得到若,干个正三角形，,我们称为小,三角形。正三角形的一条通路,是一条连续的折线，起点是最,上面的一个小三角形，终点是,最,下面一行位于中间的小三,角形。在通路中，只允许由一,个小三角形走到另一个与其有,公共边的且位于同,一行或下,一行的小三角形，并且每个小,三角形不能经过两次或两次以,上（图中是,n=5,时一条通路,的例,子）。设,n=10,，则该正,三角形的不同的通路的总数为,_,。,362880,严格证明挺复杂，找规律,可以知道总数为(n-1)!,1给定n个有标号的球，标号依次为1，,2，n。将这n个球放入r个相同的盒子,里，不允许有空盒，其不同放置方法的总,数记为S(n,r)。例如，S(4,2)=7，这7种不,同的放置方法依次为(1),(234),(2),(134),(3),(124),(4),(123),(12),(34),(13),(24),(14),(23)。当,n=7，r=4时，S(7,4)=_。,289,S(n,r)=S(n-1,r-1)+r*S(n-1,r),边界条件自己找。,难题，递推类问题,下面介绍一个简单的递推问题，好让大家,初步认识递推。,小明上楼，一步可以上一级，也可以上两,级，请问上n级有多少种上法？例如，上2,级可以有1+1，也可以一次上2级。上3级,可以是1+1+1，2+1,1+2三种。,设,f(n),表示上,n,级需要的步数，显然只能够从,n-1,级或,n-,2,级上到第,n,级，所以方法总数适用加法原理，,f(n)=f(n-1)+f(n-2),，斐波那契数列！,其中,f(1)=1,，,f(2)=2,，后面的都可以根据这两个初,始条件推出来,2N个人在操场里围成一圈，将这N个人,按顺时针方向从1到N编号，然后从第一个,人起，每隔一个人让下一个人离开操场，,显然，第一轮过后，具有偶数编号的人都,离开了操场。依次做下去，直到操场只剩,下一个人，记这个人的编号为J(N)，例,如，J(5)=3，J(10)=5，等等。,则J(400)=,_。,（提示：对J(N)=2,m,+r进行分析，其中,0r2,m,）。,289，找规律，数学好的智商分数的比较占优势,N,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,J(n),1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1,3,m,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,4,2,4,2,r,0,0,1,0,1,2,3,0,1,2,3,4,5,6,7,0,1,2r+1,1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1,3,非常容易看出：J(N)=J(2,m,+r)=2r+1,J(400)=J(2,8,+144)=2*144+1=289,问题求解总结,1、要耐心地寻找规律,2、要冷静的分析问题,3、不到万不得已决不轻言放弃,4、不懂就蒙一个！,阅读程序,1、认真计算,2、耐心分析,3、分析不下去就函数（语句作用）,4、千万记得第一个阅读程序要检查,5、多多练习，熟能生巧,6、列出变量变化表,程序填空,这种题与编程经验和算法学习的程度有,关，拿得一分是一分。不过对于编程经验,不足和算法练习少的人来说也不是没分可,拿。比如说,程序填空总结,1,、分析语句是干什么的，回到开头讲的内容：,初始化,一些明显的动作：,a.,结果没有储存在需要的地方。,b.,累加器没有做加法,c.,输出,关键动作。,2,、不懂就根据上下文猜,3,、不写白不写，蒙一下总是好的。,4,、千万注意开头和结尾，常常有送分题目！,几个小问题,A.,在1977年前后形成标准的计算机高级语言,FORTRAN77禁止在程序使用递归，,原因,之一是该方法可能会占用更多的内存空间.,B.,和非递归算法相比，,解决同一个问题，,递归算法一般运行得更快一些,C.,对于较复杂的问题，,用递归方式编程往往,比非递归方式更容易一些,D.,对于已定义好的标准数学函数sin(x)，,应,用程序中的语句“y=sin(sin(x);”就是一种,递归调用,20.,近20年来，,许多计算机专家都大力推崇,递归算法，认为它是解决较复杂问题的强有,力的工具.,在下列关于递归的说法中，,正确,的是（,）。,AC,A.,gcc/g+,C.,Turbo,C,B.,Turbo,Pascal,D.,free,pascal,16.在下列各软件中，属于,NOIP,竞赛（复,赛）推荐使用的语言环境有（,）。,ABD,A.,Pascal和C都是编译执行的高级语言,B.,高级语言程序比汇编语言程序更容易从,一种计算机移植到另一种计算机上,C.,C+是历史上的第一个支持面向对象的,计算机语言,D.,高级语言比汇编语言更高级，是因为它,的程序的运行效率更高,18.,在下列关于计算机语言的说法中，正,确的有（,）。,AB,3.在下面各世界顶级的奖项中，为计算机,科学与技术领域作出杰出贡献的科学家设,立的奖项是（,）。,C.,菲尔,B.,诺贝尔奖,E.,南丁格尔奖,A.,沃尔夫奖,兹奖,D.,图灵奖,D,2.,在关系数据库中,存放在数据库中的数,据的逻辑结构以(,)为主。,C.,哈希表,B.,多叉树,E.,二维表,A.,二叉树,D.,B+树,E,数据库有层次型数据库、关系型数据库、,网状数据库,层次是树，关系是二维表，网状是链接指针,A.,一个正确的算法至少要有一个输入,B.,算法的改进，在很大程度上推动了,计算机科学与技术的进步由,C.,判断一个算法的好坏，主要依据它,在某台计算机上具体实现时的运行时,间,D.,目前仍然存在许多涉及到国计民生,的重大课题，还没有找到能够在计算,机上实施的有效算法,19.,在下列关于计算机算法的说法,中，正确的有（,）。,BD,19.,下列活动中属于信息学奥赛系列活动,的是（,）。,A.,NOIP,B.,NOI,C.,IOI,D.,冬令营,E.,国家队选拔赛,ABCDE,16.,处理器A,每秒处理的指令数是处理器B,的2,倍。某一特定程序P,分别编译为处理器A,和处理器B,的指令，编译结果处理器A,的指令数,是处理器B,的4,倍。已知程序P,的算,法时间复杂度为O(n,2,)，如果处理器A执行程序P,时能在一小时内完成的输入规模为n，,则处理器B执行程序P时能在一小时内完成的输,入规模为（,）。,A.,4,*,n,B.,2,*,n,C.,n,D.,n,/,2,E.,n,/,4,B,彩色显示器所显示的五彩斑斓的色彩，是,由哪三色混合而成的（,）。,A.,红,B.,白,C.,蓝,D.,绿,E.,橙,ACD,美籍匈牙利数学家冯诺依曼对计算机科学发展,所做出的贡献包括（,）。,A提出理想计算机的数学模型，成为计算机科学,的理论基础。,B提出存储程序工作原理，对现代电子计算机的,发展产生深远影响。,C设计出第一台具有存储程序功能的计算机,EDVAC。,D采用集成电路作为计算机的主要功能部件。,E指出计算机性能将以每两年翻一番的速度向前,发展。,AB,下列哪个（些）是64位处理器（,）。,A.,Intel,Itanium,B.,Intel,Pentium,III,C.,AMD,Athlon64,D.,AMD,Opteron,E.,IBM,Power,5,ACDE补充：,双核处理器：,AMD速龙（althon）系列，奔腾D，酷睿,系列,幽默一下,20.,在下列关于青少年信息学竞赛的说法中，你赞成的,是（,）,A.,举行信息学竞赛的目的，是为了带动广大青少年学科,学、爱科学，为造就一大批优秀的计算机科学,与技术人,才奠定良好的基础,B.,如果竞赛优胜者不能直接保送上大学，我今后就不再,参与这项活动了,C.,准备竞赛无非要靠题海战术，为了取得好成绩，就得,拼时间、拼体力,D.,为了取得好成绩，不光要看智力因素，还要看非智力,因素。优秀选手应该有坚韧不拔的意志，有严谨求实的,作风，既要努力奋进，又要胜不骄败不馁,不是空着就得分,预祝大家初赛取得好成绩！,
展开阅读全文