【阿里】算法工程师笔试【2015.04.02】

选择题
1、在网络传输数据时，经常需要将二进制数据转换为一个可打印字符串。一般用到的可打印字符集合包含64个字符，因此又称为Base64表示法。现有一个char数组长度为12，要将它表示为Base64字符串，请问Base64字符串最少需要____ 个char；如果char数组长度为20，则需要____个char。
A. 9,15
B. 9,16
C. 16,24
D. 16,28
E. 18,30
F. 18,32

2、数字(100!)后面有__个0。
解析：
24个，分解质因数有24个5

3、假设支付宝红包口令支持1到6位的数字组合，即’0’、’1’、’003’和’999999’都是合法的红包口令，那么总共可以有多少个合法的红包口令____。
1111110

4、给定一个整数sum，从有N个无序元素的数组中寻找元素a、b、c、d，使得 a+b+c+d =sum，最快的平均时间复杂度是____。
A. O(N^2)
B. O(log N)
C. O(N)
D. O(N^3)
E. O(N^2LogN)
F. O(N^4)

5、设一组初始记录关键字序列为(4,1,7,6,3,2,5)，则根据这些记录关键字构造的二叉排序树的平均查找长度约为__。
A. 1.7
B. 1.8
C. 1.9
D. 2.0
E. 2.1
F. 2.2
（D）

6、小赵和小钱二人分别从寝室和图书馆同时出发，相向而行。过了一段时间后二人在中途相遇，小赵继续向图书馆前进，此时：若小钱继续向寝室前进，则当小赵到达图书馆时，小钱离寝室还有600米；若小钱立即折返向图书馆前进，则当小赵到达图书馆是，小钱离图书馆还有150米。那么图书馆与寝室间的距离是__。
A. 1300m
B. 1250m
C. 800m
D. 1050m
E. 1100m
F. 900m

7、有8只球队，采用抽签的方式随机配对，组成4场比赛。假设其中有3只强队，那么出现强强对话（任意两只强队相遇）的概率是__。

8、已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行__次探测。
A. n-1
B. n
C. n+1
D. n(n+1)
E. n(n+1)/2
F. 1+n(n+1)/2

9、下面代码在64位Linux系统编译执行，输出结果是__。

#include 
void func() {
    static int b;
    printf("%d", b);
}
int main() {
    static int b = 20;
    func();
}

A. 0
B. 20
C. 输出不确定
D. 编译错误
E. 运行出错
F. 以上均不正确

10、将整数序列（7-2-4-6-3-1-5）按所示顺序构建一棵二叉排序树a（亦称二叉搜索树），之后将整数8按照二叉排序树规则插入树a中，请问插入之后的树a中序遍历结果是__。
A. 1-2-3-4-5-6-7-8
B. 7-2-1-4-3-6-5-8
C. 1-3-5-2-4-6-7-8
D. 1-3-5-6-4-2-8-7
E. 7-2-8-1-4-3-6-5
F. 5-6-3-4-1-2-7-8

11、下面的SELECT语句查询返回的结果是__。

SELECT pay_month, seller_id, pay_amount FROM (select to_char(pay_date,'yyyymm') as pay_month, seller_id, sum(pay_amount) as pay_amount, row_number() over(partition by to_char(pay_date,'yyyymm') order by sum(pay_amount) desc) as rn from orders group by to_char(pay_date,'yyyymm'),seller_id ) t WHERE rn <= 10 ORDER BY pay_month, pay_amount DESC;

A. 返回任意10个卖家的 销售月份、卖家ID、月度销售额
B. 返回销售额TOP10卖家的 销售月份、卖家ID、月度销售额，且结果根据销售月份和销售金额都进行降序排列
C. 返回每月销售额TOP10卖家的 销售月份、卖家ID、月度销售额，且结果根据销售月份升序和销售金额降序排列
D. 返回每月卖家的销售月份、卖家ID、月度销售额，且结果根据销售月份升序和销售金额降序排列
E. 返回销售额最高卖家所发生的 销售月份、卖家ID、月度销售额

12、A，B，C三位同学都是很聪明的同学，面试官给他们背上依次贴上了数字2，4，8，他们都能看见别人的数字但无法看见自己的数字，现在面试官告诉他们这些数字都是自然数并且构成一个等比数列，让A、B、C同学依次循环回答是否确定自己的数字是多少，每位同学的回答算作一次，经过__次有同学能准确说出自己的数字。
A. 2
B. 3
C. 4
D. 5
E. 6
F. 7

13.以下程序输出是__。

#include 
using namespace std;
int main(void)
{
    const int a = 10;
    int * p = (int *)(&a);
    *p = 20;
    cout<<"a = "<", *p = "<<*p<return 0;
}

A. 编译阶段报错
B. 运行阶段报错
C. a = 10, *p = 10
D. a = 20, *p = 20
E. a = 10, *p = 20
F. a = 20, *p = 10

15、以下关于STL的描述中，__是错的。
A. STL容器是线程不安全的
B. 当容量不够时，vector内部内存扩展方式是翻倍
C. std::string中可以存储多个’\0’字符
D. std::bitset不是一个STL容器
E. std::stack是用deque实现的
F. std::sort可能是不稳定排序

16、以下是一个有向图，我们从节点B开始进行深度优先遍历（DFS），那么以下5个序列中，所有正确的DFS序列是__。

1、BADECF 2、BADEFC 3、BCAFDE 4、BCFDEA 5、BFDECA
A. 245
B. 24
C. 13
D. 123
E. 12345
F. 12

17、

附加题

1、给定两个已经排序好的数组int A[], int B[], 长度分别为m, n，找到两者所有元素的中位数。
函数接口：

class Solution { 
public: 
    double findMedianSortedArrays(int A[], int m, int B[], int n) { 

    } 
};

2、在一个2.5D游戏里，有很多物品，例如小人、树木和房子，当我们鼠标在界面上点击时，如何判断点中了哪个物品。请用合适的数据结构和算法对这个问题建模，并给出伪代码示例。

3、【题目】：输入一个非负整形数组，其中每个数代表紧挨着的宽为1的墙的高度，输出这些墙之间能积水的体积。函数接口为 int Volume(int * height,int n)，要求只能遍历一 遍数组，且空间复杂度为O(1)。【示例】：input：([1,0,2,1,0,1,3,2,1,2,1],11)（如下图所示），output:6。

1与3均为LeetCode上面的题~