当前位置:首页 >> 学科竞赛 >>

历届问题求解试题(NOIP1995至NOIP2015)


1995NOIP01 普及组............................................................................................................... 2 1996NOIP02 普及组.................................................

.............................................................. 2 1997NOIP03 普及组............................................................................................................... 2 1998NOIP04 普及组............................................................................................................... 2 1999NOIP05 普及组............................................................................................................... 2 2000NOIP06 普及组............................................................................................................... 3 2001NOIP07 普及组............................................................................................................... 3 2002NOIP08 普及组............................................................................................................... 4 2003NOIP09 普及组............................................................................................................... 4 2004NOIP10 普及组............................................................................................................... 4 2005NOIP11 普及组............................................................................................................... 4 2006NOIP12 普及组............................................................................................................... 5 2007NOIP13 普及组............................................................................................................... 5 2008NOIP14 普及组............................................................................................................... 6 2009NOIP15 普及组............................................................................................................... 6 2010NOIP16 普及组............................................................................................................... 7 2011NOIP17 普及组............................................................................................................... 7 2012NOIP18 普及组............................................................................................................... 8 2013NOIP19 普及组............................................................................................................... 8 2014NOIP20 普及组............................................................................................................... 8 2015NOIP21 普及组............................................................................................................... 9 1995NOIP01 提高组............................................................................................................... 9 1996NOIP02 提高组............................................................................................................... 9 1997NOIP03 提高组............................................................................................................... 9 1998NOIP04 提高组............................................................................................................... 9 1999NOIP05 提高组............................................................................................................. 10 2000NOIP06 提高组............................................................................................................. 10 2001NOIP07 提高组............................................................................................................. 10 2002NOIP08 提高组............................................................................................................. 10 2003NOIP09 提高组............................................................................................................. 10 2004NOIP10 提高组............................................................................................................. 11 2005NOIP11 提高组............................................................................................................. 11 2006NOIP12 提高组............................................................................................................. 11 2007NOIP13 提高组............................................................................................................. 12 2008NOIP14 提高组............................................................................................................. 12 2009NOIP15 提高组............................................................................................................. 12 2010NOIP16 提高组............................................................................................................. 13 2011NOIP17 提高组............................................................................................................. 13 2012NOIP18 提高组............................................................................................................. 14 2013NOIP19 提高组............................................................................................................. 14 2014NOIP20 提高组............................................................................................................. 15 2015NOIP21 提高组............................................................................................................. 15

1995NOIP01 普及组 1996NOIP02 普及组 1997NOIP03 普及组 1998NOIP04 普及组
1. 已知一个数列 U1, U2, U3, …, UN, … 往往可以找到一个最小的 K 值和 K 个数 a1, a2, …, ak 使得数列从某项开始都满足: UN+K=a1UN+K-1+a2UN+K-2+……+akUN (A) 例如对斐波拉契数列 1,1,2,3,5,…可以发现:当 K=2,a1 =1,a2 =1 时,从第 3 项 起(即 N>=1)都满足 U n+2 =Un+1+Un 。试对数列 12,22,32,…,n2,…求 K 和 a1,a2, …,aK 使得(A)式成立。 {7%}

2.某班有 50 名学生,每位学生发一张调查卡,上写 a,b,c 三本书的书名,将读过的书 打?,结果统计数字如下: 只读 a 者 8 人;只读 b 者 4 人;只读 c 者 3 人;全部读过 的有 2 人;读过 a,b 两本书的有 4 人;读过 a,c 两本书的有 2 人;读过 b,c 两本书 的有 3 人;{6%} (1)读过 a 的人数是 (2)一本书也没有读过的人数是

3.任给自然数 n,k, 1≤K≤9 ,按如下计算步骤求序列 XJXJ-1……X0 的步骤:{8%} (1) j=0 (2) 如果 N>=K 则转第 3 步,否则转第 7 步 (3) Xj = N MOD K (4) N =N DIV K (5) j=j+1 (6) 回第 2 步 (7) Xj = N (8) 结束 试求当: N=1998, K=3 时,XJXJ-1……X0 之值。 {div 表示整数除法,结果取整数; mod 表示整除取余数}

1999NOIP05 普及组
1、在磁盘的目录结构中,我们将与某个子目录有关联的目录数称为度。例如下图

