2018年春季[0012]《数据结构》大作业 答案

1. 首先根据先序和中序画出二叉树，该二叉树为： A / \\ E B 西南大学网络与继续教育学院课程考试试题卷 类别： 网教 专业： 计算机科学与技术 2018年6月 课程名称【编号】：数据结构【0012】 A卷 大作业 满分：100分 一、 大作业题目 1、已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。 2、设计在链式结构上实现简单选择排序算法。 3、请画出下图的邻接矩阵和邻接表。 \\ / \\ F G C \\ D / H \\ 4、已知一个图的顶点集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) I 20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 / \\ 5、画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 J K 二、大作业要求 大作业共需要完成3道题： 后序遍历： FEGKJIHDCBA 第1大题必做，满分30分； 第2-3大题选做1题，满分30分； 第4-5大题选作1题，满分40分。 - 1 -

3. 4. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 - 2 -