中科大2007年复试机试题

中科大2007年复试机试题文章目录中科大2007年复试机试题第一题问题描述解题思路及代码第二题问题描述解题思路及代码第三题问题描述解题思路及代码第四题问题描述解题思路及代码第一题 中科大2007年复试机试题

文章目录

• 中科大2007年复试机试题
• 第一题
• • 问题描述
  • 解题思路及代码
• 第二题
• • 问题描述
  • 解题思路及代码
• 第三题
• • 问题描述
  • 解题思路及代码
• 第四题
• • 问题描述
  • 解题思路及代码

第一题

问题描述

编写程序判断给定数字是否是回文数。 示例 1

输入12输出Y

示例 2

输入234输出N

解题思路及代码

将输入的数字当做字符串处理会简单点。与Leetcode上的题目一致。

#includeusing namespace std;int main(){ string s; while(cin>>s) { int i 0; int j s.size()-1; while(i < j) { if(s[i] ! s[j]) { cout<<"N"<问题描述

队列的循环报数问题设有n个人站成一排从左往右的编号分别为1~n现在从左往右报数“1,2,1,2…”数到“1”的人出列数到“2”的人立即站到队伍的最右端。报数过程反复进行直到n个人都出列为止。要求给出它们的出列顺序。 n从键盘输入出列顺序输出到控制台。 示例 1

输入10输出1 3 5 7 9 2 6 10 8 4

解题思路及代码

由题意得该问题涉及队列对于队列的奇偶位置上的数有不同的处理方法。

奇数位置直接弹出偶数位置先弹出再入队

重复上述操作直至队列为空。

#include #includeusing namespace std;int main(){ int n; cin>>n; queueq; for(int i 0; i < n; i) { q.push(i1); } int flag 1; while(!q.empty()) { if(flag 1) { cout<问题描述

无向图的最小生成树输入在文件3.in中给出描述了图的形状。首先给出图中结点的总数n结点编号从0到n-1然后接下来每一行给出边的信息每行包含三个数字分别是两个顶点的编号以及边长。要求出无向图对应的最小生成树将结果输出到文件3.out中。

示例 1

输入97 6 1 8 2 2 6 5 2 0 1 4 2 5 4 8 6 6 2 3 7 7 8 7 0 7 8 1 2 8 3 4 9 5 4 101 7 113 5 14输出7 -- 6 : 16 -- 5 : 28 -- 2 : 22 -- 5 : 40 -- 1 : 42 -- 3 : 71 -- 2 : 83 -- 4 : 9

解题思路及代码

求无向图的最小生成树常用的算法是prim算法和kruskal算法针对本题选择kruskal算法比较合适而且相比prim算法kruskal算法思路实现更简单复杂度一般也低。 krus算法的实现过程每次从无向图中选取边长最小的边加入最小生成树中加入时要注意不能与已经加入的顶点构成连通构成连通则需放弃加入该边如果无向图的顶点数为n那么选择n-1条符合条件的边即停止。 判断边是否连通的方法用subset[n]数组来表示每个边所在的子集序号设新加入的两个顶点的subset为i、j出现的情况为

i 0 0说明两个顶点不在其他子集中加入新的子集 i j 0两个顶点存在于相同的子集中加入的边会导致连通应该舍弃i ! j 0 0两个顶点存在与不同的子集中合并两个不同的子集((i ! 0 0) || (i 0 0))将不在任何子集中的顶点加入另一个顶点的子集

#include#include#include#includeusing namespace std;struct Edge{ int beg, eds, weight; Edge(int beg,int eds, int weight):beg(beg), eds(eds), weight(weight) {}};struct cmp //使得队列从小到大排序{ bool operator()(const Edge }};int main(){ ifstream ifs("./3.in.txt"); ofstream ofs("./3.out.txt"); int n; ifs>>n; vectorsubset(n,0); priority_queue edges; vector ans; int a,b,c; int maxid 1; while(ifs>> a >> b >> c) { edges.push(Edge(a,b,c)); } while(!edges.empty() edges.top(); edges.pop(); int i subset[e.beg], j subset[e.eds]; if(i 0 0) { subset[e.beg] subset[e.eds] maxid; ans.push_back(e); } else if(i ! j 0 0) { for(int k 0; k < subset.size();k) { if(subset[k] i) subset[k] j; } ans.push_back(e); } else if(i ! 0 0) { subset[e.eds] subset[e.beg]; ans.push_back(e); } else if(i 0 0) { subset[e.beg] subset[e.eds]; ans.push_back(e); } } for (auto } return 0;} 第四题

问题描述

中序后序得前序输入在文件4.in中给出首先给出二叉树中的顶点个数 n然后在接下来两行给出中序和后序序列要求根据中序和后序序列构建二叉树并且将二叉树的前序遍历序列输出到文件4.out中。 示例1

输入:5D B A C ED B E C A输出: A B D C E

解题思路及代码

前序根-左-右中序左-根-右后序左-右-根

根据这个特点可知后序的最后一个元素表示是根节点而在中序中根节点的左边为左子树右边为右子树故可根据这个特点将其分为两个子树然后不断循环从而构造该二叉树之后再前序遍历该二叉树。 设后序遍历的根节点在中序遍历的位置为iin数组的范围为[l1,r1],out数组的范围为[l2,r2]

左子树在in数组的位置: l1 ~ i-1 在post数组的位置: l2 ~ l2i-1-l1右子树在in数组的位置: i1 ~ r1 在post数组的位置: l2i-l1 ~ r2-1

该题与Leetcode上的题目类似。

#include#include#includeusing namespace std;struct TreeNode{ char val; TreeNode *lchild, *rchild; TreeNode(char val):val(val){}};TreeNode *make(vector in, vector post,int l1,int r1,int l2,int r2){ if(l1 > r1) return NULL; TreeNode *t new TreeNode(post[r2]); int i; for(i l1; i < r1; i) { if(in[i] post[r2]) { break; } } t->lchild make(in,post,l1,i-1,l2,l2i-1-l1); t->rchild make(in,post,i1,r1,l2i-l1,r2-1); return t;}TreeNode *buildTree(vector in, vector post){ TreeNode *root make(in,post,0,in.size()-1,0,post.size()-1); return root;}void inOrder(TreeNode *root,ofstream NULL) { ofslchild,ofs); inOrder(root->rchild,ofs); } else { return; }}int main(){ ifstream ifs("./4.in.txt"); ofstream ofs("./4.out.txt"); int n; ifs>>n; vectorin(n),post(n); for(int i 0; i < n; i) { ifs >> in[i]; } for(int i 0; i < n; i) { ifs >> post[i]; } TreeNode *root buildTree(in,post); inOrder(root,ofs); return 0;}

该机试题所有代码均已上传下载地址 https://download.csdn.net/download/LOVE_105/87381486