C++面试题整理

2018-08-01 本文已影响16人远行_2a22

C++基础部分

C++ static_cast和dynamic_cast的区别

static_cast可以部分的做显式转换的事，也可以进行继承层次的转换。它没有运行时类型检查来保证转换的安全性。它的上行转换时没问题的，但是它的下行转换时不安全的。static_cast可施加与任何类型，无需多态

dynamic_cast用来实现指针类型的转化。dynamic_cast要求src必须是多态的，因为dynamic_cast需要从类的虚函数表表中获得类类型信息。。多态分为上行转换和下行转换，上行转换没问题，子类的指针肯定可以转换成父类指针。下行转换就有问题了，如果要把父类的指针A转换成子类的指针B，如果A指向的是子类的对象，这样转没问题。但是，如果A指向的是父类的对象，正确的做法是转换应该为不成功的，因为多态里没有子类的指针指向父类的对象的。所以，在“A指向的是父类的对象，现要把A转成B”这种情况下，如果采用static_cast，不会报错，返回的是转换后的指针，但程序此时是不安全的。如果采用dynamic_cast，它会根据虚函数表找到A指向的是什么对象（这里要求父类必须要有虚函数，否则报错），如果是父类对象，返回NULL，如果是子类对象，返回转换后的指针，程序此时是安全的。所以，这就是dynamic_cast和static_cast最大的区别。

https://blog.csdn.net/u010122607/article/details/49421887、

虚函数表存放在哪里
https://blog.csdn.net/jiary5201314/article/details/52627630
C++如何实现只能动态分配类对象，不能定义类对象
https://blog.csdn.net/xiaominkong123/article/details/52162956
C++中的hash_map和map的区别
https://blog.csdn.net/zkangaroo/article/details/77368907
字符串相关

整型，浮点型和字符串的转换（atoi,atof,itoa)

字符串拷贝注意异常检查，比如空指针，字符串重叠，自赋值，字符串结束符‘\0’等。

实现strcpy函数
https://blog.csdn.net/xiaominkong123/article/details/52232268
const关键字的作用?（const成员函数,函数传递和define的区别）
https://blog.csdn.net/xiaominkong123/article/details/52232268
静态成员函数和数据成员有什么意义？

静态数据成员：类内数据成员声明的时候加上static修饰符。

特点：1）该类的所有对象共享访问该数据成员，在程序中，只有一个复制品。而对于非静态数据成员，每个类对象都有自己的复制品。

2）存储在全局数据区。定义时要分配空间，所以不能在类声明中定义。

3）与普通数据成员一样遵从public、private、protected访问规则。

4）初始化在类外，不加static。

5）静态成员之间可以互相访问，包括静态成员函数访问静态数据成员和访问静态成员函数；非静态成员函数可以任意地访问静态成员函数和静态数据成员；

优势：1）静态数据成员没有进入程序全局名字空间，因此不会与程序中其他全局名字冲突。

2）可以实现信息隐藏。静态数据成员可以是private成员，而全局变量不能。

静态成员函数：1）是为类的全部服务而不是为类的某个对象服务。

2）是类的内部实现，属于类定义的一部分。

3）由于不与任何对象相连系，因此不具有this指针。所以，无法访问类对象的非静态数据成员，也无法访问类非静态成员函数，只能访问静态数据成员，调用静态成员函数。

https://blog.csdn.net/kerry0071/article/details/25741425/

C++关键字explict的详解和使用
https://blog.csdn.net/cbNotes/article/details/39551023
迭代器删除元素的会发生什么？
https://blog.csdn.net/xiaominkong123/article/details/52232268
c++中使用struct，struct中有指针
https://blog.csdn.net/xdf191/article/details/50740277
STL

STL（Standard Templete Library）是一个C++领域中，用模板实现的数据结构和算法库，已经包含在了C++标准库中，其中的vector,list,stack,queue等结构不仅拥有更强大的功能，还有了更高的安全性。除了数据结构外，STL还包含了泛化的迭代器，和运行在迭代器至上的各种使用的算法。这些对于性能要求不是太高，但又不希望自己从底层实现算法的应用还是很具有诱惑力的。

在C++中使用引用类型的成员变量
https://blog.csdn.net/mangobar/article/details/52137830
C++面试题之浅拷贝和深拷贝的区别
https://blog.csdn.net/caoshangpa/article/details/79226270
C++中虚析构函数的作用及其原理分析
https://blog.csdn.net/derkampf/article/details/62093252
STL相关的知识。Stl容器的参数allocate是用来做什么的？这是一个函数对象，用来指定小于运算过程。Map的Key有什么要求？开始我答不能重复，他继续问，答必须重载<运算符，OK。
http://cissco.iteye.com/blog/379093
智能指针是怎么实现的，你来实现一个智能指针。在构造函数里进行指针赋值，析构里delete。其实还有很多的，比如实现get方法，拷贝构造函数、赋值运算符行为。
C++重写（覆盖）、重载、隐藏（重定义）、多态
https://www.cnblogs.com/DannyShi/p/4593735.html
智能指针的原理和实现
https://blog.csdn.net/worldwindjp/article/details/18843087

