数据结构复习提纲

1、作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 数据结构复习数据结构复习选择选择填空填空解答题（问答题）解答题（问答题）算法题算法题作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 数据结构复习数据结构复习复习原则复习原则1 理解理解各章基本概念（选择、填空）各章基本概念（选择、填空）2 存储结构：存储结构： 1）掌握基本存储结构（）掌握基本存储结构（ 表、栈、队列、二叉表、栈、队列、二叉树（顺序结构、链式结构（动态、静态）；树（顺序结构、链式结构（动态、静态）；存储信息、含义及存储信息、含义及C 语言描述）语言描述） 2）理解复杂存储结构（图

2、、树）理解复杂存储结构（图、树）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 数据结构复习数据结构复习3 算法算法 1）掌握基本算法及应用）掌握基本算法及应用 如：构造、销毁、插入、删除、遍历、查找、如：构造、销毁、插入、删除、遍历、查找、排序等，主要步骤、基本思想、主要操作的实现排序等，主要步骤、基本思想、主要操作的实现（C语言描述）语言描述） 2）复杂算法）复杂算法 掌握方法，能读懂程序（能填空；能写出主掌握方法，能读懂程序（能填空；能写出主要数据结构的变化状态）要数据结构的变化状态）4 会计算基本（简单）算法的时间复杂度。会计算基本（简单）算法的时间复杂度。作

3、者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第一章第一章 题型题型选择选择填空填空解答解答作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 数据结构和算法的有关概念数据结构和算法的有关概念数据结构数据结构数据的逻辑结构及分类数据的逻辑结构及分类数据的存储结构数据的存储结构抽象数据类型（抽象数据类型（ADT）算法算法算法的时间复杂度算法的时间复杂度 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 数据结构数据结构:带有结构和操作的数据元素集合。带

4、有结构和操作的数据元素集合。 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据操作的定义（功能）数据操作的定义（功能）数据操作的实现数据操作的实现( (在计算机上在计算机上) ) 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈、队列栈、队列树结构树结构图结构图结构 散列存储散列存储索引存储索引存储串及数组串及数组结构结构操作操作集合结构集合结构作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第二章 题型选择选择填空填空解答解答算法算法作

