《数据结构》划重点笔记

📖 阅读信息

阅读时间约 86 分钟 | 约 17254 字 | 包含 27 行代码

什么是散列表？有哪些重要的解决冲突的方法？什么是装填因子？它对散列表的搜索效率有什么影响？如何计算在散列表上搜索成功或搜索失败时的平均搜索长度？（标红）

• 位置：教材 9.4

• 散列表即哈希表。用于将任意数据映射到连续内存空间里面，具体而言：利用哈希函数 \(h(k_i)\) 将数据 \(k_i\) 映射为内存单元的下标，由此构造的线性表结构即为散列表。

• 解决冲突的方法有多种：

  • 线性探测法：当出现哈希冲突时，一直往后找，直到找到空闲的内存空间。（遇到末尾则从头开始）优点：实现简单；缺点：数据容易堆积，也就是哈希值不同的两个数据要争夺同一个内存空间。
  • 平方探测法：只探测前面和后面的 \(i^2\) 的位置，可以解决堆积问题但是不一定可以探测到所有单元。
  • 其他开放定址法，如伪随机序列法，拉链法。
  • 拉链法：将具有相同哈希值的元素拉成一个链表，而原来的内存空间存放这个链表的头结点。

• 装填因子 \(\alpha\) ：指哈希表装入元素数与原来内存空间大小的比值。

• 装填因子太小，即哈希表空间未能充分利用；太大，则容易产生冲突。

• 计算平均搜索长度：【参考教材例 9.11】对于开放定址法而言：如果搜索成功，取每一个关键字，在构建的哈希表里面模拟一下探测过程，最后把比较次数取一下平均；如果搜索失败，取每一个哈希值，然后按照探测方法直到探测到空位置，记录探测次数取平均值即可。

本知识点易考察综合题、填空题和选择题，考点为计算平均搜索长度。

什么是线性表？它的最主要的性质是什么？

• 线性表是具有相同特性的数据元素的一个有限序列。

• 性质：序列性，存在开始和终端，并且每一个元素都有唯一的前驱和后继元素。

本知识点易考察顺序表和链表进行插入、删除等操作的时间复杂度区别。也可能出判断题辨析线性表、顺序表和链表是上下位概念关系

什么是逻辑结构？什么是数据元素？什么是数据项？什么是数据类型？它们有什么联系？

• 逻辑结构是指数据之间在逻辑上的组织方式，不涉及具体的物理存储细节。

• 数据元素是基本的数据单位，是能被识别和处理的最小数据组织单位。可以理解为一条“记录”或一个“实体”。

• 数据项是数据元素的不可再分的最小单位，是构成数据元素的具体属性。

• 数据类型是对数据项的值及其操作的集合的定义，指定了该数据的存储格式和可进行的操作。

• 例如：

  struct student
  {
      std::string name;
      int age;
  };
  student group[4];
  

  里面的数组可以理解为线性逻辑结构的具体实现方式，数组里面的每一个元素就是数据元素，这每一个元素里面的 name 和 age 项就是数据项，而 student 就是数据类型。

本知识点易考判断题进行概念辨析，或者出送分题。

什么是顺序存储结构？什么是链式存储结构？还有哪些其他存储结构？

• 顺序存储结构：数据存放在连续的内存空间里面，随机访问的时间复杂度为 \(O(1)\)，插入和删除的时间复杂度为 \(O(n)\)。
• 链式存储结构：数据存放在结点里面，每个结点不仅存放数据，还存放指针，用来存储该结点的单个前驱和/或后继，随机访问的时间复杂度为 \(O(n)\)，插入和删除的时间复杂度为 \(O(1)\)。
• 还有栈结构、队列结构、树结构、图结构和索引结构等。

什么是单链表？什么是双向链表？什么是循环链表？怎样在链表上进行插入和删除操作？

• 单链表：只有一个指向后继的指针域的链表。
• 双向链表： 指针域既指向后继又指向前驱的链表。
• 循环链表：头尾节点存在指针域关联形成循环的链表。
• 插入的方法：先取待插入结点，调整其指针域，然后调整原链表里面和该结点相连的结点的指针域。
• 删除的方法同理。

易考点：哪一个选项的代码正确执行了插入/删除操作；或插入/删除操作共需要调整几个指针域。

什么是栈？给定一个入栈序列，如何判断一个出栈序列是否可能？什么是链式栈？跟顺序栈相比，它有什么优缺点？

• 栈：后进先出的数据结构。
• 判定标准：对出栈序列进行模拟，判断有无非栈顶的元素提前出栈。
• 链栈即底层使用链表实现的栈。优点是无需担心栈容量问题，不会浪费空间；缺点是删除和插入元素的常数略大。

已知二叉树的前序序列和后序序列可以恢复一棵二叉树吗？需要满足什么条件才可以呢？如何由给定的条件恢复二叉树（包括所有可能的形状）？（标红）

• 不一定可以。前序序列ULR，后序序列LRU，找到根节点之后，难以划分出左右子树。
• 何时可以？即可以划分出左右子树时，如果每个节点的左右子树大小都相等，那么我们只需要找子列的中点，就可以分开了，此时对应的是满二叉树。
• 如何恢复？遍历所有可能的左右子树分界点，递归检查左右子树是否合法。具体而言：从第一个结点到倒数第二个结点，遍历下标 \(i\) ，假定其是前序序列里面根节点左子树的最后一个结点，在后序序列里面找到它，就分出来左右子树，对这两个子树递归地进行这一操作，如果最终得到了合法的序列，成功恢复了一种可能的二叉树。

树与二叉树有哪些表示方法（如凹入表示、文氏图、广义表等）？树本身还有孩子-兄弟链表示法。如何在特定表示法下直接求取树或二叉树的某些特性（如树高等）？（标红）

• 表示方法：
  • 凹入表示：比如 Linux 里面 tree 命令的输出：

    .
    ├── docs
    │   ├── assets
    │   │   ├── ds-t6.png
    │   │   └── js
    │   │       └── init-highlight.js
    │   ├── benchmark-on-stl.md
    │   ├── css
    │   │   └── codehilite.css
    │   ├── ds-keynote.md
    │   ├── ds-t6.png
    │   ├── ds-write-up.md
    │   ├── index.md
    │   ├── stl-wheels.md
    │   ├── template-on-numeric-ring.md
    │   └── test.md
    ├── mkdocs.yml
    └── themes
        └── js
            ├── katex.js
            └── mathjax.js
    

  • 文氏图：利用圆圈的包含和并列表示树形层级。
  • 广义表：利用括号的嵌套表示层级。如 A(B(C,D),E)
  • 线连图：用线连接结点以直观表示树形结构。
  • 顺序表示：利用 \(2*i\) 和 \(2*i+ 1\) 来表示下标 \(i\) 结点的子节点，用于表示完全二叉树，例如堆。
  • 孩子-兄弟链表示：利用左孩子右兄弟方法将森林和二叉树互相转化。

什么是深度优先遍历DFS？什么是广度优先遍历BFS？针对特定的问题，如何选择使用DFS还是BFS？

• 深度优先遍历是一种用于遍历或搜索树或图的算法。它从根（或任意指定节点）开始，沿着一条路径 尽可能深地 探索每个分支，直到到达叶子节点或不能再深入为止。然后，它回溯（撤销）到前一个未完全探索的节点，并探索另一条路径。

• 工作原理（通常使用 递归 或栈 实现）：

  1. 访问起始节点。
  2. 将起始节点标记为已访问。
  3. 对于当前节点，选择一个未访问的邻居节点。
  4. 如果存在未访问的邻居节点，则对该邻居节点递归调用DFS。
  5. 如果没有未访问的邻居节点，则回溯到前一个节点。
  6. 重复此过程，直到所有可达节点都被访问。

• 特点：

  1. 栈（Stack） 的数据结构特性：后进先出（LIFO）。
  2. 非最短路径算法。
  3. 空间复杂度：对于图来说，最坏情况下可能是 \(O(V+E)\)，其中 \(V\) 是顶点数，\(E\) 是边数；对于树来说，取决于树的深度。
  4. 时间复杂度：\(O(V+E)\)。

• 广度优先遍历也是一种用于遍历或搜索树或图的算法。它从根（或任意指定节点）开始，首先访问其所有直接邻居，然后访问这些邻居的所有未访问邻居，依此类推。它以 “层” 的方式向外扩展。

