2016届 阿里巴巴校招研发工程师C/C++笔试题--2015.08.23

附加题总共三道，如下：

题目一：

给出一组整数对 {(a[0], b[0]), (a[1], b[1]) ... (a[n-1], b[n-1]) }，所有 a 值 和 b 值分别不重复（任意 i!= j 满足 a[i] != a[j] 且 b[i] != b[j]）。构造一棵 n 结点的二叉树，将这 n 个整数对分配到各个结点上。根和所有子树满足以下条件：

1) 所有结点的 a 值满足二叉查找树的顺序，即 left->a< root->a && root->a < right->a；

2) 所有结点的 b 值满足最大堆的顺序，即 root->b> left->b && root->b > right->b。

 

问题一：实现 build 函数，输入 n 个整数对，返回一棵构造好的二叉树。

struct pair_t {
    int a, b;
};
struct node_t {
    int a, b;
    node_t *left, *right;
};
node_t* build(pair_t* pair, int n);

例如，输入是 {(5, 8), (2, 10), (4, 3), (1, 5),(0, 2), (9, 1)}，输出是下列二叉树：

提示：1) 构造出的二叉树的形态是存在且唯一的。 2) 想办法确定树根。

 

问题二：已知满足上述条件的二叉树，设计算法实现插入一个整对 (a, b)，使新的二叉树仍满足上述条件。该算法比较复杂，候选人只需描述思路。

思路：

要求的树是笛卡尔树，参考百度百科：http://baike.baidu.com/link?url=FpWeU_PlLS3F5hlkk0zGHun18lUzqbx6Q56sx3ZMrqKXaz-BBKd7IFo5AUKLFR8OJpz28IhsoOUlCTzw8SKj5K。

题目二：

假设目前有3个程序A, B和C，需要相互传输数据，我们需要给做一个中转程序P。
A 读写的数据是经过某压缩格式azip压缩过的。
B 读写的数据需要base64编码。
C 读写数据需要压缩格式bzip压缩后base64编码。


现在假设已有工具函数 ：

std::string azip(const std::string& input);
std::string aunzip(const std::string& input);
std::string base64encode(const std::string& input);
std::string base64decode(const std::string& input);
bool bzip(const std::string& input, std::string* output);
bool bunzip(const std::string& input, std::string* output);

请给中转程序P设计格式转换的工具类。注意设计的通用性，比如：可能有新的角色加入，要求给做加密解密等。

题目三：

待更新……