5、者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 线性表 线性表的概念、线性表的逻辑结构线性表的逻辑结构作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 线性表的存储和实现顺序存储结构顺序存储结构- -类型定义类型定义基本操作算法基本操作算法 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 线性表的存储和实现线性链表线性链表循环链表循环链表双向链表双向链表实现方式实现方式动态链表、静态链表动态链表、静态链表链表的类型定义链表的类型定义链表的基本操作算法链表的基本操作算法链表其它操作算法链表其它操作算法作者 (时间 2000

6、年）北京理工大学计算机科学工程系 秦怀青email typedef struct Lnode ElemType data; Struct Lnode *next;LNode, *LinkList;头指针头指针a ai ia a1 1a ai+1i+1a ai i-1 1a an nL L线性链表的类型定义线性链表的类型定义作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第三章第三章 题型题型 选择选择填空填空解答解答算法算法作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email

7、 3.1 3.1 栈栈栈的概念、特点栈的概念、特点栈的顺序存储结构和实现栈的顺序存储结构和实现栈的链式存储结构和实现栈的链式存储结构和实现 顺序栈、链式栈的类型定义顺序栈、链式栈的类型定义 顺序栈、链式栈的顺序栈、链式栈的基本操作算法基本操作算法作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 表达式求值（算符优先算法）表达式求值（算符优先算法）(方法方法)理解栈在递归函数执行过程中的作用理解栈在递归函数执行过程中的作用编写递归算法编写递归算法 栈的应用栈的应用作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 队列队列队列的概念、特点队列的概念、

8、特点循环队列循环队列链式队列链式队列 循环队列、链式队列的类型定义循环队列、链式队列的类型定义 循环队列、链式队列的循环队列、链式队列的基本操作算法基本操作算法作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第五章第五章 题型题型选择选择填空填空解答解答算法算法作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 5.1 5.1 数数 组组 ( (选择、填空、解答选择、填空、解答) )数组的逻辑结构数组的逻辑结构数组的基本操作数组的基本操作数组的存储方法数组的存储方法多维数组

9、元素存储地址的计算多维数组元素存储地址的计算(低下标优先低下标优先)0 1 n-1 n n+1 2n-1 mn-10 1 n-1 n n+1 2n-1 mn-1a a00 00 a a01 01 a a0n-1 0n-1 a a10 10 a a11 11 a a1n-1 1n-1 a am-10 m-10 a am-11 m-11 a am-1n-1m-1n-1作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 5.2. 5.2.矩阵的压缩存储矩阵的压缩存储特殊矩阵的概念特殊矩阵的概念特殊矩阵的压缩存储方法（对称矩阵）特殊矩阵的压缩存储方法（对称矩阵）稀疏矩阵的概念稀疏

10、矩阵的概念稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法三元组顺序表三元组顺序表作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 矩阵快速转置算法矩阵快速转置算法numcol： 存储存储M第第col列非零元个数列非零元个数cpotcol： 存储存储M第第col列第一个非零元在列第一个非零元在T.data中中的位置的位置作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 5.3 5.3 广义表广义表广义表的概念广义表的概念广义表的存储广义表的存储（方法）方法） 头尾链表头尾链表存储结构存储结构广义表的递归算法广义表的递归算法 复制广义表复制广义表 Co

11、pyGList(T,L)CopyGList(T,L) 求广义表的深度求广义表的深度GListDepth(L)GListDepth(L) 判广义表相等判广义表相等作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第六章第六章 题型题型选择选择填空填空解答解答算法算法作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 二叉树二叉树 ( (选择、填空、问答选择、填空、问答) )二叉树的二叉树的概念概念二叉树的性质二叉树的性质作者 (时间 2000年）北京理工大学计算机科学工程系 秦

12、怀青email 二叉树存储二叉树存储 二叉树的的顺序存储二叉树的的顺序存储 (方法方法)二叉树的链式存储二叉树的链式存储 (方法、类型定义方法、类型定义)作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 二叉树的遍历（方法、算法）二叉树的遍历（方法、算法） 先序、中序、后序遍历（方法）先序、中序、后序遍历（方法） 按层遍历（方法、算法）按层遍历（方法、算法） 二叉树的递归算法二叉树的递归算法 1 1、查询二叉树中某个结点、查询二叉树中某个结点2 2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数3 3、求二叉树的深度、求二叉树的深度4 4、复制二叉树、复制二叉树

13、作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 线索二叉树线索二叉树概念概念 使用使用 (遍历方法）遍历方法）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 树树基本概念基本概念 ( (选择、填空选择、填空) )作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 树的存储和树的遍历树的存储和树的遍历双亲表示法双亲表示法 (方法）方法）孩子链表表示法孩子链表表示法 (方法）方法）孩子兄弟表示法孩子兄弟表示法 (方法）方法）森林与二叉树的对应关系森林与二叉树的对应关系 (方法）方法）先根（序）遍历：先访问树的根结点，然后依次

14、先根遍先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树。历根的每棵子树。后根（序）遍历：先依次后根遍历每棵子树，然后访问后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点。根结点。按层次遍历：先访问第一层上的结点，然后依次遍历第按层次遍历：先访问第一层上的结点，然后依次遍历第二层，二层，第第h层的结点层的结点。(方法）方法）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 哈夫曼树与哈夫曼编码（方法）哈夫曼树与哈夫曼编码（方法）哈夫曼树（最优二叉树）的概念哈夫曼树（最优二叉树）的概念构造哈夫曼树构造哈夫曼树( (方法、读懂算法）方法、读懂算法）哈夫曼编

15、码哈夫曼编码( (方法）方法）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第七章第七章 题型题型选择选择填空填空解答解答算法算法注意注意: 关键路径不考关键路径不考,以以ppt为准为准作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 图的概念与术语图的概念与术语图的存储结构及特点图的存储结构及特点图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示（方法）存储表示（方法）图的邻接表存储表示（方法）图的邻接表存储表示（方法）图的遍历（能读懂算法、方法）图的遍历（能读懂算

16、法、方法）图的深度遍历（图的深度遍历（DFSDFS）图的广度遍历（图的广度遍历（BFSBFS）图的最小生成树（方法）图的最小生成树（方法）普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法有向无环图有向无环图拓扑排序（读懂算法、方法）拓扑排序（读懂算法、方法）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 基本概念（选择、填空、问答）基本概念（选择、填空、问答）静态查找表、动态查找表静态查找表、动态查找表查找查找也叫检索，是根据给定的某个值，在也叫检索，是根据给定的某个值，在表中确定一个关键字等于

17、给定值的记录。表中确定一个关键字等于给定值的记录。查找方法评价查找方法评价查找速度查找速度占用存储空间多少占用存储空间多少平均查找长度平均查找长度 ASL(Average Search Length)1niASLPiCi作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 顺序表的查找：顺序查找顺序表的查找：顺序查找算法算法有序表的查找：折半查找有序表的查找：折半查找算法算法静态查找表（选择、填空、静态查找表（选择、填空、算法）算法）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 概念概念查找算法查找算法（编程）（编程）插入操作插入操作（方法）（方

18、法）删除操作删除操作（方法）（方法） 动态查找表动态查找表二叉排序树二叉排序树作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 概念概念平衡二叉树的构造平衡二叉树的构造平衡处理平衡处理（方法）（方法）平衡二叉排序树平衡二叉排序树作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 概念概念查找操作查找操作（方法）（方法）插入操作插入操作结点分裂结点分裂（方法）（方法）删除操作删除操作结点合并结点合并（方法）（方法） B- B-树（方法）树（方法）作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 概念（哈希函数、哈希地址、冲突）概念（哈希函数、哈希地址、冲突）处理冲突的处理冲突的方法方法哈希表构造与查找哈希表构造与查找（方法）（方法） 哈希表（散列表）哈希表（散列表） （方法）（方法）作者 (时间 2000年）