考研复试问答：

1、算法的特征？

算法的五大核心特征：

1. 有穷性：步骤有限，能在有限时间内结束
2. 确定性：每一步含义唯一，无歧义
3. 可行性：操作可执行，能得到结果
4. 输入：有零个或多个输入
5. 输出：至少有一个输出

2、时间复杂度的概念？

算法基本运算执行次数的数量级，用来衡量算法运行效率随输入规模增长的变化趋势。

3、什么是原地工作？

算法执行时，额外开辟的辅助空间大小是常数，不随问题规模 n 增大而增长

4、线性表的定义？

答：线性表是具有相同类型的 n 个数据元素的有限序列。

5、单链表的建立过程？

• 头插法：新结点先连表头后续结点，再让表头指向新结点（插入在表头后）
• 尾插法：需维护尾指针，新结点接在尾结点后，再更新尾指针指向新结点（插入在表尾）

6、为什么单链表要加头结点？

• 方便单链表的特殊操作（如在第一个结点之前插入结点），保证单链表操作的统一性
• 带头结点的单链表无论是否为空，头指针始终指向头结点，保证对空表和非空表的操作统一性

7、为了区分循环队列的队空和队满，有哪些方法

• 牺牲一个单元来区分队空和队满，队空条件：front==rear；队满条件：(rear+1)% MaxSize==front
• 类型中增加一个表示元素个数的数据成员，队空条件：size==0；队满条件：size==MaxSize
• 类型中增加一个用于标记的数据成员，若因删除导致 front==rear，则队空；若因插入导致 front==rear，则队满

8、树和二叉树的概念？

非空树：

1. 有且仅有一个根结点
2. 除根以外的结点可分为多个互不相交的有限集合，其中每个集合本身又是一棵树，称为根节点的子树。

二叉树：

1. 可以为空二叉树
2. 由一个根结点和两个互不相交的根的左子树和右子树组成，且左、右子树也都是二叉树。

9、二叉树和度为2的有序树的区别：

• 度为 2 的树至少有 3 个结点，而二叉树可以为空。
• 度为 2 的有序树的孩子结点的左右次序是相对于另一孩子结点而言的，而二叉树的孩子结点次序不是相对于另一结点而言，是确定的。

10、二叉树怎么存储？

• 顺序存储：用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点信息。这种方式仅适用于完全二叉树。
• 链式存储：用一个链表来存储一棵二叉树，二叉树中的每个结点用链表的一个链结点来存储。含有 n 个结点的二叉链表中有 n+1 个空链域。

11、完全二叉树的定义？

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

12、二叉树的层次遍历过程？

• 把根结点入队
• 把队头元素出队，访问这个元素
• 依次把该元素的左、右孩子入队
• 重复 2，3 过程，直到队列为空

13、线索二叉树的概念及构造过程？

概念：加上线索的二叉树成为线索二叉树。线索化：在遍历二叉树的过程中，检查当前结点左、右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。

14、树的存储结构有哪些？树、森林与二叉树怎么转换？

答：存储结构：双亲表示法（键值对形式，键为结点编号，值为父结点编号），孩子表示法（指针数组形式，将当前结点的所有孩子结点用链表串起来），孩子兄弟表示法（左孩子右兄弟）
        树转换为二叉树：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，即“左孩子右兄弟”。
        二叉树转换为树：若二叉树非空，则根结点及其左子树为第一棵树的二叉树形式，右子树可视为一个除了第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止。

• 双亲表示法：记父结点编号
• 孩子表示法：每个结点带孩子链表
• 孩子兄弟表示法：左孩子右兄弟

1. 树 ↔ 二叉树转换

• 树转二叉树：左孩子、右兄弟
• 二叉树转树：根 + 左子树是一棵树，右子树是剩下森林，递归处理。

15、二叉排序树的定义？简述其原理及查找过程？

    答：1.若左子树非空，则左子树上所有结点关键字值均小于根节点的关键字值。
        2.若右子树非空，则右子树上所有结点关键字值均大于根节点的关键字值。
        3.左、右子树也都是二叉排序树。
        查找过程：若查找的关键字等于根结点的关键字值，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。

16、什么是平衡因子？什么是平衡二叉树？

    答：某结点的平衡因子是该结点左子树与右子树的高度差。
        平衡二叉树又被称为AVL树，它的左右两个子树都是平衡二叉树且左右两个子树的高度差的绝对值不超过1。

17、哈夫曼树的概念以及哈夫曼树的构造？哈夫曼树的应用？前缀编码和哈夫曼编码的关系？

    答：概念：哈夫曼树是带权路径长度最小的二叉树（树的带权路径长度为所有叶结点的带权路径长度之和）
        构造过程：    1.将n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
                    2.构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左右子树上根结点的权值之和。
                    3.从F中删除刚才选出的两颗树，同时将新得到的树加入F中。
                    4.重复2，3过程，直到F中只剩下一棵树为止。
        应用：哈夫曼编码（长度最短的前缀编码）。

• 哈夫曼树：带权路径长度 (WPL) 最小的二叉树。
• 构造：每次选两棵权值最小的树合并，重复直到只剩一棵树。
• 应用：哈夫曼编码。
• 关系：哈夫曼编码是最优的前缀编码，无歧义、总长度最短。

18、图的相关概念？

    答：有向图：若边集是有向边的有限集合，则图为有向图
        无向图：若边集是无向边的有限集合，则图为无向图
        简单图：1.不存在重复边 2.不存在顶点到自身的边
        简单回路/简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路/简单环。
        完全图：任意两个顶点之间都存在边
        连通：若无向图中从顶点v到顶点w有路径存在，则称v和w是连通的
        连通图：若无向图中任意两个顶点都是连通的，则称图为连通图
        连通分量：无向图中的极大连通子图称为连通分量
        生成树：包含图中所有顶点的一个极小连通子图

---

总结要点

• 有向图：边有方向；无向图：边无方向。
• 简单图：无自环、无重复边。
• 简单回路：除起点终点外，顶点不重复。
• 完全图：任意两点之间都有边。
• 连通：两点间有路径；连通图：任意两点都连通。
• 连通分量：无向图的极大连通子图。
• 生成树：包含所有顶点的极小连通子图。

19、树和图的区别？

• 树是图的子集
• 非空树有且仅有一个根结点，且树的非根节点必定有一个父节点，图没有
• 树是层次结构，图是网络结构

20、图的存储方式有哪些？

答：邻接矩阵，邻接表，十字链表（有向图），邻接多重表（无向图）。（图的邻接矩阵表示是唯一的，且无向图的邻接矩阵一定是一个对称矩阵）

21、广度优先搜索的过程？深度优先搜索的过程？两者的时间复杂度？

21、广度优先搜索的过程？深度优先搜索的过程？两者的时间复杂度？
    答：广度搜索的过程：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2,...,wi，然后依次访问w1,w2,...,wi的所有未被访问过的邻接顶点。
        深度搜索的过程：首先访问起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2...重复上述过程。
        时间复杂度：邻接矩阵O(V^2)，邻接表O(V+E)

22、图的遍历序列是否唯一？

    答：由于图的邻接矩阵表示唯一，邻接表表示不唯一，所以基于邻接矩阵的遍历所得到的dfs序列和bfs序列是唯一的，基于邻接表的遍历所得到的dfs序列和bfs序列是不唯一的。

