保研复试——数据结构

type

status

date

slug

summary

专业课复习-数据结构

1.哈夫曼编码，哈夫曼树，等长编码

在含有n个带权叶结点的二叉树中，带权路径长度（）最小的二叉树称为哈夫曼树，也成为最优二叉树。

哈夫曼树的构造过程：

将n个节点分别作为n棵仅含一个结点的二叉树，构成森林F；

构造一个新结点，从F中选取两颗根节点权值最小的树作为新结点的左、右子树，并将新结点的权值置为左、右子树上根结点的权值之和；

从F中删除刚才选中的两棵树，同时将新得到的树加入F中；

重复步骤2和3，直到F中只剩下一棵树。

在数据通信中，若对每个字符用相等长度的二进制表示，称这种编码方式为固定长度编码,若允许对不同字符用不等长的二进制位表示,则这种编码方式称为可变长度编码，对出现频率高的字符赋以短编码，对出现频率低的字符赋以长编码，起到压缩数据的效果。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。从哈夫曼树到哈夫曼编码：首先，将每个出现的字符当作一个独立的结点，其权值为它出现的频度，构造哈夫曼树。将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为0表示“转向左孩子”，标记为1表示“转向右孩子”。

2.快速排序，堆排序，基数排序和归并排序

快速排序：

基本思想是分治法：在待排序表L[1...n]中任取一个元素pivot 作为枢轴（或称基准，通常取首元素），通过一趟快速排序将带排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中的所有元素小于pivot，L[k+1...n]中的所有元素大于或等于pivot，则pivot放在其最终位置L(k)上，这个过程称为一个划分。每次划分可以确定一个元素的位置。然后分别递归地对两个子表重复上述过程，直到每部分内只有一个元素或空为止。

有很多方法可以提高算法的效率：一种是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为枢轴元素；或者随机地从当前表中选取枢轴元素，这样可以使得最坏情况在实际排序中几乎不会发生。

堆排序：

构建最大堆：将待排序的序列构建成一个最大堆。最大堆的定义是，父节点的值大于或等于其子节点的值。通过从最后一个非叶子节点开始，依次向上调整每个子树，使得整个序列满足最大堆的性质。

堆排序：将最大堆的根节点（即序列中的最大元素）与最后一个元素交换位置，并将序列长度减一。交换后，原最大元素位于序列的最后位置。然后对剩余的元素重新进行最大堆调整。重复执行这个过程，直到序列长度为1，即完成排序。

归并排序：

一种基于分治法的经典排序算法。它的基本思想是将待排序的序列划分成两个子序列，分别对这两个子序列进行递归排序，然后将两个有序的子序列合并成一个有序的序列。

分解：将待排序的序列递归地分解成较小的子序列，直到每个子序列只有一个元素，即认为这些子序列是有序的。

合并：将两个有序的子序列合并成一个有序的序列。合并过程中，比较两个子序列的首个元素，将较小（或较大）的元素放入合并后的序列中，然后将相应子序列的指针后移，重复该过程，直到一个子序列的元素全部放入合并后的序列中。

递归：对合并后的序列重复进行分解和合并操作，直到整个序列排序完成。

基数排序：

非比较型的整数排序算法，根据元素的位值将待排序的数字序列分配到不同的"桶"中，然后按顺序收集这些桶中的元素，从而完成排序。包括分配和收集两个步骤。

3.排序算法性能比较

插入排序：直接插入排序，折半插入排序，希尔排序

直接插入排序：时间复杂度，空间复杂度，稳定算法
折半插入排序：时间复杂度，空间复杂度，稳定算法
希尔排序：当n在某个范围时，时间复杂度，最坏情况下为，空间复杂度，不稳定算法

交换排序：冒泡排序，快速排序

冒泡排序：时间复杂度，空间复杂度，稳定算法
快速排序：时间复杂度，空间复杂度（栈的深度为O(logn)），不稳定算法

选择排序：简答选择排序，堆排序

简单选择排序：时间复杂度，空间复杂度，不稳定算法
堆排序：时间复杂度，空间复杂度，不稳定算法

归并排序：时间复杂度，空间复杂度，稳定算法

基数排序：时间复杂度（d趟分配和收集，一趟收集需要O(r)，一趟分配需要O(n)），空间复杂度，稳定算法

4.散列表，哈希查找与二分查找

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(Key)=Addr（数组下标、索引和内存地址等）。散列表建立了关键字和存储地址之间的一种直接映射关系。

常用的散列函数：

直接定址法：

除留余数法：，关键在于选好质数p

数字分析法：选取数码分布较为均匀的若干位作为散列地址

平方取中法：选取关键字的平方值的中间几位作为散列地址

冲突处理方法：

开放定址法：

线性探测法：发生冲突时顺序查看下一个单元，直到找到一个空闲单元
平方探测法：，但是不能探测到所有单元，但至少能够探测到一半单元。
双散列法：
伪随机法：

拉链法：将冲突的关键字用线性链表存储。

散列表的平均查找长度依赖于散列表的填装因子，，不直接依赖于n或者m。直观来看，填装因子越大，发生冲突的可能性越大，反之发生冲突的可能性越小。

5.图的基本概念

简单图：不存在重复边，不存在顶点到自身的边