该图表达了 A 盘的目录结构:D1,Dll,…,D2 均表示子目录的名字。在这里,根目录的 度为 2,D1 子目录的度为 3,D11 子目录的度为 4,D12,D2,D111,D112,D113 的度均为 1。 不考虑子目录的名字,则可简单的图示为如下所示的树结构:

若知道一个磁盘的目录结构中,度为 2 的子目录有 2 个,度为 3 的子目录有 1 个,度为 4 的子目录有 3 个。 试问:度为 1 的子目录有几个? 2、公式推导(10 分) 根据 Nocomachns 定理,任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和。 例如: 13= 1 23= 3+ 5 33= 7+ 9 +11 43= 13+15+17+19 在这里,若将每一个式中的最小奇数称为 X,那么当给出 n 之后,请写出 X 与 n 之间的关 系表达式:

2000NOIP06 普及组
1.已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 2.有 2×n 的一个长方形方格,用一个 1×2 的骨牌铺满方格。例如 n=3 时,为 2×3 方格。 此时用一个 1×2 的骨牌铺满方格,共有 3 种铺法:

试对给出的任意一个 n(n>0),求出铺法总数的递推公式。

2001NOIP07 普及组
1、在 a,b,c,d,e,f 六件物品中,按下面的条件能选出的物品是: _____ ⑴a,b 两样至少有一样 ⑵a,d 不能同时取 ⑶a,e,f 中必须有 2 样 ⑷b,c 要么都选,要么都不选 ⑸c,d 两样中选一样 ⑹若 d 不选,则 e 也不选

2、平面上有三条平行线,每条直线上分别有 7,5,6 个点,且不同直线上三个点 都不在同一直线上。 问用这些点为顶点,能组成多少个不同三角形? ( )

2002NOIP08 普及组
1. 如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每个车厢可以向 左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3 号车厢,请写出所有 可能的到达出口的车厢排列总数(不必给出每种排列)。 出口← ← 1 2 3 4 5 S↓ 2.将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排法: 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法)

2003NOIP09 普及组
1. 现在市场上有一款汽车 A 很热销, 售价是 2 万美元。 汽车 A 每加仑汽油可以行驶 20 英里。 普通汽车每年大约行驶 12000 英里。油价是每加仑 1 美元。不久我公司就要推出新款节油汽车 B,汽车 B 每加仑汽油可以行驶 30 英里。现在我们要为 B 制定价格(它的价格略高于 A):我们 预计如果用户能够在两年内通过节省油钱把 B 高出 A 的价钱弥补回来,则他们就会购买 B,否 则就不会购买 B。那么 B 的最高价格应为 万美元。

2.无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小于 3,则 G 至少有 个顶点。

2004NOIP10 普及组
1、一个家具公司生产桌子和椅子。现在有 113 个单位的木材。每张桌子要使用 20 个单位的木材,售价是 30 元;每张椅子要使用 16 个单位的木材,售价是 20 元。 使用已有的木材生产桌椅(不一定要把木材用光) ,最多可以卖 元钱。

2、75 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已 知其中 20 人这三种东西都玩过,55 人至少玩过其中的两种。若每样乘坐一次的费 用是 5 元,游乐场总共收入 700,可知有 名儿童没有玩过其中任何一种。

2005NOIP11 普及组
1. 将数组{32, 74, 25, 53, 28, 43, 86, 47} 中的元素按从小到大的顺序排列,

每次可以交换任 意两个元素,最少需要交换次。 2. 有 3 个课外小组:物理组,化学组和生物组。今有张、王、李、赵、陈 5 名同 学,已知 张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员。如果 要在 3 个小组中分别选出 3 位组长,一位同学最多只能担任一个小组的组长,共有种 选择方案。

2006NOIP12 普及组
1. (寻找假币) 现有 80 枚硬币,其中有一枚是假币,其重量稍轻,所有真币的 重量都相同,如果使 用不带砝码的天平称重,最少需要称几次,就可以找出假币? 你 还 要 指 出 第 1 次 的 称 重 方 法 。 请 写 出 你 的 结 果 : _________________________________________________。

2. (取石子游戏)

现有 5 堆石子,石子数依次为 3,5,7,19,50,甲乙两人

