SLAM面试总结...

た入场券 2024-04-18 07:08 68阅读 0赞

## 1、什么是闭环检测，常用方法有哪些 ##

随着相机的运动，我们计算的相机位姿，三角化得到的点云位置，都是有误差的，即使我们使用局部的或全局的BA去优化，仍然会存在累积误差。而消除误差最有效的办法是发现闭环，并根据闭环对所有结果进行优化。闭环是一个比BA更加强烈、更加准确的约束。

目前SLAM中用的比较多的方法是词袋模型，词袋模型中涉及到字典的生成和使用的问题，这一部分和机器学习的只是挂钩比较深。  
字典的生成问题就是非监督聚类问题，可以采用K-means对特征点进行聚类，然后通过K叉树进行表达，相似度判断采用是TD-IDF的方法。

## 2、解释一下梯度下降，牛顿法 ，高斯牛顿和LM算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70]

## 3 ceres库 ##

求F(x) F(x)F(x)平方和最小  
思路：  
第一步：利用模板，建立CostFunctor，有4个分别是F1(x1,x2); F2(x3,x4);F3(x2,x3); F4(x1,x4)  
第二步：建立problem；先使用AutoDiffCostFunction分别对F1,F2,F3,F4求导，再problem.AddResidualBlock都加入残差块  
第三步：solver解算器的options,summary

## 4 卡尔曼滤波的3个条件 ##

状态方程和观测方程为线性方程  
观测噪声为高斯噪声  
初始状态分布为高斯分布

## 5 紧耦合和松耦合 ##

紧耦合系统将视觉测量残差和IMU测量残差一起加入后端优化系统中进行优化  
松耦合系统是计算完视觉结果和IMU结果后再进行优化。

## 6 你认为室内SLAM与自动驾驶SLAM有什么区别 ##

地图不同：自动驾驶的高精地图是经过标注后的语义地图。视觉slam的地图则主要用于导航使用。

自动驾驶的定位方案一般为：GPS+IMU+里程计，为了仿真在gps信号差的地方产生跳变，也会结合slam这种相对定位的方法。第二种方案是：GPS+多线雷达+高精度地图。第三种方案是多个双目视觉相机slam方案。

室内slam主要是以激光和视觉slam为主流。

## 7 地图点的构建方法有哪些 ##

点云地图  
2D栅格地图  
八叉树地图

## 8 鲁棒核函数有哪些 ##

## 9 介绍RANSAC等鲁棒估计的方法 ##

点：每一个数据，SLAM里指的是匹配的点对  
野值/外点：错误的点  
内点：正确的点  
内点集：内点的集合  
外点集：外点的集合  
模型：待估计的参数  
s ss ：估计模型所需要的最小点数  
S SS ：所有的点形成的点集

RANSAC的想法是从点集中随机的选择出s ss 个点，估计出一个模型，查看剩余点是否符合这个模型。如果大部分点都符合这个模型，就相当于我们找到了一个合适的模型，自然的符合模型的点就是内点啦。由于是随机选择，一次可能难以找到正确的模型，因此需要多次才可以。一般直线方程估计中采用点到线的距离的平方，基本矩阵估计中也使用点到极线的距离的平方，单应和相机内参估计中使用点到点的距离的平方。

## 10 求导 ##

## 11 单目相机的内外参模型 ##

相机内参包括焦距fx，fy，cx，cy，径向畸变系数k1,k2,k3，切向畸变系数p1,p2  
其中内参一般来说是不会改变，但是当使用可变焦距镜头时每次改变焦距需要重新标定内参  
当图像裁剪时内参cx，cy会发生改变，比如图像从88变成44时，cx，cy需要除以2  
一般标定工业相机时只需要得到畸变系数k1，k2即可，对于畸变系数较大的鱼眼相机需要得到k3，p1，p2  
相机外参分为旋转矩阵R和平移矩阵t，旋转矩阵和平移矩阵共同描述了如何把点从世界坐标系 转换到摄像机坐标系

## 12 VINS-Mono优缺点 ##

## 13 如何标定相机和IMU的外参 ##

