2025年北京航空航天大学计算机保研机试真题
本文整理北京航空航天大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
老鼠找食物的最短路径
题目描述
老鼠在寻找食物的过程中会记录移动的方向和距离。
移动的格式为 $x-y$，其中 $x$ 表示方向（$1$ 代表上，$2$ 代表下，$3$ 代表左，$4$ 代表右），$y$ 表示移动的距离。
输入以 $0-0$ 结束，表示老鼠找到了食物。
老鼠在碰到死路时会原路返回到分叉路口，探索下一个方向。
需要求解老鼠原路返回的最佳路径，最佳路径的描述是“不走回头路”，即没有折返过程。
输入格式
输入为一系列 $x-y$ 形式的移动指令，以 $0-0$ 结束。
例如：
1-1 3-1 1-1 2-1 4-2 1-2 4-1 1-1 2-1 3-1 1-1 0-0
输出格式
输出为老鼠原路返回的最佳路径，以 $x-y$ 形式表示。
例如：
2-3 3-1 2-1
学生身高分配问题
题目描述
有 $N$ 名学生在排队做核酸，编号为 $1, 2, 3, \ldots, N$，每名学生的身高都为整数。
当且仅当两名学生中间的学生身高都比他们矮时，两名学生方可看到对方。
现在，我们只知道最高的学生的身高是 $H$，剩余学生的身高未知。
但是，我们还知道这群学生之中存在着 $M$ 对关系，每对关系都指明了某两名学生 $A$ 和 $B$ 可以相互看见。
求每名学生的身高的最大可能值是多少。
输入格式
第一行输入整数 $N$, $H$, $M$，数据用空格隔开。
接下来 $M$ 行，每行两个整数 $A$ 和 $B$，代表学生 $A$ 和学生 $B$ 可以相互看见，数据用空格隔开。
输出格式
一共输出 $N$ 行数据，每行输出一个整数。
第 $i$ 行输出的整数代表第 $i$ 名学生可能的最大身高。
输入样例
9 185 5
1 3
5 3
4 3
3 7
9 8
输出样例
185
184
185
183
184
184
185
185
185
二进制序列操作
题目描述
给定一个二进制数（该二进制数的长度可能非常长），可以对该二进制数进行以下$4$种操作：
-
操作$ + $：将该二进制数加$ 1 $；
-
操作$ - $：将该二进制数减$ 1 $；
-
操作$ * $：将该二进制数乘$ 2 $；
-
操作$ / $：将该二进制数整除$ 2 $；
给定一个二进制数以及包含多个操作的操作序列，求经过运算后的二进制数。
输入格式
输入包含$3$行：
-
第一行包含$2$个正整数$ n $和$ m $：$ n $表示输入的二进制数的长度，$ m $表示输入的操作序列所包含操作的个数。
-
第二行为$1$个字符串，用来表示输入的二进制数。
该字符串的长度为$ n $，且该字符串的每一个字符是$ 0 $或者$ 1 $。
保证输入的二进制数不包含前导零。
- 第三行为$1$个字符串，用来表示输入的操作序列。
该字符串的长度为$ m $，且该字符串的每一个字符为$ + $、$ - $、$ * $、$ / $中的其中之一。
保证运算过程不会出现负数。
输出格式
输出仅包含$1$行：一个字符序列，表示经过运算后的二进制数（不包含前导零）；如果运算结果为$0$，则输出$0$即可。
输入样例
3 4
101
+*-/
输出样例
101
数组与堆
题目描述
在各类实现堆的代码中，通常选择使用一维数组去模拟堆的结构。
如果在堆构建好之后，将这个一维数组输出，可以观察到它们有一些有趣的性质。
我们将小根堆（最小堆）构建完成后所对应的数列，称为$小根堆数列$，大根堆（最大堆）构建完成后所对应的数列称为$大根堆数列$。
堆是最重要的数据结构之一，堆的类型有$2$种：$最大堆$和$最小堆$。
对于$最大堆$，父结点的键值总是大于或等于任何一个子节点的键值。
对于$最小堆$，父结点的键值总是小于或等于任何一个子节点的键值。
通常堆的实现是用一维数组完成的。
给定一个长度为$n$的一维数组，请判断该一维数组是否实现了$最大堆$或者$最小堆$。
如果该一维数组实现了$最大堆$，请输出$Max\ heap$；如果该一维数组实现了$最小堆$，请输出$Min\ heap$；如果该一维数组既没实现$最大堆$，也没实现$最小堆$，请输出$Not\ a\ heap!$。
输入格式
第一行是一个正整数$T$，表示数据组数。
接下来有$T$组数据：每组数据包含$2$行，其中第$1$行为正整数$n$，表示一维数组的长度；第$2$行为$n$个正整数（每个正整数之间用空格隔开），表示该一维数组。
输出格式
对于每一组数据，输出$Max\ heap$、$Min\ heap$或者$Not\ a\ heap!$，每个一行。
输入样例
3
6
2 3 4 5 6 7
3
5 2 1
9
3 1 4 1 5 9 2 6 5
输出样例
Min heap
Max heap
Not a heap!
数据范围
$T \leq 20$ $2 \leq n \leq 100000$ 数据保证不会有一维数组，既实现$最大堆$，又实现$最小堆$。
蓄水池储水
题目描述
一个蓄水池由多个不同高度的平台构成。
给定一个 $n$ 行 $m$ 列的二维矩阵，表示该蓄水池由 $n \times m$ 个平台构成，同时也表明了每个平台的坐标位置。
将此二维矩阵中第 $i$ 行第 $j$ 列的数字记为 $h_{i,j}$，表示处在第 $i$ 行第 $j$ 列的平台的高度。
在该蓄水池中，所有平台之间形成的空间凹陷区域可以用于储存水，求该蓄水池总共可以储存的水量。
输入格式
第一行，2个正整数 $n$, $m$，分别表示蓄水池所对应的二维矩阵的行数和列数。
接下来 $n$ 行，每行 $m$ 个非负整数，表示该行所包含的平台的高度。
输出格式
一行，仅包含1个非负整数，表示该蓄水池总共可以储存的水量。
输入样例
5 5
0 1 1 1 1
1 0 3 3 2
0 3 0 0 2
2 3 0 0 3
1 2 3 3 2
输出样例
9
数据范围
$1 \leq n, m \leq 200$ $0 \leq h_{i,j} \leq 10^4$