问题求解普及六

六、问题求解20001.已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2.有2Xn的一个长方形方格，用一个1X2的骨牌铺满方格。例如n=3时，为2X3方格。此时用一个1X2的骨牌铺满方格，共有3种铺法：试对给出的任意一个n(n>0)，求出铺法总数的递推公式。七、 问题求解(5+7=12分)2001(七)在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是: a,b两样至少有一样a,d不能同时取a,e,f中必须有2样b,c要么都选，要么都不选c,d两样中选一样若d不选，则e也不选.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？八、 问题求解:2002(八)如下图，有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。出口一 一 1 2 3 4 5SiI2.将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法：红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题:当N=4,M=3时有多少种不同排法?（不用列出每种排法）九、问题求解（每题5分，共10分）2003（九）1．现在市场上有一款汽车A很热销，售价是2万美元。汽车A每加仑汽油可以行驶20英里。普通汽车每年大约行驶12000英里。油价是每加仑1美元。不久我公司就要推出新款节油汽车B,汽车B每加仑汽油可以行驶30英里。现在我们要为B制定价格（它的价格略高于A）:我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来，则他们就会购买B，否则就不会购买B。那么B的最高价格应为 万美元。2．无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少有 个顶点。十、问题求解（每题5分，共10分）2004（十）一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖元钱。75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。十一、问题求解（请在空格处填上答案，每空5分，共10分）2005（十一）将数组｛32,74,25,53,28,43,86,47｝中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换___次。有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组分别选出3位组长，一位同学最多只能担任一个小组的组长，共有___种选择方案。十二、问题求解（共2题，每题5分，共计10分）2006（十二）1．（寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：2．（取石子游戏）现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：十三、问题求解(共2题，每题5分，共计10分)。2007(十三)1、 (子集划分)将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),再分这两种情况对原固定的数进行分析。)2、 (最短路线)某城市的街道是一个很规整的矩形网络(见下图),有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B,最短的走法共有多少种？ B十四、问题求解：(共2题,每题5分,共计10分)2008(十四)书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上,满足所有黑皮的书都排在一起的摆法有 种满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起,共有 种摆法。有6个城市，任何两个城市之间都有一条道路连接，6个城