数据结构C描述介绍资料

1、数据结构(sh j ji u) C语言描述 特色解析清华大学(qn hu d xu)计算机系 殷人昆教材介绍共一百二十七页讲座(jingzu)内容教材(jioci)编写背景教材编写的考虑学习的纲领各章知识点、特色与疑难问题2共一百二十七页新书(xnsh) 数据结构 C语言描述 分析3共一百二十七页教材编写(binxi)背景目前市场上用 C 描述的数据结构教材太多了，为什么华章约我写这样一本书？我想，主要是看重我教学经验。到底我在数据结构方面有什么经验？我自己也有些困惑，不过，在清华BBS网站“水木清华”上学生对我的评价相当正面。回顾以往，我第一次学习(xux)数据结构，是1978年，起步与赫赫

2、有名的大师严蔚敏、许卓群、杨冬青等应是同一年代，何况严蔚敏的第一本教材还借走了我的笔记呢。4共一百二十七页不过，有一段时间我参与了 VLSI CAD 数据库的研发，1985年去了日本，做了两年客座研究员，方向是“软件质量管理”，转向了软件工程方向，回国后成了郑人杰老师本科生“软件工程”课程的B角。1990年郑人杰老师调动工作到了清华同方，我就成了该课程的A角，直到2006年把课程交给留美归国的白晓颖老师。在1985年前，曾确定我担任严蔚敏老师“数据结构”的B角，为此我还做了些准备。出国后换了人，前系主任唐泽圣、周立柱都曾担任过B角，但因为(yn wi)某些原因，先后离开了。5共一百二十七页19

3、91年重新让我担任该课程的B角，为争取学校的一类课建立梯队。此前我已经担负 3 年全校非计算机专业二学位数据结构教学，与严蔚敏老师的配合比较顺利，大课一年一轮换，今年上大课来年上小班辅导课。直到1998年严老师退休，我开始担任A角。此外，应北大老师相邀，从1996年起在京海研修学院为高教自考学生上“数据结构”课程，为保证通过率，安排了80个学时讲课，教材先后用过 3 本， 感觉把数据结构的边边角角都讲到了，通过率每年都在65%以上(yshng)，年年受奖。6共一百二十七页高教自考指定(zhdng)教材北大许卓群杨冬青(dngqng)等编中科大黄刘生编北大张乃校编7共一百二十七页通过研究高教自考

4、的考试试题，总结了不少在各个知识点学生容易忽视的细节，这对我的教学积累帮助不小，后来虽然不去了，但我与北大孙家潚老师、丁文魁老师、张乃孝老师建立了友谊。1996年，美籍华人学者冀中田再次来华讲学(jing xu)，系主任周立柱问及在美国现在以什么语言上数据结构课，冀中田推荐了C+。因此，周立柱老师决策上C+的数据结构，并启动教材编写，由于我有积极性，决定让我来写。当时，我和郑人杰正在与美国Grand Valley State University终身教授陶永雷合作编写实用软件工 8共一百二十七页程（第二版），顺理成章开始数据结构 用面向对象方法和C+描述的合作。我们优选的原版英文教材是E.Ho

5、rowitz, S.Sahni & D.Mehta在1995年出版的Fundamentals of data structure in C+，它的特点是章节编排顺序与严蔚敏的教材一致，便于中国老师接受，作者都是名家，内容比较权威，面向对象算法容易阅读。编写工作(gngzu)十分吃力，还用了 3 位SRT的学生使用当时流行的Borland C+调试算法。遗憾的是，许多调试通过的算法后来用Visual C+编译不过去（系统兼容问题），给学生造成学习困难。 9共一百二十七页经过56年的教学实践，我们开始改版。这次是清华信息学院出面，在全院范围组织了课程教学组，参加者包括计算机、电子、自动化、微纳电子

6、等系数据结构教师(jiosh)，以计算机系为主，编写数据结构 用面向对象方法和C+描述（第二版）教材。由于有了教学经验和教训，这次编写比较顺利，在讲解上更加清晰，在技术细节上避开了许多语言或编译上的陷阱，选用了一些新出现的算法。由于多人合作，还会有些夹缠不清的或出现矛盾的情节，多谢许多热心读者帮助我们解决问题。10共一百二十七页直到第 4 次印刷后才算松了一口气，绝大多数问题都解决了。由于以上经历，完成好华章(huzhng)交给的任务有把握的也是对我教学经验的一个总结。11共一百二十七页教材编写(binxi)的考虑数据结构到底有什么(shn me)用？它是敲门砖你要进电脑公司吗？业务考试必考数

7、据结构。你要深造吗？计算机专业考研、考博必考数据结构。你要出国吗？进外国大学计算机专业必考数据结构。你要获得上级的青睐吗？听话，出活是必须的，要出活如何少得了数据结构。12共一百二十七页它是解决问题必不可少的世界上很多问题的解决都可以归结到离散问题。解决问题的手段是建模（数学模型抽象思维），模型求解的根本是算法（计算思维），算法设计的基础是数据结构，算法实现的基础是程序设计。沃斯说：算法+数据结构=程序。进一步说：高效的算法+适当的数据结构+程序语言的熟练运用=卓越的程序系统(xtng)。系统开发能力就是如此。13共一百二十七页学好数据结构要靠什么？责任感学习不能无目标，让你学什么就学(jix

8、u)什么。学习涉及的是一种人生观或价值观，涉及你将来在社会上扮演什么角色。战斗精神学习像打仗，没有免费的午餐。不靠拼命如何攻克堡垒，不能三天打渔两天晒网。实践精神学习不能光靠读书，要多做题。能力是知识在应用中运用的体现。14共一百二十七页创新精神问题的求解需要运用已学到的知识，问题的解决可以举一反三。特别是算法。严谨精神知识有系统性。学习就是一个系统工程，每一步(y b)学习，都在为后续的学习铺垫；每一个知识点都在后续的知识点或其他课程中用到。团队和奉献精神一个合唱队，若一个声音高亢得超出所有声音，此合唱必定不和谐。要互相帮助。15共一百二十七页这本数据结构教材是写给谁的？数据结构的知识体系难