采集图像标定相机内参和畸变参数 ，重投影误差在 0.1~0.2 标定结果较好，静止采集两个小时IMU数据的加速度计和陀螺噪声以及随机游走.  
同时采集imu和相机数据，将相机参数配置文件，imu参数配置文件，图像与imu的bag文件，标定板参数输入到kalibr\_calibrate\_imu\_camera中，输出camchain-imucam配置文件。  
注意事项：  
i,确保图像不要模糊，运动不要太快。  
ii，最好要遍历imu的所有轴，即充分旋转和加速。

## 14 给定一张图片，已知相机和地面之间的相对关系，计算出图的俯视图 ##

## 15 双线性插值 ##

## 16 视觉SLAM方法一般分为特征点法和直接法。请简述一下特征点法和直接法的概念，以及对应的优缺点。 ##

特征点法，根据提取匹配特征点来估计相机运动，优化的是重投影误差，对光照变化不敏感，是比较成熟的方案，常见的开源方案有orbslam  
优点：特征点本身对光照运动旋转比较不敏感，所有比较稳定; 相机运动较快也能跟踪成功，鲁棒性好一些;方案成熟  
缺点：关键点提取，描述子，匹配时间长;特征点丢失场景无法适应；只能构建稀疏地图；  
直接法：根据相机的亮度信息估计相机运动，可以不需要计算关键点和描述子，优化的是光度误差，根据使用像素数量可以分为稀疏半稠密稠密三种  
优点：速度快，可以省去计算特征点，描述子时间；可以用在特征缺失场合，特征法在该情况下会极速变差  
因为假设了灰度不变，所以容易受光照变化影响，要求相机运动较慢或采集频率较高;单个像素或像素块区分度不强

## 17 用自己的语言描述一下关键帧是什么？有什么用？如何选择关键帧？ ##

关键帧可以减少待优化的帧数，并且可以代表其附近的帧。

选取指标为：  
（1）距离上一关键帧的帧数是否足够多，比如我每隔固定帧数选择一个关键帧，这样编程简单但是效果不好，比如运动很慢的时候，就会有大量相似的关键帧，运动快又会丢失很多。  
（2）距离最近关键帧的距离是否足够远  
（3）跟踪质量（根据跟踪过程中搜索到的点数和共视特征点的比例）一方面，关键帧自身质量要好，例如不能是非常模糊的图像、特征点数量要充足、特征点分布要尽量均匀等等；另一方面，关键帧与其他关键帧之间的关系，需要和局部地图中的其他关键帧有少量的共视关系，但大部分特征点是新特征点，以达到既存在约束，又尽量少的信息冗余的效果，例如局部地图点投影到此帧的点数低于一个阈值或前一个关键帧的特征点在此帧里已经有90%观测不到等等。

## 18 什么是极线约束？这个约束能带来什么好处？ ##

能够自己画出上面图片

极线约束的好处：从上面的描述我们可以看到，我们在做特征点匹配时，左图成像点p1的待匹配点p2一定在相对于p1的极线上，那么我们在做搜索时就可以在极线附近（考虑实际可能 会有一点误差）进行搜索，相对暴力匹配极大减少待匹配的点的数量。

## 19 什么是边缘化？ First Estimate Jacobian？ 一致性？ 可观性？ ##

## 20 如何对匹配好的点做进一步的处理，更好保证匹配效果 ##

（1）确定匹配最大距离，汉明距离小于最小距离的两倍

（2）使用KNN-matching算法，令K=2。则每个match得到两个最接近的descriptor，然后计算最接近距离和次接近距离之间的比值，当比值大于既定值时，才作为最终match。

（3）RANSAC（使用RANSAC找到最佳单应性矩阵。由于这个函数使用的特征点同时包含正确和错误匹配点，因此计算的单应性矩阵依赖于二次投影的准确性）

21 单目相机，F和H矩阵有何不同，E和F矩阵有何不同，只旋转不平移能不能求F，只旋转不平移能不能求H  
在相机只有旋转而没有平移的情况，此时t为0，E也将为0，导致无法求解R，这时可以使用单应矩阵H求旋转，但仅有旋转，无法三角化求深度。

