[C++知识库]c++面试总结

1.递归

递归的时间复杂度 =?递归的次数 * 每次递归中的操作次数

求 x 的 n 次方

int f(int x, int n) {
    if (n == 0) {
        return 1; //0次方是等于1
    }
    return f(x, n - 1) * x;
}

时间复杂度 O(n) x 1 = O(n)

提高：

int f(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return f(x, n / 2) * f(x, n / 2)*x;
    }
    return f(x, n / 2) * f(x, n / 2);
}

递归的次数是满二叉树节点的数量 n-1，所以时间复杂度还是O(n)
因为f(x, n / 2) * f(x, n / 2) 这里乘法的时候计算了两次

int f(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = f(x, n / 2);
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

递归的次数是二叉树的深度 log2n - 1
所以时间复杂度是O(logn)

2.四大类型转换

• dynamic_cast?用于多态类型的转换
• static_cast?用于非多态类型的转换
• const_cast?用于删除const ,volatile 和 __unaligned 属性
• reinterpret_cast?用于位的简单重新解释

/将expression转换为type类型.
dynamic_cast<type>(expression);

(1) const_cast
用于将const变量转为非const

(2) static_cast
用于各种隐式转换，比如非const转const，void*转指针等, static_cast能用于多态向上转化，如果向下转能成功但是不安全，结果未知；

(3) dynamic_cast
用于动态类型转换。只能用于含有虚函数的类，用于类层次间的向上和向下转化。只能转指针或引用。向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。要深入了解内部转换的原理。

向上转换：指的是子类向基类的转换

向下转换：指的是基类向子类的转换

它通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否相同来判断是否能够进行向下转换。

(4) reinterpret_cast
几乎什么都可以转，比如将int转指针，可能会出问题，尽量少用；

3.大端和小端

大端（Big-endian）模式，是指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中

小端（Little-endian）模式，是指数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中

4.二进制求和

class Solution {
public:
    string addBinary(string a, string b) {
        int al = a.size();
        int bl = b.size();
        while(al < bl) //让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引
        {
            a = '0' + a;
            ++ al;
        }
        while(al > bl)
        {
            b = '0' + b;
            ++ bl;
        }
        for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数，同位相加
        {
            a[j] = a[j] - '0' + b[j];
            if(a[j] >=  '2') //若大于等于字符‘2’，需要进一
            {
                a[j] = (a[j] - '0') % 2 + '0';
                a[j-1] = a[j-1] + 1;
            }
        }
        a[0] = a[0] - '0' + b[0]; //将ab的第0位相加
        if(a[0] >= '2') //若大于等于2，需要进一
        {
            a[0] = (a[0] - '0') % 2 + '0';
            a = '1' + a;
        }
        return a;
    }
};

5.构造函数

构造方法没有返回类型，也不能定义为void，在方法名前面不声明方法类型；构造函数可以是私有的

6.虚函数和纯虚函数的区别

需要在基类中定义虚函数，纯虚函数在基类中是没有定义的，必须在子类中加以实现。

纯虚函数相当于接口，不能直接实例话，需要派生类来实现函数定义。

虚函数在子类里面也可以不重载的；但纯虚必须在子类去实现，

7.十进制变成二进制并统计其中1的数量

int count = 0;

while(n != 0)
{
    if(n % 2 == 1)
    {
        count++;
    }
    
    n = n >> 1;   //除以2
}

8.单例模式

定义：保证一个类仅有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。

那么我们就必须保证：

（1）该类不能被复制。

（2）该类不能被公开的创造。

那么对于C++来说，它的构造函数，拷贝构造函数和赋值函数都不能被公开调用。

?优点：

?????实现简单，多线程安全。

????缺点：

????????a. 如果存在多个单例对象且这几个单例对象相互依赖，可能会出现程序崩溃的危险。原因:对编译器来说，静态成员变量的初始化顺序和析构顺序是一个未定义的行为;具体分析在懒汉模式中也讲到了。

????????b. 在程序开始时，就创建类的实例，如果Singleton对象产生很昂贵，而本身有很少使用，这种方式单从资源利用效率的角度来讲，比懒汉式单例类稍差些。但从反应时间角度来讲，则比懒汉式单例类稍好些。

9.工厂模式

定义一个创建对象的接口，让子类决定实例化哪个类，而对象的创建统一交由工厂去生产，有良好的封装性，既做到了解耦，也保证了最少知识原则。

工厂设计模式分类

工厂模式属于创建型模式，大致可以分为三类，简单工厂模式、工厂方法模式、抽象工厂模式。
?

10.TCP：

TCP( Transmission control protocol )即传输控制协议，是一种面向连接、可靠的数据传输协议，它是为了在不可靠的互联网上提供可靠的端到端字节流而专门设计的一个传输协议。

面向连接：数据传输之前客户端和服务器端必须建立连接
可靠的：数据传输是有序的 要对数据进行校验
?

TCP三次握手

所谓三次握手(Three-way Handshake)，是指建立一个TCP连接时，需要客户端和服务器总共发送3个包。

三次握手的目的是连接服务器指定端口，建立TCP连接,并同步连接双方的序列号和确认号并交换 TCP 窗口大小信息.在socket编程中，客户端执行connect()时。将触发三次握手。

• 第一次握手： 客户端向服务器端发送报文
  证明客户端的发送能力正常
• 第二次握手：服务器端接收到报文并向客户端发送报文
  证明服务器端的接收能力、发送能力正常
• 第三次握手：客户端向服务器发送报文
  证明客户端的接收能力正常

TCP四次挥手

终止TCP连接，就是指断开一个TCP连接时，需要客户端和服务端相互总共发送4个包以确认连接的断开

建立TCP连接需要三次握手，终止TCP连接需要四次挥手

11.多线程

定义

线程是CPU使用的基本单元，线程有四种状态：新生状态、可运行状态、被阻塞状态、死亡状态。

线程与进程的区别？

1、 线程是进程的一部分，所以线程有的时候被称为是轻权进程或者轻量级进程。
2、 一个没有线程的进程是可以被看作单线程的，如果一个进程内拥有多个进程，进程的执行过程不是一条线（线程）的，而是多条线（线程）共同完成的。
3、 系统在运行的时候会为每个进程分配不同的内存区域，但是不会为线程分配内存（线程所使用的资源是它所属的进程的资源），线程组只能共享资源。那就是说，出了CPU之外（线程在运行的时候要占用CPU资源），计算机内部的软硬件资源的分配与线程无关，线程只能共享它所属进程的资源。
4、 与进程的控制表PCB相似，线程也有自己的控制表TCB，但是TCB中所保存的线程状态比PCB表中少多了。
5、 进程是系统所有资源分配时候的一个基本单位，拥有一个完整的虚拟空间地址，并不依赖线程而独立存在。

进程间通信的方式：

进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。

12.数据库索引

索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。

13.七层模型

包含的协议如下:

物理层: 通过媒介传输比特,确定机械及电气规范,传输单位为bit，主要包括的协议为：IEE802.3 CLOCK RJ45

数据链路层: 将比特组装成帧和点到点的传递,传输单位为帧,主要包括的协议为MAC VLAN PPP

网络层：负责数据包从源到宿的传递和网际互连，传输单位为包,主要包括的协议为IP ARP ICMP

传输层：提供端到端的可靠报文传递和错误恢复，传输单位为报文,主要包括的协议为TCP UDP

会话层：建立、管理和终止会话，传输单位为SPDU，主要包括的协议为RPC NFS

表示层: 对数据进行翻译、加密和压缩,传输单位为PPDU，主要包括的协议为JPEG ASII

应用层: 允许访问OSI环境的手段,传输单位为APDU，主要包括的协议为FTP HTTP DNS
?