曲靖市网站建设_网站建设公司_一站式建站_seo优化

2025年复旦大学计算机考研复试机试真题

2025年复旦大学计算机考研复试上机真题

历年复旦大学计算机考研复试上机真题

历年复旦大学计算机考研复试机试真题

更多学校完整题目开源地址：https://gitcode.com/u014339447/pgcode

百度一下pgcode即可查看，输入 “学校名称” 即可筛选该校历年机试真题，包括真题、ac代码、解题思路、视频讲解。

树的子结构-复旦大学

题目描述

输入两棵二叉树A AA和B BB，判断B BB是不是A AA的子结构。

(约定空树不是任意一个树的子结构)。

B BB是A AA的子结构，即A AA中有出现和B BB相同的结构和节点值。

输入格式

两行，第一行是树A AA的层序遍历序列，第二行是树B BB的层序遍历序列。

使用null表示空节点。

输出格式

若B BB是A AA的子结构，输出true，否则输出false。

输入样例

3 4 5 1 2 null null null null null null 4 1 null null null

输出样例

true

解释

树A AA的层序遍历序列为3 4 5 1 2 null null null null null null，表示如下二叉树：

3 / \ 4 5 / \ 1 2

树B BB的层序遍历序列为4 1 null null null，表示如下二叉树：

4 / 1

树B BB是树A AA的子结构，因此输出true。

#include<iostream>#include<vector>#include<string>#include<sstream>usingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};vector<int>splitString(string&s){vector<int>v;stringstreamss(s);string item;while(ss>>item){if(item=="null")v.push_back(-1);elsev.push_back(stoi(item));}returnv;}TreeNode*build(vector<int>&nums,inti){if(i>=nums.size()||nums[i]==-1)returnnullptr;TreeNode*root=newTreeNode(nums[i]);root->left=build(nums,i*2+1);root->right=build(nums,i*2+2);returnroot;}boolwhethersame(TreeNode*rootA,TreeNode*rootB){if(rootA==nullptr&&rootB==nullptr)returntrue;elseif(rootA==nullptr&&rootB!=nullptr)returnfalse;elseif(rootA!=nullptr&&rootB==nullptr)returntrue;elseif(rootA->val!=rootB->val)returnfalse;returnwhethersame(rootA->left,rootB->left)&&whethersame(rootA->right,rootB->right);}boolisSubStructure(TreeNode*A,TreeNode*B){// 约定：空树不是任意树的子结构if(A==nullptr||B==nullptr){returnfalse;}returnwhethersame(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);}intmain(){string A,B;getline(cin,A);getline(cin,B);vector<int>numA=splitString(A);vector<int>numB=splitString(B);TreeNode*rootA=build(numA,0);TreeNode*rootB=build(numB,0);boolflag=isSubStructure(rootA,rootB);if(flag)cout<<"true"<<endl;elsecout<<"false"<<endl;return0;}

数的间隙-复旦大学

题目描述

给一个序列a 1 a_1a1​到a n a_nan​，和一个d dd。

a n a_nan​数组排序后，后一个数减去前一个数的值称之为数的间隙，要求数的间隙均大于d dd。

请问最多能从a n a_nan​中选出多少满足条件的数字。

输入样例

5 2 1 3 6 10 15

输出样例

4

#include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;intn,d;intmaxNumbersDP(vector<int>&a,intd){sort(a.begin(),a.end());vector<int>dp(n,1);intmax_len=1;for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(a[i]-a[j]>d){dp[i]=max(dp[i],dp[j]+1);}}max_len=max(max_len,dp[i]);}returnmax_len;}intmain(){cin>>n>>d;vector<int>a(n);for(inti=0;i<n;i++){cin>>a[i];}cout<<maxNumbersDP(a,d)<<endl;return0;}

高尔夫比赛的森林砍树-复旦大学

题目描述

你被请来给一个要举办高尔夫比赛的树林砍树。

树林由一个m × n m \times nm×n的矩阵表示， 在这个矩阵中：

• 0 00表示障碍，无法触碰

• 1 11表示地面，可以行走

• 比1 11大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为1 11（即变为地面）。

你将从( 0 , 0 ) (0, 0)(0,0)点开始工作，返回你砍完所有树需要走的最小步数。

如果你无法砍完所有的树，返回− 1 -1−1。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

