人人网研发笔试卷A -2015年

一、单项选择题

1、 以下排序中时间复杂度最差的是（）

A、归并排序        B、选择排序        C、希尔排序        D、堆排序

2、当参数*x=1, *y=1, *z=1时，下列不可能是函数add的返回值的（）

int add(int *x, int *y, int *z){
    *x += *x;
    *y += *x;
    *z += *y;
    return *z;
 }

A、4        B、5        C、6        D、7

3、体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站到他的后面，这种站队的方法类似下列哪种算法（）

A、快速排序        B、插入排序        C、冒泡排序        D、归并排序

4、下面关于inode描述错误的是（）

A、inode和文件是一一对应的        B、inode能描述文件占用的块数

C、inode描述了文件大小和指向数据块的指针          D、通过inode实现文件的逻辑结构和物理结构的转换

5、设有一个栈，元素依次进栈的顺序是A,B,C,D,E。下列不可能的出栈顺序有（）

A、ABCDE        B、BCDEA        C、EABCD        D、EDCBA

6、某二叉树结点的中序序列为A、B、C、D、E、F、G、H，后序序列为B、D、C、A、F、G、H、E。该二叉树的层次次序序列为（）

A、E G H F A C D B        B、E A H C G B D F        C、E A G H C F B D        D、E G A C H D F B

7、假设平均每个人人用户有300个好友，则一个人人用户的3跳好友数的数量级是（）

A、十万级        B、百万级        C、千万级        D、亿级

8、下列哪些因素不会限制Linux服务器并发连接数（）

A、系统内存大小        B、系统网卡数量        C、系统最大文件句柄数量        D、系统IP地址数量

二、填空题

9、在区间[-1, 1]随意取两个数，它们的和大于1的概率是             。（分数表示）

10、n从1开始，每个操作可以对n加1或加倍，如果要使n是2014，最少需要                个操作。

三、问答题

11、给出二叉树接口为

class node
{
    node *get_left();
    node *get_right();
    int get_data();
}

找出值为val的最浅节点所在层数。int  find(node *root,intval)

12、计算机中处理乘法的指令要比加法复杂的多，因为在一些关键系统中我们常常会考虑如何尽可能减少乘法的运算。

13、下图所示，server接收调用方发送的请求（request）并转发给handler处理。每个调用方有名称（name）和优先级（weight），所有调用方发送同一种请求，而且有可能短时间内发送大量请求（请求尖峰）。Handler每秒最多能够处理N个请求。现在需要为server设计一个请求控制模块，要求：
        a)    调用方weight值越高的请求，平均等待时间越低
        b)    减小请求尖峰的冲击

参考答案

1、B    2、D    3、A    4、A    5、C    6、B    7、C    8、B

9、1/8    10、18

11、

int find(node * root, int val) {
    int ret = 1;
    if (root->get_data() == val) {
        return ret;
    } else {
        int  ret1 = 1 + find(root->get_left(), val);
        int  ret2 = 1 + find(root->get_right(), val);
        if (ret1 > ret2)
            ret = ret2;
        else
            ret = ret1;
        return ret;
    }
}

12、

function sum(int a[], int n, int x){
    s=a[n]
    for(int i=1; i<=n; i++){
        s += x*s + a[n-i]
    }
    return s;
}

13、

    a)：可使用优先级队列进行辅助，weight越大的优先级越高。由于所有请求都是同一种请求，所以可以将其统一封装管理。

在Java中可以使用 PriorityQueue<T> 进行处理，队列中存放待执行的请求。该优先级队列的元素需要继承Comparable接口用来实现比较，实现的时候用weight进行比较。

    b)：为减小尖峰的冲击，可以使用线程池，即运用线程池，将可执行的线程的最大值规定下来，当尖峰来临时，线程池可根据待执行的队列中的任务数量调用线程，当线程池中的所有线程都处于busy状态的时候，剩下的任务在队列中等待。直到有空余线程的时候，再从队列中取出任务进行操作。

    c)：该方法也可用于c）问题中，避免handler压力过大，对请求处理的线程数量进行限制，使得handler的处理能力高于最大任务量即可。