数据结构习题解析第0章

第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

结果不唯一

(2) 关节点为 ①、②、③、⑦、⑧ 【分析】这是有关重连通图的问题。深度优先搜索是一个需要重点掌握的方法，包括实例分析和算法。它是一个带回溯的探索问题，需要用递归算法求解。另外，关节点的判断准则有两个：其一为根至少有两个或两个以上的子女；其二为除根和叶结点外，其他结点的子女或子孙有指向该结点祖先的“回边”。掌握了这些概念，此问题就迎刃而解了。还需要了解：重连通图中任意两个顶点之间至少有两条路径相通，这有助于将非重连通图改为重连通图。

2、设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，14，20，17，30，12，18。试画出4路归并时的最佳归并树，并计算它的带权路径长度WPL。

【解答】因为 (13 - 1) % (4 - 1) = 12 % 3 = 0，所以不需要添加空段。最佳归并树为

WPL = ( 5 + 9 + 13 + 12 + 16 + 14 + 17 + 18 + 28 + 37 + 20 + 30 ) * 2 + 42 = 4 【分析】这是外排序中求最佳归并树问题，它是只有度为0和度为k的正则k叉树，满足条件n0 = (k-1)nk + 1，其中，n0是度为0的结点个数，nk是度为k的结点个数，k是归并路数。最佳归并树的构造仿照霍夫曼树，长度小的初始归并段离根远，长度大的初始归并段离根近。需要注意的是：当(n0-1) % (k-1) = m ? 0时，需要补充k-m-1个空的初始归并段，才能构成正则k叉树。

3、设散列表为HT[0..12]，即表的大小为m = 13。采用双散列法解决冲突。散列函数和再散列函数分别为： H0( key ) = key % 13; 注：%是求余数运算 Hi = ( Hi-1 + REV ( key + 1) % 11 + 1) ; i = 1, 2, 3, ?, m-1

其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37) = 73，REV(7) = 7等。若插入的关键码序列为2, 8, 31, 20, 19, 18, 53, 27。试画出插入这8个关键码后的散列表。

【解答】散列表 HT[0..12]，散列函数与再散列函数为 H0( key ) = key % 13；

Hi = ( Hi-1 + REV ( key + 1 ) % 11 + 1 ) % 13;

插入关键码序列为 { 2, 8, 31, 20, 19, 18, 53, 27 }

6

H0( 2 ) = 2, 比较次数为1 H0( 8 ) = 8, 比较次数为1 H0( 31 ) = 5, 比较次数为1 H0( 20 ) = 7, 比较次数为1

H0( 19 ) = 6, 比较次数为1 H0( 18 ) = 5, 冲突，H1 = 9，比较次数为2

H0( 53 ) = 1，比较次数为1 H0( 27 ) = 1，冲突，H1 = 7，冲突，H2 = 0，比较次数为3

插入8个关键码后的散列表

0 27 1 53 2 2 3 4 5 31 6 19 7 20 8 8 9 18 10 11 12

【分析】散列表长度和再散列函数的选取是关键。由于要求再散列函数计算出来的结果，即发生冲突时向后跨多大距离找下一个“空位”，必须与表的长度互质。因此为简化问题求解的难度，一般设表的长度为质数，本题设为13。其次，再散列函数是待散列对象的关键码的函数，计算结果的取值范围在1 ? n-1之间，其中n是表的长度。因此选取REV ( key + 1 ) % 11 + 1，其取值范围在1 ? 11之间，除1退化为线性探查外，其他都与13互质。需要注意的是，双散列法对表长度的要求不如二次探查法严格，那里要求表的长度一定是满足4j+3的质数且表的装载因子不超过0.5。此题容易出错的地方是应用再散列函数处理冲突时发生简单计算错误，一处出错，会影响后面一连串出错，一定要仔细。

0.2.5 综合算法题

有一种简单的排序算法，叫做计数排序（count Sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

(1) 给出适用于计数排序的数据表定义；

(2) 使用C++ 语言编写实现计数排序的算法；

(3) 对于有n个记录的表，关键码比较次数是多少？

【解答】

(1) 数据表定义

const int DefaultSize = 100; template class datalist template class Element { private: Type key; public:

Type getKey ( ) { return key; } }

template class datalist {

//用顺序表来存储待排序的元素，这些元素的类型是Type public:

7

//取当前结点的关键码 //将结点的关键码修改为x

void setKey ( const Type x ) { key = x; }

//关键码 //其它数据成员

field otherdata;

//数据表的前视声明 //数据表元素类的定义

datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } private:

Element * Vector; }

//存储待排序元素的向量 //最大元素个数与当前元素个数

int MaxSize, CurrentSize;

(2) 计数排序的算法 【方案1】

template

void countsort ( datalist& initList, datalist& resultList ) { int i, j, c; Type refer;

for ( i = 0; i < initList.CurrentSize; i++ ) { c = 0; }

resultList.CurrentSize = initList.CurrentSize; }

