9-6-3-最小代价生成树-克鲁斯卡尔算法

数据结构复习题汇总黄⽼师：题型结构如下：单项选择题，15⼩题，30分；填空题，5⼩题，10分；综合应⽤题，50分（树、图、查找）算法设计与分析，2选1,10分（线性结构）试卷中⼀些算法只给英⽂名称；考查范围(⿊体字为建议的重点考查内容；红字为备注；蓝字为拟纳⼊的考研⼤纲内容)⼀、绪论（⼀）算法、数据结构基本概念（⼆）算法分析中O（f（n））符号的含义（三）时间复杂度简单分析表⽰⼆、线性表（⼀）线性表的定义和基本操作（⼆）线性表的实现1.顺序存储2.链式存储3.线性表的应⽤三、栈、队列（⼀）栈和队列的基本概念（⼆）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应⽤四、树与⼆叉树（⼀）树的概念（⼆）⼆叉树1.⼆叉树的定义及其主要特征2.⼆叉树的顺序存储结构和链式存储结构3.⼆叉树的遍历及应⽤（三）树、森林1. 森林与⼆叉树的转换2. 树的存储结构；3.树和森林的遍历4.线索⼆叉树的基本概念和构造（四）⼆叉树的应⽤1.哈夫曼（Huffman）树和哈夫曼编码2.⼆叉排序树五、图（⼀）图的基本概念（⼆）图的存储及基本操作1.邻接矩阵法2.邻接表法（三）图的遍历1.深度优先搜索2.⼴度优先搜索（四）图的基本应⽤1.最⼩（代价）⽣成树2.最短路径3.拓扑排序4.关键路径六、查找（⼀）查找的基本概念（⼆）顺序查找法（三）折半查找法（四）⼆叉查找树及其基本操作（只考察基本概念）（五）平衡⼆叉树（只考察基本概念）（六）散列（Hash）表（七）查找算法的分析及应⽤七、排序（⼀）排序的基本概念（⼆）直接插⼊排序（三）⽓泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（⼋）⼆路归并排序（merge sort）（九）各种排序算法的⽐较（⼗）排序算法的应⽤选择题1、顺序队列的出队操作，正确修改队⾸指针的是（ B ）（A）sq.front = (sq.front+1)%maxsize; （B）sq.front = sq.front+1;（C）sq.rear = (sq. rear +1)%maxsize; （D）sq.rear = sq. rear +1;2、⾮空的循环单链表head的尾结点（由指针p指）满⾜（ C ）（A）p->next = NULL （B）p = NULL （C）p->next = head （D）p = head3、在单键表中，删除p所指结点的直接后继，其中指针修改为（ A ）（A）p->next = p->next ->next; （B）p = p->next; p->next = p->next->next;（C）p->next = p->next; （D）p = p->next ->next;4、通常要求同⼀逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）（A）数据元素具有同⼀特点（B）不仅数据元素所包含的数据项的个数要相同，⽽且对应数据项的类型也要⼀致（C）每个数据元素都⼀样（D）数据元素所包含的数据项的个数要相等5、关于线性表，下列说法正确的是（ D ）（A）每个元素都有⼀个直接前驱和直接后继（B）线性表中⾄少要有⼀个元素（C）表中诸元素的排列顺序必须是由⼩到⼤或由⼤到⼩的（D）除第⼀元素和最后⼀个元素外，其余每个元素都有⼀个且仅有⼀个直接前驱和直接后继6、带头结点的单链表，其表头指针为head，则该单链表为空的判断条件是（ B ）（A）head == NULL （B）head->next == NULL（C）head->next == head （D）head !== NULL7、含n个顶点的连通图中的任意⼀条简单路径，其长度不可能超过（C ）（A）1 （B）n/2 （C）n-1 （D）n8、设有⼀个顺序栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元素出栈的顺序是S2, S3, S4, S6, S5, S1，则栈的容量⾄少应该是（ B ）（A）2 （B）3 （C）5 （D）69、设深度为k的⼆叉树上只有度为0和度为2的结点，则这类⼆叉树上所含结点的总数最少为（ C ）个（A）k+1 （B）2k （C）2k -1 （D）2k +110、从具有n个结点的单链表中查找指定结点时，若查找每个结点的概率相等，在查找成功的情况下，平均需要⽐较（ D ）个结点。

