清华大学计算机系列教材 华 数据结构 大 习题解析 学 (用面向对象方法与C++语言描述) 计 112 算 10 机 8 系 殷人昆 徐孝凯编著 致 清华大学出版社 材 http://www.tup.tsinghuaedu.cn
前言 “数据结构”是有关计算技术及信息管理技术专业的一门必修的核心课程。“数据结构” 课程的任务是讨论在应用问题求解时数据的逻辑组织、在计算机中的存储实现以及相关操 作的算法，“数据结构”课程的目的是使学生掌握在实际问题解决过程中如何组织数据、如 何存储数据和如何处理数据的基本方法，为进一步学习后续课程，以及为以后从事软件开发 和应用打下坚实的基础。 本书是清华大学出版社出版的“清华大学计算机系列教材”《数据结构（用面向对象方法 与C++语言描述)》和“教育部人才培养模式和开放教育试点教材”《数据结构》的配套教 材，提供了学习“数据结构”的一些指导性建议和考试的样例。它给出主教材中绝大多数习 题的参考答案和分析，还针对基本概念补充了一些知识性的练习，对于复习和准备考试的学 生有一定参考价值。但对于正在学习“数据结构”课程的学生，应以掌握知识和培养能力为 主，不应过多地依赖现成的习题解答。本书只应作为一个参考，不应当作拐杖。 当前，数据结构的教授方法有两种。一种是注重数据结构本身的知识体系，认为“数据 结构”课程应以学生是否能掌握在应用开发中如何组织、存储、变换数据为主，使用什么语言 描述数据结构和算法都可以。持这种观点的教材多以类Pascal类C或其他伪码作为数据 结构和算法的描述工具。另一种是注重数据结构的工程应用，直接以某种可以在计算机上 实现的语言来描述数据结构和算法。随着软件开发技术的发展，后一种数据结构的教学方 法在国际上普遍得到认可。因为面向对象的软件分析和设计方法已经成为软件开发的主流 方法，如果学生在学习数据结构和程序设计的课程时养成一种动辄用面向过程的传统方法 解决问题的习惯，将来学习面向对象方法时将难以接受新的思维，或者不知如何着手，因此， 必须及早改变这种学习方式，从学习面向对象程序设计和用面向对象方法描述的数据结构 入手，培养学生用先进的方法来描述问题和解决问题的能力。 本书的主教材在清华大学计算机系已经讲授了3轮，在中央电大计算机应用专业也应 用了两年。从学生反映来看，是成功的。我们将根据在教学实践中取得的经验和暴露的问 题，不断改进教学体系和教学内容，增强实践环节，使“数据结构”课程能够紧跟国际发展，为 培养高水平计算机软件人员打下良好的基础。 本教材是基于多年来的教学实践整理成的，希望能对广大读者的学习起到促进作用。 但由于时间仓促和我们的水平所限，错误和疏漏在所难免，敬请读者提出宝贵意见。 作者 2002年1月 I
目录 第0章数据结构导论…… 0.1数据结构学习指导 0.1.1课程地位 0.1.2课程要求……………… 0.1.3课程学习指导…………… 0.2考试指导…… 0.2.1单选题 0.2.2判断题 0.2.3阋读理解题……… 15s 0.2.4简答题 U.2.综合算法题 0.2.6坷空题 0.3小结 1 第1章绪论 1.1复习提要 1.2难点与重点…… 1.3教材中习题的解析 1.4其他练习题…………… 第2章数组 2.1复习提要………………… 2.2难点与重点……… 2.3教材屮习题的解析… 2.4其他练习题………… 第3章链表 3.1复习提要 3.2难点与重点… 3.3教材屮习题的解析……… 3.4其他练习题 第4章栈和队列 4.1复习提要 76 4.2难点与重点 4.3教材中习题的解析 ·+
4.4其他练习题 第5章递归与广义表 5.1复习提要 !02 5.2难点与電点 5.3教材中习题的解析 5.4其他练习题 …………115 第6章树与森林………… 6.1复习提要 6.2难点与重点 6.3教材中习題的解析… 6.4其他练习题 第7章集合与搜索…… 7.I复勹提要 7.2难点与重点………… 7、3教材中习题的解析… 7.4其他练习题 5:司8 第8章图… 8.1复习提要 8.2难点与重点…… 8.3教材中习题的解析 8.其他练习题 ,,t. 第9章排序……… 复习提要 i98 9.2难点与重点 9,3教材中习题的解析 9.1其他练习题 第10章索引与散列 1复习提要 10.2难点与点… 10.3教材中习题的解析 10.4其他练匀题…… ……244
第0章数据结构导论 0.1数据结构学习指导 0.1.1课程地位 “数据结构”是计算杋科学与技术专业本科生的专业基础课程之一。用计算机解决何 实际问題都离不丌数据表示和数据处理,而数据表示和处理的核心问题之一是数据结构及 其实现这正是数据结构课程的基本内容。从这个意义上来说,数据结构课程在知识学 习和技能培养两个方面都是要求达到的目标,是理论和实践要求都相当高的课程。本课程 不仅为操作系统、数据库系统、编译厅法、计算机网络等后续课程提供了必要的知识基础.而 且也为计算机及其专业人员提供了必要的技能训练 对清华大学计算机系历届毕业生和部分研究生追踪调查显示:几乎所有的学生都认为 数据结构”是他们在学校里学过的最有用的课程之一,它也是国内外许多软件开发机构要 求考核的基本课程之一。由此可见“数据结构”这门课程的重要性 0.1.2课程要求 根据课程的教学大纲要求,“数据结枃”主要讨论在软件开发中如何进行数据结构和算 法的设计。因此,用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程 的重点,也是学生需要掌握的重点。面向对象方法以及结构化技术都是建立高质量软件的 技术,通过“数据结构”课程的学习和实践,可以深对这些先进软件开发方法的理解和体 会。因此,“数据结构”误程的任务是按照软件工程思想,介绍用面向过程和而向对象方法进 行数据设计和程序设计的基本思想,在必要的课程实践中逐步熟练掌握 通过木课程的学习,应达到知识和技能两方面的日标: (1)知识方面:从数据结构的类定义和对象的使用、存储表示和操作的实现这两个层 次,系统地学习和掌握常用的基本数据结构(包括数组顺序表、多项式、字符出、链表、栈与 队列、优先级队列、广义表、树与森林、二叉树、堆、集合、图、搜索结构、索引结构、散刎结构 等)及其不同的实现,了解并掌握分析、比较和选择不同数据结构、不同仔储结构、不冋算法 的原则和方法,为后续课程的学习打好基础 (2)技能方面:系统地学习和掌握对象类的设计方法和面向对象的程序设计风格,在 不同的存储结构上实现的算法的设计想,从屮体会利掌握选择结构的方法和算法设计的 思考方式及技巧,提高分析问题和解决问题的能力