915 真题

约 6734 个字 31 行代码 预计阅读时间 23 分钟

2015

判断题

1. 堆一定是完全二叉树，完全二叉树不一定是堆，二叉排序树不是堆

完全二叉树的父节点和子节点的关键字没有大小关系，二叉排序树才有

二叉排序树和堆又有区别：

• 二叉排序树的左右子树是有次序的
• 堆是无次序的（当含有一个子树的时候）

2. 折半查找仅适用于 有序的 、顺序存储结构，也就是数组

简答题

1. 什么是拓扑排序，其一般应用场景是什么？

拓扑排序：在有向无环图中进行拓扑排序，是将图中所有顶点排成一个线性序列，使得图中任何一条边 <u,v>，在线性序列中 \(u\) 出现在 \(v\) 之前。简单来说：有某个集合上的一个偏序得到该集合上的一个全序。

应用场景：判断有向图是否存在环，求 \(AOE\)网的关键路径的过程。

2. 什么是哈夫曼树？简述哈夫曼编码的过程，并证明有 \(n\) 个叶子的哈夫曼树有 \(2n-1\) 个顶点、

哈夫曼树：带权路径长度最小的二叉树称为哈夫曼树

哈夫曼编码：对构造的哈夫曼树，约定左分支表示 \(1\),右分支表示 \(0\)，从根节点到叶子结点的个分支表示组成的编码就是哈夫曼编码

证明：数学归纳法，或者 利用 \(e = n - 1\) 公式来计算。（推荐前者）

2016

判断题

1. 拓扑排序 - kahn算法：用队列维护一个入度为 0 的结点的集合 - DFS：在递归结束前输出，形成 逆拓扑排序
2. 不带头结点的单向循环链表 head 为空表的条件是 head == NULL

解答题

1. 评价算法 - 正确性：算法应道满足具体问题的需求。 - 可读性：算法应容易供人阅读和交流。 - 健壮性：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地做出反应。 - 效率和存储需求：效率是算法执行的时间；存储量需求是算法执行过程中所需要的最大存储空间。
2. 算法的定义和五个特性 - 定义：算法是对特定问题求解步骤的一种描述，它是指令的优先序列。 - 五个特性：有穷性，确定性，可行性，输入，输出。 - 算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。
3. 堆是一棵完全二叉树，对于每个结点的关键字都大于/小于等于其父亲结点的关键字。

2017

选择题

散列表的查找效率：

• 选取的散列函数
• 处理冲突的方法
• 装填因子的大小

解答题

1. 在算法设计中，什么是空间时间权衡原则？请举例说明时间复杂度和空间幅度权衡原则。

时空权衡主要是在某些情况下时间会成为决定因素或者空间会成为决定因素时，我们需要牺牲某一部分来换取另一部分效率的提高。

用时间换空间

• 稀疏矩阵的数据压缩，也是用时间换空间。
• 顺序查找是用时间换空间，占用内存小，但是查找速度为O(n)。

用空间换时间

• 哈希表是用空间换时间，它需要占用大量的内存空间，但是可以达到O(1)的查找速度。

• B+树是在磁盘上的数据记录之外又建立了一层树形索引，因此需要额外的存储空间，但与此同时用索引可以更快找到需要的记录。

• 基数排序

2. 完全二叉树的定义

一颗深度为 h 的有 n 个结点的二叉树，对树中的结点按照从上至下，从左到右的顺序进行编号，如果编号为 i 的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这课二叉树称为完全二叉树。

3. 二叉检索树的定义

一颗空树。或者具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根节点的值；若右子树不空，则右子树上所有结点的值均大于它的根节点的值。

4. 非递归的DFS中栈的变化。

// 非递归形式
bool st[N];
vector<int> e[N];
void dfs_stack(int s){
    stack<int> stk;
    stk.push(s);
    st[s] = true;

    while(stk.size()) {
        int u = stk.top();
        stk.pop();

        for(auto v:e[u]) {
            if(!st[v]) {
                st[v] = true;
                stk.push(v);
            }
        }
    }

}

5. 贪心算法的多机作业调度问题

2018

选择题

1. 时间复杂度分析

for(int i=1;i<=n;i*=10)

上述时间复杂度是 \(\log_{10}n\) ,而不是 \(\frac{n}{10}\),切记不要马虎。

2. 外部排序：多路归并算法。

3. 链表题

4. 广义表 \(LS = (a_1,a_2,\cdots,a_n)\)

