一些题目和笔记

一些判断题

（粘贴自 csdn，不确保正确）

1-1 数据元素是数据的最小单位。F
1-2 数据的逻辑结构是指数据的各数据项之间的逻辑关系。F
1-3 数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。T
1-4 数据元素可以由类型互不相同的数据项构成。T
1-5 数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。F
1-6 2N 和 N 具有相同的增长速度。F
1-7 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。T
1-8 n! is O(n^n).T
1-9 O(N2) is the same as O(1+2+3+⋯+N).T
1-10 对于顺序存储的长度为 N 的线性表，访问结点和增加结点的时间复杂度分别对应为 O(1)和 O(N)。T
1-11 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。T
1-12 对于顺序存储的长度为 N 的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为 O(1)和 O(N)。F
1-13 (neuDS)在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。T
1-14 (neuDS)所谓随机存取，就是通过首地址和元素的位序号值可以在 O(1)的时间内找到指定的元素。T
1-15 (neuDS)顺序存储的线性表不支持随机存取。F
1-16 (neuDS)在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。F
1-17 (neuDS)顺序存储方式只能用于存储线性结构。F
1-18 在具有 N 个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为 O(1)和 O(N)。F
1-19 若用链表来表示一个线性表，则表中元素的地址一定是连续的。F
1-20 将 N 个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 O(logN)。F
1-21 通过对堆栈 S 操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。F
1-22 若一个栈的输入序列为 1，2，3，…，N，输出序列的第一个元素是 i，则第 j 个输出元素是 j−i−1。F
1-23 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。T
1-24 栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。T
1-25 栈底元素是不能删除的元素。F
1-26 顺序栈中元素值的大小是有序的。F
1-27 在 n 个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。T
1-28 栈顶元素和栈底元素有可能是冋一个元素。T
1-29 栈是一种特殊的线性表，它的插入和删除操作都是在表的同一端进行。 T
1-30 链栈的插入在栈顶，删除在栈底。F
1-31 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。F
1-32 在用数组表示的循环队列中，front 值一定小于等于 rear 值。F
1-33 循环队列执行出队操作时会引起大量元素的移动。F
1-34 队列中允许插入的一端叫队头，允许删除的一端叫队尾。 F
1-35 队列结构的顺序存储会产生假溢出现象。 T
1-36 二叉树通常有顺序存储结构和链式存储结构。T
1-37 在含有 n 个结点的树中，边数只能是 n-1 条。T
1-38 完全二叉树中，若一个结点没有左孩子，则它必是树叶。T
1-39 一棵有 n 个结点的二叉树，从上至下，从左到右用自然数依次编号，则编号为 i 的结点的左儿子的编号为 2i(2i< n),右儿子的编号是 2i+1(2i+1< n)。F
1-40 用树的前序遍历和中序遍历可以导出树的后序遍历。F？
1-41 二叉树只能用二叉链表表示。F
1-42 树形结构中元素之间存在一个对多个的关系。T
1-43 度为二的树就是二叉树。F 二叉树还要有区分左右儿子的顺序
1-44 某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。T
1-45 某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。F
1-46 一棵有 124 个结点的完全二叉树，其叶结点个数是确定的。T
1-47 任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。T
1-48 二叉搜索树的查找和折半查找的时间复杂度相同。F
1-49 二叉排序树的后序遍历序列必然是递增的。F
1-50 若一搜索树（查找树）是一个有 n 个结点的完全二叉树，则该树的最大值一定在叶结点上 F
1-51 N 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 T 根节点选取不同，BST 不同
1-52 中根遍历二叉查找树所得序列一定是有序序列。T
1-53 在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。T
1-54 二叉排序树的查找效率和二叉排序树的髙度有关。T
1-55 任何最小堆的前序遍历结果是有序的（从小到大）。F
1-56 任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。T
1-57 对 N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。T
1-58 哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。F 多个字符频率相同时，在树中的位置可交换，可能导致哈夫曼码的长度不唯一
1-59 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。F？
1-60 无向连通图所有顶点的度之和为偶数。T
1-61 无向连通图边数一定大于顶点个数减 1。F 可以等于
1-62 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。F
1-63 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。T
1-64 在一个有向图中，所有顶点的入度与出度之和等于所有边之和的 2 倍。T
1-65 在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。T
1-66 图的深度优先遍历非递归算法通常采用队列实现，广度优先遍历非递归算法通常采用堆栈实现。F
1-67 如果无向图 G 必须进行两次广度优先搜索才能访问其所有顶点，则 G 中一定有回路。F
1-68 采用邻接表存储的图，其广度优先遍历类似于二叉树的先序遍历。F
1-69 若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次。F
1-70 在一个有权无向图中，若 b 到 a 的最短路径距离是 12，且 c 到 b 之间存在一条权为 2 的边，则 c 到 a 的最短路径距离一定不小于 10。T
1-71 P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。F
1-72 对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。F
1-73 对 N 个记录进行归并排序，归并趟数的数量级是 O(NlogN)。F
1-74 对 N 个记录进行堆排序，需要的额外空间为 O(N)。F
1-75 对 N 个记录进行简单选择排序，比较次数和移动次数分别为 O(N2)和 O(N)。T
1-76 对 N 个记录进行快速排序，在最坏的情况下，其时间复杂度是 O(NlogN)。F
1-77 希尔排序是稳定的算法。F
1-78 对 N 个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。F
1-79 要从 50 个键值中找出最大的 3 个值，选择排序比堆排序快。T
1-80 基于比较的排序算法中，只要算法的最坏时间复杂度或者平均时间复杂度达到了次平方级 O(N * logN)，则该排序算法一定是不稳定的。F
1-81 在堆排序中，若要进行升序排序，则需要建立大根堆。T
1-82 堆是完全二叉树，完全二叉树不一定是堆。T
1-83 直接插入排序是不稳定的排序方法。F
1-84 内排序要求数据一定要以顺序方式存储。F
1-85 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。F
1-86 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。F
1-87 快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。F
1-88 对 N 个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。F
1-89 快速排序是稳定的算法。F
1-90 用希尔(shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。F
1-91 直接选择排序的时间复杂度为 O(n2)，不受数据初始排列的影响。T
1-92 冒泡排序算法的最坏时间复杂性是 O(n2)，而快速排序算法的最坏时间复杂性是 O(nlog2n)，所以快速排序比冒泡排序效率好。F
1-93 （101,88,46,70,34,39,45,58,66,10）是堆。T
1-94 有一大根堆，堆中任意结点的关键字均大于它的左右孩子关键字，则其具有最小值的结点一定是一个叶子结点并可能在堆的最后两层中。T
1-95 在任何情况下，归并排序都比简单插入排序快。F
1-96 在散列表中，所谓同义词就是被不同散列函数映射到同一地址的两个元素。F
1-97 将 M 个元素存入用长度为 S 的数组表示的散列表，则该表的装填因子为 M/S。T
1-98 在散列中，函数“插入”和“查找”具有同样的时间复杂度。T
1-99 即使把 2 个元素散列到有 100 个单元的表中，仍然有可能发生冲突。T
1-100 将 10 个元素散列到 100 000 个单元的哈希表中，一定不会产生冲突。F

HW 总结

The Fibonacci number sequence \(\{F*N\}\) is defined as: \(F_0 = 0\), \(F_1 = 1\), \(F_N = F*{N-1} + F\_{N-2}\), \(N=2, 3, ...\) The time complexity of the function which calculates \(F_N\) recursively is \(\Theta(N!)\).

• T
• F

\( T(N)=T(N-1)+T(N-2)+O(1)\),时间复杂度为\(\Theta(\phi^n)\).

The Fibonacci number sequence \(\{F*N\}\) is defined as: \(F_0 = 0\), \(F_1 = 1\), \(F_N = F*{N-1} + F\_{N-2}\), \(N=2, 3, ...\) The space complexity of the function which calculates \(F_N\) recursively is:

• A. \(O(\log N)\)
• B. \(O(N)\)
• C. \(O(F_N)\)
• D. \(O(N!)\)

每个\(F(N)\)虽然在不同递归过程中产生,但是存储在统一空间,空间复杂度为\(O(N)\).

For a sequentially stored linear list of length \(N\), the time complexities for deleting the first element and inserting the last element are \(O(1)\) and \(O(N)\), respectively.

• T
• F

顺序存储的线性表通常指的是数组（Array）或顺序表（Sequential List），其特点是元素在内存中连续存储，且必须从第一位开始。 删除第一个后，后面的所有元素都需要向前移动一位以填补空缺，时间为\(O(N)\). 如果数组空间足够（未满），直接在 A[N] 的位置写入新元素，无需移动其他元素,时间复杂度为\(O(1)\).

If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then which of the following data structures is the most efficient?

• A. doubly linked list
• B. singly linked circular list
• C. doubly linked circular list with a dummy head node
• D. sequential list

链表不能快速随机访问 而插入删除只需要对末尾进行,线性表操作时不用移动其他位.

It is always possible to represent a tree by a one-dimensional integer array.

• T
• F

树是一种非线性数据结构，但可以通过一定的方式用线性结构（如一维数组）表示。常见的用一维数组表示树的方法包括：

1. 父节点表示法：用一维数组存储每个节点的父节点索引。
2. 左孩子右兄弟表示法：用两个一维数组分别存储每个节点的左孩子和右兄弟。（这里要两个数组，不符合）
3. 完全二叉树的数组表示：补全成完全二叉树，直接用一维数组按层级顺序存储。

关键在于存储的不是节点的数值，而是节点的编号。

There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.

• T
• F

n=2016，n1=16 n=n0+n1+n2 总边数： e=n-1 =n0+n1+n2 -1(树的性质：边数=点数-1) e=n1+2*n2 结论: n2=n0 -1 n=n1+2*n2 -1 2*n2=1001,不存在

Given a tree of degree 3. Suppose that there are 3 nodes of degree 2 and 2 nodes of degree 3. Then the number of leaf nodes must be ____.

• A. 5
• B. 6
• C. 7
• D. 8

树中节点的度是什么？树中节点的度是指该节点的子节点（直接后代）的数量。它的“度”就是它拥有的子树的个数（即直接连接的子节点数）。 Given a tree of degree 3 什么意思？树的 degree 通常指节点的最大度数（即某个节点的最大子节点数）。这里"degree 3 的树"可能指每个非叶节点最多有 3 个子节点（即 3 叉树，ternary tree）。 n2=3, n3=2 n0+n1+n2+n3-1=n1+2*n2+3*n3 n0+n1+5-1=n1+12 n0=8

If a general tree \( T \) is converted into a binary tree \( BT \), then which of the following \( BT \) traversals gives the same sequence as that of the post-order traversal of \( T \)?

• A. Pre-order traversal
• B. In-order traversal
• C. Post-order traversal
• D. Level-order traversal

怎么把普通的树转化成二叉树？

1. 选择根节点：
   • 保持原树的根节点作为二叉树的根节点。
2. 处理子节点：
   • 将节点的第一个子节点作为其左孩子（left child）。
   • 将该节点的其他子节点（按顺序）作为第一个子节点的右子树（right siblings）。
3. 递归应用：
   • 对每个子节点递归应用相同的规则。

转化成二叉树后的中序遍历等价于原树的后序遍历。

In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order.

• T
• F

对于任意节点，左子树所有节点的值一定小于右子树所有节点的值。 同一层的节点，左边的一定在某个节点的左子树，右边的在这个节点的右子树。 所以从左到右一定单调递增。

In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.

• T
• F

如果 4 和 6 是兄弟，5 一定是父亲； 如果 4 和 6 在同一层但不相邻，5 一定在中间，矛盾； 如果 4 和 6 相邻但不是兄弟，可以举出反例:

      5
     / \
    3   7
   / \ / \
  1  4 6  8

In a max-heap with \( n \) (\( > 1 \)) elements, the array index of the minimum key may be ____.

• A. 1
• B. \(\lfloor n/2 \rfloor - 1\)
• C. \(\lfloor n/2 \rfloor\)
• D. \(\lfloor n/2 \rfloor + 2\)

最小值一定是叶节点。 一共 n 层的完全二叉树，最后一层第一个是\(2^{n-1}\)，最后一个是\(2^n-1\)， 总节点数\(2^{n-1} < N <2^n-1\)，\(\lfloor N/2 \rfloor + 1\)得到最后一行第一个

Using the linear algorithm to build a min-heap from the sequence {15, 26, 32, 8, 7, 20, 12, 13, 5, 19}, and then insert 6. Which one of the following statements is FALSE?

• A. The root is 5
• B. The path from the root to 26 is {5, 6, 8, 26}
• C. 32 is the left child of 12
• D. 7 is the parent of 19 and 15

Using the linear algorithm to build a min-heap 是怎么样建堆？ 建堆的两种方法：

1. 自底向上（Bottom-up，Linear-time Heapify）：从最后一个非叶节点开始，将每个节点和其子树变为堆。时间复杂度：\(O(n)\)。
2. 逐个插入（Top-down，Incremental Heap Construction）：排成完全二叉树，每个数插入到最后再调整。时间复杂度：\(O(nlogn)\)。

If a \(d\)-heap is stored as an array, for an entry located in position \(i\), the parent, the first child and the last child are at:

• A. \(\lceil (i + d - 2) / d \rceil\), \((i - 2)d + 2\), and \((i - 1)d + 1\)
• B. \(\lceil (i + d - 1) / d \rceil\), \((i - 2)d + 1\), and \((i - 1)d\)
• C. \(\lfloor (i + d - 2) / d \rfloor\), \((i - 1)d + 2\), and \(id + 1\)
• D. \(\lfloor (i + d - 1) / d \rfloor\), \((i - 1)d + 1\), and \(id\)

d-heap 什么意思? d-heap 是堆（Heap）的一种泛化形式，其中每个节点最多有 d 个子节点（而非二叉堆的 2 个子节点）。它是完全 d 叉树（Complete d-ary Tree）。 可用 d=3 代入验证，排除错误选项

If a binary search tree of \(N\) nodes is complete, which one of the following statements is FALSE?

• A. the average search time for all nodes is \(O(\log N)\)
• B. the minimum key must be at a leaf node
• C. the maximum key must be at a leaf node
• D. the median node must either be the root or in the left subtree

完全二叉树要求上面全满，最后一层从左到右填，不一定是满二叉树。 BST 的平均搜索时间是树的高度。平衡二叉树的高度是\(log(N)\),故平均搜索时间是\(O(\log N)\)。 中位数（median node）的定义：

• 奇数个节点：正中间的节点（第 \(\lfloor(N/2)\rfloor\)个）。
• 偶数个节点：中间两个节点的第一个（即第 N/2 个节点，称为下中位数）。

N 为奇数时，中位数是根；N 为偶数时，中位数在左子树中。

In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than \(N/2\), but not \(O(\log N)\).

• T
• F

通过按大小合并，任意节点的深度不超过\(O(\log N)\)（其中 N 是总元素数）。

The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are:

• A. 1 and -6
• B. 4 and -5
• C. 8 and -5
• D. 8 and -6

disjoint set 是什么？ 并查集 习惯的并查集写法：root 和 merge，初始化为自环 上课讲的并查集写法：所有的根为负数，绝对值为这个连通块的大小

A relation \( R \) is defined on a set \( S \). If for every element \( e \) in \( S \), “\( e \, R \, e \)” is always true, then \( R \) is said to be ____ over \( S \).

• A. consistent
• B. symmetric
• C. transitive
• D. reflexive

在数学中，关系 \( R \) 在集合 \( S \) 上可以有以下几种重要性质：

1. 自反性（Reflexive）：

   • 定义：对于所有的 \( e \in S \)，有 \( e \, R \, e \)。
   • 例子：实数上的“≤”关系是自反的，因为对于任何实数 \( x \)，\( x \leq x \) 都成立。

2. 对称性（Symmetric）：

   • 定义：对于所有的 \( a, b \in S \)，如果 \( a \, R \, b \)，那么 \( b \, R \, a \)。
   • 例子：“=”关系是对称的，因为如果 \( a = b \)，那么 \( b = a \)。

3. 传递性（Transitive）：

   • 定义：对于所有的 \( a, b, c \in S \)，如果 \( a \, R \, b \) 且 \( b \, R \, c \)，那么 \( a \, R \, c \)。
   • 例子：“≤”关系是传递的，因为如果 \( a \leq b \) 且 \( b \leq c \)，那么 \( a \leq c \)。

4. 一致性（Consistent）：

   • 这个术语在关系的性质中不常见，通常不是关系的基本性质之一。可能是指关系在某些上下文中的一致性，但一般不作为关系的标准性质。

数据元素是数据的最小单位。F

数据的最小单位是数据项（Data Item），而不是数据元素（Data Element）。

• 数据项：是不可分割的最小数据单位，也称为字段或属性。例如，学生的“学号”或“姓名”是一个数据项。
• 数据元素：是由若干数据项组成的，是数据的基本单位。例如，一个学生的完整记录（包括学号、姓名、年龄等数据项）是一个数据元素。

修正说法：

• “数据项是数据的最小单位。”（T）
• 或“数据元素是数据的基本单位。”（T）

数据的逻辑结构是指数据的各数据项之间的逻辑关系。F

错误原因：

• 逻辑结构的定义是数据元素之间的关系，而非数据项之间的关系。
  • 逻辑结构：描述数据元素之间的关联方式（如线性结构、树形结构、图结构等）。
  • 例如，学生记录（数据元素）按学号顺序排列是线性结构。
• 数据项之间的关系：属于数据元素的内部细节，是物理存储或具体实现的范畴。

混淆逻辑结构与物理结构：

• 逻辑结构是抽象的（如链表、树），与存储无关。
• 数据项之间的关系更接近物理存储（如结构体中的字段排列）。

修正说法：

• “数据的逻辑结构是指数据元素之间的逻辑关系。”（T）

所谓随机存取，就是通过首地址和元素的位序号值可以在 O(1)的时间内找到指定的元素。T

随机存取是指可以直接访问存储介质中的任意位置的数据，而无需按顺序遍历前面的数据。这种访问方式的特点是访问时间与数据位置无关，无论数据存储在哪个位置，都能以相同的速度直接读取或写入。

将 N 个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 O(logN)。F

1. 二分查找的前提是“随机存取” 二分查找（Binary Search）的核心操作是 “通过下标直接访问中间元素”（即 arr[mid]），这要求数据结构必须支持 随机存取（Random Access），例如：

• 数组：通过下标可在 \( O(1) \) 时间内访问任意元素。
• 支持随机存取的线性结构（如动态数组）。

但 单向链表（Singly Linked List） 的存储特性是：

• 不支持随机存取：无法直接通过下标访问元素（如 list[5]）。
• 必须顺序遍历：要访问第 \( k \) 个节点，必须从头节点开始逐个移动 \( k-1 \) 次。

在任意一棵非空二叉搜索树，删除某结点后又将其插入，则所得二叉搜索树与删除前原二叉搜索树相同。 F

删除非叶节点后该点被其他节点代替，树的结构发生改变。重新插入后一定是叶节点，一定不在原来的位置。

一些笔记

• 队列假溢出是什么？队头已满，队尾空，但会误认为队列已满。可用循环队列解决。
• 度为 2 的树不一定是二叉树。二叉树要求所有节点的度<=2，且子节点有顺序。可能存在树的子节点无顺序，即交换两个子节点不影响树的定义。
• 树的前序遍历和中序遍历不一定能推出后序遍历。要求为二叉树（或普通树但子节点有顺序）。
• 自然数认为包括零吗？包括。
• 图中顶点的度是什么？与该点直接相连的边的数量。有向图分入度和出度。
• 深度优先和广度优先搜索的数据结构：DFS 调用堆栈，实现深度优先；BFS 调用队列，保证按层遍历。
• 有向图中不存在回路，同一节点也可能被多次访问。因为同一节点入度可能大于 1，即可能被多个节点指向，遍历时可通过每个指向它的节点访问到该节点。
• 堆排序进行升序排序，必须建大根堆；降序排序，必须建小根堆。因为堆排序的规定操作为堆顶元素和最后一个未排序的元素交换。
• 虽然给出关键字序列的顺序不一样，但依次生成的二叉搜索树可能不一样。
• 拓扑排序可以用来检验图中是否有环。排序时入度为零的节点加入，并依次为基础修改其他点的入度。若所有点都被排序，则没有环（DAG）；若有的点没有被排序，则有环。
• Partial order is a precedence relation which is both transitive and irreflexive.偏序关系是一种优先关系，满足传递性和非自反性。

AOE 网和 AOV 网是什么

AOE 网（Activity On Edge network），即边表示活动的网络，是一种用于描述工程项目中活动及其依赖关系的有向无环图（DAG）。

AOE 网与 AOV 网的区别：

自底向上和逐个插入建堆的时间复杂度比较

自底向上建堆（Bottom-up Heap Construction）的时间复杂度为 O(n)，而非直观认为的 O(n log n)，这是由堆的树状结构特性和每层节点数与调整成本的平衡决定的。以下是详细分析：

1. 复杂度分析的数学推导 假设堆是一棵完全二叉树，高度为 h = log₂n，各层节点数和调整成本如下：

总调整次数 T(n) 为各层节点数 × 其下沉步数之和：

简化求和（令 k = h - i）：

（注：级数 \(\sum\_{k=1}^{\infty} \frac{k}{2^k} = 2\) 是收敛的）

2. 直观理解

• 大部分节点位于底层：约 n/2 的叶子节点无需调整，n/4 的节点只需下沉 1 步。
• 高层节点少但代价高：仅有 1 个根节点需下沉 h 步，但因其数量极少（1 个），对总复杂度的贡献被低层节点平衡。

3. 对比自顶向下建堆（O(n log n)）

• 自顶向下（插入式建堆）：
  每次插入一个新节点并执行 上浮（Sift Up），共 n 次操作，每次最坏 O(log n)，总复杂度 O(n log n)。
• 自底向上：
  利用已有子树结构，从倒数第二层开始调整，越上层节点调整次数越多，但节点数指数级减少，总和收敛为 O(n)。

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

排序算法复杂度总表

关键说明

1. 时间复杂度：

   • 快速排序：平均性能最优，但最坏情况（如已排序数组）退化为 \(O(n^2)\)，可通过随机化枢轴避免。
   • 堆排序：时间复杂度稳定，但常数因子较大，实际慢于快速排序。
   • 计数/桶/基数排序：均基于非比较排序，时间复杂度突破 \(O(n \log n)\)，但需特定条件（如数据范围有限）。

2. 空间复杂度：

   • 原地排序：冒泡、选择、插入、希尔、堆排序的空间复杂度为 \(O(1)\)。
   • 递归开销：快速排序平均 \(O(\log n)\)（递归栈），最坏 \(O(n)\)；归并排序需 \(O(n)\) 额外空间。

3. 稳定性：

   • 稳定算法（如归并、冒泡）保持相等元素的原始顺序，适用于多关键字排序。
   • 不稳定算法（如快速、堆排序）可能改变相等元素的相对位置。

各算法特点及适用场景

1. 快速排序：

   • 优点：平均效率最高，缓存友好。
   • 缺点：最坏情况性能差，需优化枢轴选择。
   • 适用：通用场景，内存排序（如 C++ std::sort）。

2. 归并排序：

   • 优点：稳定，时间复杂度稳定。
   • 缺点：需额外空间。
   • 适用：外部排序（大数据文件）、链表排序。

3. 堆排序：

   • 优点：原地排序，无最坏情况风险。
   • 缺点：缓存不友好，实际速度较慢。
   • 适用：内存受限场景（如嵌入式系统）。

4. 计数/桶/基数排序：

   • 优点：线性时间复杂度。
   • 缺点：对数据分布有要求（如范围小、均匀分布）。
   • 适用：特定数据类型（如整数、字符串）。

栈、队列、树、图各种基本操作的时间复杂度

一、栈（Stack） 栈通常用 数组 或 链表 实现，操作时间复杂度相同：

二、队列（Queue） 1. 普通队列（数组或链表实现）

2. 优先队列（Priority Queue）

三、树（Tree） 1. 二叉搜索树（BST，未平衡）

2. 平衡二叉搜索树（AVL/红黑树）

3. 堆（Heap，以二叉堆为例）

4. Trie（字典树）

四、图（Graph） 1. 图的表示方式

• 邻接矩阵：

  • 查询边是否存在：\(O(1)\)
  • 遍历相邻节点：\(O(V)\)（\(V\) 为顶点数）
  • 空间复杂度：\(O(V^2)\)

• 邻接表：

  • 查询边是否存在：\(O(k)\)（\(k\) 为相邻节点数）
  • 遍历相邻节点：\(O(k)\)
  • 空间复杂度：\(O(V + E)\)（\(E\) 为边数）

2. 常见算法时间复杂度

栈,顺序栈和链式栈

栈分为顺序栈(数组存储)和链式栈(链表存储)两种.

倒序输出单链表

不反转链表，递归倒序输出:

1. 先递归处理下一个节点
2. 在递归返回后输出当前节点的值

倒序输出单链表:

void printReverse(Node* head) {
  if (head == NULL) // 返回条件:空链表
   return;

  printReverse(head->next); // 先递归处理下一个节点
  printf("%d ", head->data); // 递归返回后输出当前节点数据
}

中缀转后缀

数据结构:stack,用于存放运算符;output,用于存放后缀表达式 步骤:

1. 输入变量:直接放入 output
2. 输入(:放入 stack
3. 输入):将 stack 中(之前的符号全部弹出,放入 output
4. 输入比栈顶优先级高的运算符:放入 stack
5. 输入比栈顶优先级低的运算符:弹出优先级高的栈顶符号,再将该符号放入 stack
6. 输入结束:将 stack 中剩余符号依次弹出,放入 output 代码:

char postfix[N]; // 存放后缀表达式
char stk[N];     // 存放运算符

void infixToPostfix (char* infix, char* postfix) {
  for (int i = 0; i < 表达式长度; i++) {
    char ch = infix[i];
    int j = 0; // 跟踪postfix中位置
    if (ch是数字或变量) {
      postfix[j++] = ch;
    } else if (ch == '(') {
      push(stk, ch);
    } else if (ch == ')') {
      while (栈非空 && 栈顶 != '(') {
        postfix[j++] = pop(stk);
      }
      pop(stk); // 弹出左括号
    } else {    // 运算符处理
      while (栈非空 && 栈顶元素优先级 >= ch的优先级) {
        postfix[j++] = pop(stk);
      }
      push(stk, ch);
    }
  }
  while (栈非空) { // 弹出剩余运算符
    postfix[j++] = pop(stk);
  }
  postfix[j] = '\0'; // 添加字符串结束符
}

BST 树操作

特点:左子树所有节点都比根小,右子树所有节点都比根大. BST 树的中序遍历结果按从小到大排列 最小值和最大值是叶节点或只有一个儿子的节点 BST 树插入:

1. 找到插入位置:如果插入的数比根大,往左走;如果插入的数比根小,往右走
2. 新建节点并连接(插入形成的节点一定是叶节点) BST 树删除:
3. 叶节点:直接删除
4. 有一个儿子:删除父亲,用儿子代替
5. 有两个儿子:找到左子树最大节点或右子树最小节点并删除,删除根,用该节点代替

BST 树插入节点(递归,链表):

BSTNode* insert(BSTNode* rt, int val) {
  if (rt为空)
    return 建立新节点; // 返回条件

  if (val < rt的值) {
    rt的左儿子 = insert(rt的左子树, val);
  } else if (val > rt的值) {
    rt的右儿子 = insert(rt的右子树, val);
  }
  return rt;
}

BST 树插入节点(循环,数组):

void insert(int* bst, int val) {
  if (bst[1]为初始值) {
    bst[1] = val; // val是根
    return;
  }

  int cur = 1; // 从根开始
  if (val < bst[cur]) {
    if (cur左子树空) {
      bst[cur * 2] = val;
      break;
    } else {
      cur = cur * 2;   // 下移cur
    }
  } else if (val > bst[cur]) {
    if (cur右子树空) {
      bst[cur * 2 + 1] = val;
      break;
    } else {
      cur = cur *2 + 1; // 下移cur
    }
  } else { // val已存在
    break;
  }
}

BST 树删除节点(递归,链表):

BSTNode* delete(BSTNode* rt, int val) {
  if (rt为空)
    return rt;

  if (val < rt的值) {
    rt的左儿子 = delete(rt的左子树, val);
  } else if (val > rt的值) {
    rt的右儿子 = delete(rt的右子树, val);
  } else { // 要删除rt
    // 情况1:是叶节点或只有一个儿子
    if (rt的左儿子 == NULL) {
      BSTNode* tmp = rt的右儿子;
      free(rt);
      return tmp;
    } else if (rt的右儿子 == NULL) {
      BSTNode* tmp = rt的左儿子;
      free(rt);
      return tmp;
    }
    // 情况2:rt有两个儿子
    BSTNode* tmp = rt左子树的最大节点;
    rt的值 = tmp的值;
    rt的左儿子 = delete(rt的左子树, tmp的值);
  }
  return rt;
}

辅助函数,找到左子树中最大节点:

BSTNode* findMax(BSTNode* node) {
  while (node的左子树非空) {
    node = node的左儿子;
  }
  return node;
}

AVL 树平衡

平衡因子 BF:左子树高度-右子树高度 平衡因子绝对值需要<=1 每次插入或删除后通过旋转保持平衡

AVL 树左旋(递归,链表):

AVLNode* leftRotate(AVLNode *y) {
    // 保存节点指针
    AVLNode *x = y->right;
    AVLNode *B = x->left;

    // 旋转操作
    x->left = y;
    y->right = B; // 冲突的左儿子变为右儿子

    // 更新高度（必须先更新y，再更新x）
    updateHeight(y);
    updateHeight(x);

    return x; // 返回新的根节点
}

图示: y x \ /
x – 左旋(y) –> y C / \
B C B

AVL 树左旋(递归,链表):

AVLNode* rightRotate(AVLNode *x) {
    // 保存节点指针
    AVLNode *y = x->left;
    AVLNode *B = y->right;

    // 旋转操作
    y->right = x;
    x->left = B; // 冲突的右儿子变为左儿子

    // 更新高度（必须先更新x，再更新y）
    updateHeight(x);
    updateHeight(y);

    return y; // 返回新的根节点
}

图示: x y / /
y – 右旋(x) –> A x / \ / A B B

堆的操作(大根堆为例)

大根堆的特点:对于任何一个节点,节点的值大于所有子树中节点的值 堆一定是完全二叉树 将普通完全二叉树改为大根堆:

从第一个非叶节点开始倒着遍历,将每个子树改为堆 (1) 如果根的值大于左右儿子,continue (2) 如果根的值小于一个儿子,用该儿子代替根,将根下移 (3) 如果根比两个儿子都小,用较大的儿子代替根,将根下移

大根堆中插入元素:

1. 插入末尾
2. 上浮到正确位置

大根堆排序:

1. 建立大根堆
2. 将堆顶和最后一个未排序的元素交换,调整未排序的部分,直到全部排序

堆化:

// 辅助函数,将i为根的子树堆化
void heapify(int* arr, int n, int i) {
  int largest = i;
  if (左儿子位置 < n && arr[左儿子] > arr[largest]) {
    largest = 左儿子位置;
  }
  if (右儿子位置 < n && arr[右儿子] > arr[largest]) {
    largest = 右儿子位置;
  }

  if (largest != i) {
    交换arr[i]和arr[largest];
    heapify(arr, n, largest);  // 递归调整受影响的子树
  }
}

// 将完全二叉树转换为大根堆
void buildMaxHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始，向前遍历到根节点
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

堆中插入节点:

// 辅助函数,上浮
void siftUp(int* heap, int idx) {
  while (idx > 0) {
    int pa = idx父亲的索引;
  }
  if (heap[idx] > heap[pa]) {
    交换heap[idx]和heap[pa];
    idx = pa; // 更新索引,向上检查
  } else {
    break;
  }
}

// 向大根堆中插入新元素
void insertMaxHeap(int* heap, int size, int capacity, int val) {
  if (size > capacity)
    return;

  heap[size++] = val; // 添加到末尾
  siftUp(heap, size-1);
}

堆排序:

void heapSort(int* arr, int n) {
    // 1. 构建大根堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        交换arr[0]和arr[i]; // 将当前根（最大值）移动到数组末尾
        heapify(arr, i, 0); // 对缩减后的堆进行调整
    }
}