最新信息学奥赛问题求解(带答案)

1、1. 已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2. 有2 x n的一个长方形方格，用一个1 X 2的骨牌铺满方格。例如n=3时，为2 X 3方格。 此时用一个1 X 2的骨牌铺满方格，共有 3种铺法：试对给出的任意一个 n (n>0),求出铺法总数的递推公式。3. 设有一个共有n级的楼梯，某人每步可走 1级，也可走2级，也可走3级，用递推公 式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1 + 1,1+2,2+1,3 。4. 在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是:(

2、1) a,b两样至少有一样(2) a,d不能同时取(3) a,e,f中必须有2样(4) b,c要么都选，要么都不选(5) c,d两样中选一样若d不选，则e也不选5. 平面上有三条平行直线，每条直线上分别有7, 5, 6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？6. 已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为:CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：7. 平面上有三条平行直线，每条直线上分别有7, 5, 6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？8.

3、如下图，有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走，也可以进入栈 S让后面的车厢通过。现已知第一个到达出口的是 3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。出口J12345S J9. 将N个红球和M个黄球排成一行。例如：N=2,M=3可得到以下6种排法： 红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题:当 N=4,M=3时有多少种不同排法？(不用列出每种排法)n本书全部取下然后再放n = 3 时:10. 在书架上放有编号为 1 , 2 ,., n的n本书。现将 回去，当放回去时要求每本书都不能放在原来

4、的位置上。例如：原来位置为：12 3放回去时只能为：312或 231 这两种问题：求当n = 5时满足以上条件的放法共有多少种？(不用列出每种放法)11. 现在市场上有一款汽车 A很热销，售价是2万美元。汽车 A每加仑汽油可以行驶 20 英里。普通汽车每年大约行驶 12000英里。油价是每加仑1美元。不久我公司就要推出新款 节油汽车B,汽车B每加仑汽油可以行驶 30英里。现在我们要为 B制定价格(它的价格略高 于A):我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来，则他们就会购买B,否则就不会购买 B。那么B的最高价格应为 万美元。12. 某年级学生共选修 6门课程，期末考试

5、前，必须提前将这6门课程考完，每人每天只 在下午至多考一门课程，设6门课程为C1, C2, C3, C4, C5, C6, S(Ci)为学习Ci的学生集合。已知 S(Ci) n S(C6)丰 i=1 , 2, . , 5, S(Ci) n S(Ci+1)丰 © , i=1 , 2, 3, 4, S(C5) n S(C1)工© ,问至少安排 天才能考完这6门课程。13、一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是 20元。使用已有的木材生产桌椅（不一定要用光木材）做多可以买 元钱。14、

6、75名儿童去游乐场玩。他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中两种。若每玩一样的费用为5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。15. 已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语 和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语 和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以， 请以"a b”开头写出你的安排方案： 。16. 将数组32, 74, 25, 53, 28, 43, 86,

7、47中的元素按从小到大的顺序排列，每次可以交换任 意两个元素，最少需要交换次。17. 有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组中分别选出3位组长，一位同学最多只能担任一个小组的组长，共有多少种选择18. 取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为 0。当N分别为100，200，300，400，500时，先取者有无必 胜策略的标记顺序为（回答应

8、为一个由0和/或 1组成的字符串）。19. （寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指1 次的称重方法20. （取石子游戏）现有5堆石子，石子数依次为3 , 5, 7, 19, 50,甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取），取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论 乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一 堆里取多少？请写出你的结果：21 将2006个人分成若干不相交的子集，每个子集至少有3个人，并且:（1）在每个子集中，没有人

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

10、的通路的总数为。23. (子集划分)将 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)，再分这两种情况对原固定的数进行分析。)7条南北向的纵24、(最短路线)某城市的街道是一个很规

11、整的矩形网络(见下图)，有街，5条东西向的横街。现要从西南角的A走到东北角的 B,最短的走法共有多少种?25. 书架上有4本不同的书 A B、C 0其中A和B是红皮的，C和D是黑皮的。把这 4 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有 种。满足 A必须比C种摆法。靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有26有 6 个城市，任何两个城市之间都有一条道路连接， 6 个城市两两之间的距离如下表 所示，则城市 1 到城市 6 的最短距离为 。城市 1 城市 2 城市 3 城市 4 城市 5 城市 6城市 1 0 2 3 1 12 15城市 2 2 0 2 5 3 12城市

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 027. 给定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)= 。28. N个人在操场里围成一圈，将这N个人安顺时针方向从1到N编号，

13、然后，从第一个人起，每隔一个人让下一个人离开操场，显然， 第一轮过后，具有偶数编号的人都离开了操 场。依次做下去， 直到操场只剩一个人， 记这个人的编号为 J(N) ，例如， J(5)=3 ， J(10)=5 ， 等等。则 J(400)= 。对 N=2m+r 进行分析(0<=r<2m)29. 书架上有 21 本书，编号从 1 到 21 从中选 4 本，其中每两本的编号都不相邻的选法一共 有。1.答：有5种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为ab a c c/ /baccab/cbba2 .对给出的任意一个n (n>0),用F ( n)表示其铺法的总数的递

14、推公式为：F (1) =1F (2) =2F (n) =F(n-2) +F (n-1)(n3)3 用递推公式给出的某人从底层开始走完全部楼梯的走法为(用F(N )记录不同方案数)F ( 1)= 1F (2)= 2F (3)= 4F ( N )= F ( N 3)+ F (N 2)+ F (N 1)(N > 4)4.答：在a,b,c,d,e,f六件物品中，按条件能选出的物品是：a,b,c,f5答：用这些点为顶点，能组成751个不同三角形6、答：该二叉树先序遍历的顺序为：ABCEGDFHIJ7、答：这些点为顶点，能组成 2250个不同四边形8. 99.3510.4411.12.2.0413.414.16015.16.1