历年复旦大学计算机考研复试机试真题
本文整理复旦大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
树的子结构
题目描述
输入两棵二叉树 $A$ 和 $B$，判断 $B$ 是不是 $A$ 的子结构。
(约定空树不是任意一个树的子结构)。
$B$ 是 $A$ 的子结构，即 $A$ 中有出现和 $B$ 相同的结构和节点值。
输入格式
两行，第一行是树 $A$ 的层序遍历序列，第二行是树 $B$ 的层序遍历序列。
使用 null 表示空节点。
输出格式
若 $B$ 是 $A$ 的子结构，输出 true，否则输出 false。
输入样例
3 4 5 1 2 null null null null null null
4 1 null null null
输出样例
true
解释
树 $A$ 的层序遍历序列为 3 4 5 1 2 null null null null null null，表示如下二叉树：
3
/ \
4 5
/ \
1 2
树 $B$ 的层序遍历序列为 4 1 null null null，表示如下二叉树：
4
/
1
树 $B$ 是树 $A$ 的子结构，因此输出 true。
数的间隙
题目描述
给一个序列 $a_1$ 到 $a_n$，和一个 $d$。
$a_n$ 数组排序后，后一个数减去前一个数的值称之为数的间隙，要求数的间隙均大于 $d$。
请问最多能从 $a_n$ 中选出多少满足条件的数字。
输入样例
5 2
1 3 6 10 15
输出样例
4
高尔夫比赛的森林砍树
题目描述
你被请来给一个要举办高尔夫比赛的树林砍树。
树林由一个 $m \times n$ 的矩阵表示， 在这个矩阵中：
-
$0$ 表示障碍，无法触碰
-
$1$ 表示地面，可以行走
-
比 $1$ 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 $1$ （即变为地面）。
你将从 $(0, 0)$ 点开始工作，返回你砍完所有树需要走的最小步数。
如果你无法砍完所有的树，返回 $-1$ 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
输入格式
第一行两个整数，分别是 $m$ 和 $n$。
接下来有 $m$ 行，每行 $n$ 个数，代表矩阵的行。
输入样例
3 3
1 2 3
0 0 4
7 6 5
输出样例
6
层次遍历
题目描述
给定一个二叉搜索树的 $先序遍历$，求其 $层次遍历$。
输入格式
第一行输入 $n$，表示树中有 $n$ 个节点。
接下来一行输入 $n$ 个数 $tree[i]$，表示树的 $先序遍历$。
$n < 100000$
$tree[i]$ 各不相同，但不一定为 $1$ - $n$ 的全排列，且一定可以构成二叉搜索树
输出格式
输出 $1$ 行 $n$ 个数，表示 $层次遍历$ 的结果
输入样例
4
3 1 2 4
输出样例
3 1 4 2
k小数
题目描述
给定一个行列均有序的二维数组 $A$，长宽均为 $n$，求 $A$ 的第 $k$ 小元素。
输入格式
第一行输入为 $n$，$k$，$T$。
其中，$n$ 为矩阵的大小，$k$ 为要求的第 $k$ 小的元素中的 $k$。
$T$ 为生成二维数组的系数，用法见公式。
$n \leq 13000$， $k \leq n \times n$。
接下来 $2$ 行各 $4$ 个数，分别为 $(a1，b1，c1，d1)$、$(a2，b2，c2，d2)$，其中：$a1 > b1$，$a2 > b2$。
与 $T$ 通过下面公式生成二维数组：
$a[x][y] = (a1 \times x + b1 \times \sin(c1 \times x + d1) + a2 \times y + b2 \times \sin(c2 \times y + d2)) \times T$ 的整数部分。
输出格式
输出 $1$ 行，表示询问的结果。
输入样例
4 4 4
1 0 0 0
1 0 0 0
输出样例
16