复旦大学计算机考研机试真题
历年复旦大学计算机考研机试真题
复旦大学计算机考研机试真题
在线评测地址：传送门
[size=3
]树的子结构
[size=2
]标题描述
入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是恣意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
[size=2
]输入格式
两行，第一行是树A，第二行是树B。
[size=2
]输特别式
若：B是A的子结构，输出true
否则：输出false。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
3
[size=2
]serial
0
[size=3
]数的间隙
[size=2
]标题描述
给一个序列a1到an，和一个d。
an数组排序后，后一个数减去前一个数的最大值不小于d。
请问最多能从an中选出多少满足条件的数字。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
3
[size=2
]serial
1
[size=3
]高尔夫比赛的森林砍树
[size=2
]标题描述
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表现， 在这个矩阵中：
- 0 表现障碍，无法触碰
- 1 表现地面，可以行走
- 比 1 大的数 表现有树的单位格，可以行走，数值表现树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你必要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单位格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树必要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少必要砍倒一棵树。
[size=2
]输入格式
第一行两个整数，分别是m和n
接下来有m行，每行n个数，代表矩阵的行。
[size=2
]输特别式
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
3
[size=2
]serial
2
[size=3
]层次遍历
[size=2
]标题描述
给定一个二叉搜索树的先序遍历，求其层次遍历。
[size=2
]输入格式
第一行输入n，表现树中有n个节点
接下来一行输入n个数tree，表现树的先序遍历。
n<100000
tree各不相同，但不一定为1-n的全排列，且一定可以构成二叉搜索树
[size=2
]输特别式
输出1行n个数，表现层次遍历的结果
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
3
[size=2
]serial
2
[size=3
]k小数
[size=2
]标题描述
给定一个行列均有序的二维数组A ，长宽均为n，求A的第K小元素
输出要求
[size=2
]输入格式
每组询问前两个数为n，k，T
接下来2
行各4
个数(a1,b1,c1,d1)(a2
,b2
,c2
,d2
)，表现该二维数组
n<
1;13
000
a[x][y]
1;的整数部门
a1>b1,a2
>b2
k<
1;n*n
[size=2
]输特别式
输出1行，表现询问的结果。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
3
[size=2
]serial
2
[size=3
]最快到达
[size=2
]标题描述
在一条长度为n-1 km的道路上，每1公里有一个路牌，路牌上有一个数字。你如今在第1块路牌的位置，你可以花1分钟前进1公里，也可以花1分钟飞到离你最近的与你当前所在地点路牌数字相同的地方，请问最快多久可以到达道路终点。
[size=2
]输入格式
第一行输入n（n<
1;1e5
）
接下来一行n个整数a，代表第1-n块路牌上的数字，-1e15
<a<1e15
[size=2
]输特别式
输出一个数，代表最少的时间。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
3
[size=2
]serial
3
[size=3
]最大团队体现值
[size=2
]标题描述
某公司在雇用工程师来组建一个团队。现有 n 个工程师进行应聘，每个应聘工程师有速度和服从两个属性。
求由最多 k 个工程师组建的团队的最大要现值。
团队体现值定义为：一个团队中“所有工程师的速度和”乘以“他们中服从的最小值”。
请你返回该团队的最大团队体现值，由于答案可能很大，请你返回结果对 10^9^ 
3
; 7
取余后的结果。
[size=2
]输入格式
第一行：n。表现工程师的人数
第二行：n个正整数。分别表现n个工程师的速度
第三行：n个正整数。分别表现n个工程师的服从
第四行：k。表现最多选择k名工程师
[size=2
]输特别式
最大团队体现值
[size=2
]输入样例
- 6
- 2
- 10 3
- 1 5
- 85
- 4
- 3
- 9 7
- 2
- 2
]输出样例
[size=2
]year
2
02
2
[size=2
]serial
0
[size=3
]字符串编辑间隔
[size=2
]标题描述
标题描述：给定两个字符串A和B，求字符串A至少经过多少步字符利用变成字符串B。
比如eat变成tea。对于第一个字符，e !
1; a，以是要想让这两个字符相等，有三种可以选择的办法
修改字符，将e直接变成a，必要走1步。
插入字符，在e的前面插入a，也必要走1步。
删除字符，将e删除，然后比较后面的与a，也必要走1步。
[size=2
]输入格式
输入字符串A和B(长度小于1000)
[size=2
]输特别式
输出最少经过多少步可以将A变成B
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
2
[size=2
]serial
1
[size=3
]概率最大的路径
[size=2
]标题描述
给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges 
1; [a, b] 表现毗连节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与尺度答案的误差不超过 1e-5
，就会被视作正确答案。
示例 1：
输入：n 
1; 3
, edges 
1; [[0,1],[1,2
],[0,2
]], succProb 
1; [0.5
,0.5
,0.2
], start 
1; 0, end 
1; 2
输出：0.2
5
000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2
，而另一条为 0.5
* 0.5