轮流从任一堆中任取(每次只能取自一堆,不能不取), 取最后一颗石子的一方获 胜。 甲先取, 问甲有没有获胜策略 (即无论 乙怎样取, 甲只要不失误, 都能获胜) ? 如果有,甲第一步应该在哪一堆里取多少?请写出你的结果: _________________________________________________。

2007NOIP13 普及组

1、 (子集划分)将 n 个数(1,2,…,n)划分成 r 个子集。每个数都恰好属于一 个子集,任何两个不同的子集没有共同的数,也没有空集。将不同划分方法的总数 记为 S(n,r) 。例如, S(4,2)=7 ,这 7 种不同的划分方法依次为 {(1),(234)} , {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)}, {(14),(23)}。 当 n=6,r=3 时,S(6,3)=______________。 (提示:先固定一个数,对于其余的 5 个数考虑 S(5,3)与 S(5,2),再分这两种情 况对原固定的数进行分析。 ) 2、 (最短路线)某城市的街道是一个很规整的矩形网络(见下图) ,有 7 条南北向 的纵街,5 条东西向的横街。现要从西南角的 A 走到东北角的 B,最短的走法共有

多少种?___________
B

A

2008NOIP14 普及组
1. 书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的,C 和 D 是黑皮的。 把这 4 本书摆在书架上,满足所有黑皮的书都排在一起的摆法有_____种。满足 A 必须比 C 靠左,所有红皮的书要摆放在一起,所有黑皮的书要摆放在一起,共有 ______种摆法。 2.有 6 个城市,任何两个城市之间都有一条道路连接,6 个城市两两之间的距离如 下表所示,则城市 1 到城市 6 的最短距离为_____________。
城市 1 城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 0 2 3 1 12 15 城市 2 2 0 2 5 3 12 城市 3 3 2 0 3 6 5 城市 4 1 5 3 0 7 9 城市 5 12 3 6 7 0 2 城市 6 15 12 5 9 2 0

2009NOIP15 普及组

1 .小陈现有 2 个任务 A, B 要完成,每个任务分别有若干步骤如下: A=a1->a2->a3, B=b1->b2->b3->b4->b5。在任何时候,小陈只能专心做某个任务的一个步骤。但是如果愿意,他 可以在做完手中任务的当前步骤后, 切换至另一个任务, 从上次此任务第一个未做的步骤继续。 每 个 任 务 的 步 骤 顺 序 不 能 打 乱 , 例 如 … … a2->b2->a3->b3 … … 是 合 法 的 , 而 … … a2->b3->a3->b2……是不合法的。小陈从 B 任务的 b1 步骤开始做,当恰做完某个任务的某个步 骤后,就停工回家吃饭了。当他回来时,只记得自己已经完成了整个任务 A,其他的都忘了。 试计算小陈饭前已做的可能的任务步骤序列共有 种。 2.有如下的一段程序:
1. 2. a:=1; b:=a;

3. 4. 5. 6. 7.

d:=-a; e:=a+d; c:=2*d; f:=b+e-d; g:=a*f+c;

现在要把这段程序分配到若干台(数量充足)用电缆连接的 PC 上做并行执行。每台 PC 执行其 中的某几个语句,并可随时通过电缆与其他 PC 通讯,交换一些中间结果。假设每台 PC 每单位 时间可以执行一个语句, 且通讯花费的时间不计。 则这段程序最快可以在 单位时间内 执行完毕。注意:任意中间结果只有在某台 PC 上已经得到,才可以被其他 PC 引用。例如若语 句 4 和 6 被分别分配到两台 PC 上执行,则因为语句 6 需要引用语句 4 的计算结果,语句 6 必 须在语句 4 之后执行。

2010NOIP16 普及组
1. LZW 编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码词 典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并 用于后继信息的编码。 举例说明,考虑一个待编码的信息串: “xyx yy yy xyx” 。初始词典只有 3 个条目,第一个为 x, 编码为 1:第二个为 y,编码为 2:第三个为空格,编码为 3:于是串“xyx”的编码为 1-2-1(其 中-为编码分隔符) ,加上后面的一个空格就是 1-2-1-3。但由于有了一个空格,我们就知道前面 的“xyx”是一个单词,而由于该单词没有在词典中,我们就可以自适应的把这个词条添加到词 典里,编码为 4,然后按照新的词典对后继信息进行编码,以此类推。于是,最后得到编码: 1-2-1-3-2-2-3-5-3-4。 现在已知初始词典的 3 个条目如上述,则信息串“yyxy xx yyxy xyx xx xyx”的编码是:

