初赛问题求解专练

1、2006年南海区信息学夏令营OI3班练习题（二）（问题解答专练）一、问题求解：1、平面上有7个点，共有3个点共线，其余再也没有3点共线，每两点连成一条直线，一共可以连成 （1） 条不同直线。以这些点为顶点可以连成 （2） 个不同的三角形。2、某省的地图如下图，共有A,B,C,D,E,F,G七个县区，如果用红、黄、蓝、绿、紫这五种颜色给地图染色，要求相邻区县的颜色不能相同，那么共有_种不同的染色方法。3、马路上有编号为1，2，3，10的十盏路灯，为既节约用电，又能看清路面（不影响走路照明），可以把其中的三只灯关掉，但不能同时关掉相邻的两盏或两盏以上的灯。在两端的灯也不能关掉的情况下，求满足条件的

2、关灯办法有_种？4、若一个栈中有5个元素，另一个栈中有4个元素，则他们出栈的的方法共有多少种？ 5、如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。 出口 1 2 3 4 5 S6、将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法:红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法) 7、平面上有三条平行直线，每条直线

3、上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？ 8、已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 9、字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成哪些不同的字符串？_10、将数组32,74,25,53,28,43,86,47中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换_ _次。11、有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组

4、成员。如果要在3个小组分别选出3位组长，一位同学最多只能担任一个小组的组长，共有_ _种选择方案。12、无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少有_个顶点。13、在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度例如左图： 该图表达了A盘的目录结构：DI，Dll，D2均表示子目录的名字.在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D113的度均为1。又不考虑子目录的名字，则可简单的图示为如下的树结构： 若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3

5、个。 试问：度为1的子目录有几个？ 14、已知公式： 则f(f(f(3)+2)div 2)的值是( )。15、在某工厂装配30辆汽车，可供选择的设备是收音机，空调和对讲机。已知其中15辆汽车有收音机，8辆有空调，6辆有对讲机，而且其中3辆汽车这三样设备都有。请问至少有多少辆汽车没有提供任何设备？ 16、某班有30个同学报名参加100、400、800m3个运动项目比赛。已知有6人获100m参赛资格，8人获400m参赛资格，15人获800m参赛资格，且其中有3个获全部3项参赛资格，则至少有_人没有获任何项目参赛资格。17、某律师事务所共有15名工作人员，如果以下判断只有一个是真的，那么该律师事务所

6、会使用计算机的人数是_人。（1） 有人会使用计算机（2） 有人不会使用计算机（3） 所长不会使用计算机18、现在市场上有一款汽车A很热销，售价是2万美元。汽车A每加仑汽油可以行驶20英里。普通汽车每年大约行驶12000英里。油价是每加仑1美元。不久我公司就要推出新款节油汽车B，汽车B每加仑汽油可以行驶30英里。现在我们要为B制定价格(它的价格略高于A)：我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来，则他们就会购买B，否则就不会购买B。那么B的最高价格应为 万美元。19、一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子

7、要用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要用光木材）做多可以买_元钱。20、75名儿童去游乐场玩。他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中两种。若每玩一样的费用为5元，游乐场总共收入700，可知有_名儿童没有玩过其中任何一种。21、  某班有50名学生，每位学生发一张调查卡，上写a，b，c三本书的书名，将读过的书打V，结果统计数字如下：只读a者8人；只读b者4人；只读c者4人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；（1）读过a的人数是（ 

8、     ）   （2）一本书也没有读过的人数是（      ）22、 已知一串明文与对应的密码如下:明文: home 密码: fmkc若采用与上述相同的加密算法,则明文pen的密码是 。23、在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也不选24、某信息学竞赛，A、B、C、D、E、F、G、H八位同学获得

