第0章 数据结构导论
0.1 数据结构学习指导
0.1.1 课程地位
《数据结构》是计算机科学与技术专业本科生的专业基础课程之一。用计算机解决任何实际问题都离不开数据表示和数据处理，而数据表示和处理的核心问题之一是数据结构及其实现——这正是数据结构课程的基本内容。从这个意义上来说，数据结构课程在知识学习和技能培养两个方面都处于关键性地位，是理论和实践要求都相当高的课程。本课程不仅为操作系统、数据库系统、编译方法、计算机网络等后续课程提供了必要的知识基础，而且也为计算机及其专业人员提供了必要的技能训练。 在对清华大学计算机系历届毕业生和部分研究生追踪调查显示，几乎所有的同学都认为《数据结构》是他们在学校里学过的最有用的课程之一，也是国内外许多软件开发机构要求考核的基本课程之一。由此可见《数据结构》这门课程的重要性。
0.1.2 课程要求
根据课程的教学大纲要求，《数据结构》主要讨论在软件开发中如何进行数据结构和算法的设计。因此，用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程的重点，也是学生需要掌握的重点。面向对象方法以及结构化技术都是建立高质量软件的技术，通过《数据结构》课程的学习和实践，可以加深对这些先进软件开发方法的理解和体会。因此，《数据结构》课程的任务是按照软件工程思想，介绍用面向过程和面向对象方法进行数据设计和程序设计的基本思想，在必要的课程实践中逐步熟练掌握。 通过本课程的学习，应达到知识和技能两方面的目标： 1、知识方面：从数据结构的类定义和对象的使用，以及存储表示和操作的实现两个层次，系统地学习和掌握常用的基本数据结构（包括数组、顺序表、多项式、字符串、链表、栈与队列、优先级队列、广义表、树与森林、二叉树、堆、集合、图、搜索结构、索引结构、散列结构等）及其不同的实现，了解并掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法，为后续课程的学习打好基础。 2、技能方面：系统地学习和掌握对象类的设计方法和面向对象的程序设计风格，在不同的存储结构上实现的算法的设计思想，从中体会和掌握选择结构的方法和算法设计的思考方式及技巧，提高分析问题和解决问题的能力。
0.1.3 课程学习指导
学生在初学时往往感到《数据结构》课程内容多、面授容易接受，但自学难度大，特别是在编写小程序时常常无从着手。为以有限的时间和精力学好这门课程。应当注意以下几点，有助于改善自学效果。 1、注意先修课程的知识准备 在学习本课程之初，必须注意复习在用C / C++ 程序设计语言编写小程序时的语法规则和方法。为本课程的学习打下基础 C语言与Pascal语言一样，是一种面向过程的语言。C程序结构的特点是遵循“输入-处理-输出”的模式来解决问题。C++ 保留了C的面向过程编程的成分，但由于引入了面向
1
对象的成分，在数据组织方面很自然地实现了抽象数据类型的思想，并利用模板机制实现了软件复用。所以在复习C / C++ 语言时，要注意： (1) 函数的概念和相关问题。包括函数类型，函数特征，函数名重载，函数参数的传递。特别注意传值参数和引用参数在使用上的区别。还有函数的返回值的4种类型之间的区别。 (2) 函数中局部变量的作用域，它的创建和回收的有效范围。特别注意在函数中对局部变量的任何改变，因在退出函数过程时局部变量被释放而不能当作函数返回值返回。 (3) 类和对象的定义方式。特别注意为保证信息隐蔽，对类中的所有数据成员和成员函数将规定其存取级别：public, private和protected。放在public域中表示对于其他程序都是可用的；放在private域中表示对于其他程序是不可用的，对于其派生类也是不可用的；放在protected域中表示对于其他程序是不可用的，对于其派生类是可用的。 (4) 在C++ 中的动态存储分配和动态存储回收方式。 (5) 类的实例对象的建立和回收方式，构造函数和析构函数的使用，对象数据成员初始化的方式等。特别注意成员函数的作用域。 (6) 在C/C++ 中的输入/输出流文件的定义和使用。特别注意文件的连接、ifstream和ofstream类，以及文件的打开与关闭、文件模式的作用。 (7) 友元类和友元函数的定义和使用。 (8) 模板类的定义和模板类的使用。 2、在学习《数据结构》时，要注意知识体系 数据结构课程中的知识本身具有良好的结构性。从总体上来说，课程的主要内容是围绕着数组、线性表、顺序表、链表、栈、队列、优先级队列、广义表、树与二叉树、图、集合与搜索结构、索引与散列结构等常用的数据结构和递归、排序等常用算法来组织的。其中有些结构是面向应用的，有些结构是面向实现的。在课文中要注意这两个层次以及它们之间的联系。 为了完全了解数据结构的机制以及为便于数据结构的复用，课文中对每一个结构都做了较为完整的介绍，学习者最好将课文中介绍的每一结构都能以“模板类”和“模板类的成员函数的实现”的形式存于“.h”文件中，并在后续的算法或类的实现中直接复用它们。 3、注意比较 在学习中应当注意从“横向”和“纵向”进行对比以加深理解。纵向对比将一种结构与它的各种不同的实现加以比较，从继承的角度或从聚合的角度建立类的实例之间的联系；横向对比包括具有相同逻辑结构的不同数据结构（如线性表、栈、队列、优先级队列和串）的比较，具有相同功能的不同算法的比较等，了解类的层次结构和利用包的概念将不同语义的类关联起来，从而加深对抽象类和虚函数的使用。 4、注意复习和反复阅读 有些内容在初读时难以透彻理解或熟练掌握，或者看起来似乎明白了，但用的时候容易犯晕。在继续学习的过程中如遇到或用到有关内容时，应当及时复习或重读，这往往能够化难为易，温故知新。 5、充分利用考核说明及有关学习的难点和重点的说明 在进入每一章学习之前或在每一章学习之后，仔细阅读考核说明和各章学习的难点和重点，有助于集中思路和自我检查。每一章自我检查的效果不理想时，千万不要将就，更不要急于向后读，应回过头来把握住要求，有计划地重读课本，重看学习导引，重做习题，直到本章内容掌握为止。 6、注意循序渐进 在进入具体内容（如类的定义和类的成员函数的实现）之前，首先领会基本概念、基本思想，这一点极为重要。特别是在阅读算法之前，一定要先弄清其基本思想、基本步骤，这将大大降低理解算法的难度。如果读“懂”了算法而不知其基本思想，仍不算是真
2
懂。可以通过事例学习以加深理解。 7、注意练习 习题练习是课程的基本要求之一。只看书不做题，不可能真正学会有关知识，更不能达到技能培养的目的。另一方面，做题也是自我检查的重要手段。此外，在做算法设计型的习题时，应优先考虑数据结构的定义，可以直接使用以前定义的类和相应的操作（成员函数），综合已学过的知识，以提高编程的能力。为此，可以逐渐积累学过的数据结构的实现，以模板类的方式标准化，以方便在后续学习中复用它们。面向对象软件工程告诉我们，这样做所获得的回报是相当丰厚的，但不要指望立即获得回报。 8、算法思路的理解 算法及其思想、评价是本课程的重点之一，在课文中占了相当大的比例。在学习每一个算法时，建议首先理解问题的要求，在此基础上利用一个事例来模拟问题的求解，自己试着构思一下解题的思路，能够写出来更好。然后再阅读算法，在读懂之后，不要急于往下进行，而应停下来思考下列问题：该算法从逻辑上可以划分为哪几个部分（步骤）？每一部分的功能是什么？这一功能又是如何实现的？能否有别的方法实现？各部分之间的关系如何？如果问题的要求有所不同，应当如何修改算法？ 将思考的结果记载下来，在复习时会有很大帮助。另外，这样的分析也是灵活运用所学知识的关键。 9、努力培养算法设计的能力 在课程学习中最令学习者感到吃力的是设计和编写算法。算法设计水平是软件设计的基础。要提高算法的设计水平，首先需要掌握问题要求的基本内容，通过反复体会和练习来实现。通常需要根据具体问题的要求，选择合适的数据结构，设计有效的算法。有条件的学生应当在机器上多做练习。 10、及时总结 在学习完每一章、节后，要及时地进行总结，用简短的文字记录这部分的内容，尽可能用自己的话复述一遍。在本课程全部学完后应对本课程进行全面系统的复习和总结，认真做模拟试卷。在进行总复习时，可通过对比各种数据结构的异同和他们之间的相互关系，加深对各种数据结构的理解。 在复习时，可以按所记录的要点反向地进行，即依据要点找出其具体内容。按这样的方法进行，也许还能够节省时间，提高学习效果。 最后应当强调的是，学习方法主要靠自己摸索，多总结，多思考，勤上机，勤交流，是把数据结构这门课程真正学好的关键。
0.2 考试指导
数据结构考试可能的题型有以下5种： ? 单选题：给出一些有关数据结构性质、特点及一些简单算法性能的不完全叙述，要求学生从题后给出的供选择的答案中选择合适的答案，补足这些叙述。 ? 填空题：给出程序说明及一段部分语句缺失的程序，让学生补充成为完整的程序。 ? 简答题：应用作图方法或简单计算，使用给定数据建立或操作一些数据结构。 ? 判断题：给出一些有关数据结构或算法的叙述，要求学生回答这些叙述正确与否。 ? 综合算法题：给出算法设计要求，编制出部分算法程序，用来考察几个知识点的综合应用。 下面根据各种题型举例分析，说明解题方法及考试时的注意事项。
0.2.1单选题
3
从供选择的答案中选出正确的答案，将其编号填入下列叙述中的( )内。
(1) 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ A ）个元素。
(2) 设有一个二维数组A[m][ n]，假设A[0][0] 存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5] 在（ B ）位置，(10)表明用10进数表示。 (3) 一个有序顺序表有255个对象，采用顺序搜索法查表, 平均搜索长度为（ C ）。 (4) 含5个结点（元素值均不相同）的二叉搜索树有（ D ）种。
(5) 在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么搜索失败到达失败结点时所做的数据比较次数是（ E ）。
(6) 设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（ F ）个表项。（设搜索成功的平均搜索长度为 Snl＝{ 1 + 1 / (1 -α) } / 2, 其中α为装填因子） (7) n个顶点的连通图至少有（ G ）条边。 (8) 一个二叉树按顺序方式存储在一个一维数组中, 如图
0 A 1 B 2 C 3 D 4 5 E 6 F 7 8 G 9 10 11 H 12 13 I 14 J
则结点E在二叉树的第（ H ）层。 供选择的答案
A : ① 8 ② 63.5 ③ 63 ④ 7 B : ① 692(10) ② 626(10) ③ 709(10) ④ 724(10) C : ① 128 ② 127 ③ 126 ④ 255 D : ① 54 ② 42 ③ 36 ④ 65 F : ① li +1 ② li +2 ③ li - 1 ④ li G : ① 400 ② 526 ③ 624 ④ 676 I : ① n-1 ② n ③ n+1 ④ 0 J : ① 1 ② 2 ③ 3 ④ 4
【解答】A : ② B : ③ C : ① D : ② E : ④ F : ① G : ① H : ② 【分析】此类题主要是考核学生对基本知识的掌握程度，涉及范围较广。所有各章内容都可能牵涉到。主要考察对各种数据结构的定义、特点、性质（包括公式计算）、主要操作的性能分析（包括算法中多趟执行时每一趟的通项公式），因此要求复习时必须仔细看书。不提倡死记硬背，但要学会推导。
0.2.2 判断题
[判断下列各个叙述的正误。对，在题号前的括号内填入\?\；错，在题号前的括号内填入\?\
( ) (1) 有n个结点的不同的二叉树有n！棵。 ( ) (2) 直接选择排序是一种不稳定的排序方法。
( ) (3) 在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。
4
( ) (4) 当3阶B_树中有255个关键码时，其最大高度（包括失败结点层）不超过8。 ( ) (5) 一棵3阶B_树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B_树。 ( ) (6) 在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。
( ) (7) 在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有 n0 = nk + 1。
( ) (8) 折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
【解答】(1) ? (2) ? (3) ? (4) ? (5) ? (6) ? (7) ? (8) ??【分析】此类题要求对课文各章中许多细节比较清楚。事实上，数据结构课程中讲到的许多数据结构的细节是最基础的知识，将这些内容理解透彻了，以后学生在自主开发软件时将会得到回报的。在解答此类题时，不要立即提笔就答，应当把题看完，分析前后叙述是否矛盾，是否叙述中有漏洞，必要时，还需要做一下简单的推导。
0.2.3 阅读理解题
说明下列递归过程的功能。
int unknown ( BinTreeNode * t ) { //指针t是二叉树的根指针。 if ( t == NULL ) return 0; else
if ( t->leftChild == NULL && t->rightChild == NULL ) return 1; else return unknown ( t->leftChild ) + unknown ( t->rightChild ); }
【解答】计算二叉树的叶结点的个数。 【分析】此类题是递归算法问题，一般要求读懂它即可。但要理解它首先需要掌握递归算法的结构，以及相应问题的背景。有时需要以一个简单的例子来帮助理解。
0.2.4 简答题
1、如下所示的连通图，请画出 (1) 以顶点①为根的深度优先生成树；
(2) 如果有关节点，请找出所有的关节点。
【解答】
(1) 该连通图从①出发做深度优先搜索，得到的深度优先生成树为：
5