数据结构 – 期末作业

发布于 2020-06-08  8 次阅读 本文共1916个字


1. 画出向小根堆中加入数据5, 1, 6, 9, 2时,每加入一个数据后堆的变化。

参考教程

2. 已知待 为(36,15,40,63,22),散列用的一维地址空间为[0…6],假定选用的散列函数是H(K)=K mod 7,若发生冲突采用线性探测法处理。

(1) 计算出每个元素的散列地址并画出散列表;

0 1 2 3 4 5 6
63 36 15 22 40
1 1 2 3 1

(2) 求出查找每一个元素概率相等情况下的平均查找长度。

平均长度
L = (1 + 1 + 2 + 3 + 1 )/ 5 = 1.6

3. 已知序列(10,18,4,3,6,12,1,9,18,8)请用快速排序写出每一趟排序的结果。

参考教程

10 18 4 3 6 12 1 9 18 8
8 18 4 3 6 12 1 9 18
8 4 3 6 12 1 9 18 18
8 9 4 3 6 12 1 18 18
8 9 4 3 6 1 10 12 18 18
1 9 4 3 6 10 12 18 18
1 4 3 6 9
1 6 4 3 9
1 6 4 3 8 9
1 3 4 6 8 9 10 12 18 18

4. 设有无向图G如下图所示,要求画出用Prim算法构造最小生成树的各个步骤以及给出最小生成树的权值。

[参考教程] 假定从 1 开始

1 --> 3
1 --> 2
3 --> 5
5 --> 6
6 --> 4
最小生成树权值:3 + 2 + 4 + 1 + 1 = 11

5.已知数据六个字母及在通信中出现频率如下表:

*A* *B* *C* *D* *E* *F*
*0********.*****15* *0.********15* *0.********1* *0.********1* *0.********2* *0.********3*

把这些字母和频率作为叶子结点及权值,完成如下工作:

参考教程

参考教程

(1) 画出对应的Huffman树。

(2) 计算带权路径长度WPL。

(3) 求A、B、C、D、E、F的Huffman编码。

写错了,害。。格式有点没弄清

6. 设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起,逐个输入各个数据而生成的二叉搜索树的步骤。

参考教程

7.设有向图G如下图所示,若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,试写出:

参考教程

(1) 从顶点1出发进行深度优先遍历的序列;

1 --> 2 --> 4 --> 5 --> 3

(2) 从顶点2出发进行广度优先遍历的序列。

2, 3, 4 ,5 ,1

8. 已知一组记录的排序码为(46,79,56,38,40,80, 95,24),写出对其进行快速排序的每一次划分结果。。

46 79 56 38 40 80 95 24
24 79 56 38 40 80 95
24 56 38 40 80 95 79
24 40 56 38 80 95 79
24 40 38 56 80 79 95
24 40 38 46 56 80 79 95
24 38 40 46 56 79 80 95

9. 已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。

前: 中 左 右
中: 左 中 右
根节点: A
左树 EBCD
右树 FHIGJ
左 A --> B --> E
B --> C(右) 
C --> D(右)

后:EDCBIHJGFA

10.已知一个图的顶点集V和边集E分别为:V={1,2,3,4,5,6,7};

​ E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

​ (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。

参考教程

绘图得

11. 已知一棵二叉树先序遍历的结果为ABDGCEF,中序遍历的结果为DGBAECF,请画出该二叉树并写出后序遍历的结果。

懒得写了

12. 给定5个字符a,b,c,d,e,f,它们的权值集合为W={2,3,4,7,8,9},请构造一棵哈夫曼树,并给出各个字符的哈夫曼编码。

懒得写了

13. 给定带权无向图G如下,请给出采用Prim算法从顶点0出发构造最小生成树的过程。

0 --> 1
1 --> 3
1 --> 2
2 --> 4
2 --> 5

14. 设给定关键字序列为(19,1,23,14,55,20,84,27,68,11,10,77,45),给定哈希函数为H(key)=key % 13,采用线性探测法解决冲突,哈希表地址范围为0~16,请为该关键字序列构造哈希表。

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
关键字 1 14 55 27 68 19 20 84 45 23 11 10 77
查询次数 1 2 1 4 3 1 1 3 4 1 1 3 2

15. 已知关键字序列(12,2,16,30,28,10,20,6,18),请以12为轴用快速排序法将其排成升序序列,写出第一趟排序的过程及结果。

12 2 16 30 28 10 20 6 18
6 2 16 30 28 10 20 18
6 2 30 28 10 20 16 18
6 2 10 30 28 20 16 18
6 2 10 12 28 30 20 16 18

粉色的花瓣,美丽地缠绕在身上。依在风里。