• 工作原理（通常使用 队列 实现）：

  1. 访问起始节点。
  2. 将起始节点标记为已访问，并将其添加到队列中。
  3. 当队列不为空时，执行以下操作：
     • 从队列中取出（出队）一个节点。
     • 访问该节点的所有未访问的邻居节点。
     • 将这些未访问的邻居节点标记为已访问，并将它们添加到队列中。
  4. 重复此过程，直到队列为空。

• 特点：

• 队列（Queue） 的数据结构特性：先进先出（FIFO）。
• 最短路径算法：在无权图中，BFS能够找到从起始节点到所有其他可达节点的最短路径（按边数计算）。
• 空间复杂度：\(O(V+E)\)，最坏情况下需要存储所有节点和边。

• 时间复杂度：\(O(V+E)\)。

• 如何选择使用DFS还是BFS？

  • 选择DFS的场景：

    1. 查找所有可能的路径/解： 当你需要遍历所有可能的路径或找到所有满足条件的解时，DFS非常适合。例如，回溯问题（如N皇后问题、组合总和）通常使用DFS。
    2. 判断图中是否存在环： DFS可以有效地检测图中的环。当你在DFS遍历过程中遇到一个已经访问过但仍在当前DFS路径上的节点时，就表示存在环。
    3. 拓扑排序： 对于有向无环图（DAG）的拓扑排序，DFS是一个常用的方法。
    4. 连通分量： 查找图中的连通分量或强连通分量。
    5. 内存限制： 在某些情况下，如果图非常宽但深度有限，DFS可能会比BFS占用更少的内存，因为它只需要存储当前路径上的节点。
    6. 深度优先搜索的特性： 如果你想要找到一个“深层”的解，或者对路径的深度更感兴趣，DFS是自然的选择。

  • 选择BFS的场景：

    1. 最短路径问题（无权图）： 当你需要找到从一个节点到另一个节点的最短路径（以边数衡量）时，BFS是首选。例如，在一个迷宫中找到最短的逃生路径。
    2. 层序遍历： 如果你需要按层级顺序访问节点，例如在树中按层级打印节点。
    3. 查找任意一个解，且解可能位于图的浅层： 如果你知道某个问题的解可能在离起始节点不远的层级上，BFS可能会更快地找到它。

完全二叉树的结点个数、叶子结点数和高度之间满足怎样的关系？如何给完全二叉树的结点编号？

• 完全二叉树可以看作是最后一层所有节点集中在左侧，其他层构成满二叉树的一颗二叉树。

• 已知完全二叉树的结点个数，可以反推高度：高度 \(h\) 的完全二叉树的结点个数介于 \(2^{h - 1}\) 和 \(2 ^{h} - 1\) 之间。反之不然。

• 已知完全二叉树的结点个数，可以反推其叶子结点数目：已知结点数 \(n\)，首先反推其高度 \(h = \lfloor \log_2 n\rfloor + 1\)，然后可以算出从第一层到倒数第二层得到的满二叉树的节点数 \(n' = 2^{h - 1} - 1\)，于是得到底层节点数为 \(n_{\text{bottom}} = n - n'\)。这些节点都是叶子节点。然后考虑倒数第二层的结点，里面有些结点是底层结点的父节点，将倒数第二层的结点扣除这一部分，再加上底层节点即可得到叶子节点数：\(n_{\text{leaf}} = 2^{h - 1} - \lfloor\dfrac{n_{\text{bottom}} + 1}{2}\rfloor + n_{\text{bottom}}\)

• 编号问题，可以参考数组上建堆的方法，即对于下标 \(i\) 的结点，其子节点的下标为 \(2 \times i + 1\) 和 \(2\times i + 2\)。

什么是二叉排序树？形成二叉排序树的充分必要条件是什么？如何构造一棵二叉排序树？（标红）

• BST 是满足结点偏序关系的二叉树。即一颗二叉树，它的所有结点都满足左儿子小于右儿子，那么就是一颗 BST。

• 构造方法：失败查找法，即首先对新的节点值进行查找，找到查找失败时的空指针，再直接在这个空指针位置插入数据。

• 如何计算给定 BST 的平均查找次数？对于成功而言，计算每一个结点到根节点路径长度的均值；对于失败而言，计算每一个空指针到根节点路径长度的均值。

• 这种插入方法有可能导致 BST 退化成链表，或者说左右子树高度严重不对称，因此引入了各种操作来调整树高，使其维持在 \(\log n\) 的数量级。

什么是B-树？怎样构造B-树？什么是B+树？B-树与B+树的差别在哪里？

• B-树是满足以下特点的树：

  • 多路分支：每个节点可以有多个子节点（通常为m个，m称为B树的阶），而不仅仅是二叉树的两个子节点。这使得B树的高度远低于二叉树，从而减少了磁盘读写次数。
  • 平衡性：所有的叶子节点都位于同一层，从根节点到任何叶子节点的路径长度都相同。这保证了查找、插入和删除操作的时间复杂度始终为\(O(\log_m N)\)，其中\(N\)是数据总量，\(m\)是阶数。
  • 节点结构：一个B树节点通常包含\(k-1\)个关键字和\(k\)个子指针（其中\(k \le m\)）。这些关键字将节点内的键值空间划分为\(k\)个子区间，每个子指针指向对应子区间的数据或子树。
  • 关键字有序：节点内的关键字是按升序排列的。

• 一个m阶B-树的属性通常定义为

  1. 每个节点最多有m个子节点。
  2. 每个非叶子节点（除根节点）最少有\(\lceil m/2 \rceil\)个子节点。
  3. 如果根节点不是叶子节点，那么它至少有两个子节点。
  4. 有\(k\)个子节点的非叶子节点拥有\(k-1\)个关键字。
  5. 所有的叶子节点都在同一层。

• B-树的插入操作

  1. 查找插入位置：首先，从根节点开始，根据要插入的关键字，找到它应该插入的叶子节点。
  2. 插入关键字：将关键字插入到该叶子节点中，并保持节点内关键字的有序性。
  3. 处理节点上溢（分裂）：如果插入后，当前节点的关键字数量超过了允许的最大值（m-1个），则发生上溢。
     • 分裂：将该节点分裂为两个新节点。通常是将中间的关键字提升到父节点中，并将两侧的关键字分别放入两个新节点。
     • 向上递归：如果父节点因为提升的关键字也发生上溢，则重复分裂操作，直到根节点或者找到一个没有上溢的节点。如果根节点上溢，则树的高度增加一层。

• B-树的删除操作：

  • 取决于删除后是否导致节点关键字数量低于最小值，即下溢。
  • 如果不出现下溢，则直接删除。
  • 如果出现下溢，通常通过合并或借用兄弟节点的关键字来解决。
  • 合并：如果一个节点下溢，并且其兄弟节点也没有多余的关键字可以借用，那么它会与兄弟节点合并，并将父节点中分隔它们的关键字下移。
  • 借用：如果一个节点下溢，但其兄弟节点有多余的关键字，则可以从兄弟节点借用一个关键字，并相应地调整父节点中的关键字。

• B+树：是B-树的一种变体，通常在数据库和文件系统中广泛使用。它在B-树的基础上进行了一些优化，使其更适合范围查询和磁盘I/O。

• B+树的主要特点是：

  • 所有关键字都出现在叶子节点：非叶子节点只存储索引信息（关键字），不存储实际的数据记录。所有的实际数据记录都存储在叶子节点中。
  • 叶子节点形成有序链表：所有的叶子节点包含全部关键字信息，并且它们之间通过指针连接成一个有序的链表。这使得范围查询非常高效，只需遍历叶子节点链表即可。
  • 非叶子节点只作为索引：非叶子节点（内部节点）只存储关键字的拷贝，作为指向子节点的索引，不存储实际的数据指针。

• B-树与B+树的差别：

  1. 只需要记住相比于B-树，B+树是索引数据结构，并且叶子节点之间还有链表相连即可。下面的对比都是围绕这个区别展开。

  2. 数据存储方式：

     • B-树：每个节点（包括非叶子节点和叶子节点）都可能存储关键字和指向数据记录的指针。这意味着数据可能分散在树的各个层级。
     • B+树：所有的数据记录都存储在叶子节点中。非叶子节点只存储关键字（索引）和指向子节点的指针，不存储实际数据。

  3. 范围查询：

     • B-树：进行范围查询时，可能需要多次从根节点开始遍历，效率相对较低。
     • B+树：由于叶子节点形成了一个有序链表，范围查询可以直接在叶子节点链表上进行遍历，效率非常高。这是B+树在数据库索引中被广泛应用的重要原因。

  4. 适用场景：

     • B-树：适用于内存中的数据结构，或者对随机查找性能要求较高，且对范围查询没有特别要求的场景。
     • B+树：更适合外部存储（如磁盘）中的数据结构，尤其在数据库和文件系统中作为索引结构。它优化了磁盘I/O和范围查询。

