数据结构面试整理

1.数据结构基本概念

1.1 数据结构三要素

• 逻辑结构
• 物理结构
• 数据运算

2.线性表

2.1 数组与链表有什么关系

• 数组静态分配内存，链表动态分配内存
• 数组在内存中连续，链表不连续
• 数组利用下标定位，查找复杂度为O(1)，链表定位复杂度为O(N)
• 数组插入或者删除元素的时间复杂度是O(N)，链表是O(1)

2.2 线性表的存储结构

• 链式存储
• 顺序存储

2.3 头指针和头节点的区别

头指针：指向第一个节点存储位置的指针

头节点：是放在第一个元素之前，便于在第一个元素节点之前进行插入和删除操作

2.4 栈和队列的区别

栈和队列都是操作受限的线性表

• 栈：先进后出，栈顶入栈、栈顶出栈
• 队列：先进先出，队尾入栈、队首出栈

3.树

3.1 度数为2的树与二叉树有什么区别

1. 度数为2的树至少有3个结点，而二叉树可以为空
2. 二叉树有左右子树之分

3.2 唯一确定一棵二叉树

中序遍历+先序/后序/层序遍历

3.3 二叉排序树

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉排序树。

3.4 最小生成树有几种方法

Prim:在图中选择任意顶点v作为起始顶点，并加入集合V；之后遍历与V中顶点相邻的边，选择权值最小且顶点u未加入集合V中的边，将其加入集合V，直到集合V中包含所有顶点结束

时间复杂度：$O(N^2)$

Kruskal:在含有N个顶点中的图中始终选择权值最小且不会产生回路的边，一直进行此步骤直到选择到N-1条边为止

时间复杂度：$O(e\times loge)$

3.5 树的存储结构

1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法

4.图

4.1 图的存储方式有哪些？每一种方式的优缺点？

邻接矩阵：适合稠密图，确定边数总数花费时间代价大，边较少时造成空间浪费

邻接链表：适合稀疏图，节省空间，容易找出邻边，确定两个顶点间是否存在边花费时间代价大

4.2 图的遍历DFS、BFS

DFS：（效率低但是内存消耗少）

• 解决的问题：能找出所有解决方案
• 优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少的优点
• 要多次遍历，搜索所有可能路径，标识做了之后还要取消。
• 在深度很大的情况下效率不高

BFS：（效率高但是内存消耗大）

• 解决的问题：对于解决最短或最少问题特别有效，而且寻找深度小

• 每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短

• 内存耗费量大（需要开大量的数组单元用来存储状态）

4.3 图的遍历和树的遍历区别

图的遍历可能会出现循环遍历的情况，要设置标记数组。而树的遍历则不会出现这种情况。其次，图可能存在不连通的情况，而树不存在，所以图的遍历要对所有的顶点都循环一遍。

4.4 关键路径是用什么实现的

数据结构：有向无环图

关键路径的定义：路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度路径的被称为关键路径。

算法时间复杂度：O(n+e)其中n为结点个数，e为边数

算法步骤：

​ 1.利用拓扑排序求出是否能进行关键路径的查询

​ 2.在拓扑排序的过程中求出事件的最早开始时间

​ 3.利用栈把拓扑序列存储下来，然后从栈顶依次推出事件的最晚开始时间

​ 4.利用ete和lte判断这个活动是否是关键活动

​ 5.ete等于这个事件的最早开始时间（为什么？因为你这个事件要想发生，必须等前面的事情全部发生完，所以就是最早开始时间的求解步骤

​ 6.lte等于这个事件的下一个事件的最晚开始时间减去持续时间（为什么？因为下一个事件的最晚开始时间代表着后面的事件能否正常进行，也就是意味着后面的活动是否能进行，同理，最晚活动开始时间也因该是下一个事件的最晚开始时间-持续时间）

代码【参考】

5.排序

5.1 冒泡排序

