参考答案：D

答案解析：m、n 是两个升序链表，长度分别为 m 和 n。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最小值。 

方法一：分段分析

这道题思维上有一定难度。

• 先分析 3 后面的元素，即 n=4,5,…,n ， p3=n 都是可以实现的，即该元素在进栈后立即出栈。
• 再分析 3 自身，一个元素不可能出栈两次，可以直接排除。
• 最后分析 3 前面的元素 1 和 2 。
  • 若 p1=1 且 p2=3 ，出栈序列可以为 1,3,2,… 此时 p3=2 。
  • 若 p1=2 且 p2=3 ，出栈序列可以为 2,3,1,… 此时 p3=1 。

综上，只有 3 自身被排除， p3 可能取值的个数共计 n−1 。

本题选C。

方法二：找规律

若 n=3 ，则出栈序列有5种，分别是 1,2,3 、 1,3,2 、 2,1,3 、 2,3,1 、 3,2,1 。当 p2=3 时，有2种情况，分别是1,3,2 和2,3,1 ，p3 可能取值的个数是2。

若 n=4 ，则出栈序列有14种，分别是

当 p2=3 时，有5种情况，分别是 4,3,2,1 、2,3,4,1 、 2,3,1,4 、 1,3,4,2 和1,3,2,4 ，p3 可能取值的个数是3。

综上，可以猜测若 p2=3 ，则 p3 可能取值的个数是 n−1 。

本题选C。

方法一：模拟

本题要求模拟平衡二叉树（AVL树）的插入过程。

将AVL树调整平衡的方法主要有旋转法和中序遍历法。

旋转法

观察插入不平衡结点的在所在子树上的路径：

• 先经过一个左指针，再经过一个左指针，对应LL平衡旋转。LL平衡旋转为右单旋转。
• 先经过一个右指针，再经过一个右指针，对应RR平衡旋转。RR平衡旋转为左单旋转。
• 先经过一个左指针，再经过一个右指针，对应LR平衡旋转。LR平衡旋转为先左后右双旋转。
• 先经过一个右指针，再经过一个左指针，对应RL平衡旋转。RL平衡旋转为先右后左双旋转。

由于关键字是从小到大插入，出现的都是RR平衡旋转。

中序遍历法

下面介绍中序遍历法，中序遍历法本质是利用AVL树的性质从结果出发直接找出调整后AVL树的根结点。

第一步：标记出插入不平衡结点从所在子树上的根结点到插入结点路径上的3个元素，标记3个元素为橙色，再标记3个橙色元素中间元素为红色，红色元素即为调整后子树的根结点，左边橙色元素为调整后子树左子树根结点，右边橙色元素为调整后子树右子树根结点。

第二步：写出子树的中序遍历序列，调整前后AVL树的中序遍历序列保持不变，将剩余结点加入到调整后的子树中。

此时，所有关键字都已经插入到AVL树中。

题目要求考察平衡因子为 0 的分支结点，所以我们只需要考察AVL树中所有的非叶结点，即结点 2、4 和 6 ，其左右子树高度相同，平衡因子为 0 ，所以平衡因子为 0 的分支结点总共有 3 个。

本题选D。

方法二：贪心

当然，模拟完整的AVL树插入过程非常麻烦，由于AVL树一定是平衡的，总共 7 个结点，我们很容易构造出一棵满二叉树，满二叉树的根结点和两个孩子结点为符合题目要求的结点，总共有 3 个结点。

题目要求考察平衡因子为 0 的分支结点，所以我们只需要考察AVL树中所有的非叶结点，其左右子树高度相同，平衡因子为 0 ，所以平衡因子为 0 的分支结点总共有 3 个。

本题选D。

参考答案：B

答案解析：利用三叉树的 6 个叶子结点的权构建最小带权生成树，最小的带权路径长度为(2 + 3) * 3 + (4 + 5) * 2 + (6 + 7) * 1 = 46。

方法一：模拟

T 的带权（外部）路径长度最小是 (2+3)×3+(4+5)×2+(6+7)×1=46 。

