数据结构(Java版)-习题解答与实验指导.doc

1、数据结构（Java版）习题解答与实验指导目录第1章 绪论11.1 数据结构的基本概念11.2 算法2第2章 线 性 表32.1 线性表抽象数据类型32.2 线性表的顺序存储和实现42.2.1 线性表的顺序存储结构42.2.2 顺序表42.2.3 排序顺序表62.3 线性表的链式存储和实现72.3.1 单链表7【习题2-8】单链表结点类问题讨论。7【习2.1】 使用单链表求解Josephus环问题。9【习2.2】 集合并运算，单链表深拷贝的应用。102.3.2 双链表12【习2.3】 循环双链表的迭代方法。13【习2.4】 循环双链表合并连接。14第3章 串153.1 串抽象数据类型153.2

2、串的存储和实现153.2.1 串的存储结构153.2.2 常量字符串类15【习3.1】 C/C+语言，string.h中的strcpy()和strcat()函数存在下标越界错误。15【思考题3-1】逆转String串，分析算法效率。17【实验题3-1】MyString类，比较串大小，忽略字母大小写。17【例3.2思考题3-2】MyInteger整数类，返回value的radix进制原码字符串。18【实验题3-9】浮点数类。193.2.3 变量字符串类20【实验题3-11】删除变量串中的所有空格。 4-样卷203.3 串的模式匹配213.3.1 Brute-Force模式匹配算法213.3.2

3、模式匹配应用22【思考题3-4，实验题3-13】MyString类，replaceAll(pattern,s)改错。223.3.3 KMP模式匹配算法22第4章 栈和队列264.1 栈264.2 队列274.3 递归29【习4.1】 打印数字塔。29第5章 数组和广义表315.1 数组315.2 特殊矩阵的压缩存储325.2.1 三角矩阵、对称矩阵和对角矩阵的压缩存储325.2.2 稀疏矩阵的压缩存储335.3 广义表35第6章 树和二叉树366.2 二叉树366.3 线索二叉树406.4 Huffman树446.5 树的表示和实现45第7章 图467.1 图及其抽象数据类型467.2 图的表

4、示和实现467.3 图的遍历487.4 最小生成树507.5 最短路径51第8章 查 找538.1 查找的基本概念538.2 二分法查找548.4 散列558.5 二叉排序树56【实验8-1】判断一棵二叉树是否为二叉排序树，改错。56第9章 排序579.1 插入排序579.2 交换排序589.3 选择排序599.4 归并排序609.5 线性表的排序算法609.5.1 顺序表的排序算法60【实验题9-2】归并两条排序顺序表。60第10章 综合应用设计6210.1 Java集合框架62【习10.1】 Collection整数集合元素求和。6210.2 课程设计补充选题63- III -第1章 绪论

5、目的：勾勒数据结构课程的轮廓，了解本课程的目的、性质和主要内容。内容：数据结构和算法概念，算法设计与分析。要求：理解数据结构基本概念，理解抽象数据类型概念；熟悉算法设计和分析方法。重点：数据的逻辑结构和存储结构概念。难点：抽象数据类型，链式存储结构，算法分析方法。实验：简单算法设计，回顾Java语言的基本语法和面向对象基本概念。1.1 数据结构的基本概念习1-2 什么是数据结构？数据结构概念包括哪些部分？习1-3 数据的逻辑结构主要有哪三种？三者之间存在怎样的联系？习1-4 数据的存储结构主要有哪些？各有何特点？习1-5 不同数据结构之间共同的操作有哪些？【答】上述1-11-4问题说明如下。

6、数据结构，指数据元素之间存在关系的数据元素集合。 数据结构包含数据的逻辑结构、存储结构和数据操作三方面概念。 数据的逻辑结构主要有三种：线性结构、树结构和图结构，线性结构是树的特例，树结构是图的特例。 数据的存储结构有两种：顺序存储结构和链式存储结构，两者特点分别是数据元素数据连续存储、分散存储。 数据操作主要有：求数据元素个数，访问、查找、插入、删除数据元素等。数据结构概念描述如图1.1所示。图1.1 数据结构概念习1-6 数据结构与数据类型有什么区别？为什么要将数据结构设计成抽象数据类型？【答】数据结构与数据类型概念本质相同，使用数据类型描述数据特性，使用数据结构描述数据之间关系。将数据结

