Linux系统C/C++服务器后台开发面试题总结（二）

本篇文章主要和大家分享一下Linux系统C/C++服务器后台开发面试题，这些面试题都是作者为大家精心挑选的，希望对大家有所帮助。

69. 拷贝构造函数作用及用途？什么时候需要自定义拷贝构造函数？

一般如果构造函数中存在动态内存分配，则必须定义拷贝构造函数。否则，可能会导致两个对象成员指向同一地址，出现“指针悬挂问题”。

70. 100万个32位整数，如何最快找到中位数。能保证每个数是唯一的，如何实现O(N)算法？

1).内存足够时：快排

2).内存不足时：分桶法：化大为小，把所有数划分到各个小区间，把每个数映射到对应的区间里，对每个区间中数的个数进行计数，数一遍各个区间，看看中位数落在哪个区间，若够小，使用基于内存的算法，否则 继续划分

71. OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。

#define OFFSETOF（s, m） size_t（&((s*)0)->m）

72. C++虚函数是如何实现的？

使用虚函数表。 C++对象使用虚表， 如果是基类的实例，对应位置存放的是基类的函数指针；如果是继承类，对应位置存放的是继承类的函数指针（如果在继承类有实现）。所以 ，当使用基类指针调用对象方法时，也会根据具体的实例，调用到继承类的方法。

73. C++的虚函数有什么作用？

虚函数作用是实现多态，虚函数其实是实现封装，使得使用者不需要关心实现的细节。在很多设计模式中都是这样用法，例如Factory、Bridge、Strategy模式。

74.MFC中CString是类型安全类吗，为什么？

不是，其他数据类型转换到CString可以使用CString的成员函数Format来转换

74.动态链接库的两种使用方法及特点？

1)．载入时动态链接，模块非常明确调用某个导出函数，使得他们就像本地函数一样。这需要链接时链接那些函数所在DLL的导入库，导入库向系统提供了载入DLL时所需的信息及DLL函数定位。

2)运行时动态链接。

 

 二、服务器编程

1.多线程和多进程的区别（重点 必须从cpu调度，上下文切换，数据共享，多核cup利用率，资源占用，等等各方面回答，然后有一个问题必须会被问到：哪些东西是一个线程私有的？答案中必须包含寄存器，否则悲催）！

1）进程数据是分开的:共享复杂，需要用IPC，同步简单；多线程共享进程数据：共享简单，同步复杂

2）进程创建销毁、切换复杂，速度慢 ；线程创建销毁、切换简单，速度快

3）进程占用内存多， CPU利用率低；线程占用内存少， CPU利用率高

4）进程编程简单，调试简单；线程 编程复杂，调试复杂

5）进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉

6）进程适应于多核、多机分布；线程适用于多核

线程所私有的：

线程id、寄存器的值、栈、线程的优先级和调度策略、线程的私有数据、信号屏蔽字、errno变量、

2. 多线程锁的种类有哪些？

a.互斥锁（mutex）b.递归锁 c.自旋锁 d.读写锁

3. 自旋锁和互斥锁的区别？

当锁被其他线程占用时，其他线程并不是睡眠状态，而是不停的消耗CPU，获取锁；互斥锁则不然，保持睡眠，直到互斥锁被释放激活。

自旋锁，递归调用容易造成死锁，对长时间才能获得到锁的情况，使用自旋锁容易造成CPU效率低，只有内核可抢占式或SMP情况下才真正需要自旋锁。

4.进程间通信和线程间通信

1）.管道 2）消息队列 3)共享内存 4)信号量 5)套接字 6)条件变量

5.多线程程序架构，线程数量应该如何设置？

应尽量和CPU核数相等或者为CPU核数+1的个数

6.什么是原子操作，gcc提供的原子操作原语，使用这些原语如何实现读写锁？

原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch。

7.网络编程设计模式，reactor/proactor/半同步半异步模式？

reactor模式：同步阻塞I/O模式，注册对应读写事件处理器，等待事件发生进而调用事件处理器处理事件。 proactor模式：异步I/O模式。Reactor和Proactor模式的主要区别就是真正的读取和写入操作是有谁来完成的，Reactor中需要应用程序自己读取或者写入数据，Proactor模式中，应用程序不需要进行实际读写过程。

Reactor是：