1; 0.2
5
示例 2
：
输入：n 
1; 3
, edges 
1; [[0,1],[1,2
],[0,2
]], succProb 
1; [0.5
,0.5
,0.3
], start 
1; 0, end 
1; 2
输出：0.3
0000
示例 3
：
输入：n 
1; 3
, edges 
1; [[0,1]], succProb 
1; [0.5
], start 
1; 0, end 
1; 2
输出：0.00000
解释：节点 0 和 节点 2
之间不存在路径
[size=2
]数据范围
2
<
1; n <
1; 10^4
0 <
1; start, end < n
start !
1; end
0 <
1; a, b < n
a !
1; b
0 <
1; succProb.length 
1;
1; edges.length <
1; 2
*10^4
0 <
1; succProb <
1; 1
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
2
[size=2
]serial
2
[size=3
]完全二叉树
[size=2
]标题描述
给定一颗二叉树，树的每个节点的值为一个正整数。
如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点，那么节点N被以为是树上的关键节点。
求树上所有的关键节点的个数。请写出程序，并解释解题思绪。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
1
[size=2
]serial
0
[size=3
]爬楼梯
[size=2
]标题描述
训练场上有一个台阶，总共有 n 级。一个运动员可以跳 1 级，也可以跳 2
级。
求运动员有多少种跳法。请写出程序，并解释解题思绪。
[size=2
]输入样例
- [/code] [size=2
- ]输出样例[/size]
- [code]2
]year
2
02
1
[size=2
]serial
1
[size=3
]目标和
[size=2
]标题描述
给定一个非负整数序列 x1, x2
, …, xn，可以给每一个整数取负数大概取原值。
求有多少种取法使得这些整数的和等于期望值 E。
请写出程序，并解释解题思绪。
[size=2
]输入格式
第一行：非负数序列
第二行：期望E
[size=2
]输特别式
取法的数目
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
1
[size=2
]serial
2
[size=3
]列队打饭
[size=2
]标题描述
下课了，有 n 位同学陆续赶到⻝堂进⾏列队打饭。
其中第 i 位同学的到达时间为 ai，打饭耗时为 ti，等待时间上限为 bi，即如果其在第 ai
3
;bi秒的时刻仍旧没有轮到他开始打饭，那么他将离开打饭队列，另寻用饭的地⽅。
问每位同学的开始打饭时间，大概指出其提前离开了队伍（如果这样则输出 -1）
[size=2
]输入格式
第⼀⾏⼀个整数 n (1<
1;n<
1;10^5
)，表⽰来打饭的同学数目。
接下来 n ⾏，每⾏三个整数 a,t,b (1<
1;a,t,b<
1;10^9, 1<
1;i<
1;n)
分别表⽰每位同学的到达时间、打饭耗时、等待时间上限。 保证 a[1]<a[2
]<…<a[n]
[size=2
]输特别式
每位同学的开始打饭时间
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
0
[size=2
]serial
0
[size=3
]斗牛
[size=2
]标题描述
给定五个 0~9 范围内的整数 a1, a2
, a3
, a4
, a5
。
如果能从五个整数中选出三个并且这三个整数的和为10 的倍数（包罗 0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结果，显然如果有多个三元组满⾜和是 10 的倍数，剩下两个数之和对 10 取余的结果都是相同的；
如果选不出这样三个整数，则这五个整数的权值为 -1。
如今给定 T 组数据，每组数据包含五个 0~9 范围内的整数，分别求这 T 组数据中五个整数的权值。
[size=2
]输入格式
第⼀⾏⼀个整数 T (1<
1;T<
1;1000)，表⽰数据组数。
接下来 T ⾏，每⾏ 5
个 0~9 的整数，表⽰⼀组数据。
[size=2
]输特别式
输入n个整数，组数据中五个整数的权值
[size=2
]输入样例
- 4
- 1
- 0 0 1 01 0 0 8 6
- 3
- 4
- 5
- 6
- 7
- 4
- 5
- 6
- 7
- 8
]输出样例
[size=2
]year
2
02
0
[size=2
]serial
1
[size=3
]打地鼠
[size=2
]标题描述
给定 n 个整数 a1, a2
, …, an 和⼀个 d，你必要选出若⼲个整数，使得将这些整数从⼩到⼤排好序之后，恣意两个相邻的数之差都不⼩于给定的d，问最多能选多少个数出来。
[size=2
]输入格式
第⼀⾏两个整数 n,d (1<
1;n<
1;105
,0<
1;d<
1;109)
分别表⽰整数个数和相邻整数差的下界。
第⼆⾏ n个整数 a1, a2
, …, an (1<
1;ai<
1;109, 1<
1;i<
1;n)
表⽰给定的 n 个整数。
[size=2
]输特别式
仅⼀⾏⼀个整数，表⽰答案。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
0
[size=2
]serial
2
[size=3
]序列
[size=2
]标题描述
给定⼀个⻓为 n 的序列 A，其中序列中的元素都是 0~9 之间的整数，对于⼀个⻓度同样为 n 整数序列B，定义其权值为 |A_i-B_i| (1<
1;i<
1;n) 之和加上 (B_j-B_j
3
;1)^2
(1<
1;j<n) 之和。
求所有⻓为 n 的整数序列中，权值最⼩的序列的权值是多少。
[size=2
]输入格式
第⼀⾏⼀个整数 n (1<
1;n<
1;10^5
)，表⽰序列 A 的⻓度。
第⼆⾏ n 个整数 a1, a2
, …, an (0<
1;ai<
1;9, 1<
1;i<
1;n)，表⽰序列 A 中的元素。
[size=2
]输特别式
仅⼀⾏⼀个整数，表⽰答案。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
0
[size=2
]serial
3
[size=3
]二叉搜索树
[size=2
]标题描述
给定⼀个 1~n 的排列 P，即⻓度为 n，且 1~n 中所有数字都恰恰出现⼀次的序列。如今按顺序将排列中的元素⼀⼀插⼊到初始为空的⼆叉搜索树中（左小右大），问末了每个节点的⽗亲节点的元素是什么。
特别地，根节点的⽗亲节点元素视为 0。
[size=2
]输入格式
⼀⾏ n 个整数，其中第 i 个整数 ai 表⽰元素 i 对应节点的⽗亲节点的元素。特别地，根节点的⽗亲节 点元素视为 0。
[size=2
]输特别式
⼀⾏ n 个整数，其中第 i 个整数 ai 表⽰元素 i 对应节点的⽗亲节点的元素。特别地，根节点的⽗亲节 点元素视为 0。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
02
0
[size=2
]serial
4
[size=3
]日期差值
[size=2
]标题描述
输入日期格式：YYYYMMDD，求与2
01902
05
相隔天数
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
019
[size=2
]serial
0
[size=3
]最大一连子序列
[size=2
]标题描述
给定一个数字序列A1,A2
…An，求i,j(1<
1;i<
1;j<
1;n)，使得Ai
3
;…
3
;Aj最大，输出这个最大和。
[size=2
]输入格式
第一行输入一个整数n，表现数列大小
第二行输入n个整数
[size=2
]输特别式
最大和
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
019
[size=2
]serial
1
[size=3
]有向树形态
[size=2
]标题描述
求N个结点可以或许组成的二叉树的个数。 1<
1;n<
1;2
0
[size=2
]输入格式
一个整数 N。
[size=2
]输特别式
输出能组成的二叉树的个数。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
019
[size=2
]serial
2
[size=3
]求众数
[size=2
]标题描述
给定一个长度为 n 的整数序列，请你求出该序列的众数。
众数就是一个序列中出现次数最多的数字。
如果不唯一，则输出小的那个值。
[size=2
]输入格式
第一行输入一个整数 n，表现有 n 个数。
第二行输入n 个整数。
[size=2
]输特别式
输出序列中的众数，如果不唯一，则输出小的那个值。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
018
[size=2
]serial
0
[size=3
]聚集交并
[size=2
]标题描述
输入两个聚集，分别求其交集和并会合元素的个数，每个聚集中可能存在相同的元素，而最终的交集和并会合应该不存在。
[size=2
]输入格式
第一行输入两个整数 n,m 表现两个聚集中元素的个数。
第二行输入 n 个整数，表现第一个聚集中的元素。
第三行输入 m 个整数，表现第二个聚集中的元素。
[size=2
]输特别式
输出两个整数以空格分开，表现其交集和并会合元素的个数。
[size=2
]数据范围
1≤n,m≤105
,
给定聚集元素取值范围 [1,109]。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
018
[size=2
]serial
1
[size=3
]骨牌
[size=2
]标题描述
有2
*n 的地板，用1*2
和 2
*1 的骨牌进行铺地板。
问共有多少种情况。结果对 999983
取余，1<
1;n<
1;10000
[size=2
]输入格式
输入一个整数n
[size=2
]输特别式
一个整数，表现铺法数目对 999983
取模后的结果
[size=2
]数据范围
1≤n≤10000
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
018
[size=2
]serial
2
[size=3
]求交点
[size=2
]标题描述
求直线交点，输入两个直线上的各两个端点，求其交点，
若无交点或无穷个交点输出一句 Parallel or coincident，输出交点保存两位小数。
[size=2
]输入格式
第一行包含四个整数 x1,y1,x2
,y2
表现第一个直线上的两个点坐标。
第二行包含四个整数 x3
,y3
,x4
,y4
表现第二个直线上的两个点坐标。
[size=2
]输特别式
输出两个直线的交点坐标，保存两位小数。
若无交点或无穷个交点输出一句 Parallel or coincident。
[size=2
]数据范围
0≤x,y≤10
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
018
[size=2
]serial
3
[size=3
]解一元一次方程
[size=2
]标题描述
解方程，给定一个字符串，代表一个一元一次方程。
如果有解求解，输特别式“x
1;数字”，
如果解的个数无穷，输出 “infinite solutions”。
如果没有解输出“no solution”，字符串长度不超过 2
5
6
。
[size=2
]输入格式
方程
[size=2
]输特别式
解
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
018
[size=2
]serial
4
[size=3
]约数求和
[size=2
]标题描述
输入一个数n，输出前n个数的约数的和。
[size=2
]输入格式
一个整数 n
[size=2
]输特别式
一个整数，表现前 n个数的约数的和
[size=2
]数据范围
1≤n≤107
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
018
[size=2
]serial
5
[size=3
]求中位数
[size=2
]标题描述
中位数定义：一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）. 给出一组无序整数，求出中位数，如果求最中间两个数的平均数，向下取整即可（不必要使用浮点数）
[size=2
]输入格式
该程序包含多组测试数据，每一组测试数据的第一行为N，代表该组测试数据包含的数据个数，1<
1;N<
1;10000.
接着N行为N个数据的输入，N
1;0时竣事输入
[size=2
]输特别式
各个序列的中位数
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
017
[size=2
]serial
0
[size=3
]求解校验码
[size=2
]标题描述
给定一个9位数字的ISBN，求其校验位。
ISBN格式为2
-02
-03
3
5
98，校验位的计算方法如下：从左到右依次将各位数字乘10，9，8，……，2
，
求出其和S，作模运算得M
1;S mod 11
。
若11
-M在1和9之间，校验位即为该数字
若11
-M等于10，校验位为X；
11
-M等于11
，校验位为0。
输出添加校验位的ISBN，如2
-02
-03
3
5
98-0。
[size=2
]输入格式
给定一个9位数字的ISBN
[size=2
]输特别式
输出添加校验位的ISBN
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
017
[size=2
]serial
1
[size=3
]无向图
[size=2
]标题描述
一个无向图，顶点为N个，顶点编号为1~N，其中M条边已给定.
如今要从K条备选边中选出若干条，使得整个图连通，且选出的边权值和最小。
[size=2
]输入格式
第一行输入三个整数N（N<100）, M, K,
接下来一行为K个整数表现备选边的编号。
然后是是M行，每行三个数字:u,v,d(0<d<10000)表现结点u和结点v的边，权值为d
编号按照输入输入顺序依次为1~M。
[size=2
]输特别式
如果输入有解则输出选出的边的权值和
否则输出-1
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
017
[size=2
]serial
2
[size=3
]最大公共子串长度
[size=2
]标题描述
给定两个字符串，求最大公共子串的长度。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
016
[size=2
]serial
0
[size=3
]后缀序列
[size=2
]标题描述
给定一个后缀序列，求值，只有加减
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
016
[size=2
]serial
1
[size=3
]哈夫曼编码
[size=2
]标题描述
给定一个字符串，求哈夫曼编码的最短长度。
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
2
016
[size=2
]serial
2
[size=3
]Hanoi塔标题
[size=2
]标题描述
(n阶Hanoi塔标题）假设有三个分别定名为A、B、C的塔座，在塔座A上插有n(n<2
0)个直径大小各不相同、依小到大编号为1，2
，…，n的圆盘。现要求将A轴上的n个圆盘移至塔座C上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则： 1）每次只能移动一个圆盘； 2
）圆盘可以插在A、B、C中的任一塔座上； 3
）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 请通过编程来打印出移动的步骤.
[size=2
]输入格式
只有一组输入数据.输入数据N(;表如今开始时A塔座上的盘子数),当输入0时程序竣事.
[size=2
]输特别式
输出移动的步骤.如
4
;A–>C
4
;,
4
;A–>B
4
;等.每两的步骤之间有三个空格隔开,每输出5
个步骤就换行.具体的见Sample Output.
[size=2
]输入样例
[size=2
]输出样例
- A-->C A-->B C-->B A-->C B-->A
- B-->C A-->C A-->B C-->B C-->A
- B-->A C-->B A-->C A-->B C-->B
- A-->C B-->A B-->C A-->C B-->A
- C-->B C-->A B-->A B-->C A-->C
- A-->B C-->B A-->C B-->A B-->C
- A-->C
- A-->B A-->C B-->C
]year
0
[size=2
]serial
0
[size=3
]长方形中的正方形
[size=2
]标题描述
给出长方形的长和宽，每次从长方形里撕去最大的正方形，输出末了能得到多少正方形
[size=2
]输入格式
输入两个整数，n和m，分别表现长方形的长和宽，数在int范围内
[size=2
]输特别式
输出一个整数，表现末了能得到多少正方形
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
0
[size=2
]serial
1
[size=3
]a与b得到c
[size=2
]标题描述
给出a,b,c（3
个整数），判断a,b能否通过±*/得到c，ab
可以交换位置，可以输出YES，不可以则输出NO
[size=2
]输入格式
输入3
个整数a,b,c,数据都在int范围内
[size=2
]输特别式
判断a,b能否通过±*/得到c，ab
可以交换位置，可以输出YES，不可以则输出NO
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
0
[size=2
]serial
2
[size=3
]最长公共子序列LCS
[size=2
]标题描述
标题描述：输入3
个子串， 输出这3
个子串的最大公共子串
输入：
ab
cd acb ab
c
输出：
ab
[size=2
]输入格式
如题
[size=2
]输特别式
如题
[size=2
]输入样例
[size=2
]输出样例
[size=2
]year
0
[size=2
]serial
3
[size=3
]求最大一连公共字串长度
[size=2
]标题描述
标题描述：给定两个字符串，求最大公共字串的长度，长度小于1000
分为两种标题：要求计算一连最长字串的长度
如下按照寻找一连的字串理解
输入：
11
11
hello2
2
2
2
11
3
3
hello4
4
4
输出：
5
[size=2
]输入格式
如题
[size=2
]输特别式
如题
[size=2
]输入样例
- 11
- 11
- hello2
- 2
- 2
- 2
- 11
- 3
- 3
- hello4
- 4
- 4
]输出样例
[size=2
]year
0
[size=2
]serial
4
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao12
3
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