9、吗？不难。每一个知识点看起来如此简单，像一个个音符(ynf)一样；然而汇集起来，以最佳方案解决问题就不那么简单了。想把这些知识点用好，就像把音符(ynf)恰到好处地安排到适当的位置，奏出最悦耳的音乐，这就是我们的目的。这本教材想把最基本的知识体系介绍给读者且让读者能够切实理解它，掌握它。据 3 年来批阅计算机考研联考试卷的体会，不少考试基本功训练不足，亟待有人引路。16共一百二十七页本教材完全遵照全国硕士研究生入学统一考试计算机科学与技术学科联考考试大纲安排，并参照教育部计算机科学与技术教学指导委员会高等学校计算机专业人才专业能力构成与培养的要求，以专业基础能力培养为目标，承续程序设计基础课程

10、，培养基本计算思维能力，提高算法设计和程序实现能力，并为提高系统开发能力打下良好的基础。基本出发点：采用“工科”思维，启发学生(xu sheng)掌握“化复杂为简单”的方式，从问题入手，通过“问题/子问题”分解，寻找解决方案； 17共一百二十七页对基本知识点讲深讲透，通过多种应用举例，让学生了解不同问题需要采取什么方法来应对；通过大量习题，从不同视点不同层面训练学生，见多才能识广，才能培养出联想能力，提高分析问题、解决问题的能力；配合辅助教材数据结构(sh j ji u)习题精析与考研辅导，提供了多达600多题的参考答案和解析，并就关键点进行点拨；另外，提供了多套模拟题。 18共一百二十七页本

11、教材采用C语言作为数据结构及算法的描述工具，适当采用C+的少量语句以简化程序。算法描述力求结构化，注重编程风格，每个算法基本保持在100行之内，可读性强。本教材是从作者多年在清华大学计算机系讲授的“数据结构”课程的教材和课件中取材，并经过一定改编而成，因此在叙述上适合学生的特点，在内容上浅显易懂，在选材上舍弃了很多超出规范和大纲的内容，增加了许多在老教材中忽略了的内容，应该不会辜负读者的期望。 由于2012年考研大纲增加了“外排序”的内容，相应(xingyng)补充内容可从华章网站下载。19共一百二十七页参考(cnko)教材（国外）20共一百二十七页参考(cnko)教材（国内）21共一百二十七

12、页学习(xux)的纲领数据结构课程是计算机专业的专业基础课程，为业界做系统开发提供了不可或缺的技术和知识，是计算机专业考研的重头科目。数据结构课程学习有几点重要的经验提供给大家参考(cnko)。注重概念抓住特点学会算法拓展应用22共一百二十七页注重概念从考研情况分析(fnx)，试题涉及的内容都很基本，没有很深很难的内容，所以要重视概念的学习：牢记定义。结构定义有规范写出的，有言外隐藏的和引伸的概念。注意传承。某些结构与其他结构间有传承关系，有变种关系。区分层次。分清逻辑的和物理的结构，以及它们之间的关系。挖掘细节。细节可提供更多解题的知识。23共一百二十七页抓住特点每种结构有它的特点和用途，这

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

14、构的存储方式定义和相应操作的程序实现。常用算法的设计。包括设计的三阶段（基本思想、算法框架、程序实现）。算法的简单分析。掌握时间复杂性的分析技能和附加存储空间的计算。25共一百二十七页拓展(tu zhn)应用每种结构都有许多应用场合，有不同应用目的和应用方式。每种算法也可变通以适用于不同的问题求解。明确问题求解的步骤。掌握问题求解的三阶段：分析(弄懂题意)、设计(考虑解决方案)、实现(算法设计与分析)。坚持算法设计与分析的步骤。算法设计三阶段（基本思想、算法框架、程序实现）。结构和算法的不同应用。这是最繁杂、范围最广的部分。通过多练习达到熟练应用。26共一百二十七页为在有限的时间内学习好这门课

15、程，应当注意以下几点:注意学习用 C / C+ / Java 语言编写小程序时的语法规则和方法，为算法分析和算法设计题的求解打下基础。函数定义和参数使用。算法一般(ybn)以函数形式给出，函数编写需要注意的问题包括函数类型，函数参数传递，函数返回值类型等，以及传值参数和引用参数在使用上的区别。函数中局部变量的作用域。特别注意在函数中对局部变量的任何改变，在函数外不能使用。27共一百二十七页算法设计所用数据结构的自定义。算法设计时不能忽视所用数据结构的声明。CC+ 中的动态存储分配和回收方式。涉及链表结构的地方都可能有动态存储分配和回收操作。要掌握正确使用相关语句的方法。在CC+ 中输入输出文件

16、的定义和使用。特别注意正确使用文件的打开、关闭、读入、写出操作的使用。在学习数据结构时，要注意知识体系。数据结构课程中的知识本身具有良好的结构性，有些结构面向应用(yngyng)，有些结构面向实现。学习时28共一百二十七页要注意这两个层次以及它们之间的联系。注意循序渐进在学习数据结构时，首先(shuxin)需要学习数据结构的定义和特点，数据结构的使用范围，再学习各种操作的实现。在阅读算法之前，要先弄清其基本设计思想、基本步骤，并通过事例学习了解每个算法的处理流程以加深理解，最后再阅读程序代码。注意比较在复习中应当注意从“横向”和“纵向”进行对比以加深理解。29共一百二十七页纵向对比将一种结构与

