C++面试知识点汇总

逃离我推掉我的手 2022-09-02 14:45 203阅读 0赞

> 暂时存个档,可能有不足之处，欢迎指正。

# C++ 基础 #

*  new ,delete,new\[\],delete\[\],malloc,free之间的区别？
    
     *  new，delete与new\[\],delete\[\]区别在于前者管理的是单个元素空间，后者管理的是多个元素的连续空间；
     *  …pass
 *  什么是内存泄漏，如何避免？如何检测？
    
     *  定义：内存泄漏是由于疏忽或错误程序**未能释放 不再使用的内存**的情况。
     *  内存泄漏场景：
        
        1.  指针重新赋值时，忘记释放之前管理的内存；
        2.  结构化对象成员中有动态分配内存块，而却先释放了父块，导致丢失了子块控制权；
        3.  返回的是堆区域内存的指针，但是使用后没有正确处理返回的指针；
     *  避免：
        
        1.  尽量避免在堆上分配内存；
        2.  善于利用RAII机制;
        3.  尽量不要使用裸指针，而是使用智能指针；
        4.  尽量使用STL容器替代，比如用`string`代替`char*`,`vector`代替`int*`等；
     *  检测：
        
        1.  对象计数，构造++，析构–，看最终计数是否为0；
        
        2.使用检测库或检测工具，库：比如win:`crtdbg`,linux:`mcheck`,工具：比如`gperftools`;
 *  win32 一个进程最多可以开几个线程，开多了会出现什么问题？
    
     *  `2^32=4GB`，win32最大可用虚拟空间为`2GB = 2^31`左右，一个线程要`1MB`栈空间
     *  `8bit=1byte,1kb = 1024byte=2^10*8bit,1MB = 1024kb=2^20*8bit,1GB = 1024MB`
     *  `1MB * 1024 * 2 = 2GB`,所以最多可以开**2048**个线程
     *  开多了会导致整个进程异常退出

void func(int* p){
        
    	p = new int(5);
    }
    int* a = NULL;
    func(a);
    printf("%d",*a); // 结果是什么？会出现段错误，指针也是一种类型，形，实都是一种类型，是值拷贝，函数执行后a依然是空指针

