人人 2021 研发岗面试题

 一、单选题

有字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）,新序列（F,H,C,D,A,M,P,S,R,Y,Q,X）是下列（ ）排序算法一趟扫描结果。

A  堆排序

B  快速排序

C  希尔排序

D  冒泡排序

 B

以M为基准，或者P

第2题：

当一个二叉排序树左右子树都不为空时，二叉排序树中的最大值在二叉排序树的何处?        

A  根节点

B  叶子节点

C  父节点

D  兄弟节点

 B

二叉排序树（Binary    Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；    （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；  

第3题：

以下哪种排序是稳定的？      

A  希尔排序

B  堆排序

C  冒泡排序

D  快速排序

 C

堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

第4题：

使用 char* p = new char[100]申请一段内存，然后使用delete p释放，有什么问题？      

A  会有内存泄露

B  不会有内存泄露，但不建议用

C  编译就会报错，必须使用delete []p;

D  编译没问题，运行会直接崩溃

 B
C++告诉我们在回收用 new 分配的单个对象的内存空间的时候用 delete，回收用 new[]   分配的一组对象的内存空间的时候用 delete[]。
关于 new[] 和 delete[]，其中又分为两种情况：(1)   为基本数据类型分配和回收空间；(2) 为自定义类型分配和回收空间。
基本类型的对象没有析构函数，所以回收基本类型组成的数组空间用   delete 和 delete[] 都是应该可以的；但是对于类对象数组，只能用 delete[]。
   所以一个简单的使用原则就是：new 和 delete、new[] 和 delete[] 对应使用。

第5题：

 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为哪一项？

A  s->next=p->next；p->next=s；

B  q->next=s； s->next=p；

C  p->next=s->next；s->next=p；

D  p->next=s；s->next=q；

 B         

B 是正确的，q p都是指针，拥有独立的一段内存空间，q指向A，p指向B,意味着单独保存起A B节点的地址，p->next=s ,是将A中的链域（即指向B的地址）覆盖，但是p还保存着啊， s->next=p，就将X插入到A和B的节点中间了。

第6题：

下列选项中，会导致用户进程从用户态切换到内核的操作是?

I. 整数除以零 

II. sin( )函数调用   

III. read系统调用

A  仅 I、II

B  仅 I、III

C  仅 II 、III

D  I、II和III

 B

用户态切换到内核态的      3    种方式

a.  系统调用

b.  异常

c.  外围设备的中断 

I.         异常   

III.     系统调用    

第7题：

用ls –al 命令列出下面的文件列表，哪个文件是符号连接文件？           

A  -rw-rw-rw- 2 hel-s users 56 Sep 09 11:05 hello

B  -rwxrwxrwx 2 hel-s users 56 Sep 09 11:05 goodbye

C  drwxr--r-- 1 hel users 1024 Sep 10 08:10 zhang

D  lrwxr--r-- 1 hel users 2024 Sep 12 08:12 cheng > peng.yan1

 D

d表示目录directory；

l表示连接link。

第8题：

 一次期末考试，“学弱”面对两道单选题(四个选项)，完全不知所云，只得靠随机猜测。考后对答案，学霸告诉他那两道选择题至少对了一题，那么请问聪明的你，在知道至少对一题的前提下，他两道单选题全对的概率是?    

A  1/4

B  1/3

C  1/7

D  1/8

 C

至少答对一道的概率是a: 1-（3/4)^2 = 7/16

两道全对的概率是b: （1/4）^2 = 1/16

至少对一题的前提下，他两道单选题全对的概率是:

p = b / a = 1 / 7

第9题：

 Linux中，一个端口能够接受tcp链接数量的理论上限是？     

A  1024

B  65535

C  65535 * 65535

D  无上限

 D

第10题：

定义网络传输数据包为 

class packet{

     int size;

     void data[0];

}

其中data的作用是？

A  维护数据包空间的连续性

B  数据分割位

C  指向独立的数据空间

D  无任何作用

 C

1.这个叫柔性数组，它的作用跟指针差不多，但是指针占空间，而它不占空间，这就意味着可以节省空间。

2.该数组的内存地址就和它后面的元素地址相同，意味着无需初始化，数组名就是后面元素的地址，直接就能当指针使用。例如，制作动态buffer，可以这样分配空间malloc(sizeof(structXXX) +      buff_len); 直接就把buffer的结构体和缓冲区一块分配了。这样使用释放一次即可，如果使用指针，则需要释放两次。  

3.也可以写成data[1]或data[]，是考虑到可移植性的原因，因为有些编译器不支持0数组。  

第11题：

二、填空题

x为整型，请用位运算实现x%8 ________ 。

 x&7

当我们求余的时候，相当于除以2的N次冥，也就是相当于把数本身右移N位，但是右移掉的那些位需要通过位运算进行保留；用以上例子来说，X%8即X%2^3,那么就需要右移三次，那么移去的三位需要保留下来，而8=1000，刚好，可以使用0111来保留下来后三位，于是，对于除数都是2的整数次幂的情况，可以使用x    & (2^n-1)的方法进行与运算，保留下来的最末尾的n位就是余数。

该题中，结果为x&7.

第12题：

 符号-、*、$分别代表减法、乘法和指数运算，且
a)三个运算符优先级顺序为：-最高，*其次，$最低；
b)运算符运算时为左结合
则5-3*2$2*4-3$2的结果为 ________ 。

 256

5-3*2$2*4-3$2

= (5-3)*2$2*4-3$2  

= 2*2$2*4-3$2

=4$2*4-3$2

=16*4-3$2

=16*(4-3)$2

=16$2

=256

第13题：

三、问答题

删除字符串中指定的字符，如字符串”abcdeas"，需要删除的字符为“ade",则得到的结果为”bcs”。

 public class Delete{

private String str="abcdeas";

public static void main(String [] args){

private []ch=str.toCharArray();

System.out.println(ch[1]+","ch[2]+","+ch[3]+","+ch[6]);

}

}

第14题：

有一排台阶，每个台阶上有一个非负整数，代表在该台阶上时能最多向前跳几个台阶。从第0个台阶开始跳，实现一个函数，判断是否能到达最后一个台阶。
例如： 4 2 2 1 0 2 返回 false
            2 1 3 1 1 0 返回 true

bool jump(int array[], int size)

{                 

}

 思路：

采用递归和一个辅助数值来实现。辅助数值boolArr[n]表示每一个台阶是否能够到达终点。

首先，初始化一个bool类型数组：boolean []boolArr = new boolean[size];

然后调用递归方法：boolean isJump(int[] arr, boolean[] boolArr, int i, int  size) ;

通过递归调用初始化台阶数为0的boolArr 数组的值。然后从后到前一次判断每一个节点是否能够到达终点。

java源代码：

static boolean jump(int array[], int size) {

    boolean []boolArr = new boolean[size];

    return isJump(array, boolArr, 0, size);

}

private static boolean isJump(int[] arr, boolean[] boolArr, int i, int size) {

    // TODO Auto-generated method stub

    if (i == size - 1)

        return true;

    if (arr[i] == 0) {

        boolArr[i] = false;

    }

    boolean isNextStepOk = isJump(arr, boolArr, i + 1, size);

    if (isNextStepOk) {

        boolArr[i] = true;

    }

    if ((isNextStepOk && arr[i] > 0 ) || size - i - 1 <= arr[i])

        return true;

    for (int k = i + 2; k < i + arr[i]; k++) {

        if (boolArr[k] == true)return true;

    }

    return false;

}