历届问题求解试题(noip1995至noip2015)

1、1995NOIP01 普及组. 2 1996NOIP02 普及组. 2 1997NOIP03 普及组. 2 1998NOIP04 普及组. 2 1999NOIP05 普及组. 2 2000NOIP06 普及组. 3 2001NOIP07 普及组. 3 2002NOIP08 普及组. 4 2003NOIP09 普及组. 4 2004NOIP10 普及组. 4 2005NOIP11 普及组. 4 2006NOIP12 普及组. 5 2007NOIP13 普及组. 5 2008NOIP14 普及组. 6 2009NOIP15 普及组. 6 2010NOIP16 普及组. 7 2011NOIP17 普及组. 7 2012NOIP18 普及组. 8 2013NOIP19 普及组. 8 2014NOIP20 普及组. 8 2015NOIP21 普及组. 9 1995NOIP01 提高组. 9 1996NOIP02 提高组. 9 1997NOIP03 提高组. 9 1998NOIP04 提高组. 9 1999NOIP05 提高组. 10 2000NOIP06 提高组. 10 2001NOIP07 提

2、高组. 10 2002NOIP08 提高组. 10 2003NOIP09 提高组. 10 2004NOIP10 提高组. 11 2005NOIP11 提高组. 11 2006NOIP12 提高组. 11 2007NOIP13 提高组. 12 2008NOIP14 提高组. 12 2009NOIP15 提高组. 12 2010NOIP16 提高组. 13 2011NOIP17 提高组. 13 2012NOIP18 提高组. 14 2013NOIP19 提高组. 14 2014NOIP20 提高组. 15 2015NOIP21 提高组. 15 1995NOIP01 普及组普及组 1996NOIP02 普及组普及组 1997NOIP03 普及组普及组 1998NOIP04 普及组普及组 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、3 项 起（即 N=1）都满足 U n+2 =Un+1+Un 。试对数列 12，22，32，n2,求 K 和 a1,a2, ,aK 使得（A）式成立。 7% 2某班有 50 名学生，每位学生发一张调查卡，上写 a，b，c 三本书的书名，将读过的书 打，结果统计数字如下： 只读 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-1X0的步骤：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=1998， K=3 时，XJXJ-1X0 之值。 1999NOIP05 普及组普及组 1、在磁盘

4、的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图 该图表达了 A 盘的目录结构：D1，Dll，D2 均表示子目录的名字。在这里，根目录的 度为 2，D1 子目录的度为 3，D11 子目录的度为 4，D12，D2，D111，D112，D113 的度均为 1。 不考虑子目录的名字，则可简单的图示为如下所示的树结构： 若知道一个磁盘的目录结构中，度为 2 的子目录有 2 个，度为 3 的子目录有 1 个，度为 4 的子目录有 3 个。 试问：度为 1 的子目录有几个？ 2、公式推导（10 分） 根据 Nocomachns 定理，任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和。 例如： 13 1 23 3 5 33 7 9 11 43= 13+15+17+19 在这里，若将每一个式中的最小奇数称为 X，那么当给出 n 之后，请写出 X 与 n 之间的关 系表达式： 2000NOIP06 普及组普及组 1已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 2有 2n 的一个长方形方格，用一个 12 的骨牌铺满

5、方格。例如 n=3 时，为 23 方格。 此时用一个 12 的骨牌铺满方格，共有 3 种铺法： 试对给出的任意一个 n（n0），求出铺法总数的递推公式。 2001NOIP07 普及组普及组 1、在 a,b,c,d,e,f 六件物品中，按下面的条件能选出的物品是： _ a,b 两样至少有一样 a,d 不能同时取 a,e,f 中必须有 2 样 b,c 要么都选，要么都不选 c,d 两样中选一样 若 d 不选，则 e 也不选 2、平面上有三条平行线，每条直线上分别有 7，5，6 个点，且不同直线上三个点 都不在同一直线上。 问用这些点为顶点，能组成多少个不同三角形？ ( ) 2002NOIP08 普及组普及组 1. 如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每个车厢可以向 左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3 号车厢，请写出所有 可能的到达出口的车厢排列总数(不必给出每种排列)。 出口 1 2 3 4 5 S 2.将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排法: 红红黄黄黄 红