23、非连通图如何访问每一个结点？

    答：对每个连通分量调用一次DFS/BFS。

24、什么是最小生成树？最小生成树有什么性质？

    答：概念：最小生成树是边的权值之和最小的生成树。
        性质：    1.最小生成树不是唯一的
                2.最小生成树的边的权值之和总是唯一的
                3.最小生成树的边数为顶点数减1

25、怎么构建一棵最小生成树？最小生成树应用在有向图还是无向图中？

答：普里姆算法：先将图中的任意一个顶点放进集合中，然后比较所有集合内的顶点与集合外的顶点连成的线的权值，把那个能连权值最小的线的顶点和相应的边也放进集合里面。重复此步骤，直到所有顶点都加入集合。

克鲁斯卡尔算法：先在图中建立一个空集，然后在集合外选择权值最小的边，若这条边加入集合后不构成回路则将该边和边两端的顶点也加入集合。重复此步骤，直到集合中有 n-1 条边。

有向图的最小生成树叫最小树形图，有避圈法（Kruskal 算法）与破圈法，破圈法：在图中找一个回路，保证图连通的前提下去掉回路中权值最大的的边，重复上述过程，直到图保持连通且没有回路。

1. 最小生成树（普通）

   • 用于无向图。
   • Prim 算法：从点出发，每次加权最小的跨边，扩充点集。
   • Kruskal 算法：从边出发，选权最小且不形成回路的边，凑够 n-1 条。

2. 有向图

   • 不叫最小生成树，叫最小树形图。
   • 方法：避圈法、破圈法（找回路→删回路中权最大边）。

26、迪杰斯特拉算法的过程？

    答：先将图中的某个顶点作为源点放进集合中，然后比较源点到集合外的各个顶点的当前最短路径，把本轮求得的当前最短路径的顶点放进集合，然后更新源点到集合外的各个顶点的当前最短路径。重复上述过程，直到所有顶点都加入集合。
    （新加入一个未收录的顶点时，源点与集合内的顶点的当前最短路径不会更新，即源点与集合内的顶点的当前最短路径不会因为新收录顶点而变得更短）

27、什么是AOV网？什么是拓扑排序？什么是AOE网？什么是关键路径？

    答：AOV网：即顶点表示活动的网络（有向无环图中，顶点表示活动，有向边表示活动之间的前驱后继关系）
        拓扑排序：1.由有向无环图的顶点组成的序列 2.每个顶点出现且只出现一次 3.若顶点A排在顶点B之前，则不存在从顶点B到顶点A的路径
        AOE网：即用边表示活动的网络（带权有向图中，顶点表示事件，有向边表示活动，边的权值表示完成活动的开销）
        关键路径：AOE网（用边表示活动的网络）中，从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径

28、有哪些查找方法？

    答：1.线性结构有顺序查找，折半查找，分块查找（索引顺序查找）
        2.树形结构有二叉排序树，平衡二叉树，b树，b+树
        3.散列结构有散列表

29、折半查找的基本思路？适用范围？判定树高度

    答：基本思路：首先将给定值与表中间位置元素比较，若相等，则查找成功，返回该元素存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续上述查找过程，重复上述过程，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
        适用范围：该查找仅适用于线性表的顺序存储结构，且要求元素按关键字有序排列。
        判定树高：log2(n+1)向上取整

30、分块查找的分块思路？分块查找中索引表的组成？分块查找的过程？

    答：分块思路：块内无序，块间有序
        索引表项：key是各块最大关键字，value是各块中第一个元素的地址
        查找过程：第一步是顺序查找或者折半查找索引表确定待查元素所在的块；第二步是在块内顺序查找

31、b树和b+树的区别？

    答：1.b+树结点的子树个数等于关键字个数，b树结点的子树个数为关键字个数加一
        2.b+树只有叶结点包含信息，非叶结点起索引作用；b树的叶结点不含信息，非叶结点含信息
        3.b+树叶结点和非叶结点关键字可重复，b树中所有结点关键字不重复
        4.b+树的相邻叶结点按大小顺序相互链接，b树没有

32、什么是哈希表？什么是哈希冲突？处理冲突的方法？什么是装填因子？什么是堆积？

    答：哈希表是根据关键字而直接进行访问的数据结构。
        哈希冲突是散列函数可能会把两个或两个以上的不同关键字映射到同一地址的情况。
        常用散列函数：    1.直接定址法
                        2.除留余数法
                        3.数字分析法
                        4.平方取中法
                        5.折叠法
        处理冲突的方法：1.开放定址法（线性探测法，平方探测法，再散列法，伪随机序列法）
                        2.拉链法
        装填因子：散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
        堆积：开放定址法中同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起

33、各种排序的时间复杂度，空间复杂度和稳定性？

    答：                        时间复杂度                        空间复杂度    是否稳定
    直接插入排序    最好O(n)，平均O(n^2)，最坏O(n^2)                O(1)        是
    冒泡排序        最好O(n)，平均O(n^2)，最坏O(n^2)                O(1)        是
    简单选择排序    最好O(n^2)，平均O(n^2)，最坏O(n^2)                O(1)        否
    希尔排序                                                        O(1)        否
    快速排序        最好O(nlogn)，平均O(nlogn)，最坏O(n^2)            O(logn)        否
    堆排序            最好O(nlogn)，平均O(nlogn)，最坏O(nlogn)        O(1)        否
    2路归并排序        最好O(nlogn)，平均O(nlogn)，最坏O(nlogn)        O(n)        是
    基数排序        最好O(d(n+r))，平均O(d(n+r))，最坏O(d(n+r))        O(r)        是

34、快速排序的原理，运用了什么思想？

    答：1.在待排序表L中任取一个元素作为基准，通过一趟排序将待排序表划分为两个部分L1和L2，使得L1中的所有元素小于基准元素，L2中的所有元素大于等于基准元素，则基准元素放在了其最终位置上。
        2.然后递归地对两个子表上述过程，直到每部分只有一个元素或空为止，即所有元素放在了其最终位置上。
        快速排序运用了分而治之地思想（分治法）

35、什么是堆？堆的构造过程？

    答：概念：堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足：任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。若父亲大孩子小，则为大顶堆，若父亲小孩子大，则为小顶堆。
        构造过程：从最后一个结点的父结点开始，若当前结点关键字小于左右孩子中关键字较大者，则发生交换，交换后可能会破坏下一级的堆，此时需要用上述方法调整下一级的堆，直到以该结点为根的子树构成堆为止。之后向前依次对各结点进行上述过程，直到根结点。

36、为什么快速排序比堆排序快？

    答：逆序对：堆排序调整堆的过程中可能增加逆序对，做了很多无效的操作；而快排的每一次交换都离最终目标越来越近
        cache：堆排序的比较的几乎都不是相邻元素，对cache极不友好；相比之下快排比较的相邻元素更多，对cache更友好

37、基数排序的过程？

    答：以最低位优先为例，先对最低位进行一趟分配（考察对应位的值并放入相应的队列）收集（每个队列首尾相连），然后对次低位进行一趟分配收集，重复上述过程，直到最高位。时间复杂度O(d(n+r))

