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

《NOIP普及组初赛历年试题及答案求解题篇.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP普及组初赛历年试题及答案求解题篇问题求解：每次共2题，每空5分，共计10分。每题全部答对得5分，没有部分分。注：答案在文末在NOIP初赛问题求解中，经常会遇到排列组合问题。这一类问题不仅内容抽象，解法灵活，而且解题过程极易出现“重复”和“遗漏”的错误，这些错误甚至不容易检查出来，所以解题时要注意不断积累经验，总结解题规律。解答排列组合问题，首先必须认真审题，明确是属于排列问题还是组合问题，或者属于排列与组合的混合问题，其次要抓住问题的本质特征，灵活运用基本原理和公式进行分析解答。同时还要注意讲究一些策略和技巧，比如采用分类、分步、捆绑等方法

2、，也可以借助表格、方程等工具，使一些看似复杂的问题迎刃而解。NOIP2011-1.每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时，它才是有效的。例如，0000000、01010011都是有效的序列号，而11111110不是。那么，有效的序列号共有______个。NOIP2011-2.定义字符串的基本操作为:删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。字符串“ABCDEFG”到字符串“BADECG”的编辑距离为_______。NOIP2

3、012-1.如果平面上任取n个整点(横纵坐标都是整数)，其中一定存在两个点，它们连线的中点也是整点，那么n至少是_____。NOIP2012-2.在NOI期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么，这一桌共有_____种不同的就坐方案。注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。NOIP2013-1.7个同学围坐一圈，要选2个不相邻的作为代表，有

4、_____种不同的选法。NOIP2013-2.某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,...,sn，均为0或1。该系统每次随机生成n个数a1,a2,...,an，均为0或1，请用户回答(s1a1+s2a2+...+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答:就破解出了密码s1=_____，s2=_____，s3=_____，s4=_____。NOIP2014-1

5、.把M个同样的球放到N个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法?(用K表示)。例如：M=7，N=3时，K=8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。问:M=8，N=5时，K=_____。NOIP2014-2.如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是____。NOIP2015-1.重新排列1234使得每一个数字都不在原来的位置上，一共有_____种排法。NOIP2015-2.一棵结点数为2015的二叉树最多有_____个叶子结点。NOIP2016-1.从一个4×4的棋盘(不可旋转)

6、中选取不在同一行也不在同一列上的两个方格，共有______种方法。NOIP2016-2.约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有______个叶子结点;一棵结点数为2016的二叉树最小的高度值是______。NOIP2011-1.组合计数问题。C(n,m)=n!/(n-m)!*m!C(8,0)+C(8,2)+C(8,4)+C(8,6)+C(8,8)=128NOIP2011-2.编辑距离问题。先创建一个8×9（BADECG长度为6，ABCDEFG长度为7，各加2）的表如下：1、在第一行第一列分别填上两个字符串2、在第二行第二列分

7、别填上序列号3、从第三行第三列这一格开始计算填充。行列字符相等，则填左上角的数字；行列字符不等，在“左上角数字+1、左方数字+1、上方数字+1”中取最小值填充4、取最右下角的值，得编辑距离为3。NOIP2012-1.鸽巢原理问题。同一直线上三个点的坐标：(x1,y1)、(x2,y2)和中点（(x1+x2)/2,(y1+y2)/2）。如果三个点都是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。平面上的整点只有四类：(奇数,奇数)，(偶数,偶数)，(奇数,偶数)，(偶数,奇数)，根据鸽巢原理，在平面上任取五个整点，那么至少有两个整点属于一类，它

8、们连线的中点就必是整点。所以n至少是5。NOIP2012-2.圆桌排列问题。以3人为例，直线排列方案：A(3,3)=3!=