NOIP初赛试题提高组C语言

ＮＯＩＰ初赛试题（提高组Ｃ语言） 第十届（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项次，即玩1项的人数是10，所以玩0项的人数是：75-20-35-10=10 人数 金额 总共 75 700 玩3项 玩2项 玩1项 玩0项 20 300 35 350 ？ 0 2.已知 a, b, c, d, e, f, g 七个人中， a 会讲英语； b 会讲英语和汉语； c 会讲英语、意大利语和俄语； d 会讲汉语和日语； e 会讲意大利语和德语； f 会讲俄语、日语和法语； g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ a b ”开头写出你的安排方案： 。

a-b-d-f

.

c-e-g-f g-e-c-f

答： a b 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，86 2．取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为 （回答应为一个由0和/或1组成的字符串）。 分析与解：当火柴的根数为3或3的整数倍时，先取者没有必胜的策略；而当火柴的根数不为3的整数倍时，先取者有必胜的策略：取后使得剩余火柴的根数为3的整数倍。 所以答案为11011 相似的游戏：A、B两人轮流往同一储蓄罐存钱并记录每次存入的金额，每人每次可存入的金额为1元至5元间的任一整数（包括1和5），谁某次存完钱后使得储蓄罐里的总金额大于等于100即获胜利（获得储蓄罐里所有的存钱的奖励）。若让你参加该游戏并为第一个存钱者，你有必胜的策略吗？

第十二届（2006）

三．问题求解（共 2 题，每题 5 分，共计 10 分）

1．将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且： （1）在每个子集中，没有人认识该子集的所有人。

（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。

（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。 则满足上述条件的子集最多能有___________个？

分析：要使子集数最多，每一子集的人数应最少。每一子集的人数为3，不符合要求，为4也不符合要求，为5可符合要求。

2．将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的例子）。设 n=10，则该正三角形的不同的通路的总数为_____________。

分析与解：如果n=2，存在的不同的通路总数为1 如果n=3，存在的不同的通路总数为2=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)}。当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个盒子的任何一个盒子放入该球都是一种放法。所以共有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 1 1 2 1 1 3 1 1 4 1 1 5 1 6 1 7 1

2．N 个人在操场里围成一圈，将这N 个人按顺时针方向从1 到N 编号，然后，从第一个人起，每 隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。则J(400)=______________。

（提示：对N=2m+r 进行分析，其中0≤r<2m ）。

（答案：1、350；2、289）

第十四届（2008）

三．问题求解（ 共 2 题，每题 5 分，共计 10 分 ）

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

城市1 城市2 城市3 城市4 城市5 城市6 城市1 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本，其中每两本的编号都不相邻的选法一共有______种。

分析与解：若只有1-7号7本书，符合要求的取法只有1种，即取1357，取完后剩3本书，3本书间有2个空位，加上头尾2个空位，共4个空位。现把书放回去，满足要求的放法应只有1种，即为4个空位放4本书的组合数C（4，4）=1；

若有1-8号8本书，符合要求的取法有5种，即取1357、2468、1358、1468和1368，取完后剩4本书，4本书间有3个空位，加上头尾2个空位，共5个空位。现把各种取法的书放回去，满足要求的放法应该也为5种，即为5个空位放4本书的组合数C（5，4）=5；

所以，21本书，取走4本后剩余17本，17本书间有16个空位，加上头尾2个空位，共18个空位。往18个空位放4本书的组合数是C（18，4）=3060种。

十五届（2009）

三．问题求解（共2题，每空5分，共计10分）

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