9、了前八名，老师让他们猜一下谁是第一名。A说：“或者F是第一名，或者H是第一名。”B说：“我是第一名。”C说：“G是第一名。”D说：“B不是第一名。”E说：“A说的不对。”F说：“我不是第一名。”G说：“C不是第一名。”H说：“我同意A的意见。”老师指出，八人中有三人猜对了，那么，试问第一名是谁？ 25、N皇后问题要求在N*N的棋盘上放置N个皇后，使其不能互相攻击，即任意2个皇后不能处于棋盘上的同一行、同一列或同一斜线上。则当N=4时，摆放方法有哪两种？（答案写成“a b c d”的形式 ，表示摆放在第一行的第a列、第二行的第b列、第三行的第c列和第四行的第d列） 26、莎士比亚在威尼斯商人中，

10、写富家少女鲍细娅品貌双全，贵族子弟、公子王孙纷纷向她求婚。鲍细娅按照其父遗嘱，由求婚者猜盒订婚。鲍细娅有金、银、铅三个盒子，分别刻有三句话，其中只有一个盒子，放有鲍细娅肖像。求婚者通过这三句话，猜中鲍细娅的肖像放在哪只盒子里，就嫁给谁。三个盒子上刻的三句话分别是：（1）金盒子：“肖像不在此盒中。” （2）银盒子：“肖像在铅盒中。”（3）铅盒子：“肖像不在此盒中。”鲍细娅告诉求婚者，上述三句话中，最多只有一句是真的。请你猜鲍细娅的肖像究竟放在哪一个盒子里？ 。27、甲乙丙丁四人猜年龄，甲说：“我最大，乙最小，丁第三大”；乙说：“我最大，甲最小，丁第二大，丙第三大”；丙说：“乙最小，甲第三大”；丁

11、说：“我最大，丙最小，乙第二大，甲第三大”。四个人中每个人只说对了一个结果，请按从大到小的顺序写出正确结果。1、 2、 3、 4、 28、小王、小张和小李中一位是工人，一位是教师，一位是律师。现在知道小李比律师年龄大，小王和教师不同岁，教师比小张年龄小。问： 是工人、 是教师、 是律师。29、现在的时间为12点正，再过N个小时（N为整数）为几点钟？ 30、编号为1到13的纸牌顺时钟排成一圈，有人从编号为1的牌从数字1开始顺时钟数下去，1、2、3、20、21、，一圈又一圈。问：当数到数字N时，所在纸牌的编号为 。31、“鼠算遗题”。这是日本数学家吉田光在1627年提出来的。他是这样说的：“正月里

12、，鼠父鼠母生了12只小鼠，于是大小鼠共14只。二月里，两代鼠全部配对，每对鼠又各生了12只小鼠。因此共有98只。如这样下去，每月所有的鼠全部配对，每对鼠又各生了12只小鼠。十二个月后，鼠的总数是多少呢？”假设每月都按这样的规律生，而所生的鼠又全部成活，十二个月后，鼠的总数是27682574402只。你能找出计算此数的公式吗？此公式为 。32、有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。此时用一个1×2的骨牌铺满方格，共有3种铺法： 试对给出的任意一个n(n0)，求出铺法总数的递推公式。 33、公式推导： 根据Noco

13、machns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。 例如： 13 1 23 3 5 33 7 9 11 43=13十15+17+19在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式： 34、“兔子繁殖”。小兔子出生一个月后便可长成大兔子，大兔子每月都可以繁殖，生出一对小免子。假设月份有对小兔子，月份便会有对大兔子和对小兔子共对兔子，依此繁殖速度，则m月份兔子的对数F(m) 的值为。练习题（二）（问题解答专练）答案1、(1) 19 (2) 34 2、5x4x3x3x3x3x3=4860(种)   3、 或20 4、126 5、8 6、35 7、7518、答：有5种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为：9、ABC ACB BAC BCA CBA 10、答： 5 11、答： 11 12、11 13、9个 14、55 15、7 16、7 17、15 18、2.04 19、160 20、10 21、(1)读过a的人数是12人。(2)一本书也没读过的人数是30人。22、ncl 23、a,b,c,f 24、C是第一名25、 2 4 1 3 和 3 1 4 2 26、金 27、丁甲丙乙28、 小张 是工人、 小李 是教师、 小王 是律师29