算法基础

算法基础 1

第1章 算法的基本概念 1

1.1问题、算法和程序 1

1.2算法的效率和算法分析 2

1.3算法设计实例 6

习题一 11

第2章 递归 14

2.1递归的概念 14

2.2递归求解实例 18

2.3递归过程和递归工作栈 21

2.4递归算法的非递归实现 23

习题二 38

第3章 排序 40

3.1插入排序 41

3.2选择排序 42

3.3冒泡排序 42

3.4 Shell排序 45

3.5快速排序 46

3.6堆与堆排序 53

3.6.1堆在优先队列中的应用 54

3.6.2堆排序 57

3.7归并排序 59

3.8桶排序 61

3.8.1计数排序 62

3.8.2基数排序 63

3.9外排序 64

3.9.1 k路平衡归并 65

3.9.2初始归并段生成 68

习题三 70

第4章 集合和检索 73

4.1集合及其运算 73

4.2用有序链表表示的集合 75

4.3用树表示的集合 78

4.4线性表上的检索 82

4.5二叉检索树 89

4.6平衡二叉检索树 96

4.7散列 101

4.7.1散列表的检索 102

4.7.2用散列表存储集合 106

习题四 108

第5章 图的算法 111

5.1图在计算机中的表示 111

5.2图的遍历 116

5.3生成树和最小生成树 120

5.3.1普里姆（Prim）算法 120

5.3.2克鲁斯卡尔（Kruskal）算法 123

5.4最短路径 125

5.4.1求从某顶点到其他顶点的最短路径 125

5.4.2求所有顶点之间的最短路径 128

习题五 130

第6章 算法设计技术 133

6.1迭代法 133

6.2穷举搜索法 135

6.3递推法 138

6.4回溯法 140

6.5贪婪法 152

6.6分治法 158

6.7动态规划法 163

6.8图搜索 168

6.8.1求解方法概述 168

6.8.2图搜索算法 170

6.8.3图搜索A算法和A*算法 172

习题六 178

第7章 字符串匹配 182

7.1简单匹配 182

7.2 KMP算法 183

7.3 BM算法 186

7.4字符正则表达式匹配 187

习题七 195

第8章 索引技术 197

8.1索引结构 197

8.1.1线性索引 197

8.1.2倒排表 199

8.2多路搜索树 200

8.3 B树 202

8.4 B+树 209

习题八 212

参考文献 214

算法基础（6369）自学考试大纲 217

一、课程性质与设置目的 217

二、课程内容与考核目标 217

第1章 算法的基本概念 217

第2章 递归 218

第3章 排序 218

第4章 集合和检索 220

第5章 图的算法 220

第6章 算法设计技术 221

第7章 字符串匹配 222

第8章 索引技术 223

三、实践环节 223

四、有关说明与实施要求 224

附录 题型举例 227