17、它的各种不同的实现(shxin)加以比较，理解不同实现方式的优点和问题。如二叉树的顺序和链表实现。横向对比是对属于同一类逻辑结构的不同数据结构（如线性表、栈、队列）加以比较，对具有相同功能的不同算法进行比较等，了解数据结构与算法实现间的关系。注意练习只看书不做题，不能真正学会有关知识，不能达到技能培养的目的。做题是自我检查的重要手段。30共一百二十七页在做算法设计类型的习题时，应考虑数据结构的定义。提高算法设计的能力。编写算法的题可能是学生比较棘手的问题，特别是在考试这样一个氛围，时间又短促，想编出一个好算法不太容易。一个建议是首先仔细阅读试题题目，了解(lioji)它到底要你干什么。然后用一

18、个简单的例子走一下，总结每一步向下走可用什么语句实现。31共一百二十七页再做归纳，整理出处理流程。按照结构化程序设计的方法，搭建框架(kun ji)，再根据例子填入细节。在设计一个算法时，要考虑问题解决方案的多样性、算法的适用性、问题对算法选择的限制。选择合适的数据结构，设计有效的算法。下面我们将与严蔚敏老师的教材做一对比，说明我们的教材在何处补充了严蔚敏老师的教材。顺带给出一些问题的点拨。32共一百二十七页各章知识点、特色(ts)与疑难问题第一章 数据结构概论第二章 线性表第三章 栈、队列与数组第四章 树与二叉树第五章 图第六章 查找(ch zho)第七章 排序33共一百二十七页本章“绪论”

19、的知识点有 4 个：数据结构的概念使用C/C+语言描述数据结构和算法的方法算法的定义及算法的特性算法的性能分析(fnx)与严版教材的差别抽象数据类型的表述有差异增加线性结构按存取方式的分类增加算法设计步骤和算法设计基本方法算法空间复杂度度量表述有差异第一章 知识点解析(ji x)34共一百二十七页数据结构(sh j ji u)的概念问题1. 平时所说的信息和数据有何区别(qbi)？问题2. 数值性数据和非数值性数据有何区别？问题3. 数据类型与数据结构有何关系？问题4. 数据对象与数据结构有何关系？问题5. 抽象数据类型中的抽象和信息隐藏是何含义？问题6. 如何区分数据的 4 种逻辑结构类型？

20、问题7. 如何区分数据的 4 种存储结构类型？问题8. 线性结构按照数据的存取方式又可分为几种类型？35共一百二十七页使用C/C+语言描述(mio sh)数据结构和算法问题1. 定义一个struct时，前面加typedef，与不加typrdef有什么不同(b tn)？问题2. 用struct和union定义的结构体有何不同？问题3. 在循环结构中while循环和do循环中条件表达式取值对循环执行有何影响？问题4. 函数调用时，参数采取引用型和传值型有何区别？问题5. 动态存储分配和回收操作，C与C+各自如何处理，各有何特点？问题6. 输入和输出操作，C和C+各自如何处理？36共一百二十七页算法

21、(sun f)的定义及算法(sun f)的特性问题1. 算法应有输入，则0个输入是否有输入？问题2. 如果(rgu)一个求解方程根的牛顿算法不收敛，它是否违反“有穷性”的要求？问题3. 如果一个算法多层嵌套地调用了其他算法，它是否违反“可行性”的要求？问题4. 如果一个算法内部有一个随系统状态会转移到不同指令地址的开关，它是否违反“确定性”的要求？问题5. 用结构化方法设计算法有哪 4 个阶段？问题6. 穷举法与迭代法有何关系？37共一百二十七页问题7. 递推与递归又有何关系？问题8. 穷举法与递推有何关系？问题1. 如何用断言方式判断算法的正确性？问题2. 如何实现算法的健壮性？问题3. 如