## 22 描述BA ##

BA的本质是一个优化模型，其目的是最小化重投影/光度误差，用于优化相机位姿和世界点。局部BA用于优化局部的相机位姿，提高跟踪的精确度；全局BA用于全局过程中的相机位姿，使相机经过长时间、长距离的移动之后，相机位姿还比较准确。BA是一个图优化模型，一般选择LM(Levenberg-Marquardt)算法并在此基础上利用BA模型的稀疏性进行计算；可以直接计算，也可以使用g2o或者Ceres等优化库进行计算。

Bundle Adjustment : 从视觉重建中提炼出最优的3D模型和相机参数（内参和外参），好似每一个特征点都会反射几束光线，当把相机位姿和特征点位置做出最优的调整后，这些光线都收束到相机相机光心。也就是根据相机的投影模型构造构造代价函数，利用非线性优化（比如高斯牛顿或列文伯格马夸而尔特）来求最优解，利用雅克比矩阵的稀疏性解增量方程，得到相机位姿和特征点3D位置的最优解。

BA可以分为基于滤波器的BA和基于迭代的BA

## 23 描述PnP ##

Perspective-n-Points, PnP(P3P)提供了一种解决方案，它是一种由3D-2D的位姿求解方式，即需要已知匹配的3D点和图像2D点。目前遇到的场景主要有两个，其一是求解相机相对于某2维图像/3维物体的位姿；其二就是SLAM算法中估计相机位姿时通常需要PnP给出相机初始位姿。

在场景1中，我们通常输入的是物体在世界坐标系下的3D点以及这些3D点在图像上投影的2D点，因此求得的是相机坐标系相对于世界坐标系(Twc)的位姿

在场景2中，通常输入的是上一帧中的3D点（在上一帧的相机坐标系下表示的点）和这些3D点在当前帧中的投影得到的2D点，所以它求得的是当前帧相对于上一帧的位姿变换，如图所示：

两种情况本质上是相同的，都是基于已知3D点和对应的图像2D点求解相机运动的过程。

## 24 为什么要引入李群李代数 ##

旋转矩阵自身是带有约束的，正交且行列式为1，他们作为优化变量时，会引入额外的约束，时优化变的困难，通过李群李代数的转换关系，把位姿估计变成无约束的优化问题。

## 25 单目视觉slam中尺寸漂移是怎么产生的 ##

单目相机根据一张图片无法得出一张图片中物体的实际大小，同理也就无法得出运动的尺度大小，这是产生尺度漂移的根源。而在优化过程中，单目相机使用对极几何中的三角测量原理，而三角测量中，极小的角度误差在累积之后深度不确定都会变得很大，从而无法保证尺度一致性。

## 26 SLAM中的绑架问题 ##

绑架问题就是重定位，是指机器人在缺少之前位置信息的情况下，如何去确定当前位姿。例如当机器人被安置在一个已经构建好地图的环境中，但是并不知道它在地图中的相对位置，或者在移动过程中，由于传感器的暂时性功能故障或相机的快速移动，都导致机器人先前的位置信息的丢失，在这种情况下如何重新确定自己的位置。

## 27 KF和BA的区别 ##

（1） EKF假设了马尔科夫性，认为k时刻的状态只与k-1时刻有关。非线性优化使用所有的历史数据，做全体的SLAM

（2） EKF做了线性化处理，在工作点处用一阶泰勒展开式近似整个函数，但在工作点较远处不一定成立。非线性优化每迭代一次，状态估计发生改变，我们会重新对新的估计点做 泰勒展开,可以把EKF看做只有一次迭代的BA

## 28 常用的边缘检测算子和优缺点 ##

边缘检测一般分为三步，分别是滤波、增强、检测。基本原理都是用高斯滤波器进行去噪，之后在用卷积内核寻找像素梯度。常用有三种算法：canny算子，sobel算子，laplacian算子

