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

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

《数据结构(Java版)-习题解答与实验指导.doc》由会员分享，可在线阅读，更多相关《数据结构(Java版)-习题解答与实验指导.doc（90页珍藏版）》请在冰点文库上搜索。

数据结构（Java版）

习题解答与实验指导

目录

第1章绪论 1

1.1数据结构的基本概念 1

1.2算法 2

第2章线性表 3

2.1线性表抽象数据类型 3

2.2线性表的顺序存储和实现 4

2.2.1线性表的顺序存储结构 4

2.2.2顺序表 4

2.2.3排序顺序表 6

2.3线性表的链式存储和实现 7

2.3.1单链表 7

【习题2-8】单链表结点类问题讨论。

7

【习2.1】使用单链表求解Josephus环问题。

9

【习2.2】集合并运算，单链表深拷贝的应用。

10

2.3.2双链表 12

【习2.3】循环双链表的迭代方法。

13

【习2.4】循环双链表合并连接。

14

第3章串 15

3.1串抽象数据类型 15

3.2串的存储和实现 15

3.2.1串的存储结构 15

3.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】浮点数类。

19

3.2.3变量字符串类 20

【实验题3-11】删除变量串中的所有空格。

4-样卷 20

3.3串的模式匹配 21

3.3.1Brute-Force模式匹配算法 21

3.3.2模式匹配应用 22

【思考题3-4，实验题3-13】MyString类，replaceAll（pattern,s）改错。

22

3.3.3KMP模式匹配算法 22

第4章栈和队列 26

4.1栈 26

4.2队列 27

4.3递归 29

【习4.1】打印数字塔。

29

第5章数组和广义表 31

5.1数组 31

5.2特殊矩阵的压缩存储 32

5.2.1三角矩阵、对称矩阵和对角矩阵的压缩存储 32

5.2.2稀疏矩阵的压缩存储 33

5.3广义表 35

第6章树和二叉树 36

6.2二叉树 36

6.3线索二叉树 40

6.4Huffman树 44

6.5树的表示和实现 45

第7章图 46

7.1图及其抽象数据类型 46

7.2图的表示和实现 46

7.3图的遍历 48

7.4最小生成树 50

7.5最短路径 51

第8章查找 53

8.1查找的基本概念 53

8.2二分法查找 54

8.4散列 55

8.5二叉排序树 56

【实验8-1】判断一棵二叉树是否为二叉排序树，改错。

56

第9章排序 57

9.1插入排序 57

9.2交换排序 58

9.3选择排序 59

9.4归并排序 60

9.5线性表的排序算法 60

9.5.1顺序表的排序算法 60

【实验题9-2】归并两条排序顺序表。

60

第10章综合应用设计 62

10.1Java集合框架 62

【习10.1】Collection整数集合元素求和。

62

10.2课程设计补充选题 63

-III-

第1章绪论

目的：

勾勒数据结构课程的轮廓，了解本课程的目的、性质和主要内容。

内容：

数据结构和算法概念，算法设计与分析。

要求：

理解数据结构基本概念，理解抽象数据类型概念；熟悉算法设计和分析方法。

重点：

数据的逻辑结构和存储结构概念。

难点：

抽象数据类型，链式存储结构，算法分析方法。

实验：

简单算法设计，回顾Java语言的基本语法和面向对象基本概念。

1.1数据结构的基本概念

习1-2什么是数据结构？

数据结构概念包括哪些部分？

习1-3数据的逻辑结构主要有哪三种？

三者之间存在怎样的联系？

习1-4数据的存储结构主要有哪些？

各有何特点？

习1-5不同数据结构之间共同的操作有哪些？

【答】上述1-1～1-4问题说明如下。

①数据结构，指数据元素之间存在关系的数据元素集合。

②数据结构包含数据的逻辑结构、存储结构和数据操作三方面概念。

③数据的逻辑结构主要有三种：

线性结构、树结构和图结构，线性结构是树的特例，树结构是图的特例。

④数据的存储结构有两种：

顺序存储结构和链式存储结构，两者特点分别是数据元素数据连续存储、分散存储。

⑤数据操作主要有：

求数据元素个数，访问、查找、插入、删除数据元素等。

数据结构概念描述如图1.1所示。

图1.1数据结构概念

习1-6数据结构与数据类型有什么区别？

为什么要将数据结构设计成抽象数据类型？

【答】数据结构与数据类型概念本质相同，使用数据类型描述数据特性，使用数据结构描述数据之间关系。

将数据结构设计成抽象数据类型，是为了“定义和实现相分离”，这也是数据类型的特点。

