现状英语-schedule是什么意思
六、问题求解
2000
1
．已知
，按中序遍历二叉树的结果为：
abc
问：有多少种不同形态
的二叉树可以得到这一遍历结果，并画出这些二叉树。
答：
有
5
种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为
:
①
a
②
b
③
a
④
c
⑤
c
/
/
/
b
a
c
c
a
b
/
/
c
b
b
a
2
．
有
2
×
n
的一个长方
形方格，
用一个
1
×
< br>2
的骨牌铺满方格。
例如
n=3
时，
为
2
×<
/p>
3
方格。
此时用一个
1
×
2
的骨牌铺满方格，共有
3
种铺法：
试对给出的任意一个
n
（
n>0
），求出铺法总数的递推公式。
答：对给出的任意一个
n
（
n>0
），用
F
（
n
）表示其铺法
的总数的递推公式为
:
F
（
1
）
=1
F
（
2
）
=2
F
（
n
）
=F
（
n-2
）
+F
（
n-1
）
（
n
≥
3
）
七、问题求解
(5+7=12
分
)2001
（七）
1.
在
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
也不选
.
答：在
a,b,c,d,e,f
六件物品中，按条件能选出的物品是：
a,b,c,f
2.
平面上有三条平行直线，每条直线上分别有
7
< br>，
5
，
6
个点，且不同直线上三个
点都不在同一条直线上。问用这些点为顶点，能组成多少个不
同三角形？
答：用这些点为顶点，能组成
751
个不同三角形
八、问题求解
:
2002
（八）
如下图
,
有一个无穷大的的栈
S,
在栈的右边排列着
1,2,3,4,5
共五个车厢。
其中
每个车厢可以向左行走
,
也可以进入栈
S
让后面的车厢通过。现已知第一个到达
出口的是
3
号车厢，请写出所有可能的到达
出口的车厢排列总数
(
不必给出每种
排
列
)
。
出口←
←
S
↓
1
2 3 4 5
第
< br>2
个到达出口为
1
号车厢的全排
除：即排除
6
种。
< br>第
2
个到达出口为
2
号车厢的只有一种不可能：
2514
；
即排除
1
种。
第
2
个到达出口为
4
号车厢的有三种，即排除
3
种。
第
2
个到达
出口为
5
号车厢的只有一种：
5421
；即排除
5
种。
24-6-1-3-5=9
？
8
？
2.
将
N
个红
球和
M
个黄球排成一行。例如
:N=2
,M=3
可得到以下
6
种排法
:
红红黄黄黄
红黄红黄黄
红黄黄红黄
黄红红黄黄
黄红黄红黄
黄黄黄红红
问题
:
当
N=4,M=3
时有多少种不
同排法
?(
不用列出每种排法
)
35
九、问题求解
(
每题
5
分，共
10
分
) 2003
（九）
1
．现在市场上有一款汽车
A
很热销，售价是
2
万美元。汽车
A
每加仑汽油
可以行驶
20<
/p>
英里。普通汽车每年大约行驶
12000
英里。油价是每加仑
1
美元。
不久我公
司就要推出新款节油汽车
B
，汽车
B<
/p>
每加仑汽油可以行驶
30
英里。现
在我们要为
B
制定价格
(
它的价格略高于
A)
：
我们预计如果用户能够在两年内通
过节省油钱把
B
高出
A
的价钱弥补回来，
则他们就会购买
B
，
否则就
不会购买
B
。
那么
B
的最高价格应为
万美元。
1
．答：
2.04
1
1
-
）
)/ 10000
20
30
(20000+2*12000
（
2
．无向图
G
有
16
条边，有
3
个
4
度顶点、
4<
/p>
个
3
度顶点，其余顶点的度均
小于
3
，则
G
至少有
个顶点。
2
．答：
11
十、问题求解
（每题
5
分，共
10
分）
2004
（十）
1.
一个家具公司生产桌子和椅子。
现在有
113
个单位的木材。每张桌子要使用
< br>20
个单位的木材，
售价是
30
元；
每张椅子要使用
16
个单位的木材，
售价是
20
元。
使用已有的木材生产桌椅
（不一定要把木材用光）
，
最多可以卖
元
钱。
160
桌子最多
4
张，
80
个单位，<
/p>
120
元，剩下
33
单位
椅子可以
2
张，
32
个单位，
40
元。
2.
75
名
儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。
已知其中
20
人这三种东西都玩过，
55
人至少玩过其中的两种。若每样乘坐
一次的费用是
5<
/p>
元，游乐场总共收入
700
，可知有
名儿童没有玩过其中
任何一种。
10
55
人玩过至少两项，则包含了
20
个玩个
3
种东西的人。
55-20
人就是玩了两项的。
只玩了一项的：（
700-20*3*5-
（
55-20
）
*2*5
）
/5
（因为每个项目都是
5
元）
=10
（人）
< br>
最后，用
75-20-
（
55-20
）
-10=10
是
1
项都没玩过的人数。
十一、问题求解（请在空格处填上答案，每空
5
分，共
10
分）
2005
（十一）
1.
将数组
{32,74,25,53,28,43,86,47}
中的元素按从小到大的顺序排列，每次可
以交换任意两个元素，
最少需要交换
___
次。
5
32 25
74 28
53 43
74 47
86 74
2.
有
3<
/p>
个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、
5
名
同学，已知张、王为物理组成员，张、李、赵为化学组成
员，李、赵、陈为生物
组成员。
如果要在
3
个小组分别选出
3
位组长，
一位同学最多只能担任一个小组
的组长，共有
___
种选择方案。
11
以“树”来解答比较清楚。
十二、问题求解（共
2
题，每题
5
分，共计
10
分）
2006
（十二）
1
．（寻找假币）
< br>现有
80
枚硬币，其中有一枚是假币，其重量稍轻，所有
真币的重量都
相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？
你还要指出第
1
次的称重方法。请写出你的结果：
_____________________________________________
____
。
4
次
(1
分
)
，
第一步：分成
3
组：
< br>27
，
27
，
< br>26
，将前
2
组放到天平上（<
/p>
4
分）。
2
．（取石子游戏）
现有
5
堆石子
,
石子数依次为
3
，
5
，
7
，
19
，
50
，甲乙两人轮流从任一
< br>堆中任取（每次只能取自一堆，不能不取）
,
取最后一
颗石子的一方获胜。甲先取，问甲
有没有获胜策略（即无论乙怎样取，甲只要不失误，都
能获胜）？如果有，甲第一步应该在
哪一堆里取多少？请写出你的结果：
_________________________________
________________
。
有获胜策略
(1
分
)
，
第
1
次在第
5
堆中取
32
颗石子
(4
分
)
。
每一堆的石子数转换为二进制数后进行异或运算：
3
：
11
5
：
101
7
：
111
19
：
10011
50
：
xor
110010
100000
异或后得
100000
，它的
10
进制数为
32
。这样，
第一次在第
5
堆
中取
< br>32
个石子。
十三、问题求解（共
2
题，每题
5
分，共计
10<
/p>
分）。
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)}
。当<
/p>
n=6
，
r=3
时，
S(6,3)=______________
。
（提示：先固定一个数，对于其余的
5
个数考虑
S(5,3)
与
< br>S(5,2)
，再分这两种
情况对原固定的数进行分析。
）
90
分析：
< br>s(n,k)=k*s(n-1,k)+s(n-1,k-1)