数据结构导论复习与考试指导

第一章 概论 1

1.1 本章内容概述及学习方法 1

1.2 数据结构课程的作用、特点及学习方法 1

1.2.1 数据结构课程在计算机专业中的作用 1

1.2.2 数据结构课程的主要内容和特点 3

1.2.3 数据结构课程的学习方法 3

1.3 本章内容学习和辅导 4

1.3.1 有关概念的理解 4

1.3.2 算法描述及分析 6

1.4 复习题 8

第二章 线性表 9

2.1 本章内容概述及学习方法 9

2.1.1 内容简介 9

2.2.1 线性表的定义 10

2.2 线性表的定义和运算 10

2.1.2 学习方法建议 10

2.2.2 线性表的运算 11

2.3 线性表的顺序表存储结构 12

2.3.1 顺序存储结构 12

2.3.2 顺序表运算讨论的实现 13

2.3.3 顺序表的应用 16

2.4 链表 24

2.4.1 链表结构 24

2.4.2 链表运算实现 27

2.4.3 其他形式的链表结构 40

2.5 串 41

2.5.1 串的定义和运算 41

2.5.2 串的存储 42

3.1.1 定义和运算 44

3.1 栈 44

第三章 栈、队列和数组 44

3.1.2 顺序栈 45

3.1.3 链栈 47

3.2 队列 47

3.2.1 定义和运算 47

3.2.2 顺序队列 48

3.2.3 链队列 51

3.3 数组 53

3.3.1 数组的定义和运算 53

3.3.2 数据组顺序存储 54

3.3.3 矩阵的压缩存储 55

第四章 树 57

4.1 本章内容概述 57

4.1.1 本章知识点概述 57

4.1.2 树结构的有关概念 58

4.1.3 二叉树的有关概念、性质及存储结构 59

4.2 重点、难点分析 64

4.2.1 二叉树的遍历 64

4.2.2 树和森林 76

4.2.3 哈夫曼树 83

第五章 图 89

5.1 本章内容概述及学习方法 89

5.1.1 引方 89

5.1.2 本章学习方法 89

5.2 基础知识 90

5.2.1 基本概念 90

5.2.2 图的存储结构 92

5.3 图的遍历算法及其应用 95

5.3.1 深度优先搜索遍历算法及其应用 95

5.3.2 广度优先搜索遍历算法及其应用 101

5.4 图的应用 105

5.4.1 最小生成树 106

5.4.2 最短路径 110

5.4.3 拓扑排序 114

第六章 查找表 117

6.1 本章内容概述及学习方法 117

6.1.1 概述 117

6.1.2 基本概念 117

6.1.3 学习方法 118

6.2 顺序表的查找 118

6.2.1 简单顺序查找 118

6.2.2 有序表的二分查找 119

6.2.3 索引顺序表的查找 122

6.3.1 二叉排序树及其查找 123

6.3 二叉排序的查找 123

6.3.2 二叉排序树的构造和插入 124

6.4 散列表的查找 126

6.4.1 哈希表的有关概念 126

6.4.2 哈希函数的构造方法 126

6.4.3 处理冲突的方法 127

6.4.4 散列表的查找 129

第七章 文件 131

7.1 概述 131

7.1.1 文件的逻辑结构 131

7.1.2 文件的运算 131

7.1.3 文件的存储介质 132

7.2 常见文件组织形式 132

7.2.3 ISAM文件 133

7.2.4 VSAM文件 133

7.2.1 顺序文件 133

7.2.2 索引文件 133

7.2.5 散列文件 134

7.2.6 多关键字文件 134

7.3 本章思考题 134

第八章 排序 135

8.1 本章内容概述及学习方法 135

8.1.1 概述 135

8.1.2 排序及其分类 135

8.1.3 排序算法分析指标 136

8.1.4 本章的学习方法 136

8.2 直接插入排序 136

8.3 交换排序 138

8.3.1 冒泡排序 138

8.3.2 快速排序 140

8.4.1 直接选择排序 144

8.4 选择排序 144

8.4.2 堆排序 145

8.5 归并排序 150

8.5.1 归并 150

8.5.2 归并排序 151

附录一 模拟试卷 152

模拟试卷一 152

模拟试卷二 155

模拟试卷三 158

模拟试卷四 162

附录二 模拟试卷解析 165

模拟试卷一解析 165

模拟试卷二解析 173

模拟试卷三解析 180

模拟试卷四解析 187

参考文献 192