1.2算法

习1-8什么是算法？

怎样描述算法？

怎样衡量算法的性能？

【答】算法是对问题求解过程的一种描述，是为解决一类问题给出的一个确定的、有限长的操作序列。

算法特征包括：

有穷性、确定性、输入、输出和可行性。

可以采用自然语言或伪码描述算法的设计思想，采用程序设计语言实现算法。

采用渐进分析法衡量算法性能，用时间复杂度O（f（n））表示所花费时间的量级，即时间效率；用空间复杂度O（S（n））表示算法执行过程中所需要的额外空间。

第2章线性表

目的：

实现线性表抽象数据类型。

内容：

将线性表的顺序存储结构和链式存储结构实现分别封装成顺序表类、单链表类、循环双链表类等，比较这两种实现的特点以及各种基本操作算法的效率。

要求：

理解线性表抽象数据类型，掌握顺序和链式存储结构实现线性表的方法。

重点：

顺序表、单链表、循环双链表等线性表设计训练。

难点：

使用对象引用方式实现链式存储结构，改变结点间的链接关系。

实验：

掌握单链表的遍历、插入、删除、复制等操作算法，熟悉循环单链表、双链表和循环双链表的结构和基本操作。

掌握MyEclipse集成开发环境的程序调试技术。

2.1线性表抽象数据类型

2-1什么是线性表？

线性表主要采用哪两种存储结构？

它们是如何存储数据元素的？

各有什么优缺点？

画出线性表的各种存储结构示意图。

它们是否是随机存取结构？

为什么？

【答】①线性表是数据元素之间具有线性关系的一种线性结构，对线性表的基本操作主要有获得元素值、设置元素值、插入、删除、查找、替换和排序等，插入和删除操作可以在线性表的任意位置进行。

②线性表可以采用顺序存储结构和链式存储结构表示。

线性表（）的两种存储结构见教材图1.4所示。

线性表的顺序存储结构（顺序表）用一组连续的存储单元顺序存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同。

顺序表的特点是数据元素连续存储，元素的存储地址是它在线性表中位置i的线性函数，计算一个元素地址花费常量时间，即存取任何一个元素的时间复杂度是O

（1）。

因此，顺序表是随机存取结构，这是顺序表最大的优点。

顺序表缺点是插入或删除操作效率低，每插入或删除一个元素平均需要移动线性表一半元素。

线性表的链式存储用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。

特点是数据元素分散存储，优点是插入或删除操作不需要移动其他元素；缺点是，线性表的链式存储结构不是随机存取结构，获得第i个元素地址的时间复杂度是O（n），因为线性表的链式存储结构（单链表）由若干结点组成，每个结点采用指针域保存其后继结点的地址，获得第i个元素地址平均需要遍历单链表一半结点。

③第2章线性表存储结构及实现的各种类描述如图2.1所示。

图2.1线性表的存储结构

2.2线性表的顺序存储和实现

2.2.1线性表的顺序存储结构

2-2解释顺序存储结构的线性表（顺序表）与数组在概念上的差别。

【答】数组是高级程序设计语言中的一种构造数据类型，具有存储单元连续的特点。

顺序表利用数组的这个特点，将顺序表中的数据元素在数组中连续存放，以数据元素的存储位置体现线性表数据元素之间的逻辑关系，所以数组是实现顺序表的基础。

虽然数组的存储单元是连续的，但数组元素不一定连续。

而用数组实现顺序表时，数据元素必须连续存放，否则无法体现出线性表中数据元素之间的前驱和后继关系。

习2-4为什么顺序表的插入和删除操作必须移动元素？

平均需要移动多少元素？

【答】顺序表中数据元素连续存储，元素之间没有空位置，逻辑上相邻的数据元素在存储位置上也相邻。

因此，插入数据元素时，必须将指定位置之后的数据元素向后移动，以留出空位置；删除数据元素时，必须将删除位置之后的数据元素向前移动，以填补空位置。

2.2.2顺序表

【思考题2-3】SeqList类如果声明get（i）方法如下，与返回类型为T有何区别？

publicObjectget（inti） //返回第i个元素，0≤i

若i越界，返回null

【答】①SeqList类如果声明get（i）方法如下，返回类型为Object。

publicObjectget（inti） //返回第i个元素，0≤i

若i越界，返回null

{

if（i>=0&&i

returnthis.element[i]; //返回数组元素element[i]引用的对象

returnnull;

}

上述声明的调用语句如下：

SeqListlist=newSeqList（n）; //顺序表元素类型是字符串

