计算机专业考研必备殷仁昆数据结构考研要点解析（清华大学殷仁昆教授数据结构辅导班讲义）

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

2、结构的方法和算法设计的思考方式及技巧； 提高分析问题和解决问题的能力。,5,复习的纲领,数据结构课程是计算机专业的专业基础课程，为业界做系统开发提供了不可或缺的技术和知识，是计算机专业考研的重头科目。 数据结构课程复习有几点重要的体会提供给大家参考。 注重概念 抓住特点 学会算法 拓展应用,6,注重概念 从考研情况分析，试题涉及的内容都很基本，没有很深很难的内容，所以要重视概念的复习： 牢记定义。结构定义有规范写出的，有言外隐藏的和引伸的概念。 注意传承。某些结构与其他结构间有传承关系，有变种关系。 区分层次。分清逻辑的和物理的结构，以及它们之间的关系。 挖掘细节。细节可提供更多解题的知识。,

3、7,抓住特点 每种结构有它的特点和用途，这对于在解题中应使用哪种结构 (who)，在何时 (when)，何种场合(where)使用，以及如何 (how) 使用有重要作用。 理解结构的行为特征。明确每种结构的行为特征，例如栈是先进后出，队列是先进先出的，可帮助在解题时作出选择。 理解结构的应用背景。知道每种结构常在什么场合做什么用，可适时作出适当选择。 理解结构的声明方式。在适当时机合理地定义它们，可减少算法逻辑的混乱。,8,学会算法 包括结构必要操作（初始化、建立、销毁、遍历、插入、删除）的实现和常用算法（查找、排序）、算法设计（迭代、递归、分治、回溯）的设计与分析。 基本数据结构的实现方式。

4、主要是数据结构的存储方式定义和相应操作的程序实现。 常用算法的设计。包括设计的三阶段（基本思想、算法框架、程序实现）。 算法的简单分析。掌握时间复杂性的分析技能和附加存储空间的计算。,9,拓展应用 每种结构都有许多应用场合，有不同应用目的和应用方式。每种算法也可变通以适用于不同的问题求解。 明确问题求解的步骤。掌握问题求解的三阶段：分析(弄懂题意)、设计(考虑解决方案)、实现(算法设计与分析)。 坚持算法设计与分析的步骤。算法设计三阶段（基本思想、算法框架、程序实现）。 结构和算法的不同应用。这是最繁杂、范围最广的部分。通过多练习达到熟练应用。,10,复习的范围,根据2009年考试分析和历年考

5、试经验，可以对今后考试作一个简单评估： 单项选择题覆盖了考试大纲涉及的所有各章，主要考查对各个数据结构的定义和特点的理解，以及相应延伸的概念。 综合应用题分为两个部分：算法分析题和算法设计题（编程题），主要考查分析问题和解决问题的能力。算法分析题的重点在图、查找、排序部分，算法设计题的重点在线性表、树与二叉树、查找和排序部分。,11,为在有限的时间内复习好这门课程，应当注意以下几点: 注意复习用 C / C+ / Java 语言编写小程序时的语法规则和方法，为算法分析和算法设计题的求解打下基础。 函数定义和参数使用。算法一般以函数形式给出，函数编写需要注意的问题包括函数类型，函数参数传递，函数

6、返回值类型等，以及传值参数和引用参数在使用上的区别。 函数中局部变量的作用域。特别注意在函数中对局部变量的任何改变，在函数外不能使用。,12,算法设计所用数据结构的自定义。算法设计时不能忽视所用数据结构的声明。2009 年考试42 题有关链表的题，在答案中不写链表结点定义是扣了分的。 CC+ 中的动态存储分配和回收方式。涉及链表结构的地方都可能有动态存储分配和回收操作。要掌握正确使用相关语句的方法。 在CC+ 中输入输出文件的定义和使用。特别注意正确使用文件的打开、关闭、读入、写出操作的使用。 在复习数据结构时，要注意知识体系。,13,数据结构课程中的知识本身具有良好的结构性，有些结构面向应用

