数据结构面试问题组织学生集合

1.什么是数据结构？

数据结构是计算机存储和组织数据的方式。数据结构是指相互之间具有一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括四种类型。

(1)集合:数据元素之间除了数据类型相同之外，没有其他关系。

(2)线性结构:数据元素——线性表、栈、队列之间是一一对应的关系。

(3)树形结构:数据元素之间是一对多的关系。

(4)图形结构:数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

第二，解释顺序存储和链式存储。

顺序存储结构使用连续的存储空间来存储数据元素，可以随机存取，存取效率高。链式存储结构使用任意存储空间存储数据元素，不允许随机访问，因此访问效率较低。

三、头指针和头节点的区别？

头指针:指向第一个节点的存储位置的指针，具有标识的作用。头指针是链表的必要元素，无论链表是否为空，它都存在。

头节点:放在第一个元素节点之前，方便在第一个元素节点之前插入和删除。头节点不是链表的必要元素，是可选的。头节点的数据字段可能不存储任何信息。

第四，线性结构的特点

(1)集合中必须有唯一的“首元素”；

(2)集合中必须只有一个“最后元素”；

(3)除了最后一个元素，其他所有数据元素都有唯一的“继承者”；

(4)除了第一个元素，其他所有数据元素都有唯一的“前驱”。

5.数组和链表有什么区别？

从逻辑结构上看，数组的存储长度是固定的，所以不能适应数据的动态增减。链表可以动态分配存储空间以适应数据的动态增减，插入和删除都很容易。

从访问方式上看，数组在内存中是一个连续的存储空间，可以通过数组下标随机访问数组，访问效率高。链表是一种链式存储结构，存储空间不一定是连续的，可以是任意的。存取必须从前到后进行，存取效率低于数组。

如果从第I个位置插入多个元素，对于数组来说，每次插入都需要将元素后移，每次插入的时间复杂度为O(n)，而对于单链表来说，只有第一次找到I的位置时时间复杂度为O(n)，其他插入和删除操作的时间复杂度为O(1)，提高了插入和删除的效率。

6.单链表结构和顺序存储结构有什么区别？

在插入和删除时，顺序存储结构每次都需要移动元素，总时间复杂度为O (n 2)，而链式存储结构在确定I位置的指针后只需要O(1)。因为顺序存储结构需要预先分配存储空间，容易造成空间浪费或溢出。链式存储结构不需要预先分配存储空间，元素数量不受限制。

七、堆栈和队列的区别

Queue是一个线性表，可以在一段插入，在另一端删除。进入队列的元素根据“先进先出”规则处理，在头部删除，在尾部插入。

Stack是一个线性表，只能在页脚插入和删除。附加到广播到堆栈的元素数据，“LIFO”规则处理、插入和删除操作都在堆栈顶部执行。

第一，因为栈入口和栈出口都是在栈顶进行的，所以应该有一个大小变量。

记录当前堆栈的大小。进入堆栈时，大小不能超过数组的长度。

Size+1，弹出时堆栈不为空，size-1。

八、介绍字符串匹配算法:

朴素匹配算法和KMP算法

1.BF算法(BruteForce)

目标字符串T(要匹配的字符串)

模式字符串p(短字符串)

①比较T的第一个字符和s的第一个字符，如果相等，继续t-2VSp-2，如果相等，继续t-3VSp？

②不相等t-1VSp-2，t-2VSp-3。

2.KMP算法:从主串中快速找到子串。

①上下子串的前缀匹配

②找到* * *(取最长且小于比较的上下串长度)前的后缀。

(3)将后面的P子串前缀移到后缀位置。

蛮力算法在模式串中有很多字符，在主串中有几个连续的字符，但是当最后一个字符不相等时，主串的比较位置需要回退。KMP算法在上述情况下，主字符串位置不需要被返回，这样可以大大提高效率。

9.深度优先搜索和广度优先搜索是如何实现的？

深度优先搜索:(1)访问起点v0。

(2)如果v0的第一个邻点没有被访问过，则深度遍历邻点；

(3)如果已经访问了v0的第一个相邻点，则访问它的第二个相邻点进行深度遍历；重复上述步骤，直到访问完所有节点。

