《数据结构》课程教学实施计划.doc

数据结构课程教学实施计划 数据结构课程教学实施计划课程代码04812600课程名称数据结构Data Structuresand Algorithms学时/学分64学时（48授课课时+16实验课时）/31学分先修知识高等程序设计、软件基础实验、高等数学、离散数学开课单位计算机与通信学院适用专业计算机科学技术、信息安全、通信工程、智能科学与技术专业开课时间本科2年1期课程性质必修使用教材数据结构（C语言版）严蔚敏著清华大学出版社xx 一、课程教学目标“数据结构与算法”是计算机专业本科生的一门必修的专业基础课，通过本课程的学习，让学生掌握线性表、栈、队列、二叉树、树和图等常用的数据结构；掌握常用的排序、检索算法及其时间、空间代价；学会分析计算机处理的数据对象的特性，能够选择并设计合适的数据结构及相应的算法，初步掌握算法的时间和空间代价的分析方法。 二、教学内容及基本要求（一）绪论 (1)了解数据类型、抽象数据类型、数据结构的概念以及它们之间的关系 (2)了解问题、算法、程序、算法的代价等概念（二）算法分析 (1)了解渐近算法分析、算法代价的增长率等概念 (2)了解算法的最佳情况、最差情况和平均情况 (3)掌握上限、下限的概念以及大、大和大表示法 (4)掌握渐进分析的化简法则 (5)掌握简单程序运行时间的计算方法 (6)了解问题的代价与算法的代价的区别 (7)了解多参数问题、空间代价、空间/时间权衡原则和实际操作中的一些因素（三）递归掌握递归算法的设计方法（四）线性表、栈和队列 (1)了解线性表的基本概念和抽象数据类型 (2)掌握顺序表的实现方法 (3)掌握带表头结点的单链表的实现方法 (4)了解线性表的两种实现方法的优点和缺点 (5)掌握带表头结点的双链表的实现方法 (7)了解单循环链表和双循环链表的结构 (8)了解栈的基本概念 (9)掌握顺序栈的实现方法 (10)掌握链式栈的实现方法 (11)了解顺序栈与链式栈的比较 (12)了解队列的基本概念 (13)掌握顺序队列的实现方法 (14)掌握链式队列的实现方法 (15)了解顺序队列与链式队列的比较（五）二叉树 (1)了解二叉树的定义与术语 (2)掌握满二叉树与完全二叉树的定义 (3)掌握满二叉树定理及其推论 (4)了解二叉树结点的抽象数据类型 (5)掌握前序、中序和后序周游二叉树的方法 (6)掌握用指针实现二叉树的方法 (7)了解二叉树实现的结构性开销的计算 (8)掌握用数组实现完全二叉树的方法 (9)掌握二叉检索树的实现方法 (10)掌握实现堆以及利用堆实现优先队列的方法 (11)掌握Huffman编码树的建立以及利用它进行编码/反编码的方法（六）树 (1)了解树的定义与术语 (2)了解树结点的抽象数据类型及树的周游方法 (3)掌握树的父指针表示法以及利用UNION/FIND算法解决等价类问题的方法 (4)了解树的子结点表表示法、动态和静态的左子结点/右兄弟结点表示法 (5)了解K叉树和树的顺序表示法（七）图 (1)了解图的术语和邻接矩阵、邻接表表示法 (2)了解图的抽象数据类型 (3)掌握图的邻接矩阵和邻接表实现方法 (4)掌握图的两种周游算法:深度优先和广度优先算法 (5)掌握图的两种拓扑排序算法 (6)了解关键路径算法 (7)掌握求单源最短路径的Dijkstra算法 (8)掌握求每对顶点间最短路径的Floyd算法 (9)掌握求最小支撑树的Prim算法和Kruskal算法（八）内排序 (1)掌握冒泡排序、选择排序和插入排序算法 (2)了解Shell排序算法 (3)掌握快速排序算法 (4)掌握归并排序算法 (5)掌握堆排序算法 (6)了解基数排序算法 (7)了解各种排序算法的实验比较和排序问题的下限（九）查找 (1)了解已排序数组的查找方法 (2)了解自组织线性表的查找方法 (3)了解集合的查找方法 (4)了解B树 (5)掌握散列函数的设计方法 （6）掌握两种冲突解决策略:开散列方法和闭散列方法 三、考核方式课堂讲授+作业+实验+考试课堂参与 （10）+课后作业 （10）+课程实验 （20）+课程考试 （60） 四、教学进度安排（含作业及实验安排）授课内容授课时间作业课程实验第一章绪论2作业1第二章线性表8作业2实验 1、2第三章堆栈和队列4作业3实验3第四章串2作业4实验4第五章数组和广义表2第六章树和二叉树8作业5实验5第七章图6作业6实验6第八章内部排序8作业7实验7第九章查找8作业8实验8小计488次8个 四、参考书1.数据结构与算法分析（C+版）（第二版）Clifford A.Shaffer著张铭刘晓丹等译电子工业出版社xx年2.数据抽象和问题求解Java语言描述.Frank M.Carrano等著,韩志宏译.清华大学出版社xx年4月第1版.附录一大作业设计并实现一个简单文本器设计目标1.该文本器能不断接收和执行人通过键盘发出的命令，直至收到结束命令时终止运行。 2.启动后给出提示信息，表示已经进入结束和执行命令的正常工作状态。 具体要求实现如下命令（注意下面说明中的和在实际命令中并不出现，命令和命令参数之间用空格分隔）i文件名把指定文件读入器（存储区）o文件名将存储区的内容写入指定文件ln字符串把给定字符串插入文本中作为第n行dn删除区里的第n行v显示整个文本区的内容pn显示文本第n行的内容f字符串显示包含指定字符串的所有行，在行前给出行的编号r字符串1字符串2将文本里所有的字符串1替换为字符串2sn字符串1字符串2将第n行里所有的字符串1替换为字符串2q终止器程序h帮助，说明所有命令及其使用方式（类似这个表）设计建议1.请首先考虑好内容的存储组织问题2.可以假定每行的长度不超过某指定字符数，例如80和127字符3.可以不考虑跨行的字符串匹配问题4.可以考虑用C标准库的行式读入命令（gets或fgets）把命令行整个读入一个字符数组，而后在数组里分析命令内容的实现方式。 这样实现起来比较方便5.可根据自己的认识增加其他命令（设计命令形式并完成相应实现）注意事项?该设计最重要的工作就是数据结构的选择和设计。 适当的数据结构可以使程序结构清晰，操作的实现方便，算法具有好的性质（速度快，虽然在小文件时不明显，但大文件就会显现出来），适应性强（例如，请考虑能否适应大型文件），易于扩充等等。 ?请综合考虑学过的几种数据结构，考虑器需要执行的各种操作，做出自己的设计选择。 ?可能的数据结构设计非常多，建议各位同学设想若干种设计，而后根据对问题的分析选出一种使用。 作业提交要求及注意事项1.要求每个同学独立完成这个实习项目，并写出一篇“实习报告”o说明程序的使用方式，包括所实现的所有命令及其使用形式和功能o给出几个使用程序中所提供命令的例子o程序实现中的设计问题选择了什么样的数据结构（为什么）；程序的基本部分及其相互关系；几个最重要的操作的实现；实现中遇到的问题及其解决方法；最后的效果o程序完成后的思考完成的程序有哪些不足之处；如果你重新做可能怎样改进；如果要你做一个真正能提供给别人使用的器，你可能怎样设计等等。 2.程序和实习报告都采用电子文档形式（通过email附件）交老师。 报告可以交PDF或DOC文件。 3.如果采用多个源文件的形式开发，发给老师前请把文件打包（可以打包为rar或者zip）。 注意只上交所有源程序文件（不要交可执行程序）。 必须保证程序能正常编译和执行。 4.请注明所用的程序开发环境（作为程序里的注释），以便老师检查时参考。 5.请注意保证自己上交的文档中没有病毒。 6.实习项目成绩将根据所做工作和上面各项要求的完成情况评定。 附录二小作业作业一1.1什么是抽象数据类型？试述抽象数据类型与C+类的区别。 1.2试用C+的类来定义表示复数的抽象数据类型。 (1)在复数内部用浮点数定义其实部和虚部； (2)实现2个构造函数缺省的构造函数没有参数；第2个构造函数将2个双精度浮点数分别赋给复数的是部和虚部； (3)定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 1.3 (1)假设某算法在输入规模为n时的计算时间为T(n)=3*2n。 在某台计算机上实现并完成该算法的时间为t秒。 现有另一台计算机,其运行速度为第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题? (2)若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题? (3)若上述算法的计算时间进一步改进为T(n)=8,其余条件不变,那么在新机器上用t秒时间能解输入规模为多大的问题?1.4硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。 对于计算复杂性分别为n,n2,n3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题?1.5证明如果一个算法在平均情况下的计算时间复杂性为(f(n)，,则该算法在最坏情况下所需的计算时间为(f(n)?。 作业二2.1用数组实现表的一个缺点是需要预先估计表的大小。 克服这个缺点的一个方法是在初始化时先将数组大小MaxSize置为1，其后在插入一个元素时，如果表已满，就重新分配一个大小为2*MaxSize的数组，将表中元素复制到新数组中，并删除老数组。 类似地，在删除一个元素后，如果表的大小已降至1/4MaxSize，就重新分配一个大小为1/2MaxSize的新数组，将表中元素复制到新数组中，并删除老数组。 (1)用上述思想重新设计用数组实现表的模板类。 (2)设P1,P2,P3,Pn是从空表开始的n个表运算组成的序列。 如果教材中用原数组实现表的方法执行此运算序列需要F(n)计算时间，试证明用本题实现表的方法执行此运算序列最多需要cF(n)计算时间，其中c是一个常数。 2.2解决习题2.1中提出的数组空间分配问题的另一种方法是预先为数组分配一个较大的空间，让多个表共享这一数组空间。 采用这种方法在设计算法时就应考虑多个表在同一数组空间中协调共存的问题。 试用上述思想重新设计用数组实现表的一个模板类。 2.3设表的Reverse运算将表中元素的次序反转。 (1)扩充用数组实现表的模板类List，使Reverse成为它的一个公有成员函数，并要求就地实现Reverse运算。 (2)试设计一个就地实现表的反转运算的函数Reverse（L），其中L是用数组实现的表，而Reverse不是List的成员函数。 2.4设A和B均为用数组实现的List类型的表，试设计一个List的公有成员函数ALTERNATE（A，B），从表A中第1个元素开始，交替地用表A和表B中元素组成一个新表。 例如，如果设表A为a (1)，a (2)，a(n)；表B为b (1)，b (2)，b(m)，则执行ALTERNATE（A，B）运算得到的新表为a (1)，b (1)，a (2)，b (2)，。 2.5设A和B均为用数组实现的List类型的表，且设A和B中元素是按非增序排列的。 试设计一个List的公有成员函数MERGE（A，B），将有序表A和B合并为一个新的有序表，并分析算法的计算复杂性。 2.6试设计用数组实现的表类List的公有成员函数SPLIT（A，B），创建2个新表A和B，其中A包含当前表中奇数位置上的所有元素，B包含其余元素。 作业三3.1扩充抽象数据类型栈的定义，增加如下栈运算 (1)Size()确定栈中元素个数； (2)Input(S)输入栈； (3)Output()输出栈。 用数组实现扩充后的栈。 3.2扩充抽象数据类型栈的定义，增加如下栈运算 (1)Split(S1,S2)将栈S1分为大小相同的2个栈S1和S2。 栈S2中含原栈S1中上半部分元素，其余元素留在栈S1中。 (2)Combine(S1,S2)将栈S2中元素合并于栈S1顶部，且保持原栈中元素次序。 S2成为空栈。 用数组实现上述扩充后的栈。 3.3设有编号为1，2，3，4的4辆列车，顺序进入一个栈式结构的站台。 试写出这4辆车开出车站的所有可能的顺序。 3.4试证明，借助于栈，由输入序列1，2，n，得到的输出序列为p (1)，p (2)，p(n)(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形，即存在i 3.5当2个栈共享一个数组stack0.n时，试设计在第k个栈中加入元素x的算法Push(k,x)，以及删除第k个栈的栈顶元素并存入x的算法Pop(k,x)。 3.6扩充抽象数据类型队列的定义，增加如下队列运算 (1)Size()确定当前队列的大小。 (2)Input(Q)输入一个队列Q。 (3)Output()输出队列。 用指针实现上述扩充后的抽象数据类型队列。 3.7扩充抽象数据类型队列的定义，增加如下队列运算 (1)Split(S1,S2)将队列S1分为大小相同的2个队列S1和S2。 队列S2中含原队列S1中第1，3，5，个元素，其余元素留在队列S1中。 (2)Combine(S1,S2)将队列S2中元素交错地合并于队列S1中，且保持原队列中元素的相对次序。 S2成为空队列。 用指针实现上述扩充后的抽象数据类型队列。 3.8扩充抽象数据类型队列的定义，增加如下队列运算OnQueue(x)若x是队列中的一个元素，则函数返回true，否则返回false。 用指针实现上述扩充后的抽象数据类型队列。 3.9如何实现以任意长的字符串为元素的队列?将一个字符串入队的运算耗时如何?3.10双向队列是一种特殊的表，对这种表进行插入或删除操作都只能在表的任意一端进行。 试用数组，指针和游标3种不同结构实现双向队列。 作业四4.1已知串s=”(xyz)*”,t=”(x+y)*z”，试用串的基本运算将串s转换为t。 4.2设x和y是用指针表示的串，试设计一个算法找出x中第一个不在y中出现的字符。 4.3用串的块链表示法实现串的基本操作。 4.4试设计一个将串逆置的算法并实现之。 4.5设s=”00001000010100001”,t=”0001”，说明其在朴素模式匹配算法中的匹配过程。 4.6试说明朴素模式匹配算法在最坏情况下的计算时间复杂性为(n-m+1)(m-1)。 作业五5.1一个高度为L的满k叉树有如下性质第L层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序从1开始对树中所有结点进行编号，问 (1)各层的结点数目是多少? (2)编号为n的结点的父结点(若存在)的编号是多少? (3)编号为n的结点的第i个儿子结点(若存在)的编号是多少? (4)编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?5.2对于4个元素1，2，3，4，画出表示这4个元素组成的集合的所有的二叉搜索树。 5.3用函数Insert，将整数7，2，9，0，5，6，8，1插入到一个空的二叉搜索树中去。 5.4用Delete从二叉搜索树中连续删除2个元素时，所得到的二叉搜索树与删除顺序有关系吗？5.5假设在一棵二叉搜索树中已存有1到1000之间的一些数。 现要找出数363。 下列的结点序列中哪一个不可能是所检查的序列？(a)2，252，401，398，330，344，397，363(b)924，220，911，244，898，258，362，363(c)925，202，911，240，912，245，363(d)2，399，387，219，266，382，381，278，363(e)935，278，347，621，299，392，358，3635.6在一棵表示有序集S的二叉搜索树中，任意一条从根到叶的路径将S分为3部分在该路径左边结点中的元素组成的集合S1，在该路径上的结点中元素组成的集合S2，以及该路径右边结点中元素组成的集合S3。 显然有S=S1?S2?S3。 对任意a?S1，b?S2，c?S3是否总有a?b?c，为什么？5.7设T为表示有序集S的一棵二叉搜索树。 S中的元素x存储于T的一个叶结点中，其父结点中存储的元素为y，试证明y是S中大于x的最小元素或y是S中小于x的最大元素。 作业六6.1在抽象数据类型图中增加Input和Output运算，分别用于输入和输出一个给定的图。 试在用邻接表和邻接矩阵2种表示法实现的图中分别实现上述2个运算。 6.2有向图G=(V,E)的转置是图GT=(V,ET),其中ET=(v,u)VV:(u,v)E。 因此，GT就是G的所有边反向所组成的图。 试按邻接表和邻接矩阵2种表示法写出从G计算GT的有效算法，并分析算法的计算时间复杂性。 6.3有向图G=(V,E)的平方图是图G2=(V,E2)，其中(u,w)E2当且仅当存在一个顶点vV，使得(u,v)E且(u,w)E，即当图G中存在一条从顶点u到顶点w的长度为2的路径时，(v,w)E2。 试按邻接表和邻接矩阵2种表示法分别写出从G产生G2的有效算法，并分析算法的计算时间复杂性。 6.4对有向图G作深度优先搜索，得到一个深度优先生成森林。 按树根被访问到的先后顺序将森林中的树从左到右排列，并从最左边的树开始，顺序对每棵树上的顶点作后序编号，这样可以得到一种顶点的编号。 另外，对G作深度优先遍历时，按递归调用DFS完成的先后顺序对顶点编号，可以得到另一种顶点编号。 证明上述2种对顶点的编号方式得到的顶点编号相同。 6.5用邻接表表示赋权有向图G，把G的全体顶点组织成一个优先队列，并用堆来实现这个优先队列。 在这些条件下写出Dijkstra算法的完整算法。 作业七7.1试修改冒泡排序算法，使得当输入序列已排好序时冒泡排序算法只需O(n)时间。 7.2试修改选择排序算法，使得当输入序列已排好序时选择排序算法只需O(n)时间。 7.3给定单位圆中n个点，假设这n个点在单位圆中是均匀分布的。 试设计一个O(n)时间算法对这n个点依其到圆心的距离进行排序。 7.4当a的元素已排成非增序时，QuickSort需要多少计算时间?7.5试证明当数组a的所有元素的键值都相同时，QuickSort需要的计算时间为(logn)。 作业八8.1试设计一个算法，用O(n+k)时间对介于1:k之间的n个整数进行预处理，使得经过预处理后，对于任意给定的区间a:b，能够在O (1)时间内回答这n个整数中有多少个数落在所给的区间中。 8.2在一个由元素组成的表中,出现次数最多的元素称为众数。 试写一个寻找众数的算法,并分析其计算复杂性。 8.3设T0:n-1是n个元素的一个数组。 对任一元素x，设S(x)i|Tix。 当|S(x)|n/2时，称x为T的主元素。 设计一个线性时间算法，确定T0:n-1是否有一个主元素。 8.4某石油公司计划建造一条由东向西的主输油管道。 该管道要穿过一个有n口油井的油田。 从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标和y坐标,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。 8.5试证明,在最坏情况下,求n个元素组成的集合S中的第k小元素至少需要n+min(k,n-k+1)-2次比较。 附录三实验习题实验一一笔画回路?问题描述对于给定的平面上的n个点和连接这n个点的m条边，每条边连接2个点。 一笔画问题找出给定的m条边的一条首尾相接的回路，使得从任何给定点出发沿此回路可以经过m条边的每条边恰好1次又回到出发点。 ?编程任务对于给定的n个点和连接这n个点的m条边，编程计算一笔画回路。 ?数据输入由文件input.txt给出输入数据。 第1行有2个正整数n和m，表示给定n个点和连接这n个点的m条边，点编号为1，2，n。 接下来的m行中，每行有2个正整数u,v，表示连接点u和v的一条边。 ?结果输出:将编程计算出的一笔画回路输出到文件output.txt。 如果不存在一笔画回路，则输出-1。 输入文件示例输出文件示例input.txt output.txt7101754356132112131617233435455657实验提交要求及注意事项1.要求每个同学独立完成这个小实验，并写一篇“实验报告”，报告具体要求如下o说明程序的使用方式，包括所实现的所有命令及其使用形式和功能；o给出几个使用程序中所提供命令的例子；o程序实现中的设计问题选择了什么样的数据结构（为什么）；程序的基本部分及其相互关系；几个最重要的操作的实现；实现中遇到的问题及其解决方法；最后的效果；o程序完成后的思考完成的程序有哪些不足之处及可能的改进之处。 2.程序和实验报告都采用电子文档形式（通过email附件）交老师。 报告可以交PDF或DOC文件。 3.如果采用多个源文件的形式开发，发给老师前请把文件打包（可以打包为rar或者zip）。 注意只上交所有源程序文件（不要交可执行程序）。 必须保证程序能正常编译和执行。 请注意保证自己上交的文档中没有病毒。 4.实验检查时间一般安排在相应的实验课程时间。 实验成绩将根据所做工作和上面各项要求的完成情况评定，并纳为本课程综合成绩评定指标。 实验二集成电路问题?问题描述集成电路通常由集成块，针脚和连接导线组成，如图所示。 当2个针脚之间有导线相连时，称这2个针脚是连通的。 如果针脚x和y连通，且针脚y和z连通，则针脚x和z连通。 集成电路问题给定k条导线连接的针脚，确定该集成电路的连通块。 ?编程任务对于给定集成电路的连接条件，编程计算集成电路的连通块。 ?数据输入由文件input.txt给出输入数据。 第一行有2个正整数n和k。 n表示给定的集成电路有n个针脚1，2，n；k表示有k条连接针脚的导线。 接下来的k行中，每行有2个正整数i和j，表示导线连接针脚i和j。 ?结果输出:将计算出的集成电路连通块数输出到文件output.txt。 输入文件示例输出文件示例input.txt107162541927108579output.txt3实验三电路板布线问题?问题描述矩形电路板的4周分布着n个针脚1，2，n，用于连接导线。 连线(p,q)表示针脚p和q之间有一根导线相连。 连接针脚的导线只能分布在电路板的矩形区域内。 对于给定的一组连线(p1,q1)，(p2,q2)，(pk,qk)，如果能在电路板的矩形布线区域内适当安排这组连线，使它们互不相交，则称这组连线是可布线的，否则为不可布线的。 例如，当n=8，且给定的，2，（）4，1）时是可布线的；给定的连线组为（8，7，（）6，5，（）3，2，（）4，1连线组为（）时是不可布线的，如图所示。 8，7），（6，3），（5对于给定的n个针脚和k条连线，试设计一个算法判定这组连线是否是可布线的。 ?编程任务给定正整数n，表示矩形电路板的4周分布着n个针脚1，2，n，以及一组连线(p1,q1)，(p2,q2)，(pk,qk)，编程计算这组连线是否可布线。 ?数据输入由文件input.txt给出输入数据。 第一行有1个正整数n，表示电路板的4周分布着n个针脚。 接下来的n/2行，每行有2个正整数，表示1根连线。 ?结果输出:将计算结果输出到文件output.txt。 当所给连线组是可布线的，输出“Yes”，否则输出“No”。 输入文件示例输出文件示例input.txt814235678output.txt Yes实验四平行轨道车皮排序问题?问题描述在一个列车调度站中，k条轨道平行连接到1条侧轨处，形成1条主轨道和k-1条辅助调度轨道。 主轨道记为Hk，辅助轨道从下到上依次记为H1，H2，Hk-1如下图所示。 其中主轨道左边为车皮入口（记为H0），主轨道右边为出口（仍记为Hk）。 编号为a1,a2,?,an的n个车皮从入口依次进入主轨道，由调度室安排车皮进出轨次序，并对车皮按其出轨次序重新排序为1，2，n。 调度室在安排车皮进出轨次序时，遵循以下规则1 （1）车皮入口H0处的车皮可以进入辅助轨道H1，H2，Hk-1之一，或直接进入车皮出口Hk。 2 （2）辅助轨道H1，H2，Hk-1处的车皮可以进入车皮出口Hk。 ?编程任务给定正整数n，和n个车皮的初始编号a1,a2,?,an，以及轨道数k，编程计算车皮调度方案，使车皮在车皮出口按照1，2，n的顺序输出。 ?数据输入由文件input.txt给出输入数据。 第1行有2个正整数n和k，表示有n个车皮，k个轨道。 第2行是n个车皮的初始编号a1,a2,?,an。 ?结果输出:将计算出的车皮调度方案输出到文件output.txt。 文件的每行是一个形如“a-b”的输出序列。 其中a和b是轨道号，“a-b”表示轨道Ha处的车皮进入轨道Hb。 如果无法实现所要求的调度，输出“No Solution!”。 输入文件示例输出文件示例input.txt93output.txt010-10-20-20-20-32-31-32-30-20-31-32-32-31-3实验五前缀二叉树问题?问题描述图5-1所示的运算称为二叉树的叶收缩运算图5-1叶收缩运算设A和B为2棵二叉树。 若通过对二叉树B执行k次叶收缩运算后得到一棵与A同构的二叉树，则称二叉树A为二叉树B的一个前缀。 试设计一个算法来判断一棵二叉树是否为另一棵二叉树的前缀。 ?编程任务对于给定的2棵二叉树A和B，编程计算二叉树A是否为二叉树B的前缀，二叉树B是否为二叉树A的前缀。 ?数据输入由文件input.txt给出输入数据。 第1行有1个正整数n，表示给定的第1棵二叉树A有n个顶点，编号为1，2，n。 接下来的n行中，每行有3个正整数a,b,c，分别表示编号为a的结点的左儿子结点编号为b，右儿子结点编号为c。 接下来是第2棵二叉树B的信息。 第n+2行有1个正整数m，表示给定的第2棵二叉树有m个顶点，编号为1，2，m。 接下来的m行中，每行有3个正整数a,b,c，分别表示编号为a的结点的左儿子结点编号为b，右儿子结点编号为c。 各结点信息按照层序列表的顺序给出。 ?结果输出:将计算结果输出到文件output.txt。 如果二叉树A为二叉树B的前缀则在第1行输出“Yes”否则在第1行输出“No”。 如果二叉树B为二叉树A的前缀则在第2行输出“Yes”否则在第2行输出“No”。 输入文件示例i nput.txt51424302503005001012443725630105896007008009001000输出文件示例output.txt YesNo实验六最大边权最小生成树问题问题描述试设计一个构造图G的生成树的算法，使构造出的生成树的边的最大权值达到最小。 编程任务对于给定的赋权图G，编程计算图的最大边权最小生成树。 数据输入由文件input.txt给出输入数据。 第1行有2个正整数n和m，表示给定的图G有n个顶点和m条边，顶点编号为1，2，n。 接下来的m行中，每行有3个正整数u,v,w，表示图G的一条边(u,v)及其边权w。 结果输出:将编程计算出的最大边权最小生成树的最大边权输出到文件output.txt。 如果不存在所要求的最大边权最小生成树，则输出-1。 输入文件示例输出文件示例i nput.txt output.txt7925122816102714231665257524741834125422实验七输油管道问题问题描述某石油公司计划建造一条由东向西的主输油管道。 该管道要穿过一个有n口油井的油田。 从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。 编程任务给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。 数据输入由文件input.txt提供输入数据。 文件的第1行是油井数n，1n10000。 接下来n行是油井的位置，每行2个整数x和y，-10000x，y10000。 结果输出:程序运行结束时，将计算结果输出到文件output.t