2021年浙大软院推免机试题解和复试准备建议_浙江大学机试准备

今年参加了浙江大学软件学院的推免复试，分为机试和面试，复试成绩=机试成绩×15%+面试成绩×85%。虽然机试占比不大，但是相对来说在取消PAT考试成绩抵机试后，机试的难度相比PAT甲级考试略大，同学之间的差距也会比较大，且机试成绩会影响面试老师的高低。据去年和今年的录取结果来看，机试90+基本是稳录取，80+也是大概率录取，所以如果想去浙大软院读研，机试非常重要。

本次浙软的机试我考了96分（第二题21分，其他三题AC），在600考生中排名20多，最后总分是前二十。下面主要说一说机试的代码，以及我准备浙软机试、面试的经历和感想，也希望可以帮助到想要来浙软的学弟学妹。（附上浙软的复试通知）

机试题解

第一题

第一题是一个求解数字的问题，不太记得题目了，难度比较小，AC代码如下。

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, int> ump;

bool prime(int p) {
    for (int j = 2; j * j <= p; j++) {
        if (p % j == 0)return false;
    }
    return true;
}

int product(int p) {
    int res = 1;
    while (p > 0) {
        res *= p % 10;
        p /= 10;
    }
    return res;
}

bool yanzheng(int a, int b, int t) {
    string sa = to_string(a), sb = to_string(b);
    reverse(sa.begin(), sa.end());
    reverse(sb.begin(), sb.end());
    if (abs(b - stoi(sa)) <= t)return true;
    if (abs(a - stoi(sb)) <= t)return true;
    return false;
}

