苏州大学预推免 2024-8.21 机试补题（暂无数据结构）_苏州大学机试

目录

    前言

    一、程序设计题目（6道，每道60分）

      1.1    判断格子

      1.2    相差几天

      1.3    存钱

      1.4    相似单词匹配

      1.5    旋转图像

      1.6    判断2的幂

    二、数据结构题（2道，每道20分）

      2.1    反转链表

      2.2    二叉树找到仅大于target的值

    三、算法题（2道，每道20分）

      3.1    完全平方数

      3.2    错位排列

总结：

    前言

      苏州是个很美的城市，苏州大学是一所很美的大学~

      可惜自己能力不够，做了大概50-60分的题吧，基本上寄了，其实下来自己复刻代码感觉用不了2个小时就能写完，考场旁边的大哥做的飞快而且是考场第一个AK的，让我心态也很爆炸，基本上最后一小时啥也没干，道阻且长，继续努力吧。
     机房中编程环境详见

     1）C/C++编程环境为：visual studio 2010；
     2）Python编程环境：python3.7， IDE: IDLE；
     3）Java编程环境：Eclipse。

     赛时为 pdf文件*1,  sample.cpp文件*1。每个题对应一个sample文件中的函数，如第一题func1（）。需要在vs 2010下运行成功该函数。vs 2010 版本可能为C++ 98，无C++11特性如auto，匿名函数等，且并不允许代码中出现类似cout，printf的出现。

     题型并不类似于编程竞赛，更类似于leetcode，推荐leetcode Hot100进行练习。链接如下：

      题单 - 力扣（LeetCode）全球极客挚爱的技术成长平台

    需要注意！

    1. 本代码为补题代码，仅具有参考价值，并不保证样例、题目正确，只能保证相似，且并没有大样例！

    2. 如有错误请心平气和指出，本人非常fw && C++98与平时代码编写不同，做不到赛时ak

    3. 为方便输入输出样例，采用多组样例输入，原题并不存在该输入输出

    一、程序设计题目（6道，每道60分）

      1.1    判断格子

         题目：输入一个位置，如果是黑色返回True，白色返回False

输入样例：

3

a1

g6

h8

输出样例：    

True

False

True

 题解：

        a~h映射为1~8，相加为偶数 return True，奇数 return False