*  出现野指针有哪些情况，如何避免？
    
     *  野指针定义：指向非法内存地址的的指针，也叫悬挂指针；
     *  出现情况：
        
        1.  使用未初始化的指针；
        2.  指针指向对象已经消亡；
        3.  指针释放后未置空；
     *  避免：
        
        1.  尽量避免使用指针，比如用引用代替；
        2.  定义时就初始化，初始化为一个对象地址或者`nullptr`;
        3.  对指针进行`delete` 或`free`后，将其赋值为`nullptr`;
 *  指针相关：
    
     *  `int(*p)[n]`:（）优先级高，所以p是一个指针，指向int\[n\]的指针，也称**行指针**；  
        行指针++就跨一行
     *  `int* p[n]`:指针数组，含有n个指针元素，常用来指向二维数组，  
        `p[i][j] = *(p[i]+j)=*(*(p+i)+j)=*(p+i)[j]`
 *  c++ lambda表达式实现原理：
    
     *  根据`lambda`表达式返回值为一个函数对象可知其实现为：生成一个lambda\_xx 类，然后重载`operator()`
     *  具体步骤为：
        
        1.  创建 **lambda 类**，**实现构造函数**，使用 lambda 表达式的函数体重载 **operator()**（ lambda 表达式 也叫匿名函数对象）
        2.  创建 lambda 对象
        3.  通过对象调用 **operator()**
 *  编译器如何区分重载函数的?
    
    编译成了不同的函数名，查看\*\*生成的汇编代码(g++ -S xx.s xx.cpp )\*\*发现，
    
    大概规则举例：`print(int x)->_xxprinti,print(int x,int y)->__xprintii`
 *  C++ 的多态机制？
    
     *  静态多态：函数重载，**泛型编程（函数模板和类模板）**；
     *  动态多态：虚函数
 *  什么是**仿函数**？
    
     *  **通过重载operator()运算符使得class或struct对象可以像函数一样调用**，比如c++提供的`less`,`greater`等;
     *  函数指针虽然也可以将函数作为参数传递，但是不能满足STL抽象性和积木性（和STL其他组件搭配）要求。
     *  调用方式：`class_name()(args)` or `class_obj.operator()(args)`
 *  如果new的东西，用free释放会怎么样？free后再调用delete会怎么样？
    
     *  如果new对象里面没有再动态分配资源，则直接free也可以，不会有**资源**泄漏；
        
        否则会存在资源泄漏，因为对象回收资源的的析构函数没有被调用；
     *  free之后再调用delete会free两次，程序直接Aborted;
 *  自己实现一个String类
    
        class String{
              
        	public:
        		String(const char* str=nullptr){
              
        			m_size = str ? std::strlen(str) : 0;
        			m_data = new char[m_size+1];
        			if(m_size) std::strncpy(m_data,str,m_size);
        			m_data[m_size] = '\0'; // 得分
        		}
        
        		String(const String& s){
              
        			size_t len  = s.size();
        			this->m_data = new char[len+1];
        			std::strncpy(this->m_data,s.m_data,len);
        			m_size = len;
        			this->m_data[m_size] = '\0';
        		}
        
        		String& operator= (const String& s){
              
        			if(this == &s) return *this; // 得分
        			this->m_size = s.size();
        			delete[] m_data; // 得分
        			this->m_data = new char[this->m_size];
        			std::strncpy(this->m_data,s.m_data,m_size);
        			this->m_data[m_size] = '\0';
        			return *this;
        		}
        
        		String& operator+ (const String& s){
              
        			int len = s.size();
        			char* q = new char[this->m_size+len];
        			std::strncpy(q,m_data,m_size);
        			std::strncpy(q+m_size,s.m_data,len);
        			this->m_size += len;
        			q[m_size] = '\0';
        			delete[] m_data; // 得分
        			m_data = q;
        			return *this;
        		}
           
        		friend std::ostream& operator<< (std::ostream& out,String& s){
              
        			for(char* q = s.m_data; *q!='\0'; ++q){
              
        				out<<(*q);
        			}
        			return out;
        		}
        		size_t size()const{
              
        			return m_size;
        		}
        		~String(){
              
        			delete[] m_data;
        		}
        
        	private:
        		char* m_data;
        		size_t m_size;
        };
 *  自己实现单例模式
    
        // 懒汉模式：需要用时再加载（创建）
        class Object{
              
            public:
                static Object* getInstance(){
              
                    if(nullptr == m_single){
               // 只有m_single为空才加锁，加锁开销很大，避免每次调用都加锁
                        std::unique_lock<std::mutex> lock(m_mutex);
                        if(nullptr == m_single){
              
                            m_single = new Object();
                        }
                        
                    }    
                    return m_single;
                }
            private:
            	Object(){
              }
            	Object(const Object& rhs) = delete; // 禁止拷贝构造
            	Object& operator=(const Object& rhs) = delete; // 禁止赋值构造
                static Object* m_single;
            	std::mutex m_mutex;
            
        };
        // 饿汉模式: 一开始就创建好实例
        class Object{
              
            public:
                static Object* getInstance(){
              
                    static Object m_single; // 一开始就创建好放到静态存储区，在c++11下线程安全
                    return &m_single;
                }
            private:
            	Object(){
              }
           		Object(const Object& rhs) = delete; // 禁止拷贝构造
            	Object& operator=(const Object& rhs) = delete; // 禁止赋值构造
        };
 *  单例模式下，如何保证多线程模式下只有一个对象实例？
    
     *  加锁
     *  提前生成，即使用饿汉模式
 *  char ch\[\] = “hello” 和char\* p = "hello"的区别，如果对两者字符进行修改会怎么样？
    
     *  char ch\[\]最后有一个字符串结束符‘\\0’
     *  `sizeof(ch) = strlen(ch)+1`而`sizeof(p) = 8 or 4`
     *  char ch\[\]中字符串可以修改不会出现问题，而对p指向的字符串修改可能会出现问题，
        
        ch存在栈区，p指向的字符串在常量区
 *  为什么要字节对齐？字节不对齐会出现什么问题？
    
     *  提高访问效率，不对齐读取数据时可能需要多访问内存几次
 *  为什么x64 下指针占8字节，x64的寻址空间？
    
     *  x64地址总线有64条，寻址空间2^64，指针作用是指向一个地址（寻址空间中找一个地址），64bit = 8Bytes,
 *  memset有虚函数的对象为0，会不会出现问题？
    
     *  会，虚表指针被置空，导致无法调用到虚函数
 *  简述mp\[1\] 和 iter = mp.find(1)的区别，map的key有什么要求？
    
     *  下标操作符\[\],1不在mp中时会插入，而find(1),1不在时不会插入，只返回mp.end();
        
        所以如果只是判断某个数是否在mp中时尽量使用find
     *  map的key需要:
        
         *  支持拷贝构造;
         *  支持`operator=`;
         *  可比较，即支持`operator<` (如果没有operator<那么 map模板必须增加第三个模板参数)；
         *  默认的构造函数。
 *  map插入，查找时间复杂度？为什么map底层采用红黑树而不用普通AVL？ 红黑树插入和删除最多需要几次旋转？
    
     *  logn
     *  map要做频繁插入，由于普通AVL严格的平衡，一次插入需要调整需要很多次，而红黑树一次插入最多需要调整2次；
     *  插：最多调整2次，删：最多调整3次；
 *  C++中死锁的危害很大，对避免死锁有什么建议？
    
     *  避免多次锁定：尽量避免同一线程对多个锁进行锁定；
     *  按相同的顺序加锁；
     *  使用定时锁（破坏持有并等待条件）；
     *  提前进行死锁检测（银行家算法）；
 *  class A\{…virtual… \}, class B :A\{…\},B的内存布局是怎么样的？
 *  虚函数有什么缺点？作为基类，其析构函数一定要声明为virtual?
    
     *  时间：调用需要通过虚表指针查虚表，时间上开销更大；
     *  空间：由于有虚函数，所以类对象会有虚表指针，要更多内存开销；
     *  安全：将基类强制转换为子类，不可以直接访问子类特有的虚函数，可通过虚表指针间接访问；
        
        不一定，如果不需要动态管理**资源**则基类析构可不声明为virtual
 *  虚函数和普通函数的区别?
    
     *  虚函数动态编译，运行期间进行绑定；而普通函数静态编译，在运行前就绑定好了（通过this指针进行绑定）。
 *  简述几种xx\_cast的作用。
    
     *  `reinterpret_cast`：重新解释二进制码，风险很高，比如不同类型指针之间的转换，int与指针的转换等；
     *  `const_cast`：const 转为非const,volitale 转为非volitale
        
        （volitale表明所修饰变量是易变的，不要作读取优化，每次都重新从内存中取）;
     *  `static_cast`：相当于传统C语言的强制转换，非多态的转换，编译时检查，
        
        但**运行时没有安全检查**，所以子类->父类绝对安全，而父类->子类是不安全的。
        
        不能转掉const,volitale,即不可将含这些关键字的转换为不含这些关键字的类型；
     *  `dynamic_cast`：主要用途将父类指针或引用安全的转换为子类指针或引用，它在运行期间借助RAII进行类型转换，
        
        强制转换指针不成功返回空指针，强制转换引用不成功抛出异常
 *  你了解服务器的哪些架构？
 *  引用是如何实现？何时使用引用？（引用和指针的区别）
    
     *  底层实现：可以根据使用场景进行推断，声明后必须初始化且之后不可修改为其他的引用，
        
        根据这个特性可以推断底层实现是**常指针（`type* const`）**,
        
        但**sizeof(引用)是所引用对象的大小（引用是对象的别名）**；
     *  应用： 函数传参，减少大数据结构的拷贝；为什么要有引用？很多场合可以代替指针，提高可读性和实用性；
 *  说说C++的多态
    
     *  静态多态：重载（形参类型，个数，和返回值类型没有关系），泛型编程（类模板，模板函数）
     *  动态多态：虚函数
 *  虚函数，一个类可以有多个虚函数表吗？
    
     *  可以，对于**多继承**可能存在多个虚函数表（多个虚表指针）
 *  说一下程序的编译成可执行文件的过程
    
     *  预处理（替换宏定义等），编译（高级语言转换为汇编代码）汇编（汇编码转换为机器码），链接
 *  C++ STL构成：
    
     *  容器
     *  迭代器
     *  适配器
     *  分配器
     *  算法
     *  函数对象（仿函数）
 *  你常用的stl容器，vector的扩容机制，清除里面的内容内存会释放吗？
    
     *  stl容器分为**顺序容器**：
        
         *  vector:扩容机制根据实现而异，通常为2倍/1.5倍。clear不会释放内存；
         *  deque,
         *  list(双向链表),
         *  forward\_list（单向链表）,
         *  array,
         *  string
     *  **关联容器**：
        
         *  map
         *  set
         *  multimap
         *  multiset
         *  unordered\_map
         *  unordered\_set
         *  unordered\_multimap
         *  unordered\_multiset
    
    stack属于容器适配器；
 *  map和unordered\_map的区别，以及它们的查询复杂度:
    
     *  map底层红黑树（比常规AVL更适合插入修改密集型任务）,查询时间复杂度O(NlogN)；
     *  unordered\_map底层采用hash,查询时间复杂度为常数复杂度
 *  虚函数和普通函数的区别：
    
     *  虚函数运行时多态，而普通函数是静态编译，没有运行时多态；

