中科大2007年复试机试题

文章目录

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

第一题

问题描述

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

输入：12
输出：Y

示例 2

输入：234
输出：N

解题思路及代码

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

#include<iostream>
using 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"<<endl;
                break;
            }
            i++;
            j--;
        }
        if(j == i)
        {
            cout<<"Y"<<endl;
        }
    }
    return 0;
}

第二题

问题描述

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

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

解题思路及代码

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

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

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

#include <iostream>
#include<queue>
using namespace std;
int main()
{
    int n;
    cin>>n;
    queue<int>q;
    for(int i = 0; i < n; i++)
    {
        q.push(i+1);
    }
    int flag = 1;
    while(!q.empty())
    {
      if(flag == 1)
      {
          cout<<q.front()<<" ";
          q.pop();
          flag = 0;
      }
      else
      {
          int tmp = q.front();
          q.pop();
          q.push(tmp);
          flag = 1;
      }
    }

    return 0;
}

第三题

问题描述

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

示例 1

输入：
9
7      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    10
1      7    11
3      5    14
输出：
7 -- 6 : 1
6 -- 5 : 2
8 -- 2 : 2
2 -- 5 : 4
0 -- 1 : 4
2 -- 3 : 7
1 -- 2 : 8
3 -- 4 : 9

解题思路及代码

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

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

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using 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 &l, const Edge &r)
    {
        return l.weight > r.weight;
    }
};
int main()
{
    ifstream ifs("./3.in.txt");
    ofstream ofs("./3.out.txt");
    int n;
    ifs>>n;
    vector<int>subset(n,0);
    priority_queue<Edge,vector<Edge>,cmp> edges;
    vector<Edge> ans;
    int a,b,c;
    int maxid = 1;
    while(ifs>> a >> b >> c)
    {
        edges.push(Edge(a,b,c));
    }
    while(!edges.empty() && ans.size() < n-1)
    {
        Edge e = edges.top();
        edges.pop();
        int i = subset[e.beg], j = subset[e.eds];
        if(i == 0 && j == 0)
        {
            subset[e.beg] = subset[e.eds] = maxid++;
            ans.push_back(e);
        }
        else if(i != j && i != 0 && j != 0)
        {
            for(int k = 0; k < subset.size();k++)
            {
                if(subset[k] == i)
                    subset[k] = j;
            }
            ans.push_back(e);
        }
        else if(i != 0 && j == 0)
        {
            subset[e.eds] = subset[e.beg];
            ans.push_back(e);
        }
        else if(i == 0 && j != 0)
        {
            subset[e.beg] = subset[e.eds];
            ans.push_back(e);
        }
    }
    for (auto &e : ans)
    {
        ofs<<e.beg<<"--"<<e.eds<<" :"<<e.weight<<endl;
    }
    return 0;
}

第四题

问题描述

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

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

解题思路及代码

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

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

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

该题与Leetcode上的题目类似。

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
struct TreeNode
{
    char val;
    TreeNode *lchild, *rchild;
    TreeNode(char val):val(val){}
};
TreeNode *make(vector<char> in, vector<char> 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,l2+i-1-l1);
    t->rchild = make(in,post,i+1,r1,l2+i-l1,r2-1);
    return t;

}
TreeNode *buildTree(vector<char> in, vector<char> post)
{

    TreeNode *root = make(in,post,0,in.size()-1,0,post.size()-1);
    return root;

}
void inOrder(TreeNode *root,ofstream &ofs)
{
    if(root != NULL)
    {
        ofs<<root->val<<" ";
        inOrder(root->lchild,ofs);
        inOrder(root->rchild,ofs);
    }
    else
    {
        return;
    }
}
int main()
{
    ifstream ifs("./4.in.txt");
    ofstream ofs("./4.out.txt");
    int n;
    ifs>>n;
    vector<char>in(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