计算机考研复试常问问题 数据结构篇

第一章 绪论

1、时间复杂度

• 时间复杂度：算法执行时所需要的计算工作量，与整个算法的执行时间和基本操作重复的次数成正比。
• 一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)。
• O：T(n)的数量级。【数量级】数量的尺度或大小的级别,每个级别之间保持固定的比例。

2、空间复杂度

• 空间复杂度：算法执行时所耗费的存储空间。主要是指对数据进行操作所使用到的额外辅助空间。
• 算法原地工作：算法所需要的辅助空间为常量，即O(1)。

3、用循环比用递归的效率高吗？

• 各有优缺点
• 递归
  • 优点：代码简洁。
  • 缺点：递归调用次数过多，增加额外的堆栈处理，可能产生堆栈溢出。
• 循环
  • 优点：结构简单，速度快。
  • 缺点：有些问题难以解决，例如汉诺塔。

第二章 线性表

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

• 头指针：指向第一个结点存储位置的指针，具有标识作用，是链表的必要元素，无论链表是否为空，头指针都存在。
• 头结点：放在第一个元素结点之前，便于在第一个元素结点之前进行插入和删除操作，不是链表必须的，也不存储任何信息。

第三章 栈和队列

1、什么是栈？

• 只允许在表尾进行插入和删除操作，对插入到栈中的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行。

2、什么是队列？

• 只允许在表的一端进行插入另外一端进行删除操作，对插入到队列中的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。

3、如何区分循环队列是队空还是队满？

• 普通情况下，循环队列队空和队满的判定条件是一样的。
• 方法一：牺牲一个位置来判断队空和队满。
• 方法二：增加一个表示元素个数的数据成员。

第四章 串

1、串的匹配模式

• 暴力模式匹配算法：从主串的第一个字符开始，与子串的第一个字符比较，如果相同则继续比较下一个字符；如果不同则从主串的第二个字符开始，重新和子串的第一个字符比较，直到最后看是否匹配成功。
• KMP算法：当匹配失败时，如果已经匹配的相同前缀序列中有某个后缀正好是子串的前缀，则将子串向后滑动到与这些字符对齐的位置，主串的指针不变，并从该位置开始比较。

第五章 树与二叉树

1、二叉排序树

• 满足以下性质的二叉树：
  • 若左子树不空，则左子树上所有结点的值均小于根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于根结点的值；
  • 左右子树又分别是二叉排序树。

2、二叉排序树的查找过程

• 从根结点开始，若根结点的关键字等于查找的关键字，则查找成功；
• 若小于根结点的关键字，则递归查找左子树；
• 若大于根结点的关键字，则递归查找右子树；
• 若查找到叶子结点还是不相等，则查找失败。

3、平衡二叉树

• 一种特殊的二叉排序树，左右子树的高度差的绝对值不超过1，且左右子树都是平衡二叉树。
• 平衡因子：左子树的高度减去右子树的高度。

4、哈夫曼树

• 定义
  • 给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度最小，则称为哈夫曼树。
  • 从树的根结点到任意结点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。
  • 所有结点的带权路径长度之和称为该树的带权路径长度。
• 构造
  • 把n个结点视为仅有一个结点的二叉树，构成森林F；
  • 从F中选取两个根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树根结点的权值之和；
  • 从F中删除刚才选取的两棵树，并将新的树加入F中；
  • 重复上述操作，直到F中只剩一棵树为止。
• 特点
  • 权值越大的结点，离根结点越近。
  • 树中没有度为1的结点。

第六章 图

1、图的相关概念

• 图：由结点的有穷集合V和边的集合E组成。
• 有向图：若E是有向边（弧）的有限集合时，则为有向图。
• 无向图：若E是无向边（边）的有限集合时，则为无向图。
• 完全图：无向图中每一个顶点与其他所有顶点之间都存在边。
• 连通图：无向图中任意两个顶点都是连通的。
• 连通分量：无向图中的极大连通子图。
• 强连通图：有向图中，如果一对顶点之间有相互到达的路径，则这两个顶点是强连通的。图中任意一对顶点都是强连通的，则称该图为强连通图。
• 强连通分量：有向图中的极大强连通子图。
• 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。
• 生成森林：非连通图中，连通分量的生成树构成生成森林。
• 简单路径：顶点不重复的路径。
• 简单回路：除第一个和最后一个顶点外，其余顶点不重复出现的回路。

