2025年浙江大学计算机考研复试机试真题
2025年浙江大学计算机考研复试上机真题
历年浙江大学计算机考研复试上机真题
历年浙江大学计算机考研复试机试真题
更多学校完整题目开源地址：https://gitcode.com/u014339447/pgcode
百度一下pgcode即可查看，输入 “学校名称” 即可筛选该校历年机试真题，包括真题、ac代码、解题思路、视频讲解。
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#include<iostream>#include<vector>#include<unordered_map>usingnamespacestd;vector<int>postorder,inorder;unordered_map<int,int>indexMap;// 存储中序遍历中值到索引的映射// 递归函数：在后序和中序序列中查找前序遍历的最后一个节点intfindLastPreorder(intpostStart,intpostEnd,intinStart,intinEnd){if(postStart>postEnd||inStart>inEnd){return-1;// 边界条件}// 后序遍历的最后一个元素是当前子树的根节点introotVal=postorder[postEnd];introotIndex=indexMap[rootVal];// 根节点在中序遍历中的位置// 计算左右子树的大小intleftSize=rootIndex-inStart;intrightSize=inEnd-rootIndex;// 前序遍历的最后一个节点是整棵树最右下角的节点// 优先在右子树中查找，如果右子树为空则在左子树中查找if(rightSize>0){// 右子树非空，继续在右子树中递归查找returnfindLastPreorder(postStart+leftSize,postEnd-1,rootIndex+1,inEnd);}elseif(leftSize>0){// 右子树为空，左子树非空，在左子树中递归查找returnfindLastPreorder(postStart,postStart+leftSize-1,inStart,rootIndex-1);}else{// 左右子树都为空，当前节点就是叶子节点，即目标节点returnrootVal;}}intmain(){intn;cin>>n;// 读取节点数量postorder.resize(n);inorder.resize(n);// 读取后序遍历序列for(inti=0;i<n;i++){cin>>postorder[i];}// 读取中序遍历序列，并建立值到索引的映射for(inti=0;i<n;i++){cin>>inorder[i];indexMap[inorder[i]]=i;// 记录每个值在中序遍历中的位置}// 查找前序遍历的最后一个节点intresult=findLastPreorder(0,n-1,0,n-1);cout<<result<<endl;return0;}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 insert1 11,2 22,3 33,4 44, and5 55in order, then it is possible to obtain1 11,3 33,2 22,5 55, and4 44as an output, but impossible to obtain5 55,1 11,3 33,2 22, and4 44.
输入格式
Each input file contains one test case.
For each case, the first line gives 2 positive integersN NNandK KK(≤ 10 \leq 10≤10), which are the number of insertions and the number of queries, respectively.
ThenN NNdistinct numbers are given in the next line, as the insertion sequence.
FinallyK KKlines follow, each containsN NNinserted numbers as the deletion sequence to be checked.
输出格式
For each deletion sequence, print in a liney e s yesyesif it is indeed possible to be obtained, orn o nonootherwise.
输入样例
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#include<bits/stdc++.h>#definelllonglong#definei128__int128#defineilinlineusingnamespacestd;intn,k;ilboolisPossible(vector<int>&insertion,vector<int>&deletion){deque<int>dq;inti=0,j=0;while(i<n||j<n){if(!dq.empty()&&dq.front()==deletion[i]){dq.pop_front();i++;// cout << "pop_front" << endl;}elseif(!dq.empty()&&dq.back()==deletion[i]){dq.pop_back();i++;// cout << "pop_back" << endl;}elseif(j<n){dq.push_back(insertion[j]);j++;// cout << "push_back" << endl;}elsereturnfalse;}returntrue;}intmain(){cin>>n>>k;vector<int>insertion(n);vector<int>deletion(n);for(inti=0;i<n;i++)cin>>insertion[i];while(k--){deletion.clear();for(inti=0;i<n;i++)cin>>deletion[i];if(isPossible(insertion,deletion))cout<<"yes\n";elsecout<<"no\n";}return0;}Square Friends-浙江大学
题目描述
For any given positive integer $ n $, two positive integers $ A $ and $ B $ are calledSquare Friendsif 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 $. PrintNo Solution.if there is no solution.
输入样例
3 85输出样例
73 272 78 281 82 288 85 293Load Balancing-浙江大学
题目描述
L o a d b a l a n c i n g Load balancingLoadbalancing(负载均衡 负载均衡负载均衡) refers to efficiently distributing incoming network traffic across a group of backend servers. Al o a d b a l a n c i n g load balancingloadbalancingalgorithm 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 sizeS SSwill 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, ifS = 7 S=7S=7, then we can break it into3 + 4 3+43+4first, then continue as4 = 2 + 2 4=2+24=2+2.
The process stops at requiring three servers, holding loads3 33,2 22, and2 22.
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 integerS SS(2 ≤ N ≤ 200 2 \leq N \leq 2002≤N≤200), the size of the incoming traffic load.
输出格式
For each case, print two numbers in a line, namely,M MM, the maximum number of backend servers required, andD DD, the minimum of the difference between the largest and the smallest sizes in a partition withM MMservers.
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#include<iostream>#include<algorithm>usingnamespacestd;constintN=210;intn;intw[N],cnt;// w[]存储每一堆石子数量 cnt是石子堆的个数intm,d;// 答案M 和 Dintgetd()//求最大石子堆石子数量与最小石子堆石子数量之差{intx=0,y=N;for(inti=0;i<cnt;i++){x=max(x,w[i]);y=min(y,w[i]);}returnx-y;}voiddfs(){if(cnt>m)m=cnt,d=getd();//现在的石子堆数>上一次的，更新M和Delseif(cnt==m)d=min(d,getd());//相等只更新 Dif(cnt==1)//只有一堆的情况{inta=w[0];for(intx=a/3+1;x<=a/2;x++){w[0]=x;w[cnt++]=a-x;dfs();//恢复现场w[0]=a;cnt--;}}else{inti=0,j=-1;for(intk=1;k<cnt;k++)//找到第一，第二大的值的下标if(w[k]>=w[i])j=i,i=k;elseif(j==-1||w[k]>w[j])j=k;inta=w[i],b=w[j];if(a>b){for(intx=max(b/2,a/3)+1;x<=a/2;x++){w[i]=x,w[cnt++]=a-x;dfs();//恢复现场w[i]=a,cnt--;}}elsereturn;}}intmain(){cin>>n;w[cnt++]=n;//初始化只有一堆，w[0]=n,cnt=1dfs();//暴力枚举所有方案数cout<<m<<" "<<d<<endl;return0;}t x=max(b/2,a/3)+1;x<=a/2;x++)
{
w[i]=x,w[cnt++]=a-x;
dfs();
//恢复现场
w[i]=a,cnt–;
}
}
else return;
}
}
int main()
{
cin>>n;
w[cnt++]=n;//初始化只有一堆，w[0]=n,cnt=1
dfs();//暴力枚举所有方案数 cout<<m<<" "<<d<<endl; return 0;}