什么是哈夫曼编码？哈夫曼编码是如何形成的？哈夫曼编码有哪些性质？（标红）

• Huffman 编码是基于哈夫曼树的编码方式，它既是一个前缀编码（即不会有一个编码是另外一个编码的前缀），也是信息密度最高的编码。下面讲哈夫曼树。

• 哈夫曼树是叶子节点具有最短带权路径长度 (WPL) 的树。构造方式为：首先将所有数据的频数从低到高排好，然后取出最前面的两个数据，将频数相加，得到这两个结点的根节点，然后把这个和放入有序数列中，维持数列低到高的有序性，然后不断取出最前面两个数据，直到序列为空。

• 构造好哈夫曼树之后，所有叶子节点都是原来的数据节点。我们为每一个叶子指派一个编码，指派规则为：从根结点出发，向左走，就往后面添上一个0，向右走，就添上一个1，指派一个

• 为什么 Huffman 编码是前缀编码？因为所有编码的节点都是叶子节点。

• 为什么信息密度高？因为 WPL 最短。数据在某个编码下所占的空间 = 编码长度 * 频数 = 叶子节点的 WPL 之和，而 Huffman 树恰好是让这个东西最小的树。

什么是图的邻接表、逆邻接表、十字链表、邻接表多重表？

• 邻接表：图的一种链式存储结构，它为图中的每个顶点创建一个链表，链表中存储与该顶点相邻的所有顶点。

• 邻接表的结构：

  • 顶点数组： 一个包含所有顶点的数组（或链表），每个元素代表一个顶点。
  • 边链表： 对于每个顶点 \(V_i\)，有一个链表存储所有从 \(V_i\) 出发的边。链表中的每个节点通常包含：
    • 邻接顶点索引： 边的另一端顶点的索引。
    • 权值（可选）： 如果是带权图，则存储边的权值。
    • 下一条边指针： 指向该链表中下一条边的指针。

• 逆邻接表：与邻接表类似，但它存储的是指向当前顶点的边。对于有向图来说，邻接表存储的是出边，逆邻接表存储的是入边。对于无向图，邻接表和逆邻接表是等价的。它的结构和邻接表一致。

• 十字链表：针对有向图的一种更复杂的链式存储结构，它结合了邻接表和逆邻接表的思想，使得查找某个顶点的出边和入边都非常方便。每个边节点都同时存在于其起始顶点的出边链表和终止顶点的入边链表中。

• 邻接多重表：针对无向图的一种存储结构，它主要解决的是在邻接表中，每条无向边 \((V_i, V_j)\) 会存储两次的问题（一次在 \(V_i\) 的链表中，一次在 \(V_j\) 的链表中）。邻接多重表只存储每条边一次，但通过指针将其连接到相关联的两个顶点的链表中。

什么是循环队列？rear和front指针通常代表什么？循环队列为满的条件与循环队列为空的条件之间有什么关系？改变其中一个条件能推导出另一个条件吗？

• 循环队列（Circular Queue）是一种特殊的队列，它将数组的头尾连接起来，形成一个环状结构。这样做的好处是，当队列的末尾达到数组的末端时，可以从数组的开头继续存储数据，从而更有效地利用存储空间，避免了普通队列在队头元素出队后，需要将所有元素向前移动的开销。

• 根据教材的说法，只有利用数组做底层存储结构的队列才能叫循环队列。用各种链表做底层存储结构的队列叫做链队。

• 在循环队列中，通常使用两个指针：

  • front（或head）指针：指向队列的第一个元素的前一个位置（队头）。当元素出队时，front指针向前移动。
  • rear（或tail）指针：指向队列的最后一个元素（队尾）。当元素入队时，rear指针向前移动。

• 循环队列为满的条件与循环队列为空的条件之间有什么关系？

• 假设循环队列的底层数组大小为Capacity。

  • 1. 循环队列为空的条件：
  • 当 front == rear 时，表示队列为空。这意味着队头指针和队尾指针指向了同一个位置，队列中没有元素。 2. 循环队列为满的条件：

  • 为了区分队列为空和队列为满的情况，通常有以下几种处理方式：

    • 方法一：牺牲一个存储单元

      • 这是最常用的方法。我们约定，当队列为满时，front 指向的下一个位置是 rear。具体来说，当 (rear + 1) % Capacity == front 时，表示队列已满。

      • 在这种约定下，实际可存储的元素数量是 Capacity - 1，有一个位置是始终空着的，用来区分空和满。

    • 方法二：使用一个计数器（count）

      • 除了 front 和 rear 指针外，再维护一个 count 变量来记录队列中元素的数量。
      • 当 count == 0 时，队列为空。
      • 当 count == Capacity 时，队列为满。
      • 这种方法的好处是不牺牲存储空间，但需要额外维护一个计数器。

  • 改变其中一个条件能推导出另一个条件吗？

  • 通常情况下，在不引入额外信息（如计数器或标志位）的前提下，仅仅通过改变一个条件（例如，改变判断满的条件），很难直接推导出另一个条件（空的条件），因为它们依赖于指针的相对位置。如果我们简单地把满的条件也设为 front == rear，那么就会导致歧义：我们无法区分队列是空的还是满的。这就是为什么通常需要牺牲一个存储单元或者引入计数器/标志位的原因。

什么是分块查找？如何进行分块查找？如何计算分块查找的效率？

• 分块查找是一种结合了顺序查找和二分查找优点的查找方法。它适用于那些数据量较大，且数据本身不需要严格有序，但又希望比纯顺序查找效率更高的情况。

• 分块查找的基本思想是将数据集合分成若干个块，每个块内的元素可以无序，但块与块之间是有序的（即前一个块中的最大值小于或等于后一个块中的最小值，或者每个块的索引项是块内某个元素的关键字）。为了加速查找，通常会为每个块建立一个索引表，索引表记录了每个块的最大（或最小）关键字以及该块的起始地址。

• 分块查找通常分为两个步骤：

  • 1. 确定目标块：
    2. 首先，在索引表中进行查找。由于索引表中的关键字是块的代表，并且索引表本身是按关键字有序的，因此可以在索引表中进行顺序查找或二分查找来确定目标元素可能存在的块。
    3. 通常，为了提高效率，索引表会选择使用二分查找。通过比较待查找关键字与索引表中每个块的最大（或最小）关键字，找到第一个块的最大（或最小）关键字大于或等于待查找关键字的块。
  • 在目标块内查找：
    • 一旦确定了目标块，就根据索引表中记录的该块的起始地址，进入该块进行顺序查找。因为块内的元素可以是无序的，所以只能进行顺序查找。
• 分块查找的效率通常用平均查找长度（Average Search Length, ASL）来衡量。平均查找长度是指在查找过程中，平均需要比较的次数。
• 假设：
• 数据元素总数为 \(N\)。
• 将数据分成 \(m\) 个块，每个块包含 \(s\) 个元素（\(N = m \times s\)）。
• 索引表中进行的是二分查找。
• 块内进行的是顺序查找。

• 平均查找长度 \(ASL\) 可以分为两部分：

  1. 查找索引表的比较次数：
     • 如果在索引表中进行二分查找，最坏情况是 \(\log_2 m\) 次比较。平均情况下，可以近似为 \(\log_2 m\) 次。
     • 如果在索引表中进行顺序查找，平均比较次数为 \((m+1)/2\) 次。
  2. 在目标块内查找的比较次数：
     • 由于块内是顺序查找，平均需要比较 \((s+1)/2\) 次。