主线程往epoll内核上注册socket读事件，主线程调用epoll_wait等待socket上有数据可读，当socket上有数据可读的时候，主线程把socket可读事件放入请求队列。睡眠在请求队列上的某个工作线程被唤醒，处理客户请求，然后往epoll内核上注册socket写请求事件。主线程调用epoll_wait等待写请求事件，当有事件可写的时候，主线程把socket可写事件放入请求队列。睡眠在请求队列上的工作线程被唤醒，处理客户请求。

Proactor:

主线程调用aio_read函数向内核注册socket上的读完成事件，并告诉内核用户读缓冲区的位置，以及读完成后如何通知应用程序，主线程继续处理其他逻辑，当socket上的数据被读入用户缓冲区后，通过信号告知应用程序数据已经可以使用。应用程序预先定义好的信号处理函数选择一个工作线程来处理客户请求。工作线程处理完客户请求之后调用aio_write函数向内核注册socket写完成事件，并告诉内核写缓冲区的位置，以及写完成时如何通知应用程序。主线程处理其他逻辑。当用户缓存区的数据被写入socket之后内核向应用程序发送一个信号，以通知应用程序数据已经发送完毕。应用程序预先定义的数据处理函数就会完成工作。

半同步半异步模式：

上层的任务（如：数据库查询，文件传输）使用同步I/O模型，简化了编写并行程序的难度。
而底层的任务（如网络控制器的中断处理）使用异步I/O模型，提供了执行效率。

8.有一个计数器，多个线程都需要更新，会遇到什么问题，原因是什么，应该如何做？如何优化？

有可能一个线程更新的数据已经被另外一个线程更新了，更新的数据就会出现异常，可以加锁，保证数据更新只会被一个线程完成。

9.如果select返回可读，结果只读到0字节，什么情况？

某个套接字集合中没有准备好，可能会select内存用FD_CLR清为0.

10. connect可能会长时间阻塞，怎么解决?

1.使用定时器；（最常用也最有效的一种方法）

2.采用非阻塞模式：设置非阻塞，返回之后用select检测状态。

11.keepalive 是什么东西？如何使用？

keepalive，是在TCP中一个可以检测死连接的机制。

1）.如果主机可达，对方就会响应ACK应答，就认为是存活的。

2）.如果可达，但应用程序退出，对方就发RST应答，发送TCP撤消连接。

3）.如果可达，但应用程序崩溃，对方就发FIN消息。

4）.如果对方主机不响应ack, rst，继续发送直到超时，就撤消连接。默认二个小时。

12.socket什么情况下可读？

1.socket接收缓冲区中已经接收的数据的字节数大于等于socket接收缓冲区低潮限度的当前值;对这样的socket的读操作不会阻塞,并返回一个大于0的值(准备好读入的数据的字节数).

2.连接的读一半关闭(即:接收到对方发过来的FIN的TCP连接),并且返回0;
3.socket收到了对方的connect请求已经完成的连接数为非0.这样的soocket处于可读状态；
4.异常的情况下socket的读操作将不会阻塞,并且返回一个错误(-1)。

13.udp调用connect有什么作用？

1).因为UDP可以是一对一，多对一，一对多，或者多对多的通信，所以每次调用sendto()/recvfrom()时都必须指定目标IP和端口号。通过调用connect()建立一个端到端的连接，就可以和TCP一样使用send()/recv()传递数据，而不需要每次都指定目标IP和端口号。但是它和TCP不同的是它没有三次握手的过程。

2).可以通过在已建立连接的UDP套接字上，调用connect()实现指定新的IP地址和端口号以及断开连接。

14. socket编程，如果client断电了，服务器如何快速知道？

使用定时器（适合有数据流动的情况）；

使用socket选项SO_KEEPALIVE（适合没有数据流动的情况）;

1）、自己编写心跳包程序,简单的说就是自己的程序加入一条线程,定时向对端发送数据包,查看是否有ACK,根据ACK的返回情况来管理连接。此方法比较通用,一般使用业务层心跳处理,灵活可控,但改变了现有的协议;
2）、使用TCP的keepalive机制,UNIX网络编程不推荐使用SO_KEEPALIVE来做心）跳检测。
keepalive原理:TCP内嵌有心跳包,以服务端为例,当server检测到超过一定时间(/proc/sys/net/ipv4/tcp_keepalive_time 7200 即2小时)没有数据传输,那么会向client端发送一个keepalive packet。

三、liunx操作系统

1.熟练netstat tcpdump ipcs ipcrm

netstat:检查网络状态，tcpdump:截获数据包，ipcs:检查共享内存，ipcrm:解除共享内存