int main() {
    int n1, n2, t, cnt = 1;
    scanf("%d %d %d", &n1, &n2, &t);
    unordered_map<int, int> ump;
    vector<int> res;
    for (int i = 2; i < 1000000; i++) {
        if (prime(i))ump[i] = cnt++;
    }
    for (int i = n1; i <= n2; i++) {
        if (ump[i] != 0) {
            string s = to_string(i);
            reverse(s.begin(), s.end());
            int rev = stoi(s);
            if (ump[rev] != 0) {
                int flag1 = 0, flag2 = 0;
                if (yanzheng(ump[i], ump[rev], t))flag1 = 1;
                if (abs(ump[i] - product(i)) <= t)flag2 = 1;
                if (flag1 == 1 && flag2 == 1)res.push_back(i);
            }
        }
    }
    for (int i = 0; i < res.size(); i++) {
        printf("%d\n", res[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

第二题

第二题是一段话的字符串匹配+替换，给了一本书的一大段话以及一些语句的替换规则，要求输出替换后的话。这题我只得了21分，做了快2个小时，还是没办法AC，代码是21分，希望大佬可以指点指点哪儿错了。需要注意替换的空格和字母大小写问题。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, daxie = 1;
    string s1, s2, article, res;
    scanf("%d\n", &n);
    vector<pair<string, string>> translate;
    for (int i = 0; i < n; i++) {
        getline(cin, s1);
        getline(cin, s2);
        for (int j = 0; j < s1.length(); j++) {
            if (s1[j] >= 'A' && s1[j] <= 'Z') {
                s1[j] = s1[j] + 'a' - 'A';
            }
        }
        translate.emplace_back(s1, s2);
    }
    getline(cin, article);
    for (int i = 0; i < article.length(); i++) {
        int flag = 1;
        for (int j = 0; j < translate.size(); j++) {
            if (article[i] == translate[j].first[0] || article[i] + 'a' - 'A' == translate[j].first[0]) {
                string temp = article.substr(i, translate[j].first.length());
                for (int k = 0; k < temp.length(); k++) {
                    if (temp[k] >= 'A' && temp[k] <= 'Z') {
                        temp[k] = temp[k] + 'a' - 'A';
                    }
                }
                if (temp == translate[j].first) {
                    string t = translate[j].second;
                    if ((article[i] >= 'A' && article[i] <= 'Z') && (t[0] >= 'a' && t[0] <= 'z')) {
                        t[0] = t[0] - 'a' + 'A';
                    } else if ((article[i] >= 'a' && article[i] <= 'z') && (t[0] >= 'A' && t[0] <= 'Z')) {
                        t[0] = t[0] + 'a' - 'A';
                    }
                    i += translate[j].first.length() - 1;
                    res += t;
                    flag = 0;
                    break;
                }
            }
        }
        if (flag == 1)res += article[i];
    }
    for (int i = 0; i < res.length(); i++) {
        if (res[i] == 'i') {
            if (res[i - 1] == ' ') {
                if (i != res.length() - 1 && res[i + 1] == ' ')printf("I");
                else printf("i");
            } else printf("%c", res[i]);
        } else printf("%c", res[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

第三题

这题是一个模拟题，难度较小。题意是给定一些人的关注关系，网红是被关注的人数大于一个值，且因为网红高傲，不会关注关注他们的用户，求解所有的网红。可以直接使用vector求解，AC代码如下。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, t, a, b;
    scanf("%d %d %d", &n, &m, &t);
    vector<unordered_map<int, int>> celebrity(n + 1);
    vector<int> iscelebrity(n + 1, 1), count(n + 1, 0);
    vector<int> res;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        if (celebrity[b][a] == 1) {
            iscelebrity[b] = 0;
            iscelebrity[a] = 0;//如果b被a关注了，且这里b关注了a，则b不是网红,a也不是网红
        }
        celebrity[a][b] = 1;//a被b关注
        count[a]++;//a被关注的数量+1
    }
    for (int i = 1; i <= n; i++) {
        if (iscelebrity[i] == 1 && count[i] >= t)res.push_back(i);
    }
    if (res.empty())printf("None");
    else {
        for (int i = 0; i < res.size(); i++) {
            if (i != 0)printf(" ");
            printf("%d", res[i]);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第四题

第四题是个板子题，求解AVL数的翻转，以及求两节点的关系。翻转方面完全是板子题，在PAT甲级模拟题后面有一样的题目，而求解两个节点的关系可以先遍历一遍树，存储其子节点和兄弟节点，这样的话比较方便。

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;

    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

TreeNode *leftRotate(TreeNode *root) {
    TreeNode *temp = root->right;
    root->right = temp->left;
    temp->left = root;
    return temp;
}

TreeNode *rightRotate(TreeNode *root) {
    TreeNode *temp = root->left;
    root->left = temp->right;
    temp->right = root;
    return temp;
}

TreeNode *leftRightRotate(TreeNode *root) {
    root->left = leftRotate(root->left);
    return rightRotate(root);
}

TreeNode *rightLeftRotate(TreeNode *root) {
    root->right = rightRotate(root->right);
    return leftRotate(root);
}

int getHeight(TreeNode *root) {
    if (root == nullptr)return 0;
    int l = getHeight(root->left);
    int r = getHeight(root->right);
    return max(l, r) + 1;
}

TreeNode *buildMyTree(TreeNode *root, int val) {
    if (root == nullptr)root = new TreeNode(val);
    else if (root->val > val)root->left = buildMyTree(root->left, val);
    else root->right = buildMyTree(root->right, val);
    int l = getHeight(root->left), r = getHeight(root->right);
    if (l - r > 1) {
        if (val < root->left->val) {
            root = rightRotate(root);
        } else root = leftRightRotate(root);
    } else if (r - l > 1) {
        if (val > root->right->val) {
            root = leftRotate(root);
        } else root = rightLeftRotate(root);
    }
    return root;
}

int main() {
    int n, m, t, a, b;
    string s;
    scanf("%d", &n);
    TreeNode *root = nullptr;
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        root = buildMyTree(root, t);
    }
    unordered_map<int, pair<int, int>> child;
    unordered_map<int, int> siblings;
    queue<TreeNode *> q;
    if (root != nullptr)q.push(root);
    while (!q.empty()) {
        int currentSize = q.size();
        for (int i = 0; i < currentSize; i++) {
            auto node = q.front();
            int right = -1, left = -1;
            q.pop();
            if (node->left != nullptr) {
                q.push(node->left);
                left = node->left->val;
            }
            if (node->right != nullptr) {
                q.push(node->right);
                right = node->right->val;
            }
            child[node->val] = {left, right};
            if (left != -1 && right != -1) {
                siblings[left] = right;
                siblings[right] = left;
            }
        }
    }
    scanf("%d\n", &m);
    while (m > 0) {
        m--;
        int flag = 0;
        scanf("%d", &a);
        cin >> s;
        if (s == "is") {
            cin >> s;
            cin >> s;
            if (s == "root") {
                if (a == root->val) {
                    flag = 1;
                }
            } else if (s == "parent") {
                cin >> s;
                scanf("%d", &b);
                if (child[a].first == b || child[a].second == b)flag = 1;
            } else if (s == "left") {
                cin >> s;
                cin >> s;
                scanf("%d", &b);
                if (child[b].first == a)flag = 1;
            } else if (s == "right") {
                cin >> s;
                cin >> s;
                scanf("%d", &b);
                if (child[b].second == a)flag = 1;
            }
        } else if (s == "and") {
            scanf("%d", &b);
            if (siblings[a] == b)flag = 1;
        }
        getline(cin, s);
        if (flag == 1)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

面试过程

浙大软院的面试是一个人20分钟，其中个人PPT介绍5-8分钟，包括1分钟的英文介绍。据我了解，每个组的问问题差别很大，但是主要是项目、408专业课、数学（线代和概率论）以及语言基础（c、c++、java）。

我个人的面试题目如下：

• 介绍线性代数的矩阵秩是什么意思？

• 介绍一下正定矩阵的定义？

• 多个点拟合使用什么算法？

• 面向对象和面向过程的区别，面向对象的性质？

• C++和java的面向对象多态性区别

• C语言的局部变量（栈）和全局变量存储位置（堆）

• 软件项目管理的流程，用的什么教材，一个理论（听不清楚）

• 介绍一下软件测试黑盒、白盒，如何评价白盒测试的好坏？

• 介绍一下论文中提到的算法？

对我来说，浙软的面试过程十分煎熬，之前听学长说浙软侧重项目，以及计网、数据结构、操作系统这些，在面试前我也把都复习了一遍。然而面试上来就是数学三连问（ 线代大一学的，基本没复习），以及编程语言基础知识。因为没有认真复习这些，回答的模模糊糊。

在结束以后问了几个参加面试的同学，有的人一个专业课都没有，全部是问项目。总结可能是因为我的项目老师们不太懂，没办法问。所以有和老师相关的项目也是非常重要滴。不过最后的面试分数还可以，可能因为我的机试和个人条件还行。

准备建议

浙大软院从今年开始不能使用当年的PAT甲级和顶级成绩抵消机试，这两年的机试难度和PAT类似，可能略高一点。我个人是刷PAT的甲级真题，也就是官网的150多题，如果把这些题独立做完，机试90+一般没有问题。也可以关注关注大佬的题解，学习其思路，这里推荐柳神，我也是学习了不少她的题解。

面试其实就没什么好说的了，专业课+项目，需要认真复习。其中个人背景（rank、奖项）也是面试打分依据之一。另外需要注意，浙大软院面试需要交一页个人简历，**千万不要把自己不熟悉的课程写上去！！！**后来我才发现我交上去的个人简历有线代、C等成绩（因为成绩比较高），这也是需要避坑的。

对于双非本科的同学，或者是rk比较低的同学，可以考虑参加夏令营。浙软夏令营是个海王营，放1000+人进来，但是放弃的人也非常多。只要坚持做完项目得到优营的概率就挺大，今年的预推免初审也是刷掉了很多很多优秀的同学，听说有双非rk1acm金大佬。

写在最后

浙软这几年的政策变化很大，听说新院长张来后有不少操作，所以一定要注意最新的政策。今年的浙软口碑相比往年差了一点，但是热度却丝毫不减。我觉得浙软对于cs的学生来说，仁者见仁智者见智，适合自己的就是比较好的～

个人博客：randyzhang的个人博客
知乎：柠檬到了的知乎