void bubbleSort(int v[],int len){
	bool flag;
	for(int i=0;i<len-1;i++){
		flag=false;
		for(int j=i+1;j<len;j++){
			if(v[j]<v[i]){
				swap(v[i],v[j]);
				flag=true;
			}
		}
		if(!flag){
			break;
		}
	}
	show(v,len);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.2 选择排序

每次在未排序的部分中找到最小的插入到已排序的部分中的最后位置

void selectSort(int v[],int len){
	for(int i=0;i<len-1;i++){
		int min_index=i;
		for(int j=i+1;j<len;j++){
			if(v[min_index]>v[j]){
				min_index=j;
			}
		}
		swap(v[i],v[min_index]);
	}
	printf("选择排序:"); 
	show(v,len);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13

5.3 插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void insertSort(int v[],int len){
	for(int i=1;i<len;i++){
		int value=v[i];//需要插入前面到已经排序好的数组中 
		int pos=i;
		while(pos>0&&v[pos-1]>value){
			v[pos]=v[pos-1];
			pos--;
		}
		v[pos]=value;
	}
	printf("插入排序:"); 
	show(v,len);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13

5.4 归并排序

**算法：**归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

动图演示：

5.5 快速排序

动图演示：

代码展示：

void quickSort(int v[],int low,int high){
	if(low<high){
		int i=low,j=high;
		int x=v[low];
		while(i<j){
			while(i<j&&v[j]>=x)j--;
			if(i<j)v[i++]=v[j];
			while(i<j&&v[i]<=x)i++;
			if(i<j)v[j--]=v[i];
		}
		v[i]=x;
		quickSort(v,low,i-1);
		quickSort(v,i+1,high);
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.6 堆排序

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

• 调整堆
• 创建最大堆
• 堆排序

//堆排序
void Adjust(int v[],int len,int index){
	int left=index*2+1;
	int right=index*2+2;
	int max_index=index;
	if(left<len&&v[left]>v[max_index])max_index=left;
	if(right<len&&v[right]>v[max_index])max_index=right;
	if(max_index!=index){
		swap(v[index],v[max_index]);
		Adjust(v,len,max_index);
	}
}
void heapSort(int v[],int len){
	//初始化：自下而上调整堆成为大顶堆
	for(int i=len/2-1;i>=0;i--){
		Adjust(v,len,i);
	}
	for(int i=len-1;i>=1;i--){
        //排序
		swap(v[0],v[i]);
        //更新堆
		Adjust(v,i,0);
	} 
	printf("堆排序:");
	show(v,len);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

5.7 希尔排序

动图演示：

代码实现：

void shellSort(int v[],int len){
	int i,j,step;//step为步长，每次减为原来的一半
	for(step=len>>1;step>0;step>>=1) {
		for(i=0;i<step;i++){
			for(j=i+step;j<len;j+=step){
				if(v[j]<v[j-step]){
					int tmp=v[j];
					int k=j-step;
					while(k>=0&&v[k]>tmp){
						v[k+step]=v[k];
						k-=step;
					}
					v[k+step]=tmp;
				}
			}
		}
	}
	show(v,len);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6. 其他

这部分其实看你简历上写了啥，比如写了会写C++/Python那么相关的问题一定要会嗷~

6.1 C++相关问题

1. C和C++的区别

1. C是面向过程的语言，C++是面向对象的语言（继承、封装和多态）
2. C和C++动态管理内存的方法不一样，C使用的是malloc/free，而C++除此之外还有new/delete
3. C++中有引用，C中没有这个概念

2. C++中指针和引用的区别

1. 指针是一个新的变量，存储了另一个变量的地址，我们可以访问此地址来修改对应的变量；引用只是一个别名，还是变量本身，对引用的任何操作就是对变量的操作，可以达到修改的目的
2. 引用只有一级，指针可以有多级
3. 指针传参的时候还是以值传递，指针本身的值不可以修改，需要通过解引用才能进行操作；引用传参的时候，传进来的就是变量本身，因此变量可以被修改

3. 结构体struct和共同体union的区别

结构体：将不同类型的数据组合成一个整体，是自定义类型

共同体：不同类型的几个变量共同占用一段内存

（1）结构体中的每个成员都有自己独立的地址，它们是同时存在的；共同体中所有成员占一个内存，不能同时存在

（2）sizeof(struct)是内存对齐后所有成员的总长度，sizeof(union)是内存对齐后最长成员长度

结构体为什么要内存对齐呢？

1.平台原因（移植原因）：不是所有的硬件平台都能访问任意地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常

2.硬件原因：经过内存对齐之后，CPU的内存访问速度大大提升。

4. #define和const的区别

1. #define定义的常量没有类型，所以给出的是一个立即数；const定义的常量有类型名字，存放在静态区域
2. 处理阶段不同，#define定义的宏变量在预处理的时候进行替换，可能有多个拷贝，const变量是在编译时候确定其值，只有一个拷贝
3. #define定义的常量不可以用指针指向，const可以
4. #define可以定义简单的函数，cosnt不可以

5. new/delete/malloc/free之间的区别

1. malloc对于开辟空间的大小需要严格制定，而new只需要对象名
2. new为对象分配空间时，调用对象的构造函数，delete调用对象的析构函数

malloc/free是库函数，new/delete是C++运算符。对于非内部数据类型而言，光用malloc/free无法满足动态对象都要求。new/delete是运算符，编译器保证调用构造和析构函数对对象进行初始化/析构。但是库函数malloc/free是库函数，不会执行构造/析构。

6. STL库

1）STL包括两个部分：容器和算法

容器包括：序列式容器、关联式容器

序列式容器：其中的元素不一定有序，但是可以排序：vector/list/queue/stack/heap/priority_queue/slist

关联式容器：内部结构是一个平衡二叉树，每个元素都有一个键值和一个实值，比如map/set/hashtable/hash_set

算法有排序，复制等，以及各个容器特定的算法

2）vector和list的区别

• 结构上：vector是动态顺序表，内存中一块连续的数据结构；list是带头结点的双向循环链表，在内存中不是连续的一段数据结构
• 访问效率上：vector支持随机访问，指定位置插入和删除的时间复杂度O(N)；list不支持随机访问,指定位置插入和删除的时间复杂度O(1)
• 迭代器：vector利用的是原生迭代器；list对原生态指针（结点的指针）进行了封装
• 适用场景：vector适用于高效存储，需要随机访问且插入删除效率要求较低的场景；list适用于有大量插入删除操作并不关心随机访问的场景

3）vector的实现和扩容

vector使用的注意点及其原因，频繁对vector调用push_back()对性能的影响和原因。

vector就是一个动态增长的数组，里面有一个指针指向一片连续的空间，当空间装不下的时候，会申请一片更大的空间，将原来的数据拷贝过去，并释放原来的旧空间。当删除的时候空间并不会被释放，只是清空了里面的数据。对比array是静态空间一旦配置了就不能改变大小。

扩容：vector的动态增加大小的时候，并不是在原有的空间上持续新的空间（无法保证原空间的后面还有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，并释放原空间。在VS下是1.5倍扩容，在GCC下是2倍扩容。

注意：

1. vector一般是分配在堆上。

看STL源码剖析，vector的空间配置器是data_allocator，也就是simple_alloc，simple_alloc的实现就是std::alloc，根据申请的内存大小，决定用第一级配置器（malloc、free）还是第二级配置器（内存池），所以vector应该是分配在堆上的【ref】

7. c++的内存管理

C++中内存分为：栈、堆、自由存储区、静态存储区、常量区

栈：存放函数的参数和局部变量，编译器自动分配和释放

堆：new关键字动态分配的内存，由程序员手动释放，否则由程序结束后操作系统回收

自由存储区：由malloc分配的内存，和堆十分相似，由对应的free进行释放

全局/静态存储区：存放全局变量和静态变量

常量区：存放常量，不允许被修改

7.参考资料

1.数据结构面试常见问题总结_EmoryHuang的博客-CSDN博客_数据结构面试常见问题

2.[算法总结] 十大排序算法 - 知乎 (zhihu.com)

3.C++常见面试题总结 - 知乎 (zhihu.com)