复旦大学机试题题解（2017~2021） |
您所在的位置：网站首页 › 复旦考研复试一般考什么 › 复旦大学机试题题解（2017~2021） |
复旦大学机试题题解（2017~2021）
|
前言
尝试把复旦大学历年的机试题做一遍，能做多少是多少了，因为没有数据集所以也不好确认是不是对的~（题目来自王道往届学长学姐回忆以及某位热心的同学整理，如果了解来源后，我一定备注来源） （目前进度：2021、2020、2019、2018、2017） 2021年机试真题 A 完全二叉树 [水题] 题目描述给定一颗二叉树，树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点，那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序，并解释解题思路。 例子： 输入：3 1 4 3 null 1 5 直接的想法是，先依据题意建立一棵二叉树，使用struct构造一个node类型，由于二叉树可以使用数组来保存，下标i就能表示父子结点关系，故只需要存储结点值以及从根结点到当前结点路径上的最大值（包含当前结点值）。 为了后续查找方便起见，先插入一个空结点，让树结点序号从1开始。为了保持整体结构，空结点也需要插入其中。建树完成后，将每个结点的值与父结点的路径上最大值进行比较，如果小于则更新当前结点的路径上最大值，如果大于等于则cnt++。（cnt表示符合题目条件的结点个数） 后来在写程序过程中，发现由于是逐层遍历的，路径上最大值maxn可以与结点值val合并，故删去了val。 代码 #include using namespace std; struct node{ int maxn;//从根结点到当前结点的最大值。初始为各个结点的值 bool null = false;//判断是否为空结点 }; int main() { int i, cnt=1; string s; vector v; node temp; v.push_back(temp);//数组头部先插入一个结点，让根结点的下标为1，方便后续查找父结点。 while(cin>>s){ node temp; if(s!="null") temp.maxn = stoi(s); else temp.null = true;//为了维持树的完整结构，空结点也要插入 v.push_back(temp); } for(i=2; i=v[i/2].maxn) cnt++; else v[i].maxn=v[i/2].maxn; } printf("%d\n", cnt); system("pause"); return 0; } B 爬楼梯 [动态规划/矩阵快速幂/数学] 题目描述训练场上有一个台阶，总共有 n 级。一个运动员可以跳 1 级，也可以跳 2 级。 求运动员有多少种跳法。请写出程序，并解释解题思路。 思路机试时没多想，直接想法是动态规划。状态转移方程为：dp[i] = dp[i-1]+dp[i-2]。 但在机试结束后查看题解，才发现还有多种思路。一种是将斐波那契数列用矩阵的形式表示，利用矩阵快速幂减少运算；第二种是利用斐波那契的数学公式，直接计算结果。 代码 #include using namespace std; int main(){ int n, d, i, cnt=1, last; scanf("%d %d", &n, &d); vector v(n); for(i=0; i> temp) v.push_back(temp); vector dp(v.size()); map tmp; dp.push_back(tmp); dp[0][v[0]] = dp[0][-v[0]] = 1; for(i=1; ifirst)!=dp[i].end()) dp[i][v[i]+j->first] += j->second; else dp[i][v[i]+j->first] = j->second; if(dp[i].find(j->first-v[i])!=dp[i].end()) dp[i][j->first-v[i]] += j->second; else dp[i][j->first-v[i]] = j->second; } } printf("%d\n", dp[v.size()-1][E]); system("pause"); return 0; } 相关链接leetcode 494 目标和 2020年机试真题 A 斗牛 [水题] 题目描述给定五个 0~9 范围内的整数 a1, a2, a3, a4, a5。如果能从五个整数中选出三个并且这三个整数的和为 10 的倍数（包括 0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结果，显然如果有多个三元组满⾜和是 10 的倍数，剩下两个数之和对 10 取余的结果都是相同的；如果选不出这样三个整数，则这五个整数的权值为 -1。 现在给定 T 组数据，每组数据包含五个 0~9 范围内的整数，分别求这 T 组数据中五个整数的权值。 【输⼊格式】 第⼀行⼀个整数 T (1 |
输出：4（图中蓝色节点是关键节点）【本文地址】
今日新闻 |
推荐新闻 |