数据结构

既然要学索性学个彻底

题目：

1．若元素 $ a, b, c, d, e, f $ 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是：

A. $ d c e b f a $
B. $ c b d a e f $
C. $ b c a e f d $
D. $ a f e d c b $

答案：D

解释：

选项 A：可以通过操作序列 in, in, in, in, out, out, in, out, out, in, out, out 得到，符合条件。
选项 B：可以通过操作序列 in, in, in, out, out, in, out, out, in, out, in, out 得到，符合条件。
选项 C：可以通过操作序列 in, in, out, in, out, out, in, in, out, in, out, out 得到，符合条件。
选项 D：可以通过操作序列 in, out, in, in, in, in, in, out, out, out, out, out 得到，但题意要求不允许连续三次退栈操作，而选项 D 的操作序列中有五次连续的退栈操作，因此不符合条件，选项 D 错误。

题目：

2．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 $ a, b, c, d, e $ 依次入此队列后再进行出队操作，则不可能得到的出队序列是：

A. $ b a c d e $
B. $ d b a c e $
C. $ d b c a e $
D. $ e c b a d $

答案：C

解释：

此题考查的是双端队列的操作限制，其中 只能在一端进行出队操作。

选项 A：可以通过操作 左入，左入，右入，右入，右入 得到，符合条件。
选项 B：可以通过操作 左入，左入，右入，左入，右入 得到，符合条件。
选项 D：可以通过操作 左入，左入，左入，右入，左入 得到，符合条件。
选项 C：若采用 左入，左入，右入，右入 操作，无法形成选项 C 的出队序列，无法通过合法操作得到，因此选项 C 错误。

题目：

3．下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是：

答案：D

解释：

题目考查线索二叉树的基本概念和构造。线索二叉树是指用线索（虚线）来指向结点的前驱或后继结点。
本题特别关注的是后序线索二叉树。后序遍历的顺序是访问左子树、右子树，最后访问根节点。
根据给出的二叉树的后序遍历顺序 $d \to b \to c \to a$：
- 结点 $d$ 没有前驱和左子树，因此左链域为空，且没有右子树，右链域应指向它的后继结点 $b$；
- 结点 $b$ 没有左子树，左链域应指向它的前驱结点 $d$；
- 结点 $c$ 没有左子树，左链域应指向它的前驱结点 $b$，且没有右子树，右链域应指向它的后继结点 $a$。

选项 D 符合后序线索树的定义。

题目：

4．在图 B-1 所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是：

A. 13，48
B. 24，48
C. 24，53
D. 24，90

答案：C

解释：

插入关键字 48 后，平衡二叉树的根节点平衡因子由 -1 变为 -2，失去了平衡，需要进行调整。
在平衡二叉树中，调整的方法是通过旋转来恢复平衡。
插入 48 之后需要进行两次旋转操作，即先进行右旋（右子树比左子树高）操作，后进行左旋（左子树比右子树高）操作。
根据平衡调整，最终新平衡二叉树中，关键字 37 所在结点的左子结点保存的是关键字 24，右子结点保存的是关键字 53。

题目：

5．在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是：

A．41
B．82
C．113
D．122

答案：B

解释：

设树中度为 $i$（$i=0, 1, 2, 3, 4$）的结点数分别为 $N_i$，树中结点总数为 $N$。
根据树的性质，树中各结点的度之和等于 $N - 1$，即： $ _{i=0}^{4} i N_i = N - 1 $
根据题目数据，设 $N_4 = 20$，$N_3 = 10$，$N_2 = 1$，$N_1 = 10$，我们需要计算 $N_0$（叶结点个数）。
总结点数 $N$ 为： $ N = N_4 + N_3 + N_2 + N_1 + N_0 $
结点度之和为： $ 4 + 3 + 2 + 1 + 0 N_0 = N - 1 $ $ 80 + 30 + 2 + 10 = N - 1 = N - 1 N = 123 $
代入求叶结点： $ N_0 = N - (N_4 + N_3 + N_2 + N_1) = 123 - (20 + 10 + 1 + 10) = 123 - 41 = 82 $
所以树 $T$ 的叶结点个数是 82。

题目：

6．对 $n$ （$n \geq 2$）个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是：

A．该树一定是一棵完全二叉树
B．树中一定没有度为1的结点
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

答案：A

解释：

赫夫曼树是一种带权路径长度最小的二叉树，但它不一定是完全二叉树。
选项 B 正确，因为在赫夫曼树中，不会有度为 1 的结点，所有非叶结点都有两个子结点。
选项 C 正确，因为构造赫夫曼树时，最先选取两个权值最小的结点作为左、右子树构造新的二叉树，因此它们必然是兄弟结点。
选项 D 也正确，因为赫夫曼树中任何非叶结点的权值等于其左、右子树根结点权值之和，故它的权值一定不小于其子树根结点的权值。

