数据结构

既然要学索性学个彻底

问题 1

设 $ n $ 是描述问题规模的非负整数，下面程序片段的时间复杂度是什么？

1
2
3

x = 2;
while (x < n / 2)
    x = 2 * x;

A．$ O(_2 n) $
B．$ O(n) $
C．$ O(n _2 n) $
D．$ O(n^2) $

答案：A

解析：

在程序中，执行频率最高的语句是 x = 2 * x。设该语句执行了 $ t $ 次，则在每次执行后 $ x $ 的值依次为 $ 2, 4, 8, 16, $，即 $ x $ 按照指数增长。当 $ x $ 达到 $ n / 2 $ 时，循环终止。

我们可以设： $ x = 2^t $ 当 $ x $ 达到 $ n / 2 $ 时，有： $ 2^t = n / 2 t = _2(n/2) $ 忽略常数项，我们得到 $ t = O(_2 n) $，因此时间复杂度为 $ O(_2 n) $。

问题 2

元素 $ a $、$ b $、$ c $、$ d $、$ e $ 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 $ d $ 开头的序列个数是多少？

A．3
B．4
C．5
D．6

答案：B

解析：

在出栈序列中，元素的顺序必须满足“后进先出”的性质。因此，序列必须以 $ d $ 开头，接着才是 $ c $、$ b $、$ a $ 出栈，而 $ e $ 可以在任何一个间隔位置出栈，形成不同的序列。

元素 $ c $、$ b $、$ a $ 必须在 $ d $ 出栈后按照逆序出栈。而元素 $ e $ 可以放在 $ d $ 后的任意一个位置，具体位置为 4 个可能性。

因此，以 $ d $ 开头的出栈序列个数是 4。

问题 3

已知循环队列存储在一维数组 $ A[0 n-1] $ 中，且队列非空时 $ front $ 和 $ rear $ 分别指向队头元素和队尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在 $ A[0] $ 处，则初始时 $ front $ 和 $ rear $ 的值分别是多少？

A．0，0
B．0，$ n-1 $
C．$ n-1 $，0
D．$ n-1 $，$ n-1 $

答案：B

解析：

对于循环队列，初始时队列为空，通常会将 $ front $ 和 $ rear $ 指针设置为特殊状态表示队列为空。根据题意，第一个进入队列的元素要存储在 $ A[0] $ 处。

由于入队操作会改变 $ rear $ 指针，而 $ rear $ 要指向最后一个元素 $ A[0] $，因此，初始时 $ rear = n - 1 $。而队列的第一个元素在 $ A[0] $ 中，因此 $ front = 0 $ 不变。

故答案是 $ front = 0 $，$ rear = n - 1 $。

问题 4

若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是多少？

A．257
B．258
C．384
D．385

答案：C

解析：

完全二叉树的性质决定了非叶结点的个数与叶结点的个数之间的关系。设这棵树有 $ n = 768 $ 个结点，非叶结点（分支结点）的个数为 $ n/2 $。因此，分支结点的数量为：

$ / 2 = 384 $

叶结点的个数则为总结点数减去分支结点数：

$ 768 - 384 = 384 $

因此，叶结点的个数是 384。

问题 5

若一棵二叉树的前序遍历序列和后序遍历序列分别为 1, 2, 3, 4 和 4, 3, 2, 1，则该二叉树的中序遍历序列不可能是什么？

A．1，2，3，4
B．2，3，4，1
C．3，2，4，1
D．4，3，2，1

答案：C

解析：

根据前序遍历序列 $ 1, 2, 3, 4 $（表示根左右）和后序遍历序列 $ 4, 3, 2, 1 $（表示左右根），可以推测这棵二叉树的结构是只有左孩子，没有右孩子的情况。因为前序遍历和后序遍历是相反的，这表明每个结点的左右子树都是单链结构。

在这种情况下，根结点只能有左孩子，因此中序遍历的序列中根结点 $ 1 $ 必须在序列的首位或末位。同样地，子树中的根结点 $ 2 $ 也只能在其子序列的首位或末位。选项 A、B、D 都符合这一要求，但选项 C 中 $ 3 $ 不在最左边或最右边，因此中序遍历不可能是 $ 3, 2, 4, 1 $。

问题 6

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是多少？

A．115
B．116
C．1895
D．1896

答案：D

解析：

将树转换为二叉树时，每个分支结点中的子结点按照“左孩子-右兄弟”的规则转换。树中的每一个分支结点都会有一个最右的子结点，在转换为二叉树后，这个最右子结点将没有右孩子。

因此，二叉树中无右孩子的结点个数等于分支结点数加上根结点。分支结点的个数为总结点数减去叶结点数：

$ 2011 - 116 = 1895 $

再加上根结点，得：

$ 1895 + 1 = 1896 $

因此，无右孩子的结点个数为 1896。

问题 4

若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是多少？

A．257
B．258
C．384
D．385

答案：C

解析：

$ / 2 = 384 $

叶结点的个数则为总结点数减去分支结点数：

$ 768 - 384 = 384 $

因此，叶结点的个数是 384。

问题 5