广度优先搜索:(1)访问起点v0。

(2)依次遍历v0的所有未访问过的相邻点。

(3)依次访问下一层未访问过的相邻点；重复以上步骤，直到所有顶点都被访问过。

X.如何构造霍夫曼树？

求w的最小和，再求w的最小和；左小右大；施工结束后，左0右1

XI。最小生成树

最小生成树是寻找能连接所有节点的最小边，最短路径是

需要从一个节点到其余节点的最短路径。

最小盐树:

在给定的无向图G=(V，e)，(U，V)表示连接顶点U和顶点V(即)的边，w(u，V)表示这条边的权重。如果有一个子集(即非循环图)其中T是e，所以w(T)是最小值，那么这个T是g的最小生成树。

w(t)=w(u，u)

最小生成树实际上是最小(u，u)et。

prim (PRIM)算法的基本思想是:将顶点设置到其他点权重最小的边上，添加一个新的顶点集，然后寻找边…直到遍历所有点。

从连通网络N={V，E}中的一个顶点u0开始，选择与之关联的权重最小的边，将其顶点添加到顶点集合S中，然后，从所有顶点中选择权重最小的边，其中一个顶点在S集合中，另一个顶点不在S集合中，将对应的顶点添加到S集合中，直到所有顶点都添加到S集合中。

kruskal算法的基本思想是:依次选择最小的边，这样就不存在循环，所有点的遍历结束。

假设有一个有N个顶点的连通网络，N={V，E]。在初始测试中，建立了只有n个顶点且没有边的不连通图T。T中的每个顶点被视为一个连通分支。如果从边集合E中选择具有最小权重的边，并且该边的两个端点不在连通分支中，则将该边添加到T中，否则，将选择具有最小权重的新边，直到所有顶点都在该边中。

十二、最短路径算法

Dijkstra算法的时间复杂度为O(n~2)

飞行时间复杂度为o (n 3)，空间复杂度为o(N2)；

最短路径:用于计算从一个节点到所有其他节点的最短路径。主要特征是从起点向外扩展，直到终点。

Dij astra算法

经典的单源最短路径算法主要基于其动态规划思想。

弗洛伊德算法

寻找任意顶点间最短路径的经典方法是贪心法。

十三、介绍拓扑排序以及如何实现？

拓扑排序的步骤:

(1)在有向图中任意选择一个没有前任的节点输出。

(2)从图中删除节点和与之相连的边。

(3)重复上述步骤，直到输出所有顶点或者当前图中不存在没有前任的顶点，这意味着该图是循环图，因此可以通过拓扑排序来判断一个图是否有循环。

十四。简述各种搜索方法。

搜索分为静态查找表和动态查找表。

静态查找表包括:顺序查找、对折查找和块查找；

动态搜索包括二叉排序树和平衡二叉树。

(1)顺序查找:将待查找的钥匙放入岗哨位置(i=0)，然后将表格中的元素从后向前依次与钥匙进行比较。如果返回值为0，则搜索失败，并且表中没有这样的键值。如果返回值是元素的位置i(il=0)，则搜索成功。设置岗哨位置是为了加快执行速度，其时间复杂度为O(n)。

(2)对折查找:要求查找表为顺序存储结构，有序。如果关键字在表中，则返回关键字的位置。如果关键字不在表中，停止搜索的典型标志是:搜索范围的上限

(3)分块搜索:首先将查找表分成若干个子表，要求每个子表的元素小于下面子表的元素，即保证块是有序的(但不一定在子表中)，每个子表中最大的关键字组成一个索引表，其中也包含每个子表的起始地址。特点是:块间有序，块内无序，块间索引搜索，块内顺序搜索。

(4)二叉排序树:二叉排序树定义为空树或具有以下特征的树:如果树有左子树，则其左子树的所有节点值都小于根值；如果树有右子树，右子树的所有节点值都大于根值；它的左右子树也是二进制排序树。

(5)平衡二叉树:平衡二叉树又称AVL树，要么是空树，要么具有以下特征:他的左子树和右子树的高度差的绝对值不能大于1，他的左右子树也是平衡二叉树。