refer = initList.Vector[i].getKey ( ); for ( j = 0; j < initList.CurrentSize; j++ ) if (initList.Vector[j].getKey ( ) < refer ) c++; resultList.Vector[c] = initList.Vector[i]

【解答2】

template

void countsort ( datalist & initList, datalist & resultList ) { int *c = new int[initList.CurrentSize];

for ( int i = 0; i < initList.CurrentSize; i++ ) c[i] = 0; for ( i = 0; i < initList.CurrentSize-1; i++ ) }

for ( int j = i+1; j < initList.CurrentSize; j++ )

if (initList.Vector[j].getKey ( ) < initList.Vector[i].getKey ( )) c[i]++; else c[j]++;

resultList.Vector[ c[i] ] = initList.Vector[i];

for ( i = 0; i < initList.CurrentSize; i++ ) resultList.CurrentSize = initList.CurrentSize;

(3) 对于n个记录的表，解答1中关键码比较次数为n2，解答2中关键码比较次数为n(n-1)/2。

【分析】编写算法的题可能是学生比较棘手的问题，特别是在考试这样一个氛围，时间又短促，想编出一个好算法不太容易。一个建议是首先仔细阅读试题，了解它到底要你干什么。然后用一个简单的例子走一下，总结每一步向下走用什么语句，再做归纳。也可以按照结构化程序设计的方法，先搭框架，再根据例子填入细节。总之，要想又快又好地编写出算法，还要靠平时的基本训练，多做题，自主做题，各种题型都见过了，考试时自然文思泉涌，笔下就流畅了。

8

0.2.6 填空题

下面给出的是一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因退栈时需要区分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志，＝0，进入左子树，＝1，进入右子树。用栈ST保存结点指针ptr及其标志tag。top是栈顶指针。

void print ( BinTreeNode * t; Type &x ) { stack ST; int i, top; top = 0;

//置空栈

//寻找值为x的结点 ;

; //找到值为x的结点 ; i++ )

//进栈

while ( t != NULL && t->data != x || top != 0 ) {

while ( t != NULL && t->data != x ) { ① ST [top].ptr = t; ST [top].tag = 0; ② }

if ( t != NULL && t->data == x ) for ( i = 1;

else {

while ( top > 0 && ST [top].tag == 1 ) //未找到值为x的结点

top--; if ( top > 0 ) { ST [top].tag = 1; ④ }

} }

} /*print*/

//转向右子树 ; ③ cout << ST[i].ptr->data << endl;

(1) 请将缺失的语句补上 （8分）

①

② ③ ④

(2) 请给出对于右图所示的二叉树，使用上述算法搜索值为9的结点和值为10的结点的结果，以及在栈ST中的变化。（top是栈顶指针） 【解答】

(1) 请将缺失的语句补上

① top++

② t = t->leftChild ③ i <= top

9

④ t = ST[top].ptr->rightChild

(2) 搜索值为9的结点 → ④ ②

①

0 1 0 0

→ ⑦ ④ 0

② 0

① 0

ptr tag ptr tag

搜索值为10的结点 → ??0 → ??1 ⑦ 0 ⑦ 0 → ⑦ 1 ④ 1 ④ 1 ④ 1 → ④ 0 → ⑤ 0 ② 0 ② 0 ② 0 ② 0 → ② 1 ③ 0

① 0 ① 0 ① 0 ① 0 ① 0 ① 1

ptr tag ptr tag ptr tag ptr tag ptr tag ptr tag

→ ⑧ 0 → ⑧ 1 ⑤ 1 ⑤ 1 → ⑥ 0 → ⑥ 1 ③ 0 ③ 0 ③ 1 ③ 1 ① 1 ① 1 ① 1 ① 1 ptr tag ptr tag ptr tag ptr tag ptr tag

【分析】人们常说，读别人的程序不如自己重编。此话有一定道理。各人的思路不同，编程语言的运用和编程技巧的水平不同，编程风格不同，即使是几个人编写同一个功能的程序，可能面貌相差极大，读别人的程序自然困难很大。但现实是将来做技术支持必须读别人的程序。所以，必须有这方面的基本训练和要求。一个建议是：通过试题叙述阅读以了解思路，通过实例分析以了解程序结构，再通过实例跟踪以检验填空后的程序，从而得到最终的解答。

0.3 小结

数据结构课程是计算机专业的基础课程，是一门知识性、实践性都很强的课程。数据结构及算法编写与分析都是不容易的。学好它需要付出极大的劳动，在平时勤学多练。如果有碰运气或取巧的想法，十有八九通不过考试。有一次在中央电大直播课堂进行期末答疑，一位学员不问问题，在网上传来一句话：“救救我吧，我已经考了两次没通过了。”对此，只能为他遗憾。希望他能重新来过，把基础打扎实，考试才能顺利过关。就怕平时不看书，不做作业或抄别人的作业，到考试时照样不会，自然一次次通不过了。最后，祝愿同学们通过自己的勤奋努力，取得优良的成绩。 l

10

本文来源：https://www.bwwdw.com/article/2w7g.html