Objectobj=list.get（0）; //父类Object对象obj引用子类Integer的实例，类型多态

obj.toString（） //obj调用Object类声明且被子类覆盖的方法，运行时多态

obj.intValue（） //编译错，obj不能调用Integer类的成员方法

（（T）obj）.intValue（） //（T）obj是Integer类的对象

此时，obj对象只能调用Object类声明且被子类覆盖的方法，只有toString（）和equals（）方法，表现出运行时多态，实际执行obj引用实例所属Integer类提供的方法实现；而不能调用Integer类声明的成员方法。

②SeqList类声明get（i）方法如下，返回类型为T。

publicTget（inti） //返回第i个元素，0≤i

若i越界，返回null

{

if（i>=0&&i

return（T）this.element[i]; //返回数组元素引用的对象，必须进行强制类型转换

returnnull;

}

其中，数组元素element[i]的类型是Object，实际引用实例的类型是T。

上述声明的调用语句如下：

SeqListlist=newSeqList（n）; //顺序表元素类型是整数对象

Integeriobj=list.get（0）; //Integer类对象iobj引用本类的实例

iobj.intValue（） //iobj能够调用Integer类的成员方法

此时，iobj对象不仅能够调用Object类声明的toString（）等方法，表现出运行时多态；还能够调用Integer类声明的成员方法。

也可调用语句如下：

SeqListlist=newSeqList（n）;

Stringstr=list.get（0）;

str.length（） //str能够调用String类的成员方法

习2-5顺序表类以下声明有什么错误？

为什么？

publicbooleanequals（Objectobj） //比较两个顺序表是否相等

{

returnthis.n==list.n&&this.element==obj.element;

}

【答】在深拷贝的含义下，两个顺序表相等意味着：

两个顺序表长度相同且所有元素值相等。

而不是两个顺序表对象的所有成员变量值对应相等。

比较两个顺序表对象是否相等的多种情况如图2.2所示，方法实现见教材第30页。

图2.2比较两个顺序表对象是否相等

2.2.3排序顺序表

【思考题2-4】SeqList类声明以下方法，子类SortedSeqList是否可用？

为什么？

//返回将this与list所有元素合并连接的顺序表，不改变this和list

SeqListunion（SeqList

extendsT>list）

【答】①SeqList类声明以下成员方法：

publicvoidaddAll（SeqList

extendsT>list） //在this之后添加list所有元素，集合并。

见例2.5

publicSeqListunion（SeqList

extendsT>list）

{

SeqListresult=newSeqList（this）; //深拷贝this，无法创建子类实例

result.addAll（list）; //顺序表合并连接，尾插入

returnresult; //只能返回SeqList对象

}

%注意：

虽然union（list）方法与addAll（list）方法功能相同，但不能将它们重载如下，因为，参数列表相同而返回值不同，产生二义性，编译器不能根据方法的参数列表确定执行重载方法中的哪一个。

publicvoidaddAll（SeqList

extendsT>list）

publicSeqListaddAll（SeqList

extendsT>list） //语法错，参数列表相同时不能重载

②排序顺序表表示可重复的排序集合，元素按关键字大小排序。

SortedSeqList类继承SeqList类的以下成员方法：

publicvoidaddAll（SeqList

extendsT>list） //可用，参数list可引用SortedSeqList实例。

//其中，执行insert（x）方法运行时多态，当this引用子类实例时，执行排序顺序表按值插入

//合并结果this仍然是排序顺序表

publicSeqListunion（SeqList

extendsT>list） //算法正确，不可用。

希望返回排序顺序表

//因为，当this引用子类实例时，声明result和创建的仍然是SeqList实例，无法创建子类

//实例，就无法实现运行时多态，总是执行SeqList类的插入

因此，SortedSeqList类需要覆盖union（list）方法如下：

//覆盖，返回值类型不同但赋值相容。

能与父类实例运算

publicSortedSeqListunion（SeqList

extendsT>list）

{

SortedSeqListresult=newSortedSeqList（this）; //创建子类实例。

只此一句不同

result.addAll（list）; //继承父类方法，运行时多态，排序顺序表合并，按值插入

returnresult; //返回SortedSeqList对象

}

综上所述，SeqList类对于集合并操作的“有所为，有所不为”原则如下。

¤声明voidaddAll（list）方法，子类继承，运行时多态。

¤不声明SeqListunion（list）方法，因为，无法运行时多态。

一个类为一个功能只需提供一种实现，至于是否返回对象，由调用者决定，通过深拷贝和addAll（list）方法可得到。