完全图（简单完全图）：有条边的无向图

连通图：图G中任意两个顶点都是连通的（有路径）

强连通图：有向图中，任意两个顶点u,v，存在u到v的路径，也存在v到u的路径，则此图为强连通图

简单路径：在路径序列中，顶点不重复出现的路径。除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。

6.图的存储方式

邻接矩阵：适合于稠密图，空间复杂度为

邻接表：适合于稀疏图，对于无向图复杂度为，有向图为

十字链表：当需要同时考虑顶点的出度和入度时，适用于大规模有向图，。

邻接多重表：无向图的链式存储结构。

7.图的最短路径算法（Dijkstra算法和Floyd算法）

Dijkstra算法：求解单源点最短路径的经典算法，基于贪心策略，在加权有向图或无向图中找到从源点到其他结点的最短路径。基本思想是从源节点开始，逐步扩展到其他节点，通过不断选择当前距离源节点最近的节点，更新其相邻节点的距离值，直到找到源节点到其他节点的最短路径。具体步骤如下：

初始化：集合S初始化为{0}，dist[]的初始值dist[i]=arcs[0][i], i = 1,2,...,n-1。

从顶点集合V-S（未访问过的顶点集合）中选出，满足，就是当前求得的一条从出发的最短路径的终点，令。

修改从出发到集合V-S上任意一个顶点可达的最短路径长度：若dist[j]+arcs[j][k] < dist[k]，则更新dist[k]=dist[j]+arcs[j][k]。

重复步骤2，3共n-1次，直到所有的顶点都包含在S中。

时间复杂度为。

Floyd算法：求解每对顶点间的最短路径。基本思想是通过动态规划的方式逐步更新节点之间的距离，以求得最短路径。时间复杂度为。注意，如果图中存在负权回路，则Floyd算法无法正确工作，因为负权回路中存在无限小的路径，算法无法收敛。实际使用中可以将算有权值加上一个数，将其转化为正权值。

8.图的最小生成树算法（Prime算法和Kruskal算法）

Prime算法：贪心算法，基本思想是从一个起始顶点开始，逐步扩展生成树，每次选择当前生成树到非生成树顶点的最小权重边，直到生成树包含了图中的所有顶点为止。

初始时从图中任取一顶点加入树T，此时树中只有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的定点数和边数都增1。以此类推，直到图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。

算法复杂度为，不依赖于，因此它适用于求解稠密图的最小生成树。

Kruskal算法：按权值的递增次序选择合适的边来构造最小生成树。

初始时只有n个顶点而无边的非连通图，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。依次类推，直到T中所有顶点都在一个连通分量上。

算法复杂度为，适合于边稀疏而顶点较多的图。

9.图的遍历

广度优先搜索先访问离起点近的顶点，然后访问远的顶点。图的遍历，图最短路径，连通性检测，网络广播等可以通过队列来实现。

选择一个起始顶点，将其标记为已访问，并将其加入到一个队列中。

从队列中取出一个顶点，访问该顶点，并将其所有未访问的邻接顶点加入队列。

重复执行步骤2，直到队列为空。

深度优先搜索从图的某个起始顶点开始，沿着一条路径一直深入直到无法继续或达到目标顶点，然后回溯到前一个节点，继续探索其他路径，直到遍历完整个图。可以实现图的遍历，拓扑排序，环检测，连通性检测等。可以通过递归或者栈来实现。

选择一个起始顶点，将其标记为已访问。

访问当前顶点，并遍历其未访问的邻接顶点。如果存在未访问的邻接顶点，则选择其中一个作为下一个当前顶点，并重复步骤2。

如果当前顶点没有未访问的邻接顶点，或者已经遍历了所有的邻接顶点，则回溯到上一个顶点，并继续探索其他未访问的邻接顶点。

重复执行步骤2和步骤3，直到遍历完整个图。

10.平衡二叉树、完全二叉树

平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过1。

完全二叉树：当且仅当每个结点都与高为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。

二叉排序树：左子树上所有结点的关键字均小于根结点的关键字，右子树上的所有结点的关键字均大于根结点的关键字，左子树和右子树又各是一颗二叉排序树。

11.二叉树的遍历

先序遍历：访问根节点，先序遍历左子树，先序遍历右子树。

中序遍历：中序遍历左子树，访问根结点，中序遍历右子树。

后序遍历：后序遍历左子树，后序遍历右子树，访问根结点。

三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。时间复杂度都为。中序+先序、中序+后序、中序+层序可以唯一确定一颗二叉树。

12.栈、队列、循环队列

栈：后进先出（Last-In-First-Out，LIFO）原则，操作受限的线性表，只能在一端进行插入和删除。栈的应用有函数调用，表达式求值，括号匹配，编译器和解释器中的语法分析和运行时环境管理等。

队列：先进先出（First-In-First-Out，FIFO）原则，操作受限的线性表，只能在表的一端进行插入操作（入队），在另一端进行删除操作（出队）。队列的应用有线程调度，网络通信，缓冲区管理，广度优先搜索，打印机。

循环队列：当队列的尾部到达数组的尾部时，可以循环回到数组的开头继续存储，形成循环的效果，避免数据迁移和浪费。