# 计算机网络 #

*  tcp如何保证可靠性？
    
     *  校验和：由tcp伪首部（12byte），tcp首部，tcp数据 三部分组成;
     *  序列号和确认应答;
     *  超时重传：时限略大于1个RTT(往返时间);
     *  流量控制：滑动窗口机制;
     *  拥塞控制：利用拥塞窗口以不加重网络负担：慢启动（之后指数增大），拥塞避免（之后线性增大），快重传，快恢复;
     *  连接管理：三次握手，四次挥手；
 *  简述tcp/ip模型，并说明各层常用的协议
    
    **osi七层**：
    
     *  应用层：
     *  表示层：
     *  会话层：
     *  传输层：
     *  网络层：
     *  数据链路层：
     *  物理层：
    
    **tcp/ip**:
    
     *  该模型意味着tcp和ip协同工作；
     *  tcp协议在传输层，负责应用软件和网络软件之间的通信；
     *  ip协议在网络层，负责计算机之间的通信；
    
    **tcp/ip模型4层：**
    
     *  应用层（osi前三层组合）：HTTP,FTP,DNS
     *  传输层：TCP,UDP
     *  网络层：ARP,ICMP
     *  网络接口层(osi最后两层组合)：MAC,VLAN
 *  ip地址(最小)占几个字节
    
     *  ipv4由32为二进制表示，每32/8 = 4bytes
 *  accept发生在三次握手哪个阶段？
    
     *  第三次握手阶段accept返回
 *  tcp和udp的区别，还有应用场景：
    
     *  tcp面向连接的，面向字节流的，可靠的，点对点，有流量控制和拥塞控制（慢启动，拥塞避免，快重传，快恢复），
        
        首部20字节；应用：文件传输，重要状态更新；
     *  udp是面向数据报，不可靠的，支持一对一，多对多，一对多，没有拥塞控制，首部开销8字节；应用：视频传输，
        
        实时通信；
 *  tcp的四次挥手过程？
    
     *  pass
 *  了解tcp的滑动窗口？
    
    窗口：无需确认包的情况下一次性可以发送的最大数据包数量；
    
    滑动窗口机制用于流量控制，有发送窗口和接收窗口，初始窗口大小根据带宽而定，后面根据收发情况动态调整窗口大小