2. 队列快照是指在某一时刻队列中的元素组成的有序序列。例如,当元素 1、2、3 入队,元素 1 出队后,此刻的队列快照是“2 3” 。当元素 2、3 也出队后,队列快照是“” ,即为空。现有 3 个正整数元素依次入队、出队。已知它们的和为 8,则共有 种可能的不同的队列 快照(不同的队列的相同快照只计一次) 。例如, “5 1 ” 、 “4 2 2” 、 “”都是可能的队列快照;而 “7”不是可能的队列快照,因为剩下的 2 个正整数的和不可能是 1。

2011NOIP17 普及组

1、每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时,它才是有 效的。例如,00000000、01010011 都是有效的序列号,而 11111110 不是。那么,有效 的序列号共有________个。 2、定义字符串的基本操作为:删除一个字符、插入一个字符和将一个字符修改成另一个字符 这三种操作。将字符串 A 变成字符串 B 的最少操作步数,称为字符串 A 到字符串 B 的编辑 距离。字符串"ABCDEFG"到字符串"BADECG"的编辑距离为________。

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

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

2013NOIP19 普及组
1、7 个同学围坐一圈,要选 2 个不相邻的作为代表,有___________种不同的选法。 2、某系统自称使用了一种防窃听的方式验证用户密码。密码是n 个数s1, s2, …, sn,均为0 或1。 该系统每次随机生成n 个数a1, a2, …, an, 均为0 或1, 请用户回答(s1a1 + s2a2 + … + snan)除以2 的余数。 如果多次的回答总是正确, 即认为掌握密码。 该系统认为, 即使 问 答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。 然而,事与愿违。例如,当n = 4 时,有人窃听了以下5 次问答: 系统生成的n 个数 问答编号 掌握密码的用户的回答 a1 a2 a3 a4 1 2 3 4 1 0 0 1 1 0 1 1 0
, s2 =

0 1 1 1 0

0 1 0 0 0 , s3 =
, s4 =

1 0 0 0 0


5 1 就破解出了密码s1 =

2014NOIP20 普及组
1、把 M 个同样的球放到 N 个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放 置方法?(用 K 表示) 。 例如:M=7,N=3 时,K=8;在这里认为(5,1,1, )和(1,5,1)是同一种放置方法。 问:M=8,N=5 时,K=____________。 2、如图所示,图中每条边上的数字表示该边的长度,则从 A 到 E 的最短距离是________。

2015NOIP21 普及组
1、 重新排列 1234 使得每一个数字都不在原来的位置上,一共有______种排法。 2、 一棵结点数为 2015 的二叉树最多有________个叶子结点。

1995NOIP01 提高组 1996NOIP02 提高组 1997NOIP03 提高组 1998NOIP04 提高组
1.已知一个数列 U1,U2,U3,…,UN,… 往往可以找到一个最小的 K 值和 K 个数 a1,a2,…,an 使得数列从某项开始都满足: UN+K=a1UN+K-1+a2UN+K-2+……+akUN (A) 例如对斐波拉契数列 1,1,2,3,5,…可以发现:当 K=2,a1 =1,a2 =1 时,从第 3 项起(即 N>=1)都满足 U n+2 =Un+1+Un 。试对数列 13,23,33,…,n3,…求 K 和 a1,a2, …,aK 使得(A)式成立。 {8%} 2.给出一棵二叉树的中序遍历:DBGEACHFI 与后序遍历:DGEBHIFCA 画出此二叉树。 {8%} 3.用邻接矩阵表示下面的无向图: {6%}

1999NOIP05 提高组
将 Ln 定义为求在一个平面中用 n 条直线所能确定的最大区域数目。 例如: 当 n=1 时, L1=2, 进一步考虑,用 n 条折成角的直线(角度任意) ,放在平面上,能确定的最大区域数目 Zn 是多 少?例如:当 n=1 时,Z1=2(如下图所示) 当给出 n 后,请写出以下的表达式: 1 Ln = ______________ 2 Zn = _______________

