2020计算机专业保研夏令营面经：复旦计算机（含机考题目详细题解）
目录
-
整体安排
-
机考
-
-
第1题
-
- 题目
- 题解
- 测试用例
- 代码
-
第2题
-
- 题目
- 题解
- 测试用例
- 代码
-
第3题
-
- 题目
- 题解
- 测试用例
- 代码
-
-
英语口试
-
专业面试
整体安排
7.13号，各实验室利用腾讯会议进行介绍，入夜后登录系统填写志愿。14号上午进行机考，下午进行英语口试。15号的专业面试环节。
（头铁，报了人工智能方向学硕…
机考
要求如下：
编程能力摸底测试完成后，请按照以下要求进行打包提交：
1）输出一份PDF文件，文件名定为"解题思路与测试情况"，内容需依次针对每道题阐述解题思路，并列出通过的测试用例；
2）对于每道题，需输出完整的源代码文件，文件名采用题目编号命名法，例如第1题的文件名为"第1题"；
3）将上述所有文件进行压缩打包，压缩包名称需命名为"报名号 姓名"。
第1题
题目
某高校计算机专业开设了n门核心课程，这些课程被依次编号为0、1、……、n-1。每门课程的先修课程要求必须在该课程修读之前完成，例如课程0的先修课程是课程1，用[0，1]表示。根据给定的课程数量和各门课程之间的先修关系，需要确定一门满足所有先修关系要求的修课顺序。例如，输入包括课程数量以及每对课程之间的先修关系，如输入4，[1，0]，[2，0]，[3，1]，[3，2]（其中4表示课程总数，[1，0]、[2，0]、[3，1]、[3，2]表示各对课程之间的先修关系），输出则给出了满足前置关系的两种可能的修读顺序：0-1-2-3或0-2-1-3。
题解
常见的DAG拓扑排序方法。通过依次查找无前驱的顶点并输出，直到所有顶点都被输出。我采用集合来存储每个节点的前驱节点，与邻接表不同，这种方法更高效。这样，每次检查该节点的前驱数量是否为零，就能确定其是否有前驱。一旦找到一个无前驱的节点，就将其从所有其他节点的前驱列表中移除。特别注意输入格式为[a,b]，需要对无关符号进行处理。这道题是特殊判题，要求输出正确答案。
注：在PDF文档中，这道题的输入用例是中文符号，导致用户长期报错。经过长时间排查，问题终于被发现。
测试用例
测试用例1：
输入：4,[1,0],[2,0],[3,1],[3,2]
输出：0,1,2,3
测试结果：通过
测试用例2：
输入：5,[1,0],[2,1],[3,1],[1,4]
输出：0,4,1,2,3
测试结果：通过
测试用例3：
输入：5,[1,0],[2,1],[3,1],[1,4],[0,4]
输出：4,0,1,2,3
测试结果：通过
测试用例4：
输入：3,[2,1]
输出：0,1,2
测试结果：通过
代码
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin>>n;
set<int> s[n];
bool mark[n];
for(int i=0; i<n; i++) {
mark[i]=true;
}
int qian,hou;
char temp='x';
cin>>temp;
while(temp!='\n') {
cin>>temp>>hou>>temp>>qian>>temp;
s[hou].insert(qian);
temp=cin.get();
}
int count=0;
while(count<n) {
for(int i=0; i<n; i++) {
if(mark[i]&&s[i].size()==0) {
cout<<i;
count++;
mark[i]=false;
for(int j=0; j<n; j++) {
s[j].erase(i);
}
if(count!=n)
cout<<",";
}
}
}
return 0;
}
代码解读第2题
题目
给定一个二维矩阵，其中每个元素均为0或1，确定该矩阵中最大的全1正方形子矩阵（即行数与列数相同），并输出该子矩阵的行数。
题解
寻找最大正方形子矩阵，当然可以采用暴力搜索的方法。然而，采用动态规划方法后，子问题转化为：dp[i][j]表示以(i,j)为右下角顶点的最大正方形的边长。递推关系式如下：当num[i][j]的值为0时，dp[i][j]的值也为0；当num[i][j]的值为1时，则dp[i][j]的值取决于其上下左右四个方向的dp值。具体来说，如果当前单元格的上下左右四个方向的dp值均为1，则dp[i][j]的值为dp[i-1][j-1]+1；否则，dp[i][j]的值为1。这种转换方式能够有效避免复杂的循环结构。
注意：因为题目输入未明确给出矩阵的行数和列数，因此可以使用while(cin>>xx)循环来读取矩阵元素，并假设矩阵的最大尺寸为100x100。手工输入测试用例时，应按Ctrl+Z来表示输入结束，这相当于程序中的EOF处理。请注意，针对在线评测系统（OJ）的测试用例，此处理流程无需特别处理。
测试用例
测试用例1：
输入：
1 1 0 0 0
1 0 1 1 1
1 0 1 1 1
0 0 1 1 1
1 1 0 0 0
输出：3
测试结果：通过
测试用例2：
输入：
0
输出：0
测试结果：通过
测试用例3：
输入：
1
输出：
1
测试结果：通过
测试用例4：
输入：
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
输出：5
测试结果：通过
测试用例5：
输入：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
输出：0
测试结果：通过
测试用例6：
输入：
1 0 0 0 0 1 1 0 0 0 1
0 1 1 1 0 0 0 0 1 1 1
输出：1
测试结果：通过
测试用例7：
输入：
1 1 0 0 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 0 0 1 1 0
0 0 1 1 1 1 1 1 1 1
输出：2
测试结果：通过
代码
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int num[100][100];
int dp[100][100];
int i=0,j=0;
int temp;
char t='x';
int m=0,n=0,rs=0;
while(cin>>temp) {
num[i][j]=temp;
t=cin.get();
if(t==' ') {
j++;
} else {
n=j+1;
i++;
j=0;
}
}
if(j==0) {
m=i;
} else {
m=i+1;
}
for(i=0; i<m; i++) {
for(j=0; j<n; j++) {
if(num[i][j]==1) {
if(i>0&&j>0)
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
else
dp[i][j]=1;
rs=max(rs,dp[i][j]);
} else {
dp[i][j]=0;
}
}
}
cout<<rs;
return 0;
}
代码解读第3题
题目
给定一棵包含n个节点的树，其节点依次标记为0、1、……、n-1号节点，其中根节点编号为0。每个节点可以被染成黑色或白色，初始状态下，所有节点均为白色状态。对于任意节点c，可以执行以下两种操作：着色操作，将节点c设置为黑色状态；查询操作，计算节点c到所有被着色为黑色的节点的距离总和。给定m次操作序列，需要对所有查询操作的结果进行输出。输入的具体内容如下：第一行包含两个整数n和m，分别表示节点总数和操作次数；第二行包含n-1个整数，其中第i个整数表示节点i的父节点；第三行包含n-1个整数，其中第i个整数表示节点i与其父节点之间的边的长度；其余m行每行包含两个整数t和c，其中t=1表示着色操作，t=2表示查询操作，c为待操作的节点编号。
例子：
输入：
4 5
0 1 2
2 1 3
2 2
1 3
2 2
2 3
2 1
输出：
0
3
0
4
题解
完成之后，我认为这道题的核心在于数据结构，具体来说，是（如何表示每个节点的父节点关系以及每条边的长度），以及如何找到所有节点的最短路径。由于树的形状是固定的，仅取决于每个节点的颜色，因此可以预先计算结点之间的距离，并建立一个二维数组存储这些距离，这样在需要时可以直接查询数组。
如何表示树的结构？题目关注的焦点在于节点间的最短路径计算，与树的具体结构无关。因此，可以将节点间的最短距离信息存储在一个二维矩阵中。基于上述分析，可以采用Floyd算法来计算所有节点间的最短路径。Floyd算法适用于计算所有节点之间的最短路径，因此在本问题中是合适的解决方案。为了提高查询效率，可以维护一个标记数组来记录已访问的节点。在每次查询时，只需将查询节点与所有已标记节点的距离进行累加即可。
测试用例
测试用例1：
输入：
4 5
0 1 2
2 1 3
2 2
1 3
2 2
2 3
2 1
输出：
0
3
0
4
测试结果：通过
测试用例2：
输入：
7 6
0 1 2 0 4 4
1 5 4 3 2 1
1 2
2 1
1 4
2 3
1 0
2 5
输出：
5
17
18
测试结果：通过
测试用例3：
输入：
5 6
0 0 1 3
1 1 1 1
1 0
2 4
1 1
2 4
2 3
2 2
输出：
3
5
3
3
测试结果：通过
测试用例4：
输入：
3 4
0 0
1 3
1 1
2 1
2 2
2 0
输出：
0
4
1
测试结果：通过
代码
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int G[n][n];
bool mark[n];
for(int i=0; i<n; i++) {
mark[i]=false;
for(int j=0; j<n; j++) {
if(i==j)
G[i][j]=0;
else
G[i][j]=21400000;
}
}
vector<int> v;
for(int i=0; i<n-1; i++) {
int temp;
cin>>temp;
v.push_back(temp);
}
for(int i=0; i<n-1; i++) {
int temp;
cin>>temp;
G[i+1][v[i]]=temp;
G[v[i]][i+1]=temp;
}
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(G[i][j]>G[i][k]+G[k][j])
G[i][j]=G[i][k]+G[k][j];
vector<int> rs;
for(int i=0; i<m; i++) {
int order,a;
cin>>order>>a;
if(order==1) {
mark[a]=true;
} else {
int sum=0;
for(int j=0; j<n; j++) {
if(mark[j]) {
sum+=G[a][j];
}
}
rs.push_back(sum);
}
}
for(int i=0; i<rs.size(); i++)
cout<<rs[i]<<endl;
return 0;
}
代码解读英语口试
- introduce yourself
- latest project
- introduce your hometown
专业面试
- 2分钟自我介绍
- 最小生成树可以加边或者加点，那么最大生成树应该怎样求？
- Krusal算法是贪心算法，正确性怎样证明？
- 你机考题目都做出来了吗，描述一下机考题目的解题思路
- 描述一下你的项目
- 你项目里的的“智能”体现在哪个方面？
- 引申到了让我设计学生录取算法，根据学习成绩与获奖
- 我说确定每个指标的权重，老师说不是
- 我说放到二维坐标里面去，用桶，或者用堆，老师没表态