# 数据结构和算法 #

*  如何判断一点在线段的左边还是右边或者线上，如果在左边返回true,否则返回false.
    
     *  计算向量之间叉积：
        
         *  大于0 : 左侧
         *  小于0：右侧
         *  等于0：线上
 *  字符串匹配（手写KMP，并分析复杂度）
    
        // 时间复杂度： O（M+N）
        void getNext(const char* p,int* next){
              
            // 模式串p(需要匹配的)
            int i = 1;
            int j = 0;
            int len = strlen(p);
            next[0] = 0;
            while(i < len){
              
                if(p[i] == p[j]){
              
                    next[i++] = ++j;
                }
                else{
              
                    j > 0 ? j = next[j-1] : next[i++] = 0;
                }
            }
        }
        int kmp(const char* s,const char* p){
              
            // s中找p
            int i = 0;
            int j = 0;
            int lens = strlen(s);
            int lenp = strlen(p);
            while(i < lens){
              
                if(s[i] == p[j]){
              
                    ++i;
                    ++j;
                }
                else{
              
                    j > 0 ? j = next[j-1] : i++;
                }
                if(j == lenp){
              
                    return i-lenp; //匹配一个
                    // 若多个: j = next[j-1];
                }
            }
            return j == lenp ? (i-lenp) : -1;
        }
 *  快排思路
 *  对排序的稳定性是如何理解？ 快排稳定吗？
 *  进制转换：10->8,10->7
    
     *  除余法
 *  删除链表中指定元素(**需要避免内存泄漏**)
    
     *  遍历，同时记录前驱结点pre，遇到目标元素now，pre->next=now->next,delete 结点时需要注意；
        
            struc Node{
                    
                Node():val(0),next(nullptr){
                    }
                int val;
                Node* next;
            };
            Node* deleteNode(Node* head,int val){
                    
                Node* new_head = new Node();
                new_head->next = head;
                Node* pre = new_head;
                Node* now = head;
                Node* del = nullptr;
                while(now){
                    
                    if(now->val==val){
                    
                        pre->next = now->next;
                        del = now;
                        now = now->next;
                        delete del;
                    }
                    else{
                    
                        pre = now;
                    	now = now->next; 
                    }
                }
                head = new_head->next;
                delete new_head;
                return head;
            }
 *  TopK问题以及时间复杂度
    
     *  快速选择，O(N)
     *  维护大小为k的堆，O(NlogK)
     *  如果有多台机器，分治法
 *  如何解决hash碰撞：
    
     *  链地址法
     *  开放地址法（线性探测，二次方探测）
     *  再hash法
     *  建立公共溢出区（溢出区再冲突可以结合其他解决hash碰撞的方法）