2000NOIP06 提高组
1.已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 2.设有一个共有 n 级的楼梯,某人每步可走 1 级,也可走 2 级,也可走 3 级,用递推公式给出 某人从底层开始走完全部楼梯的走法。例如:当 n=3 时,共有 4 种走法,即 1+1+1,1+2,2+1, 3。

2001NOIP07 提高组
1.已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为: CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为: 2.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点 都不在同一条直线上。问用这些点为顶点,能组成多少个不同四边形?

2002NOIP08 提高组
1. 在书架上放有编号为 1 ,2 , . . . ,n 的 n 本书。现将 n 本书全部取下然后再放回去,当放 回去时要求每本书都不能放在原来的位置上。例如:n = 3 时: 原来位置为:1 2 3 放回去时只能为:3 1 2 或 2 3 1 这两种 问题:求当 n = 5 时满足以上条件的放法共有多少种?(不用列出每种放法) 2. 设有一棵 k 叉树,其中只有度为 0 和 k 两种结点,设 n 0 ,n k ,分别表示度为 0 和度为 k 的结点个数,试求出 n 0 和 n k 之间的关系(n 0 = 数学表达式,数学表达式仅含 n k 、k 和 数字) 。

2003NOIP09 提高组
1. 无向图 G 有 16 条边, 有 3 个 4 度顶点、 4 个 3 度顶点, 其余顶点的度均小于 3, 则 G 至少_______ 个顶点。

2. 某年级学生共选修 6 门课程,期末考试前,必须提前将这 6 门课程考完,每人每天只在下午 至多考一门课程,设 6 门课程为 C1,C2,C3,C4,C5,C6,S(Ci)为学习 Ci 的学生集合。已知 S(Ci)∩S(C6)≠ф,i=1,2,...,5,S(Ci)∩S(Ci+1)≠ф,i=1,2,3,4, S(C5)∩S(C1)≠ф, 问至少安排_____天才能考完这 6 门课程。

2004NOIP10 提高组
1. 75 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其中 20 人这三种东西都玩过,55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元,游乐场 总共收入 700,可知有 名儿童没有玩过其中任何一种。 已知 a, b, c, d, e, f, g 七个人中,a 会讲英语;b 会讲英语和汉语;c 会讲英语、意大利语和 俄语;d 会讲汉语和日语;e 会讲意大利语和德语;f 会讲俄语、日语和法语;g 会讲德语 和法语。 能否将他们的座位安排在圆桌旁, 使得每个人都能与他身边的人交谈?如果可以, 请以“a b”开头写出你的安排方案: 。

2.

2005NOIP11 提高组
1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列, 每次可以交换任意两个元素,最少需要交换 次。 2. 取火柴游戏的规则如下:一堆火柴有 N 根,A、B 两人轮流取出。每人每次可以 取 1 根或 2 根,最先没有火柴可取的人为败方,另一方为胜方。如果先取者有必 胜策略则记为 1,先取者没有必胜策略记为 0。当 N 分别为 100,200,300,400, 500 时, 先取者有无必胜策略的标记顺序为 (回答应为一个由 0 和 /或 1 组成的字符串) 。

2006NOIP12 提高组
1.将 2006 个人分成若干不相交的子集,每个子集至少有 3 个人,并且: (1)在每个子集中,没有人认识该子集的所有人。 (2)同一子集的任何 3 个人中,至少有 2 个人互不认识。 (3)对同一子集中任何 2 个不相识的人,在该子集中恰好只有 1 个人认识这两个人。 则满 足上述条件的子集最多能有 个? 2.将边长为 n 的正三角形每边 n 等分,过每个分点分别做 另外两边的平行线,得到若干个正三角形, 我们称为小三角 形。 正三角形的一条通路是一条连续的折线, 起点是最上面的 一个小三角形,终点是最 下面一行位于中间的小三角形。在 通路中, 只允许由一个小三角形走到另一个与其有公共边的且 位于同 一行或下一行的小三角形,并且每个小三角形不能经 过两次或两次以上(图中是 n=5 时一条通路的例 子) 。设 n=10,则该正三角形的不同的通路的总数为_ __。

