信息学选拔试题及答案.doc

信息学兴趣小组选拔试题 班级 姓名 学号 成绩 1 有红 黄 黑 白四色球各一个 放置在一个内存编号为 1 2 3 4 四个格子的盒中 每个格子放置一只球 它们的顺序不知 甲 乙 丙三人猜测放置顺序如下 甲 黑编号 1 黄编号 2 乙 黑编号 2 白编号 3 丙 红编号 2 白编号 4 结果证明甲乙丙三人各猜中了一半 写出四色球在盒子中放置情况及推理过程 写出四色球在盒子中放置情况及推理过程 2 列举一个算法 使算法的解能对应相应的问题 例如 设问题为 学生答题 答对一题可得 10 分 答错一题则要扣去 5 分 输入答对 的题数 M 与答错的题数 N 求最后得分 S 是多少 列举出相应算法为 X 10 Y 5 READ M N S X M Y N 现有以下问题 用五角钱换成 5 分 2 分与 1 分的硬币 可有多少种换法 请列出该问题的算法 请列出该问题的算法 3 下图中用点表示城市 点与点之间的联系表示城市间的道路 D C A B 试问 能否找出一条从 A 城市出发 经过图中所有道路一次后又回到出发点的通路来 能否从 A 出发 找出去每个城市且只去一次的通路来 若能 则写出通路 否则说明理由 4 一个将角编了号的正三角形可以绕着外心 O 中心 逆时针旋转 1200 如下图所示 1 3 0 0 2 3 1 2 图一 图二 如果将这一旋转用字母 a 来表示 看作运算对象 同时用 aa 或 a2 表示旋转 E F a 1200后再旋转 1200 也就是说将连续运动看作乘法运算 那么三角形状态 可 简称为元素 即可与运动表达式关联起来 请回答 如果将图一的原始三角形连续旋转 1200N 次 简单地表示为 an N 为任意自 然数 试求 an 的值 指三角形旋转后的结果状态 如果将下面的旋转看作是 a 的逆元素 记为 a 1 则有 a 1 a2 试求 a n 3 1 0 0 1 2 2 3 图三 5 已知一个数列 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 式成立 6 某班有 50 名学生 每位学生发一张调查卡 上写 a b c 三本书的书名 将读过 的书打 结果统计数字如下 只读 a 者 8 人 只读 b 者 4 人 只读 c 者 3 人 全部读过的有 2 人 读过 a b 两本书的有 4 人 读过 a c 两本书的有 2 人 读过 b c 两本书的有 3 人 6 1 读过 a 的人数是 2 一本书也没有读过的人数是 7 在磁盘的目录结构中 我们将与某个子目录有关联的目录数称为度 例如下图 该图表达了 A 盘的目录结构 D1 Dll D2 均表示子目录的名字 在这里 根 目录的度为 2 D1 子目录的度为 3 D11 子目录的度为 4 D12 D2 D111 D112 D113 的度均为 1 不考虑子目录的名字 则可简单的图 示为如下所示的树结构 若知道一个磁盘的目录结构中 度为 2 的子目录有 2 个 度为 3 的子目录有 1 个 度为 4 的子目录有 3 个 试问 度为 1 的子目录有几个 8 根据 Nocomachns 定理 任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和 aa 例如 13 1 23 3 5 33 7 9 11 43 13 15 17 19 在这里 若将每一个式中的最小奇数称为 X 那么当给出 n 之后 请写出 X 与 n 之间 的关系表达式 9 有 2 n 的一个长方形方格 用一个 1 2 的骨牌铺满方格 例如 n 3 时 为 2 3 方 格 此时用一个 1 2 的骨牌铺满方格 共有 3 种铺法 试对给出的任意一个 n n 0 求出铺法总数的递推公式 10 在 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 也不选 11 平面上有三条平行直线 每条直线上分别有 7 5 6 个点 且不同直线上三个点都不 在同一条直线上 问用这些点为顶点 能组成多少个不同三角形 12 如下图 有一个无穷大的的栈 S 在栈的右边排列着 1 2 3 4 5 共五个车厢 其中每个 车厢可以向左行走 也可以进入栈 S 让后面的车厢通过 现已知第一个到达出口的是 3 号车厢 请写出所有可能的到达出口的车厢排列总数 不必给出每种排列 出口 1 2 3 4 5 S 13 将 N 个红球和 M 个黄球排成一行 例如 N 2 M 3 可得到以下 6 种排法 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题 当 N 4 M 3 时有多少种不同排法 不用列出每种排法 14 现在市场上有一款汽车 A 很热销 售价是 2 万美元 汽车 A 每加仑汽油可以 行驶 20 英里 普通汽车每年大约行驶 12000 英里 油价是每加仑 1 美元 不久我 公司就要推出新款节油汽车 B 汽车 B 每加仑汽油可以行驶 30 英里 现在我们要 为 B 制定价格 它的价格略高于 A 我们预计如果用户能够在两年内通过节省油钱 把 B 高出 A 的价钱弥补回来 则他们就会购买 B 否则就不会购买 B 那么 B 的最 高价格应为 万美元 15 无向图 G 有 16 条边 有 3 个 4 度顶点 4 个 3 度顶点 其余顶点的度均小于 3 则 G 至少有 个顶点 16 一个家具公司生产桌子和椅子 现在有 113 个单位的木材 每张桌子要使用 20 个单位 的木材 售价是 30 元 每张椅子要使用 16 个单位的木材 售价是 20 元 使用已有的木材 生产桌椅 不一定要把木材用光 最多可以卖 元钱 17 75 名儿童到游乐场去玩 他们可以骑旋转木马 坐滑行铁道 乘宇宙飞船 已知其中 20 人这三种东西都玩过 55 人至少玩过其中的两种 若每样乘坐一次的费用是 5 元 游乐场总共收入 700 可知有 名儿童没有玩过其中任何一种 18 将数组 32 74 25 53 28 43 86 47 中的元素按从小到大的顺序排列 每次可以交换任 意两个元素 最少需要交换 次 19 有 3 个课外小组 物理组 化学组和生物组 今有张 王 李 赵 陈 5 名同学 已知张 王为物理组成员 张 李 赵为化学组成员 李 赵 陈为生物组成员 如 果要在 3 个小组分别选出 3 位组长 一位同学最多只能担任一个小组的组长 共有 种选择方案 20 寻找假币 现有 80 枚硬币 其中有一枚是假币 其重量稍轻 所有真币的重量都相 同 如果使用不带砝码的天平称重 最少需要称几次 就可以找出假币 你还要指出 第 1 次的称重方法 请写出你的结果 21 取石子游戏 现有 5 堆石子 石子数依次为 3 5 7 19 50 甲乙两人轮流从任一 堆中任取 每次只能取自一堆 不能不取 取最后一颗石子的一方获胜 甲先取 问甲有没有获胜策略 即无论乙怎样取 甲只要不失误 都能获胜 如果有 甲第 一步应该在哪一堆里取多少 请写出你的结果 答案 1 四色球在盒子中放置的情况为 4 1234 黑红白黄 推理过程是 4 假定 黑为 1 黄为 2 黑为 2 白为 3 红为 2 白为 4 黄为 4 2 列出的算法是 K 0 FOR i 0 TO 10 DO K K 50 I 5 DIV 2 1 ENDFOR 3 能 例如 A D C E A F C B A 不能 本题的回答要点如下 要到达 D E F B 四个点之一 必须由 A C 出发才可 因为 A C 只可能出发一次 所以这样的通路不存在 4 a 当 n MOD 3 1 时 a2 当 n MOD 3 1 时 a2 当 n MOD 3 2 时 a 当 n MOD 3 2 时 a3 当 n MOD 3 0 时 a3 当 n MOD 3 0 时 5 当 K 3 a1 a2 ak为 a1 3 a2 3 a3 1 时 对数列 122232 n2 A 成立 6 读过 a 的人数是 12 人 2 一本书也没读过的人数是 30 人 7 度为 1 的子目录有 9 个 8 给出 n 之后 X 与 n 之间的关系表达式为 N2 N 1 9 对给出的任意一个 n n 0 用 F n 表示其铺法的总数的递推公式为 F 1 1 F 2 2 F n F n 2 F n 1 n 3 10 在 a b c d e f 六件物品中 按条件能选出的物品