18春西南大学课程名称【编号】：数据结构【0012】网上大作业

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