内容发布更新时间 : 2024/5/9 13:16:17星期一 下面是文章的全部内容请认真阅读。
数据结构（Java版） 习题解答与实验指导
目录
第1章 绪论 ················································································ 1 1.1 数据结构的基本概念 ····················································· 1 1.2 算法 ·········································································· 2 第2章 线 性 表 ········································································· 3 2.1 线性表抽象数据类型 ····················································· 3 2.2 线性表的顺序存储和实现 ··············································· 4 2.2.1 线性表的顺序存储结构 ············································ 4 2.2.2 顺序表 ································································· 5 2.2.3 排序顺序表 ··························································· 7 2.3 线性表的链式存储和实现 ··············································· 9 2.3.1 单链表 ································································· 9
··························· 9 【习题2-8】单链表结点类问题讨论。 ·
················ 12 【习2.1】 使用单链表求解Josephus环问题。·············· 14 【习2.2】 集合并运算，单链表深拷贝的应用。 ·
2.3.2 双链表 ································································ 16
···························· 19 【习2.3】 循环双链表的迭代方法。 ································ 19 【习2.4】 循环双链表合并连接。 ·第3章 串 ·················································································· 21
3.1 串抽象数据类型 ·························································· 21 3.2 串的存储和实现 ·························································· 22 3.2.1 串的存储结构 ······················································· 22 3.2.2 常量字符串类 ······················································· 22 【习3.1】 C/C++语言，string.h中的strcpy()和strcat()函数存
···················································· 22 在下标越界错误。 ·
·············· 24 【思考题3-1】逆转String串，分析算法效率。 ·
- I -
【实验题3-1】MyString类，比较串大小，忽略字母大小写。25 【例3.2思考题3-2】MyInteger整数类，返回value的radix进
······················································· 26 制原码字符串。 ·
········································· 27 【实验题3-9】浮点数类。 ·
3.2.3 变量字符串类 ······················································· 30
··· 30 【实验题3-11】删除变量串中的所有空格。 4-样卷 ·
3.3 串的模式匹配 ····························································· 31 3.3.1 Brute-Force模式匹配算法 ········································· 31 3.3.2 模式匹配应用 ······················································· 32 【思考题3-4，实验题3-13】MyString类，replaceAll(pattern,s)
··································································· 32 改错。 ·
3.3.3 KMP模式匹配算法 ················································· 33 第4章 栈和队列 ······································································· 36 4.1 栈 ············································································ 36 4.2 队列 ········································································· 38 4.3 递归 ········································································· 41
··········································· 41 【习4.1】 打印数字塔。 ·第5章 数组和广义表 ································································ 43
5.1 数组 ········································································· 43 5.2 特殊矩阵的压缩存储 ···················································· 44 5.2.1 三角矩阵、对称矩阵和对角矩阵的压缩存储 ················ 44 5.2.2 稀疏矩阵的压缩存储 ·············································· 46 5.3 广义表 ······································································ 48 第6章 树和二叉树 ···································································· 49 6.2 二叉树 ······································································ 49 6.3 线索二叉树 ································································ 56 6.4 Huffman树 ································································· 61 6.5 树的表示和实现 ·························································· 61 第7章 图 ·················································································· 63 7.1 图及其抽象数据类型 ···················································· 63 7.2 图的表示和实现 ·························································· 64 7.3 图的遍历 ··································································· 65
- II -
7.4 最小生成树 ································································ 67 7.5 最短路径 ··································································· 69 第8章 查 找 ··········································································· 72 8.1 查找的基本概念 ·························································· 72 8.2 二分法查找 ································································ 73 8.4 散列 ········································································· 75 8.5 二叉排序树 ································································ 76
···· 76 【实验8-1】判断一棵二叉树是否为二叉排序树，改错。 第9章 排序 ·············································································· 78
9.1 插入排序 ··································································· 78 9.2 交换排序 ··································································· 79 9.3 选择排序 ··································································· 80 9.4 归并排序 ··································································· 81 9.5 线性表的排序算法 ······················································· 82 9.5.1 顺序表的排序算法 ················································· 82
·························· 82 【实验题9-2】归并两条排序顺序表。 ·第10章 综合应用设计 ····························································· 84
10.1 Java集合框架 ···························································· 84
········ 84 【习10.1】 Collection
10.2 课程设计补充选题 ····················································· 86
- III -
第1章 绪论
目的：勾勒数据结构课程的轮廓，了解本课程的目的、性质和主要内容。
内容：数据结构和算法概念，算法设计与分析。
要求：理解数据结构基本概念，理解抽象数据类型概念；熟悉算法设计和分析方法。
重点：数据的逻辑结构和存储结构概念。
难点：抽象数据类型，链式存储结构，算法分析方法。
实验：简单算法设计，回顾Java语言的基本语法和面向对象基本概
念。
1.1 数据结构的基本概念
习1-2 什么是数据结构？数据结构概念包括哪些部分？
习1-3 数据的逻辑结构主要有哪三种？三者之间存在怎样的联系？
习1-4 数据的存储结构主要有哪些？各有何特点？ 习1-5 不同数据结构之间共同的操作有哪些？ 【答】上述1-1～1-4问题说明如下。
① 数据结构，指数据元素之间存在关系的数据元素集合。
② 数据结构包含数据的逻辑结构、存储结构和数据操作三方面概念。
③ 数据的逻辑结构主要有三种：线性结构、树结构和图结构，线性结构是树的特例，树结构是图的特例。
④ 数据的存储结构有两种：顺序存储结构和链式存储结构，两者特点分别是数据元素数据连续存储、分散存储。
⑤ 数据操作主要有：求数据元素个数，访问、查找、插入、删除数据元素等。
数据结构概念描述如图1.1所示。
- 1 -
线性结构数据的逻辑结构非线性结构??线性表、串、栈、队列数组、广义表树结构：树、二叉树图 数据结构习1-6 数据结构与数据类型有什么区别？为什么要将数据结构设计成抽象数据类型？
【答】数据结构与数据类型概念本质相同，使用数据类型描述数据特性，使用数据结构描述数据之间关系。
将数据结构设计成抽象数据类型，是为了“定义和实现相分离”，这也是数据类型的特点。
1.2 算法
习1-8 什么是算法？怎样描述算法？怎样衡量算法的性能？ 【答】算法是对问题求解过程的一种描述，是为解决一类问题给出的一个确定的、有限长的操作序列。算法特征包括：有穷性、确定性、输入、输出和可行性。
可以采用自然语言或伪码描述算法的设计思想，采用程序设计语言实现算法。
采用渐进分析法衡量算法性能，用时间复杂度O(f(n))表示所花费时间的量级，即时间效率；用空间复杂度O(S(n))表示算法执行过程中所需要的额外空间。
数据的存储结构?顺序存储结构，特点：元素连续存储链式存储结构，特点：元素分散存储
数据操作?对元素的操作：判空、求元素个数、取值、设置值、遍历、插入、删除、查找、排序、替换对结构的操作：复制、判断是否相等、查找、插入、删除、替换图1.1 数据结构概念
- 2 -