2007NOIP13 提高组
1.给定 n 个有标号的球,标号依次为 1,2,…,n。将这 n 个球放入 r 个相同的盒 子里,不允许有空盒,其不同放置方法的总数记为 S(n,r)。例如,S(4,2)=7,这 7 种不同的放置方法依次为{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}。当 n=7,r=4 时, S(7,4)= 。 2.N 个人在操场里围成一圈,将这 N 个人按顺时针方向从 1 到 N 编号,然后从第一 个人起,每隔一个人让下一个人离开操场,显然,第一轮过后,具有偶数编号的人 都离开了操场。依次做下去,直到操场只剩下一个人,记这个人的编号为 J(N),例 如,J(5)=3,J(10)=5,等等。则 J(400)= 。 (提 示:对 N=2m+r 进行分析,其中 0≤r<2m)。

2008NOIP14 提高组

1.有 6 个城市,任何两个城市之间都有一条道路连接,6 个城市两两之间的距离如下表 所示,则城市 1 到城市 6 的最短距离为_____________。

城市1 城市1 城市2 城市3 城市4 城市5 城市6 0 2 3 1 12 15

城市2 2 0 2 5 3 12

城市3 3 2 0 3 6 5

城市4 1 5 3 0 7 9

城市5 12 3 6 7 0 2

城市6 15 12 5 9 2 0

2.书架上有 21 本书,编号从 1 到 21,从其中选 4 本,其中每两本的编号都不相邻的选 法一共有______种。

2009NOIP15 提高组

1.拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列,使得图中任意一对顶 点 u 和 v, 若<u, v> ∈E(G), 则 u 在线性序列中出现在 v 之前, 这样的线性序列成为拓扑序列。 如下的有向无环图,对其顶点做拓扑排序,则所有可能的拓扑序列的个数为 。

2

5 6

8

1

4 7 9

3

2.某个国家的钱币面值有 1, 7, 72, 73 共计四种,如果要用现金付清 10015 元的货物,假设 买卖双方各种钱币的数量无限且允许找零,那么交易过程中至少需要流通 张钱币。

2010NOIP16 提高组

1.LZW 编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础 构造 元素的编码词典,如果在编码的过程中遇到一个新的词条,则该词条及一个 新的 编码会被追加到词典中,并用于后继信息的编码。 举例说明,考虑一个待编码的信息串:“xyx yy yy xyx”。初始 词典 只有 3 个条目, 第一个为 x,编码为 1; 第二个为 y, 编码为 2; 第三个为空格, 编码 为 3;于是串“xyx”的编码为 1-2-1(其中-为编码分隔符),加上后面的一 个空 格就是 1-2-1-3。但由于有了一个空格,我们就知道前面的“xyx”是一个单词,而由于该单词没有 在词典中,我们就可以自适应的把这个词条添加到词典里,编码为 4,然后按照新的词典对后继信 息进行编码,以此类推。于是,最后得到编码:1-2-1-3-2-2-3-5-3-4。 我们可以看到,信息被压缩了。压缩好的信息传递到接受方,接收方也只要根据基础词典 就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的 3 个条目如 上述,接收端收到的编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6,则解码后的信息串 是”____________”。 2.无向图 G 有 7 个顶点,若不存在由奇数条边构成的简单回路,则它至多有__________条边。 3.记 T 为一队列,初始时为空,现有 n 个总和不超过 32 的正整数依次入列。如果无论这些数具体为 何值,都能找到一种出队的方式,使得存在某个时刻队列 T 中的数之和恰好为 9,那么 n 的最小值 是___________。

2011NOIP17 提高组
1.平面图是可以画在在平面上,且它的边仅在顶点上才能相交的简单 无向图。4 个顶点的平面图至多有 6 条边,如右图所示。那么,5 个顶 点的平面图至多有______条边。 2. 定义一种字符串操作, 一次可以将其中一个元素移到任意位置。 举例说明, 对于字符串”BcA”, 可以将 A 移到 B 之前, 变成字符串”ABC”。 如果要将字符串”DACHEBGIF”变成”ABCDEFGHI”, 最少需要________次操作。