• 因此，分块查找的平均查找长度（ASL）的计算公式为：

  • 当索引表采用顺序查找时： \(ASL = \frac{m+1}{2} + \frac{s+1}{2}\) 将 \(m = N/s\) 代入，得到： \(ASL = \frac{N/s+1}{2} + \frac{s+1}{2}\)1 为了使 \(ASL\) 最小，可以对 \(ASL\) 关于 \(s\) 求导并令其为0，可以近似地得到当 \(s \approx \sqrt{N}\) 时，ASL 最小。此时，ASL 大约为 \(\sqrt{N}\)。

  • 当索引表采用二分查找时： \(ASL = \log_2 m + \frac{s+1}{2}\) 将 \(m = N/s\) 代入，得到： \(ASL = \log_2 (N/s) + \frac{s+1}{2}\)

什么是AOV网？在AOV网上的经典问题和算法是什么？怎样进行拓扑排序？

• AOV网全称是Activity On Vertex Network（顶点活动网），它是一种有向无环图（Directed Acyclic Graph, DAG）。在AOV网中，图的顶点表示活动（或事件），而有向边表示活动之间的优先关系或顺序关系。例如，如果存在一条从顶点A到顶点B的边，则表示活动A必须在活动B之前完成。由于AOV网表示的是活动之间的顺序，所以它必须是无环的，否则会陷入无限的依赖循环。
• AOV网常用于描述一个工程或项目，其中各个任务之间存在依赖关系，我们需要确定一个合理的执行顺序。
• AOV网最经典的的应用就是拓扑排序。
• 拓扑排序是对AOV网的顶点进行线性排序，使得对于图中的任意一条有向边 \((u, v)\)，顶点 \(u\) 在排序结果中总是在顶点 \(v\) 之前。换句话说，拓扑排序就是找出所有活动的一个合法执行序列。
• 利用Kahn算法进行拓扑排序的步骤如下：
  1. 计算所有顶点的入度： 遍历图中的所有顶点，统计每个顶点的入度。
  2. 初始化队列： 将所有入度为0的顶点放入一个队列中。这些顶点是当前可以开始执行的活动。
  3. 循环处理队列：
     • 从队列中取出一个顶点 \(u\)，并将其加入到拓扑排序结果列表。
     • 遍历所有从顶点 \(u\) 出发的边，对于每条边 \((u, v)\)：
       • 将顶点 \(v\) 的入度减1。
       • 如果顶点 \(v\) 的入度变为0，则将 \(v\) 加入队列。
  4. 检查环： 重复步骤3，直到队列为空。
     • 如果最终拓扑排序结果列表中的顶点数量等于图中顶点的总数量，说明图是无环的，拓扑排序成功。
     • 如果拓扑排序结果列表中的顶点数量少于图中顶点的总数量，说明图中存在环，因此无法进行拓扑排序。

什么是二路归并排序？算法复杂度是什么？有什么特点？

• 二路归并排序（Two-way Merge Sort）是一种高效的排序算法，它基于“分而治之”（Divide and Conquer）的思想。

• 二路归并排序的核心思想是将一个待排序的序列递归地分成两个子序列，直到每个子序列只包含一个元素（此时认为这些子序列已经有序）。然后，将这些有序的子序列两两合并（归并），生成更大的有序子序列，重复这个过程直到所有的子序列合并成一个完整的有序序列。

• 具体步骤如下：

  • 创建一个临时数组，用于存放合并后的结果。
  • 设定两个指针，分别指向两个待合并子序列的起始位置。
  • 比较两个指针所指向的元素，将较小的元素放入临时数组，并移动相应指针。
  • 重复此步骤，直到其中一个子序列的所有元素都被放入临时数组。
  • 将另一个子序列中剩余的所有元素直接复制到临时数组的末尾。
  • 最后，将临时数组中的有序元素复制回原始数组对应的位置。

• 时间复杂度：

  • 最好、最坏和平均情况都是 \(O(N \log N)\)。
  • 分析：
    • 分解阶段：每次将序列一分为二，直到每个子序列只剩一个元素，这个过程会进行 \(\log N\) 层。
    • 合并阶段：在每一层中，合并两个子序列需要线性时间，即 \(O(N)\)（因为要遍历所有元素）。
    • 因此，总的时间复杂度为 \(O(N \log N)\)。

• 空间复杂度：

  • \(O(N)\)。
  • 分析：归并排序需要一个额外的辅助数组来存储合并后的结果，这个辅助数组的大小与原始序列的大小相同，因此空间复杂度为 \(O(N)\)。

• 有什么特点？

  1. 稳定性：二路归并排序是一种稳定的排序算法。这意味着如果序列中有两个相同值的元素，在排序前后它们的相对位置保持不变。这是因为在合并过程中，当两个子序列中的元素相等时，我们可以优先选择左边子序列的元素放入临时数组，从而保持它们的原始相对顺序。
  2. 时间复杂度稳定：无论输入数据的初始顺序如何，其时间复杂度始终为 \(O(N \log N)\)，这使其在各种情况下都表现良好。
  3. 非原地排序：由于需要额外的辅助空间进行合并操作，二路归并排序是一种非原地排序算法。
  4. 适用于外部排序：由于其分治的思想，归并排序非常适合处理大数据集，这些数据无法一次性全部加载到内存中（称为外部排序）。可以将大文件分成小块进行内部排序，然后将这些有序的小块进行多路归并。
  5. 递归实现或迭代实现：二路归并排序既可以通过递归方式实现（自顶向下），也可以通过迭代方式实现（自底向上）。
  6. 并行性：归并排序的分解和合并步骤具有一定的并行性，可以利用多核处理器进行优化。

什么是图的单源最短路径问题？解决该问题的常见方法有哪些？

• 图的单源最短路径问题是指：给定一个带权有向图或无向图 \(G = (V, E)\)，其中 \(V\) 是顶点的集合，\(E\) 是边的集合，每条边 \((u, v) \in E\) 都有一个非负的权重 \(w(u, v)\)。给定一个源点 \(s \in V\)，我们需要找到从源点 \(s\) 到图中所有其他顶点 \(v \in V\) 的最短路径。最短路径是指路径上所有边的权重之和最小的路径。

• 解决该问题的常见方法有：

  1. 广度优先搜索 (BFS) 虽然 BFS 通常用于无权图的最短路径问题，但它也可以用于解决边权都为 1 的特殊单源最短路径问题。其核心思想是，从源点 \(s\) 开始，逐层向外扩展，首先访问距离 \(s\) 为 1 的所有顶点，然后是距离 \(s\) 为 2 的所有顶点，依此类推。

     • 算法流程：
       1. 初始化所有顶点的距离为无穷大，源点 \(s\) 的距离为 0。
       2. 创建一个队列，并将源点 \(s\) 加入队列。
       3. 当队列不为空时，取出队头顶点 \(u\)。
       4. 遍历 \(u\) 的所有邻居 \(v\)。如果 \(v\) 尚未被访问（或者说 \(v\) 的距离仍然是无穷大），则将 \(v\) 的距离设置为 \(u\) 的距离加 1，并将 \(v\) 加入队列。
       5. 重复步骤 3 和 4，直到队列为空。

  2. Dijkstra 算法 Dijkstra 算法是解决带有非负权重的单源最短路径问题的常用算法。它采用贪心策略，逐步扩展最短路径树。

     • 算法流程：
       1. 初始化所有顶点的距离为无穷大，源点 \(s\) 的距离为 0。
       2. 创建一个优先队列（或称为小顶堆），并将所有顶点及其当前距离加入队列。
       3. 当优先队列不为空时，取出距离最小的顶点 \(u\)。
       4. 如果 \(u\) 已经被确定为最短路径（即已经从优先队列中取出过），则跳过。
       5. 对于 \(u\) 的每一个邻居 \(v\)，计算从源点 \(s\) 经过 \(u\) 到 \(v\) 的新距离：\(dist(u) + w(u, v)\)。
       6. 如果这个新距离小于当前 \(v\) 的距离 \(dist(v)\)，则更新 \(dist(v)\)，并将 \(v\) 及其新距离重新加入（或更新其在）优先队列中。
       7. 重复步骤 3 到 6，直到优先队列为空，或者所有可达顶点的最短路径都已确定。

  3. Floyd-Warshall 算法 Floyd-Warshall 算法是解决所有顶点对最短路径问题的算法，但它也可以通过将其应用于单个源点来解决单源最短路径问题（尽管效率不如 Dijkstra 算法）。它基于动态规划的思想，通过考虑所有可能的中间顶点来逐步计算最短路径。需要注意的是，Floyd-Warshall 算法可以处理负权边，但不能处理负权环。

     • 算法流程：
       1. 初始化一个距离矩阵 \(D\)，其中 \(D[i][j]\) 表示从顶点 \(i\) 到顶点 \(j\) 的直接边权重。如果不存在直接边，则设置为无穷大。如果 \(i=j\)，则 \(D[i][j]=0\)。
       2. 对于图中的每一个顶点 \(k\) (作为中间顶点)，遍历所有顶点对 \((i, j)\)。
       3. 更新 \(D[i][j]\) 的值：\(D[i][j] = \min(D[i][j], D[i][k] + D[k][j])\)。这意味着从 \(i\) 到 \(j\) 的最短路径要么是直接路径，要么是经过 \(k\) 的路径。
       4. 重复步骤 2 和 3，直到所有顶点 \(k\) 都作为中间顶点被考虑过。
       5. 最终，矩阵 \(D\) 中的 \(D[s][v]\) 就是从源点 \(s\) 到顶点 \(v\) 的最短路径。