canny算子：一种完善的边缘检测算法，抗噪能力强，用高斯滤波平滑图像，用一阶偏导的有限差分计算梯度的幅值和方向，对梯度幅值进行非极大值抑制，采用双阈值检测和连接边缘。

sobel算子：一阶导数算子，引入局部平均运算，对噪声具有平滑作用，抗噪声能力强，计算量较大，但定位精度不高，得到的边缘比较粗，适用于精度要求不高的场合。

laplacian算子：二阶微分算子，具有旋转不变性，容易受噪声影响，不能检测边缘的方向，一般不直接用于检测边缘，而是判断明暗变化。

## 29 为什么SLAM中常用L-M？ ##

G-N中的H矩阵可能为奇异矩阵或者病态矩阵，导致算法不收敛。而且当步长较大时，也无法保证收敛性，所以采用L-M求解增量方程，但是它的收敛速度可能较慢。

## 30 10个相机同时看到100个路标点，问BA优化的雅克比矩阵多少维，Heissian矩阵多少维 ##

Jacob矩阵是 2000×360  
因为误差对相机姿态的偏导数的维度是2×6,对路标点的偏导数是2×3，又10个相机可以同时看到100个路标点，所以一共有10×100×2行，100×3+10×6个块。

Hession是360×360

## 31 GridMap给定起点和终点，求最优路径 ##

## 32 描述PnP算法 ##

目前一共有两种解法，直接线性变换方法（一对点能够构造两个线性约束，因此12个自由度一共需要6对匹配点），另外一种就是非线性优化的方法，假设空间坐标点准确，根据最小重投影误差优化相机位姿。  
目前有两个主要场景场景，其一是求解相机相对于某2维图像/3维物体的位姿；其二就是SLAM算法中估计相机位姿时通常需要PnP给出相机初始位姿。  
在场景1中，我们通常输入的是物体在世界坐标系下的3D点以及这些3D点在图像上投影的2D点，因此求得的是相机坐标系相对于世界坐标系(Twc)的位姿  
在场景2中，通常输入的是上一帧中的3D点（在上一帧的相机坐标系下表示的点）和这些3D点在当前帧中的投影得到的2D点，所以它求得的是当前帧相对于上一帧的位姿变换.

## 33 方差，期望，协方差概念 ##

方差：描述了随机变量的离散程度  
方差性质：  
 D ( X ) = E \[ ( x − E \[ x \] ) 2 ) \] D(X)=E\[(x-E\[x\])^2)\] D(X)=E\[(x−E\[x\])2)\]， D ( X ) = E ( X 2 ) − E ( x ) 2 D(X) =E(X^2)-E(x)^2 D(X)=E(X2)−E(x)2  
如果X和Y相互独立，则  
D(X+Y) =D(X)+D(Y)  
 D ( a X + b ) = a 2 D ( X ) D(aX+b)=a^2D(X) D(aX\+b)=a2D(X)

## 34 VINS-mono 系统需要优化的变量 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 1]  
vio中关心的量主要有滑动窗口中每一帧的平移p，旋转q，速度v，以及 b a , b g b\_a,b\_g ba,bg（15个量，四元数更新是用的三维增量 δ q \\delta q δq），逆深度 λ m \\lambda\_m λm

## vinsmono系统中的残差构建，协方差传递及其对应的雅克比矩阵推算 ##

！！！！非常重要！！！！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 2]  
多传感器融合的BA关键流程可以总结如下三步：（1）构建残差的状态方程;（2）构建协方差的传递方程;（目标函数中使用的是残差的马氏距离，在ceres优化中还会对协方差矩阵进行LLT分解，相当于对残差的加权，其中方差大的残差的权重就会很小，表示对该数据的信赖程度低）（3）求解残差的Jacobian矩阵（用于高斯牛顿法的迭代）

！！！！非常重要！！！！

*  基于逆深度的视觉重投影残差，雅克比  
    vio中基于逆深度的重投影误差：特征点逆深度在第 i i i帧中初始化得到，在第 j j j帧中又被观测到，预测其在第 j j j帧中的坐标。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 3]  
    从第i帧的camera的点到第i帧body到world到第j帧body到第j帧camera中变换
 *  IMU预积分的残差，协方差，雅克比  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 4]

