普及历年问题求解试题（98-02） 【普及组 1998】 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）都满足 U n+2 =Un+1+Un 。试对数列 12，22，32，…，n2,…求 K 和 a1,a2, …,aK 使得（A）式成立。 2．某班有 50 名学生，每位学生发一张调查卡，上写 a，b，c 三本书的书名，将读过的书打 ，结果统计数字如下： 只读 a 者 8 人；只读 b 者 4 人；只读 c 者 3 人；全部读过的有 2 人；读过 a，b 两本书的有 4 人；读过 a，c 两本书的有 2 人；读过 b，c 两本书的有 3 人； （1）读过 a 的人数是 （2）一本书也没有读过的人数是 3．任给自然数 n，k， 1≤K≤9 ，按如下计算步骤求序列 XJXJ-1……X0 的步骤： MOD K （1） j=0 （2） 如果 N>=K 则转第 3 步，否则转第 7 步 （3） Xj = N （4） N =N DIV K （5） j=j+1 （6） 回第 2 步 （7） Xj = N （8） 结束 {div 表示整数除法，结果取整数； mod 表示整除取余数} 试求当： N=1998， K=3 时，XJXJ-1……X0 之值。值为 。 【普及组 1999】 1．在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图 该图表达了 A 盘的目录结构：D1，Dll，…，D2 均表示子目录的名字。在这里，根目 录的度为 2，D1 子目录的度为 3，D11 子目录的度为 4，D12，D2，D111，D112，D113 的 度均为 1。不考虑子目录的名字，则可简单的图示为如下所示的树结构： 若知道一个磁盘的目录结构中，度为 2 的子目录有 2 个，度为 3 的子目录有 1 个，度为 4 的子目录有 3 个。 试问：度为 1 的子目录有几个？ 1/5 

【普及组 2000】 1.已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 2.有 2×n 的一个长方形方格，用一个 1×2 的骨牌铺满方格。例如 n=3 时，为 2×3 方格。 此时用一个 1×2 的骨牌铺满方格，共有 3 种铺法： 试对给出的任意一个 n(n〉0)，求出铺法总数的递 推公式。 【普及组 2001】 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 个点，且不同直线上三个点都不在同 一条直线上。问用这些点为顶点，能组成多少个不同三角形？ 【普及组 2002】 1. 如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每个车厢可以向左行 走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3 号车厢，请写出所有可能的到达 出口的车厢排列总数(不必给出每种排列)。 出口← ← 1 2 3 4 5 S↓ 2.将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 10 种排法: 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 黄黄红红黄 黄黄红黄红 黄红黄黄红 红黄黄黄红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法) 【普及组 2003】 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 至 少有 个顶点。 2/5 

【普及组 2004】 1． 一个家具公司生产桌子和椅子。现在有 113 个单位的木材。每张桌子要使用 20 个单位 的木材，售价是 30 元；每张椅子要使用 16 个单位的木材，售价是 20 元。使用已有的木材 生产桌椅（不一定要把木材用光），最多可以卖 元钱。 2． 75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中 20 人这三种东西都玩过，55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元，游乐 场总共收入 700，可知有 名儿童没有玩过其中任何一种。 【普及组 2005】 1． 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以 交换任意两个元素，最少需要交换 次。 2． 有 3 个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈 5 名同学，已知 张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在 3 个小组中分别选出 3 位组长，一位同学最多只能担任一个小组的组长，共有 种选择 方案。 【普及组 2006】 1．（寻找假币） 现有 80 枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相 同，如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第 1 次 的称重方法。请写出你的 结果： 。 2．（取石子游戏） 现有 5 堆石子,石子数依次为 3，5，7，19，50，甲乙两人轮流从任一 堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。甲先取，问甲有 没有获胜策略（即无论 乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在 哪一堆里取多少？请写出你的结果： 。 【普及组 2007】 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)，再分这两种情况对原 固定的数进 行分析）。 。 3/5 

2．（最短路线）某城市的街道是一个很规整的矩形网格（见下图），有 7 条南北向的纵街，5 条东西向的横街。现要从西南角的 A 走到东北角的 B，最短的走法共有 B 种？ A 【普及组 2008】 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 城市 2 城市 3 城市 4 城市 5 城市 6 0 2 3 1 12 15 2 0 2 5 3 12 3 2 0 3 6 5 1 5 3 0 7 9 12 3 6 7 0 2 15 12 5 9 2 0 【普及组 2009】 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．有如下的一段程序： a=1; b=a; d=-a; e=a+d; c=2*d; f=b+e-d; g=a*f+c; 1. 2. 3. 4. 5. 6. 7. 现在要把这段程序分配到若干台（数量充足）用电缆连接的 PC 上做并行执行。每台 PC 执行 4/5 

其中的某几个语句，并可随时通过电缆与其他 PC 通讯，交换一些中间结果。假设每台 PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 5 单 位时间内执行完毕。注意：任意中间结果只有在某台 PC 上已经得到，才可以被其他 PC 引用。 例如若语句 4 和 6 被分别分配到两台 PC 上执行，则因为语句 6 需要引用语句 4 的计算结果， 语句 6 必须在语句 4 之后执行。 【普及组 2010】 1．LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编 码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典 中，并用于后继信息的编码。 举例说明，考虑一个待编码的信息串："xyx yy yy xyx"。初始词典只有 3 个条目，第一个 为 x，编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3；于是串"xyx"的编码为 1-2-1（其中-为编码分隔符），加上后面的一个空格就是 1-2-1-3。但由于有了一个空格， 我们就知道前面的"xyx"是一个单词，而由于该单词没有在词典中，我们就可以自适应的把 这个词条添加到词典里，编码为 4，然后按照新的词典对后继信息进行编码，以此类推。于 是，最后得到编码：1-2-1-3-2-2-3-5-3-4。 现在已知初始词典的 3 个条目如上述，则信息串"yyxy xx yyxy xyx xx xyx"的编码是 。 2．队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素 1、2、3 入队， 元素 1 出队后，此刻的队列快照是"2 3"。当元素 2、3 也出队后，队列快照是""，即为空。 现有 3 个正整数元素依次入队、出队。已知它们的和为 8，则共有 种可能的不同的 队列快照（不同队列的相同快照只计一次）。例如，"5 1"、"4 2 2"、""都是可能的队列快 照；而"7"不是可能的队列快照，因为剩下的 2 个正整数的和不可能是 1。 【普及组 2011】 1．每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有 效的。例如，0000000、01010011 都是有效的序列号，而 11111110 不是。那么，有效的序 列号共有 个。 2．定义字符串的基本操作为：删除一个字符＼插入一个字符和将一个字符修改成另外一个 字符这三种操作。将字符串Ａ变成字符串Ｂ的最少操作步数，称为字符串Ａ到字符串Ｂ的编 辑距离。字符串“ABCDEFG”到字符串“BADECG”的编辑距离为 。 【普及组 2012】 1． 如果平面上任取 n 个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中 点也是整点，那么 n 至少是 。 2． 在 NOI 期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有 5 名大陆选手和 5 名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选 手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有 种 不同的就坐方案。 注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。 5/5