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