数据结构-期末复习
栈和队列
栈的排列方式:
n个不同的元素进栈, 出栈元素不同排列的个数为
$\frac{1}{n+1}C_{2n}^n$
堆顶栈
栈满条件: top0 + 1 = top1 (无论是否从0或1开始)
循环队列判断队满的情况:
(q.rear + 1) % Maxsize == q.front
栈和队列的异同点
栈和队列都是加了限制的线性表,栈是先进后出表,队列是先进先出表。栈和队列的插入和删除操作都在端点进行,栈的插入和删除在同一端点,队列的插入和删除在不同的端点进行。
首元结点, 头结点, 头指针的区别
- 首元结点（First Node）：链表中的首元结点是指链表中第一个实际存储数据的结点。它是链表中第一个具有数据域和指针域的结点，用来存储链表中的第一个元素。
- 头结点（Head Node）：头结点是在链表中添加的一个额外的结点，位于链表的前面，不存储实际的数据。头结点的作用是为了方便链表的操作和管理，它可以包含一些附加信息，如链表的长度等。
头指针（Head Pointer）：头指针是指向头结点的指针，它是链表的入口。通过头指针，可以找到整个链表的起始位置。头指针用来记录链表的基地址，在进行链表的遍历、插入、删除等操作时，可以通过头指针来进行操作。
首元结点是链表中的第一个实际存储数据的结点。
- 头结点是在链表中添加的一个额外结点，用于方便链表的操作和管理，不存储实际的数据。
- 头指针是指向头结点的指针，用来记录链表的基地址。
哈希表
假设哈希表长为m，p为小于等于m的最大质数，则哈希函数为
H(key) = key % p
哈希表平均查找长度
查找成功的平均查找长度:
ASLsucc = 查找次数 / 元素个数
查找失败的平均查找长度:
ASLunsucc = 查找次数 / 散列后的地址长度(p)
拓扑排序
关联路径求法:
具体步骤:
- 令ve(源点) = 0, 求最早的发生时间ve()
- 令vl(汇点) = ve(汇点), 求最迟的发生时间vl()
- 根据ve()值求所有点的最早开始时间ve()
- 根据每个点的最早开始时间ve(), 求弧的最早开始时间e()
- 根据vl()值求所有点的最迟开始时间vl()
- 根据每个点的最迟开始时间vl(), 求弧的最迟开始时间l()
- 求AOE网中所有活动的差额d(), 找出所有 d() = 0 的活动构成关键路径
查找
排序
如何判断序列是否执行了快速排序:
要点: 每经过一次快速排序, 轴点元素都必然就位。也就是说, 一趟排序至少有一个元素在其最终位置上
最终排序位置是：2, 5, 12, 16, 28, 32, 60, 72，而选项中正确的位置有：
A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60
第一趟排序，确定一个元素位置
第二趟排序，又确定一个或两个元素位置
当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B选项情况）
当第一趟元素确认位置不是最左或最右时，第二趟能确认2个位置（C选项情况）
线索二叉树:
