人人网研发笔试卷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、计算机中处理乘法的指令要比加法复杂的多,因为在一些关键系统中我们常常会考虑如何尽可能减少乘法的运算。

现在有如下的表达式
        y= anxn+an-1xn-1 +…..+a1x +a0
其中an, an-1, ….a1, a0是常数, 给一个x, 要求尽快算出y的值。请尝试写出这样的一个函数。

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

        c)     不能导致handler压力过大


参考答案

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的处理能力高于最大任务量即可。


个人资料
Bingo
等级:9
文章:694篇
访问:38.9w
排名: 1
推荐
欢迎关注 “BAT笔试面试” 微信公众号
全栈面试题,你想要的都在这^_^
上一篇: 人人网前端工程师笔试卷-2011年
下一篇:人人网研发试卷B-2015年
猜你感兴趣的圈子:
人人网笔试面试圈
标签: inode、尖峰、ret、handler、ret1、面试题