NOIP问题求解集合

《NOIP问题求解集合》由会员分享，可在线阅读，更多相关《NOIP问题求解集合（10页珍藏版）》请在金锄头文库上搜索。

1、NOIP1998 普及二、问题求解： （ 20% ）1已知一个数列U1， U2， U3， UN，往往可以找到一个最小的K 值和 K 个数 a1，a2， ak使得数列从某项开始都满足：UN+K=a1UN+K-1+a2UN+K-2+ +akUN(A) 例如对斐波拉契数列1，1， 2，3，5，可以发现：当K=2，a1=1，a2=1 时，从第3 项起（即 N=1 ）都满足Un+2=Un+1+Un 。 试 对 数 列12， 22， 32， ， n2, 求K和a1,a2, ,aK使 得 （ A） 式 成 立 。7% 2某班有50 名学生，每位学生发一张调查卡，上写a，b，c 三本书的书名，将读过的书打，结

2、果统计数字如下：只读 a 者 8 人；只读b 者 4 人；只读 c 者 3 人；全部读过的有2 人；读过a，b 两本书的有4 人；读过a，c 两本书的有2 人；读过b，c 两本书的有3 人； 6% （1）读过 a 的人数是（ 2）一本书也没有读过的人数是3任给自然数n，k，1K9 ，按如下计算步骤求序列XJXJ-1 X0的步骤： 8% （1）j=0 （2）如果 N=K 则转第 3 步，否则转第7 步（3）Xj = N MOD K div 表示整数除法，结果取整数；（4）N =N DIV K mod 表示整除取余数 （5）j=j+1 （6）回第 2 步（7）Xj = N （8）结束试求当：N=1

3、998， K=3 时， XJXJ-1 X0之值。NOIP1998 提高二、问题求解：(21%) 1、已知一个数列U1，U2，U3， Un，往往可以找到一个最小的k 值和 k 个数 a1，a2， ak，使得数列从某项开始都满足：un+k=a1un+k1+a2un+k2+akun(A) 例如对斐波拉契数列1， 1， 2， 3， 5， 可以发现： 当 k=2， a1=1， a2=1 时，从第 3 项起 (即 n1)都满足 un+2=un+1+un。试对数列13，23，33， n3，求 k 和 a1，a2， ak使得(A) 成立。(8%) 2、给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：

4、DGEBHIFCA 画出此二叉树。(8%) 3、用邻接矩阵表示下面的无向图：NOIP1999 普及二、回答问题 （10 分）在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图该图表达了A 盘的目录结构：D1，Dll，D2 均表示子目录的名字。在这里，根目录的度为2，D1 子目录的度为 3，D11 子目录的度为4，D12，D2， D111，D112，D113 的度均为1。不考虑子目录的名字，则可简单的图示为如下所示的树结构：若知道一个磁盘的目录结构中，度为2 的子目录有2 个，度为 3 的子目录有1 个，度为4 的子目录有3 个。试问：度为1 的子目录有几个？三、公式推导 （1

5、0 分）根据 Nocomachns 定理，任何一个正整数n 的立方一定可以表示成n 个连续的奇数的和。例如：13 1 23 3 5 33 7 9 11 43= 13+15+17+19 在这里，若将每一个式中的最小奇数称为X，那么当给出n 之后，请写出X 与 n 之间的关系表达式：NOIP1999 提高二、回答问题（10 分）将 Ln 定义为求在一个平面中用n 条直线所能确定的最大区域数目。例如：当 n=1 时，L1=2,进一步考虑，用n 条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn 是多少？例如：当n=1 时， Z1=2（如下图所示）当给出 n 后，请写出以下的表达式：1

6、Ln = _ 2 Zn = _ NOIP2000 普及二、问题解答： （每题7 分，共 14 分）1. 已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2. 有 2n 的一个长方形方格，用一个12 的骨牌铺满方格。例如n=3时，为 23 方格。此时用一个1 2 的骨牌铺满方格，共有3 种铺法：试对给出的任意一个n(n0)，求出铺法总数的递推公式。NOIP2000 提高二. 问题求解：（ 6+6=12分）1. 已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2. 设有一个共有