7、，有些结构面向实现。在复习时要注意这两个层次以及它们之间的联系。 注意循序渐进 在复习数据结构时，首先需要复习数据结构的定义和特点，数据结构的使用范围，再复习各种操作的实现。 在阅读算法之前，要先弄清其基本设计思想、基本步骤，并通过事例学习了解每个算法的处理流程以加深理解，最后再阅读程序代码。,14,注意比较 在复习中应当注意从“横向”和“纵向”进行对比以加深理解。 纵向对比将一种结构与它的各种不同的实现加以比较，理解不同实现方式的优点和问题。如二叉树的顺序和链表实现。 横向对比是 对属于同一类逻辑结构的不同数据结构（如线性表、栈、队列）加以比较， 对具有相同功能的不同算法进行比较 等，了解数

8、据结构与算法实现间的关系。,15,注意练习 只看书不做题，不能真正学会有关知识，不能达到技能培养的目的。 做题是自我检查的重要手段。 在做算法设计类型的习题时，应考虑数据结构的定义。 提高算法设计的能力。 编写算法的题可能是学生比较棘手的问题，特别是在考试这样一个氛围，时间又短促，想编出一个好算法不太容易。,16,一个建议是 首先仔细阅读试题题目，了解它到底要你干什么。 然后用一个简单的例子走一下，总结每一步向下走可用什么语句实现。 再做归纳，整理出处理流程。 按照结构化程序设计的方法，搭建框架，再根据例子填入细节。 在设计一个算法时，要考虑问题解决方案的多样性、算法的适用性、问题对算法选择的

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

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

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

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

13、序表存储密度（有效存储/总存储）高，空间利用率好；链表存储密度较低，空间利用率差一些。,23,循环链表和双向链表,问题8. 想要以O(1)的时间代价把两个链表连接起来可采用何种链表结构？ 解析：“循环链表”，若设两个循环链表头指针为p和q，用r = p-link;p-link = q-link; q-link = r; 即可把这两个连接起来。,p,q,24,问题9. 想要判断一个带表头结点的循环链表L是否为空，应采用何种语句？ 解析： “L-link=L”。空表还需保留一个表头结点，它的下一个结点还是它自己。 问题10. 想要以O(1)的时间代价访问第 i 个表元素的直接前驱和或直接后继，应采

14、用何种链表结构？ 解析：“双向链表”。只要事先定位于该表结点，通过该结点的前驱指针和后继指针，直接能够找到该元素的直接前驱或直接后继。,25,第二章知识点解析,本章“栈、队列与数组”的知识点有 8 个： 栈和队列的定义及其特点 栈的存储表示及其基本运算的实现 队列的存储表示及其基本运算的实现 栈的应用 队列的应用 多维数组 特殊矩阵 稀疏矩阵,26,栈和队列的定义及其特点,问题1. 元素1, 2, 3, 4依次进栈，可能的出栈序列有多少种？队列呢？ 解析：用catalan函数计算有 8!/4!/4!/5=14种，用队列是1种。因栈有 FILO，队列有 FIFO 特性。 问题2. 当元素以A,

15、B, C, D, E顺序进栈，D, B, C, E, A 是可能的出栈顺序吗？ 解析：“否”，因序列的进出栈顺序为 IA IB IC ID OD, 当D 出栈后，栈顶为C，不能让B先出来。所以D, B, C, E, A 不是可能的出栈顺序。,27,问题3. 可否用两个栈模拟一个队列？反过来呢？ 解析：“可以”，一个栈把全部数据反过来，另一个栈再把这些数据反过去即可。而队列不能。 问题4. 栈、队列对线性表加了什么限制？ 解析：“限制了存取位置”。栈要求只能在表的一端（栈顶）访问、插入和删除，队列要求只能在表的一端（队尾）插入，在另一端（队头）访问和删除，不能在表的中间做上述运算。这决定了在栈和

