人人网研发试卷E-2015年

一、单项选择题

1、3417(34的17次方)对6取余, 结果是多少()

A、2        B、3        C、4        D、5

2、有如下算式成立,13*7=88,是采用()进制计算的

A、14        B、13        C、12        D、11

3、有字符序列(Q,H,C,Y,P,A,M,N,R,D,F,X),新序列(M,H,C,D,F,A,Q,N,R,Y,P,X)是下列()排序算法一趟扫描结果

A、希尔排序        B、快速排序        C、堆排序        D、冒泡排序

4、二叉排序树中的最小值在二叉排序树的何处()

A、只能在根节点        B、只能在叶子节点

 C、可能在叶子节点, 也可能在根节点,也可能在只有右孩子的父节点        D、可以在任何节点

5、一棵树用左儿子右兄弟表示法呈如下结构,请问这棵树原先结构前序遍历是()

                                        

A、ABFEDC        B、ABCEFD        C、ABDCEF        D、ADCEFB

6、一个含有n个顶点和e条边的简单无向图, 在其邻接矩阵存储结构中共有()个零元素

A、e        B、2e        C、n的2次方-e        D、n的2次方-2e

7、下面程序中, 输出是什么()

int fun(int x){
    int count = 0;
    while(x){
        count++;
        x = x &(x-1)
    }
    return count;
}
int main(){
    cout << "fun(2015)=" << fun(2015)<<endl;
}

A、fun(2015)=11        B、fun(2015)=10        C、fun(2015)=9        D、fun(2015)=8

8、若系统中有五台绘图仪,有多个进程均需要使用两台,规定每个进程一次仅允许申请一台,则至多允许()个进程参于竞争,而不会发生死锁

A、2        B、3        C、4        D、5

9、通过文件名存取文件时,文件系统内部的操作过程是通过()

A、文件在目录中查找文件数据存取位置

B、文件名直接找到文件的数据,进行存取操作

C、文件名在目录中查找对应的i节点,通过i节点存取文件数据

D、文件名在目录中查找对应的超级块,在超级块查找对应i节点,通过i节点存取文件数据

10、以下哪个协议不是无状态协议()

A、TCP协议        B、HTTP协议        C、UDP协议        D、IP协议

二、填空题

11、12个元素的排序数组进行二分查找,每个元素被查找的概率是相等的,平均比较次数为            

12、(a1+a2+a3+…+an)/b与a1/b+a2/b+…an/b(除法为整除)最大差值为             

三、问答题

13、有如下图所示(左)的一棵二叉树, 请设计一种遍历方式,使得按照如下方式(右)输出各个元素:(从下到上, 从右到左输出, 要求每层之间换行, 同行元素之间用tab分割,写出完整代码)。

                                 

14、某星球上出现了一种怪物, 这种怪物是单亲繁殖,从出生起第3个月起每个月就能繁衍一批后代共m个,但是这种怪物很短命,生存第5个月后就会毙命。目前该星球有一个这样的怪物,请编写程序计算n个月后怪物的总数。(这里我们假定第5个月怪物繁衍后再毙命)

15、有一个二叉树, 节点全部为整数,如何找到一个子树,它所有节点的和最大?要求编程序实现。

16、一般在大型系统中,都会为每个资源分配一个唯一的ID,在大型系统中这个并非易事,目前人人网一天产生新鲜事在千万量级,现在由你来设计一个产生新鲜事ID的模块。要求写出解题思路和伪代码。

拿分法宝:
    1) 新鲜事ID绝对不能重复
    2)你可以借助DB等辅助工具,提供InsertDB, UpdateDB, QueryDB三API供你使用, 假设访问DB不会有异常。
    3)  高并发情况要考虑, 提供Lock, Unlock两个API供你使用。
    4) 要求写出解题思路和伪代码出来。


参考答案

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

11、37/12

12、n-1

13、参考代码:

// 逆序 BFS 搜索
void reverseBFS(Tree *t)
{
    if(NULL == t)
    {
        return;
    }
    vector<vector<char>> vv;
    queue<Tree*> que;
    que.push(t);
    int length = 1;
    while(!que.empty())
    {
        vector<char> v;
        while(length != 0)
        {
            Tree *t = que.front();
            //cout<<t->data<<endl;
            que.pop();
            if(t->left)
            {
                que.push(t->left);
            }
            if(t->right)
            {
                que.push(t->right);
            }
            v.push_back(t->data);
            v.push_back('   '); 
            length--;
        }
        v.push_back('\n');
        vv.push_back(v);
        length = que.size();
    }
    //cout<<vv.size()<<endl;
    for (int i = vv.size() - 1; i >= 0; i--)
    {
        vector<char> v = vv[i];
        for(int j = 0; j < v.size(); j++)
        {
            cout<<v[j];
        }
    }
}

14、参考代码:

#include <iostream>
using namespace std;
int sum(int n,int m)
{
    int res=1;
    int A[100];
    A[0]=1;
    A[1]=0;
    A[2]=0;
    if(n<3)
        return res;
    for(int i=3;i<=n;i++)
    {    
        A[i]=(res-A[i-1]-A[i-2])*m;
        res+=A[i];
        if(i>=5)
            res-=A[i-5];
    }
    return res;
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<sum(n,m)<<endl;
    return 0;
}

15、

思路:使用递归方法,可以使用前序遍历,首先分别计算左右子树各自的子树和,然后记录目前最大的;再加入当前的父节点,再计算父节点开头的子树是否最大;该层递归上去即可。

参考代码:

public class MaxSumSubTree {
    class TreeNode{
        TreeNode left,right;
        int tag;
        TreeNode(int tag){
            this.tag = tag;
        }
    }

    private TreeNode maxRoot = new TreeNode(0);
    public int find(TreeNode root){
        if(root==null){
            return 0;
        } else{
            int lSum = find(root.left);
            int rSum = find(root.right);
            if(maxRoot.tag<lSum)
                maxRoot = root.left;
            if(maxRoot.tag<rSum)
                maxRoot = root.right;
            return root.tag+lSum+rSum;
        }
    }
}

16、

思路:

1)使用单例模式。定义一个sequenceGenerator单例类, 声明一个getSequence方法,将sequence序号依次相加 。

2)产生 ID 的规则是:将 ID设置为字符串。ID =  当前日期+整型sequence。

伪代码:

public class SequenceGenerator { 
    private SequenceGenerator generatorInstance = null; 
    private long sequence = 0; 
    private SequenceGenerator (){} 
    public static SequenceGenerator getInstance(){ 
        if(generatorInstance == null){ 
            synchoronized(this){ 
                generatorInstance = new SequenceGenerator (); 
            } 
            return generatorInstance  ; 
        } 
    } 
    public synchronized int getSequence(){ 
        if(++sequence没有超过long型的最大值)return sequence;     
    } 
} 


个人资料
Bingo
等级:9
文章:694篇
访问:38.9w
排名: 1
推荐
欢迎关注 “BAT笔试面试” 微信公众号
全栈面试题,你想要的都在这^_^
上一篇: 人人网研发试卷D-2015年
下一篇:迅雷C++笔试卷B-2013年
猜你感兴趣的圈子:
人人网笔试面试圈
标签: sequencegenerator、怪物、maxroot、treenode、fun、面试题