• 在广义表的定义中，\(a_i\) 可以是单个元素，也可以是广义表，分别称为广义表的 原子 和 子表
• 当广义表非空时，称第一个元素 \(a_1\) 为表头 （Head) ,称其余元素组成的表 \((a_2,a_3,\cdots,a_n)\) 是广义表的表尾 （Tail）
• 用小写字母表示原子，用大写字母表示广义表
• 任何一个列表其表头可能是原子，也可能是列表，而其表尾必维列表。

举例：\(A=(a,(b,c,d))\)

GetHead(A) = a ; GetTail(A) = ((b,c,d))

5. 二叉树的性质：

• \(n_0 = n_2 + 1\) ，(零等于二加一)
• \(e = n-1\) , n 个结点 有 n-1 个分支
• \(n = n_0 + n_1 + n_2\)
• 二叉树的高度：\(\lfloor \log _2n \rfloor \ +1\)
• 给定 \(n\) 个结点组成二叉树的个数，卡特兰数：\(\frac{C_{2n}^n}{n+1}\) , 注意 \(C_{2n}^n= \frac{2n × \cdots × (n+1)}{n!}\)

6. 哈夫曼树的构造方式：每次构造都选择两个权值最小的树作为新节点的孩子

7. 区分线性结构和非线性结构

• 常见的线性结构：数组，链表，栈，队列
• 常见的非线性结构：树（一对多），图（多对多），广义表

8. 二分查找的要求：有序表且支持随机索引 （一定是顺序存储的）

9. 图的遍历

• DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次
• BFS 每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。 (用队列来维护)

10. 二叉树的性质，上面总结好了

判断题

1. DAG ：有向无环图
2. 时间复杂度相同的程序，输入的规模不相同（\(n\) 不同），运行时间也不同
3. 完全二叉树的性质，这里给出除了二叉树之外的性质 - 定义：高度为 \(h\)、有 \(n\) 个结点的二叉树，当且仅当其每个结点都与高度为 \(h\) 的满二叉树中编号为 1 ~ n 的结点一一对应时，称为完全二叉树。 - 度为 \(1\) 的点至多有一个（可能没有）
4. Dijkstra 用于求解单源最短路径，也可以用于求多源最短路径

填空题

1. 快排的时间复杂度取决于递归的层数，这里没说明具体的 \(n\),只能按照快排的一般情况来说了

• 最好情况，划分的尽可能平均，时间复杂度 \(O(n\log n)\)
• 一般情况，时间复杂度 \(n\log n\)
• 最坏情况，每次都以最小的一个划分，递归 \(n\) 层，时间复杂度 \(O(n^2)\)

2. 拓扑排序的定义：在一个 DAG（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。

3. 主定理，比较 \(log_ba\) 和 \(f(n)\) 的时间复杂度的大小即可 $$ T(n) = a\,T(n/b) +f(n) $$ 计 \(f(n)\) 的时间复杂度 为 \(O(n^x)\),

• \(log_ba>x\) 时：\(T(n)\) 的时间复杂度为 \(O(n^{log_ba})\)
• \(log_ba = x\) 时：\(T(n)\) 的时间复杂度为 \(O(n\log n)\)
• \(log_ba < x\) 且 \(当 n \to +\infty,\exist c <1 ,s.t. af(n/b) \le cf(n)\),那么T(n)$ 的时间复杂度为 $ \(O(n^{x})\)

这里给出一个例题，对第二点进行说明

case 1： $$ T(n) = 2T(n/2) + n $$ 这里 $f(n) = O(n^1) $ , \(\log_22 = 1\),

符合主定理的第二个条件，进而 \(T(n)\) 的时间复杂度为：\(O(n \log n)\)

---

这里给出两个例题，对第三点进行说明

case 2: $$ T(n) = 3T(n/4) + n\log n \tag2 $$ 这里 \(f(n) = O(n \log n) = O(n^{1+log_n{[log n ]}})\)，\(log_34 < 1+log_n{[log n ]}\) $$ \begin{align} 3f(n/4) &= 3 \frac{n}{4} \log{\frac{n}{4}}=\frac{3}{4}n \log{\frac{n}{4}} \\ &=\frac{3}{4}n [\log n - \log 4] \\ &假设存在 c \le 1, \ &s.t.\frac{3}{4}n [\log n - \log 4] \le cn \log n \\ &只需 \frac{3}{4} \le c < 1 即可 \end{align} $$

满足第三个条件，进而 \(T(n)\) 的时间复杂度为：\(O(n \log n)\)