38、外部排序的过程？

    答：1.根据内存缓冲区的大小，将外存上的文件分成若干子文件，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件即归并段重新写回外存
        2.对归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件为止。

39、外部排序优化？

1. 增大归并路数 + 败者树

• 是什么：一次归并更多个有序小段，同时用败者树来减少内部比较。
• 有什么用：减少总的归并趟数，少读少写磁盘，速度更快。

• 2. 减少归并段数 + 最佳归并树

• 是什么：让每个归并段尽量长，并用最佳归并树安排归并顺序。
• 有什么用：让总 I/O 次数最少，磁盘读写最少。

40、求解斐波拉契序列的算法及其时间复杂度？

    答：递归算法：求解F(n),必须先计算F(n-1)和F(n-2)，以此类推，直至必须先计算F(1)和F(0)，然后逆推得到F(n-1)和F(n-2)的结果，从而计算很多重复的值，算法的时间复杂度随着N的增大呈现指数增长，时间复杂度为O(2^n)
        迭代算法：从F(2)开始计算，最后用F(n-1)和F(n-2)两个数相加求出结果，用变量保存上一次计算的结果，这样可以避免大量的重复计算，算法的时间复杂度随着n的增大呈现线性增长，时间复杂度为O(n)
        （递归就是在过程或函数里面调用自身，迭代是利用变量的原值推算出变量的一个新值）

41、单链表就地逆置算法

    答：用指针p扫描原单链表，先将头节点L的next域设置为NULL，而变成一个空链表，然后将*p节点采用头插法插入到L中。

42、链表查询某个元素，平均时间复杂度是多少？

  答：O(n)

43、哨兵的作用？

    答：哨兵用来解决边界问题，在查找方向的尽头设置哨兵免去了查找位置越界的判断

44、在一个老师学生关系中，学生学号与姓名一一对应，问采用什么数据结构通过学号查找姓名的速度最快？

    答：哈希表，索引表

45、折半查找用数组存数据，如果对数据进行删除和插入，就很麻烦，需要移动位置，那你设计一种数据结构解决这个问题？

    答：二叉排序树，平衡二叉树

46、行优先和列优先有什么不同（定义上的不同和效率上的不同）若A与B相乘，选择行优先还是列优先，为什么？

    答：存储模式：行优先的矩阵存储模式为，按照行的格式存储，一行存满了，接着存储第二行，列优先同理，一列存满了，接着存储第二列
        在内存使用上，因为程序局部性原理，连续的存储空间访问更快。
        A采用行优先，B采用列优先。

47、如何寻找两个链表的首个公共结点？

    答：1.先遍历两个链表，得到两个链表的长度，进而计算出长度之差
        2.假设一个链表比另一个长k个结点，先在长的链表上遍历k个结点，之后再同步遍历就可以保证同时到达第一个公共结点

48、bfs和dfs遍历全连通图的生成树的高度？生成树算法？

    答：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。
        一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。

49、怎么用代码实现图的邻接矩阵？邻接表？

    答：二维数组实现图的邻接矩阵
        指针数组实现图的邻接表

50、什么是红黑树？怎么计算高度？

    答：红黑树是一种含有红黑结点并能自平衡的二叉查找树。红黑树的高度是logn

51、为什么基于比较的排序算法的时间复杂度下界是O(nlogn)？

    答：所有的基于比较的排序算法都是基于决策树模型，决策树的高度也就是排序算法比较的最多次数，决策树的高度为log(n!)近似nlogn

52、汉诺塔问题？

    答：将n个盘子从a柱移到c柱，首先将n-1个盘子从a柱移到b柱，然后将第n个盘子从a柱移到c柱，再将n-1个盘子从b柱移到c柱，那么问题变成如何移动n-1个盘子
        依次类推，问题最终变成如何移动2个盘子，即将第1个盘子从a柱移到b柱，第2个盘子从a柱移到c柱，再将第1个盘子从b柱移到c柱
        最后反向逆推可以得到移动n-1个盘子的方法，进而解决移动n个盘子的方法

53、存在环的单链表寻找环的入口点？

    答：1.散列表法：将遍历到的结点放在一个散列表中，如果当前遍历的结点已经存在散列表中，说明有环，且该结点即环的入口。时间:O(n) 空间:O(n)
        2.快慢指针：两个步进不同的指针遍历链表，若链表有环，两指针必然相遇，假设此时show走了n步，fast2n步。接下来，让fast回到链表的头部，重新走，每次步长1，那么当fast和slow再次相遇的时候，就是环路的入口了。时间O(n)，空间O(1)
        （因为fash比slow快n，slow再走n步会回到相遇点，fast从链表首部走n步也会到相遇点，两段路径后面一小段重合，变成了找第一个公共结点的问题）

54、快速排序的优化思路？

    答：快速排序的优化思路是基准元素的选取
        可以选每个子部分中间位置的元素；或者是每个子部分中第一个，最后一个，中间的元素的中位数

55、在数据结构中用什么可以进行优先级的进程调度

    答：大顶堆。可以将优先级作为结点的权值，然后建队，调堆，输出最大权值的进程。

56、顺序查找有序表的过程及其判定树？

    答：顺序查找有序表：在已知表的关键字有序的情况下，通过关键字与key的比较，能快速判断是应该继续查找还是查找失败（n个关键字、n+1个失败结点）

57、已知先序和后序遍历序列可以唯一确定一棵树吗？

    答：不能，但可以确定二叉树中结点的祖先关系，当两个结点的先序序列为XY，后序序列为YX时，则X为Y的祖先
        （先序，中序，后序，遍历过程中经过结点的路线一样，只是访问结点的时机不同）

58、计算二叉树高度的算法？

    答：1.递归、后序遍历结点最大的栈即为树的高度
        2.使用层序遍历，最大层次即为二叉树的高度

59、深度优先搜索形成的是什么？森林唯一么？

（森林，不能说树）（不唯一，因为邻接表可能不唯一

60、怎么取一个单链表的倒数第K个值

    答：两个位置相差k的指针以相同步进遍历单链表，当前者遍历到底，则后者正指向倒数第k个结点

61、Dijkstra算法为什么权值不能为负？

    答：因为源点到集合内的顶点的当前最短路径后续不会更新，只会更新源点到集合外的各个顶点的当前最短路径

62、数组队列的假溢满现象

    答：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低地址还有空位置，这种现象叫做假溢出。

第一章、绪论

  算法的五大特性：有穷性：算法必须能结束，不能死循环，是有限时间、有限步骤能实现的。确定性是指算法每一步都是确定的，有明确含义的，没有歧义的。可行性是指算法每一步操作都是可行的，不是虚幻的。输入是指算法需要的初始数据，有0个或者多个。输出是指算法的输出必须有一个。

算法的五大特性分别是：有穷性，即有限步骤内终止，无死循环；确定性，步骤清晰无歧义；可行性，操作均可实现；输入，可接受 0 个或多个初始数据；以及输出，必须有至少一个结果。

数据结构三要素：

• 逻辑结构：分线性（线性表、栈、队列）和非线性（树、图、集合）。
• 存储结构：即物理结构，决定数据在内存中的存放方式。
• 数据的运算：对数据的操作。

