方法一：定义法

本题为多层循环，用定义法求解 ：

本题选C。

方法二：公式法

本题为多层循环中嵌套循环指针无关类型题。

外层循环时间复杂度为 O(log⁡n) ，内层循环时间复杂度为 O(n) 。

由公式

可得总时间复杂度为  。

本题选C。

方法一：模拟

本题考察中缀表达式转后缀表达式，需要利用栈作为辅助。

没有必要扫描完整个表达式，只需要扫描到 f 即可，过程模拟如下：

本题选B。

方法二：观察表达式

其实我们没有必要老老实实模拟整个流程，只需要观察中缀表达式即可， a/b+(c∗d−e∗f)/g 扫描到 f 时，此时 f 还没有被输出，观察前面与 f 相关的操作，也是没有能够输出的操作，这些操作都暂存在栈中，依次为 +(−∗ ，越靠近栈顶的优先级越高，显然在括号中 ∗ 比 − 的优先级高，栈顶的是 ∗ 。

本题选B。

循环队列中区分队空和队满，有三种处理方式：

① 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一个较为普遍的做法，约定以“队头指针在队尾指针的下一个位置作为队满的标志”。

队满条件：(Q.rear + 1) % MaxSize == Q.front

队空条件：Q.front == Q.rear

队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize

② 类型中增设表示元素个数的数据成员size：

队满条件：Q.size == MaxSize

队空条件：Q.size == 0

队列中元素的个数：Q.size

③ 类型中增设用于区分队满还是队空的数据成员tag，入队标记tag = 1，出队标记tag = 0：

队满条件：Q.front == Q.rear && tag == 1

队空条件：Q.front == Q.rear && tag == 0

队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize

以上三种方法本人简记为：

① 空一法（空格法）

② 计数法

③ 标记法（标志法）

A[0..M-1]数组的容量为M，队列中最多能容纳 M-1 个元素，很明显采用了空一法。

把变量名对着题目改一遍，很明显A选项符合条件。

本题选A。

中序线索化先进行中序遍历， x 左线索指向中序序列中 x 的前驱，x 右线索指向中序序列中 x 的后继。

中序遍历可以用投影法或者环线法。

得到中序遍历序列为d, e, b, x, a, c。

本题选D。

方法一：性质

将森林F转换为对应的二叉树T，即二叉树T用左孩子右兄弟法表示森林。森林F中的叶结点一定没有孩子结点，转化为二叉树T没有左孩子，所以F中叶子的个数等于T中左孩子指针为空的结点个数。

本题选C。

方法二：画图

如果仅仅利用性质分析觉得过于抽象，直接画图举例：

F中叶子的个数为5。

A选项，T中叶结点的个数为3，错误。

B选项，T中度为1的结点个数为2，错误。

C选项，T中左孩子指针为空的结点个数为5，正确。

D选项，T中右孩子指针为空的结点个数为3，错误。

本题选C。

方法一：观察选项

D选项中110是1100的前缀，不是前缀编码。

本题选D。

方法二：哈夫曼树

直接画出每种编码方案对应的哈夫曼树，遵循路径左0右1的规则。

最后检查所有编码必须存储在叶结点。

下图用黄色结点标记存储编码。

本题选D。

参考答案：D

答案解析：按照拓扑排序的算法，每次都选择入度为 0 的结点从图中删去，此图中一开始只有 结点 3 的入度为 0；删掉 3 结点后，只有结点 1 的入度为 0；删掉结点 1 后，只有结点 4 的 入度为 0；删掉 4 结点后，结点 2 和结点 6 的入度都为 0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 314265 和 314625，选 D。

每次找入度为0的点依次剥离，如下图所示：

参考答案：D

答案解析：产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选 D。

用线性探测法为例，处理冲突（碰撞）时可能出现堆积（聚焦）现象，平均查找长度会变长。

A、B和C选项均与处理冲突无关。

本题选D。

方法一：性质 + 贪心

本题选D。

方法二：公式法

本题选D。

方法三：选项排序 + 贪心

本题选D。

参考答案：B

答案解析：首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第 1+2 个元素4明显比第1个元素9要大，A 排除；若增量为3，第 i、i+3、i+6 个元素都为有序序列(i=1,2,3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。

我们依次检查每个增量，每个增量序列必须单调递增。

A错误。间隔2的序列为：9, 4, ... ，非单调递增，错误。

B正确。间隔3的序列为：9, 13, 20、 1, 7, 23、4, 8, 15，全部单调递增。

C错误。间隔4的序列为：9, 7, ...，非单调递增。

D错误。间隔5的序列为：9, 8, ...，非单调递增。

本题选B。

参考答案：C

答案解析：快排的阶段性排序结果的特点是，第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在 2 个这样的数的选项。A 选项中 2、3、6、7、9 均符合，所以 A 排除；B选项中，2、9 均符合，所以 B 排除；D 选项中 5、9 均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。

其它方法

第一步：

检查快速排序，首先利用快速排序的性质，快速排序每一趟至少能够保证一个元素落在最终位置，即枢轴一定落在最终位置。这里进行了两趟快速排序，至少两个元素落在最终位置。

我们求出排好序后的序列为：2, 3, 4, 5, 6, 7, 9，然后依次和四个选项进行比对，看有没有不符合要求的。

A中有5个落位，待定。

B中有2个落位，待定。

C中有1个落位，错误。

D中有2个落位，待定。

由于这里C选项已经确定错误，无需进行第二步。

第二步是判断枢轴左边元素是否都小于枢轴，右边元素是否都大于枢轴。

第三步是画出序列对应的递归树，判断是否为快速排序的递归树。

本题过于简单，到第一步就结束了。

本题选C。