面试经验总结_pcl 点云 面试

http://www.pianshen.com/article/5311315411/ 【C++面试知识】虎牙现场面
https://www.cnblogs.com/TenosDoIt/p/3456704.html C++智能指针
https://www.cnblogs.com/xiehongfeng100/p/4645555.html 智能指针
https://blog.csdn.net/ninili123456/article/details/53196090 判断大小端
https://blog.csdn.net/bcypxl/article/details/12278125 现场编程
https://www.cnblogs.com/s-lisheng/p/11244873.html 多线程编程及死锁
排序：

O（n2）:
冒泡排序：每个数和相邻的数比较，把小数调整到前面。
选择排序：每次选择最小的数放到最前面。
插入排序：每个数和它前面的数比较，插入到合适的位置。数组较小时很适合。

O（nlogn）
归并排序：初始长度为1的有序区间，两两合并为更大的有序区间，最终全部有序。
快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
三数取中、如果数组非常小，适合用直接插入排序。
堆排序：每次在选择到最小记录的同时，并根据比较结果对其他记录作出相应的调整，对简单选择排序的改进。
堆的性质：完全二叉树，每个节点的值都>=其左右孩子节点的值。（大顶堆）根节点是最大值。
堆排序：利用堆进行排序的方法。将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点，将它移走（即将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素的次大值，如此反复执行，便能得到一个有序序列了。
O（nlgn）：初始构建堆O（n）和重建调整堆O（nlgn）。
希尔排序：插入排序步长为1，希尔可以调整步长（从大到小），从步长为1结束。

O（n）:不是基于比较的排序算法，思想来源于桶排序。
计数排序：对身高排序：建立100-300号桶，把身高放入
相应桶中，然后从头到尾倒出即完成排序。
基数排序：建立0-9号桶，先按个位数存到相应桶中，然后从0-9倒出，然后按十位数存到桶中，然后顺序倒出，—直到按最高位存到桶中再倒出即可完成排序。

线程中锁的种类：
互斥锁、条件锁、自旋锁、读写锁、递归锁

大数据：

对10亿个ip地址排序

把任意一个数在对应位置置1，然后遍历取出。有点像桶排序。

找出出现次数最多的数：通过哈希函数进行分流解决内存限制的问题。

网页黑名单系统、垃圾邮件过滤系统：
容忍一定的失误率，对空间要求严格。
布隆过滤器可以精确的代表一个集合（代表之前所有输入对象组成的集合），可精确判断某一元素是否在此集合中，使用很少的空间就可以做到精确率较高。
用哈希表保存下来然后查询在不在黑名单里。
生成：把url通过哈希函数映射的值对m取余然后把bitarray对应的位置置一。
检查是否在布隆过滤器中：把检查值通过哈希函数映射的值对m取余然后检查bitarray对应的位置是否都为1，如果有一个不为1，则不在其中。
存在的一定存在，之前没加入过过滤器的也有可能检查为是输入对象。

禁止new一个类：把构造函数私有化
协程：
比线程更加轻量级的存在。一个线程也可以拥有多个协程。
协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。比如暂停。
性能得到了很大的提升，切换和开销比线程小。

计算机执行程序时是一条指令一条指令地执行的。执行一条指令的过程可分为两个阶段 ：
首先，CPU进入取指令阶段，从存储器中取出指令码送到指令寄存器中寄存，然后对该指令译码后，再转入执行指令阶段，在这期间，CPU执行指令指定的操作。 　取指令阶段是由一系列相同的操作组成的，因此，取指令阶段的时间总是相同的。而执行指令的阶段是由不同的事件顺序组成的，它取决于被执行指令的类型。执行完一条指令后接着执行下一条指令，即： 　取指 执指，取指 执指……如此反复，直至程序结束。

怎么在main函数开始前执行函数，做个全局类就能解决

void before_main()  
{  
    printf("%s\n",__FUNCTION__);  
}  
  
void after_main()  
{  
    printf("%s\n",__FUNCTION__);  
}  
  
class Test {  
public:  
    Test(){ before_main(); }  
    ~Test(){ after_main(); }  
}  
  
Test test;  // 全局类变量,在main前调用构造,在main结束后,调用析构函数  
  