算法的五个特征：有穷性、确定性、可行性、输入、输出。效率度量：用时间复杂度和空间复杂度衡量。

1. 时间复杂度

  大O就是时间复杂度的量级表示，不表示具体算法消耗了多少时间，而表示的是算法耗时增长趋势、增长速度是怎么样的，因为不同的电脑、语言之间都存在性能的差异，而大O表示就可以有效的避开这些的影响，只专注算法本身的优劣。

时间复杂度用大 O 符号表示，它不代表算法的具体耗时，而是描述算法耗时随输入规模的增长趋势。

这种表示方法可以屏蔽硬件、编程语言等外部因素的影响，只专注于评价算法本身的优劣，是衡量算法效率的核心指标。

2. 空间复杂度

  空间复杂度就是算法跑起来的时候，所需要的额外内存，它随着问题规模n变化而变化，用大O来表示。它一般是不算程序本身以及输入数据所占内存，只算额外开的辅助空间所占内存。如果一个算法只用了固定大小的辅助空间，比如开了几个临时变量，这种叫做原地工作，空间复杂度是O(1)。空间复杂度的作用就是评估算法好坏的，时间复杂度相同情况下，空间复杂度越小越好，同时，也可用空间换时间的方式来提高算法效率。

空间复杂度是指算法运行时所需的额外辅助空间，随问题规模 n 变化，用大 O 表示。它不计入程序本身和输入数据的空间，只算临时开辟的辅助空间。若只使用固定大小的额外空间，称为原地工作，空间复杂度为 O (1)。它用于衡量算法空间效率，时间相同时空间越小越好，也可通过空间换时间提升效率

3. 数据的逻辑结构

  数据的逻辑结构表示数据之间的关系，不关心数据在电脑中是怎么存的。先了解了数据的逻辑结构才好选择合适的存储结构存储数据。数据逻辑结构有线性结构和非线性结构。线性结构就像手拉手一样，有一般线性表，受限的线性表如栈、队列和字符串，以及推广的线性表如数组和广义表。而非线性结构有集合、树形结构如一般的树、二叉树，图状结构如有向图、无向图。

数据的逻辑结构是从逻辑关系上描述数据，与数据的物理存储无关，主要分为线性结构和非线性结构两大类。线性结构中数据元素一对一关系，包括线性表、栈、队列、串、数组、广义表等。非线性结构中数据元素一对多或多对多关系，包括集合、树形结构、图状结构。

4. 数据的存储结构

  顺序存储就是逻辑上相邻的元素存储在物理上也相邻的存储单元，它随机存取，查找快，增删慢，数据密度高，内存都用来存数据了，无外存碎片。链式存储是指逻辑上相邻的数据不要求物理上也相邻，数据带有指针指向下一个数据，查找慢，增删快，但是浪费了内存去存储下一个数据的地址。索引存储是指数据随意存放，同时需要建立一个索引表，通过索引项来查找数据，查找快，增删慢需要修改索引表项，同时建立索引表浪费空间内存。散列存储是指通过数据的关键字算出数据的存储地址，增删查改都快，但容易导致冲突，需要花费时间和空间资源去处理冲突。

数据的存储结构是数据在计算机中的物理表示，主要有四种：顺序存储：逻辑相邻、物理相邻，查找快、增删慢。链式存储：逻辑相邻、物理可不相邻，增删快、查找慢。索引存储：建立索引表，查找快，但占用额外空间。散列存储：通过关键字计算地址，存取快，但可能产生冲突。

5. 用循环比递归的效率高吗？

  递归就是函数自己调用自己，把大问题化解为与大问题结构相同的小问题，直到小问题可以直接解决，这样代码结构清晰，但需要用到栈来存储和处理数据，浪费了时间和空间。而循环就只需要套个圈就可以了，重复执行相同的逻辑代码，直到条件不满足为止，结构简单，效率高，不需要额外浪费时间和空间处理栈。但是通常情况下，循环和递归是可以相互交换的，没有决定性的说谁的效率更高，即使递归需要花费时间处理栈的操作，但是通常情况下，这点效率损失是完全可以接受的。

一般情况下，循环效率确实比递归高。递归需要函数调用和系统栈空间，会产生额外开销；而循环只是重复执行代码，没有额外栈开销。但二者通常可以相互转换，递归代码更简洁，在数据规模不大时，效率差异可以忽略。

6. 贪心算法和动态规划以及分治法的区别？

  贪心算法就是只一步一步的看，只看当前的情况，只找局部最优解，不关注长远的情况，不考虑全局最优解，这样它的处理方式简单、处理效率也高，但可能得不到全局最优解。动态规划是把大问题分解为小问题，但为防止重复计算小问题，要把小问题的答案存下来，同时，小问题之间是有依赖的，前一个问题会影响后一个问题，最后从下往上推出最优解，这样动态规划可以保证最优解，但是会浪费空间在存储小问题的答案上。分治法是把大问题分解为多个相互独立且结构与原问题相似的小问题，递归解决小问题后合并结果就得到原问题的答案了，这样把复杂问题简单化很容易实现，但是中间会出现很多重复问题，做了很多无用功。

贪心算法、动态规划和分治法都用于分解问题。贪心是局部最优选择，不回溯，可能得不到全局最优。动态规划分解有依赖的子问题，会记录结果，避免重复计算，能得到最优解。分治法分解相互独立的子问题，递归求解再合并，会存在重复计算。

第二章、线性表

线性表主要分为两种存储方式：

• 顺序存储：用数组实现，称为顺序表，随机访问快，但插入删除效率低。
• 链式存储：用指针或数组实现，包括单链表、双链表、循环链表、静态链表，插入删除灵活，但随机访问慢。

7. 顺序表和链表的比较

  顺序表是元素在逻辑上和物理上都是临近的，而链表是逻辑上邻接但物理上不临接。顺序表可以通过索引下标快速访问一个元素，时间复杂度是O（1），而链表只能顺序访问链表指针顺序访问某个元素，时间复杂度是O（n）。顺序表增删元素，需要移动大量元素，时间复杂度是O(n)，而链表增删元素很快，只需要修改相应指针就可以了，时间复杂度是O(1)。静态分配的顺序表申请空间了，就不能扩张了，可能会造成空间浪费和溢出的问题，动态分配的顺序表可以申请新的空间，但是这个空间需要是连续的地址，可能申请失败，就算申请成功也需要移动大量元素，而链表扩展空间很容易，只需要new一个出来，再修改指针就可以了，很快捷。顺序表的存储密度是很高的，所有存储空间都来存元素了，而链表需要浪费空间来存指针，存储密度更低一些。

顺序表和链表主要从这几方面对比：顺序表逻辑与物理都相邻，支持随机访问，查找快、增删慢，空间连续但扩容不便，存储密度高。链表逻辑相邻、物理可不相邻，只能顺序查找，增删快、查找慢，扩容灵活，但需要额外空间存储指针。

8. 头指针和头结点的区别

  头指针是指向第一个节点的指针，它是链表的入口标识，通过它就可以访问整个链表，它是链表必须需要的，空链表的头指针是指向null的。而头节点是第一个元素节点之前的节点，它的作用是让增加和删除操作统一，不用特殊处理增删时出现空节点或者只有一个节点时的情况，它的数据域可以不用存有效信息，它本身对于链表来说是非必须的。