2.共享内存段被映射进进程空间之后，存在于进程空间的什么位置？共享内存段最大限制是多少？

将一块内存映射到两个或者多个进程地址空间。通过指针访问该共享内存区。一般通过mmap将文件映射到进程地址共享区。

存在于进程数据段，最大限制是0x2000000Byte

3.进程内存空间分布情况

 

4.ELF是什么？其大小与程序中全局变量的是否初始化有什么关系（注意未初始化的数据放在bss段）

可执行连接格式。可以减少重新编程重新编译的代码。

5.动态链接和静态链接的区别？

动态链接是只建立一个引用的接口，而真正的代码和数据存放在另外的可执行模块中，在可执行文件运行时再装入；而静态链接是把所有的代码和数据都复制到本模块中，运行时就不再需要库了

6.32位系统一个进程最多有多少堆内存

32位意味着4G的寻址空间，Linux把它分为两部分：最高的1G(虚拟地址从0xC0000000到0xffffffff)用做内核本身，成为“系统空间”，而较低的3G字节（从0x00000000到0xbffffff）用作各进程的“用户空间”。每个进程可以使用的用户空间是3G。虽然各个进程拥有其自己的3G用户空间，系统空间却由所有的进程共享。从具体进程的角度看，则每个进程都拥有4G的虚拟空间，较低的3G为自己的用户空间，最高的1G为所有进程以及内核共享的系统空间。实际上有人做过测试也就2G左右。

7.写一个c程序辨别系统是64位 or 32位

void* number =  0;      printf(“%d\n”,sizeof(&number));

输出8就是64位 输出4就是32位的 根据逻辑地址判断的

8.写一个c程序辨别系统是大端or小端字节序

union{ short value; char a[sizeof(short)];}test;

test.value= 0x0102;

if((test.a[0] == 1) && (test.a[1] == 2)) cout

9.信号：列出常见的信号，信号怎么处理？

1).进程终止的信号 2).跟踪进程的信号 3).与进程例外事件相关的信号等

对于信号的处理或者执行相关的操作进行处理或者直接忽略

10.i++ 是否原子操作?并解释为什么?

答案肯定不是原子操作，i++主要看三个步骤

首先把数据从内存放到寄存器上，在寄存器上进行自增处理，放回到寄存器上，每个步骤都可能会被中断分离开！

11.说出你所知道的各类linux系统的各类同步机制（重点），什么是死锁？如何避免死锁（每个技术面试官必问）

1).原子操作 2).信号量（其实就是互斥锁也就是锁的机制）3).读写信号量（就是读写锁） 4）.自旋锁  5.内核锁 6）.顺序锁

死锁就是几个进程申请资源，出现了循环等待的情况！

避免死锁的方法：

1）.资源是互斥的 2）.不可抢占 3）占有且申请 4）.循环等待

12、exit() _exit()的区别？

 

13、如何实现守护进程？

1）创建子进程，父进程退出

2）在子进程中创建新会话

3）改变当前目录为根目

4）重设文件权限掩码

5) 关闭文件描述符

6) 守护进程退出处理

当用户需要外部停止守护进程运行时，往往会使用 kill命令停止该守护进程。所以，守护进程中需要编码来实现kill发出的signal信号处理，达到进程的正常退出。

 

14、linux的任务调度机制是什么？

Linux 分实时进程和普通进程，实时进程应该先于普通进程而运行。实时进程：

1） FIFO(先来先服务调度)

2） RR（时间片轮转调度）。

每个进程有两个优先级（动态优先级和实时优先级），实时优先级就是用来衡量实时进程是否值得运行的。 非实时进程有两种优先级，一种是静态优先级，另一种是动态优先级。实时进程又增加了第三种优先级，实时优先级。优先级越高，得到CPU时间的机会也就越大。

15、标准库函数和系统调用的区别？
系统调用：是操作系统为用户态运行的进程和硬件设备(如CPU、磁盘、打印机等)进行交互提供的一组接口，即就是设置在应用程序和硬件设备之间的一个接口层。inux内核是单内核，结构紧凑，执行速度快，各个模块之间是直接调用的关系。linux系统上到下依次是用户进程->linux内核->硬件。其中系统调用接口是位于Linux内核中的，整个linux系统从上到下可以是：用户进程->系统调用接口->linux内核子系统->硬件，也就是说Linux内核包括了系统调用接口和内核子系统两部分；或者从下到上可以是：物理硬件->OS内核->OS服务->应用程序，操作系统起到“承上启下”作用，向下管理物理硬件，向上为操作系服务和应用程序提供接口，这里的接口就是系统调用了。
库函数：把函数放到库里。是把一些常用到的函数编完放到一个lib文件里，供别人用。别人用的时候把它所在的文件名用#include加到里面就可以了。一类是c语言标准规定的库函数，一类是编译器特定的库函数。
系统调用是为了方便使用操作系统的接口，而库函数则是为了人们编程的方便。