2012NOIP18 提高组
1、 本题中,我们约定布尔表达式只能包含 p, q, r 三个布尔变量,以及 “与” (∧) 、 “或”(∨) 、“非”(? )
三种布尔运算。如果无论 p, q, r 如何取值,两个布尔表达式的值总是相同,则称它们等价。例如, (p∨ q)∨r 和 p∨(q∨r)等价, p∨? p 和 q∨? q 也等价;而 p∨q 和 p∧q 不等价。那么,两两不等价的 布尔表达式最多有_________个。

2、 对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如图 1 有 5 个不同的独 立集(1 个双点集合,3 个单点集合,1 个空集) ,图 2 有 14 个不同的独立集,那么,图 3 有_____________个不同的独立集。

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

1.

0 1 1 1 0

0 1 0 0 0 , s3 =
, s4 =

1 0 0 0 0


5 1 就破解出了密码s1 = 2.

现有一只青蛙, 初始时在n 号荷叶上。 当它某一时刻在k 号荷叶上时, 下一时刻将等概 率地随机跳到1, 2, …, k 号荷叶之一上, 直至跳到1 号荷叶为止。 当n = 2 时, 平均一共 跳 2 次;当n = 3 时,平均一共跳2.5 次。则当n = 5 时,平均一共跳 1 2 3 4 次。 5

2014NOIP20 提高组
1、 由数字 1,1,2,4,8,8 所组成的不同的四位数的个数是: 2、 如图所示,图中每条边上的数字表示该边的长度,则从 A 到 E 的最短距离是________。

2015NOIP21 提高组
1、 在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、5、6 三个数整除的数有______个。 2、 结点为 5 的不同形态的二叉树一共有_______种。 (结点数为 2 的二叉树一共有 2 种:一 种是根结点和左儿子,另一种是根结点和左儿子)


相关文章:
历年提高组复赛题目(1995-2015)
全国信息学奥林匹克联赛(NOIP2015)复赛提高组 day1 1995 NOI’95 “同创杯”...分区联赛复赛试题 提高组 提高组 [问题描述] 题一 一元三次方程求解 (20 分...
NOIP2015普及组复赛试题解题报告word版第一二题满分程序
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 NOIP2015 普及组复赛试题解题报告 word 版 第一二题满分程序 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组一...
NOIP2015普及组复赛试题
NOIP2015普及组复赛试题_学科竞赛_初中教育_教育专区...CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 CCF ...【问题描述】 阿明是一名推销员, 他奉命到螺丝街推销...
历届NOIP问题求解及答案(好)
历届问题求解 NOIP1998 普及 (20% 二、问题求解: 20%) 问题求解: 20%) ( 1.已知一个数列 U1,U2,U3,…,UN,… 往往可以找 到一个最小的 K 值和 K ...
noip2015普及组题解最终
noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015 年 11 月 11 日 本次试题前2题比较简单,34题容易拿到部分分,但满分有难度 1. 金币 (coin....
NOIP2015提高组初赛C++试题_图文
NOIP2015提高组初赛C++试题_学科竞赛_高中教育_教育专区。 文档贡献者 我昰岽人...2009NOIP 提高组初赛试题... 7页 5下载券 NOIP2015普及组C++试题 暂无评价 ...
NOIP2015普及组初赛试题及答案(Pascal)
B.笔 C.身份证 D.准考证 A.鼠标 二. 问题求解(共 2 题,每空 5 分,...2004NOIP初赛试题及答案... 10页 1下载券 NOIP2015提高组初赛PASC... 8页...
Noip2015复赛备考试题安排
Noip2015 复赛备考试题 day1 day2 1035 Hanoi 双塔问题 1120 Factorials 阶乘 ...(动态规划) day26 传球游戏(noip2008p 动态规划)选课(树形 dp) day25 usaco...
NOIP2015提高组Pascal试题及参考答案
NOIP2015提高组Pascal试题及参考答案_其它考试_资格考试/认证_教育专区。第二十...树 D. 连通图 三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部...
2015noip第二十一届普及组初赛试题
2015noip第二十一届普及组初赛试题_学科竞赛_高中教育_教育专区。第二十一届...A.鼠标 B.笔 C.身份证 D.准考证 二、问题求解(共 2 题 ,每题 5 分,...
更多相关标签:
noip历届试题 | noip普及组初赛试题 | noip试题 | noip初赛试题 | noip普及组试题精选 | noip提高组初赛试题 | noip历年试题 | noip2016初赛试题 |