6、黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法) 2003NOIP09 普及组普及组 1 现在市场上有一款汽车 A 很热销， 售价是 2 万美元。 汽车 A 每加仑汽油可以行驶 20 英里。 普通汽车每年大约行驶 12000 英里。油价是每加仑 1 美元。不久我公司就要推出新款节油汽车 B，汽车 B 每加仑汽油可以行驶 30 英里。现在我们要为 B 制定价格(它的价格略高于 A)：我们 预计如果用户能够在两年内通过节省油钱把 B 高出 A 的价钱弥补回来，则他们就会购买 B，否 则就不会购买 B。那么 B 的最高价格应为 万美元。 2无向图 G 有 16 条边，有 3 个 4 度顶点、4 个 3 度顶点，其余顶点的度均小于 3，则 G 至少有 个顶点。 2004NOIP10 普及组普及组 1、一个家具公司生产桌子和椅子。现在有 113 个单位的木材。每张桌子要使用 20 个单位的木材，售价是 30 元；每张椅子要使用 16 个单位的木材，售价是 20 元。 使用已有的木材生产桌椅（不一定要把木材用光） ，最多可

7、以卖 元钱。 2、75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已 知其中 20 人这三种东西都玩过，55 人至少玩过其中的两种。若每样乘坐一次的费 用是 5 元，游乐场总共收入 700，可知有 名儿童没有玩过其中任何一种。 2005NOIP11 普及组普及组 1. 将数组32, 74, 25, 53, 28, 43, 86, 47中的元素按从小到大的顺序排列， 每次可以交换任 意两个元素，最少需要交换次。 2. 有 3 个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈 5 名同 学，已知 张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果 要在 3 个小组中分别选出 3 位组长，一位同学最多只能担任一个小组的组长，共有种 选择方案。 2006NOIP12 普及组普及组 1 （寻找假币） 现有 80 枚硬币，其中有一枚是假币，其重量稍轻，所有真币的 重量都相同，如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？ 你 还 要 指 出 第 1 次 的 称 重 方 法 。 请 写 出 你 的 结 果 ： _。 2 （取石子游

8、戏） 现有 5 堆石子,石子数依次为 3，5，7，19，50，甲乙两人 轮流从任一堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获 胜。 甲先取， 问甲有没有获胜策略 （即无论 乙怎样取， 甲只要不失误， 都能获胜） ？ 如果有，甲第一步应该在哪一堆里取多少？请写出你的结果： _。 2007NOIP13 普及组普及组 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)。 当 n=6，r=3 时，S(6,3)=_。 （提示：先固定一个数，对于其余的 5 个数考虑 S(5,3)与 S(5,2)，再分这两种情 况对原固定的数进行分析。 ） 2、 （最短路线）某城市的街道是一个很规整的矩形网络（见下图） ，有 7 条南北向 的纵街，5 条东西向的横街。

9、现要从西南角的 A 走到东北角的 B，最短的走法共有 多少种？_ B A 2008NOIP14 普及组普及组 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 城市 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 2009NOIP15 普及组普及组 1小陈现有 2 个任务 A，B 要完成，每个任务分别有若干步骤如下：A=a1-a2-a3， B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他 可以在做完手中任务的当前步骤后， 切换至另一个任务， 从上次此任务第一个未做的步骤继续。 每 个 任 务 的 步 骤 顺 序 不 能 打 乱 ， 例 如 a2-b2-a3-b3 是 合 法 的 ， 而 a2-b3-a3-b2是不合法的。小陈从 B

《历届问题求解试题(noip1995至noip2015)》由会员第***分享，可在线阅读，更多相关《历届问题求解试题(noip1995至noip2015)》请在金锄头文库上搜索。