16、系统如何将一个信号通知到进程？

内核给进程发送信号，是在进程所在的进程表项的信号域设置对应的信号的位。进程处理信号的时机就是从内核态即将返回用户态度的时候。执行用户自定义的信号处理函数的方法很巧妙。把该函数的地址放在用户栈栈顶，进程从内核返回到用户态的时候，先弹出信号处理函数地址，于是就去执行信号处理函数了，然后再弹出，才是返回进入内核时的状态。

17. fork()一子进程程后父进程的全局变量能不能使用？

fork后子进程将会拥有父进程的几乎一切资源，父子进程的都各自有自己的全局变量。不能通用，不同于线程。对于线程，各个线程共享全局变量。

18. 请画出socket通信连接过程

 

19. 请用socket消息队列实现“同步非阻塞”和“异步阻塞”两种模式，并指出两者的差别和优劣

http://blog.csdn.net/yongchurui/article/details/12780653

四、网络编程

1. TCP头大小，包含字段？三次握手，四次断开描述过程，都有些什么状态。状态变迁图。TCP/IP收发缓冲区（2次）

头部大小是20字节，包含数据如下：

 

三次握手：

 

四次释放：

 

状态变迁图：

 

收发缓冲区：

 

2. 使用udp和tcp进程网络传输，为什么tcp能保证包是发送顺序，而 udp无法保证？

因为TCP发送的数据包是按序号发送，有确认机制和丢失重传机制，而udp是不可靠的发送机制，发送的对应端口的数据包不是按顺序发送的。

3. epoll哪些触发模式，有啥区别？（必须非常详尽的解释水平触发和边缘触发的区别，以及边缘触发在编程中要做哪些更多的确认）

epoll有EPOLLLT和EPOLLET两种触发模式，LT是默认的模式，ET是“高速”模式。LT模式下，只要这个fd还有数据可读，每次 epoll_wait都会返回它的事件，提醒用户程序去操作，而在ET（边缘触发）模式中，它只会提示一次，直到下次再有数据流入之前都不会再提示了，无论fd中是否还有数据可读。所以在ET模式下，read一个fd的时候一定要把它的buffer读光，也就是说一直读到read的返回值小于请求值。

也就是说在LT模式的情况下一定要确认收发的数据包的buffer是不是足够大如果收发数据包大小大于buffer的大小的时候就可能会出现数据丢失的情况。

4. tcp与udp的区别（必问）为什么TCP要叫做数据流？

1）．基于连接与无连接

2）．对系统资源的要求（TCP较多，UDP少）

3）．UDP程序结构较简单

4）．流模式与数据报模式

5）．TCP保证数据正确性，UDP可能丢包，TCP保证数据顺序，UDP不保证

6）.TCP有拥塞控制和流量控制，UDP没有

TCP提供的是面向连接、可靠的字节流服务。当客户和服务器彼此交换数据前，必须先在双方之间建立一个TCP连接，之后才能传输数据。TCP提供超时重发，丢弃重复数据，检验数据，流量控制等功能，保证数据能从一端传到另一端。

是一个简单的面向数据报的运输层协议。UDP不提供可靠性，它只是把应用程序传给IP层的数据报发送出去，但是并不能保证它们能到达目的地。由于UDP在传输数据报前不用在客户和服务器之间建立一个连接，且没有超时重发等机制，故而传输速度很快

5．流量控制和拥塞控制的实现机制

网络拥塞现象是指到达通信子网中某一部分的分组数量过多,使得该部分网络来不及处理,以致引起这部分乃至整个网络性能下降的现象,严重时甚至会导致网络通信业务陷入停顿,即出现死锁现象。拥塞控制是处理网络拥塞现象的一种机制。数据的传送与接收过程当中很可能出现收方来不及接收的情况,这时就需要对发方进行控制,以免数据丢失。

6. 滑动窗口的实现机制