如果在另一棵平衡二叉树中插入一个节点可能会造成不平衡，那么就要调整树的结构，也就是平衡旋转。包括4中情况:在左子树的左子树中插入节点时向右单向旋转；将节点插入右子树的右子树时，向一个方向向左旋转；左子树的右子树插入一个节点时，先向左旋转，再向右旋转；将节点插入到右子树的左子树时，先向右旋转，再向左旋转。

十五、各种排序算法简介(1)

内部排序包括:插入排序、选择排序、交换排序、归并排序和基数排序。

其中，插入排序包括:直接插入排序、半插入排序和hill排序；

选择排序包括:简单选择排序和堆排序；交换排序包括冒泡排序和快速排序。

(1)直接插入排序(稳定):基本思想是:将序列分为有序部分和无序部分，依次从无序部分中选取元素并与有序部分进行比较，找到合适的位置，将原来的元素后移，将元素插入相应的位置。时间复杂度为O(n~2)，空间复杂度为O(1)。

(2)半插入排序(稳定):基本思想是:设置三个变量，低高mid，和make

Mid=(低+高)/2，如果a[mid]>；键，则让高=mid-1，否则让低=mid+1直到低>；高时停止循环，对序列中的每个元素做上述处理，找到合适的位置将其他元素移回并插入。比较次数为O(nlog2n)，但由于后移，时间复杂度为O(n~2)，空间复杂度为O(1)。好处是比较的次数大大减少。

(3) Hill排序(不稳定):基本思想是:先将序列分成若干个子序列，直接对每个子序列进行插入和排序，当序列基本有序时，再对整个序列进行直接插入和排序。优点是关键字值小的元素可以快速移动到前面，在序列基本有序的情况下直接插入排序的时间效率会大大提高，空间复杂度为O(1)。

(4)简单选择排序(不稳定):基本思想是:将序列分成两部分，每遍在无序部分寻找一个最小值，然后与无序部分的第一个元素交换位置。优点是:实现简单；缺点是:每次行程只能确定一个元素的位置，时间效率低。时间复杂度为O (n 2)，空间复杂度为O(1)。

(5)堆排序(不稳定):有一个任意序列，k1，k2，"

Kn满足以下特征时称为堆:设此序列排列为b。

完全二叉树，该树具有以下特征，树中的任何节点

大于或小于其左右的子树，此树的根节点是最大或

最小值。优点是:对大文件效率明显提高，但对小文件

效率不明显。时间复杂度为O(nlog2n)，空间复杂度为O(1)。

十六、各种排序算法简介(1)

内部排序包括:插入排序、选择排序、交换排序、归并排序和基数排序。

其中，插入排序包括:直接插入排序、半插入排序和hill排序；

选择排序包括:简单选择排序和堆排序；交换排序包括冒泡排序和快速排序。

(6)冒泡排序(稳定):基本思想是:每两次比较元素，按照“先小后大”的规则交换。优点是:每一步不仅可以找到最大的元素放在序列后面，还可以理顺其他元素，如果下一次排序没有交换，可以提前结束排序。时间复杂度为O(n~2)，空间复杂度为O(1)。

(7)快速排序(不稳定):基本思想是:在序列中选择任意一个元素为中心，大于它的元素全部向后移动，小于它的元素全部向前移动，形成左右两个子序列，然后按照上述操作调整子序列，直到所有子序列中只有一个元素，序列有序。优点是:每次行程不仅可以确定一个元素，而且时间效率高。时间复杂度为O(nlog2n)，空间复杂度为O(log2n)。

(8)合并排序(稳定):基本思想是将两个或多个有序表合并成一个新的有序表。时间复杂度为O(n logn)，空间复杂度与要排序的元素个数相同。

(9)基数排序:时间复杂度为:n条记录链式基数排序的时间复杂度为O(d(n+rd))，其中每趟的时间复杂度为O(n)，恢复的时间复杂度为O(rd)。

“先小后大”的规则互换。好处是:每次行程不仅可以找到最大的元素放在序列后面，还可以理顺其他元素，如果下一次行程没有交换，可以提前结束排序。时间复杂度为O (n 2)，空间复杂度为O(1)。