当前位置 : 首页> 少儿编程 > 有关全国NOIP青少年信息学奥赛试题分享

有关全国NOIP青少年信息学奥赛试题分享

时间:2018-08-06 14:07:34   已访问:161次
热门专业

NOIP信息学奥赛可以帮我们一举成名,也可以让我们看到青少年的实力,在NOIP问题不仅内容抽象,解法灵活,而且解题过程极易出现“重复”和“遗漏”的错误,这些错误甚至不容易检查出来,所以解题时要注意不断积累经验,总结解题规律,下面一起分享一些有关NOIP青少年信息学奥赛试题及答案。

全国NOIP于少年信息学奥赛试题分享

解答排列组合问题,首先必须认真审题,明确是属于排列问题还是组合问题,或者属于排列与组合的混合问题,其次要抓住问题的本质特征,灵活运用基本原理和公式进行分析解答。同时还要注意讲究一些策略和技巧,比如采用分类、分步、捆绑等方法,也可以借助表格、方程等工具,使一些看似复杂的问题迎刃而解。

NOIP2011-1. 每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时,它才是有效的。例如,0000000、01010011都是有效的序列号,而11111110不是。那么,有效的序列号共有______个。

NOIP2011-2. 定义字符串的基本操作为: 删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串A变成字符串B的最少操作步数,称为字符串A到字符串B的编辑距离。字符串“ ABCDEFG ”到字符串“BADECG ”的编辑距离为_______。

NOIP2012-1. 如果平面上任取n 个整点(横纵坐标都是整数) ,其中一定存在两个点,它们连线的中点也是整点,那么n至少是_____。

NOIP2012-2. 在NOI期间,主办单位为了欢迎来自全国各地的选手,举行了盛大的晚宴。在第十八桌,有5名大陆选手和5名港澳选手共同进膳。为了增进交流,他们决定相隔就坐,即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么,这一桌共有_____种不同的就坐方案。注意:如果在两个方案中,每个选手左边相邻的选手均相同,则视为同一个方案。

NOIP2013-1. 7 个同学围坐一圈,要选2 个不相邻的作为代表,有_____种不同的选法。

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 = _____。

有关全国NOIP青少年信息学奥赛试题分享_www.cnitedu.cn

NOIP2014-1. 把M 个同样的球放到N 个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(用K 表示)。例如:M = 7,N = 3 时,K = 8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。问:M = 8,N = 5 时,K = _____。

NOIP2014-2. 如图所示,图中每条边上的数字表示该边的长度,则从A 到E 的最短距离是____。

有关全国NOIP青少年信息学奥赛试题分享_www.cnitedu.cn

NOIP2015-1. 重新排列 1234 使得每一个数字都不在原来的位置上,一共有_____种排法。

NOIP2015-2.一棵结点数为 2015 的二叉树最多有_____个叶子结点。

NOIP2016-1. 从一个 4×4 的棋盘(不可旋转)中选取不在同一行也不在同一列上的两个方格,共有______种方法。

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) = 128

NOIP2011-2.编辑距离问题。

先创建一个8×9(BADECG长度为6,ABCDEFG长度为7,各加2)的表如下:

1、在第一行第一列分别填上两个字符串

2、  在第二行第二列分别填上序列号

3、  从第三行第三列这一格开始计算填充。行列字符相等,则填左上角的数字;行列字符不等,在“左上角数字+1、左方数字+1、上方数字+1”中取最小值填充

4、  取最右下角的值,得编辑距离为3。

有关全国NOIP青少年信息学奥赛试题分享_www.cnitedu.cn

NOIP2012-1. 鸽巢原理问题。

同一直线上三个点的坐标:(x1,y1)、(x2,y2)和中点((x1+x2)/2, (y1+y2)/2)。

如果三个点都是整数,必须而且只须x1与x2,y1与y2的奇偶性相同。
平面上的整点只有四类:(奇数,奇数),(偶数,偶数),(奇数,偶数),(偶数,奇数),
根据鸽巢原理,在平面上任取五个整点,那么至少有两个整点属于一类,它们连线的中点就必是整点。所以n至少是5。

NOIP2012-2. 圆桌排列问题。

以3人为例,直线排列方案:A(3,3)=3!=6,分别是:123,132,213,231,312,321,如果是圆桌排列,则:123,231,312是重复方案,132,213,321是重复方案,实际有效方案为:3!/3=2。

本题中,大陆选手先排列,则有A(5,5)=5!;港澳选手再排列,共有5!*5!;再排除圆桌重复排列,则有:5!*5!/5=2880

NOIP2013-1. 乘法原理问题。

先选1个同学出来,7种选法;再选第2个同学出来,4种选法。所以,共有7×4÷2=14种选法。注意:去除重复部分(如第1次选a,第2次选b与第1次选b,第2次选a一样)

NOIP2013-2. 方程求解问题。

求解得出S1=0,S2=1,S3=1,S4=1。

NOIP2014-1. 排列组合问题。

设K=f(m,n)为m个球,n个袋子的放法数目,可以分成两类:含有0的方案数,不含有0的方案数。

当m=0,或n=1时,f(m,n)=1;当m<n时,f(m,n)=f(m,m),当m>n时,则有:

1、含有0的方案数,即有至少一个袋子空着,即相当于 f(m,n)=f(m,n-1)

2、不含有0的方案数,即全部袋子都有球,那么先从m个球中抽取出n个出来,各个袋子分一个,考虑剩下的m-n个球放到n个袋子里的放法,即 f(m,n)=f(m-n,n).

而总的放法数目等于两者的和,即f(m,n)=f(m,n-1)+f(m-n,n)

所以:f(8,5)=f(8,4)+f(3,5)=18

NOIP2014-2. 最短路径问题。

我们可以用倒推的方法,求A到E的最短距离。用k来表示阶段。

k=4,有d4(F,E)来表示F到E的距离。f4(F)=6

k=3,用d3(C,E)、d3(C,F)、d3(D,F)、d3(D,E)来表示有四条路。

f3(C)=min{d3(C,E),d3(C,F)}=min{8,1+6}=7

f3(D)=min{d3(D,F),d3(D,E)}=min{2+6,4}=4

k=2,有f2(B)=min{d2(B,C),d2(B,D)}=min{1+7,7+4}=8;

f2(G)=min{d2(G,C),d2(G,D)}=min{2+7,4+4}=8

k=1,有f1(A)=min{d1(A,B),d1(A,G),d1(A,F)}=min{3+8,4+8,6+6}=11

NOIP2015-1. 错位排列问题。

Dn=n!(1-1/1!+1/2!-1/3!+…),D4=24×(1/2-1/6+1/24)=9

NOIP2015-2. 完全二叉树问题。

二叉树的叶子结点(N0) = 度为2的结点数(N2)+1。二叉树叶子节点最多,即度为2的结点数最多,这就是完全二叉树,2015个结点的完全二叉树。

2015 = N0 + N1+ N2,当完全二叉树度为1的结点数N1 = 0时,N0 = 1008。

NOIP2016-1. 乘法原理问题。

第一个方格的选取方法:4*4=16;由于要求不同行不同列,则第二个方格的选取方法:3*3=9

根据乘法原理,且两个方格无前后排序,去除重复,则有16*9/2=72

NOIP2016-2. 完全二叉树问题。

当度为2的结点数(N2)=0时,叶子结点最少。则叶子结点(N0)=度为2的结点数(N2)+1=1;

当为完全二叉树时,二叉树的高度值最小。设二叉树得高度值为i,则共i层的完全二叉树最多有2^i-1个节点。则有:2016<=2^i-1,所以,i>=11,即最小高度值为11。


推荐内容