# 操作系统 #

*  什么是死锁，举个简单例子，死锁条件？如何避免？
    
     *  定义：多个进程因为争夺资源而造成的一种僵局，各自都无法往下推进；
        
        比如进程A,B,资源C,D,A持有了C还想要D，B持有了D还想要C;
     *  条件：
        
         *  互斥
         *  不可剥夺
         *  持有并保持
         *  循环等待
     *  避免：
        
         *  按相同的顺序加锁
         *  一定时间内没有获取到其他锁，释放已有的锁（定时锁）
         *  提前检测死锁（银行家算法）
 *  简述消费者和生产者模型和读写者模型，并简述它们的区别；
    
     *  生产者和消费者一段时间内共用一段内存（缓冲区），生：放，消：取；无数据：消费者阻塞，数据满：生产者阻塞；
     *  区别：
        
         *  读写者模型出现了读者共享的关系，而生产者和消费者模型只有互斥和同步关系（生与消：互斥和同步；生和生，消与消：互斥）；
         *  读者不会使得缓冲区改变；

### 线程通信方式，如何保证数据一致性？ ###

通信方式：

*  全局变量
 *  信号机制

同步：

临界区：通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问；

互斥量Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问

信号量Semphare：为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。

事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作；

### 进程的通信方式： ###

*  管道（PIPE和命名管道FIFO）
 *  系统IPC(inter-process communication):
    
     *  消息队列
     *  信号量
     *  信号
     *  共享内存
 *  Socket通信

### 线程同步和异步 ###

*  同步：多个线程访问同一资源，当资源互斥时，其他线程盲目等待；
 *  异步：多个线性访问互斥资源时，不盲目等待先去干其他事情；

### 阻塞和非阻塞 ###

*  阻塞：会挂起线程（盲目）
 *  非阻塞：不会挂起线程（不盲目）

# 数据库 #

*  什么是主键？什么是索引？如何使用索引？索引适用于什么场景？
    
    [ref1:【面试】面试常问之数据库索引][ref1]
    
     *  主键：能够唯一标识表中一条记录的最小属性集（候选码中选一个）
     *  索引：是数据库对表中一列或多列进行排序的结构，便于快速找到数据；
     *  使用：
        
         *  创建：
            
            way1: `create index_type index_name on table_name(column_name_tuple)`
            
            way2: `alter table table_name add index_type index_name(column_name_tuple)`
         *  删除：`drop index index_name on table_name`
         *  查询：`show index from table_name`
     *  适用场景：频繁查询，较少增加，删除，修改的情况（因为维护索引开销大）；
     *  索引的种类（[ref2:什么是数据库索引][ref2]）：
        
        大类：
        
         *  聚簇索引（将数据存储与索引放到了一块，**一个表只能有一个聚簇索引**，聚簇索引默认为主键）：
            
            在数据库中，表中数据会按主键排序；
         *  非聚簇索引（辅助索引）：给普通字段加上索引，查找时：类似于先找目录再找页码；
        
        小类：
        
         *  普通索引和唯一索引
         *  单值索引和复合索引
 *  写sql:
    
     *  不能使用min,查找char表中age最小的记录
     *  查找table（ID,Name）中具有2个以上ID的Name(即一个Name有2+个ID)
     *  查找info表中interest中含有football的用户
     *  查找info表中interest中含有football并且age小于30的用户
     *  查找info表中用户平均年龄
     *  查找ipinfo中相同ip中datetime最大的信息

# python #

*  有哪些方式class 中某个属性的值？
 *  正则匹配

# 其他 #

*  你觉得你的优势是什么？优点？缺点？
 *  你觉得你在哪方面会让别人眼前一亮？即你擅长什么？
 *  实习遇到什么困难？

[ref1]: https://blog.csdn.net/m0_37621024/article/details/117793056
[ref2]: https://www.cnblogs.com/wwxzdl/p/11116446.html