数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题6-配套说课稿.docx

大数据技术与应用专业教学资源库 《数据结构》课程说课稿 《数据结构》期末考试试卷A卷-简答题6 主讲：章万静  序号 PPT 说课稿 幻灯片 1 大家好。我是《数据结构》课程的主讲教师——章老师。 下面我们开始重点分析试卷A中的题目。 幻灯片 2 我们来看一下简答题。 幻灯片 3 简答题的第6题。 画出下图的最小生成树。 这道题5分。 我们知道，最小生成树要掌握下面三个要点： 1、6个顶点的最小生成树应该有5条边，5条边的权值加起来和最小，而且5条边能让6个顶点是连通的，并且没有闭合的回路。 2、最小生成树有2种方法：普里姆算法，克鲁斯卡尔算法。 3、最小生成树有可能不是唯一的。 幻灯片 4 第一种方法，普里姆算法生成最小生成树。这种方法是从顶点出发，每增加一个顶点，就会新增一条边，直到增加到6个顶点5条边为止，注意不能产生回路。 我们来分析普里姆算法生成最小生成树的详细过程： 第一步：以A为源点，看看其他那个顶点到A的连线权值最小。C到A的权值为3，最小。那么就新增一个顶点C，新增一条边3。 第二步：以A或C为出发点，看看其他那个顶点到A或C的连线权值最小。 B到C的权值为3，最小。那么就又新增一个顶点B，又新增一条边3。 第三步：以A、B或C为出发点，看看其他那个顶点到A、B或C的连线权值最小。E到A的权值为4，最小。那么就又新增一个顶点E，又新增一条边4。 第四步：以A、B、C或E为出发点，看看其他那个顶点到A、B、C或E的连线权值最小。F到E的权值为4，最小。那么就又新增一个顶点F，又新增一条边4。 第五步：以A、B、C、E或F为出发点，看看其他那个顶点到A、B、C、E或F的连线权值最小。F到A的权值为5，最小，但是这条边不能用，它会让AEF构成回路，必须舍弃。B到A的权值也为5，最小，但是这条边也不能用，它会让ABC构成回路，也必须舍弃。剩下就是D到A，或者D到C的权值为8，最小。这2条边随便选择一条都可以，选择的边不一样，最小生成树的结构也不一样，所以说最小生成树可能不是唯一的。这里，我们随便选择一条边，就选D到C这条边，那么就又新增一个顶点D，又新增一条边8。 通过上面这样五步，普里姆算法就实现了最小生成树，6个顶点5条边，没有回路。 幻灯片 5 第二种方法，克鲁斯卡尔算法生成最小生成树。这种方法是从边出发，每确定一条边，新增一些顶点，直到确定5条边6个顶点为止，注意不能产生回路。 我们来分析克鲁斯卡尔算法生成最小生成树的详细过程： 第一步：在所有的边中，看看那条边的权值最小。A到C，或者B到C的权值为3，最小，我们任意选择一条边，B到C。那么就确定了一条边3，2个顶点B、C。 第二步：在剩下的边中，看看那条边的权值最小。A到C的权值为3，最小。那么就新增一条边3，新增一个顶点A。 第三步：在剩下的边中，看看那条边的权值最小。E到A，或者E到F的权值为4，最小，我们任意选择一条边，E到F。那么就又新增一条边4，新增两个顶点E、F。 第四步：在剩下的边中，看看那条边的权值最小。E到A的权值为4，最小。那么就又新增一条边4，没有新增顶点。 第五步：在剩下的边中，看看那条边的权值最小。 F到A的权值为5，最小，但是这条边不能用，它会让AEF构成回路，必须舍弃。B到A的权值也为5，最小，但是这条边也不能用，它会让ABC构成回路，也必须舍弃。剩下就是D到A，或者D到C的权值为8，最小。这2条边随便选择一条都可以，选择的边不一样，最小生成树的结构也不一样，所以说最小生成树可能不是唯一的。这里，我们随便选择一条边，就选D到A这条边，那么就又新增一条边8，新增一个顶点D。 通过上面这样五步，克鲁斯卡尔算法就实现了最小生成树，5条边6个顶点，没有回路。 幻灯片 6 本次微课就介绍到这里，希望大家好好理解与掌握。谢谢观看。