什么是快速排序？在不同条件下的算法复杂度是什么？

• 快速排序的基本步骤如下：

  1. 挑选基准值（Pivot）：从数列中挑出一个元素，称为“基准”（pivot）。这个基准值的选择对算法的性能有很大影响。
  2. 分割（Partition）：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，基准值就处于其最终的排序位置。
  3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

• 算法复杂度

  1. 最好情况（Best Case）：

     • 时间复杂度：\(O(N \log N)\)
     • 当每次选择的基准值都能将数组均匀地分成两个大致相等（或接近相等）的子数组时，就会出现最好情况。例如，每次基准值都恰好是当前子数组的中位数。
     • 在这种情况下，递归的深度大约为 \(\log N\)，每层操作的时间复杂度为 \(O(N)\)（因为需要遍历元素进行分割），所以总时间复杂度为 \(O(N \log N)\)。

  2. 平均情况（Average Case）：

     • 时间复杂度：\(O(N \log N)\)
     • 在大多数实际应用中，如果基准值是随机选择的，或者通过一些策略（如“三数取中”法）来选择基准值，快速排序的性能通常会趋向于平均情况。
     • 虽然每次分割不一定都非常均匀，但从概率上讲，每次分割都能有效地减少问题规模，因此平均时间复杂度也近似于 \(O(N \log N)\)。

  3. 最坏情况（Worst Case）：

     • 时间复杂度：\(O(N^2)\)
     • 当每次选择的基准值都恰好是当前子数组的最小值或最大值时，就会出现最坏情况。
     • 例如，如果数组已经完全有序（升序或降序），并且每次都选择第一个或最后一个元素作为基准值，那么每次分割操作都会导致一个子数组为空，而另一个子数组包含除了基准值之外的所有元素。
     • 在这种情况下，递归的深度将达到 \(N\)，每层操作仍然是 \(O(N)\)，所以总时间复杂度为 \(O(N^2)\)。
     • 为了避免最坏情况的发生，通常会采用一些优化策略，例如：
       • 随机选择基准值：随机选择数组中的一个元素作为基准，可以大大降低遇到最坏情况的概率。
       • 三数取中法：选择数组的第一个、中间和最后一个元素，然后取这三个数的中位数作为基准值，这有助于在一定程度上避免极端情况。

• 空间复杂度：

  • 快速排序是原地排序（In-place sorting）算法，但由于其递归的特性，需要额外的栈空间来存储递归调用的信息。
  • 最好和平均情况：\(O(\log N)\)，对应于递归深度。
  • 最坏情况：\(O(N)\)，对应于递归深度达到 \(N\)。

什么是AOE网络？结点和边分别代表什么？什么是关键活动？怎样求关键路径？

• AOE网络（Activity On Edge Network），即边活动网络，是一种用于项目管理和调度、估算工程完成时间的带权有向无环图。它强调的是活动在边上。

  • 结点（Vertex/Node）：在AOE网络中，结点代表事件（Event）。事件表示某个活动的开始或结束的状态，它本身不耗费时间，但代表着一个特定时刻。例如，"完成地基"、"开始装修"等。
  • 边（Edge/Arc）：边代表活动（Activity）。每条边表示一个需要耗费时间和资源的具体任务或工作。边的权重通常表示该活动所需的持续时间。例如，"建造墙壁"、"铺设电缆"等。有向性表示活动的先后顺序和依赖关系。

• 关键活动（Critical Activity） 指在AOE网络中，任何一点延迟都会导致整个项目完成时间延迟的活动。换句话说，它们的浮动时间（Slack Time）为零。如果关键活动被延误，项目的总工期就会增加。

• 如何求关键路径（Critical Path）： 关键路径是AOE网络中从起点到终点的所有路径中，路径长度最长的那条路径。这条路径上的所有活动都是关键活动，它的长度决定了整个项目完成所需的最短时间。求关键路径通常采用“前向计算”和“后向计算”相结合的方法：

  1. 确定最早开始时间 (Earliest Start Time, ES) 和 最早完成时间 (Earliest Finish Time, EF)：

     • 事件的最早发生时间 (Earliest Event Time, EE)：从源点（起始事件）开始，按拓扑顺序计算每个事件可能发生的最早时间。
       • 源点（起始事件）的EE为0。
       • 对于任何事件 \(j\)，其 \(EE(j)\) 等于所有指向 \(j\) 的活动 \(i \to j\) 的最早完成时间的最大值。即 \(EE(j) = \max \{ EE(i) + Duration(i \to j) \}\)。
     • 活动的最早开始时间 (Earliest Start Time, ES)：一个活动的ES等于其前置事件的最早发生时间。
       • 对于活动 \(i \to j\)，其 \(ES(i \to j) = EE(i)\)。
     • 活动的最早完成时间 (Earliest Finish Time, EF)：一个活动的EF等于其最早开始时间加上其持续时间。
       • 对于活动 \(i \to j\)，其 \(EF(i \to j) = ES(i \to j) + Duration(i \to j)\)。
     • 整个项目的最早完成时间就是汇点（终点事件）的EE。

  2. 确定最迟开始时间 (Latest Start Time, LS) 和 最迟完成时间 (Latest Finish Time, LF)：

     • 事件的最迟发生时间 (Latest Event Time, LE)：从汇点（终点事件）开始，按逆拓扑顺序计算每个事件允许发生的最迟时间，而不影响整个项目的完成时间。
       • 汇点（终点事件）的LE等于其EE（即项目的最早完成时间）。
       • 对于任何事件 \(i\)，其 \(LE(i)\) 等于所有从 \(i\) 发出的活动 \(i \to j\) 的最迟开始时间的最小值。即 \(LE(i) = \min \{ LE(j) - Duration(i \to j) \}\)。
     • 活动的最迟完成时间 (Latest Finish Time, LF)：一个活动的LF等于其后继事件的最迟发生时间。
       • 对于活动 \(i \to j\)，其 \(LF(i \to j) = LE(j)\)。
     • 活动的最迟开始时间 (Latest Start Time, LS)：一个活动的LS等于其最迟完成时间减去其持续时间。
       • 对于活动 \(i \to j\)，其 \(LS(i \to j) = LF(i \to j) - Duration(i \to j)\)。

  3. 计算活动的浮动时间 (Slack Time)：

     • 浮动时间是指一个活动在不影响项目总工期的情况下可以延迟的时间。
     • 对于活动 \(i \to j\)，其浮动时间 \(Slack(i \to j) = LS(i \to j) - ES(i \to j)\) 或 \(Slack(i \to j) = LF(i \to j) - EF(i \to j)\)。

  4. 确定关键路径：

     • 所有浮动时间为零的活动都是关键活动。
     • 连接所有关键活动的路径，就是关键路径。通常，可能存在多条关键路径。

什么是多关键字排序？什么是基数排序算法？算法复杂度如何？

• 多关键字排序（Multi-key Sort），也称为多级排序或多维度排序，是指对一组数据进行排序时，不仅仅依据一个关键字进行排序，而是依据多个关键字的优先级顺序进行排序。

• 当数据包含多个属性（或字段）时，我们可能需要根据这些属性的组合来确定数据的最终顺序。

  1. 确定主关键字： 首先选择一个最主要的关键字作为排序的第一优先级。
  2. 次要关键字及其优先级： 接着确定次要关键字，如果主关键字的值相同，则按照次要关键字进行排序，依此类推。
  3. 逐级比较： 排序算法会先根据主关键字对数据进行排列。如果遇到主关键字相同的数据项，它会进一步比较它们的次要关键字，直到找到一个不同的关键字，或者所有关键字都比较完毕。

