信息学奥赛问题求解(带答案~).doc
《信息学奥赛问题求解(带答案~).doc》由会员分享,可在线阅读,更多相关《信息学奥赛问题求解(带答案~).doc(7页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、|1已知,按中序遍历二叉树的结果为:abc问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。2有 2n 的一个长方形方格,用一个 12 的骨牌铺满方格。例如 n=3 时,为 23 方格。此时用一个 12 的骨牌铺满方格,共有 3 种铺法:试对给出的任意一个 n(n0),求出铺法总数的递推公式。3设有一个共有 n 级的楼梯,某人每步可走 1 级,也可走 2 级,也可走 3 级,用递推公式给出某人从底层开始走完全部楼梯的走法。例如:当 n=3 时,共有 4 种走法,即1+1+1,1+2,2+1,3。4.在 a,b,c,d,e,f 六件物品中,按下面的条件能选出的物品是: (1)a
2、,b 两样至少有一样(2)a,d 不能同时取(3)a,e,f 中必须有 2 样(4)b,c 要么都选,要么都不选(5)c,d 两样中选一样(6)若 d 不选,则 e 也不选5.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形?6.已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为:CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为:7.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同四
3、边形?8.如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每个车厢可|以向左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3 号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列) 。出口 1 2 3 4 5 S9.将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排法:红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法)10 在书架上放有编号为 1 ,2 ,n 的 n 本书。现将 n 本书全部取下然后再放回去,
4、当放回去时要求每本书都不能放在原来的位置上。例如:n = 3 时:原来位置为:1 2 3放回去时只能为:3 1 2 或 2 3 1 这两种问题:求当 n = 5 时满足以上条件的放法共有多少种?(不用列出每种放法)11.现在市场上有一款汽车 A 很热销,售价是 2 万美元。汽车 A 每加仑汽油可以行驶 20英里。普通汽车每年大约行驶 12000 英里。油价是每加仑 1 美元。不久我公司就要推出新款节油汽车 B,汽车 B 每加仑汽油可以行驶 30 英里。现在我们要为 B 制定价格(它的价格略高于 A):我们预计如果用户能够在两年内通过节省油钱把 B 高出 A 的价钱弥补回来,则他们就会购买 B,
5、否则就不会购买 B。那么 B 的最高价格应为 万美元。 12. 某年级学生共选修 6 门课程,期末考试前,必须提前将这 6 门课程考完,每人每天只在下午至多考一门课程,设 6 门课程为 C1,C2,C3,C4,C5,C6,S(Ci)为学习 Ci 的学生集合。已知 S(Ci)S(C6),i=1,2,.,5,S(Ci)S(Ci+1),i=1,2,3,4,S(C5)S(C1),问至少安排_天才能考完这 6 门课程。13、一个家具公司生产桌子和椅子。现有 113 个单位的木材。每张桌子要使用 20 个单位的|木材,售价是 30 元;每张椅子要用 16 个单位的木材,售价是 20 元。使用已有的木材生产
6、桌椅(不一定要用光木材)做多可以买_元钱。14、75 名儿童去游乐场玩。他们可以骑旋转木马,坐滑行轨道,乘宇宙飞船。已知其中 20人这三种东西都玩过,55 人至少玩过其中两种。若每玩一样的费用为 5 元,游乐场总共收入 700,可知有_名儿童没有玩过其中任何一种。15. 已知 a, b, c, d, e, f, g 七个人中, a 会讲英语;b 会讲英语和汉语;c 会讲英语、意大利语和俄语;d 会讲汉语和日语;e 会讲意大利语和德语;f 会讲俄语、日语和法语; g 会讲德语和法语。能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈?如果可以,请以“a b”开头写出你的安排方案: 。1
7、6. 将数组32, 74, 25, 53, 28, 43, 86, 47中的元素按从小到大的顺序排列,每次可以交换任意两个元素,最少需要交换次。17. 有 3 个课外小组:物理组,化学组和生物组。今有张、王、李、赵、陈 5 名同学,已知张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员。如果要在3 个小组中分别选出 3 位组长,一位同学最多只能担任一个小组的组长,共有多少种选择方案。18. 取火柴游戏的规则如下:一堆火柴有 N根,A、B 两人轮流取出。每人每次可以取1 根或2 根,最先没有火柴可取的人为败方,另一方为胜方。如果先取者有必胜策略则记为1,先取者没有必胜策略记为0。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息学 问题 求解 答案
限制150内