《数据结构Java版第3版复习》由会员分享，可在线阅读，更多相关《数据结构Java版第3版复习（38页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构（Java版版）（第（第3版版）数据结构(Java版)(第3版)复习数据结构数据结构（Java版版）（第（第3版）版）第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 串串第第4章章 栈与队列栈与队列第第5章章 数组和广义表数组和广义表第第6章章 树和二叉树树和二叉树第第7章章 图图第第8章章 查找查找第第9章章 排序排序数据结构(Java版)(第3版)复习数据结构 （Java版）（第3版） 第第1章章 绪论绪论目的：目的：勾勒数据结构课程的轮廓。勾勒数据结构课程的轮廓。 内容：内容：数据结构概念，算法设计与分析。数据结构概念，算法设计与分析。要求：要求：理解数据结构基本
2、概念，理解抽象数据理解数据结构基本概念，理解抽象数据 类型概念；熟悉算法设计和分析方法。掌类型概念；熟悉算法设计和分析方法。掌 握编辑、编译、运行握编辑、编译、运行Java Application程程 序的基本技能。序的基本技能。重点：重点：数据的逻辑结构和存储结构概念。数据的逻辑结构和存储结构概念。难点：难点：抽象数据类型，算法分析。抽象数据类型，算法分析。1.1 数据结构的基本概念数据结构的基本概念1.什么是数据、数据元素、数据项和关键字？它们什么是数据、数据元素、数据项和关键字？它们之间是怎样的关系？之间是怎样的关系？2.什么是数据结构？数据结构概念包括哪三部分？什么是数据结构？数据结构
3、概念包括哪三部分？3.数据的逻辑结构主要有哪三种？各有何特点？三数据的逻辑结构主要有哪三种？各有何特点？三者之间存在怎样的联系？者之间存在怎样的联系？ 4.数据的存储结构主要有哪些？各有何特点？数据的存储结构主要有哪些？各有何特点？数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构概念数据结构概念 数据结构(Java版)(第3版)复习（Java版）（第3版） 1.数据结构与数据类型的概念有什么区别？数据结构与数据类型的概念有什么区别？为什么要将数据结构设计成抽象数据类型为什么要将数据结构设计成抽象数据类型？2.线性结构主要有哪些？各有何特点？各采线性结构主要有哪些？各有何特
4、点？各采用什么存储结构？为什么？用什么存储结构？为什么？ 数据结构(Java版)(第3版)复习（Java版）（第3版） 1.2 算法算法1.什么是算法？怎样描述算法？怎样衡量算什么是算法？怎样描述算法？怎样衡量算法的性能？法的性能？ 数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第2章章 线性表线性表目的：目的：实现线性表抽象数据类型。实现线性表抽象数据类型。内容：内容：将线性表的顺序存储结构和链式存储结构将线性表的顺序存储结构和链式存储结构 实现分别封装成顺序表类、单链表类、循环实现分别封装成顺序表类、单链表类、循环 双链表类等，比较这两
5、种实现的特点以及各双链表类等，比较这两种实现的特点以及各 种基本操作算法的效率。种基本操作算法的效率。要求：要求：理解线性表抽象数据类型，掌握顺序和链式理解线性表抽象数据类型，掌握顺序和链式 存储结构实现线性表的方法。存储结构实现线性表的方法。重点：重点：顺序表、单链表、循环双链表等线性表的设顺序表、单链表、循环双链表等线性表的设 计训练。计训练。难点：难点：使用指针实现链式存储结构，通过指针操作使用指针实现链式存储结构，通过指针操作 改变结点间的链接关系。改变结点间的链接关系。2.1 线性表抽象数据类型线性表抽象数据类型 1.什么是线性表？线性表主要采用哪两种存储什么是线性表？线性表主要采用
6、哪两种存储结构？它们是如何存储数据元素的？各有什结构？它们是如何存储数据元素的？各有什么优缺点？么优缺点？ 2.为什么顺序表的插入和删除操作必须移动元为什么顺序表的插入和删除操作必须移动元素？平均需要移动多少元素？素？平均需要移动多少元素？ 3.线性表的链式存储结构有哪几种？它们是如线性表的链式存储结构有哪几种？它们是如何存储数据元素的？各有何特点？有什么优何存储数据元素的？各有何特点？有什么优缺点？缺点？ 数据结构(Java版)(第3版)复习（Java版）（第3版） 线性表及其存储结构线性表及其存储结构 数据结构(Java版)(第3版)复习（Java版）（第3版） 线性表的两种存储结构线性表
7、的两种存储结构数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第3章章 串串目的：目的：串作为特殊线性表的实现与应用。串作为特殊线性表的实现与应用。内容：内容：字符串的基本概念，串抽象数据类型，顺序字符串的基本概念，串抽象数据类型，顺序 和链式两种存储结构存储串的特点；采用顺和链式两种存储结构存储串的特点；采用顺 序存储结构实现串的各种操作算法；两种串序存储结构实现串的各种操作算法；两种串 的模式匹配算法及应用：的模式匹配算法及应用：Brute-Force算法算法 和和KMP算法。算法。要求：要求：掌握顺序串类的基本操作实现方法，掌握串掌握顺
8、序串类的基本操作实现方法，掌握串 的模式匹配算法及应用。的模式匹配算法及应用。重点：重点：串数据类型的各种操作实现，两种串的模式串数据类型的各种操作实现，两种串的模式 匹配算法及应用。匹配算法及应用。难点：难点：KMP模式匹配算法，模式匹配算法，next数组在数组在KMP算法中算法中 的作用及产生过程。的作用及产生过程。3.1 串抽象数据类型串抽象数据类型 1.什么是串？串和线性表在概念上有何差别？什么是串？串和线性表在概念上有何差别？串操作的主要特点有哪些？串操作的主要特点有哪些？2.串和字符的存储结构有什么不同？串的存储串和字符的存储结构有什么不同？串的存储结构有几种？串通常采用什么存储结
9、构？结构有几种？串通常采用什么存储结构？数据结构(Java版)(第3版)复习（Java版）（第3版） 3.3 串的模式匹配串的模式匹配 1.什么是串的模式匹配？有哪些场合需要使什么是串的模式匹配？有哪些场合需要使用串的模式匹配？串的模式匹配主要算法用串的模式匹配？串的模式匹配主要算法有哪些，各有何特点？举例说明，并给出有哪些，各有何特点？举例说明，并给出最好情况和最坏情况及其时间复杂度。最好情况和最坏情况及其时间复杂度。 数据结构(Java版)(第3版)复习（Java版）（第3版） 3.3.1 Brute-Force算法算法 1.Brute-Force模式匹配算法的主要特点是模式匹配算法的主要
10、特点是什么？算法思路是怎样的？什么？算法思路是怎样的？ 数据结构(Java版)(第3版)复习（Java版）（第3版） 3.3.2 KMP算法算法 1.KMP算法模式匹配的主要特点是什么？算算法模式匹配的主要特点是什么？算法思路是怎样的？法思路是怎样的？next数组有什么作用？数组有什么作用？求求next数组的算法有什么特点？数组的算法有什么特点？数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第4章章 栈与队列栈与队列目的：目的：使用栈或队列作为求解复杂应用问题的使用栈或队列作为求解复杂应用问题的 有效手段和措施。有效手段和措施。内容：内容：
11、栈和队列抽象数据类型及它们的实现和应栈和队列抽象数据类型及它们的实现和应 用；优先队列；递归算法设计。用；优先队列；递归算法设计。要求：要求：掌握栈和队列抽象数据类型，以及顺序和掌握栈和队列抽象数据类型，以及顺序和链式存储结构实现；理解对于怎样的应用问题，链式存储结构实现；理解对于怎样的应用问题，需要使用栈或队列，以及怎样使用。需要使用栈或队列，以及怎样使用。重点：重点：栈和队列的设计和实现；理解递归定义，栈和队列的设计和实现；理解递归定义， 设计递归算法。设计递归算法。难点：难点：使用栈或队列求解复杂应用问题；递归算使用栈或队列求解复杂应用问题；递归算 法设计。法设计。 实验：实验：栈和队列
12、及其应用；递归算法。栈和队列及其应用；递归算法。4.1 栈栈 1.什么是栈？栈的特点是什么？在什么情况下什么是栈？栈的特点是什么？在什么情况下需要使用栈？需要使用栈？2.栈可以采用什么存储结构？执行插入、删除栈可以采用什么存储结构？执行插入、删除操作时需要移动数据元素吗？为什么？操作时需要移动数据元素吗？为什么？数据结构(Java版)(第3版)复习（Java版）（第3版） 4.2 队列队列 1.什么是队列？有何特点？说明在什么情况什么是队列？有何特点？说明在什么情况下需要使用队列。下需要使用队列。2.什么是队列的假溢出？为什么顺序队列会什么是队列的假溢出？为什么顺序队列会出现假溢出？怎样解决队
13、列的假溢出问题出现假溢出？怎样解决队列的假溢出问题？3.链式队列会出现假溢出吗？为什么？链式队列会出现假溢出吗？为什么？4.顺序栈会出现假溢出吗？为什么？顺序栈会出现假溢出吗？为什么？数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第5章章 数组和广义表数组和广义表目的：目的：线性结构到非线性结构的过渡，了解包含子结构线性结构到非线性结构的过渡，了解包含子结构的线性结构，理解链式存储结构在表达非线性数据结的线性结构，理解链式存储结构在表达非线性数据结构中的作用。构中的作用。内容：内容：使用二维数组表示矩阵及运算；三角矩阵、对称矩使用二维数组表
14、示矩阵及运算；三角矩阵、对称矩阵、稀疏矩阵等各种压缩存储方法实现矩阵运算；广阵、稀疏矩阵等各种压缩存储方法实现矩阵运算；广义表的概念、双链表示和实现。义表的概念、双链表示和实现。要求：要求：理解多维数组的存储结构；熟悉特殊矩阵的压缩存理解多维数组的存储结构；熟悉特殊矩阵的压缩存储方法；掌握稀疏矩阵三元组从顺序表、行的单链表储方法；掌握稀疏矩阵三元组从顺序表、行的单链表到十字链表等到多种存储结构的演变过程；理解广义到十字链表等到多种存储结构的演变过程；理解广义表的概念，熟悉广义表的存储结构。表的概念，熟悉广义表的存储结构。重点：重点：讨论多种由顺序存储结构和链式存储结构有机结合讨论多种由顺序存储
15、结构和链式存储结构有机结合的存储结构，以矩阵为例，研究在相同的逻辑结构的存储结构，以矩阵为例，研究在相同的逻辑结构（矩阵）（矩阵）和操作要求（矩阵运算）情况下，根据各种和操作要求（矩阵运算）情况下，根据各种矩阵的不同特矩阵的不同特性，采用多种存储结构实现矩阵运算。性，采用多种存储结构实现矩阵运算。 难点：难点：稀疏矩阵的多种存储和实现，广义表的存储和稀疏矩阵的多种存储和实现，广义表的存储和 实现。实现。 实验：实验：特殊矩阵和广义表的存储和运算。特殊矩阵和广义表的存储和运算。5.1 数组数组 1.数组有什么特点？数组有什么特点？“数据结构数据结构”课程中为什课程中为什么要研究数组？么要研究数组
16、？2.什么是随机存储结构？分别说明一维数组什么是随机存储结构？分别说明一维数组和二维数组都是随机存取结构。和二维数组都是随机存取结构。数据结构(Java版)(第3版)复习（Java版）（第3版） 5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储 1.采用二维数组存储矩阵是否具有随机存取特采用二维数组存储矩阵是否具有随机存取特性？有哪些矩阵需要压缩存储？为什么要压性？有哪些矩阵需要压缩存储？为什么要压缩？各采用怎样的压缩存储方式？各种压缩缩？各采用怎样的压缩存储方式？各种压缩存储方式是否具有随机存取特性？存储方式是否具有随机存取特性？2.有哪些特殊矩阵？特殊矩阵压缩存储的基本有哪些特殊矩阵？特殊矩阵
17、压缩存储的基本思想是什么？思想是什么？数据结构(Java版)(第3版)复习（Java版）（第3版） 矩阵的存储结构矩阵的存储结构 数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第6章章 树和二叉树树和二叉树目的：目的：理解树型结构；掌握链式存储结构表达理解树型结构；掌握链式存储结构表达 非线性结构，掌握递归算法设计。非线性结构，掌握递归算法设计。内容：内容：二叉树的定义、性质、存储结构，二叉链二叉树的定义、性质、存储结构，二叉链表表示的二叉树类；中序线索二叉树；表表示的二叉树类；中序线索二叉树；Huffman树；树的定义、存储结构和实现。树
18、；树的定义、存储结构和实现。要求：要求：理解树和二叉树概念，掌握树和二叉树的理解树和二叉树概念，掌握树和二叉树的表示和实现，掌握递归算法设计。表示和实现，掌握递归算法设计。重点：重点：二叉链表表示的二叉树类；二叉链表表示的二叉树类；Huffman树；树树；树的定义、存储结构和构造算法。的定义、存储结构和构造算法。难点：难点：链式存储结构表达非线性结构；递归算法链式存储结构表达非线性结构；递归算法 设计。设计。 实验：实验：树和二叉树的基本操作，链式存储结树和二叉树的基本操作，链式存储结构表示树和二叉树；递归算法。构表示树和二叉树；递归算法。6.1 树及其抽象数据类型树及其抽象数据类型 1.什么
19、是树？树结构与线性结构的区别是什么什么是树？树结构与线性结构的区别是什么？树与线性表有何关联？树与线性表有何关联？2.什么是有序树？什么是无序树？什么是有序树？什么是无序树？3.什么是结点的度？定义结点的度有何意义？什么是结点的度？定义结点的度有何意义？什么是树的度？什么是树的度？4.树中各结点的层次是如何定义的？结点的层树中各结点的层次是如何定义的？结点的层次有何意义？什么是树的高度？次有何意义？什么是树的高度？5.树有哪几种表示方法？各有何特点？树有哪几种表示方法？各有何特点？数据结构(Java版)(第3版)复习（Java版）（第3版） 6.2 二叉树二叉树 1.什么是二叉树？二叉树是不是
20、度为什么是二叉树？二叉树是不是度为2的树？的树？二叉树是不是度为二叉树是不是度为2的有序树？为什么？的有序树？为什么？2.什么是满二叉树？什么是完全二叉树？什么是满二叉树？什么是完全二叉树？ 数据结构(Java版)(第3版)复习（Java版）（第3版） 树和二叉树的存储结构树和二叉树的存储结构 数据结构(Java版)(第3版)复习（Java版）（第3版） 6.5 Huffman编码与编码与Huffman树树1.Huffman编码的特点是什么？有何作用？编码的特点是什么？有何作用？2.设一棵设一棵Huffman树有树有n0个叶子结点，该树共个叶子结点，该树共有多少个结点？为什么？有多少个结点？为
21、什么？【答答】2n0- -1。因为。因为Huffman树没有树没有1度结点，度结点，而而n0=n2+1，所以，所以n=n0+n2=2n0- -1。数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第7章章 图图目的：目的：学习非线性的复杂数据结构学习非线性的复杂数据结构图。图。内容：内容：图的概念、抽象数据类型、存储结构；图图的概念、抽象数据类型、存储结构；图 的深度和广度优先搜索遍历；最小生成树；的深度和广度优先搜索遍历；最小生成树； 最短路径。最短路径。要求：要求：掌握图的存储结构和操作实现。掌握图的存储结构和操作实现。重点：重点：图的两种
22、存储结构，两种遍历算法，最小图的两种存储结构，两种遍历算法，最小 生成树，最短路径。生成树，最短路径。难点：难点：图的存储和操作实现，最小生成树，最短图的存储和操作实现，最小生成树，最短 路径。路径。 实验：实验：图的建立与遍历，最小代价生成图的建立与遍历，最小代价生成 树，最短路径。树，最短路径。7.1 图及其抽象数据类型图及其抽象数据类型7.2 图的表示和实现图的表示和实现 1.什么是图？与线性表和树相比，图的特点是什么是图？与线性表和树相比，图的特点是什么？对图的操作主要有哪些？什么？对图的操作主要有哪些？2.图的存储结构有什么特点？仅用顺序表或单图的存储结构有什么特点？仅用顺序表或单链
23、表能否存储一个图？为什么？图的存储结链表能否存储一个图？为什么？图的存储结构主要有哪些？构主要有哪些？ 数据结构(Java版)(第3版)复习（Java版）（第3版） 图的存储结构图的存储结构 数据结构(Java版)(第3版)复习（Java版）（第3版） 7.3 图的遍历图的遍历 1.图的深度优先搜索遍历图的深度优先搜索遍历2.图的广度优先搜索遍历图的广度优先搜索遍历数据结构(Java版)(第3版)复习（Java版）（第3版） 7.4 最小生成树最小生成树 1.树是怎样的图？树是怎样的图？2.什么是图的生成树？什么是图的生成树？3.什么是生成树的代价？什么是生成树的代价？4.什么是图的最小生成树
24、？什么是图的最小生成树？ nPrim算法算法 nKruskal算法算法 数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构 （Java版）（第3版） 第第8章章 查找查找l目的：目的：查找算法设计。查找算法设计。内容：内容：顺序查找、折半查找、分块查找；散顺序查找、折半查找、分块查找；散 列表；二叉排序树。列表；二叉排序树。要求：要求：掌握查找的概念和多种查找算法设掌握查找的概念和多种查找算法设 计，学习根据不同情况选择合适的查计，学习根据不同情况选择合适的查 找算法，掌握提高查找效率采取的各找算法，掌握提高查找效率采取的各 种方法。种方法。重点：重点：顺序查找、折半查找、
25、分块查找；散顺序查找、折半查找、分块查找；散 列表；二叉排序树。列表；二叉排序树。 难点：难点：散列表；二叉排序树。散列表；二叉排序树。查找算法与查找结构查找算法与查找结构 数据结构(Java版)(第3版)复习（Java版）（第3版） 8.3 散列散列 1.什么是散列表？其与众不同的设计思想是什么是散列表？其与众不同的设计思想是什么？两个关键问题是什么？好的散列函什么？两个关键问题是什么？好的散列函数的标准是什么？为什么说冲突是不可避数的标准是什么？为什么说冲突是不可避免的？有哪些解决冲突的办法？免的？有哪些解决冲突的办法？数据结构(Java版)(第3版)复习（Java版）（第3版） 数据结构
26、 （Java版）（第3版） 第第9章章 排序排序目的：目的：排序算法研究。对于数据逻辑结构是线性表、存储排序算法研究。对于数据逻辑结构是线性表、存储 结构是顺序、操作是排序，体会各种不同算法实现。结构是顺序、操作是排序，体会各种不同算法实现。内容：内容：介绍插入、交换、选择、归并等多种经典排序算法，介绍插入、交换、选择、归并等多种经典排序算法， 讨论各种排序算法所适用的存储结构，以及比较各讨论各种排序算法所适用的存储结构，以及比较各 排序算法的性能。排序算法的性能。要求：要求：掌握直接插入、冒泡、直接选择等排序算法及其性能，掌握直接插入、冒泡、直接选择等排序算法及其性能， 理解希尔、快速、堆、归并等排序算法的设计思想及理解希尔、快速、堆、归并等排序算法的设计思想及 算法实现，熟悉提高算法性能的各种手段。算法实现，熟悉提高算法性能的各种手段。重点：重点：每种排序算法设计思想，算法表达，算法分析与性能评每种排序算法设计思想，算法表达，算法分析与性能评 价。价。难点：难点：希尔、快速、堆、归并等排序算法，性能较高算法的共希尔、快速、堆、归并等排序算法，性能较高算法的共 同特点。同特点。排序算法及其适用的存储结构排序算法及其适用的存储结构 数据结构(Java版)(第3版)复习（Java版）（第3版）
