《数据结构》

简答题

一、设散列函数H(key)=key MOD 11,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，18，7，11，24 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

散列函数为 H(key)=key MOD 11，将关键字序列 {13，28，72，5，16，18，7，11，24} 插入到地址空间为 0-10 的散列区中。若发生冲突，使用线性探测再散列法解决冲突。具体步骤如下：

创建一个大小为 11 的散列表，初始化所有位置为空。

依次将关键字序列中的元素插入到散列表中。对于每个关键字 key，计算其散列地址 addr = key MOD 11。如果散列表中 addr 位置为空，则将 key 存入该位置；否则，使用线性探测再散列法找到下一个空位置存储 key。线性探测再散列的方法为：依次检查 addr+1，addr+2，…，直到找到一个空位置为止。如果搜索到散列表末尾，则从头开始搜索，直到找到一个空位置。

完成插入后，散列表中的元素为：

位置 0：11

位置 1：18

位置 2：28

位置 3：24

位置 4：5

位置 5：16

位置 6：7

位置 7：13

位置 8：72

位置 9：

位置 10：

其中，位置 9 和位置 10 为空。

对于查找关键字 key，先计算其散列地址 addr = key MOD 11，然后从位置 addr 开始依次查找，直到找到关键字 key 或者遇到空位置。如果找到关键字 key，则查找成功；否则，查找失败。

求等概率情况下查找成功时的平均查找长度。在本例中，关键字序列长度为 9，插入后的散列表中有 7 个位置被占用。根据定义，平均查找长度 ASL = (查找成功的总次数)/(关键字序列长度)。因为是等概率情况下，每个关键字的查找成功概率相同，所以查找成功的总次数可以表示为散列表中元素的数量。因此，ASL = 7/9 = 0.78。

因此，在地址空间为 0-10 的散列区中建散列表后，散列表为：

位置 0：11

位置 1：18

位置 2：28

位置 3：24

位置 4：5

位置 5：16

位置 6：7

位置 7：13

位置 8：72

位置 9：

位置 10：

等概率情况下查找成功时的平均查找长度为 0.78。

二、从空树开始，画出按以下次序向2_3树中插入关键字的建树过程：20，30，50，52，60，68，70。画出每一步执行后的树的状态。

以下是按照给定次序向 2-3 树中插入关键字的建树过程，并画出每一步执行后的树的状态。

首先是空树，如下所示：

()

插入关键字 20，得到一棵只包含一个 2-节点的树，如下所示：

(20)

插入关键字 30，得到一棵只包含一个 2-节点的树，如下所示：

(20,30)

插入关键字 50，得到一棵只包含一个 2-节点的树，如下所示：

(30)

/ \

(20) (50)

插入关键字 52，需要进行结点分裂，得到一棵只包含一个 2-节点和一个 3-节点的树，如下所示：

(30)

/ \

(20) (50,52)

插入关键字 60，得到一棵只包含一个 2-节点和一个 3-节点的树，如下所示：

(30,52)

/ | \

(20) (50) (60)

插入关键字 68，得到一棵只包含一个 2-节点和一个 3-节点的树，如下所示：

(30,52)

/ | \

(20) (50) (60,68)

插入关键字 70，需要进行结点分裂，得到一棵只包含一个 3-节点和一个 2-节点的树，如下所示：

(52)

/ \

(30) (68)

/ \ / \

(20) (50) (60) (70)

因此，按照给定次序向 2-3 树中插入关键字的建树过程，最终得到的树如上所示。

三、设关键字序列为{2，25，72，36，11，20，17，13，24，32}。h (key) = key mod 7,用链地址法处理冲突在地址空间为0-6的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

根据题目中给定的散列函数 h(key) = key mod 7，我们可以将关键字序列 {2，25，72，36，11，20，17，13，24，32} 映射到地址空间为 0-6 的散列区中，即：

h(2) = 2 mod 7 = 2

h(25) = 25 mod 7 = 4

h(72) = 72 mod 7 = 2

h(36) = 36 mod 7 = 1

h(11) = 11 mod 7 = 4

h(20) = 20 mod 7 = 6

h(17) = 17 mod 7 = 3

h(13) = 13 mod 7 = 6

h(24) = 24 mod 7 = 3

h(32) = 32 mod 7 = 4

我们可以看到，关键字 2 和 72、11 和 25、32 都发生了散列冲突，需要采用链地址法处理。因此，我们可以在每个地址空间中建立一个链表，将散列到同一地址空间中的关键字存储在同一个链表中。建立散列表的过程如下：

1: 36 -> NULL

2: 2 -> 72 -> NULL

3: 17 -> 24 -> NULL

4: 25 -> 11 -> 32 -> NULL

6: 20 -> 13 -> NULL

其中，箭头 "->" 表示链表中的指针。

等概率情况下查找成功时的平均查找长度可以使用公式 L = (1 + 1/2 + 1/3 + ... + 1/n) 来计算，其中 n 表示散列表中关键字的总数。在本题中，n=10，因此平均查找长度为：

