前 言
数据结构是计算机科学与技术类各专业的必修课程,既是专业基础课程,也是专业核心课程。这不仅是因为计算机科学与技术学科的许多课程大都用到数据结构的有关知识,更重要的是从事计算机科学与技术领域的研发者必须具有良好的复杂程序设计能力,而程序数据的结构、组织、管理和应用水平是复杂程序设计能力的最基本的素质要求。数据结构课程的教学目标就是使学生学会分析研究计算机加工的数据对象的特性,能够在应用研发实践中适当地选择数据结构和相应的有关算法,初步掌握算法的时间与空间性能分析技巧,得到复杂程序设计的训练。
近些年来,数据结构课程不仅在计算机科学与技术类各专业开设,信息类的许多本科专业和其它相关专业也都为本科生相继开设了数据结构课程,计算机科学与技术学科的计算机应用技术、计算机软件与理论、计算机系统结构、软件工程等专业的硕士生和博士生入学考试也都基本上把数据结构课程列为必考的专业基础课程之一,由此可见计算机科学与技术学科对数据结构课程给予的显著地位和重视程度。
然而,数据结构课程的学习难度较大。除了课程自身的内容多、介绍的方法技术多、在先修课程中涉及的专业基础知识少之外,数据结构课程有着它自身的一些特点和规律:第一,对数据的逻辑结构的抽象数据类型表示学生不易理解和接受;第二,动态存储结构的动态性和递归技术的抽象性,使得学生对相应的知识不易掌握;第三,算法描述的形式化和程序设计语言化使许多学生望之生畏;第四,算法设计的灵活多样性以及算法分析的渐近阶概念等使得许多学生谈算法色变,叹算法却步。所有这些,都是造成学生在学习过程中普遍感觉到数据结构这门课程难度大的原因。许多学生在课堂上一听就明白,拿起课本认真一看就也能基本弄懂,但当拿起笔做作业尤其是做算法设计题目时总觉得无从下手,究其原因,主要是听懂学会数据结构的内容和应用数据结构知识解决实际问题之间存在着相当长的一段距离;理解和掌握算法分析与设计的各种方法和技术与灵活运用这些方法与技术解决算法分析与设计的具体问题之间也存在着相当长的一段距离。逐步缩短进而消除这两个距离是解决数据结构课程学习难的关键所在,其根本途径在于加强实践环节,多学、多用、多做、多练,熟能生巧,以期达到对所学知识和方法技术的融汇贯通。
我们在认真总结了二十多年数据结构课程教学实践中的经验教训和体会的基础上,结合新世纪大学生的特点和学习需求,编写了这本《数据结构习题解析与学习指导》,以期通过该书中的学习要点、主要内容和知识点,给学习数据结构课程的学生归纳出关于课程内容的一个主线条;通过典型习题的解析给学习数据结构课程的学生一些解题示范或启发。加强课程学习的实践环节,促进课程内容中各知识点与方法和技术的融汇贯通,为整个专业的学习打下一个坚实的基础。
本书的内容范围是根据计算机科学与技术专业本科《数据结构》课程的教学大纲确定的。全书共分十一章,包括绪论、线性表、栈和队列、串、数组与广义表、树、图、检索、排序、文件和模拟试题。在前十章中,都先对本章内容的学习要点、主要内容及知识点进行了概括总结,归纳出本章知识主线条,有利于学生复习总结和理解掌握;基础知识类题目是针对本章基本内容给出的复习和巩固各知识点的题目,分填空题、选择题和应用题三种题型给出;算法设计题都属于应用题的范畴,侧重于各种基本方法与技术的运用和算法分析与设计能力的训练;每章都给出了几道上机实验题目,每道实验都从题目、实验目的、主要采用的方法和技术、C语言实现程序几个环节给予解析,通过实验使学生了解并学会如何运用数据结构知识去解决现实世界的实际问题,具备较复杂程序的初步设计能力。第十一章给出了八套模拟练习题,主要是为了帮助学生在学完课程基本内容后可以自我检验学习效果;每套题目都有选择、填空、判断、应用和设计等各种题型,覆盖课程的主要知识点;题目的难度等级有易、较易、中、较难和难五种,可以适应于不同目的考前复习和模拟练习。
本书的读者对象是学习数据结构课程的本、专科学生,尤其是有志报考信息类各专业研究生的考生和参加软件水平与资格考试以及全国计算机等级考试三、四级考试的考生;也可作为高校教师和其他专业技术人员的参考用书。组织这本辅助教材的主要目的是为了帮助在校生学好数据结构这门课程,所以在使用过程中要注意以下四点:第一,要与课程学习内容同步使用。这样有利于教材中知识点的理解和掌握,有利于巩固和提高课堂教学效果。第二,切忌照抄照搬。算法的设计具有不惟一性,对算法设计类题目书中给出了一种或多种答案,要在学习、理解、领会的基础上自己动手设计算法并编写程序,这样才能获得好的效果。第三,要遵循循序渐进的原则。书中内容按知识结构分类组织,同类内容按典型到一般、由易到难的次序排列,读者最好能按次序阅读学习。但由于算法的讲解是独立构件,读者可以根据需要有选择地阅读。第四,要学会举一反三,触类旁通。课程内容中的知识点是有限的,但运用所学知识和方法技术解决实际问题则是无限的。重在掌握基本原理、基本方法和基本技术,并学以致用和灵活运用。考虑到考研考生和软件水平考试等考生的需要,在本书的内容组织上我们选择了一些难度较大的练习题;考虑到各级各类学校在教材使用中的不一致性,本书内容以知识模块结构组织而不针对某一具体教材,可以与几乎所有的数据结构教材配套使用。
本书是按清华大学出版社2003年巢湖计算机教学研讨会的讨论意见编写的。其中的第一、五、八、九章和第十一章由宁正元教授执笔,第二、三、四、六、七、十章由易金聪副教授执笔。全书由宁正元教授策划、统稿。在本书组稿期间,福州大学教授陈国龙博士提供了许多参考资料;西北大学教授康宝生博士提出过许多宝贵的意见和建议;福建农林大学计算机系李金铭主任和许多硕士生给予了许多支持帮助;清华大学出版社计算机事业部张龙主任和刘利编辑等给予了许多的支持和鼓励,在此作者一并致以深深的谢意。
由于时间仓促和作者水平所限,书中难免存在疏漏和错误,敬请业内同仁和广大读者不吝赐教。
作者
2004年12月