数据结构与算法题库

数据结构与算法题库

五、综合题

1．已知一棵二叉树的先序遍历序列为ABEcDFGHIJ，中序遍历序列为EBcDAFHIGJ。 (1) 画出这棵二叉树;

(2) 写出该二叉树的后序遍历序列;

(3) 画出这棵二叉树的中序线索二叉树的存储结构图。

2. 已知一棵二叉树的中根遍历序列为：2，4，1，5，3，7，6，8，后根遍历序列为：4，2，5，7，8，6，3，1。 (1)画出二叉树。

(2) 写出二叉树先根遍历序列。

(3) 画出该二叉树的先序线索二叉树。

3. 假设一颗二叉树的中序遍历序列为DcBGEAHFIJK和后序遍历序列为DcEGBFHKJIA.。 1） 请画出该二叉树。

2） 请画出该二叉树的后序序线索二叉树。 3） 写出该二叉树的先序遍历序列。

4. 已知一棵二叉树的先序遍历序列为ABcDEFGHIJK，中序遍历序列为cDBGFEAHJIK。 （1）请构造二叉树；

（2）画出先序线索二叉树。

（3）分别列出度为0、1和2的结点。

5.已知某通讯电文仅由a，b，c，d，e，f，g，h八个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。为这8中字母设计哈夫曼编码。

6. 假设用于通信的电文仅由5种字母ABcDE组成，每个字母出现的概率分别为0.12, 0.40, 0.15, 0.08, 0.25。

(1) 用5个概率值为权值设计Huffman(哈夫曼)树。 (2) 计算它的带权路径长度WPL。 (3) 设计这5种字符的Huffman编码

7.按下面要求转换森林和二叉树。 （1）将图-1的二叉树转换成森林。 （2）将图-2的树转换成二叉树。

A c B E D F I H J 图-1

A K J Bc D E F G H I J K 图-2 8. 画出下列二叉树相应的森林，并写出中序遍历森林的序列。

9. 已知一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，最小生成树为权值之和最小的生成树。

A 6 B 1 5 c 3 6 E 6 4 F 2 5 5 D 10. 已知一个无向图G=(V,E),V={A,B,c,D,E,F,G,H}, E = {(A,B),(A,c),(B,D),(B,E),(c,F),(c,G),(D,H),(E,H),(F,G)}; (1)画出该无向图； (2)画出该图的邻接表存储结构； (3)根据存储结构，写出深度优先搜索遍历序列和广度优先搜索遍历序列。

11. 已知一个无向图G=(V,E),V={v1,v2,v3,v4,v5,v6,v7,v8}, E = {(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7),(v4,v8),(v5,v8),(v6,v7)}; (1)画出该无向图； (2)画出该图的邻接表存储结构； (3)根据存储结构，写出深度优先搜索遍历序列和广度优先搜索遍历序列。

12.已知一个有向图如下图所示： (1)画出该图的邻接表存储结构。 (2)画出该图的逆邻接表存储结构。 (3) 写出拓扑排序序列。 (4) 写出深度优先搜索遍历序列和广度优先搜索遍历序列。 A B c D E F

13.画出如下图所示的邻接表的表示，并以顶点V1为初始源点遍历所示的有向图所得到的深度优先遍历和广度优先遍历生成森林。

14. 已知一个连通网如下图所示，试用Prime（普里姆）算法计算下图的最小生成树，起始点为A。 16 B A 5 21 19 14 9 F c

26 11 6 D E

18

15 一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，起始点为A。

16. 请利用Prime（普里姆）算法计算下图的最小生成树。 A 5 6

B 1 5 c 3 6 E 6 4 F 2 5 D

17.已知一个AoE网如下图所示： (1) 写出下图的拓扑排序顺序序列；

(2) 试计算出该图从源点A出发到达汇点F的关键路径。

a5=3 B E

a3=2 a8=1 a1=3

a7=2 D A F

a4=4

a2=2 a6=3

c