---

case 3: $$ T(n) = 2T(n/2) + n\log n \tag3 $$ 这里 \(f(n) = O(n \log n) = O(n^{1+log_n{[log n ]}})\)

\(log_22 =1 < 1+log_n{[log n ]}\) $$ \begin{align} 2f(n/2) &= 2 \frac{n}{2} \log{\frac{n}{2}}=n \log{\frac{n}{2}} \\ &= n [\log n - \log 2] \\ &假设存在 c \le 1, \ &s.t. \,\, n [\log n - \log 2] \le cn \log n, \\ &即 (1-c) \log n \le 2 ，当 n 充分大时，这显然是不成立的 \ \end{align} $$ 主定理条件不满足，主定理失效，本题采用递归树的方法求解。

共扩展 k 层，\(2^k =n\) ,每次 除以 2

第一层是 \(nlogn\)

第二层是 $\frac{n}{2} log[\frac{n}{2}] =\frac{n[\log n - \log 2]}{2} =\frac{n[\log n - 1]}{2} $

\[ \begin{align*} T(n) &= n \log n + n(\log n -1) + n(\log n-2) + \cdots + n(log_n -k+1) \\ &=(n \log n) \log n - n(1+2+\cdots+k-1) \\ &=n^2log^2n -nk(k-1)/2 \\ &= O(n \log^2n) \end{align*} \]

4. BFS 需要队列来维护，DFS 用栈维护（系统栈或者stack）
5. 4 个元素的出栈顺序，卡特兰数：\(\frac{C_{2n}^n}{n+1}\) , 注意 \(C_{2n}^n= \frac{2n × \cdots × (n+1)}{n!}\)

解答题

1. 渐进复杂度

大 \(\Theta\) 符号：对于函数 \(f(n)\) 和 \(g(n)\) , \(f(n)=\Theta(g(n))\),当且仅当 \(\exists \,c_1,c_2,n_0 >0\),使得 $$ \forall n \ge n_0,0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) $$ 大 \(O\) 符号：大 \(\Theta\) 符号同时给了我们一个函数的上下界，如果只知道一个函数的渐进上界而不知道其渐进下界，可以使用 \(O\) 符号。\(f(n)=O(g(n))\)，当且仅当 \(\exists \,c,n_0\)，使得 $$ \forall n \ge n_0,0 \le f(n) \le c \cdot g(n) $$ 大 \(\Omega\) 符号

同样的，我们使用 \(\Omega\) 符号来描述一个函数的渐进下界。\(f(n)=\Omega(g(n))\)，当且仅当 \(\exists \, c,n_0\) ，使得 $$ \forall n \ge n_0,0 \le c \cdot g(n) \le f(n) $$

2. 共享栈

typedef struct shareStack{
    int data[MaxSize];
    int top1=0;
    int top2=MaxSize;
}shareStack;

注意：写入栈出栈的时候先判断栈满或栈空

3. 最小生成树 和 图的遍历

prim （加点法） 和 Kruskal （加边法）和 BFS (宽度优先遍历) 和 DFS （深度优先遍历）

加边法：\(O(n^2)\)

​ 下面的过程重复 n-1 次

​ 每次找到距离 集合最近的顶点 t

​ 用 t 更新其他点到集合的距离

加边法：\(O(n \log n)\)

​ 每次找最小的边，且避免成环

​ 维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。

​ 用并查集来维护

DFS:

​ 核心：“能走必须走”

​ 在递归前输出：DFS 序列

​ 在递归后输出：逆拓扑排序

​ DFS 和 拓扑排序 可以验证图是否连通。

BFS:

​ 类似于二叉树的层序遍历

​ BFS 必须要借助一个 辅助队列

​ 在 BFS 中 ，入队访问 == 出队访问

4. 二叉树的性质题，送分题

5. 给出二叉树的先序遍历了，可以直接写出二叉树的中序遍历，（中序遍历是有序的，排好序就是中序遍历的）

根据二叉树的前序遍历和中序遍历就可以唯一确定一颗树，从而将树画出来了

二叉树的删除,删除结点是 z

• z 是叶结点，直接删除
• z 是单支，让其子树代替该节点的位置
• z 有左右两颗子树，让 z 的直接后继（或直接前驱）p 替代 z，删除他的直接后继 p。从而转变成前两种情况

散列表和二叉树的优缺点比较

• 散列表插入，删除的速度快，时间复杂度是 \(O(1)\) ,但存在冲突
• 二叉树的排列是有序的，散列表是不排序的，但插入和删除慢,时间复杂度是 \(O(n)\)。