滑动窗口机制，窗口的大小并不是固定的而是根据我们之间的链路的带宽的大小，这个时候链路是否拥护塞。接受方是否能处理这么多数据了。  滑动窗口协议，是TCP使用的一种流量控制方法。该协议允许发送方在停止并等待确认前可以连续发送多个分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输。

7.epoll和select的区别？

1）select在一个进程中打开的最大fd是有限制的，由FD_SETSIZE设置，默认值是2048。不过 epoll则没有这个限制，内存越大，fd上限越大，1G内存都能达到大约10w左右。

2）select的轮询机制是系统会去查找每个fd是否数据已准备好，当fd很多的时候，效率当然就直线下降了，epoll采用基于事件的通知方式，一旦某个fd数据就绪时，内核会采用类似callback的回调机制，迅速激活这个文件描述符，高效。

3）select还是epoll都需要内核把FD消息通知给用户空间，epoll是通过内核于用户空间mmap同一块内存实现的，而select则做了不必要的拷贝

8. 网络中，如果客户端突然掉线或者重启，服务器端怎么样才能立刻知道？

若客户端掉线或者重新启动，服务器端会收到复位信号，每一种tcp/ip得实现不一样，控制机制也不一样。

9. TTL是什么？有什么用处，通常那些工具会用到它？ping? traceroute? ifconfig? netstat?

TTL是Time To Live，每经过一个路由就会被减去一，如果它变成0，包会被丢掉。它的主要目的是防止包在有回路的网络上死转，浪费网络资源。ping和traceroute用到它。

10.linux的五种IO模式/异步模式.

1）同步阻塞I/O

2）同步非阻塞I/O

3）同步I/O复用模型

4） 同步信号驱动I/O

5） 异步I/O模型

 

11. 请说出http协议的优缺点.

1.支持客户/服务器模式。2.简单快速：客户向服务器请求服务时，只需传送请求方法和路径，通信速度很快。3.灵活：HTTP允许传输任意类型的数据对象。4.无连接：无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求，并收到客户的应答后，即断开连接。采用这种方式可以节省传输时间。5.无状态：HTTP协议是无状态协议。无状态是指协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息，则它必须重传，导致每次连接传送的数据量增大。缺点就是不够安全，可以使用https完成使用

12.NAT类型，UDP穿透原理。

1）Full cone NAT （全克隆nat）:一对一NAT一旦一个内部地址（iAddr:port1）映射到外部地址（eAddr:port2）。

2）Address-Restricted cone NAT（地址受限克隆nat）:任意外部主机（hostAddr:any）都能通过给eAddr:port2发包到达iAddr:port1的前提是：iAddr:port1之前发送过包到hostAddr:any. “any”也就是说端口不受限制

3). Port-Restricted cone NAT:内部地址（iAddr:port1）映射到外部地址（eAddr:port2），所有发自iAddr:port1的包都经eAddr:port2向外发送。一个外部主机（hostAddr:port3）能够发包到达iAddr:port1的前提是：iAddr:port1之前发送过包到hostAddr:port3.

4). Symmetric NAT（对称NAT）:同内部IP与port的请求到一个特定目的地的IP地址和端口，映射到一个独特的外部来源的IP地址和端口。同一个内部主机发出一个信息包到不同的目的端，不同的映射使用外部主机收到了一封包从一个内部主机可以送一封包回来

 

13.大规模连接上来，并发模型怎么设计

Epoll+线程池（epoll可以采用libevent处理）

14.tcp三次握手的，accept发生在三次握手哪个阶段？

三次握手：C—–>SYN K

S——>ACK K+1 SYN J

C——->ACK J+1

DONE!

client 的 connect  引起3次握手

server 在socket， bind， listen后，阻塞在accept，三次握手完成后，accept返回一个fd，

16.流量控制与拥塞控制的区别，节点计算机怎样感知网络拥塞了？

拥塞控制是把整体看成一个处理对象的，流量控制是对单个的节点。

感知的手段应该不少，比如在TCP协议里，TCP报文的重传本身就可以作为拥塞的依据。依据这样的原理， 应该可以设计出很多手段。

 

五、算法和数据结构

1.给定一个单向链表（长度未知），请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。“倒数第m个元素”是这样规定的：当m=0时，链表的最后一个元素将被返回。

解决问题方法思路如下：

方法一、如果我们知道链表的长度n，查找倒数第m个元素，也就是查找正序的第（n –  m）个元素（这里的序号只是为了分析，可能跟题目不一定正确的符合）。那么这样来说就简单很多。首先遍历链表得到链表长度，然后重新遍历一次，查找正数第（n-m）个元素。时间复杂度大约是O(2n)。

