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

NOIP提高组初赛历年试题及答案求解题篇 2 5 10 5 问题求解题 （每次 题，每题 分，共计 分。每题全部答对得 分，没有部 分分）注：答案在文末 提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推 理、递推问题、排列组合问题等。 NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无 4 6 5 向图。 个顶点的平面图至少有 条边，如图所示。那么， 个顶点的平面图至 _________ 多有 条边。 NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。 “BCA” A B “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.对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。 1 5 1 3 1 例如，图 有 个不同的独立集 （个双点集合、 个单点集合、 个空集）， 2 14 3 _________ 图 有 个不同的独立集。那么，图 有 个不同的独立集。 NOIP2013-1.某系统自称使用了一种防窃听的方式验证用户密码。密码是n个 数s1,s2,…,sn，均为0 或1。该系统每次随机生成n个数a1,a2,…,an，均为0 或1，请用户回答(s1a1+s2a2+…+snan)除以2 的余数。如果多次的回答总是正 确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码 ——因为用户并没有直接发送密码。 n 4 5 然而，事与愿违。例如，当 时，有人窃听了以下 次问答： 就破解出了密码s1 _________，s2 _________，s3 _________， s4 _________。 NOIP2013-2. n k 现有一只青蛙，初始时在 号荷叶上。当它某一时刻在 号荷叶 1,2,…,k 1 上时，下一时刻将等概率地随机跳到 号荷叶之一上，直至跳到 号荷叶 n 2 2 n 3 2.5 n 5 为止。当 时，平均一共跳 次；当 时，平均一共跳 次。则当 _________ 时，平均一共跳 次。 NOIP2014-1.由数字1,1,2,4,8,8 所组成的不同的四位数的个数是_________。 NOIP2014-2. A E 如