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