资源描述：
《noip提高组初赛历年试题-及答案~求解题篇》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、
2、NOIP提高组初赛历年试题及答案求解题篇问题求解题（每次2题，每题5分，共计10分。每题全部答对得5分，没有部分分）注：答案在文末提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如图所示。那么，5个顶点的平面图至多有_________条边。NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将A移到B之前，变字符串“
3、ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。NOIP2012-1. 本题中，我们约定布尔表达式只能包含p,q,r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。如果无论p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r和p∨(q∨r)等价，p∨¬p和q∨¬q也等价；而p∨q和p∧q不等价。那么，两两不等价的布尔表达式最多有_________个。NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例
4、如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），
5、图2有14个不同的独立集。那么，图3有_________个不同的独立集。NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn，均为0或1。该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。例如，当n=4时，有人窃听了以下
6、5次问答：就破解出了密码s1=_________，s2=_________，s3=_________，s4=_________。NOIP2013-2. 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5
7、时，平均一共跳_________次。NOIP2014-1.由数字1,1,2,4,8,8所组成的不同的四位数的个数是_________。NOIP2014-2. 如图所示，图中每条边上的数
8、字表示该边的长度，则从A到E的最短距离是_________。NOIP2015-1. 在1和2015之间(包括1和2015在内)不能被4、5、6三个数任意一个数整除的数有_________个。NOIP2015-2. 结点数为5的不同形态的二叉树一共有_________种。(结点数为2的二叉树一共有2种:一种是根结点和左儿子，另一种是根结点和右儿子。)NOIP2016-1. 一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。NOIP2016-2.
9、某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。最少要安排_________个不同的考试时间段才能避免冲突？
10、NOIP2011-1.无向简单图问题C(4,2)=6；C(5,2)=10。但这是“边仅在顶点上才能相交”的简单连通平面图，可手画该平面图计算边数，也可根据平面图的欧拉公式（v＋f＝e＋2）推得的定理：设G为有v个顶点e条边的简单连通平面图，若v>=3，则e<=3v-6，计算得9。NOIP2011-2最长正序列问题在普及组求解题中，我们介绍了列表求编辑距离的方法。
11、这里我们也可以用更简便的方法——“最长上升子序列”法。原字符串的最长上升子序列为：ACEGI，剩下4个字符移动插入4次即可。其中，用动态规划的方法来求出最长上升子序列的长度。将第一个字母的值设为1。之后对于每一个字母，都在字符串前面找比它小（在想要成为的字符串中在它前面的）的字母，并从中选出值（n）最大的，将这个字母的值设为n+1。如果找不到就设为1。在以下的表格中，可以看出最大的值为5，即最长上升子序列的长度为5。
12、NOIP2012-1逻辑运算问题三个变量，每个变量可取0,1两种值，共有2^3=8种组合；任意一个变量组合代入表达式，只有0
13、和1两种值。因此两两不等价的表达式最多有2^8=256种。NOIP2012-2图的独立集问题图1的独立集：{∅}{1}{2}{3}{2,3}图2的独立集：{∅}{1}{2}{3}
