数据结构面试总结【第一弹】

news/2024/4/29 7:14:12/文章来源:https://www.cnblogs.com/SaltyCheese/p/16635210.html

数据结构面试总结

数据结构面试总结
- 1.数据结构基本概念
  - 1.1 数据结构三要素
- 2.线性表
  - 2.1 数组与链表有什么关系
  - 2.2 线性表的存储结构
  - 2.3 头指针和头节点的区别
  - 2.4 栈和队列的区别
- 3.树
- 3.1 度数为2的树与二叉树有什么区别
  - 3.2 唯一确定一棵二叉树
  - 3.3 二叉排序树
  - 3.4 最小生成树有几种方法
  - 3.5 树的存储结构
- 4.图
  - 4.1 图的存储方式有哪些？每一种方式的优缺点？
  - 4.2 图的遍历DFS、BFS
  - 4.3 图的遍历和树的遍历区别
  - 4.4 关键路径是用什么实现的
- 5.排序
  - 5.1 冒泡排序
  - 5.2 选择排序
  - 5.3 插入排序
  - 5.4 归并排序
  - 5.5 快速排序
  - 5.6 堆排序
  - 5.7 希尔排序
- 6. 其他
  - 6.1 C++相关问题
    - 1. C和C++的区别
    - 2. C++中指针和引用的区别
    - 3. 结构体struct和共同体union的区别
    - 4. #define和const的区别
    - 5. new/delete/malloc/free之间的区别
    - 6. STL库
    - 7. c++的内存管理
- 7.参考资料

1.数据结构基本概念

1.1 数据结构三要素

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

2.线性表

2.1 数组与链表有什么关系

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

2.2 线性表的存储结构

链式存储
顺序存储

2.3 头指针和头节点的区别

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

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

2.4 栈和队列的区别

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

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

3.树

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

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

3.2 唯一确定一棵二叉树

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

3.3 二叉排序树

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

3.4 最小生成树有几种方法

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

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

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

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

3.5 树的存储结构

双亲表示法
孩子表示法
孩子兄弟表示法

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.排序

排序	稳定性	平均时间复杂度	最佳时间复杂度	最坏时间复杂度	辅助空间
冒泡排序	√	O($n^2$)	O(n)	O($n^2$)	O(1)
选择排序	×	O($n^2$)	O($n^2$)	O($n^2$)	O(1)
插入排序	√	O($n^2$)	O(n)	O($n^2$)	O(1)
归并排序	√	O(nlogn)	O(n)	O(nlogn)	O(n)
快速排序	×	O(nlogn)	O(nlogn)	O($n^2$)	O(logn)
堆排序	×	O(nlogn)	O(nlogn)	O(nlogn)	O(1)
希尔排序	×	O(nlogn)	O(n)	O($n^2$)	O(1)

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);
}

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);
}

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);
}

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);}
}

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);
}

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);
}

6. 其他

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

6.1 C++相关问题

1. C和C++的区别

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

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

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

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

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

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

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

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

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

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

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

4. #define和const的区别

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

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

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

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