输入格式

第一行两个整数，分别是m mm和n nn。

接下来有m mm行，每行n nn个数，代表矩阵的行。

输入样例

3 3 1 2 3 0 0 4 7 6 5

输出样例

6

importjava.util.Scanner;publicclassMain{staticinta,b;staticint[][]c;publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);a=in.nextInt();b=in.nextInt();in.nextLine();c=newint[a][b];for(inti=0;i<a;i++){for(intj=0;j<b;j++){c[i][j]=in.nextInt();}in.nextLine();}dfs(c,0,0);intcount=0;booleanimp=false;for(inti=0;i<a;i++){for(intj=0;j<b;j++){if(c[i][j]>1){imp=true;}if(c[i][j]==-1){count++;}}}if(imp){System.out.printf("-1");}else{System.out.printf("%d",count-1);}}privatestaticvoiddfs(int[][]c,inti,intj){if(i<0||j<0||i>=a||j>=b||c[i][j]==0||c[i][j]==-1){return;}else{c[i][j]=-1;dfs(c,i+1,j);dfs(c,i-1,j);dfs(c,i,j+1);dfs(c,i,j-1);}}}

层次遍历-复旦大学

题目描述

给定一个二叉搜索树的先序遍历 先序遍历先序遍历，求其层次遍历 层次遍历层次遍历。

输入格式

第一行输入n nn，表示树中有n nn个节点。

接下来一行输入n nn个数t r e e [ i ] tree[i]tree[i]，表示树的先序遍历 先序遍历先序遍历。

n < 100000 n < 100000n<100000

t r e e [ i ] tree[i]tree[i]各不相同，但不一定为1 11-n nn的全排列，且一定可以构成二叉搜索树

输出格式

输出1 11行n nn个数，表示层次遍历 层次遍历层次遍历的结果

输入样例

4 3 1 2 4

输出样例

3 1 4 2

#include<iostream>#include<vector>#include<queue>#include<climits>// 用于 INT_MIN 和 INT_MAXusingnamespacestd;// 定义二叉树节点结构structTreeNode{intval;// 节点值TreeNode*left;// 左子节点TreeNode*right;// 右子节点TreeNode(intx):val(x),left(NULL),right(NULL){}// 构造函数};// 根据先序遍历重建二叉搜索树TreeNode*buildTree(vector<int>&preorder,int&index,intminVal,intmaxVal){// 如果已经遍历完所有节点，返回空指针if(index>=preorder.size())returnnullptr;// 获取当前节点的值intval=preorder[index];// 如果当前值不在合法范围内，说明当前节点不属于当前子树，返回空指针if(val<minVal||val>maxVal)returnnullptr;// 创建当前节点TreeNode*root=newTreeNode(val);index++;// 移动到下一个节点// 递归构建左子树，左子树的值范围是 (minVal, val)root->left=buildTree(preorder,index,minVal,val);// 递归构建右子树，右子树的值范围是 (val, maxVal)root->right=buildTree(preorder,index,val,maxVal);returnroot;}// 层次遍历vector<int>levelOrder(TreeNode*root){vector<int>result;// 存储层次遍历的结果if(!root)returnresult;// 如果树为空，直接返回空结果queue<TreeNode*>q;// 使用队列辅助层次遍历q.push(root);// 将根节点入队while(!q.empty()){TreeNode*node=q.front();// 取出队首节点q.pop();// 弹出队首节点result.push_back(node->val);// 将节点值加入结果// 如果左子节点存在，将其入队if(node->left)q.push(node->left);// 如果右子节点存在，将其入队if(node->right)q.push(node->right);}returnresult;}intmain(){intn;cin>>n;// 输入节点数量vector<int>preorder(n);// 存储先序遍历结果for(inti=0;i<n;++i){cin>>preorder[i];// 输入先序遍历的每个节点值}intindex=0;// 用于跟踪当前处理的先序遍历中的节点// 重建二叉搜索树，初始范围为 (INT_MIN, INT_MAX)TreeNode*root=buildTree(preorder,index,INT_MIN,INT_MAX);// 进行层次遍历vector<int>result=levelOrder(root);// 输出结果for(inti=0;i<result.size();++i){if(i>0)cout<<" ";// 每个节点值之间用空格分隔cout<<result[i];}cout<<endl;return0;}