c++基础
1.深拷贝与浅拷贝
浅拷贝是指源对象与拷贝对象共用一份实体，仅仅是引用的变量不同（名称不同）。对其中任何一个对象的改动都会影响另外一个对象。
浅拷贝在类里面有指针成员的情况下只会复制指针的地址，会导致两个成员指针指向同一块内存，这样在要是分别delete释放时就会出现问题，因此需要用深拷贝。
2.基类析构函数为什么要声明为虚函数？
C++中基类采用virtual虚析构函数是为了防止内存泄漏。具体地说，如果派生类中申请了内存空间，并在其析构函数中对这些内存空间进行释放。假设基类中采用的是非虚析构函数，当删除基类指针指向的派生类对象时就不会触发动态绑定，因而只会调用基类的析构函数，而不会调用派生类的析构函数。那么在这种情况下，派生类中申请的空间就得不到释放从而产生内存泄漏。所以，为了防止这种情况的发生，C++中基类的析构函数应采用virtual虚析构函数。 链接标题
##3.c++内存模型
- 堆
- 栈
- 静态存储区 存放虚函数，局部/全局静态变量，全局常量指针
- 常量存储区
- 代码区
4.new和malloc的区别
操作系统
1.信号和信号量的区别
信号是通知进程产生了某个事件，信号量是用来同步进程的（用来调协进程对共享资源的访问的）
2.物理地址空间和虚拟地址空间怎么转换
内存管理单元（MMU，属于硬件）管理着地址空间和物理内存的转换，操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，叫页表，存储着程序地址空间到物理内存空间的映射表。
页表寻址
- 一个虚拟地址分为两部分，一部分存储页面号，一部分存储偏移量
- 页表分为序号、页基地址、标志位
- 访问虚拟地址，先通过页表查询页面号，查看标志位确认虚拟地址是否在物理内存中有缓存，然后由逻辑地址的高位部分先找到逻辑地址对应的页基地址，再由页基地址偏移虚拟地址中的偏移量就得到最后的物理地址
- 一般情况下，这个过程都可以由硬件完成，所以效率还是比较高的。页式内存管理的优点就是比较灵活，内存管理以较小的页为单位，方便内存换入换出和扩充地址空间。
3.线程池的作用
第一：降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。
第二：提高响应速度。当任务到达时，任务可以不需要等到线程创建就能执行。
第三：提高线程的可管理性，线程是稀缺资源，如果无限制地创建，不仅会消耗系统资源，还会降低系统的稳定性，使用线程池可以进行统一分配、调优和监控。
4.互斥锁的实现原理
互斥锁是一个二元变量，其状态为开锁(允许0)和上锁(禁止1)，将某个共享资源与某个特定互斥锁在逻辑上绑定(要申请该资源必须先获取锁)。
访问公共资源前，必须申请该互斥锁，若处于开锁状态，则申请到锁对象，并立即占有该锁，以防止其他线程访问该资源；如果该互斥锁处于锁定状态，则阻塞当前线程。
只有锁定该互斥锁的进程才能释放该互斥锁，其他线程试图释放无效。
5.死锁
死锁有哪些处理方法？
<details> <summary>鸵鸟策略</summary>直接忽略死锁。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。
</details> <details> <summary>死锁预防</summary>基本思想是破坏形成死锁的四个必要条件：
- 破坏互斥条件：允许某些资源同时被多个进程访问。但是有些资源本身并不具有这种属性，因此这种方案实用性有限；
- 破坏占有并等待条件：
- 实行资源预先分配策略（当一个进程开始运行之前，必须一次性向系统申请它所需要的全部资源，否则不运行）；
- 或者只允许进程在没有占用资源的时候才能申请资源（申请资源前先释放占有的资源）；
- 缺点：很多时候无法预知一个进程所需的全部资源；同时，会降低资源利用率，降低系统的并发性；
- 破坏非抢占条件：允许进程强行抢占被其它进程占有的资源。会降低系统性能；
- 破坏循环等待条件：对所有资源统一编号，所有进程对资源的请求必须按照序号递增的顺序提出，即只有占有了编号较小的资源才能申请编号较大的资源。这样避免了占有大号资源的进程去申请小号资源。
动态地检测资源分配状态，以确保系统处于安全状态，只有处于安全状态时才会进行资源的分配。所谓安全状态是指：即使所有进程突然请求需要的所有资源，也能存在某种对进程的资源分配顺序，使得每一个进程运行完毕。
</details> <details> <summary>死锁解除</summary>银行家算法
如何检测死锁：检测有向图是否存在环；或者使用类似死锁避免的检测算法。
死锁解除的方法：
- 利用抢占：挂起某些进程，并抢占它的资源。但应防止某些进程被长时间挂起而处于饥饿状态；
- 利用回滚：让某些进程回退到足以解除死锁的地步，进程回退时自愿释放资源。要求系统保持进程的历史信息，设置还原点；
- 利用杀死进程：强制杀死某些进程直到死锁解除为止，可以按照优先级进行。
6.多线程的使用场景
1.一个业务逻辑有很多次的循环，每次循环之间没有影响，比如验证1万条url路径是否存在，正常情况要循环1万次，逐个去验证每一条URL，这样效率会很低，假设验证一条需要1分钟，总共就需要1万分钟，有点恐怖。这时可以用多线程，将1万条URL分成50等份，开50个线程，没个线程只需验证200条，这样所有的线程执行完是远小于1万分钟的。
2.需要知道一个任务的执行进度，比如我们常看到的进度条，实现方式可以是在任务中加入一个整型属性变量(这样不同方法可以共享)，任务执行一定程度就给变量值加1，另外开一个线程按时间间隔不断去访问这个变量，并反馈给用户。总之使用多线程就是为了充分利用cpu的资源，提高程序执行效率，当你发现一个业务逻辑执行效率特别低，耗时特别长，就可以考虑使用多线程。
##7.慢开始与拥塞避免
#算法
##1.排序算法
- 当N很大时，并且有序程度高时，快速排序最快
- 当N很大时，并且有序程度低时，堆排序最快
不稳定的排序算法：快排、堆排序、选择排序
稳定的排序算法：冒泡排序、归并排序、插入排序
2.位运算
技巧
对于N为2的幂的数，都有 N&(N-1)=0
输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数
int result = 0;
5 //初始化掩码为1
6 int mask = 1;
7 for (int i = 0; i < 32; i++) {
8 if ((n & mask) != 0) {
9 result++;
10 }
11 mask = mask << 1;
12 }
13 return result;3.TF-IDF算法
TF-IDF（term frequency–inverse document frequency，词频-逆向文件频率）是一种用于信息检索（information retrieval）与文本挖掘（text mining）的常用加权技术。
TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
TF-IDF的主要思想是：如果某个单词在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。
并没有考虑词语的语义信息，无法处理一词多义与一义多词的情况。
应用： 1）搜索引擎；（2）关键词提取；（3）文本相似性；（4）文本摘要
#数据结构
##1.完全二叉树和满二叉树有什么区别
满二叉树：从形象上来说满二叉树是一个绝对的三角形，也就是说它的最后一层全部是叶子节点，其余各层全部是非叶子节点
完全二叉树：从形式上来说他是一个可能有缺失的三角形，但所缺部分肯定是右下角的某个连续部分。
2.二叉树的性质
- 非空二叉树第 i 层最多 2^(i-1) 个结点 （i >= 1）
- 深度为 k 的二叉树最多 2^k - 1 个结点 （k >= 1）
3.b树和b+树的区别
b+树相比于b树的查询优势：
- b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
- b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
- 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历
4.平衡二叉树
左旋：将当前结点S的左孩子旋转为当前结点父结点E的右孩子，同时将父结点E旋转为当前结点S的左孩子。
右旋：将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子，同时将当前结点S旋转为左孩子E的右孩子。
京公网安备 11010502036488号