6. AOE 图

• AOE 网：用边表示活动的网络

• 关键路径：从起点到终点的 最长路

• 事件 V

  1. 最早开始时间：最长路（从开始到该点的）
  2. 最晚开始时间：整个工期的时间 - 最长路（该点到最后的）

• 活动 E :\(A\xrightarrow{e}B\)

  1. 最早开始时间：==事件A的最早开始时间 == 最长路（从开始到 A 的）
  2. 最晚开始时间：整个工期的时间 - 最长路（B 到 最后的）- e 的权值

• 时序图和AOE 网的转换关系

  出的顶点先别画，有需要再添加上顶点，最后将所有没有顶点连接的指向终点

  视频讲解参考：【传送门】

• AOE 网的邻接表

  1. 头结点：

     顶点	第一个出边的指针

  2. 表结点

     邻边顶点的下标	活动的边权值	下一个出边的指针

  3. 图示

     

7. 散列表

解决冲突的办法

• 开放地址法：\(H_i = (H(key)+d_i)\%m\)

  1. 线性探测法：\(d_i = 0,1,2,\cdots ,m-1\)

  2. 平方探测法：\(d_i = 0,1^2,-1^2,2^2,-2^2,\cdots ,k^2,-k^2\)

  3. 再散列法：\(d_i = Hash_2(key)\)，就是每一次加 \(Hash_2(key)\)

     具体形式就是：

     \[ H_i = (H(key) + i × Hash_2(key) )\%m \]

• 拉链法

• 注意：开放定址下，删除一个元素，可以给它做一个删除标记，不能物理删除。因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。

8. 小根堆和希尔排序和直接插入排序

堆排序

• 建堆时间为 \(O(n)\)，之后有 \(n-1\) 次向下调整操作，每次向下调整操作的时间复杂度为 \(O(log n)\),故整个调整的时间复杂度为 \(O(n log n)\)

• 堆排序的时间复杂度为 \(O(n log n)\)

删除堆顶元素

1. 将堆的最后一个元素与堆顶交换，将堆的最后一个元素删除

   2. 对堆顶 向下调整（down）

希尔排序

又称 “缩小增量排序”

• 每组内的下标是一个等差数列，组内用插入排序

直接插入排序

类比与打扑克牌时的 插牌 过程

第一个元素 \(q[0]\) 直接插入就好

对于 第二个元素到第 \(n\) 个元素

​ 从当前元素相前看，找到第一个小于 \(w\) 的值，插在这个值后面

2019

选择题

1. 数据结构的三要素：逻辑结构，存储结构，数据的运算

ADT:抽象数据结构 是一个数据模型以及定义在该模型上的一组操作。

2. 散列表内元素是无序的（因为冲突调整后变为无序了，所以找最大值要扫描一遍

3. 拓扑排序，2018年考过，主要是考虑入度为零的点。

在一个 DAG（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。

4. 考察十大排序

• 选择排序：每次选一个最小的

• 快速排序：部分有序对快排 最痛苦。

• 希尔排序：缩小增量排序

• 冒泡排序：咕噜咕噜的将最小值冒出来

• 插入排序：类似 “插牌” 的过程

• 归并排序：二路归并，需要用到一个辅助数组暂时存储元素

5. 考察二叉树的性质：$n_0 = n_2 + 1 $ (零等于二加一)

6. 栈的出栈排列，模拟就好了

7. 链表的特点：

• 能充分利用所有存储单元
• 每个元素要存储指针占用存储空间
• 只能实现顺序存取，不能实现随机索引
• 插入和删除不需要移动元素（改变指针就可）

8. 无向图中的度：与顶点依附的边的个数

9. 二分查找的要求：有序且可随机索引（顺序存储）

10. 完全二叉树比二叉树多的性质：度为 \(1\) 的点至多有一个（可能没有）

判断题

1. Huffman 树也没有度为 1 的点，显然不一定是完全二叉树
2. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。
3. 仍然考察的是散列表的性质，散列表内元素是无序的（因为冲突调整后变为无序了
4. 最小生成树负权是没有影响的，Dijkstra 是不适用于负权边的。
5. 考察二叉搜索树 (BST) 的性质，中序遍历是有序的

填空题

1. 考察时间复杂度，数据规模太小的可以不用看，因为时间复杂度是一种渐进表示法，在充分大时才准确。

直接上图展示，由图可得在数据规模小的时候，时间复杂度是不准的。

2. 考察快排在部分有序的情况下，时间复杂度达到最坏：\(O(n^2)\)

for(int i=0;i<A.size();i++)
    qsort(A,0,i);

每一次都在一个已经排好序的数组后面增加一个新元素，在进行快排，而这恰好是快速排序的最坏的情况

每一次的时间复杂度是 \(O(n^2)\),所以总的时间复杂度是 \(1^2+2^2+\cdots+n^2 = O(n^3)\)

for(int i=0;i<A.size();i++)
    qsort(A,0,A.size()-1);

第一次是对无序的数组进行排序，复杂度是 \(O(n \log n)\)

剩下的每一次都是有序的数组进行快排，是最坏的情况，复杂度：\(O(n^2)\)

所以总的时间复杂度是 \(n\log n +(n-1) n^2 = O(n^3)\)

3. 广义表的操作，2018年整理过了

4. 堆排序的性质：

• 建堆时间为 \(O(n)\)
• 有 \(n-1\) 次向下调整操作，每次向下调整操作的时间复杂度为 \(O(log n)\),故整个调整的时间复杂度为 \(O(n log n)\)
• 堆排序的时间复杂度为 \(O(n log n)\)

5. 完全二叉树的前中后遍历，模拟题

解答题

1. 数学归纳法的证明题，看起来显然的性质还要推一遍，再去把 yxc 的证明听听

2. 用一个队列实现栈。

3. 考察 DFS 和 BFS ，简单模拟题

4. 考察数据结构和数据结构的基本操作。

哈希表（HashTable ,也称 散列表）本身是 \(key\) 到 \(addr\) 的对应，但却可以通过 A[ hash(key) ] = value 的方式来得到 \(key\) 和 \(value\) 的对应关系

5. 二叉树的遍历，简单模拟题，算法题考察了对称的二叉树，用同一种遍历顺序遍历同时遍历两棵树即可

6. 考察最小生成树

最小生成树（MST）：对一个带权连通无向图 \(G=(V,E)\) ,生成树中所有边上的权值和最小的称为最小生成树

无向图中缩小给定最小生成树的一条边，判断最小生成树是否需要改变，但不能通过 prim 和 kruskal 的方法。

表答给了一种方法，觉得很好，记录一下。

树的等价定义：无回路，但增加一条新边，得到一个且仅有一个回路

根据如上定义，我们将这条缩短的边加入最小生成树中，此时一定构成了一个回路，然后删除该回路中权值最大的边，剩下的就是得到的新的最小生成树。如果删除的是新缩短的边，说明最小生成树不需要改变，如果删除的其他变，显然删除的其他边，显然是新缩短的边替换了其他边，此时需要修改。

图的权值第二小的边一定包含在最小生成树中吗？

不一定，考虑特殊情况，权值最小的边足够将所有图结点包含，那么第二小的边就不会出现在最小生成树中。

7. 哈希表，冲突的解决方式是再散列的方法，2018总结过。

​

选择题 1 个（待定） -2

判断题 1 个（待定） -2

填空题 3 个 -4

解答题

1. 6
2. 6 （-6
3. 10
4. 16 （-8
5. 满分
6. 定义没写完全，kruskal 的判断错了一个 -5
7. 满分

编程题

1. 满分
2. 满分
3. -5

总分：128）分数图一乐

2020

选择题

5. 二叉树的前中后层序遍历时间复杂度：\(O(n)\) ，空间复杂度: \(O(n)\)

6. 折半查找的比较次数最多不会超过树的高度，查找失败时 比较 \(h\) 次，时间复杂度 ：\(O(\log n)\)

7. 判环的算法：

• DFS
• 拓扑排序
• 并查集

判断题

1. 最大生成树和最小生成树类似，只不过在一个图的所有生成树中边权值和最大的生成树即为最大生成树。

填空题

递归条件：

• 问题可以被分解成相同结构的子问题，通过 自我调用 解决 子问题
• 结束条件 定义了最简子问题的答案，可以使递归结束。

简答题

1. 散列表：根据关键字直接进行访问 的数据结构，建立了 关键字和存储地址 之间的 直接映射 关系

散列表不能随便删除已有元素：因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。要删除一个元素，可以做一个删除标记，进行逻辑删除

2. 流程图题

3. 最小生成树

4. AVL 树，考察了最少结点的递推公式

5. Dijkstra

6. 比较了十大排序

7. 树和二叉树的转换，并查集的合并

并查集实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