auto_ptr与shared_ptr
https://www.cnblogs.com/cfans1993/p/6769022.html

C++11学习之share_ptr和weak_ptr
https://blog.csdn.net/haolipengzhanshen/article/details/52205102

构造函数里调用虚函数会出什么问题。我说编译错，回答错了。不会有任何问题，只是此时的虚函数表指针指向的永远是当前类型。Effective C++中指出 Don’t 这样做。

数据结构部分：

数组和链表的区别。（很简单，但是很常考，记得要回答全面）

C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前无法确定数组的大小，只能够将数组定义成足够大小，这样数组的空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，他采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。

从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。

从内存存储的角度看；数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。

从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

链表的一些操作，如反转，链表陈钊环路判断，双向链表，循环链表相关操作。
队列，栈的应用。（比如对垒在消息队列，站用在递归调用中）
二叉树的是那种遍历方式及其递归和非递归实现，三种遍历方式的主要应用（后缀表达式），相关的时间复杂度。
数据结构中二叉树的非递归遍历（画图举例讲解，写代码）
https://blog.csdn.net/xiaominkong123/article/details/52232268
https://www.jianshu.com/p/6e739de0d206
红黑树与AVL树的相同点与区别
https://blog.csdn.net/xiaominkong123/article/details/52232268、

红黑树没有AVL树那么高度平衡，所以红黑树的查找性能相比AVL树要差一些，查找上的这一点性能差相比数据的插入和删除时的旋转性能是值得的，这就是为什么很多场合是用的红黑树，而不是AVL树，例如STL中。
当然如果遇见那种一次建树，而后只查询的这种情况时，AVL树比红黑树更实用。但如果真有这样的需求可能也不会用AVL树了，像Hash_map会更快
算法部分：

哈希表及处理冲突的方法
https://blog.csdn.net/wangwei249/article/details/70172811
单链表反向，给定head指针，写出C++函数。维护两个链表head，一个指向已反向的链表头，一个指向仍未反向的链表头。遍历一次就好了。
https://blog.csdn.net/hbuxiaofei/article/details/36673043
https://blog.csdn.net/Mikeoperfect/article/details/72642583
找出链表的中间节点。使用两个指针，一次循环中A走两步，B走一步，A到头时，B即是中间节点。其实让一个指针遍历两次其时间复杂度是一样的，只不过代码冗余。面试官不关心这个~
https://blog.csdn.net/ttyue_123/article/details/52166442
快速删除链表中某节点，有指针。用其next节点覆盖该节点内容，然后把后面链表接上。
https://blog.csdn.net/cchengone/article/details/52973877

如何根据前序、中序、后序遍历还原二叉树
https://blog.csdn.net/changjiale110/article/details/79489884

判断单链表中是否有环，找到环的入口节点
https://blog.csdn.net/u011373710/article/details/54024366

算法部分

排序算法：

排序可以算是最基本，最常用的算法，也是笔试面试中最常被考的算法，最基本的是冒泡排序，选择排序，插入排序要可以很快地用代码实现。这些主要考察你的实际编码能力。堆排序，归并排序，快速排序这些算法需要熟悉主要思想，和需要注意的细节地方。需要熟悉的常用排序算法的时间复杂度和空间复杂度。各种排序算法的使用范围：

（1）当数据规模较小时候，可以使用简单的直接插入排序或者直接选择排序。

（2）当文件的初态已经基本有序，可以用直接插入排序和冒泡排序。

（3）当数据规模较大是，应用速度最快的排序算法，可以考虑使用快速排序。当记录随机分布的时候，快速排序平均时间最短，但是出现最坏的情况，这个时候的时间复杂度是O(n^2)，且递归深度为n,所需的占空间为O(n)。

（4）对排序不会出现快排那样最坏情况，且堆排序所需的辅助空间比快排要少，但是这两种算法都不是稳定的，要求排序时是稳定的，可以考虑用归并排序。

（5）归并排序可以用于内部排序，也可以使用于排不排序。在外部排序时，通常采用多路归并，并且通过解决长顺串的合并，缠上长的初始串，提高主机与外设并行能力等，以减少访问外存额外次数，提高外排的效率。