数据结构面试常见问题总结

写在前面

本文记录了一些数据结构面试常见问题，本意用于考研复试，以下面试题为网上整理的问题以及自己加入的一些问题，答案仅供参考！

Q：数据结构三要素

A：逻辑结构、物理结构、数据运算

Q：数组与链表有什么区别？

A：

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

Q：线性表的存储结构？

A：顺序存储(内存连续)、链式存储(内存不连续)

Q：头指针和头结点的区别？

A：

头指针：是指向第一个节点存储位置的指针
头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作

Q：栈和队列的区别

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

栈：只能在栈尾入栈、出栈，是先进后出
队列：队尾进，队首出，是先进先出

Q：度为 2 的树与二叉树有什么区别

A：

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

Q：唯一确定一棵二叉树

A：中序先序/后序/层序

Q：二叉排序树

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

Q：最小生成树有几种方法？

A：

Prim（普里姆）算法：在图中取任意顶点 v 作为起始顶点，并加入集合 V；之后遍历与 V 中顶点相邻的边，选择权值最小且顶点未加入集合 V 的边，把其加入集合 V，直到集合 V 包含所有顶点结束时间复杂度：O (N2)
Kruskal（克鲁斯卡尔）算法：在含有 n 个顶点的图中始终选择权值最小且不会产生回路的边，一直进行此步骤直到选择 n-1 条边为止时间复杂度：O（e*loge）,e 为边数

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

A：邻接矩阵、邻接表、十字链表、邻接多重表

无向图：邻接矩阵、邻接表、邻接多重表
有向图：邻接矩阵、邻接表、十字链表
- 邻接矩阵：适合稠密图，确定边数总数花费时间代价大，边较少时造成空间浪费
- 邻接表：适合稀疏图，节省空间，容易找出邻边，确定两个顶点间是否存在边花费时间代价大

Q：树的存储结构

A：双亲表示法、孩子表示法、孩子兄弟表示法

Q：图的遍历和树的遍历有哪些

A：

图的遍历：广度优先遍历（BFS）、深度优先遍历（DFS）
树的遍历：先根遍历、后根遍历

Q：图的遍历与树的遍历有什么区别？

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

Q：解决哈希冲突的方法

A：

线性探测法
平方探测法
伪随机探测法
拉链法

Q：什么是稳定的算法？

A：不乱动已经排序好的数字，这样算法稳定一些

稳定的排序算法：冒泡排序、插入排序、归并排序、基数排序
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

Q：快排的操作流程

A：选取一个基准，一趟排序确定两个区间，一个区间全部比基准值小，另一个区间全部比基准值大，接着再选取一个基准值来进行排序，以此类推，最后得到一个有序的数列

Q：关键路径和关键活动

A：关键路径是项目中时间最长的活动顺序，决定着可能的项目最短工期，可能有 1 条或多条

Q：关键路径是用什么数据结构实现的

A：有向无环图

Q：排序算法的介绍

A：

冒泡排序：从左到右依次比较相邻的两个元素，如果前一个元素比较大，就把前一个元素和后一个交换位置，重复地进行直到没有再需要交换
选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
希尔排序：将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
归并排序：在排序的过程中，把原来的数组变成左右两个数组，然后分别进行排序，当左右的子数组排序完毕之后，再合并这两个子数组形成一个新的排序数组
快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
堆排序：把整个数组变成一个最大堆，然后每次从堆顶取出最大的元素，这样依次取出的最大元素就形成了一个排序的数组
基数排序：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位