SharedCourses/docs/undergraduate/数据科学与工程学院/2025-2026学年上学期前计算机科学拔尖基地遴选笔试.md

title
2025-2026学年上学期前计算机科学拔尖基地遴选笔试

一、选择题

:::info 选择题共10道 未展示部分是高考数学排列组合的内容，并且难度低于全国卷高考 :::

1. 有170多人参加人才培训，其中党员比非党员多三倍，党员中有百分之十的人会分配到包括甲在内的12个队伍中，且每个队伍至少一人。
   问：甲队伍中有两个人的概率的范围？

   答案

   \frac{11}{78}

   设总人数为 P，党员人数为 M，非党员人数为 N。 根据题意，P > 170，M = 4N，因此 P = 5N。P 必须是5的倍数。 分配到12个队伍中的党员人数为 X = 0.1M = 0.4N = \frac{2N}{5}。 由于 X 必须是整数，N 必须是5的倍数。因此，P 必须是25的倍数。 180 > P > 170 且是25的倍数，所以 P 的值为 175。

   P = 25k \implies N=5k \implies X=2k。 25k = 175 \implies k = 7，所以 X 的值为 14。

   将 X 名党员分配到12个队伍，每个队伍至少一人，总方法数为组合数 C(X-1, 11)。
   要使甲队伍恰好有两人，需要将剩下的 X-2 人分配到其余11个队伍，每个队伍至少一人，方法数为 C((X-2)-1, 11-1) = C(X-3, 10)。
   因此，甲队伍中有两人的概率为：

   $ P(X) = \frac{C(X-3, 10)}{C(X-1, 11)} = \frac{11 \cdot (X-12)}{(X-1)(X-2)}

   代入得：\frac{11}{78}

   ---

2. 六人参加面试，并满足以下条件：

   • 录取乙 当且仅当 录取丙
   • 甲、戊、己 中恰有两人被录取
   • 丁 和 丙 恰有一人被录取
   • 丁 和 甲 恰有一人被录取
   • 甲 和 乙 至少一人被录取

   问：最终录取了多少人？

   答案

   \text{设甲、乙、丙、丁、戊、己分别为 } a, b, c, d, e, f \in \{0,1\}\text{，}\\ \text{其中 } 1 \text{ 表示被录取，} 0 \text{ 表示未被录取。给定条件等价于：}

   $
   \begin{cases}
   b = c & \text{(1)} \\
   a + e + f = 2 & \text{(2)} \\
   d + c = 1 & \text{(3)} \\
   d + a = 1 & \text{(4)} \\
   a + b \geq 1 & \text{(5)}
   \end{cases}
   

   \text{由 (3) 和 (4) 可得：} d + c = 1,\quad d + a = 1 \implies c = a. \\ \text{结合 (1)，得：}a = b = c. \\ \text{代入 (5)：} a + b \geq 1 \implies 2a \geq 1. \\ \text{由于 } a \in \{0,1\},\text{ 故 } a = 1, \text{ 进而 } b = c = 1. \\ \text{由 (4): } d + a = 1 \implies d + 1 = 1 \implies d = 0. \\ \text{由 (2): } a + e + f = 2 \implies 1 + e + f = 2 \implies e + f = 1. \\ \text{即 } e \text{ 和 } f \text{ 中恰有一个为 } 1. \\ \text{综上，被录取者为 } a = 1,\ b = 1,\ c = 1,\ e + f = 1 \implies \text{共 } 4 \text{ 人被录取。}

   ---

3. (待定)某校食堂发生一起食物中毒案件，现有四人口供：

   • 甲：这起事件是由学校食物不合格引起的
   • 乙：如果这起事件是由学校食物不合格引起的，那么学校的食物监管出现问题
   • 丙：学校食堂食物不合格，但学校的食物监管没有出现问题
   • 丁：学校食堂食物合格，但学校食物监管有问题

   以上四人中只有一人的话是真的。

   选项：

   A. 乙为真，但不存在食物监管问题
   B. 乙为真，学校的食物监管有问题
   C. 甲为真
   D. 丁为真

   答案