5 6 1 4 7 9

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之； (2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

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

8 2 3 （答案：1、432；2、35）

第十六届（2010） 三、 问题求解

1. LZ W 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。

举例说明，考虑一个待编码的信息串：“ 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 ，则解码后的信息串是 :“ yyxy xx yyxy 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和bi ，使得 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。因此，答案为n=18。

第十七届（2011）

1.平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6跳边，如右图所示。那么，5个顶点的平面图至多有 9 条边。

2.定义一种字符串操作，一次可以将其中一个元素一道任意位置。距离说明，对于字符串“BCA”，可以将A移到B之前，变成字符串“ABC”，如果要将字符串”DACHEBGIF”变成”ABCDEFGHI”，最少需要 4 次操作。

第十八届（2012）

三、问题求解（共2题，每题5分，共计10分）

1. 本题中，我们约定布尔表达式只能包含p,q,r三个布尔变量，以及“与“（^）、”或“（v）、”非“（~）三种布尔运算。如果无论p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(pVq)Vr和pV(qVr)等价，pV~p和~qVq也等价，而pVq和p^q不等价。那么，两两不等价的布尔表达式最多有_______个。

解答：对于p、q、r三个变量，每个变量可取0,1两种取值，共有8种组合。 对于每种组合，代入表达式只有0和1两种答案。 因此两两不等价的表达式只有2^8=256种。

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

（答案：1、256；2、5536）

解答：

设 m(i)为以i个为根结点的树的独立集总个数

f(i)为选i的总个数

g(i)表示不选i的总个数，显然有 m(i)=f(i)+g(i)

对于二叉树，

如果根节点选，则儿子节点不能选，有 f(i)=g(left_child[i])*g(right_child[i])

如果根节点不选，则解与根节点无关，直接为左右儿子的解相乘，有 g(i)=m(left_child[i])*m(right_child[i])

具体用动态规划求解如下（计算的时候是从下往上算，这里设树的节点总数为根节点编号），显然该题就是求m(17)， m(17)=f(17)+g(17)=1936+3600=5536 f(17)=g(8)*g(8)=44*44=1936 g(17)=m(8)*m(8)=60*60=3600 m(8) =f(8)+g(8)=16+44=60

f(8)=g(1)*g(6)=1*16=16 g(8)=m(1)*m(6)=2*22=44 m(6)=f(6)+g(6)=6+16=22 f(6)=g(1)*g(4)=1*6=6 g(6)=m(1)*m(4)=2*8=16

m(4)=f(4)+g(4)=2+6=8 f(4)=g(1)*g(2)=1*2=2 g(4)=m(1)*m(2)=2*3=6 m(2)=f(2)+g(2)=3 f(2)=g(1)=1 g(2)=m(1)=2 m(1)=2 f(1)=1 g(1)=1

第十九届（2013）

1．某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, ?, sn，均为 0或 1。该系统每次随机生成 n 个数 a1, a2, ?, an，均为 0 或 1，请用户回答(s1a1 + s2a2 + ?+ snan)除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。例如，当 n = 4 时，有人窃听了以下 5 次问答：

系统生成的 n 个数 问答编号 掌握密码的用户的回答 a1 1 2 3 4 5 1 0 0 1 1 a2 1 0 1 1 0 a3 0 1 1 1 0 a4 0 1 0 0 0 1 0 0 0 0 就破解出了密码 s1 = ，s2 = ，s3 = ，s4 = 。 (0 1 1 1)

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

次。

（答案：1、0 1 1 1；2、37/12）

解：记青蛙从n号荷叶平均一共跳f(n)次会到1号荷叶上，则f(2)=2，f(3)=2.5，求f(5)。 f(2)=(1/2)*1+(1/2)*(1+f(2))?f(2)=2

f(3)=(1/3)*1+(1/3)*(1+f(2))+ (1/3)*(1+f(3))?f(3)=2.5 同理可得：

f(4)=(1/4)*1+(1/4)*(1+f(2))+ (1/4)* (1+f(3)) +(1/4)* (1+f(4))?f(4)=17/6 f(5)=(1/5)*1+(1/5)*(1+f(2))+ (1/5)* (1+f(3)) +(1/5)* (1+f(4)) +(1/5)* (1+f(5)) 解得：f(5)=37/12

2014（20届） 1．有数字1，1，2，4，8，8所组成的不同的四位数的个数是 。 2．如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是 。

（答案：1、102；2、15）

2015（21届）

1．在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数有 个。

2．结点数为5的不同形态的二叉树一共有 种。（结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。） （答案：1、1075；2、42）

2016提高组（22届） 1．一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有 种填涂方案。 2．某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。问最少要安排 个不同的考试时间段才能避免冲突？ 考试 通用技术 物理 化学 生物 历史 地理 政治 学生1 √ √ √ 学生2 √ √ √ 学生3 √ √ √ 学生4 √ √ 学生5 √ √ 学生6 √ √ √ （答案：1、55；2、3）

2017提高组（23届）

1．如图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0，至少需要3次操作。

2.如图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是4(2分)，最小代价的不同方案数是9(3分)。（只要有一条删除的边不同，就是不同的方案）

（答案：1．3；2．4、9）

1．某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…，sn,均为0或1。该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：

就破解出密码s1= ，s2= ，s3= ，s4= 。

分析： (s1*1+s2*1+s3*0+s4*0) mod 2=1 (s1*0+s2*0+s3*1+s4*1) mod 2=0 (s1*0+s2*1+s3*1+s4*0) mod 2=0 (s1*1+s2*1+s3*1+s4*0) mod 2=0 (s1*1+s2*0+s3*0+s4*0) mod 2=0

解得：s1= 0 ，s2= 1 ，s3= 1 ，s4= 1 。

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

分析与解：记青蛙从n号荷叶跳到1号荷叶上平均一共跳fn次，则： f1=1

f2=1*(1/2)+(1+f2)*(1/2)

f3=1*(1/3)+(1+f2)*(1/3)+(1+f3)*(1/3) ……

fn=1*(1/n)+(1+f2)*(1/n)+…+(1+fn)*(1/n) 即fn=(1+1+f2+…+1+fn)*(1/n)=(f1+f2+…+fn)/n

fn=1+(f1+f2+…+fn-1)/(n-1)

本文来源：https://www.bwwdw.com/article/hfi7.html