16、队列上只能顺序访问，不能直接存取，无论采用何种存储表示。这表现了它们优秀的“结构化”特性。,28,栈的存储表示及其基本运算的实现,问题5. 当栈空时顺序栈的栈顶指针top = -1，当栈非空时 top 是否指示最后元素加入的位置？ 解析：“是”，每当新元素进栈时让栈顶指针 top 先加 1，再按 top 指示位置把新元素加入，所以栈非空时栈顶指针总是指示最后加入元素的位置。 问题6. 顺序栈的进栈、出栈的先决条件是什么？ 解析：进栈的先决条件是栈未满，栈满再进栈就会产生溢出；出栈的先决条件是栈不空，栈空再退栈可报告操作失败。,29,问题7. 当两个栈共享同一个存储空间 Vm 时，可设栈顶指针数

17、组 t2 和栈底指针数组 b2。如果进栈采用两个栈相向前行的方式，则任一栈的栈满条件是什么？ 解析：“t0+1 = t1”。设 0 号栈正向进栈，1 号栈反向进栈，t0 与 t1 碰头即栈满。 问题8. 链式栈的栈顶指针是指在链头还是链尾？ 解析：“链头”，链式栈一般采用单链表，栈顶指针即为链头指针。进栈出栈均在链头进行，每次都要修改栈顶指针。链空即栈空，top = NULL。,30,问题9. 链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取，这话对吗？ 解析： “不对”，顺序栈不能直接存取。 问题10. 理论上链式栈没有栈满问题，但在进栈操作实现时，还要判断一个先决条件，是何条件？

18、解析：每创建新的栈结点时还要判断是否动态分配成功。若不成功则进栈操作失败。 StackNode *s = new StackNode; if ( s = NULL ) cerr “结点存储分配失败！” endl; exit (0); ,31,队列的存储表示及其基本运算的实现,问题11. 当用牺牲一个单元的方式组织循环队列时，队空和队满的条件是什么？进队、出队的策略是什么？ 解析：队空条件 “Q.front=Q.rear” 队满条件 “(Q.rear+1) % maxSize = Q.front” 进队：Q.rear = (Q.rear+1) % m; Q.elemQ.rear = x; 出队：

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

20、“链式队列的队头在链头，队尾在链尾”。 问题14. 链式队列的队空条件是什么？ 解析： “队空条件Q.front = NULL”，因队头指针为空则说明链表为空。用“Q.front = Q.rear”是不对的。 问题15. 同时使用多个队列时需采用何种队列结构？如何组织？ 解析：采用多个链式队列，并设置队头指针数组frn和队尾指针数组ren，分别指示各队列的队头和链尾，其中 n 是队列个数。,34,问题16. 链式队列的每个结点是否还可是队列？ 解析： “可以”，如果每个结点是顺序（循环）队列则是简单的情形；如果每个结点又链接出一个链式队列，则出现“表中套表”，是广义表了。 例题17. 当一个循

21、环队列已满，如何才能扩充队列长度，使得客户程序能够继续使用这个队列？ 解析：用指针动态定义存放队列元素的数组，当队列已满时，可创建一个更大的同类型的新数组，把队列元素全部复制到新数组，然后修改队列指针，释放老数组。注意区分 Q.rear Q.front 和Q.front Q.rear 的情形。,35,栈的应用,问题18. 在后缀表达式求值过程中用栈存放什么？在中缀表达式求值过程中又用栈存放什么？ 解析：后缀表达式求值时用栈存放操作数或运算结果，中缀表达式求值时用OPND栈存放操作数或运算结果，用OPTR栈存放操作符。 问题19. 在递归算法中采用何种结构来存放递归过程每层的局部变量、返回地址和