7、构设计成抽象数据类型，是为了“定义和实现相分离”，这也是数据类型的特点。1.2 算法习1-8 什么是算法？怎样描述算法？怎样衡量算法的性能？ 【答】算法是对问题求解过程的一种描述，是为解决一类问题给出的一个确定的、有限长的操作序列。算法特征包括：有穷性、确定性、输入、输出和可行性。可以采用自然语言或伪码描述算法的设计思想，采用程序设计语言实现算法。采用渐进分析法衡量算法性能，用时间复杂度O(f(n)表示所花费时间的量级，即时间效率；用空间复杂度O(S(n)表示算法执行过程中所需要的额外空间。第2章 线 性 表目的：实现线性表抽象数据类型。内容：将线性表的顺序存储结构和链式存储结构实现分别封装成

8、顺序表类、单链表类、循环双链表类等，比较这两种实现的特点以及各种基本操作算法的效率。要求：理解线性表抽象数据类型，掌握顺序和链式存储结构实现线性表的方法。重点：顺序表、单链表、循环双链表等线性表设计训练。难点：使用对象引用方式实现链式存储结构，改变结点间的链接关系。实验：掌握单链表的遍历、插入、删除、复制等操作算法，熟悉循环单链表、双链表和循环双链表的结构和基本操作。掌握MyEclipse集成开发环境的程序调试技术。2.1 线性表抽象数据类型2-1 什么是线性表？线性表主要采用哪两种存储结构？它们是如何存储数据元素的？各有什么优缺点？画出线性表的各种存储结构示意图。它们是否是随机存取结构？为什

9、么？【答】 线性表是数据元素之间具有线性关系的一种线性结构，对线性表的基本操作主要有获得元素值、设置元素值、插入、删除、查找、替换和排序等，插入和删除操作可以在线性表的任意位置进行。 线性表可以采用顺序存储结构和链式存储结构表示。线性表()的两种存储结构见教材图1.4所示。线性表的顺序存储结构（顺序表）用一组连续的存储单元顺序存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同。顺序表的特点是数据元素连续存储，元素的存储地址是它在线性表中位置i的线性函数，计算一个元素地址花费常量时间，即存取任何一个元素的时间复杂度是O(1)。因此，顺序表是随机存取结构，这是顺序表最大的

10、优点。顺序表缺点是插入或删除操作效率低，每插入或删除一个元素平均需要移动线性表一半元素。线性表的链式存储用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。特点是数据元素分散存储，优点是插入或删除操作不需要移动其他元素；缺点是，线性表的链式存储结构不是随机存取结构，获得第i个元素地址的时间复杂度是O(n)，因为线性表的链式存储结构（单链表）由若干结点组成，每个结点采用指针域保存其后继结点的地址，获得第i个元素地址平均需要遍历单链表一半结点。 第2章线性表存储结构及实现的各种类描述如图2.1所示。图2.1 线性表的存储结构

11、2.2 线性表的顺序存储和实现2.2.1 线性表的顺序存储结构2-2 解释顺序存储结构的线性表（顺序表）与数组在概念上的差别。 【答】数组是高级程序设计语言中的一种构造数据类型，具有存储单元连续的特点。顺序表利用数组的这个特点，将顺序表中的数据元素在数组中连续存放，以数据元素的存储位置体现线性表数据元素之间的逻辑关系，所以数组是实现顺序表的基础。虽然数组的存储单元是连续的，但数组元素不一定连续。而用数组实现顺序表时，数据元素必须连续存放，否则无法体现出线性表中数据元素之间的前驱和后继关系。习2-4 为什么顺序表的插入和删除操作必须移动元素？平均需要移动多少元素？【答】顺序表中数据元素连续存储，

12、元素之间没有空位置，逻辑上相邻的数据元素在存储位置上也相邻。因此，插入数据元素时，必须将指定位置之后的数据元素向后移动，以留出空位置；删除数据元素时，必须将删除位置之后的数据元素向前移动，以填补空位置。2.2.2 顺序表【思考题2-3】 SeqList类如果声明get(i)方法如下，与返回类型为T有何区别？ public Object get(int i) /返回第i个元素，0in。若i越界，返回null【答】 SeqList类如果声明get(i)方法如下，返回类型为Object。public Object get(int i) /返回第i个元素，0i=0 & ithis.n) return

13、this.elementi; /返回数组元素elementi引用的对象 return null;上述声明的调用语句如下：SeqList list = new SeqList(n); /顺序表元素类型是字符串Object obj = list.get(0); /父类Object对象obj引用子类Integer的实例，类型多态obj.toString() /obj调用Object类声明且被子类覆盖的方法，运行时多态obj.intValue() /编译错，obj不能调用Integer类的成员方法(T)obj).intValue() /(T)obj是Integer类的对象此时，obj对象只能调用Obj