7、n 级的楼梯，某人每步可走1 级，也可走 2 级，也可走 3 级，用递推公式给出某人从 底层开始走完全部楼梯的走法。例如：当n=3 时，共有 4 种走法，即 1+1+1，1+2，2+1，3。NOIP2001 普及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 也不选2.平面上有三条平行直线，每条直线上分别有7，5，6 个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形

8、？NOIP2001 提高二、问题求解 (5+7=12 分) 1. 已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为：2. 平面上有三条平行直线，每条直线上分别有7，5，6 个点，且不同直线上三个点都不在同一条直线 上。问用这些点为顶点，能组成多少个不同四边形？NOIP2002 普及二. 问题求解 : 1.如下图 , 有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。 其中每个车厢可以向左行走, 也可以进入栈 S让后面的车厢通过。 现已知第一个到达出口的是3 号车厢，请写出所有可能的

9、到达出口的车厢排列总数(不必给出每种排列) 。出口 1 2 3 4 5 S2. 将 N个红球和 M个黄球排成一行。例如:N=2,M=3 可得到以下6 种排法 : 红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题 : 当 N=4,M=3时有多少种不同排法?( 不用列出每种排法) NOIP2003 普及二问题求解 (每题 5 分，共 10 分) 1现在市场上有一款汽车A 很热销，售价是2 万美元。汽车A 每加仑汽油可以行驶20 英里。普通汽车每年大约行驶 12000 英里。油价是每加仑1 美元。不久我公司就要推出新款节油汽车B，汽车 B 每加仑汽油可以行驶30 英里。现在我们要为B

10、 制定价格 (它的价格略高于A)：我们预计如果用户能够在两年内通过节省油钱把B 高出 A 的价钱弥补回来，则他们就会购买B，否则就不会购买B。那么 B 的最高价格应为万美元。2无向图 G 有 16 条边，有 3 个 4 度顶点、 4 个 3 度顶点， 其余顶点的度均小于3，则 G 至少有个顶点。NOIP2004 普及1.一个家具公司生产桌子和椅子。现在有113 个单位的木材。每张桌子要使用20 个单位的木材，售价是30 元；每张椅子要使用16 个单位的木材，售价是20 元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖元钱。2.75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道

11、，乘宇宙飞船。已知其中20 人这三种东西都玩过，55 人至少玩过其中的两种。若每样乘坐一次的费用是5 元，游乐场总共收入700，可知有名儿童没有玩过其 中任何一种。NOIP2005 普及1. 将数组 32, 74, 25, 53, 28, 43, 86, 47中的元素按从小到大的顺序排列，每次可以交换任意两个元素， 最少需要交换次。2. 有3 个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈5 名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3 个小组中分别选出3 位组长，一位同学最多只能担任一个小组的组长，共有种选择方案。NOIP2006 普

12、及1 （寻找假币） 现有 80 枚硬币， 其中有一枚是假币， 其重量稍轻，所有真币的重量都相同， 如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第 1 次的称重方法。 请写出你的 结果：。2（取石子游戏）现有 5 堆石子, 石子数依次为 3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论 乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：。NOIP2007 普及二、问题求解（共2 题，每题 5 分，共计10 分） 。1、 （子集划分）将

13、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

14、 条南北向的纵街，5 条东西向的横街。现要从西南角的A 走到东北角的B，最短的走法共有多少种？_ B A NOIP2008 普及1书架上有4 本不同的书A、B、C、D。其中 A 和 B 是红皮的， C 和 D 是黑皮的。把这4 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足 A 必须比 C 靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有_种摆法。2有 6 个城市，任何两个城市之间都有一条道路连接，6 个城市两两之间的距离如下表所示，则城市1 到城市 6 的最短距离为 _。城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 城市 1 0 2 3 1 12 15

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 NOIP2009 普及1. 小陈现有2 个任务A， B 要完成，每个任务分别有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5 。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如 a2-b2-a3-b3 是合法的，而a2-b3-a3-b2 是不合法的。小陈从B 任务的b1 步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有_ 种。2. 有如下的一段程序：1. a:=1; 2. b:=a; 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7. g:=a*f+c; 现在要把这段程序分配到若干台（数量充足）用电缆连接的PC 上做并行执行。每台PC 执行其中的某几个语句，并可随时通过电缆与其他PC