预积分误差如下所示，将一段时间内 I M U IMU IMU构建的预积分量作为测量值，对两时刻之间的状态量进行约束。

其中位移，速度，偏置都是直接相减得到。第二项是关于四元数的旋转误差，其中 \[ . \] x y z \[.\]\_\{xyz\} \[.\]xyz表示只取四元数的虚部组成的三维向量。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 5]  
假设已知了相邻时刻误差的线性传递方程：  
 n i k = F k − 1 θ i k − 1 + G k − 1 n k − 1 n\_\{ik\}=F\_\{k-1\} \\theta\_\{ik-1\}+G\_\{k-1\}n\_\{k-1\} nik=Fk−1θik−1\+Gk−1nk−1  
状态量误差 θ i k \\theta\_\{ik\} θik为旋转，位移，速度的误差，测量噪声 n k n\_k nk为加速度计和陀螺仪的噪声。  
误差的传递由两部分组成：当前时刻的误差传递给下一时刻，当前时刻测量噪声传递给下一个时刻。

协方差矩阵可以通过递推计算得到：

Σ i k = F k − 1 Σ i k − 1 F k − 1 T + G k − 1 Σ n G k − 1 T \\Sigma\_\{ik\}=F\_\{k-1\}\\Sigma\_\{ik-1\}F^T\_\{k-1\}+G\_\{k-1\}\\Sigma\_nG^T\_\{k-1\} Σik=Fk−1Σik−1Fk−1T\+Gk−1ΣnGk−1T

其中 Σ n \\Sigma\_n Σn是测量噪声的协方差矩阵，方差从i时刻开始进行递推， Σ i i \\Sigma\_\{ii\} Σii=0.  
满足上面的协方差传递公式的前提是系统的状态传递为线性系统，因此需要对IMU的预积分做线性化，对于状态量之间的递推关系是非线性方程，可以用两种方法来推导状态误差的线性递推关系：基于一阶泰勒展开的误差传递方程，一种是基于误差随时间变化的递推方程（导数关系）。  
我们采用一阶泰勒展开的方法进行误差推导：  
对于非线性系统 x k = f ( x k − 1 , u k − 1 ) x\_k=f(x\_\{k-1\},u\_\{k-1\}) xk=f(xk−1,uk−1)的状态误差的线性递推关系如下：  
 δ x k = F δ x k − 1 + G n k − 1 \\delta x\_k=F\\delta x\_\{k-1\}+G n\_\{k-1\} δxk=Fδxk−1\+Gnk−1  
F是状态量 x k x\_k xk对状态量 x k − 1 x\_\{k-1\} xk−1的雅克比矩阵，G是状态量 x k x\_k xk对输入量 u k − 1 u\_\{k-1\} uk−1的雅克比矩阵。

下图是 x k = f ( x k − 1 , u k − 1 ) x\_k=f(x\_\{k-1\},u\_\{k-1\}) xk=f(xk−1,uk−1)的具体表达形式：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 6]  
用前面一阶泰勒展开的推导方式,我们希望能推导出如下的形式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 7]  
F, G 为两个时刻间的协方差传递矩阵。这个推导是一个很繁杂的过程，此处省略。

整个系统的残差对状态量求导的雅克比

## vio中为什么需要进行预积分 ##

根据IMU的运动学方程可以对IMU进行积分得到第 i i i第 j j j时刻的位移，角度，速度变化关系。

下面是对IMU的直接积分计算得到

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 8]  
我们可以根据每一个时刻的IMU测量值递推出IMU状态的变化，但是我们后面还会对中间IMU的状态量去进行迭代优化。

问题：在每次对 q w b t q\_\{wb\_t\} qwbt优化更新后，都需要重新进行积分更新后面的PVQ，运算量很大。

解决办法：采用预积分，将PVQ积分公式中的积分项变成相对于第 i i i时刻的姿态，而不是相对于世界坐标系的姿态。相对的PVQ仅和第i时刻的姿态和 i i i到 j j j时刻的姿态有关系，和 i i i时刻前面的状态无关（世界坐标系下的变化改为相对于上一时刻坐标系的变化，将绝对变化改为了相对变化的思想（个人理解））

