NOIP初赛问题求解专练.pdf

《NOIP初赛问题求解专练.pdf》由会员分享，可在线阅读，更多相关《NOIP初赛问题求解专练.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、20062006 年南海区信息学夏令营年南海区信息学夏令营 OI3OI3 班练习题（二）班练习题（二）（问题解答专练）（问题解答专练）一、问题求解：问题求解：1、平面上有7 个点，共有3 个点共线，其余再也没有3 点共线，每两点连成一条直线，一共可以连成（1）条不同直线。以这些点为顶点可以连成（2）个不同的三角形。2、某省的地图如下图，共有 A,B,C,D,E,F,G 七个县区，如果用红、黄、蓝、绿、紫这五种颜色给地图染色，要求相邻区县的颜色不能相同，那么共有_种不同的染色方法。3、马路上有编号为 1，2，3，10 的十盏路灯，为既节约用电，又能看清路面（不影响走路照明），可以把其中的三只灯关

2、掉，但不能同时关掉相邻的两盏或两盏以上的灯。在两端的灯也不能关掉的情况下，求满足条件的关灯办法有_种？4、若一个栈中有 5 个元素，另一个栈中有4 个元素，则他们出栈的的方法共有多少种？5、如下图,有一个无穷大的的栈S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每个车厢可以向左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是3 号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。出口6、将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排法:红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红问题:当

3、N=4,M=3 时有多少种不同排法?(不用列出每种排法)7、平面上有三条平行直线，每条直线上分别有 7，5，6 个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？1 2 3 4 5S8、已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。9、字符A、B、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成哪些不同的字符串？_10、将数组32,74,25,53,28,43,86,47中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换_次。11、有 3 个课外小组：物理组，化学

4、组和生物组。今有张、王、李、赵、陈5 名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在 3 个小组分别选出 3位组长，一位同学最多只能担任一个小组的组长，共有_种选择方案。12、无向图 G 有 16 条边，有 3 个 4 度顶点、4 个 3 度顶点，其余顶点的度均小于3，则 G 至少有_个顶点。113、在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度例如左图：该图表达了 A 盘的目录结构：DI，Dll，D2 均表示子目录的名字.在这里，根目录的度为2，D1子目录的度为 3，D11子目录的度为 4，D12，D2，D111，D112，D113的度均

5、为 1。又不考虑子目录的名字，则可简单的图示为如下的树结构：若知道一个磁盘的目录结构中，度为2 的子目录有 2 个，度为 3 的子目录有 1 个，度为 4 的子目录有 3 个。试问：度为 1 的子目录有几个？14、已知公式：则 f(f(f(3)+2)div 2)的值是()。15、在某工厂装配30 辆汽车，可供选择的设备是收音机，空调和对讲机。已知其中15 辆汽车有收音机，8 辆有空调，6 辆有对讲机，而且其中 3 辆汽车这三样设备都有。请问至少有多少辆汽车没有提供任何设备？16、某班有 30 个同学报名参加 100、400、800m3 个运动项目比赛。已知有6 人获 100m 参赛资格，8 人

6、获 400m 参赛资格，15 人获 800m 参赛资格，且其中有 3 个获全部 3 项参赛资格，则至少有_人没有获任何项目参赛资格。17、某律师事务所共有 15 名工作人员，如果以下判断只有一个是真的，那么该律师事务所会使用计算机的人数是_人。（1）有人会使用计算机（2）有人不会使用计算机（3）所长不会使用计算机18、现在市场上有一款汽车 A 很热销，售价是 2 万美元。汽车 A 每加仑汽油可以行驶 20 英里。普通汽车每年大约行驶 12000 英里。油价是每加仑1 美元。不久我公司就要推出新款节油汽车B，汽车 B 每加仑汽油可以行驶30 英里。现在我们要为B 制定价格(它的价格略高于 A)：

7、我们预计如果用户能够在两年内通过节省油钱把B 高出 A 的价钱弥补回来，则他们就会购买B，否则就不会购买 B。那么 B 的最高价格应为万美元。19、一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20 个单位的木材，售价是 30 元；每张椅子要用16 个单位的木材，售价是20 元。使用已有的木材生产桌椅（不一定要用光木材）做多可以买_元钱。20、75 名儿童去游乐场玩。他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。已知其中 20 人这三种东西都玩过，55 人至少玩过其中两种。若每玩一样的费用为 5 元，游乐场总共收入 700，可知有_名儿童没有玩过其中任何一种。21、某班有 5

8、0 名学生，每位学生发一张调查卡，上写a，b，c 三本书的书名，将读过的书打V，结果统计数字如下：只读 a 者 8 人；只读 b 者 4 人；只读 c 者 4 人；全部读过的有 2 人；读过 a，b 两本书的有 4 人；读过 a，c 两本书的有 2 人；读过 b，c 两本书的有 3 人；（1）读过 a 的人数是（）（2）一本书也没有读过的人数是（）22、已知一串明文与对应的密码如下:明文:home密码:fmkc21f(n)f(n 1)n(n 1)(n 1)若采用与上述相同的加密算法,则明文 pen 的密码是。23、在 a,b,c,d,e,f 六件物品中，按下面的条件能选出的物品是：(1)a,b

