人人 2021 研发岗面试题

 一、单选题

3417（34的17次方）对6取余， 结果是多少？

A  2

B  3

C  4

D  5

 C

34^17=(30+4)^17，然后二项展开，30^17能被6整除，且展开项中只要有30的项都能被7整除，余数必然在4^17中产生，容易得到，4任意次方的余数都是4。所以答案是4。

第2题：

 有如下算式成立，13*7=88，是采用（）进制计算的。

A  14

B  13

C  12

D  11

 B

14进制换算成10进制  如a选项计算（14+3）*7是否等于8*14+8 

以此类推哪个成立选哪个

答案是b

第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  冒泡排序

 A

应该是希尔排序，是中间相隔5个字母进行的希尔排序，第一次比较是：Q-M H-N C-R Y-D P-F A-X依次比较交换位置。

第4题：

 二叉排序树中的最小值在二叉排序树的何处?

A  只能在根节点

B  只能在叶子节点

C  可能在叶子节点， 也可能在根节点，也可能在只有右孩子的父节点

D  可以在任何节点

 C

二叉排序树中的最小值节点就是最左边的那个，当只有一个根节点的时候，最小值就位于根节点了。

第5题：

 一个含有n个顶点和e条边的简单无向图， 在其邻接矩阵存储结构中共有（）个零元素。

A  e

B  2e

C  n的2次方-e

D  n的2次方-2e

 D

因为有n个顶点，所以有n*n个元素，2*e个非零元素（无向图，对称），所以有n*n-2*e个零元素。

第6题：

 下面程序中， 输出是什么？

int fun(int x){

    int count = 0;

    while(x){

        count++;

        x = x &(x-1)

    }

    return count;

}

int main(){

    cout << "fun(2021)=" << fun(2021)<

}

A  fun(2021)=11

B  fun(2021)=10

C  fun(2021)=9

D  fun(2021)=8

 B

本题是统计一个数有多少个1的，2021=11111011111共10个1.

第7题：

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

A  2

B  3

C  4

D  5

 C

4台，当5个进程的时候如果都同时申请到了1台，就发生死锁了。如果是4个进程，那必然有一个能申请到2台。

第8题：

 通过文件名存取文件时，文件系统内部的操作过程是通过？

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

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

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

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

 C

如果一个文件有多个数据块，这些数据块很可能不是连续存放的，应该如何寻址到每个块呢？实际上，根目录的数据块是通过其inode中的索引项Blocks[0]找到的，事实上，这样的索引项一共有15个，从Blocks[0]到Blocks[14]，每个索引项占4字节。前12个索引项都表示块编号，例如上面的例子中Blocks[0]字段保存着24，就表示第24个块是该文件的数据块，如果块大小是1KB，这样可以表示从0字节到12KB的文件。如果剩下的三个索引项Blocks[12]到Blocks[14]也是这么用的，就只能表示最大15KB的文件了，这是远远不够的，事实上，剩下的三个索引项都是间接索引。

第9题：

 以下哪个协议不是无状态协议？

A  TCP协议

B  HTTP协议

C  UDP协议

D  FTP协议

 A

无状态服务器是指一种把每个请求作为与之前任何请求都无关的独立的事务的服务器  

<>(第二版)第546页有这样一句话:    
     虽然HTTP使用TCP的服务,但HTTP本身是无状态协议.客户发送请求报文来初始化这个事务.服务器发送响应来回答.  

暗示了TCP协议是一个有状态的协议

第10题：

 二、填空题

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

 37/12

平均查找长度公式为：ASL={[(n+1)/n]*log2^(n+1)}-1，也可以直接算出来，1*1+2*2+3*4+4*5=37，故其次数为37/12。

第11题：

 （a1+a2+a3+…+an)/b与a1/b+a2/b+…an/b（除法为整除）最大差值为 _______  。

 n-1

假设a[i]=m[i]*b+(b-x[i]),m[i]为整数,x[i]趋近于0，sum = x[i](i =  0->n),sum也趋近于0

令X =（a1+a2+...+an）/b = m[1]+m[2]+m[3]...+m[n]+(n*b-sum)/b;

  Y = a1/b+a2/b+...+an/b = m[1]+m[2]+...+m[n];

  X-Y=(n*b-sum)/b

  [X-Y] = n-1;([]表示取整数，因为X-Y = n-sum/b

第12题：

 三、问答题

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

#include

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<

    return 0;

}

第13题：

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

 使用递归方法，可以使用前序遍历，首先分别计算左右子树各自的子树和，然后记录目前最大的；

再加入当前的父节点，再计算父节点开头的子树是否最大；该层递归上去即可。

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                 maxRoot = root.left;
            if(maxRoot.tag                 maxRoot = root.right;
            return root.tag+lSum+rSum;
        }
    }
}

第14题：

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

拿分法宝：

1） 新鲜事ID绝对不能重复

2）你可以借助DB等辅助工具，提供InsertDB， UpdateDB， QueryDB三API供你使用， 假设访问DB不会有异常。
3)  高并发情况要考虑， 提供Lock, Unlock两个API供你使用。
4） 要求写出解题思路和伪代码出来。

 解题思路：

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；

}

}