• 实现多关键字排序通常有以下两种方法：

  • 多趟排序（Multi-pass Sort）： 使用一个稳定的排序算法（如归并排序或插入排序）对数据进行多趟排序。从最低优先级的关键字开始，逐级对每个关键字进行排序。由于每趟排序都是稳定的，因此前面已经排好的低优先级关键字的相对顺序不会被破坏。
  • 单一比较函数（Single Comparison Function）： 许多排序算法（如快速排序、归并排序）允许自定义比较函数。在这个比较函数中，你可以定义多个关键字的比较逻辑，按照优先级顺序进行判断。

• 基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。它不通过比较元素的大小来排序，而是通过分配和收集的过程来完成排序。

  1. 最低有效位优先（LSD Radix Sort）：

     • 从待排序数字的最低位（个位）开始，对所有数字根据该位上的值进行“分配”。通常会使用桶（Bucket）或队列来存储相同位值的数字。例如，可以创建0-9的10个桶，将个位是0的数字放入0号桶，个位是1的数字放入1号桶，以此类推。
     • 分配完成后，按照桶的顺序（从0到9）依次将桶中的数字“收集”起来，形成一个新的序列。
     • 重复上述分配和收集过程，依次对数字的更高位（十位、百位等）进行排序，直到最高位。
     • 由于每一步排序都是稳定的，所以经过所有位的排序后，整个序列就是有序的。

  2. 最高有效位优先（MSD Radix Sort）：

     • 从待排序数字的最高位开始，对所有数字根据该位上的值进行分配。
     • 对于每个桶中的子序列，递归地应用基数排序，处理下一位。
     • 当某个桶中的子序列只包含一个元素或所有元素的当前位都相同（或者达到最低位）时，停止递归。
     • 最后将所有桶中的有序子序列连接起来。

  3. 基数排序适用于整数，也可以扩展到字符串和特定格式的浮点数，因为它们可以被表示为一系列的“位”或“字符”。

• 算法复杂度

  • 基数排序的时间复杂度：

    • 基数排序的时间复杂度为 \(O(d \cdot (n + k))\)，其中：
      • \(n\) 是待排序元素的数量。
      • \(d\) 是数字的最大位数（或者说，需要进行多少轮排序）。
      • \(k\) 是基数（radix），通常是每个位上可能出现的不同值的数量，例如，对于十进制数字， \(k=10\)；对于二进制数字， \(k=2\)。
    • 每趟排序（对一位进行分配和收集）的时间复杂度是 \(O(n + k)\)。因为我们需要遍历所有 \(n\) 个数字进行分配，然后遍历 \(k\) 个桶并将所有数字收集起来。
    • 总共有 \(d\) 趟排序，所以总时间复杂度是 \(O(d \cdot (n + k))\)。

  • 基数排序的空间复杂度：

    • 基数排序的空间复杂度为 \(O(n + k)\)。
    • \(O(k)\) 用于存储 \(k\) 个桶。
    • \(O(n)\) 用于在分配过程中临时存储数字，或者用于收集时的新序列。

• 与比较排序的比较：

  • 基数排序是非比较型排序，其时间复杂度可以达到线性级别，即 \(O(n)\)，当 \(d\) 和 \(k\) 相对于 \(n\) 较小时。例如，如果所有数字的位数 \(d\) 较小，并且基数 \(k\) 也较小（常数），那么基数排序会比任何基于比较的排序算法（如快速排序、归并排序等，它们的时间复杂度通常为 \(O(n \log n)\)）更快。
  • 然而，基数排序对数据类型有严格要求（通常是整数或可转换为整数的类型），并且需要额外的空间来存储桶。而比较排序则更通用，可以适用于各种类型的数据。

什么是KMP算法？什么是目标串？什么是模式串？next数组起到什么作用？

• KMP (Knuth-Morris-Pratt) 算法是一种高效的字符串搜索算法，用于在一个较长的目标串（或称主串、文本串）中查找一个较短的模式串（或称子串、关键字）的所有出现位置。与朴素的字符串匹配算法不同，KMP 算法通过预处理模式串，避免了在发生不匹配时，目标串指针不必要的“回溯”，从而实现了线性的时间复杂度。

• KMP 算法的核心思想是，当模式串与目标串发生不匹配时，它不会简单地将模式串向右移动一位并从头开始比较。相反，它会利用已经匹配的部分信息，即模式串自身的结构特点，来决定模式串应该“跳跃”到哪个位置继续比较。这种“跳跃”是基于模式串的最长公共前缀后缀信息。

• 具体来说，KMP 算法分为两个主要阶段：

  1. 模式串预处理（构建 next 数组）：

     这个阶段是 KMP 算法的关键，它在匹配开始之前对模式串进行分析，生成一个被称为 next 数组（或称 LPS 数组，即最长公共前缀后缀数组）。next[i] 的值表示模式串 P 的前 i 个字符构成的子串 P[0...i-1] 中，最长的公共前缀（同时也是后缀）的长度。

     例如，如果模式串为 "ababa"，那么： * P[0] ("a"): 最长公共前缀后缀长度为 0。 * P[0...1] ("ab"): 最长公共前缀后缀长度为 0。 * P[0...2] ("aba"): 最长公共前缀后缀长度为 1 ("a")。 * P[0...3] ("abab"): 最长公共前缀后缀长度为 2 ("ab")。 * P[0...4] ("ababa"): 最长公共前缀后缀长度为 3 ("aba")。

     这个 next 数组在匹配过程中起到了指导模式串如何“跳跃”的作用。

  2. 模式串与目标串的匹配：

     在匹配阶段，算法使用两个指针，一个指向目标串（通常记为 i），一个指向模式串（通常记为 j）。

     • 匹配成功时： 如果 目标串[i] 和 模式串[j] 相等，则 i 和 j 都向后移动一位，继续比较下一个字符。
     • 匹配失败时： 如果 目标串[i] 和 模式串[j] 不等，此时 KMP 算法就利用 next 数组来确定模式串的新位置。
       • 如果 j > 0 (即模式串已经匹配了一部分)，那么 j 会被更新为 next[j-1]。这意味着模式串会“回退”到 next[j-1] 所指示的长度位置，因为模式串的前 next[j-1] 个字符已知是当前已匹配部分的后缀，从而避免了重复比较。
       • 如果 j == 0 (即模式串的第一个字符就未匹配成功)，则目标串指针 i 向后移动一位，模式串指针 j 保持在 0，从模式串的开头重新开始比较。

     这个过程持续进行，直到模式串完全匹配成功（j 达到模式串的长度），或者目标串已经遍历完毕。

• 目标串（Target String），也称为主串或文本串（Text String），是指我们要在其中进行搜索的、较长的字符串。KMP 算法的目的就是在目标串中找到模式串的出现位置。

• 模式串（Pattern String），也称为子串或关键字，是指我们想要在目标串中查找的、较短的字符串。KMP 算法会尝试将模式串的各个位置与目标串进行比较，以确定模式串是否存在于目标串中，以及存在的位置。

• next 数组（也常被称为 LPS 数组，即 Longest Proper Prefix which is also a Suffix 的缩写）是 KMP 算法的核心辅助数据结构。它的作用可以概括为：

  1. 存储模式串自身的结构信息： next[i] 的值记录了模式串 P 的前 i 个字符所组成的子串 P[0...i-1] 中，最长的、非自身的、既是前缀又是后缀的子串的长度。

  2. 避免目标串指针的回溯： 当模式串和目标串在某个位置发生不匹配时，next 数组会指导模式串如何“高效地”向右移动，而不需要将目标串的指针回溯到之前的位置。它告诉我们，当前模式串已匹配的部分中，有一个长度为 next[j-1] 的前缀（P[0...next[j-1]-1]）与已匹配部分的后缀（P[j-next[j-1]...j-1]）是相同的。因此，我们可以将模式串向右移动，使得模式串的 next[j-1] 位置的字符对齐到目标串当前不匹配字符的位置，继续从 模式串[next[j-1]] 处开始比较。

  3. 提高匹配效率： 通过利用 next 数组，KMP 算法在发生不匹配时，能够“跳过”那些不可能匹配的位置，从而大大减少了字符比较的次数，使得算法的时间复杂度达到线性，即 \(O(N+M)\)，其中 \(N\) 是目标串的长度，\(M\) 是模式串的长度。如果没有 next 数组，朴素的字符串匹配算法在最坏情况下可能达到 \(O(N \cdot M)\) 的时间复杂度。