头指针是指向链表第一个节点的指针，是链表的入口，必须存在，空链表时指向空。

头结点是加在第一个元素节点前的辅助节点，目的是统一插入、删除操作，非必须，数据域可不存有效信息

第三章、栈和队列

栈和队列是操作受限的线性表：

• 栈：后进先出（LIFO），有顺序栈、链栈、共享栈。
• 队列：先进先出（FIFO），有循环队列、链式队列、双端队列。

数组是线性表的推广，包括一维数组和多维数组，多维数组常采用压缩存储，如稀疏矩阵。

9. 栈和队列的区别

  队列是由两个口的线性表，对头删除元素，队尾插入元素，是FIFO先进先出的。而栈是只有一个口的线性表，只能在栈顶进行元素的增删，是LIFO后进先出的。同时，队列可以用数组或者链表来存，数组来存的话，每次操作都要判断队列是否是空的或者满的，链表来存的话，可以通过操作队头和队尾指针分别进行删除和添加操作，而栈一般是用数组来存。队列一般适用于打印机排队、消息队列类似情况，而栈一般用于函数调用、表达式求值等情况。

栈和队列都是操作受限的线性表。栈是后进先出 LIFO，只在栈顶进行插入和删除；队列是先进先出 FIFO，队尾入队、队头出队。栈常用于函数调用、表达式求值，队列多用于排队、消息处理。

10. 共享栈

  共享栈就是两个顺序栈共用同一块连续的内存空间，共享栈本质就是一个一维数组，两个顺序栈的栈底分别在数组的两头，而它们的栈顶都是向数组的中心延伸，这样就可以充分的利用空间，两个顺序栈可以相互协调，直到两个栈的栈顶碰头了，就表明空间用完了。

共享栈是指两个顺序栈共用一段连续的存储空间，两个栈的栈底分别位于数组两端，栈顶向中间延伸。这样能充分利用存储空间，提高空间利用率，只有当两个栈的栈顶相遇时，才表示栈满。

11. 如何区分循环队列是队空还是队满？

  循环队列就是用数组模拟的环状队列，一般情况下，队头指针指向第一个元素的位置，队尾指针指向队尾元素的下一个位置，这时就会队空和队满都是队头指针和队尾指针指向同一个位置的情况。因此，我们可以牺牲一个数组元素不用，这样就可以实现，队空时队头指针与队尾指针指向位置相同，队满时队尾指针指向位置加1取模数组大小等于队头指针指向位置。或者可以用一个变量size来记录循环队列中元素的个数，size==0表示队列为0，size==数组大小表示队满。

循环队列区分队空和队满常用两种方法：一是牺牲一个单元，队空时队头队尾指针相等，队满时尾指针 + 1 取模等于头指针。二是设置计数器 size，size=0 为队空，size 等于数组长度为队满。

12. 栈在括号匹配中的算法思想？

  出现任何左括号时就把它放进栈顶，出现右括号时就它与栈顶元素进行配对，若是一对的就配对成功，删除栈顶元素，若是不配对或者栈空了，就表示配对失败，当表达式遍历完后，检查栈是否为空，为空表示括号配对成功，否则表示还要左括号没配对，配对失败。

遇到左括号入栈，遇到右括号则与栈顶匹配，匹配成功则出栈，失败或栈空则不合法。遍历结束后，栈空则括号完全匹配，否则不匹配。

13. 栈在通过后缀表达式求值的算法思想？

  从左到右遍历后缀表达式，遇到数字就放到栈中，遇到运算符，就从栈顶取出两个数字，先取出来的是右操作数y，后取出来的是左操作数x，把x运算符y的运算结果压入到栈中，遍历完表达式后，栈中唯一的数值就是这个表达式的运算结果。

从左到右遍历后缀表达式，遇到数字入栈；遇到运算符，从栈顶取出两个数，先出栈的是右操作数，后出栈的是左操作数，计算结果再入栈。遍历结束后，栈中唯一元素就是最终结果。

14. 栈在递归中的应用？

  递归就是自己调用自己的编程方法，本质就是把复杂问题层层分解为与原问题结构相似的小问题来解决，可以只用少量代码就实现了，一般效率较低，可用栈来把递归的方式转为非递归的方式。栈在递归中的应用就是，程序运行时，每一次递归调用，都把当前现场信息存入栈中，比如参数、局部变量、返回地址这些存入栈中，等内部递归算完了，就从栈中把现成信息恢复了。

递归的本质是系统栈在支撑。每次递归调用时，系统会把参数、局部变量、返回地址等现场信息压入栈保存；递归返回时，再从栈中恢复现场，继续执行。栈保证了递归能按调用顺序正确返回，也可以用手动模拟栈把递归改成非递归。

15. 队列在层次遍历中的作用？

  层次遍历就是一层一层的遍历，而队列在层次遍历中的作用就是，按顺序记住下一层需要处理的所有节点，保证遍历从上到下，从左到右的顺序，比如二叉树层次遍历就是这样，先存入根节点到队列，然后取出队头元素，把队头元素的左右子节点放入队列，这样循环往复，直到最后队列中没有节点，所有节点都按层次遍历完。

队列在层次遍历里，利用先进先出的特性，按顺序保存下一层要访问的节点。先将根节点入队，然后依次出队访问，再把该节点的左右孩子入队，保证遍历从上到下、从左到右一层一层进行。

16. 队列在计算机系统中的应用？

  队列在计算机系统中，就是按照先进先出规矩排队的等待区，核心的应用场景就两类：一是调和主机和外设的速度不匹配问题，二是解决多用户抢占cpu问题。第一个场景，比如主机和打印机之间，主机把任务直接写入打印机缓冲区也就是队列中就可以不用管了，打印机就按主机给它任务的先后顺序打印就可以了，这一点也契合了队列FIFO先进先出的特点，这样既保证了主机的效率，也保证了打印机打印数据的正确率。第二个场景是，当多个用户都需要cpu时，就进入队列进行排队，按先后顺序使用cpu，队列就保证了先来后到的规则，使用户们能公平有序的使用cpu。

队列在计算机系统中主要利用先进先出的特点，用于缓冲与排队。一是解决主机与外设速度不匹配，比如打印机缓冲区；二是实现多用户、多任务公平调度，按先来先服务顺序使用 CPU，保证有序执行。

17. 矩阵的压缩存储

  矩阵的压缩存储，就是针对那些有很多相同元素或含很多0的矩阵，以更节省空间的方式存储元素，核心思路就是相同的元素包含0，只存一次，不用每个位置都存。比如对称矩阵，对角线的元素是对称相等的，因此只用存一半的元素。比如稀疏矩阵、上三角或者下三角矩阵，就含有大量的0，这样只用存非0元素就可以了。

矩阵压缩存储是为特殊矩阵节省空间的存储方式。对对称矩阵、三角矩阵、稀疏矩阵等，只存储非零元素或重复元素中的一份，不重复存储相同元素和零元素，从而减少存储空间，提高存储效率。

第四章、串

串是由字符组成的线性表，包含主串、子串、串长等基本概念。

存储结构有三种：

• 定长顺序存储
• 堆分配存储
• 块链存储