22、实参副本？ 解析：“栈”，因递归调用时需为每层分配，在退出时逐层释放，这正是后进先出的机制，可用栈来组织。,36,问题20. 为判断表达式中的括号是否配对，可采用何种结构辅助进行判断？ 解析：“栈”，扫描表达式，每当遇到左括号进栈，遇到右括号再判断栈顶所存括号是否配对，确定是否有错。 问题21. 在回溯法中采用何种结构来记录回退路径? 解析：“栈”，在沿某条路径前进时用栈记下回退路径以便回溯之用，比在路径上各个结点中增加访问标识更方便。例如图的深度优先搜索，采用在每个边结点中增加标志域的非递归算法比用栈的递归算法更复杂。,37,问题22. 若进栈序列为1, 2, 3, 4, 5, 6，出栈序列

23、为2, 4, 3, 6, 5, 1，问栈容量至少多大？ 解析：“3”。可实验画图得出。 问题23. 常用的一种链式栈是基于静态链表的。用一个整数数组 Sn 存放链接指针（游标），设初始时 top = -1，表示栈空，则其进栈、出栈、判栈空等操作如何实现？ 解析：判栈空：top = -1; 设表中第 k 个元素进栈：Sk = top; top = k; 设出栈元素是第 k 个元素：k = top; top = Stop;,38,队列的应用,问题24. 在逐层处理一个分层结构的数据时，需采用何种辅助结构来组织数据？ 解析：“队列”，在从队列中退出当前层元素（头）时把相关下层元素进队（尾），在当前层

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

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

26、可否用 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 link。,43,特殊矩阵,问题33. 如果用下三角压缩存储对称矩阵，B0存放A00，如何存取Aij？ 解析：当 ij 时，Aij在B中的位置是i*(i+1)/2+ +j。当 ij 时，Aij在B中不存在。 问题34. 两

27、个对称矩阵相加，结果矩阵还对称吗？两个对称矩阵相乘，结果矩阵还对称吗？ 解析：两个对称矩阵相加的结果矩阵是对称矩阵。相乘的结果矩阵一般不对称，除非二个对称矩阵是相同的。,44,问题35. 两个三对角矩阵相加，结果矩阵还是三对角矩阵吗？相乘的情况又如何？ 解析：相加的结果矩阵还是三对角矩阵。相乘的结果矩阵一般不是。,45,稀疏矩阵,问题36. 三对角矩阵是否稀疏矩阵？ 解析：“否”，三对角矩阵也有大量零元素，但其分布有规律，不符合稀疏矩阵定义。 问题37. 两个稀疏矩阵相加，结果矩阵还是稀疏矩阵吗？两个稀疏矩阵相乘，结果矩阵又如何？ 解析：相加的结果矩阵不一定是稀疏矩阵，相乘的结果矩阵肯定不是稀

28、疏矩阵。 问题38. 用三元组表存储稀疏矩阵的非零元素，是否失去了直接存取的特性？如何改进？,46,解析：是，原稀疏矩阵的元素可通过行列下标直接存取，而三元组表只能顺序存取。改进的方法是采用带行指针的二元组表，可以直接找到某行，且消除了三元组表中冗余的行号。在二元组表内搜索某列元素还需顺序查找，但个数少得多。,47,第三章知识点解析,本章“树与二叉树”的知识点有 10 个： 树与二叉树的定义和性质 二叉树的存储结构 二叉树的遍历 线索二叉树 树与森林 二叉树的应用（二叉排序树、平衡二叉树、并查集、Huffman树、堆）,48,树与二叉树的定义和性质,问题1. 二叉树是树吗？ 解析：“否”，树的

29、定义是从图来的，要求结点至少有1个，二叉树则可以是空树；另外二叉树必为有序树，树可有序，也可无序。 问题2. 树的叶结点无子女，是否可称它无子树？ 解析：“是”，树的定义是递归的，递归结束于只有一个结点的树。 问题3. 二叉树的叶结点无子女，它是否无子树？ 解析：“否”，二叉树的定义是递归的，递归到空树为止，所以结点无子女，应称它子树为空。,49,问题4. 树和二叉树的高度与深度如何理解？ 解析：树的高度与深度的值相等；但树中某个结点的高度与深度的值可能不同：深度是从上向下计算的，高度是从下向上计算的。 问题5. 一棵二叉树有1024个结点，其中465个是叶结点，那么树中度为2和度为1的结点各

