数据结构课程设计_数据结构最小生成树

自考02142《数据结构导论》通关宝典 　　自考神器APP推荐：自考笔果题库；自考组织推荐：自考指导圈；对自考不熟悉，自己摸索需要耗费大量的时间和精力，你要找寻的答案也许在我文章/回答里可能只是一段话而已，我，多看看我的文章和回答，对你自考大有裨益，少走弯路。如需长期专业指导 自考规划 最快毕业方案可以这里找到我。 　　https://zhuanlan.zhihu.com/p/ 　　前言 　　02142数据结构导论的真题题型主要是四大题型：选择题+填空题+应用题+算法设计题。分别占分30+26+30+14分，根据占分比，选择填空应用是我们复习的重点；算法设计题涉及到代码的实现，对于大多数人来说还是比较难的，而且两道算法设计题总分才14分，如果时间不充裕的小伙伴可以战略性放弃，主攻前面的86分。 　　选择填空都是考查细节知识，分值加起来接近及格（56分），一定要重视基础知识的掌握。 　　应用题的题型比较固定，其中一定要掌握的知识点为：二叉树（森林-二叉树的转换+遍历）、哈夫曼树及其编码、排序（快速排序、堆排序、二路并归、冒泡）。

　　前面的选择填空是及格的基础，后面的应用题则是及格的保障。如果你是代码不过关，记不住代码之类原因打算放弃最后两道设计题，那么选择填空应用这三大题型是你退无可退的路，请务必认真复习，争取一次通关。 　　数据结构导论这门专业课在很多省份都是一年只考一次，所以如果这次没过，就得到明年才能报考。意味着你的毕业将延期一年！ 　　一、选择题 　　⭐必考题：时间 空间复杂度（要么考选择题，要么考填空题）1、时间复杂度为O（n²）的程序

教材P30的原题，也是多次考过的真题



2、时间复杂度为O（n³）的程序