模式匹配算法主要有：

• 暴力匹配法：简单但效率低
• KMP 算法：利用 next 数组避免主串回溯，效率更高，还可通过 nextval 数组进一步优化

18. 串的模式匹配

  串的模式匹配就是从一个大字符串也就是主串中，找到和一个小字符串也就是模式串相同的字串的过程。一种方式是暴力匹配：从主串的第一个字符开始，一个一个与模式串进行比较，若不等，则模式串往后挪一位重新与主串开始比较，直到找到匹配的子串或者找完主串为止。第二种方式就是KMP算法，它是从分析模式串的结构着手，然后模式串在与主串匹配过程中，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么可以将模式串后滑到与这些相等字符对齐的位置，主串的指针是不用回溯的，并继续从该位置开始比较，这样就避免了很多重复的比较，提高了效率。

串的模式匹配是在主串中查找与模式串相同子串的过程。主要有两种方法：暴力匹配简单但效率低，主串指针需要回溯；KMP 算法利用模式串的前缀后缀信息，让主串指针不回溯，减少重复比较，效率更高。

第五章、树和二叉树

树形结构主要分为二叉树和树与森林两大部分：

• 二叉树：

  • 概念：包括定义和顺序、链式等存储结构。
  • 操作：有先序、中序、后序三种遍历方式，以及线索二叉树来优化遍历。
  • 应用：可作为排序二叉树（升级为平衡二叉树），也可用于构造哈夫曼树实现数据压缩。

• 树和森林：

  • 概念：包括定义和双亲、孩子、孩子兄弟等存储结构。
  • 操作：可与二叉树相互转换，并可进行遍历。
  • 应用：典型应用是并查集，用于处理不相交集合的合并与查询问题。

19. 树与二叉树的相关概念

  树是非线性结构，每一个节点都有一个前件也就是父节点，而没有的前件的节点是根节点，每一个节点可以有多个后件作为节点的子节点，没有后件的节点作为叶子节点。

  树的结构中，每个节点所拥有的子节点数目就是树的度，树中最大的节点的度就是树的度，树的最大层次就是树的深度。

  二叉树是特殊的树，每个节点至多只有两个节点，二叉树是有序树，也就是二叉树的子树有左右之分，不能随意颠倒它们的次序。

  满二叉树是除了最后一层外所有节点都有两个子节点，最后一层也就是达到了该层的节点最大值且最后一层都是叶子节点。

  完全二叉树是除了最后一层每一层节点数都达到了该层节点数目的最大值，最后一层最右侧缺少节点。

  二叉树的存储一般都是链式结构存储，而满二叉树和完全二叉树一般是顺序结构存储。

  二叉树的遍历方式有先序遍历、中序遍历、后序遍历、层序遍历它需要用到队列。

树是一对多的非线性结构，有根节点、子节点和叶子节点，节点的子节点数为度，最大层数为深度。二叉树每个节点最多两棵子树，且是有序树。满二叉树每层都满，完全二叉树仅最后一层右侧缺节点。二叉树多用链式存储，满二叉和完全二叉可用顺序存储。遍历有先序、中序、后序和层次遍历。

20. 如何由遍历序列构造一棵二叉树？

  先序序列和中序序列可以唯一确定一颗二叉树，先序序列的第一个节点就是根节点，然后用这个节点去把中序序列分成两半，左半边是根节点的左子树的中序序列，右半边是根节点的右子树的中序序列，根据这俩个子树的长度去确定先序序列对应的左子树和右子树，如此递归地进行下去，便能唯一的确定这颗二叉树。后序序列和中序序列也可以唯一确定一颗二叉树，后序序列的最后一个节点就是根节点，同样的通过它去把中序序列分成左子树中序序列和右子树中序序列，然后采用类似的方法进行下去，进而得到一棵二叉树。层次序列和中序序列也可也唯一确定二叉树，层次序列的第一个节点是根节点，同样的通过它去分割中序序列，然后再按层次序列顺序找到子树的根节点，如此递归。先序和后序是不能唯一确定的。

中序序列必须配合另一种序列，才能唯一确定一棵二叉树。先序 + 中序、后序 + 中序、层序 + 中序都可以：用另一种序列找根，用中序分左右子树，递归构造。只给先序和后序，无法唯一确定二叉树。

21. 线索二叉树的概念？

  线索二叉树就是在普通二叉树的基础上，把那些空着的指针利用起来了，让每个节点都能直接找到它在某种遍历顺序下的前驱和后继，而不用每次都重新遍历一次。n个节点就有n+1个空指针域，线索二叉树就是把这些空指针域利用起来变成线索，指向它的前驱或者后继。根据遍历的不同，分为前序、中序、后序线索二叉树。

线索二叉树利用普通二叉树中的空指针，将其改为前驱、后继线索，方便直接找到遍历次序中的前后节点，不用重复遍历。n 个节点有 n+1 个空指针域，利用这些空间建立线索，按遍历次序可分为前序、中序、后序线索二叉树。

22. 树的存储结构？

  常见有三种：第一种双亲表示法：用一组连续空间来存储每一个节点，在每一个节点中增设伪节点来指向它的父节点，这样查找当前节点的父节点就很快，而查找子节点就需要遍历整个结构。第二种孩子表示法：每个节点的孩子节点都用单链表链接起来形成一个线性结构，此时n个节点就有n个孩子链表，寻找孩子节点方便，而查找双亲节点就很麻烦。第三种孩子兄弟表示法又称作二叉树表示法，即以二叉链表作为树的存储结构，每个节点包含三个部分内容节点值、指向第一个孩子节点的指针、指向下一个兄弟节点的指针，它最大优势就是把对树的操作转换为了二叉树的操作，它查找父节点很麻烦，但是可以增设一个parent指针指向父节点，这样就方便了。

树的存储结构主要有三种：双亲表示法用数组存储，找双亲快、找孩子慢；孩子表示法用链表存孩子，找孩子方便、找双亲难；孩子兄弟表示法把树转为二叉树，方便操作，可加指针方便找父节点。

23. 二叉排序树：

  二叉排序树也叫二叉查找树，它要么是一个空树，要么需要具备这些特性：若左子树非空，则左子树上的所有节点值要小于根节点的值。若右子树非空，则右子树上的所有节点值要大于根节点的值。同时左右子树也是一棵二叉排序树。根据二叉排序树的特性，左子树节点值<根节点值<右子树节点值，遍历二叉排序树就可以得到一个递增的有序序列。

  二叉排序树的查找：从根节点开始比较，若给定值等于根节点值就查找成功，若小于就往根节点的左子树查找，若大于就往根节点的右子树查找，这是一个递归的过程，直到查找成功或者遍历到头。

  平衡二叉树，它是二叉排序树的升级版，要求任何节点的左右子树高度差不超过1，避免树变成一个链，保证查找效率的稳定性。

二叉排序树也称二叉查找树，左子树节点值小于根节点，右子树节点值大于根节点，中序遍历可得到递增有序序列。查找时从根节点比较，递归进入左或右子树，操作简单。平衡二叉树是其优化，任意节点左右子树高度差不超过 1，保证查找效率稳定。