方法二、我们是不是可以提供一个辅助存储空间，是的我们在遍历到链表结束的时候可以回溯到倒数第m个元素。比如用一个支持随机访问的容器记录链表每一个节点的地址。那么这样的就可以只遍历一次链表就能得到结果。时间复杂度大约是O(n)，但是我们是用空间换取时间的，辅助存储空间的大小由m决定，如果m过大也是不可取的。

方法三、头结点指针为当前指针，尾节点指针为拖后指针。开始的时候当前指针和拖后指针初始化为链表的头结点，首先我们让当前指针遍历到第m个元素，拖后指针不变；然后同步更新当前指针和拖后指针；直到当前指针为链表结尾。这样我们就能保证当前指针和拖尾指针之间的距离是m。

代码如下：

Node* FindMToLastNode(Node* pHead, int m)  {

// 查找到第m个元素

Node* pCurrent = pHead;

for (int i = 0; i 

{

if (pCurrent)

{

pCurrent = pCurrent->next;

}

else

{

return NULL;

}

}

 

Node* pFind = pHead;

while (pCurrent)   {

pFind        = pFind->next;

pCurrent    = pCurrent->next;

}

return pFind;

}

2. 给定一个单向链表（长度未知），请遍历一次就找到中间的指针，假设该链表存储在只读存储器，不能被修改

设置两个指针，一个每次移动两个位置，一个每次移动一个位置，当第一个指针到达尾节点时，第二个指针就达到了中间节点的位置

处理链表问题时，”快行指针“是一种很常见的技巧，快行指针指的是同时用两个指针来迭代访问链表，只不过其中一个比另一个超前一些。快指针往往先行几步，或与慢指针相差固定的步数。

node *create()  {

node *p1, *p2, *head;

int cycle = 1, x;

head = (node*)malloc(sizeof(node));

p1 = head;

while (cycle)

{

cout 

cin >> x;

if (x != 0)

{

p2 = (node*)malloc(sizeof(node));

p2->data = x;

p1->next = p2;

p1 = p2;

}

 

else

{

cycle = 0;

}

}

head = head->next;

p1->next = NULL;

return head;

}

void findmid(node* head)  {

node *p1, *p2, *mid;

p1 = head;

p2 = head;

 

while (p1->next->next != NULL)

{

p1 = p1->next->next;

p2 = p2->next;

mid = p2;

}

}

3. 将一个数组生成二叉排序树

排序，选数组中间的一个元素作为根节点，左边的元素构造左子树，右边的节点构造有子树。

4. 查找数组中第k大的数字？

因为快排每次将数组划分为两组加一个枢纽元素，每一趟划分你只需要将k与枢纽元素的下标进行比较，如果比枢纽元素下标大就从右边的子数组中找，如果比枢纽元素下标小从左边的子数组中找，如果一样则就是枢纽元素，找到，如果需要从左边或者右边的子数组中再查找的话，只需要递归一边查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

最差情况如下：假设快排每次都平均划分，但是都不在枢纽元素上找到第k大第一趟快排没找到，时间复杂度为O(n)，第二趟也没找到，时间复杂度为O(n/2)，第k趟找到，时间复杂度为O(n/2k)，所以总的时间复杂度为O(n(1+1/2+….+1/2k))=O(n)，明显比冒泡快，虽然递归深度是一样的，但是每一趟时间复杂度降低。

 5. 红黑树的定义和解释？B树的基本性质？

红黑树：

性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

B树：

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

 

6. 常见的加密算法？

对称式加密就是加密和解密使用同一个密钥。
非对称式加密就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为“公钥”和“私钥”，它们两个必需配对使用。
DES：对称算法，数据加密标准，速度较快，适用于加密大量数据的场合；
MD5的典型应用是对一段Message产生fingerprint(指纹)，以防止被“篡改”。
RSA是第一个既能用于数据加密也能用于数字签名的算法。

7. https?

HTTP下加入SSL层，HTTPS的安全基础是SSL。

8.有一个IP库，给你一个IP,如何能够快速的从中查找到对应的IP段？不用数据库如何实现？要求省空间
9.简述一致性hash算法。

1）首先求memcached服务器（节点）的哈希值，并将其配置到0～232的圆（continuum）。

2）然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。

3）然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。
11.描述一种hash table的实现方法

1） 除法散列法: p ，令 h(k ) = k mod p ，这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。最直观的一种，上图使用的就是这种散列法，公式： index = value % 16，求模数其实是通过一个除法运算得到的。

2） 平方散列法 :求index频繁的操作，而乘法的运算要比除法来得省时。公式： index = (value * value) >> 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除）

3） 数字选择法:如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。

4） 斐波那契（Fibonacci）散列法:平方散列法的缺点是显而易见的，通过找到一个理想的乘数index = (value * 2654435769) >> 28

冲突处理：令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。

12、各类树结构的实现和应用

13、hash，任何一个技术面试官必问（例如为什么一般hashtable的桶数会取一个素数？如何有效避免hash结果值的碰撞）

不选素数的话可能会造成hash出值的范围和原定义的不一致

14.什么是平衡二叉树?

左右子树都是平衡二叉树，而且左右子树的深度差值的约对值不大于1。

15．数组和链表的优缺点

数组，在内存上给出了连续的空间。链表，内存地址上可以是不连续的，每个链表的节点包括原来的内存和下一个节点的信息(单向的一个，双向链表的话，会有两个)。

数组优于链表的:

A. 内存空间占用的少。

B. 数组内的数据可随机访问，但链表不具备随机访问性。

C. 查找速度快

链表优于数组的:

A. 插入与删除的操作方便。

B. 内存地址的利用率方面链表好。

C. 方便内存地址扩展。

17.最小堆插入，删除编程实现

18. 4G的long型整数中找到一个最大的，如何做？

每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。分批读入选取最大数，再对缓存的最大数进行快排。

19. 有千万个string在内存怎么高速查找，插入和删除？

对千万个string做hash，可以实现高速查找，找到了，插入和删除就很方便了。关键是如何做hash，对string做hash，要减少碰撞频率。

20.100亿个数，求最大的1万个数，并说出算法的时间复杂度

在内存中维护一个大小为10000的最小堆，每次从文件读一个数，与最小堆的堆顶元素比较，若比堆顶元素大，则替换掉堆顶元素，然后调整堆。最后剩下的堆内元素即为最大的1万个数，算法复杂度为O(NlogN)

21.设计一个洗牌的算法，并说出算法的时间复杂度。

（1）全局洗牌法

a）首先生成一个数组，大小为54，初始化为1~54

b）按照索引1到54，逐步对每一张索引牌进行洗牌，首先生成一个余数 value = rand %54，那么我们的索引牌就和这个余数牌进行交换处理

c）等多索引到54结束后，一副牌就洗好了

（2）局部洗牌法：索引牌从1开始，到54结束。这一次索引牌只和剩下还没有洗的牌进行交换， value = index + rand（） %（54 – index）

算法复杂度是O(n)

22．请分别用递归和非递归方法，先序遍历二叉树

http://blog.csdn.net/pi9nc/article/details/13008511

24.其他各种排序方法

http://blog.csdn.net/hguisu/article/details/7776068

25.哈希表冲突解决方法？

常见的hash算法如下：

1. 1.      数字分析法 2.平方取中法 3.分段叠加法4.除留余数法 5.伪随机法

解决冲突的方法：

1. 1.      开放地址法

也叫散列法，主要思想是当出现冲突的时候，以关键字的结果值作为key值输入，再进行处理，依次直到冲突解决

线性地址再散列法

当冲突发生时，找到一个空的单元或者全表

二次探测再散列

冲突发生时，在表的左右两侧做跳跃式的探测

伪随机探测再散列

1. 2.      再哈希法

同时构造不同的哈希函数

1. 3.      链地址法

将同样的哈希地址构造成一个同义词的链表

1. 4.      建立公共溢出区

建立一个基本表和溢出区，凡是和基本元素发生冲突都填入溢出区

六、系统架构

1.设计一个服务，提供递增的SessionID服务，要求保证服务的高可靠性，有哪些方案？集中式/非集中式/分布式

2.多台服务器要执行计划任务，但只有拿到锁的任务才能执行，有一个中心服务器来负责分配锁，但要保证服务的高可靠性。

3.如何有效的判断服务器是否存活？服务器是否踢出集群的决策如何产生？

4.两个服务器如何在同一时刻获取同一数据的时候保证只有一个服务器能访问到数据？

可以采用队列进行处理，写一个队列接口保证同一时间只有一个进程能够访问到数据，或者对于存取数据库的来说，数据库也是可以加锁处理的

5.  编写高效服务器程序，需要考虑的因素

性能对服务器程序来说是至关重要的了，毕竟每个客户都期望自己的请求能够快速的得到响应并处理。那么影响服务器性能的首要因素应该是：

（1）系统的硬件资源，比如说CPU个数，速度，内存大小等。不过由于硬件技术的飞速发展，现代服务器都不缺乏硬件资源。因此，需要考虑的主要问题是如何从“软环境”来提升服务器的性能。

服务器的”软环境“

（2）一方面是指系统的软件资源，比如操作系统允许用户打开的最大文件描述符数量

（3）另一方面指的就是服务器程序本身，即如何从编程的角度来确保服务器的性能。

主要就要考虑大量并发的处理这涉及到使用进程池或线程池实现高效的并发模式（半同步/半异步和领导者/追随者模式），以及高效的逻辑处理方式–有限状态机内存的规划使用比如使用内存池，以空间换时间，被事先创建好，避免动态分配，减少了服务器对内核的访问频率，数据的复制，服务器程序还应该避免不必要的数据复制，尤其是当数据复制发生在用户空间和内核空间之间时。如果内核可以直接处理从socket或者文件读入的数据，则应用程序就没必要将这些数据从内核缓冲区拷贝到应用程序缓冲区中。这里所谓的“直接处理”，是指应用程序不关心这些数据的具体内容是什么，不需要对它们作任何分析。比如说ftp服务器，当客户请求一个文件时，服务器只需要检测目标文件是否存在，以及是否有权限读取就可以了，不需要知道这个文件的具体内容，这样的话ftp服务器就不需要把目标文件读入应用程序缓冲区然后调用send函数来发送，而是直接使用“零拷贝”函数sendfile直接将其发送给客户端。另外，用户代码空间的数据赋值也应该尽可能的避免复制。当两个工作进程之间需要传递大量的数据时，我们就应该考虑使用共享内存来在他们直接直接共享这些数据，而不是使用管道或者消息队列来传递。上下文切换和锁：并发程序必须考虑上下文的切换问题，即进程切换或线程切换所导致的系统开销。即时I/O密集型服务器也不应该使用过多的工作线程（或工作进程），否则进程间切换将占用大量的CPU时间，服务器真正处理业务逻辑的CPU时间比重就下降了。因此为每个客户连接都创建一个工作线程是不可取的。应该使用某种高效的并发模式。（半同步半异步或者说领导者追随者模式）另一个问题就是共享资源的加锁保护。锁通常被认为是导致服务器效率低下的一个因素，因为由他引入的代码不仅不处理业务逻辑，而且需要访问内核资源，因此如果服务器有更好的解决方案，应该尽量避免使用锁。或者说服务器一定非要使用锁的话，尽量使用细粒度的锁，比如读写锁，当工作线程都只读一块内存区域时，读写锁不会增加系统开销，而只有当需要写时才真正需要锁住这块内存区域。对于高峰和低峰的伸缩处理，适度的缓存。

6. QQ飞车新用户注册时，如何判断新注册名字是否已存在？（数量级：几亿) 