20091.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III8.下列叙述中，不符合m阶B树定义要求的是A．根节点最多有m棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性表是按照什么顺序排列的元素集合？A. 任意顺序B. 无序C. 有序D. 线性2. 链表与数组相比，其主要优点是什么？A. 节省空间B. 访问速度快C. 插入和删除操作灵活D. 内存分配简单3. 栈（Stack）是一种遵循什么原则的数据结构？A. 先进先出B. 先进后出C. 后进先出D. 后进后出4. 哈希表解决冲突最常用的方法是？A. 链接法B. 替换法C. 线性探测法D. 二次探测法5. 树和二叉树的主要区别是什么？A. 树的节点数可以比二叉树多B. 树的节点可以有多个子节点C. 树的节点可以没有子节点D. 树的节点可以有左子节点和右子节点6. 什么是二叉搜索树（BST）？A. 所有左子节点的值小于根节点的值B. 所有右子节点的值大于根节点的值C. 所有左子节点的值大于根节点的值D. A和B都正确7. 图的邻接矩阵表示法适用于哪种类型的图？A. 稠密图B. 稀疏图C. 有向图D. 无向图8. 排序算法的时间复杂度为O(n^2)的算法有哪些？A. 选择排序B. 冒泡排序C. 插入排序D. 所有以上9. 什么是递归？A. 函数调用自身B. 函数调用其他函数C. 循环结构D. 条件语句10. 动态规划主要用于解决什么问题？A. 排序问题B. 查找问题C. 优化问题D. 数据存储问题二、简答题（每题5分，共20分）1. 请简述链表和数组的区别。

2. 解释什么是图的深度优先搜索（DFS）。

3. 什么是二叉堆？请简述其性质。

4. 描述快速排序算法的基本思想。

三、编程题（每题15分，共30分）1. 编写一个函数，实现单链表的反转。

2. 编写一个函数，实现二叉树的前序遍历。

四、算法设计题（每题15分，共30分）1. 设计一个算法，用于在无序数组中找到第k小的元素。

2. 设计一个算法，实现最小生成树的克鲁斯卡尔算法。

五、综合应用题（10分）假设你正在开发一个在线图书管理系统，请设计一个数据结构来存储书籍信息，并实现以下功能：- 添加新书- 删除书籍- 查找特定书籍- 列出所有书籍请提供数据结构的设计思路和相应的伪代码。

考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。

n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

即无向连通图的生成树不是唯一的。

连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。

最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。

最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。

解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。

他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。

时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。

第7章 图 自测卷解答 姓名 班级一、单选题（每题1分，共16分） 前两大题全部来自于全国自考参考书！（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6 （ ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 （建议：0 1 2 3 4 5 6） （ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 2建议：先画出图，再深度遍历⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110（ A ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发不是深度优先遍历的结点序列是A．0 1 3 2 B. 0 2 3 1C. 0 3 2 1D. 0 1 2 3（A）14. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）15. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）16. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

最小生成树问题课程设计一、课程目标知识目标：1. 理解最小生成树的概念，掌握其定义及性质；2. 学会运用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法求解最小生成树问题；3. 了解最小生成树在实际问题中的应用，如网络设计、电路设计等。

技能目标：1. 能够运用普里姆和克鲁斯卡尔算法解决最小生成树问题，并进行算法分析；2. 能够运用所学知识解决实际问题，具备一定的算法设计能力；3. 能够通过合作与交流，提高问题分析和解决问题的能力。

情感态度价值观目标：1. 培养学生对数据结构与算法的兴趣，激发学习热情；2. 培养学生的团队合作意识，学会倾听、尊重他人意见；3. 培养学生面对问题勇于挑战、积极进取的精神。

课程性质：本课程为计算机科学与技术专业的高年级课程，旨在帮助学生掌握图论中的最小生成树问题及其求解方法。

学生特点：学生具备一定的编程基础和图论知识，对算法有一定的了解，但可能对最小生成树问题尚不熟悉。