# 算法数据结构 C++ #

## 1 ORB-SLAM的共视图是什么结构 ##

## 2 写一个四叉树结构 ##

## 3 不用递归遍历二叉树 ##

## 4 多线程的实现方式 ##

## 5 求最大联通域 ##

## 6 Mat是如何构造的 ##

## 7 重建二叉树 ##

## 8 实现一个稀疏矩阵的数据结构，并实现稀疏矩阵的加法 ##

## 9 写快速排序，写反转链表 ##

## 10 从数组中找出第K小的数字 ##

## 11 说一下什么是虚函数和纯虚函数，虚表，抽象类 ##

*  抽象类（虚基类）和普通类区别  
    抽象类只能作为基类，提供接口，不能有实例。  
    普通类既可以作为基类，又可以有实例。
 *  虚函数和纯虚函数定义的区别

// 虚函数定义
    class Person
    { 
    public:
    	virtual void BuyTicket()
    	{ 
    		cout<<"Price:全票"<<endl;
    	}
    };
     
    class Student
    { 
    public:
    	virtual void BuyTicket()
    	{ 
    		cout<<"Price:半票"<<endl;
    	}
    };
    
     
    // 纯虚函数定义：在虚函数后面赋值0；
    class A
    { 
       virtual void func() = 0; // 纯虚函数
    protected :
       string _a ;
    };
    class B : public A
    { };

*  虚函数需要实现，纯虚函数不需要实现  
    类里如果声明了虚函数，这个函数是实现的，哪怕是空实现，它的作用就是为了能让这个函数在它的子类里面可以被覆盖，这样编译器就可以使用后期绑定来达到多态了。纯虚函数只是一个接口，是个函数的声明而已，它要留到子类里去实现。（纯虚函数是接口，不能定义实现，需要到子类里面实现； 虚函数是必须要实现，后面在子类里面会被覆盖）
 *  虚函数在子类里面也可以不重载的；但纯虚函数必须在子类去实现，这就像 Java 的接口一样。通常把很多函数加上 virtual，是一个好的习惯，虽然牺牲了一些性能，但是增加了面向对象的多态性，因为很难预料到父类里面的这个函数不在子类里面不去修改它的实现。
 *  虚函数的类用于“实作继承”，继承接口的同时也继承了父类的实现。当然大家也可以完成自己的实现。纯虚函数关注的是接口的统一性，实现由子类完成。
 *  带纯虚函数的类叫虚基类，这种基类不能直接生成对象，而只有被继承，并重写其虚函数后，才能使用。这样的类也叫抽象类。抽象类和大家口头常说的虚基类还是有区别的，在 C\# 中用 abstract 定义抽象类，而在 C++ 中有抽象类的概念，但是没有这个关键字。抽象类被继承后，子类可以继续是抽象类，也可以是普通类，而虚基类，是含有纯虚函数的类，它如果被继承，那么子类就必须实现虚基类里面的所有纯虚函数，其子类不能是抽象类。

## 12 说一下智能指针，shared\_ptr与unique\_ptr ##

## 13 C++如何实现多态 ##

## 14 给一个2D平面的两个线段，判断两个线段是否相交 ##

## 多线程了解 ##

## 二叉树排序，堆排序，希尔排序，桶排序时间复杂度 ##

## 最长公共子串，最长公共子序列 ##

## 三维空间最近邻搜索常用的数据结构（八叉树，kd树） ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/7cbb85aed2774f3d8aeff09c7a98caf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/84619c436d7b40fb81bba0a8f5557f3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/a70ae6164d8448d7ae234e00e4411bfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/9176787de06d4cbaa5977e332f4e1473.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/4e00a53e81f9442ab69ca713935aebc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/510bf25804cb431aa5536f9ef29052d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/cc83be02ec094b55a0bd6597c209ffae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/964d936bbf714123aadfea0734142f35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8176fc30ac854518bd6b9f8f3dc0b32b.png