面试常见问题

内存分配结构

代码区：存放代码的位置，只读

常量区：存放常量（如变量名字，非零的初始化值，字符串，const常量等），只读

静态区、全局区：存放全局变量和静态变量，具体分为两个段，.bss段和.data段

• .bss段：存放未初始化的和初始化为0的全局变量或者静态变量

• .data段：初始化不为0的全局变量或者静态变量

堆：程序运行期间动态分配malloc所使用的区域

栈：用于存放地址（用于函数的现场恢复）、临时变量（函数内部定义的变量，或是函数定义的参数）等

快速排序平均复杂度

各种排序和查找比较

排序和查找时间复杂度总结

union、struct和class

1. Union：Union是一种特殊的数据结构，它允许在相同的内存位置存储不同的数据类型。Union中所有的成员都共享同一块内存，只有最后一次赋值的成员有效。Union适用于需要在不同数据类型之间进行转换的情况。

2. Struct：Struct是一种用户自定义的数据类型，它允许将不同的数据类型组合在一起成为一个新的数据类型。Struct中的每个成员都有自己的内存地址，可以分别进行访问和赋值。Struct适用于需要表示具有多个属性的对象的情况。

3. Class：Class是一种用户自定义的数据类型，它可以包含数据成员和成员函数，并且可以实现面向对象的编程。Class中的数据成员和成员函数默认是私有的，可以通过public、protected和private关键字进行访问控制。Class适用于需要表示真实世界中的对象和实现面向对象的编程的情况。

连通分量和强连同分量

• 连通分量指的是无向图中的一个极大连通子图。具体来说，对于无向图G=(V,E)，若存在一个子集U⊆V，使得U中任意两个点在图G中都可以通过一条路径相互到达，且U是极大的，即U不能再加入任何其他的点，那么U就是图G的一个连通分量。

• 强连通分量则是有向图中的一个极大强连通子图。具体来说，对于有向图G=(V,E)，若存在一个子集U⊆V，使得U中任意两个点在图G中都可以通过一条有向路径相互到达，且U是极大的，即U不能再加入任何其他的点，那么U就是图G的一个强连通分量。

一个弱连通分量不一定是强连通分量，而一个强连通分量必然是一个弱连通分量。

tarjan算法

面向对象的特征

1. 封装（Encapsulation）：封装是指将数据和方法进行包装，使其对外部隐藏，只保留必要的接口暴露给外部使用。封装可以有效地保护数据和方法，确保其不会被误用或滥用，从而提高程序的可靠性和安全性。

2. 继承（Inheritance）：继承是指通过定义子类来继承父类的属性和方法。子类可以继承父类的公共方法和属性，并且可以添加自己的方法和属性。继承可以有效地减少代码的重复，提高代码的复用性。

3. 多态（Polymorphism）：多态是指同一个方法名可以具有不同的实现方式。在面向对象编程中，多态可以通过重载、重写和接口实现。多态可以提高代码的灵活性和可扩展性，使代码更加简洁易懂。

4. 抽象（Abstraction）：抽象是指将复杂的实体抽象成类和对象，并仅保留必要的属性和方法。抽象可以让程序员更加专注于问题的本质，而不是实现的细节。同时，抽象也可以提高代码的复用性和可维护性，使代码更加健壮。

引用和指针

区别：

1. 定义方式：引用在定义时必须初始化，而指针可以先定义，后赋值。

2. 操作方式：引用在使用时类似于变量名，直接操作被引用对象，不需要使用 * 取值运算符；指针需要通过 * 取值运算符来获取被指向对象的值。

3. 空指针：指针可以指向空值，而引用不能引用空值。

4. 引用的一些特性：引用一旦绑定对象就不能更改，指针可以随时改变指向的对象。

联系：

1. 都可以用于访问内存中的数据。

2. 都可以用于实现函数参数的传递，引用参数和指针参数都可以用于在函数内部改变外部数据。

3. 引用和指针都可以作为返回值，引用作为返回值可以避免拷贝大对象的开销。

C++和C的关系

C++：面向对象，引入新语法和特性，包括类、继承、多态、模板。

判断有向图是否有环

深搜、拓扑排序