教学要求：结合学生特点，采用案例教学、任务驱动等方法，注重理论与实践相结合，培养学生的实际操作能力和创新思维。

通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高解决复杂问题的能力。

二、教学内容1. 最小生成树概念与性质- 定义、性质及定理- 最小生成树的构建方法2. 普里姆算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用3. 克鲁斯卡尔算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用4. 最小生成树在实际问题中的应用- 网络设计- 电路设计- 其他领域应用案例5. 算法比较与优化- 普里姆与克鲁斯卡尔算法的比较- 算法优化方法及其适用场景6. 实践环节- 编程实现普里姆和克鲁斯卡尔算法- 分析并解决实际问题- 小组讨论与成果展示教学内容依据课程目标进行选择和组织，注重科学性和系统性。

参考教材相关章节，制定以下教学安排：第1周：最小生成树概念与性质第2周：普里姆算法第3周：克鲁斯卡尔算法第4周：最小生成树在实际问题中的应用第5周：算法比较与优化第6周：实践环节与总结三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言和形象的比喻，对最小生成树的概念、性质、算法原理等基础知识进行讲解，使学生快速掌握课程内容。

克鲁斯卡尔算法求最小生成树的最短路径克鲁斯卡尔算法的核心思想是从图的边集中选取边来构建最小生成树，首先将图中的所有边按照权重进行排序。

然后依次取最小权重的边，如果这条边的加入不会形成环路，则将它加入最小生成树的边集中。

重复这个过程，直到最小生成树中的边数等于顶点数减一，或者所有的边都已经考虑过。

假设有一个包含n个顶点的带权无向图G=(V,E)，其中，V表示顶点的集合，E表示边的集合。

假设我们要求解G的最小生成树。

1.初始化边集E'为空集，集合S={v}，v是图中任意一个顶点。

2.对所有的边进行排序，按照边的权重从小到大排列。

3.从排序后的边集中依次选取边e，如果边e的两个顶点都不在集合S中，则将边e加入集合S，并加入边集E'中。

4.重复步骤3，直到E'中的边数等于n-1在克鲁斯卡尔算法中，需要使用并查集来判断选定的边e是否会形成环路。

并查集是一种数据结构，用于维护元素的等价关系。

它有两个主要操作，即查找和合并。

使用并查集的步骤如下：1.初始化并查集，使得每个元素都是一个单独的集合。

2.对每一条边e=(u,v)，如果u和v在同一个集合中，则说明加入这条边会形成环路；否则，将这两个集合合并。

3.重复步骤2，直到所有的边都考虑过。

接下来，我们通过一个具体的例子来说明克鲁斯卡尔算法的具体过程。

假设有以下的带权无向图G=(V,E)，其中，V={A,B,C,D,E,F,G}，E为边的集合，每条边的权重如下：AE:5AB:7AG:8BF:7BC:9CD:5CG:9DE:15DF:6EG:11EF:8FG:9按照权重对边进行排序：CD:5AE:5DF:6AB:7BF:7EF:8AG:8CG:9BC:9FG:9DE:15EG:11从最小的边开始选取，首先选取CD:5，加入到最小生成树的边集中。

最小生成树的边集：{"CD:5"}接下来选取AE:5，加入到最小生成树的边集中。

西北大学计算机专硕研究生入学考试历年真题集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY-西北大学2015年招收攻读硕士学位研究生试题(回忆版) 科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。

一、简答 [每小题6分，共30分]1、简述四类基本的数据逻辑关系，并用图表示。

2、简述数组、广义表属于线性表原因。

3、算法的定义及特性。

4、什么是平衡二叉排序树平衡因子的取值范围是什么5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。

二、分析与方法选择 [每小题10分，共30分]1、折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。

2、分析快速排序的性能（最好情况、最坏情况）。

3、关于二叉树结点度数的计算。

（牢记二叉树的5条性质，会计算二叉树及K叉树相关的计算。

）三、构造结果 [每小题8分，共40分]1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。

备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。

但是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。

这道题具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。

2、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树的生成。

3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。

4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。

5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法。