14、ect类声明且被子类覆盖的方法，只有toString()和equals()方法，表现出运行时多态，实际执行obj引用实例所属Integer类提供的方法实现；而不能调用Integer类声明的成员方法。 SeqList类声明get(i)方法如下，返回类型为T。public T get(int i) /返回第i个元素，0i=0 & ithis.n) return (T)this.elementi; /返回数组元素引用的对象，必须进行强制类型转换 return null;其中，数组元素elementi的类型是Object，实际引用实例的类型是T。上述声明的调用语句如下：SeqList list = n

15、ew SeqList(n); /顺序表元素类型是整数对象Integer iobj = list.get(0); /Integer类对象iobj引用本类的实例iobj.intValue() /iobj能够调用Integer类的成员方法此时，iobj对象不仅能够调用Object类声明的toString()等方法，表现出运行时多态；还能够调用Integer类声明的成员方法。也可调用语句如下：SeqList list = new SeqList(n); String str = list.get(0); str.length() /str能够调用String类的成员方法习2-5 顺序表类以下声明有什么

16、错误？为什么？public boolean equals(Object obj) /比较两个顺序表是否相等 return this.n=list.n & this.element=obj.element;【答】在深拷贝的含义下，两个顺序表相等意味着：两个顺序表长度相同且所有元素值相等。而不是两个顺序表对象的所有成员变量值对应相等。比较两个顺序表对象是否相等的多种情况如图2.2所示，方法实现见教材第30页。 图2.2 比较两个顺序表对象是否相等2.2.3 排序顺序表【思考题2-4】 SeqList类声明以下方法，子类SortedSeqList是否可用？为什么？/返回将this与list所有元素合

17、并连接的顺序表，不改变this和listSeqList union(SeqList list)【答】 SeqList类声明以下成员方法：public void addAll(SeqList list) /在this之后添加list所有元素，集合并。见例2.5public SeqList union(SeqList list) SeqList result = new SeqList(this); /深拷贝this，无法创建子类实例 result.addAll(list); /顺序表合并连接，尾插入 return result; /只能返回SeqList对象%注意：虽然union(list)方法

18、与addAll(list)方法功能相同，但不能将它们重载如下，因为，参数列表相同而返回值不同，产生二义性，编译器不能根据方法的参数列表确定执行重载方法中的哪一个。public void addAll(SeqList list) public SeqList addAll(SeqList list) /语法错，参数列表相同时不能重载 排序顺序表表示可重复的排序集合，元素按关键字大小排序。SortedSeqList类继承SeqList类的以下成员方法：public void addAll(SeqList list) /可用，参数list可引用SortedSeqList实例。 /其中，执行inser

19、t(x)方法运行时多态，当this引用子类实例时，执行排序顺序表按值插入 /合并结果this仍然是排序顺序表public SeqList union(SeqList list) /算法正确，不可用。希望返回排序顺序表 /因为，当this引用子类实例时，声明result和创建的仍然是SeqList实例，无法创建子类 /实例，就无法实现运行时多态，总是执行SeqList类的插入因此，SortedSeqList类需要覆盖union(list)方法如下：/覆盖，返回值类型不同但赋值相容。能与父类实例运算public SortedSeqList union(SeqList list) SortedSeq

20、List result = new SortedSeqList(this); /创建子类实例。只此一句不同 result.addAll(list); /继承父类方法，运行时多态，排序顺序表合并，按值插入 return result; /返回SortedSeqList对象综上所述，SeqList类对于集合并操作的“有所为，有所不为”原则如下。 声明void addAll(list)方法，子类继承，运行时多态。 不声明SeqList union(list)方法，因为，无法运行时多态。一个类为一个功能只需提供一种实现，至于是否返回对象，由调用者决定，通过深拷贝和addAll(list)方法可得到。2

