**

计算机考研复试面试问题总结——数据结构篇（含答案）

**

1.顺序结构和链式结构的区别？
顺序结构是指内存连续的存储单元进行存储，而链式结构是指内存不连续的结构，通过一个节点指向另外一个节点的地址。

2.栈和队列的区别？
栈是先进后出的特殊线性表，队列是先进先出的线性表。

3.复杂度是什么？
复杂度包括时间复杂度和空间复杂度，用来评价一个算法的好坏。

4.头节点的作用是什么？
头节点是指向初始地址的一个节点，它本身数据段没有内容，通过它可以标识这个链表，便于对链表进行操作。

5.介绍以下各种树
二叉树：有左右子树的区分和度不超过2。（度是指节点所拥有的字数个数）
二叉排序树：左子树均小于根，根均小于右节点。（左小右大，根中间）
线索二叉树：设置两个标识标记左右指针指向的是孩子还是前躯节点。
平衡二叉树：左右子树高度差绝对值小于等于1。
哈夫曼树：压缩用的，按权值大小排列。
完全二叉树：只能从右边为空。

6.度为二的树和二叉树的区别：
二叉树有左右子树之分。

7.树的存储结构
孩子链存储结构和双亲存储结构。

8.树的遍历
先序中序后序三种，递归实现。
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

9.图的存储
邻接矩阵和邻接表，是多对多的关系，分为有向图和无向图。

10.线性表查找有那几类？
直接查找和有序表的二分查找。

11.排序算法的介绍？
排序算法分为内部排序和外部排序。
内部排序有：插入排序、选择排序、交换排序、归并排序、基数排序。
插入排序有直接插入和折半插入。都是在有序表里插入进去的。
交换排序：冒泡，快速排序：以一个数字划分两个区域，然后分别对两个区域继续划分，直到区间为一。注意：快排是不稳定。
选择排序：简单的选择排序，堆排序
归并排序：将两个有序表归并到一个有序表。将两个有序表放到一起进行各个比较，比较完之后放回原来数组内。

12.什么是稳定的算法？
不乱动已经排序好的数字，这样算法稳定一些。

13.图的遍历方式
深度优先遍历：从初始节点开始，沿着一条道一直走，走不动了再换一条。
广度优先遍历：一层一层的遍历。

14.唯一确定一棵二叉树：
已知先序遍历+中序遍历；
已知后序遍历+中序遍历；
已知层次遍历+中序遍历。

15.直接插入排序
将数组中所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。（从小到大排序）

//未完 待续

（计算机网络+面试问题总结）
链接：https://pan.baidu.com/s/1Ixr-bHuWlvW8btEGOxOJpg
提取码：rhnz