可以试下先将用户名通过编码方式转换，如转换64位整型。然后设置N个区间，每个区间为2^64/N的大小。对于新的用户名，先通过2分寻找该用户名属于哪个区间，然后在在这个区间，做一个hash。对于不同的时间复杂度和内存要求可以设置不同N的大小~

 

加一些基础的技术面试之外的职业素养的面试问题

1.你在工作中犯了个错误，有同事打你小报告，你如何处理？

a.同事之间应该培养和形成良好的同事关系，就是要互相支持而不是互相拆台，互相学习，互相帮助，共同进步。

b.如果小报告里边的事情都是事实也就是说确实是本人做的不好不对的方面，那么自己应该有则改之，提高自己。如果小报告里边的事

情全部不是事实，就是说确实诬陷，那么应该首先坚持日久见人心的态度，持之以恒的把本职工作做好，然后在必要的时候通过适当的

方式和领导沟通，相信领导会知道的。

2.你和同事合作完成一个任务，结果任务错过了截止日期，你如何处理？

3.职业规划？

4.离职原因？

5. 项目中遇到的难题，你是如何解决的?

A．时间 b要求 c.方法

至此关于Linux系统中C/C++服务器后台开发面试题全部分享结束，大家有任何问题都可以在评论区留言。

以上就是良许教程网为各位朋友分享的Linux系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”，或扫描下方二维码进行关注，更多干货等着你！