《信息学奥赛问题求解带答案资料.pdf》由会员分享，可在线阅读，更多相关《信息学奥赛问题求解带答案资料.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1/10 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,b两
2、样至少有一样 (2)a,d不能同时取 (3)a,e,f中必须有 2 样 (4)b,c要么都选，要么都不选 (5)c,d两样中选一样(6)若 d不选，则 e也不选 2/10 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 S 9.将 N个红球和 M个黄球排成一行。例如:N=2,M=3可得到以下 6种排法:红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法)10 在书架上放有编号为 1，2，n的 n 本书。现将 n 本书全部取下然后再放回去，当放回去时要求每
4、本书都不能放在原来的位置上。例如：n=3时：原来位置为：1 2 3 3/10 放回去时只能为：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会讲俄 4/10 语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案：。16.将数组32,74,25,53,28
7、,43,86,47中的元素按从小到大的顺序排列，每次可以交换任 意两个元素，最少需要交换次。17.有 3 个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈 5 名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在 3 个小组中分别选出 3 位组长，一位同学最多只能担任一个小组的组长，共有多少种选择方案。18.取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1 根或 2 根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N 分别为100，200，300，400，500 时，
8、先取者有无必 胜策略的标记顺序为（回答应为一个由0 和/或1 组成的字符串）。5/10 19（寻找假币）现有 80 枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第 1 次的称重方法。请写出你的 结果：_。20（取石子游戏）现有 5 堆石子,石子数依次为 3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论 乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：_。21将 2006 个
9、人分成若干不相交的子集，每个子集至少有 3 个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。则满足上述条件的子集最多能有几个？22将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最 下面一行位于 6/10 中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同 一行或下一行的小三角形，并
10、且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的例 子）。设 n=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)
11、与 S(5,2)，再分这两种情况对原固定的数进行分析。）24、（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有 7条南北向的纵街，5 条东西向的横街。现要从西南角的 A 走到东北角的 B，最短的走法共有多少种？_、7/10 25.书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的，C 和 D 是黑皮的。把这 4 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足 A 必须比 C 靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有_种摆法。26有 6 个城市，任何两个城市之间都有一条道路连接，6 个城市两两之间的距离如下表所示，则城市 1 到城市
12、 6 的最短距离为_。城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 城市 1 0 2 3 1 12 15 城市 2 2 0 2 5 3 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 0 27.给定 n 个有标号得球，标号依次为 1，2，n。将这 n 个球放入 r 个相同得盒子里，不允许有空盒，其不同放置方法得总数记为 s(n,r)。例如，s(4,2)=7,这 7 种不同的放置方法依次为(1),(234)，(2),(134)，8/10(3),(124)，(4),(123)，(12),(
13、34)，(13),(24)，(14),(23)。当 n=7，r=4 时，s(7,4)=_。28.N 个人在操场里围成一圈，将这 N 个人安顺时针方向从 1 到 N 编号，然后，从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩一个人，记这个人的编号为 J(N)，例如，J(5)=3，J(10)=5，等等。则J(400)=_。对 N=2m+r 进行分析（0=r0），用 F（n）表示其铺法的总数的递推公式为:F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（n3）3用递推公式给出的某人从底层开始走完全部楼梯的走法为（用
14、 F（N）记录不同方案数）：F（1）1 F（2）2 F（3）4 F（N）F（N3）F（N2）F（N1）（N4）4.答：在 a,b,c,d,e,f 六件物品中，按条件能选出的物品是：a,b,c,f 5.答：用这些点为顶点，能组成 751个不同三角形 6、答：该二叉树先序遍历的顺序为：ABCEGDFHIJ 7、答：这些点为顶点，能组成 2250个不同四边形 8.9 9.35 10.44 11.2.04 12.4 13.160 14.10 15.a b d f g e c 16.5 17.11 18.11011 19.4 次，第一步：分成 3 组：27，27，26，将前 2 组放到天平上（4 分）。10/10 20.有获胜策略(1 分)，第 1 次在第 5 堆中取 32 颗石子(4 分)，21.401 22.9！（或 362880）23.9 24.210 25.12 4 26.7(1-2-5-6)内容总结 （1）1已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树（2）对 N=2m+r 进行分析（0=r2m）29.书架上有 21 本书，编号从 1 到 21 从中选 4 本，其中每两本的编号都不相邻的选法一共有