若一棵二叉树的前序遍历序列和后序遍历序列分别为 1, 2, 3, 4 和 4, 3, 2, 1，则该二叉树的中序遍历序列不可能是什么？

A．1，2，3，4
B．2，3，4，1
C．3，2，4，1
D．4，3，2，1

答案：C

解析：

问题 6

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是多少？

A．115
B．116
C．1895
D．1896

答案：D

解析：

因此，二叉树中无右孩子的结点个数等于分支结点数加上根结点。分支结点的个数为总结点数减去叶结点数：

$ 2011 - 116 = 1895 $

再加上根结点，得：

$ 1895 + 1 = 1896 $

因此，无右孩子的结点个数为 1896。

问题 7

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是？

A．95，22，91，24，94，71
B．92，20，91，34，88，35
C．21，89，77，29，36，38
D．12，25，71，68，33，34

答案：A

解析：

在二叉排序树中，左子树的结点值比根结点小，右子树的结点值比根结点大。对于选项 A，当从根结点 $ 95 $ 查找到 $ 91 $ 后，查找 $ 24 $ 时，路径进入左子树，但是此后路径中的 $ 94 $ 比 $ 91 $ 大，且不符合二叉排序树的性质。因此，A 选项中的序列不可能构成一条有效的查找路径。

问题 8

下列关于图的叙述中，正确的是？

Ⅰ．回路是简单路径
Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

A．仅Ⅱ
B．仅Ⅰ、Ⅱ
C．仅Ⅲ
D．仅Ⅰ、Ⅲ

答案：C

解析：

Ⅰ 错误：回路是路径，但不一定是简单路径。简单路径定义为路径中没有重复的顶点，而回路中至少有一个顶点是重复的。
Ⅱ 错误：稀疏图中，边数远少于顶点数，此时用邻接表存储比用邻接矩阵节省空间，因为邻接矩阵需要存储 $ n^2 $ 个元素（n 为顶点数），而邻接表只存储实际存在的边。
Ⅲ 正确：如果有向图存在拓扑序列，则说明该图是无环图。如果存在回路，则无法进行拓扑排序。

问题 9

为提高散列（Hash）表的查找效率，可以采取的正确措施是？

Ⅰ．增大装填（载）因子
Ⅱ．设计冲突（碰撞）少的散列函数
Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象

A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅱ
D．仅Ⅱ、Ⅲ

答案：D

解析：

Ⅰ 错误：装填因子越大，散列表中存放的元素越多，冲突的概率也会越高，查找效率下降。因此，增大装填因子会降低查找效率。
Ⅱ 正确：设计冲突少的哈希函数可以减少查找中的冲突次数，提高查找效率。
Ⅲ 正确：处理冲突时，避免聚集现象（如线性探测法中的堆积）可以提高查找效率。

问题 10

为实现快速排序算法，待排序序列宜采用的存储方式是？

A．顺序存储
B．散列存储
C．链式存储
D．索引存储

答案：A

解析：

快速排序是一种基于比较的排序算法，适合使用顺序存储结构。快速排序在排序过程中，既需要从后向前查找，也需要从前向后查找元素，因此顺序存储可以更方便地通过下标来访问元素。而链式存储在进行这种随机访问时效率较低，不适合快速排序的需求。

问题 11

已知序列 $25, 13, 10, 12, 9$ 是大根堆，在序列尾部插入新元素 $18$，将其再调整为大根堆，调整过程中元素之间进行的比较次数是？

A．1
B．2
C．4
D．5

答案：B

解析：

插入新元素 $18$ 后，序列为 $25, 13, 10, 12, 9, 18$。在大根堆中，子结点不能比父结点大，因此需要将新元素与父结点进行比较：

首先，$18$ 与其父结点 $10$ 比较，由于 $18 > 10$，交换两者位置。
之后，$18$ 与新的父结点 $25$ 比较，由于 $18 < 25$，不交换位置。

因此，总共比较了 2 次。

调整过程如下：

插入 $18$：$ 25, 13, 10, 12, 9, 18 $
第一次比较与交换：$ 25, 13, 18, 12, 9, 10 $
第二次比较，无交换：调整完成。

问题 41

已知有 6 个顶点（顶点编号为 0～5）的有向带权图 $ G $，其邻接矩阵 $ A $ 为上三角矩阵，按行优先顺序保存在如下的一维数组中：

$ 4, 6, , , , 5, , , , 4, 3, , , 3, 3 $

要求：

写出图 $ G $ 的邻接矩阵 $ A $。
画出有向带权图 $ G $。
求图 $ G $ 的关键路径，并计算该关键路径的长度。

正确解答：

（1）邻接矩阵 $ A $

邻接矩阵 $ A $ 如下：

$ A = \[\begin{pmatrix} 0 & 4 & 6 & \infty & \infty & \infty \\ \infty & 0 & 5 & \infty & \infty & \infty \\ \infty & \infty & 0 & 4 & 3 & \infty \\ \infty & \infty & \infty & 0 & \infty & 3 \\ \infty & \infty & \infty & \infty & 0 & 3 \\ \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix}\]