二、填空题

1. 一个小猴子边上有100根香蕉，它要走过50米才能到家，每次最多搬50根香蕉（多了就被压死），每走1米就要吃掉一根。
   问：它最多能把多少根香蕉搬到家里？

   答案

   \text{16 根}

   1. 当香蕉数量大于 50 根时: 猴子往返运输。为了将100根香蕉从A点运到B点，需要走3趟（运50，返回，再运50）。因此，每前进 1 米，消耗 3 根香蕉。
   2. 从100根香蕉开始，每前进1米少3根。100 - 3x <= 50，解得 x >= 50/3，当 x=16 时，还剩 52 根香蕉。
   3. 当香蕉数量小于 50 根时: 在17米处，有49根香蕉。剩下的路程为 50 - 17 = 33 米。猴子可以一次性背上所有香蕉，只需走一趟。故最终结果为 49 - 33 = 16 根。

   ---

2. 8个乒乓球，其中一个较重，有一个天平秤。
   问：至少几次能够找出重的那个乒乓球？

   答案

   \text{2次}

   使用二分法

   1. 分为 4 个的两组, 找出重的那组
   2. 分为 2 个的两组, 找出重的那组
   3. 两个比较, 拿出重的

   ---

3. 25匹马，5条跑道，找最快的3匹马，需要跑几次？

   答案

   \text{7次}

   首先将25匹马分成5组，每组5匹，各跑一次。记录下每组的排名。
   然后将5组的冠军放在一起跑一次。这次比赛后，跑得最快的马就是总冠军。
   假设冠军赛的排名是 A1 > B1 > C1 > D1 > E1 (A,B,C,D,E为组名，1,2,3为组内排名)
   - 总冠军是 A1 - 第二、三名只可能在以下马匹中：A2, A3 (A组的二、三名), B1, B2 (B组的一、二名), C1 (C组的冠军) - 将这5匹马进行最后一次比赛，取前两名。这两匹马就是总排名的第二和第三

   ---

4. 有2个鸡蛋，从100层楼上往下扔，测试鸡蛋硬度。 若鸡蛋在第 n-1 层不碎，在第 n 层碎，则临界点为 n 层。
   问：在最坏情况下，最小的尝试次数是多少？

   答案

   \text{14次}

   使用动态规划求解。

   设 m 为最少尝试次数。用第一个鸡蛋进行第一次尝试，如果它在第 x 层碎了，就需要用第二个鸡蛋从第1层到第 x-1 层逐一尝试，最坏情况需要 x-1 次。总次数为 1 + (x-1) = x 次。 如果没碎，我们就在更高的楼层用同样的方法尝试。

   我们求解等价问题：给定 m 次机会，最多能测试多少层楼？

   • 第一次在 m 层扔。如果碎了，用剩下 m-1 次机会测试1到 m-1 层。
   • 如果没碎，则第二次在 m + (m-1) 层扔。碎了，用剩下 m-2 次机会测试 m+1 到 m+(m-1)-1 层。
   • 最多能测试的总楼层数为 m + (m-1) + (m-2) + ... + 1 = \frac{m(m+1)}{2}。

   于是问题变为解不等式 \frac{m(m+1)}{2} \ge 100，解得最小的整数 m 为14。

   ---

5. 小明是某市集团总裁，每天坐火车回家，司机准时到站接他。 有一天司机晚了30分钟出发，小明没等到车，便步行回家。途中遇到司机的车，立即上车返回家中。到家后，妻子说：“你足足比平常晚到了22分钟。”
   问：小明步行了多久？

   答案

   \text{26分钟}

   司机晚出发30分钟，如果按照原计划去火车站接人再回家，那么小明也应该晚到家30分钟，但实际上小明只晚到家22分钟，这说明整个过程比 "司机去火车站接人" 节省了 30 - 22 = 8 分钟。
   因此说明司机没有开到火车站，而是在半路就接到了小明。节省的时间等于汽车从相遇地点开到火车站，再从火车站返回到相遇地点的时间，故单程时间是 8 \div 2 = 4 分钟。

   这意味着，司机在离正常接站时间还差 4 分钟时与小明相遇，而司机晚出发30分钟，所以他本应在 T + 30 分钟时到达车站（T为火车到站时刻），相遇时刻是 (T + 30) - 4 = T + 26 分钟

   所以，小明步行了26分钟。

