2025年浙江大学计算机考研复试机试真题
本文整理浙江大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分
Preorder Traversal
题目描述
Suppose that all the keys in a binary tree are distinct positive integers.
Given the $ postorder $ and $ inorder $ traversal sequences, you are supposed to output the last number of the $ preorder $ traversal sequence of the corresponding binary tree.
输入格式
Each input file contains one test case.
For each case, the first line gives a positive integer $ N $ ($ \leq 50,000 $), the total number of nodes in the binary tree.
The second line gives the $ postorder $ sequence and the third line gives the $ inorder $ sequence.
All the numbers in a line are separated by a space.
输出格式
For each test case, print in one line the last number of the $ preorder $ traversal sequence of the corresponding binary tree.
输入样例
7
1 2 3 4 5 6 7
2 1 4 3 7 5 6
输出样例
5
One Way In, Two Ways Out
题目描述
Consider a special queue which is a linear structure that allows insertions at one end, yet deletions at both ends.
Your job is to check, for a given insertion sequence, if a deletion sequence is possible.
For example, if we insert $1$, $2$, $3$, $4$, and $5$ in order, then it is possible to obtain $1$, $3$, $2$, $5$, and $4$ as an output, but impossible to obtain $5$, $1$, $3$, $2$, and $4$.
输入格式
Each input file contains one test case.
For each case, the first line gives 2 positive integers $N$ and $K$ ($\leq 10$), which are the number of insertions and the number of queries, respectively.
Then $N$ distinct numbers are given in the next line, as the insertion sequence.
Finally $K$ lines follow, each contains $N$ inserted numbers as the deletion sequence to be checked.
输出格式
For each deletion sequence, print in a line $yes$ if it is indeed possible to be obtained, or $no$ otherwise.
输入样例
5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2
输出样例
yes
no
yes
yes
Square Friends
题目描述
For any given positive integer $ n $, two positive integers $ A $ and $ B $ are called Square Friends if by attaching $ 3 $ digits to every one of the $ n $ consecutive numbers starting from $ A $, we can obtain the squares of the $ n $ consecutive numbers starting from $ B $.
For example, given $ n = 3 $, $ A = 73 $ and $ B = 272 $ are Square Friends since $ 73984 = 272^2 $, $ 74529 = 273^2 $, and $ 75076 = 274^2 $.
Now you are asked to find, for any given $ n $, all the Square Friends within the range where $ A \leq MaxA $.
输入格式
Each input file contains one test case.
Each case gives $ 2 $ positive integers: $ n $ ($ \leq 100 $) and $ MaxA $ ($ \leq 10^6 $), as specified in the problem description.
输出格式
Output all the Square Friends within the range where $ A \leq MaxA $.
Each pair occupies a line in the format $ A $ $ B $.
If the solution is not unique, print in the non-decreasing order of $ A $; and if there is still a tie, print in the increasing order of $ B $ with the same $ A $. Print No Solution. if there is no solution.
输入样例
3 85
输出样例
73 272
78 281
82 288
85 293
Load Balancing
题目描述
$Load balancing$ ($负载均衡$) refers to efficiently distributing incoming network traffic across a group of backend servers. A $load balancing$ algorithm distributes loads in a specific way.
If we can estimate the maximum incoming traffic load, here is an algorithm that works according to the following rule:
-
The incoming traffic load of size $S$ will first be partitioned into two parts, and each part may be again partitioned into two parts, and so on.
-
Only one partition is made at a time.
-
At any time, the size of the smallest load must be strictly greater than half of the size of the largest load.
-
All the sizes are positive integers.
-
This partition process goes on until it is impossible to make any further partition.
For example, if $S=7$, then we can break it into $3+4$ first, then continue as $4=2+2$.
The process stops at requiring three servers, holding loads $3$, $2$, and $2$.
Your job is to decide the maximum number of backend servers required by this algorithm.
Since such kind of partitions may not be unique, find the best solution -- that is, the difference between the largest and the smallest sizes is minimized.
输入格式
Each input file contains one test case, which gives a positive integer $S$ ($2 \leq N \leq 200$), the size of the incoming traffic load.
输出格式
For each case, print two numbers in a line, namely, $M$, the maximum number of backend servers required, and $D$, the minimum of the difference between the largest and the smallest sizes in a partition with $M$ servers.
The numbers in a line must be separated by one space, and there must be no extra space at the beginning or the end of the line.
输入样例
22
输出样例
4 1
Ambulance Dispatch
题目描述
Given the map of a city, with all the ambulance dispatch centers ($救护车派遣中心$) and all the pick-up spots marked. You are supposed to write a program to process the emergency calls. It is assumed that the callers are waiting at some pick-up spot. You must inform the nearest (that is, to take the minimum time to reach the spot) dispatch center if that center has at least one ambulance available. Note: a center without any ambulance must not be considered.
In case your options are not unique, inform the one with the largest number of ambulances available. If there is still a tie, choose the one that can pass the least number of streets to reach the spot, which is guaranteed to be unique.
输入格式
Each input file contains one test case. For each case, the first line contains two positive integers $N_s$ ($\leq 10^3$) and $N_a$ ($\leq 10$), which are the total number of pick-up spots and the number of ambulance dispatch centers, respectively. Hence the pick-up spots are numbered from $1$ to $N_s$, and the ambulance dispatch centers are numbered from $A-1$ to $A-N_a$.
The next line gives $N_a$ non-negative integers, where the $i$-th integer is the number of available ambulances at the $i$-th center. All the integers are no larger than $100$.
In the next line a positive number $M$ ($\leq 10^4$) is given as the number of streets connecting the spots and the centers. Then $M$ lines follow, each describes a street by giving the indices of the spots or centers at the two ends, followed by the time taken to pass this street, which is a positive integer no larger than $100$.
Finally the number of emergency calls, $K$, is given as a positive integer no larger than $10^3$, followed by $K$ indices of pick-up spots.
All the inputs in a line are separated by a space.
输出格式
For each of the $K$ calls, first print in a line the path from the center that must send an ambulance to the calling spot. All the nodes must be separated by exactly one space and there must be no extra space at the beginning or the end of the line. Then print the minimum time taken to reach the spot in the next line. It is assumed that the center will send an ambulance after each call. If no ambulance is available, just print $All Busy$ in a line. It is guaranteed that all the spots are connected to all the centers.
输入样例
7 3
3 2 2
16
A-1 2 4
A-1 3 2
3 A-2 1
4 A-3 1
A-1 4 3
6 7 1
1 7 3
1 3 3
3 4 1
6 A-3 5
6 5 2
5 7 1
A-2 7 5
A-2 1 1
3 5 1
5 A-3 2
8
6 7 5 4 6 4 3 2
输出样例
A-3 5 6
4
A-2 3 5 7
3
A-3 5
2
A-2 3 4
2
A-1 3 5 6
5
A-1 4
3
A-1 3
2
All Busy