9、 两样至少有一样(2)a,d 不能同时取(3)a,e,f 中必须有 2 样(4)b,c 要么都选，要么都不选(5)c,d 两样中选一样(6)若 d 不选，则 e 也不选24、某信息学竞赛，A、B、C、D、E、F、G、H 八位同学获得了前八名，老师让他们猜一下谁是第一名。A 说：“或者 F 是第一名，或者 H 是第一名。”B 说：“我是第一名。”C 说：“G 是第一名。”D 说：“B 不是第一名。”E 说：“A 说的不对。”F 说：“我不是第一名。”G 说：“C 不是第一名。”H 说：“我同意 A 的意见。”老师指出，八人中有三人猜对了，那么，试问第一名是谁？25、N 皇后问题要求在 N*N 的

10、棋盘上放置 N 个皇后，使其不能互相攻击，即任意2 个皇后不能处于棋盘上的同一行、同一列或同一斜线上。则当 N=4 时，摆放方法有哪两种？（答案写成“a bc d”的形式，表示摆放在第一行的第a 列、第二行的第 b 列、第三行的第c 列和第四行的第d 列）26、莎士比亚在威尼斯商人中，写富家少女鲍细娅品貌双全，贵族子弟、公子王孙纷纷向她求婚。鲍细娅按照其父遗嘱，由求婚者猜盒订婚。鲍细娅有金、银、铅三个盒子，分别刻有三句话，其中只有一个盒子，放有鲍细娅肖像。求婚者通过这三句话，猜中鲍细娅的肖像放在哪只盒子里，就嫁给谁。三个盒子上刻的三句话分别是：（1）金盒子：“肖像不在此盒中。”（2）银盒子：“

11、肖像在铅盒中。”（3）铅盒子：“肖像不在此盒中。”鲍细娅告诉求婚者，上述三句话中，最多只有一句是真的。请你猜鲍细娅的肖像究竟放在哪一个盒子里？。27、甲乙丙丁四人猜年龄，甲说：“我最大，乙最小，丁第三大”；乙说：“我最大，甲最小，丁第二大，丙第三大”；丙说：“乙最小，甲第三大”；丁说：“我最大，丙最小，乙第二大，甲第三大”。四个人中每个人只说对了一个结果，请按从大到小的顺序写出正确结果。1、2、3、4、28、小王、小张和小李中一位是工人，一位是教师，一位是律师。现在知道小李比律师年龄大，小王和教师不同岁，教师比小张年龄小。问：是工人、是教师、是律师。29、现在的时间为 12 点正，再过 N 个

12、小时（N 为整数）为几点钟？30、编号为 1 到 13 的纸牌顺时钟排成一圈，有人从编号为1 的牌从数字 1 开始顺时钟数下去，1、2、3、20、21、，一圈又一圈。问：当数到数字 N 时，所在纸牌的编号为。31、“鼠算遗题”。这是日本数学家吉田光在1627 年提出来的。他是这样说的：“正月里，鼠父鼠母生了 12 只小鼠，于是大小鼠共14 只。二月里，两代鼠全部配对，每对鼠又各生了12 只小鼠。因此共有 98 只。如这样下去，每月所有的鼠全部配对，每对鼠又各生了12 只小鼠。十二个月后，鼠的总数是多少呢？”假设每月都按这样的规律生，而所生的鼠又全部成活，十二个月后，鼠的总数是 402 只。你能

13、找出计算此数的公式吗？此公式为。32、有2n 的一个长方形方格，用一个12 的骨牌铺满方格。例如n=3 时，为23 方格。此时用一个 12 的骨牌铺满方格，共有3 种铺法：3试对给出的任意一个 n(n0)，求出铺法总数的递推公式。33、公式推导：根据 Nocomachns 定理，任何一个正整数n 的立方一定可以表示成n 个连续的奇数的和。例如：13 123 3 533 7 9 1143=13 十 15+17+19在这里，若将每一个式中的最小奇数称为X，那么当给出 n 之后，请写出 X 与 n 之间的关系表达式：34、“兔子繁殖”。小兔子出生一个月后便可长成大兔子，大兔子每月都可以繁殖，生出一对

14、小免子。假设月份有对小兔子，月份便会有对大兔子和对小兔子共对兔子，依此繁殖速度，则m月份兔子的对数F(m)的值为。练习题练习题（二）（问题解答专练）答案（问题解答专练）答案1、(1)19(2)342、5x4x3x3x3x3x3=4860(种)3、C6或 204、1265、86、357、7518、答：有 5 种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为：39、ABCABCACBACBBACBACBCABCACBACBA10、答：答：5 511、答：答：111112、1113、9 个 14、5515、7 16、7 17、1518、2.0419、16020、1021、(1)读过 a

15、的人数是 12 人。(2)一本书也没读过的人数是30 人。22、ncl23、a,b,c,f24、C 是第一名25、2413和314226、金金27、丁甲丙乙28、小张是工人、小李是教师、小王是律师29、1+(N-1)mod 1230、纸牌的编号为 1+（N-1）mod 13或 1+13-int(n-1)/13)*1331、公式为：f(n)27 f(n 1)(n 0)(n 0)32、对给出的任意一个n(n0)，用 F(n)表示其铺法的总数的递推公式为：F(1)=1F(2)=2F(n)=F(n-2)+F(n-1)(n3)33、关系表达式:N*N-N+1(m 1)134、2m-1 (m=1)或 f(m)=2f(m1)(m 1)4