综上，错误的叙述是 A。

题目：

7．若无向图 $ G=(V, E) $ 中含有 7 个顶点，要保证图 $ G $ 在任何情况下都是连通的，则需要的边数最少是：

A．6
B．15
C．16
D．21

答案：C

解释：

要保证无向图 $ G $ 在任何情况下都是连通的，首先需要考虑图的最小生成树（MST）。
对于一个有 $ n $ 个顶点的连通图，最小边数为 $ n-1 $。
在本题中， $ n = 7 $，因此至少需要 $ 7 - 1 = 6 $ 条边以确保图是连通的。
然而，这样的图可能无法在任何情况下保持连通。如果在边的添加或删除中存在某些边的情况下，图仍然可能会变得不连通。
为了确保图在任何情况下都是连通的，我们需要考虑更多的边。具体来说，首先需要构造一个包含 6 个结点的完全子图 $ G_1 $，这需要 15 条边。然后再添加一条边，将第 7 个结点与 $ G_1 $ 连接起来，共需 $ 15 + 1 = 16 $ 条边。

题目：

8．对图B-2进行拓扑排序，可以得到不同的拓扑序列的个数是：

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

答案：B

解释：

拓扑排序是对有向无环图（DAG）的一种线性排序方法，排序的结果使得对于每一条边 $ u v $，顶点 $ u $ 在排序中出现在顶点 $ v $ 之前。
在图B-2中，我们需要检查该图的结构，确定所有可能的拓扑排序序列。
经过分析，图B-2的拓扑排序的不同序列分别为：
- $ abced $
- $ abecd $
- $ aebcd $
因此，图B-2中有 3 个不同的拓扑排序序列。

题目：

9．已知一个长度为16的顺序表 $ L $，其元素按关键字有序排列。若采用折半查找法查找一个 $ L $ 中不存在的元素，则关键字的比较次数最多的是：

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

答案：B

解释：

折半查找（又称二分查找）的时间复杂度是 $ O(_2 n) $。
具有 $ n $ 个结点的二叉判定树的高度为 $ _2 n + 1 $。
对于长度为 16 的顺序表，计算 $ _2 16 = 4 $，所以查找一个不存在的元素时最多需要进行 $ 5 $ 次比较。

题目：

10．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是：

A．递归次数与初始数据的排列次序无关
B．每次划分后，先处理较长的分区可以减少递归次数
C．每次划分后，先处理较短的分区可以减少递归次数
D．递归次数与每次划分后得到的分区的处理顺序无关

答案：D

解释：

快速排序的递归次数与数据的初始排列情况有较大关系。如果每次划分后的两个子序列长度比较均衡，递归次数较少；如果划分后的分区非常不均衡，递归次数较多。
但无论先处理哪个分区，最终的递归次数是固定的，与处理顺序无关。因此，选项 D 是正确的。

题目：

11．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下：

第一趟排序结果：2，12，16，5，10，88
第二趟排序结果：2，12，5，10，16，88
第三趟排序结果：2，5，10，12，16，88

则采用的排序方法可能是：

A．冒泡排序
B．希尔排序
C．归并排序
D．基数排序

答案：A

解释：

通过观察每一趟的排序过程，冒泡排序的特点是每一趟都将最大的元素移动到最终位置。
第一趟中，88 被移动到了最后。第二趟中，16 被移到了正确位置。
这与冒泡排序的逐趟交换特征一致。
希尔排序、归并排序和基数排序的过程则与给出的结果不相符，因此可以排除。

题目：

41．（10 分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为 $ H(key) = (key ) $，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

（1）请画出所构造的散列表。

（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。

解答：

（1）构造散列表：

根据装载因子为0.7，数据总数为7，散列表的大小为：

$ = $

数组下标范围为0到9。

计算每个关键字的散列值：

key	H(key) = (key × 3) MOD 7
7	$ (7 ) = 0 $
8	$ (8 ) = 3 $
30	$ (30 ) = 6 $
11	$ (11 ) = 5 $
18	$ (18 ) = 5 $
9	$ (9 ) = 6 $
14	$ (14 ) = 0 $

初步散列值表：

0: 7
1: 空
2: 空
3: 8
4: 空
5: 11 (已被占用，再探测，放入18)
6: 30 (已被占用，再探测，放入9)
7: 空
8: 空
9: 空

线性探测处理冲突后得到的散列表：

地址	关键字
0	7
1	14
2	空
3	8
4	空
5	11
6	30
7	空
8	18
9	9

最终的散列表为：

地址	关键字
0	7
1	14
2	空
3	8
4	空
5	11
6	30
7	空
8	18
9	9

（2）计算平均查找长度（ASL）：

查找成功时的查找次数：