注意，这里是顶点 3 指向顶点 5，而不是顶点 4 指向顶点 5。

（2）有向带权图 $ G $

根据邻接矩阵 $ A $，修正后的有向带权图如下：

顶点 $ 0 $ 指向顶点 $ 1 $ 和 $ 2 $，权重分别为 $ 4 $ 和 $ 6 $。
顶点 $ 1 $ 指向顶点 $ 2 $，权重为 $ 5 $。
顶点 $ 2 $ 指向顶点 $ 3 $ 和 $ 4 $，权重分别为 $ 4 $ 和 $ 3 $。
顶点 $ 3 $ 指向顶点 $ 5 $，权重为 $ 3 $。
顶点 $ 4 $ 指向顶点 $ 5 $，权重为 $ 3 $。

修正后的有向图中，顶点 $ 3 $ 和 $ 4 $ 都指向顶点 $ 5 $。

（3）关键路径和长度

我们还是需要寻找从起点（顶点 0）到终点（顶点 5）的最长路径。

从 $ 0 $ 开始，选择到达顶点 $ 1 $，权重为 $ 4 $。
接着从 $ 1 $ 到达顶点 $ 2 $，权重为 $ 5 $。
从顶点 $ 2 $ 到达顶点 $ 3 $，权重为 $ 4 $。
最后，从顶点 $ 3 $ 到终点 $ 5 $，权重为 $ 3 $。

因此，关键路径为：

$ 0 $

该关键路径的长度为：

$ 4 + 5 + 4 + 3 = 16 $

总结：

邻接矩阵 $ A $ 。
根据邻接矩阵，绘制了正确的有向带权图 $ G $，修正了指向错误。
关键路径为 $ 0 $，关键路径长度为 16。

问题42

有两个长度为 $ L $ （ $ L $ ）的升序序列 $ A $ 和 $ B $，分别称两个序列中位于第 $ L/2 $ 位置的数为序列的中位数。例如，若序列 $ S_1 = (11, 13, 15, 17, 19) $，则 $ S_1 $ 的中位数是 15；若序列 $ S_2 = (2, 4, 6, 8, 20) $，则 $ S_1 $ 和 $ S_2 $ 的所有元素组合后构成的升序序列的中位数为 11。

现在，给定两个等长的升序序列 $ A $ 和 $ B $，设计一个时间复杂度和空间复杂度尽可能高效的算法，找出这两个序列的中位数。

要求：

给出算法的基本设计思想。
采用 C 或 C++ 或 Java 语言描述算法，并在关键之处加上注释。
说明所设计算法的时间复杂度和空间复杂度。

正确解答

（1）算法的基本设计思想

为了高效找出两个等长升序序列 $ A $ 和 $ B $ 的中位数，设计如下步骤：

求出中位数：分别计算序列 $ A $ 和 $ B $ 的中位数，设它们分别为 $ a $ 和 $ b $。
比较中位数：
- 若 $ a = b $，则 $ a $ 或 $ b $ 就是所求的中位数，算法结束。
- 若 $ a < b $，说明真正的中位数必然位于序列 $ A $ 的较大部分和序列 $ B $ 的较小部分。于是我们舍弃 $ A $ 的较小部分和 $ B $ 的较大部分，继续在剩下的部分递归查找。
- 若 $ a > b $，同理，舍弃 $ A $ 的较大部分和 $ B $ 的较小部分，继续在剩余的部分递归查找。
递归处理：在保留下来的两个序列中，重复上述过程，直到两个序列中只剩下一个元素，较小者即为所求中位数。

（2）算法实现

下面是该算法的 C 语言实现，包含注释：

int M_Search(int A[], int B[], int n) {
    int s1 = 0, d1 = n - 1, m1;  // A 序列的首位、末位和中位索引
    int s2 = 0, d2 = n - 1, m2;  // B 序列的首位、末位和中位索引

    // 当两个序列均有多个元素时，继续查找
    while (s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;  // 计算 A 的中位数索引
        m2 = (s2 + d2) / 2;  // 计算 B 的中位数索引

        if (A[m1] == B[m2]) {
            return A[m1];  // 若两个中位数相等，直接返回
        }

        if (A[m1] < B[m2]) {
            // 若 A 的中位数小于 B 的中位数
            if ((s1 + d1) % 2 == 0) {
                s1 = m1;  // 舍弃 A 中较小的部分
                d2 = m2;  // 舍弃 B 中较大的部分
            } else {
                s1 = m1 + 1;  // 舍弃 A 中较小部分（包含中位数）
                d2 = m2;  // 舍弃 B 中较大的部分
            }
        } else {
            // 若 A 的中位数大于 B 的中位数
            if ((s1 + d1) % 2 == 0) {
                d1 = m1;  // 舍弃 A 中较大的部分
                s2 = m2;  // 舍弃 B 中较小的部分
            } else {
                d1 = m1 + 1;  // 舍弃 A 中较大部分（包含中位数）
                s2 = m2;  // 舍弃 B 中较小的部分
            }
        }
    }

    // 返回两个序列中较小的元素作为中位数
    return A[s1] < B[s2] ? A[s1] : B[s2];
}