计算机考研 / 保研复试重点整理 - 数据结构篇
date
Jul 6, 2021
Last edited time
Jul 28, 2021 07:57 AM
status
Published
slug
计算机考研保研复试重点整理-数据结构篇
tags
DataStructure
summary
转载, 可能需要背一背这些基本概念
type
Post
Field
Plat
先来一个知识框架图，前方高能预警
好了，看完这个框架，你慌了吗？
大家心里有个数之后，我们开始划重点，都去给我背！
一、什么是数据结构？
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。
数据的逻辑结构包括 4 种，（1）集合：数据元素之间除了有相同的数据类型再没有其他的关系 （2）线性结构：数据元素之间是一对一的关系 （3）树形结构：数据元素之间是一对多的关系 （4）图状结构：数据元素之间是多对多的关系。
物理结构包括顺序存储结构和链式存储结构。
二、解释一下顺序存储与链式存储
顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。
三、头指针和头结点的区别？
头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。
头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。
四、线性结构的特点
（1）集合中必存在唯一的一个 “第一个元素”；
（2）集合中必存在唯一的一个 “最后的元素”；
（3）除最后元素之外，其它数据元素均有唯一的 “后继”；
（4）除第一元素之外，其它数据元素均有唯一的 “前驱”。
五、数组和链表的区别？
从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。
从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。 链表访问必须从前往后依次进行，访问效率较数组来说比较低。
如果从第
i 个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是 O(n)，而单链表来说只需要在第一次寻找 i 的位置时时间复杂度为 O(n)，其余的插入和删除操作时间复杂度均为 O(1)，提高了插入和删除的效率。六、单链表结构和顺序存储结构的区别？
当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为
O(n)，而链式存储结构确定 i 位置的指针后，其时间复杂度仅为 O(1)。由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受限制。七、栈和队列的区别
队列是允许在一段进行插入另一端进行删除的线性表，对于进入队列的元素按 “先进先出” 的规则处理，在表头进行删除在表尾进行插入。
栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按 “后进先出” 的规则处理，插入和删除操作都在栈顶进行。由于进栈和出栈都是在栈顶进行，所以要有一个 size 变量来记录当前栈的大小，当进栈时 size 不能超过数组长度，size+1，出栈时栈不为空，size-1。
八、栈的两个应用：括号匹配和表达式的计算是怎么应用的？（如何实现要会用语言描述）
九、介绍一下字符串匹配算法：朴素的匹配算法和 KMP 算法。（如何实现要会用语言描述）
十、如何构造赫夫曼树？（如何实现要会用语言描述）
十一、介绍一下如何用普里姆算法和克鲁斯卡尔算法构造最小生成树（各方法如何实现要会用语言描述）
普里姆（prim）算法的基本思想为：从联通网络 N={V,E} 中某一顶点 u0 出发，选择与它关联的最小权值的边，将其顶点加入到顶点集 S 中，此后就从一个顶点在 S 集中，另一个顶点不在 S 集中的所有顶点中选择出权值最小的边，把对应顶点加入到 S 集中，直到所有的顶点都加入到 S 集中为止。
克鲁斯卡尔（kruskal）算法的基本思想为：假设有一个有 n 个顶点的联通网络 N={V,E}, 初试时建立一个只有 n 个顶点，没有边的非连通图 T，T 中每个顶点都看作是一个联通分支，从边集 E 中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到 T 中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。
十二、介绍一下求最短路径的算法？（迪杰斯特拉算法和弗洛伊德算法，如何实现要会用语言描述）
迪杰斯特拉算法是经典的单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心层层向外扩展，直到扩展的终点为止。基本思想为：设置并逐步扩充一个集合 S, 存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是 V-S，其中 V 为网中所有顶点的集合。按最短路径长度递增的顺序将 V-S 中的顶点逐个加入 S 中，直到 S 中包含全部顶点。
弗洛伊德算法是经典的求任意顶点之间的最短路径，其边的权值可为负权。 基本思想为：如果 vi 到 v j 存在一条长度为 cos[i][j] 路径，该路径不一定是最短路径，需要进行 n 次试探。首先考虑路径（vi,v1,v j）是否存在，即判断弧（vi,v1）和（v1,v j）是否存在。如果存在，则比较其路径长度，取长度较短者为从 vi 到 v j 的中间顶点的序号不大于 1 的最短路径。再增加一个顶点 v2 进行试探，以此类推，最后求得的是 vi 到 v 之间的最短路径。
十三、介绍一下深度优先搜索和广度优先搜索是如何实现的？
深度优先搜索：（1）访问起始点 v0（2）若 v0 的第一个邻接点没有被访问过，则深度遍历该邻接点；（3）若 v0 的第一个邻接点已经被访问，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止
广度优先搜索：（1）访问起始点 v0（2）依次遍历 v0 的所有未访问过得邻接点 （3）再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止
十四、介绍一下拓扑排序以及是如何实现的？
拓扑排序可以决定哪些子工程必须要先执行，哪些子工程要在某些工程完成后才能执行。把以顶点为活动，边为活动间先后顺序关系的有向图成为顶点活动网，简称为 AOV 网。一个 AOV 网应该是有向无环图，不应该存在回路，如果要存在回路的话则该回路上的所有活动都无法执行。在 AOV 网中如果不存在回路，则可以把所有的活动排列成一个序列，称该序列为拓扑序列，拓扑序列并不是唯一的。形成拓扑序列的过程称为拓扑排序。
拓扑排序的步骤：（1）在有向图中任意选择一个没有前驱的节点输出（2）从图中删去该节点以及与它相连的边（3）重复以上步骤，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图，所以可以通过拓扑排序来判断一个图是否存在环。
十五、各种查找方法（各方法是如何实现的要会用语言描述）
查找分为静态查找表和动态查找表；静态查找表包括：顺序查找、折半查找、分块查找；动态查找包括：二叉排序树和平衡二叉树。
（1）顺序查找：把待查关键字 key 放入哨兵位置（i=0），再从后往前依次把表中元素和 key 比较，如果返回值为 0 则查找失败，表中没有这个 key 值，如果返回值为元素的位置 i（i!=0）则查找成功，设置哨兵的位置是为了加快执行速度，时间复杂度为
O(n)，其特点是：结构简单，对顺序结构和链式式结构都适用，但查找效率太低。（2）折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上界 <= 查找范围的下界。
（3）分块查找：先把查找表分为若干子表，要求每个子表的元素都要比后面的子表的元素小，也就是保证块间是有序的（但是子表内不一定有序），把各子表中的最大关键字构成一张索引表，表中还包含各子表的起始地址。特点是：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。
（4）二叉排序树：二叉排序树的定义为：一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树
（5）平衡二叉树：平衡二叉树又称为 AVL 树，它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于 1，且他的左右子树也都是平衡二叉树。
如果再一个平衡二叉树中插入一个节点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括 4 中情况：在左子树的左子树上插入节点时向右进行单向旋转；在右子树的右子树上插入节点时向左进行单向旋转；在左子树的右子树插入节点时先向左旋转再向右旋转；在右子树的左子树插入节点时先向右旋转再向左旋转。
十六、哈希表的概念、构造方法、冲突的解决办法？
哈希表又称为散列表，是根据关键字码的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加快查找速度，其中映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希函数的构造方法包括：直接定址法，除留余数法，数字分析法，平方取中法，折叠法，随机数法
（1）直接定址法：取关键字的某个线性函数值作为散列地址，H(key)=a*key+b。
（2）除留余数法：取关键字对 p 取余的值作为散列地址，其中 p<m, 即 H(key)=key%p (p<m)。
（3）数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列的地址，适用于所有关键字都已知的情况。
（4）平方取中法：对关键字求平方，再取结果中的中间几位作为散列地址。
（5）折叠法：将关键字分为位数相同的几部分，然后取这几部分的叠加和作为散列地址。适用于关键字位数较多，且关键字中每一位上数字分布大致均匀。
（6）随机数法：选择一个随机函数，把关键字的随机函数值作为散列地址。适合于关键字的长度不相同时。
哈希冲突的解决方法包括：开放定址法和拉链法，当冲突发生时，使用某种探测技术形成一个探测序列，然后沿此序列逐个单单元查找，直到找到该关键字或者碰到一个开放的地址为止，探测到开放的地址表明该表中没有此关键字，若要插入，则探测到开放地址时可将新节点插入该地址单元。其中开放定址法包括：线性探查法，二次探查法，双重散列法
（1）线性探查法：基本思想，探查时从地址 d 开始，首先探查 T[d], 在探查 T[d+1]… 直到查到 T[m-1]，此后循环到 T[0],T[1]… 直到探测到 T[d-1] 为止。
（2）二次探查法：基本思想，探查时从地址 d 开始，首先探查 T[d], 再探查 T[d+1^2],T[d+2^2]… 等，直到探查到有空余地址或者探查到 T[d-1] 为止，缺点是无法探查到整个散列空间。
（3）双重散列法：基本思想，使用两个散列函数来确定地址，探查时从地址 d 开始，首先探查 T[d], 再探查 T[d+h1(d)],T[d+2*h1(d)]…
链接法：将所有关键字为同义词的节点链接在同一个单链表中，若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组，凡是散列地址为 i 的节点均插入到头指针为 i 的单链表中。
十七、各种排序算法（各方法如何实现要会用语言描述）
内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。其中插入排序包括：直接插入排序、折半插入排序、希尔排序；选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。
（1）直接插入排序（稳定）：基本思想为：将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。时间复杂度为：
O(n^2), 空间复杂度为 O(1)（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)。 优点是：比较次数大大减少。
（3）希尔排序（不稳定）：基本思想为：先将序列分为若干个子序列，对各子序列进行直接插入排序，等到序列基本有序时再对整个序列进行一次直接插入排序。优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多，空间复杂度为 O（1）。
（4）简单选择排序（不稳定）：基本思想为：将序列分为 2 部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是：实现简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。时间复杂度为 O（n^2），空间复杂度为 O（1）。
（5）堆排序（不稳定）：设有一个任意序列，k1,k2,…,kn，当满足下面特点时称之为堆：让此序列排列成完全二叉树，该树具有以下特点，该树中任意节点均大于或小于其左右孩子，此树的根节点为最大值或者最小值。优点是：对大文件效率明显提高，但对小文件效率不明显。时间复杂度为 O(nlog2n), 空间复杂度为 O(1)。
（6）冒泡排序（稳定）：基本思路为：每一趟都将元素进行两两比较，并且按照 “前小后大” 的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为 O（n^2）, 空间复杂度为 O（1）。
（7）快速排序（不稳定）：基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。优点是：每一趟不仅能确定一个元素，时间效率较高。时间复杂度为
O(nlog2n), 空间复杂度为 O（log2n）.（8）归并排序（稳定）：基本思想为：把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为 O（nlogn）, 空间复杂度和待排序的元素个数相同。
（9）基数排序：时间复杂度为：对于 n 个记录进行链式基数排序的时间复杂度为 O（d(n+rd)）, 其中每一趟分配的时间复杂度为 O(n), 回收的时间复杂度为 O（rd）。