人人 2021 研发岗面试题

 一、单选题

下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是

A  插入排序

B  堆排序

C  冒泡排序

D  快速排序

 B

堆排序

有影响就是这个排序算法最好情况和最差情况的时间复杂度不同。对于无影响，我们只要找最好情况和最差情况时间复杂度一样的算法就可以了，所以是堆排序

 在以下哪个操作中， 数组比链表更快?

A  原地逆序

B  头部插入

C  返回头节点

D  返回随机节点

 D

给下标直接寻址

 假设某个广告展现后被点击的概率是1/3（实际远小于这个数，只是为方便计算），那该广告3次展现，被点击次数少于2次的概率是?

A  0.74

B  0.30

C  0.26

D  0.70

 A

题中指出2次展现，点击少于2次，即0,1,点击概率为1/3，没有点击为2/3

0次的情况有 C(3,0)(2/3)^3 = 8/27

1次的情况有 C(3,1)(2/3)^2*(1/3) = 12/27

8/27+12/27 = 20/27 约为0.74

 式子7*15=133成立，则用的是几进制?

A  7

B  8

C  9

D  11

 B

15八进制转化为十进制13

133八进制转化为十进制91

7*13=91

若系统中有5个同类资源，有多个进程均需要使用2个，规定每个进程一次仅允许申请1个，则至多允许几个进程参于竞争，而不会发生死锁?

A  5

B  2

C  3

D  4

 D

哲学家就餐问题，5个进程相当于5只筷子，4个哲学家中有一个能申请到2个资源，用完释放让其他人使用

 在支持多线程的系统中，进程P创建的若干线程不能共享的是？

A  进程P的代码段

B  进程P中打开的文件

C  进程P的全局变量

D  进程P中某线程的栈指针

 D

进程中的线程共享进程中的全部资源，但进程中某线程的栈指针对其它线程是透明的，不能与其它线程共享

 crontab文件由6个域组成，每个域之间用空格分隔，下列哪个排列方式是正确的？

A  MIN HOUR DAY MONTH YEAR COMMAND

B  MIN HOUR DAY MONTH DAYOFWEEK COMMAND

C  COMMAND HOUR DAY MONTH DAYOFWEEK

D  COMMAND YEAR MONTH DAY HOUR MIN

 B

# Example of job definition:
# .---------------- minute (0 -  59)
# |  .------------- hour (0 - 23)
# |  |  .---------- day  of month (1 - 31)
# |  |  |  .------- month (1 - 12) OR  jan,feb,mar,apr ...
# |  |  |  |  .---- day of week (0 - 6)  (Sunday=0 or 7) OR sun,mon,tue,wed,thu,fri,sat
# |  |  |  |  |
 # *  *  *  *  * user-name command to be executed

 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为?

A  CBEFDA

B  FEDCBA

C  CBEDFA

D  不定

 A
前序和中序遍历可以唯一确定一颗二叉树

 以下哪个功能比较适合使用UDP协议？

A  数据多播

B  可靠连接

C  流量控制

D  拥塞控制

 A

UDP不用建立连接，所以不可能是BCD，并且适合多播

调用recv(int sockfd, void *buf, size_t len, int flags)的过程中，一共进行了几次内存复制操作？

A  1

B  2

C  3

D  4

 B

recv是流式的，其返回长度不固定。故内部需要有一个反冲buf

 二、填空题

在一个请求页式存储管理系统中，进程P共有5页，访问序列为3，2，1，0，3，2，4，3，2，1，0，4，当分配给该进程的页帧数为3时，使用FIFO置换算法访问过程中缺页率为_______，使用LRU算法的缺页率为_______。(小数点后保留三位)

 0.75

0.833

FIFO

页面走向：3,2,1,0,3,2,4,3,2,1,0,4

页架数目：3,2,1,0,3,2,4,4,4,1,0,0

                     3,2,1,0,3,2,2,2,4,1,1

                        3,2,1,0,3,3,3,2,4,4

                -  -  -  -  -  -  -  +  +  -  -  +

“-”表示缺页，“+”表示命中

缺页率为：9/12 = 0.750 (三位小数)

LRU

页面走向：3,2,1,0,3,2,4,3,2,1,0,4

页架数目：3,2,1,0,3,2,4,3,2,1,0,4

                     3,2,1,0,3,2,4,3,2,1,0

                        3,2,1,0,3,3,4,3,2,1

                     - - - - - - - + + - - -

缺页率为：10/12 = 0.833

 2021! 的末尾有_______ 个0？

 501

末尾为0，主要看乘积项中2和5的个数，由于2的个数明显比5多，则只需看5的个数即可

2021/5 = 402....4

2021/25 = 80....14

2021/125 = 16....14

2021/625 = 3....19

故2021！末尾0的个数为402+80+16+3 = 501

 三、问答题

给定一个包含大小写字母，数字，运算符的字符串，要求设计一次遍历，空间复杂度为o(1) 的算法，使得大写字母在一起，小写字母在一起，数字在一起，运算符在一起。

按ASCII码排序 

第14题：

 反螺旋矩阵：随机给定N*M个数（无重复），先将这N*M个数排序，然后升序放置到螺旋矩阵当中：
如，给定3*5共15个数1-15，则螺旋矩阵输出如下：
1   2  3  4  5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8

N = 4

M = 5

l = []

for i in xrange(1, 1 + N*M):

 l.append(i)

m = [[None]*M for i in xrange(N)]

step = [(0, 1), (1, 0), (0, -1), (-1, 0)]

d = 0

s = (0, 0)

for num in l:

 m[s[0]][s[1]] = num

 ns = (step[d][0] + s[0], step[d][1] + s[1])

 if ns[0] >= N or ns[1] >= M or m[ns[0]][ns[1]] is not None:

 d = (d + 1) % 4

 ns = (step[d][0] + s[0], step[d][1] + s[1])

 s = ns

for i in m:

 print i

第15题：

 对一个unsigned int32型数组a进行排序，记ni为a[i]的二进制表示中"1"的数量，指定排序策略如下：
a)            如果ni < nj，则a[i]排在a[j]前面
b)           如果ni == nj，按值从小到大排序

 # include
#include
#include
#include
int fun1(int x)
{
 int count  = 0;
 while(x)
 {
  count++;
  x=x&(x-1);
 }
 return count;
}
void swap(int *i,int *j)
{
 *i = *i^*j;
 *j = *i^*j;
 *i = *i^*j;
}
int main()
{
  int n =5;
  int a[n];
  int x;
  int count1,count2;
  for (int i = 0; i < n; ++i)
  {
  printf("please input the number:\n");
  std::cin>>x;
  a[i] = x;
  }
  for (int i = 1; i < n; ++i)
  {
   for (int j = n-1; j >=i; --j)
   {
      count1 = fun1(a[j]);
      count2 = fun1(a[j-1]);
      if(count1 == count2)
      {
       if(a[j]        else continue;
      }
      else if(count1 < count2)   swap(&a[j],&a[j-1]);
      else continue;
   }
  for (int i = 0; i < n; ++i)
  {
   std::cout<   }
  printf("\n");
  }

}