bool func1(const string &str){ int a = str[0] - \'a\' + 1; int b = str[1] - \'0\' + 1; if(a + b & 1) return true; else return false;}

测试代码： 

#includeusing namespace std;bool func1(const string &str){ int a = str[0] - \'a\' + 1; int b = str[1] - \'0\' + 1; if(a + b & 1) return true; else return false;}void solve(){ string str; cin >> str; if(func1(str)) puts(\"True\"); else puts(\"False\"); }int main() { int t; cin >> t; while(t --) solve(); system(\"pause\"); return 0;}

      1.2    相差几天

         题目：给定两个非负向量，每个向量分别存年，月，日，完成代码，计算差几天

         年合法，范围是1~3000，且月和日期可能不合法，且日期取前闭后开，如[2024,8,21]与[2024,8,22]相差一天。保证前向量永远小于后向量。

         题解：计算两个向量分别到1年1日，然后相减即可，注意闰月。

输入样例（不是原本的样例）：

3

2000 1 1

2000 3 1

1999 2 29

1999 3 1

2000 1 1

2024 1 1

输出样例：    

60

-1

8766

#include using namespace std;bool check(int year) { if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) return true; else return false;}int func2(const vector &v1, const vector &v2) { int y1 = v1[0], m1 = v1[1], d1 = v1[2]; int y2 = v2[0], m2 = v2[1], d2 = v2[2]; int lu_d[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int d[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int sum_lu_d[13] = {0}; int sum_d[13] = {0}; for (int i = 1; i <= 12; i++) { sum_lu_d[i] = sum_lu_d[i - 1] + lu_d[i]; sum_d[i] = sum_d[i - 1] + d[i]; } bool l_y1 = check(y1); bool l_y2 = check(y2); if (l_y1) { if (m1  12) return -1; if (d1  lu_d[m1]) return -1; } else { if (m1  12) return -1; if (d1  d[m1]) return -1; } if (l_y2) { if (m2  12) return -1; if (d2  lu_d[m2]) return -1; } else { if (m2  12) return -1; if (d2  d[m2]) return -1; } int sum1 = 0, sum2 = 0; for (int i = 1; i < y1; i++) { sum1 += check(i) ? 366 : 365; } for (int i = 1; i < y2; i++) { sum2 += check(i) ? 366 : 365; } sum1 += l_y1 ? sum_lu_d[m1 - 1] + d1 : sum_d[m1 - 1] + d1; sum2 += l_y2 ? sum_lu_d[m2 - 1] + d2 : sum_d[m2 - 1] + d2; return sum2 - sum1;}void solve() { vector v1(3), v2(3); for (int &x : v1) cin >> x; for (int &x : v2) cin >> x; cout << func2(v1, v2) <> t; while (t--) solve(); system(\"pause\"); return 0;}

      1.3    存钱

         题目：小明第一天存一元，然后接下来两天每天存2元，再接下来三天每天存3元，按照该规律，到第n天能存多少钱

         题解：根据题意即可。

输入样例（不是原本的样例）：

3

4

6

365

输出样例：    

8

14

6579

#include using namespace std;int func3(int n){ int total = 0; // 总存款金额 int day_count = 0; // 记录已经过去的天数 int k = 1; // 当前存款金额和持续天数 while (day_count > n; cout << func3(n) <> t; while (t--) solve(); return 0;}

      1.4    相似单词匹配

        题目：只有英文字母，忽略大小写，格式如下的类似单词判断是否一致，一致输出1，不一致输出0，长度不同输出-1.

        例如\'egg\'与\'bee\'一致，\'good\'与‘food\'一致。

        题解：很多种方法，也有很多优化，纯暴力就可以。

#include using namespace std;int func4(const string &s1, const string &s2) { if(s1.size() != s2.size()) return -1; unordered_map<char, vector> mp1, mp2; for(int i = 0; i < s1.size(); i ++) { mp1[s1[i]].push_back(i); mp2[s2[i]].push_back(i); } for(int i = 0; i > s1 >> s2; cout << func4(s1, s2) <> t; while (t--) { solve(); } return 0;}

      1.5    旋转图像

        为参考链接的改题：. - 力扣（LeetCode）

        题目：输入-1时向右旋转90°，输入1时向左旋转90°，输入2是转置矩阵，输出其他数直接输出该矩阵。

输入样例（不是原本的样例）：

3

1

3 3

1 2 3

4 5 6

7 8 9

2

3 3

1 2 3

4 5 6

7 8 9

-1

3 3

1 2 3

4 5 6

7 8 9

5

3 3

1 2 3

4 5 6

7 8 9

输出样例：    

7 4 1
8 5 2
9 6 3

3 6 9
2 5 8
1 4 7

1 4 7

2 5 8

3 6 9

1 2 3

4 5 6

7 8 9

题解：

此题注意vector操作。

右旋转时，原图第一行，成为旋转后的最后一列，因此列变行，行做列对称。

左旋转时，原图第一行，成为旋转后的第一列，因此行变列，列作行对称。

转置矩阵是中心对称的，变换横纵坐标。

代码：

#include using namespace std;vector<vector> func5(vector<vector> &matrix, int flag) { int rows = matrix.size(); int cols = matrix[0].size(); vector<vector> result; if (flag == -1) { // 右旋转90度 result.resize(cols, vector(rows)); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { result[j][rows - 1 - i] = matrix[i][j]; } } } else if (flag == 1) { // 左旋转90度 result.resize(cols, vector(rows)); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { result[cols - 1 - j][i] = matrix[i][j]; } } } else if (flag == 2) { // 转置矩阵 result.resize(cols, vector(rows)); for (int i = 0; i < rows; ++i) { for (int j = 0; j > flag; int rows, cols; cin >> rows >> cols; vector<vector> matrix(rows, vector(cols)); for (int i = 0; i < rows; ++i) { for (int j = 0; j > matrix[i][j]; } } vector<vector> result = func5(matrix, flag); for (const auto &row : result) { for (const auto &elem : row) { cout << elem << \" \"; } cout <> t; while (t--) solve(); system(\"pause\"); return 0;}

1.6    判断2的幂

      题目：对一个不超过unsigned int的数，判断是不是2的幂次，本题不再给样例。

      题解：有很多方法，最简单的如代码所示：

#include using namespace std;bool func6(unsigned int x) { return x > 0 && (x & (x - 1)) == 0;}void solve(){ unsigned int n; cin >> n; cout << func6(n) <> t; while(t -- ) solve(); system(\"pause\"); return 0;}

    二、数据结构题（2道，每道20分）

      2.1    反转链表（此题后续再补，无源码）

        给定链表类构建代码，需要完成该类下函数代码的填充，并且不能修改任何函数，以及传参

        1.将一段指针翻转，如输出的为1->2->3->4->6->5->7->8,如果反转从m = 2到x = 6的段落（头节点不计数），则反转后为1->5->6->4->3->2->7->8

        2.如果m >= x，不反转

        思路：感觉写起来很麻烦

      2.2    二叉树找到仅大于target的值（此题后续再补，无源码）

        给定二叉树类构建的代码，需要完成代码的填充，并且不能修改任何函数，以及传参

        1.给定一个函数，输入一个值，然后去找到比这个树更大的值，且仅大于这个数的值。

        思路：递归查找即可

    三、算法题（2道，每道20分）

      3.1    完全平方数

        题目：力扣原题. - 力扣（LeetCode）

      绷不住了，补题补一半突然发现自己wa了,突然发现这不一眼dp，为什么有nt拿贪心做啊

        思路：线性dp，定义为背包容积为m时，采用的最少平方数个数

代码：

class Solution {public: int INF = 1e4 + 10; int numSquares(int n) { vectordp(n + 1, INF); dp[0] = 0; for(int i = 1; i <= n; i ++) for(int j = 1; j * j <= i; j ++) dp[i] = std::min(dp[i], dp[i - j * j] + 1); return dp[n]; }};

      3.2    错位排列

           题目：n个人的有n个帽子，求排列，回不到自己手里的组合数，mod1e9 + 7（

           题解：典型的错位排列问题，Wiki证明链接如下错位排列 - OI Wiki

           B站非常好的一个递推证明如下：

全网最详细的全错排问题，学不会你找我_哔哩哔哩_bilibili

           个人参考后证明如下：

输入样例（不是原本的样例）：

5

1

2

3

4

5

输出样例：    

1

2

9

44

265

#include using namespace std;int func10(int n) { int mod = 1e9 + 7; vectordp(n + 1, 0); if (n == 0) return -1; if (n == 1) return 0; if (n == 2) return 1; dp[0] = 1; dp[1] = 0; dp[2] = 1; for (int i = 3; i > n; cout << func10(n) <> t; while (t--) { solve(); } return 0;}

总结

          如果不论交题方法的话，我个人认为绝大多数人能做到90分，所以我的苏大推免大抵是寄了。可能会卡到错排（其实样例也给你了，如果有心推也能把递推公式推出来）。这份保研试题难度不能说高，但是比天大杯考的更加全面，但是天大杯也更适合我，虽然tju也没要我（好像是我自己的问题），这份试卷也让我深刻意识到自己的数据结构不足，以后也会多做一些leetcode了QAQ

          大概做到3道题以上就可以过了，苏大学硕需要手速抢，外校很少，专硕点击就送