本题选B。

方法二：贪心

下面提供秒题解法。

题目要求“最小”，四个选项中A选项最小，直接选A？

如果是这样你就错了， (2+3+4+5+6+7)×1=27 ，A选项表示一棵六叉树。

与 T 为三叉树矛盾，所以我们只能在剩余三个选项中选最小值。

本题选B。

后序线索二叉树的遍历序列即二叉树后序遍历序列，根据题意，很容易画出示意图：

X 的右线索指的是 X 的父结点。

本题选A。

二叉排序树又称二叉搜索树，本题考察二叉搜索树的性质。

方法一：性质

很明显，本题要求我们分两种情况讨论。

若 v 是 T1 的叶结点，为情况一，直接删除，再插入 v ， v 会复原到原来的位置，则 T1 与 T3 相同。

若 v 不是 T1 的叶结点，为情况二或情况三，再插入 v ， v 会变成叶结点，则 T1 与 T3 不同。

仅II、III正确。

本题选C。

方法二：断言

二叉搜索树的删除非常复杂，如果没有掌握也没有关系。

若 v 是 T1 的叶结点，插入 v ， v 还是叶结点，则 T1 与 T3 相同。

若 v 不是 T1 的叶结点，插入 v ， v 会变成叶结点，则 T1 与 T3 不同。

仅II、III正确。

虽然这样推导不严谨，但足够高效就行。

本题选C。

参考答案：C

答案解析：各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

本题考察度的定义：某顶点的度为以该顶点为端点的边的数目。

我们将顶点依次编号为 1,2,3,4 。

方法一：观察邻接矩阵

顶点 1 的度为包含 1 为端点的边数，即第一行和第一列非零元素的个数。

顶点 2 的度为包含 2 为端点的边数，即第二行和第二列非零元素的个数。

顶点 3 的度为包含 3 为端点的边数，即第三行和第三列非零元素的个数。

顶点 4 的度为包含 4 为端点的边数，即第四行和第四列非零元素的个数。

本题选C。

方法二：画出有向图

本题选C。

参考答案：D

答案解析：D 选项是深度优先遍历不是广度优先遍历的顺序。

方法一：模拟

广度优先搜索就是用一圈一圈扩散的方式进行搜索。

我们依次以A、B、C、D四个选项中序列的第一个元素为起点画出下面这个广度优先搜索过程，用颜色由深入浅标记这个扩散过程，颜色相同的结点在同一层，输出序列中，颜色相同的结点的关键字即同一层结点的关键字一定相邻。

本题选D。

方法二：找错误选项

我发现命题组设置错误选项一般比较无脑，D选项出现了无脑的a, b, c, d这种顺序，明显就是一个深度优先搜索顺序，直接排除。

本题选D。

参考答案：C

答案解析：根据 AOE 网的定义可知，关键路径上的活动时间同时减少，可以缩短工期。

方法一：完整推理

参考答案：A

答案解析：一棵高度为 2 的 5 阶 B 树，根结点只有到达 5 个关键字的时候才能产生分裂，成为高度为 2 的 B 树。

方法一：公式法

本题选A。

方法二：构造法

m 阶B树每个结点（除根结点）关键字数量 n 为 ⌈m/2⌉−1≤n≤m−1 。本题要求为5阶B树， 2≤n≤4 。

又该B树的高度为2，根结点至少有两棵子树，很容易构造出题目要求的B树。

该B树总共5个关键字。

本题选A。

方法三：选项排序 + 贪心

下面提供秒题解法。

题目要求“最少”，四个选项中A选项最少。

本题选A。

参考答案：C

答案解析：基数排序的第 1 趟排序是按照个位数字来排序的，第 2 趟排序是按然十位数字的大小进行排序的，答案是 C 选项。

本题考察基数排序，直接进行模拟即可，按照从低位到高位的顺序进行。

本题选C。

tips：本题中 007 没有简单写作 7 ，如果遇到高位缺失的情况，要记得自己补 0 。