中科大2009年复试机试题

第一题

问题描述

输入0~65535之间的十进制数。进行如下处理比如输入4转化为16位二进制数0000 0000 0000 01004个一组相异或变为0001然后把0001转化为十进制的1然后输出。
示例 1

输入4
输出1

解题思路及代码

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 0, s;
    for(int i = 0; i < 16; i++)
    {
       if(i % 4 == 0)
       {
           s = (n & 1);
       }
       else
       {
           s ^= (n & 1);
           if(i % 4 == 3)
           {
               ans += (s << (i-3)/4);
           }
       }
       n >>= 1;
    }
    cout << ans <<endl;
    return 0;
}

第二题

问题描述

处理将n个数由小到大排序如果n是奇数输出正中间的数如果n是偶数输出正中间的两个数。
示例 1

输入6 1 2 5 4 7 6
输出4 5

解题思路及代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> res(n);
    for(int i = 0; i < n; i++)
    {
       cin >> res[i];
    }
    sort(res.begin(), res.end());
    if(n % 2 == 1)
    {
        cout << res[n/2]<<endl;
    }
    else
    {
        cout << res[(n-1)/2] <<" "<<res[n/2]<<endl;
    }
    return 0;
}

第三题

问题描述

读入文件tree.in中的二叉树先序序列0表示叶子。中序输出深度≤depth/2的结点其中depth是你所建立的树的深度。

示例 1

输入ABC00DE0000
输出B A

解题思路及代码

本题需要先建树然后再计算树的深度通过中序遍历求出每个结点的深度并输出符合条件的结点。

#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
  TreeNode *lchild, *rchild;
  char val;
  TreeNode(char val) : val(val) {}
};

TreeNode *buildTree(vector<char> v, int &idx) //建树
{
  if (v[idx] == '0') return NULL;
  TreeNode *t = new TreeNode(v[idx]);
  t->lchild = buildTree(v, ++idx);
  t->rchild = buildTree(v, ++idx);
  return t;
}

int getDepth(TreeNode *t)//计算树的高度
{
    if(t == NULL) return 0;
    return max(getDepth(t->lchild),getDepth(t->rchild)) + 1;
}
void postOrder(TreeNode *root,int depth1, int depth)//中序输出结果
{
    if(root == NULL) return;
    postOrder(root->lchild, depth1+1, depth);
    if(depth1 <= depth/2)
    {
        cout<<root->val <<" ";
    }
    postOrder(root->rchild, depth1+1, depth);

}
int main()
{
    ifstream ifs("./tree.in.txt");
    char c;
    vector<char> v;
    while(ifs>> c)
    {
        v.push_back(c);
    }
    int idx = 0;
    TreeNode *root = buildTree(v,idx);
    int depth = getDepth(root);
    postOrder(root,1,depth);
    return 0;
}

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