计算机考研面试------数据结构
1.什么是数据结构？数据结构的三要素是？（不需要死记，知道大概就可以）
数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。
数据结构的三要素是数据的逻辑结构、数据的存储结构(物理结构)、数据的运算
数据的逻辑结构包括线性结构、非线性结构
线性结构包括线性表、栈、队列、数组、串
非线性结构包括集合、树、图
数据的存储结构包括顺序存储、链式存储、散列存储、索引存储
2.请说明栈与队列的区别？
首先，栈和队列都是受限的线性表，栈只能在表的一端进行插入和删除，队列只能在队列的一端进行插入另外一端进行删除。
其次，栈是先进后出，队列是先进先出。
3.解释下头指针和头节点的区别？那么单链表增加头结点的目的是什么？有什么用？
头指针:是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。
头结点:是为了操作统一和方便设立的，放在第一个元素节点之前，头结点的数据域也可以不存储任何信息，因此头结点可有可无。
增加头结点的可以方便运算，例如：在第一个元素结点前插入结点和删除结点操作与其它结点的操作统一了
ps:不明白带头结点和不带头结点的区别这个链接讲的很详细https://zhidao.baidu.com/question/568768263.html
4.循环链表的优点是什么 ？
可以从任何一个结点访问整个链表。
5.数组和链表的区别？(比较经典的问题)
从逻辑结构来看：数组的存储长度是固定的，即数组大小定义之后不能改变，而且在插入和删除操作需要移动大量的元素。相反对于链表，它能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。
从访问方式来看：数组中的元素在内存中连续存放，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，他的存储空间不是必须连续的，可以是任意的，因此链表的访问必须从前往后依次进行，访问效率比较低。
6.数据结构的复杂度o(1)是什么意思？
时间复杂度O(n)，表示程序运行时间跟n有关，并且是线性关系。
空间复杂度O(1)，表示所需辅助空间为常量，并且与n无关。
7.简述下数据结构中的各种树？(这里把一些常见的列举出来)
二叉树:只有一个根节点，每个结点最多有2个子节点，且有左右子树区分。
二叉排序树:左子树均小于根，右子树均大于根。
平衡二叉树：左右子树高度差绝对值小于等于1。
满二叉树：一棵二叉树的结点要么是叶子结点，要么它有两个子结点（如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树。）
完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。
最优二叉树(哈夫曼树)：树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
8.简述下广度优先遍历和深度优先遍历？
广度优先遍历：首先访问顶点v，然后依次遍历v的所有未访问过得邻接点，再依次遍历下一层未被访问过的邻接点，直到最后所有顶点被访问。
深度优先遍历：首先访问顶点v，若v的第一个邻接点没有被访问过，则深度遍历该邻接点；若v的第一个邻接点已经被访问，则访问其第二个邻接点，进行深度遍历；重复以上步骤，直到所有节点都被访问过为止。
9.简述下迪杰斯特拉（dijkstra）算法、弗洛伊德（Floyd）算法？
迪杰斯特拉（dijkstra）算法：迪杰斯特拉算法是经典的单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心层层向外扩展，直到扩展的终点为止，迪杰斯特拉算法要求边的权值不能为负权。
弗洛伊德（Floyd）算法：弗洛伊德算法是经典的求任意顶点之间的最短路径，其边的权值可为负权，该算法的时间复杂度为O(N^3),空间复杂度为O（N^2）。
10.简述下求最小生成树的2种算法？
普里姆（prim）算法：它的思想是随机选取一顶点出发，选择与其相邻且权值最小的边加入到集合中，然后在选与此边相连的下个顶点出发，重复上述的操作直到所有顶点被访问。
克鲁斯卡尔（kruskal）算法：它的思想是按照权值递增顺序依次从剩下未访问的边添加到集合中，如果加入之后构成回路则舍弃，直到回路中有n-1条边。
11.简述下什么是拓扑排序？
它的思想是选择一个入度为0的顶点并输出，然后从网中删除此顶点以及所有出边，循环直到结束。
12.简述下邻接矩阵与邻接表的区别？
连接矩阵表示：无向图的邻接矩阵是对称的，矩阵的行或列的有效元素的个数之和是节点的度。有向图的邻接矩阵不一定对称，矩阵中行的有效元素的个数之和是节点的出度，列的有效元素的个数之和是节点的入度。
邻接表表示：无向图的每条边在邻接表中存储两次，若想知道节点的度，只需要求出对应链表中节点的个数即可。有向图的边在邻接表中仅存储一次，若想知道节点的出度，则需要遍历对应的链表，若要求节点的入度则还需要遍历其他的链表。
邻接矩阵的优点是可以很方便的知道两个节点之间是否存在边，以及快速的添加或删除边；缺点是如果邻接矩阵中节点个数比较少容易造成存储空间的浪费。
邻接表的优点是节省空间，只给实际存在的边分配存储空间；缺点是在涉及度时可能需要遍历整个链表。
13.数据结构有哪些排序算法？说一到两种排序算法的优劣？并比较时间复杂度？
主要的排序算法有：插入排序、冒泡排序、选择排序、快速排序、归并排序、堆排序
插入排序（稳定）：将未排序序列中的元素插入到前面已排序好的元素中，最好情况时间复杂度为O（n）,平均时间复杂度和最坏情况为O(n^2)
折半插入排序（稳定）：设置三个变量low high mid，令mid=(low+high)/2,若a[mid]>key,则令high=mid-1,否则令low=mid+1,直到low>high时停止循环，对序列中的每个元素做以上处理，找到合适位置将其他元素后移进行插入。他的比较次数为O(nlog2n),但是因为要后移，因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是：比较次数大大减少。
冒泡排序（稳定）：每一趟都将元素进行两两比较，并且按照“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O（n^2）,空间复杂度为O（1）。
归并排序（稳定）：把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为O（nlogn）,空间复杂度和待排序的元素个数相同。
快速排序（不稳定）：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。优点是：每一趟不仅能确定一个元素，时间效率较高。时间复杂度为O(nlog2n),空间复杂度为O（log2n）
希尔排序（不稳定）：先将序列分为若干个子序列，对各子序列进行直接插入排序，等到序列基本有序时再对整个序列进行一次直接插入排序。优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多，空间复杂度为O（1）。
简单选择排序（不稳定）：将序列分为2部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是：实现起来特别简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。时间复杂度为O（n^2），空间复杂度为O（1）。
堆排序（不稳定）：设有一个任意序列，k1,k2,...,kn，当满足下面特点时称之为堆：让此序列排列成完全二叉树，该树具有以下特点，该树中任意节点均大于或小于其左右孩子，此树的根节点为最大值或者最小值。优点是：对大文件效率明显提高，但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。
14.什么是稳定的排序算法？
稳定的排序算法就是序列中2个相同的数字在排序前和排序后位置顺序未改变。
15.循环比递归效率高？
递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。
①递归
优点：代码简洁、清晰，并且容易验证正确性。
缺点：效率较低，递归是有时间和空间消耗的，递归中很多计算都是重复的，从而给性能带来很大的负面影响。
②循环
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
好了以上就是我个人以及网上收集资料整理的关于数据结构可能回问的题目，我已经将这些题目整理到world文档里面去了，点击这里数据结构面试汇总，然后关注公众号在后台回复考研面试，就可以获得这套资源。
作者：流年若逝