24. 哈夫曼树和哈夫曼编码

  哈夫曼树是带权路径长度最小的二叉树，也就做最优二叉树。它的构造方法是，每次选择权值最小的两棵树合并，直到只剩一颗树为止。它的特点是权值越小的叶节点，离根越远；没有度为1的节点；总结点数为2n-1；

  哈夫曼编码是一种前缀编码，而前缀编码的意思是没有一个编码是另一个编码的前缀，它是由哈夫曼树生成的。它的特点是频率越高的字符用短编码，频率越低的字符用长编码，平均编码长度最短，能压缩数据。它的编码方式是从根节点到叶子节点的路径就是对应的字符编码，一般往左孩子走标记0，右孩子方向走标记1。

哈夫曼树是带权路径长度最小的最优二叉树，每次选权值最小的两棵树合并，无度为 1 的节点，总节点数为 2n-1。哈夫曼编码是前缀编码，字符频率越高编码越短，可实现数据压缩，由哈夫曼树左右路径 0/1 生成。

第六章、图

图的知识框架可以概括为：

• 定义：由顶点和边组成的非线性数据结构。
• 存储：邻接矩阵、邻接表、邻接多重表、十字链表。
• 遍历：深度优先遍历（DFS）和广度优先遍历（BFS）。
• 应用：
  • 最小生成树：Prim、Kruskal 算法
  • 最短路径：Dijkstra、Floyd 算法
  • 拓扑排序：AOV 网
  • 关键路径：AOE 网

25. 图的一些相关定义

  图是一种由顶点和连接顶点的边组成的数据结构，用来表示事物之间的关系。

  顶点：图中的基本元素，代表一个实体。

  边：连接两个顶点的线，代表实体间的关系。有向边：有方向比如A->B，表示A到B的单向关系；无向边：无方向比如A-B，表示A和B的双向关系。

  度：无向图是顶点连接的边数；有向图分为入度和出度，入度是指向该顶点的边数，出度是从该顶点出发的边数。

  路径：从一个顶点到另一个顶点的边序列。

  连通图：任何两个顶点之间都有路径的无向图。

  强连通图：任何两个顶点之间都有的双向路径的有向图。

  权：边的附加值，代表距离、成本等信息，带权的图称为网。

图由顶点和边组成，分有向图和无向图。无向图中顶点的边数为度；有向图分入度和出度。连通图任意两点可达，强连通图在有向图中双向可达。带权值的图称为网，路径是顶点间的边序列。

26. 图的存储结构

  邻接矩阵：用一个二维数组也就是一个二维矩阵来存边的信息，比如matrix[i][j]表示存的i顶点到j顶点之间是否有边或者存的边的权值，适合存边多的稠密图。

  邻接表：每个顶点都有一个单链表，链表是用来存该顶点相邻接的顶点，适合用来存边少的稀疏图。

  十字链表：专门用来存有向图的优化版邻接表，每条边存一次，方便查找入边和出边。

  邻接多重表：专门用来存无向图的优化版邻接表，也是每条边存一次，相较于邻接表边的删除和修改等操作更高效。

邻接矩阵用二维数组表示，适合稠密图。邻接表用链表存邻接点，适合稀疏图。十字链表优化有向图，方便查入边出边。邻接多重表优化无向图，边操作更高效。

27. 图的遍历

  图的遍历就是从某个起点出发，遍历了图中所有的顶点，且每个顶点只遍历一次，这就需要用到一个visited[]数组来标记已访问过的顶点，这样就可以防止重复访问。

  图的遍历主要有两种方式：广度优先遍历，它就像逐层扫楼一样，先把起点放入队列， 然后取出起点进行访问，同时把它邻接的顶点且未访问过的顶点都放入队列，就像这样不断一层一层向外扩散。深度优先遍历，它就是一条路走到黑的方式进行遍历，从起点出发，随机选择一个未访问过的邻接点就往下一直遍历，直到走到死胡同也就是没有新的问访问的邻接点后，这时就需要往回走，走到新的未访问过的邻接点进行往下遍历。

图的遍历是访问所有顶点且只访问一次，用visited数组标记。广度优先 BFS用队列，一层一层扩散遍历；深度优先 DFS用栈 / 递归，一条路走到底再回溯。

28. 最小生成树和最短路径

  Dijkstra迪杰斯特拉算法， 求单源最短路的算法，从一个起点出来，找到它到其他顶点的最短路径，它是不处理负权边的。

  Floyd弗洛伊德算法，它是求任意顶点之间的最短路径问题，其边的权值可以为负值，时间复杂度为O（n^3），空间复杂度为O（n^2）。

  Prim普里姆算法，用来求最小生成树的算法，从一个点开始，并且把它放到一个集合中，每次选择当前集合到外部的最短边，把所有点连成一个总长度最短的网。适合边多的稠密图。

  Kruskal克鲁斯卡尔算法，也是用来求最小生成树的算法，把所有边按长度进行排序，从最短的边开始选，只要这条边不会让初始是只有点的原图形成环，就把它加进去，直到所有点都连通。适合边少的稀疏图。

最短路径：Dijkstra求单源最短路径，不支持负权边；Floyd求任意两点最短路径，时间复杂度 O (n³)。最小生成树：Prim从点出发，适合稠密图；Kruskal按边排序加边，不形成环，适合稀疏图。

29. 关键路径

  关键路径是在项目管理的有向图中，从起点到终点的所有路径中最耗时的路径，它决定了整个项目的最短完成时间，而在该路径上的活动就是关键活动，它们是丝毫不能拖延的，否则就会使整个项目的完成时间拖延。

  AOV图（顶点表示活动），顶点表示具体的活动，边表示活动的先后顺序，它解决的是哪些活动先完成，哪些活动后完成的逻辑顺序问题。

  AOE图（边表示活动），边表示活动并且标注了活动耗时，用顶点表示事件，它解决了项目多久完成，哪些活动是关键活动的问题，关键路径就是在AOE网中找的。

关键路径是AOE 网中从起点到终点最长的路径，决定项目最短完成时间，路径上活动为关键活动，不可拖延。AOV 网用顶点表示活动，解决活动先后次序；AOE 网用边表示活动，求工期与关键路径。

第七章、查找

查找按结构分三类，核心是平均查找长度：

1. 线性结构：静态查找含顺序、折半（有序）、分块查找。
2. 树形结构：动态查找有二叉排序树、平衡二叉树，及适合磁盘的 B 树、B + 树。
3. 散列结构：即散列表，核心解决哈希冲突，需做性能分析。

30. 对各种查找方法的概括？

  查找分为静态查找和动态查找，静态查找有顺序查找、二分查找、分块查找；动态查找有二叉排序树、平衡二叉树；

  顺序查找：现在i=0的位置上放置一个哨兵也就是查找的关键字的值，然后从后往前进行查找，查找到哨兵为止就说明查找失败了返回0，否则就是查找成功了返回查找成功的位置，它的时间复杂度是O（n），它的特点是结构简单，对顺序存储和链式存储都是适用，缺点是效率较低。

  二分查找：二分查找前提是数据已经排好序且是顺序存储结构，每次查找可以排除一半的数据，查找效率高但查找要求也高。

  分块查找：把查找表分为多个子表，前面子表所有的元素值都要比它后面子表的所有值小，保证块间有序，然后把各子表的最大关键字构成一张索引表，同时表中还包含了各子表的起始地址。它