2、图的存储方式

• 邻接矩阵
  • 图的顺序存储结构。
  • 用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。
• 邻接表
  • 图的链式存储结构。
  • 对图中每一个顶点建立一个单链表，每个单链表中的结点与该顶点直接相邻。
• 十字链表
  • 有向图的另一个链式存储结构。
• 邻接多重表
  • 无向图的另一种链式存储结构。

4、图的遍历

• 深度优先遍历
  • 首先访问图中某一起始顶点v1，然后由v1出发，访问与v1相邻且未被访问的任一顶点v2，再访问与v2相邻且未被访问的任一顶点v3，重复上述操作。
  • 当不能继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问，则从该顶点开始继续上述操作，直到图中所有顶点都被访问。
• 广度优先遍历
  • 首先访问图中某一起始顶点v1，然后依次访问与v1相邻的所有未被访问过的顶点v2、v3...。
  • 再从这些被访问过的v2、v3...出发，依次访问它们所有未被访问过的邻接结点，直到图中所有顶点都被访问。

5、最小生成树

• 普利姆（Prim）算法（选点）
  • 从图中任取一顶点加入树T，此时树T中只有一个顶点；
  • 然后选择一个与当前树T的顶点集合距离最近的顶点，并将其顶点和对应的边加入树T；
  • 以此类推，直到图中所有顶点都加入树T。
• 克鲁斯卡尔（Kruskal）算法（选边）
  • 初始时为n个顶点而无边的非连通图T，每个顶点自成一个连通分量；
  • 不断选取权值最小且未被选取过的边，若该边两端的顶点属于不同的连通分量，则把该边加入T，否则选取下一条权值最小且未被选取过的边；
  • 以次类推，直到T中所有顶点都在一个连通分量上。

6、最短路径

• 迪杰斯特拉（Dijkstra）算法
  • 单源最短路径，即求图中某一顶点到其他顶点的最短路径。
  • 设置一个集合S记录已经求得的最短路径的顶点。初始时把源点放入S中，计算源点到其它顶点的直接路径长度（若有），选择路径最短的顶点加入S，再根据该顶点重新计算源点到其它顶点的路径长度，重复上述操作，直到所有顶点都加入S。
  • 打个比方，A到B的距离是10，A到C的距离是4，C到B的距离是3，则A到B的距离应该修改为7。
• 弗洛伊德（Floyd）算法
  • 求每对顶点间的最短路径。
  • 设置一个n阶方阵A记录每对顶点间的路径长度，其中A[i][j]表示从顶点i到顶点j的路径长度；
  • 初始时，若任意两个顶点之间存在边，则该边的权值设为它们的最短路径；若不存在有向边，则把值设为∞；
  • 之后在原路径中不断加入其他顶点作为中转点。若增加中转点后，得到的路径比原路径长度更短，则修改原路径。

7、关键路径

• 定义：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。
• 关键路径的长度是完成整个工程的最短时间。

第七章 查找

1、查找方法总结

• 顺序查找
  • 把待查找关键字放入哨兵位置（i=0），再从后往前依次比较表中元素。
  • 时间复杂度：O(n)
• 折半查找
  • 要求查找表为顺序存储结构且有序。每次比较中间元素，大了查右边，小了查左边。
  • 时间复杂度：O(log₂n)
• 分块查找
  • 把查找表分为若干块，块间有序，块内无序。
  • 查找时块间进行索引查找，块内进行顺序查找。
• 二叉排序树
  • 时间复杂度：O(log₂n)

2、B树和B+树

