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>
using namespace std;

vector<int> postorder, inorder;
unordered_map<int, int> indexMap;  // 存储中序遍历中值到索引的映射

// 递归函数：在后序和中序序列中查找前序遍历的最后一个节点
int findLastPreorder(int postStart, int postEnd, int inStart, int inEnd) {
    if (postStart > postEnd || inStart > inEnd) {
        return -1;  // 边界条件
    }
    
    // 后序遍历的最后一个元素是当前子树的根节点
    int rootVal = postorder[postEnd];
    int rootIndex = indexMap[rootVal];  // 根节点在中序遍历中的位置
    
    // 计算左右子树的大小
    int leftSize = rootIndex - inStart;
    int rightSize = inEnd - rootIndex;
    
    // 前序遍历的最后一个节点是整棵树最右下角的节点
    // 优先在右子树中查找，如果右子树为空则在左子树中查找
    if (rightSize > 0) {
        // 右子树非空，继续在右子树中递归查找
        return findLastPreorder(postStart + leftSize, postEnd - 1, rootIndex + 1, inEnd);
    } else if (leftSize > 0) {
        // 右子树为空，左子树非空，在左子树中递归查找
        return findLastPreorder(postStart, postStart + leftSize - 1, inStart, rootIndex - 1);
    } else {
        // 左右子树都为空，当前节点就是叶子节点，即目标节点
        return rootVal;
    }
}

int main() {
    int n;
    cin >> n;  // 读取节点数量
    
    postorder.resize(n);
    inorder.resize(n);
    
    // 读取后序遍历序列
    for (int i = 0; i < n; i++) {
        cin >> postorder[i];
    }
    
    // 读取中序遍历序列，并建立值到索引的映射
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
        indexMap[inorder[i]] = i;  // 记录每个值在中序遍历中的位置
    }
    
    // 查找前序遍历的最后一个节点
    int result = findLastPreorder(0, n - 1, 0, n - 1);
    cout << result << endl;
    
    return 0;
}

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$ ($\le 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

#include <bits/stdc++.h>
#define ll long long
#define i128 __int128
#define il inline
using namespace std;

int n, k;

il bool isPossible(vector<int> &insertion, vector<int> &deletion)
{
    deque<int> dq;
    int i = 0, j = 0;
    while (i < n || j < n)
    {
        if (!dq.empty() && dq.front() == deletion[i])
        {
            dq.pop_front();
            i++;
            // cout << "pop_front" << endl;
        }
        else if (!dq.empty() && dq.back() == deletion[i])
        {
            dq.pop_back();
            i++;
            // cout << "pop_back" << endl;
        }
        else if (j < n)
        {
            dq.push_back(insertion[j]);
            j++;
            // cout << "push_back" << endl;
        }
        else
            return false;
    }
    return true;
}

int main()
{
    cin >> n >> k;
    vector<int> insertion(n);
    vector<int> deletion(n);
    for (int i = 0; i < n; i++)
        cin >> insertion[i];
    while (k--)
    {
        deletion.clear();
        for (int i = 0; i < n; i++)
            cin >> deletion[i];
        if (isPossible(insertion, deletion))
            cout << "yes\n";
        else
            cout << "no\n";
    }
    return 0;
}

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-浙江大学

题目描述

$Loadbalancing$ ($负载均衡$) refers to efficiently distributing incoming network traffic across a group of backend servers. A $loadbalancing$ 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\le N\le 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

#include<iostream>
#include<algorithm>
using namespace std;

const int N=210;

int n;
int w[N],cnt;// w[]存储每一堆石子数量 cnt是石子堆的个数
int m,d;// 答案M 和 D

int getd()//求最大石子堆石子数量与最小石子堆石子数量之差
{
    int x=0,y=N;
    for(int i=0;i<cnt;i++)
    {
        x=max(x,w[i]);
        y=min(y,w[i]);
    }
    return x-y;
}

void dfs()
{
    if(cnt>m) m=cnt,d=getd();//现在的石子堆数>上一次的，更新M和D
    else if(cnt==m) d=min(d,getd());//相等只更新 D

    if(cnt==1)//只有一堆的情况
    {
        int a=w[0];
        for(int x=a/3+1;x<=a/2;x++)
        {
            w[0]=x;
            w[cnt++]=a-x;
            dfs();
            //恢复现场
            w[0]=a;
            cnt--;
        }
    }
    else
    {
        int i=0,j=-1;
        for(int k=1;k<cnt;k++)//找到第一，第二大的值的下标
            if(w[k]>=w[i]) j=i,i=k;
            else if(j==-1||w[k]>w[j]) j=k;

        int a=w[i],b=w[j];
        if(a>b)
        {
            for(int 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;
}

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;

}