30、有多少？ 解析：由n0 = n2+1的性质，度为 2 的结点有465-1 = 464个，度为 1 的结点有1024-465-464 = 95个。 问题6. 计算深度的公式 log2(n+1) 是针对何种二叉树的？ 解析：针对完全二叉树。但对理想平衡树也可用。,50,问题7. 二叉树求深度的公式log2(n+1) 与log2n +1有何不同？ 解析：推导有些差异，都可计算二叉树深度，只不过后者对于n=0不适用。 问题8. 完全二叉树有何用处？ 解析：后续讨论可知，堆、胜者树、败者树等都按完全二叉树组织。何况完全二叉树最省存储。 问题9. n0 = n2+1公式有何用途？ 解析：对于完全二叉树最有

31、用。例如组织对抗赛可用胜者树，已知选手有n个人，取n0 = n,直接可求得比赛场次n2 = n0-1，是否有人轮空。,51,二叉树的存储,问题10. 顺序存储适用于何种二叉树？ 解析：适用于完全二叉树，可充分利用存储，并可方便地找到某结点的双亲、兄弟和子女。 问题11. 完全二叉树的结点从1开始编号和从0开始编号有何不同？ 解析：C/C+与Pascal不同，数组下标从 0 开始，完全二叉树从 0 开始编号是合理的，这时某结点i 的双亲是 (i-1)/2，左子女是2i+1，右子女是2i+2。完全二叉树结点从 1 开始编号是传承了Pascal的做法。,52,问题12. 通常使用二叉链表存储二叉树，

32、为何还选用三叉链表？ 解析：使用二叉链表找某结点的左子女和右子女比较方便，找双亲比较麻烦，三叉链表每个结点增设一个父指针，可方便地找双亲。当然，如果结点数 n 很大，不如使用二叉链表加一个栈，用栈也可记忆结点的双亲，所需空间仅O(log2n)。 问题13. 使用二叉链表存储有n个结点的二叉树，空的指针域有多少？ 解析：n 个结点的二叉树有2n个指针域，其中 n-1 个指针域被使用，有 n+1 个空指针域。,53,二叉树的遍历,问题14. 已知二叉树的前序序列abdcef，中序序列dbaecf，其后序序列是什么？ 解析：由二叉树的前序序列和中序序 列可唯一确定此二叉树，根据问 题要求构造出的二叉

33、树如右图， 后序序列为dbefca。 问题15. 前序序列与中序序列相同的是什么二叉树? 解析：要求VLR = LVR，应是左子树均 为空的单支树，或空树。,54,问题16. 前序序列与后序序列相同的是什么二叉树? 解析：要求VLR = LRV，应是只有根结点的二叉树或空树。 问题17. 前序序列与层次序序列相同的又是什么二叉树? 解析：应是右子树均为空的单支 树，或左子树均为空的单支 树，或空树。 问题18. 后序序列与层次序序列相同的是何二叉树? 解析：只有根结点的二叉树或空树。,55,问题19. 前序序列与中序序列正好相反的是什么二叉树？ 解析：要求VLR与LVR 相反，即 ，当右子树均

34、为空时， ，或空树时满足要求。 问题20. 前序序列与后序序列正好相反的是什么二叉树？ 解析：要求VLR与LRV 相反，即 ，当右子树都空时 , 或左 子树都空时 , 或空树 时满足要求。,56,问题21. 一棵二叉树的前序序列的最后一个结点是否是它中序序列的最后一个结点？ 解析：“不一定是”，右图即反例，二叉 树前序序列abdce，中序序列dbaec。 问题22. 一棵二叉树的前序序列的最后一个结点是否是它层次序序列的最后一个结点？ 解析：“是”。 问题23. 一棵有 n 个结点的二叉树的前序序列固定，可能的不同二叉树有多少种？ 解析：用catalan函数求：,57,问题24. 二叉树的前序

