中科大2009年复试机试题详解

2021.5.9 549 2 分钟

题目一

题目描述

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

输入：4
输出：1

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <iostream>
using namespace std;

int main(int argc, char *argv[]) {
  int16_t num;
  cin >> num;
  num = (num ^ (num >> 4) ^ (num >> 8) ^ (num >> 12)) & 0x000f;
  cout << num << endl;
  return 0;
}

题目二

题目描述

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

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  cout << a[n/2] << endl;
  return 0;
}

题目三

题目描述

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

输入示例：
ABC00DE0000
输出示例：
B A

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


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

int depth;
int flag = 0;

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

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

int getDepth(TreeNode *t) {
  if (!t) return 0;
  return max(getDepth(t->lchild), getDepth(t->rchild)) + 1;
}

void postOrder(TreeNode *t, int dep) {
  if (!t) return;
  postOrder(t->lchild, dep + 1);
  if (dep <= depth / 2) {
    if (flag) cout << " ";
    flag = 1;
    cout << t->val;
  }
  postOrder(t->rchild, dep + 1);
}

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

中科大复试