• B树：也称为多路平衡查找树，是二叉查找树的一般化，非叶子结点可以有两个或两个以上的子结点。
• B+树：B树的变体形式。
  • 与B树的差异：
    • B+树中，具有n个关键字的结点只含有n棵子树；B树中，具有n个关键字的结点含有n+1棵子树。
    • 同阶下，关键字个数范围不同。B+树中，每个结点（除根节点外）中的关键字个数n的范围是⌈m/2⌉<=n<=m（根节点：2<=n<=m）；B树中，每个结点（除根节点外）中的关键字个数n的范围是⌈m/2⌉-1<=n<=m-1（根节点：1<=n<=m-1）。
    • B+树中，所有非叶子结点仅仅起到索引的作用，叶节点包含了全部关键字；B树中，叶节点包含的关键字与非叶节点包含的关键字不重复。
• 【注】阶：树中结点的最大子结点个数。

3、哈希表

• 概念
  • 通过把关键字码的值映射到表中的一个位置以加快查找速度。
• 哈希函数的构造方法
  • 直接定址法
  • 除留余数法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 随机数法
• 哈希冲突的解决方法
  • 开放定址法
    • 线性探测法
      • 在发生冲突的位置，依次向后循环查找空缺的位置放置。
    • 二次探测法
    • 双重散列法
      • 使用两个散列函数来确定位置
  • 拉链法
    • 将所有关键字为同义词的结点链接到同一个单链表中。

第八章 排序

1、直接插入排序（稳定）

• 基本思想：将序列分为有序部分和无序部分，从无序部分中依次选择元素与有序部分进行顺序比较，找到合适的位置，将原来的元素及其后面的元素向后移，再将元素插入到相应的位置。
• 时间复杂度：O(n²)
• 空间复杂度：O(1)

2、折半插入排序(稳定)

• 基本思想：与直接插入排序相似，但使用折半查找找到适合位置，再将其他元素后移，最后将元素插入到相应的位置。
• 时间复杂度：O(nlog₂n)
• 空间复杂度：O(1)

3、希尔排序（不稳定）

• 基本思想：将序列中相隔某个增量的元素组成一个子序列，对各子序列分别进行直接插入排序，当整个序列的元素基本有序时，再进行一次直接插入排序。
• 空间复杂度：O(1)

4、简单选择排序（不稳定）

• 基本思想：每经过一趟在序列中找一个最小值，然后与序列的第一个元素交换并固定，固定的元素不参与后续比较。
• 时间复杂度：O(n²)
• 空间复杂度：O(1)

5、堆排序（不稳定）

• 分类：大根堆和小根堆。
  • 大根堆：每个结点的值都大于或等于其左、右孩子的值。
  • 小根堆：每个结点的值都小于或等于其左、右孩子的值。
• 基本思想：把序列建成初始堆，输出堆顶元素后，对其重新建堆，再输出堆顶元素，重复操作，直到堆中仅剩一个元素。
• 时间复杂度：O(nlog₂n)
• 空间复杂度：O(1)

6、冒泡排序（稳定）

• 基本思想：从前往后（或从后往前）两两比较相邻元素的值，若为逆序，则交换，直到比较完最后一个元素，固定该元素不再参与后续比较。再从头开始重复上述操作，每轮比较都能选出一个固定的元素。
• 时间复杂度：O(n²)
• 空间复杂度：O(1)

7、快速排序（不稳定）

• 基本思想：在序列中任意选择一个元素作为中心，把比它大的元素移到右边，把比它小的元素移到左边，形成左右两个子序列，再把子序列按上述操作调整，直到所有子序列只有一个元素时即为有序。
• 时间复杂度：O(nlog₂n)
• 空间复杂度：O(log₂n)

8、归并排序（稳定）

• 基本思想：将两个或者两个以上的有序表合并成一个新的有序表。
• 时间复杂度：O(nlog₂n)
• 空间复杂度：O(n)

9、基数排序（稳定）

• 基本思想：按关键字的权重依次进行排序，最后形成一个有序序列。
• 时间复杂度：O(d(n+r)) 
• 空间复杂度：O(r)       【注】n个数、r个队列、d趟分配