三、简答题

1. 有一枚不均匀的硬币，掷出正面朝上的概率为 70%，反面为 30%。如何高效地构造一个概率为 50% 的公平事件？

   答案

   1. 将硬币连续抛掷两次。
   2. 会产生四种可能的结果：正正、反反、正反、反正。
   3. 如果两次结果相同，则忽略这次实验，重新抛掷。
   4. 如果两次结果不同，则根据第一次的结果来判定最终结果。

   另请参阅: 冯诺伊曼提取器

   ---

2. 掷一枚均匀的骰子，连续掷出两个6点时，期望的尝试次数是多少？

   答案

   \text{42次}

   设 E 为达成目标（连续两个6）所需的期望投掷次数。
   定义两个状态：

   • 状态0: 当前没有连续的6。设从这个状态达到目标的期望次数为 E_0。
   • 状态1: 上一次投掷是6。设从这个状态达到目标的期望次数为 E_1。

   求解的目标是 E = E_0。

   建立方程：

   1. 从状态0开始：

      • 投掷一次（消耗1次）。
      • 有 1/6 的概率掷出6，进入状态1。
      • 有 5/6 的概率掷出非6，回到状态0。
      • 所以，E_0 = 1 + \frac{1}{6}E_1 + \frac{5}{6}E_0

   2. 从状态1开始：

      • 投掷一次（消耗1次）。
      • 有 1/6 的概率掷出6，达成目标（后续期望为0）。
      • 有 5/6 的概率掷出非6，之前累积的6作废，回到状态0。
      • 所以，E_1 = 1 + \frac{1}{6}(0) + \frac{5}{6}E_0

   解这个方程组：

   • 从(1)得: \frac{1}{6}E_0 = 1 + \frac{1}{6}E_1 \implies E_0 = 6 + E_1
   • 将(2)代入: E_1 = 1 + \frac{5}{6}(6 + E_1) = 1 + 5 + \frac{5}{6}E_1 = 6 + \frac{5}{6}E_1
   • \frac{1}{6}E_1 = 6 \implies E_1 = 36
   • 最后，E_0 = 6 + E_1 = 6 + 36 = 42。

   ---

3. 随机取三段长度均小于1的线段，这三条线段能组成一个三角形的概率是多少？

   答案

   \frac{1}{2}

   这是一个几何概率问题。

   1. 设三条线段的长度分别为 x, y, z。由于每条线段的长度都是在 [0, 1) 范围内随机取的，这三维的随机变量构成了一个边长为1的立方体。这个立方体的体积为 1 \times 1 \times 1 = 1，代表了所有可能结果的样本空间。

   2. 三条线段能组成三角形，必须满足三角不等式：

      • x + y > z
      • x + z > y
      • y + z > x

   3. 计算上述条件的补集会更简单。无法组成三角形的条件是：

      • x + y \le z
      • 或 x + z \le y
      • 或 y + z \le x

   4. 计算过程：

      • 这三个失败条件所定义的区域在单位立方体中是三个几乎不相交的角（仅在零体积的边界上相交）。
      • 我们计算其中一个区域的体积，例如 x + y \le z。通过三重积分 \int_0^1\int_0^1\int_0^1 I(x+y \le z) \,dx\,dy\,dz 可以得到该区域体积为 1/6。
      • 由于对称性，另外两个区域的体积也都是 1/6。
      • 因此，无法组成三角形的总概率是 1/6 + 1/6 + 1/6 = 3/6 = 1/2。

   5. 最终概率：能组成三角形的概率是 1 - P(\text{失败}) = 1 - 1/2 = 1/2。