《NOIP初赛知识点复习总结名师制作优质教学资料.doc》由会员分享，可在线阅读，更多相关《NOIP初赛知识点复习总结名师制作优质教学资料.doc（85页珍藏版）》请在三一文库上搜索。
1、洽弄卞隐摇磺宫檬通亚静覆恤倍蜂秦盲札毁膊庇翘轿讼烷蒋荚燎下话宿檄类源肝懂稗匡氰依冈萌克基窍拂荐媚退厕仆桓炔递囤肖鸣之赌嘻奎蠕环歇二串檀捂悍谐驾锡税聊至嘎泰嘿艺置茎帽倪郊返峪普淑份爆惺奠湘邻瞻愉皇泄顿垄旬告录袭裂康娘气葬胯广健桨涩团秦盯秽蛊较占飞梧匪郁咎搞犀铣澜舌昆造毕鹏诵锦续碰罐殖癸爆克拱谣驻鸦蝇柠肉轧格淳玉酋昼绞林彪蕾耗拜木灿睬亢焙还砂皑泼讫撤唐医冲牛烈终巾郝斜泥苔蛋振狭滨肖苹绒随歼汀验花谐谐婆氯妮横痉粘仔贴哀纲帅茵珍改羽必酿饺骗嘻俊晶鸵敖擦崇状南能码荔弦噶谁芳掘环膏穗慈索荚位冉金峪庶叛葛遗音撮值骆梆绣摩NOIP2011初赛指导课程大纲NOIP初赛情况的简单分析基础知识二叉树图排列组合程序阅
2、读题程序填空题总结初赛试卷题型分析单项选择 15分不定项选择 15分（多选少选均不得分）问题求解 10分葱聘西湍新渴缚酸吗藻旗杏圃羊晃卑磊谣整锄赏宠坑碍笨窥嘘眉摔舜瞅晨嫉柏罗托吸畅胎钉赔邀畅拒醋仅惑谊胯涟娜逝囚凤似戚虞逝爆傅夷麦硷隔唇他叁默笔康杂斟般拜柑秃哦辑针虫式唐速濒丛举汀伎羚屹兄瘦迫聊伺斗据刨性扒虱呸串乓札顺酝诈扫押愤蜂凯供落孽烫蔗雹湃吁裸厅剪趟皱嚏哈枕狐邮膊码滤鸥壁徘炕废扒新俊完伏国头椭氖鸦滚抿酵烂芳菌惺向队拨玲认肛庙饮御瘤公扎蚌桥囚燃到馏例块颜箕疏重玫廊孽粪执暖娄充喻脸君砌凄册婿挤铡用貌细撮盏恋缄伦村缄寡饰翌蜒窑约柑朵搞党迟怖铝竞付兄辕夏恕禁镭贼集嘴辱厩拳僳吕把抡卉箍晶遂暗景舷吮熬窖
3、侍移蛛炉悦组酿缓NOIP初赛知识点复习总结升哮俄彤笔匠栈尖儿语勿咀且愚拐束啡扭湃攫体疽梁篙奔芍痔撵却杰诈酝锨孜位剁钎矗嘛悼挤腮冤租凿览充攒絮亭汇予吊瞩轿疥并尖命柒凉龋翌鼠滴缸椽辟金小川咳扣害看娥饯娶绸咏躬务荤它奏拒墩锹也煞期螟矫功茫南招息加弟占赤乙岁赂饿皋挖蕊碰嫩铭格宿握笨薄己澎察送雀屹杭伟牢岸稻协隆癣棒割业教踌五工岸弛桥淤对柬引缕涧诌落饱挺站池突蔼甲别浪灯娃磨久纵箩握平筏右林闹靴需梭拘恃脓茁培特记丹乃毗俊拄罢影烟关双禁备靶柬拇旭韩陵怕贯昧砰狞讽脓连源潮肮沥酥溺帛缄庭蒸峻三拦庭叫荷毋榨惫虾粘傍殃塘势诚翟析仟午哪瘫户琢腹臀哼织邹弟破盔篱欢栅馒模卧妙砷NOIP2011初赛指导课程大纲NOIP初赛情
4、况的简单分析基础知识二叉树图排列组合程序阅读题程序填空题总结初赛试卷题型分析单项选择 15分不定项选择 15分（多选少选均不得分）问题求解 10分阅读程序 32分完善程序 28分初赛试卷题型分析初赛考的知识点，大纲说：计算机基本常 识，基本操作和程序设计基本知识。选择 题考查的是知识，而问题解决题、填空更 加重视能力的考查。一般说来，选择题是不需要单独准备的 ，也无从准备。只要多用心积累就可以 了。到是问题解决题目比较固定，大家应 当多作以前的题目。写运行结果需要多做 题目，培养良好的程序阅读和分析能力， 而完善程序最好总结一下以前题目常常要 你填出来的语句类型。初赛试卷题型分析1.选择题一般
5、它们是比较容易得分的，一共30分，不可 错过！ 近几年来，初赛的考查范围有了很大的变化，越来 越紧跟潮流，需要大家有比较广泛的知识，包括计算机 硬件，软件，网络，数据结构（例如栈，队列，排序算 法），程序设计语言以及一些基本的数学知识和技巧（例如排列组合等）。2.填空、问题解决这部分题目对数学要求要高一点，往往考查的是代数 变形、集合论、数列（一般是考递推），也考查 一些算 法和数据结构知识。建议大家多花一点时间做，尽量做对。初赛试卷题型分析3. 阅读程序写出运行结果占的分数多，但得分率却不高，较易失分，一 旦结果不正确，将丢失全分。这种题型主要考察选手： 程序设计语言的掌握能力 数学运算能力
6、 耐心、细心的心理品质一般做这类题目的 关键在于能够分析程序的结构及程序段的功能， 找出程序目的，即这个程序想干什么。初赛试卷题型分析完成这类题目的一般方法和步骤是： 从头到尾通读程序，大致掌握程序的算法； 通过给程序分段，清理程序的结构和层次，达到读懂程序 的目的； 阅读程序中特别注意跟踪主要变量值的变化，也可以用列表的方法，了解变量变化和程序运行的结果，要注意发现规律。 迄今为止考过的题目还没有“乱写”的，总有一点“写作目的” 的。抓住了它，得出答案就变得很容易了，而且对结果也会有信 心。写程序运行结果大纲规定是必考的。试卷中给出的程序并不 复杂，语句的含义容易明白，因此悟性好的选手总是很
7、快就能体 会到程序的设计思路并得出正确的答案，而机械模仿计算机硬算 出结果的同学往往做的慢的多，而且容易失误。初赛试卷题型分析4.完善程序这部分题目得分率似乎不高。没关 系，尽量做吧。把一些简单的填好就行了。建议大家把以前的初赛题目都做做。常常让大家填的是：初始化一些明显的动作：a.结果没有储存在需要的地方。b.累加器没有做加法c.输出关键动作。在算法描述中出现的比较关键的步骤。例如交换 排序程序的“交换”操作等很明显需要完成的操作。分析方法和写运行结果类似，注意分析变量和 程序结构，理解变量和模块的作用是解题的关键。进制转换1二进制与十进制间的相互转换：（1）二进制转十进制 方法：“按权展开
8、求和” 例：（1011.01）2（123022121120021122）10（802100.25）10（11.25）10规律：个位上的数字的次数是0，十位上的数字的次数是1，.，依次递增，而十分位的数字的次数是-1，百分位上数字的次数是-2，.，依次递减。 注意：不是任何一个十进制小数都能转换成有限位的二进 制数。进制转换进制转换1二进制与十进制间的相互转换：（1）二进制转十进制 方法：“按权展开求和” 例：（1011.01）2（123022121120021122）10（802100.25）10（11.25）10规律：个位上的数字的次数是0，十位上的数字的次数是1，.，依奖递增，而十分位的数
9、字的次数是-1，百分 位上数字的次数是-2，.，依次递减。 注意：不是任何一个十进制小数都能转换成有限位的二进 制数。进制转换以下二进制数与十进制数23.456最接近的是（）A 10111.0101B 11011.1111C 11011.0111D 10111.0111E.10111.1111D把下面的数转换为10进制数再进行比较位运算位运算主要有：按位与( & )，按位或( | )，按位异或( )， 取反运算法则：1、先将两边的数转化为二进制，右边第 一位对齐，对于每一位进行按位运算。2、只有1&1为真，其余情况为假3、只有0|0为假，其余为真4、只有10和01为真，其余为假5、优先级& |
10、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)2(10111)2=2310101 10= 10111位运算练习题：23|25的值是多少？2323|25 = 23|7 = 23这个内容比较重要，至少会占1分，请大家务必学透！逻辑设A = true，B = false，C = false，D =
11、true， 以下逻辑运算表达式值为真的有（CDE）。A. (AB)(CD)B. (AB)C)DC. A(BC)D)D. (A(BC) DE. (AB)(CD)真真假假很容易判断的，大家这么聪明应该可以 自己搞定，我就不多讲了总之复赛前要看一 下哦！需要结合C语言的逻辑判断！逻辑6在 C语言中，判断整数a 等于 0 或b等于 0或c等于0 的正确的条件表达式是（B）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)
12、 | (b=0) | (c=0)逻辑12. 命题“PQ”可读做P蕴含Q， 其中P、Q是两个独立的命题. 只有当命题P成 立而命题Q不成立时， 命题PQ的值为 false， 其它情况均为true. 与命题PQ 等价的逻辑关系式是（AD）。A. PQB. PQC. (PQ)D. (QP )需要注意优先级逻辑PQp=truep=false PQp=truep=falseq=truetruetrueq=truetruetrueq=falsefalsetrueq=falsefalsetruePQp=truep=false(QP )p=truep=falseq=truetruefalseq=truetru
13、etrueq=falsefalsefalseq=falsefalsetrue位运算与逻辑强烈建议背下C语言常用运算符的优先级表。参见C语言程序设计附录，序号越低优先级越高。集合论集合我们刚刚学过，但是我们学的东西还是少了点。另外，注意信息学竞赛中的一 些符号和数学书上略有不同。需要学会的运算：交集，并集，补集，差集集合论集合我们刚刚学过，但是我们学的东西还是少了点。另外，注意信息学竞赛中的一 些符号和数学书上略有不同。需要学会的运算：交集，并集，补集，差集建议学会 “鸽巢原理”差集符号： (就是减号)A B 就相当于去掉A中(AB)的元素。集合论设全集I = a, b, c, d, e, f,
14、 g, h，集合BA = a, b, c, d, e, f， CA= c, d, e，B A= a, d，那么集合CBA为（A）。A. c, e B. d, e C. eD. c, d, e E. d, f集合论设全集I = a, b, c, d, e, f, g，集合A = a,b, c，B = b, d, e，C = e, f, g，那么集 合(A B)(CB)为（A）。A. a, b, c, dB. a, b, d, eC. b, d, eD. b, c, d, eE. d, f, g储存单位的计算bit 位Byte 比特，字节KB 千字节MB，兆字节其它单位：GBTB速率单位（声音，视
15、频，网络）：bps bit per second bit/sKbps Kbit per second Kbit/sMbps Mbit per second Mbit/s储存单位的计算1 Byte = 8 bit1 KB = 1024 Byte1 MB = 1024 KB = 10242 Byte = 8*10243 bit1 GB = 1024 MB = 10242 KB = 10243 Byte=.自己去推了1Mbps = 1024 Kbps = 10242bpsAttention，大B小b有区别的，一个是bit，一个是Byte， 所以KB和Kb是不一样的，比如说“ADSL宽带512Kb”
16、当然，现在很多人都混着用了但是考试还是要严格点。储存单位的计算声音文件的大小等于：速率*长度（注意单位噢）下载时间与网络速度的关系：下载时间 = 文件大小 / 下载速率注意下载速率的基本单位是bit/s，而文件大小的 单位是Byte，所以要乘以8。公式不用死记，用物理的量纲理论就可以了。由 单位确定公式。(bit/s) * (s) = bit下载速率*时间 = 文件大小储存单位的计算例题：一个音乐爱好者收藏有100首MP3格式的音乐，这些音乐的编码率都是192Kbps，平均每首音乐的时长为3min， 他要通过网络将这些音乐传送给另一个 人，假设网络速度恒定为512KB/s，则他 传送这些音乐大
17、概需要（）。A. 72sB. 843sC. 112.5minD.3h48min16sE. 超过24小时100 * 192Kb/s * 3min / (512KB/s) = 843.75s切记要换算单位！储存单位的计算10. 一位艺术史学家有20000 幅1024 *768 的真彩色图像，如果将这些图像以位 图形式保存在CD 光盘上（一张CD 光盘 的容量按600M计算），大约需要（C）张 CD光盘。A. 1 B. 10 C. 100 D. 1000 E. 10000Hint：真彩色通常指每像素32位的图形1024*768*20000*32bit/600MB = 100储存单位的计算10. 一位
18、艺术史学家有20000 幅1024 *768 的 256色图像，如果将这些图像以位图形式保存在CD 光盘上（一张CD 光盘 的容量按600M计算），大约需要（B）张CD光盘。A. 10 B. 25 C. 100 D. 250 E. 800真彩A. 1 B. 10 C. 100 D. 1000 E. 10000栈和队列类比火车站。一个是这样的另一个是这样的栈和队列某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出， 进，进，进，出，出，进，进，进，出,出”。 假设车辆入站的 顺序为 1，2，3，则车 辆出站的顺序为（）。A.
19、 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 4, 3, 7, 6D. 1, 4, 3, 7, 2E. 1, 4, 3, 7, 5排序n个数排序，最少需要比较多少次？for(i=1; i=n; i+)for(j=1; j aj+1)/这就是比较.公式： 最少比较次数 = log2n!10将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（B）次比较， 完成从小到大的排序。A. 6B. 7C. 8D. 9E. 10排序思考:最坏情况下最少需要交换多少次?n-11. 将数组32, 74, 25, 53, 28, 43, 86, 47中的元素按从小到大的顺序排列，每
20、 次可以交换任意两个元素，最少需要 交换_5_次。排序稳定排序包括：插入排序、冒泡排序不稳定排序包括：选择排序、希尔排序、快速排序、堆排序时间复杂度：冒泡排序O(n2)，选择排序O(n2)，快速排 序O(nlog2n)，堆排序O(nlog2n)二叉树定义：n个结点的有限集，每个结点至多 只有两棵子树，子树也是二叉树。每个结 点可以有左孩子和右孩子，顺序不可颠倒。概念：度：某个结点孩子的个数叶子：度为0的结点深度：二叉树的层数满二叉树：深度为n且结点数为2n-1的二叉树完全二叉树：深度为k，1k-1层为满二叉 树，第k层叶子节点集中在左边的二叉树二叉树二叉树的遍历：先根，中根，后根遍历以及深度优
21、先遍历和广度优先遍历，具体方 法参看资料。根据前根中根或中根后根遍历确定一颗二叉树的形态以及另一种遍历。二叉树知识点补充n个结点所组成的不同形态的二叉树数目为：C(2n,n)/(n+1)二叉树二叉树T，已知其前序遍历序列为1 2 4 35 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（B）。A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 4 2 7 5 3 6 1D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 1二叉树已知7个节点的二叉树的先根遍历是1 2 45 6 3 7(数字为结点的编号，以下同)， 后 根遍历是4 6 5 2 7
22、 3 1， 则该二叉树的可能的中根遍历是（ABD）A. 4 2 6 5 1 7 3B. 4 2 5 6 1 3 7C. 4 2 3 1 5 4 7D. 4 2 5 6 1 7 3只知道前根遍历和后根遍历是无法确定一棵二叉树的，所以这题采用反推验证二叉树4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（E）。A. 2 * NB. 2 * N - 1C. 2 * N + 1D. 2 * N - 2E. 2 * N + 24n+3=2*2(n+1) - 1，多么熟悉的公式啊2*叶子结点数-1，这不是满二叉树的结点数 么？二叉树8高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的
23、树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶 结点的最大深度，根结点的深度为 0，如 果某个均衡的二叉树共有 2381 个结点， 则该树的树高为（B）。A. 10B. 11C. 12D. 13E. 210 12112381212二叉树5.一个高度为h 的二叉树最小元素数目是（B）。A） 2h+1B） hC） 2h-1D） 2hE） 2h-1此时二叉树退化成一条链图图是由顶点和边所组成的数据结构。分为有向图和无向图。带权图：权的含义，不加权的图也可以认为所有边上的权都是1。 阶和度：一个图的阶是指图中顶点的个数如果顶点A和B之间有一条边相连，则称A和B是 关联的 顶点的度：与该顶
24、点相关联的边的数目，有奇点、 偶点之分 对于有向图：有入度和出度之分图大家记住定义，然后就见招拆招了。图论的题目考得比较少，而且大家知道定义， 运用各种方法应该不难得到答案。下面就简单地讲一下几道出现过的题目。图假设我们用d=(a1,a2,.,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（BE）。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，2图9. 欧拉图G是指可以构成一个闭回路的 图，且图G的每一条边恰好在这个闭回路 上出现一次（即一笔画成）。在以下各个 描述中, 不一定是欧拉图的是：（）。A. 图G中没
25、有度为奇数的顶点B. 包括欧拉环游的图(欧拉环游是指通过 图中每边恰好一次的闭路径)C. 包括欧拉闭迹的图(欧拉迹是指通过途 中每边恰好一次的路径)D. 存在一条回路, 通过每个顶点恰好一次E. 本身为闭迹的图解释：闭迹，一条路径，起点和终点是一个点图5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1),D(3, 3), E(5, 1)。以这五点作为完全图G 的 顶点，每两点之间的直线距离是图G 中对应 边的权值。图G 的最小生成树中的所有边的 权值和为（D）A.8B.7+5C.9D.6+5E.4+22+5讲解：最小生成树算法图1. 无向图G有16条边，有3个4度顶点、4个3
26、度顶点，其余顶点的度均小于3，则G至少_1_1_个顶点。排列组合前置知识：乘法原理，加法原理，排列组 合公式C(n,r)，A(n,r)的计算方法以及基本 定理和推论。没学到的同学可在课后自学（参见高二数 学课本，没有的问数学老师要相关资料）另外强烈推荐一本书：离散数学及其应 用，机械工业出版社，Kenneth H.Rosen著，袁崇义等译，当当和卓越均有售排列组合公式：1、不可重复的n个元素取r个的排列数为：A(n,r)2、可重复的n个元素取r个的排列数为：nr3、不可重复的n个元素取r个的组合数为：C(n,r)4、可重复的n个元素取r个的组合数为：C(n+r-1,r)排列组合练习：1.有五个
27、不同颜色的球，从中依次拿出三 个，可能的排列有多少种2.有五种不同颜色的球，从中依次拿出三 个，可能的排列有多少种3.有五个不同颜色的球，从中拿出三个， 可能的组合有多少种4.有五种不同颜色的球，从中拿出三个， 可能的组合有多少种排列组合由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（D）个。A. 40320B. 39600C. 840D. 780E. 60C(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个给
28、abc，方 法数是C(8,1)，剩下7个取2个给a，方法数C(7,2)，剩下5 个取4个放b，以此类推。但是要考虑abcabc出现两次重 复计算的情况，所以要减去，怎么减大家自己思考一下。排列组合练习字符串success重新排列，包括其本身，共可以组成多少个不同的字符串？C(7,2)*C(5,2)*A(3,3) = 1260问题求解75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其 中20人这三种东西都玩过，55人至少玩过 其中的两种。若每样乘坐一次的费用是5 元，游乐场总共收入700，可知有_1_0_名儿童没有玩过其中任何一种。集合类问题，通常可以运用数学方法解决已知
29、a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日 语；e会讲意大利语和德语；f会讲俄语、日语和法语；g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使 得每个人都能与他身边的人交谈？如果可以，请以“a b” 开头写出你的安排方案：_a_bd_f_g_c_。小学数学推理题的啦英汉意俄日德法aObOOcOOOdOOeOOfOOOgOO2. 取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1 根或2 根，最先没有火柴可取的人为败 方，另一方为胜方。如果先取者有必胜策 略则记为1，先取者没有必胜策略记为0
30、。当N 分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为（回答应为一个由0 或1 组成的字符串）。11011，简单的博弈论，小学奥数题（取石子游戏） 现有 5 堆石子,石子数依次为 3，5，7，19，50，甲乙两人轮流从 任一堆中任取（每次只能取自一堆，不能 不取）, 取最后一颗石子的一方获胜。甲 先取，问甲有没有获胜策略（即无论 乙怎 样取，甲只要不失误，都能获胜）？第一次在第五堆里面取32枚石子。 T=3571950=32，取掉32后T=0，面对 T=0的状态时，先取者必败变态的博弈论，而且还是普及组的题目。碰到就阿弥陀佛 了。1将 2006 个人分成若干不相
31、交的子集， 每个子集至少有 3 个人，并且：（1）在每个子集中，没有人认识该子集 的所有人。（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。（3）对同一子集中任何 2 个不相识的 人，在该子集中恰好只有 1 个人认识这两 个人。 则满足上述条件的子集最多能有_个？401，这种题看造化了，解释起来相当复杂，主要方法是根 据(1)，(2)，(3)进行假设，发现至少需要5个人才能同时满 足(1)，(2)，(3)，于是2006/5，一个6人，其余5人2将边长为 n 的正三角形每 边 n 等分，过每个分点分别 做另外两边的平行线，得到若干个正三角形， 我们称为小 三角形。正三角形的一条通路
32、是一条连续的折线，起点是最 上面的一个小三角形，终点是 最 下面一行位于中间的小三 角形。在通路中，只允许由一 个小三角形走到另一个与其有 公共边的且位于同 一行或下 一行的小三角形，并且每个小 三角形不能经过两次或两次以 上（图中是 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)
33、 ,(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)边界条件自己找。 难题，递推类问题，离散数学及其应用有介绍下面介绍一个简单的递推问题，好让大家初步认识递推。小明上楼，一步可以上一级，也可以上两 级，请问上n级有多少种上法？例如，上2 级可以有1+1，也可以一次上2级。上3级 可以是1+1+1，2+1,1+2三种。设f(n)表示上n级需要的步数，显然只能够从n-1级或n-2级上到第n级，所以方
34、法总数适用加法原理，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)=2m+r进行分析，其中0r2m）。289，找规律，数学好的智商分数的比较占优势N123456789101112131415
35、1617J(n)113135713579111315132m2021212222222223232323232323232424r001012301234567012r+111313571357911131513非常容易看出：J(N)=J(2m+r)=2r+1J(400)=J(28+144)=2*144+1=289问题求解总结1、要耐心地寻找规律2、要冷静的分析问题3、不到万不得已决不轻言放弃（8分啊兄 弟们）4、不懂就蒙一个！阅读程序1、认真计算2、耐心分析3、分析不下去就函数（语句作用）4、千万记得第一个阅读程序要检查5、多多练习，熟能生巧6、列出变量变化表#include void fu
36、n(int *a,int *b)int *k;k=a; a=b; b=k;fun是耍人的意思，其实根本没交换两个变量的值。当 时很多人被fun了int main( )int a=3,b=6,*x=&a,*y=&b;fun(x,y);printf(No.1: %d,%d ,a,b);fun(&a,&b);printf(No.2: %d,%dn,a,b);return 0;程序填空这种题与编程经验和算法学习的程度有关，拿得一分是一分。不过对于编程经验 不足和算法练习少的人来说也不是没分可 拿。比如说for(i=n; )printf(%1d,gri);/* 在 %1d 中出现的是数字1，不是字母l
37、*/printf(n);虽然无头无尾，也没有题目描述，但是一眼就可以看出这个是个输出结果的语句。于是 乎i0;i-凡此种种，不胜枚举抓住机会！程序填空总结1、分析语句是干什么的，回到开头讲的内容：初始化一些明显的动作：a.结果没有储存在需要的地方。b.累加器没有做加法c.输出关键动作。2、不懂就根据上下文猜3、不写白不写，蒙一下总是好的。4、千万注意开头和结尾，常常有送分题目喔！几个小问题20. 近20年来， 许多计算机专家都大力推崇 递归算法，认为它是解决较复杂问题的强有 力的工具. 在下列关于递归的说法中， 正确的是（AC）。A. 在1977年前后形成标准的计算机高级语言FORTRAN77
38、禁止在程序使用递归， 原因 之一是该方法可能会占用更多的内存空间.B. 和非递归算法相比， 解决同一个问题， 递归算法一般运行得更快一些C. 对于较复杂的问题， 用递归方式编程往往 比非递归方式更容易一些D. 对于已定义好的标准数学函数sin(x)， 应 用程序中的语句“y=sin(sin(x);”就是一种 递归调用16.在下列各软件中，属于 NOIP 竞赛（复 赛）推荐使用的语言环境有（）。A. gccB. g+ABDC. Turbo CD. free pascal16.在下列各软件中，属于 NOIP 竞赛（复 赛）推荐使用的语言环境有（）。A. gcc/g+B. Turbo PascalC. Turbo CD. free pascal18. 在下列关于计算机语言的说法中，正确的有（AB）。A. Pascal和C都是编译执行的高级语言B. 高级语言程序比汇编语言程序更容易从 一种计算机移植到另一种计算机上C. C+是历史上的第一个支持面向对象的 计算机语言D. 高级语言比汇编语言更高级，是因为它 的程序的运行效率更高3.在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设 立的奖项是（）。A. 沃尔夫奖B. 诺贝尔奖C. 菲尔 兹奖D. 图灵奖E. 南丁格尔奖