常用的排序算法有哪些？哪些排序算法是稳定的，哪些是不稳定的？这些排序算法的时间复杂度和空间复杂度如何？单趟排序能决定某个（些）元素的最终位置的排序算法有哪些？

• 以下是一些常用的排序算法：
  1. 冒泡排序 (Bubble Sort)
  2. 选择排序 (Selection Sort)
  3. 插入排序 (Insertion Sort)
  4. 快速排序 (Quick Sort)
  5. 归并排序 (Merge Sort)
  6. 堆排序 (Heap Sort)
  7. 计数排序 (Counting Sort)
  8. 桶排序 (Bucket Sort)
  9. 基数排序 (Radix Sort)
• 算法的具体内容和原理，请结合教材自行复习。

• 排序算法的稳定性是指当待排序序列中存在值相等的元素时，经过排序之后，这些相等元素的相对次序保持不变。

  • 稳定的排序算法：

    • 冒泡排序
    • 直接插入排序
    • 归并排序
    • 计数排序
    • 桶排序
    • 基数排序

  • 不稳定的排序算法：

    • 选择排序
    • 快速排序
    • 堆排序
    • 希尔排序

• 排序算法的时间复杂度和空间复杂度

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	稳定
选择排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	不稳定
插入排序	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	稳定
快速排序	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n^2)\)	\(O(\log n)\) 到 \(O(n)\)	不稳定
归并排序	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n)\)	稳定
堆排序	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(1)\)	不稳定
计数排序	\(O(n+k)\)	\(O(n+k)\)	\(O(n+k)\)	\(O(k)\)	稳定
桶排序	\(O(n+k)\)	\(O(n+k)\)	\(O(n^2)\)	\(O(n+k)\)	稳定
基数排序	\(O(nk)\)	\(O(nk)\)	\(O(nk)\)	\(O(n+k)\)	稳定

解释：

• \(n\): 待排序元素的数量
• \(k\): 计数排序中，待排序元素的最大值与最小值之差加一；桶排序中，桶的数量；基数排序中，最大数的位数。
• \(O(1)\): 常数空间，表示只使用了少量额外空间。
• \(O(\log n)\): 对数空间，通常是递归调用栈的空间。

• \(O(n)\): 线性空间，表示额外空间与输入规模成正比。

• 以下排序算法在单趟（或一次迭代）过程中，能够确定至少一个（或某些）元素的最终排序位置（也就是说，形成的有序区是全局的）：

  1. 选择排序: 每趟选择未排序部分中的最小（或最大）元素，并将其放到已排序部分的末尾。因此，每趟都能确定一个元素的最终位置。

  2. 快速排序: 在每一趟分区（partition）操作中，基准元素（pivot）会被放置到其最终的排序位置上。

  3. 堆排序 (Heap Sort): 在构建完大顶堆（或小顶堆）后，每次取出堆顶元素（最大或最小）并将其放到数组的末尾，这个元素就确定了其最终位置。这个过程重复 \(n-1\) 次，每次确定一个元素。

  4. 冒泡排序 (Bubble Sort): 每趟冒泡排序会把当前未排序部分的最大（或最小）元素“冒泡”到其最终位置。例如，一趟冒泡后，最大的元素会位于数组的末尾。

什么是对半搜索算法？适用条件是什么？算法复杂度如何？什么是二叉判定树，怎样利用二叉判定树计算平均搜索长度？

• 对半搜索算法，也称为二分查找（Binary Search），是一种在有序数组中查找特定元素的搜索算法。它的基本思想是：每次比较数组中间的元素与目标值，如果目标值与该元素匹配，则查找成功；如果目标值小于该元素，则在数组较小的那一半中继续查找；如果目标值大于该元素，则在数组较大的那一半中继续查找。通过这种方法，每次迭代都能将搜索范围缩小一半。

• 适用条件：

  • 数据必须是有序的： 这是二分查找最核心的条件。无论是升序还是降序排列，数组中的元素都必须按照某种顺序排列。如果数据无序，则无法使用二分查找。
  • 数据存储在随机访问的数据结构中： 通常是数组。因为二分查找需要通过索引直接访问中间元素，链表等顺序访问的数据结构不适合。

• 算法复杂度：

  • 时间复杂度： \(O(\log n)\)。
    • 在每次比较后，搜索范围都会减半。这意味着在最坏情况下，查找所需的操作次数与数组大小的对数成正比。例如，对于一个包含 \(n\) 个元素的数组，最多需要 \(\log_2 n\) 次比较。
  • 空间复杂度： \(O(1)\) (迭代实现) 或 \(O(\log n)\) (递归实现)。
    • 迭代实现只需要常数级别的额外空间来存储索引变量。
    • 递归实现会因为函数调用的栈帧而消耗与递归深度成正比的空间，即 \(O(\log n)\)。

• 二叉判定树（Binary Search Tree，简称BST） 是一种特殊的二叉树数据结构，它满足以下性质：

  1. 左子树的键值都小于根节点的键值。
  2. 右子树的键值都大于根节点的键值。
  3. 左右子树也都是二叉判定树。 这个定义确保了树中的所有节点都按照特定的顺序排列，从而允许高效地进行查找、插入和删除操作。显然这里的 BST 和那个叫做二叉排序树/二叉搜索树的 BST 是一个东西，所以相关的计算也是一致的。但是，由于二叉判定树的高度相对较低，可以把它看作是一个相对比较平衡的 BST。

• 怎样利用二叉判定树计算平均搜索长度： 在二叉判定树中计算平均搜索长度通常指的是平均查找成功长度和平均查找失败长度。

  1. 查找成功长度：

     • 对于树中的每个节点，它的查找成功长度是从根节点到该节点的路径长度加1（如果根节点深度为0，则加1）。
     • 计算平均查找成功长度： 将所有节点的查找成功长度之和除以节点总数。
     • 例如，如果节点A在深度0，查找成功长度是1；节点B在深度1，查找成功长度是2。

  2. 查找失败长度：

     • 查找失败发生在搜索路径到达一个空指针（或空子树）时。
     • 在二叉判定树中，每个可能的查找失败位置对应于一个“外部节点”或“叶子节点”的空子树。这些位置通常被称为虚拟节点或空节点。
     • 查找失败长度是从根节点到查找失败位置的路径长度。
     • 计算平均查找失败长度： 将所有可能的查找失败路径长度之和除以可能的查找失败位置的数量。

假设二叉判定树中包含 \(n\) 个节点，并且所有节点的查找概率是相同的。

• 计算查找成功长度：

  1. 遍历二叉判定树，记录每个节点的深度（根节点深度为0）。
  2. 对于每个节点 \(i\)，其查找成功长度 \(L_i = \text{depth}(i) + 1\)。
  3. 平均查找成功长度 \(ASL_{成功} = \frac{\sum_{i=1}^{n} L_i}{n}\)。

• 计算查找失败长度：

  1. 找到所有可能的查找失败位置（即空子树）。在一个有 \(n\) 个节点的二叉树中，总共有 \(n+1\) 个空子树。
  2. 对于每个空子树（查找失败位置），其查找失败长度是从根节点到该空子树的路径长度。
  3. 平均查找失败长度 \(ASL_{失败} = \frac{\sum_{j=1}^{n+1} \text{PathLength}(空子树_j)}{n+1}\)。

什么是有向无环图DAG？它有怎样的特点？DAG有什么性质？DAG可以用来解决哪些问题？

• 有向无环图（Directed Acyclic Graph, 简称 DAG）是一种特殊的有向图。它由顶点（vertex）和有向边（directed edge）组成，并且不包含任何有向环。特点：
• 有向性（Directed）: 所有的边都有明确的方向，从一个顶点指向另一个顶点。这意味着如果你有一条从 A 到 B 的边，你不能沿着这条边从 B 到 A。
• 无环性（Acyclic）: 图中不存在任何可以从某个顶点出发，沿着有向边最终回到该顶点的路径。简单来说，你无法“绕一圈”回到起点。
• 层次结构（Hierarchical Structure）: 由于无环性，DAG 通常表现出一种层次结构。如果存在从顶点 u 到顶点 v 的路径，那么 u 在某种意义上“先于”v。这使得 DAG 非常适合表示任务依赖、事件顺序等。