L = (1 + 1/2 + 1/3 + ... + 1/10) ≈ 2.828

因此，等概率情况下查找成功时的平均查找长度为约 2.828。

四、已知如图所示的有向图，画出该图的: （1)邻接表 (2）写出从5出发的一个广度优先遍历序列。

1——》2

2——》3

3——》4

5——》2——》6

6——》4

562431

五、若线性表经常做插入/删除操作，则应采取什么存储结构（顺序或链式结构）？为什么？

若频繁地对线性表进行插入和删除操作,该线性表应该采用链式结构,因为若采用顺序存储结构,插入或删除一个数据元素,首先要移动其他元素的位置,使得操作的时间效率变得很低,而链式存储结构正好较好地克服了这些缺陷。

六、画出下图所示森林转化而成的二叉树，并写出该二叉树的先序遍历序列，这个序列对应了森林的什么遍历序列？

该二叉树的先序遍历序列

1 2 3 4 5 6 8 7 9 10 11 12 13 15 14

这个序列对应了森林的先序遍历序列

八、设s="I AM A WORKER"，t=" GOOD"，q=" WORKER"。求：StrLength(s)，StrLength(t) ，SubString(s,8,6) ，Index(s,q,1) 。

给定字符串 s="I AM A WORKER"，t=" GOOD"，q=" WORKER"，求：

StrLength(s)：求字符串 s 的长度。字符串 s 中共有 13 个字符，因此 StrLength(s)=13。

StrLength(t)：求字符串 t 的长度。字符串 t 中共有 5 个字符，因此 StrLength(t)=5。

SubString(s,8,6)：求从字符串 s 中第 8 个字符开始、长度为 6 的子串。字符串 s 中第 8 个字符是字母 W，因此 SubString(s,8,6)="WORKER"。

Index(s,q,1)：在字符串 s 中查找子串 q 第一次出现的位置。从字符串 s 中第一个字符开始查找，可以找到字符串 q 出现在 s 的第 8 个位置。因此 Index(s,q,1)=8。

因此，StrLength(s)=13，StrLength(t)=5，SubString(s,8,6)="WORKER"，Index(s,q,1)=8。

七、设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，试为这8个字母设计Huffman编码。

先将概率放大100倍,以方便构造哈夫曼树：w={7,19,2,6,32,3,21,10}

按哈夫曼规则:[(2,3),6], (7,10)], ……19, 21, 32

构造哈夫曼树如下:

九、设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，8，7，11 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

首先，根据散列函数 H(key)=key MOD 7，计算出关键字的散列地址如下：

13 -> 6

28 -> 0

72 -> 2

5 -> 5

16 -> 2

8 -> 1

7 -> 0

11 -> 4

由于冲突发生了，需要使用线性探测再散列法解决冲突。具体来说，就是当散列地址已经被占用时，就沿着散列表依次查找下一个空闲位置，直到找到为止。因此，按照上述方法建立的散列表如下：

0 28 7

1 8

2 72 16

4 11

5 5 13

其中，每一行的第一个数字为散列地址，后面的数字为关键字。可以看到，有些位置存储了多个关键字，这是由于发生了冲突。此时，查找关键字时，需要沿着散列表依次查找，直到找到目标关键字或者遇到空闲位置为止。

对于等概率情况下查找成功时的平均查找长度，根据公式ASL = (1+1/2+1/3+...+1/n)×α，其中 n 为散列表中关键字的总数，α 为填装因子。在本题中，散列表中关键字的总数为 8，填装因子为 8/11。因此，平均查找长度为：

ASL = (1+1/2+1/3+...+1/8)×(8/11) ≈ 1.74

十、证明：深度为k的二叉树至多有2k－1个结点(k≥1)。

证明：

用数学归纳法：当i=1时，2^（i-1）=1显然成立；现在假设第i-1层时命题成立，即第i-1层上最多有2^（i-2）个结点。由于二叉树的每个结点的度最多为2，故在第i层上的最大结点数为第i-1层的22倍，即2* 2^(i-2)=2^(i-1)。

在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为kk的二叉树的结点数至多为：

2^0+2^1+2^2+……+2^(k−1)=2^k−1

十一、假设有5项活动C1～C5，每项活动要求的前驱活动如下： C1：无； C2：C1，C3； C3：C1； C4：C3，C5 C5：C2；试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。

C1，C3，C2，C5，C4

十二、画出下图所示森林转化而成的二叉树，并写出该二叉树的中序遍历序列

先序1.2.5.6.3.4.7.9.8.10.11.13.12.14

中序5、6、2、3、9、7、8、4、1、13、11、12、10、14

13、将下列森林转化为相应的二叉树，并在其上标出先序前驱线索。

14、已知右示有向图，给出该图的：(1) 每个顶点的入度及出度；（2)邻接矩阵

解答:(1)、每个顶点的入/出度如下图:

顶点	1	2	3	4	5	6
入度	3	2	1	1	2	2
出度		2	2	3	1	3

(2)、邻接矩阵如下图:(行为出度→,列为入度↓)

(3)、邻接表如下图:(出边)

(4)、逆邻接表如下图:(入边)

15、已知某二叉树的先序序列为 { ABHFDECKG }，中序序列为 { HBDFAEKCG }, 画出该二叉树。

/ \

B E

/ \ \

H F C

/ / \

D K G

后序是 hdfbkgcea

16、假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集S={<c1,c2>,<c1,c3>,<c2,c5>,<c3,c2>,<c3,c4>,<c5,c4>},(1)试根据上述关系，画出该有向图；（2）写出该图从 c1出发的一个深度优先遍历序列。

17、使用冒泡排序或快速排序两种基于交换的内部排序方法对一组关键字序列进行排序，如果从节省时间的角度来考虑最好选择哪种排序方法？如果从节省存储空间的角度来考虑最好选择哪种排序方法？如果从排序稳定性的角度考虑最好选择哪种排序方法？分别回答并说明理由。

从节省时间的角度来考虑，最好选择快速排序，因为快速排序的时间复杂度是O(nlogn)，比冒泡排序的 O(n^2)更快，尤其是对于大规模的数据排序，快速排序的优势更加明显。

从节省存储空间的角度来考虑，最好选择冒泡排序，因为冒泡排序只需要一个额外的变量来进行交换，而快速排序需要使用递归调用栈来存储递归过程中的临时变量，这可能会占用大量的存储空间，尤其是在排序数据比较大的情况下。

从排序稳定性的角度考虑，最好选择冒泡排序，因为冒泡排序是稳定排序，即相同关键字的元素在排序后的相对位置不变，而快速排序是不稳定排序，即相同关键字的元素在排序后的相对位置可能会改变。如果排序过程中需要保持原序列中相同关键字元素的相对位置不变，那么就需要选择稳定排序算法，此时冒泡排序是更好的选择。

18、对下图所示的无向带权图，(1)写出它的数组表示法；（2)按Prim算法求其最小生成树，画出生成的全过程。

邻接矩阵：

	a	b	c	d	e	f	g	h
a	0	4	3	∞	∞	∞	∞	∞
b	4	0	5	5	9	∞	∞	∞
c	3	5	0	5	∞	∞	∞	5
d	∞	5	5	0	7	6	5	4
e	∞	9	∞	7	0	3	∞	∞
f	∞	∞	∞	6	3	0	2	∞
g	∞	∞	∞	5	∞	2	0	6
h	∞	∞	5	4	∞	∞	6	0

邻接表：

19、在单链表中设置头结点有什么作用？

头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就一样了。。

20、在地址空间为0-16的散列区中，对以下关键字序列(Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec)按线性探测开放定址法处理冲突构造散列表，设散列函数H(x)=i/2,其中i为关键字中第一个字母在字母表中的序号。画出该散列表并求在等概率情况下查找成功时的平均查找长度。

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

解决如下：

(1) 线性探测进入散列区的次序如下，X 代表冲突，要找下一个空格
Jan -> 5
Feb -> 3
Mar -> 6
Apr -> 0
May -> 6X -> 7
June -> 5X -> 6X -> 7X -> 8
July -> 5X -> 6X -> 7X -> 8X -> 9
Aug -> 0X -> 1
Sep -> 9X -> 10
Oct -> 7X -> 8X -> 9X -> 10X -> 11
Nov -> 7X -> 8X -> 9X -> 10X -> 11X -> 12
Dec -> 2

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Apr	Aug	Dec	Feb		Jan	Mar	May	Jun	July	Sep	OCt	Nov

很明显，查找成功时，查找Jan、Feb、Mar等仅需要一次，其余的也可以由上面看出来

所以查找成功时平均查找长度 (ASL) = (1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 2 + 5 + 6 + 1) / 12 = 31/12 = 2.58

21、设关键字集合为{10，2，14，8，12，6}，现对其从小到大排序，写出冒泡排序每一趟结束时的关键字状态。

初始序列：10，2，14，8，12，6

第一趟排序： 2，10，8，12，6，14

第二趟排序： 2，8，10，6，12，14

第三趟排序： 2，8，6，10，12，14

第四趟排序： 2，6，8，10，12，14

第五趟排序： 2，6，8，10，12，14

排序完成.

22、已知关键字序列{70，83，100，65，10，9，7，32}，现对其从小到大排序，写出直接插入排序每一趟结束时的关键字状态。

直接插入排序每一趟结束时的关键字状态:

第一趟:(70,83),100,65,10,9,7,32

第二趟:(70,83,100),65,10,9,7,32

第三趟:(65,70,83,100),10,9,7,32

第四趟:(10,65,70,83,100),9,7,32

第五趟:(9,10,65,70,83,100),7,32

第六趟:(7,9,10,65,70,83,100),32

第七趟:(7,9,10,32,65,70,83,100)