22、何判断算法的简单性？为何要求一个算法具有简单性？问题4. 如何判断算法的可读性？为何要求一个算法具有可读性？问题5. 算法的执行(zhxng)频度如何计算？算法(sun f)的性能分析38共一百二十七页问题6. 问题规模是什么？问题7. 算法的复杂度与问题规模有何关系？问题8. 算法复杂性度量是事前估计（分析）还是事后(shhu)测量？问题9. 空间复杂度度量应统计哪些占用的空间？问题10. 算法的大O表示是T(n) = O(f(n)，如果一个算法的执行频度是2n3+3n2+2n+1，则该算法的渐进时间复杂度为T(n) = O(n3)，为什么？39共一百二十七页本章“线性表”的知识点有 5 个

23、：线性表的定义和特点线性表的基本操作线性表的存储(cn ch)表示：顺序存储、链表存储循环链表和双向链表线性表的应用与严版教材的差别顺序表中元素的序号从 1 开始，但存储数组中的下标从 0 开始，严版的存储数组下标均从 1开始，因为它是从pascal版对译过来的。第二章 知识点解析(ji x)40共一百二十七页给出了顺序表的两种声明(shngmng)，并指出它们之间的差别，严版只有一种。顺序表的操作实现中尽量采用引用型参数传递表本身，函数体中的语句简单，容易理解；严版不是，导致实现操作的函数体内语句出现诸多指针运算和引用，可读性差。增加了单链表的递归性讨论，严版没有提及。在单链表应用中引入有序

24、链表，并用它实现集合结构；严版没有提及。把关于字符串的讨论移到线性表的应用部分，删去了KMP算法。严版单列了一章。41共一百二十七页一元多项式讨论中增加了多项式输出和多项式乘法的讨论。严版只有多项式建立和加法的讨论。最后，增加了本章小结，严版没有。问题1. 如果一个元素(yun s)集合中每个元素(yun s)都有 1 个且仅有 1 个直接前驱和 1 个直接后继，它是线性表吗？问题2. 循环链表是线性表吗？线性表的定义(dngy)和特点42共一百二十七页问题3. 如果一个元素集合有一个元素仅有 1 个直接后继而没有直接前驱，另一个元素仅有 1 个直接前驱而没有直接后继，其他每个元素都仅有 1

25、个直接前驱和 1 个直接后继，但其中各个元素可能数据类型不同，该元素集合是线性表吗？问题4. 如果一个有 n（n0）个表元素的序列构成一个表，且表元素既有不可再分的数据元素，又有可以(ky)再分的子表，它是线性表吗？如果不是，它又是什么表？什么条件下才成为线性表？ 43共一百二十七页问题1. 如果一个一维数组有 n 个数组元素(yun s)，它是线性表吗？二维数组可视为数组元素(yun s)为一维数组的一维数组，那么二维数组是线性表吗？为什么？问题2. 顺序表每插入一个新元素，或删除一个已有元素，需要移动多少元素？平均移动多少元素？问题3. 如果不想移动多个元素实现顺序表的插入与删除，应如何做

26、？ 线性表的基本操作44共一百二十七页线性表的存储(cn ch)表示问题1. 线性表的顺序存储表示是一维数组吗？问题2. 想要以O(1)的时间代价存取第 i 个表元素，线性表应采用顺序表还是单链表？问题3. 顺序表可以扩充吗？如果想要扩充，应采用何种结构？问题4. 为了统一空链表和非空链表的操作，简化链表的插入删除操作，需要给链表增加点什么？问题5. 如果想使得顺序表适合多种数据类型，顺序表应如何构建？假设顺序表的每个元素不是原子(yunz)类型，其元素成分由使用者自行决定。45共一百二十七页问题6. 在何种场合选用顺序表？链表呢？问题1. 想要以O(1)的时间代价把两个链表连接起来可采用(c

27、iyng)何种链表结构？问题2. 想要判断一个带头结点的循环链表 L 是否为空，应采用何种语句？ 问题3. 想要以O(1)的时间代价访问第 i 个表元素的直接前驱和或直接后继，应采用何种链表结构？ 循环(xnhun)链表和双向链表46共一百二十七页第三章 知识点解析(ji x)本章“栈、队列与数组”的知识点有 8 个：栈和队列的定义及其特点栈的存储表示及其基本运算(yn sun)的实现队列的存储表示及其基本运算的实现栈的应用队列的应用多维数组特殊矩阵稀疏矩阵47共一百二十七页与严版教材的差别顺序栈的栈顶指针设定为整数（即游标），它指示的是当前栈顶的下标位置。严版的栈顶指针设定为指针型，它指示的

28、是当前栈顶的内存地址，栈操作的实现(shxin)上复杂一些。为降低复杂性，提高可读性，尽量避免使用指针。链式栈增加了头结点。严版仅给出链式栈的示意图，未讨论操作的实现。增加了栈的混洗（即可能出栈序列）的讨论。严版未提及。增加了栈操作实现算法性能分析。严版没有。48共一百二十七页增加了队列操作实现算法性能分析。严版没有。通过阶乘问题的讨论，介绍(jisho)了递归实现的过程和递归工作栈。严版通过汉诺塔问题的讨论，介绍(jisho)了递归实现的过程和递归工作栈。通过汉诺塔问题的讨论，引入了分治法。严版没有提及。通过迷宫问题的讨论，引入了回溯法。严版没有此例。通过求组合问题，引入了动态规划法。严版没

29、有提及。详细定义了双端队列及其实现。严版没有提。49共一百二十七页增加了数组的应用举例，给出用数组存储长整数和实现阶乘运算的例子。严版没有。针对特殊矩阵的压缩存储，通过下标转换，实现映射。严版从矩阵到压缩存储数组有，但想从压缩数组到特殊矩阵的转换没有提及。放宽对稀疏矩阵的要求，并说明三对角矩阵是稀疏矩阵，不应把稀疏矩阵与特殊矩阵对立起来。严版仅认定一种(y zhn)判断稀疏矩阵的规则。增加了带行指针数组的二元组表示。严版没有。本章有小结，严版没有。50共一百二十七页问题1. 栈是一种先进后出的顺序存取结构，它是顺序存储结构吗？问题2. 一个较早进栈的元素能否先于在它之后进栈的元素从栈中取出？

30、问题3. 一般来讲，只允许栈顶元素从栈中退出，在什么情况下元素可以从栈底泄出？问题4. 元素以1, 2, , n的顺序进栈，如何判断可能(knng)的出栈序列？可能(knng)的出栈序列有多少种？问题5. 队列具有先进先出的特性，可不可以加塞，在队列其他位置进出队列？栈和队列(duli)的定义及其特点51共一百二十七页问题6. 以1, 2, , n进队，可能的出队序列有多少？ 问题7. 栈、队列和向量（一维数组）有什么不同？问题8. 可否(k fu)用两个栈模拟一个队列？反过来呢？问题9. 栈、队列和向量（一维数组）有什么不同？问题10. 双端队列有何特点？ 问题11. 优先级队列有何特点？

31、问题1. 当栈空时顺序栈的栈顶指针 top = -1，当栈非空时 top 是否指示最后元素加入的位置？栈的存储(cn ch)表示及其基本运算的实现52共一百二十七页问题2. 顺序栈的进栈、出栈的先决条件是什么？问题3. 当一个顺序栈已满，如何才能扩充栈长度，使得程序能够继续使用这个栈？ 问题4. 当两个栈共享同一个存储空间 Vm 时，可设栈顶指针数组 t2 和栈底指针数组 b2。如果进栈采用两个栈相向前行的方式，则任一栈的栈满条件是什么？问题5. 若进栈序列为1, 2, 3, 4, 5, 6，出栈序列为2, 4, 3, 6, 5, 1，问栈容量至少(zhsho)多大？问题6. 顺序栈的优点是什

32、么？缺点是什么？问题7. 链式栈的栈顶指针是指在链头还是链尾？53共一百二十七页问题8. 如果链式栈没有头结点，链式栈的栈顶在链表的什么位置？栈底在链表的什么位置？栈指针如何设置？栈空条件是什么？栈满条件是什么？问题9. 链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取，这话对吗？问题10. 理论上链式栈没有栈满问题，但在进栈操作实现时，还要判断一个后置条件，是何条件？问题10. 常用的一种链式栈是基于静态链表的。用一个整数(zhngsh)数组 Sn 存放链接指针（游标），设初始时 top = -1，表示栈空，则其进栈、出栈、判栈空等操作如何实现？54共一百二十七页问题11. 链式栈的

33、优点是什么？缺点是什么？ 问题1. 队列操作deQueue (Q, x)与getFront (Q, x)有什么区别(qbi)？问题2. 当用牺牲一个单元的方式组织循环队列时，队空和队满条件是什么？进队、出队如何进行？问题3. 当一个循环队列已满，如何才能扩充队列长度，使得客户程序能够继续使用这个队列？问题4. 在循环队列中进行插入和删除时，是否需要移动队列元素的位置？ 队列(duli)的存储表示及其基本运算的实现55共一百二十七页问题5. 在循环队列中将 elem 数组的尾端 elemmax Size-1 与前端 elem0 衔接起来，此时队尾指针rear和队头指针front是如何移动的？ 问

34、题6. 当用队头指针 front 和长度 length 组织循环 队列时，队空和队满的条件是什么？进队和出队的策略是什么？（设表长度为m）问题7. 链式队列的队头和队尾在链表的什么地方？问题8. 如果链式队列没有头结点，链式队列的队头和队尾在链表的什么地方？队空条件是什么？问题9. 同时使用多个(du )队列时需采用何种队列结构？如何组织？56共一百二十七页问题10. 链式队列的每个结点是否还可是队列？问题11. 队列还有哪些(nxi)变型？ 问题1. 在后缀表达式求值过程中用栈存放什么？在中缀表达式求值过程中又用栈存放什么？问题2. 为判断表达式中的括号是否配对，可采用何种结构辅助进行判断？

35、 问题3. 在递归算法中采用何种结构来存放递归过程每层的局部变量、返回地址和实参副本？栈的应用(yngyng)57共一百二十七页问题4. 递归深度与递归工作栈的层次有何关系？问题5. 在回溯法中采用何种结构来记录回退路径(ljng)？问题6. 在分治法中采用栈做什么？举例说明。问题7. 在减治法中采用栈做什么？举例说明。问题1. 在逐层处理一个分层结构的数据时，需采用何种辅助结构来组织数据？问题2. 为实现输入-处理-输出并行操作需建立多个输入缓冲区队列，这些队列是按数组方式组织的还是按链表方式组织的？队列(duli)的应用58共一百二十七页问题3. 在操作系统中一种进程调度策略是先来先服务，

36、为此使用了何种辅助结构？问题4. 在对一个无序单链表进行排序时，可先把链表截出一段段有序的子链表，再对它们做两路归并排序。为此定义队列来辅助排序，此队列的元素的数据类型是什么？问题5. 双端队列的作用是什么？有几种(j zhn)双端队列？问题6. 在用动态规划法进行问题求解时可否利用队列？为什么？问题7. 在一个网格中求两点间最短路径时可否利用队列？为什么？59共一百二十七页多维数组问题1. 一维数组是线性结构码？它是逻辑结构还是存储结构？问题2. 对于(duy)一维数组只能直接存取吗？问题3. 一维数组一旦放满可以扩充吗？问题4. 二维数组可以视为数组元素为一维数组的一维数组，因此二维数组是

37、线性结构吗？问题5. 二维数组每个元素的存取时间都相同吗？问题6. 二维数组是按一维数组存储的吗？如何计算二维数组中元素的存储地址？ 问题7. 数组是逻辑结构还是物理结构？60共一百二十七页问题8. 动态数组用指针来定义。假定数组指针为 a，可否用*a 取出数组元素的值？可否用 a+ 进到下一数组元素？问题9. 链表也是动态结构。假定链表指针为*a，可否用*a 取出链表结点的值？可否用 a+ 进到下一链表结点？问题1. 如果用下三角压缩存储(cn ch)对称矩阵，B0存放A00，如何存取Aij？特殊(tsh)矩阵61共一百二十七页问题2. 计算对称矩阵在压缩数组中的存放位置时要注意什么问题？问

38、题3. 对称矩阵是否可能是稀疏矩阵？问题4. 两个对称矩阵相加，结果矩阵还对称吗？两个对称矩阵相乘，结果矩阵还对称吗？问题5. 通过矩阵元素的行、列下标如何计算通过它的正对角线（从左上到右下的斜线）和反对角线（从左下到右上的反斜线）的编号(bin ho)？ 问题6. 两个三对角矩阵相加，结果矩阵还是三对角矩阵吗？相乘的情况又如何？62共一百二十七页问题7. 为什么特殊矩阵极少使用链接存储？问题1. 三对角矩阵是否稀疏矩阵？ 问题2. 两个稀疏矩阵相加，结果矩阵还是稀疏矩阵吗？两个稀疏矩阵相乘，结果矩阵又如何？问题3. 用三元组表存储稀疏矩阵的非零元素，是否失去了直接存取的特性(txng)？如何

39、改进？问题4. 采用带行指针的二元组表，相对于三元组表，有什么优点？ 稀疏(xsh)矩阵63共一百二十七页第四章 知识点解析(ji x)本章“树与二叉树”的知识点有 9 个：树与二叉树的定义(dngy)和性质二叉树的存储结构二叉树的遍历线索二叉树树与森林二叉排序树平衡二叉树Huffman树堆64共一百二十七页与严版教材的差别区分自由树和有根树。严版没有。区分结点的深度、结点的高度、树的深度、树的高度、树的宽度。严版没有。明确定义结点间路径及路径长度。严版没有。二叉树深度定义为log2(n+1)，当n=0也可用。严版定义为log2n+1。对于完全二叉树，增加了结点编号从 0 开始的计算方法，这在

40、讨论堆时需要(xyo)用到。严版仅讨论了结点编号从 0 开始的计算方法。增加了严格二叉树和理想平衡树的概念。65共一百二十七页增加了前序和后序的使用栈的非递归算法。严版仅给出中序的非递归算法。增加了按层次序遍历(bin l)二叉树的使用队列的实现算法。严版仅提了一句。增加了递归和非递归遍历算法的应用举例。严版几乎没有。增加了树的先根、后根、广度遍历的实现算法以及树遍历算法的应用举例。严版没有。增加了二叉排序树的非递归的查找算法。严版仅给出递归的查找算法。查找性能分析增加了不等查找概率情形。严版66共一百二十七页仅讨论了相等查找概率的情形。删去了平衡二叉树的算法。严版详尽地介绍了实现算法，使读者

41、陷入无尽的烦恼(fnno)，应换一个角度重新考虑的实现算法更好。增加了平衡二叉树的删除处理及事例。严版没有讨论。讨论了平衡二叉树的插入处理及事例。严版没有讨论。增加了关于小根堆的全面讨论。严版没有。导致在讨论图的算法中不能按边的权重高效地组织数据。67共一百二十七页树与二叉树的定义(dngy)和性质问题1. 为何(wih)有的教材定义树结点数不能为0？而N叉树的结点数可以为0？问题2. 二叉树是树吗？问题3. 树的叶结点无子女，是否可称它无子树？问题4. 二叉树的叶结点无子女，它是否无子树？问题5. 树和二叉树的结点的高度与深度如何理解？树的高度与深度又如何理解？问题6. 一棵二叉树有1024

42、个结点，其中465个是叶结点，那么树中度为2和度为1的结点各有多少？68共一百二十七页问题7. 计算深度的公式 log2(n+1) 是针对何种二叉树的？问题8. 二叉树求深度的公式log2(n+1) 与log2n +1有何不同？问题9. 完全(wnqun)二叉树有何用处？问题10. n0 = n2+1公式有何用途？问题1. 顺序存储适用于何种二叉树？问题2. 完全二叉树的结点从 1 开始编号和从 0 开始编号有何不同？二叉树的存储(cn ch)69共一百二十七页问题3. 二叉树顺序存储通常适用于哪类二叉树？问题4. 在二叉树顺序存储中，如果根结点在 0 号位置，如何判定某结点 i 的父结点、左

43、子女结点、右兄弟(xingd)结点的位置？如何判断它所处层次？问题5. 通常使用二叉链表存储二叉树，为何还选用三叉链表？问题6. 如果不使用三叉链表，能否也很容易地找到父结点？问题7. 使用二叉链表存储有 n 个结点的二叉树，空的指针域有多少？70共一百二十七页二叉树的遍历(bin l)问题1. 已知二叉树的前序序列abdcef，中序序列dbaecf，其后序序列是什么？问题2. 前序序列与中序序列相同的是什么二叉树?问题3. 前序序列与后序序列相同的是什么二叉树?问题4. 中序序列与后序序列相同的是什么二叉树？问题5. 前序序列与层次(cngc)序序列相同的是什么二叉树?问题6. 后序序列与层

44、次序序列相同的是什么二叉树?问题7. 前序序列与中序序列正好相反的是什么二叉树？71共一百二十七页问题8. 前序序列与后序序列正好相反的是什么二叉树？问题9. 一棵二叉树的前序序列的最后一个结点是否是它中序序列的最后一个结点？问题10. 一棵二叉树的前序序列的最后一个结点是否是它层次序序列的最后一个结点？问题11. 一棵有 n 个结点的二叉树的前序序列固定，可能的不同二叉树有多少种？问题12. 二叉树的前序、中序、后序遍历所走的路线都相同，只是访问时机(shj)不同，这种说法对吗？72共一百二十七页问题13. 二叉树的层次序遍历是按二叉树层次进行逐层访问，其遍历算法需要使用(shyng)何种辅

45、助结构？问题1. 为什么要建立线索二叉树？问题2. 如何构造一棵中序线索二叉树？问题3. 如何在一棵中序线索二叉树中寻找某结点p为根的子树上的中序第一个结点？问题4. 如何在一棵中序线索二叉树中寻找某结点p为根的子树上的中序最后一个结点？线索(xin su)二叉树73共一百二十七页问题(wnt)5. 如何在一棵中序线索二叉树中寻找某结点p的中序下的后继？问题6. 如何在一棵中序线索二叉树中寻找某结点 p的中序下的前驱？问题7. 如何在一棵中序线索二叉树中寻找某结点p的父结点？问题8. 如何在一棵中序线索二叉树中寻找某结点p的前序下的后继？问题9. 如何在一棵中序线索二叉树中寻找某结点p的前序下

46、的前驱？问题10. 如何构造一棵前序线索二叉树？74共一百二十七页问题11. 如何在一棵前序线索二叉树中寻找某结点p为根的子树上的前序第一个结点？问题12. 如何在一棵前序线索二叉树中寻找某结点p的前序最后一个(y )结点？问题13. 如何在一棵前序线索二叉树中寻找某结点p的前序下的后继？问题14. 如何在一棵前序线索二叉树中寻找某结点p的前序下的前驱？问题15. 在线索二叉树上插入或删除一个结点需要做什么？ 75共一百二十七页树与森林(snln)问题1. 在一棵 m 叉树，设根在第1层，并从0开始自上向下分层给各个结点编号。问(1) 第 i 层最多有多少结点？(2) 高度为 h 的 m 叉树

47、最多有多少结点？(3) 编号为 k 的结点的父结点编号是多少？(4) 编号为 k 的结点的第1个子(g zi)结点编号是多少？(5) 编号为 k 的结点在第几层？问题2. 使用树的父指针表示，寻找某结点 i 的父结点、所有子女、兄弟的时间复杂性是多少？76共一百二十七页问题3. 树的先根次序序列的特性是什么(shn me)？问题4. 树的后根次序序列的特性是什么？问题5. n 个结点的树有多少种？问题6. 森林中树T1、T2、T3的结点数为m1、m2、m3，在该森林的二叉树表示中，根的左子树和右子树各有多少结点？问题7. 在一个有 n 个结点的森林的二叉树表示中，左指针为空的结点有 m 个，那

48、么右指针为空的结点有多少个？77共一百二十七页二叉排序(pi x)树问题1. 一棵有 n 个结点的二叉排序树有多少种不同形态？问题2. 若想把二叉排序树上所有结点的数据从小到大排列，采用何种遍历算法？从大到小排列，又采用何种算法？问题3. 每次插入一个新元素到二叉排序树中应插入到什么地方？树的高度最大是多少？问题4. 衡量一棵二叉排序树的查找性能要计算其查找成功的平均查找长度和查找不成功的平均查找长度，此时可借助的辅助(fzh)结构是什么？78共一百二十七页问题5. 对下图所示二叉排序树，查找成功的平均查找长度和查找不成功的平均查找长度是多少？问题6. 对一棵二叉排序树做中序遍历，再基于得到的

49、中序序列重新构造二叉排序树，这两棵二叉排序树是否相同？问题7.如果被删结点(ji din)是非叶结点(ji din)，为何不能直接删除？kicspyf79共一百二十七页问题8. 在二叉排序树中删除结点(ji din)时如何才能保证删除后二叉排序树的高度不增加？问题9. 为何在二叉排序树的插入和删除算法中，子树的根指针定义为引用型参数？问题10. 在二叉排序树中，从根结点到任一结点的路径长度的平均值是多少？ 问题1. 二叉树、二叉排序树和平衡二叉树之间是何关系？平衡(pnghng)二叉树80共一百二十七页问题2. 有 n 个结点的平衡二叉树的最小高度和最大高度是多少？问题3. 在高度为 h 的平

50、衡二叉树中离根最近的叶结点在第几层？问题4. 平衡化旋转的目的是什么？问题5. 平衡二叉树插入新结点后可能失去平衡。如果在从插入新结点处到根的路径上有多个(du )失去平衡的祖先结点，为何要选择离插入结点最近的失去平衡的祖先结点，对以它为根的子树做平衡化旋转？ 81共一百二十七页问题1. Huffman 树是一棵扩充二叉树，外结点（叶结点）有 n 个，那么总共有多少结点？问题2. 在构造 Huffman 树的过程中，每次从森林中选(zhng xun)根的关键字值最小和次小的两棵树合并。在合并时是最小的做左子树还是次小的做左子树？问题3. 在构造 Huffman 树的过程中，如果新构造二叉树的根

51、结点的关键字值与另一棵二叉树根结点的关键字值相同，下一次选择根的关键字值最小或次小时该选哪一个？ Huffman树82共一百二十七页问题4. 用Huffman树构造最佳判定(pndng)树，内、外结点各起什么作用？带权路径长度表示什么意思？问题5. 用Huffman树构造不等长的Huffman编码，一段报文的总（二进制）编码数用什么衡量？问题1. 堆与二叉排序树有何不同？问题2. 堆用数组作为其存储，那么它是线性结构还是非线性结构？ 问题3. 堆作为优先级队列的实现，插入和删除在堆得什么位置实施？堆（heap）83共一百二十七页问题(wnt)4. 使用 siftDown() 从结点 r 开始向

52、下筛选局部形成堆的前提条件是什么？问题5. 使用 siftDown() 对从结点 r 到结点 e 的子树进行筛选以形成堆，当 r e，或 r = e 时筛选结果如何？ 问题6. 若想把数组中的 100 个元素调整为小根堆（或大根堆）需做多少次关键字比较？84共一百二十七页第五章 知识点解析(ji x)本章“图”的知识点有 7 个：图的基本概念图的存储结构(jigu)图的遍历最小生成树图的最短路径图的活动网络（拓扑排序）图的活动网络（ 关键路径）与严版教材的差别85共一百二十七页界定了本章不予讨论的带自环的图和多重边的图。严版没有说明。说明了图中简单路径的长度。严版没有说明。带权图的邻接矩阵对角

53、线均为0。严版是。给出了邻接矩阵和邻接表常用操作的实现，后面有关图的算法都用这些操作参与图的运算，不直接用图定义中的结构(jigu)分量参加图的运算。严版直接用图定义中的结构(jigu)分量参加图的运算。删去严版求重连通图关节点算法的实现代码；把重连通图改为双连通图，增加了有关三连通图k连通图的讨论。86共一百二十七页讨论最小生成树时引入了“贪婪法”。严版没有说明。对于求解最小生成树问题的Kruskal算法以及Prim算法，给出了使用小根堆和并查集（临时引入）的较新版实现代码，节省了存储，提高了可读性。改进(gijn)了求单源最短路径问题的Dijkstra算法的实现代码，路径矩阵P改为路径数组

54、P，同样达到目的。在给出Dijkstra算法的框架时明确提出各边权重非负。严版没提。87共一百二十七页在讨论求每对顶点间最短路径的Floyd算法时说明了算法采用了“动态规划法”。严版没有说明。特别讨论了Floyd算法的适用范围，只要不存在包括带负权重的边的回路，不论有向图还是无向图，该算法都可以使用。增加了对不带权有向图最短路径的讨论。严版没有。求关键路径的算法与严版不同。严版是一边拓扑排序一边求事件的最早开始时间和最迟开始时间，本教材是假定各顶点已经(y jing)按拓扑有序编号，再做计算的。算法简单得多。88共一百二十七页图的基本概念问题1. 是否有“空图”的概念(ginin)？问题2.

55、有 n 个顶点的无向图最多有多少条边，最少有多少条边？无向连通图的情形呢？问题3. 有 n 个顶点的有向图最多有多少条边，最少有多少条边？强连通图的情形呢？问题4. 在无向图中顶点的度与边有何关系？在有向图中顶点的出度、入度与边有何关系？问题5. 图中任意两顶点间的路径是用顶点序列标识的，还是用边序列标识的？89共一百二十七页问题6. 图中各个顶点的序号是规定的，还是人为可改变的？问题7. 自由(zyu)树和生成树是什么关系？ 问题1. 有 n 个顶点、e 条边的无向图的邻接矩阵有多少矩阵元素？其中有多少零元素？有向图的情形呢？问题2. 为什么在有向图的邻接矩阵中，统计某行1的个数，得到顶点的

56、出度；统计某列1的个数，得到某顶点的入度？图的存储(cn ch)结构90共一百二十七页问题3. 有一个存储 n 个顶点(dngdin) e 条边的邻接表，某个算法要求检查每个顶点，并扫描每个顶点的边链表，那么这样的算法的时间复杂度是O(n*e)，还是O(n+e)?问题4. 设每个顶点数据占 4 个字节，顶点号码占 2 字节，每条边的权值占 4 个字节，每个指针占 2 个字节。若一个无向图有 n 个顶点 e 条边，请问使用邻接矩阵经济还是使用邻接表经济？问题5. 有向图的邻接表与逆邻接表组合起来形成十字链表，它适合于什么场合？91共一百二十七页问题1. 图的遍历针对顶点，要求按一定顺序访问图中所

57、有顶点，且每个顶点仅访问一次。可否针对边也使用遍历算法？问题2. 图的深度优先搜索类似(li s)于树的先根遍历，可归属于哪一类算法？问题3. 图的遍历对无向图和有向图都适用吗？问题4. 图的深度优先遍历如何体现“回溯”？问题5. 图的广度优先遍历类似于树的层次序遍历，需要使用何种辅助结构？图的遍历(bin l)92共一百二十七页问题6. 图的广度优先生成树是否比深度优先生成树的深度低？问题7. 图的深度优先搜索是个递归的过程，而广度优先搜索为何是非递归的过程？ 问题8. 图的深度优先搜索遍历一个连通分量上的所有顶点如何得到生成树？ 问题9. 对无向图进行遍历，在何条件(tiojin)下可以建

58、立一棵生成树？在什么条件(tiojin)下得到一个生成森林，其中每个生成树对应图的什么部分？ 问题10. 对有向图进行遍历，在何条件下可以建立一棵生成树？在何条件下得到一个生成森林？ 93共一百二十七页问题11. 如何判断一个无向图中的关节点？如何以最少的边构成双连通图？问题12. 设连通图有6个顶点，双连通图、三连通图、四连通图、五连通图如何构造？ 问题1. 图的最小生成树必须满足(mnz)什么要求？问题2. 构造图的最小生成树有多种算法，都遇到在一组边集合中选出权值最小的边的问题，用什么结构辅助最好？图的最小生成(shn chn)树94共一百二十七页问题3. 把所有的边按照其权值加入到小根

59、堆中，相应算法的时间复杂度是多少？问题4. Kruskal 算法中为了判断一条边的两个端点(dun din)是否在同一连通分量上，采用何种辅助结构？问题5. Prim算法每次选择一个端点在生成树顶点集合 U，另一个端点不在生成树顶点集合 V-U 的边中权值最小的边，采用什么辅助结构？问题1. 图的最短路径问题必须满足什么要求？图的最短路径(ljng)95共一百二十七页问题2. 用Dijkstra算法求最短路径，为何要求所有边上的权值必须大于0？ 问题3. Dijkstra算法是求解单源最短路径问题的算法，可否用它解决单目标最短路径问题？问题4. 用Floyd算法求最短路径，允许图中有带负权值的

60、边，但为何不许有包含带负权值的边组成的回路(hul)？ 问题1. 什么是拓扑排序？它是针对何种结构的？拓扑(tu p)排序96共一百二十七页问题2. 可以对一个有向图的所有顶点从新编号，把所有表示边的非零元素集中到邻接矩阵的上三角部分。根据什么顺序进行顶点的编号？问题3. 拓扑排序的一个重要应用是判断(pndun)有向图中是否有环。如何判断(pndun)？问题4. 如果调用深度优先搜索算法，在每次递归结束并退出时输出顶点，就可得到一个逆拓扑有序的序列。此方法有效性的前提是什么？问题5. 为什么拓扑排序的结果不唯一？关键(gunjin)路径97共一百二十七页问题1. 关键路径法的应用背景是什么？