NOIP初赛试题提高组C语言.DOC

1、 初 赛 试 题 （ 提 高 组 语 言 ）第十届（2004）三问题求解（ 共 2 题，每题 5 分，共计 10 分 ）1.75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中 20 人这三种东西都玩过， 55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元，游乐场总共收入 700 ，可知有 名儿童没有玩过其中任何一种。分析与解：已知总人数为 75，总金额是 700，玩 3 项的人数是 20，花费的金额是 5*3*20=300，玩 2项的人数是 55-20=35，花费的金额是 5*2*35=350，剩余金额是 700-300-350=50，只能玩 50/5=10

2、 项次，即玩 1 项的人数是 10，所以玩 0 项的人数是：75-20-35-10=10总共 玩 3 项 玩 2 项 玩 1 项 玩 0 项人数 75 20 35 ？金额 700 300 350 02.已知 a, b, c, d, e, f, g 七个人中， a 会讲英语； b 会讲英语和汉语； c 会讲英语、意大利语和俄语； d 会讲汉语和日语； e 会讲意大利语和德语； f 会讲俄语、日语和法语； g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ ab ”开头写出你的安排方案： 。.a-b-d-f c-e-g-fg-e-c-f答： a b

3、d f g e c 第十一届（2005）三问题求解（请在空格处填上答案，每空 5 分，共计 10 分）1将数组32, 74, 25, 53, 28, 43, 86, 47中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换 次。32，74，25 ，53，28，43，86 ，47 25，74，32 ，53， 28，43，86 ，47 25，28，32 ，53， 74，43，86 ，47 25，28，32 ，43， 74，53，86 ，47 25，28，32 ，43， 47，53，86 ，74 25，28，32 ，43， 47，53，74 ，862取火柴游戏的规则如下：一堆火柴有

4、N 根，A、B 两人轮流取出。每人每次可以取 1 根或 2 根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为 1，先取者没有必胜策略记为 0。当 N 分别为 100，200，300，400，500 时，先取者有无必胜策略的标记顺序为 （回答应为一个由 0 和/或 1 组成的字符串）。分析与解：当火柴的根数为 3 或 3 的整数倍时，先取者没有必胜的策略；而当火柴的根数不为 3 的整数倍时，先取者有必胜的策略：取后使得剩余火柴的根数为 3 的整数倍。所以答案为 11011相似的游戏：A、B 两人轮流往同一储蓄罐存钱并记录每次存入的金额，每人每次可存入的金额为 1 元至 5

5、 元间的任一整数（包括 1 和 5），谁某次存完钱后使得储蓄罐里的总金额大于等于 100 即获胜利（获得储蓄罐里所有的存钱的奖励）。若让你参加该游戏并为第一个存钱者，你有必胜的策略吗？第十二届（2006）三问题求解（共 2 题，每题 5 分，共计 10 分）1将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。 则满足上述条件的子集最多能有_个？分析：要使子集数最多，每一子集的人数应最少

6、。每一子集的人数为 3，不符合要求，为 4 也不符合要求，为 5 可符合要求。2将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的例子） 。设 n=10，则该正三角形的不同的通路的总数为_。分析与解：如果 n=2，存在的不同的通路总数为 1如果 n=3，存在的不同的通路总数为 2=

7、1*2=2！如果 n=4，存在的不同的通路总数为 6=1*2*3=3！如果 n=5，存在的不同的通路总数为 24=1*2*3*4=4！如果 n=10，存在的不同的通路总数为 9！第十三届（2007）三问题求解（共 2 题，每题 5 分，共计 10 分） 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

8、)。当 n=7,r=4 时，S(7,4)= _。 分析与解：方法一：4 个盒子放 7 个球的情况依每个盒子所放球的个数不同可分为以下情形：4，1，1，1；共有 C（7， 4）=7*6*5*4/ （4*3*2*1）=35 种3，2，1，1；共有 C（7， 3）*C （4，2）=35*6=210 种2，2，2，1。共有 C（7， 2）*C （5，2）*C（3，2）/A（3，3）=21*10*3/6=105 种共计：35+210+105=350 种方法二：S(n,r)=S(n-1,r) r + S(n-1,r-1)因为，多一个球的放法：若空盒没有增多，则往 r 个盒子的任何一个盒子放入该球都是一种放

9、法。所以共有 S(n-1,r)r 种放法，若空盒有增加 1 个，则增加的球只能放在该盒，放法有 S(n-1,r-1)种。另：S(n,n)=1；S(n,1)=1 ，依 S(n,r)=S(n-1,r)r + S(n-1,r-1)填下表：r n 1 2 3 4 5 6 71 1 1 1 1 1 1 12 13 14 12N 个人在操场里围成一圈，将这 N 个人按顺时针方向从 1 到 N 编号，然后，从第一个人起，每 隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为 J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。

