信息学选拔试题及答案

信息学兴趣小组选拔试题

班级： 姓名： 学号： 成绩

1、有红、黄、黑、白四色球各一个，放置在一个内存编号为1、2、3、4四个格子的盒中，

每个格子放置一只球，它们的顺序不知。甲、乙、丙三人猜测放置顺序如下： 甲：黑编号1，黄编号2； 乙：黑编号2，白编号3； 丙：红编号2，白编号4 。

结果证明甲乙丙三人各猜中了一半。

写出四色球在盒子中放置情况及推理过程。

2、 列举一个算法，使算法的解能对应相应的问题。

例如，设问题为：学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M）与答错的题数（N），求最后得分（S）是多少？ 列举出相应算法为：

X：=10； Y：=5；

READ（M，N）； S：=X*M-Y*N；

现有以下问题：用五角钱换成5分、2分与1分的硬币，可有多少种换法？ 请列出该问题的算法。

3、下图中用点表示城市，点与点之间的联系表示城市间的道路：

D C

E F A B

试问：

① 能否找出一条从A城市出发，经过图中所有道路一次后又回到出发点的通路

来？

② 能否从A出发，找出去每个城市且只去一次的通路来？ 若能，则写出通路，否则说明理由。

0

4、一个将角编了号的正三角形可以绕着外心O（中心）逆时针旋转120，如下图所示： 1 3

0 0 a

2 3 1 2 图一 图二 0

如果将这一旋转用字母a 来表示，看作运算对象，同时用aa或a2 表示旋转1201

-

后再旋转120 ，也就是说将连续运动看作乘法运算，那么三角形状态（可简称为元素）即可与运动表达式关联起来，请回答：

0

① 如果将图一的原始三角形连续旋转120N次，简单地表示为an （N为任意自然

数），试求an 的值（指三角形旋转后的结果状态）；

② 如果将下面的旋转看作是a的逆元素，记为a-1 ，则有a-1 = a2 试求：a-n

3 1

0 0

aa

1 2 2 3 图三

5、已知一个数列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）式成立。

6、某班有50名学生，每位学生发一张调查卡，上写a，b，c三本书的书名，将读过的书打✓，结果统计数字如下： 只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；{6%}

（1）读过a的人数是 （2）一本书也没有读过的人数是

0

7、在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图

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

若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，

度为4的子目录有3个。

试问：度为1的子目录有几个？ 8、根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。 例如： 13＝ 1 2

-

23＝ 3＋ 5

33＝ 7＋ 9 ＋11 43= 13+15+17+19

在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的

关系表达式： 9、有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。 此时用一个1×2的骨牌铺满方格，共有3种铺法：

试对给出的任意一个n（n>0），求出铺法总数的递推公式。

10、在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是： (1)a,b两样至少有一样 (2)a,d不能同时取 (3)a,e,f中必须有2样

(4)b,c要么都选，要么都不选 (5)c,d两样中选一样

(6)若d不选，则e也不选

11、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不

在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？

12、 如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车

厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

出口←

← S↓

1 2 3 4 5

13、将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法: 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)

14、现在市场上有一款汽车A很热销，售价是2万美元。汽车A每加仑汽油可以行

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

3

-

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

16、一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖 元钱。

17、75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中

20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。

18、将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列，每次可以交换任

意两个元素，最少需要交换___次。

19、有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、5名同学，已

知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组分别选出3位组长，一位同学最多只能担任一个小组的组长，共有___种选择方案。 20、（寻找假币） 现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相

同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：____________________________________________。 21、（取石子游戏） 现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆

中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果： 。 4

-

答案

1、四色球在盒子中放置的情况为：4% 1 黑 2 红 3 白 4 黄 推理过程是：4% 假定： 黑为1√ 黄为2× 黑为2× 白为3√ 红为2√ 白为4× 黄为4√ 2、 列出的算法是：

K：=0

FOR i：=0 TO 10 DO

K：=K+（50-I*5） DIV 2+1； ENDFOR；

3、 ① 能。例如A→D→C→E→A→F→C→B→A ② 不能。本题的回答要点如下：要到达D，E，F，B四个点之一，必须由A，C出发才可，因为A，C只可能出发一次，所以这样的通路不存在。

4、

a ,当n MOD 3=1 时； a2,当n MOD 3=1 时；

① a n = a2,当n MOD 3=2 时； ② a-n= a ,当n MOD 3=2 时； a3,当n MOD 3=0 时； a3,当n MOD 3=0 时；

6、读过a的人数是12人。（2）一本书也没读过的人数是30人。 7、度为1的子目录有9个

8、给出n之后，X与n之间的关系表达式为： N2-N+1

9、对给出的任意一个n（n>0），用F（n）表示其铺法的总数的递推公式为: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（n≥3）

10、在a,b,c,d,e,f六件物品中，按条件能选出的物品是：a,b,c,f 11、用这些点为顶点，能组成751个不同三角形

5、当K= 3 ，a1,a2,…,ak为a1=3,a2=-3,a3=1时，对数列122232,…,n2,…（A）成立。

12、可能的到达出口的车厢排列总数： 9 ； 13、当N=4,M=3时有 35 种不同排法

14、 15、 11

16、 160 17、 10

18、 5 19、 11

20、 4次；第一次份3份 27 27 26 取其中相等的两份于天平上称量 21、 能；第一位拿去50颗中的32颗即可。 5