数据结构与算法 复习与习题解析.pdf

数据结构与算法复习与习题解析第一讲数据结构与算法概述 了解数据结构有关概念的含义，特别是数据的 逻辑结构和存储结构之间的关系；（重点）熟悉类c语言的书写规范;了解计算算法时间复杂度的方法。（难点）2数据结构的定义按某种逻辑关系组织起来的一批数据（或称 带结构的数据元素的集合）应用计算机语言 并按一定的存储表示方式把它们存储在计算 机的存储器中，并在其上定义了一个运算的 集合。基本概念和术语【数据结构】相互之间存在一种或多种特定关系的数据 元素的集合【数据】是对信息的一种符号表示。是可以输入计算机中，能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个 整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不 可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个 子集。424/03/201 计算机如何解决问题问题 数学模型 实现机外表示建模逻辑结构求精存储结构处理要求基本运算-1编程实现研究数据结构是为了帮计算机解决问题!524/03/2016数据结构的研究内容【数据结构的三个方面研究内容】具体来说，数据结构包 含三个方面的内容，即数据的逻辑结构,数据的存储结构 和对数据所施加的运算（操作）。线性结构数据的逻辑结构 厂（面向人类）非线性结构 数据的存储结构（面向计算机）顺序存储 链式存储 索引存储 散列存储 线性表 栈 队列、串及数组树形结构、图形结构数据的运算（操作）：检索、排序、插入、删除、修改等624/03/201四种基本逻辑结构【集合】数据元素间 除了 同属于一个集合外,无其他关系。【线性结构】1对1的 关系比如线性表.栈、队列。【树形结构】1对多的 关系比如树。【图形结构】多对多的关系比如图。24/03/20数据结构与算法算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效率;而数据结构的优劣由算法的执行来体现。“算法+数据结构二程序”算法!=程序 算法是供人阅读的，程序是让机器执行的 算法用计算机语言实现时就是程序 程序不具有算法的有穷性算法的概念算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一 个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型 O在数值性操作中主要进行的是算术运算；而在非数值性 操作中主要进行的是检索、排序、插入、删除等等。:程序不等于算法：计算机程序是算法的具体实现。924/03/201算法的性质 1 有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他 人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的 基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的 输出是指与输入有某种特定关系的量。算法设计的要求:正确性（四个境界）没有语法错误 对于合法的输入数据能够产生满足要求的输出 对于非法的输入数据能够得出满足规格说明的结果 对于任何测试数据都有满足要求的输出结果。可读性：便于阅读、理解和交流:健壮性：不合法数据也能合理处理时间效率高和存储量低1124/03/201算法效率的度量方法事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法(我们的选择)依据统计方法对算法进行估算。m=f(n),m是语句总的执行次数,n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件1224/03/2016算法时间复杂度(重点)在进行算法分析时，语句的总执行次数T(ri)是关于问题 规模n的函数，进而分析T(n)随n的变化情况并确定 T(n)的数量级。口算法的时间复杂度，也就是算法的时间量度，用“大0记法”记作:T(n)=O(f(n)o由此得到的T(n)的数量级叫“大。阶”。它表示随问题规模n的增大，算法执行时间增长 率和f(n)的增长率相同，称作算法的渐进时间复杂度，简 称时间复杂度。其中f(n)是问题规模n的某个函数。口一般情况下，T(n)增长越慢，算法越优。大0阶的数学定义当n-8时，有f(n)/g(n)=常数,0,则称函数f(n)与g(n)同阶，或者说，(n)与g(n)同一个数量级，记作f(n)=0(g(n)称上式为算法的时间复杂度，或称该算法的时间复杂 度为0(g(n)。其中，n为问题的规模(大小)的量度。若lim(f(n)/g(n)=lim(2n3+3n2+2n+l)/n3)=2 n oo n 8则算法的时间复杂度为0(2)算法空间复杂度算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=0(f(n),其中，n为问题的规模，f(ri)为语句关于n所占存 储空间的函数。我们主要讨论时间复杂度问题。1524/03/2016例题解析【例1】数据元素之间的关系在计算机中有几种表示方法？各有 什么特点？答：四种表示方法（工）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映 数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指 针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操 作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引 表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼 有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的 地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式 称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也 不能折半存取。1624/03/2016例题解析【例2】有下列运行时间函数：(1)Tjn)=1000;(2)T2(n)=n2+1000n;(3)T3(n)=3n3+100n2+n+l;分别写出相应的大。表示的运算时间答：(1)0(1)(2)O(n2)(3)O(n3)1724/03/2016例题解析【例3】已知如下程序段for(i=n;i0;i-)语句 1x=x+l;语句 2)for(j=n;j=i;j-)j 语句 3 y=y+i;j 语句 41语句1执行的频度为语句2执行的频度为语句3执行的频度为语句4执行的频度为里 1=1(1)n+1(2)n(3)n(n+l)/2+1(4)n(n+l)/2【例3】已知如下程序段int i=l;/的频度是工while(i=n)i=i*3;/求该程序的时间复杂度是多少？解：设语句的频度是f(n),贝 J：3人f(n)=n；f(n)2424/03/2016例题解析。构造有1-12元素的二分查找的判定树，并求解下列问题：（1）各元素的查找长度最大是多少？（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？（3）查找第5个元素依次要比较哪些元素？【答】12个元素的判断树如下图所示：（1）最大查找长度是树的深度4。（2 查找长度为1的元素有1个，为 第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元 素有4个，为第1、4、7、11个，查找 长度为4的元素有5个，为第2、5、8、10、12 个。3 查找第五个元素依次比较6,3,4,5o 2524/03/2016例题解析例：设有一组关键字32,75,63,48,94,25,36,18,70,采用哈希函数：H(key)=key MOD H并采用步长为1的线性探测法解决冲突，试在010的 散列地址空间中对该关键字序列构造哈希表。0123456789 10702548369418637532【答】依题意，m=ll,线性探测再散列的下一地址计算公式为：di=H(key),dj+i=(dj+1)MOD 11；j=l,2,其计算过程如下：H(32)=32 MOD 11=10 H(75)=75 MOD 11=9H(63)=63 MOD 11=8 H(48)=48 MOD 11=4H(94)=94 MOD 11=6 H(25)=25 MOD 11=3H(36)=36 MOD 11=3(冲突)H(36)=(3+l)MOD 11=4(仍冲突)H(36)=(4+l)MOD 11=5 H(18)=18 MOD 11=7H(70)=70 MOD 11=4(冲突)H(70)=(4+l)MOD 11=5(仍冲突)H(70)=(10+l)MOD 11=0排序.：.简单排序方法（0 n2 插入排序（稳定排序）选择排序（不稳定排序）冒泡排序（不稳定排序）:先进排序方法（O nlogn 快速排序（不稳定排序）归并排序（稳定排序）堆排序（不稳定排序）各种排序方法的综合比较 一、时间性能1.按平均时间性能来分，有三类排序方法：时间复杂度为o（mog）：快速排序、堆排序和归并排序，其中以 快速排序为最好。时间复杂度为。（层）：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。时间复杂度为。（*砂：基数排序。2.当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到。（）的时间复杂度，快速排序的时间性能蜕化为。（2。3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中 关键字的分布而改变-各种排序方法的综合比较 二、空间性能指的是排序过程中所需的辅助空间大小。1.所有的简单排序方法(包括：直接插入、冒泡和简单选择)和 堆排序的空间复杂度为0(1);2.快速排序为O(log)，为递归程序执行过程中，栈所需的辅助 空间；3.归并排序所需辅助空间最多，其空间复杂度为。()；4.链式基数排序需附设队列首尾指针，则空间复杂度为0(2*4+)三、排序方法的稳定性能1.当对多关键字的记录序列进行LSD方法排序时，必须采用稳 定的排序方法。2.对于不稳定的排序方法，只要能举出一个实例说明即可。3.快速排序、堆排序是不稳定的排序方法。各种内部排序方法的比较排序方法平均时间最坏情况最好情况辅助存储稳定性插入排序0(n2)0(M)0(n)0(1)稳定选择排序0(n2)0(M)0(n2)0(1)稳定冒泡排序0(n2)0(M)0(n)0(1)稳定快速排序O(nlgn)0(M)O(nlgn)O(lgn)不稳定归并排序O(nlgn)O(nlgn)O(nlgn)0(n)稳定堆排序O(nlgn)O(nlgn)O(nlgn)0(1)不稳定基数排序0(d Xn)0(d Xn)0(d Xn)0(n)稳定例题解析:设待排序的排序码序列为12,2,16,30,28,10,16*,20,6,18,试分别写出使用以下排序方法每趟排序后的结果。并说明 做了多少次排序码比较。（1）直接插入排序；（2）起泡排序；【答】（1 直接插入排序初始排列012345 6789排序码比较次数i=112216302810 16、206181i=22、1216302810 16、206181i=321216 302810 16、206181i=42121630|2810 206182i=52121628、3010 206185i=6210、12、28、30206183i=72101216206183i=8210121620、3。6183i=926、12、16、20、1281882610121618、L20、28、3。3124/03/2016例题解析:设待排序的排序码序列为12,2,16,30,28,10,16*,20,6,18,试分别写出使用以下排序方法每趟排序后的结果。并说明 做了多少次排序码比较。(1)直接插入排序；（2）起泡排序；【答】（2）起泡排序初始排优10 12345 6789 排序码比较次数i=012 2 16 30 28 10 20 6 18 9i=12 12 6 16 30 28 10 20 18 8i=22 6 12 10 16 30 28 18 20 7 A A 3224/03/2016例题解析【例】填空题:1.空格串是指，其长度等于【套案】（1）由空格字符（人$0工工值32）所组成的字符串。（2）空格个数2.组成串的数据元素只能是 o【答案】字符【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能 是字符型数据。3.两个字符串后等的充分必要条件是 o【答案】两串的长度相等且两串中对彘叠育字面赢等。4.一个字符串中 称为该串的子串。【答案】任意个造丽字湎赢字序列例题解析【例】设计一个算法，将字符串S的全部字符复制 到字符串t中，不能利用Strcpy函数。答：【算法分析】要实现两个字符串的复制，实质为两个字符数 组之间的复制，在复制时，一个字符一个字符的复制，直到遇 到，0L，0,一同复制过去，之后的字符不复制。【算法源代码】void copy(char s z char t)(int i;for(i=0;si!=,0,;i+)t i=si;ti=si;)链表链式存储结构特点用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai,除存储本身信息外，还需存储其直接后继的信息 链式存储结构的优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移 动数据元素。链式存储结构的缺点：每个结点的指针域需额外占用存储空间。当数据域所占字节不多时,指针域所占存储空间的比重显得很大。链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度O(n)不便于在表尾插入元素：需遍历整个表才能找到位置。35 24/03/2016例题解析【例1】说明在线性表的链式存储结构中，头指针与头 结点之间的根本区别。答：,在线性表的链式存储结构中，头指针指链表的指针，若链 表有头结点则是链表的头结点的指针，头指针具有标识作 用，故常用头指针冠以链表的名字。,头结点是为了操作的统一、方便而设立的，放在第一元素 结点之前，其数据域一般无意义（当然有些情况下也可存 放链表的长度、用做监视哨等等），有头结点后，对在第 一元素结点前插入结点和删除第一结点，其操作与对其它 结点的操作统一了。而且无论链表是否为空，头指针均不 为空。3624/03/2016例题解析【例2】设顺序表va中的数据元素递增有序。试设计一个算法,将x插入到顺序表的适当位置上，以保持该表的有序性。答：void Insert_SqList(SqList va,int x)/*把x插 入递增有序表G中*/int i;if(va.length MAXSIZE)return;for(i=va.length-1;va.elemix&i=0;i-)va.elem i+1=va.elem i;vaelemi+1=x;valength+;/*Insert_SqList*/1.#define MAXSIZE 1002.typedef struct(3.ElemType*elem;4.int length;5.)SqList；3724/03/2016例题解析【例3】设单链表结点指针域为next,试写出删除链 表中指针p所指结点的直接后继的C语言语句。答：q=p-next;p-next=q-next;free(q);3824/03/2016例题解析【例4】设单链表中某指针p所指结点（即p结点）的数据域为data,链指针域为next,请写出在p 结点之前插入s结点的操作。答：设单链表的头结点的头指针为head,且pre=head；while(pre-next!=p)pre=pre-next;s-next=p;pre-next=s;3924/03/2016例题解析【例5】试编写在带头结点的单链表中删除(一个)最小值结点的算法。void delete(Linklist&L)分析单链表中删除最小值结点，为使结点删除后不出现“断链”，应知 道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。故 应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作void delete(LinkedList&L)L是带头结点的单链表p=L-next；p为工作:三针。指向待处理的结点。pre=L；pre指向最小值结点的前驱。q=P；q指向最小值结点，初始假定第一结点是最小值结点。while(p-next!=null)if(p-next-datadata)pre=p；q=p-next；查最小值结点p=p-next；指针后移。pre-next=q-next；/从链表上删除最小值结点40 free(q)；释放最小值结点空间 24/03/2016I/Zr4-vfcrJI _ i _例题解析【例6】一元稀疏多项式以循环单链表按降塞排列，结点有三个域，系数域 coef,指数域exp和指针域next；现对链表求一阶导数，链表的 头指针为ha,头结点的exp域为-1。void derivative(ha)q=ha;pa=ha-next;while(1)if(2)(3);free(pa);pa=(4);else pa-coef(5);pa=(8);)(1)pa!=ha(2)pa-exp=0(3)q-next=pa-next(4)q-next(5)=pa-coef*pa-exp(6)(7)pa(8)pa-next41pa-exp(6);q=(7)_);/或 pa-exp!=l若指数为0,即本项为常数项删常数项取下一元素指数项减工前驱后移，或q-取下一元素24/03/2016例题解析【例7】(1)在一个长度为n的顺序表的第i(linext=rear-next;rear-next=s;rear=s；删除开始结点的操作顺序为Q=rear-next-next;rear-next-next=Q-next;delete q;o第三讲栈和队列（栈和队列及其应用）:栈口限定仅在表尾进行插入和删除的线性表，把这 个表尾称为栈顶。:特点口后进先出（L工F0表）:栈的存储方法口栈的顺序存储顺序栈栈的链式存储链栈44关于栈要求掌握的内容广栈的基本概念：LIFO栈的存储 J栈的应用（了解）顺序栈（熟练掌握）r初始化 取栈顶入栈出栈、判断栈空链栈初始化 取栈顶如fI/I I栈顶（熟练掌握）入栈出栈 判断栈空I a】I*栈底24/03/201队列定义队头。队列的定义队列：线性表(queue)队尾/限定在表的一端插入、另一端删除。特点：先进先出(FIFO结构)。下图是队列的示意图:出队 1 02 入队队头 队尾当队列中没有元素时称为空队列。45表尾称为队尾(rear)表头称为队头(front)插入元素称为入队 删除元素称为出队24/03/2016顺序队列的假溢出问题在顺序队列中，当尾指针已经指向了队列的最后一个 位置即数组上界时，若再有元素入队，就会发生“溢出”O“假溢出”队列的存储空间未满，却发生了溢出。解决“假溢出”的问题有两种可行的方法:(1)、平移元素：把元素平移到队列的首部。效率低。(2)、将新元素插入到第一个位置上，构成循环队列,入队和出队仍按“先进先出”的原则进行。操作效率、空间利用率高。循环队列选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。队空条件：front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=(N+rearfront)%N问1：左图中队列长度L=?5问2：在具有ii个单元的循环队列中，队满时共有多少个元素？n-1个rear4724/03/2016例题解析【例1】一个栈的输入序列是12345,若在入栈 的过程中允许出栈，则栈的输出序列43512可能 实现吗？12345的输出呢？答：4351环可能实现，主要是其中的12顺序不能 实现；1234聃输出可以实现，只需压入一个立即弹 出一个即可。4824/03/2016例题解析【例2】如果一个栈的输入序列为123456,能否得 到435612和135426的出栈序列？答：435612中到了 12顺序不能实现；135426可以实现。思考题：编写算法，利用栈判断所给字符串是否具有中心对称关系（如xyzyx和abcdcba是中心对称的）O 4924/03/2016例题解析【例3】一个栈的输入序列为123若在入栈的过程中允许出 栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解:1入1出，2入2出，3入3出,1入1出，2、3入3、2出，1、2入，2出，3入3出，1、2入，2、1出，3入3出，1、2、3入，3、2、1出，即123；即132；即231；即213；即321；合计有5种可能性。5024/03/2016例题解析【例4】简述顺序存储队列的假溢出的避免方法及队列满和 空的条件。答：设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从。到m-1。设队头指针为front,队尾指 针是rear,约定front指向队头元素的前一位置，rear指向队尾元 素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性 质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于 m-1时，若front不等于-1,则队列中仍有空闲单元，所以队列并不 是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用。至rear-front-1；二是 将队列看成首尾相连，即循环队列（O.m-l。在循环队列下，仍 定义front=rear时为队空，而判断队满则用两种办法，一是用“牺 牲一个单元”，即rear+l=frout（准确记是 rear+1%m=front,m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag,tag等于。情况下，若删除时导致front=rear为队 空；tag=l情况下，若因插入导致front=rear则为队满。51 24/03/2016第四讲特殊矩阵、广义表及其应用内容提要二维数组每一行是一个一维数组，元素间存在序偶 关系；每一列也是一个一维数组，元素间也同样存 在序偶关系。若把每一行看作是一个整体，则行与行之间是线性 关系；若把每一列看作是一个整体，则列与列之间 也是线性关系。内容提要矩阵：是由mXn个数排列成m行（横向）、n列（纵向）所形 成的矩形数表：allai2 ainA=a21。22 a2n Q.ij a iL mla 0 m2 amn(1 /m,l j 5624/03/2016例题解析【例】设有一个22X12的对称矩阵题 为了节约存储，可以只存对角线及对角线以 上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后 者称为下三角矩阵。我们把它们按行存放于一个一维数组E中，称之为对称矩 阵A的压缩存储方式。试问：(1)存放对称矩阵以上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B中从。号位置开始存放，则对称矩阵中的任一元素小：在只 存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。答：(1)数组B共有1+2+3+.+n=(n+1)*n/2个元素。(2)只存下三角部分时，若i j,则数组元素j前面有i-1行(1:L-1,第0 行第0列不算)，第1行有1个元素，第2行有2个元素，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A i j在数组B中的存 放位置为：1+2+.+(i-1)+j=(i-1)*i/2+j若i 0)n为表的长度，当长度为。时称为空表；称非空表的第一个元素dl为表头，其余元素组成的表(d2,dn)称为表尾。注意：表尾可以可以是空表，而表头可以是原子，也可 以是一个表。广义表的表达方式及例子-、1.A=()A是一个空表，其长度为0。2.B=(e)列表B只有一个原子e,其长度为1。3.C=(a,(b,c,d)列表C的长度为2,表头为原子，第二个元素是一个列表(b,c,d)o4.D=(A,B,C)列表D的长度为3,表头也是一个列表A,表尾是列表(A,B),注意：这里引用了已有的列表A、B、C作为该广义表D的元 素。5.E=(a,E)o这是一个递归列表，其元素中有自己。例题解析例:C=(a,(b,c,d),用单链存储结构表示。(b,c,d)这种存储结构的特点是：最上层的表结点数即为广义表的长度；层次清楚；表结点数目多，与广义表中括号对的数目不匹配。例题解析例:C=(a,(b,c,d),用双链存储结构表示。C _-U 1 人(b,c,d)可 a I T-r|J 人0 b-0 c-0 d同层结点链结构的特点是：表结点的数目与广义表的括号对数目一致；写递归算法不方便。第五讲二叉树、树和森林及其应用。二叉树的定义定义：是n n0）个结点的有限集合，由一个根结点以及两棵互 不相交的、分别称为左子树和右子树的二叉树组成。:逻辑结构：一对二（1：2）基本特征：每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒（有序树）。满二叉树完全二叉树二叉树的性质（能证明吗）【性质1】在二叉树的第/层上至多有2，1个结点，21。【性质2】深度为k的二叉树至多有2k.i个结点 k1 o【性质3】对任何一棵二叉树T,如果其叶子数为nO,度为2的结点数为=2,贝！/?0=/?2+1。（叶子数=结点的度为2的结点数+1【性质4】具有个结点的完全二叉树的深度为Llog2nJ+1 或者log2/?+1 。【性质5】n个结点的完全二叉树，结点按层次编号有：i的双亲是，如果i=1时为根（无双亲）；i的左孩子是2i,如果2n,则无左孩子；,i的右孩子是2i+1,如果2i+1n则无右孩子。63 24/03/201 例题解析1.深度为H的完全二叉树至少有_个结点；至多有_个结点；H和结点总数N之间的关系是 o【答案】（1 2H-1（2）2H-1（3）H=Llog2Nj+12.一棵有n个结点的满二叉树有_个度为1的结点，有_个分支（非终端）结点和 个阡子，该满二叉树的灰蔗为【答案】（1 0（2）n-1 /2（3）n+1 /2（4）Llog2nJ+13.对于一个具有n个结点的二叉树，当它为一棵 时，具有最小高度，当它为一棵 时，具有最大高度。【答案】（1）完全二叉树（2）单支树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。4.已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 o【答案】99【解析】在二叉树中，NO=N2+1,所以，有50个叶子结点的二叉树，有49个度为2的 结点。若要使该二叉树的结点数最少，度为工的结点应为0个，即总结点数N=NO+N1+N2=99o 6424/03/2016r 二叉树的存储（一）二叉树存储方法有顺序存储和链式存储。二叉树顺序存储结构完全二叉树：用一组地址连续的存储单元依次自上而下、自左至右存储结点元素，即将编号为i的结点元素 存储在一维数组中下标为i的分量中（不用下标为0存 储单元）。此顺序存储结构仅适用于完全二叉树不是完全二叉树怎么办？O 一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚 结点”，其内容为空。缺点：浪费空间；插入、删除不便6524/03/2016二叉树的存储（二）二叉树链式存储结构O二叉树结点的特点二叉树是非线性结构，适合用链式存储结 构。存储方式一般从根结点开始存储，用二叉链表来表示。（相应地，访问树中结点时也只能从根开始）parentIchild rchildIchild hatarchilSz二叉树结点数据类型定义：typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;J BiTNode/BiTree;结点结构6624/03/201k 二叉树遍历若规定先左后右，则只有前三种情况：DLR-前（根）序遍历，LDR-中（根）序遍历，LRD-后（根）序遍历 根据遍历顺序确定一棵二叉树已知二叉树的前序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的前序序列和后序序列，不能唯一确定一棵二叉树。6724/03/2016例题解析设二叉树bt的一种存储结构如下:1 2 3 4 5lehild 0 0 2 3 7data j h f d brchild 0 0 0 9 465 a07 8 9 108 0 10 1c e g i0 0 0 0其中bt为树根结点指针Jchild、rchild分别为结点的左、右孩 子指针域,在这里使用结点编号作为指针域值,0表示指针域为 空;data为结点的数据域。请完成下列各题：(1)画出二叉树的树形表示；(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列;6824/03/2016例题解析（续）1 Ichild 0 data j rchild 02 3 4 5 60 2 3 7 5h f d b a0 0 9 4 0画出二叉树的树形表示；因 为第6号结点不是任何结点的孩 子结点，该结点必定是根结点，再根据和结点左、右指针域的值 很容易得到该二叉树的树形表示 为7 8 9 108 0 10 1c e g i0 0 0 0 6924/03/2016例题解析（续）1 2 3 4 5 6 7 lehild 0 0 2 3 7 5 8data j h f d b a crchild 0 0 0 9 4 0 0(2)写出按先序、中序和后 序遍历二叉树bt所得到的结点 序列；a.先序序歹lab c e df h g i j 7024/03/2016例题解析(续)lehild data rchild12 30 0 24 5 63 7 5 d b a9 4 0(2)写出按先序、中序和后 序遍历二叉树bt所得到的结点 序列；a.先序序列ab c e df h g i j b中序序列ec bhf dj i ga78 c0 7124/03/2016例题解析(续)Ichild data rchild1 20 0 j h0 03 4 5 2 3 7 f d b0 9 465 a0(2)写出按先序、中序和后序遍 历二叉树bt所得到的结点序列；a先序序列ab c e df h g i j b中序序列ec bhf dj i ga b.后序序列ec hf j i g dba78 c0 7224/03/2016树与森林【例题】从概念上讲，树，森林和二叉树是三种不同的 数据结构，将树，森林转化为二叉树的基本目的是什 么，并指出树和二叉树的主要区别。答：,树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树 的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解 决树和森林中的问题。/树和二叉树的区别有3：一是二叉树的度至多为2,树无此限制；二是 二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指 出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般 不允许为空（个别书上允许为空）。7324/03/2016例题解析【例题】已知一棵二叉树的中序序列和后序序列分别为 GLDHBEIACJFKlLGHDIEBJKFCA（1）给出这棵二叉树；（2）转换为对应的森林。7424/03/2016例题解析【例题】假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDH工，中序序歹！J为BCDAFEH工G o请画出该二叉树，并将其转换为对应的森林。答：按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序 列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个 结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的 根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或 是当前情况下子树的根或是叶子。7524/03/2016二叉树的应用：Huff man树Hu f f man树的应用带权路径计算WPL带权路径长度WPL最小的二叉树称作赫夫曼树口具有相同带权结点的哈夫曼树不惟一满二叉树不一定是哈夫曼树哈夫曼树的结点的度数为。或2,没有度为1的结点。口包含n个叶子结点的哈夫曼树中共有221-：!个结点。76 24/03/201Huffman树的构造过程给定权值集w=234,7,8,9,试构造关于w的的一颗 哈夫曼树，并求其带权路径长度WPL。O。15O9OOO0553b0 0 095 7724/03/2016Huffman树的构造过程：给定权值集W=2,3,478,9,试构造关于w的的一颗 哈夫曼树，并求其带权路径长度WPL。WPL=(2+3)X4+4X3+9X 2+(7+8)X 2=80 7824/03/2016Huff man编码过程【例题】T=(a,2),(b,3),(c,4),(d,7),(e,9)为带权字符 集，试构造关于该字符集的一颗哈夫曼树，求其 加权路径长度WPL、T中每个字符的哈曼夫编码和 哈夫曼编码的平均长度。00T=(a,2),(b,3),C4),(d,7),(e,9)为带权字符集，试构 造关于该字符集的一颗哈夫曼树，求其加权路径 长度WPL、T中每个字符的哈曼夫编码和哈夫曼编 码的平均长度。0T=(a,2),(b,3),C4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。T=(a,2),(b,3),C4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。T=(a,2),(b,3),C4),(d,7),电9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。G 0 0 6 OI95T=(a,2),(b,3),C4),(d,7),电9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。G 0 0 6 OI9516T=(a,2),(b,3),C4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。9165T=(a,2),(b,3),C4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。G G G QI165T=(a,2),(b,3),C4),(d,7),电9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。T=(a,2),(b,3),C4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。25WPL=55a:010 b:Oilc：00 d:10e:11哈夫曼编码的平均长度916p o/i coide0/=3X2+3X3+2X4+2X7+2X9=55关于树的小结双亲表示、孩子表示孩子兄弟，先根遍历后根遍历定义和性质存储结构霍夫曼树顺序结构 存储结构,L链式结构前序遍历 遍历 9724/03/2016例题解析【解析】Prim算法的操作步骤：首先从一个只 有一个顶点的集合开始，通过加入与其中顶点 相关联的最小代价的边来扩充顶点集，直到所 有顶点都在一个集合中。9824/03/2016例题解析【解析】Kruscal算法的操作步骤：首先将n个顶 点看成n个互不连通的分量，从边集中找最小代价 的边，如果落在不同连通分量上，则将其加入最 小生成树，直到所有顶点都在同一连通分量上。(D 第一步第三步 9924/03/2016单源最短路径: