数据结构考点解析课件.ppt

《数据结构考点解析课件.ppt》由会员分享，可在线阅读，更多相关《数据结构考点解析课件.ppt（183页珍藏版）》请在三一办公上搜索。

1、数据结构 考点解析,湖北科技学院计算机学院陈博,数据结构辅导,2,数据结构考点解析,概述第一章知识点第二章知识点第三章知识点第四章知识点第五章知识点第六章知识点,3,考试的要求,考试主要从两个方面进行考查：知识和技能。知识方面从数据结构的结构定义和使用，以及存储表示和操作的实现两个层次，系统地考查：掌握常用的基本数据结构（包括顺序表、链接表、栈与队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构、散列结构）及其不同的实现。,4,2)掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法。技能方面系统地掌握基本数据结构的设计方法;掌握选择结构的方法和算法设计的思考方式及技巧；

2、提高分析问题和解决问题的能力。,5,本章“线性表”的知识点有 5 个：线性表的定义和特点：由数据元素组成，惟一直接前驱与后继。线性表的基本操作：查找、定位、遍历、插入、删除。线性表的存储表示：顺序存储、链表存储。循环链表和双向链表：定义和基本运算。线性表的应用：掌握使用线性表基本操作实现应用算法,第一章知识点解析,6,线性表的定义和特点,问题1.如果一个元素集合中每个元素都有1个且仅有1个直接前驱和1个直接后继，它是线性表吗？解析：答案“否”，该元素集合是一个回路（环）。引伸：循环链表是一个“环”，它符合线性表的定义吗？问题的关键是：线性表是逻辑结构，线性表和非线性表是从逻辑上划分的。而循环链

3、表是存储结构，是线性表的一种特殊的表示，是线性链表的一种扩展。它在形态上有线性的特征，在行为上有线性表的循序访问的特点。,7,问题2.如果一个元素集合有一个元素仅有 1 个直接后继而没有直接前驱，另一个元素仅有 1 个直接前驱而没有直接后继，其他每个元素都仅有 1 个直接前驱和 1 个直接后继，但其中各个元素可能数据类型不同，该元素集合是线性表吗？解析：答案“是”，它符合线性表的定义和特性，只要把元素定义为Union类型即可。因为线性表的定义只规定了元素间的关系及每个表元素是原子类型，并未规定每个表元素的类型必须相同。Union是一种等价类型，它允许不同类型数据共享同一存储空间，可保证每个表元

4、素所占空间相同。,8,线性表的基本操作,问题3.我们可以为线性表定义查找、插入、删除等操作吗？它们如何实现？解析：可以为线性表定义这些操作，也可以在程序中直接使用这些操作。但它们的实现与线性表选用何种存储结构有关。在定义了线性表的存储表示之后，必须为相关操作定义它们的实现代码。具体的线性表实例一定与某一存储表示相联系，因此，要使用相应的基于该存储结构实现的操作。,9,线性表的存储表示,问题4.线性表的顺序存储表示是一维数组吗？解析：答案“否”，应是顺序表，其区别在顺序表中元素是相继连续存放的。而一维数组只能有两个操作“按下标存”“按下标取”，它不一定是相继存放，不适宜存储顺序的、连续的序列元素

5、。问题5.想要以O(1)的时间代价存取第 i 个表元素，线性表应采用顺序表还是单链表？解析：“顺序表”，因为单链表只能顺序地逐个访问，顺序表可以直接访问第 i 个元素。,10,问题6.为了统一空链表和非空链表的操作，简化链表的插入删除操作，需要给链表增加点什么？解析：“增加表头结点”。问题7.在何种场合选用顺序表？链表呢？解析：从时间角度来看，需要经常查看不需经常增删的场合使用顺序表，因它可直接存取，但增删要大量移动存储块；反之，选择链表，因它在增删元素时不需移动存储，修改指针即可，但只能顺序访问，存取速度慢。从空间角度来看，顺序表存储密度（有效存储/总存储）高，空间利用率好；链表存储密度较低

6、，空间利用率差一些。,11,循环链表和双向链表,问题8.想要以O(1)的时间代价把两个链表连接起来可采用何种链表结构？解析：“循环链表”，若设两个循环链表头指针为p和q，用r=p-link;p-link=q-link;q-link=r;即可把这两个连接起来。,p,q,12,问题9.想要判断一个带表头结点的循环链表L是否为空，应采用何种语句？解析：“L-link=L”。空表还需保留一个表头结点，它的下一个结点还是它自己。问题10.想要以O(1)的时间代价访问第 i 个表元素的直接前驱和或直接后继，应采用何种链表结构？解析：“双向链表”。只要事先定位于该表结点，通过该结点的前驱指针和后继指针，直接

7、能够找到该元素的直接前驱或直接后继。,13,例1：在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行()As-next=p-next;p-next=s Bq-next=s;s-next=pCp-next=s-next;s-next=p Dp-next=s;s-next=q,14,例2：假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data,next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来

8、。定义类型LinkList如下：typedef struct node int data;struct node*next,*prior;LinkList;,15,例3：设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。/-线性表的动态分配顺序存储结构-#define maxlen 100/线性表存储空间最大容量typedef structElemType*elem;/存储空间基址 int len;/当前长度SqList;,16,例4：完成以下算法，对单链表实现就地逆置。void LinkList_reverse(Linklist,17,例5：循环链表存储结构示意图如下，请

9、填空：typedef struct LNode/结点类型ElemType data;/数据单元LNode*next;/指针单元*Link,*Position;/定义两个结点指针别名，用于操作函数typedef LNode*LinkList;/简单链表类型,18,循环链表初始化函数InitList的参考代码，一个空的循环链表至少要包含一个头结点。void InitList(LinkList/指针域指向头结点,19,循环链表销毁函数DestroyList的参考代码（循环链表L尾结点的next指针指向L）void DestroyList(LinkList,20,第二章知识点解析,本章“栈、队列与数组

10、”的知识点有 8 个：栈和队列的定义及其特点栈的存储表示及其基本运算的实现队列的存储表示及其基本运算的实现栈的应用队列的应用多维数组特殊矩阵稀疏矩阵,21,栈和队列的定义及其特点,问题1.元素1,2,3,4依次进栈，可能的出栈序列有多少种？队列呢？解析：用catalan函数计算有 8!/4!/4!/5=14种，用队列是1种。因栈有 FILO，队列有 FIFO 特性。问题2.当元素以A,B,C,D,E顺序进栈，D,B,C,E,A 是可能的出栈顺序吗？解析：“否”，因序列的进出栈顺序为 IA IB IC ID OD,当D 出栈后，栈顶为C，不能让B先出来。所以D,B,C,E,A 不是可能的出栈顺序

11、。,22,问题3.可否用两个栈模拟一个队列？反过来呢？解析：“可以”，一个栈把全部数据反过来，另一个栈再把这些数据反过去即可。而队列不能。问题4.栈、队列对线性表加了什么限制？解析：“限制了存取位置”。栈要求只能在表的一端（栈顶）访问、插入和删除，队列要求只能在表的一端（队尾）插入，在另一端（队头）访问和删除，不能在表的中间做上述运算。这决定了在栈和队列上只能顺序访问，不能直接存取，无论采用何种存储表示。这表现了它们优秀的“结构化”特性。,23,栈的存储表示及其基本运算的实现,问题5.当栈空时顺序栈的栈顶指针top=-1，当栈非空时 top 是否指示最后元素加入的位置？解析：“是”，每当新元素

12、进栈时让栈顶指针 top 先加 1，再按 top 指示位置把新元素加入，所以栈非空时栈顶指针总是指示最后加入元素的位置。问题6.顺序栈的进栈、出栈的先决条件是什么？解析：进栈的先决条件是栈未满，栈满再进栈就会产生溢出；出栈的先决条件是栈不空，栈空再退栈可报告操作失败。,24,问题7.当两个栈共享同一个存储空间 Vm 时，可设栈顶指针数组 t2 和栈底指针数组 b2。如果进栈采用两个栈相向前行的方式，则任一栈的栈满条件是什么？解析：“t0+1=t1”。设 0 号栈正向进栈，1 号栈反向进栈，t0 与 t1 碰头即栈满。问题8.链式栈的栈顶指针是指在链头还是链尾？解析：“链头”，链式栈一般采用单链

13、表，栈顶指针即为链头指针。进栈出栈均在链头进行，每次都要修改栈顶指针。链空即栈空，top=NULL。,25,问题9.链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取，这话对吗？解析：“不对”，顺序栈不能直接存取。问题10.理论上链式栈没有栈满问题，但在进栈操作实现时，还要判断一个先决条件，是何条件？解析：每创建新的栈结点时还要判断是否动态分配成功。若不成功则进栈操作失败。StackNode*s=new StackNode;if(s=NULL)cerr“结点存储分配失败！”endl;exit(0);,26,队列的存储表示及其基本运算的实现,问题11.当用牺牲一个单元的方式组织循环队列时，

14、队空和队满的条件是什么？进队、出队的策略是什么？解析：队空条件“Q.front=Q.rear”队满条件“(Q.rear+1)%maxSize=Q.front”进队：Q.rear=(Q.rear+1)%m;Q.elemQ.rear=x;出队：x=Q.elemQ.front;Q.front=(Q.front+1)%m;,27,问题12.当用队头指针 front 和长度 length 组织循环 队列时，队空和队满的条件是什么？进队和出队的策略是什么？（设表长度为m）解析：队空条件“Q.length=0”队满条件“Q.length=maxSize”进队：Q.elem(Q.front+Q.length)

15、%m=x;Q.length+;出队：Q.length-;x=Q.elem(Q.front+Q.length)%m;问题13.链式队列的队头和队尾在链表的什么地方？,28,解析：“链式队列的队头在链头，队尾在链尾”。问题14.链式队列的队空条件是什么？解析：“队空条件Q.front=NULL”，因队头指针为空则说明链表为空。用“Q.front=Q.rear”是不对的。问题15.同时使用多个队列时需采用何种队列结构？如何组织？解析：采用多个链式队列，并设置队头指针数组frn和队尾指针数组ren，分别指示各队列的队头和链尾，其中 n 是队列个数。,29,问题16.链式队列的每个结点是否还可是队列？解

16、析：“可以”，如果每个结点是顺序（循环）队列则是简单的情形；如果每个结点又链接出一个链式队列，则出现“表中套表”，是广义表了。例题17.当一个循环队列已满，如何才能扩充队列长度，使得客户程序能够继续使用这个队列？解析：用指针动态定义存放队列元素的数组，当队列已满时，可创建一个更大的同类型的新数组，把队列元素全部复制到新数组，然后修改队列指针，释放老数组。注意区分 Q.rear Q.front 和Q.front Q.rear 的情形。,30,栈的应用,问题18.在后缀表达式求值过程中用栈存放什么？在中缀表达式求值过程中又用栈存放什么？解析：后缀表达式求值时用栈存放操作数或运算结果，中缀表达式求值

17、时用OPND栈存放操作数或运算结果，用OPTR栈存放操作符。问题19.在递归算法中采用何种结构来存放递归过程每层的局部变量、返回地址和实参副本？解析：“栈”，因递归调用时需为每层分配，在退出时逐层释放，这正是后进先出的机制，可用栈来组织。,31,问题20.为判断表达式中的括号是否配对，可采用何种结构辅助进行判断？解析：“栈”，扫描表达式，每当遇到左括号进栈，遇到右括号再判断栈顶所存括号是否配对，确定是否有错。问题21.在回溯法中采用何种结构来记录回退路径?解析：“栈”，在沿某条路径前进时用栈记下回退路径以便回溯之用，比在路径上各个结点中增加访问标识更方便。例如图的深度优先搜索，采用在每个边结点

18、中增加标志域的非递归算法比用栈的递归算法更复杂。,32,问题22.若进栈序列为1,2,3,4,5,6，出栈序列为2,4,3,6,5,1，问栈容量至少多大？解析：“3”。可实验画图得出。问题23.常用的一种链式栈是基于静态链表的。用一个整数数组 Sn 存放链接指针（游标），设初始时 top=-1，表示栈空，则其进栈、出栈、判栈空等操作如何实现？解析：判栈空：top=-1;设表中第 k 个元素进栈：Sk=top;top=k;设出栈元素是第 k 个元素：k=top;top=Stop;,33,队列的应用,问题24.在逐层处理一个分层结构的数据时，需采用何种辅助结构来组织数据？解析：“队列”，在从队列中

19、退出当前层元素（头）时把相关下层元素进队（尾），在当前层元素处理完后下一层元素已经在队头了。问题25.为实现输入-处理-输出并行操作需建立多个输入缓冲区队列，这些队列是按数组方式组织的还是按链表方式组织的？解析：“按链表方式组织的”，各个队列的增长速度不一，按链表组织可以自由增长。,34,问题26.在操作系统中一种进程调度策略是先来先服务，为此使用了何种辅助结构？解析：“队列”，其特性是先进先出。问题27.在对一个无序单链表进行排序时，可先把链表截出一段段有序的子链表，再对它们做两路归并排序。为此定义队列来辅助排序，此队列的元素的数据类型是什么？解析：“链表结点指针”，存放各有序子链表的头指针

20、。每次从队列中退出两个子链表的头指针，归并后把结果子链表的头指针进队列。如此重复，直到队列中只剩下一个链表指针为止。,35,多维数组,问题28.二维数组可以视为数组元素为一维数组的一维数组，因此二维数组是线性结构吗？解析：“否”，二维数组是一维数组的扩展，每个元素最多有两个直接前驱和两个直接后继，不符合线性表的特性。问题29.二维数组每个元素的存取时间都相同吗？解析：“是”，按照下标确定每个元素存储地址的计算时间都相同，按地址存取任一元素的时间也相同。,36,问题30.数组是逻辑结构还是物理结构？解析：既是逻辑结构也是物理结构。问题31.动态数组用指针来定义。假定数组指针为 a，可否用*a 取

21、出数组元素的值？可否用 a+进到下一数组元素？解析：“可以”，这是C/C+语法文本明确定义的。例如，定义 int a5=1,3,5,7,9;int*data=a;有 int*elem=new int5;while(data!=0)*elem=*data;elem+;data+;for(int k=0;k n;k+)cout elemk;,37,问题32.链表也是动态结构。假定链表指针为*a，可否用*a 取出链表结点的值？可否用 a+进到下一链表结点？解析：“不可以”，因为 a 所指结点有两个域，*a 不能取出结点内的数据，只能用 a-data 取出结点数据。同样不能用 a+进到下一结点，因为

22、a+是进到物理上的下一个结点，而链表中逻辑上的下一个不见得是物理上的下一个，所以要进到逻辑上的下一个，只能用a=a-link。,38,特殊矩阵,问题33.如果用下三角压缩存储对称矩阵，B0存放A00，如何存取Aij？解析：当 ij 时，Aij在B中的位置是i*(i+1)/2+j。当 ij 时，Aij在B中不存在。问题34.两个对称矩阵相加，结果矩阵还对称吗？两个对称矩阵相乘，结果矩阵还对称吗？解析：两个对称矩阵相加的结果矩阵是对称矩阵。相乘的结果矩阵一般不对称，除非二个对称矩阵是相同的。,39,问题35.两个三对角矩阵相加，结果矩阵还是三对角矩阵吗？相乘的情况又如何？解析：相加的结果矩阵还是三

23、对角矩阵。相乘的结果矩阵一般不是。,40,稀疏矩阵,问题36.三对角矩阵是否稀疏矩阵？解析：“否”，三对角矩阵也有大量零元素，但其分布有规律，不符合稀疏矩阵定义。问题37.两个稀疏矩阵相加，结果矩阵还是稀疏矩阵吗？两个稀疏矩阵相乘，结果矩阵又如何？解析：相加的结果矩阵不一定是稀疏矩阵，相乘的结果矩阵肯定不是稀疏矩阵。问题38.用三元组表存储稀疏矩阵的非零元素，是否失去了直接存取的特性？如何改进？,41,解析：是，原稀疏矩阵的元素可通过行列下标直接存取，而三元组表只能顺序存取。改进的方法是采用带行指针的二元组表，可以直接找到某行，且消除了三元组表中冗余的行号。在二元组表内搜索某列元素还需顺序查找

24、，但个数少得多。,42,设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列_。AA,B,C,D,E BB,C,D,E,ACE,A,B,C,D DE,D,C,B,A,43,设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是。A.1 B.2 C.3 D.4,44,稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表 D.散列和十字链表,45,一个稀疏矩阵如下图所示，则对应的三元组线性表为_。,46,由两个

25、栈共享一个向量空间的好处是：（）A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率 C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率,47,第三章知识点解析,本章“树与二叉树”的知识点有 10 个：树与二叉树的定义和性质二叉树的存储结构二叉树的遍历线索二叉树树与森林二叉树的应用（二叉排序树、平衡二叉树、并查集、Huffman树、堆）,48,树与二叉树的定义和性质,问题1.二叉树是树吗？解析：“否”，树的定义是从图来的，要求结点至少有1个，二叉树则可以是空树；另外二叉树必为有序树，树可有序，也可无序。问题2.树的叶结点无子女，是否可称它无子树？解析：“是

26、”，树的定义是递归的，递归结束于只有一个结点的树。问题3.二叉树的叶结点无子女，它是否无子树？解析：“否”，二叉树的定义是递归的，递归到空树为止，所以结点无子女，应称它子树为空。,49,问题4.树和二叉树的高度与深度如何理解？解析：树的高度与深度的值相等；但树中某个结点的高度与深度的值可能不同：深度是从上向下计算的，高度是从下向上计算的。问题5.一棵二叉树有1024个结点，其中465个是叶结点，那么树中度为2和度为1的结点各有多少？解析：由n0=n2+1的性质，度为 2 的结点有465-1=464个，度为 1 的结点有1024-465-464=95个。问题6.计算深度的公式 log2(n+1)

27、是针对何种二叉树的？解析：针对完全二叉树。但对理想平衡树也可用。,50,问题7.二叉树求深度的公式log2(n+1)与log2n+1有何不同？解析：推导有些差异，都可计算二叉树深度，只不过后者对于n=0不适用。问题8.完全二叉树有何用处？解析：后续讨论可知，堆、胜者树、败者树等都按完全二叉树组织。何况完全二叉树最省存储。问题9.n0=n2+1公式有何用途？解析：对于完全二叉树最有用。例如组织对抗赛可用胜者树，已知选手有n个人，取n0=n,直接可求得比赛场次n2=n0-1，是否有人轮空。,51,二叉树的存储,问题10.顺序存储适用于何种二叉树？解析：适用于完全二叉树，可充分利用存储，并可方便地找

28、到某结点的双亲、兄弟和子女。问题11.完全二叉树的结点从1开始编号和从0开始编号有何不同？解析：C/C+与Pascal不同，数组下标从 0 开始，完全二叉树从 0 开始编号是合理的，这时某结点i 的双亲是(i-1)/2，左子女是2i+1，右子女是2i+2。完全二叉树结点从 1 开始编号是传承了Pascal的做法。,52,问题12.通常使用二叉链表存储二叉树，为何还选用三叉链表？解析：使用二叉链表找某结点的左子女和右子女比较方便，找双亲比较麻烦，三叉链表每个结点增设一个父指针，可方便地找双亲。当然，如果结点数 n 很大，不如使用二叉链表加一个栈，用栈也可记忆结点的双亲，所需空间仅O(log2n)

29、。问题13.使用二叉链表存储有n个结点的二叉树，空的指针域有多少？解析：n 个结点的二叉树有2n个指针域，其中 n-1 个指针域被使用，有 n+1 个空指针域。,53,二叉树的遍历,问题14.已知二叉树的前序序列abdcef，中序序列dbaecf，其后序序列是什么？解析：由二叉树的前序序列和中序序列可唯一确定此二叉树，根据问题要求构造出的二叉树如右图，后序序列为dbefca。问题15.前序序列与中序序列相同的是什么二叉树?解析：要求VLR=LVR，应是左子树均为空的单支树，或空树。,54,问题16.前序序列与后序序列相同的是什么二叉树?解析：要求VLR=LRV，应是只有根结点的二叉树或空树。问

30、题17.前序序列与层次序序列相同的又是什么二叉树?解析：应是右子树均为空的单支树，或左子树均为空的单支树，或空树。问题18.后序序列与层次序序列相同的是何二叉树?解析：只有根结点的二叉树或空树。,55,问题19.前序序列与中序序列正好相反的是什么二叉树？解析：要求VLR与LVR相反，即，当右子树均为空时，或空树时满足要求。问题20.前序序列与后序序列正好相反的是什么二叉树？解析：要求VLR与LRV相反，即，当右子树都空时,或左子树都空时,或空树时满足要求。,56,问题21.一棵二叉树的前序序列的最后一个结点是否是它中序序列的最后一个结点？解析：“不一定是”，右图即反例，二叉树前序序列abdce

31、，中序序列dbaec。问题22.一棵二叉树的前序序列的最后一个结点是否是它层次序序列的最后一个结点？解析：“是”。问题23.一棵有 n 个结点的二叉树的前序序列固定，可能的不同二叉树有多少种？解析：用catalan函数求：,57,问题24.二叉树的前序、中序、后序遍历所走的路线都相同，只是访问时机不同，这种说法对吗？解析：“对”，从给出的二叉树的前序、中序、后序的递归遍历算法就可以清楚看到。问题25.二叉树的层次序遍历是按二叉树层次进行逐层访问，其遍历算法需要使用何种辅助结构？解析：“队列”，使用队列，在逐层访问过程中一旦当前层次的结点出队进行处理，就需把它下一层的结点进队列。当当前层的结点全

32、部退出队列并处理完后下一层结点已经在队头了。,58,线索二叉树,问题26.如何构造一棵中序线索二叉树？解析：通过中序遍历，把二叉树改造为中序线索二叉树void crt-inthtree(ThreadNode*p,ThreadNode*,59,pre=p;crt-inthtree(p-right,pre);在主程序中pre=NULL;crt-inthtree(root,pre);pre-right=NULL;pre-rtag=1;问题27.如何在一棵中序线索二叉树中寻找某结点p为根的子树上的中序第一个结点？解析：沿结点p的左子树链一直走下去，直到遇到其左指针为左线索的结点为止，该结点即所求。,6

33、0,ThreadNode*inFirst(ThreadNode*p)ThreadNode*q=p;while(q,61,return q;问题29.如何在一棵中序线索二叉树中寻找某结点p的中序下的后继？解析：若结点p有右线索，则其右线索所指结点即为其中序后继；若无右线索，则其右子树中中序第一个结点即为它的中序后继。ThreadNode*inNext(ThreadNode*p)ThreadNode*q=p-right;if(q,62,问题30.如何在一棵中序线索二叉树中寻找某结点 p的中序下的前驱？解析：镜像情况。若结点 p 有左线索，则其左线索所指结点即为其中序前驱；若无左线索，则其左子树中中

34、序最后一个结点即为它的中序前驱。ThreadNode*inPrior(ThreadNode*p)ThreadNode*q=p-left;if(q,63,问题31.如何在一棵中序线索二叉树中寻找某结点p的前序下的后继？解析：右图二叉树前序遍历的结果是abdgcef。分析这个事例可知：a 有左子女 b，a 的前序后继为 b；d 无左子女但有右子女 g，d 的前序后继是 g；g 既无左子女又无右子女，g 的前序后继为 c,c 可从 g 沿右线索链到 a，a 的右子女即为g 的前序后继。,64,ThreadNode*preNext(ThreadNode*p)ThreadNode*q;if(!p-lta

35、g)q=p-left;else if(!p-rtag)q=p-right;else q=p;while(q,65,问题32.如何在一棵中序线索二叉树中寻找某结点p的前序下的前驱？解析：右图二叉树前序遍历的结果是abdgcef。为寻找 p 的前驱，需找 p 的双亲 q，确定双亲原则:若 p 是 q 的左子女，则 q 是 p右子树中序最后一个结点的右线索；若 p 是 q 的右子女，则 q 是 p 左子树中序第一个结点的左线索。ThreadNode*inParent(ThreadNode*p)if(p),66,ThreadNode*q=inLast(p-right);if(q)return q-ri

36、ght;else q=inFirst(p-left);if(q)return q-left;return NULL;找到 b 的双亲 a 后，判断:若 b 是 a 的左子女，则 b 的前序前驱是 a；否则若 c 是 a 的右子女，则c 的前序前驱是,67,a（a 的左子树空）或 a 的左子树（非空）前序最后一个结点。ThreadNode*prePrior(ThreadNode*p)ThreadNode*q=inParent(p);if(p=q-left)return q;/p是q的左子女if(!q-left)return q;/p是q的右子女 while(!q-ltag|!q-rtag)whi

37、le(!q-rtag)q=q-right;while(!q-ltag)q=q-left;return q;,68,问题33.如何构造一棵前序线索二叉树？解析：类似于构造中序线索二叉树，可通过前序遍历，把二叉树改造为前序线索二叉树：void crt-prethtree(ThreadNode*p,ThreadNode*,69,crt-prethtree(p-right,pre);在主程序中pre=NULL;crt-prethtree(root,pre);pre-right=NULL;pre-rtag=1;问题34.如何在一棵前序线索二叉树中寻找某结点p为根的子树上的前序第一个结点？解析：以结点p为

38、根的子树上前序的第一个结点就是它自己。,70,ThreadNode*preFirst(ThreadNode*p)return p;问题35.如何在一棵前序线索二叉树中寻找某结点p的前序最后一个结点？解析：若结点p有右子树，则其前序最后一个结点一定是其右子树上前序最后一个结点；若其右子树为空，则其前序最后一个结点一定是其左子树上前序最后一个结点；若其左、右子树都为空，则其前序最后一个结点即为它自己。ThreadNode*preLast(ThreadNode*p),71,if(p)if(!p-rtag)return preLast(p-right);else if(!p-ltag)return p

39、reLast(p-left);else return p;问题36.如何在一棵前序线索二叉树中寻找某结点p的前序下的后继？解析：若结点p有右线索，则其前序后继即为右线索所指结点；否则若结点p有左子女，则前序后继即为其左子女指针所指结点,否则为,72,其右子女指针所指结点。ThreadNode*preNext(ThreadNode*p)if(p)if(!p-ltag)return p-left;else return p-right;问题37.如何在一棵前序线索二叉树中寻找某结点p的前序下的前驱？解析：若结点p有左线索，则其前序下的前驱即其左线索所指结点；否则需要找到它的双亲q，若p是q的左子女

40、，则其前序下的前驱即为q，否则到,73,q的左子树中寻找其前序下最后一个结点，它就是结点p前序下的前驱。ThreadNode*prePrior(ThreadNode*p)if(p)if(p-ltag)return p-left;else ThreadNode*q=preParent(p);if(q-left=p)return q;else return preLast(q-left);如何找双亲留给大家自己考虑。,74,树与森林,问题38.在一棵 m 叉树，设根在第1层，并从0开始自上向下分层给各个结点编号。问(1)第 i 层最多有多少结点？(2)高度为 h 的 m 叉树最多有多少结点？(3)

41、编号为 k 的结点的父结点编号是多少？(4)编号为 k 的结点的第1个子结点编号是多少？(5)编号为 k 的结点在第几层？解析：(1)第 i 层最多有mi-1个结点。(2)高度为 h 的m叉树最多有(mh-1)/(m-1)个结点。(3)当 k=0时结点 k 是根，没有父结点；当 k 0 时结点 k,75,的父结点是(k-1)/m。(4)结点 k 的第 1 个子女是k*m+1。(5)设结点 k 在第 i 层，到第 i 层为止的m叉树最多有(mi-1)/(m-1)个结点，第 i 层最后一个结点编号k=(mi-1)/(m-1)-1，由此可得层次号 i=logm(k+1)*(m-1)+1)。问题39.

42、使用树的双亲表示，寻找某结点 i 的双亲、所有子女、兄弟的时间复杂性是多少？,76,解析：使用树的双亲表示，寻找某结点 i 的双亲的时间复杂度为O(1)，而寻找其他要看结点存放的顺序。如果所有结点按层次序存放，寻找所有兄弟的时间为O(1)，寻找所有子女的时间为O(n);如果所有结点按先根序存放，寻找所有子女和兄弟的时间都是O(n)，其中 n 是结点个数。问题40.树的先根次序序列的特性是什么？解析：在树的先根次序序列中，第一个元素一定是树的根，如果树的结点个数大于1，它后面紧跟的一定是第一棵子树的根，.。子树又是树，同样满足上述特性。,77,问题41.n 个结点的树有多少种？解析：可通过树的二

43、叉树表示来估计。在树的二叉树表示中，根的右指针一定是空的，因此，估计有多少种形态看根的左子树的n-1个结点能构成多少种二叉树。根据在二叉树中的分析可知，它服从catalan函数，等于问题42.森林中树T1、T2、T3的结点数为m1、m2、m3，在该森林的二叉树表示中，根的左子树和右子树各有多少结点？,二叉树表示,78,解析：在森林的二叉树表示中根是T1的根，其左子树是T1的根的子树森林，有m1-1个结点，其右子树是除T1外其他树T2、T3构成的森林，有m2+m3个结点。问题43.在一个有 n 个结点的森林的二叉树表示中，左指针为空的结点有 m 个，那么右指针为空的结点有多少个？解析：左指针为空

44、的都是森林中各棵树的叶结点，非叶结点有n-m个。每个非叶结点的子女-兄弟链都有一个右指针为空的结点，加上根结点的右指针为空，故右指针为空的结点有n-m+1个。,79,二叉排序树,问题44.一棵有 n 个结点的二叉排序树有多少种不同形态？解析：二叉排序树的中序排列一定，不同的前序序列得到不同的二叉排序树，不同二叉排序树的总数服从catalan函数问题45.若想把二叉排序树上所有结点的数据从小到大排列，采用何种遍历算法？从大到小排列，又采用何种算法？,80,解析：采用中序遍历算法：若想得到从小到大排列的遍历结果，采用LVR的方式，若想得到从大到小的遍历结果，采用RVL的方式。问题46.每次插入一个

45、新元素到二叉排序树中应插入到什么地方？树的高度最大是多少？解析：在插入之前应先调用查找算法从根开始查找插入位置，如果查找成功，说明树中已有要插入的元素，新元素不插入；如果查找失败，则把新结点插入到查找失败的位置。注意，新结点将作为叶结点插入。二叉排序树是向下增长的，最高是单支树情形，若树结点数为n，最大高度为n。,81,问题47.衡量一棵二叉排序树的查找性能要计算其查找成功的平均查找长度和查找不成功的平均查找长度，此时可借助的辅助结构是什么？解析：扩充二叉树（或称判定树）。内结点代表二叉排序树原有的数据，查找成功时查找指针停留在内结点上；外结点代表二叉排序树原来没有的数据，查找失败时查找指针走

46、到外结点。,ab,de,gh,j,l0,qr,tx,z,82,问题48.对下图所示二叉排序树，查找成功的平均查找长度和查找不成功的平均查找长度是多少？解析：查找成功的平均查找长度为查找不成功的平均查找长度为扩充二叉树的内结点的度为2,外结点的度为0。n0=n2+1,83,问题49.对一棵二叉排序树做中序遍历，再基于得到的中序序列重新构造二叉排序树，这两棵二叉排序树是否相同？解析：一般不相同。对一棵二叉排序树做中序遍历得到一个有序的序列，再顺序用序列中的数据构造二叉排序树，得到一棵单支树，每个结点的左子树均为空。,中序遍历,h,k,p,s,y,顺序插入,84,平衡二叉树,问题50.二叉树、二叉排

47、序树和平衡二叉树之间是何关系？解析：二叉排序树是二叉树的特殊情形，平衡二叉树又是二叉排序树的特殊情形。平衡二叉树是高度平衡的二叉排序树。问题51.有 n 个结点的平衡二叉树的最小高度和最大高度是多少？解析：让平衡二叉树每层结点达到最大数目，就得到它的最小高度：n2h-1 hlog2(n+1)；若让根的左右子树的结点个数达到最少，可得,85,最大高度。设高度为h的平衡二叉树的最少结点数为Nh，则有 N0=0,N1=1,Nh=Nh-1+Nh-2+1,h1。由此推出 N2=2,N3=4,N4=7,N5=12,对照斐波那契数 F0=0,F1=1,F2=1,F3=2,F4=3,F5=5,F6=8,F7=

48、13,有Nh=Fh+2-1。另外，斐波那契数满足渐进公式：由此可得,86,两边取对数 由换底公式 logX=log2X/log2 及 log2=0.694 和 可得 h 1.44*log2(Nh+1)0.33 1.44*log2(n+1)此即平衡二叉树的最大高度。问题52.在高度为 h 的平衡二叉树中离根最近的叶结点在第几层？解析：计算平衡二叉树离根最近的叶结点所在层次的方法与推导高度为 h 的平衡二叉树最少结点,87,个数的过程类似。设高度为 h 的平衡二叉树的离根最近的叶结点所在层次为Lh，则有L1=1,L2=2,Lh=minLh-1,Lh-2+1=Lh-2+1,h2直接计算 Lh=h/2

49、+1.,88,问题53.Huffman树是一棵扩充二叉树，外结点（叶结点）有 n 个，那么总共有多少结点？解析：总共有 2n-1 个结点，因它只有度为 0 和度为 2 的结点，由n0=n2+1，当n0=n时，n0+n2=n+n-1=2n-1。问题54.在构造Huffman树的过程中，每次从森林中选根的关键字值最小和次小的两棵树合并。在合并时是最小的做左子树还是次小的做左子树？解析：都可以。可参考算法的实现代码，但手工构造时没有限制。,Huffman树,89,问题55.用Huffman树构造最佳判定树，内、外结点各起什么作用？带权路径长度表示什么意思？解析：内结点是比较过程中的中间结果，外结点是

50、比较的最终结果。带权路径长度表明可能的比较次数，或总比较次数的期望值。问题56.用Huffman树构造不等长的Huffman编码，一段报文的总（二进制）编码数用什么衡量？解析：首先根据报文中各字符出现的频度和每个字符的Huffman编码，计算带权路径长度，它就是该报文的总（二进制）编码数，也叫做总编码长度。,90,问题57.并查集（mfset or UFSets or disjoint）主要用在什么地方？解析：一是判断和构造等价类，二是判断和构造图的连通分量。问题58.并查集有哪几种操作？解析：并查集以双亲表示为其存储结构，操作有:(1)Find(S,x),寻找 x 所在子树的根；(2)Uni