一、名词解释

1、顺序表

采用顺序存储结构的线性表称为顺序表。

1. 线性表的顺序存储是指用一组地址连续的存储单元来存储线性表的数据元素。
2. 顺序表的特点：在逻辑上相邻的数据元素在物理次序上也相邻。
3. 顺序表是一种随机存取的存储结构，可通过数组来实现。
4. 顺序表的优点：
   • ① 存储密度大；
   • ② 可随机存取。
5. 顺序表的缺点：
   • ① 在插入、删除某一元素时需要移动大量元素；
   • ② 浪费存储空间；
   • ③ 属于静态存储形式，数据元素不能自由扩充。
6. 顺序表的查找、插入、删除，时间复杂度都为​ O(n)。
7. 顺序表的插入需要移动 ​n-i+1 个元素。
8. 顺序表的删除需要移动 ​n-i 个元素。
9. 顺序表操作算法的空间复杂度 ​S(n)=O(1)。

2、平衡二叉树

平衡二叉树：或者是空树，或者是具有下列性质的二叉排序树：

1. ① 左子树和右子树的深度之差的绝对值不超过 1；
   ② 左子树和右子树也是平衡二叉树。
2. 平衡二叉树又叫 AVL 树。
3. 平衡因子：该结点左子树和右子树的深度之差。
4. 平衡因子只能取 - 1、0、1。
5. 平衡调整的方法有：LL 型、LR 型、RR 型、RL 型。
6. 平衡调整的原则：
   ① 降低高度；
   ② 保持二叉排序树的性质。

3、循环链表

循环链表：是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。

• 从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。
• 在循环单链表中，表尾结点的 next 域指向 L，故表中没有指针域为 NULL 的结点。因此，循环单链表的判
• 空条件不是头结点的指针是否为空，而是它是否等于头指针。
• 由循环单链表不难推出循环双链表。不同的是在循环双链表中，头结点的 prior 指针还要指向表尾结点。

4、关键路径

<1> 在 AOE - 网中，从源点到汇点的带权路径长度最长的路径称作关键路径。

<2> 关键路径上的活动称为关键活动。

<3> 确定关键路径的 4 个描述量：

• 事件 ​(v_i) 的最早发生时间 ​Ve(i)

• 事件 ​(v_i) 的最迟发生时间 ​Vl(i)

• 活动 ​a_i = \langle v_j, v_k \rangle的最早开始时间 ​e(i)

• 活动 ​a\_i = \langle v_j, v_k \rangle 的最晚开始时间 ​l(i)

<4> 关键路径是求解工程时间最短问题的方法。

<5> 例如：设一个工程有 9 项活动，7 个事件。

5、最短路径

<1> 在带权有向图中源点到终点的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

<2> 求单源点的最短路径问题用迪杰斯特拉（Dijkstra）算法

<3> 求所有顶点之间的最短路径用弗洛伊德（Floyd）算法