key	查找次数
7	1
8	1
30	1
11	1
18	3
9	3
14	2

成功查找的平均查找长度：

$ = = $

查找不成功时的查找次数：

对于查找失败的位置（0-6），我们计算各位置的查找失败次数：

H(key)	次数
0	3
1	2
2	1
3	2
4	1
5	5
6	4

查找不成功的平均查找长度：

$ = = $

最终结果：

散列表： 如上所示
查找成功的平均查找长度（ASL成功）： $ $
查找不成功的平均查找长度（ASL不成功）： $ $

题目：

42．（13 分）设将n（$n>1$）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（$0<p<n$）个位置，即将R中的数据由$(X_0, X_1, \ldots, X_{n-1})$变换为$(X_p, X_{p+1}, \ldots, X_{n-1}, X_0, X_1, \ldots, X_{p-1})$。

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

（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

解答：

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

这个问题可以看作是将数组分为两部分：前p个元素和后n-p个元素。我们可以利用数组的逆置操作来实现左移：

逆置前p个元素：将前p个元素逆置。
逆置后n-p个元素：将后n-p个元素逆置。
逆置整个数组：将整个数组逆置。

最终，我们就可以得到左移p个位置后的数组。

举例说明： 假设有数组 $[a, b, c, d, e, f, g, h]$，要左移3个位置（p=3）：

逆置前3个元素： $[c, b, a, d, e, f, g, h]$
逆置后4个元素： $[c, b, a, h, g, f, e, d]$
逆置整个数组： $[d, e, f, g, h, a, b, c]$

（2）采用C语言描述算法：

#include <stdio.h>

// 逆置数组中指定范围的元素
void Reverse(int R[], int from, int to) {
    int i, temp;
    // 交换from到to之间的元素
    for (i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

// 循环左移p个位置
void Converse(int R[], int n, int p) {
    // 逆置前p个元素
    Reverse(R, 0, p - 1);
    // 逆置后n-p个元素
    Reverse(R, p, n - 1);
    // 逆置整个数组
    Reverse(R, 0, n - 1);
}

// 测试代码
int main() {
    int R[] = {1, 2, 3, 4, 5, 6, 7, 8}; // 示例数组
    int n = sizeof(R) / sizeof(R[0]);
    int p = 3; // 左移位置

    Converse(R, n, p); // 调用左移函数

    // 打印结果
    for (int i = 0; i < n; i++) {
        printf("%d ", R[i]);
    }
    return 0;
}

（3）时间复杂度和空间复杂度分析：

时间复杂度：
- 每个逆置操作的时间复杂度是 $O(k)$，其中 $k$ 是逆置的元素个数。由于总共有3个逆置操作，最坏情况下每个操作最多涉及 $n$ 个元素。因此，整体时间复杂度为：
$ O(n) $
空间复杂度：
- 该算法只使用了常数级别的额外空间来存储临时变量（如 temp），不需要额外的数组。因此，空间复杂度为：
$ O(1) $

另一种解法（使用辅助数组）：

如果选择使用辅助数组来实现，算法思想如下：

创建一个大小为p的辅助数组S，存储R中前p个整数。
将R中后n-p个整数左移到前面。
将S中存储的p个整数依次放回R中的后续单元。

时间复杂度和空间复杂度：

时间复杂度依然是 $O(n)$。
空间复杂度为 $O(p)$，因为使用了大小为p的辅助数组。

这种方法虽然简单直观，但在空间上不如第一种方法高效。

数据结构

题目：

1．若元素 $ a, b, c, d, e, f $ 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是：

答案：D

题目：

2．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 $ a, b, c, d, e $ 依次入此队列后再进行出队操作，则不可能得到的出队序列是：

答案：C

题目：

3．下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是：

答案：D

题目：

4．在图 B-1 所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是：

答案：C

题目：

5．在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是：

答案：B

题目：

6．对 \(n\) （\(n \geq 2\)）个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是：

答案：A

题目：

7．若无向图 $ G=(V, E) $ 中含有 7 个顶点，要保证图 $ G $ 在任何情况下都是连通的，则需要的边数最少是：

答案：C

题目：

8．对图B-2进行拓扑排序，可以得到不同的拓扑序列的个数是：

答案：B

题目：

9．已知一个长度为16的顺序表 $ L $，其元素按关键字有序排列。若采用折半查找法查找一个 $ L $ 中不存在的元素，则关键字的比较次数最多的是：

答案：B

题目：

10．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是：

答案：D

题目：

11．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下：

答案：A

题目：

（1）请画出所构造的散列表。

（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。

解答：

（1）构造散列表：

（2）计算平均查找长度（ASL）：

最终结果：

题目：

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

（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

解答：

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

（2）采用C语言描述算法：

（3）时间复杂度和空间复杂度分析：

另一种解法（使用辅助数组）：