清华大学计算机系列教材 华 数据结构 大 习题解析 学 (用面向对象方法与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)技能方面:系统地学习和掌握对象类的设计方法和面向对象的程序设计风格,在 不同的存储结构上实现的算法的设计想,从屮体会利掌握选择结构的方法和算法设计的 思考方式及技巧,提高分析问题和解决问题的能力
0.1.3课程学习指导 学牛在初学时往往感到“数据结构”课程内容多、面授容易接受,但自学难度大,特别足 在编写小程序时常常无从者手。为改善自学效果以有限的时问和精力学好这门课程,应当 注意以下儿点 (1)注意先修课程的知识准备 在学习今课程之初,必须注意复习在用CC+程序设计亡编写小程序时的谙法规 则和方法,为本谍程的学习打下基础 ℃语言与 Pasca浯言一样,是一种面向过程的语言、C程序结构的特点是遵循“输入 处理输出”的模式来解决问题。(+一保留了C的亩向过程编程的成分,但由于引入了面 向对象的成分,在数据组织方囿很自然地实现了抽象数据类型的思想、并利用模板机制实现 了软件复用。在复习CC++语;时应注意 ①函数的概念和相关问题。包括函数类型,函数特征,函数名重载,函数参数的传递 特别注意传值参数和引用参数在使用上的别。还有函数返回值的1种类型之间的区别。 ②函数中局部变量的作用域,它的创建和回收的有效范围。特别注意在函数中对局部 变量的任何改变,因为在退出函数过稈时局部变量被释放而不能当作数返回值返回 ③类和对象的定义方式。特别注意为保证信息隐蔽,对类屮的所有数杯成员和成员 数将规定其存取级别: public, privale和 protected。放在 public域中表示对于其他程序都 是可用的;放在 privale域中表小对于其他程序是不叮用的,对于其派生类也是不可用的;放 在 protected域中表示对于其他程序是不可用的,对于其派生类是可用的 ④在C+十中的动态存储分和动态存储叫收方式 ⑤类的实例对象的建立和同收方式,构造函数和析构函数的使用,对象数据成初始 化的方式等。特別注意成员函数的作用或 ⑥在CC+十中的输入输出流文件的定义和使用。特别注意文件的连接, strean类 和 offstream类,文件的打开与关闭、文件模式的作用。 O友元类与友元函数的定义和使用 ⑧模板类的定义和模板类的使用 (2)在学习“数据结构”时,要注意知识体系 结构谍程中的知识本身具有良好的结构性。从总体上来说,课程的七嬃内容是 绕着数组、线性表、顺序表、链表、栈、队列、优先级队列、广义表、树与二义树、图、集合与搜索 结构、索引与散列结构等常用的数据结构和递归、排序等常用算法来组织的。其中有些结构 是面向应用的,有些结构是面向实现的。在课文中要注意这两个层次以及它们之间的联系 为了完全了解数据结构的机制以及为便于数据结构的复用课文中对轷一个结构都做 了较为完整的介绍,学习者最好将课文中介绍的每一结构都能以“模板类”和“模板类的成员 函数的实现”的形式存于“,h”文件中,并在后续的算法或类的实现中直接复用它们 3)注意比较 在学习中应当注意从“橫向”和“纵向”进行对比以加深埋解。纵向对比将种结构与它 的各种不同的实现加以比较,从继承的角度或从聚合的角度建立类的实例之间的联系;横向
对比包括具有相同逻辑结构的不同数据结构(如线性表、栈、队列、优先级队列和串)的比较 具有相同功能的不问算法的比较等,了解类的层次结构和利用包的概念将不同语义的类关 联起来,从而加深对抽象类和虚函数的使用 (1)注意复习和反复阅读 有些内容在初读时难以透彻理解或熟练掌据,或者看起来似乎明白了,但用的时候容易 犯暈,在继续学习的过程中如遇到或用到有关内容时,应当及时复习或电读,这往往能够化 难为易,温故知新 (5)充分利用考核说明及有关学习的难点和重点的说明 在进入每一帝学习之前或在每一章学习之后,仔细阅读考核说明和各章学习的难点和 重点·有助于集中思路和自我检查。如自我检查的效果不理想,千万不要将就,更不要急于 向后读应回过头来把握住要求,有计划地重读课本,重看学习导引,重做习题,直到本章内 容掌揭为止。 (6)注意循斥渐进 在进入具体内容(如类的定义和类的成员函数的实现)之前,首先领会基本概念、基本思 想这一点极为重要。特别是在阅读算法之前,一定要先弄清其基不思想、基本骤,这将大 大降低理解算法的难度。如果读“懂”了算法而不知其基本思想,仍不算是真懂。可以通过 事例学习以加深理解。 (7)注意练习 习题练习是课程的基本婴求之一。只看书不做题不可能真正学会有关知识更不能达 到技能培养的目的。另一方面,做题也是自我检查的重要手段。此外,在做算法设计型的习 题时应优先考虑数据结构的定义,可直接使用以前定义的类和相应的操作(成员函数),综 合已学过的知识以提高编程的能力。为此,可以逐渐积累学过的数据结构的实现,以模板 类的方式标准化,以方便在后缤学习中复用它们。这样做所获得的回报是相当丰厚的,但不 要指望立即获得回报。 (8)算法思路的理解 算法及其思想、评价是本课程的重点之一,在课文中占了相当大的比例。在学习每一个 算法时,建议首先理解问题的要求,在此基础上利用一个事例来模拟间题的求解.自已试着 构思一下解题的思路能够写出来更好。然后再阅读算法在读懂之后,不要急于往下进行 而应停下来思考下列问题:该算法从逻辑上可以划分为哪几个部分(步骤)?每一部分的功 能是什么?这一功能又是如何实现的?能否用别的方法实现?各部分之间的关系如何?如 果间题的要求有所不同,应当如何修改算法? 将思考的结果记载下来,在复习时会有很大帮助。另外,这样的分析也是灵活运用所学 知识的关键。 (9)努力培养算法设计的能力 在课程学习中最令学习者感到吃力的是设计和編写算法。算法的设计水平是软件设计 的基础,要提高算法的设计水平,首先需要掌握问题要求的基本内容通过反复体会和练习 来实现。通常需要根据具体问题的要求选择合适的数据结构,设计有效的算法,有条件的 学生应当在机器七多做练小
(10)及时总结 在学习完每-节、章后,要及时地进行总结,用简短的文宇记录这部分的内容,尽可能用 自己的话复述一遍。在本课程全部学完后还应对本课程进行全面系统的复习和总结,认真 做模拟试卷,在进行总复习叶,可通过对比各种数据结构的异同和它们之间的相互关系,加 深对各种数据结构的理解。 在复习时,可以按所记录的要点反向地进行,即依据要点找出其体内容。按这样的方 法进行,也许还能够节省时间,提高学习效果 最后应当强调的是,学习方法主要靠自己摸索,多总结,多思考勤上机,勤交流,这是把 数据结构”这门课程真正学好的关键 0.2考试指导 数据结构考试可能的题型有以下5种: 单选题:给出一些有关数据结构性质、特点及一些简单算法性能的不完全叙述.要求学 生从题后给出的供选择的答案巾选择合适的答案,补足这些叙述 填空题:给出程序说明及一段部分语句缺失的程序,让学生补充成为完整的程序 简答题:应用作图方法或简单计算,使用给定数据建立或操作一些数据结构: 判断題:绐出-些有关数据结构或算法的叙述,要求学生回答这些叙述正确与否: 综合算法题:给出算法设计要求·编制出部分算法程序·用来考察几个知识点的综合 应用 下面根据各种题型举例分析,说明解题方法及考试时的注意事项。 0.2.1单选题 【例L1】从供选择的答案中选出正确的答案,将其编号填入下列叙述中的()内。 (1)向一个有127个元素的顺序表中插人一个新元素并保持原米顺序不变,平均要移 动(A)个元素。 (2)设有个二维数组Am][n,假设A[OJ[0]存放付置在614,4[227存放位置 在6760,每个元素占一个空问则A15]在(B)位置,,長明用10进数表示。 (3)一个有序顺序表有255个对象,采用顺序搜索法查表,平均搜索长度为( (4)含5个结点(元索值均不相同)的二叉搜索树有(D)种 5)在分析折半搜索的性能时常加入失败结点,即外结点,从而形成扩充的二叉树。若 设失败结点所在层次为l,那么搜索失败到达失败结点时所做的数据比较次数是(E) (6)设有一个含200个麦项的散列表,用线性探查法解决冲褒,按关键码查询时找到一 个表项的平均探耷次数不超过1.5,则散列表项应能够至少容纳(F)个表项。(设搜索 成功的平均搜素长度为Sn={1+1(1-a)}:2,其中a为装填子) (7)n个顶点的连通图至少有(G)条边
(8)一个二义树按顺序方式存储在一个一维数组中,如将 0 6789C11121311 A B 则结点E在二叉树的第(H)层 供选择的答案 A.①8 ②63.5 ③63 ①69 ②6261 ③709c:④724 C.①128 ③126 ④255 D.①54 ③36 ④65 E.①l,+1 ③l1-1 ①l 676 ①n-1 ③n+1 ③3 【解答】A.②B.③C.①D.②E.④ 分析】此类题主要是考核学对基本知识的掌握程度,涉及范围较广。所有各章内容都可 能牵涉到。主要考察对各种数据结构的定义、特点、性质(包括公式计算)、主要操作的性能 分析(包括算法中多趟执行时每一趟的通项公式),因此要求复时必须仔细看书。不提倡 死记硬背,但要学会推导 0.2.2判断题 【例2.1】判断下列各个叙述的正误。对,在题号前的括号内填入“√”;错,在题号前的折号 内填入 ()(1)有丌个结点的不同的二叉树有n!棵 ()(2)直接选择排序是一种不稳定的排序方法 )(3)在2048个π不相同的关键中选揉最小的个关键码.用堆排序比用锦标赛排 序更快。 ()(4)当3阶B_树中有255个关键码时,其最大高度(包括尖败结点层)不超过8 〈)(5)一棵3阶B树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶B_树 )(6)在川散列表存储关鍵码集合时,可以用双散列法寻找下个空桶。在没计再散列 函数时,要求计算出的值与表的大小m互质。 ()(7)在只有度为0和度为k的结点的k叉树屮,设度为0的结点有n,个.度为k的结 点有n个,则有n:-n4+1。 ()(8)折半搜索只适用于有序表,包括有序的顺序表和有序的链表。 【解答】(1) 5)×(5)√(7)x 【分析】此类题要求对课文各章中许多细节比较清楚。事实1,数据结构课程屮讲到的许多 数据结构的细节是最基础的知识,将这些内谷理解透彻了,以后学生在自主开发软件时将会 得到回报的。在解答此类题肘,不要立即提笔就答.应当把题看完,分析前后叙述是否矛盾
是否叙述中有漏洞,必要时,还需要做·下简单的推导。 0.2.3阅读理解题 【例3.1】说明下列递归过程的功能 int unknown( Bin Node.t) 指针t是二叉树的枨指针 if(t=" NUlL)return 0: if(t->leftChild=--NCLL &&1->>rightChild= NUI. 1. )return I Ieft+ unknown(r.".rghihi 【解答】计算二叉树的叶结点的个数。 【分析】此类题是递归算法问题,一般要求读懂它即可。但要理解它首先需要掌握递归算決 的结构,以及相应问题的背景。有时需要用一个简单的例子来帮助理解 0.2.4简答题 【例4.1】如下所示的连通图,请画出: (1)以顶点①为根的深度优先生成树 (2)如果有关节点请找出所有的关节点 【解答】 ()该连通图从①出发做深度优先搜索,得到的深度优先生成树为 结果不唯一 (2)关节点为①②、③、⑦、⑧ 【分析】这是有关重连通图的问题。深度优先搜索是一个需要重点掌握的方法,包括实例分