《数据结构(Java版)-习题解答与实验指导.doc》由会员分享，可在线阅读，更多相关《数据结构(Java版)-习题解答与实验指导.doc（90页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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)方法，都要从头开始再次遍历单链表，时间复杂度都
28、是O(n)；再有，每次计数，欲删除第i个结点，需要再次查找使front指向第i个结点的前驱。修改例2.1程序，使用单链表求解Josephus环问题，遍历次数最少。/求解Josephus环，n（0）指定长度；s指定计数的起始位置，0sn；d计数，0dnpublic Josephus(int n, int s, int d) if (n=0 | s=n | d=n) throw new java.lang.IllegalArgumentException(n=+n+，s=+s+，d=+d); /无效参数异常 System.out.print(Josephus(+n+,+s+,+d+)，); Sin
29、glyList list = new SinglyList(); /构造空单链表 for (int i=n-1; i=0; i-) list.insert(0, (char)(A+i)+); /单链表头插入，O(1) System.out.println(list.toString(); /输出单链表的描述字符串，O(n) /以下求解Josephus环 Node front = list.head; /front指向头结点 for (int j=0; front!=null & j1) /多于一个元素时循环 for (int j=1; jd; j+) /计数，寻找删除结点。少数一个，front
30、指向待删除结点的前驱 front = front.next; if (front=null) /实现循环计数 front = list.head.next; if (front.next=null) /若front指向最后一个结点，则删除第0个结点 front = list.head; System.out.print(删除+front.next.data.toString()+，); front.next = front.next.next; /删除front的后继结点，包括头、中间/尾删除 n-; System.out.println(list.toString(); System.out
31、.println(被赦免者是+list.get(0).toString();/get(0)获得元素，O(1)执行new Josephus(5,0,3)，单链表的变化过程如图2.7所示。图2.7 使用单链表求解Josephus(5,0,3)环问题的执行过程【习2.8】 集合并运算，单链表深拷贝的应用。本题目的： 单链表作为方法参数与返回值，传递对象引用； 单链表深拷贝应用。当对象作为方法的参数或返回值时，参数传递原则同赋值，“引用参数传递对象引用”，即形式参数获得实际参数的对象引用。SinglyList单链表类声明以下成员方法，实现集合并运算。/在this单链表之后连接list的所有结点，集合并
32、；设置list为空，O(n) public void concat(SinglyList list) Node rear=this.head; while (rear.next!=null) /寻找this单链表的最后一个结点 rear = rear.next; rear.next = list.head.next; /尾插入list单链表 list.head.next=null; /设置list为空，否则逻辑错。方法体内可改变参数list引用的单链表/复制list所有结点插入到this单链表之后，集合并，不改变listpublic void addAll(SinglyList list) t
33、his.concat(new SinglyList(list); /先执行单链表深拷贝，再连接复制的list/返回复制this和list合并连接的单链表，并集，不改变this和listpublic SinglyList union(SinglyList list) SinglyList result = new SinglyList(this); /深拷贝this单链表 result.addAll(list); return result; /返回result引用的单链表，释放result变量设创建单链表lista和listb，分别调用上述方法，算法描述如图2.14所示。图2.8 集合并运算，
34、单链表深拷贝的应用4. 循环单链表【思考题2-10】能否使用以下语句创建循环单链表的头结点？为什么？head = new Node(null, head); /创建循环单链表的头结点【答】不能。因为申请结点存储空间时head没有初始化，不是null。实际语义需要的是将该结点地址作为其next域值，做不到。2.3.2 双链表1. 双链表结点习2-11 DoubleNode类能否声明如下，继承单链表结点类Node？为什么？public class DoubleNode extends Node /双链表结点类，继承单链表结点类 public DoubleNode prev; /指向前驱结点的地址域
35、【答】不能。 虽然该声明没有语法错，但有语义错，因为从父类继承来的next类型为Node，仍然指向单链表结点，等价于以下声明：public class DoubleNode /双链表结点类 public T data; public Node next; /逻辑错误 public DoubleNode prev; ;此处需要next指向双链表结点，类型是DoubleNode，两者结点结构不同。 虽然从语法上DoubleNode可以声明如下，将next重新声明为DoubleNode类型，但是双链表结点与单链表结点无关，并不是两个具有包含关系的概念。public class DoubleNode
36、extends Node public DoubleNode prev,next; /prev指向前驱结点，next指向后继结点 public DoubleNode(T data,DoubleNode prev,DoubleNode next) / super(data,next); /语义错，赋值super.next（类型为Node） super(data,null); this.next = next; /赋值this.next（类型为DoubleNode） this.prev = prev; %注意：此时DoubleNode类有两个next，使用this和super引用可区分两者，从父类
37、继承来的super.next类型为Node；子类重新声明的this.next类型为DoubleNode，this.next隐藏super.next，构造方法中super(data,next);语句对super.next赋值。如此声明，没有意义。习2-12 DoubleNode类是否需要声明析构方法和拷贝构造方法？为什么？【答】参见前述【习题2-8】。2. 双链表【思考题2-11】设p指向双链表某个结点，写出在p结点之后插入值为x结点的语句。【答】语句如下：DoubleNode q = new DoubleNode(x,p,p.next); /插入在p结点之后if (p.next!=null)
38、/中间插入 p.next.prev = q; /p.next = q; /再问：如果后两条语句次序颠倒，将会怎样？【答】导致错误，如图2.10所示，p.next.prev = q相当于q.prev = q。 图2.9 双链表后插入结点时语句次序错误3. 循环双链表习2-13 循环双链表类能否声明为如下继承单链表类，继承head成员变量？为什么？public class CirDoublyList extends SinglyList /循环双链表类，继承单链表类【答】不能。因为，如果继承，等价于以下声明：public class CirDoublyList extends SinglyList
39、 /循环双链表类，继承单链表类 Node head; /继承父类的成员变量，数据类型错误;其中，head的数据类型是Node，指向单链表结点，类型错误。应该是DoubleNode。再者，循环双链表和单链表是实现线性表的两种存储结构，两者之间没有关联，不是继承关系。可以只有循环双链表，而没有单链表。【习2.10】 循环双链表的迭代方法。以下4个方法实现循环双链表的迭代功能，时间复杂度都是O(1)，这就是设计循环双链表的目的。public DoubleNode first() /返回循环双链表第一个结点，O(1) return (head.next=head) ? null : head.next;public DoubleNode next(D