计算n！（整数n≥0）的递归算法是：int factorial（int n）{ if（n==0）return 1；else return n*Factorial（n–1）；}其时间复杂度为O（n）。计算i=1;j=0; while(i+j<=n) {if(i>j) j++; else i++;}，其时间复杂度为：O（n）时间复杂度阶数，复杂度由低到高的排序为:常数阶O（1）→对数阶O(
n)→线性阶O（n）→线性对数阶O(
n)→平方阶O(n²）→立方阶O（n³）→指数阶O（
）单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是O（1）。顺序表的时间复杂度为O（1）。已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为O（1）。设长度为n的队列用单循环链表表示（假设表尾结点为当前队列的队尾素），若只设头指针，则入队操作、出队操作的时间复杂度分别为O(n)、O(1)。在表长为n的顺序表时间复杂度为O（n）。设图的顶点数为n，则采用邻接矩阵作为存储结构的图的深度优先搜索算法的时间复杂度为O（n²）。设某个算法的计算量是问题规模n的函数：T（n）=a
+
n+cn+d，则该算法的时间复杂度：O（
）.将长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为O(m)。若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常对数阶量级复杂性小于线性阶量级。直接插入排序、直接选择排序、冒泡排序算法，其时间复杂性为：O(n²）。最好情况下，冒泡排序算法的时间复杂度为O（n）二分查找算法的时间复杂度是：O(
n)。时间复杂度为O(
n)且空间复杂度最优的排序方法是堆排序。

把这张表格背下来就行了 　　⭐必考题：排序排序之后记录的相对次序仍然保持不变，则称这种排序方法是稳定的。属于稳定的排序方法是直接插入排序、冒泡排序法、归并排序。快速排序属于交换排序。在待排数据基本有序的前提下，效率最高的排序算法是直接插入排序。能够使用二分查找算法进行查找的条件是必须以顺序方式存储，且素按关键字有序。需要辅助存储量最多的是归并排序。 　　⭐必考题：二叉树的属性深度为k（k≥1）的二叉树，结点数最多有（
-1)个。具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为13.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有：2n个指针域其中n+1个指针为NULL。二叉树的中序遍历序列中，结点P排在结点Q之前的条件是：在二叉树中P在Q的左边。与二叉链表结构形式完全相同的是孩子兄弟链表。 　　⭐必考题：有向图和无向图在一个无向图中，所有顶点的度数之和等于边数的2倍。具有n个顶点的无向图的边数最多为n*(n-1)/2。具有n个顶点的有向图的边数最多为n*(n-1)有10个顶点的无向完全图的边数是45【（10*9）/2】在带权有向图中求两个结点之间的最短路径可以采用的算法是：迪杰斯特拉（Dijkstra）算法。边稀疏的无向图采用邻接表存储较省空间。对于有n个顶点的无向图，所有生成树中都有且仅有 n-1条边含n个顶点的连通图中的任意一条简单路径，其长度不可能超过n-1例题：设有10个顶点的无向连通图，它包含的边数至少为9条边。无向图中的极大连通子图是连通分量。任何一个带权的无向连通图的最小生成树有一棵或多棵如果一个无向图有10个顶点，20条边，那么它的邻接表需要40个表结点。 　　⭐必考题：查找方法顺序查找、折半查找、索引顺序查找、分块查找，效率最高的查找方法是折半查找。若线性表采用链式存储结构，则适用的查找方法为顺序查找。采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为：从第1个素开始往后查找该数据素。要解决散列引起的冲突问题，最常用的方法是线性探测法、二次探测法、链地址法。 　　⭐必考：计算存储地址（要么考选择题，要么考填空题，主要有2种考查方式）计算指定存储地址：有二维数组，其形式为a[m][n]，每个素占K个存储单，会告知你初始存储地址（即第一个素的存储位置）。计算a[i][j]的存储地址为：起始地址+（n*i+j）*k例题①：以行序为主序的二维数组a[3][5]中，第一个素a[0][0]的存储地址是100，每个素占2个存储单，则a[1][2]的存储地址是114。【100+（5*1+2）计算第几个素地址:一个数组的第一个素的存储地址是100，每个素占2个存储单，则第5个素的存储地址是108。（100+4*2） 　　⭐结点+度对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为4。M个叶结点的哈夫曼树中，其结点总数为：2m-1。根据定义，树的叶子结点其度数：必等于0。

　　⭐零碎 　　1、表设顺序表的长度为100，在第40个素之后插入一个素所需移动素的个数为60。设顺序表的长度为100，在表中第40个素之前插入一个素时，需向后移动的素个数为61。【⭐插入操作时一定要注意是之前还是之后，如果是之前，需要+1】假设顺序表的长度为n，则在第i(1≤i≤n+1）个素之前插入一个新素x所需移动素的个数为n-i+1从一个长度为100的顺序表中删除第30个素，需向前移动的素个数为70.在表长为100的顺序表中做插入运算，平均移动素的次数为50.【100/2=50】在表长为101的顺序表中做删除运算，平均移动素的次数为50。在表长为n的顺序表中做插入运算的时间复杂度为O（n）若在长度为n的顺序表中插入一个结点，则其结点的移动次数：最少为0，最多为n。索引文件通常由索引表和主文件两部分构成，其中：索引表必须是有序文件。若线性表最常用的操作是存取第i个素及其后继的值，则最节省操作时间的存储结构是顺序表。单链表与顺序表相比，其特点是不需要预先分配存储空间。在一个长度为n（n>1）的单链表上，设有头和尾两个指针，下列操作与链表长度有关的是：删除单链表中的最后一个素.静态査找表指对査找表只进行两项操作，即查找表中某一素和读取表中“特定”数据素 　　2、树树中叶子的度是0二叉排序树中，根的左子树是二叉排序树、右子树也是二叉排序树。若一棵具有n（n>0个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是高度为n的二叉树。哈夫曼树的树形不一定唯一，但其WPL值最小且相等,总码长最短，没有严格要求区别左右子树权重次序。按层序（自顶向下、从左到右）遍历二叉树时需借助队列作辅助结构。对髙度为3的满二叉树进行层序遍历时，队列中所出现的素个数最多是4. 　　3、栈 在链栈的运算中，不需要判断栈是否为空的是进栈。将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是栈。链栈不用预先考虑容量的大小。若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有5种。栈空时出栈产生“下溢”，栈满时进栈产生“上溢“。 　　4、队 队列是先进先出的线性表。举例：一个队列的输入序列是A，B，C，D，则该队列的输出序列是A, B, C, D。关于链队列的运算说法正确的是：出队列需要判断队列是否空。队列初始化时一般将头指针 front和尾指针rear的值分别设置为0，0循环队列的队头指针为 front，队尾指针为rear，当front==rear时表明队列为空。循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为rear=(rear+1)%m。设以数组Q[m]存放循环队列的素，变量rear和 queuelen分别表示循环队列中队尾素的下标位置和素的个数。则计算该队列中队头素下标位置的公式是:（rear-queuelen+m）%m数组Q[n]表示一个循环队列，设f的值为队列中第一个素的位置，r的值为队列中实际队尾的位置加1，并假定队列中最多只有n-1个素，则计算队列中素个数的公式是:(r-f+n)%n在实现队列的链表结构中，其时间复杂度最优的是仅设置尾指针的单循环链表。 　　5、图

若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的层次遍历。“在旅游时从某地岀发要去某个目的地，如何选择线路才能使得路程最短”，从图的应用角度.最合理的解决方案是最短路径。图的深度优先搜索遍历类似于树的先序遍历；图的广度优先搜索遍历类似于树的层次遍历。 　　6、矩阵 对稀疏矩阵进行压缩存储的目的是节省存储空间。m行n列的矩阵有t个非零素，当t满足t<<m*n条件时，称该矩阵为稀疏矩阵。10阶上三角矩阵压缩存储时需存储的素个数为56。n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是n×n。把特殊矩阵A[10][10]的下三角矩阵压缩存储到一个一维数组M中，刚A中素a[4][3]在M中所对应的下标位置是13。假设一个10×10的上三角矩阵A按照列优先顺序压缩存储在一维数组B中，则B数组的大小应为55在含n个顶点和e条边的无向图的邻接矩阵中，零素的个数为n²-2e 　　二、填空题 　　⭐必考：基本概念数据结构是计算机组织数据和存储数据的方式。数据结构是指一组相互之间存在一种或者多种特定关系的数据的组织方式和它们在计算机内部的存储方式，以及定义在该数据上的一组操作。合理的数据结构可以降低程序设计的复杂性，提高程序执行效率。从数据结构的观点，数据通常可分为三个层次，即：数据、数据素和数据项。数据的基本单位是数据素。数据的不可分割的最小标识单位是数据项，它通常不具有完整确定的实际意义，或不被当作一个整体对待。数据项又称为字段或域算法的空间复杂度是指算法中需要的辅助变量所占用存储空间的大小。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。能正确地实现预定的功能，满足具体问题的需要，这种评价算法好坏的因素称为正确性。一个算法的时空性是指该算法的时间性能和空间性能。即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为健壮性。从运算类型角度考虑，属于加工型的操作是初始化、插入、删除操作；属于引用型的运算是：查找、读取。（这题是上一版本教材里面的内容）用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为非形式算法。ISAM中文含义为索引顺序存取方法。数据结构研究的主要内容包括数据的逻辑结构、存储结构、以及对数据及其关系的操作运算。一般说来，在每个逻辑结构上都定义了一组基本运算，通常这些运算包括：建立、查找、读取、插入和删除等。数据的存储结构又称为物理结构，可分为顺序存储、链式存储、索引存储、散列存储。结点按逻辑关系依次排列形成一条“锁链”的数据结构是：线性结构。根据数据素之间关系的不同特性，通常将数据结构分为四类基本结构，即：集合、线性结构、树形结构、图结构。任意两个结点之间都没有邻接关系，组织形式松散，这种组织形式称为集合。线性结构是具有n（n≥0）个结点的有穷序列。要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为机外表示、逻辑结构、存储结构。若要描述数据处理的变化过程，其正确的次序应为：处理要求、基本运算和运算、算法。从运算类型角度考虑，属于加工型的操作是初始化、插入、删除操作；属于引用型的运算是：查找、读取。为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为头节点。 　　⭐必考题：算法操作 　　1、单链表带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是：p->next==L单链表中指针p指向结点A，若要删除A之后的结点（存在且不释放存储空间），则需要修改指针的操作为p->next=p->next->next。非空的单循环链表的头指针为head，尾指针为rear，则rear->next=head设p指向单链表的最后一个结点，要在最后一个结点之后插入q所指的结点，需执行的语句序列是①、p->next=q；②、p=q ③、p->next=NULL。在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是：s->next=p->next; p->next=s。在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是：p->next—q； p->next=s。再一个单链表中，已知指针q指向指针p所指结点的前驱结点，则删除*p结点的操作是：q->next=p->next;设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是：head->next==head 　　2、双链表带头节点的双向循环链表L为空的条件是：(L->next==L)&&(L->prior==L)在双链表中，前趋指针和后继指针分别为 prior和next。若使指针p往后移动两个结点，则需执行语句p=p->next->next双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为：①、t-> prior=p;②、 t->next=p->next; ③、p->next->prior=t; ④、p->next=t.双向链表中，删除*t所指结点的操作为：t->prior->next=t->next ; t->next->prior=p->prior。(后面如果有free选项，选择free)

　　3、其他在带有头结点的循环链表中，头指针为head，判断指针p所指结点为首结点的条件是:p==head->next.在带有头结点的循环链表中，头指针为head，判断P所指结点为尾结点的条件是：p->next==head若 front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是Q.front =Q.rear。设有一循环队列SQ，现将数据x进行入队操作，语句为SQ. rear=(SQ. rear+1)% maxsize; SQ data[ SQ. rear]=x；二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是p->lchild==p->rchild== NULL一个带头结点的链栈LS，现将一个新结点入栈，指向该结点的指针为p，入栈操作为p->next=LS->next和LS->next=p判断链栈LS是否为空的条件是：LS->next==NULL判断一个带有头结点的链队列为空队列Q的条件是Q.front==Q.rear。 　　⭐必考题：逻辑结构+存储结构所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据素之间的逻辑关系。这种存储方式是顺序存储方式。表示数据素之间的关联方式通常采用的存储方式是顺序存储方式和链式存储方式。C语言对数组素的存放方式通常采用：按行为主的存储结构。若在线性表中采用二分查找法查找素，则该线性表必须按值有序，并且采用顺序存储结构。为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输岀的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是队。对于n（n≥0）个素构成的线性表L，适合采用链式存储结构的操作是：需要频繁地对L进行插入和删除操作。邻接表的存储方法结合了顺序存储与链式存储。 　　⭐必考：查找+排序在顺序査找、二分査找、散列査找和索引顺序査找四种查找方法中，平均査找长度与素个数没有关系的查找方法是散列查找。在插入排序方法中，类似图书馆中整理图书的过程的是直接插入排序。当待排记录数量较大时，比较有效的排序方法是选择排序。排序方法中，从 未排序序列中依次取出素与已排序序列（初始时为空）中的素按序进行比较，将其插入已排序序列的正确位置上的方法称为直接插入排序。插入、选择、冒泡及堆等四种排序方法在各自排序过程中其键值比较的次数与数据素的初始排列次序无关的有选择排序和堆排序。堆排序、快速排序、冒泡排序和归并排序方法对其按递增顺序进行排序，冒泡排序方法最省时间。如果要将序列{60，18，28，69，99，75，78}建成堆，则只需把60与 18 相互交换。设记录数为n，则冒泡排序算法在最好情况下所作的比较次数为n-1。用冒泡排序算法对n个带有键值的数据素进行排序，排序结束后所可能历经的最少趟数为1次。采用二叉排序树查找，平均查找长度介于O（n)和O（
n）之间。顺序查找算法的平均查找长度为(n+1)/2。二分查找算法的平均查找长度为：

(n+1)-1。

二叉排序树上的平均查找长度介于和O（
n）和O（n）之间。完成拓扑排序的前提条件是AOV网中不允许出现回路。 　　⭐其他零碎 　　1、表对顺序表执行插入操作，其插入算法的平均时间复杂性为N/2，平均需要移动约为n/2个数据素。线性表中所含结点的个数称为表长。索引顺序表由两部分组成：一个是顺序表，另一个是索引表。在表长为n的顺序表中插入或删除一个素，则需移动素的具体个数与表长和该素所处的位置有关。作为一种数据结构，查找表的逻辑结构是集合。二叉链表的结点结构包含一个数据域和两个指针域.静态查找表与动态查找表二者的根本差别在于施加在其上的操作不同。静态查找表是以具有相同特性的数据素集合为逻辑结构，但不包括插入和删除运算线性表中如果结点数不为零，刚除起始结点没有直接前驱外，其他每个结点有且仅有1个直接前驱。单链表各个结点在内存中的存储位置并不一定连续。 　　2、树树可以没有根节点。在一棵树中，根结点没有双亲。树的遍历主要有先序遍历、后序遍历和层次遍历三种。任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是都相同。满二叉树一定是完全二叉树。树的双亲表示法由一个一维数组构成，数组的每个分量包含数据域和双亲域两个域。一棵树中所有结点层次数的最大值称为该树的高度。注意区别1：一棵深度为6的满二叉树有63个节点。【
-1】注意区别2：高度（深度）为h的完全二叉树最少的结点个数是
注意区别3：假设高度为h二叉树中只有度为2和度为0这两种类型的结点，则该类二叉树中结点个数至多为
-1、至少为2h-1。二叉树第i（i≥1）层上的结点数最多为
设一个完全二叉树共含有196个结点，则该完全二叉树中含有叶结点的个数是98一个二叉树的最少结点个数为0.具有64个结点的完全二叉树的深度为7。具有63个结点的完全二叉树是满二叉树。某二叉树的先序遍历序列为 AJKLMNO，中序遍历序列为 JLKANMO，则根结点A的右子树中的结点个数为3.【画出二叉树就知道了，不知道如何画的看下面【三、应用题第2道】】

将含有80个结点的完全二叉树从根这一层开始每层从左到右依次对结点编号，根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是左孩子编号为80，右孩子不存在。在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为5个。【3*1+2*2+1*3+1=11 11-所有节点个数=5】用n个值构造一棵二叉排序树，它的最大深度为n。一棵二叉树T，度为2的结点数为20个，则叶子结点数为21。【n0=n2+1】具有10个叶结点的哈夫曼树中度为1的结点数为0个。100个结点的二叉树采用三叉链表存储时，空指针域NULL有102个。100个结点的二叉树采用二叉链表存储时，空指针域NULL有101个。对于一棵包含n个结点的二叉树，用二叉链表存储时，其指针总数为2n个，设森林F中有三棵树，其结点的个数分别为m1、m2、m3，则与F对应的二叉树根结点的右子树上的结点数是m2+m325.一个图的最小生成树是满足一定条件的生成树，即一个图的最小生成树是指该图的所有生成树中权值之和最小的生成树。构成最小生成树的算法有两种：Prim算法和克鲁斯卡尔算法。若对一棵有n（n>0）个结点的完全二叉树从1开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为1的结点存储到A[1]中，其余类推。若i>2，则A[i]的双亲结点为[i/2]用于描述分类过程的二叉树称为判定树。有10个叶结点的哈夫曼树中共有19个节点。假设初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点。将该森林构造成哈夫曼树，则最终求得的哈夫曼树的结点总数为2n-1。二叉树的任一结点都有两棵子树，并且这两棵子树之间有次序关系。由二叉树的后序（先序）序列和中序序列，可以唯一确定一棵二叉树。若一棵非空二叉树的先序序列与后序序列相同，则该二叉树可能的形状是树中只有一个根结点 　　3、栈一般情况下，函数的嵌套调用和程序递归的处理都是用栈来实现的。在栈结构中，允许插入和删除的一端称为栈顶。素的进栈次序为1，2，3，…，n，出栈的第一个素是n，则第k个出栈的素是n-k+1栈初始化运算的目的是：构造一个空栈。 　　4、队 在具有n个单、且采用顺序存储的循环队列中，队满时共有N-1个素。队列操作的原则是先进先出。 　　6、矩阵稀疏矩阵一般采用的压缩存储方法是三组表示法。若图的邻接矩阵是一个对称矩阵，则该图一定是一个无向图。无向图的邻接矩阵是对称矩阵。三个顶点v1，V2，V3的图的邻接矩阵为下图，则该图中顶点v2的出度为2.

为了节省存储空间，将矩阵中多个值相同的素只分配一个存储空间，零素不存储。这种存储方式通常称为矩阵的压缩存储。 　　7、其他

除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为简单回路。要完全避免散列所产生的“堆积”现象，通常采用链地址法。设有散列函数H（k）和键值k1、k2（k1≠k2），若H（k1）=H（k2），则这种现象称为“冲突”，且称键值k1和k2互为同义词。用键值通过散列函数存储位置的这种存储方式构造的存储结构称为散列表。数据素的键值和存储位置之间建立的对应关系称为散列函数设散列表中有n个存储单，散列函数H（key）=key%p，则p最好选择小于散列表长度n的素数。稳定性是排序方法本身的特性，与数据无关。在最好的情况下，对于具有n个素的有序序列，若采用冒泡排序，所需的比较次数为0次。影响排序算法时间复杂度的两个因素是关键字的比较次数和记录的移动次数。线性表、栈和队列中的素具有相同的逻辑结构，即线性结构。在估算算法空间复杂度时，一般只需要分析辅助变量所占用的空间。如果栈中的数据素已经满了，此时再进行进栈操作，会发生”上溢“ 　　三、应用题 　　应用题只考5题，每题6分，是最拿分的题型，请务必在这个题型上拿到高分，甚至满分！这是你这门通关的关键题型。虽然只考5题，但是历年出题过的知识点却不止5题，备考环节一定要过度做题 把每种知识点的题都能做对，考试的时候不管抽到什么知识点的题型都能得高分。 　　1、进栈出栈操作（送分题） 　　

　　2、求先序遍历 后序遍历 层次遍历（送分题） 　　考察方法一：已知中序遍历+前序或者后序遍历推算出整体二叉树。 　　这种考察方法是最根本的，如果能做出这种题型，那么下面几种考查方法就没问题了。 　　求解视频：看这个视频就知道这道题怎么做了。

　　学废了吗？学废了就要作对下面这道题哦，学费记得交一下——素质三连。

来做一道真题看看是你是否掌握考查方法二：已经画好了二叉树图，让你写出序列， 　　这是最简单的考查题型，能遇到这种题型的是天选之子无疑了。

　　3、二叉树转换成树或森林 　　考查方法主要是两种：①、树→森林；②、森林→树。

　　4、画哈夫曼树 　　考查方法一：只要你画出哈夫曼树。



考查方法二：不仅要你画出哈夫曼树，还要写出哈夫曼编码。

　　四、算法设计题（2*7=14分）