NOIP提高组初赛历年试题及答案求解题篇样稿.docx

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