int main(int argc,char **argv)  
{  
    printf("%s\n",__FUNCTION__);  
    return 0;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

浮点数在计算机中存储方式
IEEE 科学计数法

C++继承
使代码可以复用，在保持原有特性的基础上进行扩展（在父类或基类的基础上衍生出子类或派生类），增加功能。

1.基类private成员在派生类中无论以什么方式继承都是不可见的。这里的不可见是指基类的私有成员还是被继承到了派生类对象中，但是语法上限制派生类对象不管在类里面还是类外面都不能去访问它。
2.基类private成员在派生类中是不能被访问，如果基类成员不想在类外直接访问，但需要在派生类中能访问，就定义为protected。可见，保护成员限定符protected是因为继承才出现的。
3.表格里的访问方式都是取最小的“权限”。
4.使用关键字class时默认的继承方式是private，使用struct的默认继承方式是public，不过最好显示地写出继承方式。
5.**在实际运用中一般都使用的是public继承，几乎很少去使用protected/private继承，**也不提倡去使用。因为protected/private继承下来的成员都只能在派生类的类里面使用，实际中的扩展维护性不强。
https://blog.csdn.net/studyhardi/article/details/90744785

红黑树可以解决二叉查找树多次插入新节点导致的不平衡。是一种自平衡的二叉查找数，
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
https://blog.csdn.net/qq_36610462/article/details/83277524
根到叶子的最长路径不会超过最短路径的2倍。
插入新节点打破红黑树规则时需要调整：左旋\右旋、变色。
尝试把红色节点变为黑色，或者把黑色节点变为红色。
就和变魔方一样，每种情况都有相应的调整方法。
左旋：


C++中四种强制类型转换区别详解
https://www.cnblogs.com/cauchy007/p/4968707.html
C语言的类型转换太过随意，可以在任意类型之间转换。
C风格的转换没有统一的关键字和标示符。对于大型系统，做代码排查时容易遗漏和忽略。
C++
1.对类型转换做了细分，提供了四种不同类型转换；2.类型转换有了统一的标示符，利于代码排查和检视，static_cast、dynamic_cast、const_cast和reinterpre_cast.
一、static_cast转换
　　1.基本用法：static_cast expression
　　2.使用场景：
　　a、用于类层次结构中基类和派生类之间指针或引用的转换
　　上行转换（派生类---->基类）是安全的；
　　下行转换（基类---->派生类）由于没有动态类型检查，所以是不安全的。
　　b、用于基本数据类型之间的转换，如把int转换为char，这种带来安全性问题由程序员来保证
　　c、把空指针转换成目标类型的空指针
　　d、把任何类型的表达式转为void类型
　　3.使用特点
　　a、主要执行非多态的转换操作，用于代替C中通常的转换操作
　　b、隐式转换都建议使用static_cast进行标明和替换
二、dynamic_cast转换
　　1.基本用法：dynamic_cast expression
　　2.使用场景：只有在派生类之间转换时才使用dynamic_cast，type-id必须是类指针，类引用或者void*。
　　3.使用特点：
　　a、基类必须要有虚函数，因为dynamic_cast是运行时类型检查，需要运行时类型信息，而这个信息是存储在类的虚函数表中，只有一个类定义了虚函数，才会有虚函数表（如果一个类没有虚函数，那么一般意义上，这个类的设计者也不想它成为一个基类）。
　　b、对于下行转换，dynamic_cast是安全的（当类型不一致时，转换过来的是空指针），而static_cast是不安全的（当类型不一致时，转换过来的是错误意义的指针，可能造成踩内存，非法访问等各种问题）
　　c、dynamic_cast还可以进行交叉转换
三、const_cast转换
　　1.基本用法：const_castexpression
　　2.使用场景：
　　a、常量指针转换为非常量指针，并且仍然指向原来的对象
　　b、常量引用被转换为非常量引用，并且仍然指向原来的对象
　　3.使用特点：
　　a、cosnt_cast是四种类型转换符中唯一可以对常量进行操作的转换符
　　b、去除常量性是一个危险的动作，尽量避免使用。一个特定的场景是：类通过const提供重载时，一般都是非常量函数调用const_cast将参数转换为常量，然后调用常量函数，然后得到结果再调用const_cast 去除常量性。
四、reinterpret_cast转换
　　1.基本用法:reinterpret_castexpression
　　2.使用场景：不到万不得已，不用使用这个转换符，高危操作
　　3.使用特点：　　
　　a、reinterpret_cast是从底层对数据进行重新解释，依赖具体的平台，可移植性差
　　b、reinterpret_cast可以将整型转换为指针，也可以把指针转换为数组
　　c、reinterpret_cast可以在指针和引用里进行肆无忌惮的转换

lambda表达式可以简洁清晰的定义短小的逻辑，定义了一个匿名函数，可以捕获一定范围内的变量
1、声明式编程风格：就地匿名定义目标函数或函数对象，不需要额外写一个命名函数或者函数对象，以更直接的方式去写程序，好的可读性和可维护性。
2、简洁，不需要额外写一个命名函数或者函数对象，避免了代码膨胀和功能分散，让开发者更加集中精力在手边的问题，同时也获得了更高的生产率。
3、在需要的时间和地点实现功能闭包，使程序更灵活
就地封装短小的功能闭包，可以极其方便的表达出我们希望执行的具体操作，并让上下文结合的更加紧密。
可以任意封装出功能闭包，使得短小的逻辑可以以最简洁清晰的方式表达出来、
就地定义的匿名函数免除了维护一大堆函数对象的烦恼。也提高了程序的可读性。

源代码-预处理-编译-汇编-链接-可执行文件
1.程序的编译
（1）预处理：处理头文件，宏定义和条件编译，生成hello.ii文件
（2）编译：将hello.ii文件连同其他源文件一起生成汇编代码，hello.s
（3）汇编：将第二步产生的hello.s转化成目标文件hello.o
（4）链接：将第三步产生的目标文件hello.o链接成可执行文件，hello.exe或hello.out
注意：宏是在预处理的时候展开，inline是在编译的时候展开。

auto可以自动推导类型发生在编译阶段。
不能用于函数参数
不能定义数组
不能用于非静态成员变量
不能推导出模板参数有

静态链接：静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。链接器是一个独立程序，将一个或多个库或目标文件（先前由编译器或汇编器生成）链接到一块生成可执行程序。
优点：不同的程序模块可以独立开发和测试，最后链接在一起供用户使用，促进程序开发效率；
缺点：
(1) 浪费空间： 这是由于多进程情况下，每个进程都要保存静态链接函数的副本
(2)更新困难 ：当链接的众多目标文件中有一个改变后，整个程序都要重新链接才能使用心得版本

动态链接（Dynamic Linking）：相对于静态链接而言，要等到程序运行时再将组成程序的目标文件进行链接的过程。
优点：
(1)当系统多次使用同一个目标文件时，只需要加载一次即可，节省内存空间
(2)不同数据间的数据和指令访问都集中在了同一个共享模块，可以减少物理页面的换入换出，增加CPU的缓存命中率
(3)程序升级变得容易 当升级某个共享模块时，只需要简单的将旧目标文件替换掉，程序下次运行时，新版目标文件会被自动装载到内存并链接起来，即完成升级
(4)插件的引入 程序运行时可以动态选择加载的各种模块，即选择插件
(5)加强程序的兼容性 动态链接库相当于在程序和操作系统间增加一个中间层，消除程序对不同平台之间的依赖性

缺点：
(1)当程序依赖的某个模块更新后，如果新旧模块接口不兼容，将导致整个程序无法运行
(2)导致性能损失 动态链接把链接的过程推迟到装载的时候，那么程序每次被加载时都要进行重新链接，但是导致的性能损失与节省的空间和灵活性相比，还是值得的！

makefile:
target … : prerequisites …
command
目标：依赖
执行指令 …
CXX = g++
CC = gcc
client1: client1.o MySocket.o spidev_test.o uart.o mylib.o gps.o dataprocess.o VLP16.o
$(CXX) -o client1 client1.o MySocket.o spidev_test.o uart.o mylib.o gps.o dataprocess.o VLP16.o -lpthread
gps.o:gps.c gps.h conversion.h
$(CXX) -c gps.c (-c表示只编译，不链接，属于编译过程的中间阶段，
再经过链接才生成最后的可执行文件)；
clean:
rm -rf *.o
rm client1
pthread_mutex_t gps_mutex;
pthread_mutex_lock(&gps_mutex);
gps_data_copy = tdata;
pthread_mutex_unlock(&gps_mutex);

ofstream fout; //创建文件对象
fout.open(“time.txt”);
fout<" “<<-imu_angle[1]<<” “<<-imu_angle[2]<<” ";

linux启动文件.bashrc
rqt_graph能够创建一个显示当前系统运行情况的动态图形。包括节点和话题。
rostopic echo可以显示在某个话题上发布的数据。
rostopic type topic 命令用来查看所发布话题的消息类型。
我们可以使用rosmsg show msg命令来查看消息的详细情况
rostopic pub可以把数据发布到当前某个正在广播的话题上。
rostopic pub [topic] [msg_type] [args]
rqt_plot命令可以实时显示一个发布到某个话题上的数据变化图形。
用来进行调试。
rqt_console属于ROS日志框架(logging framework)的一部分，用来显示节点的输出信息。
rqt_logger_level允许我们修改节点运行时输出信息的日志等级（logger levels）
（包括 DEBUG、WARN、INFO和ERROR）。

cmake
CmakeLists.txt 文件内容：
PROJECT (HELLO)
SET(SRC_LIST main.c)
MESSAGE(STATUS "This is BINARY dir " ${HELLO_BINARY_DIR})

MESSAGE(STATUS "This is SOURCE dir "${HELLO_SOURCE_DIR})
ADD_EXECUTABLE(hello SRC_LIST)
外部构建
cmake …会生成makefile make 生成可执行文件
如何通过INCLUDE_DIRECTORIES指令加入非标准的头文件搜索路径。
如何通过LINK_DIRECTORIES指令加入非标准的库文件搜索路径。
如果通过TARGET_LINK_LIBRARIES 为库或可执行二进制加入库链接。
读串口等数据
ROS_INFO
ros::Publisher chatter_pub = n.advertise<std_msgs::String>(“chatter”, 1000);
告诉 master 我们将要在 chatter（话题名） 上发布 std_msgs/String 消息类型的消息。
这样 master 就会告诉所有订阅了 chatter 话题的节点，将要有数据发布。
第二个参数是发布序列的大小。
如果我们发布的消息的频率太高，缓冲区中的消息在大于 1000 个的时候就会开始丢弃先前发布的消息。
ros::Subscriber sub = n.subscribe(“chatter”, 1000, chatterCallback);
告诉 master 我们要订阅 chatter 话题上的消息。当有消息发布到这个话题时，ROS 就会调用 chatterCallback() 函数。
第二个参数是队列大小，以防我们处理消息的速度不够快，当缓存达到 1000 条消息后，
再有新的消息到来就将开始丢弃先前接收的消息。
cmakelists 添加可执行文件，把目标链接到库 头文件目录 包的依赖等

pthread_create QThread

vlp - 16
1.33ms一个包 频率1000/1.33=751hz （官方是754hz,1秒754个包）,12组数据，每组数据32个点。
1秒钟的点数：7541232=289536个点

频率：5-20hz
10hz时，电机600r/min, 10r/s
水平分辨率0.2度（0.2度有16个点），一个包12组数据是120.2=2.4度
一秒钟的点数：101216（360/2.4）=288000

icp pl-icp
拼接时初始选择两幅点云中有特征点的很小的一部分公共区域点云。（减小计算量增加拼接精度）

激光法线的计算可以用最小二乘法拟合一个平面及法线，也可以用pcl库直接计算法线。pca.PCL中有一个计算点云法线和曲率的类叫做NormalEstimation
法向滤波：利用pcl自带的方法（PCA主成分分析）先对每个点计算其法线，然后调整法线方向到同一个方向，
再利用各个点的K近邻通过最小二乘法拟合一个平面，通过平面法线修正第一步计算的法线（保证光顺效果的同时尽量保留原特征），
最后将该点沿修正后的法线方向投影到该平面上，
可以对点云进行平滑光顺处理。

在进行各种滤波前首先去除点云的离群点。
曲率滤波：将点云进行体素栅格划分，通过曲率的方差判断出每个栅格的曲率变化情况，对曲率变化大的栅格取曲率变化大的若干点，
对曲率变化小的栅格只取最接近这个栅格平均曲率的一个点。可以在保持点云特征的基础上减少点的数量。
法向滤波：对某个点的K近邻通过最小二乘法拟合一个平面，将该点沿拟合平面的法线方向投影到该平面上，
可以对点云进行平滑处理。
双边滤波：类似于图像处理的双边滤波算法，同时考虑了周围像素与中心像素的几何距离度量和灰度相似性度量
（两种度量均采用高斯核函数），对邻域中距离接近和灰度相似的像素点赋予较大的权值，反之赋予较小的权值。
厚度滤波：对于较厚的点云取中间正常厚度的点。
VoxelGrid滤波：对点云进行栅格划分，每个栅格中的点都用该栅格点云的质心来近似。

常见传感器工作原理：
Lidar:TOF 脉冲法 相位差法
DGPS:测量出已知位置的卫星到用户接收机之间的距离，然后综合多颗卫星(最少4颗)的数据就可知道接收机的具体位置。
距离差分。将一台GPS接收机安置在基准站上进行观测。根据基准站已知精密坐标，计算出基准站到卫星的距离改正数，并由基准站实时将这一数据发送出去。
用户接收机在进行GPS观测的同时，也接收到基准站发出的改正数，并对其定位结果进行改正，从而提高定位精度。
载波相位差分RTK（Real Time Kinematic），是实时处理两个测量站载波相位观测量的差分方法。
即是将基准站采集的载波相位发给用户接收机，进行求差解算坐标。
三维坐标x、y、z，卫星与接收机之间的时间差Δt作为未知数，然后用4个方程将这4个未知数解出来。
CAM:相机图像拍摄的过程实际上是一个光学成像的过程。相机内部具有整齐排列的微
小光敏元件-像元，像元通过外部光路接收到光线下会产生电荷并形成电压，经
过模拟数字转换电路即可得到数字信号，像元对不同光谱频段的可见光所产生的电压并
不相同，由此可以辨识物体的颜色纹理信息。所有像元形成的数字信号经过整理即可得
到图像数据，最后利用相关的图像显示软件即可形成我们熟悉的影像。
IMU：
陀螺仪：旋转角速度，
振动陀螺、科氏力间接测角速度。
光纤陀螺、光绕着圆周运动，运动的路径就是圆周的周长，如果在旋转运动时，运动的路径会增加一段或者
减少一段，根据运动路径的变化会测得旋转角速度。
加速度计：加速度，mems利用电容或者电阻桥，比如有两个电容板，中间有个物块，当加速运动时，物块会向一边运动，
电容充放电，电量的变化检测加速度。
磁力计：测磁场强度和方向。和指南针一样，检测地磁

imu单独标定：用港科大的imu_utils工具标定https://github.com/gaowenliang/imu_utils
kalibr标定IMU和摄像头的安装误差

加速度计和陀螺仪的误差包括：
确定性误差：bias、scale（实际数值和传感器输出值之间的比值1 LSB = 0.02°/sec）
六面法标定：将加速度计的3个轴分别朝上和朝下水平放置一段时间，采集六个面的数据完成标定

随机误差：假设噪声服从高斯分布、高斯白噪声、bias随机游走
Allen方差标定曲线

用陀螺角速度积分得到角度作为预测，加速度三角函数得到角度作为观测，卡尔曼滤波。
本文选用的 IMU 内部集成了三轴加速度计、三轴陀螺仪和三轴磁力计。对于加速度计，虽然可以通过反三角函数计算得到姿态角，
但是由于测量的加速度本身具有比较大的高频噪声，动态响应较差，在旋转的瞬间计算得到的姿态角往往会有比较大的误差；
对于陀螺仪，其动态响应良好，虽然可以通过按时间积分角速度来计算姿态角，但由于积分误差会随着时间积累（ADIS16480 的偏置稳定度在 6.25度 /小时，
也就是每分钟的累积误差在 0.1 左右），系统长时间运行就会造成相当大的累积误差；
所以常用的做法是对加速度计和陀螺仪的数据进行融合得到比较精确的横滚角和俯仰角。
由于加速度计只能计算出两个轴方向的姿态，所以需要引入磁力计，与陀螺仪进行融合来估计偏航角。
磁力计的特性基本与加速度计基本一致，动态响应较差，具有比较大的高频噪声，也不能单独用于姿态解算。

硬件同步了，软件怎么同步

IIC:同步、双向、半双工、
数据线SDA和时钟SCL构成的串行总线，可发送和接受数据。高速IIC总线一般可达400kbps以上。
I2C总线在传送数据过程中共有三种类型的信号，分别是：开始信号、结束信号和应答信号：
出现起始位后，SDA由高电平向低电平跳变，开始传送数据， SCL时钟线，当SCL下降沿时，结束数据传输。

SPI :同步、双向、全双工、高速
MOSI-主出从进、MISO-主进从出、SCLK-时钟信号，主设备产生、CS-片选线（选从设备）
串行外围设备接口,数据是一位一位传输的，主从模式工作，有一个主设备和一个或多个从设备，
没有地址的概念，时钟同步由SCLK来完成，主设备可以通过控制SCLK来控制数据传输快慢，甚至停止等。
接线时两个SPI口对应相接。SPI的数据输入和输出线独立，所以允许同时完成数据的输入和输出。

串口：异步、串行
TXD、RXD、GND
TX-RX,RX-TX

USB:
5V、USBDM、USBDP、GND

网口：
TD+、TD-、RD+、RD-

树莓派串口是ttl电平。硬件接线串口：GPS的TX和树莓派的RX连接，RX和TX连接，然后VCC接5V，GND接GND。这样就完成了树莓派和GPS的连接。
v4l2 直接读取 内存映射

TTL电平：全双工（逻辑1: 2.4V–5V 逻辑0: 0V–0.5V）
RS-232电平：全双工（逻辑1：-15V–3V 逻辑0：+3V–+15V）,不能联网
RS-485：半双工、（逻辑1：+2V–+6V 逻辑0： -6V—2V）这里的电平指AB 两线间的电压差。联网

智能指针：shared_ptr, weak_ptr, unique_ptr
方便内存管理（堆内存），防止内存泄漏和空悬指针。
shared_ptr实现共享式拥有（shared ownership）概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。shared_ptr使用引用计数，每一个shared_ptr的拷贝都指向相同的内存。每使用他一次，内部的引用计数加1，每析构一次，内部的引用计数减1，减为0时，自动删除所指向的堆内存。
Class unique_ptr实现独占式拥有或严格拥有概念，保证同一时间内只有一个智能指针可以指向该对象和相应资源，一旦拥有者被销毁或变为空，或开始拥有另一个对象，先前拥有的那个对象就会被销毁，其任何相应的资源也会被释放。它对于避免资源泄露——例如“以new创建对象后因为发生异常而忘记调用delete”——特别有用。
weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。
智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。

实习会负责什么工作内容
需要补充什么知识
未来的发展方向

树莓派串口是ttl电平。硬件接线串口：GPS的TX和树莓派的RX连接，RX和TX连接，然后VCC接5V，GND接GND。这样就完成了树莓派和GPS的连接。
v4l2 直接读取 内存映射

数据对齐：各类型数据按照一定的规则在空间内存上排列，而不是顺序的一个接一个的排放，这就是对齐。访问数据的地址要满足一定的条件，能被这个数据的长度所整除。 为了提高读取数据的效率，用空间换时间。
有效对齐值：自身对齐值和指定对齐值中较小的那个。对齐有两个规则：
1、不但结构体的成员有有效对齐值，结构体本身也有对齐值，这主要是考虑结构体的数组，对于结构体或者类，要将其补齐为其有效对齐值的整数倍。结构体的有效对齐值是其最大数据成员的自身对齐值；
2、存放成员的起始地址必须是该成员有效对齐值的整数倍。
大小端和数据字节对齐用在网络编程
大小端应用场合 ：大小端常用于网络主机之间传输数据
网络协议 判断网络数据是否正确

vivo:

3、 linux进程内存空间分为几段，各有什么作用
Linux进程可分为五部分：
代码区：存放可执行的指令操作，只能读不能写
全局区：存放未初始化的静态变量和全局变量
数据区：存放初始化的静态变量和全局变量
栈：存放临时变量，函数参数等
堆：存放new/malloc等动态申请的变量，用户必须手动进行delete/free操作

#include <>格式：引用标准库头文件，编译器从标准库目录开始搜索
#incluce ""格式：引用非标准库的头文件，编译器从用户的工作目录开始搜索

不是所有的函数都能自动地从基类继承到派生类中的。构造函数和析构函数是用来处理对象的创建和析构的，它们只知道对在它们的特殊层次的对象做什么。所以，在整个层次中的所有的构造函数和析构函数都必须被调用，也就是说，构造函数和析构函数不能被继承。

进程在其生存期内可能处于如下三种基本状态之一:
(1) 运行态(Run): 进程占有处理机资源，正在运行。 显然，在单处理机系统中任一时刻只能有一个进程处于此种状态;
(2) 就绪态(Ready): 进程本身具备运行条件，但由于处理机的个数少于可运行进程的个数，暂未投入运行。 即相当于等待处理机资源
(3) 等待态(Wait): 也称挂起态(Suspended)、封锁态(Blocked)、睡眠态(Sleep)。 进程本身不具备运行条件，即使分给它处理机也不能运行。 进程正等待某一个事件的发生，如等待某一资源被释放，等待与该进程相关的I/O传输的完成信号等。
进程的三个基本状态之间是可以相互转换的。具体地说，当一个就绪进程获得处理机时，其状态由就绪变为运行；当一个运行进程被剥夺处理机时，如用完系统分给它的时间片、出现更高优先级别的其它进程，其状态由运行变为就绪；当一个运行进程因某事件受阻时，如所申请资源被占用、启动I/O传输未完成，其状态由运行变为等待；当所等待事件发生时，如得到申请资源、I/O传输完成，其状态由等待变为就绪。

STL六大组件:https://www.cnblogs.com/welen/articles/3533008.html
容器（Container）:分为向量（vector），双端队列(deque)，表(list)，队列（queue），堆栈(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。
算法（Algorithm）
迭代器（Iterator）
仿函数（Function object）
适配器（Adaptor）
空间配置器（allocator）

1、数组具有遍历快，增删慢的特点。数组在堆中是一块连续的存储空间，遍历时数组的首地址是知道的.所以遍历快（数组遍历的时间复杂度为O(1) ）；当在中间插入或删除元素时，会造成该元素后面所有元素地址的改变，所以增删慢（增删的时间复杂度为O(n) ）。
链表具有增删快，遍历慢的特点。链表中各元素的内存空间是不连续的，一个节点至少包含节点数据与后继节点的引用，所以在插入删除时，只需修改该位置的前驱节点与后继节点即可，链表在插入删除时的时间复杂度为O(1)。但是在遍历时，get(n)元素时，需要从第一个开始，依次拿到后面元素的地址，进行遍历，直到遍历到第n个元素（时间复杂度为O(n) ），所以效率极低。
vector和list的区别
vector是用动态数组实现的，内存不够需再申请空间进行内存拷贝，另外地址是连续的，随机存取时间复杂度是O(1)，插入和删除时间复杂度是O(N)；
list是用双向链表实现的，是不连续的地址空间，随机存取需要遍历整个list，复杂度是O(N)，插入和删除时间复杂度是O(1)。

2、vector（动态数组）如何扩展内存和释放内存:
为了支持快速的随机访问，vector容器的元素以连续方式存放，每一个元素都紧挨着前一个元素存储。
一般vector进行内存分配时，其实际分配的容量要比当前所需的空间多一些，预留了一些额外的存储区，用于存放新添加的元素。capacity（）返回 vector 当前实际申请的空间大小，当存储容量不够时，会重新申请内存，然后将原来的元素拷贝到新的存储，然后析构原有的vector并释放原有的内存。

只有在调用析构函数的时候，vector 才会自动释放缓冲区。需要强制释放内存方法：
vector().swap(v1);将 v1 直接和空的vector交换，原内存当然就被销毁了。
//方法二：
vector v_temp;
v1.swap(v_temp);
第二种方法是曲线销毁，先定义一个临时变量。由于临时变量没有被初始化，所以，缓冲区大小为0.那么，当 V1 与它交换后，v1 原来占用的缓冲区就被销毁了。而临时变量 v_temp 调用析构函数来进行释放空间。

v.resize(0);释放内存:
v.shrink_to_fit();

STL:
****vector:****迭代器是普通指针，连续线性空间，动态数组
front,back;
vector v(2,1); size=2,值都为1
v.pop_back();

list:(环状)双向链表（prev*,next*,data），不连续空间，环状只要一个指针便可以完整表现整个链表。环状链表的尾端加上一个空白节点（前闭后开）。insert、erase、splice并不会使原有迭代器失效。

deque:双向开口的连续线性空间，deque允许常数时间对起头端进行插入或删除操作，且没有capacity概念，动态的分段连续空间组合，随时可以增加一段新的空间并链接起来，对deque的排序可先将deque完整复制到一个vector上，对vector排序后再复制回deque.deque 的底层为内存连续(分段连续)
deque采用一块所谓的map（不是map容器，是一小块连续空间）作为主控，其中每个元素（节点node）都是指针（指向指针的指针），指向另一段连续线性空间（缓冲区），默认512字节缓冲区存储空间主体。
迭代器如果到达所在缓冲区的尾端，再++,则切换至下一节点（缓冲区）的第一个元素。
迭代器如果到达所在缓冲区的头端，再–，则切换至前一节点的最后一个元素。

stack堆栈:先进后出，以deque为底部结构且封闭其头端开口，没有迭代器；

queue队列：先进先出，以deque为底部结构且封闭其底端的出口和前端的入口，没有迭代器。

map, set, multimap, and multiset底层实现是用红黑树实现的，红黑树是平衡二叉树的一种,插入、删除、查询的时间复杂度是O(logN）。获得良好的搜寻效率。

关联式容器，每个元素都有一个键值（key）和一个实值（value），当元素被插入时依照键值大小以某种特定规则将这个元素放在适当的位置。
map的键值可以和实值分开，并形成一种映射关系。

set:根据键值自动排序，不重复。set的键值就是实值，实值就是键值。不允许改变元素值（即是键值），insert或erase操作后迭代器仍然有效。存的是key。

map:根据键值自动排序，元素是pair，拥有key键值（第一元素）和value实值（第二元素），不允许相同键值。不能改变键值。可以改变实值。insert或erase操作后迭代器仍然有效。红黑树每个节点key和value都存。

hash table(散列表)、以hash table为底层机制的hash_set(散列集合)、hash_map(散列映射表)、hash_multiset(散列多键集合)、hash_multimap(散列多键映射表)。

hash table:插入、删除、搜寻等操作具有常数平均时间。是根据关键码值(Key value)而直接进行访问的数据结构，在O(1)下查找到元素。将待存数据的key经过映射函数变成一个数组(一般是vector)的索引，然后将k,v存到该索引中，查找时过程一样， key-value可快速查找。
不同的元素被映射到相同的位置,哈希表一个key对应多个value冲突（哈希碰撞）方法:
1、开放定址法：一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据存入；
2、再散列函数法：换一个散列函数计算，如除留余数、折叠、平方取中等；
3、链地址法：将冲突的value存在一个单链表中，在散列表中存储这个单链表的头指针，无论有多少冲突，都在当前位置给单链表增加节点即可；
4、公共溢出区法：将所有冲突的关键字建立一个公共的溢出区（溢出表）来存放。
hash function函数是计算元素位置的（或计算bucket位置的），取模。
STL中采用开链法处理冲突。vector中存链表（桶子buckets，表示一桶节点，存在vector里面，便于动态扩充，bucket指向一个节点，bucket初值为0），链表的每个节点nodes包括next指针和val，迭代器的前进操作如果目前节点在list的尾部，则跳到下一个bucket上。
链表插入是从链表头开始插入，（先插入的在链表尾部）。find查找时首先寻找落在那一个bucket里面，从bucket list的头开始，一一比对每个元素的键值，比对成功就跳出。count是一一比对每个元素的键值，比对成功就累加1；

hash_set：和set使用方法完全相同。无自动排序，可以快速查找元素，键值就是实值。

hash_map：根据键值快速搜寻元素，不自动排序。每个元素都存在key和value。

hash_multiset：无自动排序，可重复。

malloc分配内存是在堆里面获取内存区域的，属于用户数据段的，需要自己手动free掉。用户数据段最大3G的内存空间

memset是计算机中C/C++语言初始化函数。作用是将某一块内存中的内容全部设置为指定的值， 这个函数通常为新申请的内存做初始化工作。
char sbuf[128];
memset(sbuf,’\0’,sizeof(sbuf));目标地址，字符内容，长度
这是将sbuf置NULL值

socket编程，问了connect函数和accept函数的作用和参数

不能重载的运算符只有5个: 类属关系运算符"."、成员指针运算符".*"、作用域分辨符"::"、sizeof运算符和三目运算符"?:"

如果在vector尾部插入一个结点，当前迭代器会失效吗？
会失效，因为插入新数据后vector需要重新申请内存，那么存放这些元素的地址会发生变化，那么迭代器自然失效。

动态规划题：
1、爬楼梯-力扣
2、最小路径和-力扣
3、最长上升子序列-力扣
4、最长公共子序列-牛客
5、背包价值最大
6、编辑距离-力扣

TCP
服务器端的程序设计模式：
流程主要分为
（1）套接字初始化（socket()）
（2）套接字与端口的绑定（bind()）
（3）设置服务器的侦听连接（listen()）
（4）接受客户端连接（accept()）
（5）接收和发送数据（read()、write()）
（6）并进行数据处理及处理完毕的套接字关闭（close()）。
客户端的程序设计模式：
客户端模式分为
（1）套接字初始化（socket()）
（2）连接服务器（connect()）
（3）读写网络数据（read()、write()）
（4）并进行数据处理和最后的套接字关闭（close()）。

TCP网络编程流程：
服务端 socket bind listen accept recv/send close
客户端 socket connect send/recv close

UDP
服务器：socket bind recvfrom sendto close
客户端：socket sendto recvfrom close

共享内存信号量：
共享内存进行进程间的通信真的是非常方便，而且函数的接口也简单，数据的共享还使进程间的数据不用传送，而是直接访问内存，也加快了程序的效率。共享内存没有提供同步的机制，信号量的操作都是原子性的。
将同一段物理内存连接到两个进程各自的地址空间中，所有进程都可以访问共享内存中的地址，如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。
1、shmget用来创建共享内存shmid = shmget((key_t)1023467,BUF_SIZE,IPC_CREAT|0660)
参数：id有关、大小250K、权限，返回共享内存标识符
2、shmat用来启动对该共享内存的访问，并把共享内存连接到当前进程的地址空间。
shmptr = (char*)shmat(shmid,0,0);
参数：共享内存标识、共享内存连接到当前进程中的地址位置（0表示让系统选择）、标志位,返回指向共享内存第一个字节的指针
3、shmdt将共享内存从当前进程中分离int shmdt(const void *shmptr );
4、shmctl控制共享内存 int shmctl(int shmid , int command, struct shmid_ds *buf);
参数：共享内存标识符、采取的操作： IPC_RMID：删除共享内存段、结构指针（0）

加入信号量：信号量本质是一个计数器，控制访问共享资源的最大并行进程总数。信号量的使用主要是用来保护共享资源，使得资源在一个时刻只有一个进程（线程）所拥有。 信号量的值为正的时候，说明它空闲。所测试的线程可以锁定而使用它。若为0，说明它被占用，测试的线程要进入睡眠队列中，等待被唤醒。
信号量只能进行两种操作等待和发送信号，即P(sv)和V(sv),他们的行为是这样的：
P(sv)：如果sv的值大于零，就给它减1；如果它的值为零，就挂起该进程的执行
V(sv)：如果有其他进程因等待sv而被挂起，就让它恢复运行，如果没有进程因等待sv而挂起，就给它加1.
就是两个进程共享信号量sv，一旦其中一个进程执行了P(sv)操作，它将得到信号量，并可以进入临界区，使sv减1。而第二个进程将被阻止进入临界区，因为当它试图执行P(sv)时，sv为0，它会被挂起以等待第一个进程离开临界区域并执行V(sv)释放信号量，这时第二个进程就可以恢复执行。
semget函数创建一个新信号量或取得一个已有信号量
semctl函数用来直接控制信号量信息，SETVAL：用来把信号量初始化为一个已知的值。
IPC_RMID：用于删除一个已经无需继续使用的信号量标识符。
semop改变信号量的值 semaphore_P、semaphore_V操作等

析构函数需要用虚函数吗
需要用虚函数，因为如果不用虚函数，如果要调用子类的析构函数的话，就会只调用基类的析构函数，那么子类的内存空间得不到释放，就会造成内存泄漏。
const与#define相比，区别和优点：
（1）就起作用的阶段而言： #define是在编译的预处理阶段起作用，而const是在 编译、运行的时候起作用。
（2）就起作用的方式而言： #define只是简单的字符串替换，没有类型检查。而const有对应的数据类型，是要进行判断的，可以避免一些低级的错误。
（3）就存储方式而言：#define只是进行展开，有多少地方使用，就替换多少次，它定义的宏常量在内存中有若干个备份；const定义的只读变量在程序运行过程中只有一份备份。
（4）从代码调试的方便程度而言： const常量可以进行调试的，define是不能进行调试的，因为在预编译阶段就已经替换掉了。
const优点
（1）const常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换，没有类型安全检查，并且在字符替换可能会产生意料不到的错误。
（2）有些集成化的调试工具可以对const常量进行调试，但是不能对宏常量进行调试。
（3）const可节省空间，避免不必要的内存分配，提高效率

volatile作用：易变性。下一条语句不会直接使用上一条语句对应的volatile变量的寄存器内容，而是重新从内存中读取。“不可优化”特性。使编译器不对这个变量进行各种激进的优化，甚至将变量直接消除，保证程序员写在代码中的指令，一定会被执行。”顺序性”，能够保证Volatile变量间的顺序性，编译器不会进行乱序优化。
static对全局变量进行修饰改变了其作用域范围，由原来的整个工程可见变为本源文件可见。对于局部变量是存放在栈区的，其生命周期到该语句块执行结束，如用static修饰，便存放在静态数据区，其生命周期一直持续到整个程序执行结束。C++对类中的某个函数用static进行修饰，则表示该函数属于一个类而不是属于此类的任何特定对象static修饰函数使得函数只能在包含该函数定义的文件中被调用。

那么静态成员函数有特点呢？
（a）.静态成员之间可以相互访问，包括静态成员函数访问静态数据成员和访问静态成员函数;
（b）.非静态成员函数可以任意地访问静态成员函数和静态数据成员;
（c）.静态成员函数不能访问非静态成员函数和非静态数据成员;
（d）.调用静态成员函数，可以用成员访问操作符(.)和(->)为一个类的对象或指向类对象的指针调用静态成员函数,也可以用类名::函数名调用(因为他本来就是属于类的，用类名调用很正常)

const修饰一般常量及数组，修饰符const可以用在类型说明符前、后都行；（只读）
修饰变量，说明该变量不可以被改变；
修饰指针，分为指向常量的指针和指针常量；
常量引用，经常用于形参类型，即避免了拷贝，又避免了函数对值的修改；
修饰成员函数，说明该成员函数内不能修改成员变量。
const修饰指针变量及引用变量& ：如果const位于星号的左侧，则const就是用来修饰指针所指向的变量，即指针指向为常量；如果const位于星号的右侧，const就是修饰指针本身，即指针本身是常量。不能在类声明中初始化const数据成员。const数据成员的初始化只能在类构造函数的初始化表中进行。Const作用：定义常量具有不可变性。 便于进行类型检查，消除安全隐患；可以保护被修饰的东西，防止意外的修改，增强程序的健壮性。可以避免意义模糊的数字出现，很方便地进行参数的调整和修改。 同宏定义一样，可以不变则已，一变都变!
用extern会加速程序的编译过程，节省时间。此变量/函数是在别处定义的，要在此处引用。extern 后接C，表示告诉编译器在编译后面跟着的函数名时按着C的规则去翻译相应的函数名而不是C++的；
内联函数是代码被插入到调用者代码处的函数。通过避免被调用的开销来提高执行效率，内联函数会检查参数类型，所以更安全（宏定义不检查）；宏是由预处理器对宏进行替代，而内联函数是通过编译器控制来实现的。
heap-完全二叉树，使用最大堆排序，以数组(vector)的形式存放。

多态性：指相同对象收到不同消息或不同对象收到相同消息时产生不同的实现动作。
C++的多态分为静态多态（编译时多态）和动态多态（运行时多态）两大类。静态多态通过重载、模板来实现；动态多态就是通过虚函数来体现。虚函数作用：允许在派生类中重新定义与基类同名的函数，并且可以通过基类指针或引用来访问基类和派生类中的同名函数。方便使用多态性。当调用一个虚函数时，被执行的代码必须和调用函数的对象的动态类型相一致。通过vtbl（virtual table）和vptr（virtual table pointer）来实现的。纯虚函数是在基类中声明的虚函数，构造函数不能是虚函数，必须有实体。 。而且，在构造函数中调用虚函数，实际执行的是父类的对应函数，因为自己还没有构造好。 析构函数可以是虚函数，将一个函数定义为纯虚函数，是将这个类定义为抽象类，不能实例化对象 。析构函数可以是纯虚的，但纯虚析构函数必须有定义体，因为析构函数的调用是在子类中隐含的。 构造函数或析构函数为私有函数，所以该类是无法被继承的，

多态：动态绑定来实现，在基类的函数前加上virtual关键字，在派生类中重写该函数，运行时将会根据对象的实际类型来调用相应的函数，如果对象是派生类，则调用派生类的函数，如果对象是基类，则调用基类的函数，此为多态的实现。用vtbl和vptr来实现，每个类都有自己的vtbl，来保存自己类中虚函数的地址，对象会有一个vptr，来确定调用哪个函数，如果派生类中没有修改基类的虚函数，则指向基类的虚函数表，否则指向自己的vtbl。
虚函数是用来实现多态的，同一个实现接口，根据指向的对象不同而实现不同的功能。

1. 用virtual关键字申明的函数叫做虚函数，虚函数肯定是类的成员函数。
2. 存在虚函数的类都有一个一维的虚函数表叫做虚表。类的对象有一个指向虚表开始的虚指针。虚表是和类对应的，虚表指针是和对象对应的。
3. 多态性是一个接口多种实现，是面向对象的核心。分为类的多态性和函数的多态性。
4. 多态用虚函数来实现，结合动态绑定。
5. 纯虚函数是虚函数再加上= 0。
6. 抽象类是指包括至少一个纯虚函数的类。
   纯虚函数：virtual void breathe()=0；即抽象类！必须在子类实现这个函数!即先有名称，没内容，在派生类实现内容!

内存分配：（1）从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。（2）在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。（3）从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。
一个由C/C++编译的程序占用的内存分为以下几个部分：
1、栈区（stack）：又编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构的栈。
2、堆区（heap）：一般是由程序员分配释放，若程序员不释放的话，程序结束时可能由OS回收，值得注意的是他与数据结构的堆是两回事，分配方式倒是类似于数据结构的链表。
3、全局区（static）：也叫静态数据内存空间，存储全局变量和静态变量，全局变量和静态变量的存储是放一块的，程序结束后由系统释放。
4、文字常量区：常量字符串就是放在这里，程序结束后由系统释放。
5、程序代码区：存放函数体的二进制代码。

栈：空间由操作系统自动分配/释放，后进先出，空间有限，
堆（队列）：手动分配释放，先进先出，很大的自由存储区。

指针和引用的区别：相同点：1. 都是地址的概念；指针指向一块内存，它的内容是所指内存的地址；引用是某块内存的别名。区别：1. 指针是一个实体，而引用仅是个别名；2. 引用使用时无需解引用(*)，指针需要解引用；3. 引用只能在定义时被初始化一次，之后不可变；指针可变；4. 引用没有 const，指针有 const；5. 引用不能为空，指针可以为空；6. “sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身(所指向的变量或对象的地址)的大小；7. 指针和引用的自增(++)运算意义不一样；8.从内存分配上看：程序为指针变量分配内存区域，而引用不需要分配内存区域。
override（重写/覆盖）1、方法名、参数、返回值相同。2、子类方法不能缩小父类方法的访问权限。3、子类方法不能抛出比父类方法更多的异常(但子类方法可以不抛出异常)。4、存在于父类和子类之间。5、方法被定义为final不能被重写。
overload（重载）1、参数类型、个数、顺序至少有一个不相同。 2、不能重载只有返回值不同的方法名。3、存在于父类和子类、同类中。
动态链接是只建立一个引用的接口，而真正的代码和数据存放在另外的可执行模块中，在运行时再装入；而静态链接是把所有的代码和数据都复制到本模块中，运行时就不再需要库了。
小端模式：低位字节排放在内存的低地址端，高位字节排放在内存的高地址端；
五种I/O 模式：
1、阻塞I/O (Linux下的I/O操作默认是阻塞I/O，即open和socket创建的I/O都是阻塞I/O)
2、 非阻塞 I/O 3、 I/O 多路复用 4、信号驱动 I/O (SIGIO) 5、异步 I/O
new是分配在自由存储区而malloc分配在堆上；malloc和free是库函数，而new和delete是C++操作符；. new自己计算需要的空间大小，malloc需要指定大小；new在动态分配内存的时候可以初始化对象，调用其构造函数，delete在释放内存时调用对象的析构函数。而malloc只分配一段给定大小的内存，并返回该内存首地址指针，如果失败，返回NULL；new可以调用malloc来实现，但是malloc不能调用new来实现；C++允许重载new/delete操作符，malloc不允许重载。
平衡二叉树：其中每一个结点的左子树和右子树的高度差至多等于1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF。平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度
红黑树：是平衡树。1、红节点的孩子节点不能是红节点；2、从根到前端节点的任意一条路径上的黑节点数目一样多。红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，是一种查找树。红黑树从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。红黑树的特性:（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
字典树（Trie）可以保存一些字符串->值的对应关系。
多进程：优点：内存隔离，单个进程的异常不会导致整个应用的崩溃。方便测试，编程简单。
缺点：进程间调用，通讯和切换均比多线程大，耗资源。使用场所：目标子动能交互少，如果资源和性能许可，可以设计由多个子应用程序来组合完成目的。
多线程 ：优点：提高系统的并行性，并且开销小。数据共享方便（不需要进程间的通信）
缺点：没有内存隔离，单个线程的崩溃会导致整个应用程序的退出。编程复杂；调试困难；线程执行的随机性可能导致逻辑混乱，甚至发生死锁现象；使用场所：在存在大量IO，网络等耗时操作，或者需要和用户交互时，使用多线程有利于提高系统的并行性和用户界面快速响应从而提高友好性。
进程线程区别：一个进程可以包含多个线程，它们共享这个进程的资源。进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位。进程是资源分配的最小单位，线程是程序执行的最小单位。CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式进行。但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也死掉了，而一个进程死掉并不会对另外一个进程造成影响，因为进程有自己独立的地址空间。“互斥锁” Mutex，防止多个线程同时读写某一块内存区域。“信号量”（Semaphore），用来保证多个线程不会互相冲突。
进程间通信—使用共享内存：信号，信号量，消息队列。

计算机网络体系结构：OSI，TCP/IP，五层协议的体系结构
答:OSI分层 （7层）：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。
TCP/IP分层（4层）：网络接口层、 网际层、运输层、 应用层。
五层协议 （5层）：物理层、数据链路层、网络层、运输层、 应用层。
应用层（网络服务与最终用户的一个接口）FTP、DNS、Telnet、SMTP、HTTP、WWW、NFS
表示层（数据的表示.安全.压缩、翻译。）JPEG.ASCll.MPEG、加密格式等
会话层（建立.管理.终止会话。）
传输层（提供端到端的可靠报文传递和错误恢复）：TCP、UDP
网络层（进行逻辑地址寻址,实现不同网络之间的路径选择。）：IP、ICMP、 （路由器）
数据链路（建立逻辑连接.进行硬件地址寻址.差错校验等功能。）VLAN、MAC （网桥，交换机）
物理层（通过媒介传输比特,确定机械及电气规范）：RJ45、CLOCK、IEEE802.3 （中继器，集线器）
TCP连接的三次握手：
第一次握手：客户端发送一个tcp的syn标志位置为1的包（连接请求），指明客户打算连接服务器的端口；
第二次握手：当服务器收到连接请求之后，返回确认包（ack）应答，即将syn和ack标志位同时致为1（授予连接），并为这次连接分配资源；
第三次握手：客户端收到服务器的授予连接请求之后，再次发送确认包（ack）（syn标志位为0，ack标志位为1），并分配资源，这样tcp就建立连接了。
1、tcp是基于连接的，可靠性高；udp是基于无连接的，可靠性较低；
2、由于tcp是连接的通信，需要有三次握手、重新确认等连接过程，会有延时，实时性差；同时过程复杂，也使其易于被攻击；而udp无连接，无建立连接的过程，因而实时性较强，也稍安全；如果对实时性要求高和高速传输的场合下需要使用udp；如果需要传输大量数据且对可靠性要求高的情况下应该使用tcp；在可靠性要求较低，追求效率的情况下应该使用udp。
为什么用udp:UDP能够对握手过程进行精简，减少网络通信往返次数；收发快速，无阻塞。
采用TCP，一旦发生丢包，TCP会将后续包缓存起来，等前面的包重传并接收到后再继续发送，延迟会越来越大。本系统带宽足够，丢包较少。少量的丢包也不会产生影响。激光扫描仪 VLP-16 的工作模式是 UDP 客户端模式，控制器 CM3 作为服务器，创建 UDP Server Socket 套接字并且绑定 VLP-16 的IP 地址和端口号，读取由 VLP-16 发送过来的数据。

pwd 得到当前目录。… 上一次 / 系统根目录 ~ 用户主目录
Top 显示当前系统正在执行的进程的相关信息，包括进程ID、内存占用率、CPU占用率等
查看当前进程ps 执行退出exit 清屏 clear
cat 文件名 #显示全部文件内容
more 文件名 #分页显示文件内容
less 文件名 #与 more 相似，更好的是可以往前翻页
tail 文件名 #仅查看尾部，还可以指定行数
head 文件名 #仅查看头部,还可以指定行数
Grep 是一种强大的文本搜索工具，它能使用正则表达式搜索文本，并把匹 配的行打印出来。
使用 & 在命令结尾来让程序自动运行
Netstat 监控TCP/IP网络可以显示路由表、实际的网络连接以及每个网络接口设备的状态信息。
netstat -a # 列出所有端口 netstat -l # 只显示监听端口 netstat -p显示进程ID\名称
Structure 与 Union主要有以下区别:

1. struct和union都是由多个不同的数据类型成员组成, 但在任何同一时刻, union中只存放了一个被选中的成员, 而struct的所有成员都存在。在struct中，各成员都占有自己的内存空间，它们是同时存在的。一个struct变量的总长度等于所有成员长度之和。在Union中，所有成员不能同时占用它的内存空间，它们不能同时存在。Union变量的长度等于最长的成员的长度。
2. 对于union的不同成员赋值, 将会对其它成员重写, 原来成员的值就不存在了, 而对于struct的不同成员赋值是互不影响的。
   构造数据类型,也叫联合体：用途：使几个不同类型的变量共占一段内存(相互覆盖)
   结构体是一种构造数据类型，用途：把不同类型的数据组合成一个整体-------自定义数据类型

如何判断一棵树是平衡二叉树
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

面向对象的三个特征，分别有什么作用？
封装，也就是把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。
继承：继承是指这样一种能力：它可以使用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展
多态：允许将子类类型的指针赋值给父类类型的指针。
实现多态，有二种方式，覆盖，重载。

引用和多态的区别？
答：引用就是某一变量（目标）的一个别名，对引用的操作与对变量直接操作完全一样。
多态是允许你将父对象设置成和它一个或更多的子对象相等的技术，赋值之后， 父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。简单地说就是一句话，允许将子类类型的指针赋值给父类型的指针。多态在C++中是通过虚函数实现的。

同步通信与异步通信区别：
1.同步通信要求接收端时钟频率和发送端时钟频率一致，发送端发送连续的比特流；异步通信时不要求接收端时钟和发送端时钟同步，发送端发送完一个字节后，可经过任意长的时间间隔再发送下一个字节。 2.同步通信效率高；异步通信效率较低。3.同步通信较复杂，双方时钟的允许误差较小；异步通信简单，双方时钟可允许一定误差。4.同步通信可用于点对多点；异步通信只适用于点对点。

IP地址的分类：
A类地址：以0开头， 第一个字节范围：1~126（1.0.0.0 - 126.255.255.255）；
B类地址：以10开头， 第一个字节范围：128~191（128.0.0.0 - 191.255.255.255）；
C类地址：以110开头， 第一个字节范围：192~223（192.0.0.0 - 223.255.255.255）；
D类地址：以1110开头，第一个字节范围：224~239（224.0.0.0 - 239.255.255.255）；（作为多播使用）
E类地址：保留
其中A、B、C是基本类，D、E类作为多播和保留使用。
以下是留用的内部私有地址：
A类 10.0.0.0–10.255.255.255
B类 172.16.0.0–172.31.255.255
C类 192.168.0.0–192.168.255.255
IP地址与子网掩码相与得到网络号：
ip : 192.168.2.110&
Submask : 255.255.255.0
网络号 ：192.168.2 .0
注:主机号，全为0的是网络号（例如：192.168.2.0），主机号全为1的为广播地址（192.168.2.255）

ARP(ip地址到物理地址的解析)是地址解析协议，简单语言解释一下工作原理：
答:1：首先，每个主机都会在自己的ARP缓冲区中建立一个ARP列表，以表示IP地址和MAC地址之间的对应关系。
2：当源主机要发送数据时，首先检查ARP列表中是否有对应IP地址的目的主机的MAC地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送ARP数据包，该数据包包括的内容有：源主机 IP地址，源主机MAC地址，目的主机的IP 地址。
3：当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的IP和MAC地址写入到ARP列表中，如果已经存在，则覆盖，然后将自己的MAC地址写入ARP响应包中，告诉源主机自己是它想要找的MAC地址。
4：源主机收到ARP响应包后。将目的主机的IP和MAC地址写入ARP列表，并利用此信息发送数据。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。
广播发送ARP请求，单播发送ARP响应。
描述RARP协议：
RARP是逆地址解析协议，作用是完成硬件地址到IP地址的映射，主要用于无盘工作站，因为给无盘工作站配置的IP地址不能保存。工作流程：在网络中配置一台RARP服务器，里面保存着IP地址和MAC地址的映射关系，当无盘工作站启动后，就封装一个RARP数据包，里面有其MAC地址，然后广播到网络上去，当服务器收到请求包后，就查找对应的MAC地址的IP地址装入响应报文中发回给请求者。RARP只能用于具有广播能力的网络。
各种协议的介绍：
ICMP协议： 因特网控制报文协议。它是TCP/IP协议族的一个子协议，用于在IP主机、路由器之间传递控制消息。
TFTP协议： 是TCP/IP协议族中的一个用来在客户机与服务器之间进行简单文件传输的协议，提供不复杂、开销不大的文件传输服务。
HTTP协议： 超文本传输协议，是一个属于应用层的面向对象的协议，由于其简捷、快速的方式，适用于分布式超媒体信息系统。
NAT协议：网络地址转换属接入广域网(WAN)技术，是一种将私有（保留）地址转化为合法IP地址的转换技术，
DHCP协议：动态主机配置协议，是一种让系统得以连接到网络上，并获取所需要的配置参数手段，使用UDP协议工作。具体用途：给内部网络或网络服务供应商自动分配IP地址，给用户或者内部网络管理员作为对所有计算机作中央管理的手段。

四次挥手
断开一个TCP连接则需要“四次握手”。
第一次挥手：主动关闭方发送一个FIN，用来关闭主动方到被动关闭方的数据传送，也就是主动关闭方告诉被动关闭方：我已经不 会再给你发数据了，但是，此时主动关闭方还可 以接受数据。
第二次挥手：被动关闭方收到FIN包后，发送一个ACK给对方，确认序号为收到序号+1。
第三次挥手：被动关闭方发送一个FIN，用来关闭被动关闭方到主动关闭方的数据传送，也就是告诉主动关闭方，我的数据也发送完了，不会再给你发数据了。
第四次挥手：主动关闭方收到FIN后，发送一个ACK给被动关闭方，确认序号为收到序号+1，至此，完成四次挥手。

在浏览器中输入www.baidu.com后执行的全部过程：
1、客户端浏览器通过DNS解析到www.baidu.com 的IP地址220.181.27.48，通过这个IP地址找到客户端到服务器的路径。客户端浏览器发起一个HTTP会话到220.181.27.48，然后通过TCP进行封装数据包，输入到网络层。
2、在客户端的传输层，把HTTP会话请求分成报文段，添加源和目的端口，如服务器使用80端口监听客户端的请求，客户端由系统随机选择一个端口如5000，与服务器进行交换，服务器把相应的请求返回给客户端的5000端口。然后使用IP层的IP地址查找目的端。
3、客户端的网络层不用关心应用层或者传输层的东西，主要做的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是由路由器来完成的工作，我不作过多的描述，无非就是通过查找路由表决定通过那个路径到达服务器。
4、客户端的链路层，包通过链路层发送到路由器，通过邻居协议查找给定IP地址的MAC地址，然后发送ARP请求查找目的地址，如果得到回应后就可以使用ARP的请求应答交换的IP数据包现在就可以传输了，然后发送IP数据包到达服务器的地址。

DNS域名系统，简单描述其工作原理：
当DNS客户机需要在程序中使用名称时，它会查询DNS服务器来解析该名称。客户机发送的每条查询信息包括三条信息：包括：指定的DNS域名，指定的查询类型，DNS域名的指定类别。基于UDP服务，端口53. 该应用一般不直接为用户使用，而是为其他应用服务，如HTTP，SMTP等在其中需要完成主机名到IP地址的转换。

网络排错常用思路及每一步的作用或目的。
先ping回环地址，检查TCP/IP驱动是否正常；
再ping本网段其他主机，检查内网通信是否正常；
再ping默认网关，检查出口路由是否正常；
再ping其他网段其他主机，检查远程连通性。

请描述Linux系统优化的12个步骤。
⑴登录系统:不使用root登录，通过sudo授权管理，使用普通用户登录。
⑵禁止SSH远程：更改默认的远程连接SSH服务及禁止root远程连接。
⑶时间同步：定时自动更新服务器时间。
⑷配置yum更新源，从国内更新下载安装rpm包。
⑹调整文件描述符数量，进程及文件的打开都会消耗文件描述符。
⑻精简开机启动服务（crond、sshd、network、rsyslog）
⑼Linux内核参数优化/etc/sysctl.conf，执行sysct -p生效。

如果一台办公室内主机无法上网（打不开网站），请给出你的排查步骤？
①首先确定物理链路是否联通正常。
②查看本机IP，路由，DNS的设置情况是否达标。
③telnet检查服务器的WEB有没有开启以及防火墙是否阻拦。
④ping一下网关，进行最基础的检查，通了，表示能够到达服务器。
⑤测试到网关或路由器的通常情况，先测网关，然后再测路由器一级一级的测试。
⑥测试ping公网ip的通常情况（记住几个外部IP），
⑦测试DNS的通畅。ping出对应IP。
⑧通过以上检查后，还在网管的路由器上进行检查。
3.请简要描述Linux系统下源代码编译方式安装软件的大致步骤
tar释放源码包
cd切换到解压目录
./configure配置
make编译
makeinstall安装
如何查看端口占用情况和处理方法。
①.使用netstat命令查看端口占用情况。netstat -tln
②.我们还需要知道是什么程序占用,加上-p参数 netstat -tlnp
③.如果比较多的时候我们也可以用grep过滤一下 然后找到端口进程 netstat -tlnp|grep 10221
④.然后kill掉占用端口的进程即可,正常情况下就可以启动新进程好了
网络故障时排除故障的流程
首先确认是不是名称解析出了问题 dig hostname
是不是IP或者网卡的问题 ifconfig #查看网卡的设置和网卡的IP地址
若网卡正常还有正确获取IP地址则可能是Default gateway网关不正确
如果以上设置都正确则看看内核里是否载入了网卡驱动 cat /etc/modprobe.conf #查看是否载入网卡驱动 如果以上都不是则重新启动网卡看看有没有错误提示
ifdown eth0 #停用网卡 ifup eth0 #启动网卡
在正常情况下无论是停用或是启动系统都不会提示任何信息
开机故障时排除故障的流程
首先查看是不是开机管理程序出了问题
在RHEL4中会使用GRUB当作默认的开机管理程序
接下来确认有没有正确的载入内核 开机时发生panic则表示根目录没有挂载成功
检查/sbin/init设置有没有错误 检查/etc/inittab设置有没有错误
并且检查根目录有没有损坏 如果/etc/rc.d/rc.sysinit执行不成功则有可能是 /bin/bash文件损坏 /etc/fstab设定有误 都不是以上问题的话则检查/etc/rc.d/rc文件 检查/etc/rc.d/rcn1-6.d有没有问题
文件系统故障时,排除故障的流程
文件系统故障,通常是因为电脑宕机或不正常关机
当文件系统故障时,先卸载文件系统
#fsck –y 来测试指定的文件系统 当文件系统修复后,再挂载文件系统 #fsck 可以用来测试并修复Linux的文件系统 修复文件系统,全程文字记录 umount /home #卸载文件系统 ls /home #查看目录是不是空的确定是否被卸载
fsck -y /dev/sda8 #检查并修复文件系统对应的文件
fsck 1.39 (29-May-2006) e2fsck 1.39 (29-May-2006) /home: clean, 31/130560 files, 32156/522080 blocks mount /dev/sda2 /home #挂载修复完成的文件系统
ls /home #查看是否修复成功 apache lost+found soft tmail tmail_v4.5.1_release.tar www
Linux 下进程间的通信方式有以下几种
管道、信号、共享内存、消息队列、信号量、套接字socket、文件锁

死锁：指两个或两个以上的进程在执行过程中，由于竞争资源或由于彼此通信而造成的一种阻塞的现象，若无外力作用，他们都将无法推进下去，此时称系统进入死锁状态或产生了死锁，这些永远在互相等待的进程称为死锁进程。
条件：互斥条件、请求与保持条件、不剥夺条件、循环等待条件
预防：要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。
避免：安全序列、银行家算法
检测与解除：撤销所有的死锁进程、进程回退（Roll Back）再启动、剥夺死锁进程的所有资源可以解除死锁

产生死锁的两种情况：
一种情况是：如果同一个线程先后两次调用lock，在第二次调用时，由于锁已经被占用，该线程会挂起等待别的线程释放锁，然而锁正是被自己占用着的，该线程又被挂起而没有机会释放锁，因此就永远处于挂起等待状态了，产生死锁。
另一种典型的死锁情形是：线程A获得了锁1，线程B获得了锁2，这时线程A调用lock试图获得锁2，结果是需要挂起等待线程B释放锁2，而这时线程B也调用lock试图获得锁1，结果是需要挂起等待线程A释放锁1，于是线程A和B都永远处于挂起状态了。

如何避免死锁：

不用互斥锁（这个很多时候很难办到）
写程序时应该尽量避免同时获得多个锁。
如果一定有必要这么做，则有一个原则：如果所有线程在需要多个锁时都按相同的先后顺序（常见的是按Mutex变量的地址顺序）获得锁，则不会出现死锁。 （比如一个程序中用到锁1、锁2、锁3，它们所对应的Mutex变量的地址是锁1<锁2<锁3，那么所有线程在需要同时获得2个或3个锁时都应该按锁1、锁2、锁3的顺序获得。如果要为所有的锁确定一个先后顺序比较困难，则应该尽量使用pthread_mutex_trylock调用代替pthread_mutex_lock调用，以避免死锁。）
1
2
3

ping 使用的协议为icmp，通过域名解析，需要用到DNS，局域网中使用arp进行主机间的通信。TCP层是位于IP层之上,应用层之下的中间层。不同主机的应用层之间经常需要可靠的、像管道一样的连接

红黑树和avl树都属于自平衡二叉树；
两者查找、插入、删除的时间复杂度相同；O(log2n)
包含n个内部结点的红黑树的高度是o(logn);
TreeMap是一个红黑树的实现，能保证插入的值保证排序
红黑树不追求“完全平衡 ”，只要求部分地达到平衡，降低对旋转的要求，提高性能。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高
在AVL树中任何节点的两个儿子子树的高度最大差别为一

HTTP状态码：200(“OK”)一切正常。 404(“Not Found”)当客户端所请求的URI（统一资源标识符）不对应于任何资源时，发送此响应代码。410用于服务器端知道客户端所请求的资源曾经存在，但现在已经不存在了的情况。
HTTP和HTTPS的区别：
HTTP：超文本传输协议，是在互联网上应用最广泛的一种网络协议。是一个客户端和服务端请求和应答的标准（TCP），用于从WWW（超文本）服务器传输超文本到本地浏览器。它可以使浏览器更加高效，使网络传输减少。
HTTPS：是以安全为目标的HTTP通道，可以看做是HTTP的安全版，即HTTP+SSL（安全套接层）。HTTPS的安全基础是SSL，因此加密的详细内容就需要SSL。HTTPS作用：建立一个信息安全通道，保证数据传输的安全。确认网站的真实性。区别：
1、HTTP是超文本传输协议，信息是明文传输，HTTPS是具有安全性的SSL加密传输协议。
2、HTTPS协议需要申请证书，一般免费证书少，因而需要一定费用。
3、连接方式完全不同，用的端口也不一样。前者是80，后者是443。
4、HTTP连接是无状态的，HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，安全性高于HTTP协议。
HTTP的工作原理：1、Client与Server建立连接，单击某个超链接，HTTP的工作开始。
2、连接建立后，Client发送一个请求给Server，请求方式的格式为：统一资源标识符（URL）、协议版本号，后边是MIME信息包括请求修饰符，Client信息和可能的内容。3、Server接到请求后，给予相应的响应信息，其格式为一个状态行，包括信息的协议版本号、一个成功或错误的代码，后边是MIME信息包括Server信息、实体信息和可能的内容。4、Client接收Server返回的信息通过浏览器显示在用户的显示屏上，然后Client和Server断开连接。
HTTPS的工作原理：1、Client使用HTTPS的URL访问Web服务器，要求与Web服务器建立SSL连接。2、Web服务器收到客户端请求后，会将网站的证书信息（证书中包含公钥）传送一份给客户端。3、客户端的浏览器与Web服务器开始协商SSL连接的安全等级，也就是信息加密的等级。4、客户端的浏览器根据双方同意的安全等级，建立会话密钥，然后利用网站的公钥将会话密钥加密，并传送给网站。5、Web服务器利用自己的私钥解密出会话密钥。6、Web服务器利用会话密钥加密与客户端之间的通信。
Https优缺点：优点：可认证用户和服务器，确保数据发送到正确的客户机和服务器；可防止数据在传输过程中不被窃取、改变，确保数据的完整性。大幅增加了中间人攻击的成本。
缺点：握手阶段比较费时，页面的加载时间延长；HTTPS连接缓存不如HTTP高效，会增加数据开销和功耗，甚至已有的安全措施也会因此而受到影响；SSL证书需要钱，功能越强大的证书费用越高，加密范围也比较有限，在黑客攻击、拒绝服务攻击、服务器劫持等方面几乎起不到什么作用。
打开一个网页的过程：