35、、中序、后序遍历所走的路线都相同，只是访问时机不同，这种说法对吗？ 解析：“对”，从给出的二叉树的前序、中序、后序的递归遍历算法就可以清楚看到。 问题25. 二叉树的层次序遍历是按二叉树层次进行逐层访问，其遍历算法需要使用何种辅助结构？ 解析：“队列”，使用队列，在逐层访问过程中一旦当前层次的结点出队进行处理，就需把它下一层的结点进队列。当当前层的结点全部退出队列并处理完后下一层结点已经在队头了。,58,线索二叉树,问题26. 如何构造一棵中序线索二叉树？ 解析：通过中序遍历，把二叉树改造为中序线索二叉树 void crt-inthtree(ThreadNode *p, ThreadNode

36、*,59,pre = p; crt-inthtree(p-right, pre); ; 在主程序中 pre = NULL; crt-inthtree(root, pre); pre-right = NULL; pre-rtag = 1; 问题27. 如何在一棵中序线索二叉树中寻找某结点p为根的子树上的中序第一个结点？ 解析：沿结点p的左子树链一直走下去，直到遇到其左指针为左线索的结点为止，该结点即所求。,60,ThreadNode * inFirst(ThreadNode *p) ThreadNode *q = p; while (q ,61,return q; ; 问题29. 如何在一棵中序

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

38、= 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-ltag) q = p-left; else if (!p-rtag) q = p-righ

39、t; 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-right; else q

40、 = 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 (

41、!q-ltag | !q-rtag) while (!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

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

43、de *p) ,71,if (p) if (!p-rtag) return preLast(p-right); else if (!p-ltag) return preLast(p-left); else return p; ; 问题36. 如何在一棵前序线索二叉树中寻找某结点p的前序下的后继？ 解析：若结点p有右线索，则其前序 后继即为右线索所指结点；否则 若结点p有左子女，则前序后继即 为其左子女指针所指结点, 否则为,72,其右子女指针所指结点。 ThreadNode *preNext(ThreadNode *p) if (p) if (!p-ltag) return p-left; e

44、lse return p-right; ; 问题37. 如何在一棵前序线索二叉树中寻找某结点p的前序下的前驱？ 解析：若结点p有左线索，则其前序下的前驱即其左线索所指结点；否则需要找到它的双亲q，若p是q的左子女，则其前序下的前驱即为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 retur

45、n preLast(q-left); ; 如何找双亲留给大家自己考虑。,74,树与森林,问题38. 在一棵 m 叉树，设根在第1层，并从0开始自上向下分层给各个结点编号。问 (1) 第 i 层最多有多少结点？ (2) 高度为 h 的 m 叉树最多有多少结点？ (3) 编号为 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,的父结

46、点是(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. 使用树的双亲表示，寻找某结点 i 的双亲、所有子女、兄弟的时间复杂性是多少？,76,解析：使用树的双亲表示，寻找某结点 i 的双亲的时间复杂度为O(1)，而寻找其他要看结点存放的顺序。如果所有结点按层次序存放，寻找所有兄弟的时间为O(1)，寻找所有子女的时间为O(n);如果所有结点按先根序存放，

47、寻找所有子女和兄弟的时间都是O(n)，其中 n 是结点个数。 问题40. 树的先根次序序列的特性是什么？ 解析：在树的先根次序序列中，第一个元素一定是树的根，如果树的结点个数大于1，它后面紧跟的一定是第一棵子树的根，.。子树又是树，同样满足上述特性。,77,问题41. n 个结点的树有多少种？ 解析：可通过树的二叉树表示来估计。在树的二叉树表示中，根的右指针一定是空的，因此，估计有多少种形态看根的左子树的n-1个结点能构成多少种二叉树。根据在二叉树中的分析可知，它服从catalan函数，等于 问题42. 森林中树T1、T2、T3的结点数为m1、m2、m3，在该森林的二叉树表示中，根的左子树和右

48、子树各有多少结点？,二叉树表示,78,解析：在森林的二叉树表示中根是T1的根，其左子树是T1的根的子树森林，有m1-1个结点，其右子树是除T1外其他树T2、T3构成的森林，有m2+m3个结点。 问题43. 在一个有 n 个结点的森林的二叉树表示中，左指针为空的结点有 m 个，那么右指针为空的结点有多少个？ 解析：左指针为空的都是森林中各棵树的叶结点，非叶结点有n-m个。每个非叶结点的子女-兄弟链都有一个右指针为空的结点，加上根结点的右指针为空，故右指针为空的结点有n-m+1个。,79,二叉排序树,问题44. 一棵有 n 个结点的二叉排序树有多少种不同形态？ 解析：二叉排序树的中序排列一定，不同

49、的前序序列得到不同的二叉排序树，不同二叉排序树的总数服从catalan函数 问题45. 若想把二叉排序树上所有结点的数据从小到大排列，采用何种遍历算法？从大到小排列，又采用何种算法？,80,解析：采用中序遍历算法：若想得到从小到大排列的遍历结果，采用LVR的方式，若想得到从大到小的遍历结果，采用RVL的方式。 问题46. 每次插入一个新元素到二叉排序树中应插入到什么地方？树的高度最大是多少？ 解析：在插入之前应先调用查找算法从根开始查找插入位置，如果查找成功，说明树中已有要插入的元素，新元素不插入；如果查找失败，则把新结点插入到查找失败的位置。注意，新结点将作为叶结点插入。二叉排序树是向下增长

50、的，最高是单支树情形，若树结点数为n，最大高度为n。,81,问题47. 衡量一棵二叉排序树的查找性能要计算其查找成功的平均查找长度和查找不成功的平均查找长度，此时可借助的辅助结构是什么？ 解析：扩充二叉树（或称判定树）。内结点代表二叉排序树原有的数据，查找成功时查找指针停留在内结点上；外结点代表二叉排序树原来没有的数据，查找失败时查找指针走到外结点。,ab,de,gh,j,l0,qr,tx,z,82,问题48. 对下图所示二叉排序树，查找成功的平均查找长度和查找不成功的平均查找长度是多少？ 解析：查找成功的平均查找长度为 查找不成功的平均查找长度为 扩充二叉树的 内结点的度为 2, 外结点的度

51、 为0。n0 = n2+1,83,问题49. 对一棵二叉排序树做中序遍历，再基于得到的中序序列重新构造二叉排序树，这两棵二叉排序树是否相同？ 解析：一般不相同。对一棵二叉排序树做中序遍历得到一个有序的序列，再顺序用序列中的数据构造二叉排序树，得到一棵单支树，每个结点的左子树均为空。,中序遍历,h,k,p,s,y,顺序插入,84,平衡二叉树,问题50. 二叉树、二叉排序树和平衡二叉树之间是何关系？ 解析：二叉排序树是二叉树的特殊情形，平衡二叉树又是二叉排序树的特殊情形。平衡二叉树是高度平衡的二叉排序树。 问题51. 有 n 个结点的平衡二叉树的最小高度和最大高度是多少？ 解析：让平衡二叉树每层结

52、点达到最大数目，就得到它的最小高度：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 = 13, 有Nh = Fh+2-1。 另外，斐波那契数满足渐进公式： 由此可得,86,两边取对数 由换底公式 logX = log2X /

53、 log2 及 log2 = 0.694 和 可得 h 1.44*log2(Nh+1) 0.33 2 直接计算 Lh = h/2+1.,88,问题53. Huffman树是一棵扩充二叉树，外结点（叶结点）有 n 个，那么总共有多少结点？ 解析：总共有 2n-1 个结点，因它只有度为 0 和度为 2 的结点，由n0 = n2+1，当n0 = n时，n0+n2 = n+n-1 = 2n-1。 问题54. 在构造Huffman树的过程中，每次从森林中选根的关键字值最小和次小的两棵树合并。在合并时是最小的做左子树还是次小的做左子树？ 解析：都可以。可参考算法的实现代码，但手工构造时没有限制。,Huff

54、man树,89,问题55. 用Huffman树构造最佳判定树，内、外结点各起什么作用？带权路径长度表示什么意思？ 解析：内结点是比较过程中的中间结果，外结点是比较的最终结果。带权路径长度表明可能的比较次数，或总比较次数的期望值。 问题56. 用Huffman树构造不等长的Huffman编码，一段报文的总（二进制）编码数用什么衡量？ 解析：首先根据报文中各字符出现的频度和每个字符的Huffman编码，计算带权路径长度，它就是该报文的总（二进制）编码数，也叫做总编码长度。,90,问题57. 并查集（mfset or UFSets or disjoint）主要用在什么地方？ 解析：一是判断和构造等价

55、类，二是判断和构造图的连通分量。 问题58. 并查集有哪几种操作？ 解析：并查集以双亲表示为其存储结构，操作有: (1) Find(S, x), 寻找 x 所在子树的根；(2) Union(S, s1, s2), 合并以 s1 和 s2 为根的子树（s1 并入 s2, 还是 s2 并入 s1, 根据算法的具体实现而定）；(3) UFSets(S), 把集合S初始化为一个森林。,并查集,91,问题59. 堆作为优先级队列的实现，插入和删除在堆得什么位置实施？ 解析：插入在队尾，即堆的最后元素的后面，删除在队头，即堆顶（最前面的位置）。 问题60. 堆用数组作为其存储，那么它是线性结构还是非线性结

56、构？ 解析：即使使用数组作为存储结构，它也是非线性结构。逻辑结构才区分线性还是非线性。因为堆是用完全二叉树组织，可以利用二叉树性质很容易地找某结点的双亲、子女和兄弟。,堆（heap）,92,问题61. 若想把数组中的 100 个元素调整为小根堆（或大根堆）需做多少次关键字比较？ 解析：堆按完全二叉树组织，当n = 100为偶数时，堆有1个度为1的结点，50个叶结点，49个度为2的结点，堆的高度为 h = log2(100+1) = 7。 上面5层是满的，有25-1 = 31个结点，第6层度为2的结点有49-31 = 18个结点，则形成初始堆的最大关键字比较次数为： 第6层：18*2*1+1*1

57、*1 = 37 ； 第5层：10*2*2+6*2*1 = 52； 第4层：5*2*3+3*2*2 = 42；,18/2+1,24-10,23-5,93,第3层：22*2*4 = 32； 第2层：21*2*5 = 20； 第1层：20*2*6 = 12。 总比较次数12+20+32+42+52+37 = 195次，时间复杂度O(n)。如果借助公式 这是最大估计。,94,第四章知识点解析,本章“图”的知识点有 7 个： 图的基本概念 图的存储结构 图的遍历 最小生成树 图的最短路径 图的活动网络（拓扑排序、关键路径）,95,图的基本概念,问题1. 是否有“空图”的概念？ 解析：图的定义要求顶点集合

58、不能为空，边集合可以为空，严格地讲，没有“空图”这个定义。 问题2. 有 n 个顶点的无向图最多有多少条边，最少有多少条边？无向连通图的情形呢？ 解析：n 个顶点的无向图最多有 n(n-1)/2 条边，最少有 0 条边；如果是连通图，最多有 n(n-1)/2 条边，最少有 n-1 条边。 问题3. 有 n 个顶点的有向图最多有多少条边，最少,96,有多少条边？强连通图的情形呢？ 解析：n 个顶点的有向图最多有 n(n-1) 条边，最少有 0 条边；如果是强连通图，最多有 n(n-1) 条边，最少有 n 条边（环），特别情形：n = 1 时最少边数为 0。 问题4. 试讨论顶点的度与边的关系。 解析：无向图情形，所有顶点的度数总和等于边数的 2 倍，这是因为一条边与两个顶点关联，它们在计算度数时做了重复计算。有向图情形，所有顶点的出度总和等于入度总和，还等于边数，因为总体来看，边的出、入平衡。,97,问题5. 图中任意两顶点间的路径是用顶点序列标识的，还是