21、.3 线性表的链式存储和实现2.3.1 单链表1. 单链表的结点习2-6 写出图2.3所示数据结构的声明。图2.3 一种数据结构【答】table可声明为数组或顺序表，元素为结点或单链表，声明为以下4种之一：Node table; /一维数组，元素为结点SinglyList table; /一维数组，元素为单链表SeqListNode table; /顺序表，元素为结点SeqListSinglyList table; /顺序表，元素为单链表 【习题2-8】单链表结点类问题讨论。 Node类声明构造方法当一个类没有声明构造方法时，Java提供默认构造方法。例如：public Node() /提供默

22、认构造方法 super(); /默认调用父类的无参数构造方法当一个类声明了构造方法时，Java不再提供默认构造方法。例如，当Node类声明了Node(T data,Node next)构造方法时，Java不再提供默认构造方法Node()。如果Node类需要Node()构造方法，必须自己声明。Java方法参数没有默认值。例如，Node类可以声明以下构造方法：public Node(T data) this(data,null);但不能将Node(T data,Node next)构造方法声明为如下形式：public Node(T data,Node next=null) Node类不需要声明析构

23、方法Node类从Object父类继承了析构方法，并且Java语言将自动释放不再使用的存储空间。因此，Node类不需要声明析构方法。 Node类不需要声明拷贝构造方法Java不提供默认拷贝构造方法。Node类如果声明拷贝构造方法以下：public Node(Node p) /拷贝构造方法，复制p引用的结点 this(p.data,p.next); 相当于如下：public Node(Node p) this.data = p.data; /this.data引用p.data，对象引用赋值，两个结点引用同一个元素 this.next = p.next; /this.next指向p的后继结点，结点对

24、象引用赋值，逻辑错误由于Java的赋值=采用引用模型，执行结果如图2.4所示，this.next指向p的后继结点，并没有创建结点，只将p的后继结点作为当前结结点的后继结点，产生逻辑错误。因此，Node类不能声明浅拷贝构造方法。图2.4 Node类浅拷贝由于创建结点是单链表执行的操作，所以，Node类不需要声明拷贝构造方法。 Node类可声明以下方法：public boolean equals(Object obj) /比较两个结点值是否相等，覆盖Object类的equals(obj)方法 return obj=this | obj instanceof Node & this.data.equ

25、als(Node)obj).data); 比较对象大小Node是单链表和排序单链表的结点类。单链表不需要比较元素大小，所以Node类不能声明实现Comparable接口。排序单链表需要比较元素大小，以下排序单链表类声明，约定能够比较T对象大小。/排序单链表类（升序），继承单链表类，T或T的某个祖先类实现Comparable接口public class SortedSinglyListT extends Comparable extends SinglyList2. 单链表的基本操作【思考题2-6】 遍历单链表，如果将p=p.next语句写成p.next=p，结果会怎样？画出示意图。【答】语句p

26、=p.next使p移动到后继结点，此时结点间的链接关系没有改变。如果写成p.next=p，则使p.next指向p结点自己，改变了结点间的链接关系，并丢失后继结点，如图2.5所示，遍历算法也变成死循环。图2.5 p.next=p改变结点间的链接关系【思考题2-7】 设front指向非空单链表中的某个结点，在front结点之后插入p结点，执行以下语句结果会怎样？画出示意图。Node p = new Node(x);front.next = p; /p.next = front.next; /【答】句相当于p.next = p;，产生错误，结点间的链接关系如图2.6所示。图2.6 插入语句次序错误错

27、误原因：上述后两条语句次序颠倒。对front.next赋值将改变结点间的链接关系，从而丢失后继结点地址。因此，在改变结点链接关系时，应该先获得front.next的值，再对其赋值。头插入存在同样问题。3. 带头结点的单链表【习2.7】 使用单链表求解Josephus环问题。将例2.1程序中创建SeqList对象的语句替换为如下，其余代码不变，则使用单链表也可求解Josephus环问题。SinglyList list = new SinglyList();上述程序虽然能够运行，但是，效率太低。一是，每次循环调用单链表的size()和remove(i)方法，都要从头开始再次遍历单链表，时间复杂度都是O(n)；再有，每次计数，欲删除第i个结点，需要再次查找使front指向第i个结点的前驱。