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

《数据结构(Java版)-习题解答与实验指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构(Java版丿习题解答与实验指导目录第1章绪论11.1数据结构的基本概念11.2算法2第2章线性表32.1线性表抽象数据类型32.2线性表的顺序存储和实现42.2.1线性表的顺序存储结构42.2.2顺序表52.2.3排序顺序表72.3线性表的链式存储和实现9231单链表9【习题2・8】单链表结点类问题讨论。10【习2.1】使用单链表求解Josephus环问题。12【习2.2］集合并运算，单链表深拷贝的应用。142.3.2双链表16【习2.3］循环双链表的迭代方法。19【习2.4］循环双链表合并连接。19第3章串213.1串

2、抽象数据类型213.2串的存储和实现223.2.1串的存储结构223.2.2常量字符串类22【习3.1】C/C++语言，string.h中的strcpy()和strcat()函数存在下标越界错误。22【思考题3・1】逆转String串，分析算法效率。24【实验题3-1]MyString类，比较串大小，忽略字母大小写。25【例3.2思考题3-2]Mylnteger整数类，返回value的radix进制原码字符串。26【实验题3-9]浮点数类。273.2.3变量字符串类30【实验题3-11]删除变量串中的所有空格。4-样卷••…303

3、.3串的模式匹配313.3.1Bmte-Force模式匹配算法313.3.2模式匹配应用32【思考题34实验题3-13]MyString类，replaceAll(pattem,s)改错。323.3.3KMP模式匹配算法33第4章栈和队列364.1栈364.2队列384.3递归41【习4.1]打印数字塔。41第5章数组和广义表435」数组435.2特殊矩阵的压缩存储445.2.1三角矩阵、对称矩阵和对角矩阵的压缩存储445.2.2稀疏矩阵的压缩存储465.3广义表48第6章树和二叉树496.2二叉树496.3线索二叉树566.4Hu

4、ffman树616.5树的表示和实现61第7章图637」图及其抽象数据类型637.2图的表示和实现647.3图的遍历657.4最小生成树677.5最短路径69第8章查找728」查找的基本概念728.2二分法查找738.4散列758.5二叉排序树76【实验弘1】判断一棵二叉树是否为二叉排序树，改错。•…76第9章排序789.1插入排序789.2交换排序799.3选择排序809.4归并排序819.5线性表的排序算法829.5.1顺序表的排序算法82【实验题91】归并两条排序顺序表。82第10章综合应用设计8410.1Java集合框架8

5、4【习10.1]Collection整数集合元素求和。8410.2课程设计补充选题86第1章绪论目的：勾勒数据结构课程的轮廓，了解本课程的目的、性质和主要内容。内容：数据结构和算法概念，算法设计与分析。要求：理解数据结构基本概念，理解抽象数据类型概念；熟悉算法设计和分析方法。重点：数据的逻辑结构和存储结构概念。难点：抽象数据类型，链式存储结构，算法分析方法。实验：简单算法设计，冋顾Java语言的基本语法和面向对象基本概念。1.1数据结构的基本概念习1-2什么是数据结构？数据结构概念包括哪些部分？习1-3数据的逻辑

6、结构主要有哪三种？三者Z间存在怎样的联系？习1-4数据的存储结构主要有哪些？各有何特点？习1-5不同数据结构之间共同的操作有哪些？【答】上述1・1〜1・4问题说明如下。①数据结构，指数据元素Z间存在关系的数据元素集合。②数据结构包含数据的逻辑结构、存储结构和数据操作三方面概念。③数据的逻辑结构主要有三种：线性结构、树结构和图结构，线性结构是树的特例，树结构是图的特例。④数据的存储结构有两种：顺序存储结构和链式存储结构，两者特点分别是数据元素数据连续存储、分散存储。⑤数据操作主要有：求数据元素个数，访问、查找、插入、删除数据元素等。

7、数据结构概念描述如图L1所示。枚件履、Ilk恢、认蚪耐广炬榔恰构，W.二夏輯敷蹄构［询的伽冊詩炼几*进故存也Ibt存■始构'KjKi几聶廿肚存枷（对W的播胳貝二轧1幫牛孤取必筑历、张入*1敦掘摄fl1H除、ftft-艸辰W*I对懂钩的操fh址林HWilZ^WW.卄臨恤入、MN^«>图1」数据结构概念习1・6数据结构与数据类型有什么区别？为什么耍将数据结构设计成抽象数据类型？【答】数据结构与数据类型概念本质和同，使用数据类型描述数据特性，使用数据结构描述数据之间关系。将数据结构设计成抽象数据类型，是为了“定义和实现札!分离”，这也是

8、数据类型的特点。1.2算法习1-8什么是算法？怎样描述算法？怎样衡量算法的性能？【答】算法是对问题求解过程的一种描述，是为解决一类问题给出的一个确定的、有限长的操作序列。算法特征包括：有穷性、确定性、输入、输出和可行性。可以采用自然语言或伪码描述算