10、则 J(400)=_。 （提示：对 N=2m+r 进行分析，其中 0r E(G)，则 u 在线性序列中出现在 v 之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点作拓扑排序，则所有可能的拓扑序列的个数为 。321547689由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为 0 的顶点为止。(1) 选择一个入度为 0 的顶点并输出之；(2) 从网中删除此顶点及所有出边。循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。2某个国家的钱币面值有 1, 7, 72, 73 共计四种，如果要用现金付清 100

11、15 元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通 张钱币。（答案：1、432；2、35）第十六届（2010）三、 问题求解1. LZ W 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。举例说明，考虑一个待编码的信息串：“ xyx yy yy xyx ”。初始词典只有 3 个条目，第一个为 x, 编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3 ；于是串“xyx” 的编码为 1-2-1 （ 其中 - 为编码分隔符），

12、加上后面的一个空格就是 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 ，则解码后的信息串是:“ yyxy xx y

13、yxy xyx xx xyx ” 。2. 无向图 G 有 7 个顶点，若不存在奇数条边构成的简单回路，则它至多有 _12_ 条边 。3记 T 为一队列，初始时为空，现有 n 个总和不超过 32 的正整数依次入队。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列 T 中的数之和恰好为 9，那么 n 的最小值是_18_。本题可用抽屉原理求解。设 ai 为各正整数值，则 T 的队列顺序为 a1,a2,a3 an，设 bi为前 i 项数之和，则 b0=0，b1=a1 ，b2=a1+a2 ，b3=a1+a2+a3 。如队列 T 中的数之和恰好为 9，实际上即是找到某个 bj 和 b

14、i ，使得 bj-bi=9。由题意可知 bi 取值范围为1-32，现将这 32 个数构造为集合1,10, 2,11, , 8,17, 18,27, 19,28,23,32 ,24,25,26，这 17 个集合中的任一个集合不能包含两个或两个以上的 ，否则它们的差为 9。例如设 n=17 时，队列 T 为 11111111 10 11111111，即 b1=1, b2 =2, b8=8, b9 =18, b10=19, b11=20 b17=26,它们中没有任意两个数是在同一集合内的，所以不存在数之和恰好等于 9。故根据抽屉原理可得，当 n=18 时，至少存在两个在同一个集合，即它们的差为 9。

15、因此，答案为 n=18。第十七届（2011）1.平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4 个顶点的平面图至多有 6 跳边，如右图所示。那么，5 个顶点的平面图至多有 9 条边。2.定义一种字符串操作，一次可以将其中一个元素一道任意位置。距离说明，对于字符串“BCA”，可以将 A 移到 B 之前，变成字符串“ABC”，如果要将字符串”DACHEBGIF”变成”ABCDEFGHI”，最少需要 4 次操作。第十八届（2012）三、问题求解（共 2 题，每题 5 分，共计 10 分）1. 本题中，我们约定布尔表达式只能包含 p,q,r 三个布尔变量，以及 “与“（）、”或“（

16、v）、”非 “（ ）三种布尔运算。如果无论 p,q,r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(pVq)Vr 和 pV(qVr)等价，pVp 和qVq 也等价，而 pVq和 pq 不等价。那么，两两不等价的布尔表达式最多有_个。解答：对于 p、q、r 三个变量，每个变量可取 0,1 两种取值，共有 8 种组合。对于每种组合，代入表达式只有 0 和 1 两种答案。因此两两不等价的表达式只有 28=256 种。2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如图 1 有 5 个不同的独立集（1 个双点集合， 3 个单点集合，1 个空集），图 2 有 14 个不同

17、的独立集，那么，图 3 有_个不同的独立集。（答案：1、256；2、5536）解答：设 m(i)为以 i 个为根结点的树的独立集总个数f(i)为选 i 的总个数g(i)表示不选 i 的总个数，显然有m(i)=f(i)+g(i)对于二叉树，如果根节点选，则儿子节点不能选，有f(i)=g(left_childi)*g(right_childi) 如果根节点不选，则解与根节点无关，直接为左右儿子的解相乘，有 g(i)=m(left_childi)*m(right_childi) 具体用动态规划求解如下（计算的时候是从下往上算，这里设树的节点总数为根节点编号），显然该题就是求 m(17)，m(17)=f(17)+g(17)=1936+3600=5536f(17)=g(8)*g(8)=44*44=1936g(17)=m(8)*m(8)=60*60=3600m(8) =f(8)+g(8)=16+44=60f(8)=g(1)*g(6)=1*16=16g(8)=m(1)*m(6)=2*22=44m(6)=f(6)+g(6)=6+16=22