2.3线性表的链式存储和实现

2.3.1单链表

1.单链表的结点

习2-6写出图2.3所示数据结构的声明。

图2.3一种数据结构

【答】table可声明为数组或顺序表，元素为结点或单链表，声明为以下4种之一：

Nodetable[]; //一维数组，元素为结点

SinglyListtable[]; //一维数组，元素为单链表

SeqList>table; //顺序表，元素为结点

SeqList>table; //顺序表，元素为单链表

【习题2-8】单链表结点类问题讨论。

①Node类声明构造方法

当一个类没有声明构造方法时，Java提供默认构造方法。

例如：

publicNode（） //提供默认构造方法

{super（）; //默认调用父类的无参数构造方法

}

当一个类声明了构造方法时，Java不再提供默认构造方法。

例如，当Node类声明了Node（Tdata,Nodenext）构造方法时，Java不再提供默认构造方法Node（）。

如果Node类需要Node（）构造方法，必须自己声明。

Java方法参数没有默认值。

例如，Node类可以声明以下构造方法：

publicNode（Tdata）

{this（data,null）;

}

但不能将Node（Tdata,Nodenext）构造方法声明为如下形式：

publicNode（Tdata,Nodenext=null）

②Node类不需要声明析构方法

Node类从Object父类继承了析构方法，并且Java语言将自动释放不再使用的存储空间。

因此，Node类不需要声明析构方法。

③Node类不需要声明拷贝构造方法

Java不提供默认拷贝构造方法。

Node类如果声明拷贝构造方法以下：

publicNode（Nodep） //拷贝构造方法，复制p引用的结点

{this（p.data,p.next）;

}

相当于如下：

publicNode（Nodep）

{this.data=p.data; //this.data引用p.data，对象引用赋值，两个结点引用同一个元素

this.next=p.next; //this.next指向p的后继结点，结点对象引用赋值，逻辑错误

}

由于Java的赋值=采用引用模型，执行结果如图2.4所示，this.next指向p的后继结点，并没有创建结点，只将p的后继结点作为当前结结点的后继结点，产生逻辑错误。

因此，Node类不能声明浅拷贝构造方法。

图2.4Node类浅拷贝

由于创建结点是单链表执行的操作，所以，Node类不需要声明拷贝构造方法。

④Node类可声明以下方法：

publicbooleanequals（Objectobj）//比较两个结点值是否相等，覆盖Object类的equals（obj）方法

{

returnobj==this||objinstanceofNode

>&&this.data.equals（（（Node）obj）.data）;

}

⑤比较对象大小

Node是单链表和排序单链表的结点类。

单链表不需要比较元素大小，所以Node类不能声明实现Comparable接口。

排序单链表需要比较元素大小，以下排序单链表类声明，约定能够比较T对象大小。

//排序单链表类（升序），继承单链表类，T或T的某个祖先类实现Comparable接口

publicclassSortedSinglyList

superT>>extendsSinglyList

2.单链表的基本操作

【思考题2-6】遍历单链表，如果将p=p.next语句写成p.next=p，结果会怎样？

画出示意图。

【答】语句p=p.next使p移动到后继结点，此时结点间的链接关系没有改变。

如果写成p.next=p，则使p.next指向p结点自己，改变了结点间的链接关系，并丢失后继结点，如图2.5所示，遍历算法也变成死循环。

图2.5p.next=p改变结点间的链接关系

【思考题2-7】设front指向非空单链表中的某个结点，在front结点之后插入p结点，执行以下语句结果会怎样？

画出示意图。

Nodep=newNode（x）;

front.next=p; //①

p.next=front.next; //②

【答】②句相当于p.next=p;，产生错误，结点间的链接关系如图2.6所示。

图2.6插入语句次序错误

错误原因：

上述后两条语句次序颠倒。

对front.next赋值将改变结点间的链接关系，从而丢失后继结点地址。

因此，在改变结点链接关系时，应该先获得front.next的值，再对其赋值。

头插入存在同样问题。

3.带头结点的单链表

【习2.7】使用单链表求解Josephus环问题。

将例2.1程序中创建SeqList对象的语句替换为如下，其余代码不变，则使用单链表也可求解Josephus环问题。

SinglyListlist=newSinglyList（）;

上述程序虽然能够运行，但是，效率太低。

一是，每次循环调用单链表的size（）和remove（i）方法，都要从头开始再次遍历单链表，时间复杂度都是O（n）；再有，每次计数，欲删除第i个结点，需要再次查找使front指向第i个结点的前驱。