的特点就是块间有序，块内无序，块间进行索引查找，块内进行顺序查找。

  二叉排序树：二叉排序树是要么是空树要么就是一棵遵循如下规则的树，该树存在左子树时，它的左子树上所有节点值都比根节点值小，存在右子树时，它的右子树的所有值都比根节点值大。在查找过程中，就是从根节点值开始比较，比它小就往左孩子方向走，比它大就往右孩子方向走，循环如此，直到找到关键字或者走到底也表示查找失败。它也可以在查找过程中，增删节点但需动态维护树，保证树一直都是遵循二叉排序树的规则的。

  平衡二叉树：它是二叉排序树的升级版，它除了二叉排序树的要求，还需要任何节点的左右子树的高度差绝对值不能超过1，这样就可以避免二叉树变为一条链，同时查找效率既高也稳定。它也可以进行增删元素，但当树的失衡时，就需要用到4种旋转进行调整了，保证满足平衡二叉树的规则。

查找分静态和动态两类：静态：顺序查找简单通用、效率 O (n)；二分查找需有序 + 顺序存储，效率高；分块查找块间有序、块内无序。动态：二叉排序树左小右大，可动态增删；平衡二叉树高度差≤1，避免链化，查找更稳定。

31. B 树和 B + 树

  B树是多路平衡二叉查找树，所有关键字都分散在整棵树的节点中，包括叶节点和非叶节点，且叶节点在最后一层，保证树的平衡。它是比如m阶B树是节点最多存m-1个关键字，m个子树；非根非叶节点至少存m/2向上取整-1个关键字，根节点最少两个子树。它的特点是查找时查找到关键字就结束，或者查找到叶节点位置，叶节点是空指针实际上，它标记查找失败的意思。

  B+树是应数据库所需而出现的一种B树的变形树，一棵m阶B+树满足如下规则：所有关键字和数据指针都只存在叶节点中，非叶节点只存子节点中的最大关键字和子节点的指针，仅作索引的作用。同时，叶节点是按关键字大小进行排序好的，且用链表进行连接起来，它是支持范围查找的。

它的节点子树数目=关键字数。非根内部节点关键字的范围是m/2向上取整到m

  它们俩的主要差异：B+树中，非根内部节点的关键字范围是m/2向上取整到m，而B树是m/2向上取整-1到m-1;同时，B+树的关键字树是等于子树的数目的，而B树是关键子数目=子树数目-1。除此，B+树是关键字数据都存在叶节点中，而B树是所有节点都存有关键字数据信息，同时它的叶节点包含了所有关键字的信息，其中也包含了所有非叶节点中关键字。

B 树是多路平衡查找树，关键字分布在所有节点中，关键字数 = 子树数 − 1。B+ 树关键字只在叶子节点，非叶子节点仅作索引，叶子节点有序链表相连，支持范围查找，关键字数 = 子树数。B+ 树更适合数据库与文件系统。

32. 哈希表的概念、哈希函数的构造方法、哈希冲突的解决办法

• 哈希表（散列表）：

  • 本质：“关键字 → 数组下标” 的直接映射，像给每个数据配了个 “专属储物柜编号”，不用挨个找，直接按编号取。
  • 核心：哈希函数（映射规则）+ 数组（存储位置）。

• 哈希函数（映射规则）：

  • 作用：把任意长度的关键字，变成数组下标，让数据能直接定位。
  • 6 种构造方法：
    • 直接定址：H(key)=a*key+b，简单直接，适合关键字连续。
    • 除留余数：key%p，最常用，p 选质数能减少冲突。
    • 数字分析：挑关键字里分布均匀的几位当下标。
    • 平方取中：关键字平方后取中间几位，打散分布。
    • 折叠：关键字分段相加，适合长关键字。
    • 随机数：用随机函数，适合关键字长度不一。

• 哈希冲突（两个数据抢同一个储物柜）：

  • 原因：关键字无限，数组有限，必然有碰撞。
  • 4 种解决办法：
    • 线性探查：往后找下一个空柜子，简单但容易 “扎堆”。
    • 二次探查：按平方步长往后找，减少扎堆但不能遍历全表。
    • 双重散列：用第二个哈希函数算步长，减少扎堆。
    • 拉链法：同一个柜子里挂个链表，所有冲突数据都存在这个链表中，最常用（如 Python 的 dict）。

哈希表是通过哈希函数将关键字映射为地址，实现快速查找。哈希函数常用：直接定址、除留余数、数字分析、平方取中、折叠、随机数法。冲突解决：线性探查、二次探查、双重散列、拉链法。

第八章、排序

排序的核心是时间复杂度、空间复杂度和稳定性：

• 内部排序：

  • 插入排序：直接插入、折半插入（稳定，O (n²)）；希尔排序（不稳定）。
  • 交换排序：冒泡排序（稳定，O (n²)）；快速排序（不稳定，平均 O (nlogn)）。
  • 选择排序：简单选择、堆排序（均不稳定，堆排序 O (nlogn)）。
  • 归并排序：稳定，O (nlogn)，需 O (n) 空间。
  • 基数排序：稳定，按位排序。

• 外部排序：主要采用多路归并排序，处理内存装不下的大数据。

33. 对各种内部排序的概括与总结

  内部排序就是把一堆乱序的数据，按大小排成有序的序列。有插入排序、选择排序、交换排序、归并排序、基数排序。

  插入排序包括，直接插入：一个数一个数往前面比，找到合适位置插入进入，时间复杂度O(N^2),空间复杂度O(1)，稳定排序算法；折半插入：用二分法快速找到合适位置插入，时间复杂度O（N^2），但是比较次数相较直接插入更少了，空间复杂度O（1）；希尔排序：先分好组，每组插好，最后整体再直接插入排序一次，这样更快，空间复杂度O(1),不稳定。

  选择排序包含：简单选择：挨个找最小的，放到前面，时间复杂度O(N^2),空间复杂度O(1),不稳定；堆排序：用堆这种结构，高效地挑出最大或者最小的数，时间复杂度O(NlogN)，空间复杂度O（1），不稳定；

  交换排序包含：冒泡排序：像气泡一样，大的慢慢浮出水面，时间复杂度O（N^2），空间复杂度O（1）,稳定；快速排序：选一个基准，比它小的放左边，比它的大放右边，再递归排两边的数，最坏时间复杂度O（N^2），平均时间复杂度O（NlogN），空间复杂度O（logN）,不稳定；

  归并排序：把数据拆分成小块，每块排好，再一块块的合并成有序整体，时间复杂度O（NlogN）,空间复杂度（N），稳定。

  基数排序：适合整数、字符串可按位处理的数据，稳定且效率高，时间复杂度O(d(n + r)),空间复杂度O（n + r ），稳定。

内部排序分五类：插入：直接、折半、希尔，前两者稳定 O (n²)，希尔不稳定。选择：简单选择 O (n²)，堆排序 O (nlogn)，均不稳定。交换：冒泡稳定 O (n²)，快排平均 O (nlogn) 不稳定。归并：O (nlogn)，稳定，需 O (n) 空间。基数：按位排序，稳定，效率高。