18.已知一个AoE网如下图所示： (1) 找出AoE网源点和汇点； (2) 试计算出该图的关键路径。 V7 a4=1 a7=9 V5 a10=2 V9 a8=7 V8 a11=4 V2 a1=6 V1 a2=4 V3 a3=5 V4

a5=1 a9=4 a6=2 V6 19.已知一个AoE网如下图所示，其中V1为源点，V6为汇点。 (1) 写出拓扑排序序列； (2) 计算出从源点到汇点的关键路径。 a4=10

V3 V4 a7=6 a2=2 a6=19 V1 a3=4

a1=15 a8=5 V5 V2 a5=11

V6

20.利用Dijkstra算法计算下图中从顶点A到其余各顶点的最短路径。

4B 15 2 A 12 5 D F 3 c 4 10 6 8 E 9 G 已知一个AoE网如下图所示，试计算出该图的关键路径。 21. 用迪杰斯特拉算法求下图中从a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。 10 20 b 30 a 60 c 40 65 15 f 20 80 d e 35

22. 用迪杰斯特拉算法求下图中从A到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。

23. 已知一组关键字序列12, 23, 45, 57, 20, 3, 78, 31, 15, 36，哈希函数为H(Key) = Key % 13 (1) 利用开放定址法的线性探测再散列解决冲突，构造长度为15的哈希表，计算平均查找长度ASL； (2) 利用链地址法解决冲突，构造长度为10的哈希表，计算平均查找长度ASL；

24．设哈希表长度为10，哈希函数为H(Key) = Key Mod 7，关键字集合为{15，10，12，20，25，35，31，18}。 （1）利用开放定址法的线性探测再散列解决冲突，构造哈希表，计算平均查找长度ASL。 （2）利用链地址法解决冲突构造哈希表，计算平均查找长度ASL。

25.已知一组数据的关键字为（22，41，53，46，30，13，1，67），哈希函数为 H(Key) = (3 Key) % 11，哈希表长度为11。 1）用开放定址法的线性探测在散列解决冲突，构造哈希表，计算平均查找长度ASL。 2）利用链地址法解决冲突构造哈希表，计算平均查找长度ASL。

26. 已知一棵平衡排序二叉树如下图所示：

45

56 72 16 26 78 40 66 90 （1）在上图中若插入结点60后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。

（2）在上图中若插入结点70后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。

27. 已知一棵平衡排序二叉树如下图所示

45

78 26

16 40 66 90 56 72 （1）在上图中若插入结点60后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。 （2）在上图中若插入结点70后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。

28. 已知一个空的二叉排序树，按照下面的要求画出新的二叉排序树。 （1）设查找序列关键字为{70，30，100，25，85，63，96，125，47，117}，画出生成的二叉排序树T。 （2）画出T删除关键字为47结点后的二叉排序树。 （3）画出T删除关键字为85结点后的二叉排序树。 （4）画出T删除关键字为100结点后的二叉排序树。

29. 已知一个待排序序列为{12, 2, 16, 30, 14, 8}，请按照下面的排序方法写出每一趟排序的序列。 (1)直接插入排序 (2)气泡排序 30. 已知一个待排序序列为（49，38，65，97，76，13，27，50）。 ，请按照下面的排序方法写出每一趟排序的序列。 (1)简单选择排序 (2)气泡排序

31.已知一个序列： （49，38，65，97，76，13，27，50）。

(1) 请写出以49位轴的一趟快速排序后的序列。 (2) 请写归并排序的每一趟过程序列。

32. 已知一个序列：

（05，56，20，23，40，38，29，61，35，76，28，100）。 （1）将这个序列调整成小顶堆；

（2）用堆排序方法计算出前三个最小的元素（要求画出已经调整成堆的二叉树的最后状态

图）。

33. 已知一个序列：

（49，38，65，97，76，13，27，50）。 （1）将这个序列调整成小顶堆；

（2）用堆排序方法计算出前三个最小的元素（要求画出已经调整成堆的二叉树的最后状态图）。

34. 已知关键字序列为{326，259，369，924，726，479，568，25，8}。 （1）将其调整成堆。

（2）画出前2趟推排序状态图。（画出已经调整成堆的二叉树的最后状态图）。