下图表示并查集的合并操作：

2021

选择题

1. 衡量算法优劣的标准

• 正确性：算法能够解决实际问题，并且给出正确的结果
• 可读性：算法应该实现方式清晰易懂，便于理解和修改
• 健壮性：算法能够适应各种输入数据，包括异常情况
• 效率和低存储要求：算法应该能够快速运行，时间复杂度和空间复杂度越低越好

渐进复杂度的定义：

算法中基本操作重复执行的次数是问题规模 \(n\) 的某个函数 \(f(n)\) ，算法时间量度记作 \(T(n)=O(f(n))\) ,它表示随问题规模 \(n\) 的增大算法执行时间的增长率和 \(f(n)\) 的增长率相同，成为算法的渐进实践复杂度。

2. 共享栈：提高空间的使用效率，减少发生上溢的可能性

3. 排序算法中用到分治思想：堆排序，快速排序，归并排序，希尔排序

4. 循环队列的长度：\((Rear - front+MaxSize)\%MaxSize\)

5. 将树和森林转化为二叉树是为了：为了方便遍历

6. 最小生成树不一定是唯一的，但最小生成树的边的权值之和是唯一的，且是最小的。

• 最小生成树：Minimum-Spanning-Tree,MST

7. 一种合理的数据结构来表示一本书的目录结构可能是树形结构。

在树形结构中，每个节点都表示一个目录项，如章节标题、小节标题或者子章节。叶子节点表示书中实际的文本内容。每个节点都可以有多个子节点，表示这个目录项下面有多个子目录项。

• 二叉树 （Binary Tree）它的特点是每个节点最多只能有两个子节点，一个是左子节点，一个是右子节点。
• 二叉排序树 (BST 树) 是一种用来维护有序关键字的数据结构。它可以用来存储和维护一个有序的集合，并快速查找、插入和删除元素。
• 平衡二叉树 (AVL 树) 可以保证在查询、插入和删除操作时，树的高度不会变得过高，从而保证了操作的时间复杂度。
• 哈希表（Hash Table）是一种常见的数据结构，它通过把键值映射到数组的索引来存储数据。哈希表的优点在于查询、插入和删除的时间复杂度都很低

8. 并查集（Union-Find Set）是一种常用的数据结构，它用于维护一组不相交的集合。并查集支持两种操作：合并两个集合（Union）和查询两个元素是否在同一个集合中（Find）。

9. 在单链表上实现的插入和删除操作要比在顺序表上实现的效率高。

10. 循环链表的具体操作，见 OneNote

判断题

1. 广义表的定义，见2018年选择
2. 将大根堆调整为小根堆的时间复杂度：\(O(n)\) ,\(O(n)\) 建堆，堆排序 \(O(n\log n)\)
3. dijkstra 不适用于负权边，dijkstra 采用贪心的思想。
4. 一个结点数为 n 的树，任意结点左右高度差不超过2，树的高度是 \(O(\log n)\) : 用大 \(O\) 表示法的目的是因为 \(n\) 较小时会出现特例，如 \(n=3\) 且为单支的情况。
5. 下三角矩阵由于只有主对角线（含主对角线）以下的元素值不为 0，因此我们可以通过压缩矩阵存储来节省空间。

填空题

1. 数数题：\(loc + 前面的个数即可\)
2. --
3. --
4. --
5. 对于完全二叉树：度为 \(1\) 的结点只有 \(1/0\) 个 - 一般的二叉树：\(n_0 = n_2+1\) - \(e=n-1\) ，分支 == 顶点减一

解答题

1. 渐进复杂度定义：算法中基本操作重复执行的次数是问题规模 \(n\) 的某个函数 \(f(n)\) ，算法时间量度记作 \(T(n)=O(f(n))\) ,它表示随问题规模 \(n\) 的增大，算法执行时间的增长率和 \(f(n)\) 的增长率相同，成为算法的渐进时间复杂度。

2. 递归过程：一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程，成为递归过程。

运行调用过程之前，系统要做的三件事

• 将所有的 实参，返回地址 传递给被调用过程
• 为被调用过程的局部变量分配扩建
• 将控制转移到被调用过程的入口

运行被调用过程之后，系统要做的三件事

• 保存被调用过程的结果
• 释放被调用过程的空间
• 依照返回地址返回到调用过程

重点是这几个参数：实参，返回地址，本层参数，局部变量

3. 后面是常规大题了

---

Created: December 1, 2023
Last update: April 24, 2026

Discussion