• 拓扑排序（Topological Sort）: 对于任何 DAG，都至少存在一种拓扑排序。拓扑排序是将 DAG 的所有顶点线性排列，使得对于任何有向边 \((u, v)\)，顶点 u 总是出现在顶点 v 之前。

• 性质

  1. 没有回路: 这是其定义中最核心的性质。由于没有回路，从任何一个顶点出发，你都无法通过有向边回到该顶点。这使得 DAG 非常适合表示具有明确开始和结束的任务流程。

  2. 拓扑排序的存在性与唯一性（或非唯一性）:

     • 存在性: 任何有向无环图都至少存在一个拓扑排序。这是 DAG 区别于一般有向图的重要性质之一。
     • 唯一性: 拓扑排序不一定是唯一的。如果一个 DAG 中存在多个不相关的路径（即它们之间没有直接或间接的依赖关系），那么这些路径中的顶点可以有不同的相对顺序，从而产生不同的拓扑排序。只有当图是“链式”的，即每个顶点最多只有一个前驱和最多一个后继时，拓扑排序才可能是唯一的。

  3. 表示偏序关系: DAG 可以很好地表示偏序关系（partial order）。如果存在从顶点 A 到顶点 B 的路径，那么我们可以说 A “小于或等于” B，或者 A “先于” B。这种关系是非对称和传递的，但不是完全的（即并非所有元素之间都有可比性）。

  4. 路径的有限性: 由于没有环，任何从一个顶点到另一个顶点的路径都是有限长的。这意味着在 DAG 中，不存在无限长的路径。

  5. 不包含强连通分量（Strongly Connected Components）: 在有向图中，如果两个顶点 u 和 v 互相可达，那么它们属于同一个强连通分量。由于 DAG 不包含环，因此任何一个强连通分量都只能包含一个顶点（即顶点自身可达自身，但不能到达其他顶点并返回）。这意味着 DAG 可以看作是许多独立的顶点或由有向边连接的“链”组成。

  6. 最短路径和最长路径问题:

     • 最短路径: 在带权 DAG 中，可以使用线性时间复杂度的算法（例如基于拓扑排序的动态规划）来找到最短路径。这比一般图中需要使用 Dijkstra 或 Bellman-Ford 算法要快，因为不需要处理负权环的问题。
     • 最长路径: 类似地，在带权 DAG 中找到最长路径也是线性时间复杂度的。这在一般图中是一个 NP-hard 问题（除非图中没有负权环）。这种性质使得 DAG 在项目管理（关键路径法）、调度等领域非常有用。

  7. 动态规划的基础: 许多动态规划问题都可以被建模为在 DAG 上寻找路径或子结构的问题。例如，最长公共子序列（LCS）问题就可以转化为在 DAG 上寻找最长路径。

  8. 可以被分解为源和汇:

     • 源（Source）: 入度为 0 的顶点，没有指向它的边。
     • 汇（Sink）: 出度为 0 的顶点，没有从它发出的边。 任何非空的 DAG 至少有一个源和一个汇。这是因为如果一个 DAG 没有源，那么每个顶点都有入度，这意味着可以沿着入度方向无限回溯，最终形成一个环，这与 DAG 的定义矛盾。同理，如果一个 DAG 没有汇，也可以沿着出度方向无限前进，最终形成一个环。

什么是堆（heap）？堆有什么性质？如何构建堆？

• 堆（Heap）是一种特殊的数据结构，它通常被实现为近似完全二叉树。堆的主要特点是满足“堆序性”（Heap Property）。根据堆序性的不同，堆可以分为两种：

  1. 最大堆（Max Heap）：对于堆中的任意节点 \(P\) 和它的子节点 \(C\)，如果 \(P\) 是 \(C\) 的父节点，那么 \(P\) 的值大于或等于 \(C\) 的值。这意味着最大值总是在堆的根节点。
  2. 最小堆（Min Heap）：对于堆中的任意节点 \(P\) 和它的子节点 \(C\)，如果 \(P\) 是 \(C\) 的父节点，那么 \(P\) 的值小于或等于 \(C\) 的值。这意味着最小值总是在堆的根节点。

• 堆通常用数组来表示，因为完全二叉树的性质使得这种表示方式非常紧凑和高效。对于一个以数组形式存储的堆，如果一个节点的索引是 \(i\)：

  • 它的左子节点的索引是 \(2i + 1\)。
  • 它的右子节点的索引是 \(2i + 2\)。
  • 它的父节点的索引是 \(\lfloor(i - 1) / 2\rfloor\)。

• 堆有什么性质？

  1. 完全二叉树的结构：堆总是一棵完全二叉树。这意味着除了最底层，其他所有层都被完全填满，并且最底层的节点都尽可能地从左到右填充。这个性质使得堆可以使用数组高效地存储，而不需要使用指针连接节点，从而节省空间并提高访问效率。
  2. 堆序性（Heap Property）：这是堆最核心的性质。
     • 在最大堆中，每个父节点的值都大于或等于其所有子节点的值。因此，根节点包含堆中的最大值。
     • 在最小堆中，每个父节点的值都小于或等于其所有子节点的值。因此，根节点包含堆中的最小值。
     • 这个性质保证了我们可以高效地找到堆中的最大（或最小）元素，通常是 \(O(1)\) 时间复杂度（即直接访问根节点）。

• 构建堆的一种常用方法是筛选法（Heapify），它通过反复应用“sift down”（下沉）操作来将一个无序数组调整成一个堆。这里的“sift down”也被称为“heapify down”或“max/min-heapify”。

• 假设我们想构建一个最大堆（对于最小堆原理类似，只是比较方向相反）。sift down 操作的核心思想是：给定一个节点，如果它的值不满足堆序性（例如，在最大堆中，它比它的某个子节点小），那么就将这个节点的值与它的较大子节点（在最大堆中）进行交换，然后递归地对被交换的子节点位置重复这个过程，直到这个节点的值满足堆序性（即它比所有子节点都大），或者它成为叶子节点（没有子节点）。

  1. 选择需要调整的节点：sift down 操作通常从一个非叶子节点开始。在构建整个堆时，我们从最后一个非叶子节点开始，然后向前依次处理所有非叶子节点，直到根节点。这是因为叶子节点天然满足堆序性（它们没有子节点可以比较）。
  2. 比较并交换：
     • 对于当前需要调整的节点 \(P\)（索引 \(i\)），找到它的左右子节点 \(C_L\)（索引 \(2i+1\)）和 \(C_R\)（索引 \(2i+2\)）。
     • 在最大堆的情况下，比较 \(P\)、\(C_L\)、\(C_R\) 三个节点的值。
     • 找出这三个节点中的最大值。
     • 如果最大值就是 \(P\) 的值，说明当前节点 \(P\) 已经满足堆序性，sift down 过程结束。
     • 如果最大值是 \(C_L\) 或 \(C_R\) 的值（假设是 \(C_{max}\)），则将 \(P\) 的值与 \(C_{max}\) 的值进行交换。
  3. 递归下沉：
     • 在交换之后，\(P\) 的原始值现在位于 \(C_{max}\) 的位置。此时，需要检查 \(C_{max}\) 的位置是否满足堆序性。
     • 因此，以 \(C_{max}\) 的新位置作为新的当前节点，递归地重复步骤2，直到当前节点的值不再需要下沉（即它比其所有子节点都大或它是一个叶子节点）。

• 构建整个堆的过程（从无序数组到堆）：

  • 要将一个任意的数组构建成一个堆，我们从最后一个非叶子节点开始，逆序向上对每个非叶子节点执行 sift down 操作，直到根节点。

    • 起始节点：在一个大小为 \(N\) 的数组中，最后一个非叶子节点的索引是 \(\lfloor N/2 \rfloor - 1\)。
    • 迭代过程：从索引 \(\lfloor N/2 \rfloor - 1\) 开始，递减到索引 \(0\) (即根节点)。对于每一个节点 \(i\)，执行 sift down(i) 操作。

  • 当这个循环结束时，整个数组就变成了一个满足堆序性的堆。这个构建过程的时间复杂度是 \(O(N)\)，尽管每个 sift down 操作在最坏情况下可能需要 \(O(\log N)\) 的时间。这是因为大部分 sift down 操作发生在靠近叶子节点的层，这些层的高度较小，因此总的复杂度会低于简单的 \(N \times O(\log N)\)。

评论